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

arXiv:2610.00545v1 Announce Type: new 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 {f 1} in Ksubseteq[0,1]^d, the coefficient improves to nderlinealpha(zeta)=frac12-(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 eta*=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 zetage1/2, and show that the optimal deficit from 1/2 is Theta((1/2-zeta)^2) as zetaparrow1/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-arepsilon) 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.

Source: arXiv cs.LG | 2026-10-02

Related