Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems

Introduction

We investigate the alternating variant of gradient descent ascent (GDA) with proximal steps for weakly convex-(strongly) concave saddle point problems, given by

Nonconvex-concave saddle point problems have received a great deal of attention recently due to their application in adversarial learning , learning with nondecomposable losses , learning with uncertain data and generative adversarial imitation learning of linear quadratic regulators . Additionally, albeit typically resulting in nonconvex-nonconcave objectives, the large interest in generative adversarial networks (GANs) has led to the studying of saddle point problems under different simplifying assumptions .

In the nonconvex-concave setting inner loop methods have received much of the attention with them obtaining the best complexity results in this class, see Table 1. Despite superior theoretical performance these methods have not been as popular in practice, especially in the training of GANs where single loop methods are still state-of-the-art . The simplest approach is given by simultaneous GDA, which, for a smooth coupling function $\Phi$ and step sizes $\eta_{x},\eta_{y}>0$, reads as:

After the first step of this method, however, more information is already available, which can be used in the update of the second variable, resulting in

It has been widely known that the alternating version of GDA has many favorable convergence properties of the simultaneous one . It has been long known that for bilinear problems the iterates of simultaneous GDA may diverge while those of the alternating version at least remain bounded. Furthermore, showed that the alternating version can be made convergent for this simple setting if negative momentum is used, while the same is false for simultaneous GDA. In another special setting was able to show better local dependence on the condition number for strongly convex-strongly-concave quadratic problems. We are naturally interested in — and will give an affirmative answer to the question:

Does stochastic alternating GDA have nonasymptotic convergence guarantees for nonconvex minimax problems?

This might seem surprising as it has been sufficiently demonstrated that both versions of GDA fail to converge for simple bilinear problems if equal step sizes are used. We therefore want to point out the importance of the two-time-scale approach which was also emphasized in . However, this alone is also not enough as shown in . The seeming contradiction is resolved through the observation that our convergence guarantees only concern the $x$-component of the objective function.

For convex-concave problems this is equivalent to the first order optimality condition

Similarly to the nonconvex single objective optimization where one cannot expect to find global minima, if the minimax problem is not convex-concave the notion of saddle point is too strong. So one natural approach is to focus on conditions such as 2, as done in . However, treating the two components in such a symmetric fashion might not seem fitting since in contrast to the convex-concave problem $\min_{x}\max_{y}\neq\max_{y}\min_{x}$. Instead we will focus, in the spirit of , on the stationarity of what we will refer to as the max function given by

This makes sense from the point of view of many practical applications. Problems arising from adversarial learning can be formulated as minimax, but typically only $x$, which corresponds to the classifier is relevant as $y$ is adversarial noise. Similarly, for GANs, one is typically only interested in the generator and not the discriminator. See Table 1 for a comparison of other methods using the same notion of optimality. Note that it is possible to move from one notion of optimality to the other , but as both directions are typically associated with additional computational effort a comparison is not trivial and out of scope of this work.

We prove novel convergence rates for alternating prox-gradient descent ascent for nonconvex-(strongly) concave minimax problems in a deterministic and stochastic setting. For deterministic problems, has proved convergence rates for alternating GDA in terms of the criticality of $\Phi$ while we use the max function $\varphi$, see 3, instead. Our results are also more general than e.g. in the sense that they require $\Phi$ to be smooth in the first component wheres we only require weak convexity, similar to . Furthermore, we allow for our method to include possibly nonsmooth regularizers, similar to , by passing from a regular projected-gradient to more the more general proximal-gradient steps which captures and extends the common constraint setting, necessitating us to prove a more general version of Danskins theorem in the process.

In the remainder of this section we discuss related literature and some real-world applications resulting in nonconvex-concave problems. In Section 2 we discuss the mathematical preliminaries as well as our main assumptions about the involved functions. Section 3 and Section 4 are devoted to the setting where the objective function is assumed to be convex and strongly convex, respectively. Both times we treat the deterministic problem first and then the scenario where we are only given a stochastic gradient oracle. Finally, in Section 5 we discussed numerical experiments in adversarial learning. For the interested reader we highlighted the improvements in the analysis of alternating GDA over its simultaneous counterpart in Sections 3.5 and 4.4.

1 Related literature

For the purpose of this paper we separate the quantitative study of minimax problems into the following domains.

For convex-concave problems historically the extra-gradient and the forward-backward-forward method have been known to converge. For the former even a rate of $\mathcal{O}(\epsilon^{-1})$ has been proven in under the name of mirror-prox. Both of these methods suffer from the drawback of requiring two gradient evaluations per iteration. This has led to the development of methods such as optimistic GDA or which use past gradients to reduce the need of gradient evaluations to one per iteration. In all of these cases, however, convergence guarantees typically do not go beyond the convex-concave setting. Nevertheless, these methods have been employed successfully in the GAN setting .

Approximating the max function by running multiple iterations of a solver on the second component or convexifying the problem by adding a quadratic term and then solving the convex-concave problem constitute natural approaches . Such methods achieve the best known rates in this class. However, they are usually quite involved and have for the most part not been used in deep learning applications.

While these methods have received some attention in the training of GANs most of the theoretical statement are for convex-concave problems. In the nonconvex setting only two methods have been studied. Previous research, see , has focused on the simultaneous version of the gradient descent ascent algorithm where both components are updated at the same time. The only other work which focuses on alternating GDA is . Their results are in terms of stationarity of $\Phi$ and they do not treat the stochastic case. Note that our work is most similar to where the same notion of optimality is used and similar rates to our are obtained for simultaneous GDA.

Clearly the above categories do not cover the entire field. However, other settings have not received as much attention. Only treats (strongly) convex-nonconcave problems and proves convergence rates similar to the nonconvex-(strongly) concave setting. In a special stochastic nonconvex-linear problem with regularizers is solved via a variance reduced single loop method with a significantly improved rate over the general nonconvex-concave problem.

The most general setting out of all the aforementioned ones is discussed in , namely the weakly convex-weakly concave setting. They use however, a weaker notion of optimality related to the Minty variational inequality formulation. We also only mentioned (sub)gradient methods, but the restrictive assumption that the proximal operator of a component can be evaluated has been considered as well .

2 Nonconvex-concave applications

Such problems often use an attack model that allows for every pixel to be perturbed up to given threshold $\epsilon$:

where $z_{0}$ denotes the “true” training examples, and $z$ the adversarial attack. However, this typically leads to nonconvex-nonconcave formulation. So proposed a distributionally robust model, making use of the Wasserstein distance $W$

where $Z\sim P_{0}$, which they reformulated via a Lagrangian penalty approach to

While a larger $\gamma$ corresponds to smaller robustness $\rho$, the model can be made nonconvex-strongly-concave if it is set big enough.

2.2 Generative adversarial imitation learning of linear quadratic regulators

In imitation learning the objective is to learn from an expert’s demonstration of performing a given task. In this case the minimization is performed over the policies with the goal of reducing the discrepancy between the reward of the expert’s policy and the proposed one. The maximization is over the parameters of the reward function, see . If the underlying dynamic and the reward function come from a linear quadratic regulator, see , this can be expressed as a nonconvex-strongly-concave minimax problem

where $K$ represents the choice of policy and $\theta$ the parameters of the dynamic and reward functions.

2.3 Fair learning

The work observed that a logistic regression model trained on the Fashion-MNIST dataset (comprised of $n=10$ classes) can lead to a bias against certain classes. In order to remove this bias, they proposed to minimize the maximal loss of the different categories, i.e.

where $\Delta:=\{(t_{1},\dots,t_{n}):t_{i}\geq 0,\sum_{i=1}^{n}t_{i}=1\}$ denotes the unit simplex. Due to the linearity of (7) in the second variable $(t_{1},\dots,t_{n})$, the inner maximization problem is in particular concave.

Preliminaries

In the remainder of the section we will focus on the necessary preliminaries connected to the weak convexity of the max function in the nonconvex-concave setting, see Section 3.

In the nonconvex-concave setting of Section 3 the max function $\varphi$ will in general be nonsmooth, which makes it nonobvious how to define near stationarity. The max function $\varphi$ will, however, turn out to be weakly convex, see Proposition 3.1. For some $\rho\geq 0$, we say that

An example of a weakly convex function is one which is differentiable and the gradient is uniformly Lipschitz continuous with constant $L$ (we call such a function $L$-smooth). In this case, the weak convexity parameter $\rho$ is given by the Lipschitz constant.

The proximal operator of the function $\lambda\psi$ is the $\arg\min$ of the right-hand side in this definition, that is,

For weakly convex function the Fréchet subdifferential can simply be expressed in terms of the convex subdifferential of the (convex) function $\psi+(\rho/2)\|\cdot\|^{2}$.

While the next result is standard for the gradient and convex subgradients we explicitly mention the general case.

Now, we provide a useful characterization of the gradient of the Moreau envelope.

and this gradient is Lipschitz continuous.

In particular, a gradient step with respect to the Moreau envelope corresponds to a proximal step, that is,

The Moreau envelope allows us to naturally define a notion of near stationarity even for nonsmooth and $\rho$-weakly convex functions. We say that for an $\epsilon>0$ and a $\lambda\in(0,\rho^{-1})$

Canonically, we call a point stationary if the above holds for $\epsilon=0$. This notion of near stationarity can also be expressed in terms the original function $\psi$.

Let $x$ be $\epsilon$-stationary for the proper, $\rho$-weakly convex and l.s.c. function $\psi$, i.e. $\|\nabla\psi_{\lambda}(x)\|\leq\epsilon$ with $\lambda\in(0,\rho^{-1})$. Then there exist a point $\hat{x}$ such that $\|x-\hat{x}\|\leq\epsilon\lambda$ and $\operatorname*{dist}(0,\partial\psi(\hat{x}))\leq\epsilon$.

From the definition of the Moreau envelope, we have that

from which $\nabla\psi_{\lambda}(x)\in\partial\psi(\operatorname{prox}_{\lambda\psi}\left(x\right))$ follows by using (9). It is easy to see that $\hat{x}=\operatorname{prox}_{\lambda\psi}\left(x\right)$ fulfills the required conditions. ∎

2 About the stochastic setting

We discuss the stochastic version of problem (1) where the coupling function $\Phi$ is actually given as an expectation,

and we can only access independent samples of the gradient $\nabla_{x}\Phi(x,y;\xi)$ (or subgradient) and $\nabla_{y}\Phi(x,y;\zeta)$, where $\xi$ and $\zeta$ are drawn from the (in general unknown) distribution $\mathcal{D}$.

We require the following standard assumption with respect to these stochastic gradient estimators.

The stochastic gradient estimator is unbiased, i.e.

In the setting of Section 3 where $\Phi$ is not necessarily smooth in the first component, we make the analogous assumption for subgradients, i.e.

for a stochastic subgradient $g^{\xi}\in\partial[\Phi(\cdot,y;\xi)](x)$.

3 The algorithm

Since we cover different settings such as smooth or not, deterministic and stochastic we try to formulate a unifying scheme.

where $G_{x}$ and $G_{y}$ will be replaced by the appropriate (sub)gradient and its estimator in the deterministic and stochastic setting, respectively.

4 Notation

We collect different symbols used through this manuscript.

Note that the regularized coupling function $\Gamma$ is only needed in proofs and some technical lemmata. The remaining functions confirm to the logic that small letters denote functions maximized in the second component (and thus only depend on $x$). On the other hand (no matter if capital or not) the letter psi indicates the presence of regularizers and phi their absence.

Nonconvex-concave objective

In this section we treat the case where the objective function is weakly convex and Lipschitz in $x$, but not necessarily smooth, and concave and smooth in $y$. This will result in a weakly convex and Lipschitz max function whose Moreau envelope we will study for criticality, see (10).

While the first assumption concerns general setting of this section, i.e. weakly convex-concave, the latter ones are more of a technical nature.

concave and $L_{\nabla\Phi}$-smooth in the second component uniformly in $x$,

$\rho$-weakly convex in the first component uniformly in the second one, i.e.

Assumption 3 is fulfilled if e.g. $\Phi$ is $L_{\nabla\Phi}$-smooth jointly in both components, i.e.

in which case (ii) holds with $\rho=L_{\nabla\Phi}$.

The next assumption is classical in nonconvex optimization.

We also want to point out that this is weaker than the lower boundedness of $\Psi$, which is usually required if stationary points of the type (2) are used, see for example .

$\Phi$ is $L$-Lipschitz in the first component uniformly over $\operatorname*{dom}h$ in the second one, i.e.

The regularizers $f$ and $h$ are proper, l.s.c. and convex

Additionally, $f$ is either $L_{f}$-Lipschitz continuous on its domain, which is assumed to be open, or the indicator of a nonempty, convex and closed set. Either of those assumptions guarantees for any $\gamma>0$ the bound

Furthermore, $h$ has a bounded domain $\operatorname*{dom}h$ such that the diameter of $\operatorname*{dom}h$ is bounded by $D_{h}$.

2 Properties of the max function

is nonempty. For brevity we denote arbitrary elements of $Y(x_{k})$ by $y_{k}^{*}$ for all $k\geq 0$.

Let Assumption 3 and 6 hold true. Then, the function $\varphi$, see (3), fulfills

In particular, $\varphi$ is $\rho$-weakly convex.

where $[\Phi(\cdot,y)]^{\prime}(x;v)$ denotes the directional derivative of $\Phi$ in the first component at $x$ in the direction $v$. In conclusion,

The Lipschitz continuity of $\Phi$ in its first component implies that $\varphi$ is Lipschitz with the same constant.

The reverse direction $\varphi(x^{\prime})-\varphi(x)\leq L\|x-x^{\prime}\|$ follows analogously. ∎

3 Deterministic setting

For initial values $(x_{0},y_{0})\in\operatorname*{dom}f\times\operatorname*{dom}h$ the deterministic version of alternating GDA, for $g_{k}\in\partial[\Phi(\cdot,y_{k})](x_{k})$, reads as

Let Assumption 3, 4, 5 and 6 hold true. For algorithm (17) with the step sizes

the number of gradient evaluations $K$ required is

Similarly to the proofs in and others, the main descent statement makes use of the quantity $\operatorname{prox}_{\lambda\psi}\left(x_{k}\right)$ for a $\lambda>0$. This is somewhat surprising as this point does not appear in the algorithm and can in general not be computed.

But first, we need to establish the fact that $\hat{x}_{k}:=\operatorname{prox}_{\lambda\psi}\left(x_{k}\right)$ can also be written as the proximal operator of $f$ evaluated at an auxiliary point.

For any $\lambda\in(0,\rho^{-1})$ and all $k\geq 0$ the point $\hat{x}_{k}:=\operatorname{prox}_{\lambda g}\left(x_{k}\right)$ can also be written for some $v_{k}\in\partial\varphi(\hat{x}_{k})$ as

Let $k\geq 0$ be arbitrary but fixed and recall that $g=f+\varphi$. By the definition of $\hat{x}_{k}$ we have that

We can estimate through the continuity of $\varphi$ and subdifferential calculus

Thus, there exists $v_{k}\in\partial\varphi(\hat{x}_{k})$ such that $\frac{1}{\lambda}(x_{k}-\hat{x}_{k})\in v_{k}+\partial f(\hat{x}_{k})$. Also,

With the previous lemma in place we can now turn our attention to the first step of the actual convergence proof.

With $\lambda=\nicefrac{{1}}{{2\rho}}$ and $\eta_{x}\geq 0$ we have for all $k\geq 0$ that

where $\Delta_{k}:=\psi(x_{k})-\Psi(x_{k},y_{k})\geq 0$.

Let $k\geq 0$ be fixed. As before we denote $\hat{x}_{k}=\operatorname{prox}_{\lambda\psi}\left(x_{k}\right)$. From the definition of the Moreau envelope we have that

Let now $v_{k}\in\partial\varphi(\hat{x}_{k})$ as in Lemma 3.2. We successively deduce for $\beta:=1-\eta_{x}\lambda^{-1}$

where (19) uses Lemma 3.2 and the definition of $x_{k+1}$, inequality (20) holds because of the nonexpansiveness of the proximal operator, and (21) follows from the Lipschitz continuity of $\Phi$ and $\varphi$ (see Lemma 3.1) and the fact that Lipschitz continuity implies bounded subgradients. We are left with estimating the inner product in the above inequality and we do so by splitting it into two: first of all, from the weak convexity of $\Phi$ in $x$ we have that

Secondly, by the $\rho$-weak convexity of $\varphi$

Combining the last two inequalities we get that

where we used the fact that $1-\beta\leq 1$ in the factor of $\Delta_{k}$. Now note that

Combining (18), (23) and (24) we deduce, using $\lambda=\nicefrac{{1}}{{2\rho}}$,

Naturally, we want to telescope the inequality established by the previous lemma. We are left with estimating $\Delta_{k}$, preferably even in a summable way. But first we need the following technical, yet standard lemma, estimating the amount of increase obtained by a single iteration of gradient ascent.

This is a standard estimate on the improvement made by a single prox-gradient step for a convex (in this case concave) function, see for example [5, Lemma 2.3]. ∎

We can now use the previous lemma to estimate $\Delta_{k}$. Recall also that $y^{*}_{k}$ denotes a maximizer of $\Psi(x_{k},\cdot)$ for all $k\geq 0$.

Plugging $y=y^{*}_{m}$ into (25) we deduce that

Starting from the definition of $\Delta_{k}=\Psi(x_{k},y^{*}_{k})-\Psi(x_{k},y_{k})$, we add (27) to obtain

Due to the Lipschitz continuity of $\Phi$, terms which only differ in their first argument will be easy to estimate. Therefore, we insert and subtract $\Phi(x_{m},y_{k}^{*})$ to deduce

We estimate the above expression for $k>m$ by making use of the Lipschitz continuity of $\Phi(\cdot,y)$ and (13) deducing

For $k=m$ the inequality follows trivially. Analogously, we deduce

Plugging (29), (30) and (31) into (28) gives the statement of the lemma. ∎

In order to estimate the summation of $\Delta_{k}$ we will use a trick to sum over it in blocks, where the size $B$ of these blocks will depend on the total number of iterations $K$. Note that w.l.o.g. we assume that the block size $B\leq K$ divides $K$ without remainder.

By splitting the summation into blocks we get that

By using (26) from Lemma 3.5 with $j>0$ and $m=jB$ and the fact that $\sum_{k=1}^{B-1}k\leq\nicefrac{{B^{2}}}{{2}}$ we have

where the last term can be bounded by $D_{h}^{2}$, which was defined in Assumption 6 and denotes the diameter of $\operatorname*{dom}h$. We do the same for the case $j=0$ but choose here $m=1$ and have separate out the first summand of $\sum_{k=0}^{B-1}\Delta_{k}$ as Lemma 3.5 does not hold for $k=0$ and therefore get an extra $\Delta_{0}$ summand. where $D_{h}$ was defined in Assumption 6 and denotes the diameter of $\operatorname*{dom}h$. Plugging (34) into (33) gives

The desired statement is obtained by using the step size $\eta_{y}=\nicefrac{{1}}{{L_{\nabla\Phi}}}$. ∎

With $B=\frac{D_{h}}{L}\sqrt{\frac{L_{\nabla\Phi}}{\eta_{x}}}$, we have that

By plugging in the step size described in the statement of the theorem we obtain

4 Stochastic setting

For initial values $(x_{0},y_{0})\in\operatorname*{dom}f\times\operatorname*{dom}h$ the stochastic version of alternating GDA is given by

for $g_{k}^{\xi}\in\partial[\Phi(\cdot,y_{k};\xi_{k})](x_{k})$ for $\xi_{k},\zeta_{k}\sim\mathcal{D}$ independent from all previous iterates.

Let in addition to the assumptions of Theorem 3.1 also Assumption 1 and 2 hold true. For algorithm (35) with step sizes

$\eta_{y}=\min\{\frac{1}{2L_{\nabla\Phi}},\frac{\epsilon^{2}}{\rho\sigma^{2}}\}$ and $\lambda=\frac{1}{2\rho}$ the number of stochastic gradient evaluations $K$ required is

The proof proceeds along the same lines of the deterministic case. Similarly we show an adapted version of Lemma 3.3.

With $\lambda=\nicefrac{{1}}{{2\rho}}$ we have for all $k\geq 0$ that

Let $k\geq 0$ be arbitrary but fixed. It follows easily from (12) that

Similarly to Lemma 3.3 we deduce that for $v_{k}\in\partial\varphi(\hat{x}_{k})$ (as given in Lemma 3.2) and $\beta=1-\eta_{x}\lambda^{-1}$

Next, we discuss the stochastic version of Lemma 3.4. It is clear that we cannot expect the same amount of function value increase by a single iteration of gradient ascent if we do not use the exact gradient.

The term $\langle\nabla_{y}\Phi(x_{k+1},y_{k};\zeta_{k}),y_{k+1}-y_{k}\rangle$ is problematic, because the right hand side of the inner product is not measurable with respect to the sigma algebra generated by past iterates $\mathcal{F}_{k}:=\sigma\{x_{k+1},\dots,x_{1},y_{k},\dots,y_{1}\}$, so we insert and subtract $\langle\nabla_{y}\Phi(x_{k+1},y_{k}),y_{k+1}-y_{k}\rangle$ Now, using Young’s inequality we estimate the resulting inner product

Combining the above two inequalities for $y=y^{*}_{m}$ with $1\leq m\leq k$ and taking the expectation together with the bounded variance assumption (11) gives

From the descent lemma (in ascent form) and the fact that $\eta_{y}\leq\nicefrac{{1}}{{2L_{\nabla\Phi}}}$ we have

We plug the above inequality into (39), make use of the concavity and add $f(x_{k+1})$ on both sides to deduce the statement of the lemma. ∎

We can now use the previous lemma to estimate $\hat{\Delta}_{k}$.

Let the numbers $1\leq m\leq k$ be fixed. Starting from the definition of $\hat{\Delta}_{k}$, we add (38) to obtain

Plugging all of these into (41) gives the statement of the lemma. ∎

In order to estimate the summation of $\hat{\Delta}_{k}$ we will use the same trick as in the deterministic setting and sum over it in blocks, where the size $B$ of these blocks will divide the total number of iterations $K$.

We proceed as in Lemma 3.6. By using Lemma 3.9 we obtain $j>0$ and $m=jB$ we have that

For $j=0$ we use $m=1$ and do not estimate $\Delta_{0}$ but leave it there. Plugging (43) into (33) gives the statement of the lemma. ∎

Now we can prove the convergence result for the stochastic algorithm.

We sum up the inequality of Lemma 3.7 to deduce that

Thus, by dividing by $K$ and $\eta_{x}$ yields

With the block size $B=D_{h}\sqrt{1/(\eta_{x}\eta_{y}L(L+L_{f}+\sigma))}$ we have that

Via the step size choice presented in the theorem we obtain the desired complexity. ∎

5 Alternating vs simultaneous

Although we are not able to show improved rates for the alternating version of GDA in this setting, we would still like to point out some improvements in the constants which otherwise might go unnoticed since the statements are quite technical.

In the nonconvex-concave setting the main descent type property we focus on can be seen in Lemma 3.3 and is given by

From this it clear the only troublesome part is the estimation of $\Delta_{k}=\psi(x_{k})-\Psi(x_{k},y_{k})$ (to be precise we, we need to estimate the sum of $\Delta_{k}$ after telescoping). While we obtain

in the same estimate is obtained for simultaneous GDA plus an additional term

see [30, Lemma D.4]. While we do not have information about the sign of this term it is clear that its absence is preferable as it needs to be estimated after telescoping and averaging via

Looking at the statement of Lemma 3.5 we see, however, that factors of both of these terms already appear in the final statement due to other estimations which is why their appearance gets lost in the big O notation.

Nonconvex-strongly concave objective

By requiring in addition to the assumptions of Section 3 strong convexity in the second component and smoothness of the coupling function in $x$, we can drop any assumption about Lipschitz continuity and will be able to deduce the max function $\varphi$ is smooth with Lipschitz continuous gradient (making it weakly convex). For the technical details see the following assumptions.

Let $\Phi$ be $L_{\nabla\Phi}$-smooth uniformly in both components and concave in the second one. The regularizers $f$ and $-h$ are proper, l.s.c. and convex. Additionally, either $\Phi$ is $\mu$-strongly concave in the second component, uniformly in the first one, or $-h$ is $\mu$-strongly concave.

1 Properties of the max function

In the following we will show the smoothness of $\varphi$, as well as the fact that the solution map fulfills a strong Lipschitz property.

Thus by the strong monotonicity of $\partial h-\nabla_{y}\Phi(x,\cdot)$ we obtain

Let Assumption 7 hold true. Then, $\varphi$ is smooth and its gradient is given by

and is therefore $L_{\nabla\Phi}(1+\kappa)$-Lipschitz.

which, together with (16), yields that (4.1) holds with equality. The fact that the gradient of $\varphi$ is Lipschitz continuous follows, with $y^{*}=y^{*}(x)$ and $\bar{y}^{*}=\bar{y}^{*}(\bar{x})$, from

2 Deterministic setting

We start with the main convergence result of this section.

to visit an $\epsilon$-stationary point such that \min_{1\leq k\leq K}\operatorname*{dist}\big{(}-\nabla\varphi(x_{k}),\partial f(x_{k})\big{)}\leq\epsilon.

Before we start with the first lemma, let us recall that $\delta_{k}=\|y_{k}-y_{k}^{*}\|^{2}$ denotes for all $k\geq 0$ the squared distance between the current iterate $y_{k}$ and the maximizing argument $y_{k}^{*}=\operatorname*{arg\,max}_{y}\Psi(x_{k},y)$.

There exists a sequence ${(w_{k})}_{k\geq 1}$ such that $w_{k}\in(\partial f+\nabla\varphi)(x_{k})$ and its norm can be bounded for all $k\geq 0$ by

Let $k\geq 0$ be arbitrary but fixed. From the optimality condition of the proximal operator we deduce by adding $\nabla\varphi(x_{k+1})$ on both sides

as claimed. In order to prove the bound on $\|w_{k+1}\|$ we proceed as follows:

The smoothness of $\varphi$ implies via the descent lemma that

Since the proximal operator minimizes a $\nicefrac{{1}}{{\eta_{x}}}$-strongly convex function we have that

Adding this inequality to (46) we deduce that

Plugging (47) and (46) into (45) yields the desired statement. ∎

In the next lemma it remains to bound the gap between the current iterate and the maximizing argument of the second component $\delta_{k}=\|y^{*}_{k}-y_{k}\|^{2}$.

Let $k\geq 0$ be fixed. From the definition of $y_{k+1}$, see (44), and the fact that $y_{k+1}^{*}$ is a fixed point of the proximal-gradient operator, we deduce

If $\Phi$ is strongly concave in its second component we can use the nonexpansiveness of the proximal operator and [42, Theorem 2.1.11], which states

with $q:={\left(\frac{\kappa}{\kappa+1}\right)}^{2}$, where we used that $\eta_{y}=\nicefrac{{1}}{{L_{\nabla\Phi}}}$. If on the other hand $-h$ is strongly concave we can use the fact that the proximal operator (of $h$) is even a contraction, see [4, Proposition 25.9 (i)], to deduce that $\delta_{k+1}\leq q\|y_{k+1}^{*}-y_{k}\|^{2}$. Therefore, in either case $\delta_{k+1}\leq q\|y_{k+1}^{*}-y_{k}\|^{2}$. Using this, the triangle inequality and Young’s inequality, we have

Due to the $\kappa$-Lipschitz continuity of $y^{*}(\cdot)$ we have that $\|y^{*}_{k+1}-y^{*}_{k}\|\leq\kappa\|x_{k+1}-x_{k}\|$, which finishes the proof. ∎

Now we can bound the sum of $\delta_{k}$.

By recursively applying the previous lemma we obtain for $k\geq 1$

Now we sum this inequality from $k=1$ to $K-1$ and add $\delta_{0}$ on both sides to deduce

and $\sum_{j=0}^{\infty}{(1-{(2\kappa)}^{-1})}^{j}=2\kappa$. ∎

Summing up the inequality of Lemma 4.2 from $k=0$ to $K-1$ and applying Lemma 4.4 we deduce that

With the step size $\eta_{x}=1/(3{(\kappa+1)}^{2}L_{\nabla\Phi})$ it follows that

3 Stochastic setting

For the purpose of this section Algorithm 2.1 reads

for the minibatch gradient estimators, given by $G_{x}=\frac{1}{M}\sum_{i=1}^{M}\nabla_{x}\Phi(x_{k},y_{k};\xi^{i}_{k})$ and $G_{y}=\frac{1}{M}\sum_{i=1}^{M}\nabla_{y}\Phi(x_{k+1},y_{k};\zeta^{i}_{k})$.

Let in addition to the assumptions of Theorem 4.1 also the two properties of the gradient estimator Assumption 1 and 2 hold true. For algorithm (51) with step size $\eta_{y}=\nicefrac{{1}}{{L_{\nabla\Phi}}}$ and $\eta_{x}=\nicefrac{{1}}{{(4{(1+\kappa)}^{2}L_{\nabla\Phi})}}$ and batch size $M=\mathcal{O}(\kappa\sigma^{2}\epsilon^{-2})$ the number of stochastic gradient evaluations $K$ required is

There exists a sequence ${(w_{k})}_{k\geq 1}$ such that $w_{k}\in(\partial f+\nabla\varphi)(x_{k})$ and its norm can be bounded for all $k\geq 0$ by

Let $k\geq 0$. From the proximal operator we deduce that

Thus, we define $w_{k+1}$ such that we immediately obtain the desired inclusion

In the next lemma it remains to bound $\delta_{k}$.

Let $k\geq 0$ be fixed. We first consider the case where $\Phi$ is strongly concave in its second component from the definition of $y_{k+1}$ (see (51)) we deduce that

Some of the terms vanish after taking the expectation such as

Using furthermore [42, Theorem 2.1.11] which states that

with $q={\left(\frac{\kappa}{\kappa+1}\right)}^{2}$, where we used that $\eta_{y}=\nicefrac{{1}}{{L_{\nabla\Phi}}}$. If $h$ is strongly concave then we use the fact that the proximal operator is a contraction, see [4, Proposition 23.11], to deduce that

Using now (54) with $\mu=0$, i.e. the cocoercivity of the gradient, we deduce that

meaning that we concluded (55) in both cases. Next, using (55) and the considerations made in (49) we deduce that

Again, due to the $\kappa$-Lipschitz continuity of $y^{*}(\cdot)$ we have that $\|y^{*}_{k+1}-y^{*}_{k}\|\leq\kappa\|x_{k+1}-x_{k}\|$, which finishes the proof. ∎

Now we can bound the sum of $\delta_{k}$.

By recursively applying the previous lemma we obtain for $k\geq 1$

Now we sum this inequality from $k=1$ to $K-1$ and add $\delta_{0}$ on both sides to deduce

We sum up the inequality of Lemma 4.5 from $k=0$ to $K-1$ and applying Lemma 4.7 we deduce that

Applying the step size $\eta_{x}=\nicefrac{{1}}{{(3{(1+\kappa)}^{2}L_{\nabla\Phi})}}$ it follows that

4 Alternating vs simultaneous

Similarly to Section 3.5 we want to highlight here the difference in the analysis between the two versions of GDA. Again, in this nonconvex-strongly-concave setting the task is to estimate $\delta_{k}:=\|y_{k}^{*}-y_{k}\|^{2}$. While in the simultaneous version obtains for all $k\geq 0$ the following inequality

where $q$ is the contraction constant derived from the gradient ascent step and is roughly $1-\frac{1}{\kappa}$. In the alternating version however, we estimate for all $k\geq 0$

Evidently, in the alternating version the contraction property is applied before the triangle inequality, which leads to the second term being multiplied by $q<1$ as well, influencing the final complexity bound favorably, albeit only slightly.

Numerical Experiments

In this section, we present several experiments outlining the empirical benefits of alternating GDA over its simultaneous counterpart.

The recent paper showed an improved convergence rate of alternating GDA over the simultaneous version in the strongly convex-strongly concave quadratic setting from $\mathcal{O}(\kappa^{2})$ to $\mathcal{O}(\kappa)$. Inspired by these results we study a nonconvex-strongly-concave toy example

where the resulting max function happens to be a strongly convex quadratic

As we can see from Figure 1, alternating GDA outperforms not only its simultaneous counterpart but also the extra-gradient method (EG) and the multistep method GDmax (employing $10$ ascent steps per descent step). For the Minimax-PPA method we only counted iterations but did not account for the computational cost of the double inner procedure which required over 100 solves of a proximally regularized subproblem per iteration. We suspect that for a significantly more ill-conditioned problem the Minimax-PPA methods might have performed more competitively.

In order to account for differences in step sizes we do a grid search across possible step sizes for the two components and plot the number of iteration required to reach a target accuracy, see Figure 2. Since the Minimax-PPA method has many inner step sizes and number of inner loop calls to tune it cannot easily be compared here, so we excluded it. We can see that alternating GDA is not only convergent for many different combinations of step sizes but also consistently outperforms the other methods in terms of the required gradient oracle calls.

We also want to point out that, it might appear from the convergence behavior of the different methods that our toy example (56) is easier than the more classical bilinear problem of $\min_{x}\max_{y}\,xy$, see , where neither version of GDA converges. While for the latter problem the vector field is always perpendicular to the direction of solution, our new problem exhibits areas where the vector field points away from the solution (see the upper right corner of the Figure 1 (b)) and thus exhibits a novel (and challenging behavior) which cannot be captured by bilinear problems.

2 Adversarially robust learning

We now highlight the performance of alternating GDA for adversarial learning on the MNIST , Fashion MNIST and CIFAR10 datasets respectively. We focus on the adversarial learning formulation described in (4), which originated in and results in a nonconvex-strongly-concave minimax formulation for large enough $\gamma$. We use standard convolutional networks (CNN) for all three datasets. For MNIST and Fashion-MNIST we use the architecture proposed by of three convolutional layers followed by a dense layer and softmax output. For CIFAR10 we follow the default architecture in the tutorial of with seven convolutional layers where the third, fifth and seventh are followed by an average pooling operation.

Since the robust training did not significantly impact the performance of the CNNs on the clean test examples on any of the data sets, we only report the performance on the adversarial examples.

In contrast to multistep methods, as proposed in which aim to (approximately) solve the inner maximization problem and typically start in every iteration from either the “clean” training example (or a randomly perturbed point ), GDA can be interpreted as a warm starting procedure which stores the adversarial example computed in the previous epoch. This also emphasizes the advantage of alternating GDA (and why it can be considered the more natural approach) as this method uses computed adversarial examples right away whereas the simultaneous version stores them to only use them in the next epoch.

Although this is not the main focus this work, we also contrast the single step methods with a method approximately solving the maximization problem (GDmax, see ) and observe that while the multistep method slightly outperforms alternating GDA, see Figure 3, this comes at the cost of an $\approx 8$ times higher computation time (based on $\approx 15$ gradient ascent steps for the multistep method).

Nevertheless, all results clearly show that alternating GDA consistently outperforms simultaneous GDA without any additional computational cost.

Conclusion

We show novel complexity results for the alternating gradient descent ascent method for nonconvex-(strongly) concave minimax problems using stochastic or deterministic gradient evaluations. Since these bounds are only a first step into the analysis of alternating GDA in this sophisticated setting, they do not explain theoretically the benefit of the alternating version. However, we provide empirical evidence that this method is favorable.

References