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

Jan 30, 2025math.OC

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

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.

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

Ask PDF

Aug 31, 2026math.OC

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

We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of

\widetilde O(\sqrt{T})

. Over

T

rounds, each agent uses

T

neighbor-mixing steps and

\widetilde O(T)

separation-oracle calls. We give wrapper instantiations covering four up-concave or DR-submodular maximization problems.

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

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

Submodular Functions Decentralized Optimization Decentralized Autonomous Organization Optimistic Follow-The-Regularized-Leader Separation

Ask PDF

May 8, 2026cs.LG

Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight

63\%

approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity. Prior work handles negativity through additive bounds for the special class of decomposable functions and non-monotonicity through partial-monotonicity parameters, but these address each difficulty in isolation and neither extends the classical structural theory. We extend \emph{curvature} -- a parameter measuring how far a function deviates from linearity -- to all submodular functions, handling both non-monotonicity and negativity through a single classical concept. A greedy algorithm with pruning achieves a curvature-controlled multiplicative ratio for \emph{any} submodular function, including those taking negative values -- the first such guarantee beyond monotonicity and non-negativity. In the non-monotone regime

1 \le c_g < 2.2

, the bound strictly beats the best known uniform ratio of

0.401

(for non-negative

f

), and it recovers the classical

(1-e^{-c_g})/c_g

guarantee for monotone functions. A multilinear-extension variant extends the framework to general combinatorial constraints via multilinear relaxation. Experiments on cost-penalized experimental design, coverage, feature selection, and a curvature sweep on Multi-News passage selection support the theory.

Yixin Chen, Alan Kuhnle

Department of Computer Science & Engineering, Texas A&M University

Submodular Functions Local Curvature Greedy Algorithm Monotonicity Bayesian Experimental Design

Ask PDF