Smooth monotone stochastic variational inequalities and saddle point problems: A survey

Aleksandr Beznosikov; Boris Polyak; Eduard Gorbunov; Dmitry Kovalev; Alexander Gasnikov

doi:10.4171/mag/112

This paper is a survey of methods for solving smooth, (strongly) monotone stochastic variational inequalities. To begin with, we present 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.

1 Introduction

In its long, more than half-century history of study (going back to the classical article [⁠113⁠ G. Stampacchia, Formes bilinéaires coercitives sur les ensembles convexes. C. R. Acad. Sci. Paris 258, 4413–4416 (1964) ]), variational inequalities have become one of the most popular and universal optimization formulations. Variational inequalities are used in various areas of applied mathematics. Here we can highlight both classical examples from game theory, economics, operator theory, convex analysis [⁠6⁠ K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming. Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford (1958) , ⁠19⁠ F. E. Browder, Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. U.S.A. 56, 1080–1086 (1966) , ⁠106⁠ R. T. Rockafellar, Convex functions, monotone operators and variational inequalities. In Theory and Applications of Monotone Operators (Proc. NATO Advanced Study Inst., Venice, 1968), Edizioni “Oderisi”, Gubbio, 35–65 (1969) , ⁠110⁠ M. Sibony, Méthodes itératives pour les équations et inéquations aux dérivées partielles non linéaires de type monotone. Calcolo 7, 65–183 (1970) , ⁠113⁠ G. Stampacchia, Formes bilinéaires coercitives sur les ensembles convexes. C. R. Acad. Sci. Paris 258, 4413–4416 (1964) ], as well as newer and even more recent applications in optimization and machine learning: non-smooth optimization [⁠93⁠ Y. Nesterov, Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005) ], unsupervised learning [⁠9⁠ F. Bach, J. Mairal and J. Ponce, Convex sparse matrix factorizations, preprint, arXiv:0812.1869 (2008) , ⁠36⁠ E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015–1046 (2010) , ⁠22⁠ A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40, 120–145 (2011) ], robust/adversarial optimization [⁠11⁠ A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust optimization. Princeton Ser. Appl. Math., Princeton University Press, Princeton (2009) ], GANs [⁠47⁠ I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville and Y. Bengio, Generative adversarial networks. Commun. ACM 63, 139–144 (2020) ] and reinforcement learning [⁠100⁠ S. Omidshafiei, J. Pazis, C. Amato, J. P. How and J. Vian, Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 70, 2681–2690 (2017) , ⁠57⁠ Y. Jin and A. Sidford, Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 119, 4890–4900 (2020) ]. Modern times present new challenges to the community. The increase in scale of problems and the need to speed up solution processes have sparked a huge interest in stochastic formulations of applied tasks, including variational inequalities. This paper surveys stochastic methods for solving variational inequalities.

Structure of the paper

In Section ⁠2⁠, we give a formal statement of the variational inequality problem, basic examples, and main assumptions. Section ⁠3⁠ deals with deterministic methods, from which stochastic methods have evolved. Section ⁠4⁠ covers a variety of stochastic methods. Section ⁠5⁠ is devoted to the recent advances in (not necessarily stochastic) variational inequalities and saddle point problems.

2 Problem: Setting and assumptions

Notation. We use $⟨ x, y ⟩ : = \sum_{i = 1}^{d} x_{i} y_{i}$ to denote the standard inner product of vectors $x, y \in R^{d}$ , where $x_{i}$ is the $i$ -th component of $x$ in the standard basis of $R^{d}$ . It induces the $ℓ_{2}$ -norm in $R^{d}$ by $∥ x ∥_{2} : = ⟨ x, x ⟩$ . We denote the $ℓ_{p}$ -norm by $∥ x ∥_{p} : = (\sum_{i = 1}^{d} ∣ x_{i} ∣^{p})^{1/ p}$ for $p \in [1, \infty)$ , and $∥ x ∥_{\infty} : = max_{1 \leq i \leq d} ∣ x_{i} ∣$ for $p = \infty$ . The dual norm $∥ \cdot ∥_{*}$ corresponding to the norm $∥ \cdot ∥$ is defined by $∥ y ∥_{*} : = max {⟨ x, y ⟩ ∣ ∥ x ∥ \leq 1}$ . The symbol $E [\cdot]$ stands for the total mathematical expectation. Finally, we need to introduce the symbols $O$ and $Ω$ to enclose numerical constants that do not depend on any parameters of the problem, and the symbols $\tilde{O}$ and $\tilde{Ω}$ to enclose numerical constants and logarithmic factors.

We study variational inequalities (VI) of the form

find z^{*} \in Z such that ⟨ F (z^{*}), z - z^{*} ⟩ \geq 0 \forall z \in Z,

where $F : Z \to R^{d}$ is an operator and $Z \subseteq R^{d}$ is a convex set.

To emphasize the extensiveness of formulation (⁠1⁠), we give a few examples of variational inequalities arising in applied sciences.

Example 1 (Minimization). Consider the minimization problem

z \in Z min f (z) .

Let $F (z) : = \nabla f (z)$ . Then, if $f$ is convex, one can prove that $z^{*} \in Z$ is a solution of (⁠1⁠) if and only if $z^{*} \in Z$ is a solution of problem (⁠2⁠).

Example 2 (Saddle point problem). Consider the saddle point problem (SPP)

x \in X min y \in Y max g (x, y) .

Suppose that $F (z) : = F (x, y) = [\nabla_{x} g (x, y), - \nabla_{y} g (x, y)]$ and $Z = X \times Y$ with $X \subseteq R^{d_{x}}$ , $Y \subseteq R^{d_{y}}$ . Then, if $g$ is convex-concave, one can prove that $z^{*} \in Z$ is a solution of problem (⁠1⁠) if and only if $z^{*} \in Z$ is a solution of problem (⁠3⁠).

The study of saddle point problems is often associated with variational inequalities.

Example 3 (Fixed point problem). Consider the fixed point problem

find z^{*} \in R^{d} such that T (z^{*}) = z^{*},

where $T : R^{d} \to R^{d}$ is an operator. If we set $F (z) = z - T (z)$ , then one can prove that $z^{*} \in Z = R^{d}$ is a solution of problem (⁠1⁠) if and only if $F (z^{*}) = 0$ , i.e., $z^{*} \in R^{d}$ is a solution of problem (⁠4⁠).

For the operator $F$ from (⁠1⁠) we assume the following.

Assumption 1 (Lipschitzness). The operator $F$ is $L$ -Lipschitz continuous, i.e., for all $u, v \in Z$ , we have $∥ F (u) - F (v) ∥_{*} \leq L ∥ u - v ∥$ .

In the context of problems (⁠2⁠) and (⁠3⁠), $L$ -Lipschitzness of the operator means that the functions $f (z)$ and $g (x, y)$ are $L$ -smooth.

Assumption 2 (Strong monotonicity). The operator $F$ is $μ$ -strongly monotone, i.e., for all $u, v \in Z$ , we have $⟨ F (u) - F (v), u - v ⟩ \geq μ ∥ u - v ∥_{2}^{2}$ . If $μ = 0$ , then the operator $F$ is monotone.

In the context of problems (⁠2⁠) and (⁠3⁠), strong monotonicity of $F$ means strong convexity of $f (z)$ and strong convexity-strong concavity of $g (x, y)$ . In this paper we first focus on the strongly monotone and monotone cases. But there are also various assumptions relaxing monotonicity and strong monotonicity (e.g., see [⁠55⁠ Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Adv. Neural Inf. Process. Syst. 33, 16223–16234 (2020) ] and references therein).

We note that Assumptions ⁠1⁠ and ⁠2⁠ are sufficient for the existence of a solution to problem (⁠1⁠) (see, e.g., [⁠37⁠ F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research, Springer, New York (2003) ]).

Since we work on the set $Z$ , it is useful to introduce the Euclidean projection onto $Z$ ,

P_{Z} (z) = ar g v \in Z min ∥ z - v ∥_{2} .

To characterize the convergence of the methods for monotone variational inequalities we introduce the gap function,

Gap_{VI} (z) : = u \in Z sup [⟨ F (u), z - u ⟩] .

Such a gap function, regarded as a convergence criterion, is more suitable for the following variational inequality problem:

find z^{*} \in Z such that ⟨ F (z), z^{*} - z ⟩ \leq 0 for z \in Z .

Such a solution is also called weak or Minty (whereas the solution of (⁠1⁠) is called strong or Stampacchia). However, in view of Assumption ⁠1⁠, $F$ is single-valued and continuous on $Z$ , meaning that actually the two indicated formulations of the variational inequality problem are equivalent [⁠37⁠ F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research, Springer, New York (2003) ].

For the minimization problem (⁠2⁠), the functional distance to the solution, i.e., the difference $f (z) - f (z^{*})$ , can be used instead of (⁠5⁠). For saddle point problems (⁠3⁠), a slightly different gap function is used, namely,

Gap_{SPP} (z) : = gap (x, y) = y^{'} \in Y max f (x, y^{'}) - x^{'} \in X min f (x^{'}, y) .

For both functions (⁠5⁠) and (⁠6⁠) it is crucial that the feasible set is bounded (in fact it is not necessary to take the whole set $Z$ , which can be unbounded – it suffices to take a bounded convex subset $C$ which contains some solution, see [⁠95⁠ Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109, 319–344 (2007) ]). Therefore it is necessary to define a distance on the set $Z$ . Since this survey covers methods not only in the Euclidean setup, let us introduce a more general notion of distance.

Definition 1 (Bregman divergence). Let $ν (z)$ be a function that is $1$ -strongly convex w.r.t. the norm $∥ \cdot ∥$ and differentiable on $Z$ . Then for any two points $z, z^{'} \in Z$ the Bregman divergence (or Bregman distance) $V (z, z^{'})$ associated with $ν (z)$ is defined as

V (z, z^{'}) : = ν (z^{'}) - ν (z) - ⟨ \nabla ν (z), z^{'} - z ⟩ .

We denote the Bregman diameter of the set $Z$ w.r.t. the divergence $V (z, z^{'})$ as $D_{Z, V} : = max {2 V (z, z^{'}) ∣ z, z^{'} \in Z}$ . In the Euclidean case, we simply write $D_{Z}$ instead of $D_{Z, V}$ . Using the definition of $V$ , we introduce the so-called proximal operator as follows:

prox_{x} (y) = ar g z \in Z min {⟨ y, z ⟩ + V (z, x)} .

3 Deterministic foundation: Extragradient and other methods

The first and the simplest method for solving the variational inequality (⁠1⁠) is the iterative scheme (also known as the Gradient method)

z^{k + 1} = P_{Z} (z^{k} - γ F (z^{k})),

where $γ > 0$ is a step size. Note that using the proximal operator associated with the Euclidean Bregman divergence this method can be rewritten in the form

z^{k + 1} = prox_{z^{k}} (γ F (z^{k})) .

The basic result asserts the convergence of the method to the unique solution of (⁠1⁠) for strongly monotones and $L$ -Lipschitz operators $F$ ; it was obtained in the papers [⁠19⁠ F. E. Browder, Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. U.S.A. 56, 1080–1086 (1966) , ⁠106⁠ R. T. Rockafellar, Convex functions, monotone operators and variational inequalities. In Theory and Applications of Monotone Operators (Proc. NATO Advanced Study Inst., Venice, 1968), Edizioni “Oderisi”, Gubbio, 35–65 (1969) , ⁠110⁠ M. Sibony, Méthodes itératives pour les équations et inéquations aux dérivées partielles non linéaires de type monotone. Calcolo 7, 65–183 (1970) ].

Theorem 1.

If Assumptions ⁠1⁠ and ⁠2⁠ hold and $0 < γ < 2 μ / L^{2}$ , then after $k$ iterations method (⁠7⁠) converges to $z^{*}$ with a linear rate:

∥ z^{k} - z^{*} ∥_{2}^{2} = O (R_{0}^{2} q^{k}), with q = (1 - 2 γ μ + γ^{2} L^{2})

and $R_{0}$ denotes (here and everywhere in the sequel) the norm $∥ z^{0} - z^{*} ∥_{2}$ . For $γ = μ / L^{2}$ , we have $q = (1 - 1/ κ^{2})$ , $κ = L / μ$ , thus the upper bound on the number of iterations needed to achieve the $ε$ -solution (i.e., $∥ z^{k} - z^{*} ∥_{2}^{2} \leq ε$ ) is $O (κ^{2} lo g (R_{0}^{2} / ε))$ .

Various extensions of this statement (for the case when $F$ is not Lipschitz, but with linear growth bounds, or when the values of $F$ are corrupted by noise) can be found in [⁠10⁠ A. Bakushinskii and B. Polyak, On the solution of variational inequalities. Sov. Math. Dokl. 15, 1705–1710 (1974) , Theorem 1].

When $F$ is a potential operator (see Example ⁠1⁠) method (⁠7⁠) coincides with the gradient projection algorithm. It converges for strongly monotone $F$ . Moreover, the bounds for the admissible step size are less restrictive ( $0 < γ < 2/ L$ ) and the relevant complexity estimates are better ( $O (κ lo g (R_{0}^{2} / ε))$ ) than in Theorem ⁠1⁠; see [⁠104⁠ B. T. Polyak, Introduction to optimization. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York (1987) , Theorem 2 in Section 1.4.2].

However, in the general monotone, but not strongly monotone case (for instance, for the convex-concave SPP, Example ⁠2⁠) convergence fails. The original statements on the convergence of Uzawa’s method (a version of (⁠7⁠)) for saddle point problems [⁠6⁠ K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming. Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford (1958) ] were wrong; there are numerous well-known examples where method (⁠7⁠) for $F$ corresponding to a bilinear SPP diverges, see, e.g., [⁠104⁠ B. T. Polyak, Introduction to optimization. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York (1987) , Figure 39].

There have been many other attempts to recover the convergence of gradient-like methods, not for VIs, but for saddle point problems. One of them is based on the transition to modified Lagrangians when $g (x, y)$ is a Lagrange function, see [⁠45⁠ E. G. Gol’šteĭn, Convergence of the gradient method for finding the saddle points of modified Lagrangian functions. Èkonom. i Mat. Metody 13, 322–329 (1977) , ⁠104⁠ B. T. Polyak, Introduction to optimization. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York (1987) ]. However, we focus on the general VI case. A possible approach is based on the idea of regularization. Instead of the monotone variational inequality (⁠1⁠) one can deal with a regularized inequality, in which the monotone operator $F$ is replaced by strongly monotone one $F + ε_{k} T$ , where $T (z)$ is a strongly monotone operator and $ε_{k} > 0$ is a regularization parameter. If we denote by $z^{k}$ the solution of the regularized VI, then one can prove that $z^{k}$ converges to $z^{*}$ as $ε_{k} \to 0$ (see [⁠10⁠ A. Bakushinskii and B. Polyak, On the solution of variational inequalities. Sov. Math. Dokl. 15, 1705–1710 (1974) ]). However, usually the solution $z^{k}$ is not easily available. To address this problem, an iterative regularization technique is proposed in [⁠10⁠ A. Bakushinskii and B. Polyak, On the solution of variational inequalities. Sov. Math. Dokl. 15, 1705–1710 (1974) ], where one step of the basic method (⁠7⁠) is applied for the regularized problem. Step sizes and regularization parameters can be adjusted to guarantee convergence.

Another technique is based on the Proximal Point Method proposed independently by B. Martinet in [⁠84⁠ B. Martinet, Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4, 154–158 (1970) ] and by T. Rockafellar in [⁠107⁠ R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976) ]. At each iteration this methods requires the solution of the VI with the operator $F + c I$ , where $c > 0$ and $I$ is the identity operator. This is an implicit method (similar to the regularization method), however there exist numerous implementable versions of Proximal Point. For instance, some methods discussed below can be considered from this point of view.

The breakthrough in methods for solving (non-strongly) monotone variational inequalities was made by Galina Korpelevich [⁠64⁠ G. M. Korpelevič, An extragradient method for finding saddle points and for other problems. Èkonom. i Mat. Metody 12, 747–756 (1976) ]. She exploited the idea of extrapolation for the gradient method. How this works can be explained for the simplest example of a two-dimensional min-max problem with $g (x, y) = x y$ and $Z = R^{2}$ . It has the unique saddle point $z = 0$ , and in any point $z^{k}$ the direction $F (z^{k})$ is orthogonal to $z^{k}$ ; thus, the iteration (⁠7⁠) increases the distance to the saddle point. However, if we perform the step (⁠7⁠) and get the extrapolated point $z^{k + 1/2}$ , the direction $- F (z^{k + 1/2})$ is attracted to the saddle point. Thus, the Extragradient method for solving (⁠1⁠) reads

z^{k + 1/2} = P_{Z} (z^{k} - γ F (z^{k})),

z^{k + 1} = P_{Z} (z^{k} - γ F (z^{k + 1/2})) .

Theorem 2.

Let $F$ satisfy Assumptions ⁠1⁠ and ⁠2⁠ (with $μ = 0$ ) and let $0 < γ < 1/ L$ . Then the sequence of iterates $z^{k}$ generated by the Extragradient method converges to $z^{⋆}$ .

For the particular cases of the zero-sum matrix game or the general bilinear problem with $g (x, y) = y^{⊤} A x - b^{⊤} x + c^{⊤} y$ , the method converges linearly, provided that the optimal solution is unique (see [⁠64⁠ G. M. Korpelevič, An extragradient method for finding saddle points and for other problems. Èkonom. i Mat. Metody 12, 747–756 (1976) , Theorem 3]). In this case, the rate of convergence is equal to $O (κ lo g (R_{0}^{2} / ε))$ with $κ = λ_{max} (A A^{⊤}) / λ_{min} (A A^{⊤})$ . More general upper bounds for the Extragradient method can be found in [⁠119⁠ P. Tseng, On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60, 237–252 (1995) ] and in the recent paper [⁠87⁠ A. Mokhtari, A. Ozdaglar and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1497–1507 (2020) ]. In particular, for the strongly monotone case the estimate $O (κ lo g (R_{0}^{2} / ε))$ with $κ = L / μ$ holds true (compare with the much worse bound $O (κ^{2} lo g (R_{0}^{2} / ε))$ for the Gradient method). An adaptive version of the Extragradient method (no knowledge of $L$ is required) is proposed in [⁠61⁠ E. N. Khobotov, Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. U.S.S.R. Comput. Math. Math. Phys. 27, 120–127 (1987) ].

Another version of the Extragradient method for finding saddle points is provided in [⁠65⁠ G. M. Korpelevich, Extrapolation gradient methods and their relation to modified Lagrange functions. Èkonom. i Mat. Metody 19, 694–703 (1983) ]. Considering the setup of Example ⁠2⁠, we can exploit just one extrapolating step for the variables $y$ :

y^{k + 1/2} = P_{Y} (y^{k} + γ \nabla_{y} g (x^{k}, y^{k})),

x^{k + 1} = P_{X} (x^{k} - γ \nabla_{x} g (x^{k}, y^{k + 1/2}),

y^{k + 1} = y^{k} + q (y^{k + 1/2} - y^{k}),

with $0 < γ < 1/ (2 L)$ and $0 < q < 1$ . This method converges to the solution and if $g (x, y)$ is linear in $y$ , then the rate of convergence is linear. If we set $q = 1$ in method (⁠8⁠), then $y^{k + 1} = y^{k + 1/2}$ and we get the so-called Alternating Gradient Method (alternating descent-ascent). In [⁠123⁠ G. Zhang, Y. Wang, L. Lessard and R. B. Grosse, Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7659–7679 (2022) ], it was proved that this method has local linear convergence with complexity $O (κ lo g (R_{0}^{2} / ε))$ , where $κ = L / μ$ .

L. Popov [⁠105⁠ L. D. Popov, A modification of the Arrow–Hurwicz method for search of saddle points. Math. Notes 28, 845–848 (1981) ] proposed a version of extrapolation scheme (sometimes this type of scheme is referred to as optimistic or single-call):

z^{k + 1/2} = P_{Z} (z^{k} - γ F (z^{k - 1/2})),

z^{k + 1} = P_{Z} (z^{k} - γ F (z^{k + 1/2})) .

It requires the single calculation of $F$ at each iteration vs two calculations in the Extragradient method. As shown in [⁠105⁠ L. D. Popov, A modification of the Arrow–Hurwicz method for search of saddle points. Math. Notes 28, 845–848 (1981) ], method (⁠9⁠) converges for $0 < γ < 1/ (3 L)$ . Rates of convergence for this method were derived recently in [⁠41⁠ G. Gidel, H. Berard, G. Vignoud, P. Vincent and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, preprint, arXiv:1802.10551 (2018) , ⁠87⁠ A. Mokhtari, A. Ozdaglar and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1497–1507 (2020) ], i.e., $O (κ lo g (R_{0}^{2} / ε))$ with $κ = L / μ$ for the strongly monotone case and $κ = λ_{max} (A A^{⊤}) / λ_{min} (A A^{⊤})$ for the bilinear case. Note that in the general strongly monotone case this estimate is optimal [⁠124⁠ J. Zhang, M. Hong and S. Zhang, On lower iteration complexity bounds for the convex concave saddle point problems. Math. Program. 194, 901–935 (2022) ], but for the bilinear problem the upper bounds available in the literature for both the Extragradient and optimistic methods are not tight [⁠56⁠ A. Ibrahim, W. Azizian, G. Gidel and I. Mitliagkas, Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 4583–4593 (2020) ]. Meanwhile, optimal estimates $O (κ lo g (R_{0}^{2} / ε))$ with $κ = λ_{max} (A A^{⊤}) / λ_{min} (A A^{⊤})$ can be achieved using approaches from [⁠7⁠ W. Azizian, D. Scieur, I. Mitliagkas, S. Lacoste-Julien and G. Gidel, Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1705–1715 (2020) , ⁠4⁠ M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, Accelerated methods for saddle-point problem. Comput. Math. Math. Phys. 60, 1787–1809 (2020) ].

An extension of the above schemes to an arbitrary proximal setup was obtained in the work of A. Nemirovsky [⁠92⁠ A. Nemirovski, Prox-method with rate of convergence O⁢(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2004) ]. He proposed the Mirror-Prox method for VIs, exploiting the Bregman divergence:

z^{k + 1/2} = prox_{z^{k}} (γ F (z^{k})),

z^{k + 1} = prox_{z^{k}} (γ F (z^{k + 1/2})) .

This yields the following rate-of-convergence result.

Theorem 3.

Let $F$ satisfy Assumptions ⁠1⁠ and ⁠2⁠ (with $μ = 0$ ), and let

\overset{z}{^}^{k} = \frac{1}{k} i = 1 \sum k z^{i + 1/2},

where $z^{i + 1/2}$ are generated by algorithm (⁠10⁠) with $γ = 1/ (2 L)$ . Then, after $k$ iterations,

Gap_{VI} (\overset{z}{^}^{k}) = O (\frac{L D _{Z, V}^{2}}{k}) .

Numerous extensions of these original versions of iterative methods for solving variational inequalities were published later. One can highlight Tseng’s Forward-Backward Splitting [⁠120⁠ P. Tseng, A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38, 431–446 (2000) ], Nesterov’s Dual Extrapolation [⁠95⁠ Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109, 319–344 (2007) ], Malitsky and Tam’s Forward-Reflected-Backward [⁠83⁠ Y. Malitsky and M. K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30, 1451–1472 (2020) ]. All methods have convergence guarantees (⁠12⁠). It turns out that this rate is optimal [⁠101⁠ Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. 185, 1–35 (2021) ].

4 Stochastic methods: Different setups and assumptions

In this section, we move from deterministic to stochastic methods, i.e., we consider problem (⁠1⁠) with an operator of the form

F (z) = E_{ξ \sim D} [F_{ξ} (z)],

where $ξ$ is a random variable, $D$ is some (typically unknown) probability distribution and $F_{ξ} : Z \to R^{d}$ is a stochastic operator. In this setup, calculating the value of the full operator $F$ is computationally expensive or even intractable. Therefore, one has to work mainly with stochastic realizations $F_{ξ}$ .

4.1 General case

The stochastic formulation (⁠13⁠) for problem (⁠1⁠) was first considered by the authors of [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ]. They proposed a natural stochastic generalization of the Extragradient method (more precisely, of the Mirror-Prox methods):

z^{k + 1/2} = prox_{z^{k}} (γ F_{ξ^{k}} (z^{k})),

z^{k + 1} = prox_{z^{k}} (γ F_{ξ^{k + 1/2}} (z^{k + 1/2})) .

Here it is important to note that the variables $ξ^{k}$ and $ξ^{k + 1/2}$ are independent and $F_{ξ} (z)$ is an unbiased estimator of $F (z)$ . Moreover, $F_{ξ} (z)$ is assumed to satisfy the following condition.

Assumption 3 (Bounded variance). The unbiased operator $F_{ξ}$ has uniformly bounded variance, i.e., for all $ξ \sim D$ and $u \in Z$ , we have $E ∥ F_{ξ} (u) - F (u) ∥_{*}^{2} \leq σ^{2}$ .

Under this assumption, the following result was established in [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ].

Theorem 4.

Let $F_{ξ}$ satisfy Assumptions ⁠1⁠, ⁠2⁠ (with $μ = 0$ ) and ⁠3⁠, and let $\overset{z}{^}^{k}$ be defined as in (⁠11⁠), where $z^{i + 1/2}$ are generated by algorithm (⁠14⁠) with $γ = min {\frac{1}{3 L}, D_{Z, V} \frac{1}{7 k σ ^{2}}}$ . Then, after $k$ iterations, one can guarantee that

E [Gap_{VI} (\overset{z}{^}^{k})] = O (\frac{L D _{Z, V}^{2}}{k} + D_{Z, V} \frac{σ ^{2}}{k}) .

In [⁠17⁠ A. Beznosikov, V. Samokhin and A. Gasnikov, Distributed saddle-point problems: Lower bounds, optimal and robust algorithms, preprint arXiv:2010.13112 (2020) ], the authors carried out an analysis of algorithm (⁠14⁠) for strongly monotone VIs in the Euclidean case. In particular, under Assumptions ⁠1⁠, ⁠2⁠ and ⁠3⁠ one can guarantee that after $k$ iterations of method (⁠14⁠) one has that (here and below we omit numerical constants in the exponential multiplier)

E ∥ z^{k} - z^{*} ∥_{2}^{2} = \tilde{O} (R_{0}^{2} exp (- \frac{μ k}{L}) + \frac{σ ^{2}}{μ ^{2} k}) .

Also in [⁠17⁠ A. Beznosikov, V. Samokhin and A. Gasnikov, Distributed saddle-point problems: Lower bounds, optimal and robust algorithms, preprint arXiv:2010.13112 (2020) ], the authors obtained lower complexity bounds for solving VIs satisfying Assumptions ⁠1⁠, ⁠2⁠ and ⁠3⁠ with stochastic methods. It turns out that the conclusions of Theorem ⁠4⁠ in the monotone case and estimate (⁠16⁠) are optimal and meet lower bounds up to numerical constants.

Optimistic-like (or single-call) methods were also investigated in the stochastic setting. The work [⁠41⁠ G. Gidel, H. Berard, G. Vignoud, P. Vincent and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, preprint, arXiv:1802.10551 (2018) ] applies the following update scheme:

z^{k + 1/2} = P_{Z} (z^{k} - γ F_{ξ^{k - 1/2}} (z^{k - 1/2})),

z^{k + 1} = P_{Z} (z^{k} - γ F_{ξ^{k + 1/2}} (z^{k + 1/2})) .

For this method, in the monotone Euclidean case, the authors proved an estimate similar to (⁠15⁠). In the strongly monotone case, method (⁠17⁠) was investigated in the paper [⁠54⁠ Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, On the convergence of single-call stochastic extra-gradient methods. Adv. Neural Inf. Process. Syst. 32, 6938–6948 (2019) ], but the estimates obtained there do not meet the lower bounds. The optimal estimates for this scheme were obtained later in [⁠14⁠ A. Beznosikov, A. Gasnikov, K. Zainulina, A. Maslovskiy and D. Pasechnyuk, A unified analysis of variational inequality methods: Variance reduction, sampling, quantization and coordinate descent, preprint, arXiv:2201.12206 (2022) ].

The work [⁠66⁠ G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation. SIAM J. Optim. 32, 2041–2073 (2022) ] deals with a slightly different single-call approach in the non-Euclidean case:

z^{k + 1} = prox_{z^{k}} (γ_{k} F_{ξ^{k}} (z^{k}) + γ_{k} α_{k} [F_{ξ^{k}} (z^{k}) - F_{ξ^{k - 1}} (z^{k - 1})]) .

This update rule is a modification of the Forward-Reflected-Backward approach, namely, here $α_{k}$ is a parameter, while in [⁠83⁠ Y. Malitsky and M. K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30, 1451–1472 (2020) ], $α_{k} \equiv 1$ . The analysis of method (⁠18⁠) gives optimal estimates in both the strongly monotone and monotone cases.

The theoretical results and guarantees discussed above rely in significant manner on the bounded variance assumption (Assumption ⁠3⁠). This assumption is quite restrictive (especially when the domain is unbounded) and does not hold for many popular machine learning problems. Moreover, one can even design a strongly monotone variational inequality on an unbounded domain such that method (⁠14⁠) diverges exponentially fast [⁠26⁠ T. Chavdarova, G. Gidel, F. Fleuret and S. Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. Adv. Neural Inf. Process. Syst. 32, 393–403 (2019) ]. The authors of [⁠55⁠ Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Adv. Neural Inf. Process. Syst. 33, 16223–16234 (2020) , ⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] consider a relaxed form of the bounded variance condition and assume that $E ∥ F_{ξ} (u) - F (u) ∥_{2}^{2} \leq σ^{2} + δ ∥ u - z^{*} ∥_{2}^{2}$ with $δ \geq 0$ in the Euclidean case. Under this condition and Assumptions ⁠1⁠ and ⁠2⁠, it is proved in [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] that after $k$ iterations of algorithm (⁠14⁠) (when $Z = R^{d}$ ) it holds that

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (κ R_{0}^{2} exp (- \frac{k}{κ}) + \frac{σ ^{2}}{μ ^{2} k}),

where $κ = max {\frac{δ}{μ ^{2}}; \frac{L + δ}{μ}}$ . The same assumption on stochastic realizations was considered in [⁠67⁠ G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning. SIAM J. Optim. 32, 1120–1155 (2022) ], where method (⁠18⁠) was used, yielding the estimate

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (R_{0}^{2} exp (- \frac{μ k}{L}) + \frac{σ ^{2} + δ ^{2} D _{Z}^{2}}{μ ^{2} k}) .

Estimates (⁠19⁠) and (⁠20⁠) are competitive: the former is superior in terms of the stochastic term (second term), while the latter is superior in terms of the deterministic term (first term). However, none of these results deals completely with the issue of bounded noise, because the condition considered above is not general. The key to avoiding the bounded variance assumption on $F_{ξ}$ lies in the way how stochasticity is generated in method (⁠14⁠). Method (⁠14⁠) is sometimes called Independent Samples Stochastic Extragradient (I-SEG). To address the bounded variance issue, K. Mishchenko et al. [⁠86⁠ K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020) ] proposed another stochastic modification of the Extragradient algorithm, called Same Sample Stochastic Extragradient (S-SEG):

z^{k + 1/2} = z^{k} - γ F_{ξ^{k}} (z^{k}),

z^{k + 1} = z^{k} - γ F_{ξ^{k}} (z^{k + 1/2}) .

For simplicity, we present the above method for the case when $Z = R^{d}$ ( $F (x^{*}) = 0$ ), and refer the reader to [⁠86⁠ K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020) ] for a more general case of regularized VIs. In contrast to I-SEG, S-SEG uses the same sample $ξ^{k}$ for both steps at iteration $k$ . Although such a strategy cannot be implemented in some scenarios (streaming oracle), it can be applied to finite-sum problems, which have been gaining an increasing attention in the recent years. Moreover, S-SEG relies in significant manner on the following assumption.

Assumption 4. The operator $F_{ξ} (z)$ is $L$ -Lipschitz and $μ$ -strongly monotone almost surely in $ξ$ , i.e., $∥ F_{ξ} (z) - F_{ξ} (z^{'}) ∥_{2} \leq L ∥ z - z^{'} ∥_{2}$ and $⟨ F_{ξ} (z) - F_{ξ} (z^{'}), z - z^{'} ⟩ \geq μ ∥ z - z^{'} ∥_{2}^{2}$ for all $z, z^{'} \in R^{d}$ , almost surely in $ξ$ .

The evident difference between the I-SEG and S-SEG setups can be explained through the connection between the Extragradient and the Proximal Point (PP) methods [⁠84⁠ B. Martinet, Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4, 154–158 (1970) , ⁠107⁠ R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976) ]. In the rest of this subs-section we assume that $Z = R^{d}$ ( $F (z^{*}) = 0$ ). In this setup, PP has the update rule

z^{k + 1} = z^{k} - γ F (z^{k + 1}) .

The method converges for any monotone operator $F$ and any $γ > 0$ . However, the update rule of PP is implicit and in many situations it cannot be computed efficiently. The Extragradient method can be seen as a natural approximation of PP that substitutes $z^{k + 1}$ in the right-hand side by one gradient step from $z^{k}$ :

z^{k + 1} = z^{k} - γ F (z^{k} - γ F (z^{k})) .

In addition, when $F$ is $L$ -Lipschitz, one can estimate how good the approximation is. Consider $z^{k + 1} = z^{k} - γ F (z^{k} - γ F (z^{k}))$ (the Extragradient step) and $\tilde{z}^{k + 1} = z^{k} - γ F (\tilde{z}^{k + 1})$ (the PP step). Then $∥ z^{k + 1} - \tilde{z}^{k + 1} ∥_{2}$ can be estimated as follows [⁠86⁠ K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020) ]:

∥ z^{k + 1} - \tilde{z}^{k + 1} ∥_{2} = γ ∥ F (z^{k} - γ F (z^{k})) - F (\tilde{z}^{k + 1}) ∥_{2} \leq γ L ∥ z^{k} - γ F (z^{k}) - \tilde{z}^{k + 1} ∥_{2} = γ^{2} L ∥ F (z^{k}) - F (\tilde{z}^{k + 1}) ∥_{2} \leq γ^{2} L^{2} ∥ z^{k} - \tilde{z}^{k + 1} ∥_{2} = γ^{3} L^{2} ∥ F (\tilde{z}^{k + 1}) ∥_{2} \leq γ^{3} L^{3} ∥ \tilde{z}^{k + 1} - z^{*} ∥_{2} .

That is, the difference between the Extragradient and PP steps is of the order $O (γ^{3})$ rather than $O (γ^{2})$ . Since the latter corresponds to the difference between PP and the simple gradient step (⁠7⁠), the Extragradient method approximates PP better than gradient steps, which are known to be non-convergent for general monotone Lipschitz variational inequalities. This approximation feature of the Extragradient method is crucial for its convergence and, as the above derivation implies, the approximation argument significantly relies on the Lipschitzness of the operator $F$ .

Let us go back to the differences between I-SEG and S-SEG. In S-SEG, the $k$ -th iteration can be regarded as a single Extragradient step for the operator $F_{ξ^{k}} (z)$ . Therefore, Lipschitzness and monotonicity of $F_{ξ^{k}} (z)$ (Assumption ⁠4⁠) are important for the analysis of S-SEG. In contrast, I-SEG uses different operators for the extrapolation and update steps. In this case, there is no effect from the Lipschitzness/monotonicity of individual $F_{ξ} (z)$ s. Therefore, the analysis of I-SEG naturally relies on the Lipschitzness and monotonicity of $F (z)$ as well as on the closeness (on average) of $F_{ξ} (z)$ and $F (z)$ (Assumption ⁠3⁠).

The convergence of I-SEG was discussed earlier in this section. Regarding S-SEG, one has the following result [⁠86⁠ K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020) ].

Theorem 5.

Let Assumption ⁠4⁠ hold. Then there exists a choice of step size $γ$ (see [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ]) such that the output of S-SEG after $k$ iterations satisfies

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (\frac{L R _{0}^{2}}{μ} exp (- \frac{μ k}{L}) + \frac{σ _{*}^{2}}{μ ^{2} k}),

where $σ_{*}^{2} = E ∥ F_{ξ} (z^{*}) ∥_{2}^{2}$ .

This rate is similar to the one known for I-SEG, with the following differences. First, instead of the uniform bound on the variance $σ^{2}$ , the rate depends on $σ_{*}^{2}$ , which is the variance of $F_{ξ}$ measured at the solution. In many cases, $σ^{2} = \infty$ , while $σ_{*}^{2}$ is finite. From this perspective, S-SEG enjoys a better rate of convergence than I-SEG. However, this comes at a price: while the rate of I-SEG depends on the Lipschitz and strong-monotonicity constants of $F$ , the rate of S-SEG depends on the worst constants of $F_{ξ}$ , which can be much worse than those for $F$ . In particular, consider the finite-sum setup with uniform sampling of $ξ$ : $F (x) = \frac{1}{n} \sum_{i = 1}^{n} F_{i} (x)$ , where $F_{i}$ is $L_{i}$ -Lipschitz and $μ_{i}$ -strongly monotone, and $P {ξ = i} = \frac{1}{n}$ . Then Assumption ⁠4⁠ holds with $L = max_{1 \leq i \leq n} L_{i}$ and $μ = min_{1 \leq i \leq n} μ_{i}$ and these constants appear in the rate from Theorem ⁠3⁠. The authors of [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] tighten this rate. In particular, they prove that for S-SEG with different step sizes for the extrapolation and update steps one has that

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (\frac{L R _{0}^{2}}{μ} exp (- \frac{μ k}{L}) + \frac{σ _{*}^{2}}{μ ^{2} k}),

where $σ_{*}^{2} = \frac{1}{n} \sum_{i = 1}^{n} ∥ F_{i} (z^{*}) ∥_{2}^{2}$ and $\overline{μ} = \frac{1}{n} \sum_{i = 1}^{n} μ_{i}$ . Since $\overline{μ}$ is (sometimes considerably) larger than $μ$ , the improvement is noticeable. Moreover, when the constants ${L_{i}}_{i = 1}^{n}$ are known, one can consider the so-called importance sampling [⁠52⁠ R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin and P. Richtárik, SGD: General analysis and improved rates. In Proceedings of the 36th International Conference on Machine Learning, Proc. Mach. Learn. Res. 97, 5200–5209 (2019) ]: $P {ξ = i} = L_{i} / (n \overline{L})$ , where $\overline{L} = \frac{1}{n} \sum_{i = 1}^{n} L_{i}$ . As the authors of [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] show, importance sampling can be combined with S-SEG by allowing the extrapolation and update step sizes at the $k$ -th iteration to depend on the sample $ξ^{k}$ . In particular, for the proposed modification of S-SEG they derive the estimate

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (\frac{L R _{0}^{2}}{μ} exp (- \frac{μ k}{L}) + \frac{σ ^ _{*}^{2}}{μ ^{2} k}),

where $\overset{σ}{^}_{*}^{2} = \frac{1}{n} \sum_{i = 1}^{n} \frac{L}{L _{i}} ∥ F_{i} (z^{*}) ∥_{2}^{2}$ . The exponentially decaying term is always better than the corresponding one for S-SEG with uniform sampling. This usually implies faster convergence during the initial stage. Next, typically, a larger norm of $F_{i} (z^{*})$ implies larger $L_{i}$ , e.g., $∥ F_{i} (z^{*}) ∥_{2}^{2} \sim L_{i}^{2}$ . In this case, $\overset{σ}{^}_{*}^{2} \leq σ_{*}^{2}$ , because

\overset{σ}{^}_{*}^{2} \sim (\overline{L})^{2} and σ_{*}^{2} \sim \overline{L^{2}} = \frac{1}{n} i = 1 \sum n L_{i}^{2} \geq (\overline{L})^{2} .

Moreover, one can allow other sampling strategies and cover the case when some $μ_{i}$ are negative, see [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] for the details.

4.2 Finite-sum case

As noted earlier, when we deal with problem (⁠13⁠), it is often the case (especially in practical problems) that the distribution $D$ is unknown, but nevertheless some samples from $D$ are available. Then one can replace problem (⁠13⁠) by a finite-sum approximation:

F (z) = \frac{1}{n} i = 1 \sum n F_{i} (z) .

This approximation is sometimes also called Monte Carlo approximation. For machine learning problems the term empirical risk is often encountered. Although calls of the full operator are now tractable, they remain expensive in practice. Therefore, it is worth avoiding frequent computation of $F$ and mainly use calls to single $F_{i}$ operators or small batches of them.

Before presenting the results, let us introduce the appropriate analogue of the Lipschitzness assumption.

Assumption 5 (Lipschitzness in the mean). The operator $F$ is $L_{avg}$ -Lipschitz continuous in mean, i.e., for all $u, v \in Z$ , we have

E [∥ F_{ξ} (u) - F_{ξ} (v) ∥_{*}^{2}] \leq L_{avg}^{2} ∥ u - v ∥^{2} .

For example, if $F_{i}$ is $L_{i}$ -Lipschitz for all $i$ and we draw the index $ξ = i$ with probability $p_{i} = L_{i} / \sum_{j} L_{j}$ , then

L_{avg} = \frac{1}{n} j \sum L_{j} .

The study of finite-sum problems in stochastic optimization is connected, first of all, with classical methods for minimization problems such as SVRG [⁠59⁠ R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural Inf. Process. Syst. 26, 315–323 (2013) ] and SAGA [⁠29⁠ A. Defazio, F. Bach and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Adv. Neural Inf. Process. Syst. 27, 1646–1654 (2014) ]. For the saddle point problems, these methods were adopted in [⁠102⁠ B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems. Adv. Neural Inf. Process. Syst., 1416–1424 (2016) ] (in fact, these results are also valid for variational inequalities). The authors considered strongly convex-strongly concave saddles in the Euclidean case and proved the following estimates for SVRG and SAGA:

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (R_{0}^{2} exp (- min {\frac{1}{n}, \frac{μ ^{2}}{L _{avg}^{2}}} k)) .

Since this last bound is not tight in terms of $L_{avg} / μ$ , the authors proposed accelerating SVRG and SAGA via the Catalyst envelope [⁠76⁠ H. Lin, J. Mairal and Z. Harchaoui, A universal catalyst for first-order optimization. Adv. Neural Inf. Process. Syst. 28, 3384–3392 (2015) ]. In this case, they obtain the bound

E ∥ z^{k} - z^{*} ∥_{2}^{2} = O (R_{0}^{2} exp (- min {\frac{1}{n}; \frac{μ}{n L _{avg}}} \frac{k}{lo g [ L _{avg} / μ ]})) .

The same estimates for methods for saddle point problems based on accelerating envelopes were also presented in [⁠118⁠ V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021) ].

An important step in the study of the finite-sum stochastic setup was taken in the work [⁠25⁠ Y. Carmon, Y. Jin, A. Sidford and K. Tian, Variance reduction for matrix games, preprint, arXiv:1907.02056 (2019) ], which is primarily focused on bilinear games. For this class of problems, the authors improved estimate (⁠21⁠) and removed the additional logarithmic factor. For general problems (saddle point and variational inequalities) the results of [⁠25⁠ Y. Carmon, Y. Jin, A. Sidford and K. Tian, Variance reduction for matrix games, preprint, arXiv:1907.02056 (2019) ] are very similar to those in (⁠21⁠) and also include an additional logarithmic factor. The authors also considered the convex-concave/monotone case in the non-Euclidean setting and found that for their method after $k$ iterations it holds that

E [Gap_{VI} (\overset{z}{^}^{k})] = \tilde{O} (\frac{n L _{avg} D _{Z, V}^{2}}{k}) .

The issue of the additional logarithmic factor was resolved in [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) ], where the following modification of the Extragradient method was proposed:

z^{k + 1/2} = P_{Z} (z^{k} + τ (w^{k} - z^{k}) - γ F (w^{k})),

Δ^{k} = F_{ξ^{k}} (z^{k + 1/2}) - F_{ξ^{k}} (w^{k}) + F (w^{k}),

z^{k + 1} = P_{Z} (z^{k} + τ (w^{k} - z^{k}) - γ Δ^{k})

w^{k + 1} = {z^{k + 1}, w^{k}, with probability p, with probability 1 - p .

This algorithm is a combination of the extra step technique from the theory of VIs and the loopless approach [⁠73⁠ D. Kovalev, S. Horváth and P. Richtárik, Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, edited by A. Kontorovich and G. Neu, Proc. Mach. Learn. Res. 117, 451–467 (2020) ] for finite-sum problems. An interesting ingredient of the method is the randomized negative momentum: $τ (w^{k} - z^{k})$ . While for minimization problems it is usual to apply a positive/heavy-ball momentum, the opposite approach proves useful for saddle point problems and variational inequalities. This effect was noticed earlier [⁠42⁠ G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang, S. Lacoste-Julien and I. Mitliagkas, Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1802–1811 (2019) , ⁠122⁠ T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with o⁢(1/k2) rate on squared gradient norm. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 12098–12109 (2021) , ⁠3⁠ A. Alacaoglu, Y. Malitsky and V. Cevher, Forward-reflected-backward method with variance reduction. Comput. Optim. Appl. 80, 321–346 (2021) ] and is encountered now in the theory of stochastic methods for VIs. Also, in [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) ], the authors presented modifications for the Forward-Backward, Forward-Reflected-Backward as well as for the Extragradient methods in the non-Euclidean case.

As we noted earlier, the results of [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) ] give estimates (⁠21⁠) and (⁠22⁠), but without additional logarithmic factors. That is, to achieve

E ∥ z^{k} - z^{*} ∥_{2}^{2} \leq ε

in the strongly monotone case,

E [Gap_{V I} (\overset{z}{^}^{k})] \leq ε

in the monotone case,

the methods from [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) ] require

O (max {n; \frac{n L _{avg}}{μ}} lo g \frac{R _{0}^{2}}{ε})

and

O (\frac{n L _{avg} D _{Z, V}^{2}}{ε})

stochastic oracle calls, respectively. It remains to discuss the effect of batching on the method from (⁠23⁠), i.e., see how the oracle complexity bounds change if instead a single sample $F_{ξ^{k}}$ at each iteration we use but a batch size of $b$ : $\frac{1}{b} \sum_{i \in S^{k}} F_{i}$ , where $S_{k} \subseteq {1, \dots, n}$ is the set of cardinality $b$ of indices in the mini-batch. In this case, the methods from [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) ] give estimates (⁠24⁠) and (⁠25⁠), but multiplied by an additional factor $b$ . This extra multiplier issue was resolved in [⁠69⁠ D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik and A. Gasnikov, Optimal algorithms for decentralized stochastic variational inequalities, preprint, arXiv:2202.02771 (2022) ] using the following method:

Δ^{k} = \frac{1}{b} i \in S^{k} \sum [F_{i} (z^{k}) - F_{i} (w^{k - 1})

+ α (F_{i} (z^{k}) - F_{i} (z^{k - 1}))] + F (w^{k - 1}),

z^{k + 1} = P_{Z} (z^{k} + τ (w^{k} - z^{k}) - γ Δ^{k}),

w^{k + 1} = {z^{k + 1}, w^{k}, with probability p, with probability 1 - p .

The authors proved that in the strongly monotone case this method gives estimate (⁠24⁠), i.e., without additional logarithmic factors and without factors depending on $b$ .

The only issue that remains to be understood is whether the current state-of-the-art methods with best complexities from [⁠2⁠ A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021) , ⁠69⁠ D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik and A. Gasnikov, Optimal algorithms for decentralized stochastic variational inequalities, preprint, arXiv:2202.02771 (2022) ] are optimal. The lower bounds from [⁠53⁠ Y. Han, G. Xie and Z. Zhang, Lower complexity bounds of finite-sum optimization problems: The results and construction, preprint, arXiv:2103.08280 (2021) ] claim that under Assumptions ⁠5⁠ and ⁠2⁠, the methods above are optimal. However, under $L_{max}$ -Lipschitzness of all $F_{i}$ , $i \in {1, \dots, n}$ and Assumption ⁠2⁠, the lower bound from [⁠53⁠ Y. Han, G. Xie and Z. Zhang, Lower complexity bounds of finite-sum optimization problems: The results and construction, preprint, arXiv:2103.08280 (2021) ] is

E ∥ z^{k} - z^{*} ∥_{2}^{2} = Ω (R_{0}^{2} exp (- min {\frac{1}{n}, \frac{μ}{L _{max}}} k)) .

The question whether this lower bound is tight remains open.

4.3 Cocoercivity assumption

In some papers, the following assumption is used instead of Assumption ⁠1⁠.

Assumption 6 (Cocoercivity). The operator $F$ is $ℓ$ -cocoercive, i.e., for all $u, v \in Z$ , we have $∥ F (u) - F (v) ∥_{2}^{2} \leq ℓ ⟨ F (u) - F (v), u - v ⟩$ .

Cocoercivity is stronger than monotonicity + Lipschitzness, i.e., not all monotone Lipschitz operators are cocoercive. Note, for instance, that the operator for the bilinear SPP ( $min_{x} max_{y} x^{⊤} A y$ ) is not cocoercive. However, if $F$ is $L$ -Lipschitz and $μ$ -strongly monotone, then it is $(L^{2} / μ)$ -cocoercive. Moreover, the operator corresponding to a convex $L$ -smooth minimization problem is $L$ -cocoercive.

There is no need to use an Extragradient method for cocoercive operators. One can apply the iterative scheme (⁠7⁠) and its modifications for the stochastic case. In spite of this, the first work on cocoercive operators in the stochastic cases used the Extragradient as the basic method [⁠26⁠ T. Chavdarova, G. Gidel, F. Fleuret and S. Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. Adv. Neural Inf. Process. Syst. 32, 393–403 (2019) ]. In this paper, the authors investigated methods for finite-sum problems. The subsequent results from [⁠81⁠ N. Loizou, H. Berard, G. Gidel, I. Mitliagkas and S. Lacoste-Julien, Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Adv. Neural Inf. Process. Syst. 34, 19095–19108 (2021) , ⁠15⁠ A. Beznosikov, E. Gorbunov, H. Berard and N. Loizou, Stochastic gradient descent-ascent: Unified theory and new efficient methods, preprint, arXiv:2202.07262 (2022) ] give an almost complete picture of stochastic algorithms based on method (⁠7⁠) for operators under Assumption ⁠6⁠. In particular, the work [⁠15⁠ A. Beznosikov, E. Gorbunov, H. Berard and N. Loizou, Stochastic gradient descent-ascent: Unified theory and new efficient methods, preprint, arXiv:2202.07262 (2022) ] provides a unified analysis for a large number of popular stochastic methods currently known for minimization problems [⁠51⁠ E. Gorbunov, F. Hanzely and P. Richtárik, A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 680–690 (2020) ].

4.4 High-probability convergence

Up to this point, we focused on convergence-in-expectation guarantees for stochastic methods, i.e., bounds on $E [Gap_{VI} (\overset{z}{^}^{k})]$ and/or $E ∥ z^{k} - z^{*} ∥_{2}^{2}$ . However, high-probability convergence guarantees, i.e., bounds on $Gap_{VI} (\overset{z}{^}^{k})$ and/or $∥ z^{k} - z^{*} ∥_{2}^{2}$ that hold with probability at least $1 - β$ for a given confidence level $β \in (0, 1)$ , reflect the real behavior of the methods more accurately [⁠50⁠ E. Gorbunov, M. Danilova and A. Gasnikov, Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Adv. Neural Inf. Process. Syst. 33, 15042–15053 (2020) ]. Despite this fact, high-probability convergence of stochastic methods for solving VIs is studied only in a couple of works.

It is worth mentioning that one can always deduce the high-probability bound from the in-expectation one via Markov’s inequality. However, in this case, the derived rate of convergence will have a negative-power dependence on $β^{- 1}$ . Such guarantees are not desirable and the goal is to derive the rates that have a (poly-)logarithmic dependence on the confidence level, i.e., $β$ should appear only in the $O (poly (lo g (\frac{1}{β})))$ factor.

The first, and for many years the only high-probability guarantees of this type for solving stochastic VIs were derived in [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ]. The authors assume that $F$ is monotone and $L$ -Lipschitz, the underlying domain is bounded, and $F_{ξ}$ is an unbiased estimator with sub-Gaussian (light) tails of the distribution:

E [exp (\frac{∥ F _{ξ} ( x ) - F ( x ) ∥ _{2}^{2}}{σ ^{2}})] \leq exp (1) .

The above condition is much stronger than Assumption ⁠3⁠. Under the listed assumptions, the authors of [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ] prove that after $k$ iterations of Mirror-Prox with probability at least $1 - β$ (for any $β \in (0, 1)$ ) the following inequality is in force:

Gap_{VI} (\overset{z}{^}^{k}) = O (\frac{L D _{Z}^{2}}{k} + \frac{σ D _{Z} lo g ( 1/ β )}{k}) .

Up to the logarithmic factor this result coincides with in-expectation one and, thus, it is optimal (up to the logarithms). However, the result is derived under the restrictive light-tails assumption.

This last limitation was recently addressed in [⁠49⁠ E. Gorbunov, M. Danilova, D. Dobre, P. Dvurechensky, A. Gasnikov and G. Gidel, Clipped stochastic methods for variational inequalities with heavy-tailed noise, preprint, arXiv:2206.01095 (2022) ], where the authors derive the high-probability rates for the considered problem under just the bounded variance assumption. In particular, they consider the clipped-SEG for problems with $Z = R^{d}$ :

z^{k + 1/2} = z^{k} - γ \cdot clip (F_{ξ^{k}} (z^{k}), λ_{k}),

z^{k + 1} = z^{k} - γ \cdot clip (F_{ξ^{k + 1/2}} (z^{k + 1/2}), λ_{k + 1/2}),

where $clip (x, λ) = min {1, λ / ∥ x ∥_{2}} x$ is the clipping operator, a popular tool in deep learning [⁠46⁠ I. Goodfellow, Y. Bengio and A. Courville, Deep learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge (2016) , ⁠103⁠ R. Pascanu, T. Mikolov and Y. Bengio, On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, 1310–1318 (2013) ]. In the setup when $F$ is monotone and $L$ -Lipschitz and Assumption ⁠3⁠ holds, in [⁠49⁠ E. Gorbunov, M. Danilova, D. Dobre, P. Dvurechensky, A. Gasnikov and G. Gidel, Clipped stochastic methods for variational inequalities with heavy-tailed noise, preprint, arXiv:2206.01095 (2022) ] it is proved that after $k$ iterations of clipped-SEG with probability at least $1 - β$ (for any $β \in (0, 1)$ ) the following inequality holds:

Gap_{VI} (\overset{z}{^}^{k}) = O (\frac{L R _{0}^{2} lo g ( k / β )}{k} + \frac{σ R _{0} lo g ( k / β )}{k}) .

Up to the differences in logarithmic factors, the definition of $σ$ , and the difference between $D_{Z}$ and $R_{0}$ , the rate coincides with the one from [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ], but it was derived without the light-tails assumption. The key algorithmic tool that allows removing the light-tails assumption is clipping: with a proper choice of the clipping level $λ$ the authors cut heavy tails without making the bias too large. It is worth mentioning that the result for clipped-SEG is derived for the unconstrained case and the rate depends on $R_{0}$ , while in [⁠60⁠ A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011) ], the analysis relies on the boundedness of the domain, the diameter of which appears explicitly in the rate obtained. To remove the dependence on the diameter of the domain, the authors of [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] show that with high probability the iterates produced by clipped-SEG stay in the ball around $x^{*}$ with a radius proportional to $R_{0}$ . Using this trick, they also show that it is sufficient that all the assumptions (monotonicity and Lipschitzness of $F$ and bounded variance) hold just on this ball. Such a degree of generality allows them to cover problems that are non-Lipschitz on $R^{d}$ (e.g., for certain monotone polynomially growing operators) and also the situation when the variance is bounded only on a compact set, which is common for many finite-sum problems. Finally, [⁠48⁠ E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022) ] contains high-probability convergence results for strongly monotone VIs and VIs with structured non-monotonicity.

5 Recent advances

In this section, we report briefly on a few recent theoretical advances with practical impacts.

5.1 Saddle point problems with different constants of strong convexity and strong concavity

Saddle point problems with different constants of strong convexity and strong concavity started gaining interest a few years ago, see e.g., [⁠4⁠ M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, Accelerated methods for saddle-point problem. Comput. Math. Math. Phys. 60, 1787–1809 (2020) , ⁠77⁠ T. Lin, C. Jin and M. I. Jordan, Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 2738–2779 (2020) ]. However, even for the particular case

x \in R^{d_{x}} min y \in R^{d_{y}} max g (x, y) = f (x) + y^{⊤} A x - h (y),

where the function $f$ is $μ_{x}$ -strongly convex ( $μ_{x} > 0$ ) and $L_{x}$ -smooth, and the function $h$ is $μ_{y}$ -strongly convex ( $μ_{y} > 0$ ) and $L_{y}$ -smooth, optimal algorithms have been proposed only recently [⁠72⁠ D. Kovalev, A. Gasnikov and P. Richtárik, Accelerated primal-dual gradient method for smooth and convex-concave saddle-point problems with bilinear coupling, preprint, arXiv:2112.15199 (2021) , ⁠116⁠ K. K. Thekumparampil, N. He and S. Oh, Lifted primal-dual method for bilinearly coupled smooth minimax optimization, preprint, arXiv:2201.07427 (2022) , ⁠58⁠ Y. Jin, A. Sidford and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, preprint, arXiv:2202.04640 (2022) ]. These algorithms have the convergence rates

O ((\frac{L _{x}}{μ _{x}} + \frac{λ _{max} ( A ^{⊤} A )}{μ _{x} μ _{y}} + \frac{L _{y}}{μ _{y}}) lo g \frac{1}{ε})

and attain the lower bound, which was obtained in [⁠56⁠ A. Ibrahim, W. Azizian, G. Gidel and I. Mitliagkas, Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 4583–4593 (2020) , ⁠124⁠ J. Zhang, M. Hong and S. Zhang, On lower iteration complexity bounds for the convex concave saddle point problems. Math. Program. 194, 901–935 (2022) ] (here one needs to assume that $λ_{min} (A^{⊤} A) \leq μ_{x} μ_{y}$ ; without this assumption no optimal methods are known).

Note that the algorithm from [⁠58⁠ Y. Jin, A. Sidford and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, preprint, arXiv:2202.04640 (2022) ] is built upon a technique related to the analysis of primal-dual Extragradient methods via relative Lipschitzness [⁠28⁠ M. B. Cohen, A. Sidford and K. Tian, Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Article No. 62, (2021) , ⁠115⁠ F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov and V. Piskunova, Inexact model: A framework for optimization and variational inequalities. Optim. Methods Softw. 36, 1155–1201 (2021) ]. As a by-product, this technique makes it possible to obtain Nesterov’s accelerated method as a particular case of primal-dual Extragradient method with relative Lipschitzness [⁠28⁠ M. B. Cohen, A. Sidford and K. Tian, Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Article No. 62, (2021) ].

For the non-bilinear SPP, optimal methods, based on the accelerated Monteiro–Svaiter proximal envelope, were developed only in the non-composite case [⁠24⁠ Y. Carmon, A. Jambulapati, Y. Jin and A. Sidford, Recapp: Crafting a more efficient catalyst for convex optimization. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 2658–2685 (2022) , ⁠71⁠ D. Kovalev and A. Gasnikov, The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization, preprint, arXiv:2205.05653 (2022) ]. For the non-bilinear SPP with composite terms, there is a poly-logarithmic gap between the lower bound and the best known upper bounds [⁠118⁠ V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021) ]. A gap also appears for the SPP with stochastic finite-sum structure [⁠58⁠ Y. Jin, A. Sidford and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, preprint, arXiv:2202.04640 (2022) , ⁠82⁠ L. Luo, G. Xie, T. Zhang and Z. Zhang, Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization, preprint, arXiv:2106.01761 (2021) , ⁠118⁠ V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021) ]. The stochastic setting with bounded variance was considered in [⁠32⁠ S. S. Du, G. Gidel, M. I. Jordan and C. J. Li, Optimal extragradient-based bilinearly-coupled saddle-point optimization, preprint, arXiv:2206.08573 (2022) , ⁠85⁠ D. Metelev, A. Rogozin, A. Gasnikov and D. Kovalev, Decentralized saddle-point problems with different constants of strong convexity and strong concavity, preprint, arXiv:2206.00090 (2022) , ⁠125⁠ X. Zhang, N. S. Aybat and M. Gurbuzbalaban, Robust accelerated primal-dual methods for computing saddle points, preprint, arXiv:2111.12743 (2021) ].

Further deterministic “cutting-plane” improvements are connected with the additional assumptions about small dimension of the involved vectors $x$ or/and $y$ (see [⁠43⁠ E. Gladin, I. Kuruzov, F. Stonyakin, D. Pasechnyuk, M. Alkousa and A. Gasnikov, Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables, preprint, arXiv:2010.02280 (2022) , ⁠44⁠ E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov and M. Alkousa, Solving smooth min-min and min-max problems by mixed oracle algorithms. In Mathematical Optimization Theory and Operations Research—Recent Trends, Commun. Comput. Inf. Sci. 1476, Springer, Cham, 19–40 (2021) , ⁠91⁠ A. Nemirovski, Efficient methods in convex programming. Lecture notes, https://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf (1994) ]) or with different structural (e.g., SPP on balls in $1$ - or $\infty$ -norms) and sparsity assumptions, see e.g., [⁠21⁠ Y. Carmon, Y. Jin, A. Sidford and K. Tian, Coordinate methods for matrix games. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 283–293 (2020) , ⁠111⁠ C. Song, C. Y. Lin, S. J. Wright and J. Diakonikolas, Coordinate linear variance reduction for generalized linear programming, preprint, arXiv:2111.01842 (2021) , ⁠112⁠ C. Song, S. J. Wright and J. Diakonikolas, Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 9824–9834 (2021) ] and references therein. Here lower bounds are mostly unknown.

In this subsection we mentioned many works dealing with (sub-)optimal algorithms for different variants of SPP. We note that, in contrast to convex optimization, where the oracle call is uniquely associated with the gradient call $\nabla f (x)$ , for SPP we have two criteria: the number of $\nabla_{x} g (x, y)$ -calls and that of $\nabla_{y} g (x, y)$ -calls (and more variants for SPP with composites). “Optimality” in the most of the aforementioned papers means that the method is optimal according to the worst of the criteria. In [⁠4⁠ M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, Accelerated methods for saddle-point problem. Comput. Math. Math. Phys. 60, 1787–1809 (2020) , ⁠118⁠ V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021) ], the authors consider these criteria separately. However, the development of the lower bounds and optimal methods for a multi-criterion setup is still an open problem.

5.2 Adaptive methods for VI and SPP

Interest in adaptive algorithms for stochastic convex optimization mainly arose in 2011 after the development of the AdaGrad (adaptive gradient) [⁠33⁠ J. Duchi, E. Hazan and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12, 2121–2159 (2011) ] and Adam (adaptive moment estimation) [⁠63⁠ D. P. Kingma and J. Ba, Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2305–2313 (2015) ] algorithms. For variational inequalities and saddle point problems, people became interested in adaptive methods only in the last few years, see, e.g., [⁠8⁠ F. Bach and K. Y. Levy, A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, Proc. Mach. Learn. Res., 164–194 (2019) , ⁠40⁠ A. V. Gasnikov, P. E. Dvurechensky, F. S. Stonyakin and A. A. Titov, An adaptive proximal method for variational inequalities. Comput. Math. Math. Phys. 59, 836–841 (2019) ] (see also [⁠61⁠ E. N. Khobotov, Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. U.S.S.R. Comput. Math. Math. Phys. 27, 120–127 (1987) ]). Currently, this area of research is well developed. One can mention here works devoted to both adaptive step sizes [⁠5⁠ K. Antonakopoulos, E. V. Belmega and P. Mertikopoulos, Adaptive extra-gradient methods for min-max optimization and games, preprint, arXiv:2010.12100 (2020) , ⁠34⁠ A. Ene and H. L. Nguyen, Adaptive and universal algorithms for variational inequalities with optimal convergence. In Proceedings of the AAAI Conference on Artificial Intelligence, 36, 6559–6567 (2022) , ⁠35⁠ A. Ene, H. L. Nguyen and A. Vladu, Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, 35, 7314–7321 (2021) , ⁠114⁠ F. Stonyakin, A. Gasnikov, P. Dvurechensky, A. Titov and M. Alkousa, Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle. J. Optim. Theory Appl. 194, 988–1013 (2022) , ⁠117⁠ A. A. Titov, S. S. Ablaev, M. S. Alkousa, F. S. Stonyakin and A. V. Gasnikov, Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness, preprint, arXiv:2207.09544 (2022) ] and adaptive scaling/preconditioning [⁠12⁠ A. Beznosikov, A. Alanov, D. Kovalev, M. Takáč and A. Gasnikov, On scaled methods for saddle point problems, preprint, arXiv:2206.08303 (2022) , ⁠31⁠ Z. Dou and Y. Li, On the one-sided convergence of Adam-type algorithms in non-convex non-concave min-max optimization, preprint, arXiv:2109.14213 (2021) , ⁠80⁠ M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das and T. Yang, Towards better understanding of adaptive gradient algorithms in generative adversarial nets, preprint, arXiv:1912.11940 (2019) ]. Approaches from the second group are based on the idea of a proper combination of AdaGrad/Adam with Extragradient or its modifications. All of the mentioned adaptive methods have no better (typically the same) theoretical rates of convergence than their non-adaptive analogues, but require less input information or demonstrate better performance in practice.

5.3 Quasi-Newton and tensor methods for VI and SPP

Quasi-Newton methods for solving nonlinear equations (unconstrained VI) and SPP are proposed in [⁠75⁠ D. Lin, H. Ye and Z. Zhang, Explicit superlinear convergence rates of Broyden’s methods in nonlinear equations, preprint, arXiv:2109.01974 (2021) , ⁠121⁠ H. Ye, D. Lin and Z. Zhang, Greedy and random Broyden’s methods with explicit superlinear convergence rates in nonlinear equations, preprint, arXiv:2110.08572 (2021) ] and [⁠79⁠ C. Liu and L. Luo, Quasi-Newton methods for saddle point problems, preprint, arXiv:2111.02708 (2021) ], respectively. In these papers, local superlinear rates of convergence are derived for the modifications of the Broyden-type methods for solving nonlinear equations with Lipschitz Jacobian and SPP with Lipschitz Hessian. Stochastic versions of these methods for VI and SPP still await to be developed.

Tensor methods for convex optimization problems are currently quite well developed. In particular, starting with [⁠99⁠ Y. Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance. Math. Program. 108, 177–205 (2006) ] it has been shown that optimal second- and third-order methods can be implemented with almost the same complexity of each iteration as the Newton method [⁠89⁠ R. D. C. Monteiro and B. F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23, 1092–1125 (2013) , ⁠97⁠ Y. Nesterov, Implementable tensor methods in unconstrained convex optimization. Math. Program. 186, 157–183 (2021) , ⁠39⁠ A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck et al., Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1392–1393 (2019) ]. Moreover, optimal $p$ -order methods (which use $p$ -order derivatives) significantly reduce the rate of convergence from $k^{- 2}$ to $k^{- (3 p + 1) /2}$ (see [⁠70⁠ D. Kovalev and A. Gasnikov, The first optimal acceleration of high-order methods in smooth convex optimization, preprint, arXiv:2205.09647 (2022) , ⁠23⁠ Y. Carmon, D. Hausler, A. Jambulapati, Y. Jin and A. Sidford, Optimal and adaptive Monteiro–Svaiter acceleration, preprint, arXiv:2205.15371 (2022) ]). For VI and SPP, the study was initiated in [⁠94⁠ Y. Nesterov, Cubic regularization of Newton’s method for convex problems with constraints. CORE Discussion Paper No. 2006/39, https://ssrn.com/abstract=921825 (2006) , ⁠88⁠ R. D. C. Monteiro and B. F. Svaiter, Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM J. Optim. 22, 914–935 (2012) ] and optimal $p$ -order methods reduce the rate of convergence from $k^{- 1}$ to $k^{- (p + 1) /2}$ (see [⁠1⁠ D. Adil, B. Bullins, A. Jambulapati and S. Sachdeva, Line search-free methods for higher-order smooth monotone variational inequalities, preprint, arXiv:2205.06167 (2022) , ⁠78⁠ T. Lin, M. Jordan et al., Perseus: A simple high-order regularization method for variational inequalities, preprint, arXiv:2205.03202 (2022) ]) (for $k^{- 1}$ , see Theorem ⁠3⁠). However, in contrast to convex optimization, the use of tensor methods for sufficiently smooth monotone VIs and convex-concave saddle point problems is not expected to be as effective. Note that in [⁠1⁠ D. Adil, B. Bullins, A. Jambulapati and S. Sachdeva, Line search-free methods for higher-order smooth monotone variational inequalities, preprint, arXiv:2205.06167 (2022) , ⁠78⁠ T. Lin, M. Jordan et al., Perseus: A simple high-order regularization method for variational inequalities, preprint, arXiv:2205.03202 (2022) ] one can also find optimal rates for strongly monotone VIs and strongly convex-concave SPP. Stochastic tensor methods for variational inequalities and saddle point problems still await to be developed.

5.4 Convergence in terms of the gradient norm for SPP

Several recent advances in the development of optimal algorithms are based on accelerated proximal envelopes with proper stopping rules for inner loop algorithms [⁠71⁠ D. Kovalev and A. Gasnikov, The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization, preprint, arXiv:2205.05653 (2022) , ⁠70⁠ D. Kovalev and A. Gasnikov, The first optimal acceleration of high-order methods in smooth convex optimization, preprint, arXiv:2205.09647 (2022) , ⁠68⁠ D. Kovalev, A. Beznosikov, E. Borodich, A. Gasnikov and G. Scutari, Optimal gradient sliding and its application to distributed optimization under similarity, preprint, arXiv:2205.15136 (2022) , ⁠109⁠ A. Sadiev, D. Kovalev and P. Richtárik, Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with inexact prox. arXiv:2207.03957 (2022) ]. Such rules are built upon the norm of the gradient calculated for the target function of the inner problem.

For smooth convex optimization problems, Yu. Nesterov in 2012 posed the problem of making the gradient norm small with the same rate of convergence as a gap in the function values, i.e., proportional to $k^{- 2}$ (see [⁠96⁠ Y. Nesterov, How to make the gradients small. Optima. Mathematical Optimization Society Newsletter 88, 10–11 (2012) ]). To address this problem, in [⁠96⁠ Y. Nesterov, How to make the gradients small. Optima. Mathematical Optimization Society Newsletter 88, 10–11 (2012) ] he proposed an optimal (up to a logarithmic factor) algorithm. This question was further investigated, leading to optimal results without additional logarithmic factors [⁠62⁠ D. Kim and J. A. Fessler, Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. J. Optim. Theory Appl. 188, 192–219 (2021) , ⁠98⁠ Y. Nesterov, A. Gasnikov, S. Guminov and P. Dvurechensky, Primal-dual accelerated gradient methods with small-dimensional relaxation oracle. Optim. Methods Softw. 36, 773–810 (2021) ] (see also [⁠30⁠ J. Diakonikolas and P. Wang, Potential function-based framework for minimizing gradients in convex and min-max optimization. SIAM J. Optim. 32, 1668–1697 (2022) ] for explanations and a survey). In the stochastic case, algorithms were presented in [⁠38⁠ D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan and B. Woodworth, The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1319–1345 (2019) ].

For smooth convex-concave saddle point problems an optimal algorithm with $∥ \nabla_{x, y} f (x^{k}, y^{k}) ∥_{2}$ proportional to $k^{- 1}$ was proposed in [⁠122⁠ T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with o⁢(1/k2) rate on squared gradient norm. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 12098–12109 (2021) ] (see also [⁠30⁠ J. Diakonikolas and P. Wang, Potential function-based framework for minimizing gradients in convex and min-max optimization. SIAM J. Optim. 32, 1668–1697 (2022) ] and [⁠71⁠ D. Kovalev and A. Gasnikov, The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization, preprint, arXiv:2205.05653 (2022) ] for monotone inclusion). For the stochastic case, see [⁠74⁠ S. Lee and D. Kim, Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Adv. Neural Inf. Process. Syst. 34, 22588–22600 (2021) , ⁠20⁠ X. Cai, C. Song, C. Guzmán and J. Diakonikolas, A stochastic halpern iteration with variance reduction for stochastic monotone inclusion problems, preprint, arXiv:2203.09436 (2022) , ⁠27⁠ L. Chen and L. Luo, Near-optimal algorithms for making the gradient small in stochastic minimax optimization, preprint, arXiv:2208.05925 (2022) ].

5.5 Decentralized VI and SPP

In practice, in order to solve a variational inequality problem more efficiently and quickly, one usually resorts to distributed methods. In particular, methods that work on arbitrary (possibly time-varying) decentralized communication networks between computing devices are popular.

While the field of decentralized algorithms for minimization problems has been extensively investigated, results for broader classes of problems have only begun to appear in recent years. Such works are primarily focused on saddle point problems [⁠90⁠ S. Mukherjee and M. Chakraborty, A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), 2967–2972 (2020) , ⁠17⁠ A. Beznosikov, V. Samokhin and A. Gasnikov, Distributed saddle-point problems: Lower bounds, optimal and robust algorithms, preprint arXiv:2010.13112 (2020) , ⁠108⁠ A. Rogozin, A. Beznosikov, D. Dvinskikh, D. Kovalev, P. Dvurechensky and A. Gasnikov, Decentralized distributed optimization for saddle point problems, preprint, arXiv:2102.07758 (2021) , ⁠18⁠ A. Beznosikov, G. Scutari, A. Rogozin and A. Gasnikov, Distributed saddle-point problems under data similarity. Adv. Neural Inf. Process. Syst. 34, 8172–8184 (2021) , ⁠16⁠ A. Beznosikov, A. Rogozin, D. Kovalev and A. Gasnikov, Near-optimal decentralized algorithms for saddle point problems over time-varying networks. In Optimization and applications, Lecture Notes in Comput. Sci. 13078, Springer, Cham, 246–257 (2021) ], but we note that most of these results can easily be extended to variational inequalities. Let us emphasize two works that were from the outset devoted to VIs. In [⁠13⁠ A. Beznosikov, P. Dvurechensky, A. Koloskova, V. Samokhin, S. U. Stich and A. Gasnikov, Decentralized local stochastic extra-gradient for variational inequalities, preprint, arXiv:2106.08315 (2021) ], the authors proposed a decentralized method with local steps, and [⁠69⁠ D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik and A. Gasnikov, Optimal algorithms for decentralized stochastic variational inequalities, preprint, arXiv:2202.02771 (2022) ] presented optimal decentralized methods for stochastic (finite-sum) variational inequalities on fixed and varying networks.

Acknowledgements. The work was supported by Russian Science Foundation (project No. 21-71-30005).

Aleksandr Beznosikov is a PhD student at the Moscow Institute of Physics and Technology (Moscow, Russia). He is also a researcher at the Laboratory of Mathematical Methods of Optimization and at Laboratory of Advanced Combinatorics and Network Applications in the Moscow Institute of Physics and Technology, a junior researcher at the International Laboratory of SA and HDI in the Higher School of Economics (Moscow), a research intern at Yandex Research (Moscow). His current research interests are concentrated around variational inequalities, saddle point problems, distributed optimization, stochastic optimization, machine learning and federated learning. anbeznosikov@gmail.com Boris Polyak (1935–2023) was head of the Ya. Z. Tsypkin Laboratory of the Institute for Control Science of the Russian Academy of Sciences in Moscow and a professor at the Moscow University of Physics and Engineering. He received a PhD degree in mathematics from Moscow State University in 1963 and a Doctor of Science degree (habilitation) in engineering from the Institute for Control Science of the Russian Academy of Sciences in Moscow in 1977. He authored or coauthored more than 250 papers in peer-reviewed journals as well as four monographs, including “Introduction to Optimization”. He was an IFAC Fellow, a recipient of the EURO-2012 Gold Medal and the INFORMS Optimization Society Khyachyan Prize. His main area of research was optimization algorithms and optimal control. Eduard Gorbunov is a researcher at the Laboratory of Mathematical Methods of Optimization in the Moscow Institute of Physics and Technology. His current research interests are concentrated around stochastic optimization and its applications to machine learning, distributed optimization, derivative-free optimization, and variational inequalities. ed-gorbunov@yandex.ru Dmitry Kovalev is a PhD student at King Abdullah University of Science and Technology (Thuwal, Saudi Arabia). In 2020 and 2021 he received the Yandex Award (Ilya Segalovich Award). His current research interests include continuous optimization and machine learning. dakovalev1@gmail.com Alexander Gasnikov is a professor at the Moscow Institute of Physics and Technology, head of the Laboratory Mathematical Methods of Optimization and head of the department Mathematical Foundations of Control. He received a Doctor of Science degree (habilitation) in mathematics in 2016 from the Faculty of Control and Applied Mathematics of the Moscow Institute of Physics and Technology. In 2019 he received an award from the Yahoo Faculty Research and Engagement Program. In 2020 he received the Yandex Award (Ilya Segalovich Award). In 2021 he received the Award for Young Scientists from the Moscow government. His main area of research is optimization algorithms. gasnikov@yandex.ru

References

D. Adil, B. Bullins, A. Jambulapati and S. Sachdeva, Line search-free methods for higher-order smooth monotone variational inequalities, preprint, arXiv:2205.06167 (2022)
A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021)
A. Alacaoglu, Y. Malitsky and V. Cevher, Forward-reflected-backward method with variance reduction. Comput. Optim. Appl. 80, 321–346 (2021)
M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, Accelerated methods for saddle-point problem. Comput. Math. Math. Phys. 60, 1787–1809 (2020)
K. Antonakopoulos, E. V. Belmega and P. Mertikopoulos, Adaptive extra-gradient methods for min-max optimization and games, preprint, arXiv:2010.12100 (2020)
K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming. Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford (1958)
W. Azizian, D. Scieur, I. Mitliagkas, S. Lacoste-Julien and G. Gidel, Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1705–1715 (2020)
F. Bach and K. Y. Levy, A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, Proc. Mach. Learn. Res., 164–194 (2019)
F. Bach, J. Mairal and J. Ponce, Convex sparse matrix factorizations, preprint, arXiv:0812.1869 (2008)
A. Bakushinskii and B. Polyak, On the solution of variational inequalities. Sov. Math. Dokl. 15, 1705–1710 (1974)
A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust optimization. Princeton Ser. Appl. Math., Princeton University Press, Princeton (2009)
A. Beznosikov, A. Alanov, D. Kovalev, M. Takáč and A. Gasnikov, On scaled methods for saddle point problems, preprint, arXiv:2206.08303 (2022)
A. Beznosikov, P. Dvurechensky, A. Koloskova, V. Samokhin, S. U. Stich and A. Gasnikov, Decentralized local stochastic extra-gradient for variational inequalities, preprint, arXiv:2106.08315 (2021)
A. Beznosikov, A. Gasnikov, K. Zainulina, A. Maslovskiy and D. Pasechnyuk, A unified analysis of variational inequality methods: Variance reduction, sampling, quantization and coordinate descent, preprint, arXiv:2201.12206 (2022)
A. Beznosikov, E. Gorbunov, H. Berard and N. Loizou, Stochastic gradient descent-ascent: Unified theory and new efficient methods, preprint, arXiv:2202.07262 (2022)
A. Beznosikov, A. Rogozin, D. Kovalev and A. Gasnikov, Near-optimal decentralized algorithms for saddle point problems over time-varying networks. In Optimization and applications, Lecture Notes in Comput. Sci. 13078, Springer, Cham, 246–257 (2021)
A. Beznosikov, V. Samokhin and A. Gasnikov, Distributed saddle-point problems: Lower bounds, optimal and robust algorithms, preprint arXiv:2010.13112 (2020)
A. Beznosikov, G. Scutari, A. Rogozin and A. Gasnikov, Distributed saddle-point problems under data similarity. Adv. Neural Inf. Process. Syst. 34, 8172–8184 (2021)
F. E. Browder, Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. U.S.A. 56, 1080–1086 (1966)
X. Cai, C. Song, C. Guzmán and J. Diakonikolas, A stochastic halpern iteration with variance reduction for stochastic monotone inclusion problems, preprint, arXiv:2203.09436 (2022)
Y. Carmon, Y. Jin, A. Sidford and K. Tian, Coordinate methods for matrix games. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 283–293 (2020)
A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40, 120–145 (2011)
Y. Carmon, D. Hausler, A. Jambulapati, Y. Jin and A. Sidford, Optimal and adaptive Monteiro–Svaiter acceleration, preprint, arXiv:2205.15371 (2022)
Y. Carmon, A. Jambulapati, Y. Jin and A. Sidford, Recapp: Crafting a more efficient catalyst for convex optimization. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 2658–2685 (2022)
Y. Carmon, Y. Jin, A. Sidford and K. Tian, Variance reduction for matrix games, preprint, arXiv:1907.02056 (2019)
T. Chavdarova, G. Gidel, F. Fleuret and S. Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. Adv. Neural Inf. Process. Syst. 32, 393–403 (2019)
L. Chen and L. Luo, Near-optimal algorithms for making the gradient small in stochastic minimax optimization, preprint, arXiv:2208.05925 (2022)
M. B. Cohen, A. Sidford and K. Tian, Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Article No. 62, (2021)
A. Defazio, F. Bach and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Adv. Neural Inf. Process. Syst. 27, 1646–1654 (2014)
J. Diakonikolas and P. Wang, Potential function-based framework for minimizing gradients in convex and min-max optimization. SIAM J. Optim. 32, 1668–1697 (2022)
Z. Dou and Y. Li, On the one-sided convergence of Adam-type algorithms in non-convex non-concave min-max optimization, preprint, arXiv:2109.14213 (2021)
S. S. Du, G. Gidel, M. I. Jordan and C. J. Li, Optimal extragradient-based bilinearly-coupled saddle-point optimization, preprint, arXiv:2206.08573 (2022)
J. Duchi, E. Hazan and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12, 2121–2159 (2011)
A. Ene and H. L. Nguyen, Adaptive and universal algorithms for variational inequalities with optimal convergence. In Proceedings of the AAAI Conference on Artificial Intelligence, 36, 6559–6567 (2022)
A. Ene, H. L. Nguyen and A. Vladu, Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, 35, 7314–7321 (2021)
E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015–1046 (2010)
F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research, Springer, New York (2003)
D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan and B. Woodworth, The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1319–1345 (2019)
A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck et al., Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1392–1393 (2019)
A. V. Gasnikov, P. E. Dvurechensky, F. S. Stonyakin and A. A. Titov, An adaptive proximal method for variational inequalities. Comput. Math. Math. Phys. 59, 836–841 (2019)
G. Gidel, H. Berard, G. Vignoud, P. Vincent and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, preprint, arXiv:1802.10551 (2018)
G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang, S. Lacoste-Julien and I. Mitliagkas, Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1802–1811 (2019)
E. Gladin, I. Kuruzov, F. Stonyakin, D. Pasechnyuk, M. Alkousa and A. Gasnikov, Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables, preprint, arXiv:2010.02280 (2022)
E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov and M. Alkousa, Solving smooth min-min and min-max problems by mixed oracle algorithms. In Mathematical Optimization Theory and Operations Research—Recent Trends, Commun. Comput. Inf. Sci. 1476, Springer, Cham, 19–40 (2021)
E. G. Gol’šteĭn, Convergence of the gradient method for finding the saddle points of modified Lagrangian functions. Èkonom. i Mat. Metody 13, 322–329 (1977)
I. Goodfellow, Y. Bengio and A. Courville, Deep learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge (2016)
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville and Y. Bengio, Generative adversarial networks. Commun. ACM 63, 139–144 (2020)
E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022)
E. Gorbunov, M. Danilova, D. Dobre, P. Dvurechensky, A. Gasnikov and G. Gidel, Clipped stochastic methods for variational inequalities with heavy-tailed noise, preprint, arXiv:2206.01095 (2022)
E. Gorbunov, M. Danilova and A. Gasnikov, Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Adv. Neural Inf. Process. Syst. 33, 15042–15053 (2020)
E. Gorbunov, F. Hanzely and P. Richtárik, A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 680–690 (2020)
R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin and P. Richtárik, SGD: General analysis and improved rates. In Proceedings of the 36th International Conference on Machine Learning, Proc. Mach. Learn. Res. 97, 5200–5209 (2019)
Y. Han, G. Xie and Z. Zhang, Lower complexity bounds of finite-sum optimization problems: The results and construction, preprint, arXiv:2103.08280 (2021)
Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, On the convergence of single-call stochastic extra-gradient methods. Adv. Neural Inf. Process. Syst. 32, 6938–6948 (2019)
Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Adv. Neural Inf. Process. Syst. 33, 16223–16234 (2020)
A. Ibrahim, W. Azizian, G. Gidel and I. Mitliagkas, Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 4583–4593 (2020)
Y. Jin and A. Sidford, Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 119, 4890–4900 (2020)
Y. Jin, A. Sidford and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, preprint, arXiv:2202.04640 (2022)
R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural Inf. Process. Syst. 26, 315–323 (2013)
A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011)
E. N. Khobotov, Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. U.S.S.R. Comput. Math. Math. Phys. 27, 120–127 (1987)
D. Kim and J. A. Fessler, Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. J. Optim. Theory Appl. 188, 192–219 (2021)
D. P. Kingma and J. Ba, Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2305–2313 (2015)
G. M. Korpelevič, An extragradient method for finding saddle points and for other problems. Èkonom. i Mat. Metody 12, 747–756 (1976)
G. M. Korpelevich, Extrapolation gradient methods and their relation to modified Lagrange functions. Èkonom. i Mat. Metody 19, 694–703 (1983)
G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation. SIAM J. Optim. 32, 2041–2073 (2022)
G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning. SIAM J. Optim. 32, 1120–1155 (2022)
D. Kovalev, A. Beznosikov, E. Borodich, A. Gasnikov and G. Scutari, Optimal gradient sliding and its application to distributed optimization under similarity, preprint, arXiv:2205.15136 (2022)
D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik and A. Gasnikov, Optimal algorithms for decentralized stochastic variational inequalities, preprint, arXiv:2202.02771 (2022)
D. Kovalev and A. Gasnikov, The first optimal acceleration of high-order methods in smooth convex optimization, preprint, arXiv:2205.09647 (2022)
D. Kovalev and A. Gasnikov, The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization, preprint, arXiv:2205.05653 (2022)
D. Kovalev, A. Gasnikov and P. Richtárik, Accelerated primal-dual gradient method for smooth and convex-concave saddle-point problems with bilinear coupling, preprint, arXiv:2112.15199 (2021)
D. Kovalev, S. Horváth and P. Richtárik, Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, edited by A. Kontorovich and G. Neu, Proc. Mach. Learn. Res. 117, 451–467 (2020)
S. Lee and D. Kim, Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Adv. Neural Inf. Process. Syst. 34, 22588–22600 (2021)
D. Lin, H. Ye and Z. Zhang, Explicit superlinear convergence rates of Broyden’s methods in nonlinear equations, preprint, arXiv:2109.01974 (2021)
H. Lin, J. Mairal and Z. Harchaoui, A universal catalyst for first-order optimization. Adv. Neural Inf. Process. Syst. 28, 3384–3392 (2015)
T. Lin, C. Jin and M. I. Jordan, Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 2738–2779 (2020)
T. Lin, M. Jordan et al., Perseus: A simple high-order regularization method for variational inequalities, preprint, arXiv:2205.03202 (2022)
C. Liu and L. Luo, Quasi-Newton methods for saddle point problems, preprint, arXiv:2111.02708 (2021)
M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das and T. Yang, Towards better understanding of adaptive gradient algorithms in generative adversarial nets, preprint, arXiv:1912.11940 (2019)
N. Loizou, H. Berard, G. Gidel, I. Mitliagkas and S. Lacoste-Julien, Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Adv. Neural Inf. Process. Syst. 34, 19095–19108 (2021)
L. Luo, G. Xie, T. Zhang and Z. Zhang, Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization, preprint, arXiv:2106.01761 (2021)
Y. Malitsky and M. K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30, 1451–1472 (2020)
B. Martinet, Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4, 154–158 (1970)
D. Metelev, A. Rogozin, A. Gasnikov and D. Kovalev, Decentralized saddle-point problems with different constants of strong convexity and strong concavity, preprint, arXiv:2206.00090 (2022)
K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020)
A. Mokhtari, A. Ozdaglar and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1497–1507 (2020)
R. D. C. Monteiro and B. F. Svaiter, Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM J. Optim. 22, 914–935 (2012)
R. D. C. Monteiro and B. F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23, 1092–1125 (2013)
S. Mukherjee and M. Chakraborty, A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), 2967–2972 (2020)
A. Nemirovski, Efficient methods in convex programming. Lecture notes, https://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf (1994)
A. Nemirovski, Prox-method with rate of convergence O⁢(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2004)
Y. Nesterov, Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)
Y. Nesterov, Cubic regularization of Newton’s method for convex problems with constraints. CORE Discussion Paper No. 2006/39, https://ssrn.com/abstract=921825 (2006)
Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109, 319–344 (2007)
Y. Nesterov, How to make the gradients small. Optima. Mathematical Optimization Society Newsletter 88, 10–11 (2012)
Y. Nesterov, Implementable tensor methods in unconstrained convex optimization. Math. Program. 186, 157–183 (2021)
Y. Nesterov, A. Gasnikov, S. Guminov and P. Dvurechensky, Primal-dual accelerated gradient methods with small-dimensional relaxation oracle. Optim. Methods Softw. 36, 773–810 (2021)
Y. Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance. Math. Program. 108, 177–205 (2006)
S. Omidshafiei, J. Pazis, C. Amato, J. P. How and J. Vian, Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 70, 2681–2690 (2017)
Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. 185, 1–35 (2021)
B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems. Adv. Neural Inf. Process. Syst., 1416–1424 (2016)
R. Pascanu, T. Mikolov and Y. Bengio, On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, 1310–1318 (2013)
B. T. Polyak, Introduction to optimization. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York (1987)
L. D. Popov, A modification of the Arrow–Hurwicz method for search of saddle points. Math. Notes 28, 845–848 (1981)
R. T. Rockafellar, Convex functions, monotone operators and variational inequalities. In Theory and Applications of Monotone Operators (Proc. NATO Advanced Study Inst., Venice, 1968), Edizioni “Oderisi”, Gubbio, 35–65 (1969)
R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
A. Rogozin, A. Beznosikov, D. Dvinskikh, D. Kovalev, P. Dvurechensky and A. Gasnikov, Decentralized distributed optimization for saddle point problems, preprint, arXiv:2102.07758 (2021)
A. Sadiev, D. Kovalev and P. Richtárik, Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with inexact prox. arXiv:2207.03957 (2022)
M. Sibony, Méthodes itératives pour les équations et inéquations aux dérivées partielles non linéaires de type monotone. Calcolo 7, 65–183 (1970)
C. Song, C. Y. Lin, S. J. Wright and J. Diakonikolas, Coordinate linear variance reduction for generalized linear programming, preprint, arXiv:2111.01842 (2021)
C. Song, S. J. Wright and J. Diakonikolas, Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 9824–9834 (2021)
G. Stampacchia, Formes bilinéaires coercitives sur les ensembles convexes. C. R. Acad. Sci. Paris 258, 4413–4416 (1964)
F. Stonyakin, A. Gasnikov, P. Dvurechensky, A. Titov and M. Alkousa, Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle. J. Optim. Theory Appl. 194, 988–1013 (2022)
F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov and V. Piskunova, Inexact model: A framework for optimization and variational inequalities. Optim. Methods Softw. 36, 1155–1201 (2021)
K. K. Thekumparampil, N. He and S. Oh, Lifted primal-dual method for bilinearly coupled smooth minimax optimization, preprint, arXiv:2201.07427 (2022)
A. A. Titov, S. S. Ablaev, M. S. Alkousa, F. S. Stonyakin and A. V. Gasnikov, Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness, preprint, arXiv:2207.09544 (2022)
V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021)
P. Tseng, On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60, 237–252 (1995)
P. Tseng, A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38, 431–446 (2000)
H. Ye, D. Lin and Z. Zhang, Greedy and random Broyden’s methods with explicit superlinear convergence rates in nonlinear equations, preprint, arXiv:2110.08572 (2021)
T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with o⁢(1/k2) rate on squared gradient norm. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 12098–12109 (2021)
G. Zhang, Y. Wang, L. Lessard and R. B. Grosse, Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7659–7679 (2022)
J. Zhang, M. Hong and S. Zhang, On lower iteration complexity bounds for the convex concave saddle point problems. Math. Program. 194, 901–935 (2022)
X. Zhang, N. S. Aybat and M. Gurbuzbalaban, Robust accelerated primal-dual methods for computing saddle points, preprint, arXiv:2111.12743 (2021)

Cite this article

Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov, Dmitry Kovalev, Alexander Gasnikov, Smooth monotone stochastic variational inequalities and saddle point problems: A survey. Eur. Math. Soc. Mag. 127 (2023), pp. 15–28

DOI 10.4171/MAG/112

🅭🅯

This open access article is published by EMS Press under a CC BY 4.0 license, with the exception of logos and branding of the European Mathematical Society and EMS Press, and where otherwise noted.

Back to Issue 127

[bib-bib1] D. Adil, B. Bullins, A. Jambulapati and S. Sachdeva, Line search-free methods for higher-order smooth monotone variational inequalities, preprint, arXiv:2205.06167 (2022)

[bib-bib2] A. Alacaoglu and Y. Malitsky, Stochastic variance reduction for variational inequality methods, preprint, arXiv:2102.08352 (2021)

[bib-bib3] A. Alacaoglu, Y. Malitsky and V. Cevher, Forward-reflected-backward method with variance reduction. Comput. Optim. Appl. 80, 321–346 (2021)

[bib-bib4] M. S. Alkousa, A. V. Gasnikov, D. M. Dvinskikh, D. A. Kovalev and F. S. Stonyakin, Accelerated methods for saddle-point problem. Comput. Math. Math. Phys. 60, 1787–1809 (2020)

[bib-bib5] K. Antonakopoulos, E. V. Belmega and P. Mertikopoulos, Adaptive extra-gradient methods for min-max optimization and games, preprint, arXiv:2010.12100 (2020)

[bib-bib6] K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming. Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford (1958)

[bib-bib7] W. Azizian, D. Scieur, I. Mitliagkas, S. Lacoste-Julien and G. Gidel, Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1705–1715 (2020)

[bib-bib8] F. Bach and K. Y. Levy, A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, Proc. Mach. Learn. Res., 164–194 (2019)

[bib-bib9] F. Bach, J. Mairal and J. Ponce, Convex sparse matrix factorizations, preprint, arXiv:0812.1869 (2008)

[bib-bib10] A. Bakushinskii and B. Polyak, On the solution of variational inequalities. Sov. Math. Dokl. 15, 1705–1710 (1974)

[bib-bib11] A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust optimization. Princeton Ser. Appl. Math., Princeton University Press, Princeton (2009)

[bib-bib12] A. Beznosikov, A. Alanov, D. Kovalev, M. Takáč and A. Gasnikov, On scaled methods for saddle point problems, preprint, arXiv:2206.08303 (2022)

[bib-bib13] A. Beznosikov, P. Dvurechensky, A. Koloskova, V. Samokhin, S. U. Stich and A. Gasnikov, Decentralized local stochastic extra-gradient for variational inequalities, preprint, arXiv:2106.08315 (2021)

[bib-bib14] A. Beznosikov, A. Gasnikov, K. Zainulina, A. Maslovskiy and D. Pasechnyuk, A unified analysis of variational inequality methods: Variance reduction, sampling, quantization and coordinate descent, preprint, arXiv:2201.12206 (2022)

[bib-bib15] A. Beznosikov, E. Gorbunov, H. Berard and N. Loizou, Stochastic gradient descent-ascent: Unified theory and new efficient methods, preprint, arXiv:2202.07262 (2022)

[bib-bib16] A. Beznosikov, A. Rogozin, D. Kovalev and A. Gasnikov, Near-optimal decentralized algorithms for saddle point problems over time-varying networks. In Optimization and applications, Lecture Notes in Comput. Sci. 13078, Springer, Cham, 246–257 (2021)

[bib-bib17] A. Beznosikov, V. Samokhin and A. Gasnikov, Distributed saddle-point problems: Lower bounds, optimal and robust algorithms, preprint arXiv:2010.13112 (2020)

[bib-bib18] A. Beznosikov, G. Scutari, A. Rogozin and A. Gasnikov, Distributed saddle-point problems under data similarity. Adv. Neural Inf. Process. Syst. 34, 8172–8184 (2021)

[bib-bib19] F. E. Browder, Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. U.S.A. 56, 1080–1086 (1966)

[bib-bib20] X. Cai, C. Song, C. Guzmán and J. Diakonikolas, A stochastic halpern iteration with variance reduction for stochastic monotone inclusion problems, preprint, arXiv:2203.09436 (2022)

[bib-bib21] Y. Carmon, Y. Jin, A. Sidford and K. Tian, Coordinate methods for matrix games. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, 283–293 (2020)

[bib-bib22] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40, 120–145 (2011)

[bib-bib23] Y. Carmon, D. Hausler, A. Jambulapati, Y. Jin and A. Sidford, Optimal and adaptive Monteiro–Svaiter acceleration, preprint, arXiv:2205.15371 (2022)

[bib-bib24] Y. Carmon, A. Jambulapati, Y. Jin and A. Sidford, Recapp: Crafting a more efficient catalyst for convex optimization. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 2658–2685 (2022)

[bib-bib25] Y. Carmon, Y. Jin, A. Sidford and K. Tian, Variance reduction for matrix games, preprint, arXiv:1907.02056 (2019)

[bib-bib26] T. Chavdarova, G. Gidel, F. Fleuret and S. Lacoste-Julien, Reducing noise in GAN training with variance reduced extragradient. Adv. Neural Inf. Process. Syst. 32, 393–403 (2019)

[bib-bib27] L. Chen and L. Luo, Near-optimal algorithms for making the gradient small in stochastic minimax optimization, preprint, arXiv:2208.05925 (2022)

[bib-bib28] M. B. Cohen, A. Sidford and K. Tian, Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 185, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Article No. 62, (2021)

[bib-bib29] A. Defazio, F. Bach and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Adv. Neural Inf. Process. Syst. 27, 1646–1654 (2014)

[bib-bib30] J. Diakonikolas and P. Wang, Potential function-based framework for minimizing gradients in convex and min-max optimization. SIAM J. Optim. 32, 1668–1697 (2022)

[bib-bib31] Z. Dou and Y. Li, On the one-sided convergence of Adam-type algorithms in non-convex non-concave min-max optimization, preprint, arXiv:2109.14213 (2021)

[bib-bib32] S. S. Du, G. Gidel, M. I. Jordan and C. J. Li, Optimal extragradient-based bilinearly-coupled saddle-point optimization, preprint, arXiv:2206.08573 (2022)

[bib-bib33] J. Duchi, E. Hazan and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12, 2121–2159 (2011)

[bib-bib34] A. Ene and H. L. Nguyen, Adaptive and universal algorithms for variational inequalities with optimal convergence. In Proceedings of the AAAI Conference on Artificial Intelligence, 36, 6559–6567 (2022)

[bib-bib35] A. Ene, H. L. Nguyen and A. Vladu, Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, 35, 7314–7321 (2021)

[bib-bib36] E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015–1046 (2010)

[bib-bib37] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research, Springer, New York (2003)

[bib-bib38] D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan and B. Woodworth, The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1319–1345 (2019)

[bib-bib39] A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck et al., Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. In Conference on Learning Theory, Proc. Mach. Learn. Res., 1392–1393 (2019)

[bib-bib40] A. V. Gasnikov, P. E. Dvurechensky, F. S. Stonyakin and A. A. Titov, An adaptive proximal method for variational inequalities. Comput. Math. Math. Phys. 59, 836–841 (2019)

[bib-bib41] G. Gidel, H. Berard, G. Vignoud, P. Vincent and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, preprint, arXiv:1802.10551 (2018)

[bib-bib42] G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang, S. Lacoste-Julien and I. Mitliagkas, Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1802–1811 (2019)

[bib-bib43] E. Gladin, I. Kuruzov, F. Stonyakin, D. Pasechnyuk, M. Alkousa and A. Gasnikov, Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables, preprint, arXiv:2010.02280 (2022)

[bib-bib44] E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov and M. Alkousa, Solving smooth min-min and min-max problems by mixed oracle algorithms. In Mathematical Optimization Theory and Operations Research—Recent Trends, Commun. Comput. Inf. Sci. 1476, Springer, Cham, 19–40 (2021)

[bib-bib45] E. G. Gol’šteĭn, Convergence of the gradient method for finding the saddle points of modified Lagrangian functions. Èkonom. i Mat. Metody 13, 322–329 (1977)

[bib-bib46] I. Goodfellow, Y. Bengio and A. Courville, Deep learning. Adaptive Computation and Machine Learning, MIT Press, Cambridge (2016)

[bib-bib47] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville and Y. Bengio, Generative adversarial networks. Commun. ACM 63, 139–144 (2020)

[bib-bib48] E. Gorbunov, H. Berard, G. Gidel and N. Loizou, Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7865–7901 (2022)

[bib-bib49] E. Gorbunov, M. Danilova, D. Dobre, P. Dvurechensky, A. Gasnikov and G. Gidel, Clipped stochastic methods for variational inequalities with heavy-tailed noise, preprint, arXiv:2206.01095 (2022)

[bib-bib50] E. Gorbunov, M. Danilova and A. Gasnikov, Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Adv. Neural Inf. Process. Syst. 33, 15042–15053 (2020)

[bib-bib51] E. Gorbunov, F. Hanzely and P. Richtárik, A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 680–690 (2020)

[bib-bib52] R. M. Gower, N. Loizou, X. Qian, A. Sailanbayev, E. Shulgin and P. Richtárik, SGD: General analysis and improved rates. In Proceedings of the 36th International Conference on Machine Learning, Proc. Mach. Learn. Res. 97, 5200–5209 (2019)

[bib-bib53] Y. Han, G. Xie and Z. Zhang, Lower complexity bounds of finite-sum optimization problems: The results and construction, preprint, arXiv:2103.08280 (2021)

[bib-bib54] Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, On the convergence of single-call stochastic extra-gradient methods. Adv. Neural Inf. Process. Syst. 32, 6938–6948 (2019)

[bib-bib55] Y.-G. Hsieh, F. Iutzeler, J. Malick and P. Mertikopoulos, Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Adv. Neural Inf. Process. Syst. 33, 16223–16234 (2020)

[bib-bib56] A. Ibrahim, W. Azizian, G. Gidel and I. Mitliagkas, Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 4583–4593 (2020)

[bib-bib57] Y. Jin and A. Sidford, Efficiently solving MDPs with stochastic mirror descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 119, 4890–4900 (2020)

[bib-bib58] Y. Jin, A. Sidford and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, preprint, arXiv:2202.04640 (2022)

[bib-bib59] R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural Inf. Process. Syst. 26, 315–323 (2013)

[bib-bib60] A. Juditsky, A. Nemirovski and C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1, 17–58 (2011)

[bib-bib61] E. N. Khobotov, Modification of the extra-gradient method for solving variational inequalities and certain optimization problems. U.S.S.R. Comput. Math. Math. Phys. 27, 120–127 (1987)

[bib-bib62] D. Kim and J. A. Fessler, Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. J. Optim. Theory Appl. 188, 192–219 (2021)

[bib-bib63] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2305–2313 (2015)

[bib-bib64] G. M. Korpelevič, An extragradient method for finding saddle points and for other problems. Èkonom. i Mat. Metody 12, 747–756 (1976)

[bib-bib65] G. M. Korpelevich, Extrapolation gradient methods and their relation to modified Lagrange functions. Èkonom. i Mat. Metody 19, 694–703 (1983)

[bib-bib66] G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. I: Operator extrapolation. SIAM J. Optim. 32, 2041–2073 (2022)

[bib-bib67] G. Kotsalis, G. Lan and T. Li, Simple and optimal methods for stochastic variational inequalities. II: Markovian noise and policy evaluation in reinforcement learning. SIAM J. Optim. 32, 1120–1155 (2022)

[bib-bib68] D. Kovalev, A. Beznosikov, E. Borodich, A. Gasnikov and G. Scutari, Optimal gradient sliding and its application to distributed optimization under similarity, preprint, arXiv:2205.15136 (2022)

[bib-bib69] D. Kovalev, A. Beznosikov, A. Sadiev, M. Persiianov, P. Richtárik and A. Gasnikov, Optimal algorithms for decentralized stochastic variational inequalities, preprint, arXiv:2202.02771 (2022)

[bib-bib70] D. Kovalev and A. Gasnikov, The first optimal acceleration of high-order methods in smooth convex optimization, preprint, arXiv:2205.09647 (2022)

[bib-bib71] D. Kovalev and A. Gasnikov, The first optimal algorithm for smooth and strongly-convex-strongly-concave minimax optimization, preprint, arXiv:2205.05653 (2022)

[bib-bib72] D. Kovalev, A. Gasnikov and P. Richtárik, Accelerated primal-dual gradient method for smooth and convex-concave saddle-point problems with bilinear coupling, preprint, arXiv:2112.15199 (2021)

[bib-bib73] D. Kovalev, S. Horváth and P. Richtárik, Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, edited by A. Kontorovich and G. Neu, Proc. Mach. Learn. Res. 117, 451–467 (2020)

[bib-bib74] S. Lee and D. Kim, Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems. Adv. Neural Inf. Process. Syst. 34, 22588–22600 (2021)

[bib-bib75] D. Lin, H. Ye and Z. Zhang, Explicit superlinear convergence rates of Broyden’s methods in nonlinear equations, preprint, arXiv:2109.01974 (2021)

[bib-bib76] H. Lin, J. Mairal and Z. Harchaoui, A universal catalyst for first-order optimization. Adv. Neural Inf. Process. Syst. 28, 3384–3392 (2015)

[bib-bib77] T. Lin, C. Jin and M. I. Jordan, Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, Proc. Mach. Learn. Res., 2738–2779 (2020)

[bib-bib78] T. Lin, M. Jordan et al., Perseus: A simple high-order regularization method for variational inequalities, preprint, arXiv:2205.03202 (2022)

[bib-bib79] C. Liu and L. Luo, Quasi-Newton methods for saddle point problems, preprint, arXiv:2111.02708 (2021)

[bib-bib80] M. Liu, Y. Mroueh, J. Ross, W. Zhang, X. Cui, P. Das and T. Yang, Towards better understanding of adaptive gradient algorithms in generative adversarial nets, preprint, arXiv:1912.11940 (2019)

[bib-bib81] N. Loizou, H. Berard, G. Gidel, I. Mitliagkas and S. Lacoste-Julien, Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Adv. Neural Inf. Process. Syst. 34, 19095–19108 (2021)

[bib-bib82] L. Luo, G. Xie, T. Zhang and Z. Zhang, Near optimal stochastic algorithms for finite-sum unbalanced convex-concave minimax optimization, preprint, arXiv:2106.01761 (2021)

[bib-bib83] Y. Malitsky and M. K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30, 1451–1472 (2020)

[bib-bib84] B. Martinet, Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4, 154–158 (1970)

[bib-bib85] D. Metelev, A. Rogozin, A. Gasnikov and D. Kovalev, Decentralized saddle-point problems with different constants of strong convexity and strong concavity, preprint, arXiv:2206.00090 (2022)

[bib-bib86] K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtárik and Y. Malitsky, Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 4573–4582 (2020)

[bib-bib87] A. Mokhtari, A. Ozdaglar and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 1497–1507 (2020)

[bib-bib88] R. D. C. Monteiro and B. F. Svaiter, Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM J. Optim. 22, 914–935 (2012)

[bib-bib89] R. D. C. Monteiro and B. F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23, 1092–1125 (2013)

[bib-bib90] S. Mukherjee and M. Chakraborty, A decentralized algorithm for large scale min-max problems. In 2020 59th IEEE Conference on Decision and Control (CDC), 2967–2972 (2020)

[bib-bib91] A. Nemirovski, Efficient methods in convex programming. Lecture notes, https://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf (1994)

[bib-bib92] A. Nemirovski, Prox-method with rate of convergence O⁢(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2004)

[bib-bib93] Y. Nesterov, Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)

[bib-bib94] Y. Nesterov, Cubic regularization of Newton’s method for convex problems with constraints. CORE Discussion Paper No. 2006/39, https://ssrn.com/abstract=921825 (2006)

[bib-bib95] Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109, 319–344 (2007)

[bib-bib96] Y. Nesterov, How to make the gradients small. Optima. Mathematical Optimization Society Newsletter 88, 10–11 (2012)

[bib-bib97] Y. Nesterov, Implementable tensor methods in unconstrained convex optimization. Math. Program. 186, 157–183 (2021)

[bib-bib98] Y. Nesterov, A. Gasnikov, S. Guminov and P. Dvurechensky, Primal-dual accelerated gradient methods with small-dimensional relaxation oracle. Optim. Methods Softw. 36, 773–810 (2021)

[bib-bib99] Y. Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance. Math. Program. 108, 177–205 (2006)

[bib-bib100] S. Omidshafiei, J. Pazis, C. Amato, J. P. How and J. Vian, Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proceedings of the 34th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 70, 2681–2690 (2017)

[bib-bib101] Y. Ouyang and Y. Xu, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Program. 185, 1–35 (2021)

[bib-bib102] B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems. Adv. Neural Inf. Process. Syst., 1416–1424 (2016)

[bib-bib103] R. Pascanu, T. Mikolov and Y. Bengio, On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, 1310–1318 (2013)

[bib-bib104] B. T. Polyak, Introduction to optimization. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York (1987)

[bib-bib105] L. D. Popov, A modification of the Arrow–Hurwicz method for search of saddle points. Math. Notes 28, 845–848 (1981)

[bib-bib106] R. T. Rockafellar, Convex functions, monotone operators and variational inequalities. In Theory and Applications of Monotone Operators (Proc. NATO Advanced Study Inst., Venice, 1968), Edizioni “Oderisi”, Gubbio, 35–65 (1969)

[bib-bib107] R. T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)

[bib-bib108] A. Rogozin, A. Beznosikov, D. Dvinskikh, D. Kovalev, P. Dvurechensky and A. Gasnikov, Decentralized distributed optimization for saddle point problems, preprint, arXiv:2102.07758 (2021)

[bib-bib109] A. Sadiev, D. Kovalev and P. Richtárik, Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with inexact prox. arXiv:2207.03957 (2022)

[bib-bib110] M. Sibony, Méthodes itératives pour les équations et inéquations aux dérivées partielles non linéaires de type monotone. Calcolo 7, 65–183 (1970)

[bib-bib111] C. Song, C. Y. Lin, S. J. Wright and J. Diakonikolas, Coordinate linear variance reduction for generalized linear programming, preprint, arXiv:2111.01842 (2021)

[bib-bib112] C. Song, S. J. Wright and J. Diakonikolas, Variance reduction via primal-dual accelerated dual averaging for nonsmooth convex finite-sums. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 9824–9834 (2021)

[bib-bib113] G. Stampacchia, Formes bilinéaires coercitives sur les ensembles convexes. C. R. Acad. Sci. Paris 258, 4413–4416 (1964)

[bib-bib114] F. Stonyakin, A. Gasnikov, P. Dvurechensky, A. Titov and M. Alkousa, Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle. J. Optim. Theory Appl. 194, 988–1013 (2022)

[bib-bib115] F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov and V. Piskunova, Inexact model: A framework for optimization and variational inequalities. Optim. Methods Softw. 36, 1155–1201 (2021)

[bib-bib116] K. K. Thekumparampil, N. He and S. Oh, Lifted primal-dual method for bilinearly coupled smooth minimax optimization, preprint, arXiv:2201.07427 (2022)

[bib-bib117] A. A. Titov, S. S. Ablaev, M. S. Alkousa, F. S. Stonyakin and A. V. Gasnikov, Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness, preprint, arXiv:2207.09544 (2022)

[bib-bib118] V. Tominin, Y. Tominin, E. Borodich, D. Kovalev, A. Gasnikov and P. Dvurechensky, On accelerated methods for saddle-point problems with composite structure, preprint, arXiv:2103.09344 (2021)

[bib-bib119] P. Tseng, On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60, 237–252 (1995)

[bib-bib120] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38, 431–446 (2000)

[bib-bib121] H. Ye, D. Lin and Z. Zhang, Greedy and random Broyden’s methods with explicit superlinear convergence rates in nonlinear equations, preprint, arXiv:2110.08572 (2021)

[bib-bib122] T. Yoon and E. K. Ryu, Accelerated algorithms for smooth convex-concave minimax problems with o⁢(1/k2) rate on squared gradient norm. In International Conference on Machine Learning, Proc. Mach. Learn. Res., 12098–12109 (2021)

[bib-bib123] G. Zhang, Y. Wang, L. Lessard and R. B. Grosse, Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res., 7659–7679 (2022)

[bib-bib124] J. Zhang, M. Hong and S. Zhang, On lower iteration complexity bounds for the convex concave saddle point problems. Math. Program. 194, 901–935 (2022)

[bib-bib125] X. Zhang, N. S. Aybat and M. Gurbuzbalaban, Robust accelerated primal-dual methods for computing saddle points, preprint, arXiv:2111.12743 (2021)