Metraipolis › archive › dc_fd43600d5c8e
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader — arXiv:2609.09466
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.09466
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T07:54:20.766Z
- SHA-256 of the archived text
40d5342251129581774b474b6a362715bb56ec990c00d2c2776df56b75401475- Stable URL of this page
https://metraipolis.com/documento/dc_fd43600d5c8e
How to cite
Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader — arXiv:2609.09466 — arXiv (en), https://arxiv.org/abs/2609.09466 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd43600d5c8e (Metraipolis archive dc_fd43600d5c8e, sha256 40d5342251129581774b474b6a362715bb56ec990c00d2c2776df56b75401475)
BibTeX
@misc{dcfd43600d5c8e,
title = {Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader — arXiv:2609.09466},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.09466},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd43600d5c8e; sha256 40d5342251129581774b474b6a362715bb56ec990c00d2c2776df56b75401475},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.09466. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-10 in cs.GT). Categorie arXiv: Machine Learning (cs.LG) ; Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.09466 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T07:30:50.758Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).