Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
arXiv:2208.13592 · doi:10.4171/MAG/112
Abstract
This paper is a survey of methods for solving smooth (strongly) monotone stochastic variational inequalities. To begin with, we give the deterministic foundation from which the stochastic methods eventually evolved. Then we review methods for the general stochastic formulation, and look at the finite sum setup. The last parts of the paper are devoted to various recent (not necessarily stochastic) advances in algorithms for variational inequalities.
arXiv comment12 pages
References in corpus (42)
- Adam: A Method for Stochastic Optimization
- On the difficulty of training Recurrent Neural Networks
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- A Universal Catalyst for First-Order Optimization
- A Variational Inequality Perspective on Generative Adversarial Networks
- Convex Sparse Matrix Factorizations
- Reducing Noise in GAN Training with Variance Reduced Extragradient
- A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
- Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
- Linear Lower Bounds and Conditioning of Differentiable Games
- Accelerating Smooth Games by Manipulating Spectral Shapes
- Efficiently Solving MDPs with Stochastic Mirror Descent
- Stochastic Variance Reduction for Variational Inequality Methods
- Revisiting Stochastic Extragradient
- Solving smooth min-min and min-max problems by mixed oracle algorithms
- Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
- Optimal Algorithms for Decentralized Stochastic Variational Inequalities
- Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling
- Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods
- Adaptive extra-gradient methods for min-max optimization and games
- Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization
- Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
- Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise
- A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
- Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods
- Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity
- Optimal and Adaptive Monteiro-Svaiter Acceleration
- RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
- Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization
- The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
- On Accelerated Methods for Saddle-Point Problems with Composite Structure
- Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
- Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
- The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
- Greedy and Random Broyden's Methods with Explicit Superlinear Convergence Rates in Nonlinear Equations
- On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
- Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equations
- On Scaled Methods for Saddle Point Problems
- Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox
- Robust Accelerated Primal-Dual Methods for Computing Saddle Points
- Coordinate Linear Variance Reduction for Generalized Linear Programming
- Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization