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

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 $\zeta {\bf 1} \in K\subseteq[0,1]^d$, the coefficient improves to $\underline\alpha(\zeta)=\tfrac12-(1-2\zeta)_+^2/[2(3-2\zeta)^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 $\beta_*=0.470438681380894\ldots$ at $\zeta=0$, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every $\zeta$. The lower and upper bounds match at $1/2$ for $\zeta\ge1/2$, and show that the optimal deficit from $1/2$ is $\Theta((1/2-\zeta)^2)$ as $\zeta\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 $\zeta=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.