First-order online learning methods control distinct geometric regret classes
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
Machine LearningComputer Science and Game Theory
Summary
Online learning algorithms try to improve decisions over time by comparing themselves to fixed strategies. This work finds the exact types of changes or deviations these algorithms can handle without regret, using a geometric viewpoint. It shows that different algorithms like gradient descent and mirror descent work within different geometric frameworks, meaning they control different kinds of errors. The authors also explore how this affects game scenarios and introduce a new equilibrium concept tied to these geometric properties.
What this means in practice
- •For game designers: Design game learning systems that exploit distinct geometric regret classes to improve player strategy adaptation under various learning dynamics.
- •For online advertising teams: Tune bidding strategies using gradient-based algorithms that account for geometry-specific regret to optimize long-term performance.
A theory result. No direct application yet.
Authors
Ashkan Soleymani, Gabriele Farina, Patrick Jaillet
Abstract
Online gradient descent is usually studied through external regret, where the learner competes with fixed alternatives. Recent work shows that first-order methods control richer action-dependent deviations. We ask for a geometric characterization of the deviations with respect to which online gradient descent, mirror descent, and follow-the-regularized-leader (FTRL) achieve no regret. We identify exactness as the common principle. Exactness means that the relevant displacement field is generated by a scalar potential, or equivalently that the associated one-form is exact in the geometry used by the algorithm. This geometry depends on the algorithm. For gradient descent it is Euclidean geometry, for mirror descent it is the geometry induced by the regularizer, and for FTRL it is the cumulative dual state. Under mild regularity conditions, exactness yields sublinear regret, while nonzero circulation provides the complementary obstruction and leads to linear regret. This gives a unified geometric framework for understanding the deviation classes controlled by these algorithms and reveals that different first-order methods can control genuinely different classes of deviations. These deviation classes have direct consequences for learning, particularly in games. We study the equilibrium notions induced by exact-form deviations and introduce conservative correlated equilibrium, reflecting both the conservative geometry of the underlying displacement fields and the restricted family of deviations available to the players. We characterize its relation to correlated equilibrium, determine when the resulting equilibrium notions coincide and when they separate, and show how these relationships depend on the geometry and the learning algorithm. Overall, this work gives a unified geometric account of what first-order online learning algorithms are no-regret with respect to, beyond fixed comparators.