提出新型后悔值，让梯度下降更优的原理更清晰。
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
- 用近端算子定义新后悔值，介于传统后悔与交换后悔之间。
- 在线梯度下降可实现最优 $O(\sqrt{T})$ 近端后悔，无需修改。
- 适用于分析梯度类算法在博弈中的收敛性，适合研究在线学习者。
学习与均衡计算是博弈论、计算理论和人工智能的核心问题。本文引入近端后悔（proximal regret），一种基于近端算子的新后悔概念，其严格介于外部后悔与交换后悔之间。当每个参与者采用无近端后悔算法时，行为经验分布收敛至近端相关均衡（PCE），这是粗相关均衡的精化。该框架统一了在线学习与博弈论中的若干新兴概念（如梯度均衡、半粗相关均衡），并引入新概念。主要结果表明，经典在线梯度下降（GD）算法在近端后悔上达到最优 $O(\sqrt{T})$ 界，说明无需修改即可最小化强于外部后悔的后悔度。这为梯度下降在在线学习与博弈中表现优异提供了新解释。进一步分析扩展至Bregman设定下的镜面下降及乐观梯度下降，在光滑凸博弈中实现更快收敛。
原文摘要 · Abstract (English)
Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new notion of regret based on proximal operators that lies strictly between external and swap regret. When every player employs a no-proximal-regret algorithm in a general convex game, the empirical distribution of play converges to proximal correlated equilibria (PCE), a refinement of coarse correlated equilibria. Our framework unifies several emerging notions in online learning and game theory-such as gradient equilibrium and semicoarse correlated equilibrium-and introduces new ones. Our main result shows that the classic Online Gradient Descent (GD) algorithm achieves an optimal $O(\sqrt{T})$ bound on proximal regret, revealing that GD, without modification, minimizes a stronger regret notion than external regret. This provides a new explanation for the empirically superior performance of gradient descent in online learning and games. We further extend our analysis to Mirror Descent in the Bregman setting and to Optimistic Gradient Descent, which yields faster convergence in smooth convex games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。