Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence

By Alina Ene, Huy L. Nguyen. 2020

18 citations recorded by the source corpus.

We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms automatically adapt to unknown problem parameters such as the smoothness and the norm of the operator, and the variance of the stochastic evaluation oracle. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates in the non-smooth, smooth, and stochastic settings. The convergence guarantees of our algorithms improve over existing adaptive methods and match the optimal non-adaptive algorithms. Additionally, prior works require that the optimization domain is bounded. In this work, we remove this restriction and give algorithms for unbounded domains that are adaptive and universal. Our general proof techniques can be used for many variants of the algorithm using one or two operator evaluations per iteration. The classical methods based on the ExtraGradient/MirrorProx algorithm require two operator evaluations per iteration, which is the dominant factor in the running time in many settings.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Gauthier Gidel
6. Martin Jaggi
7. Francis R. Bach
8. Robert Mansel Gower

In Computational Mechanics

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Gauthier Gidel
6. Sebastian U. Stich
7. Francis R. Bach
8. Martin Takác

In Management Science and Operations Research

1. Simon Lacoste-Julien
2. Nicolas Loizou
3. Antonio Orvieto
4. Peter Richtárik

In Optimization & Training

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Peter Richtárik
4. Antonio Orvieto
5. Gauthier Gidel
6. Sebastian U. Stich
7. Martin Jaggi
8. Francis R. Bach

Citations in the corpus

• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “Unfortunately, this is a common problem of all AdaGrad variants: with the exception of [33] (which works in a slightly different scenario), no rate can be provided in the stochastic setting without the bounded iterates/gradients [12] assumption — even after assuming strong convexity.”