PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader

Ashkan Soleymani, Gabriele Farina, Patrick Jaillet

arXiv:2609.09466v1cs.LGcs.GTmath.OC

TL;DR

The paper asks which action-dependent deviations receive no-regret guarantees from online gradient descent, mirror descent, and FTRL beyond fixed comparators. It develops an exactness-based geometric characterization across their respective geometries, showing that exactness supports sublinear regret while circulation yields linear-regret obstructions and distinct equilibrium implications. The paper also identifies scope limits in mirror representation and continuous-support equilibrium separation.

  • Problem

    The paper addresses the gap between external regret against fixed comparators and the richer action-dependent deviation classes controlled by first-order algorithms.

  • Method

    It represents feasible deviations through exact displacement fields or algorithm-specific exact one-forms and analyzes circulation, boundary feasibility, and induced equilibrium constraints.

  • Results

    Exactness yields sublinear regret under regularity assumptions, whereas nonzero circulation can force linear regret; the controlled deviation classes differ across gradient descent, mirror descent, and FTRL.

  • Takeaways & Limitations

    The relevant no-regret class is determined by the algorithm’s geometry, and strict differences between deviation maps may or may not persist in the resulting equilibrium sets.

  • Takeaways & Limitations

    In general mirror geometry, proximal representation requires curvature conditions beyond mirror exactness, and the continuous-support separation construction has absolutely continuous marginals but lies on a lower-dimensional diagonal.

Abstract

from arXiv · show

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.

1 Introduction

The paper characterizes action-dependent deviations controlled by first-order methods through exactness of displacement fields, with circulation providing the obstruction to sublinear regret. It extends this framework across Euclidean, mirror, and cumulative-dual geometries and studies the resulting equilibrium notions.

  • 1 Introduction: The paper studies finite feasible deviation maps for gradient descent, mirror descent, and FTRL rather than only fixed comparators.The deviation classes depend on the algorithm’s geometry and may differ at boundary points.
  • 1 Introduction: Smooth exact-form deviations strictly contain weakly convex proximal deviations, making proximality a mechanism for exactness rather than the defining property.Every smooth Euclidean exact-form deviation admits a sufficiently small identity interpolation that is proximal.
  • 1 Introduction: Exact displacement fields yield sublinear regret, while nonzero circulation can generate linear regret.For gradient descent, exactness is Euclidean; mirror descent uses its regularizer-induced one-form, while FTRL uses cumulative dual state.
  • 1 Introduction: In mirror geometry, radial proximal classes lie within mirror-exact classes, but Euclidean interpolation equivalence can fail for nonquadratic regularizers.The representation gap is tied to curvature conditions on the regularizer.
  • 1 Introduction: FTRL exactness implies mirror exactness, whereas the converse can fail, especially when boundary effects separate their finite deviation classes.The paper develops FTRL’s theory in cumulative dual state and exhibits a powered ℓp separation.
  • 1 Introduction: The induced conservative correlated equilibrium coincides with proximal correlated equilibrium in the stated unrestricted setting and with correlated equilibrium in finite-support and interval-action cases.The paper also constructs continuous-support settings where these equilibrium notions separate.

2 Related Work

Related work has expanded regret analysis beyond fixed comparators, while the paper develops a finite feasible-map theory explaining which action-dependent deviations first-order methods control. Its geometric perspective specializes and extends prior conservative-field and proximal-regret frameworks.

  • 2 Related Work: Φ-regret generalizes external regret by comparing actions with feasible action-dependent transformations, motivating the search for efficiently controlled deviation classes.External regret is recovered when the deviation family contains all constant maps.
  • 2 Related Work: Recent work challenges the view that online gradient descent only minimizes external regret and motivates finite-map characterizations for simpler first-order algorithms.The paper targets online gradient descent, mirror descent, and FTRL.
  • 2 Related Work: The paper specializes first-order conservative-field ideas to feasible endomorphisms and finite Φ-regret against actual endpoints.This avoids tangent-projection machinery and focuses on boundary feasibility directly.
  • 2 Related Work: It answers an open question by characterizing the larger finite-map class controlled by gradient descent through exactness and circulation beyond proximal deviations.The result identifies a geometric boundary for gradient-descent regret guarantees.
  • 2 Related Work: The framework replaces constant gradient-equilibrium directions with nonlinear feasible displacements generated by potentials.Both settings use a telescoping mechanism, but this paper studies finite Φ-regret and induced equilibrium constraints.

3 Setting and Notation

The paper formulates regret against feasible deviation maps and displacement fields, then defines Euclidean exact-form deviations through differentiable potentials. Smoothness and normalization provide the regularity needed for uniform guarantees.

  • 3 Setting and Notation: For a feasible deviation ϕ, regret compares observed losses with the displaced action through Dϕ(x)=x−ϕ(x).The framework also defines regret directly for arbitrary displacement fields and transfers linearized bounds to convex losses.
  • 3 Setting and Notation: A Euclidean exact-form deviation has a displacement field generated by the gradient of a continuously differentiable potential.The exact-form class consists of feasible maps satisfying this potential representation.
  • 3 Setting and Notation: Smooth exact-form results require the potential gradient to be locally Lipschitz, which is stronger than bare C1 regularity.This stronger condition is later used to show that scaled exact deviations are proximal.
  • 3 Setting and Notation: Normalized exact-form classes fix potential-oscillation and gradient-smoothness parameters when taking a supremum over deviations.The normalization prevents fixed-deviation bounds from being mistaken for uniform Φ-regret guarantees.

4 Online Gradient Descent Minimizes Exact-form Regret

Online gradient descent achieves sublinear regret against smooth feasible exact-form deviations because their displacement fields telescope through a potential. Feasibility controls the projection residual, while circulation supplies the matching obstruction.

  • 4 Online Gradient Descent Minimizes Exact-form Regret: Exactness makes the displacement contribution telescope, yielding O(T) regret bounds for smooth feasible deviations under bounded gradients and potential oscillation.A single learning rate controls the normalized class Φexact(B,L).
  • 4 Online Gradient Descent Minimizes Exact-form Regret: Feasibility makes the projection residual favorable because the residual lies in the normal cone while ϕ(K) remains inside K.On an unconstrained domain, the projection residual vanishes.
  • 4 Online Gradient Descent Minimizes Exact-form Regret: The OGD bound applies when Dϕ(x)=∇Ψ(x) and Ψ has an L-Lipschitz gradient with respect to the Euclidean norm.The theorem holds for every loss-gradient sequence under the stated assumptions.

5 Proximal Deviations are Exact-Form

Weakly convex proximal deviations have exact displacement fields, so projected gradient descent controls them through the broader exact-form framework. The section also shows that this framework covers several standard deviation classes, including fixed comparators, projections, interpolations, local proximal maps, and symmetric affine swaps.

  • 5 Proximal Deviations are Exact-Form: The Moreau-envelope identity is the key mechanism that places weakly convex proximal deviations inside the exact-form class.The indicator of K ensures the proximal map is a feasible map from K to K.
  • 5 Proximal Deviations are Exact-Form: Weakly convex proximal maps are feasible Euclidean exact-form deviations because x − ϕ_F(x) equals the gradient of their Moreau envelope.The displacement gradient is Lipschitz, yielding the corresponding projected-gradient regret guarantee under boundedness assumptions.
  • 5 Proximal Deviations are Exact-Form: The resulting regret bound is nontrivial when the gradient bound and potential oscillation are positive; otherwise the displayed optimizing step size need not be used.The zero-gradient or zero-oscillation cases give a trivial bound.
  • 5 Proximal Deviations are Exact-Form: The exact-form class includes external-regret comparators, projections, projection-based deviations, identity interpolations, local proximal deviations, and symmetric affine swaps.These examples are obtained through indicator functions, linear-plus-indicator functions, quadratic interpolation generators, and symmetric affine displacement fields.
  • 5 Proximal Deviations are Exact-Form: Symmetric affine deviations are exact-form directly because their displacement is the gradient of a quadratic potential.This avoids needing a proximal representation for the affine map.

6 The Exact-form Class Strictly Contains the Proximal Class

Smooth Euclidean exact-form deviations strictly contain weakly convex proximal deviations as maps, but sufficiently small identity interpolations of every smooth exact deviation become proximal. Consequently, the strict map-level separation need not produce different equilibrium sets.

  • 6 The Exact-form Class Strictly Contains the Proximal Class: A smooth feasible exact-form deviation exists that is not proximal for any one-dimensional weakly convex function.The construction uses nonmonotonicity, whereas one-dimensional weakly convex proximal maps are monotone.
  • 6 The Exact-form Class Strictly Contains the Proximal Class: Every smooth exact-form deviation admits a sufficiently small positive interpolation with the identity that is proximal.The interpolation scales the displacement and transfers the relevant proximal-regret guarantee.
  • 6 The Exact-form Class Strictly Contains the Proximal Class: The identity-radial closure of Euclidean proximal deviations equals the class of smooth exact-form deviations.Thus Φprox is strictly contained in Φsm, while their radial closures coincide.
  • 6 The Exact-form Class Strictly Contains the Proximal Class: Linearized deviation regret scales exactly under identity interpolation, and convex losses preserve profitability under every positive interpolation.This scaling supplies the mechanism behind the equilibrium equivalence.
  • 6 The Exact-form Class Strictly Contains the Proximal Class: For convex games with compact action sets and jointly continuous losses, conservative correlated equilibrium equals proximal correlated equilibrium.The equality holds despite the strict inclusion between the underlying deviation-map classes.

7 Curl Induces Linear Regret for Online Gradient Descent

For online gradient descent, exact displacement fields have zero circulation and yield sublinear regret under the stated regularity conditions. Nonzero circulation instead supports a bounded cyclic adversary that forces linear regret, establishing a curl-based boundary.

  • 7 Curl Induces Linear Regret for Online Gradient Descent: Exact displacement fields have zero circulation around every closed loop, so this obstruction cannot arise for exact-form deviations.The upper-bound proof telescopes because exact one-forms integrate to zero around closed loops.
  • 7 Curl Induces Linear Regret for Online Gradient Descent: Nonzero circulation along a feasible closed loop can be converted into a bounded cyclic adversary causing linear regret for online gradient descent.The lower bound uses a sufficiently small constant step size and a loop with positive circulation.
  • 7 Curl Induces Linear Regret for Online Gradient Descent: The lower bound remains linear under an anytime geometric-epoch schedule, so it is not an artifact of knowing the horizon.Epoch transients sum to a lower-order term while the positive loop contributions sum to Ω(T).
  • 7 Curl Induces Linear Regret for Online Gradient Descent: The constant-step lower-bound construction may require a sufficiently small step size depending on the witnessing loop, unlike the usual known-horizon upper bound.This is the main learning-rate distinction between the two directions.
  • 7 Curl Induces Linear Regret for Online Gradient Descent: On a simply connected relative interior, vanishing skew derivatives are equivalent to a gradient potential, while a nonzero skew derivative enables linear-regret forcing along a small feasible loop.This gives the Euclidean curl criterion for finite deviation maps, subject to feasibility and smoothness assumptions.

8 Online Mirror Descent and Exact One-forms

Mirror descent controls deviations whose displacement is exact in mirror geometry, with Bregman proximal maps as a special case. The characterization remains valid beyond Legendre regularizers, while boundary effects can separate mirror descent from FTRL and nonquadratic geometry can separate mirror-exactness from proximal representability.

  • 8 Online Mirror Descent and Exact One-forms: Mirror descent controls mirror-exact deviations because the displacement is a gradient in dual coordinates, making the regret proof telescope.The relevant one-form is Dϕ(x)^T d∇R(x), and mirror-exactness is equivalent to exactness after weighting by the mirror metric.
  • 8 Online Mirror Descent and Exact One-forms: At the boundary, standard constrained mirror descent and FTRL can have different dynamics and exact deviation classes despite coinciding for constant-step linearized losses in the Legendre interior.Mirror descent carries a normal-cone residual, whereas FTRL retains accumulated losses in one regularized minimization.
  • 8.1 Examples of Mirror-exact Deviations: Mirror-exact deviations include every fixed-comparator deviation and can include deviations that are not Euclidean-exact.Multiplicative-weights instances also admit multiplicative mirror-exact deviations with arbitrary temperature vectors.
  • 8.3 Bregman Proximal Regret is Mirror-exact: Bregman proximal deviations are mirror-exact, so Bregman proximal regret is a special case of mirror-exact regret.The result is first established in the Legendre interior and then extended to boundary iterates.
  • 8.4 Full Mirror Characterization Beyond Legendre Regularizers: Beyond Legendre regularizers, mirror descent has sublinear regret when the mirror one-form is exact and the potential and displacement satisfy the stated regularity conditions.The bound applies with boundary iterates and does not require ∇R to be onto or R to be Legendre.
  • 8.4 Full Mirror Characterization Beyond Legendre Regularizers: Nonzero mirror circulation can be exploited along a feasible loop to force linear regret, making exactness the sharp geometric boundary under the stated assumptions.The upper and lower bounds are complementary: smoothness and potential oscillation determine rates, while circulation rules out no regret.
  • 8.5 Identity Interpolation of Bregman Proximal Deviations: Identity interpolation always transfers Bregman proximal regret to the radial proximal class, but this class can be strictly smaller than the mirror-exact class.In Legendre geometry, proximal representation additionally requires convexity of R*−αΨ and a curvature condition.

9 Follow-the-Regularized-Leader Beyond Legendre Regularizers

FTRL shares mirror descent’s exactness guarantees in the Legendre interior but diverges at boundaries, where cumulative-dual exactness characterizes its own sublinear-regret class.

  • Beyond the Legendre interior, boundary effects can make mirror descent and FTRL control different deviation classes.
  • In the Legendre interior, mirror descent and FTRL generate identical iterates for constant-step linearized losses, so mirror-descent guarantees transfer to FTRL.
  • FTRL-exactness requires the displacement field to be exact in the cumulative dual state, with a differentiable potential generating that displacement.
  • Exact FTRL fields achieve sublinear regret under uniform convexity, relative smoothness, bounded gradients, and bounded potential oscillation.
  • Nonzero circulation in the cumulative dual state lets bounded-gradient adversaries force linear regret, yielding an exactness-versus-circulation characterization.
  • A smooth deviation can be mirror-exact with O(T) regret under constrained mirror descent yet incur cT −O(1/η) regret under FTRL, proving strict separation.

10 Conservative Correlated Equilibria in Convex Games

The paper defines conservative correlated equilibrium using exact-form deviations and relates it to proximal and full correlated equilibrium under different support and action-space conditions.

  • Equilibrium constraints are invariant under identity-radial closure, although quantitative bounds additionally require a common lower bound on interpolation scales.
  • Conservative correlated equilibrium tests nonpositive gain against a specified family of feasible Euclidean exact-form deviations.
  • Regret guarantees for normalized exact-form families yield approximate conservative correlated equilibria through the standard regret-to-equilibrium conversion.
  • Under unrestricted conventions, proximal and conservative correlated equilibrium coincide, while strict inclusion of deviation maps need not imply strict inclusion of zero-tolerance equilibrium sets.
  • CE, ConCE, and PCE coincide on finite supports and under continuous losses with one-dimensional individual action spaces.
  • A two-player convex game admits an uncountably supported distribution with absolutely continuous marginals satisfying ConCE = PCE but not CE.

11 Conclusion

The conclusion presents exactness as the common geometric principle behind first-order regret guarantees while emphasizing algorithm-dependent boundary effects and open limitations.

  • Exact feasible displacement fields yield regret bounds in Euclidean geometry, while nonzero circulation can force linear regret.
  • Mirror geometry replaces Euclidean exactness with a regularizer-dependent one-form and requires additional regularity to control boundary residuals.
  • Proximal deviations are a subclass of exact-form deviations, and mirror descent and FTRL can diverge at constrained boundaries despite agreeing in the Legendre interior.
  • Unrestricted ConCE and PCE coincide with CE on finite supports and one-dimensional continuous-action spaces, but separate in a two-dimensional continuous-support example.
  • The paper leaves open whether weaker mirror regularity suffices and whether the equilibrium separation persists for full-dimensional absolutely continuous joint distributions.

B Scaled Exact Deviations and Proximal Representation

Euclidean smooth exact-form deviations admit sufficiently small identity interpolations that are weakly convex proximal maps, and the converse identifies the radial proximal closure with smooth exact-form deviations.

  • The construction replaces the potential outside the action set, then uses strong convexity of the interpolated generator to obtain a weakly convex proximal representation.
  • Every feasible C1,1 exact-form deviation admits a sufficiently small identity interpolation that is a weakly convex proximal map.
  • The interpolated map equals the proximal map on the feasible set because convexity and feasibility prevent the constraint from changing the unconstrained minimizer.
  • The identity-radial closure of Euclidean proximal deviations equals the class of smooth exact-form deviations.

C Boundary-Compatible Finite Interpolation

Finite cyclic monotonicity characterizes when subgradients come from a convex potential, enabling finite interpolation by weakly convex proximal maps. Exact-form deviations yield sublinear regret for OGD, whereas nonzero circulation creates linear regret.

  • Finite interpolation: Finite data admit a proper closed convex potential exactly when their subgradient pairs are cyclically monotone.Checking nontrivial simple cycles suffices.
  • Finite interpolation: For any distinct targets in K, sufficiently small common α produces a ρ-weakly convex proximal map satisfying proxFα(xj) = (1 −α)xj + αyj.The proximal minimizer is unique under the stated weak-convexity condition.
  • Exact-form regret: OGD controls every Euclidean exact-form deviation whose displacement is the gradient of an L-smooth potential.The proof telescopes potential terms and bounds the remaining terms using the gradient norm.
  • Exact-form regret: A single learning rate controls the normalized class Φexact(B, L), with the bound obtained uniformly over all deviations in that class.Normalization makes the common step size possible.

D.2 Proofs for Section 5

Euclidean proximal maps form a broad exact-form deviation class for projected gradient descent. This class contains fixed comparators, projections, interpolation maps, local proximal deviations, and suitable symmetric affine swaps.

  • Proximal deviations: Every proper lower-semicontinuous ρ-weakly convex proximal map is Euclidean exact-form, with a Lipschitz gradient determined by ρ.Consequently, projected gradient descent controls these proximal deviations through the exact-form regret theorem.
  • Contained deviations: The exact-form class includes external regret, projection to a convex subset, and projection-based/no-move deviations.These arise by choosing indicator or linear-plus-indicator regularizers.
  • Contained deviations: Interpolation maps ϕ(x) = (1 −α)x + αu are proximal deviations generated by a quadratic regularizer centered at u.Convexity of K makes the unconstrained minimizer feasible.
  • Affine deviations: Affine maps are exact-form when I −A is self-adjoint on the direction space of aff(K), provided the map is feasible.The potential is constructed on the affine hull and extended to the ambient space.

D.3 Proofs for Section 7

The proof theory links exactness to zero circulation in the relevant geometry and shows that nonzero circulation yields linear regret. Mirror exactness is geometry-dependent and can differ from Euclidean exactness.

  • Euclidean circulation: Nonzero circulation around a feasible loop lets an adversary force OGD to incur linear regret, including after a bounded steering transient.The resulting lower bound is Ω(T).
  • Euclidean circulation: A closed polygon traversed by projected gradient descent accumulates regret C/η in one traversal.The construction chooses gradients so the iterates follow the polygon exactly.
  • Euclidean exactness: On a simply connected relative interior, vanishing skew derivatives are equivalent to a gradient potential, while nonzero curl supplies a loop with linear-regret obstruction.The curl-free case requires an ambient smooth extension satisfying the theorem’s assumptions.
  • Mirror exactness: Mirror exactness means D(x)^T d∇R(x) is the differential of a scalar potential, so the relevant displacement field is exact in mirror geometry.This yields a dual-gradient representation.
  • Mirror exactness: Mirror-exact regret is genuinely different from Euclidean exact-form regret because changing the mirror map changes which deviations telescope.The paper gives a feasible field that is mirror-exact but not Euclidean-exact.
  • Mirror deviations: Bregman proximal regret is a special case of mirror-exact regret, while mirror-exact deviations also include dual-coordinate interpolation and multiplicative deviations on the simplex.Fixed comparators are mirror-exact for every mirror map.

D.8 Proofs for Section 8.4

The proofs establish that exact displacement fields yield sublinear regret, whereas nonzero circulation can force linear regret, with the characterization depending on algorithmic geometry. They also prove separations between mirror descent and FTRL deviation classes and derive consequences for conservative correlated equilibrium.

  • Mirror-descent upper bounds: The constrained mirror-descent proof controls regret by telescoping potential differences plus regularity terms, producing o(T) regret under bounded gradients and suitable oscillation or Lipschitz assumptions.The optimized bound is obtained by balancing the potential term and the step-size-dependent error term.
  • Mirror-descent lower bounds: A nonzero circulation loop can be tracked exactly by constrained mirror descent, yielding a positive average regret and hence linear cumulative regret after repetition.The construction remains valid at boundary points because each iterate is the unique minimizer of a strongly convex mirror-descent subproblem.
  • Mirror exactness and circulation: Exact mirror displacement fields yield sublinear regret, while failed exactness or nonzero circulation can force linear regret on sufficiently small loops.The equivalence between exactness, coordinate symmetry, and vanishing circulation holds on the open convex interior under the stated regularity assumptions.
  • FTRL exactness: For FTRL, exactness is characterized in cumulative dual state: a smooth deviation is exact if and only if its Jacobian is symmetric, while a nonzero skew derivative permits linear regret along a small dual loop.The lower bound can be forced from every initial dual state with sufficiently small constant step size.
  • Mirror descent versus FTRL: FTRL-exact deviations are mirror-exact, but the inclusion is strict: a smooth feasible deviation can receive O(T) mirror-descent regret while FTRL incurs cT −O(1/η) regret against the same map.This establishes an algorithmic separation between the finite deviation classes controlled by the two methods.
  • Equilibrium consequences: For finitely supported distributions in convex games, correlated equilibrium, conservative correlated equilibrium, and proximal correlated equilibrium coincide, whereas with uncountable support CE can be strictly smaller than ConCE = PCE.The separation example uses absolutely continuous marginals and a measurable profitable deviation outside the conservative family.
Loading 2609.09466v1…