Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems

Introduction

In recent years, min-max problems have received significant attention across the optimization and machine learning communities due to their applications in training generative adversarial networks (GANs) , training machine learning models that are robust to adversarial attacks , reinforcement learning , fair statistical inference , and distributed non-convex optimization , to name a few. These applications involve solving optimization problems in the general form

where $F$ is a smooth objective function and $X,Y$ is a pair of convex sets in the corresponding Euclidean spaces $\mathcal{X},\mathcal{Y}$. When the objective is convex in $x$ and concave in $y$, 1 is well-studied. In this case, the corresponding variational inequality is monotone, and there is a number of efficient algorithms known for solving it, even at the optimal rate (see, e.g., , , ). However, many of the applications discussed above involve an objective $F$ that is nonconvex in $x$ and not necessarily concave in $y$, which makes the problem much harder to solve. In fact, even Nash equilibria are not guaranteed to exist in 1 in this general nonconvex-nonconcave setting.

In this work, we study (1) under the assumption that $F(x,y)$ is concave in $y$ but do not assume convexity $x$. To the best of our knowledge, was the first work providing non-asymptotic convergence rates for nonconvex-concave problems without assuming special structure of the objective function. They use the notion of $\varepsilon$-first order Nash equilibrium (FNE) to measure the rate of convergence of their algorithm. This notion looks at the min-max problem as a two-player zero-sum game and uses the first-order optimality condition with respect to each variable as the optimality measure. Using this notion, they showed that their algorithm finds an $\varepsilon$-first-order Nash equilibrium in $O({\varepsilon}^{-3.5})$ gradient evaluations. In this work, we use a similar optimality notion to the one in ; however, in order to measure the optimality w.r.t. the $x,y$ variables separately, we generalize their notion to $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-first order stationarity. Therefore, by setting $\varepsilon_{\textsf{{x}}}=\varepsilon_{\textsf{{y}}}=\varepsilon$, we obtain the optimality measure used in . Using the defined first order stationarity measure, we propose an algorithm that can find $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-first order stationary point in $O({\varepsilon_{\textsf{{x}}}}^{-2}{\varepsilon_{\textsf{{y}}}}^{-1/2})$ gradient evaluations.

Another way to measure the convergence rate of an algorithm for solving (1) is to define the primal function $\varphi(x)=\max_{y\in Y}F(x,y)$, and measure the first-order optimality in terms of the nonconvex problem $\min_{x\in X}\varphi(x)$. In this context, a commonly used inaccuracy measure for a candidate solution $\widehat{x}$ is the gradient norm of the standard Moreau envelope of the primal function (see Section 5 for more details). Using this viewpoint, subtle analyses have been provided in , and more recently, in the concurrent work whose preprint was announced a few days prior to ours. More recently, a similar approach has been used in . The underlying idea in all these works, as well as in ours, is to obtain the next iterate $(x_{t+1},y_{t+1})$ by approximately solving a strongly-convex-concave saddle-point problem

where $L_{{\textsf{{x}}}{\textsf{{x}}}}$ is the uniform over $y\in Y$ bound on the Lipschitz constant of $\nabla_{\textsf{{x}}}F(\cdot,y)$. Yet, there are notable differences between all these works, which we shall now discuss.

The work focuses on the problem of finding an $\varepsilon_{\textsf{{x}}}$-stationary point of the Moreau envelope $\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(x):=\min_{x^{\prime}\in X}[\varphi(x^{\prime})+L_{{\textsf{{x}}}{\textsf{{x}}}}\|x^{\prime}-x\|^{2}]$. To achieve this goal, they solve 2 up to accuracy $\epsilon$ in objective value. The resulting scheme produces a point $\widehat{x}$ satisfying $\|\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|\leqslant\varepsilon_{\textsf{{x}}}$ in $O(\varepsilon_{\textsf{{x}}}^{3})$ oracle calls, provided that one takes $\epsilon=O(\varepsilon_{\textsf{{x}}}^{2})$. However, they only handle the case $X=\mathcal{X}$ and do not provide an algorithm to reach an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE for general $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$; modifying their scheme correspondingly might be challenging because of $Y\neq\mathcal{Y}$. (Our discussions in Section 5 shed some light on such intricacies). Moreover, their proposed algorithm is way less transparent than ours: it comprises an extragradient-type scheme as well as Nesterov’s acceleration, whereas our approach is based solely on the analysis of Fast Gradient Method (FGM) a version of Nesterov’s accelerated algorithm, and uses the readily available results for inexact-oracle FGM due to .

The approach in the concurrent work more closely resembles ours. In particular, their scheme also avoids using an extragradient-type subroutine, and produces an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in $O(\varepsilon_{\textsf{{x}}}{}^{-2}\varepsilon_{\textsf{{y}}}{}^{-1/2})$ oracle calls; setting $\varepsilon_{\textsf{{y}}}=O(\varepsilon_{\textsf{{x}}}^{2})$ then allows to recover the $O(\varepsilon_{\textsf{{x}}}^{-3})$ result for the Moreau envelope. However, they use the definition of $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE based on the proximal gradient norm, or the weak criterion in our terminology in Section 2 (cf. 6), whereas our scheme produces an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE with respect to the so-called strong criterion (cf. 5). As we discuss in 1, the latter task is more challenging: an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE with respect to the strong criterion is also such with respect to the weak criterion (hence the names); meanwhile, a guarantee on the weak criterion does not imply any guarantee on the strong one in the presense of constraints. Moreover, the $\varepsilon_{\textsf{{y}}}=O(\varepsilon_{\textsf{{x}}}^{2})$ reduction for the Moreau envelope in does not allow for $X\neq\mathcal{X}$ (same as in ). In addition, this reduction relies on the result [18, Prop. 4.12]; as we discuss in Section 5, this result seems to be invalid unless $Y=\mathcal{Y}$, which is irrelevant in the context of 1. We rectify both these issues in Section 5 through the delicate use of the strong criterion. It should be noted, however, that the authors of focus on the convex-concave scenario which we do not address here.

The work also establishes an $O(\varepsilon_{\textsf{{x}}}{}^{-2}\varepsilon_{\textsf{{y}}}{}^{-1/2})$ complexity to find an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-first-order stationary point; however, to the best of our understanding, their stationarity criterion is not directly comparable to ours nor to the one in . Setting $\varepsilon_{\textsf{{y}}}=O(\varepsilon_{\textsf{{x}}}^{2})$, the authors of obtain $O(\varepsilon_{\textsf{{x}}}^{-3})$ complexity result for the criterion similar to the gradient norm of the Moreau envelope, but slightly weaker (as follows by comparing [17, Eq. (2)] with the second claim of our Proposition 5.1). However, they assume direct access to the gradient of the smooth function $\max_{y\in Y}[F(x,y)-\lambda\|y\|^{2}]$, which is unrealistic (e.g., we solve a similar task via an FGM subroutine). This assumption has been removed in the recent work (that appeared some time after our work). Moreover, while only focuses on the primal accuracy measure (in the same sense as ), they address the general Bregman geometries (which we also do, see Appendix B). However, do not address the general $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-stationarity notion.

Finally, let us discuss the precursor work . In our terminlogy, shows an $O(\varepsilon_{\textsf{{x}}}{}^{-2}\varepsilon_{\textsf{{y}}}{}^{-3/2})$ complexity estimate to find an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE, using a notion of stationarity weaker than the one in (and thus a fortiori weaker than the one we use in the present work). The extra $\varepsilon_{\textsf{{y}}}^{-1}$ complexity factor compared to our result comes from using a more naive algorithmic approach: instead of forming an iterate sequence by solving 2, they proceed by running projected gradient descent on the smoothed primal function $\max_{y\in Y}[F(x,y)-\lambda_{{\textsf{{y}}}}\|y\|^{2}].$ Taking $\lambda=\varepsilon_{\textsf{{y}}}/R_{{\textsf{{y}}}}$ ensures that $\nabla_{\textsf{{y}}}[F(x,y)-\lambda_{{\textsf{{y}}}}\|y\|^{2}]\approx\nabla_{\textsf{{y}}}F(x,y)$ up to $O(\varepsilon_{\textsf{{y}}})$ error, which guarantees that $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE for the new problem is still valid for the initial one. However, gradient descent suffers from a poor smoothness of the smoothed primal function, whose gradient is only Lipschitz with modulus $L_{{\textsf{{x}}}{\textsf{{x}}}}+O(L_{{\textsf{{x}}}{\textsf{{y}}}}^{2}/\lambda_{{\textsf{{y}}}})=O(\varepsilon_{\textsf{{y}}}^{-1})$, which results in the final iteration complexity estimate $O(\varepsilon_{\textsf{{x}}}{}^{-2}\varepsilon_{\textsf{{y}}}{}^{-3/2})$.

Problem formulation and preview of the main result

We study the min-max problem 1 in the setting where $X,Y$ are convex and “projection-friendly” sets with non-empty interior in the corresponding Euclidean spaces $\mathcal{X},\mathcal{Y}$; moreover, $Y$ is contained in a Euclidean ball with radius $R_{{\textsf{{y}}}}<\infty$. The function $F:X\times Y\to\mathds{R}$ is concave in $y$ for all $x\in X$, and has Lipschitz gradient, namely, the inequalities

hold uniformly over $x,x^{\prime}\in X$ and $y,y^{\prime}\in Y$ with Lipschitz constants $L_{{\textsf{{x}}}{\textsf{{x}}}},L_{{\textsf{{y}}}{\textsf{{y}}}},L_{{\textsf{{x}}}{\textsf{{y}}}}$. Here and in what follows, $\|\cdot\|$ and $\left\langle\cdot,\cdot\right\rangle$ denote the standard Euclidean norm and inner product (regardless of the space), and $[\nabla_{\textsf{{x}}}F(x,y),\nabla_{\textsf{{y}}}F(x,y)]$ are the components of the full gradient $\nabla F(x,y)$. Instead of seeking an exact solution to (1), we focus on the more feasible task of finding an approximate first-order Nash equilibrium.

A point $(\widehat{x},\widehat{y})\in X\times Y$ is called $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-approximate first-order Nash equilibrium ($(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE) in the problem (1) if the following holds:

where the inaccuracy measure $\textsf{{S}}_{Z}$, with $Z$ being a convex subset of a Euclidean space $\mathcal{Z}$, is defined on triples $z,\zeta\in Z$, $L\geqslant 0$ as follows:

A more common stationarity measure in the context of constrained minimization of a convex function $f:Z\to\mathds{R}$ is the norm of the proximal gradient, that is $\textsf{{W}}_{Z}(\widehat{z},\nabla f(\widehat{z}),L):=L\left\|\widehat{z}-\Pi_{Z}\left[\widehat{z}-\tfrac{1}{L}\nabla f(\widehat{z})\right]\right\|,$ where $\Pi_{Z}(\cdot)$ is the operator of Euclidean projection onto $Z$ (see ), and we define the functional

for convenience. In the unconstrained case, both measures reduce to $\|\nabla f(\widehat{z})\|$. However, in the general constrained case $\textsf{{S}}_{Z}$ provides a stronger criterion, in the following sense:

For any $z,\zeta,L$ one has $\textsf{{W}}_{Z}(z,\zeta,L)\leqslant\textsf{{S}}_{Z}(z,\zeta,L)$; thus, any $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in the sense of Definition 2.1 is an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in the weak sense, i.e., $\textsf{{W}}_{X}(\widehat{x},\nabla_{\textsf{{x}}}F(\widehat{x},\widehat{y}),L_{{\textsf{{x}}}{\textsf{{x}}}})\leqslant\varepsilon_{\textsf{{x}}},\textsf{{W}}_{Y}(\widehat{y},-\nabla_{\textsf{{y}}}F(\widehat{x},\widehat{y}),L_{{\textsf{{y}}}{\textsf{{y}}}})\leqslant\varepsilon_{\textsf{{y}}}$. See [3, Thm. 4.3].

The converse is generally false (unless in the unconstrained case). In particular, in Section 5 (cf. 4) we exhibit a minimization problem in which $\textsf{{W}}_{Z}(\widehat{z},\nabla f(\widehat{z}),L)\leqslant\varepsilon$ at $\widehat{z}\in Z$, but $\textsf{{S}}_{Z}(\widehat{z},\nabla f(\widehat{z}),L)$ is arbitrarily large.

Our goal is to provide an efficient algorithm for finding $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNEExact FNE might not exist when $X$ is not compact; however $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE exists for all $\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}}>0$. given access to the full gradient oracle $\nabla F(x,y)$. Following the established trend in the literature, we assume the feasible sets $X,Y$ to be “projection-friendly”, i.e., Euclidean projection onto them can be done with a small computational effort; thus, the natural notion of efficiency is simply the number of gradient computations. Besides the two accuracies $\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}}$, the Lipschitz parameters $L_{{\textsf{{x}}}{\textsf{{x}}}},L_{{\textsf{{y}}}{\textsf{{y}}}},L_{{\textsf{{x}}}{\textsf{{y}}}}$, and the “radius” $R_{{\textsf{{y}}}}$ of $Y$, we need a parameter quantifying the hardness of the primal problem – that of minimizing

Since $X$ can be unbounded, the natural choice of such parameter is the primal gap $\Delta$,

where $x_{0}$ is the initial iterate. To give a concise and intuitive statement of our main result, it is helpful to define the “coupling-adjusted” counterpart $L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}$ of $L_{{\textsf{{y}}}{\textsf{{y}}}}$, defined as

as well as the unit-free quantities – the “complexity factors” $T_{\textsf{{x}}}$ and $T_{\textsf{{y}}}$ given by

Upon consulting the literature (e.g., ), we recognize $T_{\textsf{{x}}}$ as the iteration complexity of finding $\varepsilon_{\textsf{{x}}}$-stationary point (with respect to gradient norm) in the class of unconstrained minimization problems with $L_{{\textsf{{x}}}{\textsf{{x}}}}$-smooth (possibly nonconvex) objective and initial gap $\Delta$. On the other hand, we recognize $T_{\textsf{{y}}}$ as the tight complexity bound for the problem of finding $\varepsilon_{\textsf{{y}}}$-stationary point in the class of maximization problems with concave and $L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}$-smooth objective, given the initial point within $R_{{\textsf{{y}}}}$ distance of an optimum, using first-order information. (This bound is also tight in the constrained setup, with $\varepsilon_{\textsf{{y}}}$ bounding the proximal gradient norm.) We now state our main result.

There exists an algorithm that, given $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}},L_{{\textsf{{x}}}{\textsf{{x}}}},L_{{\textsf{{x}}}{\textsf{{y}}}},L_{{\textsf{{y}}}{\textsf{{y}}}},R_{{\textsf{{y}}}},\Delta)$, outputs $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE of the problem (1) in

computations of $\nabla F(x,y)$ and projections, where $\widetilde{O}(\cdot)$ hides logarithmic factors in $T_{\textsf{{x}}}^{\vphantom{+}},T_{\textsf{{y}}}$.

This result merits some comments. First, from 9-10 we see that the complexity of finding $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in the problem (1) can be viewed as the product of the “primal” complexity of finding an $\varepsilon_{\textsf{{x}}}$-stationary point of $F(\cdot,y)$ with fixed $y$, and the “dual” complexity of finding $\varepsilon_{\textsf{{y}}}$-stationary point of $\psi_{x}(\cdot)=\min_{x^{\prime}\in X}F(x^{\prime},\cdot)+L_{{\textsf{{x}}}{\textsf{{x}}}}\|x^{\prime}-x\|^{2}$ with fixed $x\in X$ on $R_{{\textsf{{y}}}}$. Note that $\psi_{x}(\cdot)$ has $L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}$-Lipschitz gradient by Danskin’s theorem (see and [29, Lem. 24]), and is associated with the standard Moreau envelope $\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(x):=\textstyle\min_{x^{\prime}\in X}[\varphi(x^{\prime})+L_{{\textsf{{x}}}{\textsf{{x}}}}\|x^{\prime}-x\|^{2}]$ of the primal function $\varphi(x)$ ().

Second, in Section 5 we prove that the primal component $\widehat{x}$ of an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE with $\varepsilon_{\textsf{{y}}}=\varepsilon_{\textsf{{x}}}^{2}/(L_{{\textsf{{x}}}{\textsf{{x}}}}R_{{\textsf{{y}}}})$ satisfies $\|\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|=O(\varepsilon_{\textsf{{x}}})$. In view of Theorem 2.2, this leads to the complexity $\widetilde{O}(\varepsilon_{\textsf{{x}}}^{-3})$ of finding an $\varepsilon_{\textsf{{x}}}$-stationary point for the standard Moreau envelope (see Section 5 for the rigorous result (cf. 76) and detailed discussion). Such a result is known from the recent literature in the case $X=\mathcal{X}$; moreover, as we discuss in Section 5, the result [18, Prop. 4.12] that is commonly used (in particular, in ) in order to reduce the Moreau envelope criterion to the criterion based on the norm of the proximal gradient (i.e., our weak criterion in 6) seems to be invalid when $Y\neq\mathcal{Y}$. Our results close these gaps by working with the strong criterion 5.

Third, our approach can be extended to composite objectives, e.g., by following . To keep the presentation simple, we avoid such extension here (see, e.g., ). On the other hand, extension to non-Euclidean geometries faces some non-trivial challenges that have not been properly addressed in the prior literature.A notable exception is the work that appeared shortly after the first version of this manuscript. In Appendix B we discuss these challenges and introduce the necessary adjustments into our framework.

Throughout the paper, and unless explicitly stated otherwise, $\|\cdot\|$ and $\left\langle\cdot,\cdot\right\rangle$ denote the standard Euclidean norm and inner product regardless of the (Euclidean) space. We let $[T]:=\{1,2,...,T\}$ for $T\in\mathds{N}$. $\log(\cdot)$ is the natural logarithm; $g=O(f)$ means that for any $z\in\text{Dom}(f)=\text{Dom}(g)$ one has $f(z)\leqslant Cg(z)$ with $C$ being a generic constant; $g=\widetilde{O}(f)$ means the same but with $C$ replaced by a poly-logarithmic factor in $g$. We write $\partial_{\textsf{{y}}}F(x(y),y)$ for the partial gradient in $y$ of $F(x(y),y)$ as a function of $y$; in other words, $\partial_{\textsf{{y}}}F(x(y),y)=\nabla_{\textsf{{y}}}F(x,y)$ with $x=x(y)$ substituted post-factum. We shall introduce additional notation when the need arises.

Building blocks and preliminaries

Given a convex set $Z$ in a Euclidean space $\mathcal{Z}$ and a pair $z,\zeta\in Z$, we define the prox-mapping

In what follows, we assume $\textup{prox}_{z,Z}(\zeta)$ to be computationally cheap. Note that in the unconstrained case with $Z=\mathcal{Z}$, one has $\textup{prox}_{z,Z}(\zeta)=z-\zeta$, whereas in the (general) constrained case one has $\textup{prox}_{z,Z}(\zeta)=\Pi_{Z}(z-\zeta)$. Furthermore, in what follows we use the notion of inexact first-order oracle for a smooth convex function due to .

Let $f:Z\to\mathds{R}$ be convex with $L$-Lipschitz gradient. Pair $[\widetilde{f}(\cdot),\widetilde{\nabla}f(\cdot)]$ is called inexact oracle for $f$ with accuracy $\delta\geqslant 0$ if for any pair of points $z,z^{\prime}\in Z$ one has

Note that, unlike , we do not include $L$ into the definition of inexact oracle.

Next we present Nesterov’s fast gradient method (FGM) for smooth convex optimization with inexact oracle (see ) and a restart scheme for it. We use them in two scenarios: (a) minimization of a strongly convex function on $X$ with exact oracle; (b) maximization of a strongly concave function on $Y$ with $\delta$-inexact oracle.

Assume we are given initial point $z_{0}\in Z$, target number of iterations $T$, stepsize $\gamma>0$, and access to a $\delta$-inexact (or, possibly, exact) oracle for function $f:Z\to\mathds{R}$ which satisfies the requirements in Definition 3.1.

2 Proximal point operator and its implementation via FGM

Next we briefly review the proximal point method, which forms the backbone of our approach, in the context of searching for stationary points of nonconvex functions. Then we show how the iterations of this method can be approximated by using Algorithm 2.

Given a convex set $X$ and $\phi:X\to\mathds{R}$ with $L$-Lipschitz gradient, the proximal point operator of $\phi$ on $X$ with stepsize $0<\gamma<1/L$ is defined by

Denoting $x^{+}=x^{+}_{\gamma\phi,X}(x)$ for brevity, the first-order optimality condition in 19 writes

Note that this reduces to the “implicit gradient descent” update $x^{+}=x-\gamma\nabla\phi(x^{+})$ in the unconstrained case. For large stepsize, computing the proximal operator at a point might be as hard as minimizing $\phi$. However, with sufficient regularization, namely when $\gamma=c/L$ for $0<c\leqslant 1/2$, the task becomes easy, since the objective in 19 is strongly convex and well-conditioned, with $\kappa=(1+c)/(1-c)\leqslant 3.$ On the other hand, with such stepsize the proximal point method, as given by

attains the optimal rate $O(1/\sqrt{T})$ of minimizing the stationarity measure $\textsf{{S}}_{X}$ (cf. Definition 2.1). Indeed, from (19) with $\gamma=c/L$ we get

Iterating this $T$ times according to (21) results in

where $\Delta=\phi(x_{0})-\textstyle\min_{x\in X}\phi(x)$ is the initial gap. On the other hand,

where we first used the first-order optimality condition 20 and then Young’s inequality; note that the last inequality becomes tight when $X=\mathcal{X}$. Combining 21, 23 and 24, we arrive at

i.e., the iteration complexity $T(\varepsilon)=O\left({L\Delta}/{\varepsilon^{2}}\right)$ of minimizing the measure $\textsf{{S}}_{X}$, which is optimal in the unconstrained case .

Of course, the above argument would be useless if 23 or 24 were not tolerant to errors when computing $x^{+}_{\gamma\phi,X}(x)$, i.e., when minimizing the regularized function

(Here we fixed $c=1/2$ for simplicity, i.e., $\gamma=1/(2L)$, cf. 19.) We shall now verify such error-tolerance for 23, 24 and 25 as a result. Indeed, let $\widetilde{x}^{+}\in X$ satisfy

for given $x$, where $x^{+}=x^{+}_{\phi/2L,X}(x)$ is the true minimizer, $\varepsilon$ the desired accuracy, and the constant $1/24$ will be convenient in further calculations. Consider the counterpart of 21, i.e., the sequence $\widetilde{x}_{t}=\widetilde{x}^{+}_{\phi/2L,X}(\widetilde{x}_{t-1})$ obeing (27) at each step. Using 22 and proceeding as when deriving 23, we obtain the following counterpart of 23:

thus showing the desired error-tolerance for 23. Moreover, assume now that $\widetilde{x}^{+}$, in addition to 27, admits the matching guarantee for the stationarity measure, that is

here we first used the explicit form of $\nabla\phi_{L,x}$, then estimated the additional term via Young’s inequality, and finally used that $\textsf{{S}}_{X}(x,\xi,L)$ is non-decreasing in $L$, as follows from the proximal Polyak-Lojasiewicz lemma ([16, Lem. 1]).Namely, we apply [16, Lemma 1] using the indicator of $X$ as the proximal function $g(x)$ there. Thus, we have just verified the required error-tolerance for 24. Finally, by recalling 28 we arrive at

which results in the same complexity $T(\varepsilon)=O\left({L\Delta}/{\varepsilon^{2}}\right)$ as for the exact updates 21.

It remains to notice that the point $\widetilde{x}^{+}$ satisfying 27 and 29 can be obtained by running FGM with restarts (Algorithm 2) with a near-constant total number of oracle calls, since the function $\phi_{L,x}$ minimized in 19 is $3L$-smooth and $L$-strongly-convex. Namely, combining Corollary 3.3 and Corollary 3.5, we obtain the following.

Given some $x\in X$, let $\phi:X\to\mathds{R}$ have $L$-Lipschitz gradient, and let $x^{+}=x^{+}_{\phi/(2L),X}(x)$ be the minimizer of $\phi_{L,x},$ cf. 26. Let $\widetilde{x}^{+}$ be the output of Algorithm 2 run with exact oracle $\nabla\phi_{L,x}(\cdot)$, $z_{0}=x,$ $Z=X$, and parameters

where $\Delta_{L,x}:=\phi(x)-\textstyle\min_{x^{\prime}}\phi_{L,x}(x^{\prime})$. Then

Note that $\phi_{L,x}(\cdot)$ is $3L$-smooth, has condition number $\kappa\leqslant 3$, and is $\Delta_{L,x}$-suboptimal at $x$. Hence, Algorithm 2 run with $T=11>\sqrt{40\kappa}$ and

cf. 18, outputs a point for which 16 holds with the following replacements:

Using that $\textsf{{S}}_{X}(x,\xi,L)\leqslant\textsf{{S}}_{X}(x,\xi,3L)$, we verify all three inequalities in 33.

Algorithm and main result

In order to better convey the ideas behind our approach, we shall present it in a similar manner as in Section 3.2. Namely, we shall first present the “conceptual” algorithm with exact proximal-point type updates, and then show how to approximate these updates, which shall result in our final algorithm.

First, following , we reduce the problem of finding $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in 1 to the problem of finding approximate FNE of the regularized function

This function has a unique maximizer for any $x\in X$ as it is $\varepsilon_{\textsf{{y}}}/R_{{\textsf{{y}}}}$-strongly concave. This strong concavity will help us obtain faster algorithms for finding $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE when applying standard accelerated procedures.

The crux of our approach is to run a version of primal-dual proximal-point method, choosing the next iterate $(x_{t},y_{t})$ as an approximate optimal solution to the convex-concave saddle-point problem (with unique exact solution):

To illustrate this idea, let us consider the idealized iterates $(\widehat{x}_{t},\widehat{y}_{t})$ corresponding to the exact saddle point in 35, which exists and is unique by Sion’s minimax theorem . By definition, we have

Using the expression for $F^{\textup{reg}}_{t}(x,y)$ in 35, the right-hand inequality in 36 reads

Meanwhile, the first inequality in 36 implies that $F^{\textup{reg}}(\widehat{x}_{t},\widehat{y}_{t})\geqslant F^{\textup{reg}}(\widehat{x}_{t},\widehat{y}_{t+1})$. Thus we arrive at

The point here is that, unlike 37, relation 38 can now be iterated, as the index gets shifted in the left-hand side for both variables. Iterating 38 results in a similar argument as in 22-25 and gives the $T_{\textsf{{x}}}$ complexity factor. More precisely, applying 38 for $t\in[T-1]$ and 37 at $t=T$, we arrive at an analogue of 23:

Now observe that we can relate $F^{\textup{reg}}(\widehat{x}_{0},\widehat{y}_{1})-F^{\textup{reg}}(\widehat{x}_{T},\widehat{y}_{T})$ to $\Delta=\varphi(\widehat{x}_{0})-\textstyle\min_{x\in X}\varphi(x)$:

Thus we can guarantee the existence of $\tau\in[T]$ for which $\|\widehat{x}_{\tau}-\widehat{x}_{\tau-1}\|^{2}\leqslant\frac{\Delta+2\varepsilon_{\textsf{{y}}}R_{{\textsf{{y}}}}}{L_{{\textsf{{x}}}{\textsf{{x}}}}T},$ mimicking 23 up to $O(\varepsilon_{\textsf{{y}}})$ additive error. Now we can proceed as in 24, using the primal optimality condition in 35 and $\nabla_{\textsf{{x}}}F^{\textup{reg}}(x,y)\equiv\nabla_{\textsf{{x}}}F(x,y)$. This results in

corresponding to $O(T_{\textsf{{x}}})$ iterations 9 to ensure $\textsf{{S}}_{X}(\widehat{x}_{\tau},\nabla_{\textsf{{x}}}F(\widehat{x}_{\tau},\widehat{y}_{\tau}),L_{{\textsf{{x}}}{\textsf{{x}}}})\leqslant\varepsilon_{\textsf{{x}}}$. Meanwhile, we remain near-stationary in $y$: indeed, for any iteration $t\in[T_{\textsf{{x}}}]$ we have that

where in the second inequality we used the dual optimality condition for 35, and then used Young’s inequality. Thus, $(\widehat{x}_{\tau},\widehat{y}_{\tau})$ is an $(\varepsilon_{\textsf{{x}}},O(\varepsilon_{\textsf{{y}}}))$-FNE.

So far we assumed the update (35) can be done exactly and analyzed the iteration complexity of the resulting idealized procedure. Next we show how to approximate (35) via Algorithm 2, leading to our final algorithm and its efficiency estimate.

2 Implementation of conceptual algorithm

As in the case of the usual proximal point method, the update stemming from the auxilliary min-max problem in 35 cannot be performed exactly. To address this problem, we extend the approach described in Section 3.2 and approximately solve the (primal) minimization problem in 35 up to $O(\varepsilon_{\textsf{{x}}})$ accuracy in the $\textsf{{S}}_{X}$-measure via Algorithm 2 (cf. Proposition 3.6). The key challenge here is that the function to minimize in 35 stems from the nested maximization problem, hence neither it nor its gradient can be computed exactly. Instead, we provide inexact oracle for this function through the following steps.

First, given the current primal iterate $x_{t-1}$, consider the minimization problem corresponding to the dual function of 35 evaluated at some fixed $y\in Y$:

Solving this minimization problem for fixed $y\in Y$ by running Algorithm 2 with exact oracle $\nabla_{\textsf{{x}}}F(\cdot,y)+2L_{{\textsf{{x}}}{\textsf{{x}}}}(\cdot-x_{t-1})$, we obtain approximation $\widetilde{x}_{t}(y)$ of the exact minimizer $\widehat{x}_{t}(y)$. As $F_{t}(\cdot,y)$ is well-conditioned, it only takes a logarithmic number of oracle calls to ensure a very small (inversely polynomial in the problem parameters) error of approximating $\widehat{x}_{t}(y)$. On the other hand, a version of Danskin’s theorem ([29, Lem. 24]) guarantees that the gradient of $\psi_{t}(y)$, given by

is $O(L_{{\textsf{{y}}}{\textsf{{y}}}}^{+})$-Lipschitz. Hence, $\widetilde{x}_{t}(y)$ provides a $\delta$-inexact oracle for $\psi_{t}(y)$:

cf. Definition 3.1, where the accuracy parameter $\delta$ can be arbitrarily chosen. For convenience, we outline the subroutine that returns $\widetilde{x}_{t}(y)$ and the approximate dual gradient $\widetilde{\nabla}\psi_{t}(y)$ in Algorithm 3. Now, observe that we can switch the order of $\min$ and $\max$ in 35, recasting it as $y_{t}=\arg\max_{y\in Y}\psi_{t}(y),$ and $x_{t}=\widehat{x}_{t}(y_{t}).$ Naturally, we replace those with the approximate updates given by

maximizing $\psi_{t}(y)$ by running Algorithm 2 with inexact gradient $-\widetilde{\nabla}\psi_{t}(y)$ defined in 41, and without using $\widetilde{\psi}_{t}(y)$. Since $\psi_{t}(y)$ is $L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}$-smooth and $(\varepsilon_{\textsf{{y}}}/R_{{\textsf{{y}}}})$-strongly concave, in $O(T_{\textsf{{y}}})$ calls of the inexact oracle $-\widetilde{\nabla}\psi_{t}(\cdot)$ Algorithm 2 finds $O(\varepsilon_{\textsf{{y}}})$-approximate maximizer $y_{t}$ of $\psi_{t}$, ensuring that

Combining the first of these inequalities with 40 and recalling that $\widetilde{x}_{t}(y_{t})\approx\widehat{x}_{t}(y_{t})$ with very high accuracy, we ensure that $(x_{t},y_{t})$ obtained via 42 is $O(\varepsilon_{\textsf{{y}}})$-stationary in $y$ (in the sense of Definition 2.1). As this must be repeated for $t\in[T_{\textsf{{x}}}]$, we recover the first term in 10. On the other hand, the second inequality leads to the extra $O(\varepsilon_{\textsf{{y}}}^{2}/L_{{\textsf{{y}}}{\textsf{{y}}}}^{+})$ error in the saddle point relation 36, whereas, as we know from Proposition 3.6, this error must be $O(\varepsilon_{\textsf{{x}}}^{2}/L_{{\textsf{{x}}}{\textsf{{x}}}})$ in order to preserve the argument in Section 4.1. This is easy to fix: it suffices to perform a logarithmic in $T_{\textsf{{x}}}$ number of additional restarts when maximizing $\psi_{t}(y)$ (cf. 32). Thus, the argument in Section 4.1 remains valid, and we find $(\varepsilon_{\textsf{{x}}},O(\varepsilon_{\textsf{{y}}}))$-FNE in 1 in $\widetilde{O}(T_{\textsf{{x}}}T_{\textsf{{y}}})$ gradient computations and projections. The resulting algorithm, our main practical contribution, is given in Algorithm 4.

3 Convergence guarantee for Algorithm 4

Define $\lambda_{{\textsf{{y}}}}:=\frac{\varepsilon_{\textsf{{y}}}}{R_{{\textsf{{y}}}}},\quad\Theta:=L_{{\textsf{{y}}}{\textsf{{y}}}}R_{{\textsf{{y}}}}^{2},\quad\Theta^{+}:=L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}R_{{\textsf{{y}}}}^{2},$ and

Its output is $(2\varepsilon_{\textsf{{x}}},5\varepsilon_{\textsf{{y}}})$-FNE in the problem 1, in the sense of Definition 2.1, in $\left\lceil T^{o}S^{o}S_{\textsf{{y}}}\overline{T}_{\textsf{{x}}}\overline{T}_{\textsf{{y}}}\right\rceil$ computations of $\nabla F(x,y)$ and twice that many projections onto $X$ and $Y$.

We emphasize that our criterion of approximate FNE (cf. Definition 2.1) is stronger than the criterion based on the proximal gradient: the obtained point $(\widehat{x},\widehat{y})$ also satisfies

cf. Remark 1. On the other hand, the converse is not true: the above guarantee is not sufficient to conclude that the point is $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE in the sense of Definition 2.1.

From Theorem 4.1 we see that Algorithm 4 can also be used when the objective $F(x,y)$ is $\lambda_{{\textsf{{y}}}}$-strongly concave in $y$ with general $\lambda_{{\textsf{{y}}}}$, leading to the complexity estimate $\widetilde{O}(T_{\textsf{{x}}}(\kappa_{{\textsf{{y}}}}^{+})^{1/2})$, where $\kappa_{{\textsf{{y}}}}^{+}=L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}/\lambda_{{\textsf{{y}}}}$ is the condition number of the dual function in 35. This matches the best known rate (see, e.g., ). To this end, it suffices to run the algorithm with parameters set as in the premise of Theorem 4.1, but fixing a prescribed value for $\lambda_{{\textsf{{y}}}}$.

As per Theorem 4.1, the value $\Delta$ enters the prescribed setup of parameters for Algorithm 4, in three places: in the expression for the number $\overline{T}_{\textsf{{x}}}$ of iterations in the outer loop and under the logarithms in $S^{o}$ and $S_{y}$ through $\delta$, cf. 43. In practice, $\Delta$ is usually unknown, but this does not pose a problem. Indeed, in the case of logarithmic dependencies (in $S^{o}$ and $S_{y}$), we can use, instead of $\Delta$, a very crude upper bound (e.g., we always have $\Delta\leqslant 2L_{{\textsf{{x}}}{\textsf{{x}}}}^{\vphantom{2}}R_{{\textsf{{x}}}}^{2}$ whenever $X$ is contained in the Euclidean ball with radius $R_{{\textsf{{x}}}}$). As for $\overline{T}_{\textsf{{x}}}$, observe that, when actually running Algorithm 4, one does not have to fix in advance the number of outer loop iterations. Instead, one can run an infinite loop and check the stopping criterion $\textsf{{S}}_{X}(x_{t},\nabla_{\textsf{{x}}}F(x_{t},y_{t}),L_{{\textsf{{x}}}{\textsf{{x}}}})\leqslant 2\varepsilon_{\textsf{{x}}}$ after each iteration, which amounts to computing a prox-mapping for $X$. This is a valid stopping criterion: as follows from the proof of Theorem 4.1, the complementary condition $\textsf{{S}}_{Y}(y_{t},-\nabla_{\textsf{{y}}}F(x_{t},y_{t}),L_{{\textsf{{y}}}{\textsf{{y}}}})\leqslant 5\varepsilon_{\textsf{{y}}}$ is maintained at each $t$. To this end, Theorem 4.1 guarantees the termination of Algorithm 4 after at most $\overline{T}_{\textsf{{x}}}$ outer loop iterations.

4 Proof of Theorem 4.1

We use the notation introduced in Section 4.1–4.2 and refer to the arguments presented there if needed.

$\boldsymbol{{1}^{o}}$. Given a primal iterate $x_{t-1}$, let us define the following auxiliary functions:

Consider first the “idealized” update from the primal iterate $x_{t-1}$, as given by

Here, $\psi_{t}(y)$ and $\widehat{x}_{t}(y)$ are defined as

with Clearly, $\psi_{t}(y)$ is $\lambda_{{\textsf{{y}}}}$-strongly concave with $\lambda_{{\textsf{{y}}}}=\varepsilon_{\textsf{{y}}}/R_{{\textsf{{y}}}}$. On the other hand, by Danskin’s theorem (see, e.g., [29, Lem. 24]), $\psi_{t}(y)$ is continuously differentiable with

and $\nabla\psi_{t}(y)$ is $(L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}+\lambda_{{\textsf{{y}}}})$-Lipschitz with $L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}$ defined in 8.

$\boldsymbol{{2}^{o}}$. We now focus on the properties of the point $\widetilde{x}_{t}(y)$ returned when calling SolveRegDual$(y,x_{t-1},\bar{y},\gamma_{\textsf{{x}}},\lambda_{{\textsf{{y}}}},T^{o},S^{o}),$ cf. line 4 of Algorithm 4, as well as the corresponding pair $[\widetilde{\psi}_{t}(y),\widetilde{\nabla}\psi_{t}(y)]$, cf. 41. Note that the function value $\widetilde{\psi}_{t}(y)$ is never computed in Algorithm 4 and we only use it in the analysis. Inspecting the pseudocode of SolveRegDual(Algorithm 3), we see that $\widetilde{x}_{t}(y)$ corresponds to the approximate minimizer of $F^{\textup{reg}}_{t}(x,y)$ (thus also $F_{t}(x,y)$) in $x$, obtained by running restarted FGM (Algorithm 2) starting from $x_{t-1}$, with stepsize $\gamma=1/(3L_{{\textsf{{x}}}{\textsf{{x}}}})$, $T^{o}=11$ inner loop iterations, and the number of restarts $S^{o}$ given in 46. Observe that minimizing $F_{t}(\cdot,y)$ corresponds to computing the proximal operator ${\textsf{{x}}}^{+}_{\gamma F(\cdot,y),X}(x_{t-1})$ for the function $F(\cdot,y)$ which is $L_{{\textsf{{x}}}{\textsf{{x}}}}$-smooth. Hence, due to our choice of input parameters, the premise of Proposition 3.6 is satisfied; applying it with our choice of $S^{o}$ yields

Here, 50 and the first respective terms in 51–(52) are due to the first of three terms in brackets under logarithm in 46, cf. 32, combined with a very crude uniform over $y\in Y$ estimate

(We defer the proof of 53 to appendix.) On the other hand, the second respective estimates in (51)–(52) correspond to the two remaining terms in brackets under logarithm in 46, cf. 32, combined with the following easy-to-verify relations:

Now, (50)–(52) have two consequences. First, by 52 we immediately have

which mimics 37. The bound 54 will be our departure point when bounding $\textsf{{S}}_{X}$ later on. Second, the second respective terms in the right-hand side of 51–(52) together ensure that the pair $[-\widetilde{\psi}_{t}^{\delta}(y),-\widetilde{\nabla}\psi_{t}(y)]$ with

is a $\delta$-inexact first-order oracle for $-\psi_{t}(y)$ in the sense of Definition 3.1, namely,

where we used that $\psi_{t}$ is $(L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}+\lambda_{{\textsf{{y}}}})$-smooth (the proof of 56 is deferred to appendix).

$\boldsymbol{{3}^{o}}$. Now consider the actual update performed in the for-loop of Algorithm 4:

where the precise meaning of “$\approx$”, is $y_{t}=$RestartFGM$(\bar{y},Y,\gamma_{\textsf{{y}}},\overline{T}_{\textsf{{y}}},S_{\textsf{{y}}},-\widetilde{\nabla}\psi_{t}(\cdot)),$ cf. line 3. In other words, $y_{t}$ is obtained by running Algorithm 2 with $\delta$-inexact gradient $\widetilde{\nabla}\psi_{t}(\cdot)$, starting from $\bar{y}\in Y$, with $\overline{T}_{\textsf{{y}}}$ iterations in the inner calls of FGM and $S_{\textsf{{y}}}$ restarts, $\overline{T}_{\textsf{{y}}}$ and $S_{\textsf{{y}}}$ being given in 45. Recall that $\psi_{t}(\cdot)$ is $(L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}+\lambda_{{\textsf{{y}}}})$-smooth and $\lambda_{{\textsf{{y}}}}$-strongly convex with $\lambda_{{\textsf{{y}}}}=\varepsilon_{\textsf{{y}}}/R_{{\textsf{{y}}}}$, and

i.e., the condition in 13 is satisfied. By our choice of $\overline{T}_{\textsf{{y}}}$ and $S_{\textsf{{y}}}$ in 45, and due to Corollary 3.3, we get

and $\textsf{{S}}_{Y}(y_{t},-\nabla\psi_{t}(y_{t}),L_{{\textsf{{y}}}{\textsf{{y}}}}^{+}+\lambda_{{\textsf{{y}}}})\leqslant{\varepsilon_{\textsf{{y}}}}/{3},$ where $y_{t}^{*}$ is the exact maximizer of $\psi_{t}$ (cf. 16). Here we used the first lower bound in 45 for $S_{\textsf{{y}}}$ to obtain all estimates except for the second estimate of $\psi_{t}(y_{t}^{*})-\psi_{t}(y_{t})$, and for this latter estimate we used the second bound in 45 for $S_{\textsf{{y}}}$ and the last bound in 43 for $\delta$, and did a series of estimates:

Now, by the proximal PL-lemma ([16, Lem. 1]), $\textsf{{S}}_{Y}(y,g,L)$ is non-decreasing in $L$, so

Due to 49 and the Lipschitzness of $\nabla_{\textsf{{y}}}F(\cdot,y)$ and $\textup{prox}_{y_{t},Y}(\cdot)$, $x_{t}=\widetilde{x}_{t}(y_{t})$ satisfies

Here in $(a)$ we used that $\textsf{{S}}_{Y}(y,g,L)$ is non-decreasing in $L$ ([16, Lem. 1]); in $(b)$ we used 60; in $(c)$ we used Young’s inequality; in $(d)$ we used the Cauchy-Schwarz inequality; in $(e)$ we used the Lipschitzness of $F$; in $(f)$ we used 51; in $(g)$ we used our choice of $\delta$ in 43. Thus, $(x_{t},y_{t})$ is kept $5\varepsilon_{\textsf{{y}}}$-stationary in $y$ at any iteration $t$.

$\boldsymbol{{4}^{o}}$. We now revisit 54. Applying it to $y=y_{t}$, we get

which mimics 37. Our goal, however, is to mimic 38, for which we must lower-bound, up to a small error, $F^{\textup{reg}}(x_{t},y_{t})$ via $F^{\textup{reg}}(x_{t},y_{t+1})$, or, equivalently, $F^{\textup{reg}}_{t}(x_{t},y_{t})$ via $F^{\textup{reg}}_{t}(x_{t},y_{t+1})$. First,

where $\varphi_{t}(x):=\textstyle\max_{y\in Y}F^{\textup{reg}}_{t}(x,y)$ is the primal function in the saddle-point problem 35. On the other hand, denoting $x_{t}^{*}=\widehat{x}_{t}(y_{t}^{*})$, so that $(x_{t}^{*},y_{t}^{*})$ is the unique saddle point in 35, we have

It remains to compare $\varphi_{t}(x_{t})$ and $\varphi_{t}(x_{t}^{*})$. Combining $F^{\textup{reg}}_{t}(x_{t}^{*},y_{t}^{*})\geqslant F^{\textup{reg}}_{t}(x_{t}^{*},y_{t})$ with the previous inequality, and observing that $F^{\textup{reg}}_{t}(\cdot,y_{t})$ is $L_{{\textsf{{x}}}{\textsf{{x}}}}$-strongly convex and minimized at $\widehat{x}_{t}(y_{t})$, we obtain $\|\widehat{x}_{t}(y_{t})-x_{t}^{*}\|^{2}\leqslant\frac{\varepsilon_{\textsf{{x}}}^{2}}{9L_{{\textsf{{x}}}{\textsf{{x}}}}^{2}\overline{T}_{\textsf{{y}}}^{2}}.$ On the other hand, 51 applied to $y=y_{t}$ gives

where we used the last expression in 43 for $\delta$. Combining these results, we get

Now, $\varphi_{t}$ is $\left(3L_{{\textsf{{x}}}{\textsf{{x}}}}+{L_{{\textsf{{x}}}{\textsf{{y}}}}^{2}}/{\lambda_{{\textsf{{y}}}}^{\vphantom{2}}}\right)$-smooth by Danskin’s theorem, and minimized at $x_{t}^{*}$. Thus

where in the last step we plugged in $\overline{T}_{\textsf{{y}}}$ from 45. Returning to 62–63, we get $F^{\textup{reg}}(x_{t},y_{t})\geqslant F^{\textup{reg}}(x_{t},y_{t+1})-{0.25\varepsilon_{\textsf{{x}}}^{2}}/{L_{{\textsf{{x}}}{\textsf{{x}}}}}.$ Combining this with 61 we finally get the desired analogue of 38:

This bound can be iterated, and we can proceed as in Section 3.2. First we mimic 28:

where we used the estimates 39 and plugged in $T_{\textsf{{x}}}$. It remains to mimic (30):

where in $(a)$ we used 50 with $y=y_{t}$, in $(b)$ we used Young’s inequality, and $(c)$ was due to 67. Combining this with the result of $\boldsymbol{{3}^{o}}$, we conclude that $(x_{\tau},y_{\tau})$ with $\tau\in\operatorname*{argmin}_{t\in\overline{T}_{\textsf{{x}}}}\|x_{t}-x_{t-1}\|^{2}$ is $(2\varepsilon_{\textsf{{x}}},5\varepsilon_{\textsf{{y}}})$-FNE. Moreover, we have performed $\left\lceil T^{o}S^{o}S_{\textsf{{y}}}\overline{T}_{\textsf{{x}}}\overline{T}_{\textsf{{y}}}\right\rceil$ iterations of FGM (in the for-loop of Algorithm 1) in total, with one computation of $\nabla F$ and at most two projections on $Y$ and $X$ at each iteration. \proofbox

Guarantees for the Moreau envelope

We now consider the standard Moreau envelope (see ) of the primal function $\varphi(x)=\max_{y\in Y}F(x,y)$, cf. 7:

Clearly, $\varphi$ is $L_{{\textsf{{x}}}{\textsf{{x}}}}$-weakly convex, thus the minimized function in 68 is $L_{{\textsf{{x}}}{\textsf{{x}}}}$-strongly convex. Focusing on the Moreau envelope makes sense in the applications where one is only interested in the “primal” accuracy of solving 1. A common practice, in the $x$-unconstrained case ($X=\mathcal{X}$), is then to use the primal component $\widehat{x}$ of an approximate Nash equilibrium $(\widehat{x},\widehat{y})$ as a candidate near-stationary point, measuring the accuracy by $\|\nabla\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|$. When $X=\mathcal{X}$, passing to the Moreau envelope can be motivated as follows. On the one hand, $\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}$ has Lipschitz gradient on $X$ (by Danskin’s theorem), and we can “ignore” the non-differentiability of $\varphi$. On the other hand, $\|\nabla\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|\leqslant\varepsilon_{\textsf{{x}}}$ implies that the point $x^{+}=x^{+}(\widehat{x})$ delivering the minimum in 68 for $x=\widehat{x}$ (formally, $x^{+}_{\lambda\varphi,\mathcal{X}}(\widehat{x})$ with $\lambda=\tfrac{1}{2L_{{\textsf{{x}}}{\textsf{{x}}}}}$, cf. 19) satisfies $\|x^{+}-\widehat{x}\|=O(\tfrac{\varepsilon_{\textsf{{x}}}}{L_{{\textsf{{x}}}{\textsf{{x}}}}})$ and $\min_{\xi\in\partial\varphi(x^{+})}\|\xi\|\leqslant\varepsilon_{\textsf{{x}}}$, see, e.g., . In other words, any $\varepsilon_{\textsf{{x}}}$-stationary point for the Moreau envelope is within $O(\varepsilon_{\textsf{{x}}}/L_{{\textsf{{x}}}{\textsf{{x}}}})$ distance from a point at which $\varphi$ has an $\varepsilon_{\textsf{{x}}}$-small subgradient. We now extend this result to the case $X\subseteq\mathcal{X}$.

Let $\phi:X\to\mathds{R}$ be $L$-weakly convex, and define its standard Moreau envelope $\phi_{2L}(x)=\min_{x^{\prime}\in X}[\phi(x^{\prime})+L\|x^{\prime}-x\|^{2}]$, cf. 68. Then: 1. We have $\|\nabla\phi_{2L}(x)\|=\textsf{{S}}_{X}(x,\nabla\phi_{2L}(x),2L)=\textsf{{W}}_{X}(x,\nabla\phi_{2L}(x),2L)$ for any $x\in X$. 2. We have $\nabla\phi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})=2L_{{\textsf{{x}}}{\textsf{{x}}}}(\widehat{x}-x^{+})$, where $x^{+}=\operatorname*{argmin}_{x^{\prime}\in X}\left[\phi(x^{\prime})+L_{{\textsf{{x}}}{\textsf{{x}}}}\|x^{\prime}-\widehat{x}\|^{2}\right]$. Thus $\|\nabla\phi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|\leqslant\varepsilon_{\textsf{{x}}}$ implies $\|x^{+}-\widehat{x}\|\leqslant{\varepsilon_{\textsf{{x}}}}/{(2L_{{\textsf{{x}}}{\textsf{{x}}}})}$ and $\displaystyle\min_{\xi\in\partial\phi(x^{+})}\textsf{{S}}_{X}(x^{+},\xi,2L_{{\textsf{{x}}}{\textsf{{x}}}})\leqslant\varepsilon_{\textsf{{x}}}.$

This result is proved in appendix. Proposition 5.1 motivates the task of finding a point $\widehat{x}$ with a small norm of the Moreau envelope $\|\nabla\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|$. The recent work proposes an algorithm that directly produces such a point in $O(\varepsilon_{\textsf{{x}}}^{3})$ first-order oracle calls in the primally-unconstrained setup ($X=\mathcal{X}$). The work uses a different approach. They first find an $O(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE for (1) with respect to the weak criterion, i.e., $(\widehat{x},\widehat{y})$ such that 4 holds with $\textsf{{S}}_{X},\textsf{{S}}_{Y}$ replaced with $\textsf{{W}}_{X},\textsf{{W}}_{Y}$ respectively. Then they use the result [18, Prop. 4.12] that claims to guarantee (again in the case $X=\mathcal{X}$) that $\|\nabla\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|=O(\varepsilon_{\textsf{{x}}})$ whenever $\varepsilon_{\textsf{{y}}}=O(\varepsilon_{\textsf{{x}}}^{2})$. Let us rephrase the claim in .

Assuming 3 and $X=\mathcal{X}$, one has that

where $\widehat{\textsf{{W}}}_{{\textsf{{y}}}}:=\textsf{{W}}_{Y}(\widehat{y},-\nabla_{\textsf{{y}}}F(\widehat{x},\widehat{y}),L_{{\textsf{{y}}}{\textsf{{y}}}})$. In particular, $\|\nabla\varphi_{2L_{{\textsf{{x}}}{\textsf{{x}}}}}(\widehat{x})\|=O(\varepsilon_{\textsf{{x}}})$ provided that $\|\nabla_{\textsf{{x}}}F(\widehat{x},\widehat{y})\|\leqslant\varepsilon_{\textsf{{x}}}$ and $\widehat{\textsf{{W}}}_{{\textsf{{y}}}}\leqslant\varepsilon_{\textsf{{x}}}^{2}/(L_{{\textsf{{x}}}{\textsf{{x}}}}R_{{\textsf{{y}}}})$.

Inspecting the results in , we conclude that their algorithm outputs an $(\varepsilon_{\textsf{{x}}},\varepsilon_{\textsf{{y}}})$-FNE (with respect to the weak measure $\textsf{{W}}_{Y}$ in $y$) in $\widetilde{O}(T_{\textsf{{x}}}T_{\textsf{{y}}})$ oracle calls. By Proposition 5.2, this translates to finding an $\varepsilon_{\textsf{{x}}}$-stationary point for the Moreau envelope in

oracle calls. However, our careful inspection of the proof of [18, Prop. 4.12] only allowed to verify 69 in the unconstrained case $Y=\mathcal{Y}$ (and replacing $R_{{\textsf{{y}}}}$ with the distance $\|\widehat{y}-y^{o}\|$ for some $y^{o}\in\operatorname*{Argmax}_{y\in Y}F(\widehat{x},y)$), so that $\widehat{\textsf{{W}}}_{{\textsf{{y}}}}$ becomes $\|\nabla_{\textsf{{y}}}F(\widehat{x},\widehat{y})\|$. The underlying issue is that the proof relies on the bound

where $\widehat{\zeta}_{{\textsf{{y}}}}:=L_{{\textsf{{y}}}{\textsf{{y}}}}(\Pi_{Y}[\widehat{y}+\tfrac{1}{L_{{\textsf{{y}}}{\textsf{{y}}}}}\nabla_{\textsf{{y}}}F(\widehat{x},\widehat{y})]-\widehat{y})$ is the negative proximal gradient of $-F(\widehat{x},\cdot)$ at $\widehat{y}$; this gives the term $R_{{\textsf{{y}}}}\textsf{{W}}_{Y}(\widehat{y},-\nabla_{\textsf{{y}}}F(\widehat{x},\widehat{y}),L_{{\textsf{{y}}}{\textsf{{y}}}})$ in 69 by Cauchy-Schwarz. However, 71 can be invalid when $Y\neq\mathcal{Y}$. The following result allows to rectify this.

Let $h:Y\to\mathds{R}$ be differentiable and concave, and define $\zeta^{L}(y):=L(\Pi_{Y}[y+\tfrac{1}{L}\nabla h(y)]-y)$ for $L>0$. Then for any $y,y^{\prime}\in Y$ and $L>0$, one has that