A Unified Approach to Submodular Maximization Under Noise
Authors: Kshipra Bhawalkar
Yang Cai
Zhe Feng
Christopher Liaw
Tao Lin
Venue: NeurIPS 2025 poster ()
Keywords: submodular maximization
noisy submodular maximization
robustness
continuous greedy algorithm
Primary area: theory
TL;DR: We develop a framework for noisy submodular maximization which allows us to reuse existing algorithms while retaining their guarantees.

Abstract: We consider the problem of maximizing a submodular function with access to a _noisy_ value oracle for the function instead of an exact value oracle.
Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value.
In this model, Hassidim and Singer (2017) design a $(1-1/e)$-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a $(1-1/e)/2$-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint.
In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee.
By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a $(1-1/e)$-approximation (resp. $1/e$-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise.
Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a $1/2$-approximation for unconstrained (non-monotone) submodular maximization under noise.

A Unified Approach to Submodular Maximization
Under Noise
Kshipra Bhawalkar
Yang Cai Yale University New Haven, CT yang. cai@yale edu
Google Mountain View, CA
kshipra@google.com
Zhe Feng Google
Christopher Liaw Google Mountain View, CA cvliar0google, com
Tao Lin" Harvard University Cambridge, MA tlin0g harvard edu
Mountain View, CA zhef@google.co com
Abstract
We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of exact value oracle. Similar prior work [3] [6], we assume that the noisy oracle is persistent in that multiple calls the oracle for specific set always return the same value. In this model, Hassidim and Singer [3] design a (1 - s/e)-approximation algorithm for mono- tone submodular maximization subject to cardinality constraint and Huang al. algorithm for monotone submodular
[16] design a (1 /aaee///--pppoximmati maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algoriut the measured continuous greedy algorithm, we obtain (1 - (/pp)))pppxxiiitiio (resp. 1/e a--aprxximaaiin) for monotone (resp. non-mon monotono) submodular maxi- mization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain 1 //2aapproximation for unconstrained (non-monotone) submodular maximization under noise.
with
Introduction
Submodular maximization is fundamental problem that frequently appears in various forms in many fields such as machine learning, combinatorial optimization, and economics. Submodular functions functions that satisfy the diminishing returns property. More formally, function f: 2 IR on a ground set N is said to be submodular if for any sets S C C N and element E N \ T, we have JSSU - /(S) (TT (TT). Despite the intuitive nature of submodular functions, many basic problems are NP-hard such as maximizing monotone submodular function subject to cardinality constraint or maximizing a non monooone submodular function without any constraints. Given the inherent intractability of this problem, there has been vast body of research that aims to develop computationally efficient approximation algorithms for maximizing submodular functions in various settings.
The standard model in submodular maximization assumes that we have value oracle access the submodular function f where, given set S, we can retrieve the exact value of f(S). However, in
Work done student researcher at Google in 2024.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

many settings it is not realistic to assume the existence of an exact value oracle. For example, in machine learning, we can never evaluate the true loss function of model as we do not have access to the true distribution of the population. At best, we may have access to noisy version of the loss function. In this paper, we study model for noisy submodular maximization introduced by Hassidim and Singer [3] where querying set S returns only an unbiased estimate of f(S). A notable feature of this model is persistent noise, where querying the value of a set twice returns the same value. Thus, simply querying submodular function multiple times at the same input cannot be used to denoise the function. Nonetheless, one can still ask whether existing algorithms work in this setting. However, Hassidim and Singer [33 show that this is probably unlikely. For example, they show that the natural greedy algorithm is too sensitive to noise and only obtains an of ((1) - aaproxxmmation despite being the optimal algorithm when there is no noise. Thus, new algorithms are needed to deal with noise.
For the problem of maximizing noisy monotone submodular function subject to a cardinality con- straint, Hassidim and Singer [3] designed an algorithm that achieves a tight (1 1/e))- 11/e)-aaprxximation At a high-level, their algorithm computes a smooth surrogate function which essentially averages a few queries together to obtain an estimate that may have less noise but potentially be biased. They then apply the greedy algorithm on this surrogate function to obtain a (1 11-1/6
follow-up work, Huang et al. [66 proved a (1 - 1/e)/ /tt///apppoiimatiii (1-1/e)-approne -/e)-approximationn In submodular maximization under an arbitrary matroid. This approximation ratio can be improved to property. While Huang et al. [16] also make use of the smoothing technique, their algorithm is based on a local search algorithm [0].
ratio for noisy monotone
1 - 1/ee e if the matroid satisfies a "strongly Wase-orderable
Main question. While prior work has established that submodular maximization feasible in the noisy setting, notable downside is that the algorithms and analyses are designed for their specific problems. For example, Hassidim and Singer [3] only obtain results for monotone submodular maximization subject to a cardinality constraint and, while Huang et al. [16] extend to arbitrary matroids, their analyses have a factor of 2 gap with the optimal result, despite an algorithm which is provably optimal in the non-noisy setting. Our main question is whether such specific analyses are necessary. In particular, we want to answer the following question:
Can we design a framework for noisy submodular maximization that allows us to reuse existing algorithms for the noiseless submodular maximization problems while retaining existing guarantees?
Our contributions. Our main contribution in this paper is an affirmative answer to the above question. In particular, we show that any algorithm for exact submodular optimization which is sufficiently "robust" can be translated to an algorithm for noisy submodular optimization with only an o(1) loss in the approximation ratio. For many settings, this obviates the need for designing new algorithms and instead relies only on checking whether existing algorithms are sufficiently robust. Our technique builds on but differs from 13 propose the use of random surrogate function, which circumvents the limitation of a deterministic surrogate function in [3]
For our first application, we instantiate our framework with the continuous greedy algorithm 4 4. Specifically, we use the measured continuous greedy algorithm of Feldman et al. g which gives (1 - 1/))-//pprooimaaiiii non-monotone submodular maximization, both subject to matroid constraints. As our framework inherits the approximation guarantees of these algorithms,, we achieve the same approximation ratios for the noisy setting, with only o(1) loss in the approximation ratio. Our second application is to instantiate our framework with the double greedy algorithm 3 to obtain 1/2-approximation for noisy unconstrained submodular maximization, which is tight even without noise. To our knowledge, we provide the first set of results for noisy submodular maximization for non-monotone functions, in both unconstrained and matroid constrained settings. We summarize our results in Table
for monotone submodular maximization and a 1 //e-approximation for
Other related works. Another work that is closely related ours is Hassidim and Singer 14. which also studies the setting where the noise is persistent. In particular, they considered intersection of matroids and show a 1/(1 + P)-approximation There have also been works that look at the noisy submodular setting but withoul persistent noise: for example, Singla et al. 220 consider model where one only has preference information, and Chen et al. 5 assume that one has access to noisy marginal estimates instead of value oracle.

---

Table 1: Our work compared with previous works on noisy submodular maximization. (tight) means
optimal approximation ratios achievable by polynomial-tie algorithms even without noise.
Submodular function
Constraint
Previous work
Our work
Cardinality
1 1/e (tight)
1 - 1-1/e (tight)
Monotone
13
Theorem 4.2
Matroid
1
1/e)/2
1-1/e (tight)
16
Theorem 4.2
Unconstrained
None
1/2 (tight)
Non-monotone
Theorem 4.5
Matroid
None
1/e Theorem 4.3
Another related line of work is optimizing approximately submodular functions, where the noise is not unbiased and can adversarial. Horel and Singer [15] show that even there only 1/ l/vn noise, the problem becomes intractable and prove exponential lower bounds the query complexity. On the other hand, they show that constant approximation algorithms are achievable when the "curvature" is bounded or when the noise is small in terms of the rank of the matroid. Zheng et al. [25) study maximizing approximately k-submodular functions. Chierichetti et al. [6] study functions that satisfy submodularity E-approximately and convert them to exactly submodular functions that are en eco-e to the original functions, establishing a reduction to the exact submodular setting. A difference with work is that our noisy value funetion far from being e-approximately submodular. A key contribution of our work is to convert our noisy value function to surrogate function that is close to the underlying submodular function, which then enables reduction similar to 6
less related line of work on online submodular maximization [22 [8 21 22). Here, one is given sequence of submodular functions f2. ........ and before seeing ft. player must decide
set to play. The goal is to minimize "a-regret" which is the difference between the value obtained by the player and an a-approximation of the optimum. Although the problem setting is different, these works also tend to show that many known algorithms are "robust" and develop a way to reuse these algorithms in the online setting. Such approach is similar to ours as show that number of algorithms are robust and reuse them for the noisy setting.
Preliminaries
Submodular set function. Let N be ground set of size |N| For set S and element we denote 5 + x S U {x) and 5 - x = fx). Let ʃ 2 - R2 be a non-negative function defined on subsets of N. Assume f(0) = of We use fs(x) = f(S + z) - f(S) to denote the N with respect to set C N. The function f is said to be:
marginal value of element
submodular for any subsets C C and any element E B, fa() 2 fb(z).
monotone if for any subsets A C B C N. f(A) J(B).
This work considers both monotone and non-monotone (general) submodular functions.
noisy value oracle for is denoted by f:2N RRz-- Following previous works [3 [6), we consider a multiplicative noisy value oracle defined by f(S) = (S) for all sets S N. where {s is non-negative random variable distributed according to some distribution D. We call Es the noise multiplier for set S. Following [3 [6], we assume that the noisy value
Noisy value oracle.
oracle satisfies the following three properties:
Unbiased: E[}(S)) S(S), namely, E[Es] 1
FFor our applications. this without loss generality since one can a "dummy" element Zo then detine g()) = 0, ((x)) = f0), and g(S) g(S+ = f(S) for S + 0. The function g remains submodular, and an a-approximation for maximizing gives an a-approximation for maximizing f. For feasibility. any set that was feasible for the original problem remains feasible after adding 20. This remains matroid constraint.

---

Persistent: querying set S multiple times returns the same value f(S).
Independent across different sets: for different sets SI....,,.. (..).......
f(5k) are independent.
Namely, , Es, are independent.
If one does not assume persistence, and querying f(S) multiple times gives independent estimates of f(S), then the problem becomes trivial since one can easily estimate f((S) by repeated sampling.
In this work, assume that the noise multiplier {s D is sub-exponential.
Definition 2.1 (see, e.g., Wainwright (24). A distribution DD (or random variable & ~ D) is sub-exponential with parameters (v, (x) if R[eA(s-E(1)) I e= holds for any X satisfying [ S 3-
Sub- cub-exponential distributions are large class of distributions, including bounded, Gaussian, and exponential distributions. For example, a random variable & bounded in [0, B) is sub-exponential with parameters (v B, a = 0). Moreover, sub-exponential distributions include the generalized exponential tail distributions that have been considered by previous work on monotone submodular maximization under noise [13 []]. We assume that the parameters (v, ai) of the sub-exponential distribution D are known while the distribution D itself is unknown.
Matroid constraints. We aim to maximize the function f using noisy value oracle f over subsets S C N that satisfy some constraints. Let C 2 be collection of feasible subsets of N. We assume I to be downward-closed: i.e., for / E I and l' C 1 E I.. We define two types of constraints:
Unconstrained: I = =-
Matroid constraint: I is called a matroid if, in addition to being downward-closed, the following condition holds: for any I1, I2 I satisfying |/|| < 1/2/, there exists an element e E /2 \ / such that I, U {e} E I. Each I E I is called an independent set. A maximal independent set is called a basis of the matroid. can be shown that all maximal independent sets are of the same size, which is called the rank of the matroid. We denote the rank by r(I).
An important special case of matroid constraint is cardinality constraint, where I E I if and only if [7] S
Given feasibility set I, use O" to denote optimal set. In other words, O E arg max f(S). We will use f(O") to denote the optimal value. Recall that solving the above optimization problem is generally NP-hard but efficient approximation algorithms are known for many settings.
A Unified Approach to Noisy Submodular Maximization
In this section, we present unified approach to the noisy submodular maximization problem. This approach is a reduction to the submodular maximization problem with the exact value oracle.
Theorem 3.1 (Informal). Let A be "robust" algorithm that obtains an a-approximation ratio to the problem maxsez (SS with exact value oracle. Then, A can be converted into an algorithm achieving an (a -(1)) apprrxxaapooiiiionn to the problem maxser f(S) with the noisy oracle f.
The definition of "robust" is in Section 3.2 and the formal theorem is Theorem 3.4 We remark that the conversion process above is agnostic to the algorithm A and just uses as a black box.
Our reduction uses an idea proposed by previous work on noisy submodular maximization This idea is estimate the value fSS of set S using the noisy value of some surrogate function F(S) = To. ΣreTs f(T') where Ts is a collection of sets related to S. One example is to choose small
B3 16
and let Ts- = {S H' for H' C HJ.. In previous work, different surrogate functions were constructed for different settings. Here, we construct a single surrogate function for all the settings we consider (unconstrained monomonte maximization, monotone and non-monotone maximization under matroid constraints); see Section 3.1 for details. Then, the reduction is to run the algorithm A to maximize the noisy surrogate function F(S) = 1.5 ΣTETs f(T) N F(S).
The main technical challenge here is to ensure that the surrogate function F(S) approximates the true function f(S) well. As shown by [I3 16), deterministic surrogate function does not always guarantee good approximation to the true function. So, they need to use arguments that are specific

---

to their algorithms to show that the surrogate functions work well. A key insight in our work is the use of random surrogate function. We show that such random surrogate function can approximate the true function in all settings with matroid constraints (see Section 3.3
3.1 Surrogate Function
Let H S N be subset of size H h where h is small integer. We call H smoothing set. Let t < h be another integer. Let H = {H' - H |H| = t be all the subsets H of size t; there are (.) such subsets. We use H' ~ [t) to denote sampling a subset H' S H of size t uniformly at random. Define a funntiatt FH, as follows:
F#*((S = BE
Σ (ISUH), JSSN. H'EHH
(I)
The surrogate marginal value of element with respect to Si 1 (()))
Remark 3.1. Another natural way to define a surrogate function would be to take the expectation over all subsets of and not just subsets of size t. This also works when the submodular function f is monotone. Intuitively, this is because adding elements could never hurt. However, when f is non-monotone, adding elements may degrade the value of f. We thus want to ensure that (4) is large enough for denoising but t small enough to limit the potential degradation.
Claim 3.2. The surrogate function F is submodular.
Because we do not have access to f. we cannot query the surrogate function HH directly. Instead, we can query the noisy surrogate function:
(.)
Σ i(SUH'),
NSSA
( H'EHN
and the noisy surrogate marginal value (x) P + (H). When (1) is large, F*)((S) is expensive compute exactly. Instead, we can approximately compute (S) by sampling sets HI.... Hm ~ H(1 and taking the sample average:
j.H. (S) = J(SUH.).
(3)
To guarantee a good concentration property of 1 m E j(SU Hi), we sample Hi...., Hm ~ H without replacement ensure that they are different sets, so f(S U Hı).... f(S U Hm) are independent. The following lemma shows that, with high probability, the sample average f. (S) close to the noisy surrogate value FHt((S) and the noisy surrogate value FR) close the true surrogate value F (S), when the parameters h, t, m satisfy some condition:
Lemma 3.3. Let fuax 2 maxsçN (S) be an upper bound on the maximum value of f. Suppose the noise distribution DD is (v, az) -bbeeepnnotl Suppose the integers h, t, m satisfy the following:
2 max|2, 8122 S (n + log log
t t² (4m), and h == t
(4)
Then, for S 5
2 a max, we have:
Pr VSCN
FF Se 5.
(5)
The proof of this lemma uses a Hoeffding inequality for sampling without replacement and a concentration analysis for sub-exponential distribution. It is given in Appendix B.I
3.2 A Meta-Algorithm for Noisy Submodular Maximization
We now present a "meta-algorithm" that converts any algorithm A for submodular maximization with exact value oracle to an algorithm for noisy value oracle. Given matroid I and a set H C N, we consider the contraction of I by defined as
Is = (S : SU. CI.
(6)
5

---

In other words, ZH is the matroid where the independent sets are all sets whose union with H are independent I. The meta-algorithm (Algorithm D works as follows: pick an arbitrary basis Bo of the original matroid Z, randomly sample subset H of Bo of size h. run A to maximize the approximate noisy surrogate function (S) over the minor matroid Σи to obtain solution Sи. and finally return the set Sh U where H' a random subset H of size
Algorithm 1: Meta- Meta-algorithm for noisy submodular maximization under matroid constraints Input :Noisy oracle f for a submodular function on ground set N. Matroid I.
Parameter th, m.
Let Bg be an arbitrary basis of matroid I, which has size Bol r. Sample subset H of Bo of size h uniformly at random.
Run submodular maximization algorithm A solve maXseтh FS):(S) using oracle fl
obtaining solution Sμ E Tn. Sample subset H' of H of size uniformly at random.
Return Sn U H'
Before presenting the main result for the meta-algorithm, we define the "robustness" of a submodular maximization algorithm. Let A be a-approximation algorithm for submodular maximization under constraint using the exact value oracle f. namely: the solution S. returned by A satisfies [[](SA)] maxser (SS). We say A is robust if its performance degrades only a little if the exact value oracle is replaced by an approximate oracle. This is formalized the following definition.
Definition 3.1 (Robustness). An e-approximate oracle for submodular function f a function f: NN - R. that satisfies [f(s) - f(S) S E for any queried set Algorithun A is ((e)-robust against e-approximate oracle if. when running A on E-approximate oracle f. the returned solution SA satisfies [Sf( 2 maxser f(E)
-
We are now ready to present our main result regarding the meta-algorithm.
Theorem 3.4. Suppose 0 < & < 2v² Jmax and the parameters h, I, satisfy 4 with 8 = 1/nn. If algorithum A has a a-approximation ratio and is -re)brt against E-approximate oracle, then the expected value of the solution ALG returned by Algortihm [ satisfies:
For non monotone submodular f. [[](ALG) 2 a r-h -())))))--- -(())
For monotone submodular J. [[J(AGG)) 2 ( - 3(e).
Let (AA) be the query complexity of A. The number of queries f made by Algorithm iis m- Q(A).
3.3 Proof of Theorem 3.4
key step to prove Theorem 3.4 is to show that, with a randomly sampled smoothing set H, maximizing the surrogate function HH, is roughly equivalent to maximizing the original function f. This is formalized by the following lemma, which we call a "smoothing lemma".
Lemma 3.5 (Smoothing lemma). Let f be a submodular function.
For any J, we have EH~B,IM] maxxetty (H)) 2 (1 -
I is monotone then [H~B.[N] maxseTa (H) (1-A))00))
Proof of Theorem 3.4 According Lemma 3.3 with probability at least 1 8, the function f1, is an E-approximate oracle for M.t for all sets S E In. We denote this event by E. Conditioning on E, the expected value of the solution ALG returned by Algorithm [ satisfies
[[f(A | E] = EH Eyandonnesss of AHH~HHH
E [f U U |
E7 Erandomness of ( (Sn) []]
by the definition of H
a Eh
max (S) 3(s)
by B(bbuutbss of A.
SEI

---

By the smoothing lemma (Lemma 3.5) for any submodular function f. we have
[[f(ALG) E] 2 (1- r- h-t --))((0) f(0)) - -(=).
h t
Since the event & happens with probability least 1 Ö, we have
[[J(AT)) 2 (1 8) (1
r h 1-))((0))) - -(e)) + +6.0
h
1 -
a h t
- -(0)) -(E).
h-t
Letting proves the theorem for the first case. For the monotone case, we can remove the term by Lemma 3.5
remains to prove Lemma 3.5
Proof of Lemina 3.5 We prove this lemma for the non-monotone case here. The proof for the monotone case is simpler and given in Appendix B.2 We will use the following basis exchange property for matroids.
Lemma 3.6 (Donald and Tobey (7). For any two bases B1, B2 of a matroid, for any integer Z 1, there exists bijection from subsets of By with size h to subsets of B3 with size h such that, for every subset C B1 with size h, B- - (l1) H a basis.
Recall that O = arg maxoez f(O) is an optimal solution for f over the original matorid I. Since is non- mon-monotone, O* is not necessarily basis of matroid I. Let B1 2 O" be any basis of matroid I that contains O We apply Lemma 3. bases Bo and B, to obtain a bijection a between subsets of By with size h and subsets of B, with size h, such that B₁ a (H) + H is basis of matroid I, for every subset II S Bo with size h. We note that (B, - - n H have O" (H) C B1 o(H) E In. Thus,
oH) belongs
to In. Because matroid is downward-closed, maxs'eIn F 2 Flt (O* oH)). Taking expectation over H ~ Bo [h]. we get
E Bo[h)
max [S) 2 E BB(Ao (0 - SETH
EnEEH~HH [1(0- - -O(H) - H')
|H'
2 En f(00 - o(H))
|/|| [H'| s'Co' F(S')
max
by Lemma A.3 A.3
Eu [1(0 o (H))
1 h- 100"
Because a a bijection between subsets of Bg and subsets of B₁ and H is uniformly random
subset of Bo with size h, aHH) must be uniformly random subset of B3 with size h. By Lemmal A.2
EH [r( ((0))
f(0")
h
max S'CO'BB,
f(S") f(00)
r- f(0)). (8)
h
Bi h
This implies
h EH max F (S) 2 f(0)) f(00) h-t f(-" f(0)),
SETH
which proves the lemma for the non-monotone case.
Noisy Submodular Maximization Under Specific Settings
In this section, we instantiate our meta-algorithm (Algorithm I with existing algorithms for submod- ular maximization with exact value oracle. By proving that existing algorithms are robust, we obtain results for noisy submodular maximization under various specific settings.
Otherwise, the size Bi (HH) H < - (H) + H = r h + h contradicting the fact that Bi (H) + H basis and should have size
7

---

4.1 Matroid Constraints
Robustness of Measured Continuous Greedy. We first consider maximizing monotone and non- monotone submodular functions under matroid constratins. We prove that the measured continuous greedy algorithm of Feldman et al. [9] robust. Here, we recall the algorithm (with exact value oracle). First, define the multilinear extension of submodular function as
F(x) = Σ
I(S) IES
II
II ( iES
x.),
Vx E 1]"
SCh
Then the algorithm works as follows. First, define z(0) = 0 (the 0 vector) and let å E (0, 1) be such that 1/8 is an integer. Given a point (t( at time t, we first solve
y" (t) arg max mag P
ΣOF(((t)))))
where the argmax max taken over the matroid polytope P. Then we update zi(1 8) x, (1) + 6(1 (t)))) (t). Finally, use pipage rounding [4] (which is obvlious rounding scheme) to convert the fractional solution x(1) to a discrete set I. The pipage rounding technique guarantees that [[f(S)] 2 F(x(1)). In addition, we have that F ((x(L)) monotone and ((x(())/ 2 1/e O when f is non-monotone.
2 1 - 1/e O(n²)) when f is
The following lemma establishes the robustness of the measured continuous greedy algorithm.
Lemma 4.1 (Robustness of measured continuous greedy). For submodular function maximization under matroid constraint, the measured continuous greedy algorithm [0] obtains (1 1/e)- approximation when f is monotone and a (1/e) approximation when f is non-monotone. Moreover, the algorithm is (nn))-robus
The proof can be found in Appendix C In particular, see Lemma C.6 for the monotone case and Lemma C.8 for the non-monotone case. Note that, technically, Lemma 4.1 has a small discretization error but this can be made arbitrarily small so omit it in the statement. In addition, we can absorb the discretization error into the error due to noise in our theorem statements below.
Monotone Submodular Functions with Matroid Constraints. We apply Theorem 3.4 to the problem of maximizing monotone submodular functions with matroid constraints under noisy value oracle. Let the algorithm in Algorithm be the measured continuous greedy algorithm
max mentioned above. Fix parameter E (0, 2n² ). Choose integer m 2 maxf2, 8v²) n" (n+ log (4) =
0 (4m) (log(()). and f² (log?( (2)). Then, we apply Theorem and and
Lemma 4.1 with parameter 1 = E/max to obtain:
n²a
h [[[(AL))] 2 (1- (1- r r-h 1) F(00)) O(ne1)
(1- -1- 1) (1 0(log (T))
+) 5((r)) -0= Sfmax
r -- Olog (1))
(log?(
1 n
-(e)) s(0))
e O(log" (e))
which immediately leads to the following corollary.
Theorem 4.2. Fix e E (0, 20²). Suppose n. 2 1 and the matroid's rank 52 lo)). By letting the A in Algorithum bb the measured continuous greedy algorithm 19). we obtain a polynomial-time algorithm for maximizing monotone submodular functions under matroid constraints with noisy oracle satisfying [ALG) Z -0()))))
Previous work 16 gave a polynomial-time algorithm with (1 (1-1/e)/2-Ofs approximation ratio for noisy monotone submodular maximization under matroid constraints, assuming n 2 - and r 2 E 4/3 Our Theorem 4.2 improves [16] by increasing the approximation ratio to 1 - -1/e- - ((e)
(which is the tight ratio even with the exact value oracle) as well as relaxing the condition
and
8

---

In the special case of cardinality constraints, []6] 's algorithm achieves (1 (1-1/c- approximation with Ö(r²n²/ /E) query complexity (their Theorem 4.6). By letting A be the greedy algorithm with query complexity Q(A) = O(rn), our algorithm achieves the same approximation ratio with query complexity m ((A) = D(nn/e²) (rr)) = /="). While our query complexity might be worse than [16], the advantage of algorithm lies in its generality and better approximation ratio in the more general matroid constraints case.
Non-Monotone Submodular Functions with Matroid Constraint. For non monotone submod- ular functions, choosing the parameters as above, by Theorem 3.4 and Lemma 4.1 we obtain the following:
E [[[GA]] 2 ! (1 r h h-t 10)0-)
- -((E))
(log2(2)
1 -(E)) f(0*).
- O(log" (2))
(log ()
n
Theorem 4.3. Fix E (0, 2-²), Suppose 2 and the matroid's rank 22 (z)) By letting the A in Algorithm be the measured continuous greedy algorithm (9]. we obtain a polynomial time algorithm for maximizing non-monotone submodular functions under matroid constraints with noisy oracle satisfying [AIGG) 2 ( Toloo E - (()))
The R 0.367 approximation above is not necessarily tight. Buchbinder and Feldman 2 design a w.401-aaproxiimatio algorithm for non- non-monotone submodular maximization under matroid constraint with exact value oracle. Their algorithm is quite technical, so we leave as an open question whether their algorithm robust against approximate value oracle. If their algorithm is robust, then can be directly converted to an algorithm for noisy non-monotone submodular maximization under matroid constraint achieving 0.401 o(1) approximation, using our Algorithm
High-Prrbbablitt Result. While main results (Theorems 3.4 and 4. are stated in terms of the expected value [[[GG) we can obtain a high-probability result for maximizing monotone submodular functions under noise. The idea is to repeat Algorithm [ mulltiple times and output the best solution. The challenge here is to compare two sets S1, S2 using noisy values, without access to the true values ((S,), ), (S2). For monotone functions, one can construct another surrogate function fo))), by randomly removing an element from S, do the comparison. Monotonicity combined with submodularity ensures f(S) 2 fo(S) 2 (1 - [S fS)) Such an idea was also utilized by [16]. However, constructing such surrogate functions for non-monotone functions becomes technically challenging. The surrogate function above no longer works since removing an element could actually improve the objective. Indeed, an approximate version of monotonicity is not true in general. We leave for future work to obtain high probbbbiyy results for maximizing non- monooonee functions under noise. See Appendix F for a detailed discussion.
4.2 Unconstrained Submodular Maximization
Finally, we consider maximizing any (non (non-monoter monotone)) submodular function without constraints.
Here, we instantiate Theorem 3.4 with the double greedy algorithm [3] which is known to give a 1 1/2-approximation for unconstrained submodular maximization. At a high-level, the double greedy algorithm works as follows. We first initialize two sets X, = 0 and Y, N. Let N (ei..... en we check the marginal value a, of adding e₁ to X,-1 and the marginal value b, of removing e, from X,-1- With probability a./(a; + bt) (with some clipping operations if necessary), we add e, to X,-1 to get X₁ and set Y, Yr-1- Otherwise, we set = =X-1 and remove e, from Y.-1 to get Y, formal description of the algorithm can be found in Appendix D The key fact that require is the following lemma, with proof given in Appendix D
Fort=1,... 1,.... .,....
Lemma 4.4 (Robustness of double greedy). The double greedy algorithm obtains 1/2 //2aapproiimation for maximizing a submodular function without constraints. Moreover, the algorithm is
Directly applying Lemma 4.4 and the non-monotone case in Theorem 3.4 gives us an algorithm for maximizing unconstrained non-monotone functions with noisy oracle with e(log Рン O())

---

approximation ratio. Yet, the unconstrained case allows for a more refined analysis which gives better approximation ratio that removes the Blog F) term (see Appendix for the proof);
Theorem 4.5. Fix e E (0, 2x² Suppose n. 2 2( (.)). By letting the A in Algorithm 7 be the double greedy algorithm (3.. we obtain a polynomial- time algorithm for maximizing unconstrained non-monotone submodular functions with noisy oracle satisfying Elf 2 ( f(E))
5 Simulation Results
In this section, present simulation results to compare the performances of our proposed algorithm (Algorithm D and some heuristic algorithms for the noisy submodular maximization problem.
We focus on the simple yet underexplored case of unconstrained non-monotone noisy submodular maximization. We consider an example where the submodular function is a weighted additive function with quadratic cost in the subset size: AS S N, f(S) = =Eies w;, c|S|? where each element i has weight Wi ~ Uniform[O. 20), with cost parameter = 10/n, so the ground set N has expected value When sampling wA we ensure that f is non-negative. The noisy value function is J(S) (S) where {s ~ Normal(j = a,a2 = 0.1). We compare four algorithms against the optimal value benchmark f(O*) maxsÇN [S)):
Double greedy (DG) with exact value oracle 33: this is worst-case optimal polynomial-time
algorithm in the noiseless setting. It uses the exact value oracle and is used only for reference.
Double greedy (DG) with noisy value oracle: the DG algorithm that uses the noisy value oracle directly. It a natural algorithm to compare to, given the optimality of noiseless DG.
Random subset: pick subset of size n//2 uniformly at random.
Our algorithm in Theorem 4.5 our surrogate-value-bee based meta algorithm (Algorithm I instantiated with DG. After simple tuming, set the parameters to h 20, t 4, and vary
We run 1000 simulations. In each simulation, we first sample f (namely, the weights wx)) and the noisy function (the multipliers Es), then run each of the above four algorithms once. Table shows [(LG)] and standard deviations of the true values of the obtained sets, as a fraction of the optimal value. We observed that the heuristic algorithm, DG with Noisy Oracle, does not perform well; is only slightly better than Random Subset. Our algorithm significantly outperforms the heuristic algorithms,, with = 15% improvement with m 50 and z 25% with m = 200.
the means E f(o.!
Table Comparison between ours and other algorithms, in the unconstrained non-monotone noisy submodular maximization setting.
Ground
DG with
DG with
Random
Our Algorithm
Our Algorithm (m = 200)
Set Size
Exact Oracle
Noisy Oracle
Subset
(m = 50)
n 50
0.944 (# 0.028)
0.601 (#: 0.074)
0.550 (# 0.079)
0.674 (#: 0.067)
0.735 (#: 0.059)
n 100
0.944 (# 0.019)
0.565 (# 0.055)
0.536 (# 0.057)
0.657 (# 0.047)
0.731 (#: 0.041)
6 Conclusion and Future Work
In this paper, we developed framework for noisy submodular maximization which allows us to reuse existing robust algorithms for submodular maximization while obtaining essentially the same approximation guarantee. As applications, we considered submodular maximization subject to a matroid constraint (both monotone and non-monotone) and unconstrained monoonee submodular maximization. We conclude this paper with a few open questions. The first is to obtain high- probability bounds for non-monotone submodular maximization. The second is to explore whether there is some meta-algorithm that can take any existing algorithm and utilize it for the noisy setting. Finally, an interesting open direction is to explore noisy submodular mininization.
References
[1] Rémi Bardenet and Odalric-Ane Aambric-Ambrym Maillard. Concentration inequalities for sampling without replacement. Bernoulli, 21(3), August 2015.
10

---

[2] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1820-1831, 2024.
[3] Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM Journal on Computing, 44 (5):1344-1402, 2015. 1137/130929255
doi: 10.1137/130929205. URL http:///pppll siam. org/ org/doi/10
[4] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing Monotone Submodular Function Subject to a Matroid Constraint, SIAM Journal on Computing. 40(6);
1740-1766, January 2011. ISSN 0097-5397, 1095-7111, doi: 10. 10.1137/080733991. URL
http://epubs.. siam. am. org/ /to//o/o11001// 1137 1137/080733991
[5] Wenjing Chen, Shuo Xing, and Victoria G Crawford. A threshold greedy algorithm for noisy submodular maximization. arXiv preprint arXiv:2312.0015. 2023.
[6] Flavio Chierichetti, Anirban Dasgupta, and Ravi Kumar. On additive approximate submodularity. Theoretical Computer Science, 922:346-366 360. 2022.
[7] John Donald and Malcolm Tobey. A generalised exchange theorem for matroid bases. Bulletin of the Australian Mathematiical Sociery, 43 April 1991. ISSN 0004-9727, 1755-1633. doi: 10. 10.1017/500049977000092333 URL URL
http::ttt://tttt http://wwwwwwwbbbeccc cambridge.org/comeee www./oorrppouuccc
[8] Moran Feldman. Maximization Problems with Submodular Objective Functions. PhD thesis, Technion Israel Institute of Technology, June 2013.
[9] Moran Feldman, Joseph Naor, and Roy Schwartz. A Unified Continuous Greedy Algorithm for Submodular Maximization. In 201 I IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 570-579, Palm Springs, CA, October 2011. IEEE, ISBN 978-1-4577-184344 978 978-0-7695-457144 14. doi: 10.1 10.1109/OOCS2000 201 1.46. URL https://1eeexpploree .eeeeeerrreeeeeeeeeeeee.oeeeeeee org/ document/61082118/
[10] Yuval Filmus and Justin Ward. Monotone submodular maximization over matroid via non- oblivious local search. SIAM Journal on Computing, 43(2):514-544) 2014.
[11] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds. In Advances in Neural Information Processing Systems, volume 33, pages 123-133. Curran Associates, Inc., 2020.
[12] Nicholas Harvey, Christopher Liaw, and Tasuku Soma. Improved algorithms for online submod- ular maximization via first-order regret bounds. Advances in Neural Information Processing Systems, 133-333, 2020.
[13] Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. In Conference on Learning Theory, pages 1229 PMLR, 2017.
[14] Avinatan Hassidim and Yaron Singer. Optimization for approximate submodularity. Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, pages 394 405, 2018
[15] Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. Ad- vances in neural information processing systems, 29, 2016
[16] Lingxiao Huang, Yuyi Wang, Chunxue Yang, and Huanjian Zhou. Efficient Sub- modular Optimization under Noise: Local Search is Robust. In Advances in Neu- ral Information Processing Systems, volume 35, pages 26122-26134 Curran Associates, neurips cc/ppper.ppppp.ececcceeceeee...p of files/ pttlee///paprrr22///11121
2022. Utt.httss://proceeeeet 474454aadd$65555c3447777777771 Paapr//eeeeeaaaaeeooooeeeeeeeeee
[17] Rad Niazadeh, Negin Golrezaei, Joshua R Wang, Fransisca Susan, and Ashwinkumar Badani- diyuru. Online learning via offline greedy algorithms: Applications in market design and optimization. Proceedings of the 22nd ACM Conference on Economics and Computation, pages 737-738, 2021.
11

---

[18] Tim Roughgarden and Joshua R Wang. An optimal algorithm for online unconstrained submod- ular maximization. arXiv preprint arXi::1806.033499 2018.
[19] Tim Roughgarden and Joshua R. Wang. An optimal learning algorithm for online uncon- strained submodular maximization. In Proceedings of the 31st Conference On Learning Theory, pages 1307-1325, PMLR, 2018. URL hattps://proceeddngg mlr pat..pressss.. roughgardenn8a. html
[20] Adish Singla, Sebastian Tsschiatshhek, and Andreas Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 1A page
2037-2043, 2016.
[21] Tasuku Soma. No-regret algorithms for online k-submodular maximization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1205-1214, PMLR, 2019.
[22] Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems, 21, 2008.
[23] Jan Vondrak. note on concentration of submodular functions, 2010. URL aatpi org/abs/1005 2791
[24] Martin J. Wainwright. High-Dimensionall Statistics: A Non-Asymptoticc Viewpoint. Cambridge University Press, edition, February 2019. ISBN 978-1-108-62777-1 978-1-108-49802- doi: 10.101797881000277777
URL https://www wwwprreee....ggg/ore///eeee///ee
identifier httfffiee997111000 i /1112////9777100027777//////////
[25] Leqian Zheng, Hau Chan, Grigorios Loukides, and Minming Li. Maximizing approximately
k-submodular functions. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 414 422. SIAM, 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This a theoretical paper. The abstract and introduction describe our main results and our techniques.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed, for example, that our work does not always get the tight result (e.g, non-monotone submodular maximization subject matroid constraint; see
Section 4) and that we were not able to get high probability bounds for all our results (also see Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We aimed to be precise in our theorem statements and to be precise in our model. All our proofs either appear the main body or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is uploaded.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips. htcp//blcc//uddeeeeeeeeeeeeeeeee
ssiobbiiiisiooccccyy. for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Our experiments do not involve typical machine learning training.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We presented sample standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [NA]
Justification: violation.
We have reviewed the code ethics and don't think there should be any
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Purely theoretical paper unlikely to have any direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Purely theoretical paper so unlikely to pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Purely theoretical paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Purely theoretical paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No use of human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No of human objects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No direct link with LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM for what should or should not be described.
19

---

A Useful Facts
Lemma A.I. Let be non-negative submodular function, Let S, E N be two sets. Let be random element from A. Then (g)A((()) - - -x]]= [A J(5).
Proof.
Denote S n A {a1,...... 2 BISnA| We have
E [[()) f($ {x})
Pr(r S A]
Sna (((S) /(S) {x})
InAI
|
Σ
f(5)-f(8) F(S (x:1)]
|A]
SNA
ISNAI
ISNA
Σ
f(S) \ (x1..... - f(S)) (xI........1.. m1)]
A
ISNA
1
[ (J(S) S(S) A))
1
A f(S),
as desired.
Lemma A.2. For any two sets S, A S for integer 1, sampling subset of size from A uniformly at random, we have:
k
max [B B}] 2 f(S) [A| - S'CSNA, 18 [8 f(S").
Proof. The proof is by induction. Let B, be i 1 random elements from A without duplicates. Let b, E A \ B and B; = Bi-1 U {b By the induction hypothesis, we have
i-1
EB. [FSS) B--1)] Z S(S)
A - S'ESNA, ( f(5).
We now condition on B;- By Lemma A.1 we have
Es, (SS B,)] S(S) B;-1) |A| i 1(8) B1-1)-
Adding the last two inequalities gives E{f(S) B,)] 2 f(S) - [Ai max 2[S The lemma follows by induction.
Lemma A.3. For any two sets S, A C N. for integer z 1, sampling a subset of size k from A uniformly at random, have:
k max
EB-AH [[SUB] 2 f(S)
|A] - k sEsS''S f(S').
Proof. Follows from Lemma A.2 by applying to the submodular function g(S) = f(N \ ()).
B Missing Proofs from Section 3
B.1 Proof of Lemmal
Lemma B.1 (Hoeffding's inequality for sub-exponential distributions: see, e.g., page 29 in 24 Let
X1,.. Xm be independent random variables where each X, is O-mean and (V,, at (2) --b-----u---xentiiie
Let a2 = max 0i and V. = -V VE v?? Then,
12epp
me? 202
for 0 < < for n²
Pr
Σ
X, 26 <
exp
2a.
ma.
20

---

Proof of Lemma 3.3 Fix a set S S N (:) EHrERH f(SUH'). H'). By definition, Hi...., Hm are sampled from H[] without replace-
H. Let = FS) = Bm U H') =
ment. Since each f(S U H") is bounded in [0. fmax.. by Hoeffding's 's inequality for sampling without replacement (see, e.g., Proposition 1.2 in [L), we have
Pr m Σ (SSH)) - 1
el 2
2exp
(-
mE²
S 8'
2 max
2faax log 87
given
Assume that
m Zi=1
S(S H.) 14| 5 & holds. We then consider the difference
1
f(SUH)) 1 Σ f(SUH) Σ -Ex X₁
111
H'CH
where
x; f H.) f(S H.) (EsJH. () U H,)
is a random variable with mean [[X;] (by the unbiased property of noise) and is sub-exponential with parameters
(Ufmaxx
Because the sets H1 HI...., Hm are sampled without replacement, we have H, + Hj for i + j. so U H; F U Hy. This means that the noise multipliers ESUH, and {SUH, independent, so X; and X, are independent. Then, we apply Lemma B.1 E X, with a, afmax and
v. V / max to obtain
Pr
m
I 2 exp (-
mE²
2 eexp
(-
mE?
S 8'
(10)
8v² Sy2/m
8y/2 f2
m
maxx
Su2 - Ijuna log z/4 and
22
2² funs
given 2
fmax.
ma.
a
Taking a union bound over 9 and 10) and a union bound over all sets S C N H. we have with
probability at least - 2 2 for all sets S S N H, we have both E f(S U H,) .ul S 2
and Ea Xil hold, which implies
( - F = Σ 1=1
((U - Al S s.
Let = 2'. The m has to satisfies
{
max
8v2 F2
m 2 max
log
log
g2
5
8' $
4.2" 2"
max 8y
max
log
52
8
fax
log log 4 8
12 Su²)
8²
which is satisfied when m 2 max 802) Layx (n + log 4)
In order to sample m sets H1 Hm from H[{ without replacement, the h and have to satisfy
N m.
By the inequality ())
n' for t Vh and letting h t?
we have
ht
t
2
m
41
when f 2 (4m).
21

---

B.2 Proof of Lemma 3.5 for Monotone Submodular Function
We follow the proof for the con-oootone case until
where we have
En
max (S))
En [10 o(H) -
SEIH
Because f is monotone, we immediately have f(0" o(H) + H') 2 f(0 o(H) and hence
(S)
2 Eh f(00 o(H))
max
SETH
8 N f(0") h
by
r- f(0").
C Robustness of Measured Continuous Greedy: Proof of Lemma 4.1
Algorithm 2: Mcasured continuous greedy with approximate value oracle
Input Approximate value oracle f to a submodular function ground set N. Matroid I.
Let n [V] 8 n
Initialize = 0, x0) E [0, 1J".
3 while < do
Let RR()) be the random set that contains each element i N independently with probability x1()).
For each i E N, let (t) be estimate of the expected marginal value E[Sn(o)) (i)), obtained by taking the average of 10 log(2n) samples of (i))
Let [tt) arg m Eier W; (t) be maximum- independent set.
Let (t + 5) be the following: for every E N, (t + 5) < rt(() + 5(1 - z, (t))
7
t t +
end
Use pipage rounding 4 (which does not require access to f) convert the fractional solution sx(1) to discrete set S E I.
return 5
In this section, we establish the robustness the measured continuous greedy algorithm (the full algorithm is given in Algorithm 2. Let f be an e-approximate value oracle for f. The proof for the approximation ratios of the measured continuous greedy algorithm with exact value oracle provided
by Feldman g We analyze how the e-approximate value oracle f will affect the approximation ratios. The main step is Lemma C.4 which provides a replacement of Corollary 3.2.7 of [8]. Once this is established, we can apply the remaining arguments Section 3.2.1 and Section 3.2.2 by replacing the discretization error of O(n²8*) (8) with the discretization and approximation error established in Lemma
Here, we use to denote the multilinear extension of the submodular f. In other words,
F(x)
= Σ ((S)
[ iES
II 2
[I
Vo |0,
SCIml
igs
We use f to denote the multilinear extension with f replaced with f.
f(x)
Σ f(s)
II Ø
Va 00, 1 [1-1x;),
SCIn
iES
igs
We require two well-known properties of the multilinear extension.
Claim C.1. The partial derivatives of the multilinear extension satisfy:
0,F(x) F(x F(x 1z).
. 0,0,F(2) F(x FEA
22

---

At high level, the measured continuous greedy algorithm works follows. Let E (0, 1) be defined such that 1/6 an integer. Let P be the matroid polytope. Given a point (t time use samples to estimate 0 (x))) and then solve
y" (t) arg max P
Σ a (x(()))
Then we update x; + 6) (t) 8(1 (x)) (t).
Note that (11) is feasible since the update at time is bounded by 6y (t) which is feasible and thus 5(y" (0) y" (1/6) +... 12 11-(111111 1/5)) is also feasible. Since the matroid polytope is downward- closed, we conclude that (1) is feasible.
We use 1, to denote the vector whose ith coordinate is 1 and 0 otherwise and 1; 1 1, Let OPT arg max ((S) an optimal solution. We let H(PPT)*
Lemma C.2. Suppose [f()) f(S)) S E af(OPT). Then, for every i, we have (0,F(x)) 0,F((x)) z (oP(O = 2e.
Proof. Directly follows from Claim C.I
Lemma C.3. 0xF(x)
F(av1.)-F(a)
1-m;
Proof. This is a simple calculation. Indeed,
0.F(z) F(xV F(aAA) PLA V( FFF(x V 1,) - -11- F(x 1;)
1
F(x V 1,) F()x)
24
as desired.
We now establish the main lemma of this section.
Lemma C.4. Suppose that If(S) - f(S) < a f(OPT) for all S. Then ((x(++8)) - F((((t) 2 ò (F(a(t) v LOPT) F((((t))) (45an ((OP).
Proof. Let xl1 + 6) arl) and consider the univariate function g(s) = F(x(() sz). By Taylor expansion, we have
F(x(1+ + 5)) F(x(1) = ((1) .(0) 2 g0( max [g"(s))-
sE(0.1]
Taking derivatives, we have
g(()) = Σ +
and
(s) F.0,F(z(t) 82)222.
We have the bound |0,0,F| 2n f(OPT) (second item of Claim 2n388 (OPT))
C.I and |2||
5 so (g)
23

---

Now, we bound g0).. We have
00(0) Σ 0 (.F((()))
= Σ O.F(((t))( - (t)))
Σ (.(()( (1- (1) 2dan S(OPT)
by Lemma C.2
Σ a.((((()) 2;(1)) 20an S(OPT)
iЕOPT
28 Σ 0.F(((()) (1 x()()) 4ôon f(OPT)
by Lemma C.2
ंЕОPT
=d Σ (F(r(1)VL) F(x(())) 40am ((OP)(
iЕOPT
By submodularity, have E (F(a(1) V1), F(x(())) ((x(() TOrT) F(x(()). To the last inequality, let = So C S1 C... C SiorT] OPT be such that [S, S = 1. Then
[PPT|
F(x(1) V IOPT) F(x(())
Σ (((0))) .)
[OPT|
M
F(x(() V 1t2) F(x(() v Vls, .)-
We can then iteratively apply Lemma C.5 to each summand.
Lemma C.5. For any + j. we have F(r V(IVL.VI - F(z & Fxx).
Proof. The inequality we want to prove can be written as
Es-e If(S +i+ f(S + +)] s Es -fs))
which is true since f is submodular.
C.1 The Monotone Case
Lemma C.6. F(x(1)) 2 1/an n) f(OPT).
Proof. From Lemma C.4 we have
F(x(t 6)) (1 ())(((())))+)))))))))))))))))))) (8- 48an n n(88))(OPT).
Let C (1 4an - n2 (OPT) that the above equation becomes
Flz(t + d)) 2 (1 - 6)F(((t)) &C.
Unrolling the recursion, we have
1/6-1
-c 61- 20 - -11-1/e--6 1/2-8/26)
F(x(1)) Σ
1=0
where used Claim C.7 for the last inequality. Plugging in C gives the claim.
Claim C.7. If 0.5 then - 11=x) < 1/e + x/2e.
Proof. First, by a Taylor expansion, we have log(1 - x) < - 2 which is valid for all x E (0, 1). We thus have log(1-2) < - + so (1 // < e tE2/2 Next, we use the numerie inequality x e/2 < + which is valid for < 2. So conclude that log(1-2) <e- + x/2).

---

From Lemma C.6
we obtain
F(x(1)) 2 [1 1/e O(am + n r) S(OPT)
[1 1/e O(n¹)) ((PP) (
[1 1/e 0 f(OPT) O(En),
with 8 = n- in Algorithm 2 which proves Lemma 4.1 for the monotone case.
C.2
The Non-Monotone Case
The following lemma be established from following the proofs of Lemma 3.2.8, Lemma 3.2.9, Corollary 3.2.10, and Lemma 3.2.11 from g verbatim but replacing ((n*)) in their argument with O n²8) (i.e. Lemma C.4
Lemma C.8. F(x(1)) 2 [1/e O + no))] f(OPT)
This implies F(x(1)) [1/e ( f(OPT) (Een) and proves Lemma 4.1 for the non- monotone case.
D Robustness of Double Greedy: Proof of Lemma 4.4
Algorithm 3: Double greedy with approximate value oracle
Input: An approximate value oracle f for a non-negative submodular function f 2 R4. Initialize Xo = 0, Yo N.
Let (ui,.... un,) be an arbitrary order of the elements in N.
3 for i to n do
Let à; be the approximate value of a; fx._, (u:) = f(X (ui)) f(X,-1). Let b, be the approxiamte value of 6; = - fr. Mu. (4:) = (Y ((u)))
ā; > 0 and b,
a, 5.+b.
Let (p., (.) =
(1,0)
ā; > 0 and b, S
(0,1)
à; < 0.
With probability p., let X1 X4-1 [u:}, Y, = Y
otherwise, let X; Xi-1, Y; = Y-1 {u:].
end
10 return Xn (which equals Yn).
This section proves the robustness of the double greedy algorithm approximate value oracle.
3 (given in Algorithm against
Lemma D.I. Suppose Jā, a,l S s and l6, b, E. Let OPT = arg maxsCN f(S). The expected
value of the solution X,, returned by Algorithm iis at least
E[f(X,)) 2 2 2 nE.
((OPT)
(11)
Proof. Define the following quantity:
= max(p.b,, 9.a,} (p.a. + q.b:).
(12)
When the value oracle is exact, the probabilities pi, qi are computed from the correct marginal values a, and by:
(a,46,
if à, > 0 and by > 0 if a; > and S
(p),
(1.0)
(13)
(0,
a, $
In this case, it can be easily verified that T3 = max(p;b; q:a:) (p.a - q.b.) < 0. Due to approximate oracle, = max (pebi, (sa,) 2 (p.a; + q.b;) may be positive. [19] show that the loss of performance of the double greedy algorithm due approximate oracle can be upper bounded by
Ei Tú
25

---

Lemma D.2 (see Theorem 2.1 in [19] or Lemma 4.3 in [I]).
The expected value of the set Xn
returned by Algorithmm is is least:
Bif(X.) 2 2 ((OPT) EE r2]
(14)
Then, remains upper bound E re]. which we do in the following lemma:
Lemma D.3. Suppose (å; - agl S and 16, bul S E, then S 2cc
Proof. simplify notations, we drop the subscript i, so r max {اا,, qa} 2 + qb). Consider three cases separately:
â >> and 0. In this case, we have p 3.
a+b 9
b
and
a+b
r à à+b max (bb, ba} { -86)
Using the inequalities
S à E b S b Eb, and à > 0, >>0 0.
1
r r
max{a(b+ Eb), Eb), +a)) {ā((ā Ea) b(b Eb))
à + 6
(ab+ max(aes, bEa) (a² - -b² - âEa - -bsb)
+ b
1
mmax(des dea7 + (āEa + bEo) 2 (a² B² 2ab)
à 6
< maxx(aes, B + (āEa + bea)
1
+ i
max (pEa. g + (pEa + GEL)
à 0 and b 0. In this case, we have f q and
max 0} t
On the one hand, 5 Ea. On the other hand, because b 2 holds for any submodular function 3. we have a 2 -b 2 -Eb. Therefore,
max 56 0} (- e
à < 0. In this case, we have P = 0, q = 1, and
max a} 6
On the one hand, a á Ea I fa. On the other hand, because a + 2 holds for any submodular function 31, we have b > -e.. Therefore,
r S max (0, Ea) {--E)) = 3ea-
All the three cases above give r < max(ea, 3.).
Using Lemmas
D.2 and D.3 we immediately obtain [Xf( > f(((PT) 3
26

---

E
Proof of Theorem 4.5
Lemma E.1. Fix any set 8 C.N. Sample a uniformly random set H S N of size h. We have:
h max S(S').
B (S) H) 2 (n
IN h S'
Proof. Let H' ~ H[] denote the random sampling of subset H' of H with size t. By definition, (S) E, Mf H'). So,
En [ H1 (S) pH (S) H)) = EnEEy-HI - S((S))))))))))))))) H) H)UH)
En ((SUH) - (ASSS((SH))))))) (1 H²))
= En [f(SUH) -o0---f(SUURA f((SU()) (H H))]
where the notation H'' means sampling H conditioning on H'. We note that, conditioning on H', the distribution the set \ H' is uniform across all subsets of H' of size h L. So, letting B = H H', we have
E# [F (S) - F (S H))
BE
H (((SUH)) - B)
B
EH
N
H'
B
S'CSUH'
max
[(S)]
by Lemma A.2
$
max
f(S").
|N| - h 1'
Lemma E.2. For any set S S N. Sample a uniformly random set H S N size have
max EH-NM (S)] 2 f(S) IN - s* 18 f(S').
Proof. Let H' ~ H[] denote a random subset of H with size L. Then, we have
BH = EM (SU H")
EM ((SUH))
max 2 f(S) |N| - st (
f(S")
by Lemma A.3
max 2 S(S) NN| - suSssIN, 1| S(S).
Proof of Theorem 4.5
The double greedy algorithm has approximation ratio a = 1/2 and is B(s1)
O(ne1)-robus) -robust against Ei Ei-approximate value oracle by Lemma 4.4 Then, following the proof of
Theorem 3.4 we have with probability at least 8 over the randomness of f, the expected value of the final solution ALG satisfies
B[f(ALG) E] 2 En-NM
max F (S*(S)) - O(nE1)
2
SCNVH
2 [FHNNI[[HH.CCC \ H)] O(ne))
(because O' A H)
2
2 (BI-N((F"::(0))
1
n - f(00)) )
h
O(nEs)
by Lemma
2 (1(0T) - 2 n - s(0r)) ) O(NE))
by Lemma
27

---

Letting d and = f,())), and taking into account the remaining g probability, we have B[S(ALG)) 2 (1 (ALG) 8] + 6.0
h
2 2 n - h
S(O
1 - S10))
with h = ((og and 2 2 (?)).
F
Discussion on High Probability Results
Our main results for noisy submodular maximization (Theorems 3.4
stated in terms 4.3 4.5
of the expected value [[f(AG)) 2 (a - (O))) We discuss high seeh-robability results this section.
standard way to obtain high-pne potthabobbbbtyy results from expectation results is to repeat the randomized algorithm multiple times and output the best solution. In our case, this means repeating Algorithm I for T times and picking the best set among the T outputted sets Si,.... ST. The challenge here is
how to compare two sets, in order to pick the best one, using noisy values instead of the true values.
For monotone submodular functions, Huang al. 16 provide method to do noisy comparison. For any set S _ N, define the following comparison surrogate function fo(S) and the noisy version fo(S):
1 Σ I(S- e), fo(S) 1 Σ f(S -c) 15|
fo(5)
(15)
5
To compare two sets S₁ and Sz,, we compare fo(),) and fo(S2).
Lemma F. (116). Let E, (0, 1/2). Suppose |S| x log(E) where is the sub-exponential norm of the noise multiplier. Then,
Pr [[o(5) - fo()) Efo(s) 8
-
(16)
Now, suppose we repeat Algorithm for T times and obtain solutions Si,..., Sr. Let X; = f(8.)
1(0)) E
[0, 1]. By Theorem 4.2 the expected value of each solution satisfies [S.) 2 (1 1/e--) (0)
namely [[X,] 2 1/e E. According to Markov's inequality, Pr[X, < 1 - 1/e - 22l =
Pr[1 X > 1/e + 2e]
<
-1-x, I/e+2s
1/o+s I/e+2c
~ 1 hence
Pr
max X; < 1/e- 28 s (1 eE)T 2 [E[T]
given T log(1/8) Namely, with probability at least 6, we have
et
max f(S)) 2 (1- (1-1/e- 20))
(17)
<E(T]
Let S be the best solution according noisy comparison, namely i arg max fo(S.). Let i" arg max, fS.). The true value of Sy satisfies
f(S;) 2 (o;)
by monotonicity
2 1
+ (o()))
by Lemma
1
2 + (u(Sr))
by the definition of i
1 -
Z 1 + E
(S(S)-)
by Lemma
z 1-
1
((S=-)
by Lemma
1 I+E
1-E
1
-1---26) -2))5((0))
|
by 17
Ite
[
28

---

For maximizing monotone submodular function. the size of each solution satisfies |S the failure probability of 'T' noisy comparisons to be less than ó, according to Lemma we need
So, for
|S:| Ω log ( a
log 2 2
We thus obtain the following high-probability result for noisy submodular maximization for monotone functions under matroid constraints:
Corollary F22 Fix E E (0, 2n ). Suppose the matroid's rank r 2 2 (z) & log (2 )
dc
By repeating the algorithm in Theorem 4.2 for T log(1/81 times and outputting Sj. we obtain an algorithm for maximizing monotone submodular functions under matroid constraints with noisy value oracle that, with probability least
es
6, returns a solution satisfying
f(S)) 2 - f(0*)
For non-monotone submodular functions, the above approach to obtaining high-probability result does not work because: (I) the f(S,) > (u,S,) step in the noisy comparison analysis longer holds, and (2) the size the solution |S,] can less than the rank of the matroid, so the (1 [s:] factor in the approximation ratio can be small. Another attempt on obtaining high-probabillty results for non- mon-monoe functions could be use some concentration analyses for submodular functions, such as [23]. However, the concentration analyses in prior works usually require the Lipschitz constant (the largest absolute marginal value) of the submodular function f to be small compared to f(O"). It remains open how to obtain brghhbrobbbility results for maximizing general non-monee monoooootte submodular functions under noise.
29


Reviews:
[{"review_id": "n11gxO2Tei", "reviewer": "Reviewer_WQvx", "summary": "This paper studies submodular function maximization under a persistent noisy value oracle model, where repeated queries to the same set yield a fixed noisy value. Building upon prior work [11, 14], the authors propose a meta-algorithm that systematically converts any robust noiseless submodular maximization algorithm into one that works under persistent noise, while preserving approximation guarantees. By instantiating this framework with measured continuous greedy and double greedy algorithms, the paper recovers or improves state-of-the-art approximation ratios across cardinality, matroid, and unconstrained settings for both monotone and non-monotone functions.", "questions": "See the questions in weakness section.", "limitations": "Yes.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. Introduce a meta-algorithm that robustly extends noiseless submodular maximization algorithms to the persistent noise setting, achieving near-optimal guarantees: a tight (1 -\\frac{1}{e})-approximation for monotone submodular maximization under matroid constraints, a 1/2-approximation for unconstrained non-monotone maximization (tight even under noise), and a 1/e-approximation for non-monotone maximization under matroid constraints. This includes the first theoretical guarantees for noisy non-monotone submodular maximization.\n2. Employ a novel randomized surrogate function technique that overcomes the limitations of prior deterministic smoothing approaches, allowing a unified treatment of various constraints while inheriting strong guarantees from continuous greedy and double greedy algorithms.\n3. Significantly broaden the applicability of noise-aware submodular maximization by generalizing previous algorithms that were limited to monotone functions and specific constraints, providing tight approximation guarantees under realistic persistent noise models.\n\nWeakness:\n1. Although the paper is relatively complete in theoretical analysis, the core method is mainly based on the robustness analysis of existing continuous greedy and double greedy algorithms, lacking essential breakthroughs in existing work. In particular, the surrogate function design and sampling mechanism proposed in the framework have obvious inheritance relationships with previous works such as [11][14]. It is recommended that the author clearly explain the substantial innovation compared with these works.\n2. The results shown in Table 1 of the paper have improved previous work in some scenarios. In the non-monotonic case, although it fills the theoretical gap of unconstrained and pseudo-matrix constraints, it is difficult to judge its practical value without comparing it with the empirical performance of heuristic methods.\n3. Theorem 4.2 requires that the rank constraint satisfies $r \\geq \\Omega(\\varepsilon^{-1} \\log^2 n)$. Taking the typical parameters n=10^4 and ε=0.1 as an example, this means that $ r\\geq 500$ is required to ensure that the theoretical result holds. However, many practical applications usually involve low-rank constraints (such as r=10). Does the theoretical guarantee of the framework completely fail? \n4. Although it is a theoretical paper, since it claims to propose a \"widely reusable unified algorithm framework\", its actual effects should be demonstrated through small-scale experiments or simulations to demonstrate its \"practical applicability\".", "was_revised": true, "final_justification": "I am giving the paper a positive score; however, my assessment is largely an educated guess.", "rebuttal": "Thanks for your review.  We would like to address the weaknesses you pointed out.\n\n__(Weakness 1)__ \nAs you mentioned, one of the core methods is based on the robustness analysis of existing algorithms.  However, we think this is actually one of the main advantages of our work.  Previous work [11, 14] defined surrogate functions and implicitly used robustness arguments.  However, their analysis mixes these two components and is very specific to their setting.  It is unclear whether or not these two components can be separated to obtain a more general reduction.  In contrast, we construct a new surrogate function that enables these two parts to be analyzed separately, establishing a clean reduction from the noisy submodular maximization problem to the robustness analysis of existing algorithms.  Such a new surrogate function requires randomization that is not present in previous work. \n\n__(Weakness 2)__\nAs with prior work on this topic (specifically [11, 14]), and many prior works on submodular optimization published in NeurIPS, our goal is to advance the theoretical understanding of submodular optimization with noise. With that said, we also agree with the reviewer that the empirical comparison with heuristic methods may be helpful to demonstrate the practical value of our algorithm.  So, we have implemented our algorithm and compared it with heuristic methods; please see the end of our rebuttal for details.  \n\n__(Weakness 3)__\nYes, the rank constraint is a current limitation of our work.  When the rank $r$ is very small, it is unclear whether the surrogate function approach (using auxiliary subsets to denoise the function) still works.  Nonetheless, we note that our work already improves upon the dependency of the rank in prior work such as [14].  In [14], they have two regimes.  The regime which is the most comparable is when $n \\geq 1/\\epsilon^4$ (Theorem 5.2 of [14]).  For reference, note that we require $n \\geq 1/\\epsilon$ so our requirement on $n$ is better (their other regime actually requires $n$ to be exponential in $poly(1/\\epsilon)$). In this case, their Theorem 5.2 requires $r \\geq n^{1/3} \\geq 1 / \\epsilon^{4/3}$.  So our dependency on the rank $r$ is exponentially better than [14]. \n\nFor completeness, we will note that in [14], if they assume $n$ is exponential in $poly(1/\\epsilon)$ (although it is unclear what the degree of the polynomial is), then $r \\geq 1/\\epsilon$ is sufficient. In this regime, their dependency on the rank is better but we reiterate that this requires that $n$ is very large.\n\n__(Weakness 4)__\nAs discussed earlier, our main focus is on a better theoretical understanding of submodular optimization with noise. To complement the theoretical perspective, we provide experiments to demonstrate the “practical applicability” of our algorithms.  Please see the details below.\n\n\n__Added experiments:__\nTo address Reviewer WQvx’s concerns in Weaknesses 2 and 4, we provide some experimental results.  We focus on the simple yet underexplored case of unconstrained non-monotone submodular maximization.  We consider an example where the submodular function has additive weights and quadratic cost in size: $f(S) = \\sum_{i\\in S} w_i - c |S|^2$, with $w_i \\sim \\mathrm{Uniform}[0, 20]$ and $c = 0.1$, with groundset size $n=100$. To match the setting in our paper, we ensured $w_i$ were chosen so that $f$ was non-negative (although this does not impact the results). The noisy value is $\\tilde f(S) = \\xi_S f(S)$ where $\\xi_S \\sim \\mathrm{Normal}(\\mu=1, \\sigma^2=0.1)$.  We compare four algorithms against the optimal value benchmark:\n\n(1) Double greedy (DG) algorithm with exact value oracle (Buchbinder et al, 2015).  This is a worst-case optimal polynomial-time algorithm in the noiseless setting. \n\n(2) Random subset: pick a random subset of size $n/2$.  This trivial algorithm is only for reference. \n\n(3) Double greedy (DG) algorithm that uses the noisy value oracle directly. This is a natural heuristic algorithm.  Reviewer WQvx suggested we compare against heuristic algorithms. \n\n(4) Our algorithm in Theorem 4.5, which is the surrogate-function-based meta-algorithm instantiated with double greedy.   After simple tuning, we set the parameters to h = 20, t = 4, and vary m.\n\nResults are shown in the following table. We fix a function $f$, run the randomized algorithms for 100 simulations, and show the mean values (E[ALG] / OPT) and standard deviations.\n\n|    Optimal value    |  DG with exact oracle  |    Random subset    |  DG with noisy oracle  |  Our algorithm (m=50)  |  Our algorithm (m=200) |\n| :-----------------: | :--------------------: | :-----------------: | :--------------------: | :--------------------: | :--------------------: |\n|   normalized to 1   |    0.940 (+/- 0.017)   |  0.527 (+/- 0.054)  |    0.557 (+/- 0.048)   |    0.659 (+/- 0.047)   |    0.742 (+/- 0.045)   |\n\nWe see that the heuristic algorithm (DG with noisy oracle) does not perform well in this example; its performance is similar to a random subset. Our algorithm significantly outperforms the heuristic algorithm, with 18% improvement with m = 50 and 33% with m = 200."}, {"review_id": "VYNpWXzUT2", "reviewer": "Reviewer_ZGB3", "summary": "Submodular maximization under noise is the problem of maximizing submodular function $f \\colon 2^N \\to \\mathbb{R}_{\\ge 0}$ with access to only a noisy oracle that returns $\\tilde{f}(S) = \\xi_S f(S)$ for each $S \\subseteq N$, where $\\xi_S$ is a stochastic and persistent sub-exponential noise with mean $1$. This paper proposes a unified framework for obtaining an algorithm with the same approximation ratio guarantee from any \"robust\" existing algorithm. Using this framework, the present paper proposes a $(1-1/e)$-approximation algorithm for the monotone and matroid case, $1/e$-approximation for the non-monotone and matroid case, and $1/2$-approximation for the non-monotone and unconstrained case.", "questions": "No question.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The theoretical results are very good. It resolves the open question of whether it is possible to obtain the same approximation ratio even under the noisy setting under several constraints.\n- The idea behind the proposed algorithm is interesting. As existing studies on this topic, the proposed algorithm maximizes a surrogate function instead of maximizing the noisy objective function itself. The main idea of this paper is to estimate the function value $f(S)$ by sampling values $f(S \\cup H')$ for random $H' \\subseteq H$ with $|H'| = t$. By using the smoothing lemma (Lemma 3.5), maximizing the surrogate function leads to a good approximation to maximizing the original function. This idea is very clean and can be applied to many other settings of submodular maximization. I have not read all the proofs in the appendices and do not understand why this simple approach overcomes the barrier that the existing papers had, but the proofs of Lemma 3.5 and Appendix A seem to use submodularity in a good way.\n- The paper is clearly written.\n\n---\nWeaknesses:\n- The definitions of submodularity in the beginning part of this paper are wrong. In the Introduction section, \"$i \\in T \\setminus S$\" should be replaced by \"$i \\in N \\setminus T$\". In the beginning of Section 2, \"any element in $x \\in N$\" should be replaced by \"any element in $x \\in N \\setminus B$. I believe that these are just typos, but if these wrong definitions are used anywhere in the proof, it would be problematic.", "was_revised": true, "final_justification": "I did not have any concern, and I keep my positive score.", "rebuttal": "Thanks for reviewing the paper and spotting the typo! We will fix it."}, {"review_id": "dI2Z2qRan1", "reviewer": "Reviewer_u1Du", "summary": "A fundamental problem in optimization is maximizing a submodular set function. When having access to a value oracle (i.e. an oracle giving the value of the set function for any set *precisely*), approximation algorithms for the maximization problem subject to cardinality/matroid constraints are known. The paper under consideration studies this problem with a slight twist: the value oracle is noisy, i.e. we observe a noisy version $\\tilde{f}(S)$ instead of $f(S)$, and we still would like to find a set which (approximately) maximizes the function's value. \nThe noise under consideration is multiplicative, i.e. for any set $S$, we have $\\tilde{f} (S) = \\epsilon_S \\cdot f(S)$ for noise $\\epsilon_S$. \n\nThe paper derives a black-box reduction from the noisy to the exact setting. More precisely, it states a meta-algorithm which satisfies that \"under some assumptions\", any approximation algorithm for the exact setting can be used to obtain the same approximation guarantee for the noisy case.\nFrom a technical point of view, the meta-algorithm is based on a randomized surrogate function which allows to estimate the value of the function $f$ with a reasonable error.\n\nUsing their reduction, the authors then derive (tight) approximation guarantees for the noisy setting subject to cardinality and matroid constraints in the monotone and non-monotone regime by applying their meta-algorithm to several known approximation algorithms.", "questions": "* Based on one of the weaknesses mentioned above: What is the intuition behind the sub-exponential noise? What are the limitations of the approach towards general noise?\n\n* The robustness assumption in Definition 3.1. seems restrictive at first glance. Is this really the case (even though several approx. algorithms fulfill this definition)? Could this be extended to less restrictive definitions as well?\n\n* Is your approach also usable for, say, knapsack constraints or similar?", "limitations": "No negative societal impact expected.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*: \nThe general framework is powerful in a sense to deliver tight approximation guarantees in the settings under consideration. It extends previous work (where surrogate functions to approximate the value of the submodular set functions where mainly deterministic) in a suitable way by randomization. \nThis allows the authors to provide a unified framework for several problem specifications (matroids/monotone/...) which were previously handled by more tailored approaches.\nThat said, the meta-algorithm is very clean -- in my opinion an additional plus of the construction in the paper. \n\n*Weaknesses*:\nFrom a purely technical perspective, the contribution of the paper seems to work in the direction of the natural extension of previous work. Working with surrogate functions was already known before and also the choice of the randomized surrogate function in the paper seems to be not super unexpected. In addition, the distribution of the noise is limited to sub-exponential distributions which ensure desirable concentration properties. This further weakens the results of the paper as it remains open if the approach can be extended to general noise as well.", "was_revised": true, "final_justification": "As said, I keep my positive score.", "rebuttal": "Thanks for your review and positive assessment! \n\n> (Weakness 1) Randomized surrogate function seems to be not super unexpected. \n\nWe agree that the idea of using randomization is not super surprising in and of itself. However, we still find it interesting that a simple randomized framework is already sufficient to recover and improve existing results while also allowing us to easily prove new results. It also allows us to reduce the problem of designing and analyzing algorithms in the noisy setting to checking robustness of existing approximation algorithms. It was not clear from prior work that this decoupling was possible.\n\n> (Question 1) What is the intuition behind the sub-exponential noise? What are the limitations of the approach towards general noise?\n\nWe would need some assumption on the distribution in order to have some result. Without any assumptions, we could have very bad distributions. For example, consider a case where there are n items and we just want to pick one. One item is very valuable but extremely noisy and will return 1 most of the time. All other items have value 1. It would not be possible for any algorithm to distinguish between these items. In addition, we also note that our sub-exponential assumption is already more general than prior work such as [11, 14].\n\n> (Question 2) The robustness assumption in Definition 3.1. seems restrictive at first glance. Is this really the case (even though several approx. algorithms fulfill this definition)? Could this be extended to less restrictive definitions as well?\n\nWe suspect that the robustness definition is not an extremely strong assumption but we don’t yet have a formal argument for it. Intuitively, if you ran an approximation algorithm but the values were off by $\\epsilon$ then, by virtue of it being an approximation algorithm, you would still expect a good approximation. It is an interesting question to see if one can formalize a connection between approximation algorithms and robustness.\n\n\n> (Question 3) Is your approach also usable for, say, knapsack constraints or similar?\n\nGreat question! This is a great open question for future work. The analysis of our meta algorithm does rely on the fact the constraint is a matroid constraint.  Our analysis uses a basis-exchange property for matroids, which does not directly extend to more general constraints (e.g., knapsack constraint)."}, {"review_id": "aMnk9qpDzG", "reviewer": "Reviewer_GM3f", "summary": "This paper studies the problem of submodular maximization problems under a noisy oracle. In particular, it is assumed that the noise is random and unbiased, and that multiple queries of the submodular objective on the same subset is persistent. In that sense, the estimate of the same marginal gain/subset can't be made more accurate through averaging over multiple queries. To address this challenge, the authors construct a surrogate function to estimate marginal gains and propose algorithms for both monotone and non-monotone submodular maximization under this noise model.", "questions": "Please refer to my comments under the \"Strengths And Weaknesses\" section. If the authors are able to adequately address the concern regarding the correctness of the proof, I would be open to raising my score. More generally, I recommend that the authors carefully review the technical details to ensure the correctness of all proofs.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "* Strength:\n1. The paper addresses a challenging and practically relevant problem. Unlike prior work that assumes either deterministic persistent noise or unbiased noise with access to repeated queries, this work considers a more realistic and difficult setting: unbiased random noise with only one query per subset, where noise is persistent.\n\n2. The proposed method is quite interesting. By estimating the marginal gain through the construction of a surrogate function, it might be possible to proposed unified algorithms for solving various submodular maximization problems.\n3. The paper is well-written and easy to follow\n\n* Weakness:\n1. A major concern lies in the correctness of the technical proofs. While I did not verify every detail, I identified a potential issue in Lemma 3.3. Specifically, to apply the Hoeffding's inequality, the random variables $f(S\\cup H_i)$ for different $i\\in[m]$ should be independent. However, since $H_i$ are sampled without replacement, $f(S\\cup H_i)$s are no longer independent. This mistake in the proof raised concerns about whether there exists other incorrect proofs in this paper.", "was_revised": true, "final_justification": "The authors have addressed my concerns regarding the correctness of the technical proofs, and I have updated my score accordingly.", "rebuttal": "Thank you for noting the issue with Lemma 3.3.  As noted in the paper, one cannot use the usual Hoeffding inequality out of the box because the random variables are not independent.  However, Hoeffding also proved a version for sampling without replacement (see Proposition 1.2 of [1] below or Section 6 of Hoeffding’s paper [2]). Basically, the result says that the same bound holds even when sampling without replacement.  Using the notation in [1], we would just set $X_i = f(S \\cup H_i)$, so $X_1, …, X_m$ are sampled from a finite population of $h$-choose-$t$ elements without replacement.  We will add this reference to the proof of Lemma 3.3.\n\n-----\n\n[1] Bardenet, Rémi, and Odalric-Ambrym Maillard. \"Concentration inequalities for sampling without replacement.\" Bernoulli (2015): 1361-1385.\n\n[2] Hoeffding, Wassily. \"Probability inequalities for sums of bounded random variables.\" Journal of the American statistical association 58.301 (1963): 13-30."}]

Author rebuttal:

Meta-review: The paper studies submodular maximization in the setting where we are given only noisy evaluations and the noise is persistent in the sense that multiple calls to the evaluation oracle with the same set return the same value. This model was introduced and studied in prior work, which also designed an algorithm with an optimal 1-1/e approximation for monotone submodular maximization with a cardinality constraint and a sub-optimal (1-1/e)/2 approximation for a matroid constraint. The main contribution of this work is an algorithm that provides a black-box way of turning an algorithm for the setting without noise with certain properties into an algorithm for the noisy setting with only an o(1) loss in the approximation. By combining this algorithm with the continuous greedy algorithm and the double greedy algorithm, the paper obtains improved approximation guarantees for a matroid constraint and the unconstrained setting.

The reviewers appreciated the theoretical contributions and found the main results to be strong. The reviewers also raised several concerns, most of which were sufficiently addressed by the author response and the subsequent discussion. One of the remaining concerns was that the novelty of the techniques is somewhat limited. Following the discussion, there was sufficient support among the reviewers for accepting the paper, and the reviewer with a more negative evaluation noted that the discussion addressed their concerns.
Decision: Accept (poster)