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.

Machine Learning (cs.LG)

arXiv:2610.00545 [cs.LG]

(or arXiv:2610.00545v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.00545 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.