A Near Linear Query Lower Bound for Submodular Maximization
Authors: Binghui Peng
Aviad Rubinstein
Venue: ICML 2025 poster (2025)
Keywords: Submodular maximization
sublinear algorithm
Primary area: theory->optimization

Abstract: We revisit the problem of selecting $k$-out-of-$n$ elements with the goal of optimizing an objective function, and ask whether it can be solved approximately with sublinear query complexity. For objective functions that are monotone submodular, [Li, Feldman, Kazemi, Karbasi, NeurIPS'22; Kuhnle, AISTATS'21] gave an $\Omega(n/k)$ query lower bound for approximating to within any constant factor. We strengthen their lower bound to a nearly tight  $\tilde{\Omega}(n)$. This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires near-linear query complexity, but we can estimate the value of the optimal subset in $\tilde{O}(n/k)$ queries, and that this is tight up to polylog factors.

A Near Linear Query Lower Bound for Submodular Maximization
Binghui Peng Aviad Rubinstein
Abstract
scales sublinearly with
We revisit the problem of selecting k-out-of-n el- ements with the goal of optimizing an objective function, and ask whether it can be solved ap- proximately with sublinear query complexity. For objective functions that monotone submodu- lar, [Li, Feldman, Kazemi, Karbasi, NeurlPS' 22; Kuhnle, AISTATS'21] gave an (n/kk) query lower bound for approximating to within any con- stant factor. We strengthen their lower bound to a nearly tight (m)) This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires linerr query complexity, but we can estimate the value of the optimal subset in Ö(n/k) queries, and that this is tight up to polylog factors.
In full generality, it is clearly hopeless to find approxi- mately optimal k-subset without querying all (*) subsets (not to mention sublinear query complexity), so as is com- mon in the litcrature we restrict our attention to monotone submodular objective functions, i.c. we assume that the marginal contribution from each additional element is di- minishing, yet it is always non-negative (see Section 2 for formal definition). Since our result for worst-case func- tions in this class is quite negative, we also consider the most important special case: (monotone) additive objective functions, i.e. f(S) = Eies w; for unknown w; 2 0.
Monotone submodular maximization has important appli- cations in machine learning (see e.g. the recent survey of Bilmes (2022) and references therein), and the prob- lem sizes in those machine learning applications increases rapidly. This inspired over the past decade extensive effort in obtaining sublinear time algorithms for approxi- mate submodular maximization by parallelization (Balkan- ski et al., 2016; Balkanski & Singer, 2018; Balkanski et al., 2018; 2019; Chekuri & Quanrud, 2019a;b; Chen et al., 2019; Ene & Nguyen, 2019; Fahrbach et al., 2019; Kazemi et al., 2019a; Breuer et al., 2020; Ene & Nguyen, 2020: Balkan- ski et al., 2022a:b). In contrast, in this work we look for algorithms whose total work (specifically, total query com- plexity) sublinear. Indeed, this is motivated in part by the increasing monetary and environmental cost of total work of state-of-the-ree machine learning algorithms that already achieve significant parallelization. Beyond these important connections to applications in machine learning, submodu- lar maximization itself is generally fundamental problem in optimization.
1. Introduction
We consider the problem of selecting the "best" kfout-of-n elements, e.g. selecting & locations to place sensors, select- ing & features include in data analysis, or selecting k samples for training& model. We particularly interested in the case where:
Expensive query access We are not given an explicit func- tion to compute what makes one subset "better" than an- other: rather we have expensive query access to an oracle that evaluates different candidate subsets (e-g. estimating the quality of prediction from subset of features or samples by training a smaller model on them).
Sublinear query complexity Motivated by the expensive query constraint and large problem sizes in machine learn- ing applications, we ask whether it is possible to obtain approximately optimal subsets with query complexity that
The question of sublinear-query algorithms for submodular maximization was considered by Li et al. (2022); Kuhnle (2021), who showed that any constant factor approxima- tion algorithm requires query complexity ((n/k)) Li et al. (2022) additionally proved lower bound of ② [ng(mj) for the special case of k: = O(n). Hence, for the special case of k ((1) and (n), previous work rules truly sublinear query complexity algorithms.
'epaarment of Computer Science, Stanford Univer- sity. United States 'Department of Computer Science, Stanford University, United States. Correspondence to: Binghui Peng <binghuip Siinghip@stanford.dduss Aviad Rubinstein <aviad es stanford.edu>>.
Our first result strengthens this impossibility result by rul- ing out approximate submodular maximization in sublinear query complexity for any k & n, even if we're just inter-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lower bound for submodular maximization
ested in estimating the value of the optimal subset:
can proceed with further analysis selection; otherwise, unnecessary efforts can be avoided.
Theorem (Submodular: informal version of Theorem 3.9). With a monotone submodular objective function and for any k o(n), no O(n) -qqeryy complexity algorithm can approximate the value of the optimal k--ubset to within any constant factor.
Query complexity vs. Runtime The focus of this paper is on the query complexity, which is standard in the liter- ature. Our algorithm uses sublinear queries (i.e., ((n/k) /k)) and linear computation time (i.e. Ö(n)), both of which are optimal'. The motivation for studying query complex- ity arises from practical concerns in training large models using only subset of the data. Even under the simplest assumption- an additive function we lack explicit input specifying each data point's marginal value. Instead, we estimate the value of a subset by, for example, training a smaller model from scratch. Related applications include data valuation (Ilyas et al., 2022), where a query to subset corresponds to training neural network over set [n] (S; in- fluence maximization (Kempe al., 2003), where query to subset S corresponds to a simulation or social experiment using S as the seed set. In all these settings, queries are significantly more expensive than individual computational steps: while linear computation time (c.g., loading or pro- cessing the full dataset) is feasible, making a linear number of queries (e.g., training different models) is impractical.
We note for typical applications of submodular maximiza- tion (e.g. dataset selection selecting a small dataset to train a model; influence maximization selecting a small subset of influential users), the subset size & is neither linear in the entire dataset, nor a small constant that can be ignored. Comparing with previous work (Li et al., 2022; Kuhnle, 2021), we obtain improved (and optimal) lower bound for the critical regime of polylog(n) S k 1 polylog(n)) Our lower bound rules out sublinear query algorithms over all possible regimes of k and fully resolves the query complex- ity of monotone submodular maximization (up to polylog factor). fundamental question in optimization theory.
Given this sweeping negative result, we turn our attention to characterizing the complexity of selecting an approximately optimal k-subsee with an additive objective function. Here, we have a mix of negative/positive results, where the key difference depends on whether we just want to estimate the value of the optimal subset, or actually find it:
Additional related work The query complexity of mono- tone submodular maximization has been studied in the lit- erature. The greedy algorithm (Fisher al., 1978) finds an (1 - -appoooppoo solution using ((nk) queries. The query complexity can be improved, the stochastic greedy al- gorithm (Mirzasoleiman et al., 2015) makes O(n log(1 /e)) queries and return an (1-1/e-o approximate solution; (Li et al., 2022) gives a deterministic algorithm using Onn/c) queries. Despite of extensive research, the only query lower bound known ((n/k) from the recent work of (Li et al., 2022; Kuhnle, 2021).
Theorem (Additive:
Informal version of Theo-
rems 3.7, 4.1,
With a monotone additive objective function and for any k = o(n).
No Ö(n) qquery complexity algorithm can find an ap- proximately optimal k-subbse, for any constant approx- imation factor (Theorem 3.7).
For any constant > 0, there exists an (1 + e)- approximation algorithm for estimating the value of the optimal k-subset using only Ö(nkk) queries (The- orem 1.
In addition to previously mentioned work on parallel al- gorithms for submodular maximization, our work is also related to algorithms for submodular maximization in other sublinear models such as dynamic (where the update time needs to be sublinear) (Chen & Peng. 2022; Peng, 2021; Peng & Rubinstein, 2023; Lattanzi et al., 2020; Monem- izadeh, 2020; Dütting et al., 2023; Agarwal & Balkanski, 2023; Banihashem et al., 2024; 2023) and streaming (where the space needs to be sublinear) (Badanidiyuru et al., 2014; Feldman et al., 2023; Chakrabarti & Kale, 2015; Chekuri et al., 2015; Feldman et al., 2021; Huang et al., 2021; Liu et al., 2021; Shadravan, 2020; Norouzi-Fard et al., 2018; Alaluf & Feldman, 2019; Agrawal al., 2018; Kazemi et al.,
Furthermore, this query complexity nearly tight for any algorithm obtaining any constant factor approximation (Theorem 4.7).
Our algorithm uses sublinear queries and estimates the value of the optimal k-subset, this is a standard goal in the field of sublinear algorithms, see (Chen et al., 2022; Charikar et al., 2023; Behnezhad, 2023; Behnezhad et al., 2023; Bhat- tacharya et al., 2024) and reference there in. To motivate this, consider a scenario where one needs to select sub- set from a large dataset under a budget constraint. Our algorithm can first be used to assess whether the dataset is sufficiently valuable- - that is, whether it contains elements with large values. If the dataset meets this criterion, one
'It is casy to see that lincar computation time is necessary: Imagine there is one (unknown) element that has huge value com- paring all other elements, an algorithm needs to at least load that element estimate its value, which takes 2(n) time in expec- tation.
2

---

Lower bound for submodular maximization
2019b; Huang et al., 2022; Feldman et al., 2018; Alaluf et al., 2022; McGregor & Vu, 2019; Indyk & Vakilian, 2019).
better than (Li al., 2022; Kuhnle, 2021) (i.e., B(yn). From technical point of view, all previous lower bounds are proved using counting arguments. Our technique is completely different from them, it is based on novel ideas, including (1) the query to communication reduction, (2) a communication lower bound using information complexity and distributed proea-pocessing inequality, and (3) new construction of the hard submodular function with two-level truncation.
1.1. Technique Overview
The linear lower bound for submodular maximization The key idea driving our approach for proving lower bounds is to relate the query complexity of submodular maximiza- tion to the communication complexity of distributed set de- lection problem.
We first describe the communication problem of distributed set detection task. The distributed set detection is a multi- party communication problem, where each party observes the outcome of n coins. Among these coins, k coins are fair and have mean 1/2, while the rest - & coins are biased and have small mean vallue. The goal of these parties is to collectively identify a small fraction (e.g. k.1 of fair coins. We prove that the distributed set detection requires ((1)) communication cost using the distributed strong data process incquality (SDPI) and a direct-sum argument.
Sublinear algorithm for linear function Our algorithm is multi-scale combination of two base subroutines. The first subroutine is to randomly select set of size n/m and estimate the value of each individual element. This sub- routine yields a good estimate on the top m-th quantile of the ground set, but fails to give an accurate estimation on top (mm) elements (to see this, imagine there are o(m) ele- ments that have super large value, then one can observe their value only after sampling > n/m elements). The second subroutine is to partition the ground set into subsets and estimate the value of each subset. Intuitively, this subrou- tine alleviates the weakness of the first subroutine - if there are (m) elements that have super large value, then most of them would fall into different subsets and we can have good sense of their value after querying the value of m subsets. Nevertheless, the second subroutine could fail if the top o(m) elements are not significantly larger than rest elements (say they have value 2 and the rest have value O or 1, then querying the value of m subsets gives negligible hints on the value of top (m) elements).
Our key observation is that the linear communication lower bound for distributed set detection yields a linear query lower bound of submodular maximization. To this end, con- sider a linear function whose weight on the i-th element equals the summation of the outcome of the i-th coin. The optimal susbbet is exactly the i fair coins, given the num- ber of parties is roughly (llo(())). The crucial observation is one could simulate the query algorithm in the communi- cation model, with only polylog(n) overheads: If the query algorithm asks for the value of f(S) for some set S, then all parties just locally compute the summation of coins in S and broadcast their results, it takes at most ((log(n))² communication bits (O)) parties and log(n) bits per party). This proves that finding the optimal k-subset requires (()) queries due to the 2(n) communication lower bound of distributed set detection.
Intuitively, both subroutine have their own weakness, but they are somewhat complementary to each other. We wish to combine them in careful manner to get optimal sub- linear algorithm. The real situation gets complicated due to the possible intricate choice of the top k elements, so we only sketch our final solution here. Indeed, we compose the two base subroutines in multiple scales. Let k; = (1 + e)", at each level r, the algorithm randomly partitions the ground set into nk,/k subsets and estimates the ky-th quantile of these subsets (hence each level takes ((n/k) queries). Roughly speaking, we expect the top k,-th subsets to be as valuable as the top ky-th element + an average bucket. Our final estimate is weighted average over the output at each scale. See Section 4 for details.
When the goal is to estimate the value of the optimal k- subset, the above hard instance fails because the query algo- rithm could easily find one fair coin using Ö(n/k) queries. To this end, we construct a monotone submodular function by applying two levels of truncation to the above linear function. Roughly speaking, the optimal k-subset still corre- sponds to the k fair coins in distributed set detection, but the two-level truncation over the linear function (see Eq. (2)(3))
masks off useful information on large sets and requires the detection of a non-trivial fraction of the fair coins (see Sec- tion 3.2 for detailed description).
Remark 1.1 (Comparison with previous work al., 2022; Kuhnle, 2021)). The previous work (Li et al., 2022: Kuhnle, 2021) prove a lower bound of ((nn/k) and (I.i et al., 2022)
Organization of the paper We describe notations and models in Section 2. The lower bound for submodular max- imization is presented in Section 3, and the algorithm for additive function is in Section 4. Due to space constraints, we defer detailed proof to the appendix.
additionally has a lower bound of ((()) when k = (()).
Our approach yields significantly stronger lower bound, e.g. when k: = vn, our lower bound (i.e., M(n)) is quadratically
3

---

Lower bound for submodular maximization
2. Preliminary
3. Lower Bound for Submodular Maximization
Notation We write [n] = 21,2,..., nnj. For random vari- ables X, Y, we use Y( to denote the mutual infor- mation of X, Y. Yr) denote the Hellinger distance, TV(X; Y) to denote the total variation distance. For any value E [0, let Bp the Bernoulli distributions with mean
We prove that the distributed set detection requires (2(n) communication cost in Section 3.1, using the distributed SDPI inequality and direct sum argument. In Section 3.2, we give a simple reduction from distributed set detection to submodular maximization, which rules out the possi- bility of approximately finding the optimal k-subser using sublinear query (and it holds even for additive function). In Section 3.3, we present a more involved reduction that proves the hardness of appreximating the value of optimal k-subset.
Submodular maximization Let ʃ {0, + R+ be a nonnegative set function. For any sets A, B C [n]. let (B( = f(A U BB (A) be the marginal value of a set B w.r.t. set A. The function is monotone if fBB)= f(A) for any A S B. The function is said to be submodular if fa(u)= 2 fa(()) holds for every sets A S B S [m] and every element u E [n] \. B. In a constrained monotone submodular maximization problem, there is a budget & E [n] and the goal is find a subset 5 S [n]] of size most k that (approximately) maximizes the function value, i.e., |ax J(S). The problem is studied in the query oracle model, where each time the algorithm submit query V S [n] and the oracle returns the function value f(V).
3.1. Communication Lower Bound
A key ingredient of our proof is a communication lower bound on the distributed set detection problem. The dis- tributed set detection is a multi-party communication prob- lem and we study it under the blackboard model, where every party can write and read over a common blackboard.
Definition 3.1 (Distributed set detection). Let n, k, m be in- put parameters, Do, Dj be two Bernoulli distributions with mean Ma, Ml. m the number of parties, who communi- cate in the blackboard model. Let I S [n]] be an index set of size [4/2, A:). The input of the t-th party (t E [m]) is vector X, E {0,, 1)", such that for any i E [m], Xt, ~ Du if i E [n] / and X ~ Dj if E I. The goal is to output set I C [m] ( = k) that maximizes the intersection [ [
Let S* := argmax sg [_], (SS) be the optimum solu- tion set (breaking ties arbitrarily). In the search problem, the goal to find an (approximately) optimal solution, and say the algorithm finds an a-approximate solution if it returns set S ((S) I k) such f(S) 2 (S*) In the decision problem, the goal is to determine the opti- mal value, given a value OPT, we say an algorithm is a-approximate if it can distinguish between f(S*) 2 OPT vs. f(S*) S a OPT.
The main goal of this section is to establish the following communication lower bound of distributed set detection.
We have the following basic fact about submodular func- tions.
Theorem 3.2 (Communication lower bound). Let E (0, 1). n, k, m be integers and satisfy S en/4. Let e 2 be some constant and 20 S f1 S cpo. For the problem of distributed set detection, any (randomized) communication protocol that outputs e-fraction of the index set (i.e., II n I 2 ek) in expectation has communication complexity at least M(e2n/c).
Fact 2.1. We have the following basic facts about submod- ular functions: (1) A linear function is submodular; (2) If f. are submodular, then f ++ is submodular; and (3) If I is monotone submodular, Let e >> O be any constant, and let g(S) = min{f(S), c} for any S C [n), then is also submodular.
With the goal of proving Theorem 3.2, we first introduce the distributed detection problem, where each party only receives one coordinate and the goal is to detect whether they come from Do or D1,
Information theory To establish communication lower bounds, we need few basic facts of information theory.
Fact 2.2 (Hellinger v.s. total variation). For any two distri- butions P, Q, we have
Definition 3.3 (Distributed detection). Let V B1y2 and Do. Dj be two Bernoulli distributions with mean Moo Pt There are m parties communicate in the blackboard model and each party receives a single bit Z, ~ Dy independently drawn from Dy (with the same V for all parties). The goal is to determine the value of V.
h²(P. = TV(P.Q) Q))
Fact 2.3. Suppose A, B are independent when conditioned on C. then we have
The distributed detection problem has large information cost.
T(D; A|C) + I(D;; B|C) S T(D;A, B(C
4

---

Lower bound for submodular maximization
Lemma 3.6. Suppose the communication protocol of dis- tributed set detection outputs e-fraction of the index set, then the protocol in Figure 1 correctly guesses the value of V with probability at least + 1'
Using public randomness, the m parties sample set (i1...., i [n].
For any E [m]. the t-th party constructs the vector X E {0, 1)" as follow:
Combining Lemma 3.4 - 3.6, we can prove Theorem 3.2.
Do
E [m]]Z
X1,1 ~
Dr i (i,....,kk]
3.2. Lower Bound for Search Problem
24 i i=
We start with simpler linear query lower bound for the search problem. It is worth noting that the lower bound holds even when the function additive.
Then the m parties follow the communication protocol of distributed set detection, and they output 1 i I.
Theorem 3.7. Let n be the size of the ground set, k E [n] the cardinality constraint, a E (0, be the approxima- tion ratio and l. = ((a)). A randomized algorithm must make at least St(2n// log (n)) queries in order find an c- a-approximate solution for submodular maximization under the cardinality constraint.
Figure I. Communication protocol for distributed detection
Lemma 3.4 (Distributed SDPI, Theorem 1.1 in (Braverman al., 2016)). Suppose Po 141 S cpe, 3(Po,1) 11) be the SDPI constant of Pos f11 Let TI be the communication transcript, = (resp. I1lv=1) 1) be the transcript when V =0 (resp. = 1). In the distributed detection problem, we have the following distributed strong data processing inequality.
We reduce from the distributed set detection problem. Let
100
a 15,
e2
and
N4 =, P1 = 1/2
c= 1/2e
1 (TI (=,, =11 & K (B(p0,111)
Given instance of distributed set detection with input X1,..., Xm E 10, consider the following function
min 7 Zm = 0), I(TI; 7 7 = 1)}
f(5) = Σ Σ X (
for some fixed constant K 0.
rE
We apply a direct sum argument and prove the information cost for distributed set detection (n) times the informa- tion cost of distributed detection. To this end, consider the communication protocol in Figure for distributed detec- tion.
It is clear that the function f is non-negative, monotone, submodular since it is linear function. Furthermore, its optimal solution satisfies
Lemma 3.8. With probability least 1- 1/n"", for any a-approximate solution set S C [n] ([S] < k), we have |S n Z 2 ck.
Let II be the transcript of distributed set detection. Let R be the public randomness used by the distributed set detec- tion, R' = (R, I) be the public randomness of distributed detection. The information cost of distributed set detection defined as
The proof of Theorem 3.7 follows from Lemma 3.8 and the communication lower bound of distribution set detection (Theorem 3.2).
IC
max 4/2
(II:
Xm I, R).
(1)
3.3. Lower Bound for Decision Problem
The information cost is also a lower bound on the communi- cation cost of distributed set detection.
We next prove a linear query lower bound for the decision problem.
We have the following direct-sum thcorem on the informa- tion cost, the proof is similar to Proposition 5.2 (Braver- man et al., 2016).
Theorem 3.9. Let n. be the size of the ground set, k E [n] the cardinality constraint, a (0, 1) be the approxima- tion ratio, OPT g and k 0(a2n), n). A randomized algorithm must make at least Di n/ log (n)) queries in order to distinguish between
Lemma 3.5. For any k 2 2, we have
IC
I11, Zm V 0)
n1
k
YES Instance f(S*) 2 OPT
We next analyse the correctness the protocol.
NO Instance f(S*) s OPT
5

---

Lower bound for submodular maximization
We present reduction from the distributed set detection problem. The construction of the submodular function and the choice of parameters are slightly different from Theo- rem 3.7. Let
From high level, the communication proceeds in (at most) R rounds. At the r-th round, the m parties look at the r-th query S, S [ra] of ALG, they either decide an output set or construct the value oracle f(S,). Con- cretely, if the size of S, is large, they set f(Sr) = mk and proceed to the next round/query. Otherwise, they par- tition the set S, sets, each of size at most k. The m parties then com- pute the value of Exes.,, Elelm Xx,; for each subset Spt (T E [20/ar)) If the value is large, they return the set I + S,,7 otherwise, they set the oracle value ((S)) = min (Exe(m) Eies. Xt,: + (sk0 mk) and proceed to the next round/query.
a²
100 log e2
800
Sr, U... U S,,20/a into 20/a sub-
and
N4 P1 1/2,
c= 1/2e
Given an instance of distributed set detection with input X1...., Xm E {0, 1)", consider the following functions
(S) = min Σ Σ
X1,+ +
Σ
Σ
X1,
VESnZ [E(m)
{I fe/m]
Algorithm 1 Reduction: From submodular maximization to distributed set detection
am |||
+
mkk
20
1: Input: Input XI...., .......,,m... E {0,1)", submodular max- imization algorithm AL.G,
and
for r 1,2,... .... R do
fSo(S)=
min
min
Σ
X
aamk
3: Let S, S [n] be the r-th query of AL.G
10
4: if [S > 20k/a then
iESnZ (E(m]
5:
f(S.) <- mk
aml
X +
.mk
(3)
6:
else
20
7: Partition S, = Sy,1 U U...UU..UUU.000
1EST [E[m]
for = 1.2......0/ do
if Eiss., Eie(m) Xx, 2 mk/200 then
It is easy to that both fyes. fno monotone and submodular, because linear combination and minimum with a constant keep submodularity and monotonicity (see Fact 2...
10:
i+ S.,r and return
11:
end if end for
12:
13:
S(S,)
min Ere(ml X +
We first make a few simple observations.
amm (m//5,1/20,m. mk)
Lemma 3.10. With probability at least 1/n we have
14: end if
15:
end for
X1,i [01/2 e)m, (1/2 e)m] I
(4)
[E(m]
Correctness First, we prove the correctness of the proto- col. We divide into two cases.
and
Σ X E (em/2, 2em) [c(m)
e [m]]z
(5)
Case Algorithm returns a set Î + Sr at some round
r E [R] and E [20/a]. Then we prove must satisfy
[S,, nz 2 ek.
In the rest of the proof, we would condition the high probability event of Lemma 3.10. Let OPT mk/5. We have the following observation on the optimal value of fyes and Sno-
We have
m2 2
Σ
X
ieS,,r 1E(m)
Lemma 3.11. We have (1) maxs- gin) fyes(S*) > OPT; and (S) < OPT for any S C [S] k.
Σ
Σ
X +
X1
iES., NI tE|m
iES. MnS
< |S 0z) (1/2 + e)m + 2em.
Now we can proceed to prove Theorem 3.9.
Here the first step follows from the assumption, the third step follows from Lemma 3.10. Plugging the value of a, e, we have that
Proof of Theorem 3.9. Suppose there exists an algorithm ALG that makes at most R queries and distinguishes be- tween the YES/NO instance. Consider the communica- tion protocol in Algorithm for distributed set detection.
a²/2000 2 k > ek.
S 0I
1/2
6

---

Lower bound for submodular maximization
Case 2. Suppose Algorithm 1 never returns anything, i.e., the if condition Line 9 of Algorithm is never satisfied. Then we prove f(S,) (S.) (S,) holds for every r E [R].
Parameters and notation Let w; = f() 0 and we have f(S) Eies wi for all S C [n]. For parameters R, R1, R2 defined below, we define set {kr}, Jr of scales ranging from hr = 1 to RR-R,+R, = k. Specifically, we let R = 100 log(n)/e², R1 = logi+e l (k/R2), R2 log1+o (182). Let ky = r for r S R. and K, = R(1 + e)"
Fix a round r E [ if |s,| 2 20k/a, then we have (S,) = (S.) = mk = (S.) due to Line 5 of Algorithm 1. Now suppose |s,| a we have
for E [R + 1: R + R + Ra].
20k
Algorithm description Our approach is de- picted as LINEARSUM (Algorithm 2). From a high level, LINEARSUM divides the largest k ele- ments into multiple scales. For the largest scales, kn E [KR+R,+I,.... k LINEARSUM di- rectly estimates the k,-th quantile and it takes roughly Ö(n/k,) = ((//k) samples.
f(S,) = min
Σ LESt [E(m]
Σ
Xx, + 0m/22120 mk
= (S,)
Meanwhile, by the assumption of the second case, we also have
Σ
Σ
XW S Σ Σ X
For smaller scales, k, E KRt we cannot directly use this naive estimation approach as we can- not afford ((n/kip) query complexity for smaller ky. To avoid this increase in query complexity, LINEARSUM ran- domly partitions the ground set [v] into nk./k buckets Ar,1...., Ar,nk, /1- Define f+(1) == f(Ar,) for i E [kk,/k], LINEARSUM estimates the ky largest element of fr- Roughly speaking, we expect the top k, bucket to be as valuable as the top k,-th element + an average bucket, so LINEARSUM further subtracts the average value of a bucket get an estimate of the contribution just from the top k, elements.
iES, te(m!
E ΣΣ X1,3
rE[20/a] iESr,r te|m]
emk/10, Hence, we also have (no = Syes (Sp) (see the definition in Eq. (2)()), This proved that (Sea(S,) = (S,) = f(S,) for any r e [R).
S (20//a) (a2mkk
In summary, we conclude that in Case 1, the reduction outputs a set I with [IZ] 2 ek, while in Case 2, the transcript of ALG is the same for fyes and fno. Since we assume ALG is able to distinguish between fyee: fno after R queries, then we must fall into Case 1. This proves the correctness of Algorithm 1.
Algorithm 2 LINEARSUM(f..)
1: r 1,2, ...., R+ R₁ do
Random partition [n] = Ar,1 U... U Ar /k into
Communication complexity Next we analyse the com- munication complexity. At each round E [R], the m par- ties need to compute Exe(m) Eies.,, Xe,s for T E [20/a]. For each 7 E [20/a], the t-th party (t E [m]) could com- pute the partial sum Eies., X locally, and then write it on the blackboard. Hence, the total communication cost per round is at most T m log(n) Ologg (n)/aa) There are at most R rounds, so the total communication cost over R rounds are (o)loo((n///) By Theorem 3.2, we must have Rlog² (m)/ 2 Q(En/c) = R2 a(a n/ log? (n)).
/k subsets
3: Define fr(1)= == I(Ar,)) for Vi [nk,/k]
4:
b, +- EESTMATTEUANTIIIIS..R
& 5: G. + bp nt. ((a))
6: end for
7: G.
<- ESTIMATEQUANTIIFU. kr) for r E [R + Rı +
1: R+ R2 + [B2
(n))c²))) =
8: Return RR+Ri Rd + Ra (kr k
Algorithm 3 ESTTIMATEQUUNTTIEEG ()
1: if log(m)) then
2: Random sample a set S C [m] of size
100m log(n)/te²
4. Sublinear Algorithm for Additive Function
3: Query g(i) for all E S and let by be the 100 lon(m)/ee2-t largest element of {g(1)ess
Theorem 4.1. Let n be the size of ground set, l be the con-
straint, e E (0, 1/8) be constant. Suppose I is monotone
Return b;
and additive, then there is an algorithm that approximates the value of max =(x)
5: else
within (1 + <) factor
6: Query g and Return the t-th largest element
using (n/k) poly(log(n)) e)) number of queries and suc- ceeds with probability at least 4/5.
7: end if
7

---

Lower bound for submodular maximization
4.1. Analysis
Fix partition A,, U...U.U.AAAAa..... For any subset S C [n]]. the number of collisions among S is defined as the total number of elements in S that are allocated to subsets with more than one element of S. We first prove that (with sufficiently high probability) there are few collisions among the largest t, elements.
We relabel the ground elements such that w 2.. W/ for convenience; note that LINEARSUM is oblivious to the labeling of ground set elements so this is without loss of generality.
We first prove that ESTIMATEQUANTIIELG !) gives good estimate on the value of the top f-th element g. [m] + R and let bj 2 b2 2 ...bm be the descending ordering of (g(i)) For any t. E [m)) the output by of ESTIMATEQUANTILE(, satisfies
Lemma 4.4. We have
Lemma 4.2. Given any function
For r & R, with probability at least 1 1 are no collisions among the top t, elements.
10OR. there
For r E E R + R1), with probability at least 1 1- 1-1/n', the number of collisions among the top tr elements are most is at most ek,
B(1+2)e S be S b(1+e)--4
for t > 100log(n)/e² with probability at least 1/n*, and b.- = by fort & 100 (o0go//))/
We next prove EjEAn Wytt, Aersish 5k is negligible.
Lemma 4.5. For any [R + Ri), S [nk,/k], with probability at least 1 - 1/n2, we have
In the rest of the proof, it is convenient to assume k divides n, and further that
log log2(n
Σ
wylt,<isk S
Σ Wj. 5
(log(n)/c)* < s n (c(c/oo((n))
(6)
br
jEA
This assumption is without loss of generality as we could just add dummy elements to the ground set.
Finally, we prove Ejeam. Wj 1j28 concentrates around the mean.
The key step is to prove that c, gives good estimate on the ky-th largest element of f.
Lemma 4.6. For any E [R+ Ry] and i E [nk,/k], with probability at least - 1/n2,
Lemma 4.3. For r I R, with probability at least
100
k nk,
2c
Σ
w S S Wk.
2c
wy.
(7)
Σ Wy 1isk JEAL.
Σ j>k
Uj +
Trr
log(n)wrk
R
R
jsk
JSK
and for r [R +
1: R R1), with probability least
We can obtain Lemma 4.3 from Lemma 4.4 Lemma 4.6, and obtain Theorem 4.1 using Lemma 4.3.
1 ni, we have
2
2
Σ Wy-
4.2. A Nearly-matching Lower Bound
(1126))k kr
Wi S G S W(1-2ebr
+
J5k
jSk
We present a matching lower bound to Theorem 4.1 whose proof can be found at the Appendix.
(8)
Theorem 4.7. Let f be an additive function, n be the size of ground set, be the constraint, a E (0,1) 1) be a con- stant. Then it takes 2(a2n/ hollog(()) queries distinguish between
The detailed proof of Lemma 4.3 can be found at Appendix and we sketch the high level idea here. In the proof of Lemma 4.3, fix value of r, let 4, Iog"(n))e" when < R and t, = k, log" log"(n/)// when E [R+ 1: R + R1)- For each subset i /k), we decompose f(Ar,) into three parts
YES Instance: f(S*) > OPT
NO Instance: f(S*) S a OPT
f(Ar.))
Σ Wi JEAni
A Acknowledgement
Σ jEA.,
wylyst + Σ
wjlt + Σ Wylgsk
The authors would like to thank Yair Carmon for useful discussion over the project. The work is supported by NSF CCF-1954927, a David and Lucile Packard Fellowship. AFOSR award FA9550231025 and ONR award number N000142212771
jEA,
JEAr,
From a high level, we wish to prove that (1) there is at most one element contributes the first term; (2) the second term negligible; and (3) the last term concentrates on mean.
8

---

Lower bound for submodular maximization
Impact Statement
Balkanski, E.,, Rubinstein, A., and Singer, Y. An exponential speedup in parallel running time for submodular maxi- mization without loss in approximation. In Chan, T. M. (ed.), Proceedings of the Thirtieth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 283-302. SIAM, 2019. doi: 01111331197861119777
This is a theoretical paper and it does not present foreseeable
negative social impacts.
References
Agarwal, A. and Balkanski, E. Learning-augmented dynamic submodular maximization. arXiv preprint arXiv:2311.13000 2023.
Balkanski, E., Rubinstein, A., and Singer, Y. An optimal approximation for submodular maximization under ma- troid constraint in the adaptive complexity model. Oper. Res., 7065):2967-2881, 2022a. doi: 10. 10.1287/OPRE.2021. 2170.
Agrawal, S., Shadravan, M., and Stein, C. Submodu- lar secretary problem with shortlists. arXiv preprint arXiv: 2018.
Balkanski, E., Rubinstein, A., and Singer, Y. The limitations of optimization from samples. J. ACM, 69(3):21:1 2022b. doi: 10.1145/3511018
Alaluf, N. and Feldman, M. Making sieve random: Im- proved seni-stre algorithm for submodular maxi- mization under a cardinality constraint. arXiv preprint 1900, 2019.
Banihashem, K., Biabani, L.., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., and Monemizadeh, M. Dynamic con- strained submodular optimization with polylogarithmic update time. In International Conference on Machine Learning, pp. 1660-1691, PMLR, 2023.
Alaluf, N., Ene, A., Feldman, M., Nguyen, H. L., and Suh,
A. An optimal streaming algorithm for submodular max- imization with a cardinality constraint. Mathematics of Operations Research, 47(4):2667-284 2690, 2022.
Banihashem, K., Biabani, L.,, Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., and Monemizadeh, M. Dynamic algorithms for matroid submodular maximization. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3485-3533 SIAM, 2024.
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., and Krause, A. Streaming submodular maximization: Mas- sive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference Knowl- edge discovery and data mining, pp. 671-680, 2014.
Balkanski, E. and Singer, Y. The adaptive complexity of maximizing a submodular function. In Diakoniko- las, I., Kempe, D., and Henzinger, M. (eds.), Proceed- ings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 pp. 1138-1151. ACM, 2018. doi: 10. 10.114553188745531868775 URL https: //o1.. http:/1111111111181111 3188752.
Behnezhad, S. Dynamic algorithms for maximum matching size. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 129-162. SIAM, 2023.
Behnezhad, S., Roghani, M., and Rubinstein, A. Sublinear time algorithms and complexity of approximate maxi- mum matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp. 267-280, 2023.
Balkanski, E., Rubinstein, A., and Singer. Y. The power of optimization from samples. In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 4017-4025, 2016.
Bhattacharya, S., Kiss, P., Saranurak, T., and Waje, D. Dy- namic matching with better-than approximation in poly- logarithmic update time. Journal of the ACM, 71(5):1-32, 2024.
Bilmes, A. Submodularity in machine learning and arti- ficial intelligence. CoRR, abs/2202.001332. 2022. URL https: /apps://araa http//axxvvv.ggg....... wttp:o///b.bb/..10..1.1222
Balkanski, E.,. Breuer, A., and Singer, Y. Non-monotone sub- modular maximization in exponentially fewer iterations. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 2359 2370, 2018
Braverman, M., Garg, A., Ma, T., Nguyen, H. L., and Woodruff, D. P. Communication lower bounds for sta- tistical estimation problems via a distributed data pro- cessing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 1011-1020, 2016.

---

Lower bound for submodular maximization
Breuer, A., Balkanski, E., and Singer, Y. The FAST al- gorithm for submodular maximization. In Proceedings of the 37th International Conference Machine Learn- ing. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp- 1134-1143. PMLR, 2020.
Dütting, P., Fusco, F., Lattanzi, S., Norouzi-Farde A., and Zadinoghaddam, M. Fully dynamic submodular maxi- mization over matroids. In International Conference Machine Learning, pp.
PMLR, 2023.
Enc, A. and Nguyen, H. Submodular maximization with nearly-optimal approximation and adaptivity in nearly- linear time. In Chan, T. M. (ed.), Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, PP. 274-282. SIAM, 2019. doi:
Chakrabarti, A. and Kale, S. Submodular maximization meets streaming: matchings, matroids, and more. Mathe- matical Programming, 154:225-247, 2015.
Charikar, M., Chen, B., Ré, C., and Waingarten, E. Fast algorithms for new relaxation of optimal transport. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4831 4862. PMLR, 2023.
Ene, A. and Nguyen, H. L. Parallel algorithm for non-monotone dr-submodular maximization. In Pro- ceedings of the 37th International Conference on Ma- chine Learning, ICML 2020, 13-18 July 2020, Vir- tual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2902-2911. PMLR, 2020.
Chekuri, C. and Quanrud, K. Parallelizing greedy for submodular set function maximization in matroids and beyond. In Charikar, M. and Cohen, E. (eds.), Pro- ceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoemix, AZ, USA, June 23-26, 2019, pp. 78-89. ACM, 2019a. doi: 10.1 00.1145/3313226.33166
URL http: WtLLhtt:p/ppoeeeeee http///oooednng..ee/ee www...mlr........ mwt.pprss//v19////// ene20a html.
Fahrbach, M., Mirrokni, V. S., and Zadimoghaddam, M. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Chan, T. M. (ed.), Proceedings of the Thirtieth An- nual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6- 9, 2019, pp. 255-273. SIAM, 2019. doi: 10.1137/1. 9781611975482.17. URL https: /dt::///ooiio// org/10. 1137/1 97111117711111999909
Chekuri, C. and Quanrud, K. Submodular function max- imization in parallel via the multilinear relaxation. In Chan, M. (ed.). Proceedings of the Thirtieth An- nual -SAM Symposium on Discrete Algorithms, SODA 2019, San Diego California, USA, January 6- 9, 2019, pp. 303-322. SIAM, 2019b. doi: 10.1137/ 1.9786611954882.2 URL https: http:///co.oo////// 1137/1.9781611999
Chekuri, C., Gupta, S., and Quanrud, K. Streaming algo- rithms for submodular function maximization. In Au- tomata, Languages, and Programming: 42nd Interna- tional Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 42, pp. 318 330. Springer, 2015.
Feldman, M., Karbasi, A., and Kazemi, F. Do less, get more: Streaming submodular maximization with subsampling. Advances in Neural Information Processing Systems, 31, 2018
Feldman, M., Liu, P., Norouzi-Fard, A., Svensson, O., and Zenklusen, R. Streaming submodular maximization un- der matroid constraints. arXiv preprint arXiv:2 2021.
Chen, L., Feldman, M., and Karbasi, A. Unconstrained submodular maximization with constant adaptive com- plexity. In Charikar, M. and Cohen, E. (eds.), Pro- ceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 26, 2019, pp. 102-113. ACM, 2019. doi: 10.1145//31322663333333
Feldman, M., Norouzi-Fard, A., Svensson, O., and Zen- klusen, R. The one-way communication complexity of submodular maximization with applications to streaming and robustness. Journal of the ACM, 70(4):1-52, 2023.
Chen, X. and Peng, B. On the complexity of dynamic sub- modular maximization. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1698, 2022.
Fisher, M. L., Nemhauser, G. L.,, and Wolsey, L. A. An analysis of approximations for maximizing submodular set functions Springer, 1978.
Chen, X., Jayaram, R., Levi, A., and Waingarten, E. New streaming algorithms for high dimensional emd and mst. In Proceedings of the 54th Annual ACM SIGACT Sympo- sium on Theory of Computing, pp. 222-233, 2022.
Huang, C.-C., Thiery, T., and Ward, J. Improved multi-pass streaming algorithms for submodular maximization with matroid constraints. arXiv preprint arXiv:2102.096 2021.
10

---

Lower bound for submodular maximization
Huang, C.-C., Kakimura, N., Mauras, S., and Yoshida, Y. Approximability of monotone submodular function maxi- mization under cardinality and matroid constraints in the streaming model. SIAM Journal on Discrete Mathematics, 36(1):355-382 2022.
Liu, P., Rubinstein, A., Vondrák, J., and Zhao, Cardi- nality constrained submodular maximization for random streams. Advances in Neural Information Processing Systems, 14:6491-6500 2021.
McGregor, A. and Vu, H. T. Better streaming algorithms for the maximum coverage problem. Theory of Compuling Systems, 63:1595-1619, 2019.
Ilys,, A., Park, S. M., Engstrom, L., Leclerc, G., and Madry, A. Datamodels: Predicting predictions from training data. In Proceedings of the 39th International Conference on Machine Learning, 2022.
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., and Krause, A. Lazier than lazy greedy. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Indyk, and Vakilian, A. Tight trade-offss for the maximum k-coverage problem in the general streaming model. In Proceedings of the 38th ACM SIGMOD-SIGACT-SII Symposium on Principles of Database Systems, pp. 200- 217,20 2019.
Monemizadeh, M. Dynamic submodular maximization. Advances in Neural Information Processing Systems, 33: 9806-9817, 2020.
Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., and Karbasi, A. Submodular streaming in all its glory: Tight approximation, minimum memory and low adap- tive complexity. In Chaudhuri, K. and Salakhutdinov, R. (eds.). Proceedings of the 36th International Confer- ence on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3311-3320. PMLR, 2019a. URL http::/p/// ppppeeeecceengssseeeeeeepcc...se malr.press) v97/kazena 9a html.
Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., and Svensson, O. Beyond 1/2- approximation for submodular maximization on massive data streams. In International Conference on Machine Learning, pp. 3829-3838, PMLR, 2018.
Peng, B. Dynamic influence maximization. Advances in Neural Information Processing Systems, 34:10718- 10731, 2021.
Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., and Karbasi, A. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In International Conference Machine Learning, pp. 3311-3320 PMLR, 2019b.
Peng, B. and Rubinstein, A. Fully-dynammictt--ccreeeeett reductions with known deletion order (eg sliding window). In Symposium on Simplicity Algorithmss (SOSA), pp- 261-27 SIAM, 2023.
Shadravan, M. Improved submodular secretary problem with shortlists. arXiv preprint arXiv:2010.01901, 2020.
Kempe, D.,. Kleinberg. J., and Tardos, É. Maximizing the spread of influence through a social network. In Proceed- ings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003.
Kuhnle, A. Quick streaming algorithms for maximization of monotone submodular functions in linear time. In International Conference Artificial Intelligence and Statistics, pp. 1360-1368. PMLR, 2021.
Lattanzi, S., Mitrović, S., Norouzi-Fard, A., Tarnawski, J. M., and Zadimoghaddam, M. Fully dynamic algo- rithm for constrained submodular optimization. Advances in Neural Information Processing Systems, 33:12923- 12933, 2020.
Li, W., Feldman, M., Kazemi, E.,, and Karbasi, A. Submod- ular maximization in clean linear time. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA November 28- December 2022, 2022.

---

Lower bound for submodular maximization
A. Missing Proof from Section 3 first prove Lemma 3.5.
Proof of Lemma 3.5. First, we have
I(11, R1; Zi..... V 0) -[[I;; ....., (m.12 V00)
=III; X1, X [R,I, = 0)
E [III; X1,,, Xm,I, RR, I2 = 12 I. ik, V = 0). is.....
(9)
The first step follows because the public randomness R' independent of ZI..... Zm conditioning on V 0, the second step follows from R' IR, and 7.,..., Zn embedded the I₁-th coordinate. The third step follows from the definition of condition mutual information.
For any fixed .2,..., dg. we bound the RHS of Eq. (9) and our goal is to prove
IC n1 k
I[II X1, X,,,, R, 12, ....... Is ik. V 0)
(10)
To this end, we have
IIII; X12,
RR, i2..... Ia = i V = =0)
XI,, Xm,I, RR I1 = i, = i.,...., Is ig. = 0)
k
++
Σ
I(II: X1, Xm, RI = i...... Is = 12 V = 0)
++1
[[II: (X1,....
immi RRI i2. ..... ... I 4, V =0
n k ++1
T(II; XI...., X,, I2 12, Is = ik, 0).
(11)
n
The first step holds since the choice of I is uniform over [r]] ( Xi....... Xm, for E in])fi,..... & } does depend on (because they are drawn from Di and the transcript II is oblivious of 1, The third step holds due to X1.i..... Xm,i are independent across ............ and Fact 2.3.
i. The second step holds since the distribution of
Finally, for any i2, .., ig. we have
[II; X1
RR,RII = I, ix, ( V = 0) IC
(12)
holds for any & 2 2 due to the definition of information cost (see Eq. (1)).
We have proved Eq. (10) combining Eq. (11)(12), and combining with Eq. (9), we complete the proof.
We next prove Lemma 3.6
Proof of Lemma 3.6. When V 1, note {Xi.i.... ..., tier drawn from the same distribution, hence we have
Ini
ek
Pr|fi E 7
c.
When V O, note (X1. ... heellllMM have the same distribution, hence have
k
Prii E E
71 t:
1s +
Combining the above two cases, the success probability is at least
1
1
k
1
E
(1
+
2
2
n
+
2
4"
Here we use the fact that ls S en/4.
12

---

Lower bound for submodular maximization
Now provide the proof of Theorem 3.2
Proof of Theorem 3.2. By Lemma 3.6, we have that TV I[ 2 2. and therefore,
e²
oo 11|v=1) 2 ( -|v==1)
32
Here, the first step follows from Fact 2.2.
By Lemma 3.4 and the fact that the SDPI constant B(Hu: (1) is at most 1, we have
T(11: Z1, Z IV = 0) 2 ((1/c) ( I[v=) = (2(2/e))
By Lemma 3.5, we have IC M((2n/c). This completes the proof since the communication cost is at least the information cost.
Next prove lower bound for submodular maximization. We first prove Lemma 3.8.
Proof of Lemma 3.8. By Chernoff bound, we have
f(i) Σ
Xe, E [(1/2 (1/2 (1/2+ c)m] Vi
(13)
AE [m]
and
f(i) Σ X1, S 2cm
[
(14)
sE(m]
holds with probability at least - 1/n Hence, have
f(S*) 2 f()) Σ
2 (L/2) e)m.
(15)
FET
The first steps follow from the definition, the last step follows from
[ 2 k/2 and Eq. (13).
On the other hand, for any set S S [n]] with size k; we have
f(S) = f(Snz) f s ( + + m + 2em.
(16)
The first step follows from the definition of f. The second step follows from Eq. (13) Combining Eq. (15)(66,, we can conclude that for any a-approximate solution S,
f(S) f(S+)
|Snz - c)) m k 2em
=a 15c =
2 15c
S Z 2 ck.
(1/2) -c)m
We next prove Theorem 3.7
Proof of Theorem 3.7. Suppose there exists algorithm ALG that makes at most queries and outputs a-approximate solution S for the submodular maximization problem. Consider the following communication protocol: The protocol proceeds in R rounds, where in the r-th round (r E [R), suppose ALG queries set S,,, then the m parties collectively compute the value of f(S,). Since
f(S.) = Σ
Σ
X = Σ
Σ X
VE 1mmm)
TE TE iES,
13

---

Lower bound for submodular maximization
it suffices for the 1-th party compute Eies, Xt. locally and writes it on the blackboard. Given the knowledge of St...., Sr, ((i).. (S,), parties simulate ALG and determine the next query S,-1, and therefore, continue the protocol. Finally, m parties output the solution set ] =
The communication cost each round equals log(n) Ollog² (n))/()))/2) and there is sequence of R queries, there are log (m))/) bits of communication total. Moreover, ALG guarantees the output solution 7 S = 15c-approximate, by Lemma 3.8, we know that [In Z 2 ck. By Theorem 3.2, we must have
R llog (n)/E² (((nn/)) + R 2 27E log (m)) s(a' n/ log log((n))
We next prove Lemma 3.10 and Lemma 3.11.
Proof of Lemma 3.10. This follows directly from Chernoff bound. For any i E I. Xt, B1/2, and therefore
Pr
Σ [E|m]
X1,5
mm/2
2 em
< 2
7,200
and for any E [n]]I, Xt, Be,
Pr
Σ [E|m]
X1,5
2 em/2
2exp(-me²/23 -me2/2)
n0
Proof of Lemma I. For the YES instance, we have
ΣΣ iEZ rE/m)
max Syes(St) 2 (I) 2 min
Xe,s mik
2 (4/2)(1/2- - e)m OPT
8 (S)
where the second step follows from the definition of Syes (see Eq. (2)), the third step follows from Eq. (4) and the last step holds since OPT.
For the NO instance, for any set S of size at most k we have
(S) min
Σ
X
amrk
Σ
Σ X
amk
10
20
SesrI [E(m]
vESn tE/m)
S <amk/10 + k 2em + oonk//2 S OPT
where the first step follows from the definition of fno (see Eq. (3)), and the second step holds due Eq. (5) and |S| S The last step follows from the choice of parameters.
B. Missing Proof from Section 4
We first prove Lemma 4.2.
Proof of Lemma 4.2. We focus the non-trivial case of / 100 log(n)/e2. By Cheroof bound, we have
100 log(n)
exp (-2- 100 log(n)
1
Pr(b, < bittedd= Pr ss [11 ()]]
2) s 50
14

---

Lower bound for submodular maximization
here the second step follows from Chernoff bound and
100m log(n)
(1 + c)t
100 log
| S n [(1 + +e]d]]]
(1 e))
LE2
Similarly,
100 100 log(n)
Pr(b: 2 b(1+0)-11] Pr |sn [11 +)]+++++]]]]
2²
exp (-(1+t) 1 )²
100 log(n)
1
S
(1 c)e
3
n
where the second step follows from Chernoff bound and
100m log(n)
100 log(n))
B[IS + +t]]=
tca
(1 c)m
(1 + c)e
We next prove Lemma 4.4 4.6
Proof of Lemma 4.4. For R., the probability that is there are collisions among [t,] equals
1-(1- 1.11-k kym )
-(1
(t,
1)k:
2 1
ki,
k
100R
(here the last inequality uses (6)).
For E [R+1: 1:
R + R1). consider the random process that 1, 1,2,3, .......... ..... are randomly put into Ar, Ar.ke Let Xy indicates if j falls into the same set as some element j' < i.e.
{
j E An E A,, for some j' < j E [nk,/k] otherwise
X, {
We know that [E[X,] < tp
ky and
E
Σ
Xt
k
(kr logllgg)))))) (n)/E)2
k
loo (n) ne² ky S ckr/4
kip
knn
J.C
where the last step holds since assume &s S c/n/ (n).
By Azuma-Hooe Hoeffing bound, we have
Pr
Σx, X, 2 ckr/2
<exp(-ck,/10 < 1/n².
jshr
This completes the proof.
Proof of Lemma 4.5. For any r E [R+ + Rı], for any subset C [niki//],, we have
log
(n)
E
Σ
Σ
Wj
Wi:
nkir
24
jEA,.
jSk
where the second step follows from the choice of parameters. By Chernoff bound, we have
log" (1)
Pr
Σ
wyle,
Wi
exp
Σ my log log2(n)) (1),
t,
JEA.
I exp(
log2 (n)/6) - 1/n
where the second step follows from wi, S E, jst. 0j S 5,
Σ
Σ joز Wi-
15

---

Lower bound for submodular maximization
Proof Lemma 4.6. We have
E
Σ
w/
h
Wj
nkir
jEAr,
j>k
We use Chernoff bound. If & nk.
Ej>e wy 2 /k/ lk, log(n) then we have
Pr
Σ sEArt
Wi 1,>k
k nkkr
Σ w
log(n)wx
log" (n)k// Krr
2 1 - 2exp
3k Σランı W// ///kk W///kkk Wk
2 exp(p (m))()))) 2 n
Otherwise, If k nk,
Ei>k w/ / /k/k, log(n) wk. then we have
Pr
Σ
Wy
1,>k
k
Σup
wj
log(n)wx log)eo
Vk/k,
nkkr 1>kk
jEA.
2 - exp (-log" (n)k/kk.)
1
log 2 exp(- log (n)/3) 2 n
Now we can finish the proof of Lemma 4.3.
Proof of Lemma 4.3. Fix a value of r, for each subset i E [kkk,//:), we would decompose ((Ar,)) into three parts
f(Ar,)) = Σ w = E
wylsst, +
Σ jEA.,
wyle,ejsk +
Σ
wylz>k.
(17)
JEA,
jEAn
JEA
CASE [R+1: R R1]
We first consider the case that [R+1 + 1: R + Rí] and prove Eq. (8). For the LHS of Eq. (8), let I S [nk,/k] be the
collection of subsets such that contain the top (1 + ke) elements, i.e. [(1 + 2e)k, S UiezAr, By Lemma 4.4, we know that [ 2 (1 + e)ky. We have
b,
min IEI
Σ wy jEAm
min IEI
Σ jEAms
wylsst, +
Σ wyJt,<jsk+ +
Σ
wy Wylssk
jEAn,
JEA.s
W(1+2c)k, +0+
Σ
W/ - v kt/ log(n)wk
nkr j>k
k
Σ Wi
1
((122))k
wy
(18)
nkkr
kr
jsk
The first step follows from the guarantee of QUANTILEESTIMATE (see Lemma 4.2), the third step follows from Lemma 4.6, the last step follows from k S k/ log?(n), (n).
16

---

Lower bound for submodular maximization
Meanwhile, have
[(n])
Wj
k
W
+ k
Σ j2k
(19)
nky
niir
nkr
j=1
j.h
.
k
Combining Eq. (18),19), we have
k
2 hr jsk
Cr b,
s((n)) 2 ((1+2))k
Σ
Wr
nk,
For the RHS of Eq. (8). Let I, S [kk be the top (1 ki subsets of (Elnk. By Lemma 4.4, we know that there exists i, E Iz, such that, either (A,, n [t,] = 0, or j. Ari, n [tn] and j. 2 (1 2e)ky. Therefore, we have
by S
Σ
wj
jEArir
Σ
uyyl
+
Σ
wylenejsk
Σ
wyl
jEAr.
jEA
jEAnd
I (1(1)c))k + log
1og2(n) (n)
k
Σ Wy + log(n))
Wy
t
nk
jSk
j>k
k
1+1 1
S Wk,
+
+
Wj
nkk
lir
j>
jSk
The first step follows from the guarantee of QUANTILEESTIMATE (see Lemma 4.2), the third step follows from Lemma 4.5 and Lemma 4.6, the last step follows from the choice of parameters.
Hence, we have
b
G = b,
f((n))
nk,
$ w/1 -c)kkr + k Σ wy
2
Σ
k
Σ
+
wj
w
nk, jzk
Kr
nky
jsk
jzk
2 Σ Wg--
< ((11-e)kr +
ky
JSk
CASE 2: r S R
We next study the case that r & R. The proof is similar. For the LHHS of Eq. (7), let I S [nkk,/k] be the collection of subsets such that in [k,] C U,,5 By Lemma 4.4, we know that [I] = pky. We have
b, > min
Σ W/ JEAn
min sEi
Σ Wi Wyljst, +
Σ wile +
Σ Wilisk
jEAn,
jEAr,
JEAr.
k nky
2 Wk. + +0+ +
Σ Wi
v k// kip log(n)wr
Wk, + nd
Wj
(20)
R
j>k
17

---

Lower bound for submodular maximization
The first step follows from the guarantee of QUANTILEESSTIMATE (see Lemma 4.2), the third step follows from Lemma 4.5, the last step follows from the choice of parameters. Meanwhile, we have
k: f((n))
= k
Σ j=1
Wj
Σ
Wi
+
Σ
W
S
6
Σ
W
+
k
Σ
Wj
(21)
nk,
nk,
nkk J5k
nkr
R
nkr
j>k
j
j2k
Combining Eq. (20)(11), we have proved
k
2E
b,
nk,
[(m)) 2 Wk.
R
Wr.
jSk
For the RHS of Eq. (7). I, S [nkk,// /k] be the top ky subsets of (Ar, i beln,, /kj. By Lemma 4.4, we know that there exists i, E Iy, such that, either |r O [4]] 0, or jr Ar.r O [4r] and jr 2 ky. Therefore, we have
by S
Σ w/
jeAnir
Σ wyljsh +
Σ wjle,<jsk + Σ waرzsk jEArt
=
jEAntr
jEAnt
I Wkk
+
(n)
Σ
Wi + nk,
k
Σ jzk
Wi + kk/kk
tr
55k
k
26
S Wky
+
Wi
+
Wi
Wkk
R
j>
jzk
The first step follows from the guarantee of QUANTILEESTIMATTE (see Lemma 4.2), the third step follows from Lemma 4.5 and Lemma 4.6, the last step follows from the choice of parameters. Consequently, we have
k
by
f((n))
nk,
k
2E
S Wkk + nki j>k
Σ Wi +
Wj
Σ
Wi
R
Tık
jSk
j2h
2c Σ Wi.
< Wkk +
R
jšk
This completes the proof.
Now we can wrap up the proof Theorem 4.1
Proof of Theorem 4.1. We prove LINEARSUM(f. k) approximates the optimal value within (1 + O(log(n)e) factor with probability least 4/5, and it draws at most (n/k) poly(n, 11 samples.
For the correctness guarantee, we condition on the event of Lemma 4.3, which holds with probability at least 5/6. For < R. by Lemma 4.3, we have
R
R wi
kr ky
+
2
Wi.
(22)
1=1
jSk
18

---

Lower bound for submodular maximization
For j [R+ 1, + R,]. we have
R+
Σ
(kg
100 S
Σ
(kip
1
+llog(n)e Σ Wj
R+1
r=R+1
kR+R; R
Σ
wj + (log((n))
Σ wj
(23)
j=
JSk
where the first step follows from Lemma 4.3 and ky - k S cli-- Similarly, we have
R+R1 Σ
R+ R
(kg
ky 10 2
Σ
(ke k 1 - -2 2log(n)e
Σ
wy
r= R++1
R++1
JSK
kR+R;
Wj O(log(n)c Σ wj
(24)
j=
Finally, for E [R+ Ri 11 R+ Ri
R2], by the guarantee of ESTIMATEEQUNTIIA. (see Lemma 4.2)
n+ B+B
kR+ +
Σ R+
(Kir - 11 =
Σ
wj +)+
Σ w/
(25)
j=kn+ +1
k
Combining Eq. (22)-25), we have
R+ R1 +
Σ
(ki hy
1
Σ
Wjj = O(log(n)c)
3=1
JSk
For the sample complexity, for [R R1), the total number of samples to obtain (b, (br)re|R+a) is most
R+ R.
Σ
100mmk//))log(m//kk== (n/k) poly(log(n)), e
for [R+ Rí +1::1+ R+ R1
R2], the total number of samples obtain ( Ri is at most
R+ + R2
Σ
100n logg)//)) = (n/k) poly(log(n),
r= R+ +1
This completes the proof.
Next we prove Theorem 4.7. We reduce from decision version of the distributed detection problem.
Definition B.1 (Distributed index detection). Let n, m be input parameters, Do. Dj be two Bernoulli distributions with mean No: P1. is the number of parties, who communicate the blackboard model. The input of the 1-th party (t E [m]] vector X, (0, such that
YES Instance: X Do for E [n]][i*) and Xe, Dí:
NO Instance: X1, ~ Do for all i e [n]
The goal is to distinguish between the YES/NO instance.
The communication complexity of distributed index detection is at least (nn/clog()) because there is an ((n/c) lower bound of finding the index i" in the YES instance (taking = 1, e = 1/2 Theorem 3.2), and one could find the index i* by performing binary search using (log(n)) calls to distributed index detection.
19

---

Lower bound for submodular maximization
Proof of Theorem 4.7. Given n, k a, suppose there exists algorithm ALG that makes most I queries and approximates the value of optimal solution. Consider instance of distributed index detection with
10 (n)
a/15,
n'=n/k
22
MAO e,
P1 1
Let XI,..., Xm E 1j" be the input of distributed index detection. Consider the following function f [n] + R
f(S) Σ 5()
and f(i)
Σ
Xx, (mod w²)-
IE
rE(m)
It is easy see that f is additive and monotone. By Lemma 3.10, in the YES instance, by taking S {i i== (mod n')), have
(Se) kf((t) (1/2 e)mk.
(26)
In the NO instance, for any set S of size at most k. we have we
[na(S)= S 2emk..
(27)
Let OPT (1/2 - c)mkk. Consider the following communication protocol: The protocol proceeds R rounds, where in the r-th round (r E [R]), suppose ALG queries set Sy, then the m parties collectively compute the value of f(S,). Since
f(S.) Σ
Σ 1E|m]
X1,i (mod n!)
Σ
X1,5 (mod n²))
rE/m) KES.
it suffices for the t-th party to compute Eies, Xt,i (mod w²) locally and write it on the blackboard. Given the knowledge
of , J(S)) (..) ((,,), ), m parties can simulate ALG and determine the next query Sr+1, and therefore, continue
the protocol. Finally, m parties could distinguish between (1) f(5*) 2 OPT = (1/2 - -))nk and (2)f(5*) S OPT = a11/2- c)mk, and therefore, resolve the distributed index detection task (see Eq. (26).7)).
The communication cost each round equals log(n) O(log" (n))e² bits of communication in total. Hence, have
(n)/e2), 0(log((n)/e2)
and there is sequence of R queries, there
(n)/²²)
Rlog (n)22m))/² 2 en' log(n)
R ann/kloo"( (n).
20


Reviews:
[{"review_id": "wnkP9YTGEO", "reviewer": "Reviewer_2EUZ", "summary": "This paper studies the query complexity for monotone submodular maximization over cardinality constraint. The authors provide a nearly tight query lower bound $\\tilde{\\Omega}(n)$ for obtaining any constant factor approximation for any $k = o(n)$, which improves over the existing bound of $\\Omega(n / k)$. This bounds holds even in the special case of a monotone modular (additive) function. They also show that this lower bound holds even for estimating the optimal value of a monotone submodular function. But for estimating the optimal value of a monotone modular function, they provide an algorithm which achieves a $( 1 \\pm \\epsilon)$-approximation in $\\tilde{O}(n/k)$ queries, and show that this is tight up to polylog factors.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and will incorporate your suggestions into our paper.\n\n> Are there any existing algorithms for estimating the optimal value of a monotone modular function using sublinear queries?\n\nTo the best of our knowledge, no such algorithms currently exist.\n\n> Are there any existing query lower bounds for estimating the optimal value of a monotone submodular function?\n\nYes—the $\\Omega(n/k)$ lower bound established in prior work also applies to the estimation of the optimal value.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I checked all proofs except those of Lemmas 3.5, 4.3, 4.5, 4.6 and Theorems 4.1 and 4.7.\n\n The proofs I checked are correct, but have some typos and steps which are not well explained. In general, more details and intuitive explanations should be provided in the proofs.\n\n- In the proof of Lemma 3.6, $Pr[i_1 \\in \\mathcal{I}]$ should be $Pr[i_1 \\in \\hat{\\mathcal{I}} \\mid V = 1]$ on line 648-649 and $Pr[i_1 \\in \\hat{\\mathcal{I}} \\mid V = 0]$ on line 652-653. I think the latter should be equal to $ |\\mathcal{I} \\cap \\hat{\\mathcal{I}}| / (n- k + 1)$ instead of  $ |\\mathcal{I}| / (n- k + 1)$  (the lemma is still correct though as this is a valid upper bound).  Also, more explanation should be given for why the equalities on both these lines hold.\n\n- In the proof of Theorem 3.2, it's not clear why the first inequality on TV holds. \n\n- In the proof of Lemma 3.10, the second inequality bounds the probability that $\\sum_t X_{t, i}$ deviates from its mean by more than $\\epsilon m/2$, while the Lemma requires bounding the probability of $\\sum_t X_{t, i}$ not being in $(\\epsilon m/2, 2 \\epsilon m)$, so the bound given doesn't actually match that. The lemma is still correct, but the proof needs to corrected.\n\n- In the proof of Lemma 4.4, give more details for why the first two inequalities hold (1st one can be proved by induction, for 2nd one remind the reader of how all these quantities are related..). Moreover why is Azuma-Hoeffding bound needed, this bound holds by Hoeffding inequality.", "experimental_designs_or_analyses": "No experiments included.", "relation_to_broader_scientific_literature": "Obtaining constant factor approximation algorithms for monotone submodular maximization with low query complexity is important for applications where function evaluations are costly, such as neural networks training and influence maximization. Estimating the optimal value is also valuable in some cases, for example to assess dataset quality before proceeding with further analysis or selection, or as a subroutine in some submodular optimization algorithms.\n\nExisting query bounds for constant factor approximation in monotone submodular maximization are $\\Omega(n / k)$ for any $k$ and $\\Omega(n / \\log n)$ for $k = \\Theta(n)$. These bounds rule out sublinear query complexity algorithms for \n$k = \\Theta(1)$ and $k = \\Theta(n)$. This work strengthen these impossibility results, showing that sublinear query complexity is also not possible for any $k \\ll n$. This is particularly relevant as many applications involve $k$ that is not constant but still much smaller than $n$.\n\nThe lower bound  $\\tilde{\\Omega}(n)$ provided here holds for the special case of modular functions too. This is also the case for the existing $\\Omega(n / \\log n)$ bound (see Theorem 4.2 in (Li et al., 2022)) but not for the $\\Omega(n / k)$ bound.\nThe provided lower bound holds also for estimating the optimal value of a monotone submodular function. I am not aware of other existing lower bounds for this.\n\nExisting algorithms for submodular maximization achieve a $(1 - 1/e - \\epsilon)$-approximation, using $O(n \\log(1 /\\epsilon))$ queries with a randomized algorithm, and $O(n/\\epsilon)$ queries with a deterministic algorithm. So the $\\tilde{\\Omega}(n)$ query lower bound in this paper is tight up to log factors.\n\nFrom a technical perspective, prior lower bounds are based on counting arguments. This paper uses novel techniques. Namely the lower bound for finding an approximate solution is derived via a reduction from the query complexity of submodular maximization to the communication complexity of a problem called distributed set detection. The lower bound for estimating the optimal value of a monotone submodular function is obtained by constructing a challenging submodular instance.\n\nThe proposed algorithm for estimating the optimal value of a monotone modular function uses two intuitive subroutines. I am not aware of existing algorithms for this problem that use sublinear queries, so this might be the first.", "essential_references_not_discussed": "The lower bound $\\Omega(n / \\log n)$ for $k = \\Theta(n)$ provided in (Li et al., 2022) holds for the special case of monotone modular function too (see Theorem 4.2 therein).  This should be mentioned.", "other_strengths_and_weaknesses": "Already highlighted above.\n\nOther weaknesses:\nThe paper lacks clarity due to numerous typos and insufficient details in the proofs", "other_comments_or_suggestions": "I recommend moving the discussion in Section 1.1 to the relevant sections, as in provide the high level idea of each result in the same section where you give the formal result, and only keep in this section a very high level description of the main techniques you use.\n\n- Restate theorems/lemmas in the appendix for convenience for the reader.\n\n- In the definition of $f_{yes}$ in Eq. (2), why not simply write this as one sum over $i \\in S$?\n\n- Specify the expected input in Algorithm 3 ($g: [m] \\to \\mathbb{R}^+, t > 0$). Also clarify where do you query $g$ on line 6. \n\n- On line 412, make it clearer that you're discussing here the proof sketch of Lemma 4.3.\n\nTypos:\n- References to lines in Algorithms need to be fixed throughout.\n- In Definition 3.1, $I$ should be $\\mathcal{I}$.\n- In Figure 1, $i$ should be $i_1$?\n- In Algorithm 3, line 1 the inequality should be $>$.\n- LINEARSUM is mispelled a few times on p. 7", "questions_for_authors": "1- Are there any existing algorithm for estimating the optimal value of a monotone modular function using sublinear queries?\n\n2- Are there any existing query lower bounds for estimating the optimal value of a monotone submodular function?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bypq5LgL8q", "reviewer": "Reviewer_9nYb", "summary": "The paper studies the submodular maximization problem under cardinality constraint $k$. They prove a new lower bound on the required query complexity for achieving a constant factor approximation ratio, which improves upon established results when $\\text{polylog}{(n)} \\le k \\le \\frac{n}{\\text{polylog}{(n)}}$. \n\nThey also consider a special case of this problem where the function subject to maximization is also additive. For this problem, they prove the same lower bound and additionally propose an $(1 + \\epsilon)$ approximation algorithm with only $\\tilde{O}(\\frac{n}{k})$ query complexity to find the value of the optimal solution.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback and will incorporate your suggestions into our paper.", "claims_and_evidence": "Fine.", "methods_and_evaluation_criteria": "Fine.", "theoretical_claims": "The high-level ideas seem fine and sound.", "experimental_designs_or_analyses": "This theoretical paper focuses on impossibility results, rendering experiments inapplicable.", "relation_to_broader_scientific_literature": ".", "essential_references_not_discussed": ".", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper uses novel and involved techniques. \n\nThe lower bound results are strong.\n\nWeakness:\n\nThe writing could have had a better flow. \n\nProposing an algorithm for additive functions is not (well-)motivated.\n\nProposing an algorithm with the objective of finding value of optimal subset instead of the subset using sub-linear query time is motivated, but it's not convincing enough.", "other_comments_or_suggestions": "line 118: vallue -> value\n\nline 134 and 135: wrong parenthesis", "questions_for_authors": ".", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QpdDirE1tc", "reviewer": "Reviewer_eFo7", "summary": "They give a lower bound for monotone submodular maximization under cardinality constraint, showing any algorithm achieving a constant approximation factor requires $\\Omega(n)$ query complexity.\n\nThey also provide an algorithm which estimates the maximum value when the function is additive using $\\tilde{O}(n/k)$ query calls.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback. We will incorporate your suggestions into our paper and expand the discussion on the motivation behind our algorithm for additive functions.", "claims_and_evidence": "They have completely proved their claims.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I only checked the proofs in the main part of the paper and not the appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Previously, this problem had a general $\\Omega(n/k)$ lower bound and also a $\\Omega(n)$ lower bound when $k=\\theta(n)$ but they could show that this lower bound holds for any $k$.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The lower bound result is interesting, especially while previous works provided $\\Omega(n)$ lower bound for only large $k$, they show that it always holds and closes the gap between lower bound and upper bounds for this problem. \n\nHowever, their algorithm for the additive case does not seem interesting since in the additive case, selecting $k$ elements with maximum value is enough and while they find a sublinear query complexity for this problem, the query complexity is not really important in this case.", "other_comments_or_suggestions": "I am not sure if the statement in the theorem at the end of the first page matches Theorem 3.9. Instead of 'no O(n)-query complexity,' shouldn't it be 'no o(n)-query complexity'? (using little-o instead of big-O)", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gf3V27hlAr", "reviewer": "Reviewer_34cm", "summary": "The authors present query lower bounds for the problem of maximizing a monotone submodular function under a cardinality constraint.\nSpecifically, they improve the already existing lower bound of $\\Omega(n/k)$ to $\\tilde{\\Omega}(n)$.\nThe bound holds for even estimating the value of the optimal set.\n\nThey also study the special case of additive functions (with non-negative weights).\nThey show that in this case one can find the optimal value with $\\tilde{O}(n/k)$ queries\nand that this is optimal up to polylog factors. However, they prove that finding the optimal set still requires\n$\\Omega(n)$ queries.\n\nThe main technique used in the paper is to reduce submodular maximization to distributed set detection.\n\n## update after rebuttal\nI keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback, we will incorporate your suggestions into our paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have not checked in detail but overall the claims and sketches make sense", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is of interest to the submodular community.", "essential_references_not_discussed": "None that I know of", "other_strengths_and_weaknesses": "The paper studies a natural problem which is previously studied in the literature\nand provides a noticeable improvement. The techniques used are interesting and may be of independent interest.\nFor the special case of additive functions, the results are somewhat surprising.\n\nThe main weakness is that the improvement compared to the previous work is in a somewhat limited setting.\nSpecifically, previous papers essentially already obtain a nearly-linear query lower bound for both very large $k$ and very small $k$.\nThe paper's main contribution therefore is to further study what the role of $k$ would be in such lower bounds. \nWhile I agree that $k$ is a natural parameter, one could argue that the existing lower bounds were already \"nearly-linear\".", "other_comments_or_suggestions": "The paper title in open review does not say \"nearly-linear\" and just says \"linear\". This should be corrected;\nthe lower bounds are not linear!\nAlgorithm 1: I believe this is a reduction from distributed set detection to submodular maximization, not the other way round.", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies the query complexity of monotone submodular maximization with a cardinality constraint and provides improved lower bounds on the query complexity for achieving a constant factor approximation. Prior work has shown a lower bound of  $\Omega(n/k)$ and this work strengthens this result to a nearly-tight $\widetilde{\Omega}(n)$ lower bound. For additive functions, the paper gives a sublinear algorithm for estimating the value of the optimal solution.

Overall, this work is a valuable addition to the submodular maximization literature and it is relevant to the community. The reviewers appreciated the main contribution of this work and support accepting the paper. There was consensus among the reviewers that the main result is strong and the techniques are novel.
Decision: Accept (poster)