Tight last-iterate convergence rates for no-regret learning in multi-player games

Abstract

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of $O(1/\sqrt{T})$ with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos & Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the $O(1/\sqrt{T})$ rate is tight for all $p$-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.

arXiv commentTo appear at NeurIPS 2020. 41 pages

References in corpus (19)

• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Optimization, Learning, and Games with Predictable Sequences
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• No-regret Dynamics and Fictitious Play
• On accuracy of approximation of the spectral radius by the Gelfand formula
• Last-iterate convergence rates for min-max optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Accelerating Smooth Games by Manipulating Spectral Shapes
• On the Iteration Complexity of Oblivious First-Order Optimization Algorithms
• A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Negative Momentum for Improved Game Dynamics
• Revisiting Stochastic Extragradient
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Potential-Function Proofs for First-Order Methods
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games
• Learning in games with continuous action sets and unknown payoff functions

Cited by in corpus (1)

• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity