Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

Yiyang Lu; Haresh Jadav; Mohammad Pedramfar; Ranveer Singh; Vaneet Aggarwal

cs.LGFeb 24, 2026

Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

Authors: Yiyang Lu, Haresh Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, IN, USA · IIT Indore, MP, India · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Abstract

We study online maximization of non-monotone Diminishing-Return(DR)-submodular functions over down-closed convex sets, a regime where existing projection-free online methods suffer from suboptimal regret and limited feedback guarantees. Our main contribution is a new structural result showing that this class is $1/e$ -linearizable under carefully designed exponential reparametrization, scaling parameter, and surrogate potential, enabling a reduction to online linear optimization. As a result, we obtain $O(T^{1/2})$ static regret with a single gradient query per round and unlock adaptive and dynamic regret guarantees, together with improved rates under semi-bandit, bandit, and zeroth-order feedback. Across all feedback models, our bounds strictly improve the state of the art.

Figures & tables

Oracle	Feedback	Reference	Approx.	Queries	Regret Guarantees
Oracle	Feedback	Reference	Approx.	Queries	Static	Adaptive	Dynamic ( $\times\sqrt{1+P_{T}}$ )
$\nabla F$	Full Info	( Thang and Srivastav, 2021 )	$1/e$	$T^{\beta},\beta\in[0,\frac{3}{4}]$	$O(T^{1-\beta/3})$	–	–
		( Zhang et al., 2023 )	$1/e$	$T^{\beta},\beta\in[0,\frac{3}{2}]$	$O(T^{1-\beta/3})$	–	–
		( Zhang et al., 2023 )	$1/e$	$1$	$O(T^{4/5})$	–	–
		( Pedramfar et al., 2024a )	$1/e$	$1$	$O(T^{2/3})$	–	–
		This Paper	$\mathbf{1/e}$	1	$\mathbf{O(T^{1/2})}$ (Prop. 1 )	$\mathbf{O(T^{1/2})}$ (Prop. 2 )	$\mathbf{\tilde{O}(T^{1/2})}$ (Prop. 3 )

Table 1: Comparison of Regret Bounds for Online Non-Monotone DR-Submodular Maximization over Down-Closed Sets. Oracle denotes the feedback type (

\nabla F

: Gradient,

F

: Value). Our framework is the first to provide Adaptive and Dynamic regret guarantees while achieving

{\mathcal{O}}(T^{1/2})

static regret in the

O(1)

query regime. Thang and Srivastav (2021) achieves

{\mathcal{O}}(T^{3/4})

regret with

T^{3/4}

queries per round when

\beta=\frac{3}{4}

. Zhang et al. (2023) achieves

{\mathcal{O}}(T^{1/2})

regret with

T^{3/2}

queries per round when

\beta=\frac{3}{2}

, but only achieves

{\mathcal{O}}(T^{4/5})

regret with

{\mathcal{O}}(1)

queries.

Submodular Optimization

Submodular optimization studies efficient selection and allocation when each added item tends to provide diminishing returns.

See all 52 papers

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization
Sep 30, 2026Vaneet Aggarwal, Yiyang LuSubmodular Optimization Regret Minimization
Purdue University
Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Jan 30, 2025Yiyang Lu, Mohammad Pedramfar, Vaneet AggarwalSubmodular Optimization Online 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 Optimization Follow-the-Regularized-Leader
Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Sep 30, 2026J/K move · Enter open · S save

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

Vaneet Aggarwal, Yiyang Lu

Purdue University

Submodular Optimization Regret Minimization

Open paper AskPDF arXiv

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets

K\subseteq[0,1]^d

. A supplied feasible diagonal point

ζ{\bf 1}\in K

gives an upper-linearizable comparison with coefficient

\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]

. This gives

4/9

ζ=0

and

O(\sqrt T)

expected online approximate regret with one gradient query and one projection per round, including stochastic gradients. The same coefficient admits

O(T^{3/4})

regret with one noisy value query, or

O(\sqrt T)

with two exact value queries. All objective queries lie in the cube. Our analytical offline upper bound at

ζ=0

improves the bound

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

established in 2011, even with exact values and full gradients. Two constructions extend it to positive diagonal levels; one has a finite representation below

1/8

and a piecewise rational formula above it. Online-to-batch conversion gives offline approximation and sample complexity, while a constant-objective reduction transfers the upper bound to online optimization. Both general-class coefficients equal

1/2

for

ζ\ge1/2

, and their deficits below this level have quadratic order. Analytic polynomial comparisons give coefficient

1/2

for quadratics and

\max\{8/17,2\sqrt{3-4r}/(1+\sqrt{3-4r})^2\}

for cubics, where

r=\min\{ζ,1/2\}

, with online and offline query implementations. Finally, for discrete submodular maximization, multilinear extension and established rounding give

\underlineα(ζ)-\varepsilon

under one matroid constraint and

4/9-\varepsilon

under a fixed number of knapsack constraints.

Abstract

Submodular Optimization

Explore similar work

Geometry-Dependent Online and Offline Approximation for Non-Monotone DR-Submodular Maximization

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