Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey

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.

12 pages

References in corpus (21)

• On the difficulty of training Recurrent Neural Networks
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Convex Sparse Matrix Factorizations
• A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
• Efficiently Solving MDPs with Stochastic Mirror Descent
• Adaptive extra-gradient methods for min-max optimization and games
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization
• 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
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox
• Greedy and Random Broyden's Methods with Explicit Superlinear Convergence Rates in Nonlinear Equations
• On Scaled Methods for Saddle Point Problems
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization

Cited by in corpus (4)

• Randomized gradient-free methods in convex optimization
• Gradient-free algorithm for saddle point problems under overparametrization
• About some works of Boris Polyak on convergence of gradient methods and their development
• Extragradient Sliding for Composite Non-Monotone Variational Inequalities