Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling

Abstract

Owing to their stability and convergence speed, extragradient methods have become a staple for solving large-scale saddle-point problems in machine learning. The basic premise of these algorithms is the use of an extrapolation step before performing an update; thanks to this exploration step, extra-gradient methods overcome many of the non-convergence issues that plague gradient descent/ascent schemes. On the other hand, as we show in this paper, running vanilla extragradient with stochastic gradients may jeopardize its convergence, even in simple bilinear models. To overcome this failure, we investigate a double stepsize extragradient algorithm where the exploration step evolves at a more aggressive time-scale compared to the update step. We show that this modification allows the method to converge even with stochastic gradients, and we derive sharp convergence rates under an error bound condition.

In Advances in Neural Information Processing Systems 33 (NeurIPS 2020); 29 pages, 5 figures

References in corpus (11)

• Which Training Methods for GANs do actually Converge?
• 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
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Accelerating Smooth Games by Manipulating Spectral Shapes
• Stochastic Hamiltonian Gradient Methods for Smooth Games
• Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games
• Extragradient with player sampling for faster Nash equilibrium finding

Cited by in corpus (14)

• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Optimality and Stability in Non-Convex Smooth Games
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Stochastic Extragradient: General Analysis and Improved Rates
• About some works of Boris Polyak on convergence of gradient methods and their development
• Geometry-Aware Universal Mirror-Prox
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent