alphaFeedback

WorksComputer Science

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

AI contributions
Not recorded for this paper
View details

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.

Introduction

Online gradient descent is classically understood as an external-regret minimizer [1, 2, 3]. Against a sequence of linear losses, its iterates compete with every fixed comparator x′∈Kx' \in K. This guarantee is the basic engine behind the standard convergence of no-regret play to coarse correlated equilibrium [4, 5]. From the viewpoint of swap regret and the notion of hindsight rationality, however, external regret is only the simplest notion out of a wide spectrum. External regret compares xtx_t with fixed alternatives, while a general deviation may replace xtx_t by a feasible point ϕ(xt)∈K\phi(x_t) \in K that depends on the current action [6, 7, 8].

Recent work makes clear that gradient dynamics control more than fixed comparators, although the guarantees appear in different forms. In first-order equilibrium theory, Ahunbay [ [9] studies infinitesimal strategy modifications generated by continuous vector fields. In the coarse adversarial setting, the fields certified by projected gradient dynamics are conservative gradient fields with the appropriate tangency to the action set. In normal-form games, Ahunbay and Bichler [ [10] specialize this picture to a tractable linear–quadratic family and obtain semicoarse correlated equilibria through LP-based guarantees. In parallel, Cai, Daskalakis, Luo, Wei, and Zheng [ [11] showed that online gradient descent and mirror descent control deviations generated by proximal operators of weakly convex functions. As discussed by Cai et al. [ [11] and Ahunbay [ [9], these lines of work have substantial overlap but are not comparable in general, reflecting the different deviation classes and guarantees they study.

In this paper, we study Φ\Phi-regret against actual feasible deviation maps ϕ:K→K\phi: K \to K. Writing Dϕ(x):=x−ϕ(x)D_{\phi}(x) := x - \phi(x), we show that online gradient descent has O(T)O(\sqrt{T}) regret against every sufficiently regular feasible deviation whose displacement is exact, Dϕ=∇ΨD_{\phi} = \nabla\Psi, and obtain a uniform bound over normalized families with common smoothness and potential-oscillation parameters. Thus the comparator is the actual endpoint ϕ(xt)\phi(x_t), rather than an infinitesimal modification of the current action. The underlying Euclidean exactness principle can also be obtained by specializing the more general first-order framework of Ahunbay [ [9] to displacement fields generated by feasible endomorphisms. Working directly with endomorphisms, however, removes the tangent-projection machinery and allows the boundary geometry to be handled directly through feasibility, convexity, and normal cones. This yields explicit finite-time bounds for feasible endomorphisms.

A simple example reveals the geometry behind this formulation. Consider an affine deviation ϕ(x)=Ax+b\phi(x) = Ax+b, whose displacement is Dϕ(x)=(I−A)x−bD_{\phi}(x) = (I-A)x-b. When I−AI-A is symmetric, this displacement is the gradient of a quadratic potential. Thus the symmetric affine deviations appearing in Ahunbay and Bichler [ [10], Cai et al. [ [11] are finite maps with exact displacement fields. The example suggests that the relevant property is not linearity itself, but exactness of the displacement.

The same structure appears in proximal deviations. If F=f+ιKF = f + \iota_K is weakly convex, the Moreau-envelope identity gives x−prox⁡F(x)=∇MF(x)x-\operatorname{prox}_F(x) = \nabla M_F(x), where MFM_F is the Moreau envelope of FF. Proximal deviations therefore also have exact displacement fields. From this viewpoint, proximality is one mechanism for producing exactness rather than the underlying geometric property itself. We show that the smooth exact-form class strictly contains the weakly convex proximal class, while every smooth Euclidean exact-form deviation admits a sufficiently small interpolation with the identity that is proximal.

As it turns out, this characterization is tight, as witnessed by circulations. Exact one-forms have zero circulation around closed loops, whereas nonzero circulation can be converted into a bounded cyclic adversary with linear regret. For feasible finite maps, this gives an exactness-versus-circulation criterion under the regularity and step-size conditions developed below. Together with the positive result, this identifies the geometric boundary of the finite deviation class controlled by online gradient descent.

We next extend this finite-map viewpoint to mirror descent. The relevant notion of exactness is determined by the mirror geometry, through the one-form Dϕ(x)Td∇R(x)D_{\phi}(x)^{\mathsf{T}}\mathrm{d}\nabla R(x). We first develop the theory in the Legendre interior, where the geometry is most transparent, and recover Bregman proximal deviations as a special case. We then remove the Legendre assumption and obtain corresponding upper and lower bounds for standard constrained mirror descent with boundary iterates. This gives a finite-map exactness-versus-circulation characterization in mirror geometry as well.

Bregman proximality leads to a separate representation problem. Identity interpolation always transfers proximal regret to the radial closure of the Bregman proximal class, and this radial class is contained in the mirror-exact class. In Euclidean geometry the two classes coincide after radial closure, but this can fail for a general mirror regularizer. In the Legendre regime, we characterize proximal interpolation through the convexity of R∗−αΨR^*-\alpha\Psi and the curvature of the reconstructed proximal generator. A squared ℓp\ell_p example shows that no positive interpolation may exist even when the dual potential is smooth with globally Lipschitz gradient.

We also treat FTRL separately. Mirror descent and FTRL coincide for constant-step linearized losses in the Legendre interior, but their finite deviation classes can separate once boundary effects are present. We develop the corresponding exactness-versus-circulation theory in the cumulative dual state of FTRL and show that FTRL exactness implies mirror exactness, while the converse can fail. A powered ℓp\ell_p construction gives a deviation with O(T)O(\sqrt{T}) regret under mirror descent and linear regret under FTRL.

Finally, we study the equilibrium notions induced by these finite deviation classes. We call the equilibrium notion associated with Euclidean exact-form deviations conservative correlated equilibrium (ConCE). The name reflects the fact that these deviations are generated by conservative, or exact, displacement fields, and that players are correspondingly restricted to this conservative family of deviations rather than arbitrary measurable remappings. Although smooth exact-form maps strictly contain weakly convex proximal maps, their unrestricted equilibrium constraints, in convex games with compact action sets and jointly continuous losses, coincide when the approximation error is zero, so ConCE = PCE. We further show that this common notion coincides with full correlated equilibrium on finite support and, under continuous losses, when every player’s action space is an interval. In contrast, with two-dimensional individual action spaces we construct an uncountably supported distribution with absolutely continuous marginals for which CE ⊊\subsetneq ConCE = PCE.

Contributions relative to prior work. Relative to Ahunbay [ [9], our Euclidean analysis specializes the first-order geometric framework to finite feasible endomorphisms and studies the resulting Φ\Phi-regret and equilibrium classes. This specialization yields explicit finite-time bounds by exploiting the additional convex geometry available for endomorphisms and avoiding the tangent projections and auxiliary geometric quantities needed in the general infinitesimal formulation. Relative to Ahunbay and Bichler [ [10], our exact-form class extends the tractable linear-quadratic family to nonlinear finite deviations while retaining the symmetric affine maps as a special case. Relative to Cai et al. [ [11], we identify exactness as the broader finite-map mechanism containing weakly convex proximal deviations, prove strict map-level containment, and characterize the role of identity interpolation in relating the two classes.

Beyond the Euclidean setting, we develop the finite-map theory for standard constrained mirror descent without Legendre duality, separate mirror exactness from Bregman proximal representability, and show that the Euclidean interpolation phenomenon can fail in nonquadratic mirror geometry. We also develop a separate cumulative-dual theory for FTRL and exhibit a boundary separation between the finite deviation classes controlled by FTRL and mirror descent. These algorithmic results are complemented by the interpolation and equilibrium results above, which determine when distinctions between deviation classes persist at the level of correlated-equilibrium constraints.

Related Work

The notion of regret is one of the central concepts in the theory of online algorithms. In its simplest incarnation, regret measures competitiveness against the best fixed comparator in hindsight. In other words, letting KK denote the set of possible decisions, xtx_t be the decision at time tt, and ⟨gt,⋅⟩\langle g_t,\cdot\rangle be the linear loss incurred at time tt by the decision maker, regret takes the form

sup⁡x^∈K∑t=1T⟨gt,xt−x^⟩.\sup_{\widehat{x}\in K}\sum_{t=1}^{T}\langle g_t,x_t-\widehat{x}\rangle.

As is standard, we refer to this notion of regret as external regret. Since the seminal work of Zinkevich [ [1], it is known that online gradient descent keeps external regret sublinear. Generalizations of this result to online mirror descent and follow-the-regularized-leader (FTRL) are by now standard [12, 2] (Oрабona 2019), in particular optimistic algorithms and their variants for the self-play setting in games [Rakhlin and Sridharan, 2013a,b, Syrgkanis et al., 2015, Chen and Peng, 2020, Daskalakis et al., 2021, Farina et al., 2022a, Piliouras et al., 2022a, Soleymani et al., 2025a,b].

Over the past few decades researchers have been interested in obtaining guarantees for stronger notions of online competitiveness than external regret. Within the constellation of alternative notions (which includes concepts such as interval regret, dynamic regret, policy regret, switching regret, among others), the notion of Φ\Phi-regret [6] is the most related to our work.

Φ\Phi-regret is a generalization of external regret indexed by a set Φ\Phi of deviation functions ϕ:K→K\phi:K\to K, comparing the sequence of online choices xtx_t to the transformed sequence ϕ(xt)\phi(x_t) across all ϕ∈Φ\phi\in\Phi:

sup⁡ϕ∈Φ∑t=1T⟨gt,xt−ϕ(xt)⟩.\sup_{\phi\in\Phi}\sum_{t=1}^{T}\langle g_t,x_t-\phi(x_t)\rangle.

External regret is then understood as the special instantiation of Φ\Phi-regret in which the set Φ\Phi contains all constant functions. Partially motivated by game-theoretic applications and the celebrated wealth of connections between regret and equilibrium notions [22, 4] Cesa-Bianchi and Lugosi, [5], a long line of work has been concerned with characterizing the largest set of deviations Φ\Phi that admits efficient algorithms guaranteeing sublinear Φ\Phi-regret (e.g., [8, 23, 24, 25, 26, 27] and references therein). Among the most general results in that space, it is now understood that Φ\Phi-regret minimization with respect to all linear or low-degree polynomial endomorphic transformations of KK can be achieved efficiently for any convex and compact set KK given via efficient oracle access [28, 29]. These algorithms are quite involved, and make use of complex separation and fixed-point machinery to deal with the geometry of endomorphisms.

While the common wisdom had been for a long time that simple algorithms such as online gradient descent only minimize external regret—and the more complex algorithms mentioned above are thus necessary to target more challenging variants of Φ\Phi-regret—recent papers have challenged this view. Specifically, Ahunbay [ [9], Ahunbay and Bichler [ [10], Cai et al. [ [30, 11] demonstrated that online gradient descent keeps under control far more than just external regret: for example, it minimizes regret against all symmetric linear endomorphic transformations, and all proximal transformations of KK. These results invite intriguing questions on exactly what notions of Φ\Phi-regret online gradient descent minimizes, for at least two reasons: (i) notions of Φ\Phi-regret induced by proximal transformations are not currently known to be achievable in other ways (for example, by low-degree polynomial transformations); and (ii) the extreme simplicity of online gradient descent compared to more advanced Φ\Phi-regret techniques makes a compelling case that the former should be used whenever possible. The main goal of the present paper is to develop a finite feasible-map theory that explains a broad class of Φ\Phi-regret guarantees given by these algorithms, including online gradient descent, mirror descent and FTRL.

Our Euclidean results are closely related to the first-order framework of Ahunbay [ [9]. After specializing that framework to displacement fields generated by feasible endomorphisms, its qualitative conservativity and circulation conclusions yield the corresponding exactness picture for projected gradient descent. We focus instead on Φ\Phi-regret against the actual endpoints ϕ(xt)\phi(x_t) and on the equilibrium notions induced by these finite deviations. The endomorphism structure also permits a more direct quantitative analysis. Feasibility, convexity, and normal-cone geometry remove the tangent projections and auxiliary geometric quantities of the general infinitesimal formulation. Relative to Ahunbay and Bichler [ [10], our exact-form class extends the tractable linear–quadratic family to nonlinear feasible deviations while retaining symmetric affine endomorphisms as a special case.

Our results also address an open question raised by Cai et al. [ [11]. After showing that gradient descent minimizes proximal regret, they ask for a tight characterization of the regret guarantees of gradient descent and note that the class controlled by the algorithm may be strictly broader than the proximal class. We characterize this larger finite-map class geometrically through exactness and circulation. For online gradient descent, smooth exact-form deviations strictly contain weakly convex proximal deviations, while the circulation converse identifies the corresponding obstruction to sublinear regret. We develop the analogous characterization for standard constrained mirror descent with differentiable strongly convex regularizers, where the relevant object is the mirror one-form Dϕ(x)Td∇R(x)D_{\phi}(x)^{\mathsf{T}}\mathrm{d}\nabla R(x). Under our regularity assumptions, this identifies the full geometric deviation class controlled by mirror descent and goes beyond the Bregman proximal class studied by Cai et al. [ [11]. We also study FTRL, which is not treated in Cai et al. [ [11], and show that its controlled deviation class can differ from that of mirror descent once boundary effects are present. We further show that proximal representability is a separate question. In Euclidean geometry, identity interpolation recovers the smooth exact-form class, while in general mirror geometry the radial Bregman proximal class can be strictly smaller than the mirror-exact class. Finally, we derive the equilibrium consequences of these finite deviation classes. To our knowledge, the resulting equilibrium results are new, including the equality of ConCE and PCE under the unrestricted definitions, their coincidence with CE on finite support and on interval action spaces under continuous losses, and their strict separation from CE on a continuous support in higher dimension.

The gradient-equilibrium framework of Angelopoulos et al. [ [31] is closely connected to our potential-based viewpoint. In the unconstrained setting, their gradient-equilibrium condition can be recovered from the linear potentials Ψv(x)=⟨v,x⟩\Psi_v(x)=\langle v,x\rangle, whose exact displacements are the constant vectors ∇Ψv=v\nabla\Psi_v=v. Our framework replaces these constant directions by nonlinear finite displacements Dϕ(x)=∇Ψ(x)D_{\phi}(\mathbf{x}) = \nabla\Psi(\mathbf{x}) generated by feasible endomorphisms ϕ:K→K\phi: K \to K. In this sense, both approaches are driven by the same telescoping mechanism, while our setting uses it to study finite Φ\Phi-regret and the equilibrium constraints induced by nonlinear action-dependent deviations. Their constrained formulation incorporates feasibility through boundary or regularization residuals, whereas ours builds feasibility directly into the deviation map.

Setting and Notation

Let K⊆RdK \subseteq\mathbb{R}^{d} be a nonempty closed convex action set. Throughout the Euclidean sections, gradients, projections, and normal cones are taken in the ambient space Rd\mathbb{R}^{d}. When a statement is intrinsically lower-dimensional, such as the curl criterion on relint⁡(K)\operatorname{relint}(K), derivatives and differential forms are taken in affine coordinates on aff⁡(K)\operatorname{aff}(K). The mirror section introduces its own explicit affine-hull convention. Vectors are written in bold, e.g. x\mathbf{x}, g\mathbf{g}, and coordinates use brackets, e.g. x[j]\mathbf{x}[j]. We write [T]:={1,…,T}[T] := \{1,\ldots,T\}. We use ∥⋅∥\lVert\cdot\rVert as shorthand for the Euclidean norm ∥⋅∥2\lVert\cdot\rVert_{2}, and we denote projection onto KK by ΠK\Pi_{K}. Define the ambient normal cone at any x∈K\mathbf{x} \in K by

NK(x):={n∈Rd:⟨n,y−x⟩≤0 for every y∈K}.N_{K}(\mathbf{x}) := \left\{\mathbf{n} \in\mathbb{R}^{d} : \langle\mathbf{n}, \mathbf{y} - \mathbf{x}\rangle\le0 \text{ for every } \mathbf{y} \in K\right\}.

A learner plays xt∈K\mathbf{x}_{t} \in K and observes a vector loss gt∈Rd\mathbf{g}_{t} \in\mathbb{R}^{d}. For a deviation ϕ:K→K\phi: K \to K, define

Dϕ(x):=x−ϕ(x),Reg⁡T(ϕ):=∑t=1T⟨gt,Dϕ(xt)⟩.D_{\phi}(\mathbf{x}) := \mathbf{x} - \phi(\mathbf{x}), \qquad\operatorname{Reg}_{T}(\phi) := \sum_{t=1}^{T} \langle\mathbf{g}_{t}, D_{\phi}(\mathbf{x}_{t})\rangle.

More generally, for a displacement field D:K→RdD: K \to\mathbb{R}^{d}, define Reg⁡T(D):=∑t=1T⟨gt,D(xt)⟩\operatorname{Reg}_{T}(D) := \sum_{t=1}^{T} \langle\mathbf{g}_{t}, D(\mathbf{x}_{t})\rangle. When losses ℓt:K→R\ell_{t}: K \to\mathbb{R} are convex and differentiable, taking gt=∇ℓt(xt)\mathbf{g}_{t} = \nabla\ell_{t}(\mathbf{x}_{t}) gives

ℓt(xt)−ℓt(ϕ(xt))≤⟨∇ℓt(xt),xt−ϕ(xt)⟩.\ell_{t}(\mathbf{x}_{t}) - \ell_{t}(\phi(\mathbf{x}_{t})) \le\langle\nabla\ell_{t}(\mathbf{x}_{t}), \mathbf{x}_{t} - \phi(\mathbf{x}_{t})\rangle.

Thus every linearized regret bound below immediately implies the corresponding convex-loss deviation-regret bound.

Definition 3.1 (Exact-form deviation). A deviation ϕ:K→K\phi: K \to K is Euclidean exact-form if there exists a continuously differentiable potential Ψ\Psi, defined on a neighborhood of KK, such that

x−ϕ(x)=∇Ψ(x)for every x∈K.\mathbf{x} - \phi(\mathbf{x}) = \nabla\Psi(\mathbf{x}) \qquad\text{for every } \mathbf{x} \in K.

When a result refers to a smooth exact-form deviation, the gradient of its potential is locally Lipschitz on a neighborhood of KK. This is stronger than the bare C1C^{1} regularity in the definition above and is the regularity used later to show that scaled exact deviations are proximal; see Theorem 6.2.

We denote the Euclidean exact-form class by

Φexact:={ϕ:K→K:ϕ is a Euclidean exact-form deviation}.\Phi_{\mathrm{exact}} := \{\phi: K \to K : \phi\text{ is a Euclidean exact-form deviation}\}.

Throughout the paper, the subscript identifies the deviation class. Thus Φprox\Phi_{\mathrm{prox}} denotes the Euclidean proximal class, Φexactsm\Phi_{\mathrm{exact}}^{\mathrm{sm}} denotes the smooth exact-form class, and the superscript RR is reserved for a regularizer-dependent mirror class. When a regularizer-dependent class is considered on more than one input domain, the domain is displayed explicitly in parentheses.

Finally, we use the symbol osc⁡K\operatorname{osc}_{K} to denote the range of a function on the set KK, that is,

osc⁡K(Ψ):=sup⁡x∈KΨ(x)−inf⁡x∈KΨ(x).\operatorname{osc}_{K}(\Psi) := \sup_{\mathbf{x}\in K} \Psi(\mathbf{x}) - \inf_{\mathbf{x}\in K} \Psi(\mathbf{x}).

Bounds for a fixed deviation may depend on the parameters of that deviation and therefore need not yield a uniform Φ\Phi-regret bound. We therefore use the following normalized class whenever a supremum over deviations is taken.

Definition 3.2 (Normalized exact-form class). For constants B,L≥0B,L \ge0, let Φexact(B,L)\Phi_{\mathrm{exact}}(B,L) consist of all feasible maps ϕ:K→K\phi:K\to K for which there is a differentiable potential Ψϕ\Psi_{\phi}, defined on a neighborhood of KK, satisfying

x−ϕ(x)=∇Ψϕ(x),osc⁡K(Ψϕ)≤B,x-\phi(x)=\nabla\Psi_{\phi}(x),\qquad\operatorname{osc}_{K}(\Psi_{\phi})\le B,

and whose gradient satisfies

∥∇Ψϕ(y)−∇Ψϕ(x)∥≤L∥y−x∥for all x,y∈K.\lVert\nabla\Psi_{\phi}(y)-\nabla\Psi_{\phi}(x)\rVert\le L\lVert y-x\rVert\qquad\text{for all }x,y\in K.

Proofs not given in the main text are found in the appendices. Appendix A records the convex-analytic preliminaries; Appendix B proves the scaled proximal representation; Appendix C proves the finite interpolation theorem; and Appendix D contains the remaining proofs, organized in the same order as the main text.

Online Gradient Descent Minimizes Exact-form Regret

Online gradient descent with constant step size η>0\eta>0 is

xt+1:=ΠK(xt−ηgt).x_{t+1}:=\Pi_K(x_t-\eta g_t).

(OGD)

We prove a telescoping regret bound for every smooth feasible exact-form deviation ϕ\phi. Under bounded gradients and bounded potential oscillation, this gives Reg⁡T(ϕ)=O(T)\operatorname{Reg}_T(\phi)=O(\sqrt{T}). Exactness of the displacement field, rather than proximality, is the geometric property that makes the bound telescope on Ψ\Psi. Compared with the unconstrained case (online gradient descent over an unbounded domain), the only additional issue is the projection step. The projection residual lies in the normal cone, and the feasibility condition ϕ(K)⊆K\phi(K)\subseteq K ensures that its contribution has the favorable sign.

References

  1. [1]Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, 2003.
  2. [2]Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4): 157–325, 2016.
  3. [3]Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019.
  4. [4]Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127–1150, 2000.
  5. [5]Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
  6. [6]Amy Greenwald and Amir Jafari. A general class of no-regret learning algorithms and game-theoretic equilibria. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernerl 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 2–12. Springer, 2003.DOI
  7. [7]Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
  8. [8]Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning, pages 360–367, 2008.DOI
  9. [9]Mete Şeref Ahunbay. First-order (coarse) correlated equilibria in non-concave games. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026.arxiv.org/abs/2403.18174
  10. [10]Mete Şeref Ahunbay and Martin Bichler. Semicoarse correlated equilibria and lp-based guarantees for gradient dynamics in normal-form games. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 91–91, 2025.arxiv.org/abs/2502.20466
  11. [11]Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. Proximal regret and proximal correlated equilibria: A new tractable solution concept for online learning and games. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 1639–1650, 2026.arxiv.org/abs/2511.01852
  12. [12]Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012.
  13. [18]Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076–39089, 2022a.arxiv.org/abs/2206.08742
  14. [21]Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. Cautious optimism: A meta-algorithm for near-constant regret in general games. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 870–870, 2025b.
  15. [22]Dean P. Foster and Rakesh V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21(1–2):40–55, 1997.
  16. [23]Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. Journal of the ACM, 69(6):41:1–41:41, 2022b. doi: 10.1145/3563772.DOI
  17. [24]Dustin Morrill, Ryan D’Orazio, Marc Lanctot, James R. Wright, Michael Bowling, and Amy R. Greenwald. Efficient deviation types and learning for hindsight rationality in extensive-form games. In Proceedings of the 38th International Conference on Machine Learning, 2021.
  18. [25]Kaito Fujii. Bayes correlated equilibria, no-regret dynamics in bayesian games, and the price of anarchy. In The Thirty Eighth Annual Conference on Learning Theory, pages 2190–2191. PMLR, 2025.
  19. [26]Binghui Peng and Aviad Rubinstein. Fast swap regret minimization and applications to approximate correlated equilibria. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1223–1234, 2024.arxiv.org/abs/2310.19647
  20. [27]Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. From external to swap regret 2.0: An efficient reduction for large action spaces. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1216–1222, 2024.DOI
  21. [28]Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, and Jon Schneider. Efficient learning and computation of linear correlated equilibrium in general convex games. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 542–553, 2025.arxiv.org/abs/2412.20291
  22. [29]Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde, Ratip Emin Berker, Gabriele Farina, Vincent Conitzer, and Tuomas Sandholm. Learning and computation of φ-equilibria at the frontier of tractability. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 1105–1105, 2025.
  23. [30]Yang Cai, Constantinos Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. On tractable Φ-equilibria in non-concave games. Advances in Neural Information Processing Systems, 37:140366–140404, 2024.arxiv.org/abs/2403.08171
  24. [31]Anastasios N. Angelopoulos, Michael I. Jordan, and Ryan J. Tibshirani. Gradient equilibrium in online learning: Theory and applications. Journal of Machine Learning Research, 26(305):1–68, 2025.arxiv.org/abs/2501.08330
  25. [32]Jean Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273–299, 1965.DOI
  26. [33]Rémi Gribonval and Mila Nikolova. A characterization of proximity operators. Journal of Mathematical Imaging and Vision, 62(6):773–789, 2020.arxiv.org/abs/1807.04014
  27. [35]H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research, 18(90):1–50, 2017.arxiv.org/abs/1403.3465
  28. [36]Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 2010.
  29. [37]Huang Fang, Nicholas JA Harvey, Victor S Portella, and Michael P Friedlander. Online mirror descent and dual averaging: keeping pace in the dynamic case. Journal of Machine Learning Research, 23(121):1–38, 2022.
  30. [38]Robert J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67–96, 1974. doi: 10.1016/0304-4068(74)90037-8.DOI
  31. [39]Barnabé Monnot and Georgios Piliouras. Limits and limitations of no-regret learning in games. The Knowledge Engineering Review, 32:e21, 2017. doi: 10.1017/S0269888917000133.DOI
  32. [40]Georgios Piliouras, Mark Rowland, Shayegan Omidshafiei, Romuald Elie, Daniel Hennes, Jerome Connor, and Karl Tuyls. Evolutionary dynamics and Φ-regret minimization in games. Journal of Artificial Intelligence Research, 74:1125–1158, 2022b.DOI
  33. [41]David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):1–8, 1956.DOI
  34. [42]Jacob Abernethy, Peter L Bartlett, and Elad Hazan. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory, 2011.
  35. [43]Brian W. Lee, Nika Haghtalab, Michael I. Jordan, and Ryan J. Tibshirani. Blackwell approachability and gradient equilibrium are equivalent. In Proceedings of Thirty Ninth Conference on Learning Theory, 2026.

Paper details

vlnc:W_jug9kw4z

published ·

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

Not recorded for this paper · View statement →

Looking for related papers…
Contents