Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
Authors: Yixin Chen
Wenjing Chen
Alan Kuhnle
Venue: ICML 2025 poster (2025)
Keywords: submodular optimization
combinatorial algorithms
parallel algorithms
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: First combinatorial algorithm for the non-monotone submodular maximization problem achieving a $1/e$ approximation ratio with sublinear adaptivity

Abstract: With the rapid growth of data in modern applications, parallel combinatorial algorithms for maximizing non-monotone submodular functions have gained significant attention. In the parallel computation setting, the state-of-the-art approximation ratio of $1/e$ is achieved by a continuous algorithm (Ene & Nguyen, 2020) with adaptivity $\mathcal O (log(n))$. In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound – a randomized parallel approach achieving $1/e − \epsilon$ approximation ratio. This result bridges
the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4 − \epsilon)$-approximation algorithm with high probability $(\ge 1 − 1/n)$. Both algorithms achieve $\mathcal O (log(n) log(k))$ adaptivity and $\mathcal O (n log(n) log(k)) query complexity. Empirical results show our algorithms achieve competitive objective values, with the $(1/4 − \epsilon)$-approximation algorithm particularly efficient in queries.

Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and 1/e Approximation
Yixin Chen
Wenjing Chen
Alan Kuhnle
Abstract
atschek et al., 2014) and feature selection (Bilmes, 2022),
it helps identify the most informative subsets efficiently. In social network analysis (Kempe et al., 2003), it aids in in- fluence maximization by selecting a subset of individuals to maximize information spread. Additionally, in machine learning (Bairi et al., 2015; Elenberg et al., 2017; Prajapat et al., 2024), submodular functions are used for diverse tasks like active learning, sensor placement, and diverse set selection in recommendation systems. These applications demonstrate the flexibility and effectiveness of submodular optimization in addressing real-world problems with both monotone and non-monotone objectives.
With the rapid growth of data in modern appli- cations, parallel algorithms for maximizing non- monotone submodular functions have gained sig- nificant attention. In the parallel computation setting, the state-of-the-an approximation ratio of 1/e is achieved by continuous algorithm (Ene & Nguyen, 2020) with adaptivity O (log(n)). In this work, focus size constraints and present the first combinatorial algorithm matching this bound a randomized parallel approach achieving 1/e- E approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop simpler (1/4- - ->approoxiationn algorithm with high probability (2 1 1/nt). Both algorithms achieve O (log(n) log(k)) adap- tivity and O (n log(n) log(k)) query complexity. Empirical results show our algorithms achieve competitive objective values, with the (1/4- (44-s) e)- approximation algorithm particularly efficient in queries.
Problem Definition and Greedy Algorithms. In this work, we consider the size-constrained maximization of submodular function: given submodular function ground set of size n, and given integer k, find arg max f(S). If additionally f is assumed to be monotone, we refer to this problem as SM-MON; otherwise, we call the problem SM-GEN. For SM-MON, a standard greedy algorithm gives the optimal' approximation ratio of 1 - 1/e = 0.63 (Nemhauser et al., 1978) in most kn queries" to f. In contrast, standard greedy can't achieve any constant approximation factor in the non-monotone case; however, an elegant, randomized variant of greedy, the RAN- DOMGREEDY of Buchbinder et al. (2014) obtains the same greedy ratio (in expectation) of - 1/e for monotone objec- tives, and 1/c z 0.367 for the general, non-monotone case, also at most kn queries. However, as modern instance sizes in applications have become very large, kn queries too many. In the worst case, h ((n),, and the time com- plexity of these greedy algorithms becomes quadratic. To improve efficiency, Buchbinder et al. (2017) leverage sam- pling technique to get FASTRANDOMGREIS the query complexity to O (n) when 2 Se log((e (2)
1. Introduction
Submodular Optimization. Submodular optimization is powerful framework for solving combinatorial optimiza- tion problems that exhibit diminishing returns (Nemhauser et al., 1978; Feige& & Goemans, 1995; Coruueooss et al., 1977). In monotone setting, adding more elements to a solution always increases its utility, but at a decreasing rate. On the other hand, non non-monotone objectives may have elements that, when added, can reduce the utility of solution. This versatility makes submodular optimization widely applicable across various domains. For instance, in data summarization (Mirzasoleiman et al., 2018; Tschi-
reducing
Parallelizable Algorithms. In addition to reducing the number of queries, recently, much work has focused on developing parallelizable algorithms for submodular opti-
Department of Computer Science & Engineering, Texas A&M University, College Station, Texas, USA. Correspondence to: Alan Kuhnle <kuhnle tamu.edu>.
'Opimmal in polynomially many queries to in the value query model (Nemhauser & Wolsey, 1978).
"Typically, queries to f dominate other parts of the computa- tion, in this field time complexity of algorithm is usually given as oracle complexity to f.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Sublinear Adaptive Algorithm for Submodular Maximization
Table 1. Theoretical comparison of greedy algorithms and parallel algorithms with sublinear adaptivity.
Algorithm
Ratio
Queries
Adaptivity
FASTRANDOMCREEDY (Buchbinder et al., 2017)
1/e -
O (n)
ANM (Fahrbach al., 2023)
0.039
O (n (og(
(log(n))
Ene & Nguyen (2020)
1/e.
0 (IPn (n)" (
(log(n))
PARKNAPS ACAMaassCKAAmaaiiiii et al., 2021)
0.172
O [Inn log(n] [og(k)) [|O (og(n) (k))
(log(n)) ||O (log(n) log(k))
AST (Chen & Kuhalc, 2024)
1/6-
(A))
(log(n))
ATG (Chen & Kuhnle, 2024)
0.193
O (n (og)
O (log(n) log(A))
PARSKP (Cui et al., 2023)
0.125
(Io log" (n]) ||0 (n log (n) log(R))
O (log(n]) ||O (log(n) log(k))
PARSSP (Cui et al., 2023)
0.25 e
(Ko log (oi)) ||O (n log log(k))
0 (log (n)) ||O (log (nx) log()))
PARALLELIN PARALLBLLAVERROLLATEDOEEDDD (Alg. 11)
(Alg. 6)
0.25 - st
(n log(n) log(k))
O (log(n) log(k))
1/e- -
O (n log(n) (A)
O (log(n) log(k))
The parallel algorithm in Enc & Nguyen (2020) queries to the continuous oracle. The approximation ratio is achieved with high probability (at least 1 1/n).
mization. One measure of parallelizability is the adaptive complexity of an algorithm. That is, the queries to f are divided into adaptive rounds, where within each round the set queried may only depend on the results of queries in previous rounds; the queries within each round may be arbi- trarily parallelized. Thus, the lower the adaptive complexity, the more parallelizable an algorithm is. Although the initial algorithms with sublinear adaptivity were impractical, for the monotone case, these works culminated in two practi- cal algorithms: FAST (Breuer et al., 2020) and LS+PGB (Chen et al., 2021), both of which achieve nearly the opti- mal ratio in nearly linear time and nearly optimal adaptive 5
Algorithm 1: INTERLACEGGEEDDY( (f; k): The INTER- LACEGREEDY Algorithm (Kuhnle, 2019)
Input: evaluation oracle f: 2 - R20, constraint Initialize :dg - arg mixxx=e I (æ), + B < 0,
D + E {. add 24 dummy elements
the ground set
for 0 to ks - do
A <- A + arg max DEUN A (a A)
3
B - B + arg
A (x: B)
4
for i + 1 to - do
D - D + arg max A (x D)
rounds. For the nonmonotone case, the best approxima- tion ratio achieved in sublinear adaptive rounds is 1/e (Ene & Nguyen, 2020). However, this algorithm queries to continuous oracle, which needs to be estimated through a substantial number of queries to the original set function oracle. Although practical, sublinearly adaptive algorithms have also been developed, the best ratio achieved in nearly linear time is nearly 1/4 (Cui et al., 2023), significantly worse than the state-of-the-ards this 1 ratio also stands as the best even for superlinear time parallel algorithms. Fur- ther references to parallel algorithms and their theoretical guarantees are provided in Table
E + E + arg mEX A (a: E)
return C' t arg mag (A) f (B) (D),
contained within the optimal solution O. Based on this hy- pothesis, the algorithm initializes two solution pools differ- ently: if ap is not in O the pools begin empty (A = B = 0); otherwise, they are initialized with dp (D = E = {ao)))
The algorithm then proceeds by alternately selecting ele- ments for each pool in a greedy fashion, ultimately returning the best solution found. We provide its theoretical guaran- tees below.
Greedy Variants for Parallelization. To enhance the ap- proximation ratios for combinatorial sublinear adaptive al- gorithms, it is crucial to develop practical parallelizable algorithms that serve universal frameworks for such par- allel approaches. Among existing methods, INTERLACE- GREEDY (Kuhnle, 2019), with an approximation ratio of 1/4, and INTERPOLATEDGRREDY (Chen & Kuhnle, 2023), with an expected approximation ratio of 1/c, have emerged as promising candidates due their unique and determinis- tic interlacing greedy procedures.
Theorem 1.1. Let f :21 Rz0 be submodular, let k E U, let O arg ma (S), and let C INTERLACEGREEDY (f, k). Then
[C) 2 (O)
and INTERIACEERREDD makes O (kn) queries to f.
The key to this guarantee lies in the alternating selection strategy between the two pools. For any disjoint pools {S,T), it holds that
INTERLACEGRREDY (Alg. 1) operates by first guessing whether the maximum singleton
arg max f (z) is
+
'The best known ratio in polynomial time was very recently improved from close to 1/c ee to 0.401 (Buchbinder & Feldman, 2024)
where the first inequality follows from the alternating se- lection strategy, and the second inequality follows from submodularity and monotonicity.
2

---

Sublinear Adaptive Algorithm for Submodular Maximization
Building on this, INTERPOLATEDGGREEDD (Chen & Kuhnle, 2023) generalizes the approach by maintaining e sets, each containing k/L elements at each iteration (see pseudocode and theoretical guarantees in Appendix C). However, in their original formulations, both algorithms require an initial step to guess whether the first element added to each solution belongs to the optimal set O. This results in repeated for loop with different initial values in INTERLACEGREEDY and success probability of (E 1)
Nearly-linear Query Complexity Using Unified Sub- routine. In Section 4, present two sublinear adaptive al- gorithms, PARALLEINNEERAACGGEEDD (PIG) and PAR- ALLELINTERPOLANEDGREED (PITG) that share unified subroutine, PIG. The core innovation of PIG lies in its novel threshold sampling procedure, which simultaneously preserves the crucial alternating selection property of in- terlaced greedy methods while enabling efficient parallel implementation.
Like prior parallel algorithms, PIG maintains descending thresholds for each solution, adding elements whose average marginal gain exceeds the current threshold. However, PIG introduces two critical modifications to maintain the inter- laced greedy structure: 1) strict synchronization of batch sizes across all & parallel solutions, and 2) coordinated ele- ment selection to maintain sufficient marginal gain for each solution.
1.1. Contributions
1/4
1/e
Alternating Selection
InteriooGredyy
InvepsaateGeedyyy (2023)
This design achieves three fundamental properties. First, it preserves the essential alternating selection property of the interlaced greedy methods. Second, through threshold sampling, it geometrically reduces the size of candidate sets crucial for achieving sublinear adaptivity. Third, its efficient batch selection ensures each added batch provides sufficient marginal contribution to the solution. Together, these properties allow PIG to match the approximation guarantees of the vanilla interlaced greedy method while achieving parallel efficiency.
Blended Märginal Gain
Stmrpiified InterfacCGreddy (Alg.
Simpliiied Inteppduiddaaredyy (Alg 2)
Threshold Sampling
PralkllintciaeCCeeddy (Alg.
PandielinerpaalstGeedd (Alg I1)
Figure 1. This figure illustrates strategies employed by each al- gorithm. The three leftmost algorithms achieve asymptotic approximation ratio of 1/4, while the three rightmost algorithms attain an asymptotic ratio of 1/c.
Leveraging this unified framework, a single call to PIG achieves an approximation ratio of (1/4 e) with high probability. Repeated calls to PIG yields PITG, further enhance the approximation ratio to an expected (1/e E). Both algorithms achieve O (Iog(n) log(k)) adaptivity and O (n log(n) log(k)) query complexity, making them efficient for large-scale applications.
Technical Contributions: Blended Marginal Gains Strategy. Our first contribution is novel method of analy- sis for interlaced greedy- based algorithms, such as INTER- POLATEDGREEDY (Chen & Kuhnle, 2023). The core in- novation introduces multiple upper bounds on the marginal gain of the same element regarding the solution, offering greater flexibility in the analysis. This approach yields three notable advances: First, we present Alg. (Section 3) with O (kn) query complexity, achieving expected ap- proximation ratios of 1/e E, eliminating the probabilistic guessing step that limited prior method to (1 + f success probability. Second, as a byproduct, we also provide a sim- plified version of INTERLACEG ACEGREEDY (Kuhnle, 2019) that preserves theoretical guarantees in Appendix D. Most im- portantly, these simplified variants establish the theoretical foundation for parallel algorithms. By removing branching dependencies and probabilistic guesswork, our framework enables the first efficient parallelization of these interlaced greedy approaches while preserving their approximation guarantees.
Empirical Evaluation. Finally, we evaluate the perfor- mance of our parallel algorithms in Section 5 and Ap- pendix H across two applications and four datasets. The results demonstrate that our algorithms achieve competitive objective values. Notably, PARALLELINTER L outperforms other algorithms in terms of query efficiency, highlighting its practical advantages.
2. Preliminary
Notation. We denote the marginal gain of adding A to B by A (A) B) = (AU B) f (B). For every set S C U and an element x E U, we denote S U {x) by S + x and S {x} by S 5-z. z.
Submodularity. modular, if A (x () 2 A (x|7) (T) for all S C T C u and
set function f 2 - R20 is sub-
2 \ T. or equivalently, for all A, B C U. it holds
Parallel Algorithms with Logarithmic Adaptivity and
3

---

Sublinear Adaptive Algorithm for Submodular Maximization
that / /A) + (BB) 2 + B). With size constraint k, let O = arg maxsgu,|sis f (S).
success probability 1, all possible solution branches must be checked, increasing the query complexity by a prohibitive O ((E + 1)²) factor. While asymptotically efficient (O (nk) queries), INTERPOLATEDDRREDD suffers from either low success probability or impractical computational overhead, making it unsuitable for parallelization.
In Appendix B, we provide several key propositions derived from submodularity that streamline the analysis.
Organization. In Section 3, the blending technique is in- troduced and applied to ETERLACEGREEDY and INTER- POLATEDGREEDY, with detailed analysis provided in Ap- pendix D and E. Section 4 discusses their fast versions with pseudocodes and comprehensive analysis in Appendix F. Subsequently, Section 4 delves into our sublinear adaptive al- gorithms, with further technical details and proofs available in Appendix G. Finally, we provide the empirical evaluation in Section 5, with its detailed setups and additional results in Appendix H.
3.2. Motivation for Simplification
The primary challenge in parallelizing INTERPOLATED- GREEDY stems from its inherent branching structure specifically, the need to make + guesses, each resulting in an independent construction path for solution pools. This complex architecture naturally raises a fundamental ques- tion: Can we develop alternative analysis framework that eliminates the need to explicitly guess the position of Omax? ?
3. A Parallel-Friendly Greedy Variant via Blending Technique
To address this, we introduce a novel blended marginal gains strategy. Our key insight demonstrates that by care- fully tracking combined marginal gains across iterations, effectively work with just a single solution family of pairwise disjoint solutions while preserving all theoretical guarantees.
In this section, we present a simplified and practical variant of INTERPOLATEDDREEDY (Chen & Kuhnle, 2023) that retains its theoretical guarantees while improving its success probability from (6++1 1)+11--fm to 1. This simplification serves as a key step toward developing efficient parallll submodular maximization algorithms (Section 4). As a byproduct, we also show that INTERLACEGREEDY (Kuhnle, 2019) can be simplified (Appendix D) and parallelized (Section 4).
This simplification not only boosts the success probability to 1 but also enables a more efficient parallel implementa- tion. We present the pseudocode of the simplified INTER- POLATEDGREEDY in Alg. 2, with theoretical guarantees in Theorem 3.1.
3.1. An Overview of Prior Work and Its Limitation
INTERLACEGREEDY (Alg. 1) employs a two-branch ini- tialization strategy conditioned on differently based on the guessing of whether the maximum singleton ag arg mag f (I) is contained within the optimal solution O. The algorithm initializes two solution pools either as empty sets if dg & O, or both containing on otherwise. It then alternates between two greedy procedures, growing solutions pools one by one until they reach size k. The algorithm returns the best solution, achieving 1/4 e approximation. This structure is necessary to handle the uncertainty about whether the maximum singleton ag coin- cides with 0max arg max f (o).
Algorithm 2: A simplified INTERPOLATEDGREEDY
with a randomized 1 approxiiiat ratio and O (nkl) query complexity.
Input: evaluation oracle f: 24 + Rzo, constraint k, size of solution E, error E Initialize: - 0, V <- 24, < [ add 2k dummy elements to the ground set.
for i 1 to & do
A + G, VI E [4]
3
for j + 1 to m do
for / + 1 to E do
Later on, INTERPOLATEDGREDDY (Alg. 7, Appendix C) generalizes this idea by interlacing greedy procedures, each adding k/C elements to intermediate solutions. Crit- ically, the algorithm must account for uncertainty in the position of Omax- Since Omax could be one of the top-l el- ements in marginal gain (or none of them), the algorithm must consider é + 1 possible cases. To handle this, it main- tains E + solution families (a set of multiple potential so- lutions), each corresponding to a distinct guess about where Omax appears. The algorithm then returns a random solution from the solution families, achieving a 1/e - e approxi- mation with success probability (e + 1) To guarantee
5
a K- arg max A A
A: + a, V + V
G a random set in {At]uet
return G
Theorem 3.1. With input instance (J, k, t,e) such that
eg- ez-? Alg. 2 returns a set G with O (kn/e)) queries such that E [f (G) 2 (1/e e)) (0).
O ( (s-1) cs
2 and k > 2(el-2)
4

---

Sublinear Adaptive Algorithm for Submodular Maximization
3.3. Technical Overview of Blended Marginal Gains Strategy for INTERPOLATEDGREED
2) 1+ m
(A (Ar, Gc-1) + A (AI, (G-
2 A (01g) A4) + A (Oi, AAi)) LA < h < 22 St.
In INTERPOLATEDGREEDY,, each iteration maintains L + solution families, each containing & nearly pairwise disjoint sets. Among these solution families, only one is right which satisfies the following key inequality:
Step 2: Sell-Interaction Term Bounding. The partition from Claim 3.1 immediately yields our first bound. For any LE [e] elements in O₂ \ A were available but not selected by the greedy procedure, directly implying the first required bound.
A (0) Au,i) S L i G), Vi [.]
(1)
where G is the intermediate solution at the start of this iteration, and A is the i-th solution in the u-th solution families at the end of this iteration.
Step 3: Cross-Interaction Term Bounding. The primary technical challenge lies in effectively bounding the cross- interaction terms A (Ar, G,-1) + A (Ai, | G₁-z), Rather than relying on original greedy selection bounds, we develop more sophisticated approach through our blended marginal gains technique, formalized in the following proposition:
The right solution families guarantees that elements added in the first round do not belong to O \ A for any [e]. This property enables a partition of the optimal solution O into k/l subsets of size f, where each subset's marginal gain is dominated by corresponding element in Au,i Conse- quently, A (O Au,;) depends solely on A (Au.a G).
Proposition 3.3 (Blended Marginal Gains), For any sub- modular function f: 2 + R2o and S, T, E U. Let S; be a prefix of S with size such that St S O. Similarly, define Tj. satisfies that,
In what follows, we introduce a novel blended marginal gains approach to analyze INTERRPLLATEDGREEDD using only single interlaced greedy step (Alg. 2). This approach leverages mixture of marginal gains across solutions to derive tighter bounds for each A (0) A).. The analysis proceeds in four steps:
(OO & A (S. (O) ( 1T). S. ( S (T, + ( T, 1S),
(3)
(4)
The key insight involves strategically partitioning O into two components: 1) a subset keeps the original greedy se- lection bound, and 2) a residual subset where we apply submodularity only.
Step 1: Partitioning the Optimal Solution O. Our anal- ysis begins by establishing a correspondence between the algorithm's solutions and partitions of the optimal set O. Claim 3.1 provides the foundation for this pairing:
Applying this proposition to each solution pair (Ar, Atg) with carefully chosen prefixes yields the second inequality in Lemma 3.2.
Claim 3.1. At an iteration i of the outer for loop in Alg. 2,
let G be G' at the start of this iteration, and A be the set at the end of this iteration, for each E [c]. The set O G can then be split into l pairwise disjoint sets {O1...., Oz) such that |Or| < & and (O) \ Gi-1) (Ar) G.-1) C Oi, for all E [e].
Step 4: Final Composition. By applying Inequality (2) and Lemma 3.2, we derive a result analogous to Inequality (1) achieved by ITTERROL.ATEDGREEDDY
Σ S (1+ [E
Σ AA (5)
This partition enables us to decompose the marginal gains of O with respect to each solution Ai. Specifically, we express the total marginal gain as:
LE[
Σ Ai)
A (O.) Ar)
(Proposition B.
This forms the key property necessary to establish the 1/e- approximation ratio while requiring only a single pool of solutions. The detailed analysis of the approximation ratio is provided in Appendix E.
LELO]
KE|4 KE[L]
= Σ
(A,,)) Ar,) + (Oi, A()))
154
A
4. Sublinear Adaptive Algorithms
1E
The decomposition consists of two types of terms: 1) self- interaction term A (O;l Ar) for each / E [e], and 2) cross- interaction terms A (O,, A (O:, I Ar,) for each 1 x 4 < 12 < E. Below we establish upper bounds for each term type, with detailed analysis to follow.
In this section, we present the main subroutine for our parallel algorithms, PARALELLIVEELLAEEGEEEYY (PIG, Alg. 6). A single execution of PIG achieves an approx- imation ratio of 1/4 E with high probability, while re- peatedly running PIG, as in PARAILELINTERRPI.ANE GREEDY (PITG, Alg. 11 in Appendix G.3), guarantees a randomized approximation ratio of 1/c - e. Below, we outline the theoretical guarantees, with the detailed analysis provided in Appendix G.
Lemma 3.2. Fix on G;-1 for an iteration of the outer for loop in Alg. 2. Following the definition in Claim 3.1, it holds that
I) (Ar |G-1) 2 (0,) A)) VI sisC
5

---

Sublinear Adaptive Algorithm for Submodular Maximization
Theorem 4.1. With imput 2,, 2M e), where M max f (x), PIG (Alg. 6) returns {A(;AA) A2) with o (E log(n) log(k) adaptive rounds and O ( log(n) log(k)) queries with a probability of 1 - 1/n. It satisfies that maxif (f))(((A))
Algorithm 4: Select prefix of V s.t. its average marginal gain is greater than (1 - a)T, and with prob- ability of 1/2, more than an E/ /-ffraccionnn of V has a marginal gain less than T relative to the prefix.
Procedure PREFIX- SELECTION (T,
(1/4 1//4-))((O) (O).
Input: evaluation oracle f 24 + RR2, maximum size s, threshold T, error E, candidate pool where A (a () for any 2 E Initialize: B(1 + V+
Theorem 4.2. With input (f, E, such that e 0 (E-1)
4 and k 2 cet-4 PITG (Alg. 11) returns G such that
(2-z)
f none, none {u1, -.. +- random-permutaatoo(())
[ 2 (1/e - e) ( (O) with O (s=9log()) log(k)) adaptive rounds and (e-2n log(n) log(k)) queries with a probability of - O (I/(s))).
for i + 1 to in parallel do
Ti-1 4 {Ul...., Vi-13
if A (2; T(-1) 2 T then B[i] +- true
The remainder of this section organized as follows. In Sec- tion 4.1, we present the key subroutines that form the build- ing blocks of PIG. Section 4.2 then provides high-level overview of the algorithm, and introduces several critical properties that must be preserved throughout the process.
else if A (v: 7--1) < 0 then B[i] < false
+- max(i: #trues B[1 : i| 2 (1 E}1}
8
return 1", B
4.1. Subroutines for PIG
8-15 of THRESHSEQ (Chen & Kuhnle, 2024), and conse- quently inherits similar theoretical guarantees (Lemma 4 and 5) as follows.
DISTRIBUTE (Alg. 3) constructs pairwise disjoint subsets [ [e]} from candidate pools {Vi [4]] preparing for the subsequent threshold sampling phase. This crucial preprocessing step ensures that all elements added to the solution maintain disjointness across different solution sets. We provide its theoretical guarantee in Lemma 4.3.
Lemma 4.4. In PREFX-SELECCION, given V af- ter random- cinidoonpermutatiion {ar E V: (x T2) < r). It holds that |Dol = 0. |Pal V and D S D.).
Line 2. let D. =
Lemma 4.5. In
following the defini-
Lemma 4.3. With input {Vi) where |Vil 2 2 for each 1 [e], DISTRIBUTE returns E pairwise disjoint sets Vil
tion of D, in Lemma 4.4, let t min(i: |P,] e|21/2). It holds that IP [+- < min(s, {)] S 1/2.
{Vileeg s.t. Vi S V1 and V21 2 27
Algorithm 5: Update candidate set V with threshold
Algorithm 3: Return pairwise disjoint subsets where 1211 1V
value 7
for any E [6] if [V5| 2 26
Procedure UPDATE (f, T,E):
Procedure DISTRIBUTE ( (V; Input: Vi, V2,...,, V/ C U
[q]]
Input: evaluation oracle f 2 + Rzu, candidate
set V, threshold value т, error
Initialize: V1, V2..... V/= + 0, 1 t [2]
2
for j + to to in parallel do
for i +-++ to l do j f arg minjer Vy
3
V + {Ir E V : A (a 0) 2 r}
4
while |V| do
7 T (1 E)T
V3 t randomly select
elements in
V + {I E A 0) 2
VG \ (Urenn Pi)
7
return V,T
I I+ - return (V) E [e]]
UPDATE maintains the candidate set V for a solution using threshold r. If V becomes empty, it decrease the threshold and regenerate V until it is not empty. This is a common component of threshold sampling algorithms.
TREFIX-SELECHE (Alg. 4) serves as the fundamental building block for threshold sampling procedure. It achieves two critical objectives simultaneously: 1) it identifies a pre- fix T:- that provides sufficient marginal gain to the solution, and 2) with probability at least 1/2, it guarantees that constant fraction of candidate elements have low marginal gain (< T) relative to the augmented solution.
4.2. Algorithm Overview
PIG synthesizes threshold sampling techniques with inter- laced solution construction to achieve both parallel effi- ciency and strong approximation guarantces. It begins by initializing & empty solutions (A, : J [4], with corre-
Our implementation of PREFIX-SELECCT SELECCION follows Lines
6

---

Sublinear Adaptive Algorithm for Submodular Maximization
sponding threshold values set to the maximum singleton marginal gain M maxxeu A (x: 0).
of elements in the blocks may have marginal gains below Jj. the process retains the alternating property a structural level: the uniform block sizes, and disjoint selection mimic the alternating addition of elements, even when processing multiple elements in parallel.
At each iteration, PIG dynamically switches between two distinct operational modes based on candidate set sizes. When any candidate set Vj (maintained by UPDATE, Alg. 5) contains fewer than 20 elements, the algorithm enters an alternating addition phase where single elements are sequen- tially distributed across solutions. This preserves the alter- nating selection property crucial for maintaining approxi- mation guarantees while ensuring progress when candidate pools are limited.
4.2.2. ENSURING SUBLINEAR ADAPTIVITY THROUGH THRESHOLD SAMPLING
The core mechanism for achieving sublinear adaptivity lies in iteratively reducing the pool of high-quality candidate el- ements (those with marginal gains above the threshold) by constant factor within a constant number of adaptive rounds. This progressive reduction ensures efficient convergence.
For cases where all candidate sets contain sufficient number of elements (V;I 2 2 for each j E [4], PIG employs an efficient batch processing approach. First, DISTRIBUTE con- structs pairwise disjoint candidate subsets, enabling parallel processing while maintaining solution quality. PREFIX- SELECTION then simultaneously looks for blocks with high- marginal-gain elements. At last, the block size and the elements added to each solution are carefully chosen to maintain both solution quality parity and the equivalent alternating selection effect.
At every iteration of the while loop in Alg. 6, after updating the candidate sets, if there exists V, such that [V]] < 2 the following occurs after the for loop (Lines 7-13): If the threshold тj remains unchanged, one element from Vj is added to the solution. If T, is reduced, Vj is repopulated with high-quality elements. This implies that a 1/(2e)-fraction of V3 is filtered out after per iteration, or even further, it becomes empty and the threshold value is updated.
This dual-mode architecture combines the strengths of threshold sampling and interlaced greedy methods. The threshold sampling components (UPDATE and PREFIX- SELECTION) ensure efficient element filtering and geomet- ric threshold reduction, while the interlaced construction maintains the crucial alternating marginal gain properties. This allows PIG to achieve sublinear adaptivity without compromising its approximation guarantee.
In the second case, where Lines 16-24 are executed, the algorithm employs -SLEETION (Alg. 4) in Line 18, inspired by THRESSSSE (Chen & Kuhnle, 2024). Then, the smallest prefix size i" is selected in Line 19. For the solution where its corresponding call to PREFIX- SEEFFI--SLECCIE SELECTION returns i" the entire prefix with size i" is added to it. This ensures that a constant fraction of elements Vj can be filtered out by Lemma 4.5 with probability at least 1/2, Moreover, Lemma 4.3 guarantees that [Vyl 2 | for each candidate set. As result, with constant probability, at least one candi- date set will filter out a constant fraction of the elements.
Below, we further analyze three fundamental properties that the algorithm must maintain throughout execution.
4.2.1. MAINTAINING ALTERNATING ADDITIONS DURING PARALLEL ALGORITHS
4.2.3. ENSURING MOST ADDED ELEMENTS SIGNIFICANTLY CONTRIBUTE TO THE SOLUTIONS
This property is crucial to interlaced greedy variants intro- duced in prior sections. Below, we demonstrate that PIG preserves this property.
In THRESHSEQ. the selection of a good prefix inherently ensures this property immediately. However, when interlac- ing threshold sampling processes, prefix sizes selected in Line 18 by each solution may vary. To preserve the alternat- ing addition property introduced in Section 1.2.1, subsets of equal size are selected instead of variable-length good prefixes. This raises the question: How can a good subset be derived from a good prefix? The solution lies in Line 21 of Alg. 6.
During an iteration of the while loop in Alg. 6, after updating the candidate sets in Lines 3-5, two scenarios arise. In the first scenario, there exists a candidate set satisfies |Vyl < 26, Lines 7-14 are executed, and elements are appended to solutions one at time in turn. In this case, the alternating property is maintained immediately.
In the second scenario, Lines 16-24 are executed. Here, block of elements with average marginal gain approxi- mately exceeding Ty is added to each solution Ay. These blocks Sj are of the same size i* (Line 21) selected from Vj. and guaranteed to be pairwise disjoint by Lemma 4.3 (for DISTRIBUTE, Alg. 3). Crucially, threshold values Ty remain unchanged during this step. While small fraction
For any j e I. =i,, Sy is directly the good prefix V 17]. Otherwise, if if i 2 i", i" elements are selected from [, : 15] in three sequential passes until the size limit is reached:
First pass: Iterate through the prefix, selecting those with marginal gains strictly greater than Ty (marked true in
7

---

Sublinear Adaptive Algorithm for Submodular Maximization
Algorithm 6: A
highly
algorithm query complexity.
parallelized
with O 0 log
adaptivity
and
O
1 1 log(n) log
Tiiin
Procedure PARALELLNTERRLAGEGEEEEN
f,,,,, Tmin: E):
Input: evaluation oracle / 2 + RR2, constraint m. constant L, minimum threshold value Tmins error & Initialize:MM : + max À ([=) 0), 1 = [C] mo t m, Aj + A + 0, Tj t M, V3 + u, e [4]
while + 0 and mo > 0 do
for j E in parallel do /* Update candidate sets with high-qualite lity e eleents [1, - UPDATE(JA, (un A.): \ (ULEl) A,,))
if Ty < Tmin then / + --j if Di E 7 s.t. [V]] < 28 then / Add element to each solution alternately for j I in sequence do
if [Vg] = 0 then (V + UPDATE(JA, (un A1) T3.c
if ry < Tmin then I I --j
else
Ij < randomly select one element from Vj
Aj f + Tj, 4J AG + A3 + 2j
Vi + Vi zz, 4l [0]
mg + m00
15
else /* Add an equal number of el elements to each solution
- DISTTRIBUTT((VV ()) // Create pairwise disjoint candidate sets s mwmmmmmmmm min(mm, :1 :1 1}}
for j E in parallel do i7, By PREFFX-SSLLETTINNNAAA V/, T,,,)
i* mi..
for j
l in parallel do / Add i hi high-quality elements each set Sy f select i" elements from [ it] in three passes, prioritizing Byli] true, then By none, and finally B = false
S + S, n {or E vv; B o false}
A₁ A₂ US,
A3 US
24
mg + mg i*
25
return { 1 [
Bj).
ing its performance to 5 baseline algorithms. We measured the objective value (normalized by ATG (Chen & Kuhnle, 2024)) achieved by each algorithm, the number of queries made, and the number of adaptive rounds required. The re- sults showed that our algorithm achieved competitive objec- tive value, number of queries and adaptive rounds compared to nearly linear time algorithms.
Second pass: From the remaining elements in the prefix, select those with marginal gains between O and Ty (marked as none in B3).
Third pass: Fill any remaining slots with remaining ele- ments from the prefix (marked as false in Bj).
This approach, combined with submodularity, ensures that any element marked as true in the selected subset has marginal gain greater than Tj. By prioritizing the addition of these true elements, the selected subset remain high-quality while adhering to the alternating addition framework.
A Applications and Datasets. 2 applications: Maximum Cut (maxcut) and Revenue Maximization (revmax), with er (n = 99, 997), synthetic random graph, web-Google (n = 875, 713), musac-github (n = 37, 700) and twitch-gament (n = 168, 114) datasets, the rest of which are real-world social network datasets from Stanford Large Network Dataset Collection (Leskovec Krevl, 2014). See Appendix H.1 and H.2 for more details.
The algorithms were evaluated
5. Empirical Evaluation
To evaluate the effectiveness of our algorithms, ducted experiments on 2 applications of SM-GEN, compar-
*Our code available https//giitab.com//uiaayyyy instraints-parallel algoitthg..
8

---

Sublinear Adaptive Algorithm for Submodular Maximization
1.0
10a
Adaptive Rounds
10
Value ATG
Total Queries
10a
0.8
107
10
0.6
10
10a
0.4
0.05
0.10
0.15
0.05
0.10
0.15
0.10
0.15
k/n
k/n
k/n
(a) solution value
(b) query
(c) round
1.0
Value ATG
0.9
Total Queries
Adaptive Rounds
10
10a
0.8
10
0.7
10²
107
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15
k/n
k/n
k/n
(d) twitch-gamers, solution value
(c) writch-gamers, query
(f) twitch-gamers, round
Figure 2. Results for maxcut on er with n 99, 997, and revnax on twitch
twitch-gamers gamers with n 168, 114.
We provide the result of er and twitch-gamers in the main paper, while the other results can be found in Appendix H.3.
In terms of query complexity, PARSSP exhibits the high- est query complexity (O (n log log²(n) log(k))) followed by our proposed algorithms (O (n log(n) log(k))), compared to other algorithms (O (n (on()))))) (k))). Nevertheless, PIG achieves second-best performance across both datasets. The top three performing algorithms consistently include PIG, ATG and PARSSP. PITG is slightly better than ADAP- TIVENOMONNTONEM.X on and both are more ef- ficient than FASTRANDOMMRRFEDY on the two datasets. FASTRANDOMGREDD'S high query count arises from requirement for a large number of samples (specif- ically. 8nk - log((: (2==12=))) 8k Sk-lg-1 1og(2e-1) 1, it defaults executing RANDOM- GREEDYinstead, which incurs O (nk) queries.
Baselines and their Setups. We compare our algorithms with FASTRANDOMGREEDY (Buchbinder et al., 2017),
ADAPTVENONMONNTONER
(Fahrbach al., 2023),
AST (Chen & Kuhnle, 2024), ATG (Chen & Kuhnle, 2024),
and PARSSP (Cui et al., 2023) using binary search. For those algorithms who required an UNCONSTRAINEDMN algorithm, a random subset was employed instead. For all algorithms, the accuracy parameter and the failure proba- bility parameter 8 were both to 0.1. Whenever smaller and 5 values were specified by the algorithm, substi- tuted them with the input values. samples each element in the ground set l with probability 8k-l log(2e 1)) If p > 1, RANDOMGREEDY in Buchbinder et al. (2014) was implemented instead. As for THRESHOLD-SS AMPLLIGG in ADAPIVENONMONOTONE MAX, 100 samples were used to estimate an indicator. the implementation of PITG, algorithms repeated with 5 runs, and the mean is ported. The standard deviation is represented by shaded region in the plots.
-)) at every iteration. When
Regarding adaptive rounds (Fig. 2(c) and 2(c)), the results align with theoretical guarantees. ADAPTIVENONMONO- TONEMAX and AST operate with (log(n)) adaptivity and achieve the best performance. They are followed by ATG, PIG, and PITG which all achieve O (Iog(n) log(k)) adaptivity.
to 5. All randomized
PARSSP exhibits an interesting trade-off: while its binary search procedure benefits query complexity, it significantly increases adaptive rounds, performing worse than even FAS- TR FRANDOMGREEDY (which requires adaptive rounds) on the twitch-gant gaccessamers dataset.
Overview of Results. On the er dataset (Fig. 2(a)), PIG and PITG achieve highest objective values, followed by ATG, FASTRANDOMGREEDD and PARSSP. For the twitch- gamers dataset (Fig. 2(d)), PIG and PITG demonstrate greater robustness, particularly for larger values of k.

---

Sublinear Adaptive Algorithm for Submodular Maximization
Impact Statement
with Size Constraint. Journal of Artificial Intelligence Research, 79:599-633 637, 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, Y., Dey, T., and Kuhnle. A. Best of Both Worlds: Practical and Theoretically Optimal Submodular Maxi- mization in Parallel. In Advances in Neural Information Processing Systems, NeurIPS, 2021.
References
Cornuejols, G., Fisher, M. L., and Nemhauser, G. L. Lo- cation of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management science, 23(8)789-8110 1977.
Amanatidis, G., Fusco, F., Lazos, P., Leonardi, S., Marchetti- Spaccamela, A., and Reiffenhäuser, R. Submodular maxi- mization subject to knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity. In Proceedings of the 38th International Conference on Ma- chine Learning, ICMI., 2021.
Cui, S., Han, K., Tang, J., Huang, H., X., and Zhiyuli, A. Practical Parallel Algorithms for Submodular Maxi- mization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity. Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
Badanidiyuru, A. and Vondrák, J. Fast algorithms for max- imizing submodular functions. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2014.
Elenberg, E. R., Dimakis, A. G., Feldman, M., and Karbasi, A. Streaming weak submodularity: Interpreting neural networks on the fly. In Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, NeurlPS, 2017.
Bairi, R., Iyer, R. K., Ramakrishnan, G., and Bilmes, J. A. Summarization of multi-document topic hierarchies using submodular mixtures. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, ACL, 2015.
Ene, A. and Nguyen, H. Parallel Algorithm for Non- Monotone DR-Submodular Maximization. In Proceed- ings of the 37th International Conference Machine Learning, ICML, 2020.
Bilmes, J. Submodularity in machine learning and artifi- cial intelligence. CoRR, abs/2202.00133 2022.
ERDdS, and R&wi, A. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Breuer, A., Balkanski, E., and Singer, Y. The FAST Algo- rithm for Submodular Maximization. Proceedings of the 37th International Conference on Machine Learning, ICML, 2020.
Fahrbach, M., Mirrokni, V., and Zadimoghaddam, M. Non- monotone submodular maximization with nearly opti- mal adaptivity and query complexity. arXiv preprint arXiv:1800 808.06932,,... 2023.
Buchbinder, N. and Feldman, M. Constrained submodular maximization via new bounds for dr-submodular func- tions. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, STOC, 2024.
Feige, U. and Goemans, M. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pp. 182-189. IEEE, 1995.
Buchbinder, N., Feldman, M., Naor, S., and Schwartz, R. Submodular Maximization with Cardinality Constraints. In Symposium on Discrete Algorithms, SODA, 2014.
Hartline, J. D.,, Mirrokni, V. S., and Sundararajan, M. Op- timal marketing strategies over social networks. In Pro- ceedings of the 17th International Conference on World Wide Web, WWW, 2008
Buchbinder, N., Feldman, M., and Schwartz, R. Compar- ing apples and oranges: Query trade-off submodular maximization. Math. Oper. Res., 42(())308-333 -2200088--22200 2017.
Kempe, D.,, Kleinberg, J. M., and Tardos, É. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD, 2003.
Chen, Y. and Kuhnle, A. Approximation algorithms for size- constrained non-monotone submodular maximization in the 29th ACM
deterministic linear time. In Proceedings the SIGKDD Conference on Knowledge Discovery and Data Mining, KDD, 2023.
Kuhnle, A. Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Advances Neural Information Processing Systems 32: Annual
Chen, Y. and Kuhnle, A. Practical and Parallelizable Al- Submodular Maximization
gorithms for
10

---

Sublinear Adaptive Algorithm for Submodular Maximization
Conference on Neural Information Processing Systems 2019, NeurIPS, pp- 2371-2381, 2019.
Leskovec, and Krevl, A. SNAP Datasets: Stan-
ford large network dataset collection. http://snap. stanford. edu/ data, jun 2014.
Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure large networks: Natural cluster sizes and the absence of large well-defined clusters. In- ternet Math., 6(1):29-123, 2009.
Mirzasoleiman, B., Jegelka, S., and Krause, A. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium Educational Advances in Artificial Intelligence (EAAI- 18), New Orleans, Louisiana, USA, February 2-7, 2018, 2018.
Mitzenmacher, M. and Upfal, E. Probability and computing: Randomization and probabilistic techniques in algorithums and data analysis. Cambridge university press, 2017.
Nemhauser, L. and Wolsey, L. A. Best Algorithms for Approximating the Maximum of Submodular Set Func- tion. Mathematics of Operations Research, 373):177-188 1978.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. An analysis of approximations for maximizing submodular set functions-L. Mathematical Programming, 14(1):265- 294, 1978.
Prajapat, M., Mutny, M., Zeilinger, M. N., and Krause, A. Submodular reinforcement learning. In The Twelfth International Conference Learning Representations, ICLR, 2024.
Rozemberezki, B. and Sarkar, R. Twitch gamers: dataset for evaluating proximity preserving and structural role- based node embeddings. 2021.
Rozemberezki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding, 2019.
Tschiatschek, S., Iyer, R. K., Wei, H., and Bilmes, J. A. Learning mixtures of submodular functions for image collection summarization. In Advances in Neural Infor- mation Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, NeurIPS. 2014.

---

Sublinear Adaptive Algorithm for Submodular Maximization
A. Technical Lemmata
Lemma A.I.
S log(r) S x - 1,
Vx > 0
x x+1 2 ;
Vx E R
(1 - 1-=x)=11 2e my
Yay 1
Lemma A.2 (Chernoff bounds (Mitzenmacher & Upfal, 2017)). Suppose X1, ... X, are independent binary random
variables such that IP [X; 1] = Pt. Let μ Sim Pt, and X Ei=1 X₁. Then for any ō 2 have
P 2 (1+0)p1 Se $
(6)
Moreover, for any S < 1, we have
-1 8) S 4
Lemma A.3 (Chen al. (2021)). Suppose there is a sequence Bernoulli trials: X1, X2...., Xa, where the success probability of X; depends on the results of the preceding trials Xi...., X,-1- Suppose holds that
P X = 1 X Iı, X2, = 02, X xi-1] 4
where 77 0 is constant and ø1, ...... -i-1 are arbitrary.
Then, if Yi..... Yn are independent Bernoulli trials, each with probability of success, then
P
Xi
< b
< P
Y < b
where b is arbitrary integer.
Moreover, let A be the first occurrence of success in sequence X,. Then,
[[]] 1/n.
B. Propositions Submodularity
Proposition B.1. Let {A1, Az,..., Am} be m pairwise disjoint subsets Uf U, and B E U. For any submodular function f: 24 + R2o, it holds that
1)
Σ () 24
U A. B
iE|m]
2)
Σ {
(m 1)f (B).
kE(m]
Proposition B.2. Let A = {ai,................... }m} and A, = (a....., a for all i E [m]. For any submodular function f 24 + R20, let B arg max Σ A (a, A;-1). 1). It holds that f (B) 2 (1 1.) f (A).
BC BCA.(
Proposition B.3. For any submodular function f 24 - Rzo. let O₂ = arg mggxxxcu.jssh, (S) and Oz arg max Ssu o (S). It holds that
kn (O2).
[(0)) 2
ki2
12

---

Sublinear Adaptive Algorithm for Submodular Maximization
C. Pseudocode and Theoretical Guarantees of INTERPOLATEDGREEDD (Chen & Kuhnle, 2023)
In this section, we provide the original greedy version of INTERPOLATEEDRREDDY (Chen Kuhnle, 2023) with its theoretical guarantees.
Algorithm 7: INTERPOLLATDDRREEDD///...
An -ppp: appproxmmmtionnn algorithm for SMCC
Input: oracle f 24 + R20, constraint k error E
Initialize: +- 2: + 1, Go 9
for m -- to do
{a1. ] f- top elements in Gm-1 with respect marginal gains on Gm-1
for to in parallel do
if u = 0 then Au, & G U ). for all 1 sise
else A,,, + G {a,), for all sise
for j - 1 to k/L
do
for - 1 to do
8
Jj -- arg max SEU (UL Au.)) A (x: Ans)
Au,i + Au,i U {
9
10
Gm f a random set in {Aui < < u
return Ge
Theorem C.1. Let 2 O, and (f, k) be an instance of SMCC, with optimal solution value OPT. Algorithu INTERPOLAT-
EDGREEDY outputs a set G5 with O (22k)) queries such that OPT < (e (e+ (G+)] with probability (e+ (1+1)"", where
2e
+1.
D. Analysis of Simplified INTERLACEGREEDY (Alg. 8)
In this section, present detailed approximation analysis of the simplified INTERLACEGREEDY (Alg. 8), demonstrating that while the algorithm removes the initial guessing step from its original formulation, it maintains the same theoretical approximation guarantees.
Algorithm 8: A deterministic 1/4-approximation algorithm with (nk) queries.
Input: evaluation oracle f' 2d R2z, constraint &
Initialize: A
<- 0. add 2 dummy elements the ground set
for i + to A: do
arg maxxEI((AAB)) A (x AA)
A A a
b + arg max A [z] B)
B t b
return S t arg mf (f).f (B)}
Theorem D.1. With input instance (f. 1e), Alg. 8 returns set S with O (kn) queries such that (S) 2 1/4f
Proof of Theorem D.I. Notation. Let be the i-th element added to A, and A, be the set containing the first elements of A. Similarly, define b, and B, for the solution B.
Since the two solutions A and By are disjoint, by submodularity and non-negativity,
(() S (OU Ax) + (OU B&).
Let it max [k]: A, S }} and = max E [t] Bj S O). If either i* = k or - = k, then f(S) = (0). In the following, we consider i < k and j < & and discuss two cases of the relationship between i' and j (Fig. 3).
Case 1: 5 < 5 k; Fig. 3(a). First, we bound f (0 U As). Consider the set Ô = O (Ag U BB.). Obviously, holds that |0] < k 2*. Then, order Ô as (0r, 02,...) such that o, & B for all S |O]. Thus, by the greedy
13

---

Sublinear Adaptive Algorithm for Submodular Maximization
selection step in Line 2, it holds that A (a=- A A (a: 11++-1) for all S 1Ò). Then,
f(OUAs) - = AA) + A (0) As)
1
(B(+)) +
Σ
A (0: Ax))
1
(f( +
Σ
A (o: Acts--1)
(B+)+
Σ
P (a:
(A:-),
1-++1
where the first three inequalities follow from submodularity; and the last inequality follows from A (aits- 11+
A (os -1) for all 1 < s 1Ò), and A (a: A{-1) 2 0 for all i E [k].
f
A
B
B
(a) i" 5
(b) 1" 5
Figure 3. This figure depicts the components of solution sets A and B in Alg. The black rectangle highlights sequence of consecutive elements from O that were added to the solution the initial. Red circles with cross mark signifies the first element in A or B that is outside O.
Next, we bound f f(OU Consider the set Ô 0 (A,, Bg). Obviously, it holds that |0] S k- --. Since
i" max E [k] A, S O}. we know that 41 g O. Thus, we can order |Ô] as (2,,02,-. such that 0; & Ai+a- for all < i < 10). Then, by the greedy selection step in Line 4, it holds that A (bets- B141=-1) 2 A (o, B,++-11) for all
1 < i S [0]. Following the analysis for f (O U A), we get
f Bx) - f (Bx) < A (A,
B&) + A (o)
Bx)
10
S +
Σ (ox B&)
|
(A())) +
Σ
A (a. B14
(A,))
Σ *=*++
A (b: Br-1) = (Ax) - f (B..).
Case 2: 0 S jr < < k; Fig. 3(b). First, we bound f (O U As). Consider the set Ô = 0 (As U Bj.). where 1Ô S k --j" j" - 1. By the definition of j", we know that by-+1 & O. Thus, we can order Ô as {0r, 02 such that o; g Bi+j-
for all 1 < <i< < [Ò]. Then, by the greedy selection step in Line 2, it holds that A (a:4j++1 (A45.) 2 A (o: A1ag-) for all
1 I i [Ò). Following the above analysis, we get
f(O (.) - 1 (Ax) < (B, A + A (0) At)
10
< f + Σ A 1o, A+)
14

---

Sublinear Adaptive Algorithm for Submodular Maximization
101
( + Σ
(os Asts-)
==1
(B +
Σ
A (asl (B;
1=j++2
Next, we bound/ f (O U BB). Consider the set Ô = (A U BB), where 1Ō S -- Then, order Ô as (2..02
such that of & As+5" for all S i < [Ò]. By the greedy selection step in Line it holds that A (bs+g- Bi+j+-1) A (os B1) Then,
B&) (0) B₂) ((OUBB) (Bx) S (A
101
f (Ag+4)) +
Σ
A (o, BB)
101
f (Ag++1) +
Σ
A (o,1 B1-
i=1
k
S (A(A41)) +
Σ
A (b:
(B;)).
1=1+41
Therefore, in both cases, it holds that
(OU B&) (2) ( (S)
E. Analysis of Simplified INTERPOLATEDGREDD (Alg. 2, Section 3)
In the section, first provide key Lemmata and their analysis in Appendix E.1 for the when & mod e = 0. Then, conclude with an analysis of approximation ratio in Appendix E.2.
E.1. Proofs of Lemmata for Theorem 3.1
In what follows, we address the scenario where & mod = 0 and Alg. returns solution with size exactly k.
Notation. Let G:-1 be G at the start of i-th iteration in Alg. 2, A, be the set at the end of this iteration, and a.j be the j-th element added to A, during this iteration. Lemma 3.2. Fix Gę-1 for iteration of the outer for loop in Alg. 2. Following the definition in Claim 3.1, it holds that
1) A (A: G.-1) 2 A (b) v1 < S,
2)
(A G. A (Ai, G.-1))
2 A (O:z AA,) + A (0,, A.) VI h < <6
Proof of Lemma 3.2. Recall that Ar, is A after j-th element is added to A at iteration i of the outer for loop, and G max {c E [m] : At. \ G C Ot).
First, we prove that the first inequality holds. For each I E [f]. order the elements in O₂ as {or, 02..0 such that o, & Ar, for any < j < |O:]. Since each o, is either in A₁ or not in any solution set, it remains in the candidate pool when at, considered be added to the solution. Therefore, it holds that
A (ar, A15-1) 2 A Atz-1).
15

---

Sublinear Adaptive Algorithm for Submodular Maximization
S
An
2, a (2.l/a))
(a//4.)
Ag
Figure 4. This figure depicts the components of the solution sets Ai, and At.. A blue circle with a check mark represents an element O, while circle with a cross mark represents an element outside of O. The grey rectangles indicate sequence of consecutive elements in O. The pink rectangles indicate the corresponding elements used to bound A (O;, Ad, ) or A (O,, Ar₂). It is illustrated that (Oi, (Aa)) + (O1, An) S (Ar, Gi-1) + A (Atz G,-1) under both cases.
Then,
m Σ A (ar.) Arj-1) = AA
(O) Σ (o, EyEO;
E Σ (o, Atj-1) S oyEO,
j=1
where the first inequality follows from Proposition B.1, the second inequality follows from submodularity, and the last inequality follows from Inequality (8).
In the following, we prove that the second inequality holds. For any relationship between o7 and of in the following.
S l S l/ S E, we analyze two cases of the
Case 1: of, S c; left half part in Fig. 4.
First, we bound A (O,, At.). Since cf, S. m, we know that the (cf, + 1)-th element in A,, \ G is not in O. So, we can order the elements in Oi, AA1,0, as (01,,0,...) such that 0j & Ats.r +j+1- (Refer to the gray block with a dotted edge in the top left corner of Fig, 4 for Ot, Since each oj is either added to Ar, or not in any solution set, it remains in the candidate pool when 0/2,t, +j is considered to be added to Ar,. Therefore, it holds that
A (i2. +s Alairi +1-1) 2 A ((0)) Aig.et, Ma.ce,+511) t5-1) v1 sism G.
Then,
A (Or, Aia) (Alset
Als)) +
Σ
A (oy1Ang (A,)
(Proposition B.
o,E0i, Idi
5 Alsin
Gi-1)= + Σ
A (0s Alanot +5-1)
(submodularity)
ofEOi, Vnn
m-c/,
< f (An.et) ) - - -G +
Σ
(abet to Alausi +3-1)
(Inequality (9))
1=1
< ʃ (A - (G+-)) { (Ais.T,)
Similarly, bound A (Oi,1 Ar,) below. Order the elements in Oi \ Aln.st for 02, such that oj & Ais.et, +j- (See the gray block with a dotted edge in the bottom left corner of Fig. 4 for O1..) Since each 0j either added to At, or not in
16

---

Sublinear Adaptive Algorithm for Submodular Maximization
any solution set, it remains in the candidate pool when 0f1.of, +s is considered be added to A Therefore, it holds that
A ( (an.oi +s| Alsici (o-t(++1)) 2 A 2(0) An.o),+5-1) S G. و
(10)
Then,
A (0,, SA (Asici
A1,)+ +
Σ
A (oyl AA,
(Proposition B.1)
1,2 Al2ist,
s A Alarri Gi-1) +
Σ
{03 Alsno
(submodularity)
0:E012 A12iot
m m-
$ f (Als)e,) ) - -5 (G + Σ
A (aliet Alnos,ti-1
(Inequality (9)
S (As - (G (((,) - (AlisT,)
Thus, the lemma holds in this case.
Case 2: of > oj right half part in Fig. 4. First, we bound A (O;, |Aa.). Order the elements in O₁, \ At,, -1 as for, 02,...,.... such that of & Als.et, +J- (Refer to the gray block with dotted edge in the top right corner of Fig. 4 for Ot Since each oj is either in Ad, or not in any solution set, it remains in the candidate pool when al2,et, +i considered be added to Ar,. Therefore, it holds that
A (au.ri, +i Alartt+i-1) 2 2
A sissjssi m -G, - 1.
(11)
Then,
A (Oi,1 |A,) S A (Ali .1, +1 Ala) +
Σ
A (Aa))Ai))
(Proposition B.1)
ojEDi -
$ A (Al, +1 Gi-1)
Σ
A A(03| Alann1izt-- +j-1
(submodularity)
ojE0i AeLisiz
m- -1
< / (An +1) - (G(-i) +
Σ
A (12.itz -j Manitzzt-11
(Inequality (11))
#=1
< f (An,,,+1) +1 - ((G.- + (Atz) (Alarit)
Similarly, bound A (O:,1 AA;) below. Since of c%2, we know that the (of, + 1) element in Ar, \ G not in O which implies that [O;₂1 < m. So, can order the elements in Ot, A as (0r ... . such that oj & Ala ti for each 1 < j S m . (See the gray block with a dotted edge the bottom right corner of Fig. for Oi
When 1 < j m c since each 0j is either in Al, or not in any solution set, it remains in the candidate pool when al1,0 +i+1 is considered to be added to Ar, Therefore, it holds that
A (ah +5+1 An.eit+)) 2 a (0) A . vA . ct
(12)
As for the last element om ot in 01, \ AAtaee we know that Om-ei is not added to any solution set. So,
m
1 A (Ar, (G,1)
Om-oi (11) 5 m i=1
(an Anj-1) m
(13)
17

---

Sublinear Adaptive Algorithm for Submodular Maximization
Then,
A (Otz |Ar) S A (Aerrt A1s) +
Σ
A0j
(Proposition B.1)
of orE0r Adigiciz
S Alsrri
Gi-1) +
Σ
A
Annoists
(submodularity)
0,5012 Algi
m- o2
f (Awnt)) ) -G(-)) +
A (alenig jit1 Alrinits)) + - (Au, G.-1) (Inequality (L1))
-s S (Ansst))) -((Gi-) + (( ( (Mir)))(Aassttt) + - a (Ai,
-Ai, G
(O1zl m)
Thus, the lemma holds in this case.
Lemma E.1. For any iteration of the outer for loop in Alg, it holds that
2 I हमं 1 (1
m (1-m+
(1-+)ELIOUG_))) (G
Proof of Lemma E.I. Fix G5-1 for an iteration i of the outer for loop in Alg. 2. Let A be the set after for loop in Lines 3-6 ends (with m iterations). Then,
Σ CO 41) <
(O +
Σ (O A12) + (Oi, At)) 1shebse
(Inequality 2)
LE|9
(1+ m
< Σ
A (Ai Gi-1)
Σ
(A (Ar, GG-1) A (Ai, G.-1))
(Lemma 3.2)
LE|T
1shsbse
s l
1+ m
1
Σ
(A (A-1) Gr-1)
LE(A]
(1+ m
(L 11)
Σ GAI))) -f
EE(
(f (f-
(14)
where the last inequality follows from Proposition B.1. Then, it holds that
([J - / (G:-1) Gi-1]= 1 Σ (Ai
LE(A]
(1-1)
m
7 m m
(Inequality (14))
By unfixing G the lemma holds.
Lemma E.2. For any iteration of the outer for loop in Alg. 2, holds that
( 2 (1 (1- El (OUGGGG-
18

---

Sublinear Adaptive Algorithm for Submodular Maximization
Proof of Lemma E.2. Fix G the beginning of this iteration. Since {Ar \ Gi-1hett are pairwise disjoint sets the end of this iteration, by Proposition B.1, it holds that
(OU())))) G--1)= = 1 Σ [(OUA) (1-2) ( (OUGii)).
Then, by unfixing G;-1, the lemma holds.
E.2. Proof of Theorem 3.1
Theorem 3.1. With input instance (f, e) such that E O (c-1) ez
and k 2
2)et-2)
Alg. 2 returns set G with
66 06-
O (km/E) queries such that [f (G)) 2
Proof. By Lemma E.1 and E.2, the recurrence of [f (G.)] can be expressed as follows,
1
m (1-
)) B (G: + e+i
1 (1
m +1 (1-+1)
) (1-2) 2) s(0)
E ( 2
1
8+1
1 (1
m +1 11) (1- 1 2) ((0).
2 E ()-i)+
By solving the above recurrence,
1
1 41- f())
Blf Bff(G))
1
1+]
m
+ 1
8-1
1
(0)
(Lemma A.1)
1+1 1
m +
1
2
(1
1
L
e (O)
(m k
1
k
1
1-
1
2
2l 4
e f()
1
{
k)
M
(e-1 s) (O).
(E
2 k 2(8-2) 2e 65
l mod & 0, the approximation ratio holds immediately.
Otherwise, when & mod é > 0, the algorithm returns an approximation solution for a size constraint of é. Proposition B.3, it holds that
[g]. By
f(0') 26 l- i /kf 2 --0,0000''''
= arg max f(S).
(15)
In this case, the approximation ratio still holds.
F. Preliminary Warm-Up of Parallel Approaches: Nearly-Linear Time Algorithms
Kuhnle (2019) introduced fast version of INTERLACEGRFEDD replacing the greedy procedure with descending threshold greedy procedure (Badanidiyuru & Vondrák, 2014) to achieve a query complexity of O (n log(k)). This same technique was subsequently employed in INTERPOLAATEDGREEDD (Chen & Kuhnle, 2023). this section, we present simplified versions of both algorithms, incorporating the blended marginal gain analysis strategy introduced in Section 3. These fast algorithms serve as building blocks for the parallel algorithms introduced in this work.
19

---

Sublinear Adaptive Algorithm for Submodular Maximization
Algorithm 9: A nearly-linear time, (1/4 - -ppproxiaaiit algorithm.
Input: evaluation oracle f 2d Rzo. constraint k. emror
Initialize: :A 0, B 0, M +- max ((=)), + M, 72 M
for
to k do
while 7I
=M and |A| k do
if 3a E U (AUB) B) x.1. A (a A) 2 then
A + aa
+
break
else + (1 -1-18 -1-
while T2 EM and B k do
if 36 NEU / B) s.t.
then
B+B b
break
else (1 s)
return S < arg max f (B))
E1. Simplified Fast INTERLACEGREEDY with 1/4 - Approximation Ratio (Alg. 9)
Theorem F.1. With input instance (f, s),, Alg. 9 returns S with (n (olo(())/e) queries such that f f()) 2
(
Proof. Query Complexity. Without loss of generality, analyze the number queries related to set A. For each threshold value T1, most queries are made to the value oracle. Since is initialized with value M, decreases by factor of 1 and cannot exceed cM " there are at most logi-s (E) + possible values of 71. Therefore, the total number of queries is bounded as follows,
#ueeries 2 n (logi-c 1081-c(2 (6) +1) s 2000 (n (og)(())/))
where the last inequality follows from the first inequality in Lemma A.1. Approximation Ratio. Since A and B are disjoint, by submodularity and non-negativity,
+ fO) < (( (OUB).
(16)
Let a, be the i-th element added to A, A; be the first i elements added to A, and The be the threshold value when a, is added to A. Similarly, define by, B,, and bb. Let i" max(i < |A| A; S O} and j max(i < [B]: B, S CO. If either
i" = k or j = k. then (S) = f (O). Next, we follow the analysis of Alg. in Section to analyze the approximation ratio Alg. 9.
Case 1: O. 8" S k; Fig. 3(a). First, we bound fOu A). Since B,. CO by submodularity
((OAA) f (A) S (Br () + (O) \ B, () (B+)
Σ
(o)
(17)
(EUB(AU
Next, we bound A [ol A) for each o E 0 (AU
Let Ô 0 ON(AAU B+.). Obviously, it holds that Ö S i* Then, order Ô as for, 02, such that o, & B1 for all iss ÓO. If [ the algorithm terminates with Ti E Thus, it follows that
EM
A (o: (o) < k(1 - 2)
A - 1" <is
(18)
Next, consider tuple (o,, 0,407, A for any < < min [Ō) - 17). Since G++s" the threshold value when a,+4* is added, holds that
A (aits. 114+-1) 2 न. RM v1 Si S | i"
(19)
20

---

Sublinear Adaptive Algorithm for Submodular Maximization
Then, show that A (0s -1) < 1 /(1 - E) always holds for any S i S min([O),1A]) -i)
Since M max f ((x3), if 7| T 2 M, it always holds that A (or A++++-1) < (M Ti 0++ /(1 E). If
1 ai+i" < M, since & -1 is not considered to be added to A with threshold value "/ /(1 E). Then, by
submodularity, A (o: A44++ < Pc+e" /(1 c)). Therefore, by submodularity and Inequality (19), it holds that
A (0 A) - (o -14= < A (asts A44++-1) - s), s min min( )
(20)
Then,
S(OU (4)
E (o)
(EOV(AUB..)
min((ó1,AA)--
A (atts (4 -)) + eM
S (B())
Σ
1-
< - -
(21)
where the first inequality follows from Inequality (17); the second inequality follows from Inequalities (18) and (20); and the last inequality follows from M S (O).
Second, we bound f fOO U B). Since A;- S O, by submodularity
(OUB) - f (B) & A B) + +A(0) (B)
E (EOA(BU);))
A B).
(22)
Next, we bound A [o) B) for each E (O\(BU,)))
Let Ô OB A,-). Obviously, it holds that Ö k- Then, since a, O, can order Ô as (2,,02.... Thus, it follows that
such that og Aipr, for all 1 < i 1Ò). If [B] < k. the algorithm terminates with 72 k
=M
EM
A (o: B) <
- -i<
(23)
1(1 - 8)
Next, consider tuple (or, b B for any <is < min([1], ). Since T2 be4s is the threshold value when buue- is added, it holds that
A (br-e0 Bi+i 1) T2 1 V1 S < [B| - i*
(24)
Then, we show that A (os Bu+r -1) < T2
h445 /(1 E) always holds for any 1 S S min ( [B), }.).
Since M = max f (fx)), if T2 but1* 2 M, it always holds that A (o, B1++-11) < M/(1 -) S T2
bit** /(1 E). If
bits" < M, since o & A 0g is not considered to be added to B with threshold value T22 bit+" /(1 1 e). Then, by T2
/(1 E). Therefore, by submodularity and Inequality (24), it holds that submodularity, A (o: B1)+-11 < T2
bare"
A (o:1 B) < A (o: B A (b.-+ (B+r s), v1 < < min {*
(25)
Then,
(B)
Σ
B)
(EO\(BUA,-)
min((01)18)--
<A(++)++
Σ
A Alb+s B (1- + EM
1-8
_1 (A,)) + (B) (0))
1
<
(26)
1-E
21

---

Sublinear Adaptive Algorithm for Submodular Maximization
where the first inequality follows from Inequality (22); the second inequality follows from Inequalities (23) and (25); and the last inequality follows from M S (O).
By Inequalities (16), (21) and (26), it holds that
- S 1-8
2s (0)
S(0)
(A(A)+ + 1-8
-f(5) 2
1
5
8 f(0)2 2 1
[ - f(0)
f(0)
(E < 1/2)
4
2(4 - 2c)
Case 2: 0 S J <i- k; Fig. 3(b).
First, we bound fOU A). Since By: S O, by submodularity
[OU A) (4) < A By- 4) - (0) \ B5- (B)-))
Σ ()) OEO3(AUB,).)
(27)
Next, we bound A A) for each o E (AUBB.)..
Let Ô = 0
Since 1* }ン 2 0, holds that 10 S k j" - Since by.41 & O, we can order Ô as {or, 02, such that o; & Bit5*, for all that
S < Ö If ||| < k. the algorithm terminates with Ti < =M
Thus, follows
k
EM
A (o; A)
k(1 - 8) A|AI 6r - 1 -
(28)
Next, consider tuple (o;, 0:45' +1, A(ts)) ), for any Si min ( (0 |/|1 -j" - 1}. Since T| -1--1++ is the threshold value when 0i4j-=1 1 added, it holds that
A +1 A(ts+) 1 0++5++ 4A iis A - 5²
- 1.
(29)
Then, we show that (0: Aits*) ) < TI +1+/++1 +1 /(1 - E) always holds for any sis - -"
Since M max,cu f [[x]), if T1
(1) 0:45541 2 M, it always holds that A (o; A4.))) < () $ 1 -,445~11 /(1 E). If
4:43-44 < M. since o & Bi+j*, 0 not considered to be added to A with threshold value T, (11-5"/(11- =). Then, by
G:13"11 11 /(1 - e). Therefore, by submodularity and Inequality (29), it holds that submodularity, A (o: A(+j.) < TI
A (0: A) $ A (0: Astj-) A (a ( A44)) - v1 ta < min(/O], - -5" -1).
(30)
Then,
Σ
(ol
(EUB()),,.))
min(|O[/A|
{B(
Σ
A | A4+))) /(1 =) E) +
EM
1-6
< - 1-c
1
(31)
where the first inequality follows from Inequality (27); the second inequality follows from Inequalities (28) and (30); and the last inequality follows from M < (O).
Second, bound f (OUB) Since Ay++1 C O, by submodularity
f(OuB) - f (B) < A (AA B) + A (0 1)
Σ
()
(32)
(BUA(
Next, we bound A (o) B) for each E 0 (BU A1.41).
22

---

Sublinear Adaptive Algorithm for Submodular Maximization
Let Ô = 0 Obviously, it holds that |Ò k j-j" -1. --. Then, order Ô as (01, 02....) such that og & Apts*
for all 1 s [Ō) If [B] < k, the algorithm terminates with 72 < SM A
Thus, it follows that
E.M
A (o: B)
VBB - J" - 1 -
(33)
k:1 - 8)
Next, consider tuple (os: be+5*, 11), for any s < min min([O],|BB] - j - -1. Since 72 b,1s" is the threshold value when bypj. is added, it holds that
A (bets- Bets+-1) 2 T2 bass 1A S i < B 5 1
(34)
Then, show that A 1o < 72
h445" /(1 - E) always holds for any s i S min ( (10), -5" -1}.
Since M = max f (1x3), if T2
bets" 2 M, it always holds that A (o: B1+5~-1) < M/(1 -) S T2
b / E). If
T2 dits" < M, since o & Acts', 0f is not considered to be added B with threshold value T2 84ts" /(1 E). Then, by
submodularity, A (o: -1) < T2 b/-s" (1- Therefore, by submodularity and Inequality (34), it holds that
B) S A (o: Bea < A (bi+g (Bet)BBB) - sis min( [B] - j" - -}. (o:
(35)
Then,
- f( < ((
E
B)
8EO1 (BUA
minf min((01111155-111
eM
$ (Ap++))
Σ
A (bi+3- Bi+5- - =) +
1 1-E
$ - (
(B)
(36)
where the first inequality follows from Inequality (32); the second inequality follows from Inequalities (33) and (35); and the last inequality follows from M S (O).
By Inequalities (16), (31) and (36), it holds that
S(0) S 2
2s
(B)))
+ 1 1- (0)
1-
(S 2 4
1 5
5(0) 2 (1
4 (4-))10) 1(0)
(s < 1/2)
2(4 25)
Therefore, in both cases, it holds that
1 - f f0) f())
F.2. Simplified Fast INTERPOLATED with 1/e - & Approximation Ratio (Alg. 10)
Theorem F.2. With input instance (f, k, E) such that - 0 (: ( 1 ce G2 with O (nlog(k)/e)) queries such that (Gt) 2 (1/e e)) (0).
and k 2 cet-1 Alg. 2 (Alg. 10) returns a set
2(2-))²2
Proof. When le mod > 0, the algorithm returns an approximation with a size constraint of E- [ where by Proposition B.3,
f(0) 2 1 (I- 110) =
arg max
f f()).
(37)
sgu.
23

---

Sublinear Adaptive Algorithm for Submodular Maximization
Algorithm 10: nearly- time, (1/e- - approxxmmatinnnnn algorithm.
Input: evaluation oracle f: 2d R20, constraint k error &
Initialize: Gg <- 0. 2. m 12] e - af I. M maxxeM / ((x))
for i <- to & do
4 M, vl [e]
A + G;- vl E [e]
for j - to m do
for - 1 to do
while 2 e'M and |Ai \ Gi-1l < m do
&
if 1c Eu (Ureja) Ar) s.1. A (al A1) 2 m then
8
A + At + break
9
else Ti < (1-E')m m')
10
G < a random set {AthEe
11
12
return Ge
In the following, we only consider the case where mod = O.
At every iteration of the outer for loop, solutions are constructed, with each solution being augmented by at most k/6 elements. To bound the marginal gain of the optimal set O each solution set A,, we consider partitioning O into & subsets. We formalize this partition the following claim, which yields a result analogous to Claim 3.1 presented in Section 3.3, Specifically, the claim states that the optimal set O can be evenly divided into & subsets, where each subset only overlaps with only one solution set.
Claim F.1. At iteration i of the outer for loop in Alg. 10, let G be G the start of this iteration, and A be the set the end of this iteration, for each 1 E [e]. The set O \ Gi-1 can then be split into é pairwise disjoint sets (Oi.... O₂) such that |O < and (O \ G;1) n (Ai \ G;-1) C O,, for all / e [8]
Next, based such partition, we introduce the following lemma, which provides bound on the marginal gain of any subset Ol, with respect to any solution set AI,, where < 4,,42 < f.
Lemma F.3. Fix on Gi-1 for an iteration of the outer for loop in Alg. 10. Following the definition in Claim 3.1, it holds that
1) () ((A ( e'M
v1 SisE
1-E! (1 (1)e
1
1 (A (Ar, G.-1) + (A,, (1- E')E
2
2) A (Ot, A,,) + (O,, (A,)) 1-E'
1+
v1 4144 < </ se
m
Followed by the above lemma, we provide the recurrence of [f (G.) and B[f(OuG)))
Lemma E4. For any iteration i of the outer for loop in Alg. 10, holds that
[OUG)) (1 (1-)) ([JUGG
1
e -())
2) Ef - (G.-1) 1+ i
m m+1)
T-
By solving the recurrence in Lemma F.4, we calculate the approximation ratio of the algorithm follows,
B[ (1- E (G
1
(1
((1-2) 1 1- S(0)
1 s'
(G.- 1)]
(1-
1+
+1
24

---

Sublinear Adaptive Algorithm for Submodular Maximization
1
E'
(1 1- (1-2)) S(0)
BB
2
+ 1-
m
+ +1
1-6
1
(1 (1---) 5(0)
e
1+ 1-2'
m + 1
1- e
1
1 1-
2
1
2
1 1- (1 (1-o1) f(0)
e'
1 1- k
f
k)
2(1 8'6
(
e
1--6 e
1-e (1 - - 1(0)
1 1- k
{
k
1
(1 (1-
(6-
e¹
(1 (1-E-1) 1(0)
(8 2 k²
2(1 20 -6'-
1 l-
ce
1
1- IV
(c-1 s)
(E' = 5
By Inequality 37, the approximation ratio of Alg. 10 e E.
In the rest of this section, we provide the proofs for Lemma F33 and F.4.
Proof of Lemma F.3. At iteration i of the outer for loop, let A be the set at the end of iteration i, at, be the j-th element added to A,, oÿ be the threshold value of 7i when at, is added to A,, and Ar, be As after at is added to A,. Let of = =maxfe E [m] Ar, \ G O
First, we prove that the first inequality holds. For each I [f]. order the elements in Or (2,,02,...) such that og & A for any 1 j S |A, \ Ge-al. and o, & A for any |A \ G.-1l < m.
When 1 S |A \ G.-1l, by Claim 3. each 0j is either added to A or not in any solution set. Since is initialized with the maximum marginal gain M, oj is not considered to be added to A, with threshold value T/ /1111 e')- Therefore, by submodularity it holds that
(0 Arg-1) < -
( S (an.s A1g- c'), S / |Ac G.-1l-
(38)
When |Ar \ Gi-il m, the minimum value of 7 is less than E'M, to be added to A₁ with threshold value less than e' M (I-E'p6- It follows that
Then, for any |A: \ G:-1l <j S m, og is not considered
&
E'M MA A Gi-1l <j S m.
A (oj Ar) < (1- E/DR
(39)
Then,
A (OO1AA)
Σ (o)
(Proposition B.
o,EO,
MAG-I
Σ
A (o At5-1)+
Σ
A (o, Ar)
(Submodularity)
Ø=1
5-|ANG 11+1
IANGI1I 1|
A Aaa. (als|Arg-1)
E'M
Σ
(Inequalities (38) and (39))
1-6¹
61-
F=1
A (Ar G
E'M
(1 - e'-
The first inequality holds.
In the following, we prove that the second inequality holds. For any 1 S 4 < la S l, we analyze two cases of the relationship between of and of the following.
25

---

Sublinear Adaptive Algorithm for Submodular Maximization
Case 1: oi S c left half part in Fig. 4.
First, we bound A (Ot, At,). Order the elements in Ot \ At,ee as (0,,02...., such that 0j & Ar, +J. (Refer to the gray block with a dotted edge in the top left corner of Fig. for Ot, of +j is greater than the number of elements added to At,, Al2,e,, ti refers to -t Note that, since An, Ot,, it follows that |O,, Ats,et, S G
When 1 و - Ar, \G-1I- - a since each og is either added to A,, or not in any solution set by Claim 3.1 and 712 is
initialized with the maximum marginal gain M, Oj is not considered to be added Ai₃ with threshold value 76 /11 e¹). Therefore, it holds that
+1
o
A (airoo +1 Atroo +i-1)
A (0s Alari, Alaoo,+)-11
LA VIsiS
|At GG-11-
(40)
5d
1
When |Ag \ Gi-nl < m and Atg AGiz1l to be added to Alg. Thus, it holds that
- c
<مs S m G. this iteration ends with ni < E'M and 0j is never considered k
E'M
A [o51A15 < (1- e')Rk'
M/Aiz \ Gi-il- o. <ism m m- T.
(41)
Then,
A (Oi, A1)) S A 5 (An,
111)+ +
Σ
A Al))
(Proposition B.1)
ojEOi, (A
Mig 101-11-91
m m-
S A ( (Asio
G--1) +
Σ
A 0g A Alenot, +5-1) +
Σ
A M0,1 Ata)
s=|Aiz 10--1--0 +1
(submodularity)
| Ma10,11100
A (alarz +i
Alangz +5-1) +5-1)
<$ (AAnr)))) - (Gi-1)
Σ
e'M
--
(1 (1-=% E
(Inequality (40) and (41))
SS (Ance,) - (G f(A)) -f -(Alaitt)) 1- gl
e'M
(42)
(1-e')e
Similarly, we bound A (Ot, (Ar,) below. Order the elements in Ot \ Al2,,7, as {0r, 02 02.... such that 0j & Abasst +J-1- (See the gray block with a dotted edge in the bottom left corner of Fig. 4 for Oig- If cj + - 1 is greater than the number of elements added to Aig. Ata.ct +j-1 refers to Aig.) Note that, since Aia. S O1 it follows that Or₂ \ AAg.ci | I m of
When 1 < j < Ar, \ GG-11 d,, since each oj is either added to AI, or not in any solution set by Claim 3.1 and n, is oi +5 /(1 (1-
initialized with the maximum marginal gain M, oy is not considered to be added to A,, with threshold value Therefore, holds that
T
+5 A (anee t1 A +5-1) T S
A (03 Ane 43-1
<
AI V | \ G--11- -f
(43)
1-
When |A, \ G. < m and A AG,-Il- ci <j S m cf this iteration ends with Ti, to be added to AG. Thus, it holds that
<
e'M
and 0j is never considered k
5'M
A (oz Al,) <
(1 e')k' MAAr, \ G--il- ci <j m -q.
(44)
26

---

Sublinear Adaptive Algorithm for Submodular Maximization
Then,
A (0/21 A,) S A (Aisce, (11)+ +
Σ
A (0,1AA,) A1,)
(Proposition B.1)
01 M42e
m
<A A Alseet
Gr-1++ +
Σ
A (03 (M107743-1) +
E
A (oz AA,)
j=1
s=|As, 10-al-o7, +1
(submodularity)
|A Gi-il-,,, A (ar tj Alrnet +3-1)
S (Als,c, - ) (G
E
E'M
1 1-
(1-E')
5=1
(Inequality (43) and (44))
(aan)-(((nnssi (Arise,
f {AA, -
Ss (Avsoii - -(G
+ E'M
+
(45)
6-6¹
(1 - 5²)e
By Incqualities (42) and (45),
1 1- (A_1,,),_))
/G,-1 + (Ai, GG:-1))+ + 2
A (O,, At,) + (O1, AA,) 5
(1 =')e
Thus, the lemma holds in this case.
Case 2: of > o right half part in Fig. 4.
First, we bound A (Oi, AAg)) Order the elements in Oi, \ A +1 as f0r, 00.,02....] such that oj & At,e +j. (Refer to the gray block with a dotted edge in the top right corner of Fig. 4 for Oi If of, + j is greater than the number of elements added to Ar,, Ah,st, +j refers to -t Note that, since An, +1 S Ot, it follows that (Oi AA +1/ S -c, 1.
When و |A,, \ G - e - 1, since each 0j is either added to Ad, or not in any solution set by Claim 3.1 and T22 is
initialized with the maximum marginal gain M, oj is not considered to be added to At, with threshold value T/ 42, /11=="). Therefore, it holds that
+s
a12.77, +i Al2. +5-1
A (03
T/2
< el
A1 vi Gi-1l c₂2 -1 1.
(46)
When |Ar, \. Gi-zl < m and |Ag \ Gi-1l- - ct2 - considered to be added to Atg. Thus, holds that
< j S m ct2 - 1, this iteration ends with The <
E'M &
and o, is never
e'M
A (o, Anx)) < (1 -1- =')k" MAA \ Gi-1l - - - 1 < S m - c/2 -1
(47)
Then,
A (Oi,1 Ar2) S A ( (Aric2 Als) +
Σ
(oj Aca)
(Proposition B.
ojE0i, /A12,st, 11
|Ag 1G--1---/---
m- -1 j= (eg GG-rl-
< A (Ahisi Gi-1)
Σ
A 0j
Aianoi +3-1)
A A(5z A1g)
(submodularity)
Aig (G--11-og
A
(12211 +i Alaniizz-1 ti-1
2 55(Aug))
(Als 1 - (G
Σ
e'M E')E
e¹
F=1
(Inequality (46) and (47))
27

---

Sublinear Adaptive Algorithm for Submodular Maximization
f (Alret)) ( f fAA)) f (Alarets)
E'M (1-E')
(48)
1-
Similarly, we bound A (O/al I Ar,) below. Order the elements in Oiz \ Al2,ct, as f0r, o2..... such that or & Alg +s- (See the gray block with a dotted edge in the bottom right corner of Fig. 4 for Otg- If ci2 + j is greater than the number of elements added to Al2. Ala.ci, +j refers to At.-) Note that, since Ats.et, C Ot... it follows that 1O Ataret, S m dz
When 1 j S |4, G - ci and Tú, is initialized with the maximum marginal gain M, 0j is not considered to be added to AI, with threshold value ci +-+1 Th
since each oj is either added to At, or not any solution set by Claim 3.1
/11 E'). Therefore, it holds that
+5++ A (ann +5+1 An,e Th
A ((: 0z 10 +)
1A MisislAn Gi-il - -1- -1.
(49)
1 g-
If |A, Gi-il= = m, consider the last element Om-ci, in O12 \ Al2.7 Since On Om-riz & A1₂ and Om- & Ali Om is not considered be added to Ar, with threshold value T1,/(11 E¹) for any j [mm]. Then,
A (om-cc An) < =
m -==1
Thp
m A (an A(.-i) A (Ai, Gi-1)
(50)
(1 E')m
(1 - E'Jm
When Ar, \ Gi-il < and AAr, \ Gi-il- G/2 considered to be added to Ar, Thus, it holds that
-l<j S m -g this iteration ends with 7n < E'M
k and oj is never
E'M
A (o, AAn) <
vIA \ Gi-1l - -c - <iisinn m d.
(51)
(1 (1-)
Then,
(Oiz Ar,) S S (Als.ct
Ans) +
Σ
A (0,
(Proposition B.1)
os osE01a AAr.
< A AAssst (rn1)+ +
Σ
A Oj A A
A (oz AAi)
j=|de, iGi-1l-
(submodularity)
|4 1--11-
A (an, ti Al
< f (Arrrci)) ) - ((
Σ
A (Ai, |Ga-1)
E'M
+
(1 8')m
(1 =')6
j=1
(Inequalities (49)-(51))
[(Ai,) - (Arsri))
< (Ar2.t)) ((G-1))+ +
A (Ar, G:-1) (1-E')m (1))
e'M
(52)
1-
By Inequalities (48) and (52),
1
(1= 1 m
2 (A (A ( |G- + e1-e))
A (O,, Av2) A (Oi,) AN,
1 1-
Thus, the lemma holds in this case.
Proof of Lemma F.4. Fix on G at the beginning of this iteration, Since (Ar \ G5-1: 1i:1:le E [4] are pairwise disjoint sets, by Proposition B. it holds that
E [OUG)) G--1== 1 Σ (IOAA)
(1-1) ((OUG..).
28

---

Sublinear Adaptive Algorithm for Submodular Maximization
Then, by unfixing G5-1, the first inequality holds. To prove the second inequality, also consider fix on G at the beginning of iteration i. Then,
(O) A.)
Σ
Σ
(Oi, AA2))
(Proposition B.1)
[E(
Σ
A [0)) +
Σ (A A + +O,, (A,)
(Lemma F.3)
l
1shsbse
A [A1]Gr-1]
e'M
Σ
1-EE
(1- (1-E)e
(1+ 1
2
Σ
(A (A G--1) + + Gr-1) + (1 (1- =')e
(Lemma E.3)
1 1-
m
1shslsse
1
1 + m
Σ
A (A: Gi-1) (
(M S (O)
1- e¹
(c
1 - +
1+ {
)
1
E
Σ ((
1 - 8 f (0)
Ell
m
E
Ell
2 (L- ((--))((U---) ef
f (0)
Thus,
B[S (f Gi-1l= 1 E EA(AIGGL
(E(4
m (1-2) ((OUGL))- -f (Gi-1) 1 I- 1-g)(00)
E'
I+ - m1
(Proposition B.1)
By unfixing G;-1, the second inequality holds.
G. Analysis of Parallel Algorithms Introduced in Section 4
This section presents the formal analysis of our parallel algorithms introduced in Section We first prove fundamental lemmata for PIG in Appendix G.I, then establish its approximation guarantees in Appendix G.2, and finally analyze PITG in Appendix G.3.
G.1. Key Lemmata for PIG (Alg. 6, Section 4)
We provide the key lemmata achieved by PIG as follows,
Lemma G.1. With input (J,m, f, Tmin; <), PARAILEI.INTERRLAGFGRRRR (Alg. 6) runs in O (ee-2logg log Timin
.M
adaptive rounds and O [ (0=-2n (nn log MM (. )) queries with probability of 1 - 1/n, and terminates with {(A,,
1 E [4] s.t.
1. 4/ C AG, A (4 M) 2 A (A 11, 4A 11 16,, e, and (Ax : I [f]} are pairwise disjoint sets,
A(41 0)
2. A (O: AA) v (1-5)=
M-Taiin 1-8
41 515654
3. A (O,, A ) + A (O, Atr) - (1-))=
| (A (A) 0) A (AI, [))
2m-m 1-2
if if O1,, V1 54 </ <256. se
where O, C U, 10 < m, and 0, A = 1 for each j #
Especially, when ? 2,
29

---

Sublinear Adaptive Algorithm for Submodular Maximization
4. A (S A1) + (S) A2) S p-- (A (Ai, 0) + + (AI, 0))
2mm-Tii
AS CU S m.
I-c
Before proving Lemma G.1, we provide the following lemma regarding each iteration of PARALLEL Lemma G.2. For any iteration of the while loop in PARALLEE
(Alg. 6), let AI,o. Al.0- VL.0. Tı,0 be the set and threshold value at the beginning, and Ar, Al. V1, n. be those at the end. The following properties hold.
1. With a probability of at least 1/2, there exists I E [4] s.t. Ti < Ti, or mo = 0 or Vil = (1- 5 1V,o--
2. (Ar (AE [{] have the same size and are pairwise disjoint.
3. For each æ E Ar \ Aro, let 7/ be the threshold value when is added to the solution, Ar,a)) be the largest prefix of A that do not include x, and for any j E [4] and j * 1, As,(n) be the prefix of A, with (Ar()) elements if j < I, or
with |A((a))) - elements if > 1. Then, for any E [c], E A \ Ar,o, and y E u \ (Usete Alco)) it holds that
A y Al,())
4. A C A A Al Al.)) 2 A (Ar and A (Al Alo) 2 (1 - E)
a for all E [e].
Proof of Lemma G.2. Proof of Property 1. At the beginning of the iteration, if there exists / E s.t. |Vi.ol 26, then either 7ro is decreased to 7i and Vi is updated accordingly, or element 21 from Vi, is added to A₁ and A3, and subsequently removed from Ví,0- This implies that
VI S VV,ol - < (1 (1-2)
28 )
Vooll-
Property 1 holds in this case.
Otherwise, for all / L, it holds that VV,ol 2 26, and the algorithm proceeds to execute Lines 16-24. By Lemma 4.3, in Line 16, M 2 |V for each [ I. Consider the index j E where i; = i" Then, O, consists of the first i* elements in Vú by Line 21, By Lemma 4.5, with probability greater than 1/2, either i" = mg or at least an 5 5-fraction of elements V, satisfy A (ar A,) < Tj.0- Consequently, either my = after Line 24, or, after the UPDATE procedure in Line 4, one
22
of the following holds: Vil S (1 : VV,ol, T, < 7,00- Therefore, Property holds in this case.
Proof of Property 2. At any iteration of the while, either [7] different elements or [7] pairwise disjoint sets with same size 8" are added to solution sets {A, : : E f}. Therefore, Property 2 holds.
Proof of Property 3. At any iteration, if T. is not updated on Line 8, then prior to this iteration, all the elements outside
of the solutions have marginal gain less than - I- Thus, for any x E A \ Aroo y E u \ (Ureta A,,0). it holds that
7 T-c
A (y) AI,)))
by submodularity, Property 3 holds in this case.
Otherwise, if 7j is updated on Line 8, only one element is added each solution set during this iteration. Let Ai \ A For any j E [4] and j # I, it holds that A,,(x) A, if j < I, or Az(c)) As,0 if j > l. Since elements added to each pair of solutions in sequence within the for loop in Lines 7-13, by the UPDATE procedure, for any y ( (USera Arcco):
it holds that A (y) AL,e)) I-c- Therefore, Property also holds in this case.
Proof of Property 4. First, we prove A/ S A, by induction. At the beginning of the algorithm, Ai and A are initialized as empty sets. Clearly, the property holds the base case. Then, suppose that AL.0 C Ar,-- There are three possible cases of updating AL.o and Ar, at any iteration: 1) A/- = A/,o and A Ar,0. 2) A/ Al,0 + ø1 and A = Ar, + 24 in Line 12, or 3) A/ M/. U Sy and A, AI, U S in Line 23. Clearly, A C A, holds in all cases.
Next, we prove the rest of Property 4.
If 4 = A/.o and A = Ar,o. then A AA Ah.0) = A (Ail Ar,0) = 0. Property 4 holds.
If A/, and A are updated in Line 12, by submodularity, (m) Therefore, Property also holds.
A' Ai.)) = A (ar
A/.0) 2 A A(m AL,)) = A (A AA,) 2
30

---

Sublinear Adaptive Algorithm for Submodular Maximization
If ALo and Aço updated in Line 23, know that Ai Ai,0 U U/ and A At,o St. Suppose the elements in St and Sj retain their original order within Vi. For each x: E St let St,()) Vz)(z) and AI,(a) be the largest prefixes of St, Vi and A that do not include z, respectively. Moreover, let S(,(z) = S(.(x)) O Sj and Al,(z) AI,x) Ai. Say an element x E Si true if [x((=]] = true, where Bi [x]] is the i-th element in B if x is the i-th element in V/. Similarly, say an element St false if Bx[(=)] false, and none otherwise.
Following the above definitions, for any true or none element E St, by Line 21, it holds that St,(z) S Vi(a)- Then, by Line 5 and submodularity,
Ti (xr) if x is true element
A (xr AL(w)) A (x Aco S1,(2) 2 (xr Aro U ((())) 2
0. if at is none element
Since true elements are selected at first and 07 2 it, there more than (1 =)i² true elements in St. Therefore,
A (Ai) Al,u)
Σ
A < x Al,(o))
Σ
A (z/ A1,
zEAfiAf of is true element
A is none element
A (xr Al(o))
A ((x Al,(n)
=EA/tAf A/, is true element
xEA (f is none element
2 (1 - A) \ A (2) for any x Ar \ Ar.0
(1 =) Σ
(x)
AA,o
The third part of Property 4 holds.
To prove the second part Property 4, consider any false element x E St. By Line 21, it holds that Vl((z) = St,(a)- Then, by Line 6
A (ar AL,()) = A xx A1,0 UL()))))))
A (a Ar,0 U Vi, O.
(53)
By Line 22, all the elements in S \ S are false elements. Then,
(Ai) f (Ar,0)
Σ
A (ar
AL,))) (
Σ ZESIVSE
A ( AI,aa)
zES
A
(I)
A1,(2))
(Inequality 53)
xES{
Σ
A
x A(.wo)
(Submodularity)
zES(
(AA)
f (Al.o)
By Lemma G.2, we ready prove Lemma G.I.
Proof of Lemma G.I. Proof of Property 1. By Property 2 and 3 in Lemma G.2, this property holds immediately.
Proof of Property 2. For any / E [E]. since O n A; @ for each j * I, O₂ \ Ai is outside of any solution set. If [AA = m. by Property 4 of Lemma G.2,
A (0)1At) <
Σ
<
Σ (x)
(1)-))
(Property 3 in Lemma G.2)
SEA
(A
(Property 5 in Lemma G.2)
(1-
31

---

Sublinear Adaptive Algorithm for Submodular Maximization
If | < m, then the threshold value for solution A has been updated to be less than Tmin- Therefore, for any y E 0, \ Ar,
it holds that A (yl Ar) Jmin Then,
A (OH1AS
Σ Ayl -
mimmi
1-6
BEOAA,
Therefore, Property holds by summing the above two inequalities.
Proof of Property 3 and 4. Let ot, be the j-th element added Ar, o/ be the threshold value of n when dt is added to A,, and Ar, be A after or,j is added to A,. Let of max [m] : Ar, S Or).
In the following, we analyze these properties together under two cases, similar to the analysis of Alg. 11. For the case where t= 2, let O2 = \ A2, and O2 = 5 \ A1, unifying the notations used in Property 3 and 4. Note that, the only difference between the two analyses is that, a small portion (no more than & fraction) of elements in the solution returned by Alg. 6 do not have marginal gain greater than the threshold value.
Case 1: of S G left half part in Fig. 4.
First, we bound A (Oi, Aig). Consider elements in An,ei S Oi Let An,.i ( Oeg For each 1 S j S c since oj is added to Ad, with threshold value Ti and the threshold value starts from the maximum marginal gain M, clearly, oj has been filtered out with threshold value /1 -s.. Then, by submodularity,
(Al AAss) S (4(A (1s 0) - Σ j=1
Aop An.-i) S Σ /1 s). j=1
(54)
Next, consider the elements in Oi, \. AAneei, Order the elements in Oi, \ An, as for, 02... . such that of & Ari,i + (Refer to the gray block with a dotted edge in the top left corner of Fig. 4 for Ot, If of + j is greater than |Ac, Ar, +3 refers to Ar.)) Note that, since Aq, C Oig it follows that |Or, \ A S cf,
When S j S |4,1 - c since each 0j is either added to A,, or not in any solution set and n2 is initialized with the of +5 maximum marginal gain M, 0j is not considered to be added to A with threshold value T/2 /(1 - =) by Property 3 of Lemma G.2. Therefore, it holds that
d, +s v1
A (0, Ala <
7
Visj
|Ap1 -
(55)
1-8
When |Atal < m and |Atg of <j S m - cT,, the algorithm ends with Tla < Tmin and oj is never considered to be added
to Ar,- Thus, it holds that
A (0 Ar,)
Tmin
v|Atz1 - cg <j S m cT
(56)
1 1- E
Then.
A (Oi1 Ara) S A (Ar d +
Σ
A (osl Ara)
(Proposition B.
ofEOi, AA
A1z1-ci,
m-c
< A
(Asres
1 (0)+ + Σ
0g
Algnet +--1) +
Σ
A AAa))
(submodularity)
j=1
j= A Aigl-si, +1
4
|
T/2 1-8
<
Σ
+
Σ
+
Tmin
(57)
8
1-E
j=0t
where the last inequality follows from Inequalities (54)-(56).
32

---

Sublinear Adaptive Algorithm for Submodular Maximization
Similarly, we bound A (0/2 Ar,) below. Consider elements in Ata.e,, O Let Ata.e, (01,..., Oeg ). For each i S a since oj is added to At, with threshold value T/2 and the threshold value starts from the maximum marginal gain M, clearly, oj has been filtered out with threshold value T 72/(U E). Then, by submodularity,
A (Annet Ae.) S A
(5(AAs (Als.e 0)) (0)= Σ (0, Aba-11) S Σ 711(1-=)
(58)
Next, consider the elements in O12 \ Ala,ct, Order the elements in O12 \ Abace, as foi, 02,... such that oj & Ata,et +j-1- (See the gray block with a dotted edge in the bottom left corner of Fig. for Oty- If o + 1 is greater than |Ar Alasst, + refers to Atg-) Note that, since Ats,ct, S O12 it follows that Oi, Abseet, I m cf
When 1 S j < |A,1 - i since each 03 is either added to Ar, or not in any solution set, and nr is initialized with the maximum marginal gain M, 0j is not considered to be added to At, with threshold value T/ /(1 - =) by Property 3 of Lemma G.2. Therefore, it holds that
T d +s
A (0) os A <
visjS
|4al -
(59)
1-
When |A,, < m and |Ar,1 - G, < S m G/ this iteration ends with 7T < Tmin and 0j is never considered to be added
to Ar,. Thus, it holds that
Tmin 1/An, of <js m G.
A (03) Ar,)
(60)
1-
Then,
A (Otz A1,) S A ( (Arii (An)+ +
Σ
A Ar)
(Proposition B.
or o,E00 MAgist
1
m-
s A ( (Abrri, (0)
Σ
A
Oj
Alr t2-1) +
Σ
A A Ar,)
(submodularity)
j=MA, +1
1 |4
$ 1
Σ
m Tmin
(61)
1-E
1-
1=1
j=
where the last inequality follows from Inequalities 58-60. By Inequalities (57) and (61).
A
|Agg
j
A (Oi, Ar,) + A (Or, AA,))
12 +
2m Tmin
(62)
8
1-6
j=1
j=1
Case 2: ci, > of,; right half part in Fig. 4.
First, we bound A (O,, Ar,). Consider elements in An, +1 S Or,- Let An, = (oi...., +1)- For each
1 S j < G + 1, since oj is added to Ad, with threshold value Ti and the threshold value starts from the maximum marginal gain M, clearly, 0j has been filtered out with threshold value T. 7 - e). Then, by submodularity,
4/ +1
ci -1
A (Arr Ats) s (Aniee, 10) =
Σ
A (0,
Ahi-i) S
Σ
/11 - =).
(63)
33

---

Sublinear Adaptive Algorithm for Submodular Maximization
Next, consider the elements in O₁ \ An,,t, +1- Order the elements in Oi, \ \An.et, +1 as 02.......... such that of & At1, +J* (Refer to the gray block with dotted edge in the top right corner of Fig. 4 for O₁,- If ci + j is greater than [Aa) Arr,ef + refers to - Note that, since An +1 - Ot, it follows that [O,, \ A -1 S m cf 1.
When - j - Atg - o2 - 1, since each 0z is either added to Ar, or not in any solution set and T22 is initialized with the (iz
maximum marginal gain M, 0j is not considered to be added AI, with threshold value T/2 /(1 - E). Therefore, it holds that
c +s
A [0) A12,ct+t--1)
To
LA Sク
Gi-1l |Ai, \
a 1.
(64)
When |Atz < m and |Atz| - c22 - m 1/2
1, this iteration ends with 7/2 < Tmin and 0j is never considered to
be added to Aty. Thus, holds that
Tmin A Aigl
A (o3 AArz)
< 1 - 8
o/2
1/2 -1.
(65)
Then,
A (Or, A1,) S A ( (Aniot A1z) +
Σ
A (0,l Ava)
(Proposition B.
o2 2,50t, (A
|
m m=
< A An ()) +
Σ
A (o}
Als +3-1) +
Σ
A (o, Aia)
(submodularity)
j=|A121-08
< 6 Tr (1 [1+ +
Atgl
Σ
/ e)+
m. Timin
(66)
1-E
j=1
+= +1
where the last inequality follows from Inequalities (63)-(65).
Similarly, we bound A (O:₂1 Ar)) below. Consider elements in Ai, C Stg. Let Alg.ti, ( Ge J. For each
1 1 S Gg since oj is added to At, with threshold value 7/, and the threshold value starts from the maximum marginal gain M, clearly, 0, has been filtered out with threshold value 711((1= E). Then, by submodularity,
c/2 (0, 11))-11 S
%2
(Als.ci, AA.) s (Ass.e 0
10
>
// -E). E).
(67)
j=1
Next, consider the elements in Ot \ Ala.tt Order these elements {or, 02, .) such that oj & Alaret, +s- (See the gray block with a dotted edge in the bottom right corner of Fig. for Ozg. If cf2 + j is greater than the number of elements added to Alg. Ala.st, tj refers to Atg.) Note that, since Atg.rt, C Otg. it follows that |01, \ Alg S m %/
Furthermore, for the case where f= 2, as considered in Property 4, we have O S Ag and O₂ = S 3\ AA for given S C l where |S| I m. Since cf, > oi 2 0, it follows that oi 2 1, which implies O2 = |S A S m 1. In this case, it holds that 10t2 \ AA2.et, 5 m cf2
When 1 و < |A,1 ot2 1, since each o, is either added to Ad, or not in any solution set by Claim 3.1 and n. is oi +5+1 /(1 (1-e).
initialized with the maximum marginal gain M, oj is not considered to be added to Ar, with threshold value Tt Therefore, holds that
4 +i+1
A (03 An An), < 1-E
The
AI S - 1 -
(68)
If Ar,| m, consider the last element Om-e7, in O1, Atn
Since Om- & Al, and om-et, & Ar, On is not
34

---

Sublinear Adaptive Algorithm for Submodular Maximization
considered be added to Ad, with threshold value TH, /1 E) for any j E [m]]. Then,
Σ j=1 7
A
(om-riz Ais)
(69)
(1 8)m
Else. |Ar, < and this iteration ends with 77 added to Ar,- Thus, it holds that
EM k
For any |Ai - C/2- - < S m cz.0 oj is never considered to be
A (0g Ar,)
Tmin
A/An|
o/2 -1 j S m 4
(70)
1 1-
Then,
A (02z A1.) S A (AvosTs Ann)+ +
Σ
A
(Proposition B.1)
oyE0tz AAigitt
|Ag 1G--11-0,
m-
A (Alesii (0) +
Σ
A 0j
Als Als +
Σ
(o; A1,; if |Or,1 = m
j=1
s=1Ar 1G-11-of2
M4, \G--
m- 2/2
A (Alenns (0) +
A (oj
Alsiot +3-1) Al
+
A (oj Ar,); otherwise
j Arg io, 11-11
(submodularity)
12
|
1+ m
1
T +
m Tiin
if |0 m
E
1
E
1-
1=1
j=o +2
(71)
42
T
m- Tmin
otherwise
1-6
8
1-6-
J=1
j=ct2+
+2
where the last inequality follows from Inequalities (67)-(70). By Inequalities (66) and (71),
2m Tmin
1+
Σ
if 1010,1
11
l2
=
m
m
E
1-E
j=1
j=1
A (Oi,1 A1,) + A (Ot) 1A,)
(72)
A
|Ata
1
2m Tmin
+
T/a
otherwise
1-8
- 6
1=1
1=1
Overall, in both cases, if 10i,1 = m,
A1g
Algl
A (Or, |Aa) + + (Otz |
1+ m
1
1
Σ
2m Tiia T/2
+
2m Tmin
(Inequalities (62) and (72))
1-3 g
1 1-E
<
[+ m
1
(A (4h, 00) +
(Ai. (0)) +
(1 2)²
(Property 4 of Lemma G.2)
Otherwise, if [0zz < m,
A |
1
2m Tmin
A (Or, AA,)) + A IA))
1-6
Σ
T/
T22
+
1
(Inequalities (62) and (72))
|=1
35

---

Sublinear Adaptive Algorithm for Submodular Maximization
2m Tmin
8) (A (A), 0) + A (A 0)) + -
(Property 4 of Lemma G.2)
Property (3) and (4) hold.
Proof of Adaptivity and Query Complexity. Note that, at the beginning of every iteration, for any j E I, Vi contains all the elements outside of solutions that has marginal gain greater than Tj with respect to solution A,. Say an iteration successful either 1) algorithm terminates after this iteration because of mg 0, 2) all the elements in V3 can be filtered the end of this iteration and the value of Tj decreases, or 3) the size of V decreases by a factor of iz' Then, by Property 1 of Lemma G.2, with probability of at least 1/2, the iteration is successful. Furthermore, if Ty is less than Tmin- j will be removed from and solutions A and A13 won't be updated anymore.
For each j [e], there are at most logi-e ( (ruii) - e- log
possible threshold values. And, for each threshold value, with at most log1- + (+) - log(n) successful iterations regarding solution Aj. the threshold value Ty will decrease or the algorithm terminates because of mg = 0. Overall, with at most 2 log(n) log
M
Tiin
M
successful iterations, the
Tanin
algorithm terminates because of mng = 0 or I = 0.
Next, we prove that, after N (log(n) - log(n) log at least = log(n) log successful iterations. Then, X can be regarded as a sum of N dependent Bernoulli trails, where the success probability is larger than 1/2. Let Y be sum of N independent Bernoulli trials, where the success probability is equal to 1/2. Then, the probability that the algorithm terminates with at most N iterations can be bounded as follows,
)) iterations, with a probability of there exists Twin
M
successful iterations, or equivalently, the algorithm terminates. Let X be the number of
Timtn
M
[#iterations
NJ S
S 462 log(n))
Tiin
(0) I
M
P
Y < 4.2 log(n) log
(Lemma A.3)
Tmin
st2 2 louc Nw
(Lemma A.2)
(4lox())+882 lox(n) Lonk 10(102())1 Asog(w)) low
mmin
6 Tmin
Therefore, with probability of x2* loop.
the algorithm terminates with O (ee- (e===log(()
Ad Tmin
iterations of the while
In Alg. 6, oracle queries occur during calls to UPDATE and PREFIX-SELECTO on Line 8, 18 and 4. The PREFIX- SELECTION algorithm, with input (f.V, 8, T, c), operates with adaptive rounds and most |V] queries. The UPDATE algorithm, with input Vo, To:
To:e), e), outputs (V,+) with 1 log
adaptive rounds and most [V] logi
queries. Here, logi-c (I) equals the number of iterations in the while loop within UPDATE. Notably, every iteration successful, as the threshold value is updated. Consequently, we can regard an iteration of the while loop in UPDATE as separate iteration of the while loop in Alg. 6, where such iteration only update one threshold value Tj and its corresponding candidate set Vg. So, each redefined iteration has no more than 2 adaptive rounds, and then the adaptivity of the algorithm
should be no more than the number of successful iterations, which is (feg- =log(n) log M
Since there are at most
Twin
in queries at each adaptive rounds, the query complexity is bounded by O (63g-2)) (oggn)) log
Timin
G.2. Analysis of Guarantees achieved by PIG (Theorem 4.1, Section
In this section, we provide the analysis of the parallel (1/4 - e) approoximatio algorithm.
36

---

Sublinear Adaptive Algorithm for Submodular Maximization
Theorem 4.1. With input (J,k22 2, EM e)), where M max I (x), PIG (Alg. 6) returns {A1, A2) with O (e-1 log(n) n.) log(k)) adaptive rounds and O (e- log(n) (eg9n) that m (A1), f (A2) 2 (1/4-e)1 (O).
log(k)) queries with probability of 1/n. It satisfies
Proof of Theorem 4.1. The adaptivity and query complextiy are quite straightforward. In the following, we will analyze the approximation ratio.
Let S = O Lemma G.1, holds that
f (A4 2 f (Ai), 1I = 1,2
(73)
A1 0 A2 = 0
(74)
1
2
(0) A1) - (0) A2)
- (1 - 8) (S(A)) + (I(A)) (
(75)
1
Then,
(Submodularity, Nonnegativity, Inequality (74))
2
S)(A)) + +0 (Aa) (1- (A + (A2)) + 1-8
(Inequality (75))
1
((G) + 28
2 14 (1 E)?
(0)
(Inequality (73) and G arg max (41), (A2)) (A2))
1-6
f 2 (1-3e)(1 =)
2() ( f(0)
2(1 8) + +++
G.3. Pseudocode and Analysis of PITG (Theorem 4.2, Section 4)
Algorithm 11: A randomized (1/e a)aaprroximation algorithm with O (fog-2 log(k:) adaptivity and O ( log(n) log(k)) query complexity
Procedure PARALE
kf
Input: evaluation oracle f nd + Rzo, constraint k, constant l, error
Initialize: + 0, + 5 m
M + max f ({x}) Tmin + E'M.
k
for i + 1 to f do
(A) [(] PARAILELINTERRLAACCGEEEED (Ja, m, Tmin; e')
G random set in (GU A₁ le [4]
return G
This subsection presents the pseudocode and theoretical analysis of our parallel (1/e E) approximatio algorithm.
First, we provide the following lemma which provides a lower bound on the gains achieved after every iteration in Alg. 11. Lemma G.3. For any iteration i of the outer for loop in Alg. 11, it holds that
(EI((OUG)) (1- Elf (OUG
(1-=+1)
E (LOUGGLLLL (G -
2) - (GG-1))
(1-
Proof of Lemma G.3. Fix G,-1 at the beginning of this iteration, Since {Ai :1 [C]} pairwise disjoint sets, by Proposition 1. it holds that
E [(SG))))) G-1]= Σ
Σ
S(OUGH (1- / (OUGG.)).
leTe
37

---

Sublinear Adaptive Algorithm for Submodular Maximization
Then, by unfixing C,-1, the first inequality holds.
To prove the second inequality, also consider fix G²-1 at the beginning of iteration i. By Lemma G.I, { : / [e]} are paiewise disjoint sets, and the following inequalities hold,
A/ S A. A (Aj 0) 2 A (Ai 0), LA 213E
(76)
( A < ( 0)
E'M
(1 (1-E') E'- 4I315A
(77)
2')²
1 1+
2 (1 E'-'")e"
A AOi, At.) + (Oi, AA.) S
(A (Ar 0) (4%
1A 1h < Se
(78)
(1 31-87 872
Then,
Σ
Σ Σ (O,, UGG-)
(Proposition B.1)
E
1E/4 12((()
Σ A(Or)A))G-))
Σ (A AI, UG (0,, Ar, UG;-1)) slh
(Lemma F.3)
A AA1
E'M
Σ
+ (1 e'yL
(1 E7)2 (1-61)2
(1+ 1
2
Σ
(1- (A (A/, G.-1) + +A/,, G,-1))+ + (1 (1-
1s4
(Inequalitics (77) and (78))
8
A G et
$
1+ m)
Σ
1-6 1- (0)
(M $ (O))
(1-E!)²
(E(8]
=(1+ 11
(1-E8) -1/2
E7/2 )
|+ m
Σ
elt AAA -
1 e {())
(E(1]
1e(1
(Inequality (76))
2 -
1 1 (()
Thus,
E (G.)) G--1l= = Σ A (AA))
e' (1-2) (f 1-g.((0)
(Proposition B.1)
+ (1- m
By unfixing G the second inequality holds.
Theorem 4.2. With input (J,k,e) 8) such that O (8-1) 2 oz and (2=5) ect-4 PITG (Alg. 11) returns G such that
[f 2 (1/e f) (O) with O (<-5log(n)) log(k)) adaptive rounds and O log(n) log(k)) queries with probability of - O (1/(En)).
Proof of Theorem 4.2. Since the algorithm contains for loop which runs PRAALELNTERLAAEGREEEDD times, by Lemma G. the adaptivity, query complexity and success probability holds immediately.
O (1/s)
Next, we provide the analysis of approximation ratio. By solving the recurrence Lemma G.3, we calculate the approxima- tion ratio of the algorithm as follows,
(1 m 1 11)
((--))
e'
E (G.)) 2 1- El (G--1)l + 1 7-
f(0)
1 -
38

---

Sublinear Adaptive Algorithm for Submodular Maximization
1
(1 1- (1-1((1111) (1-(--))) 110)
2
(1-87}
m
+
1
1 1- 5
1
( +
|
e
(1 -(-) f(0)
1-
(1-F)
(1- (1-2')2 {
2
1 k
e
1-e (1 - 1
-1-c-1)) (0)
1
1
(1 (1= 2
2(1 - =
T- (1 1--01-111-0 (1---)))100 S10)
E'
k
(1 - (e+ + 1)=') (e
1- o (1-E11) f(0)
(e2 2 k -0-211
-e) (0).
(5' -
By Inequality 37, the approximation ratio of Alg. e
H. Experimental Setups and Additional Empirical Results
In the section, we introduce the settings in Section 5 further, and discuss more experimental results on SM-GEN and SM-MON.
H.I. Applications
Maxcut. In the context of the maxcut application, we start with graph G = (V, E¹) where each edge ij E E' has a weight Wij. The objective is to find a cut that maximizes the total weight of edges crossing the cut. The cut function f 2 - Rg0
is defined as follows,
f(S) ((s)=>> Σ Wiy, VS V.
IES JEVIS
This is non-monotone submodular function. our implementation, for simplicity, all edges have a weight of 1.
Revmax. In our revenue maximization application, we adopt the revenue maximization model introduced in (Hartline et al., 2008), which we will briefly outline here. Consider social network G (V, where V denotes the buyers. Each buyer i's value for good depends on the set of buyers S that already own it, which is formulated by
(() = fi
Σ wis
jES
where fo R220 > R2o is non-negative, monotone, concave function, and way is drawn independently from a distribution. The total revenue generated from selling goods to the buyers S is
f(8) Σ fs (EVIS
Σ Wij jES
This is non-monotone submodular function. In our implementation, we randomly choose each wij E (0, 1), and [x(x) = r where a; E (0, 1) is chosen uniformly randomly.
H.2. Datasets
er is synthetic random graph generated by Erdös-Rényi model (ERDdS & R&wi, 1959) by setting number of nodes 100, 000 and edge probability = 5
web-Google (Leskovec et al., 2009) is a web graph of n = 875, 713 web pages as nodes and 5, 105, 039 hyperlinks as edges.
39

---

Sublinear Adaptive Algorithm for Submodular Maximization
musae-github (Rozemberczki al., 2019) is social network of GitHub developers with 37, 700 developers and 289, 0033 edges, where edges are mutual follower relationships between them.
twitch-gamers (Rozemberezki & Sarkar, 2021) is social network of 168, 114 Twitch users with 6, 797, 557 edges, where edges are mutual follower relationships between them.
H.3. Additional Results
Fig. 5 provides additional results on musae-github dataset with 37, 700 and web-Google dataset with 875, 713. It shows that as and & increase, our algorithms achieve superior on objective values. The results of query complexity and adaptivity align closely with those discussed in Section 5. Notably, the number of adaptive round of PITG exceeds on musae-github, which may be attributed to the dataset's relatively small size.
1.0
10a
Adaptive Rounds
Value ATG
0.9
Total Queries
0.8
10
0.7
107
0.6
10a
Purtt
0.5
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15
k/n
k/n
musac- github, solution value
(b) musae-github query
(c) musae- github, round
10
1.0
Adaptive Rounds
Value ATG
Total Queries
104
0.9
10a
10a
0.8
107
10a
0.7
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15
k/n
k/n
k/n
(d) web Google solution value
(e) web reb-Google, query
web- web-Google, round
Figure 5, Results for revmax musae github with 37, 700, and maxcut web-Google with 875, 713.
40


Reviews:
[{"review_id": "aKV73gWCuL", "reviewer": "Reviewer_GBRx", "summary": "The paper studies the non-monotone submodular maximization in the parallel model. They provide two algorithms with the best one having a $1/e$ approximation factor, $O(log(n)log(k))$ adaptivity and almost linear query complexity.Previously, the only algorithm with a $1/e$ approximation factor and logarithmic adaptivity relied on continuous approaches, which required many queries.", "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": "```\nTheir experiments seem reasonable, but the graph on solution value is missing the data for the ATG algorithm, which appears to have better adaptivity and query complexity.\n```\nThank you for pointing this out. Since the objective value is normalized by ATG, the ATG data would appear as a horizontal line with value 1 in the graph. To improve clarity, we will add this line to the graph.\n\n\n```\nComparing with PARSSP would also be interesting, as it achieves better approximation factors than other logarithmic adaptivity algorithms.\n```\nThank you for the suggestion, we will add the comparison to PARSSP in the next version.", "claims_and_evidence": "They provide proof for their claims.", "methods_and_evaluation_criteria": "Their experiments seem reasonable, but the graph on solution value is missing the data for the ATG algorithm, which appears to have better adaptivity and query complexity. Comparing with PARSSP would also be interesting, as it achieves better approximation factors than other logarithmic adaptivity algorithms.", "theoretical_claims": "I reviewed the proofs in the main part of the paper, but not the appendix.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "There are many works on this problem, and among the works with logarithmic adaptivity (which is usually the most important factor for parallel algorithms), most works have worse approximation factors compared to them and the only work that matches their approximation factor uses continuous methods which are not practical.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Their result is interesting because it achieves the best-known approximation factor with logarithmic adaptivity and near-linear query complexity. However, a limitation of their approach is that it does not achieve $O(\\log n)$ adaptivity, unlike the continuous algorithm.", "other_comments_or_suggestions": "Please add the ATG data in Figures 2a and 2d.", "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": "7w6oCnBgF8", "reviewer": "Reviewer_KJuz", "summary": "The problem of submodular maximization under a cardinality constraint is a fundamental topic with numerous applications. The submodular function, defined on a ground set $U$, can be either monotone or non-monotone, with the non-monotone case being notably more challenging.\n\nThere is a wealth of results on non-monotone submodular maximization under a cardinality constraint. The current state-of-the-art algorithm is a $1/e$ approximation algorithm based on continuous greedy, which requires $O(k^2 n \\log^2(n))$ oracle queries. This paper introduces a sublinear algorithm that achieves the same $1/e$ approximation guarantee but uses only $O(n \\log(n) \\log(k))$ queries. This makes the algorithm sublinear, assuming that $O(nk)$ is considered the linear query complexity regime. Furthermore, the paper presents a parallel version of this algorithm, which requires $O(\\log(n) \\log(k))$ adaptive rounds.\n\nOverall, the paper is well-written, and I appreciate the contributions. However, there are a few aspects that need improvement:\n\n1. Clarity and Readability:\n   The paper requires significant polishing. The current version is difficult to follow, even for an expert in the area. Frequent references to the appendix make the paper hard to read, as it requires constant switching between the main text and the appendix. I recommend minimizing these references and integrating more details directly into the paper to improve its flow.\n\n2. Algorithm Overview:\n   The paper lacks a clear, intuitive overview of how the sublinear and parallel algorithms function. Section 5 describes the algorithmic steps but does not provide sufficient intuition for why these steps are taken and how they contribute to the solution. While Sections 5.1 and 5.2 attempt to offer an overview, they are cluttered with references to the appendix, which makes them hard to follow. I suggest adding a more detailed, intuitive explanation of the algorithm's workings, especially in the early sections.\n\n3. Unusual Notations:\n   In Algorithm 3 (the main algorithm), the notations used in Lines 4 and 8 are unconventional. It is unclear whether these notations are intentional or typographical errors. There is no explanation of these symbols in the paper, which makes it difficult to understand their meaning. I recommend clarifying or correcting these notations.\n\n4. Preliminaries Section:\n   The \"Preliminaries\" section is overly brief and lacks a proper explanation of key concepts, such as the parallel model and adaptivity. These concepts should be clarified earlier in the paper. For example, when Algorithm 3 and the \"UPDATE\" procedure refer to parallelism, it is not clear whether this refers to $\\ell$ parallel machines or some other form of parallelism. A more detailed explanation is needed.\n\n5. Table 1:\n   Table 1 is difficult to follow. It includes many results, some of which are not essential for understanding the key contributions of the paper. I recommend simplifying the table to focus on the most important results.\n\n6. Algorithm Structure:\n   I suggest reintroducing the procedures \"UPDATE\", \"DISTRIBUTE\", and \"Pre-fix selection\" into the main body of the paper, or alternatively, dedicating a separate section to explain them. Additionally, Algorithm 3 could be split into two or three sub-algorithms to improve readability—one for Lines 6-14 and another for Lines 16-24.\n\n\nGeneral Suggestions:\n\n- Overview and Intuition: It would be helpful to include a concise, intuitive overview of the algorithm in the first few pages, which explains its core idea and key steps. This will make it easier for the reader to understand the subsequent details.\n  \n- Sublinear Query Complexity: While I understand the concept of sublinear query complexity, it would be useful for the paper to explicitly define and explain it. This would ensure that the reader has a clear understanding of what is meant by sublinear complexity in the context of this paper.\n\n- Parallel Model and Adaptive Rounds: A more detailed explanation of the parallel model and the concept of adaptive rounds is necessary. This is a crucial aspect of the algorithm, and it would benefit from a clearer definition and description.\n\n\nOverall, the paper presents an interesting and valuable contribution. With some revisions to improve clarity, provide more intuition, and ensure consistency in notation and terminology, the paper would be much more accessible and impactful.", "questions": "", "limitations": "", "rating": 2, "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 reviewers for their constructive suggestions. We will revise the manuscript to improve clarity and presentation. In Section 1.1, we clarify the technical contributions, focusing on how the simplified InterpolatedGreedy enables parallelization and enhancing the explanation of our parallel algorithm (PIG). In Section 2, we refine definitions of adaptivity, parallel algorithms, and the thresholding technique. We restructure Section 3, remove Section 4 for conciseness, and improve Section 5 with an overview, pseudocode, and key subroutine introductions.\n\nBelow, we detail these changes.\n\n1. Section 1.1. Contributions.\n    - Our first contribution is a technical contribution that simplifies both InterpolatedGreedy and InterlaceGreedy. Importantly, by eliminating the low-success-probability requirement, the simplified InterpolatedGreedy serves as an efficient framework for parallel algorithm design. We will clarify this in the revised manuscript as follows.\n\n    \"... Most importantly, these simplified variants establish the theoretical foundation for parallel algorithms. By removing branching dependencies and probabilistic guesswork, our framework enables the first efficient parallelization of these interlaced greedy approaches while preserving their approximation guarantees.\"\n    - Our second contribution is the proposed parallel algorithms, where we explain how integrating the interlaced greedy approach with threshold sampling achieves both theoretical guarantees and practical efficiency. The revised version is below.\n\n    \"... The core innovation of PIG lies in its novel threshold sampling procedure, which simultaneously preserves the crucial alternating selection property of interlaced greedy methods while enabling efficient parallel implementation.\n    \n    Like prior parallel algorithms, PIG maintains descending thresholds for each solution, adding elements whose average marginal gain exceeds the current threshold. However, PIG introduces two critical modifications to maintain the interlaced greedy structure: 1) strict synchronization of batch sizes across all $\\ell$ parallel solutions, and 2) coordinated element selection to maintain sufficient marginal gain for each solution.\n\n    This design achieves three fundamental properties. First, it preserves the essential alternating selection property of the interlaced greedy methods. Second, through threshold sampling, it geometrically reduces the size of candidate sets - crucial for achieving sublinear adaptivity. Third, its efficient batch selection ensures each added batch provides sufficient marginal contribution to the solution. Together, these properties allow PIG to match the approximation guarantees of the vanilla interlaced greedy method while achieving parallel efficiency...\"\n2. Section 2. Preliminary\n    - We will include formal definitions of adaptivity and parallel algorithms in the revised manuscript. Additionally, we will clarify the concept of sublinear adaptive algorithm.\n    - We will provide a concise introduction to the thresholding technique, explaining its role in the parallel algorithms.\n3. Section 3. The Blending Technique for Greedy\n    - We will retitle this section as \"A Parallel-Friendly Greedy Variant via Blending Technique\" to better reflect its focus on developing an efficient parallelizable algorithm.\n    - We will focus on the simplified InterpolatedGreedy (achieving a $1/e$-approximation) and leave the simplified InterlaceGreedy (achieving a $1/4$-approximation) in appendix.\n    - The structure of the section will be as follows:\n        - Section 3.1: An Overview of Prior Work and Its Limitation. \n            - Summarizes how InterpolatedGreedy works and identifies key bottlenecks for parallelization.\n        - Section 3.2: Motivation for Simplification. \n            - Explains the rationale behind our approach and its advantages.\n        - Section 3.3: Technical Overview of Blended Marginal Gains Strategy for InterpolatedGreedy. \n            - Provides a high-level explanation of how the blended marginal gains strategy enhances InterpolatedGreedy's efficiency.\n4. Section 4. Preliminary Warm-Up of Parallel Approaches: Nearly-Linear Time Algorithms (Removal)\n    - To streamline the presentation and avoid redundancy, we will remove this section. This adjustment allows us to dedicate more space to Sections 3 and 5, where we will elaborate on the high-level ideas and technical details of the proposed algorithms.\n5. Section 5. Sublinear Adaptive Algorithms\n    - Section 5.1: Subroutines for PIG.\n        - This subsection will include the pseudocodes for key subroutines (Distribute, Update, Prefix-Selection) and provide a high-level description of their functionality.\n    - Section 5.2: Algorithm Overview\n        - Here, we will introduce the core intuition behind the algorithm, emphasizing its novel components and how they collectively achieve sublinear adaptivity.", "claims_and_evidence": "Nothing", "methods_and_evaluation_criteria": "Nothing", "theoretical_claims": "The correctness of the theoretical claims was not explicitly questioned in the review. However, the review does highlight issues related to clarity, notation, and organization, which may indirectly affect the readability and verification of the proofs. Specifically:\n\nNotation Issues: The review notes that some notations in Algorithm 3 (Lines 4 and 8) are unconventional and unclear. If these notations are crucial for the proofs, their ambiguity could make it difficult to verify correctness. It is recommended to clarify or correct these notations.\n\nAppendix References: Frequent references to the appendix make it hard to follow the logical flow of the paper. If key proofs rely on these sections, integrating more details into the main text would help in assessing their correctness.\n\nPreliminaries and Definitions: The review points out that the \"Preliminaries\" section is overly brief, lacking proper explanations of key concepts like the parallel model and adaptivity. If these concepts play a role in the proofs, their insufficient explanation could hinder proper verification.\n\nWhile no specific errors in the theoretical results were identified, improving the clarity, notation, and structure of the paper would facilitate a more thorough and accessible verification of the proofs.", "experimental_designs_or_analyses": "For me, the most important part was the theory part.", "relation_to_broader_scientific_literature": "The paper contributes to the well-studied problem of submodular maximization under a cardinality constraint, which has numerous applications. The broader scientific literature on this topic includes both monotone and non-monotone submodular functions, with the non-monotone case being particularly challenging.\n\nA key reference point in the literature is the state-of-the-art $1/e$ approximation algorithm based on continuous greedy, which requires $O(k^2 n \\log^2(n))$ oracle queries. The primary contribution of this paper is introducing a sublinear algorithm that achieves the same $1/e$ approximation guarantee but significantly reduces the query complexity to $O(n \\log(n) \\log(k))$. This advancement aligns with recent trends in submodular optimization that seek more efficient algorithms with lower query complexity.\n\nAdditionally, the paper extends its contribution by presenting a parallel version of the algorithm, which requires only $O(\\log(n) \\log(k))$ adaptive rounds. This connects to the broader literature on parallel submodular optimization, an area of increasing importance for large-scale applications. However, the review suggests that the paper could benefit from a clearer discussion of the parallel model and adaptivity, ensuring that the contribution is well-situated in the context of existing work.\n\nIn summary, the paper builds on and improves key results in submodular maximization, particularly by introducing a sublinear and parallelizable approach while maintaining the best-known approximation guarantee. To strengthen its connection to prior literature, the paper should explicitly compare its results to previous work in terms of efficiency, adaptivity, and practical implications.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "It's given in the review.", "other_comments_or_suggestions": "It's given in the review.", "questions_for_authors": "It's given in the review.", "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": "AjE56wrUsW", "reviewer": "Reviewer_9FCa", "summary": "This work introduces enhanced solutions for maximizing a non-monotone submodular function under a cardinality constraint. The authors concentrate on solution quality, query count, and adaptivity, which are the key performance indicators in this area of research.", "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 constructive comments.\nRegarding the suggestions related to paper presentation and organization, we have provided detailed responses to each point in our reply to Reviewer KJuz.\n\n```\nThe results provide marginal improvement compared to the state of the art.\n```\nWe sincerely appreciate the reviewer’s feedback. While the improvement in approximation ratio may appear incremental at first glance, we would like to clarify the significance of our contribution.\n\nOur work represents the first advancement in five years since the breakthrough $1/e$-approximation achieved by a parallel continuous algorithm (Ene & Nguyen, 2020). Specifically, we improve the approximation ratio for parallel combinatorial algorithms from $1/4$ to $1/e$, bridging a key gap between combinatorial and continuous approaches. Given that the current best-known approximation ratio for non-monotone submodular maximization is 0.401 [1], an improvement exceeding 0.11 is, in fact, a meaningful step forward in this challenging problem space.\n\n[1] Buchbinder, N. and Feldman, M. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This paper presents results that are relevant to researchers in submodular maximization", "essential_references_not_discussed": "This paper provides a deep comparison with the publications in this field.", "other_strengths_and_weaknesses": "\"+\" The paper is well-written.\n\n\"+\" Thorough and clearly stated comparisons with previous work are provided.\n\n\"+\" The results are interesting, and the techniques might be applicable to other problems in this field.\n\n\"+\" Bridging the gap between continuous and combinatorial algorithms is of high interest.\n\n\"+\" The experimental section uses well-known applications in the field.\n\n\"+\" The strengths and weaknesses of the approach are clearly stated.\n\n\"-\" The results provide marginal improvement compared to the state of the art.\n\n\"-\" The experimental section shows that the proposed algorithms have higher quality but also higher queries and adaptivity in some cases.", "other_comments_or_suggestions": "The paper would benefit from a clearer explanation of its core and novel ideas, which will improve its impact. The algorithm's complexity made it a bit hard to follow; providing more intuition would improve understanding.\n\nAlthough the paper does not present an impact statement, I do not have any ethical concern.", "questions_for_authors": "Could you please provide a highlight of the new ideas in this work.", "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": "Wqo5BY6pWu", "reviewer": "Reviewer_AdQT", "summary": "This paper studies the problem of maximizing a non-monotone submodular function subject to a size constraint. In the problem, we are given a set $\\mathcal{U}$ of $n$ elements, (a value-oracle of) a non-monotone submodular function $f$, and a positive integer $k$, and the goal is to find a subset $S$ of $\\mathcal{U}$ that maximizes $f(S)$ subject to $|S|\\leq k$. A well-known randomized approximation algorithm for the problem achieves the $1/e$-approximation (in expectation). The query complexity of this algorithm is $O(kn)$, which was later improved to $O(n)$ (for some regime of $k$). Additionally, to further improve the scalability, much work has studied parallelizable algorithms for the problem. The parallelizability of an algorithm is measured by the adaptive complexity, i.e., the number of buckets needed to divide the queries to $f$ into adaptive rounds such that within each round the sets to be queried only depend on the results of queries in previous rounds. The lower the adaptive complexity, the higher the parallelizability because the queries in each round can be arbitrarily parallelizable. The current best approximation ratio among those achieved by the algorithms with a sublinear adaptive complexity is $1/e-\\epsilon$; however, the algorithm achieving that ratio needs to estimate the multilinear extension of $f$, requiring a substantial number of queries to the original $f$ and making it impractical. The main contribution of this paper is a combinatorial $(1/e-\\epsilon)$-approximation algorithm with a sublinear adaptive complexity and a nearly-linear query complexity (to the original $f$).\n\n## update after rebuttal\n\nI maintain my overall recommendation (weak reject) based on the discussion with the authors.", "questions": "", "limitations": "", "rating": 2, "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 thoughtful feedback. Regarding the suggestions related to paper presentation and organization, we have provided detailed responses to each point in our reply to Reviewer KJuz. For other questions, we address each point below.\n\n```\nThe authors state that they only provide the results for er in the main body, but the results for twitch-gamers are also given there.\n```\nThank you for pointing this out. We will correct our statement in the next version.\n\n```\nThe selection criterion of baseline methods is unclear. \n```\nThank you for the suggestion. In our current experiments, we focused on parallel algorithms designed specifically for size-constrained problems. While algorithms like ParKnapsack, ParSKP, and ParSSP can handle more complex constraints, such as knapsack constraints, they currently suffer from high query complexity, which limits their practicality. For completeness, we plan to include experimental results for these algorithms in our next version.\n\n```\n... it seems unfair to employ a random subset for the algorithms that require to solve the unconstrained problem.\n```\nWe appreciate the reviewer’s observation regarding the use of a random subset for baseline methods that require solving the unconstrained problem. We would like to clarify the rationale behind our experimental design:\n- The $1/2$-approximation constant-adaptive algorithm proposed by [1] is used for ANM, AST, and ATG. However, this algorithm relies on querying the multilinear extension $F$ of the objective function, whose estimation requires an impractically large number of queries to the value oracle $f$. This makes the algorithm prohibitively expensive to run in experiments, despite its theoretical guarantees.\n- Based on our experimental evaluation, the solutions returned by unconstrained algorithms (e.g., [1]) do not dominate other solutions. Thus, their inclusion would not meaningfully improve objective values in practice.\n- In summary, while implementing [1] would align with theoretical comparisons, it would incur significant query complexity without commensurate gains in solution quality. Our goal was to focus on practical and scalable baselines, which better reflect real-world constraints.\n\n[1] Chen, L., Feldman, M., & Karbasi, A. (2019). Unconstrained submodular maximization with constant adaptive complexity. In Charikar, M., & Cohen, E. (Eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pp. 102–113. ACM.\n```\nThe problem of maximizing non-monotone submodular functions is not motivated accordingly. Indeed, the application examples listed by the authors are mostly with monotone submodular functions (e.g., inﬂuence maximization).\n```\nWe appreciate the reviewer’s feedback. For the same application, different submodular functions can be defined as either monotone or non-monotone. For example, influence maximization can have non-monotone variants when considering competition or oversaturation effects.\n\nWe also acknowledge that some of our cited papers focus on monotone functions. To clarify this distinction, we will differentiate between monotone and non-monotone papers and add the following paper as a non-monotone variant for the revenue maximization application.\n- Amanatidis, Georgios, et al. \"Fast adaptive non-monotone submodular maximization subject to a knapsack constraint.\" Advances in neural information processing systems 33 (2020).\n\n```\n... but the approximation ratio itself is nothing new, so mentioning it as one of the proposals would be weird for the readers ...\n```\nWe appreciate this insightful observation. While the 1/4-approximation ratio itself is not novel, our algorithm achieve this ratio with high probability ($\\ge 1-1/n$). In Cui et al. (2023), ParSSP achieves $1/4$ approximation ratio in expectation. We will revise our abstract as follows which leads with our primary 1/e-approximation result and present the 1/4-result as a byproduct.\n\n\"... In this work, we focus on size constraints and present the first combinatorial algorithm matching this bound - a randomized parallel approach achieving $1/e − \\varepsilon$ approximation ratio. This result bridges the gap between continuous and combinatorial approaches for this problem. As a byproduct, we also develop a simpler $(1/4 − \\varepsilon)$-approximation algorithm with high probability $( \\ge 1 − 1/n)$...\"\n\n\n```\nIn Section 3.1, the authors state that intuitively adding an element from $O$... just meaning that the ﬁrst step can be eliminated.\n```\nWe sincerely appreciate this insightful observation. We agree that the explanation here might be misleading. We will revise the text to remove ambiguous descriptions as follows.\n\n\"This complex architecture naturally raises a fundamental question: Can we develop an alternative analysis framework that eliminates the need to explicitly guess the position of $o_{\\max}$?\"", "claims_and_evidence": "Although a lot of evidences (and even the proposed algorithm itself) are presented in the appendix, the claims seem to be supported.", "methods_and_evaluation_criteria": "The proposed $(1/e-\\epsilon)$-approximation algorithm is called ParallelInterpolatedGreedy (PItG). This algorithm repeats the subroutine called ParallelInterlaceGreedy (PIG), which is also a novel component and achieves the $(1/4-\\epsilon)$-approximation. PIG can be seen as a parallel counterpart of the existing non-parallel InterlaceGreedy and InterpolatedGreedy. To obtain PIG and its approximation ratio analysis, the authors first introduce the blended marginal gains strategy, which provides multiple upper bounds on the marginal gain of an element with respect to sets kept in the algorithm. This strategy simplifies InterlaceGreedy and InterpolatedGreedy and enables to incorporate thresholding techniques to reduce their query complexity.", "theoretical_claims": "I checked the correctness of the contents in the main body. Other than some undefined notation and typos, I did not find any technical issue.", "experimental_designs_or_analyses": "The proposed algorithms are evaluated using two applications, i.e., Maximum Cut and Revenue Maximization, with large-scale real-world networks. The authors state that they only provide the results for er in the main body, but the results for twitch-gamers are also given there. The selection criterion of baseline methods is unclear. There are many existing parallel algorithms for the problem that are listed in Table 1 but not tested in the experiments. Also, regarding the implementation of the baseline methods, it seems unfair to employ a random subset for the algorithms that require to solve the unconstrained problem.", "relation_to_broader_scientific_literature": "Submodular maximization has actively been studied in machine learning. Dealing with non-monotone submodular functions is still important, and the parallelization is a reasonable way to accelerate the algorithms. The proposed algorithm is the first combinatorial $(1/e-\\epsilon)$-approximation algorithm with a sublinear adaptive complexity and a nearly-linear query complexity, which could be a good addition to the literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I acknowledge the technical contribution of the paper but also believes that the presentation could have been done better in both non-technical and technical parts. Some suggestions are given below: \n- The presentation of the technical contents should be improved. The most significant issue is that the authors directly dive into the technical details and do not explain the overall algorithm design and analysis before that. This makes the technical contents quite puzzled. It is understandable that Algorithms 1 and 2 are improved versions of the existing InterlaceGreedy and InterpolatedGreedy, respectively, but how those algorithms are utilized in the proposed algorithms is quite unclear. Do the authors really need Algorithm 1 to design the proposed algorithms? Also, the behavior of the thresholding techniques used in the proposed algorithms are not explained in the main text. What the property of the alternating additions means should be explained. \n- The problem of maximizing non-monotone submodular functions is not motivated accordingly. Indeed, the application examples listed by the authors are mostly with monotone submodular functions (e.g., influence maximization). \n- There are some descriptions that do not make sense. For instance, in the abstract, the authors state that they propose a $(1/4-\\epsilon)$-approximation algorithm with high probability for the problem, but the approximation ratio itself is nothing new, so mentioning it as one of the proposals would be weird for the readers. Later it turns out that the algorithm is a preliminary result, which should have been explicitly mentioned. The same thing can be pointed out in Section 1.1. In Section 3.1, the authors state that intuitively adding an element from $O$ to the solution should not negatively impact it and the question \"can the second interlaced greedy step be eliminated?\" naturally arises. However, the question is not reasonable. If the addition does not negatively impact the solution, the second interlaced greedy step should work well, just meaning that the first step can be eliminated.", "other_comments_or_suggestions": "Typos and minor things: \n- Many equations are presented using smaller fonts. \n- Sec 1: $\\mathcal{U}$ and $\\epsilon$ are undefined. \n- Tab 1: The notation || is undefined. \n- Sec 3.1: the maximum singleton $a_0$ is undefined. \n- Alg 1: dummy elements should be defined.\n- Alg 2: \"size of solution\" is misleading.", "questions_for_authors": "See Other Strengths and Weaknesses.", "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": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"], "ethical_review_concerns": "This paper doesn't include impact statements."}}]

Author rebuttal:

Meta-review: This work studies low-adaptivity algorithms for non-monotone submodular maximization subject to a cardinality constraint. Specifically, it gives the first $(1/e-\varepsilon)$-approximation algorithm with nearly optimal query and adaptivity complexity. Note that [Ene-Nguyen, ICML 2020] gave a *continuous* algorithm for this problem that achieves a $(1/e-\varepsilon)$-approximation ratio with near-linear adaptivity but $O(n k^2 \log^2 n)$ calls to an oracle for multilinear extension queries. This work also presents a simpler algorithm called `ParallelInterlaceGreedy` (Algorithm 3) that achieves a $(0.25 - \varepsilon)$-approximation guarantee w.h.p. in $O(n \log(n) \log(k))$ queries and $O(\log(n) \log(k))$ adaptive rounds, improving on the algorithm and analysis in [Kuhnle, NeurIPS 2019]. The authors also include an empirical study comparing their algorithms to related work on standard benchmarks.

Overall, this is a borderline submission with mixed reviews (scores: [4, 2, 3, 2]). The improvement to the approximation ratio for low-adaptivity combinatorial algorithms for SM-GEN is clearly a very nice improvement. However, most reviewers commented that the presentation/organization (for both technical and non-technical parts) noticeably affects the readability and verification of proofs.
Decision: Accept (poster)