Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

Vaneet Aggarwal

cs.LGSep 30, 2026

Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

Authors: Vaneet Aggarwal

Organizations: Purdue University

Abstract

We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient $4/9$ , improving the online $0.401$ benchmark, with one gradient query and one projection per round and $O(\sqrt T)$ expected approximate regret. If $ζ{\bf 1} \in K\subseteq[0,1]^d$ , the coefficient improves to $\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]$ . The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound $β_*=0.470438681380894\ldots$ at $ζ=0$ , even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every $ζ$ . The lower and upper bounds match at $1/2$ for $ζ\ge1/2$ , and show that the optimal deficit from $1/2$ is $Θ((1/2-ζ)^2)$ as $ζ\uparrow1/2$ . For coefficient-revealed polynomials we obtain $1/2$ for quadratics and a geometry-dependent cubic coefficient starting at $8/17$ , including $0.49$ at $ζ=1/5$ . A constant objective sequence yields an offline $(4/9-\varepsilon)$ approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including $O(T^{3/4})$ regret with one noisy value per round.

Figures & tables

Result	Coefficient	Feedback, constraint access, and guarantee
Buchbinder and Feldman (2024)	$0.401$	Offline; smooth objective and meta-solvable constraints
Lu et al. (2026)	$1/e$	Online; one gradient and $O(\sqrt{T})$ regret
Aggarwal and Lu (2026)	$0.401$	Online; one noisy value and $O(T^{4/5})$ regret
Corollary 5.5	$4/9-\varepsilon$	Offline; exact first-order and projection access; $d+O(dD^{2}B^{2}/(\varepsilon^{2}v^{2}))$ calls to each, with $v\geq\OPT/(2d)$ computed
Corollary 5.2	$\underline{\alpha}(\zeta)$	Online; one gradient, one projection, and $O(\sqrt{T})$ regret
Corollary 5.4	$\underline{\alpha}(\zeta)$	Online; two exact values and $O(\sqrt{T})$ regret, or one noisy value and $O(T^{3/4})$ regret

Table 1: Approximation coefficients and feedback models. Upper-bound rows limit achievable coefficients; the other rows are constructive. Online orders suppress dimension and regularity factors. Our algorithms use the projection and objective oracles specified in Section 2 ; the offline comparison of Buchbinder and Feldman (2024) uses a different constraint oracle.

Symbol	Meaning
$K,d,D,\Pi_{K}$	Feasible set, dimension, diameter, and Euclidean projection.
$\zeta,\zeta(K)$	Supplied diagonal level and largest $t$ with $t\mathbf{1}\in K$ .
$f_{t},x_{t},p_{t},o$	Round- $t$ objective, internal state, rewarded action, and comparator.
$M,B,B_{1},\sigma$	Bounds on objective values, gradient norm, root conditional second moment of gradient responses, and root conditional variance of value noise.
$\Reg_{\alpha},\Reg^{\rm ad}_{\alpha}$	Expected static approximate regret for oblivious and nonanticipating adaptive adversaries.
$c_{\zeta},h_{\zeta},g_{\zeta}$	Rational parameter, action map, and comparator-independent field.

Table 2: Notation used across sections. Auxiliary coordinates and parameters are defined where they occur. The subscripts on

C_{n}

refer only to base size, unlike the component count in

U_{2}

$\zeta_{j}$	$1/200$	$1/100$	$1/40$	$1/20$	$1/10$	$3/20$	$1/5$	$1/4$	$3/10$	$2/5$
$a_{j}$	0.471	0.472	0.474	0.4779	0.484	0.488	0.490	0.492	0.4955	0.499

Table 3: Additional cubic achievable coefficients. Each exact decimal

a_{j}

is attained by two shared scalar maps and is valid on the entire interval

\zeta\geq\zeta_{j}

. No interpolation between the rows is assumed.

Panel of Figure 1 — Figure 1: Achievable coefficients for general DR objectives, quadratics, and cubics under the same diagonal condition. The cubic curve combines the analytic comparison with the exact interval guarantees in Table 3 ; jumps correspond to a new admissible two-map law, not interpolation. The dashed upper curve bounds the general DR class , not the polynomial subclasses, whose implementations use coefficients or exact reconstruction. All four curves equal $1/2$ for $\zeta\geq 1/2$ . The upper steps use exact right-endpoint certificates, as described in Appendix D .

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Inequality	Knot vertices	Accepted intervals	Accepted triangles
( 86 )	41	40	0
( 87 )	1681	40	0
( 88 )	35301	315	1993
( 89 )	35301	315	1939

Appendix

Table 4: Exact full-domain verification of the cubic law. The intervals for the last two rows include degenerate sections. Maximum subdivision depths are 0, 5, and 2 for the directed, coverage, and product sections. The original three-argument boxes are reduced only by the proven section argument, not by a monotonicity assumption.

Law $j$	Directed intervals	Coverage triangles	Product triangles
1	24	219	228
2	24	225	255
3	22	210	213
4	26	216	261
5	27	234	222
6	26	243	231

Appendix

Table 5: Exact full-domain checks for the additional cubic laws. The two unary comparisons, every knot vertex, and the degenerate sections are checked as well. Counts refer to accepted nondegenerate sections after rational subdivision.

$n$	$10^{9}\eta$	$10^{9}\theta$	$10^{9}\lambda$	$10^{9}\mu$	$10^{9}\nu$	$(2n-1)10^{9}\delta$	$10^{7}\kappa_{n}$
4	500343128	209472587	222806519	67377766	20204317	81376300	4838886
5	463019062	231658815	253421053	51901070	16197717	107641600	4812874
6	443926408	241116467	268083844	46873281	13451100	120121744	4795186
8	422808327	250401165	283603439	43187069	10126985	131698664	4772807
10	411657989	254636013	291432770	42273228	8134341	136880291	4759261
16	395367406	260723814	302954313	40954467	5149981	143304902	4738800

Appendix

Table 6: Exact integer numerators for Proposition 4.5 . Each row satisfies ( 47 ); in fact

\nu+\delta=\lambda/(2n-1)

. The accepted interval counts in increasing

n

order are

7,8,8,8,8,8,9

Explore similar work

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Jan 30, 2025Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalDecentralized Optimization Convex Optimization
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
Aug 31, 2026Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular Functions Decentralized Optimization
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions
May 8, 2026Yixin Chen, Alan KuhnleSubmodular Functions Local Curvature
Department of Computer Science & Engineering, Texas A&M University

Jan 30, 2025, math.OCJ/K move · Enter open · S save

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Decentralized Optimization Convex Optimization Submodular Functions \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret

Open paper AskPDF arXiv

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of

O(T^{1-θ/2})

with communication complexity of

O(T^θ)

and number of linear optimization oracle calls of

O(T^{2θ})

for decentralized upper-linearizable function optimization, for any

0\le θ\le 1

. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

Abstract

Explore similar work

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions