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

arXiv: https://arxiv.org/abs/2610.00545 · HTML: https://mlsanity.com/paper/2610.00545/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 22 references that are in the map.
- First posted on arXiv 30 Sep 2026.

## Builds on (most cited first, 3 of 3)

- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets](https://mlsanity.com/paper/2602.20578/) (2026)
- [Online Non-Monotone DR-Submodular Maximization Matching the Offline 0.401 Factor](https://mlsanity.com/paper/2609.02145/) (2026)

## Abstract (arXiv)

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(√ T) expected approximate regret. If zeta bf 1 ∈ Ksubseteq[0,1]d, the coefficient improves to underlineα(zeta)=tfrac12-(1-2zeta)_+2/[2(3-2zeta)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.470438681380894ldots 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≥1/2, and show that the optimal deficit from 1/2 is Theta((1/2-zeta)2) as zetauparrow1/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(T3/4) regret with one noisy value per round.