Linear Last-iterate Convergence in Constrained Saddle-point Optimization
arXiv:2006.09517
Abstract
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable last-iterate convergence. However, their behaviors for simple bilinear games over the probability simplex are still not fully understood - previous analysis lacks explicit convergence rates, only applies to an exponentially small learning rate, or requires additional assumptions such as the uniqueness of the optimal solution. In this work, we significantly expand the understanding of last-iterate convergence for OGDA and OMWU in the constrained setting. Specifically, for OMWU in bilinear games over the simplex, we show that when the equilibrium is unique, linear last-iterate convergence is achieved with a learning rate whose value is set to a universal constant, improving the result of (Daskalakis & Panageas, 2019b) under the same assumption. We then significantly extend the results to more general objectives and feasible sets for the projected OGDA algorithm, by introducing a sufficient condition under which OGDA exhibits concrete last-iterate convergence rates with a constant learning rate whose value only depends on the smoothness of the objective function. We show that bilinear games over any polytope satisfy this condition and OGDA converges exponentially fast even without the unique equilibrium assumption. Our condition also holds for strongly-convex-strongly-concave functions, recovering the result of (Hsieh et al., 2019). Finally, we provide experimental results to further support our theory.
References in corpus (9)
- Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
- 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
- Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
- Fast Convergence of Regularized Learning in Games
- Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
- Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
- Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games