DR-Submodular Maximization with Stochastic Biased Gradients: Classical and Quantum Gradient Algorithms
Authors: Shengminjie Chen
Xiaoming Sun
Wenguo Yang
Jialin Zhang
Zihan Zhao
Venue: ICLR 2026 Poster (2026)
Keywords: DR-submodular Maximization
Stochastic Biased Gradients
Zero-Order Optimization
Quantum Gradient Estimation
Approximation Algorithms
Primary area: optimization

Abstract: In this work, we investigate DR-submodular maximization using stochastic biased gradients, which is a more realistic but challenging setting than stochastic unbiased gradients. We first generalize the Lyapunov framework to incorporate biased stochastic gradients, characterizing the adverse impacts of bias and noise. Leveraging this framework, we consider not only conventional constraints but also a novel constraint class: convex sets with a largest element, which naturally arises in applications such as resource allocations. For this constraint, we propose an $1/e$ approximation algorithm for non-monotone DR-submodular maximization, surpassing the hardness result $1/4$ for general convex constraints. As a direct application of stochastic biased gradients, we consider zero-order DR-submodular maximization and introduce both classical and quantum gradient estimation algorithms. In each constraint we consider, while retaining the same approximation ratio, the iteration complexity of our classical zero-order algorithms is $O(\epsilon^{-3})$, matching that of stochastic unbiased gradients; our quantum zero-order algorithms reach $O(\epsilon^{-1})$ iteration complexity, on par with classical first-order algorithms, demonstrating quantum acceleration and validated in numerical experiments.

Published as a conference paper at ICLR 2026
DR-SUBMODULAR MAXIMIZATION WITH STOCHAS- TIC BIASED GRADIENTS: CLASSICAL AND QUANTUM GRADIENT ALGORIHTM
Shengminjie Chen Xiaoming Sun Wenguo Yang", Jialin Zhang
4.2, Zihan Zhao
1.State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences
2. Schooool of Computer Science and Technology. University of Chinese Academy of Sciences 3. 3.School of Mathematical Sciences, University of Chinese Academy of Science 4. Institute Computing Technology, Chinese Academy of Sciences
ABSTRACT
In this work, we investigate DR-submodular maximization using stochastic biased gradients, which more realistic but challenging setting than stochastic unbi- ased gradients. We first generalize the Lyapunov framework to incorporate biased stochastic gradients, characterizing the adverse impacts of bias and noise. Lever- aging this framework, we consider not only conventional constraints but also novel constraint class: convex sets with a largest element, which naturally arises in applications such resource allocations. For this constraint, propose I/e approximation algorithm for non-monotone DR-submodular maximization, surpassing the hardness result 1/4 for general convex constraints. As a direct ap- plication of stochastic biased gradients, we consider zero-order DR-submodular maximization and introduce both classical and quantum gradient estimation algo- rithms. In each constraint we consider, while retaining the same approximation ratio, the iteration complexity of our classical zero-order algorithms is O(c-3), matching that of stochastic unbiased gradients; our quantum zero-order algorithms reach O(e- iteration complexity, on par with classical first-order algorithms, demonstrating quantum acceleration and validated in numerical experiments.
INTRODUCTION
Diminishing Returns submodular (DR-submodular) maximization has gareered significant interest in theoretical computer science and operations research. While carly studies predominantly ad- dressed discrete settings, the emergence of continuous methods has greatly advanced algorithm de- sign for such problems. Consequently, continuous DR-submodular maximization has become an active research area, particularly given its broad applications in machine learning (Bian al. 2019), social network (Chen et al., 2020 2021; (0236), woon-convex/non-cooee concccvv quadratic programming (Staib & Jegelkal (017), and among others.
Fundamental properties of DR-suboodular functions were initially studied through ultramodular functions (Marinacci & Montrucchio/ (2005): if F is ultramodular, then -F is DR-submodular. Bian et al. (2017b) directly characterized similar properties for DR-submodular functions in con- tinuous domains. While minimizing continuous submodular functions can be done polynomial time (Bach 2019). DR- DR-submodular maximization is NP-hard. For monotone cases, approximation algorithms include Frank- Wolfe variants achieving (1 (1-e- e (1-e-')-approeee "appproximmtion subject to down-closed convex constraints (Bian et al. (0177) that also can be generalized to convex constraints and pro- jected gradient ascent with 1/2-approximation over general convex sets (Hsssani al. 2017). For non-monotone functions, various Frank-Wolfe variant methods have been proposed, offering ap- proximations 1/4 with general convex constraints (Dul 2022) that is also tight (Mualem & Feldman, 2023) and 1/c with down-closed convex constraints (Bian al. 2017a). In addition, the Lyapunov framework in (Du 2022) unifies the design and analysis of aforementioned algorithms. Further improvements for down-closed convex constraints achieve ratios up to 0.385 (Chen al.) 2023a
"Corresponding Author: Xiaoming Sun, sunxiaoming@ict.ecc ict.aa.n

---

Published as a conference paper at ICLR 2026
Table 1: DR-submodular Maximization with Stochastic Biased Gradient Estimation
Iteration Complexity
Approx Ratio
Funs/Cons
Hardness
Quan 0-order
Class
Class, Det
Class, Ran
0-order
1-order
1-order
O
O
1-6
Monotone/ Convex Set
(Bian
(Zhang
1
Vondrák 2009)
al.
al.
201
2022)
1-x(0]
O
Non- Monotone/
(
11-x(0)
Mualem & Feldman
(uu
(Pedramfar
et al. 2023
Convex Set
2022
2023)
(
O
Non-
Thm. 3
Thm.
O (Chen
Monotone /
0.478
O(e
0.385
Down-Closed
Qi 2022
al. 2023a
Thm.
Convex Set
Non- Monotone
1 |1-x(U)]
(
Convex Set with a Largest Element
Unknown
Thm.
Thm.
0.401 (Buchbinder Feldman 2024), which are still gap for the hardness results 0.478 (Qi 2022). For box constraints, a tight 1/2-approximation is proposed by Niazadeh et al. (2020). While these constraints cover numerous application problems, there exist some application problems with other constraint properties, such as containing largest element. For example, in some limited resource allocation, e.g., wireless network resource allocation, our goal to allocate resources to users to maximize the utility function of resource allocation while satisfying the lower-bound constraints the resources each receives, e.g., (x [0, | b), A Rgo b 1- Whether algorithms with higher approximation ratios exist under such constraints remains an open question.
However, the aforementioned approximation algorithms are based on the exact gradient oracle. In practical scenarios such as influence maximization and resource allocation in wireless networks, ob- taining exact gradients is often challenging due to inherent randomness. To address this challenge, gradient estimation via sampling has emerged standard approach, driving the development of approximation algorithms for DR-submodular maximization problems with stochastic unbiased gra- dients. For stochastic gradient ascents, Hassani al. (2017) proposed 1/2 approximation with O(c²²) iteration complexity for monotone DR DR-submodular functions under convex constraints. This was improved by Zhang al. (2022) to an - E ' approximation by incorporating boosting and non-oblivious functions. For non-monotone functions, a modified non-oblivious function enables an 1/4 approximation
stochastic projected gradient ascents (Zhang et al. 2024). Mokhtari et al. 2020) proposed stochastic continuous greedy with the momentum technique to reduce variances, yielding (1 e e1) and e approximation with O iteration complexity for monotone cases and non-monotone cases, respectively. Under high-order smooth assumptions, Hassani et al. (2020) retained the (1 - e-1) approximation ratio with less iteration complexity O(c-²). Further exten- sions include non-monotone functions under down-closed constraints (Pedramfar al. 2023 and
variance-reduced methods (Lian et al. 2024a). On the other hand, [Hzaan et al. (2016) introduced a smoothing method F(x) = E...s ru)], which provides an unbiased gradient estima- tion for v (x) but yields a biased estimation for Fx))), i.c., [ v Fx))]l2 * 0. When applying approximation algorithms with stochastic unbiased gradients, the effective objective be- comes (x)), whose deviation from F(x) can be quantified. Subsequently, this smooth technique is applied to 7ero-sum games with submodular functions (Wilder) 2018), zero-order stochastic DR- submodular maximization (Pedramfar et al. 2023), and zero-order optimization for the finite-sum of DR-submodular functions (Lian et al. 2024b). In addition, (Wan al. 2023) also adopted the ellipsoid gradient estimator for DR-submodular maximization. However, the transformation of the objective function F' to would be unnecessary if an analysis method tailored stochastic biased gradients existed.
2

---

Published as a conference paper at ICLR 2026
Given the widespread of gradient estimators in real-world scenarios, often due to privacy, sam- pling constraints, robust, or value oracle only, gradient estimates typically exhibit bias. While the smoothing technique introduced in (Hazan et all, 2016) provides alternative approach to handle stochastic biased gradients via the smoothing function F(x), direct theoretical analysis is of sig- nificant theoretical and practical value. Although previous works (Ajalloeian & Stich 2020 Driggs al., 2022) have examined stochastic gradient descent under biased gradients in convex optimiza- tion settings, yielding important insights (Bhaskara et al. [2025] Augustino et al. (025). the directly systematic investigation of DR-suboodular maximization with stochastically biased gradients re- mains an open challenge.
Contribution. this work, we investigate the subsuuumo maximization problem with stochas- tic biased gradients subject to several constraints. The main contributions are as follows:
Extend the Lyapunov framework for algorithm design on DR DR-submodular maximization to stochastic biased gradients, characterizing adverse impacts of bias and variance.
Propose an 1/ee approximation algorithm for non-monotone DR-submodular maximization subject convex sets with a largest element, surpassing the previous hardness result 1/4 under general convex constraints by incorporating properties for the largest element.
Illustrate quantum zero-order algorithms achieve the same approximation ratio and conver- gence rate classical first-order algorithms, exhibiting substantial quantum acceleration.
Organization. Section 2 is problem settings and some important inequalities for algorithm design. In Section 3] we extend the Lyapunov framework from exact gradients stochastic biased gradi- ents and propose some approximation algorithms for DR-submodular maximization under several constraints. As direct application, consider zero-order algorithms with quantum and classical gradient estimations in Section Section 5 is numerical experiments. Conclusion is in Section 6
2 PRELIMINARY
In this section, we first explicitly define the problem setting, the gradient setting, and introduce some inequalities of DR-submodular functions for approximation algorithms design. Detailed proofs in this section can be referred in Appendix[A]
DR-submodular Functions. The function F is defined over 1] F is DR-submodular, for Vx < E [0, 1]. , Vk E Rzo and Vi E [d] such that x + k1,, + k1; E [o, 1]" the inequal- ity holds F(x k1,)
F(x) Z Fly k1,) F(y). If is wiie-difffeenniible, then, for < 0. For sake of the following description, there are explanations of some vi,j E [d] 0z,0z,
(²x(x)
notations: 0(t) ||x(t)]l max, (t)), D maxx,yee ||x y V (max y1 (i)eea) and x A y (x;, y/ ) )ee the optimal solution x for DR- DR-submodular maximization. Here, we illustrate the inequality used for algorithm design under convex constraints with a largest ele- ment. Other inequalities related to algorithm design for general convex constraints and down-closed convex constraints are provided in Appendix(A)
Given that all entries of the Hessian matrix non-positive, the function exhibits concavity along nonnegative directions, which implies the following upper bound for the optimal solution.
Lemma 1. If F is non-monotone DR-suboodular function, then
(I -1-0()) (1-)(t)F(x)))) F(x" V x(1) S F(x(() + (VF((()))
x(t))
(I)
Problem Setting. Our objective in this work is to identify a feasible solution within a given con- straint set that maximizes a subboouuu function. The formal statement is as follows:
max xE
F(x)
(2)
where F denotes DR-submodular function that is Lo-continuous and Li-smooth and C is the feasible set. We mainly focus on the following constraints:
(1) C is a general convex set, i.e.,
Vx,y E C and Aλ E [0, 1]. Ax + (1 A)y E C; (2) C is down-closed and convex set, i.e., C is convex and if y E C, then x I y implies x E C: (3) is a convex set with a largest element, i.c.,
convex and there is Xtarge C such that Vx E C, Xtarge-
3

---

Published as a conference paper at ICLR 2026
Gradient Setting. The algorithm in this work is built upon stochastic biased gradient oracle, representing a more practically motivated yet challenging setting. Similar settings have already been considered in convex optimization. The formal statement is as follows:
g(x(()) = (F(((()) b(x(() + m(x((),
where b(x(t)) is the bias and (xx(),, represents the noise following prescribed distribution, satisfying Eg (n(x(t),()
and Vg(n(x(tt.<) * O, i.e., Elg(((())x((t) V Fx(((t)) +b((tt). For notational convenience, the dependence on & will be omitted in subsequent descriptions and [x(g(x([)]] = [l)((()) Because boundless bias and noise will cause the algorithm to fail to converge, in our settings, we assume the bias and the noise is bounded as follows:
Assumption ((m, 76)-) bounded bias).
[|b(x(()|l2 S [V)(( (1)
(4)
Assumption ((M, 7m) bouunded noise).
[[]](((())| & M + (t)
(5)
Therefore, in the algorithm design, the total variance between stochastic biased gradients and exact gradients can be bounded as follows. For notational convenience, we denote the total variance as A() E -
[[)((()))) Sm M) (x)) + (%)) + (t) - t()
[ ([((x()) (|)(()))
(6)
LYAPUNOV-BASED FRAMEWORK WITH STOCHASTIC BIASED GRADIENTS
In this section, generalize the Lyapunov framework in DR-submodular maximization within exact gradients to stochastic biased gradients and illustrate implementation details of our proposed algorithms. For additional technical elaborations in Lyapunov framework and omitted proofs for the theoretical guarantee algorithms, please refer to Appendix
3.1 LYAPUNOV-BASED FRAMEWORK WITH STOCHASTIC BIASED GRADIENTS
The primary objective of proposed algorithms is commence from an initial solution and converge to a solution endowed with theoretical guarantees upon termination. Considering an iteration al- gorithm with the initial solution x(0), the algorithm moves the current solution along a direction with a certain step length in each iteration, i.e., x(tz+1) x(tz) a(tz)v(ty)- Potentially, this difference equation can be viewed as a numerical discretization for continuous dynamic system x() Vx(()= = vx(()). This process can be conceptualized as identifying trajectory originating from the initial solution, such that the final solution achieves theoretical guarantee performances while the trajectory length computational complexity is as small as possible. Considering the algorithm based on the stochastic biased gradient oracle, our algorithm can be regarded as the fol- lowing dynamic system:
(t) Vx(t)= = ((x()).g(((1)
where g(x()) is the stochastic biased gradient. In Du-submodular maximization, the primary ob- jective in approximation algorithm design is to maximize the expected approximation ratio, because the gradient stochastic and biased. Consequently, we construct the following variational problem:
BXF(x(T))
max
F(x*)
S.t. x(1 = f(x(I),g(((I)
x(T) E C2x(0)= Xinitial
where denotes the terminal time, x(0) is the initial solution, and x" is the optimal solution for (2. The objective function in the above variational problem corresponds the expected approx- imation ratio, defindd E[F(x(T)) Solving such fractional optimization problems challenging, as the optimal solution is generally unknown in advance. While an upper bound of the optimal so- lution can be derived based on the properties of the objective function and constraints and such
F(x")
4

---

Published as a conference paper at ICLR 2026
bound typically relies only information from the current solution, substituting this upper bound for the optimal solution remains the fractional problem. It remains intractable to solve directly. To address this challenge, leverage the inherent connection between ratio optimization and differ- ence optimization being generally more tractable and construct a Lyapunov function to streamline the analysis. In addition, we outline a systematic procedure to derive a feasible solution for the above variational problem via this Lyapunov function.
Definition yLaapunov Function). The Lyapunov function associated with continuous-time algo- rithm x(t) for problem Eq. 2 with stochastic biased gradients is as follows:
E(x(t)) (())E[((x(())
(8)
where a(t), b(t) are non-negative and non-decreasing functions depending on time
Assumption 3. The upper bound of the optimal solution F(x") in continuous time as follows:
F(x') Sp(x(t)) (((())) v(x(())) + =((x())B,,lll(x((()) ([x(]))])[[(())))(())(())))))))) ((x ((x))))))))))))])))(x/))0))))) (|x(x()))l
where p(x(t)), ((x(t) are non-negative stochastic functions depending on the stochastic function x(t). The exact form of p(x(())), (x(())) (((())))((((t v(x(t) only relies on function properties and constraints, and can be obtained before designing the algorithm.
Because the function value F' is non-negative. if we can ensure that the Lyapunov function non- decreasing, then we have the approximation ratio for the algorithm x(t) is as follows:
F F(x(0)) B(T) b(0) F(x)) a(T) aTT)
a(0)
((T) b(0) F(x")
E(x(T)) 2 E(x()) = E[F(x(T)) 2
a(T)
Considering the derivative of the Lyapunov function and replacing the upper bound of the optimal solution, we can obtain a sufficient condition to ensure that the Lyapunov function is approximately non-decreasing. If the stochastic biased gradient is strengthened to the exact gradient, this approxi- mate non-decreasing property of the Lyapunov function transitions to an exact non-decreasing one. The accumulation of errors arising from this approximate non-decreasing adversely impact the ap- proximation ratio. Consequently, we reconstruct the variational optimization problem as follows:
((T) - b(0) 1
(b())a(((0)) (A(x(t), 0) [[)()())) de
max
a(T)
a(T)
s.t.
a(t) b(t) p(x(())) 2 0
(10)
xtt) ((t)g(x(t)) a(t) o(x(t))
is known in Eq. 9b. The functions that need to be optimized are a(t), b(t). The aforemennioned procedure is formulated in the continuous time, which essentially serves informal statement for approximation algorithms. Next, introduce the discrete time version. Considering the discrete counterpart of Lyapunov function namely potential function:
where
Definition (Potential Function). The Potential function associated with a discrete-tine algorithm x(,;) for problem Eq. (2) with stochastic biased gradients is follows:
P(x(1)) a((, ((())))))
(11)
where a(t;), b(tz) are non-negative and non-decreasing sequences depending on time series lj. Assumption 4. The upper bound of the optimal solution F(x") in discrete time is as follows:
F(x") (X0
(12)
where alt,), b(tz) are non-negative and non non-decraa,,ng. p(x(t,)), g(x(t,)) are non-negative stochastic functions depending the stochastic sequence x(1;).
5

---

Published as a conference paper at ICLR 2026
Similarly, if ensure that the potential function P(x(ty)) is non-decreasing, have:
b(Ix) -(xx)b((o) b(lo) F(x*)+
a(O) F(x(0))
P(x((x)) 2 P(x(to)) F[F(x((x))
a(tx)
a(tx)
where N the total number of the sequence. Considering the difference between adjacent iter- ations in algorithm x(t;), because the total variance Eq. and the Lı-smooth condition cannot be neglected, there is a sufficient condition to ensure the potential function is approximate non- decreasing. The accumulation of such non-decreasing errors exerts adverse impacts both the approximation ratio and the iteration complexity. Certain variance reduction techniques establish explicit relationships among the total variance, the number of iteration steps, and the step size. These relationships enable the mitigation of variance-induced effects on algorithm performances by increasing the number of iterations. Consequently, we reconstruct the sequence problem as follows:
Σ j=0 2lb(()+)) ((()))((x(()))) (())))((( 4)) (loxx)))))))))))))()((()(()))))) (1)()
b(tn)= - b(tu) a(tN)
max
a(tN)
I Bla(ts+1) |xx(t++1) - x
(13)
a(t.v)
s.t. al(+t1)) a(tz) [b(l++1) b(tz)) p(x(())) 2 0 x(ts+1)= - x((t)) = [b(1++1) ( b(11)))(x((())) (xx(t))
a(tz+1)
3.2 DRSSUBMODULAR MAXIMIZATION WITH STOCHASTIC BIASED GRADIENT
Leveraging inequalities Section 2 and the Lyapunov framework, we design approximation al- gorithms tailored to DR-submodular maximization with stochastic biased gradients under several constraints. When gradients are exact or stochastically unbiased, these algorithms achieve theo- retical guarantees identical to those established in (Du [022] Pedramfar et al.) [023] Chen et al.) 2023a) for convex constraints and down-closed convex constraints. As a demonstration, the main text focuses on convex constraints with the largest element, which is newly introduced in this work. Details for DR-submodular maximization with stochastic biased gradients under convex constraints and down-closed convex constraints, please refer to Appendix B.2 Because a tight approximation (1 e for monotone DR-submodular maximization are reached, our analysis of monotone cases confined general convex constraints.
Theorem 1. [Informal Statement] For monotone DR-submodular maximization with stochastic bi- ased gradients, there is an (1 e-1) approximation algorithm under general convex sets. When considering non-monotone DR- submodularr functions, the approximation results under different con- straints are as follows: [| ||1x(00]l (general convex sets). 0.385 (down-closed convex sets), and [1 [1-x(0]]l (convex sets with the largest element). If the gradient becomes an exact gradient, the iteration complexity for aforementioned approximation algorithms is O(E-1).
4
Next, we illustrate details for convex constraints with the largest element. This is a part of proof for the above theorem. Considering the upper bound of the optimal solution in Eq.[]. we have:
F(x") F(x(t)) + EE, [maxvec (g)(()))
x(t)) EE [ln(((())) + b(x(t))l,VV 0(t)
where the inequality comes from 1 and V x" C. The above inequality implies the explicit formula for p( p(x(1)) q((()))((()))).))))))))))))))))) v(x(t)) as follows:
p(x(t)) = (x())) = 1 1-0(t) 0(t) V Vnux (t) = arg max ()) = -vmax (t) - x(t)
vec
Replacing the above parameter functions into IO
(())) b(t) (()())) 0
a(t)
xx()) (x0)g(x()) ((x(t))
+ x(1)
a(t) (x(())
(14)
a(1)

---

Published as a conference paper at ICLR 2026
Formally, the above procedure is implemented into the continuous time. To demonstrate that the solution is a convex combination of feasible solutions, we use the following limit form.
th a(s) a(s) ((x)(x))) lim Vmax (t) x(t)]e
a(t) c- a(t)
lim x(t + c) - x(t) = c-0
- lim
Because the constraint is convex, the above inequality shows (T) is feasible solution. In addition, due to Vmax(1) (1) I 1, the explicit formula for (()) can be determined as follows:
a(t)
a(t)
11 x(t)) = x(t -1 (1 x(O))e Jo a dr = (1-11 ((0)
(t) a(t) (x(()) =
a(t)
a(t)
ato Combining Eq. with p(x(1)) || |1-x(00) ~n aμ!
the approximation ratio is as follows:
a(O) b(t) b(T) - b(0)
a(0)
(T)
| (0)1(
|1- - x1)xl a(t)
|| x x())l
In
S
a(t)
a(T)
a(T) a(0)
we assume T = 1, the explicit formula is as follows:
a(t) e², b(t) || x00]
The above analysis is based on continuous times. To adopt the potential function for deriving a discrete time algorithm and leverage the explicit formula for parameter functions in the Lyapunov function, we first claim that parameter functions in the Lyapunov function satisfy constraints in Eq. 13):
a(()) (()-))--))----))))))k-)t)tt))))) = eb - e -5- 11 - [y] 2
This implies that only consider the second objective function in Eq. (13) derive the complexity
of the 1-x(0)i approximation algorithm. we set a constant time step 1y N we have:
L1 Ela(t)+1) [[x(t++)) x(t,)
2 VD
Le -) O(e)
([A(((t)).t))
N
2N
j=0
When the first item is 0, i.e., the stochastic biased gradient is strengthened to the exact gradient, our algorithm yields an || |1~x(0)ll= approximation algorithm for DR-submodular maximization with the exact gradient subject to convex constraints with the largest element, after N O(2) iterations. Therefore, obtain approximation algorithm with the following theoretical guarantees.
|1-x(0]]l> O())
Approximation Ratio:
Algorithm:
x(1x+1) = N - + +)((1)+++++++))))))() + - +v((s)
Iteration Complexity: En 20 VD D
L, D(c-1)
< O(e)
2eN
4 ZERO-ORDER ALGORITHMS WITH GRADIENT ESTIMATION
As a direct application to stochastic biased gradients, this section introduces several zero-order al- gorithms based on gradient estimation techniques. First, we adopt quantum gradient estimation method that integrates the Jordan algorithm with quantum state tomography. Subsequently, we intro- duce classical gradient estimation approach that incorporates smoothing techniques and variance reduction methods. Detailed algorithms and proofs in this section can be referred in Appendix
4.1 QUANTUM ZERO-ORDER ALGORITHM
Quantum Jordan algorithm exhibits polynomial acceleration in problem dimensions compared to classical algorithms for estimating gradients. In this section, we employ an improved Jordan algo- rithm, proposed by van Apeldoorn al. 2003) and characterize the variance of this algorithm when estimating stochastic biased gradients using biased function value oracles, which is motivated by the fact that, in finite-qubits, obtain a 8-approximation function value Fş(x) of the exact function F(x) for all Rdd Several parameters in our setup differ from those in (Augustino et al. 2025
7

---

Published as a conference paper at ICLR 2026
Theorem 2.
Let :R. + Rzo be Ly Lu-Lipschitz continuous and L1-smooth function, let a E
RR+
with tn (0,1), and let Fx(x) be the B-approximation finction for F(x) with Vx in B (x,
23
V
Lid
The gradient estimation g(x) returned by the quantum algorithm in Appendix C.1 satisfies
E [llg(x)
when
x²
3 288 (8 36Lod + 1)
The query complexity of the value oracle F is ((8 In 36Lad
For DR-submodular functions and Vx,y E [0, 1] we have:
[F(x) -F(() cly VF e(y 122
x)|
2 ly - S (IVF(0)) + -
The above inequality demonstrates that the DR-subnodular function is continuous with the constant Lo [ 1|2 ||VF(1)) The first inequality follows from Bauchy-Schward inequality and the second is from the property of DR-sur -ubmoduula functions. Combining this inequality with results in Section 3.2 we illustrate that the quantum zero-order algorithm, i.e., B[A(x(t)): 44)
can achieve the performance of classical first-order methods both approximation ratio and complexity.
Theorem 3. For Lo-Lipschitz continuous and Li-soooth DR-submodular functions F, when adopt the algorithm in Theorem 2 to estimate the gradient for F, quanttum zero-order algorithms in Appendix C.1 C.aaciive approximation ratios in Theorem after O(e=!) iteration complexity.
4.2 CLASSICAL ZERO-ORDER ALGORITHM
When only the function value oracle available for queries, the following smooth technique is widely used in classical algorithms, which the expectation for sampling some points through unit ball centered at give point.
= Eu-a [F(x + ru)
where BB = (v R41lV112 1). key advantage of this smooth technique is that unbiased estimation of the gradient for after smoothing function can be obtained by sampling the original function values through unit sphere. Since [Shamir (2017) demonstrated that two-point estimation yields smaller variance, in our work, we also adopt the two-point estimation.
V = -Ku-ssFF + ru)u] = Lu ru) - --x--(ux)pp
2r
where S = (v E |v|l2 = 1}. Leveraging the unbiased gradient for F(((t)), most existing works convert the optimized objective function into the smooth function F(x). whose distance for the original function can be bounded by the Lg-continuous constant the original function. How- ever, when we directly consider the original function, the above gradient estimation is biased estimation for V F (x(().. Next, we illustrate both the bias and the noise are bounded as follows:
Lemma 2. If F is L1 -moothhh then F is L1 smooth and
[|(x((t)]lz Fx(x) VF(x) -(F(x))((((x))) [] S / 16V 116/2
22gr d4y 2"
E [[][((())))]====
To mitigate the above variance in the algorithm, we adopt the variance reduction technique in CCen al. (2018); Mokhtari al. (2020), which introduced momentum term and based the unbiased stochastic gradient. Next, we prove analogous results for the case of stochastic biased gradients.
Theorem 4. For a -smoohhh function F, g(x(L)) the gradient of x(1) returned by a stochastic biased gradient oracle with Assumptions 7 and 2 i.e., g(x(1)) V (x(()) + b(x(1)) + n(x())). yD [[x(((++1) x(1))l12 < N the variance of the di (1 - Pt, dt pxg((((;)) as follows:
B[[[F(((())) de 5 Q(t,))
(j + 9)2/3
8

---

Published as a conference paper at ICLR 2026
where Q(t,) = max 1 +1 ma A 8)2/3 maX [lb(x(t+)) 1 [V((((t)) - dt, 12 92/3
maxkel) [bb(x(t)))l2+166())
Combining the above variance reduction technique and results Section 3.2 the theoretical guar- antee for classical zero-order algorithms with stochastic biased gradients is as follows:
Theorem 5. For Lo-Lipschitz continuous and Lı-smooth DR-submodular functions F, when we adopt the algorithm Theorem estimate the gradient for F, there are some classical algorithms with the stochastic biased gradient oracle achieving approximation ratios in Theorem Martoremmaftee O(E iteration complexity.
classical first-order
classical zero-order
quantum zero-order
Down-Closed
Convex Constraints
Convex Constraints
Convex Constraints
with a Largest Element
Quadratic Programming
9.0046
0.0130
0060
0.0133
4.0033
2.0002
Finita Sum
0.006
9.0023
9.0344
9.0033
0.0004
9.0013
100
0.009
0.0217
0.0030
0.077
0.0007
Coverage
0.00.3
0.0045
0.0004
0.0035
20
Figure 1: Comparison of classical first-order algorithm(blue). quantum zero-order ggree), and classical zero-order algorithm(orange) with d = 3. The x-axis is the number of iterations. The y-axis is the function value.
NUMERICAL EXPERIMENTS
In this section, we evaluate algorithms proposed in Section 3.2 and Section on three standard test problems: DR-submodular quadratic programming, finite sums of DR-submodular quadratic functions, and regular coverage functions. The consider three constraint settings: convex constraints, down-closed convex constraints, and convex constraints with a largest element. These problems are widely used benchmarks Du-uuuoodular maximization (Bian al.] 2017b] Chen et al.) 2023a Lian et al., 2024b) with practical applications such scheduling (Skutella (2001)) and demand forecasting (Ito Fujimaki (2016)). Due to the high computational cost of classical simulation of quantum algorithms, only set 3. For settings of the problem, parameters of the experiment, and more experimental results, please refer to Appendix D
In Fig I under general convex constraints, quantum zero-order algorithm exhibits faster conver- gence than the classical zero-order algorithm, while achieving solution quality comparable to that of the classical first-order algorithm in DR-submodular quadratic programming and its finite-sum. For

---

Published as a conference paper at ICLR 2026
Table 2: The rough analysis of clock times for phase estimations quantum gradient algorithms
Dimension
Errors
Depth
Qubits
Clock Time
Dimension of Vector
CLG = 0.1
= 203
~ 130
2 20μss
~ 2130
d = 10
CALG = 0.01
394
190
z 39μs
2
CALG 0.001
2 543
230
s 54us
Rd 2230
EALG = 0.1
2 512
~ 1600
Ra 5lus
R 2 1600
d = 100
EALG = 0.01
796
2300
Rs 79us
R3 24300
EALG 0.001
1002
2600
100μs
A 24600
down-closed convex constraints, the quantum zero-order algorithm retains faster convergence than the classical zero-order algorithm. It trails the classical first-order algorithm slightly in solution qual- ity for DR-submodular quadratic programming but still outperforms the classical zero-order algo- rithm. Under convex constraints with the largest element, the quantum zero-order algorithm attains convergence speed close to the classical first-order algorithm, with both outperforming the classi- cal zero-order algorithm in iteration complexity and solution quality for DR-submodular quadratic programming and its finite-sum. Although a degradation in solution quality is observed for regular coverage maximization, the convergence rate still surpasses that of classical zero-order algorithm. Numerical experiments demonstrate quantum accelerations.
To obtain general yet rough understanding of the clock-time performance for quantum gradient estimation algorithms,, we first assume that the time-consuming for singlc/double qubit gate is ap- proximately 50/100ns, an achievable assumption with the existing quantum technology. Because a quantum algorithm implemented and gates at the same depth can be executed in parallel, we can construct a rough relationship between clock times for quantum algorithms and depth for their corresponding quantum circuits. Numerical details are in Tab Thus, the clock time for phase estimation is about 100μus when the dimension d 100 and the numerical errors EALG 0.001. Notably, preparing quantum states required as input for gradient estimation algorithms depends on the depth of the quantum circuit for the value oracle F, which varies by case and cannot be uniformly characterized. If we consider the quadratic function, the depth for value oracle F on quantum circuits is roughly (dd). Assuming that the copies of (ı²), required as input for the quantum algorithm Theorem 2 can be prepared simultaneously across multiple quantum computers, the total clock time for quantum gradients esti-
quantum circuits consists of several single/double qubit gates,
mation algorithm is about few hundred js when the dimension d = 100 and the numerical errors
EALG 0.001. With the development of quantum hardware, the time-consuming of this quantum gradient estimation algorithm is expected to be further reduced.
6 CONCLUSION
In this work, we study the continuous DR-submodular maximization problem with stochastic biased gradients. First, we extend the Lyapunov framework originally developed for exact gradients to stochastic biased gradients by characterizing the adverse impacts of bias and the noise. These in- sights are further employed to design approximation algorithms for DR-submodular maximization under three constraints. For a novel constraint, convex sets with largest element, propose 1/e approximation algorithm, surpassing the prior 1/4 hardness result under general convex constraints by leveraging the largest element. In addition, we consider zero-order DRssubmodular maximiza- tion as a direct application for stochastic biased gradient oracles. Our quantum zero-order method attains the iteration complexity O(c-1), outperforming the classical iteration complexity O(c-3). Notably, it also matches the performance of classical first-order methods in both approximation ratio and complexity, demonstrating substantial quantum acceleration.
ACKNOWLEDGMENTS
This work was supported in part by Quantum Science and Technology- -atioonal Science and Tech- nology Major Project under Grant No. 2024ZD0300500 and the National Natural Science Founda- tion of China Grant Nos. 92465202, 12501450, 12571382, and 62272441.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Ahmad Ajalloeian and Sebastian Stich. On the convergence of SGD with biased gradients. arXiv preprint arXiv:2008. 0000:2008000055,,, 2020.
Brandon Augustino, Dylan Herman, Enrico Fontana, Junhyung Lyle Kim, Jacob Watkins, Shou- vanik Chakrabarti, and Marco Pistoia. Fast convex optimization with quantum gradient methods. arXiv preprint arXiv:2503. / 2025.
Francis Bach. Submodular functions: From discrete to continuous domains. Mathematical Pro- gramming, 175(3):419-559, 2019, doi: 10. 11t1//100000-11--2488580
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Descent with misaligned gradients and applications to hidden convexity. The Thirteenth International Conference on Learning Representations, 2025.
An Bian, Kfir Levy, Andreas Krause, and Joachim M Buhmann. Continuous DR-submodular max- imization: Structure and algorithms. In Advances in Neural Information Processing Systems, volume 30, 2017a.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non-convex optimization: Submodular maximization over continuous domains. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 111- 120, 2017b.
Yatao Bian, Joachim Buhmann, and Andreas Krause. Optimal continuous DR-submodular max- imization and applications to provable mean field inference. Proceedings of the 36th In- ternational Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 644-653, 2019.
Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for DR-submodular functions. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, STOC 2024, pp. 1820-1831, 2024. ISBN 9798400703836. doi: 10.1 1,111466688.0. 3649630.
Lin Chen, Christopher Harshaw, Hamed Hassani, and Amin Karbasi. Projection-free online opti- mization with stochastic gradient: From convexity to submodularity. In International Conference on Machine Learning, pp. 814 123. PMLR, 2018
Shengminjie Chen, Donglei Du, Wenguo Yang, Dachuan Xu, and Suixiang Gao. Continuous non-monotone dr-submodular maximization with down-closed convex constraint. arXiv preprint arXiv:2307.09616 2023a.
Shengminjie Chen, Wenguo Yang, and Suixiang Gao. Positive evaluation maximization social networks: Model and algorithm. IEEE Transactions on Computational Social Systems, 10(3): 1402-1413, 2023b.
doi:
Wei Chen, Weizhong Zhang, and Haoyu Zhao. Gradient method for continuous influence maxi- mization with budget-saving considerations. Proceedings of the AAAI Conference on Artificial Intelligence, 34(01):43-50, 2020. doi: 10. 10.1609/aaai, (349//aai.334111... v34i01.5332.
Wei Chen, Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Network inference and influence maxi- mization from samples. Proceedings of the 38th International Conference on Machine Learn- ing, volume 139 of Proceedings of Machine Learning Research, pp. 1707-1716, 18 24 Jul 2021.
Derek Driggs, Jingwei Liang, and Carola- Birlaa- Schönlieb. On biased stochastic gradient estima- tion. Journal of Machine Learning Research, 23(24):1-43, 2022.
Donglei Du. Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. arXiv preprint 22X.v:2205.1244 2022.
Hamed Hassani, Mahdi Soltanolkotabi, and Amin Karbasi. Gradient methods for submodular maxi- mization. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17 17, pp. 5843-5853 2017.
11

---

Published as a conference paper at ICLR 2026
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradi- ent++: (non)convex minimization and continuous submodular maximization. SIAM Journal on Optimization, 30(4):3315-3344, 2020. doi: 10.1137/19M1304277.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
Shinji Ito and Ryohei Fujimaki. Large-scale price optimization via network flow. In Advances in Neural Information Processing Systems, volume 29, 2016.
Yuefang Lian, Donglei Du, Xiao Wang. Dachuan Xu, and Yang Zhou. Stochastic variance reduction for DR-submodular maximization. Algorithmica, 86:1 335--136,,, 2024a.
Yuefang Lian, Xiao Wang, Dachuan Xu, and Zhongrui Zhao. Zeroth-order stochastic approximation algorithms for DR-submodular optimization. Journal of Machine Learning Research, 25(391): 1-55, 2024b.
Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic non-smooth non-convex optimization. Advances in Neural Information Processing Systems, 35: 26160-26175, 2022.
Massimo Marinacci and Luigi Montrucchio. Ultramodular functions. Mathematics of Operations Research, 31-33,3 2005.
Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. Stochastic conditional gradient methods: From convex minimization to submodular maximization. Journal of Machine Learning Research, 21((055:1 -9,, 2020.
Loay Mualem and Moran Feldman. Resolving the approximability of offline and online non- monotone DR-submodular maximization over general convex sets. In Proceedings of The 26th International Conference Artificial Intelligence and Statisties, volume 206, pp. 2542-2566 2023.
Rad Niazadeh, Tim Roughgarden, and Joshua Wang. Optimal algorithms for continuous non- monotone submodular and DR-submodular maximization. The Journal of Machine Learning Research, 21(1):4937-4967, 2020.
Mohammad Pedramfar, Christopher John Quinn, and Vaneet Aggarwal. A unified approach for maximizing continuous submouuau functions. In Proceedings of the 37th International Con- ference Neural Information Processing Systems, 2023.
Benjamin Qi. On maximizing sumss of non- non-monotone submodular and linear functions. arXiv preprint arXiv:2205. 01.22555157744 15874, 2022.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Martin Skutella. Convex quadratic and semidefinite programming relaxations in scheduling. J. ACM, 48(2):206 242, mar 2001. doi: 10. 10.1145/375827.37555))
Matthew Staib and Stefanic Jegelka. Robust budget allocation via continuous submodular func- tions. In Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 9230-3240, 2017.
Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomog- raphy using state prataarrepaattion unitaries. In Proceedings the 2023 annual ACM-SIAM symposium on discrete ulgorithms (SODA), pp. 1265-1318. SIAM, 2023.
Jan Vondrák. Symmetry and approximability of submodular maximization problems. In 2009 50th Anmual IEEE Symposium on Foundations of Computer Science, pp. 651-670, 2009. doi: 10. 109/
FOCS.2009.25 2009.24 24.
12

---

Published as a conference paper at ICLR 2026
Zongqi Wan, Jialin Zhang, Wei Chen, Xiaoming Sun, and Zhijie Zhang. Bandit multi- linear DR- submodular maximization and its applications on adversarial submodular bandits. In Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Ma- chine Learning Research, pp. 35491-35524, 23-29 Jul 2023.
Bryan Wilder. Equilibrium computation and robust optimization in zero sum games with submodular structure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Qixin Zhang, Zengde Deng, Zaiyi Chen, Haoyuan Hu, and Yu Yang. Stochastic continuous submod- ular maximization: Boosting via non-oblivious function. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 26116 111166261444 17-23 Jul 2022.
Qixin Zhang, Zongqi Wan, Zengde Deng. Zaiyi Chen, Xiaoming Sun, Jialin Zhang, and Yu Yang. Boosting gradient ascent for continuous dr-submodular maximization. arXiv preprint 24X1::200100830, 2024.
13

---

Published as a conference paper at ICLR 2026
THE USE OF LARGE LANGUAGE MODELS
We acknowledge the assistance of the large language model in polishing the English expression of this article.
A THE PROOF FOR SECTION 2
In this section, we prove some important inequalities for DR-submodular functions that are essential ingredients the design of approximation algorithms. First, we re-state the definition of submod- ular functions and DR-submodular functions.
Definition 3. The submodular function F defined over 104, i.e. F [0, 1]a - IR, satisfies the following inequality:
F(xVy) + F(xAy) S F(x)+F(y)) Vx, E [0,
The above inequality can be rewrite as the weakly diminishing return property. For Vx S y E [0, 1]s, Ak E R20 and Vi E [d] with 24 Ys such that x + kli,y kl; [0, 1]4, the inequality holds:
F(x+ k1,) F(x) 2 F Fly) viV= {j E [d] y₁}
When F is twice-differentabble its Hessian matrix possesses the following properties
Fx) SO Viijiijj
dr,Ox,
Definition 4. The DR-submodular function F defined over [0, 1]d i.e. F [0, + R, for Vx S y e [0, 1Js vk E Rzo and Vi E [d] such that x + kl,, y + k1; E [0, 1]2. the inequality holds:
F(x k1.) F(x) 2 Fly k1,) - Fly)
When F is diieediiferentiable, its Hessian matrix possesses the following properties
F I 50 vi.j e [d]
dx,dx,
Based on the above definitions, evident that DR-submodularity stronger than submodularity. In some scenarios. the submodularity can be equivalently described the weak DR-submodularity. which retains diminishing returns in dimensions with the same component. Leveraging the dimin- ishing return and the submodularity, the followings illustrate inequalities for approximation algorithm design.
Lemma 3. If F is a monotone DR-submodular function,, then
F(x") S F(x" x(()) S F(x(1) (VF(x()):x(1)v -
(15)
a non-monotone DR-submodular functiioo then
(1- (1-(())(x')) F(x" V vx()) ( x(1 VX -x())
(16)
Proof of Lemma 3 Because all entries of the Hessian matrix are non-positive for DR-submodular functions, for all non-negative vector v E IRd we have:
V''2
F(Ax+
A)y)
2 AF(x) + -1 A)F(()
where x y E [0, 1) This inequality implies the concavity along with the non-negative directions for DR-submodular functions. By leveraging this partial concavity, we have:
F(x(t) V xx) F(x(t) + x(t) vx" - x(t)) < Fxx(t)) + (VF(((t)) x(t) Vx x(t))
where vt) = x(t) vx* - x(t) is non-negative direction, i.e., F is concavity along with v(t). If F is monotone, then have:
F(x") & F(x(() V x & F(x(() (VF(x((), x vx(() x(1))
14

---

Published as a conference paper at ICLR 2026
If F is non-monotone, then we have:
F(x(t)) + (VF(((t)) x" Vx(t) - x(1)) 2 F(x" V x((t)
F((1 - 0(1))x -00))x+000( + vx= x
O(1)
2 (1 ((t))((x) ((0)F(x( x(1) V x- -x"
O(t)
(1 ((1)F())
where ((t) ||x(t)] If O(t) s |xx())l it will cause x* + x(UVx"'xx' to be outside the domain ((1)
[0, 1]9, making the function value undefined.
When we have much detailed description for x(),, i.e., the upper bound for the x() can divided into a partition V.U. i.e., VnU = 0 and V UU [d], we can obtain another inequality to estimate the upper bound for the optimal solution.
Lemma 4. Denote (t) = [t)()) = maxiev (t),, (rr(t) [(x max,et (z)( If (1) - (I), then, for a non-monotone DR-submodular funccc function F, we have
u(t)(1 0v (1)) ((()))()))())()))))))))))))))))) (VF(x(()),x()) (x" A (u(t)L V vo(()v)) x(1))
+ (1 (1- u() (1-0))111000)) Bv())) F(x Alv)
- 0r (0o(())ov(1)) F((x A (u(l) v v(()l)))
+
(17)
where u(t), e(t) are parameter fuuntiions in these two parts U, V.
Proof of Lemma For the sake of description, we set oy (t), 0y ( and denote z x" A (u(t)lv V v()]vv). Considering the concavity along with the non-negative direction in these two components respectively, we have:
L (x(1) V x)
F(x(() V2) 2 (1 0U) F(z) + OuF a
OU
(1 0u) F(z) 0g P(PB VP VPB, V VZBa)
du Bv F(ps, V Vpg V V2B.)
2 (1 (1) F(x) + 0y
fu F(z) + (0u - (v) (F(z) F(z lv)) 2 (1 F))
(1 0y) F(z) (Bu 60) Fl) F(zV1v)
where B,, B2, Bg is the partition for the dimension set [d], i.e Bi = (i E [d] : : 2.)
E [d] vi 2i, 5 Bv
00 BB
B3 = {ie [d] rr z,, p: 86 and p = + (x(1) Vz-
Pai V VPa, V PB. The first equality comes from Ps, 2B, P3. > PB. 2B i.e.,
PB, VPв, VPB, = PB, Vps, Vps, VZB, The first and the third inequality comes from concavity along the non-negative direction. The last inequality comes from the definition of DR-submodular function, i.e., F(PB, Vzn, V Vpn,) + P(2vIv) 2 + +F ly Vpn, Van, Vpn)). Replacing
with x" (u(t)lo V v(()lv), we have:
F x(1) V (x" A (u(1)lu V v((())))) 2 (1-00) F(X (u(1)to vo(()lv))
(uu Bv) F F((x (u(t)lo v=(t)lv))viv)
2 vv) [Fxx A (u(l))t V vo())t)) + F(x A (1v v v((()t))) - F(x A Av)
(0v - vr) (v)(( FF [(((x( (u(t)1u vo011)))))))))
2 u(t) (1 8v ((())((x)))))))))))))) - (1- (1- 8v) A1x)
- (or - (0u-
-rr rr r(x (u(()lo vlv)
15

---

Published as a conference paper at ICLR 2026
The second inequality comes from F(x" A Alv) F(x A (u(t)Lv Vo(()lv)) V(())))) F(x* A (u(()] A 1v) e())lv) with the non-negative direction. Therefore, we have
r(x' (Iv vu(()l()). The third inequality comes from the concavity along
u(I) (())11 - (00)))(0()))()))) (F(()))))()(((((())))))))))))))) + (VF(X()), V (x* A (u(1)t vo(()v))) - x(1))
+ (1- (1-0))) (11-00)(1-000) A
+ (ou(t) ( -r((t) ((xx (u(t)le v o(t)lv)) viv
The above inequality only consider the non- non-negative direction x(t) Vx* x(t). When we consider
the another non-negative direction x(t) - x(t) A x" simultaneously, we can obtain the following upper bound for optimal solutions.
Lemma 5. For non-monotone DR-submodular function F, then
(1 F((( - F(x" V x(t)) 2F(((t)) + (VF(x(t)), - -x(t))
(18)
In addition, if xt) is a stationary point, combining two non-negative directions x(t) V x x((t) and x(t) x(t A xx, have:
& F(x(t)), va E [0, 10,
(19)
Proof of Lemma 5 When we consider the following two non-negative direction x V x and xxx" simultancously, we have
V F ( x(1) x(1) Vx x(t) 2 - x()), -x xx(()) F(x(t)) -(x()) Ax)
where the inequality comes from the concavity along with the non-negative direction. Combining the above two inequalities, we have
(VF(x(t),x* x(1)) 2 F(x(t) + F(x(t) Ax')
- (x((()))
Because the non non-negativity for the function F, we have
(VF(x(t)) x x(t)) + (F(((t)) 2 F(x(t) Vx) + v F(x((t) A Ax')
2 F(x(t) Vx*) 2 (1 ((t))
If x(t is a stationary point for DR-submodular maximization, i.c., Vy C.O 2 (VF(x(()),)- x(t),, leveraging the above inequality, we have
F(x(() V y) + F(x(() A 2F(((()
In addition, when the constraint is down-closed and x(f) is stationary point, i.e., Vy E C we have x(t) A E C, it implics
F(x(1) (x(1) A)) F(x(1) x(1) AY) < 2F(((()
The convex combination for the above two inequality, we have
( Ar) < F(x(!)), [0,
B DETAILED DESCRIPTION SECTION 3
In this section, first provide detailed description of the Lyapumov framework. We then demon- strate how to apply it to design approximation algorithms for susuuuuou maximization using stochastic biased gradients.
16

---

Published as a conference paper at ICLR 2026
B.1 DETAILED DESCRIPTIONS LYAPUNOV FRAMEWORK
The primary goal in designing approximation algorithms is to find an algorithm that achieves the highest possible approximation ratio. This objective is referred to the ratio maximization prob- lem E First, we illustrate the relationship between the ratio maximization problem and the difference maximization problem.
Lemma 6. If (T) and a are the optimal solution and the optimal value of maxx(() F(x))
([F(X(T)
respectively, then (T) is the optimal solution of (a)x(() B[F(((T)) - ax"(x)).
Proof of Lemma 6 Denote xT(T) and a are the optimal solution and the optimal value for ratio maximization problem, i.e., X arg EAC [[F(x(T) max [[F(x(T)) F(x)) Suppose
Fix")
XA is not the optimal solution for maxx(T) E[F(((T)) aF(x*). Then, there is a solution XB (T) ACG such that
B[F((x(T)) - oF((x) >BDD>>>FFFFFE E[F(xA aF aF(x'))x))))))))))))))())) B[F((B(T))
>
F(x*)
That is contradiction with the optimal value a. Therefore, x. (T) is the optimal solution for maxx(T)eAcc [[](x(())))o[(((
Leveraging Lemma 6 and regarding the objective value of Eq. 7 as (t) that depends on the current time I, we reformulate the ratio maximization problem as the difference maximization given in (2.
max
x(t) ((x(t).g(x(1)
(20)
x(T) E C, x00) = Xinitial
a(t) where write (t) as b(t) and x(0) is the initial solution chosen before algorithm design. For obtaining the explicit solution of the Eq. (2). we construct the Lyapunov function in Definition [ inspired by the objective function, and design algorithms by remaining non-decreasing Lyapunov function. Considering the derivative of the Lyapunov function:
E(x(t)) 2((t)F(((()) - b(t) p(x(t)) F(x(t)) - b(t)g(x(() [[n(x(t)) + b(x(t)ll [x(((())l + =(()(VV(((())) - ((0(((()))(((((())((
z)(t)F(x(t)) - ((x())(((()()))))))))) F(x(())
+ ((())g((()),x())) - ((0)(((()))) (g(((()) ((x(1)))
-a(1) []n(((()) b(x(())ll ||x(1ll
(xt)) [|n(x(t)) [|n(x(()++b(x((()))))))) bbx(t)) [[(((())]l
The first inequality is obtained by substituting the upper bound of the optimal solution from (q. Since the bias and noise are from gradient estimations and cannot be neglected within approximation algorithms, taking the expectation FFy both on two sides, we establish a sufficient condition such that the Lyapunov function remains approximately non-decreasing:
((t)) b(t) p(x(t)) ((x)())()) v(x(t))
+ =(((() 2 (2)(0))(()) (( [[((()))lla)
x(t)= a(1)
The above errors come from stochastic biased gradients which is bounded by Assumption | and When we ensure that the Lyapunov function is approximately non-decreasing, we have:
F(((T)) Z F(x(0)) 1h" (x))) (A)))(((())) [[(((()))]]]
B(F(((T)) 2 b(T) b(0)
a(0)
F(x*)
a(T) F(x(0)
a(T)
1
[A(x(t), t) [[x(((t)]]l) dt
a(T)
17

---

Published as a conference paper at ICLR 2026
The above procedure implies that the approximation ratio is (TT)b(0)
a(T) when ensuring the approxi- mately non-decreasing Lyapunov function. Consequently, we reconstruct the variational optimiza- tion problem in (2) as follows: the target is to maximize the approximation ratio while minimiz- ing errors arising from stochastic biased gradients, with the constraint that the Lyapunov function is approximate non-decreasing.
b(T) 6(0) 1
a(T) L'" 26(t)g(x(())((A(((()) [|)((((t))]
max
a(T)
s.t. a(t) b(t) -((((t))) 20
b(t)g(x(1)) v(x(t))
x(t) a(t)
The above procedure is formulated in continuous time, serving as a theoretical construction rather than directly implementable algorithm. Next, we illustrate how the potential function introduced in Definition 2 can be employed in the design of discrete-time algorithms. Considering the difference between adjacent iterations in algorithm x(2)):
P(x((3-1)) - = -()
- -((H))
(((+)))(VFF(((())( x(1)) L1 ||x(1++1) x(())
-((t)))) (0((+1) =((x))
= - x(t)) 1T |x((x+2) - x(tz)11
+ -
=((x)))((x')
xx(t))
2 a((x((t)), (x()))))())))(( - x(t,)] - [b(t)+1) b(t, b(t:)l((((())))xxxx())
Ina(t;t1)
2 [x((++1) - x
+ [a(t)+1) a(t)) - (b(t)+1) - -(t,)
a(()+1)(((x((())) + =(x(()))xxx(x)) x((4))
-
(|((((t))+ +n(((t))) [x(((())]
Taking the expectation both two sides, there is sufficient condition to ensure the potential
function in Definition 2 is approximately non-decreasing:
(a(t)11) - a(t,) - [b(t,-1) - b(t,)) p(x(t;)) 20
x(ts+1) -((,))))x(tt) bic, bit, exx(t)))
all++1)
P(x(t++1)) - P(x(t,)) 2(b(()+2)) ((x (loxxt) (1x(x(t)))11
L1 Ela(ts+1) [|x(1++1) x(+))
When we ensure that the potential function is approximately non-decreasing, we have:
N
P(x(tN)) 2 P(x(to))
- - Σ - (()))))))(((((()))))))))))1))111 (((((()))
y=u
L [lo(t))))l((()))
$
E[F(x([N))] b(tN) - b(to)
alto) F(x(to))
F(x")
a(lN)
a(IN)
- (b(1))))MM)))]44(A))44444) (l [(((()))) 4 B(a((++1) ([x(t+1)))(()) x(t)))1
a(tN)
18

---

Published as a conference paper at ICLR 2026
Similarly, the above procedure implies that the approximation ratio is b(tx)=b(to) a(tx) when ensuring the approximately non-decreasing potential function. Accordingly, we reconstruct the sequence problem as follows: the target is to maximize the approximation ratio while minimizing errors arising from stochastic biased gradients and the smosthh condition, with the constraint that the potential function is approximate non-decreasing.
{ (blNN) - b(to) 1 N-1
max
(((NN)
(LL)))))))))(((((()))))))))))) (10))))))))))))))))))))))))))))) (x((((
a(lN)
(((N)
[|x((++)) [|(r(())))(((((()++))))))))))))1 s.t. a(t]+1) - a(t;)= - [b((+1) - b(tt)) p(x(t;)) 2
+
L1 - BB((((++1)
- x(6))
2
x(()+1) x(tz) = (((t+1) b(tt))a(x(())) v(x(t)))
a(t)+1)
B.2 DETAILED DESCRIPTION FOR DR-SUBMODULAR MAXIMIZATION WITH STOCHASTIC BIASED GRADIENTS
We investigate the DR- oubmuuuaa maximization with stochastic biased gradients subject to three constraint classes: general constraints, down-closed convex constraints, and convex constraints with the largest element. By leveraging inequalities in Section 2 our approximation algorithms are con- structed through solving the variational problem Eq.413. Our algorithm achieves approximation ratio (1 - for monotone DR-submodular maximization subject to general convex constraints, matching the hardness result for monotone DR- submodular maximization under the above three constraints. Consequently, in work, focus exclusively on general convex constraints when addressing monotone DR-submodular functions.
and the sequence optimization problem
Convex Constraints. As a warm-up, we first consider general convex constraints. When F is monotone DR-submodular function, in light of Eq.(15) we can obtain the explicit formula for the upper bound of the optimal solution (q.
F(x*) S F(x* V x()) & F(X(()) + ((1) x())
S F(x(()) + (VF(x(0),,')
F(x(()) + (g(x(1) - n(x(()) - b(x(1),x))
S F((((() (g(x(()), Vmmx (1)) + [I(((()) b(x(O)ll2
where the first and the third inequality comes from the monotonicity. The last inequality comes from Cauchy-Schwarz inequality and Vmax arg maxvec(g(x(()), v), ||x*|l2 I VD maxx,yee ||x - y- When F is non-monotone DR submoddodla function, in light of Eq 18 the upper bound of the optimal solution (9) can be rewrite as follows:
(1 - ((x))
< F(x" V x(t)) < (F(x(t)) + (VF(((t)), x" - -x(t)
$ 2F(((()) (g(x())) b(x ( x x(())
2(F(((t)) + (n)(g((()),
+ [n(((t) + b(x(t))ll vD
VEc
Simultancously taking expectations E/|-] on both sides of the equation, we can obtain the explicit formula in (0p follows:
x(1) a(t)
a(t) b(t) p(x(t))
(x(())
if monotone
x(t)= ((0g(x(()) o(x(t))
a(t)
a(t)
v(x(t)) = Vmax(()
p(x(()) = =x(((t)) =1
Vinax (1) arg (xxx)e)
(á(t) b(t) p(x(t)) =
x(1) 2a(1)
a(t)
(x(())
x(1) ((0))(((t) v(x(1))
if non-monotone
alt)
e(((t)) Vina (t) - x(t)
p(x(t)) = 2x(x(t) =I- -I-((0)
Vmax (1) arg max (gr (g((())))v))
(21)
19

---

Published as a conference paper at ICLR 2026
For monotone cases, choose x(0) = 0. which means that x(T) be represented by the convex combination of solutions the convex feasible domain for T 1. There a natural choice a(t) =
e'. Similarly, for non non-monotone cases, if x(0) C and Vmax (t) E C, x(T) E C. because x(T) is
also the convex combination of solutions in the convex feasible domain.
if monotone
x xTT) - x() = So Vimax (t)d
r+e
a(s)
lim a(t) 2a(8)
if non-monotone
lim x(t + e) x(t) lim
((x(s)
myxx (t) x(t)]e
2a(s)
Additionally, because Vmax (t) - 1, for non-monotone cases, we have the following upper bound for x(t) to obtain the explicit formula for 0(t):
x(t) - 2a(t)
a(t) (1 x()) = xt) S 1 (x((0))) So
ds Zn(e)
ale)
= (1 x
a(O)
a(t)
Combining Eq. 21 with p(x(t)) 1 for monotone cases and p(x(t)) ||1-x(0)]l ~z v a((0/a(())
have:
a(t) = b(t)= + b(T) - b(0)
a(T) a(0)
if monotone
a(T)
a(T)
e
a(0)
2b(1) + b(T) b(0)
[V
a(O) ((T)
a(0)
- mz) d(0y )
x(0)ll 00
a(l)
a(T)
if non-monotone
1 x(0)
The explicit formula is as follows, when 7' = 1:
(a(t) c², b(t) e' (a()) = (t + b(t))(t)
monotone x0)) t, non-monotone
Algorithm Frank-Wolfe Variant for Convex Constraints
Input: F: objective function, C: feasible domain
Output: the solution x(1 Initialize x(0) 0, to
2: for j= 0 to N - 1 do
3: Estimate the gradient g(x(t,))
4: v(tz) arg max (g (x(xt))),
5: x((++1) x(tz) + (1- x vt,,)
if monotone
G+I+Ny )x(tt)
iNN
G+1+NY v(ty) if non-monotone
J+N
6: end for
The aforementioned procedure focuses on continuous-time settings. which cannot be directly im- plemented on computers. Next, we introduce the analysis procedure based on the potential function. Instead of directly solving Eq.(13) we exploit the explicit formula for parameter functions in the Lyapunov function to the potential function. Therefore, the constraint in Eq. is as follows:
a(tz+1) - a(t,) - [b(tz+1) b(t,)l((x(tt))
[e511 - e/s 165111 -e')
if monotone
-11++1 +12 (t, + - 1)(t,+1 - ty] ] (1y+1
1,,2 11:4111,22
if non-monotone
This implies that parameter functions within Lyapunov function also satisfies the constraint in [3). Consequently, we can directly consider the discrete time for parameter functions in the Lyapunov function while retaining the same approximation ratio:
If monotone: b(tx) b(to) = -1, If non-monotone: b(tN) b(ta) a(tx)
1 =1 - -
a(tx) 4
20

---

Published as a conference paper at ICLR 2026
Therefore, can analyze the second objective function in Eq. ( obtain the complexity of our algorithms, which maintains the above approximation ratio. Specially, when we consider a constant time step, i.c., the time sequence is given by tj = &. we have:
L Bla((++)) [x((++)) - x(())
-(())))))
(lxx))
2( et d+)\/DE(A(((()))..)) brehi -16511--4)9
if monotone
26' 11 ( D if non-monotone
2(1++1 4)(4 +IVDEIAA((())))))))
2(1)-1+1)
2e (1 (1-e- (-=+))DD((((((() (5) + Le (1 (1-e- - if monotone
2 2 ([A(((t)))
L (N D
if non-monotone
N-1 ((x((((())))))))))))))) Nー 2 N² / DEEAA(((t)) L
if monotone
N
if non-monotone
2N
If the stochastic biased gradient is strengthened to the exact gradient, the first item will be reduced to O. Specifically, when N 42 this recovers the approximation algorithm for DR-submodular maximization with the exact gradient subject to convex constraint. Therefore, for DR-submodular maximization with the stochastic biased gradient, obtain approximation algorithms with the fol- lowing theoretical guarantees. The iteration complexity can determined by the total variance of the stochastic bias gradient and the T1-sootth condition.
- - -ee)
monotone
Approximation Ratio:
{ O(E)
If non-monotone
x(tt) + (1 (1- )v(tt)
if monotone if non-monotone
Algorith::x(441
iN (x(())
G+I+Ny v(4)
i+N
Gfi+Ny
+ (xx 4)4 +
if monotone
Iteration Complexity:
N
<()))
2 N (DE(A(((()).)))) L.D
if non-monotone
Down-Closed and Convex Constraints, On the basis of the convex set, consider the constraint set is also down-closed. If 1v in (7) comes from stationary point y, i.e., i E V with the probability yr. then we have the following upper bound of the optimal solution:
F(x")= x F(x(1)) + www.::/woa...oooooooooooooonn//a
vD [n((()) + b(x()))ll
(1 - (1-v (() Alv) u(t)(1 (t))
(t) 0v (1)) (xe (u(t)lv V vo(t)lv))VIv)
(1))11 - Ov(())
F(x(t)) + max -iC www.://witt....oooooooooonaaaadd - VD |[n(((t) + b(x(t))lla
u(t)(1 (1)
1--1v( v(t) (0u(t) 0v F(1y) (u())((()
+Lu()oot) + u(t)(1 - (0 (v))
Since the upper bound of the optimal solution incorporates information about the stationary point, we consider the following Lyapunov function and the upper bound of the optimal solution that combines the stationary point.
F(x(()) ((0))((((() (()))()))))
+ +XXX))))(((XXX))))=X))))))),),1)
21

---

Published as a conference paper at ICLR 2026
When the Lyapunov function is non-decreasing, we have:
a ( + -c() c(0) a(T) c(T) a(T) c(T) c(0) + a(0)F(x(0))
((7))[F(x(T)) + (c(7) - F(y)
z [(TT) - [(0]
a - (())
It can be regarded as the algorithm returning the solution x x() with the probability a(T)++(7)-<(0
a(T)
and the stationary point with the probability <(T))c(()) +(T))+(T)-<00) Considering the derivative of the Lya-
рunov function when taking expectations [.,[]] on both sides:
E(x(t)) 2(a(t) b(t) p(x(t)))F(((() + (o(t) - b(t) ((((t)))(())
+ +x(0)g(((0)) ((0_ X0
a(t) [ln(((()) + b(x(1))l2 [x(())l2
-(())(((1)) [|](((()) + b(x(i)) [o((())l2
Similarly, by combining coefficients of identical terms in the derivative of the Lyapunov function, have the following sufficient condition. Given that the total variance of stochastic biased gradients is non-negligible, this condition guarantees the Lyapunov function is approximately non-decreasing.
a(t) b(E) p(x(t)) = 0
ε(1) b(L) :x(((() O
x(() = ((0g(x(0) v(x(t))
alt)
1
p(x(t)) = g(x(t)) = u(t) - 0y (t)) w(x(()) 1 v(t) (tu (t))))
(22)
a(t))(t)
u(t)(1 (t))
x(() a(l)
((x(t)
a(t)
(x((1) arg xx
Where p(x((),, q (((()), w (x(()) comes from the expectations [.] on both sides of the upper bound for the optimal solution. Formally, we choose x(0) 0, a(l) et, and T 1, x(1) is the convex combination of feasible solutions.
x (T) - x(0) = I' ((x(T))dl((((()
Additionally, according to the upper bound of the optimal solution, we can obtain the explicit for- mula 0y (t) and Bu (t):
z;(1) < 1 - -h f(r)dd iEU U
x(t) < (1 x(t) C (u(t)lu V vu(t)lv))
xx(1) S e - v(r)dr iEV
Therefore, with the constraints for the approximation algorithm design given in Eq. 22 the corre- sponding objective function for the algorithm design is as follows:
c(1) - c()) So e v(r)dr
So ((())- dt
b(7) b(0)
So e' u(r)dt u(t)dt
maXEq (T))+ +(T) c(0) maxeq
1
+ lo el- S v(r)dr drr
Sc u(r)-v(()dd di
(((t)
To obtain the explicit solution for the above objective function, we first consider the derivative for utt) in numerator and denominator.
S0 v(r)dr u(t). e6 v(T)dr >
e'-S u(r)dr
c u(F)dr
Ou
Iu
u(t) 1Vt E [0, 1] such that our target is as large as possible.
22

---

Published as a conference paper at ICLR 2026
Table 3: Parameter functions in the Lyapunov function
a(t) dt)
b(t) c--(t223)) e" (t+1-s) e²
p(x(()) ((x(L)) w(x(tt)
0, 8 t (s. 1 e'
E
e¹
-t
2-6
1-
When v(t) is chosen to be large, the contribution for the numerator is greater than that for the denominator. This implies that selecting large possible u(t) results in a larger value of the objective
function. Leveraging this observation, we can simplify r (x* A (Iv ve(()l))) Iv) F(x" v
1v), which implies the objective function can be rewrote as follows:
So c--So u(r)dr dt So et v(r)d7 vlt - o(F)drdt
max
dt
24 1-10 str)ar
+
1o ucr)dr
Therefore, we aim to minimize e u(r)dr while maximizing So' e- u(r)dr, This in turn implies that there is s E [0, 1] for which the explicit formula for v(t) can be derived.
v(t) Ovt [0, s); vt() 1 [s.1]
Accordingly, parameter functions in Lyapunov function are determined as shown in Tab and and the variational problem can formulated as a numerical optimization problem. Solving the following numerical optimization problem, have:
22 - 5)
b(T) b(0) a a(T) c(T) 0.385
max 0. e - 3+ s)E* + 0.372,
Next, we introduce the analysis procedure based the potential function. Correspondingly, consider the following potential function and the upper bound of the optimal solution in discrete time:
= of
- F(tx))((x)
F(x*) =x
x(x(t)))
+ ((xx(t))),,(IIx((((((( + b(x(t)))ll (1(((())))
the potential function is non-decreasing, we have:
[(tx))[[((x(x)) a(tN) + c(t)) - c(to) a(tN) + cctw) e(to) a(tN) + c(tN) c(to) a(tN) c(tn) c(to)
(c(tn)-c((e)) c(to) [(tt) b(to)((()))( ((to))(x(to)))
To ensure that the non-decreasing potential function, consider the difference between adjacent iterations algorithm x(tz) when taking expectations E.1-] on both sides:
P(x((g-1)) P(x(()) 2 (s(x(t)),
- ((55))))))))))(((((())))))))
Lia(lit1) - -(()))
2
+ [a(t)++) a(ty)) (b(t)+1) )
+ [[c(t(+t) - - - ((s)))((((()))(() )
a(()+1)(((x(())) +n(((()))xx(())) -x(1,)
- ((t,)))))) |b(x((t)) + =n(x(t)))ll [x(((t
There are two types of errors: (1) error from stochastic biased gradients, (2) error from L1 smooth condition. Combining coefficients of identical terms in the difference of the potential function, have the following sufficient condition to ensure that the potential function is approximate non- decreasing.
a(()-1)) a(l,) [b(1)+1) b(t)) p(x(l)) 2 0
c(()+1) - c(t,) -lb(t)+1) (xt,)) 20
x(tx+1) -x(t,) (BCe--)--Bey))a( (M (x((x)
a(tz-1)
23

---

Published as a conference paper at ICLR 2026
To substituting the explicit formula of the parameter functions of the Lyapunov function into the potential function, we first check these parameter functions also satisfy the constraints for approx- imately non-decreasing potential functions. Since we partition the parameter functions of the Lya- punoy function into two segments, the difference in the potential function between adjacent itera- tions is also split into two corresponding parts:
a(t/-1) - a(ty) [b(tz+1) b(t))lp(x(t))
(e - -ets - [e4s+ - - 0 if < 0.372N
=
c1 - c²t - et: -1,220 if > 0.372N
o(tj+1) ((tp) - [b(tz+1) - b(t))lw(x(t,))
/2|e cb] - M1++1 - -4y] [e -2
if j S 0.372N
1e - ty]
- - -1((1-
if > 0.372N
Therefore, we only need to analyze the remaining terms in the difference of the potential function to determine the complexity of the algorithm that consistent with the second objective function in Eq.
L Bla(tz+1) (x(()))))(x(((tt)) x(t))
216(t)+1) - (()5)))))))))))(0))44444444))))) 4) (1((( 2
0.372N-1
4 (e - -tt)²
<
Σ
2(e (
D
2
eb1l
1=
N-1
L e (tz+1 - -t,)2
Σ
2e (1 ((HH))-DDDDAAXX +
D
2
Etill
J=0.7NN
0.372N -1
Σ
2e N (1- -1- (DEAA(XX)))
_. 1+1 e1-e- +
1=0
N-1
e D
Lie'N
D
N
2 N2
0.372N
Σ 7=0
BIA(((6))
Σ j=0.372N
N-1
21+11
VDELA(((())))) + D( -1) N2
N
2N
When the stochastic biased gradient is strengthened to the exact gradient, our method recovers the approximation algorithm for DR-suboodular maximization under down-closed convex constraints with exact gradients with N D(e-)) Therefore, for DR-submodular maximization with the stochastic biased gradient, we obtain an approximation algorithm with the following theoretical guarantees. The iteration complexity can be determined by the total variance of the stochastic bias gradient and the Ly-mmotth condition.
2x
Approximation Ratio: 0.385 Occ)
x(t)) (1 - eiti )v(t))
If 0.372N
Algorithm: x(tx+1)=
x(4)) (Ni+Na)e गाोन
v((y)
If > 0.372N
arg wngmaaxPP.vee
(VF(x(t)).)) v) (VF(x(t))),
If S 0.372N
v(G))
arg
If 0.372N
0.372N
2 + VD
N-1
Iteration Complexity:
Σ
B B[A(((t)) (t),
Σ
(E(,A(((t))
N
e
1=0
j=0.372
Ia (e 1)
< O(e)
2N
24

---

Published as a conference paper at ICLR 2026
Algorithm 2 Aided Frank-Wolfe Variant for Down-closed Convex Constraints
Input: F: objective function, C: feasible domain, & E [0. 1]: parameter.
Output: x(1) with probability 1 p and y with probability
1: y Frank-Wolfe P))
2: V is a random subset of [d]. For all E [4]. i E with probability of independently.
Initialize x(0)
4: for j = 0 to N do
5:
i
then
6:
v(t,) arg v (VF())())) (VF(x(t))).
7:
x(tz+1) x(t,) + 2MTTT)) vv(1))
8:
else
9:
v(() arg maxveP.vsi (VF((()))
x(1x+1) = x(t)) + (Ni+ NT.N2 v(t,)
11: end if
12:
end for
C DETAILED DESCRIPTION IN SECTION 4
In this section, first introduce the total variance for the quantum gradient estimation algorithm. Next, we demonstrate the bias and the noise when the smoothing technique is adopted to estimate the gradient that is classical algorithm. Since this constitutes biased estimation of V Fx), also extend the prior variance reduction technique originally developed for unbiased gradient estimations and provide a corresponding analysis.
C.I QUANTUM ZERO-ORDER ALGORITHM
Jordan Algorithm is the gradient estimation algorithm on quantum computers whose query complex- ity is 1 for the function value oracle, instead of the query complexity is O(d) for classical computers. In (van Apeldoorn et al. (202)), authors proposed an improved Jordan algorithm that adopt the state tomograph technique reduce the bias for the Jordan algorithm estimate the gradient.
Lemma 7 (Suppressed-Bir Bias Gradient Estimation (van Apeldoorn al. 2023)). Let e, (0, J.
and g E Rdd such that lggll
S Let
[log2 and
If
8
[+b)
Σ
e (y)
$
Bd
24
od + 8
YEGS
given access 8[In 6d
copies of w), we can compute k E
[ 11d satisfying
21 2
Pr| k glooc 2 5 [[E[k]
gl S 8
The procedure has a gate complexity Odd & log log( log !)) and requires a corresponding circuit depth of O(log log(4 log L)).
The above lemma shows that the bias for the quantum gradient is Therefore, the total variance be obtained by the following procedure.
5 Pr|] glas <c.c Biikk 8llool < Pr[ glloo c..
However, when preparing the state lob), truncation errors arise the function value F due to the fi- nite number of qubits. Leveraging the above lemma, next, we prove the total variance when account- ing for the finite-bit precision of F. For convenience, we denote G(x +r) = F'x + +ry) F(xx,,
Go = 1 } + 2- (b+1) E [O.... - 1}} and G = &GG. In Algorithms, we denote 1 2" Σ²-=1 e (2xBG,(xtrr)) 09 v1)
|1b) 22u Ey= (B
/2nd
25

---

Published as a conference paper at ICLR 2026
Algorithm 3 Suppressed-Bing BBis Phase Estimation
Input: | = <22 1 Σw 22n ( and n E N
1: Sample uniformly random n-digit binary number E (0, and define 2 2
2: Apply multi-phase gate Σド= - ()) (jl (g))
3: Perform inverse Fourier transform over Zas and measure the statement, yielding outcome
4: return p
2n 5
Algorithm
Input: 2m copeis of [b) V25a Eyno el2n ((
1: while for each 8 E [d] do
2: for j E [2m 1] do
3: Suppressed-Be BBis Phase Estimation( Estimation((),()))...))) ()). where (1) the s-th register of the j-th
copy of (+b)
4: end for
5: for 1mm+1]am do
6: Compute dj the m-th smallest distance in the (multi)set f1e 9p 1ax : k E [2m + 1] {b}
7: Define wy = d,
8: end for
9:
P. = My with probability 31)
end while
11: return (F. Pa)
Proof of Theorem In the finite precision scenario, i.e., with finite number of qubits, we can only query the 3 approximation function value [Gs(y) - G(y) < B. Consequently, we only have (15) /Ba Eyeag (2xiBCg(x+tr) ly). Next, we establish the relationship between / and 6. First, for To Lipschitz continuous and L, smooth functions, we have ||VF(x)]I I Lo- This implies F(()
1/4 In light of the above theorem, we have:
3hg
v))
2 FFO0 36g
v) ly)
2t
BGg(x-ry) 3r
ly)
Σ
2riB( FF00
311
sily))
VB YEGR
B
YEGS
yEGg
2
2n BG, (x+ry)
2 3
FF(x)
(x)
Bd
Σ
BG (xG(x
2
Tho (
y)
1x)
B
Bd
YEGU
YEGU
max
2riB
Cslairy) 3r
- 2
FP(c) skg
.x)
<
B
max Gp (x ry) (VF(x),
yEG,
Lr yEGs
2T max
Gr +ry) ((x++r))) + ry) -(VF(xx)
3r yEGs
B L 2
<2x
3r Tr
If we choose
2idr 2
then have:
+ La dr
4m 4B
2m BTBBa
3rlo
3
23 Lid
Lo
24 In
6d
+3
Therefore, if we choose:
L288
35
8n 2² (8 In 6d
+ 1)2
26

---

Published as a conference paper at ICLR 2026
We can compute k [- 21 satisfying
VF
Pr
k
2
$ 6,
B[k]
S
3L.0
3T.
Next, we show the variance. If choose
then, we have:
6L.0
Vx(x)
(F(x)
5 Pr
VF(x)
E k
S Pr
cs k
k
2
xc
xc
3Lg
3Lg
3Lg
20
x
56
+ c(1 8) cc 0
6
3Lo
Therefore, we have
E ||kk VF() So
The above proof demonstrates that the algorithm designed using quantum gradient estimation ex- hibits the following total variance in each iteration. Using this variance, we can derive the complex- ity of quantum zero-order algorithm.
E[A(((t,), 15)1 = E (m (m++ M)
3 ( + +n((ts) ma(ct) ao
Proof of Theorem 3
By substituting the above total variance for the stochastic biased gradient into Section 3.2. we obtain the iteration complexity of the quantum zero-order algorithm follows, where we restrict both the first term and the second term to be 5.
Convex constraint.
2 VD E[Ax(())))))))+++
En Σ
DD N
monotone
eN
2 EE=
N-
-
(DE(A(((t)))))))
41 L
if non-monotone
2(e D(N Dd
+
LD
a= 0 2(e DDd-DWDee ), 0 0(4 if monotone
De
N (N+1)ovDa N
N
=0(e)
+ 2 N
D
σ 0
2 DVDa(Ia
D N = =0(
if non-monotone
Down-closed and convex constraints
0.372N
Σ
2e
TTl VD
EN
(T)(((())),t)))
N-1
Σ
21+1 VDE(A(((t)),t)]+ + L.D(e - 1)
N
eN22
2eN
1
/=0.37
2(c 0.372
1)(N
Dd Dd
+ 0.628
+ 1)oV Dd
(e -0-11
+
N
N
2N
3(N + Dd
LiD(e - 1) -e
O(e) =(e)
N
2N
$
= 0 DiD(-11e D(- ) N = 0 (()
Convex constraints with the largest element
N 2 VD
LiD 1)
2(N + 1)ov Dd
Dd
+ L,D(e - 1)
E[A(x(t))
O
N
2N
N
2N
0=
$
= 0 (e-1)Li
N = 0 ((
27

---

Published as a conference paper at ICLR 2026
C.2 CLASSICAL ZERO-ORDER ALGORITHM
The smoothing technique involving sampling over unit ball centered at given point is widely adopted in zero-order algorithms. While sampling over unit sphere centered the given point yields an unbiased gradient estimation for smoothing function F, is a biased estimation for A (x).. Next, we illustrate the bias and the noise can be bounded as follows:
Proof of Lemma 2 If Lo-continuous, we have
- F(y) Buva Pa ru) F(y ru)] S EL ||x y112] = Lo ||x yll2
implies that F(x) is Lo-continuous. In addition, combining the Loncoiiinuuus and the radius r, the difference between Fxx) and F(x) can be bounded as follows:
[F(x) - F(x) [u~ssF(x + ru) F(x)]l Eu~B(Lor [|u)]l2] s Lor
When F is Is-soooth, the following inequality implies F is also I -mooth::
(x()) - vF(y) = |Ba-s VV - VF + +r)]ll2 = Eu |x y112l S In ||x - yyll
The above gradient estimation corresponds single-point estimation scheme. Since Shamir (2177) demonstrated that two-point estimation yields a smaller variance, next, we prove the bias b(x) and the noise n(x) of the two-point estimation can be bounded as follows:
[bxx)]l2 Fx(x) v((x)
d
Eur Eu (F( F(x ((xxrr))ji - VF(x)
2r
d Eu-s (F + ru) F(x ( (r) 2ru
2r
d
Eu Eu-sll + ru) F(x ru))u (VF(
2r
d
Eans
[| (F(x + ru) - F(x (VF [1ا|
2r
Euwall
(V(F(x - ru 2tru)) - ( 2ru) [|ا||]]]]
2r
S dBmus!
[|V(F(x- ru 2(ru)) - [F(x)]l dl)
- dl, FunssEns [|ul|]] / 12t 1ldt 1
dL1r
2
The second equality comes from Eu-s (VF u)u] third inequality comes from Lsmmoothh
Euss iun [uF()FF(x)) fIVF(x). The
E [nxx) = =
[F(x) - E[VF(x)
[[]]
(VF(x) B(V FF(x) -
|| xx) |?] - 1 [
|?] - 16
=
The last inequality comes from (Li et al.
2022
Using the bias and noise results from Lemma we can obtain the total variance for the gradient estimation when employing the smoothing technique.
B[A(x(()) = [((((((()) vF(((t))))))).)) = = [[((((()) + b(x(4))l1
S (x) (bb((((t))l,, 2 + +116V2
dLrr
28

---

Published as a conference paper at ICLR 2026
Algorithm 5 The Estimation of Gradient with Variance Reduction
Input: Step-size Pt; (++a)ar3 Current gradient di,_ and solution x(4,)
4
I: g(x(tz)) )) is the gradient of x(t;) returned by the stochastic biased gradient oracle
2: dr = (1 - Ptg ),, 1 + Ptg B((())
3: return de;
When we directly employ the above gradient estimation to design algorithm, the total variance cannot be controlled by the algorithm behavior. To reduce the variance, we introduce the momentum term that was mentioned in (Mokhtari et al. (020). Specifically, we initialize the momentum term di O. In each iteration, the discrete time algorithm adopt the gradient with momentum as follows:
de = =11 - (11-,,)ddr Pr,))d + Pt, pt,g((((t))
where the discrete time 1, = t g(x((,)) is the gradient estimation obtained via the smooth- ing technique at x(4)), and Pt. = ()+5)273- Through the above procedure, the variance between
the Fx((()) and di decreases the number of iterations increases. While Chen al. (2018); Mokhtari et al. (2020) proved the upper bound for the total variance, their proof relies on the assump- tion that g (t²)) constitutes an unbiased estimation of FF(((t))). By combining the Lemma 2 which illustrates the bounded bias and the noise for the g(x(t))), next, we prove the variance reduc- tion statement for the biased gradient estimation.
Proof of Theurem 4
= == + (1- P(, PP (1 (1--,,))/P((())--XX0000
E VF(((t,) - dr,
=
-
d 1||++=+(0 Pc,) -I
+ 9,010 d
+ - (bx(
$ 1,
VF(x(() -
(b(x
VF(x(t)-1)) -VF()))))))
- d d 112 (1 - p1 (VF(((()) - (F(X(()-1)11
-
D,D
+(1 (1- (V dey-1112- (1(t))N22
+ +11 (1- (t- )c, (t,s) |[ d 11 [b(((L))
B2(())
L LIVD + 2(1 - pr,)
||b(x(t)))I2z
N
The inequality comes from the Young's inequality. i.e., 2(a, b) S B aal2 + ||b||/ /B. In
addition, we have || [x))))())) VF(x((--1))l I L1 [x((,)) - x((--))l22 S
L
when
N
[x((t) - x(li-1)112 - D Setting Bi((,) (2,) d. we have
D
(1 11-th -Ps5)((1 - (1) + p()1--;;)((
(4;) 5 P
-
(1 - (t,))(1++ + ,,
D N (1 ),0,,
12D
S(1 + (j + 5)2/3)
[+af S GLID
4
No
(1 Mr,)pt, |bb(((t)))
2(1 Pp: N
LiVD
[b(x(t)))]lz 81, +1, ((
b,Ct,)
(B+8)473
The above inequalities are because of j < N and < s N. Setting:
Q(t,) = max ( |VVF(x(to)) de, 112 (s 1)2/33
D + 16 max A?(x(11);:4 4x) + ST, / max [b(((4))ll2 + 16(1 + x/2/3 max [b((((+)))1 kebi
kE()
kEGi
29

---

Published as a conference paper at ICLR 2026
Clearly, Q(t, is non-decreasing, i.e. Q(t - Q(tz). If l|b(((t)) 0, it is degenerated to Chen et al. (0018: Mokhtari et al. (2020). Next, we adopt the induction to prove the variance
Q(t,)
B|| (Fx(tt) di 1121
(23)
(j + + 1)2/3
Considering lo. we have
(s + 11-1) ((( - d < ((o))
The above inequality implies Eq.
23 holds. Assume the Eq.
23 for the variance holds when 8R-1
Bll[F((((ts) - de 12 S
2
V
(x 1)) d
11 +
Q(4x-1)
(k + s)2/3
(A: + s)4/3
2
((xx-1)
+ Q(tx-1)
(1
(k + s)2/3
(k+ 5)2/3
(++5)472
2
Q((x-1)
+ Q(4x-1)
$ (1
(k + 8)2/3
(k + s)2/3
(k + s)4/3
((k: + s//33 1)Q(tt))
Q(4+)
((tx)
(k + s)4/3
(k: + s)2/3
+1 (k+ 1
Therefore, the proof for Eq. 23 is complete.
Using Theorem 4
obtain the variance between the gradient in algorithm and the orig- inal gradient V FF(((t))) For the convenience of algorithmic analysis, we further rewrite the aforementioned inequality as follows, where ((4)) max([)VF(x((o))) - llo 92/3 v5DL. +
maxkels A(ta) /8LIV (8LiVDmaxieLi) [bxx(
B[A(x(())44] = (i (im+ + M) VF(((
|
- N1 2
+ +m(4)) + mm((s) x (Q(t)) (j+ 9)1/3
max [VF(xtto) - de 112 91/3
(j + 9)2333
v LD + maxkels A(x((x),(4)) + v 1L DD maxeeii (j 1 9)1/3
+ 40j + maxkels [bb(((+))]la
< max VF(((to)) - d4, 91/3
+ 9)2333
V5DL + maxkels A(x(tx), (x) + / /8L VD DD maxkebi [lb(x(ta)]ll
4 max b(x(tx))]l } REDL
1++91/3
[VF(((()) - de 112 91/3
V5DL1 4aakebb t(x(tx),tt) (j + 1/133
88 maxke[s [b(x(tx))]l
S max
(j ()+9)1/3
4 max
[|b(x(4))]12
kEbi
q(t))
+ max [b(x(()))]l2 kEjj
( + 9/1/3
When we adopt the smoothing technique in Section 4.2 we have:
(tt,) max ( d2, 92/3 V5DL, + 2dL, + 16Lo / /2nd + v /AL = Q
The above inequality shows that q(t,)) is independent of the discrete time. For notational conve- nience, rewrite q(t,) Q, which implies the total variance is given by:
Q
B[A(((():4)) = E (m M)
+ (l)()) + the (()) <
(j ++11/3 + 2dLr
By substituting the above total variance into the algorithmic analysis, we can derive the iteration complexity of the classical zero-order algorithm follows:
30

---

Published as a conference paper at ICLR 2026
Proof of Theorem 5 Since the term 2dL,r in the total variance is independent in the iteration step, it can only be reduced by controlling the radius r the algorithm design. Therefore, we restrict the first term and the third term in the following inequalities 5. respectively, which can be reduced by the iteration step.
Convex constraints.
2e
D VD ([[A(((t)):t)))
if monotone
2
N
(D((A(((()),55)))
2 N
4. L1D
if non-monotone
VD /Q(t))
2j= 2e
N
(1+9)1/3
+
D
N
monotone
0=
2
No
1+
VD (Qit)
(5+9)/3
+ 22N
if non-mmontonee
ΣØ=
N-1 2e//D
2dL1r| +
D N
if monotone
N
1+911/3
Σe=
2
VDD
(149173 2dL1rl
Ia
L
if non-monotone
GEVDQN2/3
4ev Dd rr + 12
if monotone
1
N
= = N 0
BVDON2 + AVDdd,r + L N
if non-monotone
Down-closed and convex constraints.
0.372N-1 -1,
VD
N-1
2 2i+1
Le
Σ
B[A(((4).
Σ
VDDIA(((())6))
N2
2N
1=0
f=0.372N
0.372N-1 1
2e DD
VQL)
N-1 Σ
2vD vQ(4) Le
Σ
N
(
N (j+ 9////3
2N
J=0372N
Gev Gev DQN2/3
L, D(e 1 = ( = N =
Aev DdL +
N
2N
Convex constraints with the largest elements.
2e VD t())
(e 1))
N-1
2evD vQ(t)
De - 1)
Σ
<
N
2N
N (j 9)1/3
2N
j=0
26ev DQQ2/33
+ 4e 4eVDdLLT +
L2D(e 1)
((e) = 0
N
2N
D NUMERICAL EXPERIMENTS
This section details the settings of test problems, the parameter configurations of experiments, and additional specifics regarding the numerical tests.
D.1 SETTINGS
Continuous Du-submodular functions possess wide range of applications in domains including machine learning, resource allocation, and among others. We employ the following examples to evaluate our algorithms.
Non-convex/coneave quadratic programming (NQP): This type of problem arises in many applications, such as demand forecasting (Ito & Fujimaki (2016)). The goal is to maxi- mize a quadratic DR-function under some constraints. The formal statement objective function is as follows:
F(x) =
x T Hx + x
2
31

---

Published as a conference paper at ICLR 2026
classical first-order
classical zero-order
quantum zero-order
Down-Closer
Convex Constraints
Convex Constraints
Convex Constraints
with Largest Element
9.0381
9.004
Quadratic Programming
9/0365
6,0000
0.0002
9.8115
90043
0.0073
9.0020
9 0.004
2.5093
5.0953
3.0004
9,6005
16
20
30
40
10
30
40
20
30
80227
0.0394
0.0030
90094
9,0355
5.0009
Finite Sum
9.0022
9.8118
0.0153
9 0.0050
0.0001
9.0116
0.0020
2.0083
6.0070
94000
5.0005
0.0023
10
20
30
40
10
20
30
0.0100
0.0215
0.0030
0.0057
0.0373
0.0003
Coverage
0.0267
0.0331
0.0038
0.0046
0.0099
0.0300
0.0075
0.0047
0.0098
0004
0.0004
0.0011
35
20
Figure 2: Comparison of classical first-order algorithm(blue), quantum zero-order algorithm(green), and classical zero-order algorithm(orange). The x-axis the number of iterations. The y-axis the function value.
In our numerical experiments, choose d = and consider a randomly generated matrix H Rdxd and vector h RR The constant is set to sufficiently large value to guarantee that F(x) is non-negative.
Finite sums of DR-submodular quadratic programming: Building the DR-submodular quadratic programming, we consider a finite-sum formulation that arises applications like multi-resolution data summarization (Bian al. 2017b). In our numerical experi- ments, the formal statement of the objective function is as follows:
m
F(x)
Σ Px(x) 1=1
Σ
x H hxx++hx+
where we choose m = 10 and 3. The matrix H,. the vector hy, and the constant c are generated in the same manner in the DR-submodular quadratic programming case.
Regular coverage maximization: A coverage function is well-known monotone sub- modular set function, and its multilinear extension is a monotone DR-submodular func- tion. In numerical experiment, we consider special case based on the regular erage function from (Chen et al., 2023a). For a ground set V = 21, n} and a sub- set collection {S) (S.,..., S..) where S; C V. the regular coverage function defined as f(X) = 1Uiex S.| [X]. whose multilinear extension is as follows:
k
F(x) k -1 (1 - 2z II (1 x.)) - (1 - +1)+1)
44
32
Since in our theoretical analysis, we consider three type constraints: general convex constraints, down-closed convex constraints, and convex constraints with the largest element, consider the
32

---

Published as a conference paper at ICLR 2026
following constraints in numerical experiments that can be easily to generate the aforementioned three type constraints:
C= {x [0, A]x bb}
A Rexd and E R", is easy generate an example such that C. is general convex. When A IRxd and E 1 down-closed convex. A -000 and E Rg C is convex set with largest element. All matrices and vectors here are randomly generated. Due the high com- putational cost of classical simulation of quantum algorithms, we only set d = 3 on DR-submodular quadratic programming and its finite-sum and & on regular coverage maximization. For the number of the total iteration, we set N 50, 100 respectively.
classical first-order
classical zero-order
quantum zero-order
Down-Closed Convex Constraints
Convex Constraints with a Largest Element
Convex Constraints
Quadratic Programming
641933
0.0399
0.036
02226
0.0003
Finite Sum
0.0776
0.0135
0 00146
0.0127
0.0077
0.0288
0.0074
0.0022
Coverage
0.0166
0.00226
0.0175
Figure 3: Comparison of classical first-order algorithm(blue). quantum zero-order algorithm(green), and classical zero-order algorithmmorange). The x-axis the number of iterations. The y-axis the difference between the function value and the baseline value. D.2 RESULTS
In this subsection, we present numerical experiments conducted with N = 50. Fig depicts the quality of the current solution, exhibiting experimental phenomena consistent with those Fig Fig illusttrate the difference between the current solution and the baseline value.
For DR-submodular quadratic programming, the quality of the solution returned by quantum zero- order algorithm approximately approaches that of the solution returned by classical first-order al- gorithm. Although the quality returned by quantum zero-order algorithm has a slight degeneration under down-closed convex constraints and convex constraints with the largest element, it still sig- nificantly outperforms the classical zero-order. For the convergence rate, the quantum zero-order algorithm illustrate the significant acceleration for classical zero-order algorithm, achieving the ap- proximate convergence rate for classical first-order algorithm.
For finite sums of DR-submodular quadratic programming, under both down-closed convex straints and convex constraints with the largest element, the quantum zero-order algorithm demon- strates significant improvements in both solution quality and convergence rate compared the clas-
33

---

Published as a conference paper at ICLR 2026
sical zero-order algorithm. Moreover, its performance approaches that of the classical first-order algorithm across all constraint types.
When considering regular coverage maximization, the quantum zero-order algorithm performs cellently under general convex constraints and down-closed convex constraints, outperforming the classical zero-order algorithm and achieving performance close that of the classical first-order algorithm. However, under convex constraints with the largest element, its performance degrades the same level the classical zero-order algorithm. This is primarily attributed the excessive specificity of regular coverage maximization when the problem dimension is extremely small, i.e., V (1, 3), S (1.3), S2 {2), S3 = [1.3}. Then, f((1)) 1, f((2)) 0, f({3)) = 1, 2(11,)) = 1, f((1,3)) = 0, f([2,3)) = =. f(11,,, 3)) = O. According to results DRssubmodular quadratic programming. we believe that when the dimension is large, quantum zero-order algorithm can outperform classical zero-order algorithm both in the quality of solution and the convergence rate.
Totally, the numerical experiments with N 50 exhibit similar phenomena those with N = 100, confirming the quantum acceleration of the quantum zero-order algorithm relative to the classical zero-order algorithm.
34


Reviews:
[{"review_id": "8QnjozI3NS", "reviewer": "Reviewer_bbTg", "summary": "The authors consider the problem of DR-submodular maximization.  They consider a few combinations of monotone/non-monotone functions over the hypercube and classes of convex constraints (general, down-closed, largest element).  The authors first propose an extension of a Lyapunov framework from exact to stochastic and biased gradients.  The authors consider a new constraint setting (largest element) for the non-monotone setting and obtain an improved approximation ratio (over using a general convex region based method).  The authors also show significant improvements in complexity for the value oracle setting using a quantum algorithm for gradient estimation.  Lastly, the authors run several experiments to demonstrate the improvements of the quantum based method.", "questions": "- Do the complexity bounds depend on the dimension?\n- I found Section 4 on quantum acceleration hard to follow.  I am not familiar with quantum methods.  I have some uncertainty about the specific set up and some uncertainty about whether the impressive complexity results using quantum algorithms are purely of theoretic interest or if in the (near) future there could be the potential for real-world use.\n    - From line 354, just to confirm, the set up is identical in terms of the environment (the (biased) value oracle)?  A learner that has access to a quantum computer can use quantum Jordan algorithms to achieve the speedup in terms of query complexity over a learner that only has access to classical computers, but the environment itself and how they interact with the environment is identical?\n    - Could the authors remark on example situations where there could be a practical benefit in terms of total run-time?  Eg Figure 1 is measured in terms of iterations.  How would that map to clock time?  I understand that in the experiments the authors were simulating a quantum algorithm on a classical computer, so there could be large overhead.     \n        - For readers unaware of how much overhead, just looking at Fig 1 results it might be tempting to consider using a simulated quantum algorithm even for a smaller number of iterations if the overhead is low enough.  What were the (rough) run-times?\n        - Would the authors be familiar enough with current quantum computers on the market if they would be big enough to be used for this type of problem? If not, is there an educated guess for how close quantum computing is to the scale even to be used for the small $d=3$ experiments here?\n        - For current/near future quantum systems, is there a rough sense for how long each iteration (for the quantum Jordan algorithm) might take in clock time?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors present a new approximation ratio for the case of non-monotone DR-submodular maximization over convex constraints with a largest element.\n- The authors show that there is a notable convergence speedup using quantum algorithms for gradient estimation (for the value oracle setting).\n- The authors extend the Lyapunov framework for DR-submodular maximization to handle stochastic and biased oracles.\n- The authors include experiments that show improved convergence for quantum algorithms in the value oracle setting.", "weaknesses": "- I had some uncertainty about the extent of technical challenges and novelty for some parts\n    - For the Lyapunov extension to handle stochastic biased gradients, it was unclear to me from the description in the main section what technical challenges were encountered compared to past works.   Could the authors summarize the challenges?\n        - in line 047 (Du, 2022) is cited as having a unifying Lyapunov framework unifying many previous methods.  That reference is not brought up in Section 3 for the framework, though the authors are upfront that they generalize a previous framework to handle stochastic (and biased) gradients.\n        - Du’s work applied the Lyapunov framework for DR-submodular, and though that work presumed exact oracles, for convex optimization at least has there been Lyapunov based approaches that handled stochastic and biased (or at least stochastic) gradients? If so, are there unique challenges in extending the Lyapunov framework for DR-submodular problems from exact to stochastic (and biased) gradients? \n    - For the quantum section, the authors adopt a quantum algorithm for gradient estimation for DR-submodular maximization similar to past works in convex optimization.  In light of past works (both from classic gradient estimation in DR-submodular works and wrt Augustino et al 2025 for quantum methods in convex optimization), were there some key steps that were particularly challenging?  \n\n\n### Minor\n- Table 1 I’d suggest listing DR-max approx. bounds (and complexities) for stochastic first order based methods for reference.  \n\n- Non-monotone max with largest element is new setting considered, so appx ratio is first, but not clear  how tight it may be (no lower bound)\n\n- Theorem statements referencing algorithms were imprecise, \n    - eg line 360 “returned by quantum algorithms satisfies” – do the bounds in Theorem 2 hold for any quantum algorithms, or the (single) specific algorithm adopted from van Apeldoorn et al 2023?  \n    - Theorem 3 line 377 “there are some quantum zero-order algorithms achieving” \n- Fig 1 the axes’ fonts are too small\n\n### Very Minor\n- “Lipschitz” not “Lipschiz”\n- line 407 “with [A]ssumption[s] 1 …”\n- line 366 “The query complexity of the value oracle” should that be the complexity of the algorithm?", "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": "t5aP3DN3Kh", "reviewer": "Reviewer_AyjJ", "summary": "This paper investigates the problem of continuous DR-submodular maximization under the practically relevant yet theoretically challenging setting of stochastic biased gradients. The authors extend the Lyapunov framework, traditionally developed for exact or unbiased stochastic gradients, to handle gradient estimators that contain both bias and noise, thereby characterizing their effects on convergence and approximation guarantees. They further introduce a new class of constraints, namely convex sets with a largest element, that naturally arise in resource allocation and similar applications. Under this setting, the paper proposes a $1/e$-approximation algorithm for non-monotone DR-submodular maximization, which surpasses the known $1/4$ hardness bound for general convex sets. Building upon this framework, the authors design both classical and quantum zero-order algorithms, showing that the quantum version achieves the same approximation ratio with only $O(\\varepsilon^{-1})$ iteration complexity, demonstrating a quantum acceleration compared with classical zero-order methods that require $O(\\varepsilon^{-3})$. Numerical experiments on quadratic and coverage-type DR-submodular functions validate the theoretical results, showing that quantum algorithms converge faster and achieve comparable solution quality to classical first-order methods. Overall, the paper provides a unified theoretical and algorithmic treatment of DR-submodular maximization in the presence of biased gradients and connects classical optimization with emerging quantum techniques.", "questions": "Please refer to the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper extends the Lyapunov-based analytical framework to accommodate stochastic biased gradients, a setting that more faithfully represents real-world learning and optimization scenarios where gradient estimates are noisy and biased. The work also successfully integrates quantum computation into continuous submodular optimization, showing that quantum zero-order algorithms can match the convergence rate of classical first-order methods, offering a clear demonstration of quantum speedup. The results are rigorously proven, the methodology is well grounded in prior literature, and the experimental findings, though small in scale, corroborate the theoretical analysis.", "weaknesses": "The paper currently lacks experimental results on runtime performance, which makes it difficult to assess the practical efficiency of the proposed algorithms.\n\nMoreover, it would be beneficial if the authors could provide additional real-world examples or application scenarios to better justify the practical relevance of the studied problem, since DR-submodular maximization has so far attracted more attention from the theoretical community rather than from most of the ICLR audience.\n\nMinor comment: In Figure 1, the legends in the third and sixth subplots appear partially covered by light-colored text, suggesting a plotting or rendering issue that should be corrected for clarity.", "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": "NcKE4SRqr7", "reviewer": "Reviewer_VyE8", "summary": "This paper studies continuous DR-submodular maximization under stochastic biased gradient oracles. It extends Du's Lyapunov framework to handle bias and variance in gradient estimators. Based on this, it provides approximation algorithms under three constraint classes: general convex, down-closed convex, and convex sets with a largest element. The paper develops zeroth-order algorithms, where the classical version achieves $O(\\epsilon^{-3})$ while the quantum version achieves $O(\\epsilon^{-1})$ iteration complexity, matching the performance of classical first-order methods.", "questions": "- How tight is the $1/e$ approximation for convex sets with a largest element? \n- Would it be possible to provide alternative constructions for $a(t)$ and $b(t)4 that possibly improve the current setup?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Extending Du's Lyapunov framework to stochastic biased gradients seems interesting. The framework explicitly characterize the effect of bias and noise, and the resulting analysis looks useful beyond this problem setting.\n- The constraint set given by a convex set with a largest element is well-motivated. Bridging the convex and down-closed settings leads to a provable $1/e$ guarantee.\n- The paper shows that quantum gradient estimation can close the gap to first-order methods in ratio and complexity.", "weaknesses": "- The experiments are limited to $d=3$ due to simulating quantum algorithms in classical computers. To improve empirical evidence, larger-scale tests would make the claim of quantum acceleration more convincing.", "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": "1wohvWDEQJ", "reviewer": "Reviewer_3kKo", "summary": "The paper studies a quite general optimization problem, namely maximizing a function F on [0,1]^n under some contraints defining a feasible set $\\cal C \\in [0,1]^n$. The function is DR-submodular. The feasible set is convex. Such a problem is typically solved using gradient ascend, and there is a huge literature on these techniques.\n\nThere are 3 contributions.\n\n1. Extending the Lyapunov framework, to allow gradients to be imprecise, with a bias and a noise.\n2. Proposition an 1/e approximation for non-monotone DR-submodular maximization over a convex set. The novelty is the assumption on a largest feasible point. This overcomes a 1/4 upper bound on the general optimization problem.\n3. Providing a quantum algorithm, based on the improved quantum Jordan algorithm from 2023, which has the same performance guarantees as its classical counterpart but improves in cubic iteration time.\n\nSome performance guarantees are proven, and experiments are conducted with standard benchmarks.\n\nMy background is too weak in this area to judge the results.", "questions": "- at some moment it would be good to say what DR stands for (diminishing return)\n- Page 3 line 127. I think you mean $\\textbf{x} \\vee \\textbf{y} = (\\max\\\\{x_i, y_i\\\\})_{i\\in [d]}$\n- Also here dimension is d and later it is n\n- Page 3, line 150. I could not understand the difference of a bias and a noise. Is the noise consistent, in the sense that n is a deterministic function? What is the domain of $\\xi$? What is known to the algorithm? Does it know the functions $b,n$ and the parameter $\\xi$ or only some of them? Does the algorithm knows the assumed bounds $m,\\eta_b, M, \\eta_n$?\n- Page 4 line 205. It wasn't clear to me before that the function x(t) is an algorithm.\n- Page 5 line 228. What does it mean to maximize two values? Or do you mean to maximize the maximum of the two values?\n- Page 6 line 277: which we have newly introduced -> Potential author name revealing\n- Page 8 line 418 Lipschiz -> Lipschitz \n- Page 10. Some acronyms should be uppercase, i.e. in curly brackets in the bibtex file. Such as DR, SGD.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The domain is important and has a huge literature. The paper has 3 contributions, all of which seem central and important. The paper has a theoretical and a practical side.", "weaknesses": "The paper seems to be hard to follow for an outsider.", "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)