[]{}

# Efficient Submodular Optimization under Noise: Local Search is Robust

Lingxiao Huang<EMAIL_ADDRESS>Huawei TCS Lab $\to$ Nanjing
University. Yuyi Wang<EMAIL_ADDRESS>Swiss Federal Institute of
Technology. Chunxue Yang<EMAIL_ADDRESS>Nanyang Technological
University. Huanjian Zhou<EMAIL_ADDRESS>The University of Tokyo.

###### Abstract

The problem of monotone submodular maximization has been studied extensively
due to its wide range of applications. However, there are cases where one can
only access the objective function in a distorted or noisy form because of the
uncertain nature or the errors involved in the evaluation. This paper
considers the problem of constrained monotone submodular maximization with
noisy oracles introduced by [11]. For a cardinality constraint, we propose an
algorithm achieving a near-optimal
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation guarantee (for
arbitrary $\varepsilon>0$) with only a polynomial number of queries to the
noisy value oracle, which improves the exponential query complexity of [20].
For general matroid constraints, we show the first constant approximation
algorithm in the presence of noise. Our main approaches are to design a novel
local search framework that can handle the effect of noise and to construct
certain smoothing surrogate functions for noise reduction.

###### Contents

  1. 1 Introduction
    1. 1.1 Our contributions
    2. 1.2 Related work
  2. 2 The model
  3. 3 Local search with approximate evaluation oracles to auxiliary functions
  4. 4 Our algorithms and main theorems for cardinality constraints
    1. 4.1 Algorithmic results for cardinality constraints when $r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap O\left(n^{\frac{1}{3}}\right)$
      1. 4.1.1 Useful notations and useful facts for Theorem 4.1
      2. 4.1.2 Algorithm for Theorem 4.1
      3. 4.1.3 Proof of Theorem 4.1
    2. 4.2 Algorithmic results for cardinality constraints when $r\in\Omega\left(n^{\frac{1}{3}}\right)$
      1. 4.2.1 Useful notations and useful facts for Theorem 4.16
      2. 4.2.2 Algorithm for Theorem 4.16
      3. 4.2.3 Proof of Theorem 4.16
  5. 5 Our algorithms and main theorems for general matroid constraints
    1. 5.1 Algorithmic results for matroid constraints with rank $r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap O\left(n^{\frac{1}{3}}\right)$
      1. 5.1.1 Useful notations and useful facts for Theorem 5.1
      2. 5.1.2 Algorithm for Theorem 5.1
      3. 5.1.3 Proof of Theorem 5.1
    2. 5.2 Algorithmic results for matroid constraints with rank $r\in\Omega\left(n^{\frac{1}{3}}\right)$
      1. 5.2.1 Useful facts for Theorem 5.7
      2. 5.2.2 Algorithm for Theorem 5.7
      3. 5.2.3 Proof of Theorem 5.7
  6. 6 Discussions
  7. 7 Conclusions
  8. A The Invalid Result for General Matroid Constraints in [20]
  9. B More Related Work
  10. C Approximation algorithm for strongly base-orderable matroid constraints
    1. C.1 Algorithm for Theorem C.2
    2. C.2 Proof of Theorem C.2

##  1 Introduction

Consider the following problems in machine learning and operations research:
(1) selecting a set of locations to open up facilities with the goal of
maximizing their overall user coverage [15]; (2) reducing the number of
features in a machine learning model while retaining as much information as
possible [23]; and (3) identifying a small set of seed nodes that can achieve
the largest overall influence in a social network [14]. Solving these problems
all involves maximizing a monotone _submodular_ set function
$f:2^{N}\mapsto\mathbb{R}$ subject to certain constraints. Intuitively,
submodularity captures the property of diminishing returns. For example, a
newly opened facility will contribute less to the overall user coverage if we
have already opened many facilities and more if we have only opened a few.
Although the general problem of monotone submodular maximization subject to a
cardinality or general matroid constraint is NP-hard [5], the greedy
algorithm, which selects an element with the largest margin at each step, can
approximately solve this problem under a cardinality constraint by a factor of
$1-1/e$, and this approximation ratio is tight [18]. Moreover, a non-oblivious
local search algorithm, which iteratively alters one element to improve an
auxiliary objective function, is guaranteed to achieve an approximation ratio
of $1-1/e$ for general matroid constraints [7].

In the literature, the submodular optimization problem usually assumes a
_value oracle_ to the objective function $f$, which means one is allowed to
query the _exact_ value of $f(S)$ for any $S\subseteq N$. However, in many
applications, due to the uncertain nature of the objective or the errors
involved in the evaluation, one can only access the function value in a
distorted or noisy form. For example, [9] pointed out that selecting features
to construct a robust learning model is particularly important in domains with
non-stationary feature distributions or input sensor failures. It is known
that without any assumption on the noise, direct adaptions of the greedy and
local search methods mentioned above may yield arbitrarily poor performance
[12]. To address this issue, [11] introduced and studied the following problem
of _monotone submodular maximization under noise_ : For a monotone submodular
function $f$, given a noisy value oracle $\tilde{f}$ satisfying
$\tilde{f}(S)=\xi_{S}f(S)$ for each set $S\subseteq N$, where the noise
multiplier $\xi_{S}$ is independently drawn from a certain distribution, the
goal is to find a set $S$ maximizing $f(S)$ under certain constraints. Some
applications of this problem are provided in [20] such as revealed preference
theory [3] and active learning [6]. [11] showed that under a sufficiently
large cardinality constraint, a variant of the greedy algorithm achieves a
near-optimal approximation ratio of $1-\frac{1}{e}-O(\varepsilon)$ for
arbitrary $\varepsilon>0$. The problem becomes more challenging when the
cardinality constraint is relatively small since there is less room for
mistakes. In a subsequent work, [20] developed another greedy-based algorithm
for small cardinality constraints and showed a near-tight approximation
guarantee.

Despite these encouraging results, we want to point out two directions along
this line of monotone submodular maximization under noise that still have room
for improvements:

  * •

In the algorithm from [20], the query complexity to the noisy value oracle is
exponential in $\varepsilon^{-1}$, which is costly when a near-optimal
solution is needed, i.e., when the parameter $\varepsilon$ is close to $0$. Is
it possible to obtain near-optimal approximations for monotone submodular
maximization under cardinality constraints with the number of queries
polynomial in $\varepsilon^{-1}$?

  * •

All previous works in submodular maximization under noise consider only the
cardinality constraint, and no approximation guarantee is known under other
constraints. 111Note that [20] also provide an algorithm to deal with general
matroid constraints. However, we will argue in Section A that their algorithm
fails to obtain the approximation guarantee they claim. Is there any algorithm
that can achieve a constant approximation for submodular maximization under
noise for more general constraints, such as commonly studied matroid
constraints [16, 26]?

In this paper, we provide answers to both questions above.

###  1.1 Our contributions

We study the problem of constrained monotone submodular maximization under
noise (Problem 2.6). Following prior works [11, 20], we assume generalized
exponential tail noises (Definition 2.5) and consider the solutions subject to
cardinality constraints (Definition 2.2) and matroid constraints (Definition
2.3). The main contribution of this work is to show that for optimizing a
monotone submodular function under a cardinality constraint,
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximations can be obtained
with high probability by querying the noisy oracle only
$\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ times.

######  Theorem 1.1 (Informal, see Theorems 4.1 and 4.16).

Let $\varepsilon>0$ and assume $n$ is sufficiently large. For any
$r\in\Omega\left(\frac{1}{\varepsilon}\right)$, there exists an algorithm that
returns a $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation for the
monotone submodular maximization problem under a $r$-cardinality constraint,
with probability $1-o(1)$ and query complexity
$\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ to $\tilde{f}$.

For a cardinality constraint, this paper and prior works [11, 20] all achieve
near-optimal approximations. However, our result is applicable for a larger
range $\Omega\left(\frac{1}{\varepsilon}\right)$ of cardinalities than
$\Omega\left(\log\log n\cdot\varepsilon^{-2}\right)$ in [11]. Moreover, we
only require $\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ queries to the
noisy value oracle, which improves the query complexity
$\Omega(n^{\frac{1}{\varepsilon}})$ of [20]. Our main idea to address this
problem is to employ a local search procedure, whereas prior methods are all
variants of the greedy algorithm. Intuitively, local search is more robust
than the greedy since the marginal functions are more sensitive to noise than
the value functions. To achieve a sufficient gain in each iteration, the
greedy algorithm must identify the element with maximum margin. In contrast,
local search only needs to estimate the sets’ values. This is why we can
improve the query complexity to
$\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ for small cardinality
constraints.

We present a unified framework (Algorithm 1) for enhancing the local search to
cope with noise. One of the main differences between our framework and the
non-oblivious local search proposed by [7] is that we use an approximation of
the auxiliary function (Definition 3.2) rather than the exact one due to the
presence of noise. We analyze the impact of the inaccuracies on the
approximation performance and query complexity of the local search (Theorem
3.3). Another difference is the construction of the auxiliary functions used
to guide the local search. We construct the auxiliary function not based on
the objective function but on smoothing surrogate functions. A surrogate
function $h$ needs to meet two properties: (i) $h$ should depend on an
averaging set of size $\mathrm{poly}(n)$, such that $h(S)$ and its noisy
analogue $\tilde{h}(S)$ are close for all sets $S$ considered by local search;
(ii) $h$ needs to be close to the original function $f$, such that optimizing
$h$ can yield a near-optimal solution to optimizing $f$. However, a large
averaging set is more likely to induce a large gap between the surrogate and
original function, making simultaneous fulfillment of both properties non-
trivial. In this paper we carefully design the smoothing surrogate functions
as follows. For a set with size
$r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap O\left(n^{1/3}\right)$, we
define the smoothing surrogate function $h$ as the expectation of $f$’s value
when a random element in $N$ is added to the set (Definition 4.2). This
surrogate function is robust for a relatively small cardinality as it is based
on a rather large averaging set with size nearly $n$, but too concentrated for
a large cardinality close to $n$. Thus, we consider another smoothing
surrogate function $h_{H}$ for size $r\in\Omega\left(n^{1/3}\right)$, defined
as the average value combined with all subsets of a certain small-size set $H$
(Definition 4.17). The auxiliary functions constructed on both smoothing
surrogates are shown to have almost accurate approximations (Lemma 4.4 and
4.19). Consequently, we can apply our unified local search framework
(Algorithm 1) in both cases (Algorithm 3 and 5), and guarantee to achieve
nearly tight approximate solutions (Theorem 4.1 and 4.16). The other
contribution of this paper is a constant approximation result for maximizing
monotone submodular functions with noisy oracles under general matroid
constraints.

######  Theorem 1.2 (Informal, see Theorems 5.1 and 5.7).

Let $\varepsilon>0$ and assume $n$ is sufficiently large. For any
$r\in\Omega\left(\varepsilon^{-1}\log(\varepsilon^{-1})\right)$, there exists
an algorithm that returns a
$\left(\frac{1}{2}\left(1-\frac{1}{e}\right)-O(\varepsilon)\right)$-approximation
for the monotone submodular maximization problem under a matroid constraint
with rank $r$, with probability $1-o(1)$ and query complexity at most
$\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ to $\tilde{f}$.

To the best of our knowledge, this is the first result showing that constant
approximation guarantees are obtainable under general matroid constraints in
the presence of noise. To cope with noise, one common approach for cardinality
constraints is to incorporate some extra elements to gain robustness and
include these elements in the final solutions. However, for a matroid,
additional elements may undermine the independence of a set. To address this
difficulty, we develop a technique for comparing the values of independent
sets in the presence of noise, which allows us to select either the local
search solutions or the additional elements for robustness and leads to an
approximation ratio of $\frac{1}{2}\left(1-\frac{1}{e}\right)$.

###  1.2 Related work

Research has been conducted on monotone submodular maximization in the
presence of noise. We say a noisy oracle is inconsistent if it returns
different answers when repeatedly queried. For inconsistent oracles, noise
often does not present a barrier to optimization, since concentration
assumptions can eliminate the noise after a sufficient number of queries [21,
13]. When identical queries always obtain the same answer, the problem becomes
more challenging. Aside from the i.i.d noise adopted in [11, 20] and this
paper, [12] study submodular optimization under noise adversarially generated
from $[1-\varepsilon/r,1+\varepsilon/r]$, where the greedy algorithm achieves
a ratio of $1-1/e-O(\varepsilon)$. No algorithm can obtain a constant
approximation if noise is not bounded in this range.

##  2 The model

This section formally defines our model (Problem 2.6) of maximizing a monotone
submodular function (Definition 2.1) under a cardinality constraint
(Definition 2.2) or a matroid constraint (Definition 2.3), given access to a
noisy value oracle (Definition 2.4). Let $N$ be the ground set with size
$|N|=n$, and we use the shorthands $S+x=S\cup\\{x\\}$ and
$S-x=S\backslash\\{x\\}$ throughout this paper. We first review the definition
of monotone submodular functions.

######  Definition 2.1 (Monontone submodular functions).

A function $f:2^{N}\to\mathbb{R}_{\geq 0}$ is monotone submodular if 1)
(monotonicity) $f(A)\leq f(B)$ for any $A\subseteq B\subseteq N$; 2)
(submodularity) for any subset $A,B\subseteq N$ and $x\in N$: $f(A+x)-f(A)\geq
f(B+x)-f(B)$.

There are various examples of monotone submodular functions in optimization,
such as budget additive functions, coverage functions, cut functions and rank
functions [1]. Since the description of a submodular function may be
exponential in the size $N$, we usually assume access of a _value oracle_ that
answers $f(S)$ for each $S\subseteq N$. Let $\mathcal{I}$ denote a collection
of feasible subsets $S\subseteq N$. The goal of a constrained monotone
submodular maximization is to find a subset $S\subseteq\mathcal{I}$ to
maximize $f(S)$. The objective $f$ is further assumed to be normalized, i.e.,
$f(\varnothing)=0$. We consider two types of constraints in our models:
cardinality constraints and matroid constraints.

######  Definition 2.2 (Cardinality constraints).

Given a ground set $N$ and an integer $r\geq 1$, a cardinality constraint is
of the form $\mathcal{I}(r)=\\{S\subseteq N:|S|\leq r\\}$.

######  Definition 2.3 (Matroids and Matroid constraints).

Given a ground set $N$, a matroid $\mathcal{M}$ is represented by an ordered
pair $(N,\mathcal{I}(\mathcal{M}))$ satisfying that 1)
$\varnothing\in\mathcal{I}(\mathcal{M})$; 2) If $I\in\mathcal{I}(\mathcal{M})$
and $I^{\prime}\subseteq I$, then $I^{\prime}\in\mathcal{I}(\mathcal{M})$; 3)
If $I_{1},I_{2}\subseteq\mathcal{I}(\mathcal{M})$ and $|I_{1}|<|I_{2}|$, then
there must exist an element $e\in I_{2}\setminus I_{1}$ such that
$I_{1}\cup\\{e\\}\in\mathcal{I}(\mathcal{M})$. Each
$I\in\mathcal{I}(\mathcal{M})$ is called an independent set. The maximum size
of an independent set is called the rank of $\mathcal{M}$. We call the
collection $\mathcal{I}(\mathcal{M})$ a matroid constraint.

Assume we are given a _membership oracle_ of $\mathcal{I}(\mathcal{M})$ that
for any set $S\subseteq N$ answers whether $S\in\mathcal{I}(\mathcal{M})$. As
a widely used combinatorial structure, there is an extensive study on matroids
[28, 19, 27]. Common matroids include uniform matroids, partition matroids,
regular matroids, etc. See [19] for more discussions. Specifically, a uniform
matroid constraint is equivalent to a cardinality constraint, implying that
cardinality constraints are a special case of matroid constraints.

##### Noisy value oracle.

It is well known that given an exact value oracle to $f$, for any
$\varepsilon>0$, there exists a randomized $(1-1/e-\varepsilon)$-approximate
algorithm for the submodular optimization problem under a matroid constraint,
i.e., $\max_{S\subseteq\mathcal{I}}f(S)$ [2, 7]. However, as discussed
earlier, the value oracle of $f$ may be imperfect, and we may only have a
noisy value oracle $\tilde{f}$ instead of $f$. We consider the following noisy
value oracle that has also been investigated in [12, 11].

######  Definition 2.4 ((Multiplicative) noisy value oracle [11]).

We call $\tilde{f}:2^{N}\to\mathbb{R}_{\geq 0}$ a (multiplicative) noisy value
oracle of $f$, if there exists some distribution $\mathcal{D}$ s.t. for any
$S\subseteq N$, $\tilde{f}(S)=\xi_{S}f(S)$ where $\xi_{S}$ is i.i.d. drawn
from $\mathcal{D}$.

Throughout this paper, we consider a general class of noise distributions,
called generalized exponential tail distributions, defined in [20].

######  Definition 2.5 (Generalized exponential tail distributions [20]).

A noise distribution $\mathcal{D}$ has a generalized exponential tail if there
exists some $x_{0}$ such that for every $x>x_{0}$ the probability density
function $\rho(x)=e^{-g(x)}$, where $g(x)=\sum_{i}c_{i}x^{\gamma_{i}}$ for
some (not necessarily integers)
$\gamma_{0}\geq\gamma_{1}\geq\dots,s.t.\gamma_{0}\geq 1$ and $c_{0}>0$. If
$\mathcal{D}$ has bounded support we only require that either it has an atom
at its supremum or that $\rho$ is continuous and non-zero at the supremum.

W.l.o.g., we assume $\mathbb{E}[\mathcal{D}]=1$.222Otherwise, we can scale
$\mathcal{D}$ to be
$\mathcal{D}^{\prime}=\mathcal{D}/\mathbb{E}[\mathcal{D}]=1$. As mentioned in
[20], the class of generalized exponential tail distributions contains
Gaussian distributions, exponential distributions, and all distributions with
bounded support that is independent of $n$.

##### The model.

We are ready to propose the main problem, which has already been considered in
[11, 20].

######  Problem 2.6 (Constrained submodular optimization under noise).

Given a noisy value oracle $\tilde{f}:2^{N}\to\mathbb{R}_{\geq 0}$ (with a
certain generalized exponential tail distribution $\mathcal{D}$) to an
underlying monotone submodular function $f$, and a cardinality constraint
$\mathcal{I}=\mathcal{I}(r)$ or a matroid constraint
$\mathcal{I}=\mathcal{I}(\mathcal{M})$, the goal is to find
$S\subseteq\mathcal{I}$ to maximize $f(S)$.

##  3 Local search with approximate evaluation oracles to auxiliary functions

This section proposes a non-oblivious local search framework with a noisy
value oracle (Algorithm 1), and gives an analysis (Theorem 3.3) of its
performance. This algorithm is a generalization of that in [7] and will be
used as a meta-algorithm for solving Problem 2.6 in Sections 4 and 5. Roughly
speaking, a local search framework first constructs a "good" initial solution
via a standard greedy algorithm and then iteratively improves the solution
w.r.t. to an auxiliary function (Definition 3.1) by swapping an element at
each step. The following auxiliary function proposed by [7] is a linear
combination of the original function over all subsets.

######  Definition 3.1 (Auxiliary function [7]).

Given a monotone submodular function $h:2^{N}\to\mathbb{R}_{\geq 0}$, its
auxiliary function $\varphi_{h}:2^{N}\to\mathbb{R}_{\geq 0}$ is defined as
$\varphi_{h}(S)=\sum_{T\subseteq S}m_{|S|-1,|T|-1}\cdot h(T)$, where
$m_{s,t}=\int_{0}^{1}e^{p}(e-1)^{-1}p^{t}(1-p)^{s-t}dp$ for all $s\geq t\geq
0$.

We use $h$ instead of $f$ because we may do local search on certain smoothing
surrogate function $h$ of $f$ (see examples in Definitions 4.2 and 4.17). Note
that $\varphi_{h}$ is also a monotone submodular function. Given an exact
value oracle of $\varphi_{h}$ and a matroid constraint
$\mathcal{I}(\mathcal{M})$, [7] show that there exists a local search
algorithm that outputs a $(1-1/e)$-approximate solution for the optimization
problem $\max_{S\subseteq\mathcal{I}(\mathcal{M})}h(S)$. However, as mentioned
before, we do not have an exact value oracle of $h$. Thus, it may not be
possible to construct an exact value oracle of $\varphi_{h}$. To understand
how these inaccuracies can affect the performance of the local search
algorithm, we introduce the following approximation for the auxiliary function
$\varphi_{h}$.

######  Definition 3.2
($(\alpha,\delta,\mathcal{I}(\mathcal{M}))$-approximation of $\varphi_{h}$).

Given an auxiliary function $\varphi_{h}$, a matroid constraint
$\mathcal{I}(\mathcal{M})$ and constants $\alpha,\delta>0$, we say a
randomized function $\widehat{\varphi_{h}}$ is an
$(\alpha,\delta,\mathcal{I}(\mathcal{M}))$-approximation of $\varphi_{h}$ if
for any independent set $A\in\mathcal{I}(\mathcal{M})$,

$\mathbb{P}\left[\left|\widehat{\varphi_{h}}(A)-\varphi_{h}(A)\right|>\alpha\cdot\max_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)\right]\leq\delta.$

Intuitively, $\widehat{\varphi_{h}}$ is a randomized version of $\varphi_{h}$
with an additive concentration guarantee, where the randomness may come from
noise of $h$ or sampling error for estimating $\varphi_{h}$. As
$\alpha,\delta$ tend to 0, $\widehat{\varphi_{h}}$ is a better approximation
of $\varphi_{h}$. Specifically, when $\alpha=\delta=0$ and
$\mathcal{I}=2^{N}$, $\widehat{\varphi_{h}}$ is exactly equivalent to
$\varphi_{h}$. Now we are ready to provide our local search framework
(Algorithm 1), which is a generalization of [7, Algorithm 2]. The main
difference is that we use an approximation $\widehat{\varphi_{h}}$ instead of
$\varphi_{h}$ for evaluation at each greedy step (Line 4) and local search
step (Line 12). The performance of Algorithm 1 is summarized in Theorem 3.3.

Input : A matroid constraint $\mathcal{I}(\mathcal{M})$ of rank $r\geq 1$, a
value oracle to an $(\alpha,\delta,\mathcal{I}(\mathcal{M}))$-approximation
$\widehat{\varphi_{h}}$ of $\varphi_{h}$, a stepsize $\Delta\in(0,1/2)$.

1 Set
$I\leftarrow\left\lceil\log_{1+\Delta}\left(\frac{2(1+\alpha)}{1-2(r+1)\alpha}\right)\right\rceil$

2 Initialize: $U_{0}\leftarrow\varnothing$, $i=1$

3 while  _$i\leq r$_ do

4
$u_{i}\leftarrow\mathop{\arg\max}_{e:U_{i-1}+e\in\mathcal{I}(\mathcal{M})}\widehat{\varphi_{h}}(U_{i-1}+e)$

5 $U_{i}\leftarrow U_{i-1}+u_{i}$

6 $i\leftarrow i+1$

7

$S_{0}\leftarrow U_{r}$

$\triangleright$ Initial solution by greedy

8 for  _$i=0$ to $I-1$_ do $\triangleright$ Local search for $I$ iterations

9 for  _each element $x\in S_{i}$ and $y\in N\setminus S_{i}$_ do

10 $S^{\prime}_{i}\leftarrow S_{i}-x+y$

11 if  _$S_{i}^{\prime}\in\mathcal{I}(\mathcal{M})$_ then

12 if
_$\widehat{\varphi_{h}}(S^{\prime}_{i})\geq(1+\Delta)\cdot\widehat{\varphi_{h}}(S_{i})$_
then $\triangleright$ An improved solution $S_{i}^{\prime}$ was found

13 $S_{i+1}\leftarrow S^{\prime}_{i}$

14 break and continue to the next iteration of $i$

15

16

17

return $S_{I}$

Algorithm 1 Noisy local search
(NLS($\widehat{\varphi_{h}},\mathcal{I}(\mathcal{M}),\Delta$))

######  Theorem 3.3 (Performance of noisy local search).

Let $I=\log_{1+\Delta}\left(\frac{2(1+\alpha)}{1-2(r+1)\alpha}\right)$. With
probability at least $1-(I+1)rn\delta$, the output $S_{I}$ of Algorithm 1 is a
$\left(1-\frac{1}{e}\right)\left(1-r\ln(er)\left((2+\Delta)\alpha+\Delta\right)\right)$-approximate
solution for problem $\max_{S\subseteq\mathcal{I}(\mathcal{M})}h(S)$, with at
most $\left(I+1\right)rn$ calls to $\widehat{\varphi_{h}}$.

Roughly, given a nearly accurate approximation $\widehat{\varphi_{h}}$, we can
show that the initial solution $S_{0}$ is likely to be a constant
approximation for $\max_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$ (Lemma
3.4). This guarantees that we will reach a local optimal solution w.r.t.
$\varphi_{h}$ in $I$ iterations with high probability (Claim 3.6). Then
combining with basic properties of $\varphi_{h}$ shown in [7] and the fact
that $\widehat{\varphi_{h}}$ is "close" to $\varphi_{h}$, we obtain Theorem
3.3.

###### Proof.

We first analyze the query complexity to $\widehat{\varphi_{h}}$ and then
prove the approximate ratio together with the success probability.

##### Query complexity of Algorithm 1.

For any $i\in[r]$, define
$\mathcal{U}_{i}:=\\{U_{i-1}+e\in\mathcal{I}(\mathcal{M}):e\in N\backslash
U_{i-1}\\}$ to be the collection of subsets considered in Line 4. For any
$i=0,1\cdots,I-1$, define
$\mathcal{U}_{i}^{\prime}:=\\{S_{i}^{\prime}\in\mathcal{I}(\mathcal{M})\\}$ to
be the collection of subsets considered in Line 10 in interation $i$. Let
$\mathcal{U}=\left(\mathop{\bigcup}\limits_{i\in[r]}\mathcal{U}_{i}\right)\cup\left(\mathop{\bigcup}\limits_{0\leq
i\leq I-1}\mathcal{U}_{i}^{\prime}\right)$. Since each
$\left|\mathcal{U}_{i}\right|\leq n$ and each
$\left|\mathcal{U}_{i}^{\prime}\right|\leq rn$, we have

$\left|\mathcal{U}\right|\leq(I+1)rn.$

Thus the total query complexity is less than $(I+1)rn$.

##### Approximate ratio and success probability of Algorithm 1.

We say that event $\mathcal{E}_{g}$ happens if for all sets $A\in\mathcal{U}$,
the following inequality holds:

$\mathbb{P}\left[\left|\widehat{\varphi_{h}}(A)-\varphi_{h}(A)\right|>\alpha\max_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)\right]\leq\delta.$

By the above argument, we know that the total number of calls to
$\widehat{\varphi_{h}}$ is at most $(I+1)rn$. Thus

$\mathbb{P}[\mathcal{E}_{g}]\geq 1-(I+1)rn\delta.$

In the remaining proof, we assume $\mathcal{E}_{g}$ holds. Firstly we prove
the following lemma which analyzes the performance of the greedy initial
solution $S_{0}$ in Line 7 of Algorithm 1.

######  Lemma 3.4 (Approximation ratio of $S_{0}$).

Conditioned on $\mathcal{E}_{g}$, we have

$\varphi_{h}(S_{0})\geq\frac{1-2r\alpha}{2}\max_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S).$

###### Proof.

We first introduce the following well-known fact.

######  Fact 3.5 (Brualdi’s lemma).

Suppose $A$, $B$ are two bases in a matroid. There is a bijection $\pi:A\to B$
such that for all $a\in A$, $A-a+\pi(a)$ is a base. Furthermore, $\pi$ is the
identity on $A\cap B$.

Let
$O^{\star}\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$
be a set on which $\varphi_{h}$ attains its maximum value. For $O^{\star}$ and
$U_{r}$, we index the elements of $O^{\star}$ as $\\{o_{1},\dots,o_{r}\\}$
according to the Brualdi’s lemma such that $o_{i}=\pi(u_{i})$ with
$U_{i-1}+o_{i}\in\mathcal{I}(\mathcal{M})$. From how we choose $u_{i}$ in Line
4 of Algorithm 1, we have

$\widehat{\varphi_{h}}(U_{i-1}+u_{i})\geq\widehat{\varphi_{h}}(U_{i-1}+o_{i})$
(1)

for all $i\in[r]$. To utilize monotonicity and submodularity of $\varphi_{h}$,
we translate the inequality above into that of $\varphi_{h}$:

$\displaystyle\varphi_{h}(U_{i-1}+u_{i})+\alpha\varphi_{h}(O^{\star})$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\widehat{\varphi_{h}}(U_{i-1}+u_{i})$ (event $\mathcal{E}_{g}$)
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\widehat{\varphi_{h}}(U_{i-1}+o_{i})$ (Ineq. (1))
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\varphi_{h}(U_{i-1}+o_{i})-\alpha\varphi_{h}(O^{\star})$
$\displaystyle\text{(event $\mathcal{E}_{g}$)}.$

That is,

$\varphi_{h}(U_{i-1}+u_{i})\geq\varphi_{h}(U_{i-1}+o_{i})-2\alpha\cdot\varphi_{h}(O^{\star}).$

Subtracting $\varphi_{h}(U_{i-1})$ from each side gives

$\varphi_{h}(U_{i-1}+u_{i})-\varphi_{h}(U_{i-1})\geq\left[\varphi_{h}(U_{i-1}+o_{i})-\varphi_{h}(U_{i-1})\right]-2\alpha\cdot\varphi_{h}(O^{\star})$

for all $i\in[r]$. Summing these $r$ inequalities, we obtain

$\varphi_{h}(S_{0})\geq\sum_{i=1}^{r-1}[\varphi_{h}(U_{i-1}+o_{i})-\varphi_{h}(U_{i-1})]-2r\alpha\cdot\varphi_{h}(O^{\star}).$
(2)

From submodularity of $\varphi_{h}$, we have

$\sum_{i=1}^{r-1}[\varphi_{h}(U_{i-1}+o_{i})-\varphi_{h}(U_{i-1})]\geq\sum_{i=1}^{r-1}[\varphi_{h}(S_{0}+o_{i})-\varphi_{h}(S_{0})]\geq\varphi_{h}(S_{0}\cup
O^{\star})-\varphi_{h}(S_{0}).$ (3)

Combining (2) and (3) gives

$2\varphi_{h}(S_{0})\geq\varphi_{h}(S_{0}\cup
O^{\star})-2r\alpha\cdot\varphi_{h}(O^{\star})\geq(1-2r\alpha)\varphi_{h}(O^{\star}).$

This completes the proof. ∎

######  Lemma 3.6 (Maximum iterations of the local search procedure in
Algorithm 1).

Conditioned on event $\mathcal{E}_{g}$, the local search procedure in
Algorithm 1 terminates within
$I=\log_{1+\Delta}\left(\frac{2(1+\alpha)}{1-2(r+1)\alpha}\right)$ iterations.

###### Proof.

Let
$O^{\star}\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$
be a set on which $\varphi_{h}$ attains its maximum value and
$O^{\prime}\in\mathop{\arg\max}\limits_{S\in\mathcal{U}}\widehat{\varphi_{h}}(S)$
be the set with largest value of $\widehat{\varphi_{h}}$. By Lemma 3.4, we
have

$\displaystyle\widehat{\varphi_{h}}(S_{0})\leavevmode\nobreak\
\geq\leavevmode\nobreak\ $
$\displaystyle\varphi_{h}(S_{0})-\alpha\varphi_{h}(O^{\star})$
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1-2(r+1)\alpha}{2}\varphi_{h}(O^{*})$ (Lemma 3.4)
$\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1-2(r+1)\alpha}{2(1+\alpha)}\varphi_{h}(O^{\prime})+\frac{(1-2(r+1)\alpha)\alpha}{2(1+\alpha)}\varphi_{h}(O^{*})$
(optimality of $O^{*}$) $\displaystyle\geq\leavevmode\nobreak\ $
$\displaystyle\frac{1-2(r+1)\alpha}{2(1+\alpha)}\left(\widehat{\varphi_{h}}(O^{\prime})-\alpha\varphi_{h}(O^{*})\right)+\frac{(1-2(r+1)\alpha)\alpha}{2(1+\alpha)}\varphi_{h}(O^{*})$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1-2(r+1)\alpha}{2(1+\alpha)}\widehat{\varphi_{h}}(O^{\prime}).$

Since every local search step increases the function value
$\widehat{\varphi_{h}}$ by $1+\Delta$, Algorithm 1 searches for at most
$I=\log_{1+\Delta}\left(\frac{2(1+\alpha)}{1-2(r+1)\alpha}\right)$ iterations.
∎

Conditioned on $\mathcal{E}_{g}$, we finally obtain the approximation ratio of
$S_{I}$ by the locally optimality of $S_{I}$ by Theorem 1 and Lemma 4 in [7].

######  Lemma 3.7 ([7, Theorem 1]).

Let $A=\\{a_{1},\cdots,a_{r}\\}$ and $B=\\{b_{1},\cdots,b_{r}\\}$ be any two
bases of $\mathcal{M}$. Further suppose that we index the elements of $B$ so
that $b_{i}=\pi(a_{i})$, where $\pi:A\to B$ is the bijection guaranteed by
Fact 3.5 (Brualdi’s lemma). Then,

$\sum\limits_{i=1}^{r}\left[\varphi_{h}(A-a_{i}+b_{i})-\varphi_{h}(A)\right]\geq
h(B)-\frac{e}{e-1}h(A).$

######  Lemma 3.8 ([7, Lemma 4]).

For all $A\subseteq N$,

$h(A)\leq\varphi_{h}(A)\leq\frac{e}{e-1}H_{|A|}h(A),$

where $H_{|A|}=\sum\limits_{i=1}^{|A|}\frac{1}{i}.$

Let $O\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}h(S)$ and
$O^{\star}\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$.
By Fact 3.5, we index the elements of $S_{I}$ and $O$ by
$S_{I}=\\{s_{1},\cdots,s_{r}\\}$ and $O=\\{o_{1},\cdots,o_{r}\\}$ such that
$S_{I}-s_{i}+o_{i}\in\mathcal{I}(\mathcal{M})$ holds for all $i\in[r]$. We
firstly transfer $S_{I}$’s the locally optimality w.r.t.
$\widehat{\varphi_{h}}$ to the locally optimality w.r.t. $\varphi_{h}$. For
all $s_{i}$ and $o_{i}$, we have

$\displaystyle\varphi_{h}(S_{I}-s_{i}+o_{i})-\alpha\varphi_{h}(O^{*})$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\widehat{\varphi_{h}}(S_{I}-s_{i}+o_{i})$ (event $\mathcal{E}_{g}$)
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
(1+\Delta)\widehat{\varphi_{h}}(S_{I})$ (Lemma 3.6)
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
(1+\Delta)\left(\varphi_{h}(S_{I})+\alpha\varphi_{h}(O^{\star})\right)$ (event
$\mathcal{E}_{g}$)

which implies

$\varphi_{h}(S_{I}-s_{i}+o_{i})-\varphi_{h}(S_{I})\leq\Delta\varphi_{h}(S_{I})+(2+\Delta)\alpha\varphi_{h}(O^{\star}).$

Summing the resulting $r$ inequalities gives

$\displaystyle\sum\limits_{i=1}^{r}[\varphi_{h}(S_{I}-s_{i}+o_{i})-\varphi_{h}(S_{I})]$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
r\Delta\varphi_{h}(S_{I})+r(2+\Delta)\alpha\varphi_{h}(O^{\star})$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ rH_{r}\Delta
h(S_{I})+r(2+\Delta)\alpha H_{r}h(O^{\star})$ (Lemma 3.8)
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
rH_{r}\left((2+\Delta)\alpha+\Delta\right)h(O).$ (optimality of $O$)

Combine the Lemma 3.7, we have

$h(O)-\frac{e}{e-1}h(S_{I})\leq\sum\limits_{i=1}^{r}[\varphi_{h}(S_{I}-s_{i}+o_{i})-\varphi_{h}(S_{I})]\leq
rH_{r}\left((2+\Delta)\alpha+\Delta\right)h(O).$

Thus

$\displaystyle h(S_{I})$ $\displaystyle\leavevmode\nobreak\
\geq\leavevmode\nobreak\
\left(1-\frac{1}{e}\right)\left(1-rH_{r}\left((2+\Delta)\alpha+\Delta\right)\right)h(O)$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\left(1-\frac{1}{e}\right)\left(1-r\left(\ln
r+1\right)\left((2+\Delta)\alpha+\Delta\right)\right)h(O).$

This completes the proof of Theorem 3.3.

∎

######  Corollary 3.9.

Assume
$n\in\Omega\left(\exp\left(\left(\frac{1}{\varepsilon}\right)^{O(1)}\right)\right)$,
if $\alpha,\Delta=\frac{\varepsilon}{4r\log r}$, we have $I\leq\frac{5r\ln
r}{\varepsilon}$, and with probability at least $1-(I+1)rn\delta$, the output
$S_{I}$ of Algorithm 1 is a
$\left(1-\frac{1}{e}-\varepsilon\right)$-approximate solution for problem
$\max_{S\subseteq\mathcal{I}(\mathcal{M})}h(S)$, with at most
$\left(I+1\right)rn$ calls to $\widehat{\varphi_{h}}$.

##  4 Our algorithms and main theorems for cardinality constraints

For different ranges of cardinalities, this section presents algorithms
(Algorithm 3 and 5) that return a
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation for Problem 2.6 with
only $\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ queries to the noisy
oracle $\tilde{f}$. The analyses (Theorem 4.1 and 4.16) of the algorithms
constitute a proof of Theorem 1.1.

###  4.1 Algorithmic results for cardinality constraints when
$r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap
O\left(n^{\frac{1}{3}}\right)$

We first present an algorithm (Algorithm 3) and its analysis (Theorem 4.1)
that are applicable for all $r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap
O\left(n^{\frac{1}{3}}\right)$ when $n$ is sufficiently large.

######  Theorem 4.1 (Algorithmic results for cardinality constraints when
$r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap
O\left(n^{\frac{1}{3}}\right)$).

Let $\varepsilon>0$ and assume
$n\in\Omega\left(\exp\left(\left(\frac{1}{\varepsilon}\right)^{O(1)}\right)\right)$
is sufficiently large. For any $r\in\Omega(\frac{1}{\varepsilon})\cap
O\left(n^{\frac{1}{3}}\right)$, there exists an algorithm that returns a
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation for Problem 2.6
under a $r$-cardinality constraint, with probability at least
$1-O\left(\frac{1}{\log n}\right)$ and query complexity at most
$O\left(r^{2}\log^{2}r\cdot n^{\frac{3}{2}}\varepsilon^{-1}\max\\{r,\log
n\\}\right)$ to $\tilde{f}$.

The assumption that $n$ is sufficiently large is necessary and has also been
adopted in prior works on noisy submodular optimization [11, 20]. We achieve a
tight approximation ratio of $1-1/e-O(\varepsilon)$. Furthermore, we only
require $\text{Poly}\left(n,1/\varepsilon\right)$ queries to $\tilde{f}$, in
contrast to $\Omega\left(n^{1/\varepsilon}\right)$ for the prior greedy
algorithm [20].

####  4.1.1 Useful notations and useful facts for Theorem 4.1

Our algorithm and analysis are based on the following smoothing surrogate
function $h$.

######  Definition 4.2 (Smoothing surrogate function i@).

For any set $S\subseteq N$, we define the smoothing surrogate function $h(S)$
as the expectation of $f(S+e)$ over a random element $e\in N$, i.e.,
$h(S)=\frac{1}{n}\sum_{e\in N}f(S+e)$.

The surrogate function $h(S)$ is robust to noise when $|S|$ is relatively
small since at this time $h(S)$ is based on a rather large averaging set with
size nearly $n$. Note that $h(S)$ becomes too concentrated on $f(S)$ as
$|S|\approx n$, and hence, we consider this surrogate $h$ for the range $r\in
O\left(n^{\frac{1}{3}}\right)$. We now show that $h$ shares some basic
properties with $f$.

######  Lemma 4.3 (Properties of $h$).

The smoothing surrogate function $h$ is monotone and submodular.

###### Proof.

For any set $S\subseteq N$ and $x\notin S$, by Definition 4.2 we have

$h(S+x)-h(S)=\frac{1}{n}\sum_{e\in N}\left[f(S+x+e)-f(S+e)\right].$ (4)

This immediately implies that $h$ is monotone, since the monotonicity of $f$
implies that each term $f(S+x+e)-f(S+e)$ is non-negative. Next, suppose that
$T\subseteq S$ and $x\notin S$. Then

$\displaystyle h(T+x)-h(T)$ $\displaystyle=\frac{1}{n}\sum_{e\in
N}\left[f(T+x+e)-f(T+e)\right]$ (Eq. (4))
$\displaystyle\geq\frac{1}{n}\sum_{e\in N}\left[f(S+x+e)-f(S+e)\right]$
(submodularity of $f$) $\displaystyle=h(S+x)-h(S).$ (Eq. (4))

Thus, $h$ is submodular. ∎

Note that $h$ is implicitly constructed since we only have a value oracle to
$\tilde{f}$ instead of $f$. Hence, we construct an approximation of its
auxiliary function $\varphi_{h}$; summarized by the following lemma.

######  Lemma 4.4 (Approximation of $\varphi_{h}$).

Let $\alpha,\delta\in(0,1/2)$ and assume
$n\in\Omega(\alpha^{-2}\log(\delta^{-1}))$. There exists a value oracle
$\mathcal{O}$ to an
$\left(\alpha,\delta,\mathcal{I}(r-1)\right)$-approximation
$\widehat{\varphi_{h}}$ of $\varphi_{h}$, which answering $\mathcal{O}(A)$
queries at most $M=\Theta\left(\log r\cdot n^{\frac{1}{2}}\max\\{r,\log
n\\}\right)$ times to $\tilde{f}$ for each set $A\in\mathcal{I}(r-1)$.

The above lemma indicates that for a sufficiently large $n$, we can achieve an
arbitrary accurate approximation $\widehat{\varphi_{h}}$ of $\varphi_{h}$,
which queries $\tilde{f}$ only $\tilde{O}(rn^{\frac{1}{2}})$ times for each
$\widehat{\varphi_{h}}(A)$.

More precisely, the relationship among $\alpha$, $\delta$ and $n$ can be
expressed as $\alpha^{-2}\ln(4\delta^{-1})\leq c\cdot n\kappa^{-2}$ (See Lemma
4.9), where $\kappa$ is the sub-exponential norm (Definition 4.6) of the noise
distribution $\mathcal{D}$ depending on the parameters $c_{i},\gamma_{i}$ of
density function, and $c$ is an absolute constant. A small $\kappa$ indicates
a concentrated noise distribution. Generally speaking, the more concentrated
the noise is ($\kappa\rightarrow 0$), the more accurate approximation we are
able to obtain ($\alpha,\delta\rightarrow 0$).

###### Proof.

Here we illustrate intuitively how to obtain the value oracle $\mathcal{O}$ to
an $(\alpha,\delta,\mathcal{I}(r-1))$-approximation $\widehat{\varphi_{h}}$ of
$\varphi_{h}$. When $n$ is large enough, the generalized exponential tail
allows the difference between $\varphi_{h}$ and its noisy analogue
$\widetilde{\varphi_{h}}$ to be averaged out. Thus we can obtain an
approximation $\widehat{\varphi_{h}}$ of $\varphi_{h}$ by approximating
$\widetilde{\varphi_{h}}$. Since evaluating $\widetilde{\varphi_{h}}$ exactly
will require an exponential number of value queries to $\tilde{f}$, we use a
random sampling procedure (Algorithm 2) to estimate it. With only polynomial
queries to $\tilde{f}$, $\widetilde{\varphi_{h}}$ can be approximated to the
desired accuracy.

To prove Lemma 4.4, we first show some bounds for coefficients $\tau_{A}(T)$.
With these bounds, we will then prove that when $n$ is sufficiently large,
$\varphi_{h}$ and its noisy analogue $\widetilde{\varphi_{h}}$ are close to
each other by Bernstein’s inequality for sub-exponential variables. Finally,
we use Hoeffding’s inequality to show that with enough samples,
$\widehat{\varphi_{h}}$ is close to $\widetilde{\varphi_{h}}$ and therefore a
good approximation of $\varphi_{h}$.

For a set $A\subseteq N$, we rewrite the auxiliary function $\varphi_{h}(A)$
as a linear combination of $f(T)$ according to Definition 3.1 and 4.2 and
obtain

$\displaystyle\varphi_{h}(A)=\frac{1}{n}\sum_{T\subseteq
A}\left[(m_{|A|-1,|T|-1}+m_{|A|-1,|T|-2})|T|\cdot f(T)+\sum_{e\in N\backslash
A}m_{|A|-1,|T|-1}\cdot f(T+e)\right].$

(5)

We define the averaging set of $\varphi_{h}(A)$ as

$\mathcal{L}_{A}=\left\\{T\in 2^{N}:T\subseteq A,\text{\ or\ }\exists\
S\subseteq A\ \text{and}\ e\in N\backslash A\text{\ s.t.\ }S+e=T\right\\}.$

For any $T\in\mathcal{L}_{A}$, we denote by $\tau_{A}(T)$ the linear
coefficient of $f(T)$. Then we can write $\varphi_{h}(A)$ as
$\sum\limits_{T\in\mathcal{L}_{A}}\tau_{A}(T)f(T)$.

######  Lemma 4.5 (Useful bounds of the linear coefficients).

For any $A\subseteq N$ with $|A|\leq\sqrt{n}$, we have

$\displaystyle(1)\sum_{T\in\mathcal{L}_{A}}\tau^{2}_{A}(T)\leq\frac{12}{n|A|};$
$\displaystyle(2)\max_{T\in\mathcal{L}_{A}}\tau_{A}(T)\leq\frac{4}{n};$
$\displaystyle(3)\sum_{T\in\mathcal{L}_{A}}\tau_{A}(T)\leq
2\left(\ln|A|+2\right).$

###### Proof.

For notation convenience, we let $a=|A|$ and $t=|T|$ in this proof. For any
$A\subseteq N$, we have

$\displaystyle\sum_{T\in\mathcal{L}_{A}}\tau^{2}_{A}(T)$ $\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum^{a}_{t=0}{a\choose
t}\left[(m_{a-1,t-1}+m_{a-1,t-2})^{2}\cdot
t^{2}+m^{2}_{a-1,t-1}\cdot(n-a)\right]$ (Eq. (5)) $\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\\!\left\\{{a\choose
1}\left(\int_{0}^{1}\frac{e^{p}}{e-1}(1-p)^{a-1}dp\right)^{2}(n-a+1)\right.$
(Definition 3.1) $\displaystyle\left.+\sum^{a}_{t=2}{a\choose
t}\\!\left[\left(\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-2}(1-p)^{a-t}dp\right)^{2}\\!\\!t^{2}+\left(\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-1}(1-p)^{a-t}dp\right)^{2}\\!\\!(n-a)\right]\right\\}$
$\displaystyle\leq$
$\displaystyle\frac{e^{2}}{(e-1)^{2}n^{2}}\left\\{\sum^{a}_{t=2}\left(\frac{at}{(t-1)^{2}}+\frac{n-a}{at}\right)\frac{\Gamma(t)\Gamma(a-t+1)}{\Gamma(a)}+\frac{n-a+1}{a}\right\\}$
(6) $\displaystyle\leq$
$\displaystyle\frac{e^{2}}{(e-1)^{2}n^{2}}\left\\{\frac{1}{a-1}\sum^{a}_{t=2}\left(2a+\frac{n-a}{a}\right)\frac{1}{{{a-2}\choose{t-2}}}+\frac{n-a+1}{a}\right\\}$
($\frac{t}{t-1}\leq 2$ for $t\geq 2$) $\displaystyle<$
$\displaystyle\frac{6}{n^{2}}\left(a+\frac{n}{a}\right),$
($\frac{e^{2}}{(e-1)^{2}}\leq 3$ and ${{a-2}\choose{t-2}}\geq 1$)

where we use the fact that $e^{p}\leq e$ for $p\in[0,1]$ and a property of
beta function that

$B(x,y)=\int_{0}^{1}p^{x-1}(1-p)^{y-1}dp=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$
(7)

to obtain Ineq. (6). In particular, if $|A|\leq\sqrt{n}$, we have
$\sum_{T\in\mathcal{L}_{A}}\tau^{2}_{A}(T)\leq{12}/{(n|A|)}$.

Next we show that $\max_{T\in\mathcal{L}_{A}}\tau_{A}(T)\leq{4}/{n}$. For any
set $T\subseteq A$ with $|T|\geq 2$, we have

$\displaystyle\tau_{A}(T)$
$\displaystyle=\frac{1}{n}(m_{a-1,t-1}+m_{a-1,t-2})\cdot t$ (Eq. (5))
$\displaystyle=\frac{t}{n}\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-2}(1-p)^{a-t}dp$
(Definition 3.1)
$\displaystyle\leq\frac{e}{e-1}\cdot\frac{t}{n}\cdot\frac{(t-2)!(a-t)!}{(a-1)!}$
($p<1$ and Eq. (7))
$\displaystyle\leq\frac{2}{n}\cdot\frac{t}{a-1}\leq\frac{4}{n}.$
($\frac{e}{e-1}\leq 2$, ${{a-2}\choose{t-2}}\geq 1$ and $\frac{t}{a-1}\leq 2$)

Similarly, for a set $T$ that only contains a single element in $A$,

$\tau_{A}(T)=\frac{m_{a-1,0}}{n}=\frac{1}{n}\int_{0}^{1}\frac{e^{p}}{e-1}(1-p)^{a-1}dp\leq\frac{2}{an}.$

For any $T\in\mathcal{L}_{A}\setminus 2^{A}$, we have

$\displaystyle\tau_{A}(T)$ $\displaystyle=\frac{1}{n}\cdot m_{a-1,t-2}$ (Eq.
(5))
$\displaystyle=\frac{1}{n}\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-2}(1-p)^{a-t+1}dp$
(Definition 3.1)
$\displaystyle\leq\frac{e}{(e-1)n}\cdot\frac{1}{{{a}\choose{t-2}}}\cdot\frac{1}{a-t+2}\leq\frac{2}{n}.$
(Eq. (7) and $2\leq t\leq a+1$)

Combining these three parts gives
$\max_{T\in\mathcal{L}_{A}}\tau_{A}(T)\leq{4}/{n}$. Finally we can bound
$\sum_{T\in\mathcal{L}_{A}}\tau_{A}(T)$ as below:

$\displaystyle\sum_{T\in\mathcal{L}_{A}}\tau_{A}(T)$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum^{a}_{t=0}{a\choose
t}\left[(m_{a-1,t-1}+m_{a-1,t-2})t+m_{a-1,t-1}(n-a)\right]$ (Eq. (5))
$\displaystyle=$ $\displaystyle\frac{1}{n}\left\\{\sum^{a}_{t=2}{a\choose
t}\left[t\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-2}(1-p)^{a-t}dp+(n-a)\int_{0}^{1}\frac{e^{p}}{e-1}p^{t-1}(1-p)^{a-t}dp\right]\right.$
$\displaystyle\left.+{a\choose
1}(n-a+1)\int_{0}^{1}\frac{e^{p}}{e-1}(1-p)^{a-1}dp\right\\}$ (Definition 3.1)
$\displaystyle\leq$
$\displaystyle\frac{e}{(e-1)n}\cdot\left[\sum^{a}_{t=2}\left(\frac{a}{t-1}+\frac{n-a}{t}\right)+(n-a+1)\right]$
($p<1$) $\displaystyle\leq$ $\displaystyle 2(\ln a+2).$ ($\frac{e}{e-1}\leq 2$
and $\sum^{a}_{t=2}\frac{1}{t-1}\leq\ln a+1$)

∎

We now use concentration results of sub-exponential distributions to bound the
difference between $\varphi_{h}$ and its noisy analogue
$\widetilde{\varphi_{h}}$.

######  Definition 4.6 (Sub-exponential distribution).

The sub-exponential norm of $X\in\mathbb{R}$ is

$\left\|X\right\|_{\psi_{1}}=\inf\\{t>0:\mathbb{E}\exp(|X|/t)\leq 2\\}.$

If $\left\|X\right\|_{\psi_{1}}$ is finite, we say that $X$ is sub-
exponential.

######  Claim 4.7.

Let $\xi$ be a random variable with a generalized exponential tail
distribution $\mathcal{D}$. Then $\xi-1$ is sub-exponential.

###### Proof.

If the support of $\mathcal{D}$ is bounded by some constant $b$, then let
$\kappa=(b+1)/\ln 2$, and we have $\left\|\xi-1\right\|_{\psi_{1}}\leq\kappa$.
For the case where $\mathcal{D}$ does not have bounded support, recall that
the probability density function $\rho(x)$ of $\mathcal{D}$ is
$\exp(-\sum_{i}c_{i}x^{\gamma_{i}})$. When

$x\geq\max\left\\{1,\left(\frac{2\sum_{i=1}|c_{i}|}{c_{0}}\right)^{\frac{1}{\gamma_{0}-\gamma_{1}}}\right\\},$

the term $\frac{1}{2}c_{0}x^{\gamma_{0}}$ dominates the rest of the terms, and
thus $\rho(x)\leq e^{-\frac{1}{2}c_{0}x^{\gamma_{0}}}\leq
e^{-\frac{1}{2}c_{0}x}$. Let

$\kappa=\max\left\\{2,\
\frac{2}{c_{0}}\cdot\ln\left(\frac{8}{c_{0}}\right)+1,\
\ln\left(\frac{2}{3}\right)\cdot\left(\frac{2\sum_{i=1}|c_{i}|}{c_{0}}\right)^{\frac{1}{\gamma_{0}-\gamma_{1}}}\right\\}.$

It is straightforward to verify that
$\mathbb{E}\left[\exp\left(\frac{|\xi-1|}{\kappa}\right)\right]\leq 2$. Hence
$\xi-1$ is a sub-exponential variable with a constant sub-exponential norm
$\left\|\xi-1\right\|_{\psi_{1}}\leq\kappa$. ∎

For sub-exponential random variables, we have the following Bernstein’s
inequality.

######  Lemma 4.8 (Bernstein’s inequality for sub-exponential variables [24]).

Let $X_{1},\dots,X_{m}$ be independent, mean zero, sub-exponential random
variables, and $a=(a_{1},\dots,a_{m})\in\mathbb{R}^{m}$. Then, for every
$t>0$, we have

$\mathbb{P}\left[\left|\sum^{m}_{i=1}a_{i}X_{i}\right|\geq t\right]\leq
2\exp\left[-c\min\left(\frac{t^{2}}{K^{2}\left\|a\right\|^{2}_{2}},\frac{t}{K\left\|a\right\|_{\infty}}\right)\right],$
(8)

where $K=\max_{i}\left\|X_{i}\right\|_{\psi_{1}}$ and $c$ is a constant.

With Bernstein’s inequality, we can bound the difference between $\varphi_{h}$
and $\widetilde{\varphi_{h}}$ by the following lemma.

######  Lemma 4.9 (Difference between $\varphi_{h}$ and
$\widetilde{\varphi_{h}}$).

Suppose that $n\geq 192\kappa^{2}c^{-1}\cdot\alpha^{-2}\ln(4\delta^{-1})$,
where $\kappa$ denotes the sub-exponential norm of the noise multiplier and
$c$ is the constant in Ineq. (8). For any set $A\in\mathcal{I}(r-1)$, we have

$\mathbb{P}\left[|\widetilde{\varphi_{h}}(A)-\varphi_{h}(A)|>\frac{\alpha}{2}\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right]\leq\frac{\delta}{2}.$

###### Proof.

Let us fix a set $A\in\mathcal{I}(r-1)$. From monotonicity and submodularity
of $f$, for any $T\in\mathcal{L}_{A}$,

$f(T)\leq f(A)+\max_{e\in N}f(e)\leq 2\cdot\max_{S\in\mathcal{I}(r-1)}f(S)\leq
2\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S).$ (9)

Let $X_{T}=\xi(T)-1$ and $a_{T}=\tau_{A}(T)f(T)$. By Lemma 4.5, we have

$\displaystyle\sum_{T\in\mathcal{L}_{A}}\left(\tau_{A}(T)f(T)\right)^{2}\leq
4\left(\sum_{T\in\mathcal{E}_{A}}\tau^{2}_{A}(T)\right)\left(\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right)^{2}\leq\frac{48}{|A|n}\cdot\left(\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right)^{2}$

and

$\max_{T\in\mathcal{L}_{A}}\tau_{A}(T)f(T)\leq
2\max_{T\in\mathcal{L}_{A}}\tau_{A}(T)\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\leq\frac{8}{n}\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S).$

Since we have $\alpha|A|<\varepsilon/(4H_{r-1})<12\kappa$, applying Lemma 4.8
gives

$\mathbb{P}\left[|\widetilde{\varphi_{h}}(A)-\varphi_{h}(A)|\geq\frac{\alpha}{2}\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right]\leq
2\exp\left(-c\cdot\frac{n\alpha^{2}|A|}{192\kappa^{2}}\right).$

By assumption that $n\geq
192\kappa^{2}c^{-1}\cdot\varepsilon^{-2}_{0}\ln(4\delta^{-1})$, the
probability above is at most $\delta/2$. ∎

The random sampling procedure that we use to estimate
$\widetilde{\varphi_{h}}$ is presented as Algorithm 2.

Input : Noisy oracle $\tilde{f}$, a set $A\in\mathcal{I}(r-1)$, number of
samples $M$.

1 Construct a distribution $\nu(T)$ on set $\mathcal{L}_{A}$ such that
$\nu(T)={\tau_{A}(T)}/{\left(\sum_{T^{\prime}\in\mathcal{L}_{A}}\tau_{A}(T^{\prime})\right)}$

2 Sample $M$ sets $T_{1},\dots,T_{M}$ in $\mathcal{L}_{A}$ according to the
distribution $\nu(T)$

3
$\widehat{\varphi_{h}}(A)\leftarrow\left(\sum_{T^{\prime}\in\mathcal{L}_{A}}\tau_{A}(T^{\prime})\right)\cdot\frac{1}{M}\sum_{j=1}^{M}\tilde{f}(T_{j})$

return $\widehat{\varphi_{h}}(A)$

Algorithm 2 Approximation of $\varphi_{h}$

We plan to use Hoeffding’s inequality to show that $\widehat{\varphi_{h}}(A)$
and $\widetilde{\varphi_{h}}(A)$ are very close to each other, and thus
$\widehat{\varphi_{h}}$ is a $(\alpha,\delta,\mathcal{I}(r-1))$-approximation
of $\varphi_{h}$.

######  Lemma 4.10 (Hoeffding’s inequality).

Let $X_{1},\cdots,X_{N}$ be independent bounded random variables such that
$X_{i}\in[a_{i},b_{i}]$, where $-\infty<a_{i}\leq b_{i}<\infty$. Then

$\mathbb{P}\left[\left|\frac{1}{N}\sum\limits_{i=1}^{N}(X_{i}-\mathbb{E}X_{i})\right|\geq
t\right]\leq
2\exp\left[-\frac{2N^{2}t^{2}}{\sum^{N}_{i=1}(b_{i}-a_{i})^{2}}\right].$

To use Hoeffding’s inequality, we need a bound $b$ for noise multipliers. If
the noise distribution $\mathcal{D}$ has bounded support, this bound is
natural. When the support of $\mathcal{D}$ is not bounded, we let

$b=\frac{2}{c_{0}}\ln\left(c_{0}^{-1}2^{|A|+3}n\delta^{-1}\right).$

When $n$ is sufficiently large,

$\mathbb{P}\left[\xi\geq
b\right]\leq\int_{b}^{\infty}\exp\left(-\frac{1}{2}c_{0}x\right)dx\leq\frac{\delta}{2^{|A|+2}n}.$

The probability that all $\xi(T)\ (T\in\mathcal{L}_{A})$ are bounded by $b$ is

$\left(1-\frac{\delta}{2^{r}n}\right)^{|\mathcal{L}_{A}|}\geq
1-|\mathcal{L}_{A}|\cdot\frac{\delta}{2^{|A|+2}n}\geq 1-\frac{\delta}{4}.$

######  Lemma 4.11 (Difference between $\widetilde{\varphi_{h}}$ and
$\widehat{\varphi_{h}}$).

For any set $A\in\mathcal{I}(r-1)$, we assume $M\geq
c^{\frac{1}{2}}\kappa^{-1}\cdot b(\ln(r-1)+2)\sqrt{n}$, where $c$ is the
constant in Ineq. (8), and suppose that all $\xi(T)\ (T\in\mathcal{L}_{A})$
are bounded by $b$. Then

$\mathbb{P}\left[|\widehat{\varphi_{h}}(A)-\widetilde{\varphi_{h}}(A)|>\frac{\alpha}{2}\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right]\leq\frac{\delta}{4}.$

###### Proof.

We apply Hoeffding’s inequality by letting
$X_{j}=\left(\sum_{T^{\prime}\in\mathcal{L}_{A}}\tau_{A}(T^{\prime})\right)\tilde{f}(T_{j})$
and obtain

$\mathbb{P}\left[|\widehat{\varphi_{h}}(A)-\widetilde{\varphi_{h}}(A)|\geq\frac{\alpha}{2}\cdot\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right]\leq
2\exp\left[-\frac{M^{2}\varepsilon^{2}_{0}}{8b^{2}\left(\sum_{T\in\mathcal{E}_{A}}\tau_{A}(T)\right)^{2}}\right].$

By assumption that $M\geq c^{\frac{1}{2}}\kappa^{-1}\cdot
b(\ln(r-1)+2)\sqrt{n}$ and $n\geq
192\kappa^{2}c^{-1}\cdot\alpha^{-2}\ln(4\delta^{-1})$, the probability above
is at most ${\delta}/{4}$. ∎

For any $A\in\mathcal{I}(r-1)$, by taking a union bound,
$|\widehat{\varphi_{h}}(A)-\varphi_{h}(A)|\leq\alpha\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)$
fails with probability at most
${\delta}/{2}+{\delta}/{4}+(1-{\delta}/{4}){\delta}/{4}\leq\delta$. The lemma
is proved. ∎

####  4.1.2 Algorithm for Theorem 4.1

Input : a value oracle to $\tilde{f}$, budget
$r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap
O\left(n^{\frac{1}{3}}\right)$ and $\varepsilon\in(0,1/2)$

1 Let $\widehat{\varphi_{h}}$ be a $\left(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{1}{(I+1)(r-1)n^{2}},\mathcal{I}(r-1)\right)$-approximation of
$\varphi_{h}$ as in Lemma 4.4

$S_{L}\leftarrow\mathtt{NLS}\left(\widehat{\varphi_{h}},\mathcal{I}(r-1),\Delta=\frac{\varepsilon}{4r\ln
r}\right)$

$\triangleright$ Local search phase

$S_{M}\leftarrow S_{L}+\arg\max_{e\in N\backslash S_{L}}\tilde{f}(S_{L}+e)$

$\triangleright$ $\tilde{f}$-maximization phase

return $S_{M}$

Algorithm 3 Noisy local search under a small cardinality constraint

We present Algorithm 3 that contains two phases: a local search phase (Line 2)
and a $\tilde{f}$-maximization phase (Line 3). We first run a non-oblivious
local search procedure (Algorithm 1) under the $(r-1)$-cardinality constraint
(Line 2). We set $\delta=\frac{1}{(I+1)(r-1)n^{2}}$ by Corollary 3.9 when
applying Algorithm 1 to obtain a
$\left(1-\frac{1}{e}-\varepsilon\right)$-approximation solution $S_{L}$ for
$h$-maximization. At the $\tilde{f}$-maximization phase (Line 3), we obtain
$S_{M}$ by selecting an additional element $e\in N\setminus S_{L}$ that
maximizes $\tilde{f}(S_{L}+e)$. This guarantees that
$f(S_{M})\geq(1-\varepsilon)h(S_{L})$ with high probability (Lemma 4.12),
which results in the approximation ratio $1-\frac{1}{e}-O(\varepsilon)$ in
Theorem 4.1. Given the smoothing surrogate function $h(S)$ (Definition 4.2), a
natural idea is to simply apply local search (Algorithm 1) to optimize it
under the $r$-cardinality constraint. However, this idea does not yield a
provable approximation of $\max_{S:|S|\leq r}f(S)$, since it is not easy to
control the contribution of the additional element $e\in N$ to $h(S)$ and it
is possible that $h(S)\gg f(S)$. To handle this difficulty, Algorithm 3 first
runs a local search procedure under the $(r-1)$-cardinality constraint, and
then selects an additional element with a "large enough" margin at the
$\tilde{f}$-maximization phase. This idea enables us to control the loss
induced by the surrogate $h$ within $\frac{1}{r}\cdot\max_{S:|S|\leq r}f(S)$.

####  4.1.3 Proof of Theorem 4.1

We first analyze the query complexity and then prove the approximation
performance.

##### Query complexity of Algorithm 3.

In Line 3, we make $(n-r+1)$ calls to the noisy oracle $\tilde{f}$ in total.
By Corollary 3.9, the total number of queries to $\widehat{\varphi_{h}}$ in
Line 2 is at most $(I+1)(r-1)n$ and $I\leq\frac{5r\ln r}{\varepsilon}$.
Combining with Lemma 4.4, the query complexity to $\tilde{f}$ is upper bounded
by $(n-r+1)+M(I+1)(r-1)n=O\left(r^{2}\log^{2}r\cdot
n^{\frac{3}{2}}\varepsilon^{-1}\max\\{r,\log n\\}\right)$. This matches
Theorem 4.1.

##### Approximation ratio and success probability of Algorithm 3.

Let $O_{h}\in\arg\max_{S\in\mathcal{I}(r-1)}h(S)$ represent the $(r-1)$-set
whose value of $h$ is the largest. Following from Theorem 3.3, we have
$h(S_{L})\geq\left(1-\frac{1}{e}-\varepsilon\right)h(O_{h})$ with probability
at least $1-\frac{1}{n}$. We denote by
$O_{f}\in\arg\max_{S\in\mathcal{I}(r)}f(S)$ the optimal solution to $f$. By
the submodularity of $f$, $O_{f}$ has a subset $\tilde{O}_{f}$ with $r-1$
elements such that $f(\tilde{O}_{f})\geq\left(1-\frac{1}{r}\right)f(O_{f})$.
Then we have

$h(S_{L})\geq\left(1-\frac{1}{e}-\varepsilon\right)h(\tilde{O}_{f})\geq\left(1-\frac{1}{e}-\varepsilon\right)f(\tilde{O}_{f})\geq\left(1-\frac{1}{r}\right)\left(1-\frac{1}{e}-\varepsilon\right)f(O_{f}),$
(10)

where the first inequality follows from
$h(S_{L})\geq\left(1-\frac{1}{e}-\varepsilon\right)h(O_{h})$ and the second
from monotonicity of $f$. Since $r$ is assumed to be
$\Omega\left(\frac{1}{\varepsilon}\right)$, $h(S_{L})$ is a
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation of $f(O_{f})$.

Recall that $h(S_{L})$ is the expectation of $f(S_{L}+e)$ over a random
element $e\in N$. Ineq. (10) already proves a claim that uniformly randomly
adding an element $e\in N$ to $S_{L}$ achieves an approximation ratio of
$1-\frac{1}{e}-O(\varepsilon)$ in expectation for maximizing $f$, i.e.,
$\mathbb{E}[f(S_{L}+e)]\geq\left(1-\frac{1}{e}-O(\varepsilon)\right)f(O_{f}).$
Moreover, we can convert this claim to a with-high-probability claim by the
following lemma.

######  Lemma 4.12 (Approximation at the $\tilde{f}$-maximization phase).

With probability $1-O\left(\frac{1}{\log n}\right)$, we have
$f(S_{M})\geq(1-\varepsilon)h(S_{L}).$

This lemma indicates that a bad element $e\in N\setminus S_{L}$ with
$f(S_{L}+e)<(1-\varepsilon)h(S_{L})$ is unlikely to be chosen at the
$\tilde{f}$-maximization phase. This is because the local search procedure
guarantees that the number of good elements with
$f(S_{L}+e)\geq(1-\varepsilon)h(S_{L})$ is almost of the same order as the bad
ones.

###### Proof.

We denote by $e^{\star}\in\arg\max_{e\in N\backslash S_{L}}\tilde{f}(S_{L}+e)$
the element added to $S_{L}$ at the $\tilde{f}$-maximization phase by
Algorithm 3. We define two kinds of elements in $N\backslash S_{L}$. Say that
an element $e$ is good if

$f(S_{L}+e)\geq(1-\frac{\varepsilon}{2})h(S_{L}),$ (11)

and $e$ is bad if

$f(S_{L}+e)<(1-\varepsilon)h(S_{L}).$

The set of good elements and that of bad ones are denoted as $\mathcal{G}$ and
$\mathcal{B}$, respectively. Our goal is to prove that $e^{\star}$ is not bad
with probability $1-O\left(\frac{1}{\log n}\right)$. First we use the
following lemma to quantify the number of good elements.

######  Lemma 4.13 (The number of good elements).

With probability $1-\frac{1}{n}$, there are at least $\frac{\varepsilon
n}{16H_{r-1}}$ good elements in $N\backslash S_{L}$, where
$H_{r-1}=\sum^{r-1}_{i=1}\frac{1}{i}$.

###### Proof.

Suppose by contradiction that $|\mathcal{G}|<\frac{\varepsilon n}{16H_{r-1}}$.
We will show that if there are only a few good elements in $N\backslash
S_{L}$, a good element with very large $f$-value must exist. However, this
contradicts how Algorithm 3 does local search, which should have changed some
element in $S_{L}$ for the one with such large $f$-value.

By construction of function $h$ and definition of good elements, we have

$\displaystyle h(S_{L})$
$\displaystyle=\frac{1}{n}\left(\sum_{e\in\mathcal{G}}f(S_{L}+e)+\sum_{e\in
N\backslash\mathcal{G}}f(S_{L}+e)\right)$ (Definition 4.2)
$\displaystyle<\frac{1}{n}\left(\sum_{e\in\mathcal{G}}f(S_{L}+e)+|N\backslash\mathcal{G}|\left(1-\frac{\varepsilon}{2}\right)h(S_{L})\right).$
(Ineq. (11))

Rewriting the inequality above gives

$\sum_{e\in\mathcal{G}}f(S_{L}+e)>\left(n-\left(1-\frac{\varepsilon}{2}\right)|N\backslash\mathcal{G}|\right)\cdot
h(S_{L})>\frac{\varepsilon n}{2}\cdot h(S_{L}),$

where the last inequality holds since $|N\backslash\mathcal{G}|<n$. Hence,
there must exist a good element $e_{0}$ such that

$f(S_{L}+e_{0})\geq\frac{\varepsilon n}{2|\mathcal{G}|}\cdot
h(S_{L})>8H_{r-1}\cdot h(S_{L}).$ (12)

Consider the set $S_{L}+e_{0}-e^{\prime}_{0}$, where $e^{\prime}_{0}$ is an
arbitrary element in $S_{L}$. On the one hand, we must have

$\widehat{\varphi_{h}}(S_{L}+e_{0}-e^{\prime}_{0})\leq(1+\alpha)\widehat{\varphi_{h}}(S_{L}).$
(13)

Otherwise, Algorithm 3 would have changed $e^{\prime}_{0}$ for $e_{0}$ rather
than returning $S_{L}$. We translate Ineq. (13) to that of $\varphi_{h}$. With
probability $1-O(\frac{1}{n})$,

$\displaystyle\varphi_{h}(S_{L}+e_{0}-e^{\prime}_{0})$
$\displaystyle\leq\widehat{\varphi_{h}}(S_{L}+e_{0}-e^{\prime}_{0})+\alpha\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)$
(Lemma 4.4)
$\displaystyle\leq(1+\alpha)\widehat{\varphi_{h}}(S_{L})+\alpha\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)$
(Ineq. (13))
$\displaystyle\leq(1+\alpha)\left[\varphi_{h}(S_{L})+2\alpha\max_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)\right]$
(Lemma 4.4)
$\displaystyle\leq(1+\alpha)\left(1+\frac{4\alpha}{1-2r\alpha}\right)\varphi_{h}(S_{L})$
(Lemma 3.4) $\displaystyle\leq(1+10\alpha)\varphi_{h}(S_{L}).$
($r\alpha<{1}/{4}$)

On the other hand, for any $\alpha<\frac{1}{4}$ and $r\geq 2$,

$\displaystyle\varphi_{h}(S_{L}+e_{0}-e^{\prime}_{0})$ $\displaystyle\geq
h(S_{L}+e_{0}-e^{\prime}_{0})$ (Lemma 3.8) $\displaystyle\geq
f(S_{L}+e_{0})-f(e^{\prime}_{0})$ (monotonicity and submodularity of $f$)
$\displaystyle\geq(8H_{r-1}-1)h(S_{L})$ (Ineq. (12)) and
$f(e^{\prime}_{0})\leq f(S_{L})\leq h(S_{L})$)
$\displaystyle>(1+10\alpha)\frac{e}{e-1}H_{r-1}h(S_{L})$ ($\alpha<1/4$ and
$\frac{e}{e-1}<2$) $\displaystyle\geq(1+10\alpha)\varphi_{h}(S_{L}).$ (Lemma
3.8)

This constitutes a contradiction, and the lemma is proved. ∎

Let $\xi^{*}_{\mathcal{G}}=\max_{e\in\mathcal{G}}\xi(S_{L}+e)$ and
$\xi^{*}_{\mathcal{B}}=\max_{e\in\mathcal{B}}\xi(S_{L}+e)$ denote the largest
noise multiplier on the sets belonging to $\\{S_{L}+e:e\in\mathcal{G}\\}$ and
$\\{S_{L}+e:e\in\mathcal{B}\\}$, respectively. Next we show that with
sufficient good elements guaranteed by Lemma 4.13, $\xi^{*}_{\mathcal{G}}$ and
$\xi^{*}_{\mathcal{B}}$ are close to each other with high probability.

If the distribution has bounded support and there is an atom at the supremum
with some probability $p$, it is clear that both $\xi^{*}_{\mathcal{G}}$ and
$\xi^{*}_{\mathcal{B}}$ reaches the supremum with high probability if $n$ is
sufficiently large. Hence we focus on the case where the distribution
$\mathcal{D}$ does not have bounded support in the following analysis. Recall
that the probability density function $\rho(x)$ of the noise distribution
$\mathcal{D}$ is $\exp(-\sum_{i}c_{i}x^{\gamma_{i}})$. We define two threshold
$m_{\mathcal{G}}$ and $M_{\mathcal{B}}$:

$m_{\mathcal{G}}=\left[\frac{1}{(1+\beta)c_{0}}\cdot\ln\left(\frac{|\mathcal{G}|}{\gamma_{0}\ln
n}\right)\right]^{\frac{1}{\gamma_{0}}}$

and

$M_{\mathcal{B}}=\left[\frac{1}{(1-\beta)c_{0}}\ln\left(\frac{|\mathcal{B}|\ln
n}{\gamma_{0}}\right)\right]^{\frac{1}{\gamma_{0}}},$

where we set $\beta=\left(\frac{1}{\ln
n}\right)^{\frac{\gamma_{0}-\gamma_{1}}{2\gamma_{0}}}$. Note that
$m_{\mathcal{G}}$ and $M_{\mathcal{B}}$ are very close to each other in a
sense that

$\frac{m_{\mathcal{G}}}{M_{\mathcal{B}}}\geq\left[\frac{1-\beta}{1+\beta}\cdot\frac{\ln
n-\ln(1/\varepsilon)-\ln\ln n-\ln(16\gamma_{0}H_{r-1})}{\ln n+\ln\ln
n-\ln\gamma_{0}}\right]^{\frac{1}{\gamma_{0}}}>1-\frac{\varepsilon}{2},$

holds when $n\geq
6\exp\left(\left(\frac{1}{\varepsilon}\right)^{\frac{2\gamma_{0}}{\gamma_{0}-\gamma_{1}}}\right)$.
Our goal is to show that with high probability, $m_{\mathcal{G}}$ is a lower
bound for $\xi^{*}_{\mathcal{G}}$, and $M_{\mathcal{B}}$ is an upper bound for
$\xi^{*}_{\mathcal{B}}$. Before that, we need the following upper and lower
bounds for the probability density function $\rho(x)$ of a noise distribution.

######  Lemma 4.14 (Upper and lower bounds for $\rho(x)$ [20]).

For any noise distribution $\mathcal{D}$ has a generalized exponential tail,
there exists $n_{0}$ such that for any $n>n_{0}$ and
$x\geq\left(\frac{2\sum_{i=1}|c_{i}|}{c_{0}}\right)^{\frac{1}{\gamma_{0}-\gamma_{1}}}\cdot(\ln
n)^{\frac{1}{2\gamma_{0}}}$, the probability density function
$\rho(x)=\exp(-\sum_{i}c_{i}x^{\gamma_{i}})$ of $\mathcal{D}$ has the
following upper and lower bound:

$(1+\beta)c_{0}x^{\gamma_{0}-1}e^{-(1+\beta)c_{0}x^{\gamma_{0}}}\leq\rho(x)\leq(1-\beta)c_{0}x^{\gamma_{0}-1}e^{-(1-\beta)c_{0}x^{\gamma_{0}}}.$

######  Lemma 4.15 (Bounds for $\xi^{*}_{\mathcal{G}}$ and
$\xi^{*}_{\mathcal{B}}$).

With probability $1-O(\frac{1}{\log n})$, $\xi^{*}_{\mathcal{G}}\geq
m_{\mathcal{G}}$ and $\xi^{*}_{\mathcal{B}}\leq M_{\mathcal{B}}$.

###### Proof.

For a single sample $\xi$ drawn from noise distribution $\mathcal{D}$, we have

$\mathbb{P}\left[\xi\leq
m_{\mathcal{G}}\right]=1-\int^{\infty}_{m_{\mathcal{G}}}\rho(x)dx\leq
1-\int^{\infty}_{m_{\mathcal{G}}}(1+\beta)c_{0}x^{\gamma_{0}-1}e^{-(1+\beta)c_{0}x^{\gamma_{0}}}dx=1-\frac{\ln
n}{|\mathcal{G}|},$

which follows from the lower bound shown in Lemma 4.14 when $n$ is
sufficiently large. The probability that all $\xi(S_{L}+e)\ (e\in\mathcal{G})$
are bounded by $m_{\mathcal{G}}$ is at most

$\left(1-\frac{\ln n}{|\mathcal{G}|}\right)^{|\mathcal{G}|}\leq\frac{1}{e^{\ln
n}}=\frac{1}{n}.$

Hence $\xi^{*}_{\mathcal{G}}\geq m_{\mathcal{G}}$ holds with probability at
least $1-\frac{1}{n}$.

The probability that a single noise multiplier $\xi$ is bounded by
$M_{\mathcal{B}}$ is at least

$\mathbb{P}\left[\xi\leq
M_{\mathcal{B}}\right]=1-\int^{\infty}_{M_{\mathcal{B}}}\rho(x)dx\geq
1-\int^{\infty}_{M_{\mathcal{B}}}(1-\beta)c_{0}x^{\gamma_{0}-1}e^{-(1-\beta)c_{0}x^{\gamma_{0}}}dx=1-\frac{1}{|\mathcal{B}|\ln
n},$

which follows from the upper bound shown in Lemma 4.14 when $n$ is
sufficiently large. Then we obtain

$\mathbb{P}[\xi^{*}_{\mathcal{B}}\leq
M_{\mathcal{B}}]\geq\left(1-\frac{1}{|\mathcal{B}|\ln
n}\right)^{|\mathcal{B}|}\geq 1-\frac{1}{\ln n}.$

Therefore, by a union bound, $\xi^{*}_{\mathcal{G}}\geq m_{\mathcal{G}}$ and
$\xi^{*}_{\mathcal{B}}\leq M_{\mathcal{B}}$ hold with probability
$1-O(\frac{1}{\log n})$. ∎

With Lemma 4.15, we have

$\max_{e\in\mathcal{G}}\tilde{f}(S_{L}+e)\geq
m_{\mathcal{G}}h(S_{L})>\left(1-\frac{\varepsilon}{2}\right)M_{\mathcal{B}}h(S_{L})>\max_{e\in\mathcal{B}}\tilde{f}(S_{L}+e)$

with probability $1-O(\frac{1}{\log n})$. Thus a bad element will not be
selected by Algorithm 3 at the $\tilde{f}$-maximization phase, i.e.,
$f(S_{M})\geq(1-\varepsilon)h(S_{L})$. ∎

By Ineq. (10) and Lemma 4.12, we complete the proof of Theorem 4.1.

###  4.2 Algorithmic results for cardinality constraints when
$r\in\Omega\left(n^{\frac{1}{3}}\right)$

We present in this subsection an algorithm (Algorithm 5) and its analysis
(Theorem 4.16) that can be applied to $r\in\Omega\left(n^{\frac{1}{3}}\right)$
when $n$ is sufficiently large.

######  Theorem 4.16 (Algorithmic results for cardinality constraints when
$r\in\Omega\left(n^{\frac{1}{3}}\right)$).

Let $\varepsilon>0$ and assume
$n\in\Omega\left(\frac{1}{\varepsilon^{4}}\right)$ is sufficiently large. For
any $r\in\Omega\left(n^{\frac{1}{3}}\right)$, there exists an algorithm that
returns a $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation for
Problem 2.6 under a $r$-cardinality constraint, with probability
$1-O\left(\frac{1}{n^{2}}\right)$ and query complexity at most
$O(n^{6}\varepsilon^{-1})$ to $\tilde{f}$.

The above theorem addresses the remaining range of $r$ in Theorem 4.1, and
also achieves a tight approximation ratio of $1-\frac{1}{e}-O(\varepsilon)$
with $\text{Poly}(n,1/\varepsilon)$ queries to $\tilde{f}$.

####  4.2.1 Useful notations and useful facts for Theorem 4.16

Our algorithm and analysis in this subsection are based on another smoothing
surrogate function $h$.

######  Definition 4.17 (Smoothing surrogate function ii@).

Given a subset $H\subseteq N$, for any set $S\subseteq N\setminus H$, we
define the smoothing surrogate function $h_{H}(S)$ as
$h_{H}(S)=\sum_{H_{j}\subseteq H}f(S\cup H_{j})/2^{|H|}$.

Intuitively, if $|H|$ is sufficiently large, the surrogate function $h$ is
robust to noise as it is based on a large averaging set with size $2^{|H|}$.
Throughout the rest of this subsection, we consider the case that
$|H|\in\Omega(\log n)$. Similar to Section 4.1.1, we give some basic
properties of $h_{H}$.

######  Lemma 4.18 (Properties of $h_{H}$).

For any $H\subseteq N$, the smoothing surrogate function $h_{H}$ is monotone
and submodular, and for all $S\subseteq N\setminus H$,
$h_{H}(S)\geq\frac{1}{2}f(S\cup H)+\frac{1}{2}f(S)$.

###### Proof.

For any set $S\subseteq N$ and $x\not\in S$, by Definition 4.17, we have

$h(S+x)-h(S)=\frac{1}{2^{|H|}}\sum\limits_{H_{j}\subseteq H}\left[f(S\cup
H_{j}+x)-f(S\cup H_{j})\right],$

which immediately indicates that $h$ is monotone. Moreover, for a set
$T\subseteq S$,

$\displaystyle h(T+x)-h(T)$
$\displaystyle=\frac{1}{2^{|H|}}\sum\limits_{H_{j}\subseteq H}\left[f(T\cup
H_{j}+x)-f(T\cup H_{j})\right]$
$\displaystyle\geq\frac{1}{2^{|H|}}\sum\limits_{H_{j}\subseteq H}\left[f(S\cup
H_{j}+x)-f(S\cup H_{j})\right]$ (submodularity of $f$)
$\displaystyle=h(S+x)-h(S).$

Thus $h$ is also submodular. Finally, we lower bound $h_{H}(A)$ as below:

$\displaystyle h_{H}(A)$ $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{1}{2^{|H|}}\sum\limits_{H_{j}\subseteq H}f(A\cup
H_{j})$ $\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2^{|H|+1}}\sum\limits_{H_{j}\subseteq H}\left[f(A\cup H_{j})+f(A\cup
H\setminus H_{j})\right]$ $\displaystyle\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \frac{1}{2^{|H|+1}}\sum\limits_{H_{j}\subseteq
H}\left[f(A\cup H)+f(A)\right]$ (submodularity of $f$)
$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{1}{2}\left[f(A\cup H)+f(A)\right].$

∎

Given a cardinality $r$ and a set $H\subseteq N$, we define a
$(r-|H|)$-cardinality constraint confined on $N\backslash H$ as
$\mathcal{I}_{H}(r)=\left\\{S\subseteq N\setminus H:|S|=r-|H|\right\\}$.
Similar to Section 4.1.1, we provide the following lemma indicating that the
auxiliary function $\varphi_{h_{H}}$ can be well approximated.

######  Lemma 4.19 (Approximation of $\varphi_{h_{H}}$).

Let $\varepsilon>0$ and assume $n\in\Omega\left(\varepsilon^{-4}\right)$. For
a set $H$ with $|H|\geq 3\ln n$, there exists a value oracle $\mathcal{O}$ to
a $\left(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{3}{n^{6}},\mathcal{I}_{H}(r)\right)$-approximation
$\widehat{\varphi_{h_{H}}}$ of $\varphi_{h_{H}}$, which answering
$\mathcal{O}(A)$ queries $\tilde{f}$’s oracle
$O\left(r\varepsilon^{-1}\log^{\frac{5}{2}}n\log^{2}r\right)$ times for each
set $A\in\mathcal{I}_{H}(r)$.

The above lemma indicates that for sufficiently large $n$ and $|H|$, we can
achieve an almost accurate approximation $\widehat{\varphi_{h_{H}}}$ of
$\varphi_{h_{H}}$, which queries $\tilde{f}$ only
$\tilde{O}(n\varepsilon^{-1})$ times for each $\widehat{\varphi_{h_{H}}}(A)$.
By Corollay 3.9, we set $\delta=\frac{3}{n^{6}}$ when applying Algorithm 1.

###### Proof.

For any set $A\subseteq N$, we rewrite $\varphi_{h_{H}}(A)$ as a linear
combination of $f(T)$ according to Definitions 3.1 and 4.17:

$\varphi_{h_{H}}(A)=\frac{1}{2^{|H|}}\sum\limits_{T\subseteq
A}\sum\limits_{H_{i}\subseteq H}m_{|A|-1,|T|-1}f(T\cup H_{i}).$

We will use Algorithm 4 to construct the oracle of approximate function
$\widehat{\varphi_{h_{H}}}$. Similar to Lemma 4.4, we first show some bounds
of coefficients $m_{|A|-1,|T|-1}$. With these bounds, we will then prove
$\varphi_{h_{H}}$ and its noisy analogue $\widetilde{\varphi_{h_{H}}}$ are
close to each other by Bernstein’s inequality for sub-exponential variables.
Finally, we use Hoeffding’s inequality to show that with enough samples,
$\widehat{\varphi_{h_{H}}}$ is close to $\widetilde{\varphi_{h_{H}}}$ and
therefore a good approximation of $\varphi_{h_{H}}$.

Input : Noisy oracle $\tilde{f}$, a set $A\in\mathcal{I}_{H}(r)$ and
$\varepsilon\in(0,1/2)$

1 Let $M=32rH_{r}^{2}\log^{\frac{5}{2}}n\cdot\varepsilon^{-1}$ and
$s(A)=\sum_{T\subseteq A}m_{|A|-1,|T|-1}$

2 Construct a distribution $\nu_{A}(B)$ on set $2^{N}$ such that
$\nu_{A}(B)=\left\\{\begin{array}[]{ll}\dfrac{m_{|A|-1,|T|-1}}{2^{|H|}s(A)}&\mbox{
if there exists $T\subseteq A$ and $H_{i}\subseteq H$ such that $B=T\cup
H_{i}$}\\\ 0&\mbox{otherwise}\end{array}\right.$

3 Sample $M$ subsets $B_{1},\cdots,B_{M}$ with distribution $\nu_{A}(B)$

4 $\widehat{\varphi_{h}}(A)\leftarrow
s(A)\sum\limits_{i=1}^{M}\tilde{f}(B_{i})/M$

return $\widehat{\varphi_{h}}(A)$

Algorithm 4 Approximation of $\varphi_{h}$

######  Lemma 4.20 (Useful bounds of the coefficients).

For any $A\subseteq N$ with size $|A|\geq 2$, we have

$\displaystyle(1)\leavevmode\nobreak\ \leavevmode\nobreak\
\sum\limits_{T\subseteq A}m_{|A|-1,|T|-1}\leq H_{|A|};$ ([7, Lemma 2])
$\displaystyle(2)\leavevmode\nobreak\ \leavevmode\nobreak\
\sum\limits_{T\subseteq
A}m^{2}_{|A|-1,|T|-1}\leq\dfrac{e^{2}}{(e-1)^{2}}\dfrac{2}{|A|}\leq 3.$

###### Proof.

It only remains to estimate the bound of $\sum\limits_{T\subseteq
A}m^{2}_{|A|-1,|T|-1}$. We have

$\displaystyle\sum\limits_{T\subseteq
A}m^{2}_{|A|-1,|T|-1}\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\sum\limits_{i=1}^{|A|}\left(\int_{0}^{1}\frac{e^{p}}{e-1}p^{i-1}(1-p)^{|A|-i}dp\right)^{2}\binom{|A|}{i}$
(Definition 3.1) $\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ $
$\displaystyle\frac{e^{2}}{(e-1)^{2}}\sum\limits_{i=1}^{|A|}\left(\int_{0}^{1}p^{i-1}(1-p)^{|A|-i}dp\right)^{2}\binom{|A|}{i}$
($p\in[0,1]$) $\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\frac{e^{2}}{(e-1)^{2}}\sum\limits_{i=1}^{|A|}\left(\frac{\Gamma(i)\Gamma(|A|-i+1)}{\Gamma(|A|+1)}\right)^{2}\binom{|A|}{i}$
(Ineq. (7)) $\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\frac{e^{2}}{(e-1)^{2}}\left(\frac{1}{|A|}+\sum\limits_{i=2}^{|A|}\frac{1}{i(|A|-i+1)}\frac{1}{\binom{|A|}{i-1}}\right)$
($\binom{|A|}{i-1}\geq|A|$) $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\frac{e^{2}}{(e-1)^{2}}\frac{2}{|A|}\leq 3.$

∎

To show that $\widehat{\varphi_{h_{H}}}$ is a
$\left(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{3}{n^{6}},\mathcal{I}_{H}(r)\right)$-approximation of
$\varphi_{h_{H}}$, it suffices to prove

$\mathbb{P}\left[\left|\widehat{\varphi_{h_{H}}}(A)-\varphi_{h_{H}}(A)\right|>\frac{\varepsilon}{4rH_{r}}\cdot\varphi_{h_{H}}(A)\right]\leq\frac{3}{n^{6}}.$

First, we prove the the following lemma using concentration properties of sub-
exponential random variables.

######  Lemma 4.21 (Difference between $\varphi_{h_{H}}$ and
$\widetilde{\varphi_{h_{H}}}$).

If $|H|=\lceil 3\ln n\rceil$, we have

$\mathbb{P}\left[|\widetilde{\varphi_{h_{H}}}(A)-\varphi_{h_{H}}(A)|>\dfrac{\varepsilon}{8rH_{r}}\varphi_{h_{H}}(A)\right]\leq\frac{2}{n^{6}}.$
(14)

###### Proof.

Let $\xi$ be a random variable with a generalized exponential tail
distribution $\mathcal{D}$. The varaiable $\xi-1$ has a finite sub-exponential
norm $\kappa$ by Claim 4.7. Let

$X_{i,j}=\frac{1}{2^{|H|}}\cdot m_{|A|-1,|T_{j}|-1}f(T_{j}\cup
H_{i})\cdot(\xi_{T_{j}\cup H_{i}}-1),$

where $H_{i}\subseteq H$, $T_{j}\subseteq A$ and $i\in[2^{|H|}]$,
$j\in[2^{|A|}]$. Applying Bernstein’s inequality (Lemma 4.8) gives

We can bound $\max_{i,j}\left\|X_{i,j}\right\|_{\psi_{1}}$ by

$\max_{i,j}\left\|X_{i,j}\right\|_{\psi_{1}}\leq\frac{\kappa}{2^{|H|}}f(A\cup
H)\cdot\max_{T_{j}}m_{|A|-1,|T_{j}|-1}\leq\frac{3}{2^{|H|}}\kappa\cdot f(A\cup
H),$

where we use the fact that for any $a,t\geq 0$,

$m_{a,t}=\int_{0}^{1}\frac{e^{p}}{e-1}p^{t}(1-p)^{a-t}dp\leq 3.$

With Lemma 4.20, $\sum\limits_{i,j}\left\|X_{i,j}\right\|^{2}_{\psi_{1}}$ can
be bounded by

$\sum\limits_{i,j}\left\|X_{i,j}\right\|^{2}_{\psi_{1}}\leq\frac{1}{2^{|H|}}\sum\limits_{T_{j}\subseteq
A}m^{2}_{|A|-1,|T_{j}|-1}\left(f(A\cup
H)\right)^{2}\kappa^{2}\leq\frac{3}{2^{|H|}}\kappa^{2}(f(A\cup H))^{2}.$

For a sufficiently large $n\in\Omega(\varepsilon^{-4})$, we have $|H|\geq 3\ln
n\geq\ln\left(\frac{36864\kappa^{2}}{c}r^{2}H_{r}^{2}\ln
n\cdot\varepsilon^{-2}\right)$. Then by Lemma 4.18 and direct calculations, we
can conclude that

$\displaystyle\min\left(\frac{\left(\dfrac{\varepsilon}{8rH_{r}}\right)^{2}\left(\varphi_{h_{H}}(A)\right)^{2}}{\sum\limits_{i,j}\left\|X_{i,j}\right\|^{2}_{\psi_{1}}},\frac{\dfrac{\varepsilon}{8rH_{r}}\varphi_{h_{H}}(A)}{\max\limits_{i,j}\left\|X_{i,j}\right\|_{\psi_{1}}}\right)\geq\frac{6}{c}\ln
n.$

Therefore Ineq. (14) holds. ∎

Next we prove the following lemma using Hoeffding’s inequality (Lemma 4.10).

######  Lemma 4.22 (Difference between $\widehat{\varphi_{h_{H}}}$ and
$\widetilde{\varphi_{h_{H}}}$).

If $n\in\Omega(\varepsilon^{-4})$, we have

$\mathbb{P}\left[|\widehat{\varphi_{h_{H}}}(A)-\widetilde{\varphi_{h_{H}}}(A)|>\dfrac{\varepsilon}{8rH_{r}}\varphi_{h_{H}}(A)\right]\leq\frac{1}{n^{6}}.$

###### Proof.

To use Hoeffding’s inequality, we need a bound $b$ for noise multipliers. If
the noise distribution $\mathcal{D}$ has bounded support, this bound is
natural. When the support of $\mathcal{D}$ is not bounded, we let

$b=\frac{16}{c_{0}}\ln\left(n\cdot c_{0}^{-\frac{1}{4}}\right).$

Recall that we sample $M$ sets $B_{1},\dots,B_{M}$ to estimate
$\widehat{\varphi_{h}}(A)$ in Algorithm 4. We say that event $\mathcal{E}_{A}$
happens if for all $i\in[M]$, we have $\xi_{B_{i}}\leq b$. If the support of
$\mathcal{D}$ is bounded, event $\mathcal{E}_{A}$ trivially holds. Otherwise,
for a distribution with unbounded support, recall that when

$x\geq\max\left\\{1,\left(\frac{2\sum_{i=1}|c_{i}|}{c_{0}}\right)^{\frac{1}{\gamma_{0}-\gamma_{1}}}\right\\},$

we have the probability density $\rho(x)\leq
e^{-\frac{1}{2}c_{0}x^{\gamma_{0}}}\leq e^{-\frac{1}{2}c_{0}x}$. When $n$ is
sufficiently large, we have

$\mathbb{P}\left[\xi\geq
b\right]\leq\int_{b}^{\infty}\exp\left(-\frac{1}{2}c_{0}x\right)dx\leq\frac{2}{c_{0}}\exp\left(-\frac{1}{2}c_{0}b\right)=\frac{2}{n^{8}}.$

Thus by taking a union bound, event $\mathcal{E}_{A}$ happens with probability
at least $1-{2M}/{n^{8}}$. Conditioned on event $\mathcal{E}_{A}$, consider
the random variables $X_{i}=s(A)\tilde{f}(B_{i})$. We bound $X_{i}$ by

$\displaystyle X_{i}$ $\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\
s(A)\xi_{B_{i}}f(B_{i})$ (Definition 2.4) $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ H_{r}bf(B_{i})$ (Lemma 4.20 with $|A|\leq r$ and
event $\mathcal{E}_{A}$) $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ H_{r}bf(A\cup H).$ (monotonicity of $f$)

Thus applying Hoeffding’s inequality (Lemma 4.10), we obtain

$\displaystyle\mathbb{P}\left[|\widehat{\varphi_{h_{H}}}(A)-\widetilde{\varphi_{h_{H}}}(A)|>\dfrac{\varepsilon}{8rH_{r}}\varphi_{h_{H}}(A)\right]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{2}{n^{8}},$

which holds for a sufficiently large $n$ such that $\ln^{2}n\geq b$.
Therefore,
$|\widehat{\varphi_{h}}(A)-\widetilde{\varphi_{h}}(A)|>\frac{\varepsilon}{8rH_{r}}\varphi_{h}(A)$
holds with probability at most

$\frac{2M}{n^{8}}+\left(1-\frac{2M}{n^{8}}\right)\frac{2}{n^{8}}=O(n^{-6}).$

∎

Combining Lemma 4.21 and 4.22, we complete the proof of Lemma 4.19.

∎

####  4.2.2 Algorithm for Theorem 4.16

We present Algorithm 5 that mainly contains a local search phase (Line 3). The
main difference from Algorithm 3 is that Algorithm 5 arbitrarily select a
redundant set $H$ (Line 1), and use this set to construct a smoothing
surrogate function $h_{H}$ for local search (Line 3). Then Algorithm 5 returns
$S_{L}\cup H$ directly (Line 4) without a $\tilde{f}$-maximization phase.

Input : a value oracle to $\tilde{f}$, budget
$r\in\Omega\left(n^{\frac{1}{3}}\right)$, and $\varepsilon\in(0,1/2)$

1 Arbitrarily select a subset $H\subseteq N$ with $|H|=\lceil 3\ln n\rceil$

2 Let $\widehat{\varphi_{h_{H}}}$ be a $\left(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{3}{n^{6}},\mathcal{I}_{H}(r)\right)$-approximation of
$\varphi_{h_{H}}$ as in Lemma 4.19

$S_{L}\leftarrow\mathtt{NLS}\left(\widehat{\varphi_{h_{H}}},\mathcal{I}_{H}(r),\Delta=\frac{\varepsilon}{4r\ln
r}\right)$

$\triangleright$ Local search phase

return $S_{L}\cup H$

Algorithm 5 Noisy local search under large cardinality constraint

####  4.2.3 Proof of Theorem 4.16

Again, we first analyze the query complexity and then prove the approximation
performance.

##### Query complexity of Algorithm 5.

Since $n\in\Omega\left(\frac{1}{\varepsilon^{4}}\right)$, we have $I\in
O(n^{2})$ in Corollary 3.9. Hence Line 4 calls the oracle of
$\widehat{\varphi_{h_{H}}}$ at most $O(rn^{3})$ times by Corollary 3.9, and
each call to $\widehat{\varphi_{h_{H}}}$ queries $\tilde{f}$ at most
$O\left(r\varepsilon^{-1}\log^{\frac{5}{2}}n\log^{2}r\right)$ times by Lemma
4.19. Thus we query $\tilde{f}$ at most $O(n^{6}\varepsilon^{-1})$ times.

##### Approximation ratio and success probability of Algorithm 5.

Corollary 3.9, we have
$h_{H}(S_{L})\geq\left(1-\frac{1}{e}-\varepsilon\right)\cdot\max_{S\subseteq\mathcal{I}_{H}(r)}h_{H}(S)$
with probability $1-O\left(\frac{1}{n^{2}}\right)$. Furthermore, $f(S_{L}\cup
H)\geq h_{H}(S_{L})$ follows from the monotonicity of $f$. Then we can
demonstrate the approximation performance of Algorithm 5 by the following
lemma.

######  Lemma 4.23.

Let $O^{\star}=\mathop{\arg\max}_{S\in\mathcal{I}(r)}f(S)$. We have
$\max_{S\in\mathcal{I}_{H}(r)}h_{H}(S)\geq\left(1-\frac{|H|}{r}\right)f(O^{\star})$.

Roughly speaking, there exists a subset $A\subseteq O^{\star}$ of size $|H|$
such that $f(O^{\star}\backslash
A)\geq\left(1-\frac{|H|}{r}\right)f(O^{\star})$ by submodularity of $f$. The
claim follows from $\max_{S_{L}\in\mathcal{I}_{H}(r)}h_{H}(S)\geq
h(O^{\star}\backslash A)\geq f(O^{\star}\backslash A)$.

###### Proof.

We first show that a random set $A$, which is uniformly selected from all
subsets of $N$ with size $|H|$, satisfies that

$\mathop{\mathbb{E}}\left[f(O^{\star}\setminus
A)\right]\geq\left(1-\frac{|H|}{r}\right)f(O^{\star}).$

To prove this, we index $O^{\star}$ as $\\{o_{1},\cdots,o_{r}\\}$ and denote
by $I_{A}$ the indexes of elements in $O^{\star}\cap A$. Then we decompose
$f(O^{\star})$ as below:

$f(O^{\star})=\sum\limits_{i=1}^{r}f(o_{i}\mid o_{t},\leavevmode\nobreak\
t\in[i-1]),$

where $o_{0}$ is defined to be $\varnothing$. Similarly, we decompose
$f(O^{\star}\setminus H)$ as

$\displaystyle f(O^{\star}\setminus A)\leavevmode\nobreak\
=\leavevmode\nobreak\ $ $\displaystyle\sum\limits_{i\in[r]\setminus
I_{A}}f(o_{i}\mid o_{t},\leavevmode\nobreak\ t\in[i-1]\mbox{ and }t\not\in
I_{A})$ $\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\ $
$\displaystyle\sum\limits_{i\in[r]\setminus I_{A}}f(o_{i}\mid
o_{t},\leavevmode\nobreak\ t\in[i-1]).$ (submodularity of $f$)

Taking an expectation gives

$\displaystyle\mathop{\mathbb{E}}\left[f(O^{\star}\setminus
A)\right]\leavevmode\nobreak\ \geq\leavevmode\nobreak\ $
$\displaystyle\mathop{\mathbb{E}}\left[\sum\limits_{i\in[r]\setminus
I_{A}}f\left(o_{i}\mid o_{t},\leavevmode\nobreak\ t\in[i-1]\right)\right]$
$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\left(1-\frac{|H|}{r}\right)\left(\sum\limits_{i=1}^{r}f(o_{i}\mid
o_{t},\leavevmode\nobreak\
t\in[i-1])\right)=\left(1-\frac{|H|}{r}\right)f(O^{\star}).$

Thus there must exist a set $A_{0}$ such that $f(O^{\star}\setminus
A_{0})\geq\left(1-\frac{|H|}{r}\right)f(O^{\star})$. Therefore, we have

$\max\limits_{S\in\mathcal{I}_{H}(r)}h_{H}(S)\geq h_{H}(O^{\star}\setminus
A_{0})\geq f(O^{\star}\setminus
A_{0})\geq\left(1-\frac{|H|}{r}\right)f(O^{\star}).$

∎

Combining the fact that $f(S_{L}\cup
H)\geq\left(1-\frac{1}{e}-\varepsilon\right)\max_{S\subseteq\mathcal{I}_{H}(r)}h_{H}(S)$
with Lemma 4.23, we complete the proof of Theorem 4.16.

##  5 Our algorithms and main theorems for general matroid constraints

In this section, we consider Problem 2.6 under matroid constraints. Similarly,
for different ranges of matroid ranks, we prove there are
$(1-\frac{1}{e}-O(\varepsilon))/2$-approximate algorithms (Theorems 5.1 and
5.7). W.l.o.g., we assume that all single elements are feasible for the given
matroid constraints.

###  5.1 Algorithmic results for matroid constraints with rank
$r\in\Omega\left(\frac{1}{\varepsilon}\right)\cap
O\left(n^{\frac{1}{3}}\right)$

In this section, we generalize Algorithm 3 to deal with general matroid
constraints, which results in an algorithm (Algorithm 6) achieving the
performance stated in Theorem 5.1.

######  Theorem 5.1 (Algorithmic results for matroid constraints with rank
$r\in\Omega\left(\frac{1}{\varepsilon}\log\left(\frac{1}{\varepsilon}\right)\right)\cap
O\left(n^{\frac{1}{3}}\right)$).

Let $\varepsilon>0$ is sufficiently small and assume
$n\in\Omega\left(\exp\left(\left(\frac{1}{\varepsilon}\right)^{O(1)}\right)\right)$
is sufficiently large. For any
$r\in\Omega(\varepsilon^{-1}\log(\varepsilon^{-1}))\cap
O\left(n^{\frac{1}{3}}\right)$, there exists an algorithm that returns a
$\left(\left(1-\frac{1}{e}\right)/2-O(\varepsilon)\right)$-approximation for
Problem 2.6 under a matroid constraint $\mathcal{I}(\mathcal{M})$ with rank
$r$, with probability at least $1-O\left(\varepsilon^{4}\right)$ and query
complexity at most $O\left(r^{2}\log^{2}r\cdot
n^{\frac{3}{2}}\varepsilon^{-1}\max\\{r,\log n\\}\right)$ to $\tilde{f}$.

The main difference from Theorem 4.1 is that the approximation ratio is
$\left(1-\frac{1}{e}\right)/2-O(\varepsilon)$ instead of
$1-\frac{1}{e}-O(\varepsilon)$. The reason is that to maintain the feasibility
of the output, we may not be able to add an element to $S_{L}$ as in Line 3 of
Algorithm 3. To address this issue, we design a comparison procedure (Lines
4-8 of Algorithm 6) to evaluate the value of $f(S_{L})$ and $f(S_{M}\setminus
S_{L})$ and output the larger one, which results in a loss on the
approximation ratio. Moreover, the failure probability of the comparison
procedure is upper bounded by $O(\varepsilon^{4})$.

####  5.1.1 Useful notations and useful facts for Theorem 5.1

The local search procedure in this subsection is still based on the smoothing
surrogate function $h$ in Definition 4.2. Similar to Lemma 4.4, we can
construct a
$\left(\alpha,\delta,\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})\right)$-approximation
of auxiliary function $\varphi_{h}$.

######  Lemma 5.2 (Approximation of $\varphi_{h}$).

Let $\alpha,\delta\in(0,1/2)$ and assume
$n\in\Omega(\alpha^{-2}\log(\delta^{-1}))$. There exists a value oracle
$\mathcal{O}$ to an
$\left(\alpha,\delta,\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})\right)$-approximation
$\widehat{\varphi_{h}}$ of $\varphi_{h}$, which answering $\mathcal{O}(A)$
queries at most $O\left(\log r\cdot n^{\frac{1}{2}}\max\\{r,\log n\\}\right)$
times to $\tilde{f}$ for each set
$A\in\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})$.

Compared with the $\left(\alpha,\delta,\mathcal{I}(r-1)\right)$-approximation
in Lemma 4.4, an
$\left(\alpha,\delta,\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})\right)$-approximation
requires a smaller estimation error
$\alpha\cdot\max\limits_{S\in\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$
than $\alpha\cdot\max\limits_{S\in\mathcal{I}(r-1)}\varphi_{h}(S)$. However,
the proof of Lemma 4.4 remains valid for Lemma 5.2. This is because for any
set $A\in\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})$, we can still bound
$f(T)$ for all $T\in\mathcal{L}_{A}$ by
$2\cdot\max_{S\in\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})}\varphi_{h}(S)$
as in Eq. (9). Thus the concentration results (Lemma 4.9 and 4.11) in the
proof hold as well.

Besides $\varphi_{h}$ (Definition 3.1) guiding the local search, we introduce
another auxiliary function $\widehat{f}_{0}$ in this subsection, which will be
used to compare the values of sets at the final step of Algorithm 6.

######  Definition 5.3 (Comparison auxiliary function).

For any set $S\subseteq N$, we define the comparison auxiliary function
$f_{0}(S)$ as the expectation of $f(S-e)$ over a random element $e\in S$,
i.e.,

$f_{0}(S)=\frac{1}{|S|}\sum_{e\in S}f(S-e).$

The comparison auxiliary function $f_{0}$ is close to $f$ in the sense that
the following lemma holds.

######  Lemma 5.4 (Bounds of $f_{0}$).

For any set $S\subseteq N$, we have

$\left(1-\frac{1}{|S|}\right)f(S)\leq f_{0}(S)\leq f(S).$

###### Proof.

From monotonicity of $f$, we have $f_{0}(S)\leq f(S)$ immediately. We index
the elements of $S$ as $s_{i}$, where $i\in[|S|]$. Then

$\displaystyle f_{0}(S)$ $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\ \frac{1}{|S|}\sum_{e\in S}\left[f(S)-f(e\mid
S-e)\right]$ (Definition 5.3) $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\ f(S)-\frac{1}{|S|}\sum_{e\in S}f(e\mid S-e)$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
f(S)-\frac{1}{|S|}\sum_{i\in[|S|]}f(s_{i}\mid s_{1},s_{2},\cdots,s_{i-1})$
(submodularity of $f$) $\displaystyle\leavevmode\nobreak\
=\leavevmode\nobreak\ \left(1-\frac{1}{|S|}\right)f(S).$
($\sum_{i\in[|S|]}f(s_{i}\mid s_{1},\cdots,s_{i-1})=f(S)$)

∎

Note that $f_{0}$ is also implicitly constructed since we only have a value
oracle to $\tilde{f}$ instead of $f$. We denote $f_{0}$’s noisy analogue as
$\widetilde{f_{0}}$, i.e.,

$\widetilde{f_{0}}(S)=\frac{1}{|S|}\sum_{e\in S}\tilde{f}(S-e).$

As $f_{0}(S)$ is based on an averaging set of size $|S|$, the following lemma
indicates that $f_{0}$ and $\widetilde{f_{0}}$ are close to each other when
$|S|$ is sufficiently large.

######  Lemma 5.5 (Concentration property of $f_{0}$).

Let $\varepsilon,\delta\in(0,1/2)$ and suppose that
$|S|\geq\kappa\varepsilon^{-1}\ln(2\delta^{-1})$, where $\kappa$ is the sub-
exponential norm of the noise multiplier. For any subset $S\subseteq N$, we
have

$\mathbb{P}\left[\left|\widetilde{f}_{0}(S)-f_{0}(S)\right|>\varepsilon\cdot
f_{0}(S)\right]\leq\delta.$

###### Proof.

For any set $T\in\\{S-e:e\in S\\}$, let $X_{T}=\xi(T)-1$ and
$a_{T}=\frac{1}{|S|}\cdot f(T)$. Recall that $X_{T}$ is a sub-exponential
random variable with norm $\kappa$ by Claim 4.7. Applying Bernstein’s
inequality for sub-exponential variables (Lemma 4.8) gives

$\mathbb{P}\left[\left|\widetilde{f}_{0}(S)-f_{0}(S)\right|>\varepsilon
f_{0}(S)\right]\leq
2\exp\left[-c\min\left(\frac{\varepsilon^{2}|S|^{2}}{\kappa^{2}},\frac{\varepsilon|S|}{\kappa}\right)\right].$

By assumption that $|S|\geq\kappa\varepsilon^{-1}\ln(2\delta^{-1})$, the
probability above is at most $\delta$. ∎

####  5.1.2 Algorithm for Theorem 5.1

We present Algorithm 6 that is a variant of Algorithm 3. The main difference
is that Algorithm 6 contains a comparison phase (Line 4-7). Since $S_{M}$ may
not be an independent set defined by $\mathcal{I}(\mathcal{M})$, Algorithm 6
compares $S_{L}$ returned by local search with the element $S_{M}\backslash
S_{L}$ obtained at the $\tilde{f}$-maximization phase and returns the one with
a larger $\widetilde{f_{0}}$ value.

Input : a value oracle to $\tilde{f}$, rank
$r\in\Omega\left(\frac{1}{\varepsilon}\log\left(\frac{1}{\varepsilon}\right)\right)\cap
O\left(n^{\frac{1}{3}}\right)$ and $\varepsilon\in(0,1/2)$

1 Let $\widehat{\varphi_{h}}$ be a $\left(\frac{\varepsilon}{4r\ln
r},\frac{1}{(I+1)(r-1)n^{2}},\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M})\right)$-approximation
of $\varphi_{h}$ as in Lemma 5.2

$S_{L}\leftarrow\mathtt{NLS}\left(\widehat{\varphi_{h}},\mathcal{I}(r-1)\cap\mathcal{I}(\mathcal{M}),\Delta=\frac{\varepsilon}{4r\ln
r}\right)$

$\triangleright$ Local search phase

$S_{M}\leftarrow S_{L}+\mathop{\arg\max}\limits_{e\in N\backslash
S_{L}}\tilde{f}(S_{L}+e)$

$\triangleright$ $\tilde{f}$-maximization phase

2 if  _$\widetilde{f}_{0}(S_{L})\geq\frac{1}{2}\widetilde{f}_{0}(S_{M})$_ then

return $S_{L}$

$\triangleright$ Comparison phase

3

4else

5 return $S_{M}\backslash S_{L}$

Algorithm 6 Noisy local search subject to matroids with small ranks

####  5.1.3 Proof of Theorem 5.1

We first analyze the query complexity and then prove the approximation
performance of Algorithm 6.

##### Query complexity of Algorithm 6.

We call the noisy oracle $\tilde{f}$ only $(2r-1)$ times at the comparison
phase. The query complexity of Algorithm 6 is dominated by the number of calls
it makes at the local search phase and therefore of the same order
$\tilde{O}(r^{2}n^{\frac{3}{2}}\varepsilon^{-1})$ as Algorithm 3.

##### Approximate ratio and success probability of Algorithm 6.

Recall that
$O_{f}\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}f(S)$ denote
an optimal solution to $f$. Similar to the analysis of Algorithm 3, it can be
shown that we obtain a set $S_{M}$ at the end of the $\tilde{f}$-maximization
phase such that with probability $1-O\left(1/\log n\right)$,

$f(S_{M})\geq\left(1-\frac{1}{e}-O(\varepsilon)\right)f(O_{f}).$ (15)

Although $S_{M}$ may not be an independent set, we can decompose $S_{M}$ into
two feasible parts $S_{L}\in\mathcal{I}(\mathcal{M})$ and $S_{M}\backslash
S_{L}\in\mathcal{I}(\mathcal{M})$ and output one of them. The approximate
ratio of the output set is guaranteed by the following lemma.

######  Lemma 5.6.

We assume a sufficient small $\varepsilon$ and suppose that
$r\in\Omega\left(\varepsilon^{-1}\log(\varepsilon^{-1})\right)$. Let $S_{R}$
denote the set returned by Algorithm 6. With probability at least
$1-2\varepsilon^{4}$, we have

$f(S_{R})\geq\left(\frac{1}{2}-O(\varepsilon)\right)f(S_{M}).$

###### Proof.

By Lemma 5.5 with $\delta=\varepsilon^{4}$, we have

$\left|\widetilde{f}_{0}(S)-f_{0}(S)\right|\leq\varepsilon f_{0}(S)$ (16)

holds for both $S_{L}$ and $S_{M}$ with probability at least
$1-2\varepsilon^{4}$. Suppose this is true.

If $\widetilde{f}_{0}(S_{L})\geq\frac{1}{2}\widetilde{f}_{0}(S_{M})$, then
$S_{R}$ is $S_{L}$. We translate the inequality into that of $f_{0}$ by Ineq.
(16):

$f_{0}(S_{L})\geq\frac{\widetilde{f}_{0}(S_{L})}{1+\varepsilon}\geq\frac{\widetilde{f}_{0}(S_{M})}{2(1+\varepsilon)}\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\cdot
f_{0}(S_{M}).$

Then from Lemma 5.4, we have

$f(S_{L})\geq
f_{0}(S_{L})\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\cdot
f_{0}(S_{M})\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\left(1-\frac{1}{r}\right)f(S_{M}).$

For any $r>1/\varepsilon$, the inequality above implies that

$f(S_{L})\geq\left(\frac{1}{2}-2\varepsilon\right)f(S_{M}).$

Algorithm 6 returns $S_{M}\setminus S_{L}$ if
$\widetilde{f}_{0}(S_{L})<\frac{1}{2}\widetilde{f}_{0}(S_{M})$. Similarly, we
convert this by Ineq. (16) into the following inequality:

$f_{0}(S_{L})\leq\frac{\widetilde{f_{0}}(S_{L})}{1-\varepsilon}\leq\frac{1}{2}\cdot\frac{\widetilde{f_{0}}(S_{M})}{1-\varepsilon}\leq\frac{1}{2}\cdot\frac{1+\varepsilon}{1-\varepsilon}f_{0}(S_{M}).$

By Lemma 5.4,

$f(S_{L})\leq\frac{r-1}{r-2}f_{0}(S_{L})<\frac{1}{2}\cdot\frac{1+\varepsilon}{1-\varepsilon}\cdot\frac{r-1}{r-2}f_{0}(S_{M})\leq\frac{1}{2}\cdot\frac{1+\varepsilon}{1-\varepsilon}\cdot\frac{r-1}{r-2}f(S_{M}),$

which is directly followed by

$f(S_{L})<\frac{1}{2}(1+5\varepsilon)f(S_{M})$

if $\varepsilon<1/3$ and $r\geq 2/\varepsilon$. Since submodularity of $f$
indicates that $f(S_{L})+f(S_{M}\setminus S_{L})\geq f(S_{M})$, we have

$f(S_{M}\setminus S_{L})\geq\left(\frac{1}{2}-3\varepsilon\right)f(S_{M}).$

∎

Combining Ineq. (15) and Lemma 5.6, we prove that Algorithm 6 achieves a
$((1-1/e)/2-O(\varepsilon))$-approximation with probability
$1-O(\varepsilon^{4})$.

###  5.2 Algorithmic results for matroid constraints with rank
$r\in\Omega\left(n^{\frac{1}{3}}\right)$

We present in this subsection an algorithm (Algorithm 7) and its analysis
(Theorem 5.7) that can be applied to $r\in\Omega\left(n^{\frac{1}{3}}\right)$
when $n$ is sufficiently large.

######  Theorem 5.7 (Algorithmic results for matroid constraints with rank
$r\in\Omega\left(n^{\frac{1}{3}}\right)$).

Let $\varepsilon>0$ and assume
$n\in\Omega\left(\frac{1}{\varepsilon^{4}}\right)$ is sufficiently large. For
$r\in\Omega\left(n^{\frac{1}{3}}\right)$, there exists an algorithm returning
a $\left(\left(1-\frac{1}{e}\right)/2-O(\varepsilon)\right)$-approximation for
Problem 2.6 under a matroid constraint $\mathcal{I}(\mathcal{M})$ with rank
$r$, with probability $1-O\left(\frac{1}{n^{2}}\right)$ and query complexity
$O(n^{6}\varepsilon^{-1})$ to $\tilde{f}$. Specifically, for a strongly base-
orderable matroid (Definition C.1), the approximation ratio can be improved to
$1-\frac{1}{e}-O(\varepsilon)$.

The main difference from Theorem 4.16 is again the approximation ratio. For
maintaning the feasibility, we divide an arbitrary base into two equal-size
subsets, apply Algorithm 5 to both subsets, and output the larger one.
Consequently, we achieve a
$\left(\left(1-\frac{1}{e}\right)/2-O(\varepsilon)\right)$-approximation
ratio. Specifically, for a strongly base-orderable matroid, we can use its
good exchangable property to maintain the feasibility without sacrificing the
approximation ratio; see Section C for a complete proof.

####  5.2.1 Useful facts for Theorem 5.7

Our algorithm and analysis in this subsection are based on the smoothing
surrogate function $h_{H}$ in Definition 4.17 and comparison auxiliary
function $f_{0}$ in Definition 5.3. We introduce a contraction matroid
$\mathcal{I}_{H}(\mathcal{M})$ confined on $N\backslash H$. Any feasible set
$S\in\mathcal{I}_{H}(\mathcal{M})$ can be converted to an independent set
subject to $\mathcal{I}(\mathcal{M})$ by adding $H$.

######  Definition 5.8 (Contraction matroid).

For any subset $H$ and matroid constraint $\mathcal{I}(\mathcal{M})$, we
define contraction matroid over $N\setminus H$ as the following:

$\mathcal{I}_{H}(\mathcal{M})=\\{S\subseteq N\setminus H:S\cup
H\in\mathcal{I}(\mathcal{M})\\}.$

Similar to Lemma 4.19, the following lemma indicates that the auxiliary
function $\varphi_{h_{H}}$ can be well approximated.

######  Lemma 5.9 (Approximation of $\varphi_{h_{H}}$).

Let $\varepsilon>0$ and for sufficiently large
$n\in\Omega(\frac{1}{\varepsilon^{4}})$. If $|H|\geq 3\ln n$, there exists a
value oracle $\mathcal{O}$ to an $(\frac{\varepsilon}{4r\ln
r},\frac{3}{n^{6}},\mathcal{I}_{H}(\mathcal{M}))$-approximation
$\widehat{\varphi_{h_{H}}}$ of $\varphi_{h_{H}}$, in which answering
$\mathcal{O}(A)$ queries at most $\tilde{f}$’s oracle
$O(r\varepsilon^{-1}\log^{\frac{5}{2}}n\log^{2}r)$ times of $\tilde{f}$ for
each set $A\in\mathcal{I}$.

The proof of Lemma 4.19 actually demonstrates a stricter claim that for any
set $A\in\mathcal{I}_{H}(r)$,
$\mathbb{P}\left[\left|\widehat{\varphi_{h}}(A)-\varphi_{h}(A)\right|>\frac{\varepsilon}{4r\ln
r}\varphi_{h_{H}}(A)\right]\leq\frac{3}{n^{6}}$. Since
$\mathcal{I}_{H}(\mathcal{M})\subseteq\mathcal{I}_{H}(r)$, the proof remains
valid for Lemma 5.9.

####  5.2.2 Algorithm for Theorem 5.7

Input : a value oracle to $\tilde{f}$, rank
$r\in\Omega\left(n^{\frac{1}{3}}\right)$, and $\varepsilon\in(0,1/2)$

1 Arbitrarily select a basis $B_{0}\subseteq N$ and spilt $B_{0}$ into two
parts $H_{1},H_{2}$ with size $\lfloor\frac{r}{2}\rfloor$ or
$\lfloor\frac{r}{2}\rfloor+1$

2

3for  _$t=1,2$_ do

4 Let $\widehat{\varphi_{h_{H_{t}}}}$ be a $(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{3}{n^{6}},\mathcal{I}_{H_{t}}(\mathcal{M}))$-approximation of
$\varphi_{h_{H_{t}}}$ as in Lemma 5.9

$S_{t}\leftarrow\mathtt{NLS}\left(\widehat{\varphi_{h_{H_{t}}}},\mathcal{I}_{H_{t}}(\mathcal{M}),\Delta=\frac{\varepsilon}{4r\ln
r}\right)$

$\triangleright$ Local search phase

5

Let
$i^{\star}\leftarrow\mathop{\arg\max}\limits_{t\in\\{1,2\\}}\widetilde{f_{0}}(S_{t}\cup
H_{t})$

$\triangleright$ Comparison phase

return $S_{i^{\star}}\cup H_{i^{\star}}$

Algorithm 7 Noisy local search subject to matroids with large ranks

We present Algorithm 7 that contains two phases: a local search phase (Lines
2-4) and a comparison phase (Line 5). Algorithm 7 arbitrarily splits a basis
(maximal independent set) into two parts of almost the same size, and it then
grows each one of them into a basis using Algorithm 1, respectively. Finally
the algorithm compares two solutions $S_{t}\cup H_{t}\ (t=1,2)$ and outputs
the better one in terms of $\widetilde{f_{0}}$.

####  5.2.3 Proof of Theorem 5.7

To prove Theorem 5.7, we analyze the query complexity and approximation
performance of Algorithm 6 as below.

##### Query Complexity of Algorithm 7.

The number of calls to $\tilde{f}$ during local search phase dominates the
query complexity of Algorithm 7 as it queries only $2r$ times at the
comparison phase. Algorithm 7 runs the local search procedure twice, and thus
the query complexity of Algorithm 7 is of the same order
$O(n^{6}\varepsilon^{-1})$ as that of Algorithm 5.

##### Approximation performance analysis of Algorithm 7.

Similar to the analysis of Algorithm 5, for $t\in\\{1,2\\}$, Corollary 3.9
implies that with probability $1-O\left(\frac{1}{n^{2}}\right)$,

$f(S_{t}\cup
H_{t})\geq\left(1-\frac{1}{e}-\varepsilon\right)\max\limits_{S\subseteq\mathcal{I}_{H_{t}}(\mathcal{M})}h_{H_{t}}(S).$
(17)

Recall that $O^{\star}\in\mathop{\arg\max}_{S\in\mathcal{I}(\mathcal{M})}f(S)$
denotes an optimal solution. The following lemma relates
$\max_{S\subseteq\mathcal{I}_{H_{t}}(\mathcal{M})}h_{H_{t}}(S_{t})$ to
$f(O^{\star})$.

######  Lemma 5.10.

$f(O^{\star})\leq\max\limits_{S\subseteq\mathcal{I}_{H_{1}}(\mathcal{M})}h_{H_{1}}(S_{1})+\max\limits_{S\subseteq\mathcal{I}_{H_{2}}(\mathcal{M})}h_{H_{2}}(S_{2})$.

###### Proof.

We first introduce a lemma concerning the structure of matroids.

######  Lemma 5.11 (See [10]).

Given two bases $B_{1},\ B_{2}$ of a matroid $\mathcal{M}$ a partition
$B_{1}=X_{1}\cup Y_{1}$ , there is a partition $B_{2}=X_{2}\cup Y_{2}$ such
that $X_{1}\cup Y_{2}$ and $X_{2}\cup Y_{1}$ are both bases of $\mathcal{M}$.

The lemma above indicates that there is a partition of $O^{\star}=O_{1}\cup
O_{2}$ such that $O_{t}\cup H_{t}\in\mathcal{I}(\mathcal{M})$ for
$t\in\\{1,2\\}$. Hence we have

$\displaystyle\max\limits_{S\subseteq\mathcal{I}_{H_{1}}(\mathcal{M})}h_{1}(S_{1})+\max\limits_{S\subseteq\mathcal{I}_{H_{2}}(\mathcal{M})}h_{2}(S_{2})$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
h_{H_{1}}(O_{1})+h_{H_{2}}(O_{2})$ $\displaystyle\leavevmode\nobreak\
\geq\leavevmode\nobreak\ f(O_{1})+f(O_{2})$ (monotonicity of $f$)
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\ f(O_{1}\cup
O_{2})=f(O^{\star}).$ (submodularity of $f$)

∎

Finally, we show that comparison with noisy auxiliary function
$\widetilde{f_{0}}$ causes only a small loss in the approximate ratio.

######  Claim 5.12.

We assume a sufficient small $\varepsilon$ and suppose that
$r\in\Omega\left(n^{\frac{1}{3}}\right)$. Let $S_{R}$ denote the set returned
by Algorithm 7. With probability at least $1-\frac{2}{n^{4}}$, we have

$f(S_{R})\geq\left(\frac{1}{2}-O(\varepsilon)\right)\left(f(S_{1}\cup
H_{1})+f(S_{2}\cup H_{2})\right).$

###### Proof.

By Lemma 5.5 with $\delta=1/n^{4}$, we have

$\left|\widetilde{f}_{0}(S)-f_{0}(S)\right|\leq\varepsilon f_{0}(S)$ (18)

holds for both $S_{1}\cup H_{1}$ and $S_{2}\cup H_{2}$ with probability at
least $1-2/n^{4}$. Suppose this is true. Then for $t\in\\{1,2\\}$, we have

$\displaystyle f_{0}(S_{R})$
$\displaystyle\geq\frac{1}{1+\varepsilon}\cdot\widetilde{f_{0}}(S_{R})$ (Ineq.
(18))
$\displaystyle\geq\frac{1}{2(1+\varepsilon)}\cdot\left(\widetilde{f_{0}}(S_{1}\cup
H_{1})+\widetilde{f_{0}}(S_{2}\cup H_{2})\right)$
($\widetilde{f_{0}}(S_{R})=\max_{t\in\\{1,2\\}}\widetilde{f_{0}}(S_{t}\cup
H_{t})$)
$\displaystyle\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\cdot\left(f_{0}(S_{1}\cup
H_{1})+f_{0}(S_{2}\cup H_{2})\right).$ (Ineq. (18)) (19)

We convert this inequality of $f_{0}$ to that of $f$:

$\displaystyle f(S_{R})$ $\displaystyle\geq f_{0}(S_{R})$ (Lemma 5.4)
$\displaystyle\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\cdot\left(f_{0}(S_{1}\cup
H_{1})+f_{0}(S_{2}\cup H_{2})\right)$ (Ineq. (19))
$\displaystyle\geq\frac{1}{2}\cdot\frac{1-\varepsilon}{1+\varepsilon}\cdot\left(1-\frac{1}{r}\right)\left(f(S_{1}\cup
H_{1})+f(S_{2}\cup H_{2})\right)$ (Lemma 5.4)
$\displaystyle\geq\left(\frac{1}{2}-2\varepsilon\right)\left(f(S_{1}\cup
H_{1})+f(S_{2}\cup H_{2})\right),$ ($\frac{1-\varepsilon}{1+\varepsilon}\geq
1-2\varepsilon$ and $r\geq 1/\varepsilon$)

which completes the proof. ∎

Combining Ineq. (17), Claim 5.10 and Claim 5.12, we can conclude that with
probability $1-O\left(\frac{1}{n^{2}}\right)$,

$f(S_{i^{\star}}\cup
H_{i^{\star}})\geq\left(\frac{1}{2}\left(1-\frac{1}{e}\right)-O(\varepsilon)\right)f(O^{\star}),$

which matches Theorem 5.7.

##  6 Discussions

For any cardinality $r\geq 2$, Algorithms 3 and 5 return a
$\left(\left(1-\frac{1}{r}\right)\left(1-\frac{1}{e}\right)-O\left(\varepsilon\right)\right)$-approximation
for monotone submodular maximization problem under noise with query complexity
$\mathrm{Poly}\left(n,\frac{1}{\varepsilon}\right)$. When
$r\in\Omega\left(\frac{1}{\varepsilon}\right)$, the approximation ratio can be
written as $\left(1-\frac{1}{e}\right)-O(\varepsilon)$ (Theorem 1.1). However,
if $r\in O\left(\frac{1}{\varepsilon}\right)$, then this ratio is not close to
the optimal one. In this case, [20] provide an algorithm that achieves
$\left(1-\frac{1}{r}\right)$-approximation with query complexity
$\Omega(n^{r})$. It remains open whether there is an algorithm that returns
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation with query
complexity $\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ for $r\in
O\left(\frac{1}{\varepsilon}\right)$. The main challenges of our approach to
handle this range of $r$ is that the introduction of surrogates (Definition
4.2) inevitably results in a loss of $\frac{1}{r}$ in approximation ratio. For
the special case of $r=1$, one of the few known results is an algorithm by
[20] achieving a $\frac{1}{2}$-approximation guarantee in expectation, which
is information theoretically tight. To the best of our knowledge, there is no
with-high-probability result for this case.

Another limitation of this work is that we only consider independent noise.
For non-i.i.d. noise, [11] indicate that no algorithm can achieve a constant
approximation when the noise multipliers are arbitrarily correlated across
sets. Considering this, it may be worthwhile to consider special cases of
correlated distributions for which optimal guarantees can be obtained. One of
them is a model called $d$-correlated noise [11]: a noise distribution is
$d$-correlated if for any two sets $S$ and $T$ such that $|S\backslash
T|+|T\backslash S|>d$, the noise is applied independently to $S$ and to $T$.
The noise multipliers can be arbitrarily correlated when $S$ and $T$ are
similar in the sense that $|S\backslash T|+|T\backslash S|\leq d$. We notice
that our algorithms can be naturally extended to $d$-correlated noise for
$d\in O(1)$. In particular, to adapt Algorithm 3 to deal with $d$-correlated
noise, we need to arbitrarily split $N$ into sets
$T_{1},\dots,T_{\lfloor\frac{N}{d+1}\rfloor}$ and define the smoothing
surrogate function as $h(S)=\frac{1}{L}\sum^{L}_{l=1}f(S\cup T_{l})$ to
replace the original surrogate.

##  7 Conclusions

In this work, we study the problem of constrained monotone submodular
maximization with noisy oracles. We design a unified local search framework
that allows for inaccuracy in the objective function. Under this framework, we
construct several smoothing surrogate functions to average the noise out. For
cardinality constraints, the local search framework results in algorithms that
achieve a $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation with
$\text{Poly}\left(n,\frac{1}{\varepsilon}\right)$ query complexity. Moreover,
for general matroid constraints, the framework obtains an approximation ratio
arbitrarily close to $\left(1-\frac{1}{e}\right)/2$, which is the first
constant approximation result to our knowledge.

There are many directions in which this work could be extended. For submodular
maximization with noisy oracles under general matroid constraints, there is a
gap between the approximation ratio of $\left(1-1/e\right)/2-O(\varepsilon)$
provided in this paper and impossibility results [5, 20]. The first open
question is to close this gap. In addition, it would be interesting to
consider more complex constraints under noise including knapsack constraints
[4]. It is meaningful to investigate submodular maximization with correlated
noise. Moreover, it is also worthwhile to investigate the robustness of other
submodular optimization approaches, e.g., multi-linear extension [25].

## Acknowledgements

We are grateful to Dr. Bei Xiaohui for his good counsel and valuable comments
on the manuscript.

## References

  * [1] Niv Buchbinder and Moran Feldman.  Submodular functions maximization problems.  In Handbook of Approximation Algorithms and Metaheuristics, page 771–806. Chapman and Hall/CRC, 2018.
  * [2] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM Journal on Computing, 40(6):1740–1766, 2011.
  * [3] Christopher P Chambers and Federico Echenique.  Revealed Preference Theory.  Cambridge University Press, 2016.
  * [4] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing, 43(6):1831–1879, 2014.
  * [5] Uriel Feige.  A threshold of $\ln n$ for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * [6] Vitaly Feldman.  On the power of membership queries in agnostic learning.  The Journal of Machine Learning Research, 10:163–182, 2009.
  * [7] Yuval Filmus and Justin Ward.  Monotone submodular maximization over a matroid via non-oblivious local search.  SIAM Journal on Computing, 43(2):514–542, 2014.
  * [8] Marshall L Fisher, George L Nemhauser, and Laurence A Wolsey.  An analysis of approximations for maximizing submodular set<EMAIL_ADDRESS>In Polyhedral combinatorics, pages 73–87. Springer, 1978.
  * [9] Amir Globerson and Sam Roweis.  Nightmare at test time: robust learning by feature deletion.  In Proceedings of the 23rd international conference on Machine learning, pages 353–360, 2006.
  * [10] Curtis Greene.  A multiple exchange property for bases.  Proceedings of the American Mathematical Society, 39(1):45–50, 1973\.
  * [11] Avinatan Hassidim and Yaron Singer.  Submodular optimization under noise.  In Conference on Learning Theory, pages 1069–1122. PMLR, 2017.
  * [12] Thibaut Horel and Yaron Singer.  Maximization of approximately submodular functions.  Advances in neural information processing systems, 29, 2016.
  * [13] Shinji Ito.  Submodular function minimization with noisy evaluation oracle.  Advances in Neural Information Processing Systems, 32, 2019.
  * [14] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003.
  * [15] Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos.  Efficient sensor placement optimization for securing large water distribution networks.  Journal of Water Resources Planning and Management, 134(6):516–526, 2008.
  * [16] Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin.  Simultaneous placement and scheduling of sensors.  In 2009 International Conference on Information Processing in Sensor Networks, pages 181–192. IEEE, 2009.
  * [17] Jon Lee, Maxim Sviridenko, and Jan Vondrák.  Submodular maximization over multiple matroids via generalized exchange properties.  Mathematics of Operations Research, 35(4):795–806, 2010.
  * [18] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set<EMAIL_ADDRESS>Mathematical programming, 14(1):265–294, 1978.
  * [19] James G Oxley.  Matroid theory, volume 3.  Oxford University Press, USA, 2006.
  * [20] Yaron Singer and Avinatan Hassidim.  Optimization for approximate submodularity.  Advances in Neural Information Processing Systems, 31, 2018.
  * [21] Adish Singla, Sebastian Tschiatschek, and Andreas Krause.  Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization.  In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
  * [22] Maxim Sviridenko.  A note on maximizing a submodular set function subject to a knapsack constraint.  Operations Research Letters, 32(1):41–43, 2004.
  * [23] Marisa Thoma, Hong Cheng, Arthur Gretton, Jiawei Han, Hans-Peter Kriegel, Alex Smola, Le Song, Philip S Yu, Xifeng Yan, and Karsten Borgwardt.  Near-optimal supervised feature selection among frequent subgraphs.  In Proceedings of the 2009 SIAM International Conference on Data Mining, pages 1076–1087. SIAM, 2009.
  * [24] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science.  Cambridge University Press, 2018.
  * [25] Jan Vondrák.  Optimal approximation for the submodular welfare problem in the value oracle model.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67–74, 2008.
  * [26] Jan Vondrák, Chandra Chekuri, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 783–792, 2011.
  * [27] Dominic JA Welsh.  Matroid theory.  Courier Corporation, 2010.
  * [28] Robin J Wilson.  An introduction to matroid theory.  The American Mathematical Monthly, 80(5):500–525, 1973.

##  Appendix A The Invalid Result for General Matroid Constraints in [20]

In this section, we recall Algorithm 8 ([20, Algorithm 2]) and its analysis
Theorem A.1 ([20, Theorem 4.2]) proposed by [20] for monotone submodular
maximization with noisy oracles under general matroid constraints. We argue
that Algorithm 8 fails to obtain the approximation guarantee claimed in
Theorem A.1.

For a set $S\subseteq N$, a bundle $\boldsymbol{b}\subseteq N$ and an
intersection of matroids $\mathcal{F}$, the _mean value_ , _noisy mean value_
and _mean marginal contribution_ of $\boldsymbol{b}$ given $S$ are,
respectively:

$\displaystyle
F(S\cup\boldsymbol{b}):=\mathbb{E}_{\boldsymbol{z}\sim\mathcal{B}_{S}(\boldsymbol{b})}\left[f(S\cup\boldsymbol{z})\right]$
$\displaystyle\tilde{F}(S\cup\boldsymbol{b}):=\mathbb{E}_{\boldsymbol{z}\sim\mathcal{B}_{S}(\boldsymbol{b})}\left[\tilde{f}(S\cup\boldsymbol{z})\right]$
$\displaystyle
F_{S}(\boldsymbol{x}):=\mathbb{E}_{\boldsymbol{z}\sim\mathcal{B}_{S}(\boldsymbol{b})}\left[f_{S}(\boldsymbol{b})\right]$

where $\mathcal{B}_{S}(\boldsymbol{b})$ represents the ball around
$\boldsymbol{b}$, i.e.,
$\mathcal{B}_{S}(\boldsymbol{b})=\\{\boldsymbol{b}-x_{i}+x_{j}\in\mathcal{F}:x_{i}\in\boldsymbol{b},x_{j}\notin
S\cup\boldsymbol{x}\\}$.

Input : intersection of matroids $\mathcal{F}$, precision $\varepsilon>0$,
$c\leftarrow\frac{56}{\varepsilon}$

1 $S\leftarrow\varnothing$, $X\leftarrow N$

2 while  _$X\neq S$_ do

3 $X\leftarrow
X\backslash\\{\boldsymbol{x}:S\cup\boldsymbol{x}\notin\mathcal{F}\\}$

4
$\boldsymbol{x}\leftarrow\arg\max_{\boldsymbol{b}:|\boldsymbol{b}|=c}\tilde{F}(S\cup\boldsymbol{b})$

5
$\hat{\boldsymbol{x}}\leftarrow\arg\max_{\boldsymbol{z}\in\mathcal{B}_{S}(\boldsymbol{x})}\tilde{f}(S\cup\boldsymbol{z})$

6 $S\leftarrow S\cup\hat{\boldsymbol{x}}$

return $S$

Algorithm 8 SM-Matroid-Greedy

Algorithm 8 is a variant of the standard greedy algorithm, which at every
iteration adds a bundle $\hat{\boldsymbol{x}}$ of size
$c=\Theta(1/\varepsilon)$ instead of a single element. In each iteration, the
algorithm updates the set $X$ of candidate elements (Line 3) in order to
obtain a feasible set $S\in\mathcal{F}$. Then it selects a bundle
$\boldsymbol{x}\in\arg\max_{\boldsymbol{b}:|\boldsymbol{b}|=c}\tilde{F}(S\cup\boldsymbol{b})$
with the largest noisy mean value $\tilde{F}(S\cup\boldsymbol{b})$ (Line 4).
Finally, Algorithm 8 evaluates all possible bundles
$\boldsymbol{z}\in\mathcal{B}_{S}(\boldsymbol{x})$ in the ball around
$\boldsymbol{x}$ identified at last step and incorporates the one whose noisy
value $\tilde{f}(S\cup\boldsymbol{z})$ is largest (Line 5 and 6).

[20] claim that Algorithm 8 can achieve the following approximation
performance.

######  Theorem A.1 (Wrong theorem [20, Theorem 4.2]).

Let $\mathcal{F}$ denote the intersection of $P\geq 1$ matroids with rank
$r\in\Omega\left(\frac{1}{\varepsilon^{2}}\right)\cap\sqrt{\log n}$ on the
ground set $N$, and $f:2^{N}\rightarrow\mathbb{R}$ be a non-negative monotone
submodular function. Then with probability $1-o(1)$ the SM-Matroid-Greedy
algorithm returns a set $S\in\mathcal{F}$ s.t.:

$f(S)\geq\frac{1-\varepsilon}{P+1}.$

Now we argue that Theorem A.1 does not hold even under a single matroid
constraint. [20] employed [20, Lemma 3.4] to prove Theorem A.1. However, this
lemma cannot be generalized beyond cardinality constraints to matroid
constraints. This is because [20, Lemma 3.4] is based on the following fact:
for any bundle $\boldsymbol{b}$ of size $1/\varepsilon$,

$F_{S}(\boldsymbol{b})\geq(1-\varepsilon)f_{S}(\boldsymbol{b}).$ ([20, Lemma
2.2])

This fact results in [20, Corollary 2.3], which appears as the premise of [20,
Claim 3.1] to prove [20, Lemma 3.4]. Under a cardinality constraint, the ball
$\mathcal{B}_{S}(\boldsymbol{b})$ contains all the neighbors of a bundle
$\boldsymbol{b}$, which differ from $\boldsymbol{b}$ by only one element. A
bundle $\boldsymbol{b}$ with good margin is likely to be surrounded by
neighbors in $\mathcal{B}_{S}(\boldsymbol{b})$ which also have large margins
on average, and the fact that
$F_{S}(\boldsymbol{b})\geq(1-\varepsilon)f_{S}(\boldsymbol{b})$ naturally
holds. However, when we consider a matroid that restricts feasible neighbors
of $\boldsymbol{b}$ to be those with small margins only,
$F_{S}(\boldsymbol{b})$ can be far less than $f_{S}(\boldsymbol{b})$.

We provide a concrete example to show that Algorithm 8 cannot obtain any with-
high-probability constant approximation under a matroid constraint.

######  Claim A.2.

For any constant $m$, there exists a partition matroid $\mathcal{M}$ with rank
$r\in\Omega\left(\frac{1}{\varepsilon^{2}}\right)\cap O(\sqrt{\log n})$ for
which Algorithm 8 fails to achieve an approximate ratio better than $1/m$ with
probability at least $1/3$.

###### Proof.

Our plan is to construct a partition matroid for which Algorithm 8 performs
badly.

######  Definition A.3 (Partition matroid).

A matroid $\mathcal{M}=(N,\mathcal{I}(\mathcal{M}))$ is a partition matroid if
$N$ is partitioned into $k$ disjoint sets $C_{1},C_{2},\dots,C_{k}$ and

$\mathcal{I}(\mathcal{M})=\left\\{S\subseteq N:|C_{i}\cap S|\leq d_{i}\text{\
for\ }i=1,2,\dots,k\right\\}.$

Let there be $r$ disjoint sets, where
$r\in\Omega\left(\frac{1}{\varepsilon^{2}}\right)\cap O(\sqrt{\log n})$. For
all $i\in[r-1]$, $C_{i}$ contains only one element with value $0$. The set
$C_{r}$ with $|C_{r}|=n-r+1$ contains most of the elements. There is a special
element $e^{\star}$ in $C_{r}$ with $f(e^{\star})=m$, and other elements in
$C_{r}$ are all attributed with value $1$. An independent set of matroid
$\mathcal{M}$ contains at most one element from each disjoint set. That is,
$d_{1}=d_{2}=\cdots=d_{r}=1$. The noise distribution will return $m$ with
probability $\delta=\frac{1}{2(n-r)}$ and $1$ otherwise.

Now we apply Algorithm 8 to maximize $f$ under this matroid constraint with a
noisy oracle. Since the elements in $C_{i}\ (i\in[r-1])$ are all with value 0,
we focus on the bundles $\boldsymbol{b}$ that consist of an element in $C_{r}$
and some other elements $\boldsymbol{b}_{-r}$. Suppose Algorithm 8 selects one
of them as $\boldsymbol{x}$ at Line 4. Feasible bundles in
$\mathcal{B}_{S}(\boldsymbol{x})$ containing $e^{\star}$ can only be obtained
by changing one of the elements in $\boldsymbol{x}_{-r}$. Thus there are at
most $(c-1)(r-c)$ such bundles. With probability at least
$\left(1-\delta\right)^{(c-1)(r-c)}$, the noise multipliers on such bundles
are all $1$.

On the other hand, at least $n-r$ bundles in $\mathcal{B}_{S}(\boldsymbol{x})$
do not include $e^{\star}$. With probability at least $1-(1-\delta)^{n-r}$,
there exists one of these bundles with noise multiplier $m$. Thus Algorithm 8
selects a bundle that does not include $e^{\star}$ at Line 5 with probability
at least

$\left(1-\delta\right)^{(c-1)(r-c)}\left[1-\left(1-\delta\right)^{n-r}\right]\geq\left(1-\frac{(c-1)(r-c)}{2(n-r)}\right)\left(1-\frac{1}{\sqrt{e}}\right).$

When $n$ is sufficiently large, the probability above is at least $1/3$. ∎

By the proof of Claim A.2, we have an intuition that the problem of submodular
maximization under a partition matroid with any rank may degenerate to that
under $1$-cardinality constraint. The case of $r=1$ is rather difficult for
Problem 2.6, and the only known result is an algorithm by [20] which achieves
a $1/2$-approximation guarantee in expectation for this case. To the best of
our knowledge, there is no with-high-probability result before.

##  Appendix B More Related Work

Besides cardinality and single matroid constraints, more complex constraints
have also been considered in the context of submodular optimization before.
[8] present an algorithm achieving a $1/(k+1)$-approximation for monotone
submodular maximization under $k$ matroid constraints. [17] subsequently
improve the approximation guarantee to $1/(k+\varepsilon)$ for $k>2$. [22]
provides a $\left(1-\frac{1}{e}\right)$-approximation under knapsack
constraints. With the multilinear relaxation technique, [4] obtain a
$0.38/k$-approximation for maximizing a monotone submodular function subject
to $k$ matroids and a constant number of knapsack constraints.

##  Appendix C Approximation algorithm for strongly base-orderable matroid
constraints

In this section, we consider a special family of matroids, called _strongly
base-orderable matroids_.

######  Definition C.1 (Strongly base-orderable matroid).

A matroid $\mathcal{M}$ is strongly base-orderable if given any two bases
$B_{1}$ and $B_{2}$, there is a bijection $\sigma:B_{1}\to B_{2}$ such that
for any $X\subseteq B_{1}$, $(B_{1}\setminus X)\cup\sigma(X)$ is a basis, and
$(B_{2}\setminus\sigma(X))\cup X$ is a basis.

As is evident from Definition C.1, the cardinality constraint which we discuss
in Section 4 is a special case of strongly base-orderable matroid. Moreover,
this family of matroids includes many typical matroids as well, such as
partition matroids (Definition A.3) and transversal matroids.

Next we present an algorithm (Algorithm 9) and its analysis (Theorem C.2) that
achieves near-tight approximation guarantees subject to strongly base-
orderable matroids with rank $r\in\Omega\left(n^{\frac{1}{3}}\right)$.

######  Theorem C.2 (Algorithmic results for cardinality constraints when
$r\in\Omega\left(n^{\frac{1}{3}}\right)$).

Let $\varepsilon>0$ and assume
$n\in\Omega\left(\frac{1}{\varepsilon^{4}}\right)$ is sufficiently large. For
any $r\in\Omega\left(n^{\frac{1}{3}}\right)$, there exists an algorithm that
returns a $\left(1-\frac{1}{e}-O(\varepsilon)\right)$-approximation for
Problem 2.6 under a strongly base-orderable matroid constraint
$\mathcal{I}(\mathcal{M})$, with probability at least
$1-O\left(\frac{1}{n}\right)$ and query complexity at most
$O(n^{7}\varepsilon^{-1})$ to $\tilde{f}$.

Compared with Theorem 5.7, Theorem C.2 improves the approximate ratio to
$\left(1-\frac{1}{e}-O(\varepsilon)\right)$ for the strongly base-orderable
matroids, which have stronger exchangeable structures.

###  C.1 Algorithm for Theorem C.2

Similar to Algorithm 7, Algorithm 9 also contains two phases: a local search
phase (Lines 3-5) and a comparison phase (Line 6). The local search procedure
is based on the smoothing surrogate function $h_{H}$ in Definition 4.17, while
the comparison auxiliary function $f_{0}$ in Definition 5.3 is used at Line 6.
Algorithm 7 differs from Algorithm 9 by running the local search procedure
(Algorithm 1) $\lfloor\frac{r}{l}\rfloor$ times rather than twice, with
different smoothing surrogate functions $h_{H_{t}}$.

Input : a value oracle to $\tilde{f}$, rank
$r\in\Omega\left(n^{\frac{1}{3}}\right)$, and $\varepsilon\in(0,1/2)$

1 Let $l\leftarrow\lceil 3\ln n\rceil$

2 Arbitrarily select a basis $B_{0}$ and arbitrarily spilt $B_{0}$ into
$\lfloor\frac{r}{l}\rfloor$ parts $H_{1},\cdots,H_{\lfloor\frac{r}{l}\rfloor}$
with size $l$ or $l+1$

3 for  _$t=1,\cdots,\lfloor\frac{r}{l}\rfloor$_ do

4 Let $\widehat{\varphi_{h_{H_{t}}}}$ be a $(\alpha=\frac{\varepsilon}{4r\ln
r},\delta=\frac{3}{n^{6}},\mathcal{I}_{H_{t}}(\mathcal{M}))$-approximation of
$\varphi_{h_{H_{t}}}$ as in Lemma 5.9

$S_{t}\leftarrow\mathtt{NLS}\left(\widehat{\varphi_{h_{H_{t}}}},\mathcal{I}_{H_{t}}(\mathcal{M}),\Delta=\frac{\varepsilon}{4r\ln
r}\right)$

$\triangleright$ Local search phase

5

Let
$i^{\star}\leftarrow\mathop{\arg\max}\limits_{t\in[\lfloor\frac{r}{k}\rfloor]}\widetilde{f_{0}}(S_{t}\cup
H_{t})$

$\triangleright$ Comparison phase

return $S_{i^{\star}}\cup H_{i^{\star}}$

Algorithm 9 Noisy local search under strongly base-orderable matroid
constraints

###  C.2 Proof of Theorem C.2

We analyze the query complexity and approximation performance of Algorithm 9
to prove Theorem C.2. To simplify notation, we use $h_{t}$ to stand for
$h_{H_{t}}$, $\widehat{\varphi_{h_{t}}}$ for $\widehat{\varphi_{h_{H_{t}}}}$,
and $\mathcal{I}_{t}(\mathcal{M})$ for $\mathcal{I}_{H_{t}}(r)$ in the
analysis.

##### Query Complexity of Algorithm 9.

Similar to the proof of Theorem 5.7, Algorithm 9 runs the local search
procedure $\lfloor r/l\rfloor$ times, and thus the query complexity of
Algorithm 9 is at most $O({n^{7}}{\varepsilon}^{-1})$.

##### Approximation performance analysis of Algorithm 9.

Similarly, from mononicity of $f$ and Corollary 3.9, we have that

$f(S_{t}\cup
H_{t})\geq\left(1-\frac{1}{e}-\varepsilon\right)\max\limits_{S\subseteq\mathcal{I}_{t}(\mathcal{M})}h_{t}(S)$
(20)

holds for all $t\in[\lfloor r/l\rfloor]$ with probability
$1-O\left(\frac{r}{n^{2}}\right)$. Let
$O^{\star}\in\mathop{\arg\max}\limits_{S\in\mathcal{I}(\mathcal{M})}f(S)$ be
an optimal solution. The following lemma relates
$\max\limits_{S\subseteq\mathcal{I}_{t}(\mathcal{M})}h_{t}(S)$ to
$f(O^{\star})$.

######  Lemma C.3.

We have

$\mathop{\mathbb{E}}\limits_{t\sim\mathcal{U}}\left[\max\limits_{S\subseteq\mathcal{I}_{t}(\mathcal{M})}h_{t}(S)\right]\geq\left(1-\frac{l+1}{r}\right)f(O^{\star}),$

where $\mathcal{U}$ is a uniform distribution over
$[\lfloor\frac{r}{l}\rfloor]$.

###### Proof.

By Definition C.1, there is a bijection $\sigma:B_{0}\to O^{\star}$ between
the elements in $B_{0}$ and $O^{\star}$ such that for all
$t\in[\lfloor\frac{r}{l}\rfloor]$,
$(O^{\star}\setminus\sigma(H_{t}))\in\mathcal{I}_{t}(\mathcal{M})$. The
following lemma gives a lower bound of $f(O^{*}\setminus\sigma(H_{t}))$ in
expectation.

######  Lemma C.4.

Given an arbitrary partition $O_{1},\cdots,O_{\lfloor r/l\rfloor}$ of
$O^{\star}$ such that $|O_{t}|\in\\{l,l+1\\}\
(t\in[\lfloor\frac{r}{l}\rfloor])$, we have

$\mathop{\mathbb{E}}\limits_{t\sim\mathcal{U}}\left[f(O^{\star}\setminus
O_{t})\right]\geq\left(1-\frac{l+1}{r}\right)f(O^{\star}),$

where $\mathcal{U}$ is a uniform distribution over
$[\lfloor\frac{r}{l}\rfloor]$.

###### Proof.

We index $O^{\star}$ as $\\{o_{1},\cdots,o_{r}\\}$ and denote by $I_{t}$ the
indexes of the elements in $O_{t}$ for $t\in[\lfloor\frac{r}{l}\rfloor]$. We
can decompose $f(O^{\star})$ as

$f(O^{\star})=\sum\limits_{i=1}^{r}f(o_{i}\mid o_{k},k\in[i-1]).$

$f(O^{\star}\setminus O_{t})$ can also be decomposed as below:

$\displaystyle f(O^{\star}\setminus O_{t})$
$\displaystyle=\sum\limits_{i\in[r]\setminus I_{t}}f(o_{i}\mid
o_{k},k\in[i-1]\mbox{ and }k\not\in I_{t})$
$\displaystyle\geq\sum\limits_{i\in[r]\setminus I_{t}}f(o_{i}\mid
o_{k},k\in[i-1]).$ (submodularity of $f$)

Taking an expectation over $t\in[\lfloor\frac{r}{l}\rfloor]$ gives

$\displaystyle\mathop{\mathbb{E}}_{t\sim\mathcal{U}}\left[f(O^{\star}\setminus
O_{t})\right]$