Efficient Submodular Maximization for Sums of Concave over Modular Functions
Authors: Yang Lv
Guihao Wang
Dachuan Xu
Ruiqi Yang
Venue: ICLR 2026 Poster (2026)
Keywords: Submodular maximization
Sums of Concave over Modular functions
Accelerated Approximate Projected Gradient Ascent
Randomized rounding
GPU-parallel optimization
Primary area: optimization

Abstract: Submodular maximization has broad applications in machine learning, network design, and data mining. However, classical algorithms often suffer from prohibitively high computational costs, which severely limit their scalability in practice. In this work, we focus on maximizing Sums of Concave over Modular functions (SCMs), an important subclass of submodular functions, under three fundamental constraints: cardinality, knapsack, and partition matroids. 
	Our method integrates three components: continuous relaxation, Accelerated Approximate Projected Gradient Ascent (AAPGA), and randomized rounding, to efficiently compute near-optimal solutions. We establish a $(1 - \varepsilon - \eta - e^{-\Omega(\eta^2)})$ approximation guarantee for both cardinality and partition matroid constraints, with query complexity $O\left(n^{1/2}\varepsilon^{-1/2} (T_1 + T_2)\right)$. For the knapsack constraint, the approximation ratio degrades by a factor of $1/2$, with query complexity $O\left(n T_1 + n^{1/2}\varepsilon^{-1/2} T_2\right)$, where $T_1$ denotes the computational cost of evaluating the concave extension, and $T_2$ denotes the computational cost of backpropagation. By leveraging efficient convex optimization techniques, our approach substantially accelerates convergence toward high-quality solutions. 
	In empirical evaluations, we demonstrate that AAPGA consistently outperforms standard PGA. On small-scale experiments, AAPGA achieves superior results in significantly less time, being up to $32.3\times$ faster than traditional methods. On large-scale experiments, our parallel multi-GPU implementation further enhances performance, demonstrating the scalability of our approach.

Published as a conference paper at ICLR 2026
EFFICIENT SUBMODULAR MAXIMIZATION FOR SUMS OF CONCAVE OVER MODULAR FUNCTIONS
Yang Lv. Guihao Wang, Dachuan Xu, and Ruiqi Yang
Institute of Operations Research and Information Engineering
Beijing University of Technology
Beijing 100124, P.R. China
(1 Tyvang, Wangghao) 0ema 1 1.. wjut.jttt................ edu..teddduccm en, (xude, yangruia ji } Hbjjut edu. cn
ABSTRACT
Submodular maximization has broad applications in machine learning, network design, and data mining. However, classical algorithms often suffer from pro- hibitively high computational costs, which severely limit their scalability in prac- tice. In this work, we focus on maximizing Sums of Concave over Modular fune- tions (SCMs), important subclass of submodular functions, under three funda- mental constraints: cardinality, knapsack, and partition matroids. Our method tegrates three components: continuous relaxation, Accelerated Approximate Pro- jected Gradient Ascent (AAPGA), and randomized rounding, to efficiently com- e -2(r") approximation guarantee for both cardinality and partition matroid constraints, with query com- plexity (1,2 (Ti + T2))- For the knapsack constraint, the approximation ratio degrades by factor 1/2, with query complexity O + (.1/2g-1/2TT)) where Ti denotes the computational cost of evaluating the concave extension, and To denotes the computational cost of backpropagation. By leveraging efficient convex optimization techniques, our approach substantially accelerates conver- gence toward high-quality solutions. In empirical evaluations, we demonstrate that AAPGA consistently outperforms standard PGA. On small-scale experiments, AAPGA achieves superior results in significantly less time, being up to 32.3x faster than traditional methods. On large-scale experiments, our parallel multi- GPU implementation further enhances performance, demonstrating the scalability of our approach.
pute near-optimal solutions. We establish a (1 -
INTRODUCTION
Submodular functions have attracted considerable attention due to their diminishing marginal returns property and have been applied in various fields such as determinantal point processes (Gillenwa- ct all 2012), sensor placement (Krause et all 2000). and probabilistic inference (Diolonga & Krause. 20))). As set functions, submodular functions are defined over the power set, with their range residing within 2" di-dinensional cone in IR2" exhibiting rich structural properties. While the minimization of submodular functions can be solved in polynomial time (Fujishige, 20025), the max- imization problem with cardinality constraints is NP-hard. However, researchers proposed simple greedy algorithm, which guarantees a (1 - 1/ee approximation ratio for monotone submodular func- tions under constraints (NNemhauser et aLl 1978), and this ratio has been proven be optimal (Ferge, 1998). Moreover, different variants of the submodular maximization problem have been extensively studied, further advancing submodular optimization theory
Even for approximate solutions to submodular maximization, the extremely large scale of modern machine learning problems makes acceleration of submodular optimization crucial research di- rection. Existing acceleration methods for submodular maximization can be broadly categorized as follows. The earliest serial acceleration approaches (Minoux, 1978% Mirzasoleiman et all 2015)
"Corresponding author: Ruiqi Yang

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of representative algorithms for submodular maximization under different constraints. T1 denotes the computational cost of evaluating the concave extension, and T2 denotes the computational cost of backpropagation.
Method
Type
Constraint
Approsimation Guarantee
Query Complexity
Confmnaiity Consmaiin
Lazee-GGeedy (hirasala MITK)
Submodular
Canditality
Oln (o O(2)
FAST Eimmereen (TA)
Submodular Submodular
Canlinality
1/e-
LS+PGB
Cardinality
Matroid Constolttt
Subqud (ooeee 181R
Submodular
Mizroid
1-1/e-8
O ((u)))g of ( of (
SPGA (Xmmmnaa MIFE
Coverage Functions
Matroid
1-1/e-e
PGA 11 Un)
Deep Sabmodular
Matroid
1-2 -----000""
Kngpanck Constraint
Modified Greedy Crii [GD
Coverage Functions
Knapsack
10-1/00
O(n") Ofaej (l1ye) la Olnkton" R) 01 log
Fnam-Grredly lvmnirn MIN
Submodular
Knapsack
1- 1/c
Density Gready Nrower MTV
Submedular
Knapsack
1 1/c
ParSKP Camme 1AA
Submodular
Knapsack
MultiStream A 817
Submodular
Knapsack
Our Priposed Methoa
Ours
SCM
Cardinality / Pariition Matroid
6 n 9691
Ota + Ty)) Ote 2019g-1/199)
Ours
SCM
Knupsack
1 Rxh))
avoid evaluating the marginal gains of all elements at each step, while still achieving utility compara- ble the standard greedy algorithm. However, their (1z) serial complexity remains inadequate for large-scale applications. Subsequently, researchers have developed streaming algorithms (Badanı
diyuru et all 201 4 Halabi et all (0200), parallel algorithms (Breuer et all 2020; Chen all
2021: Cui et all 2023: Amanatiis et all 2021), distributed algorithms (Mirzasoleiman all 2016).
continuous relaxations (Bdannddyuuu & Vondrák, 2014), and multi-stage submodular maximization
methods (Wei et all, 2014), among others.
Many of these acceleration algorithms treat the submodular function as a black box, adopting the value oracle model. While such methods can improve computational efficiency, they do not fully exploit the structural properties of submodular functions. In recent years, more targeted studies on specific function classes have achieved order-of order-of-magninnn m-gnitudd speedups. For example, (Iyer & Bilmes, 2019) introduced memoization framework to maintain auxiliary information of sets, enabling rapid evaluation of submodular functions and representing one of the first works to leverage internal struc- ture for optimization. (Karimi el all, 2017) studied coverage functions and proposed a "three-step" framework: first relaxing the function continuously, then solving the constrained continuous opti- mization problem, and finally applying rounding to obtain an integer solution. By exploiting the spe- cific properties of coverage functions, this approach significantly reduces computational cost. The introduction of deep submodular functions (Dolhansky & Bilmes, 2(T))) enabled neural networks to capture broader class of submodular objectives, further facilitating efficient GPU-based optimiza- tion (Bai al 2018). Nevertheless, the number of iterations required by Projected Gradient Ascent remains (n²² / with query complexity ((n2/e² T2), where T2 denotes the computational cost of backpropagation. This remains prohibitively large for large-scale problems. More detailed results and contributions are provided in Table M. The combination of submodularity and neural networks could open new avenues for integrating learning-basee techniques with classical optimiza- tion theory, and its effectiveness has already begun to be demonstrated in applications (Ghadimi & Beigy, 2020; laisnkkr et all (()24).
In this work, we study the maximization of Sums of Concave over Modular functions (SCMs) and propose an efficient optimization framework inspired by neural networks. We design an approxima- tion algorithm with query complexity (222/22-1/2 (Ti + T2)) for cardinality and partition matroid constraints, and (nT, + 1//T/_ for the knapsack constraint, where T₃ denotes the computa- tional cost of evaluating the concave extension and T, denotes the cost of backpropagation. In the tra- ditional value oracle model, costs such as Ti, To are often neglected, as the oracle is typically treated as "black box," where the computational process is considered a "zero-cost" operation. The frame- work integrates three key components: continuous relaxation, Accelerated Approximate Projected Gradient Ascent (AAPGA), and randomized rounding. Our method achieves an approximation ratio of max - s)(1 - m) [1 [V] exp (17 minsev min m.ck) m;;
under cardinality and partition
2

---

Published as a conference paper at ICLR 2026
10
Modified Greedy
04
Fast
01
23'
Figure 1: The figure shows the trends of the approximation ratios for cardinality and partition ma- troid constraints k varies, as presented in Theorem Ø. The left plot assumes min my/ max my 0.1 and [V] 10. The right plot shows the trend of the approximation ratio for the knapsack constraint the knapsack capacity B changes, with min m./ max m, 0.1, max & 10, and [V]= = 10.
[Vlexp(-i minkev max my max der the knapsack constraint. The comparison of approximation ratios with other algorithms is shown in Figure As can be seen, with the increase of the constraints k and B, the approximation ratio tightens accordingly, outperforming the algorithms presented in the figure. This suggests that our method provides better theoretical guarantees for large-scale submodular optimization. Compared with the algorithm of Bai all (2018), which requires O T=*T;) time, approach offers sub- stantially stronger computational guarantees.
matroid constraints, and & max -1=
my
In the experimental evaluation, compare algorithm with existing Submodular/SCM maxi- mization algorithms. Under cardinality and knapsack constraints, AAPGA achieves speedup of up to 32.3 times while maintaining strong solution quality. On large-scale datasets, our multi-GPU parallelization implementation further outperforms PGA with pipage rounding. demonstrating both faster convergence and practical scalability.
2 BACKGROUND AND PROBLEM SETUP
The submodular function f is a set function defined on N {1, 2..,,.,,, J It satisfies the diminishing returns property, i.e., for any C B C N and any E B, it holds that f(A (c)) - ʃ(A) 2 f(B J (et) ACB C N, we have f(A) < f(B).
f(B). In this paper, we only consider monotone submodular functions, i.e., for
Definition 1 (SCM). A Sum of Concave over Modular functions (SCM) is defined as follows. Let (0, 12 + zeevv be collection of non-negative, non-decreasing monotone, and normalized concave functions with (0) O. Let {m 2N + IRzoiiev be the corresponding modular functions defined by m, (A) EvEA A N. Then, the function
f(A) = Σ (A), ACN
(I)
iEV
called an SCM. It is monotone and submodular.
The modular functions m, in equation @ can be naturally extended to linear mappings over the continuous domain, i.e., m, [0, 1] -> R4. Since the composition of concave function with linear function remains concave, and the sums of concave functions is also concave, we can construct a concave extension F(x) f(A) such that f(A) F(1x) for every N. Formally, this extension is given by
F(x) (m)(m(())), x {
Previous studies on submodular maximization via continuous relaxation typically rely on the multi- linear extension (Calinescu et all 2011), defined F., ΣACN (AA &y IlueA
3

---

Published as a conference paper at ICLR 2026
Te), which can be equivalently written as (x) = EA-D, [f Pr(A)
Io Te H (1-xao). The multilinear extension enjoys a directional concavity property, which makes it particularly suitable for rounding schemes that yield strong approximation guarantees.
However, (2) is generally intractable to compute exactly, and sampling- based approximations are often required. In practice, evaluating its gradient involves (F, F. (x Ve,) - Fmm (x A which must also be approximated via stochastic sampling. In contrast, the concave extension does not possess the same directional concavity that facilitates rounding, but it has two important advan- tages: (i) it can be efficiently parallelized on GPUs (including multi-GPU settings), and (ii) super- gradients can be efficiently obtained via backpropagation. Therefore, in our approach we adopt the concave extension within the AAPGA optimization stage to accelerate computation, while leverag- ing the multilinear extension in the rounding step provide theoretical guarantees. This hybrid strategy combines the computational efficiency of the concave extension with the approximation quality enabled by the multilinear extension, leading both faster optimization and provable per- formance bounds.
dze
SCMs can express a wide variety of functions. For the classic coverage function Fige, 1998), let the element set be U = {ei, .2, 6n). and let there be m subsets 81, 82, 8m C U. For any index set A _ {1, m). we define f(A) = Uie si|, which can be written as an SCM in the following form: fxx) = En,er min (x), 1}. where the linear function Me; assigns coefficient 1 to the j-th component 8j covers e,, and 0 otherwise. Since min .r} is a concave function, this fits into the SCM framework. For the probabilistic coverage function (Lau et al, 2023: Dai et all 2025), assume 81, $2, .... Sm. S U, but the probability that 8; covers e, becomes Pij. Each element ej has associated reward Vn- Given index set A, the expected reward of an element being N
covered by at least one set is: f(x) Ee= By (1 [Is
(1 -tt)).). Taking the logarithm exp EEM zy log(1 - p(y))) where the function
gives an equivalent form: [xx = 2j=1 Uj exp g(x) - exp(-cx), for > O. is concave. Hence, probabilistic coverage is an instance of SCM. The facility location function (Wer et all 20L5) is also an SCM. It selects a subset A from the demand set U such that the facilities in A provide maximum benefit. The overall service quality is given by: f(A) = Ener max w(, u), which can be approximated using the following expression: (x) = Ener log (Ei= I exp(ywa)). As 7y approaches infinity, (x( matches fA) at integer points, and o, is an SCM function.
In submodular maximization, typical constraints include the cardinality constraint |A| < k, the knapsack constraint c(A)= S B, where c(A) = Esea C. denotes the total cost of selecting set A under item costs Ci, and the partition matroid constraint |A n GyI S Tj. Vj [m], where the ground set V is partitioned into disjoint groups G1, Gg...., Gms each with its own rank bound ry. These can be unified under general optimization framework:
max (AA,
(3)
AEC
where C denotes the feasible region specified by the chosen constraint.
OPTIMIZATION FOR SCM MAXIMIZATION
We follow the optimization framework proposed by (Bar al 2018). In this framework, the prob- lem is first extended to the continuous domain via SCM, followed by the computation of supergra- dients. Then, the Projected Gradient Ascent algorithm applied obtain a continuous solution, which is subsequently rounded to an integral solution using pipage rounding. Based on this frame- work, we make the following improvements: (i) we extend the computation of supergradients to the case of non-differentiable SCMs; (ii) we replace Projected Gradient Ascent with the Accelerated Approximate Projected Gradient Ascent method; and (iii) we provide more detailed discussion of rounding techniques under cardinality, knapsack and partition matroid constraints, along with proofs of their approximation guarantees and running time complexities.
Continuous Relaxation We observe that several commonly used functions, such as min(x, (z, 1}. 1- (x), log(1 + æ). and Vi, are concave and can serve as activation functions. However, these functions may not be differentiable at certain points. Therefore, it is necessary explain how to
4

---

Published as a conference paper at ICLR 2026
perform differentiation of SCMs under non-differentiable activation functions. For analysis. consider the right derivative of Φ. We define the superdifferential of F at x by aF(x) = {g E R" F(y) F(x) - 9 (y x), Vy P). Any g E 0F(x) is called supergradient of F at The vector ! - E maj (mx(x)) is element of (F(x), where d'4 denotes the right-hand derivative of di with respect the i-th share. This formulation enables efficient computation of supergradients via the backpropagation algorithm of deep neural networks, leveraging multi nuU parallelization. It effectively addresses the inefficiency of gradient computation in the multilinear extension, which is a bottleneck in the standard continuous greedy algorithm.
Constraints originally defined over the discrete domain {0, 13" can be naturally relaxed to the con- tinuous domain [0, _|". For example, the cardinality constraint of selecting at most i elements from N fl......y n). {x E {0, 13" Ei= 24 S k}, is relaxed {x E [0, 1 Σ 2, S k). Simi- larly, the knapsack constraint with item weights ot and budget B, {x {0, 13 Ei= Q.Y S B}. relaxed to fx E [0. 1]"h
Ei= G,T; I B). Finally, letting A {I....,7) nu be parti- tioned into disjoint blocks Gi,.... Gm with capacities r; E Zzo. the partition matroid constraint {x {0, 13td Eieo, Iz S rj, Vý [m]] is relaxed {x [0, Lieo, T; S Tj V-j E [m]]] For simplicity of notation, we refer to the relaxed constraint polytope P throughout the paper.
Accelerated Approximate Projected Gradient Ascent The AAPGA method is similar to the standard PGA method, with the key distinction that the projection is performed on y("), which is linear combination of x()) and (t--1), rather than directly on x(!), Since the projection is computed only approximately, we define the approximate projection set as
Pi =
{f fx E E ||x - [ (9) + (r(y {6)
where (-) denotes the exact projection onto the polytope P, 8 >>> 0 is the admissible approxima- tion error, and ( E OF denotes subgradient of F at (())
We assume that (x) E (x), i.e., it is one representative point from the approximate projection set. Under this formulation, the per-iteration computational cost remains nearly identical to that of the standard PGA method, while the total number of iterations required is significantly reduced. The pseudocode is given in Algorithm II. The quadratic surrogate function is defined (x.
F(y) (x (--+xxxy,)) (y)( 1/ ||x y/12.
Similar to the classical FISTA algorithm (Beck & Tehoulle, 2019), our AAPGA method also achieves an O convergence rate. The key difference is that, due the 6-approximate pro- jection in AAPGA, we require to be sufficiently small (specifically 8 < O(1/T") to ensure convergence.
Theorem 1. Suppose F is continuously differentiable with Lipschitz continuous gradient, with Lip- schitz constant denoted by L(J), i.e., [V](x) - vf(y)l < L(f) -yll, yll, Vx, E R.. Let x" = arg max F(x) be the optimal solution, and let x() denote the output of AAPGA after T iterations. If the error parameter in AAPGA satisfies 8 O(1/T%), then the algorithm achieves
F(x") F(x(T) < (
(8)
We show in the appendix that for cardinality, knapsack, and partition matroid constraints, an approx- imate projection x' can be computed in O(n log(n/))) time such that || II(=)]l 8.
By leveraging the faster convergence of AAPGA over the standard PGA, we obtain an improved (I - approxxiiatao guarantee. Given the time complexity T Onn² /=2) in (Bai et all 2018), our method achieves significantly faster convergence rate for the SCM maximization problem.
Corollary 1. Assume that F' is continuously differentiable with Lipschitz continuous gradient. For any < 1, AAPGA selects (E33/2n 3/22), then
((X(T) 2 (1-5) F(x").
The number of iterations required by AAPGA is 012 and the query complexity is T (T, +T) 122 + T2)) where T, denotes the computational cost of evaluating the concave extension, and T2 denotes the computational cost of backpropagation.
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Accelerated Approximate Projected Gradient Ascent
Require: SCM concave extension F. constraint polytope P, maximum iterations T, initial parame- ter 01 = 1, step size Lo > 0, scaling factor 33 >>> 1.
Initialize x(1) & arg minxep ||x [-
2: Set y < (0)
3: for t = 1.2...... do
4: The superdifferential (F( is obtained via backpropagation.
5: Find the smallest non-negative integer is such that L, = 3 L1-1 satisfies
F (pit z Q (1)))(()), (())
(4)
6: Set Le 17²x L and update
x(0) Phr (x!11).
(5)
7: Update the momentum parameter
1+ 1 + 4a/
0++1
(6)
2
8: Extrapolate
y(++1) = (() + O2 - (x(1)) - (x-1)
a1+1
9: end for return x (T).
Proof. From Theorem MI we have F(x') F(x(T) I On/TT). To guarantee that F(x 2
(1 --=) =) F(x"), (x)",, it suffices to require (n S =F(x"). This holds when, T On ((112)
Since Theorem II further requires å < 0(1 )T the projection accuracy parameter â must satisfy
5 <
The algorithm in Algorithm II computes the supergradient in Step T times, with each backpropa- gation step for the supergradient having a time complexity of T2, resulting in a query complexity of O(T-T2). Step 5 of the algorithm in Algorithm II each iteration requires verifying whether i, = holds. The number of evaluations of F (p'z (x())) and Qú (P'r (y()), y()) is constant, requiring a query complexity of O(T T.). Since L 2 L(f) holds, we can deduce that equation A is satisfied, and thus L. will not exceed (B((). As T. grows exponentially, the number of iterations that do not satisfy equation is given by log
(3.(5) / log 3, which is of constant order. Therefore, the overall Lo
complexity is T .T + To O (n 1 1/2 + Te)).
Randomized Rounding. After obtaining a fractional solution I, it is necessary to round it to an integral solution. For cardinality and partition matroid constraints, one can apply the pipage rounding algorithm (Calinescu et all 2011), which runs in O(n) time. This method leverages the fact that the multilinear extension satisfies convexity along directions of the form Fm (((tt(e,ee))) where e, (O..... 0, 1, ... 0) is the standard basis vector. Consequently, the rounding preserves the approximation guarantee in expectation. However, under a knapsack constraint, achieving a
(1 z)- approximation via rounding requires time complexity O (nf (f=(==1+1) (Kulik et all 2013).
To address this limitation, we propose ((n)-time rounding algorithm tailored for the knapsack constraint, which achieves a constant-facto approximation of 1/2.
Since the algorithm relies the multilinear extension, (Bai all 2018) established the following relationship between the concave extension and the multilinear extension:
Lemma (cf. (Bai et all 2018)). Let F be the concave extension induced by an SCM, and let F. denote the multilinear extension of the original submodular function. Then, for all x E [0, 1]", the following inequality holds:
max (1 - n) 1 - (-M1exp(-> F(x) & Fm(()) & F(x),
[E(11]]

---

Published as a conference paper at ICLR 2026
Algorithm 2 Knapsack- Crapsaack-Conttraieeedd Maximization of SCM Functions via Rounding
1: Input: Submodular function f. ground set N,, knapsack polytope P, item weights
2: Step I: Best Singleton Selection
3: Identify the best singleton element: arg max.NN f(e)
4: Step 2: Fractional Solution via Gradient Ascent
5: Compute fractional solution [0, 1 using Algorithm II
6: Step 3: Randomized Rounding
7: while more than entry of x is fractional do
8: Randomly select a pair (i,j) such that 0 < In, <
9: Define the direction v e o7 ej
10: Compute feasible step sizes min, max such that both satisfy x + 0v EVP E
11: Update x as follows:
With probability -mmin +
Omin
set x f- x + 0 V
Otherwise, set x f- x 0mnn V
14:
end while
15:
Final adjustment: set any remaining fractional entries of x to
16: return arg m&Xx,e f())
where (xx) minkev
(x)))
max TTR
By Lemma MI the solution (T) obtained by AAPGA can be directly rounded via randomized round- ing. Moreover, through the multilinear extension, this procedure enjoys theoretical approximation guarantees.
Theorem For the SCM maximization problem under cardinality and partition matroid constraints, combining AAPGA with pipage rounding yields the following guarantee:
min my mm:k))
} max my S [(XOOT). (9)
[=f((') 2
max (0==))(1-1) (11-) -1)
min tEV
0E
Under the knapsack constraint, applying Algorithm 2 with AAPGA and randomized rounding gives
minm; .B .B) -B]] EEV max m, max C;
[(((')) 2
max (1 ()- -1) 1 exp -1p² min TE(0.1]
Viexp
((OPT).
The overall query complexity is ( - T2)) for cardinality and partition matroid con- straints, and O(n Ti + /2 for the knapsack constraint.
The approximation bounds above are not fixed constants; however, (Karimi et all 2017) proved that for coverage functions, the approximation ratio reaches 1 1/e - e. This suggests that in many practical scenarios, algorithm can achieve significantly better empirical performance than the worst-case guarantee.
EMPIRICAL EVALUATION
The numerical experiments organized into three parts. First, we demonstrate that AAPGA achieves faster convergence than PGA under the concave extension. Second, we show that AAPGA combined with randomized rounding outperforms accelerated submodular maximization algorithms in terms of both solution quality and computational efficiency. Finally, we evaluate large-scale graph problems, where AAPGA with pipage rounding, enhanced by multi-GPU parallelization, achieves superior performance compared to PGA combined with pipage rounding. All experiments are con- ducted on server equipped with a Hygon C86 7380 32-core CPU, two NVIDIA A800 80GB GPUs, and 256 GB RAM. The system was running CUDA 12.2. Our implementation is open-sourced at https: /ttp:://qithan com/ Lvymathl /tfeeiifiiiiee Sewiilenttuuuuboon Submodular- Maximization
4.1 CONVERGENCE SPEED OF AAPGA
The convergence rate of AAPGA to achieve a (1 E) approximation ratio is T 0(21/2--1/2) while PGA requires T = O 2). Due to Nesterov acceleration, AAPGA exhibits a substantial advantage over PGA.
7

---

Published as a conference paper at ICLR 2026
Facebock Fop Network (Candinaity)
EU Email (Candinality
CA-GrGc (Cardinalit)
Witipedis Vote [Candinalit)
1200
1200
Otpechee
5400
1200
3000
1000
150
200
100
703
150
190
2000
90
100
202
Sleps
Staps
Sleps
5ta5
(Knapsack)
(Knepsact)
CA-GrOz (Knapsack)
(Knapsact)
1300
793
Dieethee Vileo
750
3200
250
200
8
773
$1299
Steg0
FGA
APPGA
50055
Figure 2: Performance comparison between PGA and AAPGA under cardinality and knapsack con- straints.
We consider the coverage function in the SCM setting, defined F(x)=Ein (x),, where m²(x)) denotes the linear function representing the coverage contribution of component in x, and di(x) mi] is concave function. Thus, F(x) is the continuous extension of the coverage function. We compare AAPGA and PGA under both the cardinality constraint {x E {0, 1)"
CjT, E Fz S k} and the knapsack constraint {x E [0, 1]" Ei= C,a S B).
Figure Q illlustrates the convergence behavior of PGA and AAPGA across four representative graph datasets: CA-GrQc, Wikipedia Vote, EU Email, and Facebook Ego Network. The datasets are drawn from the SNAP repository: Facebook Ego Network (348 vertices, 5038 edges), EU Email (1005 vertices, 25,571 edges). CA-GrQe (5242 vertices, 28,980 edges), and Wikipedia Vote (8298 vertices, 103 669 edges).
Across all eight settings (two constraints per dataset). AAPGA consistently outperforms PGA in both convergence speed and final objective value. The advantage is particularly pronounced in the early iterations: for instance, under the knapsack constraint on the EU Email dataset, AAPGA achieves an objective value of 748.7 within just 20 iterations, whereas PGA only reaches 743.8 3.8 after 50 iterations. Likewise, on the Wikipedia Vote dataset, PGA converges to 4600.6, while AAPGA attains a higher value of 4629.0. These results demonstrate that AAPGA not only converges significantly faster in the early stages but also achieves superior final objective values compared to PGA.
In classical PGA, the step size must be carefully tuned to avoid oscillations, particularly when the objective exhibits steep curvature in certain directions. This cautious choice often slows progress along flatter directions, resulting in overall slow convergence. In contrast, AAPGA employs more efficient step size strategy that mitigates oscillations caused by overly aggressive fixed steps while simuitaneously accelerating progress along low-curvature directions. This explains both the rapid initial gains and the consistently higher function values observed across datasets.
4.2 EXPERIMENTS ON SMALL-SCALE SUBMODULAR MAXIMIZATION
In many applications, submodular optimization is often studied under small-scale settings. We focus on the problem of submodular maximization under two types of constraints: cardinality and knap- sack. The objective function is defined the probabilistic coverage problem. Let the ground set be V = 21, n1.. Each candidate element i E 5 C V covers a target node j E V with probability Piy E [o, 1]. The function is given by f(S) = Eeev (1 IIes - -pi)). . In the SCM form, the function is written as fxx Ejev expl ex-e x; log(1 - -P-)) Throughout, we assume an undirected graph G = (V, E) and define the coverage probabilities by Pij = 0.8 if (i, E and Pıy = 0 otherwise, where we further take Pış Pj; for undirected edges and set Pa: = 0.
2,
We evaluate our methods on two synthetic graphs, namely the Stochastic Block Model (2000 nodes, 150 edges) and the Erdōs-Réd Rényi random graph (4000 nodes, 40,031 edges), as well as two real- world graphs: the EU Email network (1005 vertices, 25,571 edges) and the Wikipedia Vote network (8298 vertices, 103,689 edges). On these four datasets, compare the performance of different
8

---

Published as a conference paper at ICLR 2026
Table 2: Probabilistic coverage maximization under a cardinality constraint. Comparison of algo-
rithms on four datasets; for each dataset, the left entry reports the objective value (higher is better) and the right entry reports wall-clock time in seconds (lower better). In each column, the best, second-best, and third-best results are marked with and 1 respectively.
Algorithm
BU-Email
Facehook-ege
Stochastic Block Model
Erdós Rényi
Result
Time
Result
Time
Result
Time
Result
Time
FAST
636.67
0.11
1494.33
1.16
1355.20
0.03
3491.66
0.27
LS+PGB
781.55
0.09
3145.43
1.06
1400.58
0.11
3541.94
0.34
Stream
784.74
0.99
3441.45
25.47
1440.89
1.90
3538.56
6.88
Greedy
864.61
4.96
3676.31*
145.74
1654.00*
9.73
3773.46"
42.02
Lazzer-greedy
853.75
1.02
3610.243
29.18
1628.711
1.98
3748.74
8.44
PGA+Rounding
862.69-
1.68
1661.63
1.49
1427.04
2.09
3652.71
2.50
AAPGAA+ounding
864.60
1.12
3653.14t
1.84
1642.381
1.78
3714.83
1.30
Table 3: Probabilistic coverage maximization under the knapsack constraint. For each dataset, the left entry reports the objective value (higher is better) and the right entry reports wall-clock time in seconds (lower is better).
Algorithm
EU-Email
Facebook-cgo
SBM
Erdös Erdös-Rényi
Result
Time
Result
Time
Result
Time
Result
Time
Stream
826.82
2.08
4629.69
37.88
1986.84
2.00
4023.25
9.02
Lazier-greedy 879.72
1.18
4885.69
34.51
1999.92
1.12
4208.90
7.62
AAPGA+Rounding 874.89
0.86
4850.83
3.55
1999.72
0.48
4183.47
3.38
algorithms under both the cardinality and knapsack constraints. Due to the use of stochastic algo- rithms, the results and runtime of all algorithms averaged over 50 runs.
For the cardinalitycoonstraieedd sctting, we compare against several well-cstablished algo- rithms, including the classical serial methods GREEDY (Nembanser et al (1778) and (Mirzasoleiman et all, 2015), the parallel implementations FAST (Breuer all 2020, LS+PGB (Chen 202I), streaming methods (Badanidiyuru et all 2014), and continuous relaxations with PGA followed by pipage rounding (Baret 2018). Since SCM functions can be efficiently computed on GPUs, we apply GPU acceleration to all methods, regardless of whether they are originally designed as GPU algorithms. We also evaluate our proposed AAPGA combined with pipage rounding (AAPGA+Rounding) under the same constraint. Throughout, we the car- dinality budget to k = 50; that is, each method selects 50 elements to maximize the submodular objective.
For the wrapsack-constraiigg setting, we use as baselines the [ - ((11-1/))apppplaeaa approxxmaxxiinnnonn greedy algorithm Khuller et all (1199)), which we implement with lazy updates to accelerate computation, as well as the streaming methods of Huang et al, (2020), In addition, we evaluate our proposed AAPGA combined with randomized rounding (AAPGA+Rounl Roounding). The knapsack budget is defined as B ~ Unif( 1 //50, Ei= c/20), that is, B is drawn uniformly at random from the interval between Σ e/55 and Σ 222
We evaluate and compare the solution quality and running time of all algorithms on the four graphs, with the results summarized in Tables @ and R
Unless otherwise specified, AAPGA is run for 100 iterations, while PGA is run for 200 iterations. For AAPGA, To 1 2. Under the cardinality constraint, AAPGA+Rounding consistently ranks among the top three objective value across datasets, while providing substantial speedups. For example, the mid-scale Erdös-Rényi random graph, AAPGA+Rounding is 32.3 faster than Greedy. Because Greedy and Lazier-Greedy are difficult to parallelize effectively, they exhibit sig- nificantly higher running times. In contrast, methods that leverage GPU parallelism consistently achieve markedly lower wall-clock time, underscoring the benefits of GPU acceleration for submod- ular maximization at this scale.
Under the knapsack constraint, our method consistently outperforms the streaming baseline in terms of objective value. Compared to Lazier-greedy, it sacrifices small amount of solution quality

---

Published as a conference paper at ICLR 2026
Cardinality Constraint
Partition Matroid Constraint 1-0.11
10.000
PGA Ir=1.0
Objective Valuee
5,000
Objective Value
0.000
4,000
7,000
3.000
6,000
1.000
3.000
Budget (K)
Budget
Comparison of AAPGA with pipage rounding and PGA with pipage rounding under cardinality and partition matroid constraints.
Figure 3:
but achieves a dramatic speedup. For instance, on the Facebook-ego graph, AAPGA+Rounding is nearly 9.72x faster than Lazier-greedy, representing substantial improvement in computational efficiency.
4.3 EXPERIMENTS ON LARGE-SCALE SUBMODULAR MAXIMIZATION
Large-scale submodular maximization particularly challenging due high memory require- ments and the necessity of multi- UPU parallelization. In this experiment, we focus on comparing PGA and AAPGA (instead including other baselines) in order to clearly highlight the benefits brought by acceleration. The dataset under consideration is the Google+ social network, collected from users who voluntarily shared their circles via the "share circle" feature. The submodular func- tion is defined as the number of users covered by selecting seed users (Singer, 2012). The dataset consists of 107,614 vertices and 30, 40,466666 edges. The cardinality budget & ranges from 10 to 5120, increasing exponentially.
As shown in Figure &L the objective value increases monotonically under both cardinality and parti- tion matroid constraints. More importantly, AAPGA consistently exhibits faster growth rate than PGA across all learning-rate settings. Since the cardinality constraint is simpler than the partition matroid constraint, PGA combined with pipage rounding performs comparatively better under the cardinality setting. Overall, these results demonstrate that AAPGA, when integrated with pipage rounding, provides more effective and scalable solution for large-scale submodular maximization.
ACKNOWLEDGMENTS
This work was partially supported by National Natural Science Foundation of China (No. 12131003) and Beijing Natural Science Foundation (No. 7220004).
REFERENCES
Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, Alberto Marchetti- Spaccamela, and Rebecca Reiffenhäuser. Submodular maximization subject knapsack con- straint: Combinatorial algorithms with near-optimal adaptive complexity. In International Con- ference on Machine Learning, pp. 231-242. PMLR, 2021.
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular func- tions. In Proceedings of the twenty-fithh annual ACM-SIAM symposium on Discrete algorithms, pp. 1497-1514. SIAM, SIAM, 2014.
Ashwinkumar Badanidiyuru, Baharam Mirzasoleiman, Amin Karbasi, and Andreas Krause. Stream- ing submodular maximization: Massive data summarization the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 67 170- 2014.
10

---

Published as a conference paper at ICLR 2026
Wenruo Bai, William Stafford Noble, and Jeff A Bilmes. Submodular maximization via gradient as- cent: the case of deep submodular functions. Advances in neural information processing systems, 31, 2018.
Amir Beck and Mare Teboulle. fast iterative shrinkagg-threshholdnn algorithm for linear inverse problems, SIAM journal on imaging sciences, 2(1):183-202, 2009.
Adam Breuer, Eric Balkanski, and Yaron Singer. The fast algorithm for submodular maximization. In Interaational Conference on Machine Learning, pp. 1134 143. PMLR, 2020.
Gruia Calineseu, Chandra Chekuri, Martin Pal, and Jan Vondrák. Maximizing monotone submod- ular function subject to matroid constraint. SIAM Journal Computing, 40(6):1440-166,, 2011.
Yixin Chen, Tonmoy Dey, and Alan Kuhnle, Best of both worlds: practical and theoretically optimal submodular maximization in parallel. Advances in Neural Information Processing Systems, 34: 2021.
Shuang Cui, Kai Han, Jing Tang, He Huang, Xueying Li, and Aakas Zhiyuli. Practical parallel algorithms for submodular maximization subject knapsack constraint with nearly optimal adaptivity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7261-7269 2023.
Shuang Cui, Kai Han, and Jing Tang. Linear-time algorithms for representative subset selection from data streams. In Proceedings of the ACM on Web Conference 2025, WWW '25, pp. 47104721, New York, NY, USA, 2025. Association for Computing Machinery, ISBN 97984007 12746. doi:
10.1 10.114533664400.3711 4899444499....
Xiangxiang Dai, Xutong Liu, Jinhang Zuo, Hong Xie, Carlee Joe-Wong, and John CS Lui. Variance- aware bandit framework for dynamic probabilistic maximum coverage problem with triggered or self-reliant arms. IEEE Transactions on Networking, 2025.
Josip Djolonga and Andreas Krause. From map marginals: Variational inference in bayesian submodular models. Advances in Neural Information Processing Systems, 27, 2014.
Brian W Dolhansky and Jeff A Bilmes. Deep submodular functions: Definitions and learning. Ad- vances Neural Information Processing Systems, 29, 2016.
Marwa El Halabi, Slobodan Mitrović, Ashkan Norouzi-Fard, Jakab Tardos, and Jakub M Tarnawski. Fairness in streaming submodular maximization: Algorithms and hardness. Advances in Neural Information Processing Systems, 33:13609-13622, 2020.
Alina Ene and Huy L Nguyen. A nearly-linear time algorithm for submodular maximization with knapsack constraint. In International Colloquium on Automata, Languages, and Programming. volume 132, 2019.
Uriel Feige. A threshold of In n for approximating set cover. Journal of the ACM (JACM), 45(4): 634-652, 1998.
Satoru Fujishige. Submodular functiioon and optimizaaion, volume 58. Elsevier, 2005.
Alireza Ghadimi and Hamid Beigy. Deep submodular network: An application to multi-document summarization. Expert Systems with Applications, 152:11339) 2020.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. Advances in Neural Information Processing Systems, 25, 2012.
Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 82(4):1006-1032,
2020.
Rishabh Iyer and Jeffrey Bilmes. A memoization framework for scaling submodular optimization to large scale problems. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2340-2349. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2026
Vijay Jaisankar, Sambaran Bandyopadhyay, Kalp Vyas, Varre Chaitanya, and Shwetha Somasun- daram. Postdoc: Generating poster from a long multimodal document using deep submodular optimization. arXiv preprint arXiv:2405.20213, 2024.
Mohammad Karimi, Mario Lucic, Hamed Hassani, and Andreas Krause. Stochastic submodular maximization: The case of coverage functions, Advances in Neural Information Processing Sys- tems, 30, 2017.
Samir Khuller, Anna Moss, and Joseph Seffi Naor. The budgeted maximum coverage problem. Information processing letters, 70(1):39-45, 1999.
Yusuke Kobayashi and Tatsuya Terao. Subquadratic submodular maximization with general troid constraint. arXiv preprint vrXiv:2405.00359 2024.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian pro- cesses: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2). 2008.
Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Mathematics of Operations Research, 38 (4):729-739, 2013.
Xutong Liu, Jinhang Zuo, Hong Xie, Carlee Joe- Wong, and John CS Lui. Variance-adaptive algo- rithm for probabilistic maximum coverage bandits with general feedback. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pp. 1-10. IEFE, 2023.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular functions, Opti- mization Techniques, pp. 234-243, 1978.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):33008873, 2016.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functionsi. Mathematical programming, 14:265-294, 1978.
Yaron Singer. How to win friends and influence people, truthfully: influence maximization mech- anisms for social networks. In Proceedings of the fifth ACM international conference Web search and data mining, pp. 733-742, 2012.
Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack con- straint. Operations Research Letters, 32(1):41-43 2004.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi multi-stage submodular maximization. In International conference on machine learning, pp. 1494-1500 1502. PMLR, 2014.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pp. 1954-1963, PMLR, 2015.
12

---

Published as a conference paper at ICLR 2026
APPENDIX A: PROOF OF THEOREM II
For convenience in the proof, we define the exact projection
PL ()() 1lp (x()) + + (
Since F is defined over R", the maximization problem
max F(x) XEP
can be equivalently reformulated as the minimization problem
min h(x) min (-F(x)) - 1 (x)) = -min xER
(-F(x) -F()))
xER"
XER"
where h(x) ;= Fxx) - (x) and g(x) == (x))
Lemma 2. For any y E IR", if 7 E 0g(z), then with z' = p'y. (y) and z = (r((), the following holds:
Fy)) + L(z - y) -(y) ( -2).
Proof. The result follows directly from the optimality conditions of the strongly convex function QL. Specifically, we have
VF(() + L(plly) -y) -(y) 0,
which further implies
+ + ((PL(y) M/( -)) I)p((y) - )
Lemma 3. Let y E R and L > O. Suppose that F(P' (y)) 2 (PL(()))))
For any x E [0, 11" holds that
h(x) hx) N 1yl2((r) - y12 + L(y py(()) -y) --)- -2LR8.
Proof. From the given conditions, can derive
h(x) - h(p' (x)) h(x) + F(P((y)) 2 h(x) + Q(P)()),))
(10)
By the concavity of F and h, we have
- F()) 2 -Fly) -(x V.
(11)
xx() > (y)) (x- ())) To (y)).
(12)
Adding the two inequalities equation I and equation 12 yields
h(x) 2 -F(y) (x y. VF())) vx(((x))
- (x-1'e -)))(()))(()())))>)))))))))))))) (1)
(13)
By definition,
Q(p)(r)),)) = Fly) + (p - VF())) - ( (1) - y11
(14)
Substituting equation 13 and equation 14 into equation IICL we obtain
h(x) - (()) 2 -(x--'(y>, VFx 41v - -112.
L((x p'. pb,(y)) (11ph(()) y|1² L(x p
-1Ilp's (x) - +ly+ -xp(.(y) - y) - -L(x - (ea--p((x),pppp - PL(())
2 & (x) y11 + +L(y -x,p((x) -y) 2LRR8.
13

---

Published as a conference paper at ICLR 2026
Lemma 4. For the sequence {x((1) y generated by Accelerated Aeceleeaatd.Apppoximmtttt Projected Gradient Ascent, for all 2 we have
v((+1) 2 ||u |1 4.88 a; where wlt) = -(x((()))) 1((x) and ut!) = axx(1) (at 1)x -x.
21, 2 244 x
Proof. By substituting x - x(1) and y((+1) into Lemma B, or alternatively x = xx and
y = yy)(+)) we obtain
21 - -((x(tt1)) 2 |xx(+ -yltt1) | 2 - -y(tt), -x()) (15)
and
-2 2(111)
||x(++]) - y2 + 2(x(++1) y(t+1), ylttl) - x²) - 4.6.
(16)
Multiplying the inequality equation by (at+1 1) and adding it to the inequality equation GG gives
2 [att] - 1)((0) a111 2 a++1|x((+11) - 1(2
2 x((+1) ( -((tt),, (t-1)(t-1)- -(a44 1)x(1) xx)
4R860+11
Multiplying both sides by a++1 and using the identity as = ab+1 - ac-1, we obtain
21,11 (02v11) -a / (((t)) 2 |lau+1 (x(++(((((+)) (x(1+1) - (1+
201+1 (xlctt)) - y(t+1) ar-1y(1+1). - (au+1 - 1)x(1) x")
(17)
-4R8 2
|| (ar+1 1)x(*) -x -x11|
||441y((+1) (at+1 - 1)x(() -x1 4R8 a
The last step follows from the identity In addition, we have the identity
b a|l2 + 2(b
c) = l/b c||2 ccl2.
a+t1 (t) a041x(1) + (ar (x(1)) - ((-1))
Substituting the definition of ( into the inequality yields
2 (2,00)) - ((t || 11 4R8 4R8
Finally, since L1+1 2 L1, we conclude
21 22 ))) 2L 2
(++1)2 0112 4R8 a
We now conclude with the proof of Theorem II
14

---

Published as a conference paper at ICLR 2026
Proof. It follows from Lemma that
h(x(1)) - h(x*) = h(p/, (x -((x")
L1 S 41 1121, (x(1)) - - (y(()
x', P2, - l |xx()) -11 - -11 -x,x -y + 22
-y(1)) + 2L,
41 2 (1x(1) x²1 1|2 111-1ly- (ly - -x11²) + 2L,
(18)
By summing Lemma over to 1, we obtain
24 a2 2L v 2 || 1| 12
u 11 Σ
ARSE.
1=2
Since 01 = 1 and the term |ur|1 can be discarded, we have
LT
Lr 2a |xx(1)
2R Σ of
((T) =
(h(x!)) - h(xx)) + Lia
x211+
2
(19)
Since & S. i, combining equation IN and equation 1B yields the desired bound. Here we omit the proof of the inequality (f + 1)/2 S a t.
2R
EE 12 +1) (T 11/4)
h(x(T)) - -x(x))-((x')) <
2Lr | - x" =11 (141)
T(T + 1)(2T + +1)
2(1+1)² 11 x12 11 + 4RRLT
Lr
3(T + 1)2
(20)
2(T 11y1 x211 4RSTT
T(2T +1)
LT
3
T+1
O(n/T3) + R(T
Recalling that l(x) = ===F(x) - 1x(x), we obtain
F(x') F(x(F)) < O(n/T²) RōL,
(21)
In particular, when 5 (11TT)), the algorithm achieves convergence rate of (n/T2))
APPENDIX B: PROJECTION ALGORITHMS
In this section, we employ projection methods to compute approximate projections for cardinality, knapsack, and matroid constraints in On log(n/8)) time.
PROJECTIONS UNDER CARDINALITY AND KNAPSACK CONSTRAINTS
Consider a knapsack constraint defined by item sizes c (c1, C2.... Cn) and knapsack capacity B. The cardinality constraint can be regarded as special case with 1, and capacity k. The corresponding feasible polytope is
P {x ERE
c x < B, 0 01
For any given point v, the projection problem can be formulated as
min w 2
1 2/(
v
s.t. Σ cau, < B, 0 w; 1
Vie [n].
15

---

Published as a conference paper at ICLR 2026
The corresponding Lagrangian can be written
L(w, 0t, 3, = w v
Σ 1=1
- -BTw w + + (w 1,),
where a E RR, 3 E R are dual variables.
Taking the derivative with respect to yields
wy
Us + ac; -B: 7
Ow;
By the KKT conditions, we have
Baw; 7x(w-11) =0 vi [n].
It follows that the solution takes the form
((a) min max c.
If the optimal solution lies in the interior with E Guy; < B, then a 0 and the projection is simply v. Otherwise, when the solution lies on the boundary with Di=1 c.w. < B, an appropriate must be chosen such that
Σ ((a) = B.
Since w(a) is monotone in can efficiently determine the optimal using binary search. The initial search interval set to [0, max w//c.. Performing bisection until the error is within 8/ V requires (llo((n/)) iterations. Hence, the overall projection can be computed in O( (onlog///)) time.
Algorithm 3 Projection onto the Knapsack Polytope via Bisection
Require: RR" item sizes
(C1, C2; ..., Cn); knapsack capacity B, tolerance 5
1: if V then
2: return
3: end if
4: Initialize z
5: lo + O, hi +- maxie(n] Us/C
6: while hi - lo 8/vn. do
7: a (lo hi)/2
8:
カ= minf 1, m0 vs ac;}
9:
if s > B then
1o +- a
11:
else
hi 6
13:
end if
14: end while
15: f- min max hi- c}}
16: return z
PROJECTIONS UNDER PARTITION MATROIDS
For a partition matroid, the feasible region can be written as
P x 10
Σ x STy, Vj [m]
GEG,
where (G1, Gz...., Gm is partition of the ground set. Hence, projection reduces to solving separate projection subproblem for each block Gj. Each block requires O(G,, log(n/8) time, and summing over all blocks yields the total complexity O(n log(n/8)).
16

---

Published as a conference paper at ICLR 2026
APPENDIX C: PROOF OF LEMMA II
Lemma 5. (Bounds in the tails of the distribution of a weighted sum of independent Bernoulli trials) Let a1, 02:-..... ar be reals in (0, 1]. Let X X2...., Xn be independent Bernoulli trials with E[X,] = Pj. For the random variable Y = 2ij1 aj and E (0, 11.
Pr(v < (1 - EB <e
We now turn to the proof of Lemma
We begin by proving that (2) S F(r). We prove the result by induction on the dimension n.
Base case: When
have
(2) = =00
where F(0) and P(1) are SCM evaluations at the endpoints. Since di are concave functions and (3) is linear in æ, Jensen's ss inequality gives
(1 + (1- x)) s F(x) E))(m())).
Inductive step: Assume the statement holds for dimension n k. For E [0, 1J define:
Fm ny. Fm (c& x) + (1 Fm (ox A x))
where eş denotes the k-th standard basis vector, and éş denotes the vector with 0 in the k-th coordi- nate and in all other coordinates. By the inductive hypothesis, we have
(c, V Vx)= s F(cx V Vx), (oz A Ax) S F(ex Ax).
Using the convex combination and the concavity of f, we get:
(x) S 3t F(ck Vx) + = A x) S F(x).
Hence, by induction, the inequality F(x) (x) holds for all x E [0,
The following proof more intricate. Recall that the multilinear extension is defined as (x) = EA~D__f (A)]. One natural approach is to estimate the probability Pr(f(A) 2 CF(()), which immediately yields the lower bound:
(x) Pr(f(A) 2 CF(x)) CF(x).
We begin by analyzing the function mn- According to Lemma E. we have:
Pr [r[m1(A) (1 E)E < exp (- B'EA-
max(mm))
Since EA-D, [m (A)] mi x, follows that:
Pr [mm (A) < (1 m)m 2] exp (- 17 n/²m1
max(m))
Define the event Bm, (n) = {mi( (A) < E (m, (A)]}. Then we have:
Pr Bmn (n)] < cxp (- (-
172 n²m x 2 max(m1)
the event Bm, (n) occurs, that is, m mI(A) > (1 - 17)E A~ [m (A)), then by the monotonicity of
the function d. we obtain: @(m) (A)) 2 Ø((1 1) A~ [m (A)]). Using the concavity of d. follows that:
Φ(1 (m (1 (EAAEE (A)))) (1 AAD (((m
17

---

Published as a conference paper at ICLR 2026
Hence,
(- n x
Pr Pr(((m)(A)) 2 (1 (dmm 2 - exp
max max(m))
Regardless of whether the events B,n (1) are dependent or not, union bound gives:
Pr[Br(n)] - Σ
Pr(Bm.(n)]
iEV
Therefore, we obtain:
Pr f(A) = Σ ((m, 2 Σ ((
KEV
iEV
Pr([((A) 2 (1 (m)((()m)))))
rpmm
M 1 IV
max EV
exp
2 max(m;))
Combining this with the earlier bound yields:
npmm
) )) Fm (x).
F(x) (1 11) -
max 8EV
exp
2 m
APPENDIX D: PROOF OF THEOREM P
We first analyze the SCM maximization problem under cardinality and partition matroid constraints.
Let F denote the concave extension of f. By applying the AAPGA algorithm to compute &, we obtain
F(x) 2 (1 E) max F(x).
xEP
According to Lemma MI the following inequality holds:
F (x)
2
max (1 17) [1 IV exp (- A(x)) F(x),
ne(0,1]
where
my
min m; k max
(
min .V
2 min ev
max m,
my min m, k holds because lies on the face of P. Therefore, we can further derive the following bound:
max (1 - 7)) - /1/eeepp exp (-7² min (](0.1]
min m, ..kk) F(X)..
max me }
Fm (x)
NEV
Hence,
min m, k)
*)] F(x).
Fx)()) 2 (1-E) max F(x)
2
max (1- (1-e) 1 |V|exp exp
-17² min iEV
XEP
max m,
(22)
By relaxing the expression, we obtain
(1 (1-1)
1 1 /Vlexp
(-1f
min
min my VEV max my
] 2 - e R(v2)
Since pipage rounding guarantees that the integral solution is worse than the multilinear relax- ation, the rounded solution x' satisfies
[X((x') 2 F., (x).
18

---

Published as a conference paper at ICLR 2026
Therefore, conclude that [[f(x)) 2 (1 -1 - e 2((7)) max F(x) 2 (1 (1 -
f(XorT).
xEP
XOPTEC
Since pipage rounding only converts & into x' without requiring any information from F, incurs no additional query complexity. Therefore, the overall query complexity remains
1/2 + +T2)
Pipage rounding effective for both cardinality and partition matroid constraints. At the end of the rounding process, all coordinates are guaranteed to be integral. However, this is not the case for the knapsack constraint: general, the process may leave one fractional coordinate, which requires separate treatment.
During the rounding phase, let &o + 81 + + X5 denote the sequence of intermediate fractional solutions produced by pipage rounding, where Xo = &. At each step & = 0, ......K k 1, the convexity of the multilinear extension F ensures that
mmin
Omax
(8++1
(2t Oxnxx v) + -Omin + +maxx
(St
Omiu v) Fm (8t).
Omin + mmax
By induction, obtain
E( 2 E[ (x) = Fx)
According to Lemma
[x+m( Fm(()
max (1 11) [1 |V eVlpeppp-1> )())) F()).
ne (6,0,l]
where
my
min m,
(
= min REV max
2 min
eEV max max
my x min m holds because x lies on the face of P. Ca Thus, we have the following inequality:
E| (xx)]
max 0
1) 11-
IV exp
(-n²²
min min m, B iEV max m, maxe; F(x). ]
Next, let X denote the integral vector obtained from X by keeping all entries equal un- changed, and rounding all fractional entries down to O. Let arg max.eN s(e). Then we have Fm (xx+1) S f(e),
Fm (xx)
which implies
max Fm (x++1); [(e)) 2 (x +
2 1 2 (x))).
Taking expectation on both sides gives
E|max Fm (x f()H
2
1 [[m
2
-11 min EEV max m, max Ci }
min m, B
max (1 - 1)) 1 - |x|exp
F(X).
nE[0.1]
min iEV max m. max B
min m, B
)
max (1 - =1 17) - 1-IVeex
max F(x). XEP
1
Since
max F(x)
max F(XoPT),
xEP the inequality also holds under the knapsack constraint.
XOPrEC
Since randomized rounding only converts & into x' without requiring any information from F, it incurs no additional query complexity. However, the Best Singleton Selection step requires time complexity O(n Ti). Therefore, the overall query complexity is
0n Ti + +n+ 1/22211/2T))
19

---

Published as a conference paper at ICLR 2026
APPENDIX E: CHOICE OF 7)
In Theorem 2 we establish that the approximation guarantee for the SCM maximiza- tion problem under cardinality and partition matroid constraints is max (1 ==)(1
1)) [ 11-1Vexp exp (-n2 minsev min ma min maxm:
]] and under the knapsack constraint becomes
my jo. (1) -n) |1|V] (-1² mingev mass max cs }] A natural question is: what
the appropriate choice of 17? If is too close to 0, the term 1 - [V] exp (-1² minsev
min min mick max
becomes extremely small; if ry is too close to 1, the factor (1 - 7)) collapses, making overall expression small as well.
Figure illustrates this trade-off:: as r) increases from 0 to 1, the approximation ratio first increases and then decreases. Hence, selecting an appropriate n that maximizes the bound is essential.
REE 0.05
FEET 0.1
0.2
approximation ratio
17
Figure 4: The figure illustrates the trends of the approximation ratios for cardinality constraints as varies, as stated in Theorem E Four curves corresponding min m,/ max m, 0.05, 0.1, 0.2, are plotted. The plot assumes k = 1000 and [V] 10.
In Figure EL we further examine the optimal choice of 7 as the cardinality parameter and the knapsack capacity B increase. We observe that, depending the specific values of ls and B, the optimal 7 may take almost any value within the interval 1]. This highlights that selecting an appropriate is crucial for attaining strong approximation guarantee.
225
0.00
250 002
06
Figure 5: The left figure shows the optimal choice of 7) for the cardinality constraint as A varies, based on the bound in Theorem A Four curves are plotted for min m:/ max m, 0.05, 0.1, 0.2, 0.3, with |V| = 10. The right figure shows the optimal r for the knapsack constraint the capacity B changes. Four curves are plotted for min m;/ max m, = 0.02, 0.05, 0.1, 0.2, assuming [ = 10, max G; = 10.
20


Reviews:
[{"review_id": "BIuR2kczfS", "reviewer": "Reviewer_4AFT", "summary": "This work studies submodular function optimization where the submodular function is a concave function over the sum of modular functions (SCM).  The authors establish a continuous algorithm for cardinality constraint,  whose approximation ratio is (1-\\epsilon) and query complexity is $\\sqrt(n) (T_1+T_2)$, where $T_1$ is the time needed for evaluating the concave function and $T_2$ is time needed for back propagation.  Authors present algorithms for knapsack case with an approximation ratio 1/2-\\epsilon. \n\nI would like to disclose that I have only superficial familiarity with continuous optimization techniques.", "questions": "Please see the weakness\nWhat is the effect of T_1 and T_2? How large could they be in the worst-case?\nIt is not clear to me that the rounding techniques proposed are any different from the known pipage rounding. Can you explain the differences?\nCan you compare the performance with the algorithms listed in lines 59, 60 and 61?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This work substantially improves the query complexity compared to previous works, especially for the cardinality constraint.  For example, for cardinality constraints, the best known query complexity is  $O(n/epsilon)$. Similarly, for knapsack, the best known quesry comlexity isO(nklog^2 n)$. \n\nThe main technical contribution is the development of the Accelerated Approximate Projected Gradient Ascent algorithm, that converges faster than the known algorithms.", "weaknesses": "While the query complexity is smaller, when measured in-terms of $n$, it is not clear what is effect of T_1 and T_2. If they are large, then it is not clear if the proposed algorithm offers any advantage.\n\nTypically, continuous optimization algorithms run slowly compared to the discrete versions. Given that it is not clear how much computational advantage the proposed algorithm offers compared to the LS+PGB algorithm that uses $O(n/epsilon)$ queries", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hSS6S3ox53", "reviewer": "Reviewer_ehgF", "summary": "This paper proposes an efficient algorithm, Accelerated Approximate Projected Gradient Ascent (AAPGA), for maximizing Sums of Concave composed with Modular functions (SCMs). The method applies a Nesterov-accelerated projected gradient ascent optimization directly on the function's concave extension. Theoretically, the algorithm achieves a $(1-\\epsilon-\\eta-e^{-\\Omega(\\eta^{2})})$ approximation guarantee with a \"square-root level\" query complexity of $O(n^{1/2}\\epsilon^{-1/2}(T_{1}+T_{2}))$, where $T_1$ is the cost of backpropagation and $T_2$ is the cost of function evaluation. Empirical evaluations confirm that AAPGA converges faster and achieves superior results compared to the standard Projected Gradient Ascent (PGA) method.", "questions": "1.\tCan the costs of $T_1$ and $T_2$ be made explicit as closed-form expressions? If we consider the traditional value oracle model, what is $T_1$ and $T_2$？\n2.\tThe meanings of the parameter $T_1$ and $T_2$ are not consistent in the paper. For example, let us consider the time of evaluation of the concave extension. In the abstract, it is $T_2$, but in the corollary 1, it is $T_1$. The parameters in table 1 and in the description of table 1 (in page 2) are also not consistent. \n3.\tWhat is the parameter $ \\eta $? It seems this parameter appears in Lemma 1 which shows that $\\eta$ is related to the SCM function itself. Thus if we cannot choose arbitrary small $\\eta$, the approximation ratio of the proposed algorithm may be very bad.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe paper considers a subclass of submodular functions and provides the algorithm with sublinear query complexity.\n2.\tThe paper considers several important constraints in the submodular maximization area. \n3.\tExperimental results are provided to show the effectiveness of their algorithms.", "weaknesses": "1.\tThe meaning of the parameter $ \\eta $ is barely explained in the abstract or the main text, which can be confusing to readers.\n2.\tThe meanings of the parameter $T_1$ and $T_2$ are not consistent in the paper. It is confusing. \n3.\tThe knapsack results seem weak: the rounding procedure sacrifices a $1/2$ approximation ratio by enumerating the largest item in an outer loop.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ls8KKAYASO", "reviewer": "Reviewer_nxbx", "summary": "This paper investigates the maximization problem of the sum of concave composed with modular functions (SCMs), an important subclass of submodular functions, under cardinality, knapsack, and partition matroid constraints respectively. Paper proposes an optimization framework that integrates three key components: continuous relaxation, accelerated approximate projected gradient ascent, and randomized rounding. The experimental evaluation assesses the effectiveness and acceleration advantages of our method from three perspectives: convergence speed, small-scale submodular maximization, and large-scale submodular maximization.", "questions": "The paper discusses how to handle the non-differentiability of the activation function in SCM, but Theorem 1 assumes that $F$ is continuously differentiable. There seems to be a discrepancy between these two statements. Could you please clarify the rationale behind this assumption?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a novel optimization framework that employs the concave extension during the optimization phase to enhance computational efficiency, while leveraging the multilinear extension in the rounding phase to ensure theoretical approximation guarantees. The relationship between these two extensions is bridged by a key lemma, thereby balancing computational performance with theoretical assurance. Furthermore, to address the non-differentiability of certain activation functions in SCMs, the paper presents a supergradient calculation formula based on the right-hand derivative and integrates it with the backpropagation mechanism of neural networks, effectively resolving gradient computation in non-differentiable cases.", "weaknesses": "1. It is unclear whether the results for the randomized algorithms in Section 4.2 represent averages from multiple runs or the outcome of a single run.\n\n2. In the experimental section, several key parameters that affect the performance of the AAPGA, such as the approximation projection error $\\delta$ and the step size $L_0$, are not provided.\n\n3. Some related works on submodular maximization under knapsack constraints may require further discussion to contextualize the current paper, such as:\n\n   * *Fast adaptive non-monotone submodular maximization subject to a knapsack constraint*\n   * *Submodular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity*\n   * *Streaming algorithms for constrained submodular maximization*\n   * *Linear-Time Algorithms for Representative Subset Selection From Data Streams*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FrLa5eKQCZ", "reviewer": "Reviewer_suJC", "summary": "In this paper, the authors study the problem of submodular maximization where the objective function can be expressed as the sum of concave composed with modular functions (SCMs), subject to various types of constraints. The proposed algorithms utilize the continuous relaxation, Accelerated Approximate Projected Gradient Ascent (AAPGA), and randomized rounding.  The method achieves an approximation ratio of $1-\\epsilon-\\eta-e^{-\\Omega(\\eta^2)}$ for both cardinality and partition matroid constraints and $1/2(1-\\epsilon-\\eta-e^{-\\Omega(\\eta^2)})$ for general matroid constraints.", "questions": "1. The parameter $\\eta$ in Algorithm 1 is introduced without explanation, which makes it difficult to interpret the theoretical guarantees.  \n   - Is $\\eta$ assumed to lie within the range \\([0, 1]\\)? If so, it seems that the approximation guarantee is valid only for certain values of \\(\\eta\\), since when $\\eta=0$ or $\\eta=1$, the bound becomes trivial.  \n   - In addition, the scaling factor $\\beta$ does not appear in the theoretical guarantee—are $\\eta$ and $\\beta$ intended to represent the same parameter?  \n   Clarification on this point is needed.  \n2. The definition of the set $P'_L(\\mathbf{x})$ (Line 206) takes a point $\\mathbf{x}$ as input; however, in the actual expression, only $y^{(t)}$ appears. \n    It is unclear what $\\mathbf{x}$ refers to in this context. Please clarify the definition and role of $\\mathbf{x}$.\n3. Can you clarify in detail why the proposed Accelerated Approximate Projected Gradient Ascent method is better than the existing PGA method?\n4. The computational cost of \\textbf{Algorithm 1} is not clearly analyzed. In particular, Line 5 in the pseudocode requires determining $i_t$, which involves evaluating Equation (4) for each possible $i_t$. How is the number of $i_t$ evaluations bounded? \n5. The paper mentions the use of \\textbf{deep neural networks} to accelerate the computation of the supergradient. However, if the objective function is simply a composition of a concave and a linear function, it is unclear why a neural network is necessary for this task.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "1. The paper addresses an interesting problem of submodular maximization where the objective function is formulated as a composition of concave and linear functions. The motivation is clearly presented, and the inclusion of representative examples such as the coverage and facility location functions helps illustrate the relevance of the studied setting.\n2. The authors tackle an important challenge in continuous optimization methods for submodular maximization. While such methods often yield stronger approximation guarantees compared to discrete approaches, their high query complexity and computational overhead have limited their practical use. Hence, the effort to design continuous algorithms that are both query-efficient and computationally efficient is timely and significant.\n2. The integration of deep neural networks into the study of submodular optimization is an innovative and inspiring direction. This approach has the potential to be generalized to a broader class of submodular functions and could open new avenues for combining learning-based techniques with classical optimization theory.", "weaknesses": "The key concern is the poor clarity and organization of the paper. Several important details are missing from the main text, and some parameters are introduced without proper definition or explanation (see the Questions section for specifics). The core ideas underlying the proposed algorithms are not clearly presented, making it difficult to follow the methodological contributions. Furthermore, the paper does not clearly articulate how its technical contributions differ from or improve upon existing work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)