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

Abstract

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 $\zeta {\bf 1}\in K$ gives an upper-linearizable comparison with coefficient $\underline\alpha(\zeta)=\tfrac12-(1-2\zeta)_+^2/[2(3-2\zeta)^2]$. This gives $4/9$ at $\zeta=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 $\zeta=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 $\zeta\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\{\zeta,1/2\}$, with online and offline query implementations. Finally, for discrete submodular maximization, multilinear extension and established rounding give $\underline\alpha(\zeta)-\varepsilon$ under one matroid constraint and $4/9-\varepsilon$ under a fixed number of knapsack constraints.