Stochastic Extragradient: General Analysis and Improved Rates

Abstract

The Stochastic Extragradient (SEG) method is one of the most popular algorithms for solving min-max optimization and variational inequalities problems (VIP) appearing in various machine learning tasks. However, several important questions regarding the convergence properties of SEG are still open, including the sampling of stochastic gradients, mini-batching, convergence guarantees for the monotone finite-sum variational inequalities with possibly non-monotone terms, and others. To address these questions, in this paper, we develop a novel theoretical framework that allows us to analyze several variants of SEG in a unified manner. Besides standard setups, like Same-Sample SEG under Lipschitzness and monotonicity or Independent-Samples SEG under uniformly bounded variance, our approach allows us to analyze variants of SEG that were never explicitly considered in the literature before. Notably, we analyze SEG with arbitrary sampling which includes importance sampling and various mini-batching strategies as special cases. Our rates for the new variants of SEG outperform the current state-of-the-art convergence guarantees and rely on less restrictive assumptions.

AISTATS 2022. 37 pages, 3 figures, 2 tables. Changes in v2: some minor typos were fixed, several places were clarified. Changes in v3: few typos were fixed, inaccuracies in Appendix B were corrected. Code: https://github.com/hugobb/Stochastic-Extragradient

References in corpus (8)

• FeUdal Networks for Hierarchical Reinforcement Learning
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• Minimax Estimation of Conditional Moment Models
• Stochastic Hamiltonian Gradient Methods for Smooth Games
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

Cited by in corpus (1)

• About some works of Boris Polyak on convergence of gradient methods and their development