On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games

• URL: http://arxiv.org/abs/2503.02825v1
• Date: Tue, 04 Mar 2025 17:49:24 GMT
• Title: On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
• Authors: Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, Weiqiang Zheng,
• Abstract summary: Non-ergodic convergence of learning dynamics in games is widely studied because of its importance in both theory and practice.<n>Recent work showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update, can exhibit arbitrarily slow last-iterate convergence.<n>We show that OMWU achieves an $O(T-1/6)$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games.
• Score: 71.73971094342349
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update (OMWU), can exhibit arbitrarily slow last-iterate convergence even in simple $2 \times 2$ matrix games, despite many of these dynamics being known to converge asymptotically in the last iterate. It remains unclear, however, whether these algorithms achieve fast non-ergodic convergence under weaker criteria, such as best-iterate convergence. We show that for $2\times 2$ matrix games, OMWU achieves an $O(T^{-1/6})$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games. Furthermore, we establish a lower bound showing that OMWU does not achieve any polynomial random-iterate convergence rate, measured by the expected duality gaps across all iterates. This result challenges the conventional wisdom that random-iterate convergence is essentially equivalent to best-iterate convergence, with the former often used as a proxy for establishing the latter. Our analysis uncovers a new connection to dynamic regret and presents a novel two-phase approach to best-iterate convergence, which could be of independent interest.

Related papers

• Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games [31.989723099872638]
  Last-iterate behaviors of learning algorithms in two-player zero-sum games have been extensively studied. Most existing results establish these properties under the assumption that the game is time-independent. In this paper, we investigate the last-iterate behaviors of optimistic and extra-gradient methods in the constrained periodic games.
  arXiv  Detail & Related papers  (2024-06-15T11:50:36Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [72.43065138581589]
  We study the last-iterate convergence properties of various popular variants of RM$+$. We show numerically that several practical variants such as simultaneous RM$+$, alternating RM$+$, and predictive RM$+$, all lack last-iterate convergence guarantees. We then prove that recent variants of these algorithms based on a smoothing technique do enjoy last-iterate convergence.
  arXiv  Detail & Related papers  (2023-11-01T17:34:58Z)
• The Power of Regularization in Solving Extensive-Form Games [22.557806157585834]
  We propose a series of new algorithms based on regularizing the payoff functions of the game. In particular, we first show that dilated optimistic mirror descent (DOMD) can achieve a fast $tilde O(T)$ last-iterate convergence. We also show that Reg-CFR, with a variant of optimistic mirror descent algorithm as regret-minimizer, can achieve $O(T1/4)$ best-iterate, and $O(T3/4)$ average-iterate convergence rate.
  arXiv  Detail & Related papers  (2022-06-19T22:10:38Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  We significantly expand the understanding of last-rate uniqueness for Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) We show that when the equilibrium is unique, linear lastiterate convergence is achieved with a learning rate whose value is set to a universal constant. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption.
  arXiv  Detail & Related papers  (2020-06-16T20:53:04Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  We characterize the finite-time last-iterate convergence rate for joint OGD learning on $lambda$-cocoercive games. We show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart.
  arXiv  Detail & Related papers  (2020-02-23T01:46:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.