On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems

Introduction

We consider the following smooth minimax optimization problem:

One of the simplest candidates for solving problem (1.1) is the natural generalization of gradient descent (GD) known as gradient descent ascent (GDA). At each iteration, this algorithm performs gradient descent over the variable $\mathbf{x}$ with the stepsize $\eta_{\mathbf{x}}$ and gradient ascent over the variable $\mathbf{y}$ with the stepsize $\eta_{\mathbf{y}}$. On the positive side, when the objective function $f$ is convex in $\mathbf{x}$ and concave in $\mathbf{y}$, there is a vast literature establishing asymptotic and nonasymptotic convergence for the average iterates generated by GDA with the equal stepsizes ($\eta_{\mathbf{x}}=\eta_{\mathbf{y}}$); (see, e.g., Korpelevich, 1976; Chen and Rockafellar, 1997; Nedić and Ozdaglar, 2009; Nemirovski, 2004; Du and Hu, 2018). Local linear convergence can also be shown under the additional assumption that $f$ is locally strongly convex in $\mathbf{x}$ and strongly concave in $\mathbf{y}$ (Cherukuri et al., 2017; Adolphs et al., 2018; Liang and Stokes, 2018). However, there has been no shortage of research highlighting the fact that in a general setting GDA with equal stepsizes can converge to limit cycles or even diverge (Benaım and Hirsch, 1999; Hommes and Ochea, 2012; Mertikopoulos et al., 2018).

Recent research has focused on alternative gradient-based algorithms that have guarantees beyond the convex-concave setting (Daskalakis et al., 2017; Heusel et al., 2017; Mertikopoulos et al., 2019; Mazumdar et al., 2019). Two-timescale GDA (Heusel et al., 2017) has been particularly popular. This algorithm, which involves unequal stepsizes ($\eta_{\mathbf{x}}\neq\eta_{\mathbf{y}}$), has been shown to empirically to alleviate the issues of limit circles and it has theoretical support in terms of local asymptotic convergence to Nash equilibria (Heusel et al., 2017, Theorem 2).

This asymptotic result stops short of providing an understanding of algorithmic efficiency, and it would be desirable to provide a stronger, nonasymptotic, theoretical convergence rate for two-timescale GDA in a general setting. In particular, the following general structure arises in many applications: $f(\mathbf{x},\cdot)$ is concave for any $\mathbf{x}$ and $\mathcal{Y}$ is a bounded set. Two typical examples include training of a neural network which is robust to adversarial examples (Madry et al., 2017) and learning of a robust classifier from multiple distributions (Sinha et al., 2018). Both of these schemes can be posed as nonconvex-concave minimax problems. Based on this observation, it is natural to ask the question: Are two-timescale GDA and stochastic GDA (SGDA) provably efficient for nonconvex-concave minimax problems?

This paper presents an affirmative answer to this question, providing nonasymptotic complexity results for two-time scale GDA and SGDA in two settings. In the nonconvex-strongly-concave setting, two-time scale GDA and SGDA require $O(\kappa^{2}\epsilon^{-2})$ gradient evaluations and $O(\kappa^{3}\epsilon^{-4})$ stochastic gradient evaluations, respectively, to return an $\epsilon$-stationary point of the function $\Phi(\cdot)=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ where $\kappa>0$ is a condition number. In the nonconvex-concave setting, two-time scale GDA and SGDA require $O(\epsilon^{-6})$ gradient evaluations and $O(\epsilon^{-8})$ stochastic gradient evaluations.

Main techniques:

Compared to GDmax and multistep GDA, two-time scale GDA and SGDA are harder to analyze. Indeed, $\mathbf{y}_{t}$ is not necessarily guaranteed to be close to $\mathbf{y}^{\star}(\mathbf{x}_{t})$ at each iteration and thus it is unclear that $\nabla_{\mathbf{x}}f(\mathbf{x}_{t},\mathbf{y}_{t})$ might a reasonable descent direction. To overcome this difficulty, we develop a new technique which analyzes the concave optimization with a slowly changing objective function. This is the main technical contribution of this paper.

Notation.

Related Work

Nonconvex-concave setting.

Nonconvex-concave minimax problems appear to be a class of tractable problems in the form of problem (1.1) and have emerged as a focus in optimization and machine learning (Namkoong and Duchi, 2016; Sinha et al., 2018; Rafique et al., 2018; Sanjabi et al., 2018; Grnarova et al., 2018; Lu et al., 2019; Nouiehed et al., 2019; Thekumparampil et al., 2019; Kong and Monteiro, 2019); see Table 1 for a comprehensive overview. We also wish to highlight the work of Grnarova et al. (2018), who proposed a variant of GDA for nonconvex-concave problem and the work of Sinha et al. (2018) and Sanjabi et al. (2018), who studied a class of inexact nonconvex SGD algorithms that can be categorized as variants of SGDmax for nonconvex-strongly-concave problem. Jin et al. (2019) analyzed the GDmax algorithm for nonconvex-concave problem and provided nonasymptotic convergence results.

Rafique et al. (2018) proposed “proximally guided stochastic mirror descent” and “variance reduced gradient” algorithms (PGSMD/PGSVRG) and proved that these algorithms find an approximate stationary point of $\Phi(\cdot):=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$. However, PGSMD/PGSVRG are nested-loop algorithms and convergence results were established only in the special case where $f(\mathbf{x},\cdot)$ is a linear function (Rafique et al., 2018, Assumption 2 D.2). Nouiehed et al. (2019) developed a multistep GDA (MGDA) algorithm by incorporating accelerated gradient ascent as the subroutine at each iteration. This algorithm provably finds an approximate stationary point of $f(\cdot,\cdot)$ for nonconvex-concave problems with the fast rate of $O(\epsilon^{-3.5})$. Very recently, Thekumparampil et al. (2019) have proposed a proximal dual implicit accelerated gradient (ProxDIAG) algorithm for nonconvex-concave problems and proved that the algorithm find an approximate stationary point of $\Phi(\cdot)$ with the rate of $O(\epsilon^{-3})$. This complexity result is also achieved by an inexact proximal point algorithm (Kong and Monteiro, 2019). All of these algorithms are, however, nested-loop algorithms and thus relatively complicated to implement. One would like to know whether the nested-loop structure is necessary or whether GDA, a single-loop algorithm, can be guaranteed to converge in the nonconvex-(strongly)-concave setting.

Nonconvex-nonconcave setting.

During the past decade, the study of nonconvex-nonconcave minimax problems has become a central topic in machine learning, inspired in part by the advent of generative adversarial networks (Goodfellow et al., 2014) and adversarial learning (Madry et al., 2017; Namkoong and Duchi, 2016; Sinha et al., 2018). Most recent work aims at defining a notion of goodness or the development of new procedures for reducing oscillations (Daskalakis and Panageas, 2018b; Adolphs et al., 2018; Mazumdar et al., 2019) and speeding up the convergence of gradient dynamics (Heusel et al., 2017; Balduzzi et al., 2018; Mertikopoulos et al., 2019; Lin et al., 2018). More specifically, Daskalakis and Panageas (2018b) studied minimax optimization (or zero-sum games) and show that the stable limit points of GDA are not necessarily Nash equilibria. Adolphs et al. (2018) and Mazumdar et al. (2019) proposed Hessian-based algorithms whose stable fixed points are exactly Nash equilibria. On the other hand, Balduzzi et al. (2018) developed a new symplectic gradient adjustment (SGA) algorithm for finding stable fixed points in potential games and Hamiltonian games. Heusel et al. (2017) proposed two-timescale GDA and show that Nash equilibria are stable fixed points of the continuous limit of two-timescale GDA under certain strong conditions. All of the existing convergence results are either local or asymptotic and can not be extended to cover our results in a nonconvex-concave setting. Very recently, Mertikopoulos et al. (2019) and Lin et al. (2018) provide nonasymptotic guarantees for a special class of nonconvex-nonconcave minimax problems under variational stability and the Minty condition. However, while both of these two conditions must hold in convex-concave setting, they do not necessarily hold in nonconvex-(strongly)-concave problem.

Online learning setting.

From the online learning perspective, it is crucial to understand if the proposed algorithm achieves no-regret property. For example, the optimistic algorithm (Daskalakis and Panageas, 2018a) is a no-regret algorithm, while the extragradient algorithm (Mertikopoulos et al., 2019) is not. In comparing limit behavior of zero-sum game dynamics, Bailey and Piliouras (2018) showed that the multiplicative weights update has similar property as GDA and specified the necessity of introducing the optimistic algorithms to study the last-iterate convergence.

Preliminaries

We recall basic definitions for smooth functions.

A function $f$ is $L$-Lipschitz if for $\forall\mathbf{x},\mathbf{x}^{\prime}$, we have $\left\|f(\mathbf{x})-f(\mathbf{x}^{\prime})\right\|\leq L\left\|\mathbf{x}-\mathbf{x}^{\prime}\right\|$.

We start by defining local surrogate for the global minimum of $\Phi$. A common surrogate in nonconvex optimization is the notion of stationarity, which is appropriate if $\Phi$ is differentiable.

A point $\mathbf{x}$ is an $\epsilon$-stationary point ($\epsilon\geq 0$) of a differentiable function $\Phi$ if $\|\nabla\Phi(\mathbf{x})\|\leq\epsilon$. If $\epsilon=0$, then $\mathbf{x}$ is a stationary point.

Definition 3.3 is sufficient for nonconvex-strongly-concave minimax problem since $\Phi(\cdot)=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ is differentiable in that setting. In contrast, a function $\Phi$ is not necessarily differentiable for general nonconvex-concave minimax problem even if $f$ is Lipschitz and smooth. A weaker condition that we make use of is the following.

Although Definition 3.7 uses the language of Moreau envelopes, it also connects to the function $\Phi$ as follows.

We remark that our notion of stationarity is natural in real scenarios. Indeed, many applications arising from adversarial learning can be formulated as the minimax problem (1.1), and, in this setting, $\mathbf{x}$ is the classifier while $\mathbf{y}$ is the adversarial noise for the data. Practitioners are often interested in finding a robust classifier $\mathbf{x}$ instead of recovering the adversarial noise $\mathbf{y}$. Any stationary point of the function $\Phi(\cdot)=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ corresponds precisely to a robust classifier that achieves better classification error.

There are also other notions of stationarity based on $\nabla f$ are proposed for nonconvex-concave minimax problems in the literature (Lu et al., 2019; Nouiehed et al., 2019). However, as pointed by Thekumparampil et al. (2019), these notions are weaker than that defined in Definition 3.3 and 3.7. For the sake of completeness, we specify the relationship between our notion of stationarity and other notions in Proposition 4.11 and 4.12.

Main Results

In this section, we present complexity results for two-timescale GDA and SGDA in the setting of nonconvex-strongly-concave and nonconvex-concave minimax problems.

The algorithmic schemes that we study are extremely simple and are presented in Algorithm 1 and 2. In particular, each iteration comprises one (stochastic) gradient descent step over $\mathbf{x}$ with the stepsize $\eta_{\mathbf{x}}>0$ and one (stochastic) gradient ascent step over $\mathbf{y}$ with the stepsize $\eta_{\mathbf{y}}>0$. The choice of stepsizes $\eta_{\mathbf{x}}$ and $\eta_{\mathbf{y}}$ is crucial for the algorithms in both theoretical and practical senses. In particular, classical GDA and SGDA assume that $\eta_{\mathbf{x}}=\eta_{\mathbf{y}}$, and the last iterate is only known convergent in strongly convex-concave problems (Liang and Stokes, 2018). Even in convex-concave settings (or bilinear settings as special cases), GDA requires the assistance of averaging or other strategy (Daskalakis and Panageas, 2018a) to converge, otherwise, with fixed stepsize, the last iterate will always diverge and hit the constraint boundary eventually (Daskalakis et al., 2017; Mertikopoulos et al., 2018; Daskalakis and Panageas, 2018a). In contrast, two-timescale GDA and SGDA ($\eta_{\mathbf{x}}\neq\eta_{\mathbf{y}}$) were shown to be locally convergent and practical in training GANs (Heusel et al., 2017).

One possible reason for this phenomenon is that the choice of $\eta_{\mathbf{x}}\neq\eta_{\mathbf{y}}$ reflects the nonsymmetric nature of nonconvex-(strongly)-concave problems. For sequential problems such as robust learning, where the natural order of min-max is important (i.e., min-max is not equal to max-min), practitioners often prefer faster convergence for the inner max problem. Therefore, it is reasonable for us to choose $\eta_{\mathbf{x}}\ll\eta_{\mathbf{y}}$ rather than $\eta_{\mathbf{x}}=\eta_{\mathbf{y}}$.

Finally, we make the standard assumption that the oracle $G=(G_{\mathbf{x}},G_{\mathbf{y}})$ is unbiased and has bounded variance.

In this subsection, we present the complexity results for two-time-scale GDA and SGDA in the setting of nonconvex-strongly-concave minimax problems. The following assumption is made throughout this subsection.

$\mathcal{Y}$ is a convex and bounded set with a diameter $D\geq 0$.

We present a technical lemma on the structure of the function $\Phi$ in the nonconvex-strongly-concave setting.

Since $\Phi$ is differentiable, the notion of stationarity in Definition 3.3 is our target given only access to the (stochastic) gradient of $f$. Denote $\Delta_{\Phi}=\Phi(\mathbf{x}_{0})-\min_{\mathbf{x}}\Phi(\mathbf{x})$, we proceed to provide theoretical guarantees for two-timescale GDA and SGDA algorithms.

Under Assumption 4.1 and 4.2 and letting the stepsizes $\eta_{\mathbf{x}},\eta_{\mathbf{y}}$ be chosen as the same in Theorem 4.4 with the batch size $M=\Theta(\max\{1,\kappa\sigma^{2}\epsilon^{-2}\})$, the iteration complexity of Algorithm 2 to return an $\epsilon$-stationary point is bounded by

which gives the total stochastic gradient complexity:

First, two-timescale GDA and SGDA are guaranteed to find an $\epsilon$-stationary point of $\Phi(\cdot)$ within $O(\kappa^{2}\epsilon^{-2})$ gradient evaluations and $O(\kappa^{3}\epsilon^{-4})$ stochastic gradient evaluations, respectively. The ratio of stepsizes $\eta_{\mathbf{y}}/\eta_{\mathbf{x}}$ is required to be $\Theta(\kappa^{2})$ due to the nonsymmetric nature of our problem (min-max is not equal to max-min). The quantity $O(\kappa^{2})$ reflects an efficiency trade-off in the algorithm.

Furthermore, both of the algorithms are only guaranteed to visit an $\epsilon$-stationary point within a certain number of iterations and return $\hat{\mathbf{x}}$ which is drawn from $\{\mathbf{x}_{t}\}_{t=1}^{T}$ at uniform. This does not mean that the last iterate $\mathbf{x}_{T}$ is the $\epsilon$-stationary point. Such a scheme and convergence result are standard in nonconvex optimization for GD or SGD to find stationary points. In practice, one usually returns the iterate when the learning curve stops changing significantly.

Finally, the minibatch size $M=\Theta(\epsilon^{-2})$ is necessary for the convergence property of two-timescale SGDA. Even though our proof technique can be extended to the purely stochastic setting ($M=1$), the complexity result becomes worse, i.e., $O(\kappa^{3}\epsilon^{-5})$. It remains open whether this gap can be closed or not and we leave it as future work.

2 Nonconvex-concave minimax problems

In this subsection, we present the complexity results for two-timescale GDA and SGDA in the nonconvex-concave minimax setting. The following assumption is made throughout this subsection.

$\mathcal{Y}$ is a convex and bounded set with a diameter $D\geq 0$.

We make several additional remarks. First, two-timescale GDA and SGDA are guaranteed to find an $\epsilon$-stationary point in terms of Moreau envelopes within $O(\epsilon^{-6})$ gradient evaluations and $O(\epsilon^{-8})$ stochastic gradient evaluations, respectively. The ratio of stepsizes $\eta_{\mathbf{y}}/\eta_{\mathbf{x}}$ is required to be $\Theta(1/\epsilon^{4})$ and this quantity reflects an efficiency trade-off in the algorithm. Furthermore, similar arguments as in Section 4.1 hold for the output of the algorithms here. Finally, the minibatch size $M=1$ is allowed in Theorem 4.9, which is different from the result in Theorem 4.5.

3 Relationship between the stationarity notions

We provide additional technical results on the relationship between our notions of stationarity and other notions based on $\nabla f$ in the literature (Lu et al., 2019; Nouiehed et al., 2019). In particular, we show that two notions can be translated in both directions with extra computational cost.

We present our results in the following two propositions.

Under Assumption 4.2, if a point $\hat{\mathbf{x}}$ is an $\epsilon$-stationary point in terms of Definition 3.3, an $O(\epsilon)$-stationary point $(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$ in terms of Definition 4.10 can be obtained using additional $O(\kappa\log(1/\epsilon))$ gradients or $O(\epsilon^{-2})$ stochastic gradients. Conversely, if a point $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is an $\epsilon/\kappa$-stationary point in terms of Definition 4.10, a point $\hat{\mathbf{x}}$ is an $O(\epsilon)$-stationary point in terms of Definition 3.3.

To translate the notion of stationarity based on $\nabla f$ to our notion of stationarity, we need to pay an additional factor of $O(\kappa\log(1/\epsilon))$ or $O(\epsilon^{-2})$ in the two settings. In this sense, our notion of stationarity is stronger than the notion based on $\nabla f$ in the literature (Lu et al., 2019; Nouiehed et al., 2019). We defer the proofs of these propositions to Appendix B.

4 Discussions

Second, our complexity results are also valid in the convex-concave setting and this does not contradict results showing the divergence of GDA with fixed stepsize. We note a few distinctions: (1) our results guarantee that GDA will visit $\epsilon$-stationary points at some iterates, which are not necessarily the last iterates; (2) our results only guarantee stationarity in terms of $\mathbf{x}_{t}$, not $(\mathbf{x}_{t},\mathbf{y}_{t})$. In fact, our proof permits the possibility of significant changes in $\mathbf{y}_{t}$ even when $\mathbf{x}_{t}$ is already close to stationarity. This together with our choice $\eta_{\mathbf{x}}\ll\eta_{\mathbf{y}}$, makes our results valid. To this end, we highlight that our algorithms can be used to achieve an approximate Nash equilibrium for convex-concave functions (i.e., optimality for both $\mathbf{x}$ and $\mathbf{y}$). Instead of averaging, we run two passes of two-timescale GDA or SGDA for min-max problem and max-min problem separately. That is, in the first pass we use $\eta_{\mathbf{x}}\ll\eta_{\mathbf{y}}$ while in the second pass we use $\eta_{\mathbf{x}}\gg\eta_{\mathbf{y}}$. Either pass will return an approximate stationary point for each players, which jointly forms an approximate Nash equilibrium.

Overview of Proofs

In this section, we sketch the complexity analysis for two-timescale GDA (Theorems 4.4 and 4.8).

In the nonconvex-strongly-concave setting, our proof involves setting a pair of stepsizes, $(\eta_{\mathbf{x}},\eta_{\mathbf{y}})$, which force $\{\mathbf{x}_{t}\}_{t\geq 1}$ to move much more slowly than $\{\mathbf{y}_{t}\}_{t\geq 1}$. Recall Lemma 4.3, which guarantees that $\mathbf{y}^{\star}(\cdot)$ is $\kappa$-Lipschitz:

If $\{\mathbf{x}_{t}\}_{t\geq 1}$ moves slowly, then $\{\mathbf{y}^{\star}(\mathbf{x}_{t})\}_{t\geq 1}$ also moves slowly. This allows us to perform gradient ascent on a slowly changing strongly-concave function $f(\mathbf{x}_{t},\cdot)$, guaranteeing that $\|\mathbf{y}_{t}-\mathbf{y}^{\star}(\mathbf{x}_{t})\|$ is small in an amortized sense. More precisely, letting the error be $\delta_{t}=\|\mathbf{y}^{\star}(\mathbf{x}_{t})-\mathbf{y}_{t}\|^{2}$, the standard analysis of inexact nonconvex gradient descent implies a descent inequality in which the sum of $\delta_{t}$ provides control:

The remaining step is to show that the second term is always small compared to the first term on the right-hand side. This can be done via a recursion for $\delta_{t}$ as follows:

where $\gamma<1$ and $\beta$ is small. Thus, $\delta_{t}$ exhibits a linear contraction and $\sum_{t=0}^{T}\delta_{t}$ can be controlled by the term $\sum_{t=0}^{T}\|\nabla\Phi(\mathbf{x}_{t})\|^{2}$.

2 Nonconvex-concave minimax problems

In this setting, the main idea is again to set a pair of learning rates $(\eta_{\mathbf{x}},\eta_{\mathbf{y}})$ which force $\{\mathbf{x}_{t}\}_{t\geq 1}$ to move more slowly than $\{\mathbf{y}_{t}\}_{t\geq 1}$. However, $f(\mathbf{x},\cdot)$ is merely concave and $\mathbf{y}^{\star}(\cdot)$ is not unique. This means that, even if $\mathbf{x}_{1},\mathbf{x}_{2}$ are extremely close, $\mathbf{y}^{\star}(\mathbf{x}_{1})$ can be dramatically different from $\mathbf{y}^{\star}(\mathbf{x}_{2})$. Thus, $\|\mathbf{y}_{t}-\mathbf{y}^{\star}(\mathbf{x}_{t})\|$ is no longer a viable error to control.

Fortunately, Lemma 4.7 implies that $\Phi$ is Lipschitz. That is to say, when the stepsize $\eta_{\mathbf{x}}$ is very small, $\{\Phi(\mathbf{x}_{t})\}_{t\geq 1}$ moves slowly:

Again, this allows us to perform gradient ascent on a slowly changing concave function $f(\mathbf{x}_{t},\cdot)$, and guarantees that $\Delta_{t}=f(\mathbf{x}_{t},\mathbf{z})-f(\mathbf{x}_{t},\mathbf{y}_{t})$ is small in an amortized sense where $\mathbf{z}\in\mathbf{y}^{\star}(\mathbf{x}_{t})$. The analysis of inexact nonconvex subgradient descent (Davis and Drusvyatskiy, 2019) implies that $\Delta_{t}$ comes into the following descent inequality:

where the first term on the right-hand side is the error term. The remaining step is again to show the error term is small compared to the sum of the first two terms on the right-hand side. To bound the term $\sum_{t=0}^{T}\Delta_{t}$, we recall the following inequalities and use a telescoping argument (where the optimal point $\mathbf{y}^{\star}$ does not change):

The major challenge here is that the optimal solution $\mathbf{y}^{\star}(\mathbf{x}_{t})$ can change dramatically and the telescoping argument does not go through. An important observation is, however, that (5.1) can be proved if we replace the $\mathbf{y}^{\star}$ by any $\mathbf{y}\in\mathcal{Y}$, while paying an additional cost that depends on the difference in function value between $\mathbf{y}^{\star}$ and $\mathbf{y}$. More specifically, we pick a block of size $B=O(\epsilon^{2}/\eta_{\mathbf{x}})$ and show that the following statement holds for any $s\leq\forall t<s+B$,

We perform an analysis on the blocks where the concave problems are similar so the telescoping argument can now work. By carefully choosing $\eta_{\mathbf{x}}$, the term $\sum_{t=0}^{T}\Delta_{t}$ can also be well controlled.

Experiments

We mainly follow the setting of Sinha et al. (2018) and consider training a neural network classifier on three datasetshttps://keras.io/datasets/: MNIST, Fashion-MNIST, and CIFAR-10, with the default cross validation. The architecture consists of $8\times 8$, $6\times 6$ and $5\times 5$ convolutional filter layers with ELU activations followed by a fully connected layer and softmax output. Small and large adversarial perturbation is set with $\gamma\in\{0.4,1.3\}$ as the same as Sinha et al. (2018). The baseline approach is denoted as GDmA in which $\eta_{\mathbf{x}}=\eta_{\mathbf{y}}=10^{-3}$ and each inner loop contains $20$ gradient ascent. Two-timescale GDA is denoted as GDA in which $\eta_{\mathbf{x}}=5\times 10^{-5}$ and $\eta_{\mathbf{y}}=10^{-3}$. Figure 1 and 2 show that GDA consistently outperforms GDmA on all datasets. Compared to MNIST and Fashion-MNIST, the improvement on CIFAR-10 is more significant which is worthy further exploration in the future.

Conclusion

In this paper, we show that two-time-scale GDA and SGDA return an $\epsilon$-stationary point in $O(\kappa^{2}\epsilon^{-2})$ gradient evaluations and $O(\kappa^{3}\epsilon^{-4})$ stochastic gradient evaluations in the nonconvex-strongly-concave case, and $O(\epsilon^{-6})$ gradient evaluations and $O(\epsilon^{-8})$ stochastic gradient evaluations in the nonconvex-concave case. Thus, these two algorithms are provably efficient in these settings. Future work aim to derive a lower bound for the complexity first-order algorithms in nonconvex-concave minimax problems.

Acknowledgments

We would like to thank three anonymous referees for constructive suggestions that improve the quality of this paper. This work was supported in part by the Mathematical Data Science program of the Office of Naval Research under grant number N00014-18-1-2764.

References

Appendix A Proof of Technical Lemmas

In this section, we provide complete proofs for the lemmas in Section 3 and Section 4.

We provide a proof for an expanded version of Lemma 3.6.

Proof. By the definition of $\Phi$, we have

A.2 Proof of Lemma 3.8

A.3 Proof of Lemma 4.3

Letting $\mathbf{y}=\mathbf{y}^{\star}(\mathbf{x}_{2})$ in (A.1) and $\mathbf{y}=\mathbf{y}^{\star}(\mathbf{x}_{1})$ in (A.2) and summing the resulting two inequalities yields

Recall that $f(\mathbf{x}_{1},\cdot)$ is $\mu$-strongly concave, we have

Since $\mathbf{y}^{\star}(\mathbf{x})$ is unique and $\mathcal{Y}$ is convex and bounded, we conclude from Danskin’s theorem [Rockafellar, 2015] that $\Phi$ is differentiable with $\nabla\Phi(\mathbf{x})=\nabla_{\mathbf{x}}f\left(\mathbf{x},\mathbf{y}^{\star}(\mathbf{x})\right)$. Since $\nabla\Phi(\mathbf{x})=\nabla_{\mathbf{x}}f\left(\mathbf{x},\mathbf{y}^{\star}(\mathbf{x})\right)$, we have

A.4 Proof of Lemma 4.7

A.5 Proof of Lemma on Stochastic Gradient

The following lemma establishes some properties of the stochastic gradients sampled at each iteration.

$\frac{1}{M}\sum_{i=1}^{M}G_{\mathbf{x}}(\mathbf{x}_{t},\mathbf{y}_{t},\xi_{i})$ and $\frac{1}{M}\sum_{i=1}^{M}G_{\mathbf{y}}(\mathbf{x}_{t},\mathbf{y}_{t},\xi_{i})$ are unbiased and have bounded variance,

Proof. Since $G=(G_{\mathbf{x}},G_{\mathbf{y}})$ is unbiased, we have

Putting these pieces together yields the desired result. $\Box$

Appendix B Proof for Propositions 4.11 and 4.12

In this section, we provide the detailed proof of Propositions 4.11 and 4.12.

Assume that a point $\hat{\mathbf{x}}$ satisfies that $\|\nabla\Phi(\hat{\mathbf{x}})\|\leq\epsilon$, the optimization problem $\max_{\mathbf{y}\in\mathcal{Y}}f(\hat{\mathbf{x}},\mathbf{y})$ is strongly concave (cf. Assumption 4.2) and $\mathbf{y}^{\star}(\hat{\mathbf{x}})$ is uniquely defined. We apply gradient descent for solving such problem and obtain a point $\mathbf{y}^{\prime}\in\mathcal{Y}$ satisfying that

If $\|\nabla\Phi(\hat{\mathbf{x}})\|\leq\epsilon$, we have

The required number of gradient evaluations is $\mathcal{O}(\kappa\log(1/\epsilon))$. This argument holds for applying stochastic gradient with proper stepsize and the required number of stochastic gradient evaluations is $\mathcal{O}(1/\epsilon^{2})$.

Conversely, if a point $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ satisfies that

Since $f(\hat{\mathbf{x}},\cdot)$ is $\mu$-strongly-concave over $\mathcal{Y}$, the global error bound condition [Drusvyatskiy and Lewis, 2018] holds true here and we have

B.1 Proof of Proposition 4.12

The required number of gradient evaluations is $O(\epsilon^{-2})$ [Mokhtari et al., 2019a]. This argument holds for applying stochastic mirror-prox algorithm and the required number of stochastic gradient evaluations is $O(\epsilon^{-4})$ [Juditsky et al., 2011].

By the definition of $\hat{\mathbf{y}}^{+}$, we have

Putting these pieces together yields that

Appendix C Proof of Theorems in Section 4.1

In this subsection, we present the full version of Theorems 4.4 and 4.5 with the detailed choice of $\eta_{\mathbf{x}}$, $\eta_{\mathbf{y}}$ and $M$ which are important to subsequent analysis.

which is also the total gradient complexity of the algorithm.

C.2 Proof of Technical Lemmas

In this subsection, we present three key lemmas which are important for the subsequent analysis.

For two-timescale GDA, the iterates $\{\mathbf{x}_{t}\}_{t\geq 1}$ satisfies the following inequality,

For two-timescale SGDA, the iterates $\{\mathbf{x}_{t}\}_{t\geq 1}$ satisfy the following inequality:

Plugging $\mathbf{x}_{t}-\mathbf{x}_{t-1}=-\eta_{\mathbf{x}}\nabla_{\mathbf{x}}f(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$ into (C.1) yields that

By the Cauchy-Schwartz inequality, we have

Plugging (C.2) and (C.4) into (C.2) yields the first desired inequality.

We proceed to the stochastic setting. Plugging $\mathbf{x}_{t}-\mathbf{x}_{t-1}=-\eta_{\mathbf{x}}\left(\frac{1}{M}\sum_{i=1}^{M}G_{\mathbf{x}}(\mathbf{x}_{t-1},\mathbf{y}_{t-1},\xi_{i})\right)$ into (C.1) yields that

Taking an expectation on both sides, conditioned on $(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$, yields that

Plugging (C.2) and (C.4) into (C.2) and taking the expectation of both sides yields the second desired inequality. $\Box$

For two-timescale GDA, let $\delta_{t}=\|\mathbf{y}^{\star}(\mathbf{x}_{t})-\mathbf{y}_{t}\|^{2}$, the following statement holds true,

Since $\mathbf{y}^{\star}(\cdot)$ is $\kappa$-Lipschitz, $\|\mathbf{y}^{\star}(\mathbf{x}_{t})-\mathbf{y}^{\star}(\mathbf{x}_{t-1})\|\leq\kappa\|\mathbf{x}_{t}-\mathbf{x}_{t-1}\|$. Furthermore, we have

Putting these pieces together yields the first desired inequality.

Since $\mathbf{y}^{\star}(\cdot)$ is $\kappa$-Lipschitz, $\|\mathbf{y}^{\star}(\mathbf{x}_{t})-\mathbf{y}^{\star}(\mathbf{x}_{t-1})\|\leq\kappa\|\mathbf{x}_{t}-\mathbf{x}_{t-1}\|$. Furthermore, we have

Putting these pieces together yields the second desired inequality. $\Box$

For two-timescale GDA, let $\delta_{t}=\|\mathbf{y}^{\star}(\mathbf{x}_{t})-\mathbf{y}_{t}\|^{2}$, the following statement holds true,

Combining (C.8) with the first inequality in Lemma C.3 yields that

Since $\nabla\Phi(\mathbf{x}_{t-1})=\nabla_{\mathbf{x}}f\left(\mathbf{x}_{t-1},\mathbf{y}^{\star}(\mathbf{x}_{t-1})\right)$, we have

Putting these pieces together yields the first desired inequality.

We proceed to the stochastic setting, combining (C.8) with the second inequality in Lemma C.3 yields that

Since $\nabla\Phi(\mathbf{x}_{t-1})=\nabla_{\mathbf{x}}f\left(\mathbf{x}_{t-1},\mathbf{y}^{\star}(\mathbf{x}_{t-1})\right)$, we have

Putting these pieces together yields the second desired inequality. $\Box$

C.3 Proof of Theorem C.1

Combining (C.3) with the first inequality in Lemma C.5 yields that,

Summing up (C.10) over $t=1,2,\ldots,T+1$ and rearranging the terms yields that

Putting these pieces together yields that

By the definition of $\Delta_{\Phi}$, we have

This implies that the number of iterations required by Algorithm 1 to return an $\epsilon$-stationary point is bounded by

which gives the same total gradient complexity.

C.4 Proof of Theorem C.2

Combining (C.11) with the second inequality in Lemma C.5 yields that,

Summing up (C.4) over $t=1,2,\ldots,T+1$ and rearranging the terms yields that

Putting these pieces together yields that

By the definition of $\Delta_{\Phi}$, we have

This implies that the number of iterations required by Algorithm 2 to return an $\epsilon$-stationary point is bounded by

iterations, which gives the total gradient complexity of the algorithm:

Appendix D Proof of Theorems in Section 4.2

In this subsection, we present the full version of Theorems 4.8 and 4.9 with the detailed choice of $\eta_{\mathbf{x}}$, $\eta_{\mathbf{y}}$ and $M$ which are important to subsequent analysis.

which is also the total gradient complexity of the algorithm.

which is also the total gradient complexity of the algorithm.

D.2 Proof of Technical Lemmas

In this subsection, we present three key lemmas which are important for the subsequent analysis.

For two-timescale GDA, let $\Delta_{t}=\Phi(\mathbf{x}_{t})-f(\mathbf{x}_{t},\mathbf{y}_{t})$, the following statement holds true,

Since $f(\cdot,\mathbf{y})$ is $L$-Lipschitz for any $\mathbf{y}\in\mathcal{Y}$, we have

Furthermore, $\Phi(\hat{\mathbf{x}}_{t-1})\geq f(\hat{\mathbf{x}}_{t-1},\mathbf{y}_{t-1})$. By the definition of $\Delta_{t}$, we have

We proceed to the stochastic setting. Indeed, we have

Taking an expectation of both sides of the above inequality, conditioned on $(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$, together with Lemma A.2 and the Lipschitz property of $f(\cdot,\mathbf{y}_{t-1})$ yields that

Taking the expectation of both sides together with Lemma A.2 yields that

Combining with (D.4) and (D.5) yields that

For two-timescale GDA, let $\Delta_{t}=\Phi(\mathbf{x}_{t})-f(\mathbf{x}_{t},\mathbf{y}_{t})$, the following statement holds true for $\forall s\leq t-1$,

Proof. We first consider the deterministic setting. For any $\mathbf{y}\in\mathcal{Y}$, the convexity of $\mathcal{Y}$ and the update formula of $\mathbf{y}_{t}$ imply that

Plugging $\mathbf{y}=\mathbf{y}^{\star}(\mathbf{x}_{s})$ ($s\leq t-1$) in the above inequality yields that

By the definition of $\Delta_{t-1}$, we have

Since $f(\mathbf{x}_{s},\mathbf{y}^{\star}(\mathbf{x}_{s}))\geq f(\mathbf{x}_{s},\mathbf{y})$ for $\forall\mathbf{y}\in\mathcal{Y}$, we have

Since $f(\cdot,\mathbf{y})$ is $L$-Lipschitz for any $\mathbf{y}\in\mathcal{Y}$, we have

Putting these pieces together yields the first desired inequality.

We proceed to the stochastic setting. For $\forall\mathbf{y}\in\mathcal{Y}$, we use the similar argument and obtain that

Taking an expectation of both sides of the above equality, conditioned on $(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$, together with Lemma A.2 yields that

Taking the expectation of both sides together with Lemma A.2 yields that

Plugging $\mathbf{y}=\mathbf{y}^{\star}(\mathbf{x}_{s})$ ($s\leq t-1$) in the above inequality yields that

By the definition of $\Delta_{t-1}$, we have

By the fact that $f(\cdot,\mathbf{y})$ is $L$-Lipschitz for $\forall\mathbf{y}\in\mathcal{Y}$ and Lemma A.2, we have

Putting these pieces together with (D.2) yields the second desired inequality. $\Box$

Without loss of generality, we assume that $B\leq T+1$ such that $(T+1)/B$ is an integer. The following lemma provides an upper bound for $\frac{1}{T+1}(\sum_{t=0}^{T}\Delta_{t})$ for two-timescale GDA and SGDA using a localization technique.

For two-timescale GDA, let $\Delta_{t}=\Phi(\mathbf{x}_{t})-f(\mathbf{x}_{t},\mathbf{y}_{t})$, the following statement holds true,

Proof. We first consider the deterministic setting. In particular, we divide $\{\Delta_{t}\}_{t=0}^{T}$ into several blocks in which each block contains at most $B$ terms, given by

Furthermore, letting $s=0$ in the first inequality in Lemma (D.4) yields that

Similarly, letting $s=jB$ yields that, for $1\leq j\leq\frac{T+1}{B}-1$,

Plugging (D.2) and (D.9) into (D.7) yields

Since $f(\cdot,\mathbf{y})$ is $L$-Lipschitz for any $\mathbf{y}\in\mathcal{Y}$, we have

Plugging (D.11) into (D.10) yields the desired inequality. As for the stochastic case, letting $s=jB$ in the second inequality in Lemma D.4 yields that

Using the similar argument with (D.12) and (D.7) yields the second desired inequality. $\Box$

D.3 Proof of Theorem D.1

Summing up the first inequality in Lemma D.3 over $t=1,2,\ldots,T+1$ yields that

Combining the above inequality with the first inequality in Lemma D.5 yields that

By the definition of $\widehat{\Delta}_{\Phi}$, we have

This implies that the number of iterations required by Algorithm 1 to return an $\epsilon$-stationary point is bounded by

which gives the same total gradient complexity.

D.4 Proof of Theorem D.2

Summing up the second inequality in Lemma D.3 over $t=1,2,\ldots,T+1$ yields that

Combining the above inequality with the second inequality in Lemma D.5 yields that

By the definition of $\widehat{\Delta}_{\Phi}$, we have

Letting $B=1$ for $D=0$ and $B=\frac{D}{2}\sqrt{\frac{1}{\eta_{\mathbf{x}}\eta_{\mathbf{y}}L\sqrt{L^{2}+\sigma^{2}}}}$ for $D>0$, we have

This implies that the number of iterations required by Algorithm 2 to return an $\epsilon$-stationary point is bounded by

which gives the same total gradient complexity.

Appendix E Results for GDmax and SGDmax

The sample size $M=O(\kappa\sigma^{2}\epsilon^{-2})$ guarantees that the variance is less than $\epsilon^{2}/\kappa$ so that the average stochastic gradients over the batch are sufficiently close to the true gradients $\nabla_{\mathbf{x}}f$ and $\nabla_{\mathbf{y}}f$.

When $\sigma^{2}\lesssim\varepsilon^{2}$, the stochastic gradients are sufficiently close to the true gradients $\nabla_{\mathbf{x}}f$ and $\nabla_{\mathbf{y}}f$ and the gradient complexity of SGDmax matches that of GDmax.

We present the gradient complexity bound of the gradient-ascent-based $\zeta$-accurate max-oracle in the following lemma.

Proof. Since $f(\mathbf{x}_{t},\cdot)$ is $\mu$-strongly concave, we have

Proof of Theorem E.1: It is easy to find that the first descent inequality in Lemma C.3 is applicable to GDmax:

Since $\nabla\Phi(\mathbf{x}_{t-1})=\nabla_{\mathbf{x}}f\left(\mathbf{x}_{t-1},\mathbf{y}^{\star}(\mathbf{x}_{t-1})\right)$, we have

Plugging (E.2) and (E.3) into (E.1) yields that

Summing up (E.4) over $t=1,2,\ldots,T+1$ and rearranging the terms yields that

By the definition of $\eta_{\mathbf{x}}$ and $\Delta_{\Phi}$, we conclude that

This implies that the number of iterations required by Algorithm 3 to return an $\epsilon$-stationary point is bounded by

Combining Lemma E.5 gives the total gradient complexity of Algorithm 3:

E.2 Proof of Theorem E.2

We present the gradient complexity bound of the stochastic-gradient-ascent-based $\zeta$-accurate max-oracle in terms of stochastic gradient in the following lemma.

Proof. Since $f(\mathbf{x}_{t},\cdot)$ is $\mu$-strongly concave, we have

Proof of Theorem E.2: It is easy to find that the second descent inequality in Lemma C.3 is applicable to SGDmax:

Since $\nabla\Phi(\mathbf{x}_{t-1})=\nabla_{\mathbf{x}}f\left(\mathbf{x}_{t-1},\mathbf{y}^{\star}(\mathbf{x}_{t-1})\right)$, we have

Summing up (E.7) over $t=1,2,\ldots,T+1$ and rearranging the terms yields that

By the definition of $\eta_{\mathbf{x}}$ and $\Delta_{\Phi}$, we conclude that

This implies that the number of iterations required by Algorithm 4 to return an $\epsilon$-stationary point is bounded by

Note that the same batch set can be reused to construct the unbiased stochastic gradients for both $\nabla_{\mathbf{x}}f(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$ and $\nabla_{\mathbf{y}}f(\mathbf{x}_{t-1},\mathbf{y}_{t-1})$ at each iteration. Combining Lemma E.6 gives the total gradient complexity of Algorithm 4:

E.3 Proof of Theorem E.3

We present the gradient complexity bound of the gradient-ascent-based $\zeta$-accurate max-oracle in the following lemma.

Proof. Since $f(\mathbf{x}_{t},\cdot)$ is concave, we have

Proof of Theorem E.3: It is easy to find that the first descent inequality in Lemma D.3 is applicable to GDmax:

Summing up (E.8) over $T=1,2,\ldots,T+1$ together with $\Delta_{t-1}\leq\zeta$ and rearranging the terms yields that

By the definition of $\eta_{\mathbf{x}}$ and $\widehat{\Delta}_{\Phi}$, we have

This implies that the number of iterations required by Algorithm 3 to return an $\epsilon$-stationary point is bounded by

Combining Lemma E.7 gives the total gradient complexity of Algorithm 3:

E.4 Proof of Theorem E.4

We present the gradient complexity bound of the stochastic-ascent-based $\zeta$-accurate max-oracle in the following lemma.

Proof of Theorem E.4: It is easy to find that the second descent inequality in Lemma D.3 is applicable to SGDmax:

Summing up (E.10) over $T=1,2,\ldots,T+1$ together with $\Delta_{t-1}\leq\zeta$ and rearranging the terms yields that

By the definition of $\eta_{\mathbf{x}}$ and $\widehat{\Delta}_{\Phi}$, we have

This implies that the number of iterations required by Algorithm 4 to return an $\epsilon$-stationary point is bounded by

Combining Lemma E.8 gives the total gradient complexity of Algorithm 3: