Better bounds improve online maximization of complex value functions
Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization
Machine Learning
Summary
This paper studies how to make better decisions repeatedly when facing changing rewards that have diminishing returns but are not always increasing. The authors improve the mathematical guarantees for how well an algorithm can perform compared to the best fixed choice after seeing all outcomes. They show new bounds depending on the shape of the decision space that tighten previous results and provide limits on what's possible, even with full information. These findings help in designing efficient algorithms that use limited feedback, like only the gradient or noisy values, while keeping regret low over time.
What this means in practice
- •For machine learning engineers: Use improved regret bounds to design online learning systems that handle complex objectives with diminishing returns more efficiently.
- •For online advertising teams: Inform strategies for sequential ad placements where rewards are non-monotone and feedback is limited, optimizing long-term performance.
A theory result. No direct application yet.
Authors
Vaneet Aggarwal
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 $ζ{\bf 1} \in K\subseteq[0,1]^d$, the coefficient improves to $\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^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.470438681380894\ldots$ at $ζ=0$, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every $ζ$. The lower and upper bounds match at $1/2$ for $ζ\ge1/2$, and show that the optimal deficit from $1/2$ is $Θ((1/2-ζ)^2)$ as $ζ\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 $ζ=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.