Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
Authors: Yixin Chen
Tonmoy Dey
Alan Kuhnle
Venue: NeurIPS 2021 Poster (2021)
Keywords: submodular maximization
parallelizable algorithms
adaptive complexity

Abstract: For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint $k$ on a ground set of size $n$, we provide an algorithm that achieves the state-of-the-art in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of $O(n)$ in expectation, adaptivity of $O(\log(n))$, and approximation ratio of nearly $1-1/e$. The main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as a preprocessing algorithm to improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of $O( \log (n / k) )$ which is smaller than that of any previous algorithm in the literature. The second component is a parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of-the-art algorithm FAST in a comprehensive evaluation with six submodular objective functions.

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
Yixin Chen
Tonmoy Dey Department of Computer Science Florida State University Tallahassee, Florida td td18ddmy. fsu. edu
Department of Computer Science
Florida State University
Tallahassee, Florida
yc19e@my fsu.fuuueeee edu
Alan Kuhnle
Department of Computer Science
Florida State University
Tallahassee, Florida
kuhnle@cs fdu
Abstract
For the problem of maximizing monotone, submodular function with respect a cardinality constraint on a ground set size n, we provide an algorithm that achieves the state-of-the-an in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of O (n) in expec- tation, adaptivity of O (log(n)). and approximation ratio of nearly main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as prepro- cessing algorithm improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of ((log(n/k)) which is smaller than that any previous algorithm the literature. The second component is parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of ofe-----thherrre algorithm FAST in a comprehensive evaluation with six submodular objective functions.
1/e. The
Introduction
The gurdinality-constriil optimization of monotone, submodular function f: 2 R+ defined on subsets of a ground set N of size n, is general problem formulation that is ubiquitous in wide- ranging applications, e.g. video image summarization [30], network monitoring [26], information gathering [23], and MAP Inference for Determinantal Point Processes [20], among many others. The function f 2 > R is submodular iff for S T C N, & T, A (x (T) A (a: SS):: and the function f is monotone if f(S) < f(T) for all S C T. In this paper, we study the following submodular maximization problem (SM)
(S)) subject |S| k where f is monotone, submodular function; SM is an NP-hard problem. There has been extensive effort into the design of approximation algorithms for SM over the course more than 45 years, e.g. [32, 12, 10, 21, 24]. For SM, the optimal ratio has been shown to be 1 1/e 0.63 [32].
(SM)
A (a S*) denotes the marginal gain of x to S: f(S (x}) S(S).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table I: Theoretical comparison to algorithms that achieve nearly optimal adaptivity, ratio, and query complexity: the algorithm of Ene and Nguyen [14], RANDOMIZED- PEDOMMIZED-PRAALLLLLL PARALLEL-GREED (RPG) of Chekuri and Quanrud [11]. SINARY-SEARCH, SEARCH-MAXIMIZATTII MAXIMIZATION (BSM) and SUBSAMPLE- MAXIMIZATION (SM) of Fahrbach et al. [17], FAST of Breuer et al. 19]. The symbol i indicates the result holds with constant probability in expectation; the symbol & indicates the result does not hold on all instances of SM; while no symbol indicates the result holds with probability greater than 1 O(1/n), Observe that our algorithm LS+PGB dominates in least one category when compared head-to-head with any one of the previous algorithms.
Reference
Ratio
Adaptivity
Queries
Ene and Nguyen [14]
1 1/e-
2 log(n)
(mpoly(logn, l/e))
Chekuri and Quanrud [11] (RPG)
1 1- 1/e- - 8
O log(n)
0 1. log(n)) i
Fahrbach et al. [17] (BSM)
1- 1/e-
log (n))
2 log log k)
Fahrbach et al. [17] (SM)
1- 1/ee - 1
27 log (v))
m. log(1/s))
Breuer al. [9] (FAST)
1 1- 1/6 =
2 log(n) log"
log(k)
0
2z log
log(k)
LS+PGB [Theorem 3]
1 1/e E
O ( log (m//))
0
1
As instance sizes have grown very large, there has been much effort into the design of efficient, parallelizable algorithms for SM. Since queries to the objective function can be very expensive, the overall efficiency of an algorithm for SM is typically measured by the query complexity, or number of calls made to the objective function ʃ [2, 9]. The degree of parallelizability can be measured by the adaptive complexity of an algorithm, which is the minimum number of rounds into which the queries to / may organized, such that within each round, the queries are independent and hence may be arbitrariliy parallelized. Observe that the lower the adaptive complexity, the more parallelizable an algorithm is. To obtain a constant approximation factor, a lower bound of (2()) has been shown on the query complexity [24] and a lower bound of (1og(n)) log log(n)) has been shown on the adaptive complexity [3].
Several algorithms have been developed recently that are nearly optimal in terms of query and adaptive complexities [14, 11, 17, 5]: that is, these algorithms achieve O (log n) adaptivity and O (mpolylog(n) query complexity (see Table 1). However, these algorithms use sampling techniques that result in very large constant factors that make these algorithms impractical. This fact discussed in detail in Breuer et al. [9]; as an illustration, to obtain ratio 1 - 1/e 0.1 with 95% confidence, all of these algorithms require more than 10t queries of sets of size k/ log(n) in every adaptive round [9]; moreover, even if these algorithms are run as heuristics using a single sample, other inefficiencies preclude these algorithms of running even on moderately sized instances [9]. For this reason, the FAST algorithm of Breuer et al. [9] has been recently proposed, which uses entirely different sampling technique called adaptive sequencing. Adaptive sequencing was originally introduced in Balkanski et al. [6]. but the original version has quadratic query complexity in the size of the ground set and hence is still impractical on large instances. To speed it up, the FAST algorithm sacrifices theoretical guarantees to yield algorithm that parallelizes well and is faster than all previous algorithms for SM in an extensive experimental evaluation. The theoretical sacrifices of FAST include: the adaptivity of FAST is (2(lo((n) log"(log n)), which is higher than the sfate-of-the and more significantly, the algorithm obtains no approximation ratio for k 850?; since many applications require small choices for k. this limits the practical utility of FAST. A natural question thus: is tt possible to design an algorithm that is both practical and theoretically optimal in terms of adaptivity, ratio, and total queries?
1.1 Contributions
In this paper, we provide three main contributions. The first contribution is the algorithm LINEARSEQ
(LS, Section 2) that achieves with probability 1 1-1, 1/n a constant factor (4 + O(e))=1 in expected linear query complexity and with n) adaptive rounds (Theorem 1). Although the ratio of
se 0.25 is smaller than the optimal 1 - 1/e x 0.63, this algorithm can be used to improve the query
'The approximation ratio 1 - 1/e - 4s of FAST holds with probability 1 - 8 for t 2 0(k,8,k) = 2 log(20 (log( log(k)))/e?(L 5z).
2

---

Table 2: Empirical comparison of our algorithm with FAST, with each algorithm using 75 CPU threads on a broad range of l values and six applications; details provided in Section 4. Parameter settings are favorable FAST, which is run without theoretical guarantees while LS+PGB enforces ratio R 0.53 with high probability, For each application, we report the arithmetic mean of each metric over all instances. Observe that LS outperforms FAST in runtime all applications.
Runtime (s)
Objective Value
Queries
Application
FAST
LS+PGB
FAST
LS+PGB
FAST
LS+PGB
TrafficMonitor
3.7 x 10-1
2.1 x 10
4.7 X 10
5,0 x 10
3.5 x 10a
2.4 x 10
InfluenceMMx
4.4 x 10
2.3 x 10
1.1 X 103
1.1 x 103
7.7 x 10*
4.0 x 10
TwitterSumm
1.6 x 10a
3.5 x 10
3.8 x 10
3.8 x 109
1.5 x 10
6.2 x 10
RevenueMax
3.9 x 102
5,4 x 10"
1.4 x 104
1.4 x 104
7.6 x 10*
2.7 x 10
MaxCover (BA)
3.7 x 102
7.6 x 10
6.0 x 104
6.3 x 10*
5.8 x 10
1.8 x 10s
ImageSumm
1.6 x 10
8.1 X 10
9.1 x 10a
9.1 X 103
1.3 x 10a
4.8 x 10
complexity of many extant algorithms, we decribe in the related work section below. Interestingly, LINEARSEQ can be modified to have adaptivity O (log(n/k) at a small cost to its ratio as discussed in Appendix F. This version of LINEARSEQ is constant-factor algorithm for SM with smaller adaptivity than any previous algorithm in the literature, especially for values of & that are large relative to
Our second contribution is an improved parallelizable thresholding procedure THRESHOLDSEQ (TS, Section 3) for commonly recurring task in submodular optimization: namely, add all elements that have a gain a specified threshold T to the solution. This subproblem arises not only in SM, but also e.g. in submodular cover [17] and non-monotone submodular maximization [4, 18, 15, 25]. Our 1/n in O n) adaptive rounds and expected ((n) query complexity (Theorem 2), while previous procedures for this task only add elements with an expected gain of 7 and use expensive sampling techniques [17]: have ?(log" n) adaptivity [22]; or have (2kk) query complexity [6].
TS accomplishes this task with probability
Finally, we present in Section 3 the parallelized greedy algorithm PARALLEI Y BooST (PGB), which is used in conjunction with LIN and THRESHOLDSEQ yield the final algorithm LS+PGB, which answers the above question affirmatively: LS+PGB obtains nearly the optimal 1 1/c ratio with probability 1 2/n in (log n) adaptive rounds and O(n) queries in expectation; moreover, LS+PGB is faster than FAST in extensive empirical evaluation (see Table 2). In addition, LS+PGB improves theoretically on the previous algorithms in query complexity while obtaining nearly optimal adaptivity (see Table 1).
1.2 Additional Related Work
Adaptive Sequencing. The main inefficiency of the adaptive sequencing method of Balkanski et al. [6] (which causes the quadratic query complexity) is an explicit check that a constant fraction of elements will be filtered from the ground set. In this work, we adopt similar sampling technique to adaptive sequencing, except that we design the algorithm to filter constant fraction of elements with only constant probability. This method allows us to reduce the quadratic query complexity of adaptive sequencing to linear query complexity while only increasing the adaptive complexity by small constant factor. In contrast, FAST of Breuer et al. [9] speeds up adaptive sequencing by increasing the adaptive complexity of the algorithm through adaptive binary search procedures, which, in addition to the increasing the adaptivity by logarithmic factors, place restrictions values for which the ratio can hold. This improved adaptive sequencing technique is the core of our TURESHOLDSEO procedure, which has the additional benefit of being relatively simple to analyze.
the k
Algorithms with Linear Query Complexity. Our LINEARSEQ algorithm also uses the improved adaptive sequencing technique, but in addition this algorithm integrates ideas from the (ddaaadattive linear-time streaming algorithm of Kuhnle [24] to achieve a constant-factor algorithm with low adaptivity in expected linear time. Integration of the improved adaptive sequencing with the ideas of Kuhnle [24] non-trivial, and ultimately this integration enables the theoretical improvement in query complexity over previous algorithms with sublinear adaptivity that obtain constant ratio with
3

---

high probability (see Table 1). In Fahrbach et al. [17], a linear-time procedure SUBSAMPLEPRE: PROCESSING is described; this procedure is the best of our knowledge the only algorithm in the literature that obtains a constant ratio with sublinear adaptive rounds and linear query complexity and hence is comparable to LINEARSEQ. However, AUBSAMPL.PRREE MPLEEPREPOCESSIIN uses entirely different ideas from our LINEARSEQ and has much weaker theoretical guarantees: for input 0 < 8 < 1,
it obtains ratio 2x10 with probability 1 ô in ((log)))8) adaptive rounds and ((n) queries in expectation the small ratio renders SUBRSAMPP.PPREPROCSSSTE
82
impractical; also, its ratio holds only with constant probability. By contrast, with & = 0.1, our LInEARSeQ obtains ratio ss 0.196 1/n in (Ilg())) adaptive rounds and (n) queries in expectation.
with probability
Using LS for Preprocessing: Guesses OPT. Many algorithms for SM, including FAST and all of the algorithms listed in Table I except for SM and our algorithm, use strategy of guessing logarithmically many values of OPT. Our LINEARSEQ algorithm reduces the interval containing OPT from size & to a small constant size in expected linear time. Thus, LINEARSEQ could be used for preprocessing prior to running FAST or one of the other algorithms in Table 1, which would improve their query complexity without compromising their adaptive complexity or ratio; this illustrates the general utility of LINEARSEQ. For example, with this change, the theoretical adaptivity of FAST improves, although it remains worse than LS+PGB: the adaptive complexity of FAST becomes O 1 DUBSAMPPEERREPRCESSIII
22 log(n) log ( log(k)) in contrast to the O ( log (n/e)) of LS+PGB. Although
may be used for the same purpose, its ratio only holds with constant probability which would then limit the probability of success of any following algorithm.
Relationship of THRESHOLDSEQ to Existing Methods. The first procedure in the literature to perform the same task is the BURESHOLLSAMPLING procedure of Fahrbach et al. [17]: however, SHRESHOLDSAMPLIN
only ensures that the expected marginal gain of cach element added is at least T and has large constants in its runtime that make it impractical [9]. In contrast, THRESHOLDSS ensures that added elements contribute gain of at least with high probability and is highly efficient empirically. A second procedure in the literature to perform the same task is the ADAPTIVE- random
SEQUENCING method of Balkanski et al. [6], which similarly to THRESHOLDSED permutations of the ground set; however, ADAPTIVE- -AAPIIVESEQQENNING focuses on explicitly ensuring a constant fraction of elements will be filtered in the next round, which is expensive check: the query complexity of ADAPTIVE-SEQQENCC ensures this property with constant probability, which is sufficient to ensure the adaptivity with the high probability of 1/n in (n)) expected queries. Finally, a third related procedure in the literature is THRESHOLDS sample elements. However, this algorithm has the higher adaptivity of O (log(n) log(k)), in contrast to the O (log(n)) of THRESHOLDSEO.
is Okk)). In contrast, our THRESHOLDSEE algorithm
of Kazemi et al. [22], which also uses random permutations to
MapReduce Framework. Another line of work studying parallelizable algorithms for SM has focused the MapReduce framework [13] in a distributed setting, e.g. [7, 8, 16, 28). These algorithms divide the dataset over a large number of machines and are intended for a setting in which the data does not fit single machine. None of these algorithms has sublinear adaptivity and hence all have potentially large numbers of sequential function queries on each machine. In this work, our empirical evaluation is on a single machine with a large number of CPU cores; we do not evaluate our algorithms in a distributed setting.
The constant-factor algorithm LINEARSEQ is described and analyzed in Section 2; the details of the analysis are presented in Appendix C. The variant of LINEARSEQ with lower adaptivity is described in Appendix F. The algorithms ThReSHOLDSEQ and PARALLEL GRLLEYY BOOST are discussed at a high level in Section 3, with detailed descriptions of these algorithms and theoretical analysis presented in Appendices D and E. Our empirical evaluation is summarized in Section 4 with more results and discussion in Appendix H.
Organization.
2 A Parallelizable Algorithm with Linear Query Complexity: LINEARSEQ
In this section, we describe the algorithm LInEARSEo for SM (Alg. 1) that obtains ratio (4+)(=)) in O (2) log(n)) adaptive rounds and expected O (5) queries. If c S 0.21, the ratio of LINEARSEQ is lower-bounded by (4 + 16s)- 2 0. 0.135, which shows that relatively large constant ratio is obtained even at large values of E. An initial run of this algorithm is required for our main algorithm LS+PGB.

---

Algorithm The algorithm that obtains ratio (4 (c)) O (log(n)/e") adaptive rounds and expected O (n/=²) queries.
1: procedure LIN (..oo. k,
2: Input: evaluation oracle f :2N RR+, constraint k, enror
3: a a= arg max f((u))
4: Initialize A +- {a). V + N,
+
5: for j to do
6: Update V <- fo LVEV: A (a A) 2 f(4)k)) and filter out the rest
7: if V = 0 then break
8:
V
" <- r-rnddom-pemminnn conddom-permuuation(>)
9:
+ {[(1+))'] 1:1 (1+ +)" s k. NJ
Uilk + uek] kk usk] S M
10:
B[A = false, for A; E
11:
for X A in parallel do
12:
UxL Tx, + ful, 22 :x < TrATa. A (Tx, AAT /TT 1 2 - =)ʃ(A Tx. x; )/k then B[A:] true
TA-- + {ei, U2.
13:
14:
X + max E E B[A = false and ((A: I k and B[1] to B[A:-1] are all true) or
(A:
> k and 3m > s.t. I Tx N k and [3(mm) to B[A are all true))]
15:
A 4 UT-
16:
if [V > 0 then return failure
return A' + last & elements added A 17:
Description of LS. The work of LS is done within iterations of sequential outer for loop (Line 5) this loop iterates at most O (log(n)) times, and each iteration requires two adaptive rounds; thus, the adaptive complexity of the algorithm A, which is initially empty. Within each iteration, there are four high-level steps: 1) filter elements from V that have gain less than fAA)/ (Line 6); 2) randomly permute V (Line 8); 3) compute in parallel the marginal gain of adding blocks of the sequence of remaining elements in V to A (for loop on Line 11); 4) select a prefix of the sequence V = -Vv,, v2,..., )lll) to add to (Line 14). The selection of the prefix to add is carefully chosen to approximately satisfy, on average, Condition I for elements added; and also to ensure that, with constant probability, a constant fraction of elements of V are filtered the next iteration.
(log(n)). Each iteration adds more elements the set
The following theorem states the theoretical results for LINFARSFO. The remainder of this section proves this theorem, with intuition and discussion of the proof. The omitted proofs for all lemmata are provided in Appendix C.
Theorem 1. Let (f.k) be an instance of SM. For any constant < 1/2, the algorithm
LINEARSEQ has adaptive complexity O (log(n)/e²) and outputs A' S N with A'| S such that the following properties hold: 1) The algorithm succeeds with probability least 1 1/n. 2) There are O ((1/(ek) + 1)m/6²) oracle queries in expectation. 3) If the algorithm succeeds, 1(2-8) 4+ (1-))11-2 f(A) 2 f(O), where O is an optimal solution to the instance (f, k)-
Overview. The goal of this section is to produce constant factor, parallelizable algorithm with linear query complexity. As a starting point, consider an algorithm' that takes one pass through the ground set, adding each element candidate set A iff
A Ac f(A)/k.
(1)
Condition 1 ensures two properties: 1) the last i: elements in A contain constant fraction of the value f(A); and 2) (A) is within a constant fraction of OPT. By these two properties, the last elements of A are constant factor approximation to SM with exactly one query of the objective function per element of the ground set. For completeness, we give a pseudocode (Alg. 3) and proof in Appendix B. However, each query depends all of the previous ones and thus there are n adaptive rounds. Therefore, the challenge is to approximately simulate Alg. 3 in a lowly adaptive (highly parallelizable) manner, which what LINEARSEQ accomplishes.
This algorithm is simplitied version of the streaming algorithm of Kuhnle [24].
5

---

c
(8)
AWA'
A
= A
(b)
T
Figure 1: This figure depicts the way elements are added to A, with A, denoting the value of A after iteration of the outer for loop; the prefix added at iteration i is denoted by Ti The orange lines mark the blocks comprising each prefix. Also, the set A' of the last & elements added to A is shown. Parts (a) and (b) depict two separate cases in the proof of Claim 1.
2.1 Approximately Satisfying Condition 1
Discarding Elements. In one adaptive round during each iteration j of the outer for loop, all elements with gain to A of less than f (A) /k are discarded from V (Line 6). Since the size of A increases the algorithm runs, by submodularity, the gain of these elements can only decrease and hence these elements cannot satisfy Condition and can be safely discarded from consideration. The process of filtering thereby ensures the following lemma at termination.
Lemma 1. At successful termination of LINEARSEO, f(O) s (A)) where O C is an optimal solution of size k.
Addition of Elements. Next, we describe the details of how elements are added to the set A. The random permutation of remaining elements on Line constructs sequence (v1, U2, .... flll) such that each element is uniformly randomly sampled from the remaining elements. By testing the marginal gains along the sequence parallel, is possible determine good prefix of the sequence (u;) to add to A to ensure the following: 1) Condition I is approximately satisfied; and 2) We will discard constant fraction of V in the next iteration with constant probability. Condition is important for the approximation ratio and discarding constant fraction of V is important for the adaptivity and query complexity. Below, we discuss how to choose the prefix such that both are achieved. To speed up the algorithm, we do not test the marginal gain at each point in the sequence (v;). but rather test blocks of elements at once as determined by the index set defined in the pseudocode.
Prefix Selection. Say block is bad if this block does not satisfy the condition checked on Line 13 (which is an approximate, average form of Condition 1); otherwise, the block is good. At the end of an iteration, we select the largest block index X", where this block is bad and the previous consecutive blocks which together have at least i elements are all good; or this block is bad and all the previous blocks are good blocks. Then, we add the prefix Tx- = (v); 12, Ux- into A. Now, the relevance of Condition for the approximation ratio is that it implies f f(A) > 2 \ A'), where A' are the last elements added to A. Lemma shows that the conditions required on the marginal gains of blocks added imply an approximate form of this fact is satisfied by LINEARSEQ. Indeed, the proof Lemma 2 informs the choice of blocks evaluated and the computation of X*
Lemma 2. Suppose LINEARSEQ terminates successfully. Then f(A)
2(1-c+t² S(A)A))
1tc
Proof. If [A]
<. the lemma is immediate, so assume |A k. For iteration j. let T3,;; denote the set added to A during iteration j: and let T3,35 = 0 the algorithm terminates before iteration Let A, denote the value of A after iteration j. Define
max(e N A' C (1,z)1 Then, [Te.g]] > O; and for any j > c, [T,agl < k. It holds that (Uf TxA;) c A' c (Txx)))))))) Figure shows how A is composed of these sets TjAy and how each set is composed of blocks. The following claim is proven in Appendix C.3.
Claim 1. It holds that A (Ta.: (AAA) 2 (1 E) max(0, Tax; DA'l 2ck) f(A)AA)/K. For
j > e, it holds that (TAxz A 2 1 (T,gg A(A\AA)K..

---

From Claim 1,
Σ A (Texg A4-1) (1 - (1-E)(1 -2c) =(AAA)) (2)
f(A)- A (Tex: [A(A)+
1+E
jmot1
where Inequality 2 is proven in Appendix C.4.
In the remainder of this subsection, we will show that (Be)-fraction of V is discarded at each iteration j of the outer for loop with probability at least 1/2, where / is a constant in terms of e as defined on Line 4 in the pseudocode. The remainder of the proof' in this section are implicitly conditioned on the behavior of the algorithm prior to iteration j. The next lemma describes the behavior of the number of elements that will be filtered iteration j 1. Observe that the set S; defined in the next lemma is the set of elements that would be filtered at the next iteration if prefix TV added to A.
Lemma 3. Let S; E (x < f(AUT)/Kk) It holds that |Sol = 0, |5|v) [V and |SA| < |/
By Lemma 3, we know the number of elements in S; increases from 0 to [V| with i. Therefore, there exists a such that / = min E N |S| 2 Be|V]). If X 2 I, SSx1 2 Ve and we will successfully filter out more than (fr)-fraction of V at the next iteration. In this case, say that the iteration j succeeds. Otherwise. if X* < t. the iteration may fail. The remainder of the proof bounds the probability that X < which is an upper bound on the probability that iteration j fails. Let X = max À E A X < t}, and let X; = max((XX E A EAEA,NSASA, [Tx| 2 k} U (1)). X < 4, there must be at least one index À between X; and X such that the block Tý is bad. The next lemma bounds the probability that any block TV with
X₁, bad.
Lemma 4. Let t = min(i E N: : [ 2 Be[V[]; A = max(A E A: A (Y:) be sequence of independent and identically distributed Bernoulli trials, where the success probability Be. Then for any X < d, Pr (B[A) = false) < Pr |M
Y Y s|Tx).
Finally, we bound the probability that an iteration j of the outer for loop fails. Let Bi = E A k and A < A1). B₂ = {> A A [X, Aell [1/e]]. Then
Pr (iteration j fails) Pr (E) E B1 U B2 with B[A] false) S 1/2,
(3)
where the proof of Inequality 3 is Appendix C.7.
2.2 Proof of Theorem
From Section 2.1, the probability at any iteration of the outer for loop of successful filtering of an (Be)-fraction of V is at least 1/2. We can model the success of the iterations as sequence of dependent Bernoulli random variables, with success probability that depends on the results of previous trials but is always at least 1/2.
Success Probability of LINEARSEQ. If there are least m = [s [1/n)] successful iterations, the algorithm LINEARSEO will succeed. The number of successful iterations X. up to and including the b-th iteration is sum of dependent Bernoulli random variables. With some work (Lemma in Appendix A), the Chernoff bounds can be applied to ensure the algorithm succeeds with probability least 1 - n, as shown Appendix C.2.
Adaptivity and Query Complexity. Oracle queries are made on Lines 6 and 13 of LINEARSEQ.
The filtering on Line 6 is in one adaptive round, and the inner for loop is also in one adaptive
round. Thus, the adaptivity is proportional to the number of iterations of the outer for loop, O (f) O (log(n)/e²). For the query complexity, let Y; be the number of iterations between the (i - 1)-th
and i-th successful iterations of the outer for loop. By Lemma in Appendix A, E .Y]] < 2. From here, we show in Appendix C.8 that there are at most O (n/=²) queries expectation.
Approximation Ratio. Suppose LINEARSEQ terminates successfully. We have the approximation ratio follows:
(6) f(A') 2 f(A) f(AAA)) 2 f(A) 2(1 8 52)
1+
f(A) (c)
1
f(0),
4(2 c)
4 +
[I-E]
7

---

where Inequality (a) is from submodularity of f. Inequality (b) is from Lemma 2, and Inequality (c) from Lemma
3 Improving to Nearly the Optimal Ratio
In this section, we describe how to obtain the nearly optimal ratio in nearly optimal query and adaptive complexities (Section 3.2). First, in Section 3.1, we describe THRESHOLDSEO. a parallelizable procedure to add all elements with gain above a constant threshold to the solution. In Section 3.2, we describe PARALLEL Y BOOST and finally the main algorithm LS+PGB. Because of space constraints, the algorithms are described in the main text at high level only, with detailed descriptions and proofs deferred to Appendices and E.
3.1 The THRESHOLDSEQ Procedure
In this section, we discuss the algorithm THRESHOLDSEO, which adds all elements with gain above an imput threshold up accuracy E (log 1z) adaptive rounds and ((n) queries in expectation. Pseudocode is given in Alg. 4 in Appendix D.
Overview. The goal of this algorithm is, given input threshold and size constraint k to produce a set of size at most A such that the average gain of elements added is at least т. As discussed in Section this task is an important subroutine of many algorithms for submodular optimization (including our final algorithm), although by itself it does not produce any approximation ratio for SM. The overall strategy of our parallelizable algorithm THRESHOLDSEE analagous that of LINEARSEO, although THRESHOLDSEQ is considerably simpler to analyze. The following theorem summarizes the theoretical guarantees of THRESHOLDSEQ and the proofs are in Appendix D.
Theorem 2. Suppose THRESHOLDSEO is run with inpul (f,k, e, 6, r). Then, the algorithm has
adaptive complexity O(log(n/8)/e and outputs A C N with |A] I such that the following properties hold: 1) The algorithum succeeds with probability least
8/n. 2) There are O(n/E)
oracle queries in expectation. 3) It holds that f(A)/IA| Z (1 - E) / (1 + E). 4) If |A| then A (ar A) T for all N.
3.2 The GARELLEL Procedure and the Main Algorithm
In this section, we describe the greedy algorithm PARALLEL- Algorithm 2 The PARALLEL BooST procedure.
GREEDY (PGB, Alg. 2) that uses multiple calls to THRESH- OLDSEQ with descending thresh- olds. Next, our state-of-the-e art al- gorithm LS+PGB is specified.
Input:
evaluation oracle f :2V + R. constraint k.
constant o, value I such that T s f(O) T/o, accuracy
parameter &
Initialize T/(ak), ( + 1), A <
3:
while 7 (3/ do
T 7(1 a)
Description of PARALLEL-
5:
5 4 TIIRESSOOLDSSOO/A.... 1,/ 0,e/3/3,777
GREEDYBOOST. This procedure takes as input the results from running an a-approximation algo- rithm on the instance (J, k) of SM; thus, PARALLE.GRREEDYBOOOS is not meant to be used as standalone algorithm. Namely, of a-approximation algorithm for SM; this solution value I' is then boosted to ensure the ratio 1 1-1/e- - e on the instance. The values of and a are used to produce an initial threshold value r for THRESHOLDSEo. Then, the threshold value is iteratively decreased by a factor of (1 - =) and the call to THRESHOLDSEQ is iteratively repeated to build up solution, until a minimum value for the threshold of T/(3k) is reached. Therefore, THRESHOLDSS DSEQ is called at most O (log(1/a))/ times. We remark that a is not required to be a constant approximation ratio.
< AUS
7:
if |A| = k then
return A
9: return
takes as input I,, the solution value
Theorem 3. Let (f, k) be an instance of SM. Suppose an a- approximation algorithm for SM is used to obtain I, where the approximation ratio a holds with probability - Pa. For any constant >> 0,
the algorithm PARALLELGREES BOOST has adaptive complexity
log e
log
n logg(
8

---

and outputs A E N with |A| S k such that the following properties hold: 1) The algorithm succeeds 1/n n Pa- 2) If the algorithm succeeds, there are O log (a-1) ( / oracle queries in expectation. 3) If the algorithm succeeds, {(A) 2 (1 1/e - =)f( where O is
with probability at least 1 -
an optimal solution the instance (f. k)).
Proof. Success Probability. For the while loop in Line 3-8, there are no more than [og (a /3] iterations. THRESHOLDSEO completes successfully at every iteration, Algorithm 2 also succeeds. The probability that this occurs is lower bounded in Appendix E.1.1. For the remainder of the proof of Theorem 3, we assume that every call to THRESHOLLSEE succeeds.
Adaptive and Query Complexity. There are at most (a/3)] iterations of the while loop. Since log(æ) I x 1, [log)_aa/33]] = [logla/3) log(1-e) 1. and & < 1/e, it holds that [logi-c(a/3) < (o And for each iteration, queries to the oracle happen only on Line 5, the call to THRESSOOLDSEO. Since the adaptive and query complexity of THRESHOLD- SEQ is O (log(n/6)/8 and O (n/e), the adaptive and query complexities for Algorithm 2 are log n Iog(a
,0 loga-1 22
(org-"n) respectively.
log
Approximation Ratio. Let A, be the set A we get after Line 6, and let S₃ be the set returned by THRESHOLDSEQ in iteration j of the while loop. Let l be the number of iterations of the while loop.
First, in the case that |A| < k at termination, THRESHOLDDEE returns O S | < k |Ac-1 at the last iteration. From Theorem 2, for any o E 0, A (o A) < T T/(3)) By submodularity and monotonicity, (O) f(A - f(O A) - f(A) - Σ A (ol A) S EoEors T/(3)) S /00/3, and the ratio holds.
Second, consider the case that |A| k. Suppose in iteration j + 1, THRESHOLDSEQ returns a nonempty set S,+1. Then, in the previous iteration j. THRESHOLDSEQ returns set Sy that < [Sy1 < k |A/-1 From Theorem
(1-E/3) -3) (1
f(0) - f(A+1) &
(1+e/3)k
-
(4)
The above inequality also holds when Aj+1 = Aj. Therefore, it holds that
(1-e/3)(-c) 1+c/3
S(0) f(1) S
f(O) S (1/e (11/++))11) s))(O)
(5)
The detailed proof of Inequality 4 and 5 can be found in Appendix E.1.2.
Main Algorithm: LS+ To obtain the main algorithm of this paper (and its nearly optimal theoretical guarantees), we use GREEDY BooST with the solution value I and ratio given by LINEARSEO. Because this choice requires an initial run of LINEARSEQ. we denote this algorithm by LS+PGB. Thus, LS+PGB integrates LINEARSEQ and BARALLELGREED GREEDyBoOST BoOST to get nearly the optimal 1 - 1/e ratio with query complexity of O (n) and adaptivity of O (log(n)).
4 Empirical Evaluation
In this section, we demonstrate that the empirical performance of LS+PGB outperforms that of FAST for the metrics of total time, total queries, adaptive rounds, and objective value across six applications of SM: maximum cover on random graphs (MaxCover), twitter feed summarization (TweetSumm), image summarization (ImageSumm), influence maximization (Influence), revenue maximization (RevMax), and Traffic Speeding Sensor placement (Traffic). See Appendix H.2 for the definition of the objectives. The sizes of the ground sets range from 1885 to 100000.
Implementation and Environment. We evaluate the same implementation of FAST used in Breuer et al. [9]. Our implementation of LS+PGB is parallelized using the Message Passing Interface (MPI) within the same Python codebase as FAST (see the Supplementary Material for source code). Practical optimizations to LINEARSEQ are made, which do not compromise the theoretical guarantees, which are discussed in Appendix G. The hardware of the system consists of 40 Intel(R) Xeon(R) Gold 5218R CPU @ 2. 10GHz cores (with 80 threads available), of which up to 75 threads are

---

ImageSumm
RevenueMax
17432)
ImageSurm (n=10000)
RevenueMax
Objectivve Grreedy
1.0
Objective Gready
1.0
107
Haht
Qveriea /
Quarfes I
10
0.8
0.8
6 10
0.6
FAST
0.6
FAST
4x 10
10
30"
10
kin
Kin
kin
kim
(a)
(b)
(c)
(d)
ImageSumm (n= 10000)
RevenueMax [n= 17432)
ImageSurim (n= 10000)
RevenueMax (n=17432)
Adaptive Roundss
rear
Adsyptive Rounds
rest
Time Takenn (s)
Thme Takenn (s)
10*
1AB1
60
100
10.
ao²
t0
20*
20
10*
10
10
10
10
30
10
10
10"2 kin
10a2
10
30"
10a
k/n
kin
(c)
g
(h)
Figure 2: Evaluation of adaptive algorithms on ImageSumm and RevenueMax in terms of objective value normalized by the standard greedy value (Figure 2(a) 2(b)), total number of queries (Figure 2(c) 2(d)), total adaptive rounds (Figure 2(e) 2(D) and the time required by each algorithm (Figure 2(g) 2(h))
made available to the algorithms for the experiments. On each instance, the algorithms are repeated independently for five repetitions, and the mean and standard deviation of the objective value, total queries, adaptive rounds and parallel (wall clock) runtime to the submodular function is plotted.
Parameters. The parameters 5 of FAST are set to enforce the nominal ratio of 1-11e-000 0.1 ~ 0.53
with probability 0.95; these are the same parameter settings for FAST as in the Breuer al. [9] evaluation. The parameter of PGB is set enforce the same ratio with probability 1 1-2/n, With these parameters, FAST ensures its ratio only k: 2 (e, 8, k) = 2 log(28 log( log( 5e) 2 7103. Since & < 7103 on many of our instances, FAST is evaluated in these instances as theoretically motivated hcuristic. In contrast, the ratio of LS+PGB holds on all instances evaluated. We exponentially increasing & values from n/ 1000 to n 10 for each application to explore the behavior of each algorithm across broad range instance sizes.
Overview of Results. Figure 2 illustrates the comparison with FAST across the ImageSumm and RevenueMax application; results on other applications are shown Appendix H. Runtime: LS+PGB is faster than FAST by more than 1% on 80% of instances evaluated; and is faster by an order magnitude on 14% instances. Objective value: LS+PGB achieves higher objective by more than 1% on 50% of instances, whereas FAST achieves higher objective by more than 1% on 8% of instances. Adaptive rounds: LS+PGB achieves more than 1% fewer adaptive rounds on 75% of instances, while FAST achieves more than 1% fewer adaptive rounds 22% of instances. Total queries: LS+PGB uses more than 1% fewer queries on 84% of scenarios with FAST using more than 1% fewer queries 9% of scenarios. In summary, LS+PGB frequently gives substantial improvement in objective value, queries, adaptive rounds, and parallel runtime. Comparison of the arithmetic means of the metrics over all instances is given in Table 2. Finally, FAST and LS+PGB show very similar linear speedup with the number of processors employed: as shown in Fig. 7.
Concluding Remarks
In this work, we have introduced the algorithm LS+PGB, which is highly parallelizable and achieves state-of-the-ar empirical performance over any previous algorithm for SM; also, LS+PGB is nearly optimal theoretically in terms of query complexity, adaptivity, and approximation ratio. An integral component of LS+PGB is our preprocessing algorithm LINEARSEO, which reduces the interval containing OPT to a small constant size in expected linear time and low adaptivity, which may be independently useful. Another component of L.S PGB is the THRESHOLDDSOO procedure, which adds all elements with gain above a threshold algorithms in the literature for the same task.
parallelizable manner and improves existing
10

---

Acknowledgements
The work of Yixin Chen, Tonmoy Dey, and Alan Kuhnle was partially supported by Florida State University. The authors have received no third-party funding in direct support of this work. The authors have no additional revenues from other sources related to this work.
References
[1] CalTrans. Pems:
California performance measuring system. http://pems. dot. ca. ga.gov/.
[Online; accessed 1-May-2018j.
[2] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
[3] Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In ACM SIGACT Symposium on Theory of Computing (STOC), 2018.
[4] Eric Balkanski, Adam Breuer, and Yaron Singer. Non-monotone submodular maximization in exponentially fewer iterations. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 2359-2370 2018.
[5] Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An Exponential Speedup in Parallel Rumning Time for Submodular Maximization without Loss in Approximation. In ACM-SIAM Symposium Discrete Algorithms (SODA), 2019.
[6] Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proceedings of the Annual ACM Symposium on Theory of Computing, pages 66-77, nov 2019.
[7] Rafael Barbosa, Alina Ene, Huy Le Nguyen, and Justin Ward, The Power of Randomization: Distributed Submodular Maximization Massive Datasets. In International Conference Machine Learning (ICML), 2015.
[8] Rafael Da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. A New Framework for Distributed Submodular Maximization. IEEE Symposium on Foundations of Computer Science (FOCS), 2016.
[9] Adam Breuer, Eric Balkanski, and Yaron Singer. The FAST Algorithm for Submodular Maximization. In International Conference on Machine Learning (ICML), 2019.
[10] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing Submodular Set Function subject to a Matroid Constraint. In Integer Programming and Combinatorial Optimization (IPCO), pages 182-196, 2007.
[11] Chandra Chekuri and Kent Quanrud. Submodular function maximization parallel via the multilinear relaxation. In Proceedings of the Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 303-322, jul 2019.
[12) Michele Conforti and Gérard Cormuéjols. Submodular set functions, matroids and the greedy algorithm:
Tight worst-case bounds and some generalizations of the Cado-Edmonds theorem. Discrete Applied Mathematics, 7(3):251-2 1984.
[13] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, 51(1):107-113, 2008.
[14] Alina Ene and Huy L Nguyen. Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
[15] Alina Ene and Huy Nguyên. Parallel Algorithm for Non-Monotone OR-Submodular Maxi- mization. In International Conference on Machine Learning (ICML), 2020.

---

[16] Alessandro Epasto. Vahab Mirrokni, and Morteza Zadimoghaddam. Bieriteria Distributed Submodular Maximization in a Few Rounds. In Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017.
[17] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam, Submodular Maximization with Nearly Optimal Approximation. Adaptivity, and Query Complexity. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 255-273, 2019.
[18] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Non- mon-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. In International Conference on Machine Learning (ICML), 2019.
[19] Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning, pages 1833-1842. PMLR, 2019.
[20] Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-Optimal MAP Inference for Deter- minantal Point Processes. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
[21] Thibaut Horel and Yaron Singer. Maximization of Approximately Submodular Functions. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
[22] Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddamm, Silvio Lattanzi, and Amin Karbasi. Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity. In International Conference on Machine Learning (ICML), 2019.
[23] Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular functions. AAAI Conference on Artificial Intelligence. 2007.
[24] Alan Kuhnle. Quick Streaming Algorithms for Maximization of Monotone Submodular Func- tions in Linear Time. In Artificial Intelligence and Statistics (AISTATS), 2021.
[25] Alan Kuhnle. Nearly Linear-Time Parallelizable Algorithms for Non-Monoton Submodular Maximization. In AAAI Conference on Artificial Intelligence, 2021.
[26] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Natalic Glance. Cost-effective Outbreak Detection in Networks. In ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), 2007.
Faloutsos, Jeanne VanBriesen, and
[27] Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pages
Springer, 1978.
[28] Vahab Mirrokni and Morteza Zadimoghaddam. Randomized Composable Core-Sets for Dis- tributed Submodular Maximization. In ACM Symposium on Theory of Computing (STOC). 2015.
[29] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning, pages 1358-1367. PMLR, 2016.
[30] Baharan Mirzasoleiman, Stefanic Jegelka, and Andreas Krause. Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly. In AAAI Conference on Artificial Intelligence, 2018.
[31] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and proba- bilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
[32] G I. Nemhauser and I. A Wolsey. Best Algorithms for Approximating the Maximum of a Submodular Set Function. Mathematics of Operations Research, 3(3):177-188. 1978.
[33] Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[34] Abraham Wald. Some generalizations of the theory of cumulative sums of random variables. The Annals of Mathematical Statistics, 16(3):287-293, 1945.
12


Reviews:
[{"review_id": "xvCIQQwCMN2", "reviewer": "Reviewer_1sHC", "summary": "In recent years there has been a theoretical breakthrough in low adaptivity O(log(n)) parallel algorithms for submodular maximization, but these algorithms are very slow in practice. Very recently, Breuer et al. proposed an algorithm, FAST, that trades off a small factor in asymptotic adaptive complexity to obtain the practically fastest algorithm. Building on this line of research, the authors propose a new algorithm with slightly better practical performance absent the tradeoff in asymptotic adaptive complexity. The authors demonstrate the practical performance advantage by benchmarking their approach against the FAST algorithm on numerous experiments. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "Overall, I agree with the authors that it is desirable to design a practically fast algorithm with O(log(n)) adaptivity. Some of the ideas used to obtain this, while based significantly on recent work, are also nontrivial. For example, the LinearSeq subroutine and also the ThresholdSeq subroutine to identify high value elements are of general interest and might be used to accelerate other algorithms. In general, the ideas here refine and expand upon the sequencing techniques introduced in Balkanski et al., 2020 and Breuer et al., 2020. The paper and proofs are clearly written.\n\nHowever, the magnitude of the contribution of the paper hinges on the claim that the proposed algorithm is empirically faster than the FAST algorithm. The reported runtimes and objective values suggest that the algorithm is slightly faster for most (but not all) experiments and parameter combinations. This may be thought of as incremental progress, and to contextualize the magnitude of the obtained speedups, I would note that it is possible to achieve similar or greater speedups for the FAST algorithm by considering various factors such as e.g. better parallel load balancing, etc. (though these might also apply to the authors' algorithm). I will nonetheless acknowledge that if the authors' claims are correct, then their algorithm is currently the fastest for generic submodular maximization (even if by a small margin), which is still useful/interesting. Also, I note that the reported query counts do appear to significantly improve on FAST's queries for most experiments (Appendix Fig. H.3). This means that the performance advantage may actually be better on different (larger?) hardware.\n\nBecause the magnitude of the contribution hinges on the experimental results, implementations and experimental setup are critical. \n\nIn this respect, I appreciate that the majority of the applications replicate Breuer et al (the FAST algorithm), and also that the authors have also added the Image Summary and Information Monitoring objectives to add some diversity. This gives a nice balance of 6 established benchmarks (from the FAST paper) and two additional ones for diversity. The plots are clear; the values of k are chosen and plotted in a theoretically reasonable way (as values of k/n), and the authors show averages over multiple runs + error bars. \n\nI also dug around the codebase (which is nice to see in the submission). It appears to extend the FAST codebase, and it uses MPI functions, helper functions, etc. from the former. I also develop in MPI, and I appreciate that this is nontrivial. It is also advantageous here because it gives confidence that the authors' comparison to FAST uses a fair/coonosistent comparison of codes, subroutines, timings, etc. It is also nice to see papers adopting and expands a fast parallel codebase & benchmarks that can be used by other researchers in the future.\n\nI would note that because the hardware appears to be a server machine instead of AWS/GoogleCloud/Azure, the reported timings are not strictly replicable (absent buying an identical server machine). As a heuristic check, I compared the benchmark runtimes the authors obtain using FAST against those reported in the original FAST paper, and they do appear to be reasonably consistent. (Note: Please consider adding a \\ref to Appendix H in the text of the paper where you discuss threads/processors.)\n\nOne oddity in the experiments is that the Parameters paragraph (line 328) and also Appendix H state \"these are the same parameter settings for FAST as in the Breuer et al. \", but Breuer et al. (p.6) reports using probability 0.95, not 0.975 as reported here. 0.975 is a fine value to use for benchmarking, but consider revising these paragraphs in the paper and the Appendix (as they also use the probability parameter to compute the values of k under which the Breuer paper's guarantees are heuristic only.)\n\nI will consider updating my review based on the authors' response.\n\n**UPDATE after reading the authors' response**\nThank you for the response. I had a closer look at the code and experiments. There are two things that I think would improve the paper and code. First, I would just re-emphasize that you ought to consider benchmarking on AWS or a cloud computing platform such that your experimental results can be shown to not be dependent on your specific lab hardware. Second, I note the following line of your code inside your parallel_adaptiveAdd() method (which shoulders a lot of the computation for your algorithm):\n\nline 148:             gain= objective.value( tmpS ) - valTmpS;  \n which can be found inside your parallel_adaptiveAdd() method.\n\nThis is technically fine, but if the goal is to do a fair comparison with the FAST code, consider instead:\n\ngain= objective.marginalval( new_tmpS, tmpS);  # where new_tmpS = list( set(tmpS) | set( Ti) )\n\nThe reason is that the FAST codes allow you to specify a marginalval() method, which might use memoization or other speedups. Your code in contrast is memoizing the value of the original  tmpS (once per processor), but computing the full function value of the new tmpS and taking the difference of the two. \n\nThe point is that depending on the specific objective function, and also on how objective.marginalval() is written (e.g. whether it uses memoization or speedups on a particular objective), either the FAST code or your code will have a potentially significant advantage. Fixing this will allow the two to be on the same footing.\n\nAgain, I do not believe this should lower your review score as it could either help or hurt your algorithm's performance vis-a-vis FAST depending on the specific objective function---I merely suggest it as a means to improve the fairness of the comparison.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are noted; the societal impact is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "T4rICHLLD5B", "reviewer": "Reviewer_EF6P", "summary": "This paper proposes several new algorithms for maximizing submodular functions which when combined achieve state of the art combination of approximation ratio, adaptive complexity, and query complexity. Empirically, the combined LS+PGB algorithm is also equal to or better than the recent FAST algorithm.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "This paper proposes a new algorithm for maximizing submodular functions that achieves state of the art combination of approximation ratio, adaptive complexity, and query complexity. Empirically, the algorithm is also equal to or better than FAST.\n\nImpact: This is nice paper with impressive results that improve over previous state of the art. The improved ThresholdSeq algorithm in particular may improve many existing algorithms that rely on this subproblem.\n\nQuality/Originality: Builds on and expands previous work in a novel way. The experiments would be improved if additional large scale datasets were used such as ImageNet, MovieLens, or Uber Pickups\n\nClarity/Organization:\n- Very good overview of previous state of the art, with guarantees as well as high level explanation of various algorithms\n- The paper ends abruptly with many results deferred to the Supplementary material. I suggest moving the complete proof of ThresholdSeq to the main paper as a warmup, then explain how the analysis must change for LinearSeq and defer the full proof of LinearSeq to the Supplementary Material.\n- Please mention that \"adaptivity\", \"adaptive complexity\", and \"adaptivity complexity\" are used interchangeably\n\nQuestions:\n- How does the proposed method compare to FAST for larger values of k?\n\n---\nEDIT: The authors answered my main question in their response. Therefore, I am keeping my review the same.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Little to no discussion of limitations or societal impact. The authors could discuss environmental impact of large-scale datasets and/or subset selection problems reinforcing existing biases in data", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KE7BK019Kvl", "reviewer": "Reviewer_gBDP", "summary": "Submodular maximization is an important problem with many relevant applications in machine learning. With the huge amount of existing data and increase in the available computational power (increase in the number of machines), it is important to design scalable and parallelizable algorithms with provable guarantees from both practical and theoretical points of view. Many recent works have studied the submodular maximization in the context of adaptivity (“The degree of parallelizability can be measured by the adaptive complexity of an algorithm, which is the minimum number of rounds into which the queries to f may be organized”). In this paper, the authors propose an algorithm that achieves the state-of-the-art in terms of adaptive complexity, query complexity, and approximation ratio.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "This is a nicely written paper. It studies an important paper. It adds another important piece to the collection of recent developments in the scalable submodular maximization domain. The authors have performed an extensive set of experiments. The code and the data for the experiments are shared. As far as I checked, the proof looks correct. As a result, I recommend this paper for acceptance. \n\nI have a few suggestions that could improve the presentation of the paper:\n* It would be useful to add FAST [8] to Table 1 as it is used as the baseline in the experiments.\n* In the experiments, it is useful to report the adaptivity of the algorithms.\n* Adding more details to the experiments in the main text could improve comparison. You can reduce the number of datasets and instead report the objective, adaptivity, and number of queries too.\n* You can add more context to the explanation of the main algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any immediate negative societal impact from this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "2T28cdccNYo", "reviewer": "Reviewer_ubfR", "summary": "This work introduces the LinearSeq subroutine, which achieves a 1/4\napproximation ratio for monotone submodular maximization subject to a\ncardinality constraint w.h.p. while using $O(n)$ queries in expectation and\n$O(\\log n)$ adaptive rounds. The authors then show how to use LinearSeq\ntogether with a thresholding subroutine to achieve an algorithm with a\n$(1-1/e-\\varepsilon)$ approximation for monotone submodular maximization in\n$O(1/\\varepsilon^2 \\log(n / \\varepsilon))$ adaptive rounds and an expected $O(n\n/ \\varepsilon^2)$ queries. This is an improvement over the previous works of\n[Balkanski-Rubinstein-Singer, SODA 2019], [Ene-Nguyen, SODA 2019],\n[Fahrbach-Mirrokni-Zadimoghaddam, SODA 2019] in terms of $\\varepsilon$ factors\n(for the query complexity) and practicability.\n\nThe authors compare their work extensively to the recent FAST algorithm of\n[Breuer-Balkanski-Singer, ICML 2019], which sacrifices some theoretical\nguarantees in favor of being extremely practical. Compared to all previous\nworks, the main result here improves the query complexity without sacrificing\nthe approximation quality or (much of) the adaptivity. The experiments in this\npaper compare against FAST and demonstrate that the algorithm in this paper is\nsubstantially faster than FAST without compromising on the solution quality\n(see Figure 3 in the full version of the paper).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "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": "", "main_review": "**Originality.**\nThis paper builds on recent line of work on low-adaptivity monotone submodular\nmaximization. The overarching approach is reasonably well understood in the\nsubmodular literature, but the new subroutine (LinearSeq) that the authors\nintroduce is a powerful, standalone technique for preprocessing the candidate\nspace for a good guess of OPT, and therefore can be used to reduce the query\ncomplexity of all existing low-adaptivity algorithms (i.e., this idea allows us\nto find an interval $[L, U]$ such that $U/L = O(1)$ and $OPT \\in [L, U]$ using\na nearly optimal number of queries and adaptive rounds).\n\n**Quality.**\nThe LinearSeq subroutine is a low-adaptive adaptation of the novel streaming\nalgorithm of [Kuhnle, AISTATS 2021]; hence, this paper does a great job of\nbridging the two literatures (streaming and low-adaptivity) in a meaningful\nway. Overall, the paper is good, but it's not clear that the previous\nstate-of-the-art algorithm for this problem is the FAST algorithm\n[Breuer-Balkanski-Singer, ICML 2020], even though it's the most recent in this\nline of work. The authors compare only against this, but it would be valuable\nto see how the algorithms from SODA 19 compare as well, as they have better\ntheoretical guarantees than FAST.\n\nThe theory is interesting and seems to follow the high-level approach of\n[Fahrbach-Mirrokni-Zadimoghaddam, SODA 2019], which is a thresholding\nbatch-greedy algorithm. The experiments could be improved in my opinion, since\nthey only compare against FAST. In the first nine pages, only the running times\nare considered, which can be somewhat implementation-specific. For the revision,\nit seems that comparing the solution quality (i.e., Figure 3 in the appendix)\nwould be more meaningful, since most of the running time information is\ncaptured in Table 2. Further, the drop in running time for FAST in the\nMaxCover(WS) experiment seems inconsistent with the other data points and\nshould probably be explained (especially since this is averaged over five\ntrials). In general, the running time of this algorithm is 10x faster than FAST\nwith comparable solution quality and ~10x fewer oracle queries.\n\n**Clarity.**\nThe paper is written pretty well for a familiar audience. One comment here is\nthat I would advertise all results of this paper clearly in the abstract, not\njust that LinearSeq achieves a 1/4 approximation with nearly optimal adaptivity\nand query complexity. At quick glance, it's not clear that the paper contains a\n$(1-1/e-\\varepsilon)$-approximation algorithm, which then makes the optimality\ncomponent of the title somewhat confusing.\n\n**Significance.**\nOverall, this is a good result in an active area of research. The remaining\nproblems in low-adaptivity monotone submodular maximization are (1) shaving off\n$\\varepsilon$ factors and (2) making the algorithms more practical. This paper\ntackles both of these problems.\n\n**Typos / Suggestions.**\n- Suggestion: Consider removing \"Best of Both Worlds\" from the title since it\n  somewhat implies that no previous works achieve this balance.\n- [33] Suggestion: Consider using the author names + the citation in the\n  Reference column of Figure 1. It seems like this would be easier to read than\n  the algorithm acronym and citation number.\n- [74] Suggestion: Would be good to include the line of low-adaptivity\n  submodular maximization algorithms for non-monotone functions, instead of just\n  citation [22]:\n  * Balkanski, Eric, Adam Breuer, and Yaron Singer. \"Non-monotone submodular\n    maximization in exponentially fewer iterations.\" Advances in Neural\n    Information Processing Systems 31 (NeurIPS 2018).\n  * Fahrbach, Matthew, Vahab Mirrokni, and Morteza Zadimoghaddam. \"Non-monotone\n    submodular maximization with nearly optimal adaptivity and query complexity.\"\n    International Conference on Machine Learning. PMLR, 2019.\n  * Ene, Alina, and Huy Nguyen. \"Parallel algorithm for non-monotone\n    DR-submodular maximization.\" International Conference on Machine Learning.\n    PMLR, 2020.\n- [93] Suggestion: The paper seems to have a somewhat of an aggressive in\n  the first few pages (in my opinion). The superior results are clear from the\n  main theorem alone, so I'd let them speak for themself. Examples:\n  * [93] \"arguably, this is the right way to conduct adaptive sequencing\"\n  * [77] \"highly impractical\" -- maybe, but it's probably better to say \"very expensive\"\n- [158] Typo: Line 2 of Algorithm 1 uses $\\epsilon$ instead of $\\varepsilon$\n- [280] The guarantees of ThresholdSeq in Theorem 2 has the same format of\n  Lemma 3.2 in [Fahrbach-Mirrokni-Zadimoghaddam, SODA 2019] for their\n  Threshold-Sampling algorithm. If the ThresholdSeq algorithm was inspired by\n  that subroutine, it makes sense to at least point to that reference and their\n  algorithm.\n- [302] Is the $\\alpha$ in \"$\\Gamma$, $\\alpha$, where the...\" a typo?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers liked both the theoretical guarantees and the empirical performance achieved by the algorithm proposed in this paper, which improves over state-of-the-art algorithms for submodular maximization. For the final version, please include the additional comparison to [FMZ19] that was discussed in the response.
Decision: Accept (Poster)