Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems – Survey

In its long, more than half-century history of study [112], 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 classic examples from game theory, economics, operator theory, convex analysis [6, 18, 106, 109, 112], as well as newer and even very young applications in optimization and machine learning: non-smooth optimization [92], unsupervised learning [8, 35, 24], robust/adversarial optimization [10], GANs [46] and reinforcement learning [99, 56]. Modern times present a new challenges to the community. The increase in scale of problems and the desire to speed up solution processes have led to a huge interest in stochastic formulations of applied tasks, including variational inequalities. A survey of stochastic methods for solving variational inequalities is the subject of this paper.

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 been developed. Section 4 covers the stochastic methods. Section 5 is devoted to the recent advances in (not necessarily stochastic) variational inequalities and saddle point problems.

Notation. We use $⟨x,y⟩\text{vcentcolon}={\sum }_{i=1}^n{x}_i{y}_i$ to denote standard inner product of $x,y\in R^d$ where $x_i$ corresponds to the $i$-th component of $x$ in the standard basis in $R^d$. It induces ${\ell }_2$-norm in $R^d$ in the following way $\parallel x{\parallel }_2\text{vcentcolon}=\sqrt{⟨x,x⟩}$. We denote ${\ell }_p$-norms as $\parallel x{\parallel }_p\text{vcentcolon}={\left({\sum }_{i=1}^d|x_i{|}^p\right)}^{\text{nicefrac}1p}$ for $p\in [1,\infty )$ and for $p=\infty$ we use $\parallel x{\parallel }_{\infty }\text{vcentcolon}={max}_{1\le i\le d}|x_i|$. The dual norm $\parallel \cdot {\parallel }_{\ast }$ for the norm $\parallel \cdot \parallel$ is defined in the following way: $\parallel y{\parallel }_{\ast }\text{vcentcolon}=max\{⟨x,y⟩\mid \parallel x\parallel \le 1\}$. Operator $E[\cdot ]$ denotes full mathematical expectation. Finally, we need to introduce $O,\Omega$-notation to hide numerical constants which do not depend on any problem parameter, and notation $\tilde{O},\tilde{\Omega }$ to hide numerical constants and logarithmic factors.

We study variational inequalities (VI) of the form

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

To emphasise the extensiveness of the formalism (1), we give some examples of variational inequalities arising in applied science.

[Minimization] Consider the minimization problem:

Suppose that $F\left(z\right)\text{vcentcolon}=\nabla f\left(z\right)$. Then, if $f$ is convex, it can be proved that $z^{\ast }\in Z$ is a solution for (1) if and only if $z^{\ast }\in Z$ is a solution for (2).

[Saddle point problem] Consider the saddle point problem (SPP):

Suppose that $F\left(z\right)\text{vcentcolon}=F(x,y)=\left[{\nabla }_{x}g\right(x,y),-{\nabla }_{y}g(x,y\left)\right]$ and $Z=X\times Y$ with $X\subseteq R^{d_x}$, $Y\subseteq R^{d_y}$. Then, if $g$ is convex-concave, it can be proved that $z^{\ast }\in Z$ is a solution for (1) if and only if $z^{\ast }\in Z$ is a solution for (3).

Minimization problems are widely researched separately from variational inequalities. The study of saddle point problems is often associated with variational inequalities.

[Fixed point problem] Consider the fixed point problem:

where $T:R^d\to R^d$ is an operator. With $F\left(z\right)=z-T\left(z\right)$, it can be proved that $z^{\ast }\in Z=R^d$ is a solution for (1) if and only if $F\left(z^{\ast }\right)=0$, i.e. $z^{\ast }\in R^d$ is a solution for (4).

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

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

In the context of (2) and (3), strong monotonicity of $F$ means strong convexity of $f\left(z\right)$ and strong convexity-strong concavity of $g(x,y)$. In this paper we first concentrate on the strongly monotone and monotone cases. But there are also various assumptions relaxing monotonicity and strong monotonicity (e.g., see [54] and references therein).

One can point out that Assumptions 1 and 2 are sufficient for the existence of a solution (1) [36].

Since we work on the set $Z$, let us introduce the Euclidean projection on this set:

To characterise the convergence of the methods for monotone variational inequalities we introduce the gap function:

Such a gap function, as a convergence criterion, is more suitable for the following variational inequality problem: $⟨F\left(z\right),z^{\ast }-z⟩\le 0$ for $z\in Z$. Such a solution is also called weak or Minty (the solution of (1) is called strong or Stampacchia). However, according to Assumption 1 we have that $F$ is single-valued and continuous on $Z$, meaning that both formulations of the variational inequality problem are equivalent [36].

For the minimization problem (2), the functional distance to the solution: $f\left(z\right)-f\left(z^{\ast }\right)$, can be used instead of (5). For saddle point problems (3), the gap function is also used, but it is slightly different:

For both functions (5) and (6), it is critical that the set over which this function is calculated is bounded (in fact it is not necessary to take the whole set $Z$ which can be unbounded, it is enough to take a bounded convex subset $C$ which contains some solution – see [94]). Therefore it is necessary to define a distance on the set $Z$. Since in this survey we will encounter methods not only in the Euclidean setup, let us introduce a more general notion of distance.

[Bregman divergence] Assume that function $\nu \left(z\right)$ is $1$-strongly convex w.r.t. $\parallel \cdot \parallel$-norm and differentiable on $Z$ function. Then for any two points $z,z^{\prime }\in Z$ we define Bregman divergence $V(z,z^{\prime })$ associated with $\nu \left(z\right)$ as follows:

We denote the Bregman-diameter of the set $Z$ w.r.t. $V(z,z^{\prime })$ as $D_{Z,V}\text{vcentcolon}=max\{\sqrt{2V(z,z^{\prime })}\mid z,z^{\prime }\in Z\}$. In the Euclidean case, we use $D_Z$ instead of $D_{Z,V}$. Using the definition of $V$, we denote the proximal operator as follows:

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

where $\gamma >0$ is a step size. Note that this method can be rewritten using the proximal operator with the Euclidean Bregman divergence:

The basic result is the convergence of the method to the unique solution of (1) for strongly monotone and $L$-Lipschitz operator $F$; it was obtained in the papers [18, 106, 109].

If Assumptions 1, 2 hold and $0<\gamma <2\mu /L^2$, then after $k$ iterations the method (7) converges to $z^{\ast }$ with linear rate:

and $R_0=\parallel z^0-z^{\ast }{\parallel }_2$ (here and below). For $\gamma =\mu /L^2$ we have $q=(1-1/{\kappa }^2),\kappa =L/\mu$, thus the upper bound on the number of iterations to achieve the $\epsilon$-solution (i.e., $\parallel z^k-z^{\ast }{\parallel }_2^2\le \epsilon$) is $O\left({\kappa }^2\log \right(R_0^2/\epsilon \left)\right)$.

Various extensions of this statement (for $F$ being non-Lip-
schitz but with linear grow bounds, or for values of $F$ corrupted by noise) can be found in Theorem 1 from [9].

If $F$ is a potential operator (see Example 2) the method (7) coincides with the gradient projection algorithm. It converges for strongly monotone $F$. Moreover, bounds for the admissible step size are less restrictive ($0<\gamma <2/L$) and complexity estimates are better ($O\left(\kappa \log \right(R_0^2/\epsilon \left)\right)$) than in Theorem 3.

However, in the general monotone but non-strongly monotone case (for instance, for convex-concave SPP, Example 2) convergence is lacking. Original statements on the convergence of Uzava method (a version of (7)) for saddle point problems [6] were wrong; numerous examples of divergence of the method (7) for $F$ corresponding to bilinear SPP are well known, see e.g. Figure 39 from [103].

There were many other attempts to recover 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 Lagrange function, see [44, 103]. However, we focus on general VI case. A possible approach is based on regularization idea. Instead of the monotone variational inequality (1) one can deal with the regularized one, when monotone $F$ is replaced with strongly monotone $F+{\epsilon }_{k}T$, where $T\left(z\right)$ is a strongly monotone operator and ${\epsilon }_k>0$ is a regularization parameter. If we denote $z^k$ as the solution of regularized VI, then it is possible to prove [9] that $z^k$ converges to $z^{\ast }$ for ${\epsilon }_k\to 0$. However, the solution $z^k$ usually is not easily available. To adress this problem, the iterative regularization technique is proposed in [9], where one step of the basic method (7) is applied for the regularized problem. Step sizes and regularization parameters can be adjusted to guarantee the convergence.

Another technique is based on the Proximal Point method proposed independently by B. Martinet in [83] and by T. Rockafellar in [105]. At each iteration it requires the solution of VI with $F+cI$, where $c>0$ and $I$ is the identity operator. This is implicit method (similar with regularization method), however there exist numerous implementable versions of Proximal Point. For instance, some methods below can be considered from this point of view.

The breakthrough for solving (non-strongly) monotone variational inequalities was made by Galina Korpelevich [63]. She exploited the idea of the extrapolation for the gradient method. It can be explained for the simplest example of a two-dimensi-
onal min-max problem with $g(x,y)=xy,Z=R^2$. It has the unique saddle point $z=0$, and in any point $z^k$ the direction $F\left(z^k\right)$ is orthogonal to $z^k$; thus the iteration (7) enlarges the distance to the saddle point. However, if we make the step (7) and get extrapolated point $z^{k+1/2}$, the direction $-F\left(z^{k+1/2}\right)$ is attracting to the saddle point. Thus, the Extragradient method for solving (1) reads:

{theorem}

Let $F$ satisfy Assumptions 1, 2 (with $\mu =0$) and $0<\gamma <1/L$, then for the Extragradient method $z^k\to z^{\ast }$.

For particular case of the zero-sum matrix game the method converges linearly, provided that the optimal solution is unique (see Theorem 3 from [63]). For $g(x,y)=y^{\top }Ax-b^{\top }x+c^{\top }y$ the following estimate holds: $O\left(\kappa \log \right(R_0^2/\epsilon \left)\right)$ with $\kappa ={\lambda }_{max}\left(A{A}^{\top }\right)/{\lambda }_{min}\left(A{A}^{\top }\right)$. More general upper bounds for the Extragradient method can be found in [118] and in the recent paper [86]. In particular, for the strongly monotone case the estimate $O\left(\kappa \log \right(R_0^2/\epsilon \left)\right)$ with $\kappa =L/\mu$ holds true (compare with much worse bound $O\left({\kappa }^2\log \right(R_0^2/\epsilon \left)\right)$ for Gradient method). Adaptive version of the Extragradient method (no knowledge of $L$ required) is proposed in [60].

Another version of the Extragradient method for finding saddle points is provided in [64]. Considering the setup of Example 2, we can exploit just one extrapolating step for variables $y$:

with $0<\gamma <1/2L$ and $0<q<1$. This method converges to the solution and if $g(x,y)$ is linear in $y$, then the convergence rate is linear. If we put $q=1$ in the method (3), then $y^{k+1}=y^{k+1/2}$ and we get the so-called Alternating Gradient method (Alternating descent-ascent). In [122], it was proved that this method has local linear convergence with complexity $O\left(\kappa \log \right(R_0^2/\epsilon \left)\right)$, where $\kappa =L/\mu$.

L. Popov [104] proposed a version of extrapolation scheme (sometimes this type of scheme is called optimistic or single-call):

It requires the single calculation of $F$ at each iteration vs two calculations in the Extragradient method. As shown in [104], the method (10) converges for $0<\gamma <1/3L$. Convergence rates for this method were obtained recently [40, 86], it is $O\left(\kappa \log \right(R_0^2/\epsilon \left)\right)$ with $\kappa =L/\mu$ for the strongly monotone case and $\kappa ={\lambda }_{max}\left(A{A}^{\top }\right)/{\lambda }_{min}\left(A{A}^{\top }\right)$ for the bilinear case. It is important to note that in the general strongly monotone case this estimate is optimal [123].

The extension of the above schemes to an arbitrary proximal setup was obtained in the work of A. Nemirovsky [91]. He proposed the Mirror-Prox method for VIs, exploiting Bregman divergence:

It implies the following result on the convergence rate. {theorem} Let $F$ satisfy Assumptions 1, 2 (with $\mu =0$) and

where $z^{i+1/2}$ are generated by algorithm (11) with $\gamma =1/\sqrt{2}L$. Then, after $k$ iterations

Numerous extensions of these original versions of iterative methods for solving variational inequalities were published later. One can highlight Tseng’s Forward-Backward Splitting [119], Nesterov’s Dual Extrapolation [94], Malitsky and Tam’s Forward-Reflected-Backward [82]. All methods have convergence guarantees (13). It turns out that this rate is optimal [100].

In this section, we move from deterministic to stochastic methods, i.e., we consider (1) with the following operator:

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