Near-Optimal Algorithms for Minimax Optimization

Introduction

The theoretical study of solutions of problem (1) has been an focus of several decades of research in mathematics, statistics, economics and computer science (Basar and Olsder, 1999; Nisan et al., 2007; Von Neumann and Morgenstern, 2007; Facchinei and Pang, 2007; Berger, 2013). Recently, this line of research has become increasingly relevant to algorithmic machine learning, with applications including robustness in adversarial learning (Goodfellow et al., 2014; Sinha et al., 2018), prediction and regression problems (Cesa-Bianchi and Lugosi, 2006; Xu et al., 2009) and distributed computing (Shamma, 2008; Mateos et al., 2010). Moreover, real-world machine-learning systems are increasingly embedded in multi-agent systems or matching markets and subject to game-theoretic constraints (Jordan, 2018).

Can we design first-order algorithms that achieve the lower bounds in these settings?

This paper presents an affirmative answer by resolving the above open problem up to logarithmic factors. More specifically, our contribution is as follows.

We provide a head-to-head comparison between our results and existing results in the literature in Table 1 for convex-concave settings, and Table 2 for nonconvex-concave settings.

Related work

To the best of our knowledge, the earliest algorithmic schemes for solving the bilinear minimax problem, $\min_{\mathbf{x}\in\Delta^{m}}\max_{\mathbf{y}\in\Delta^{n}}\mathbf{x}^{\top}A\mathbf{y}$, date back to Brown’s fictitious play (Brown, 1951) and Dantzig’s simplex method (Dantzig, 1998). This problem can also be solved by Korpelevich’s extragradient (EG) algorithm (Korpelevich, 1976), which can be shown to be linearly convergent when $A$ is square and full rank (Tseng, 1995). There are also several recent papers studying the convergence of EG and its variants; see Chambolle and Pock (2011); Malitsky (2015); Yadav et al. (2018) for reflected gradient descent ascent, Daskalakis et al. (2018); Mokhtari et al. (2019b, a) for optimistic gradient descent ascent (OGDA) and Rakhlin and Sridharan (2013a, b); Mertikopoulos et al. (2019); Chavdarova et al. (2019); Hsieh et al. (2019); Mishchenko et al. (2019) for other variants. In the bilinear setting, Daskalakis et al. (2018) established the convergence of the optimistic gradient descent ascent (OGDA) method to a neighborhood of the solution; Liang and Stokes (2019) proved the linear convergence of the OGDA algorithm using a dynamical system approach. Very recently, Mokhtari et al. (2019b) have proposed a unified framework for achieving the sharpest convergence rates of both EG and OGDA algorithms.

For the convex-concave minimax problem, Nemirovski (2004) proved that his mirror-prox algorithm returns an $\epsilon$-saddle point within the gradient complexity of $O(\epsilon^{-1})$ when $\mathcal{X}$ and $\mathcal{Y}$ are bounded. This algorithm was subsequently generalized by Auslender and Teboulle (2005) to a class of distance-generating functions, and the complexity result was extended to unbounded sets and composite objectives (Monteiro and Svaiter, 2010, 2011) using the hybrid proximal extragradient algorithm with different error criteria. Nesterov (2007) developed a dual extrapolation algorithm which possesses the same complexity bound as in Nemirovski (2004). Later on, Tseng (2008) presented a unified treatment of these algorithms and a refined convergence analysis with same complexity result. Nedić and Ozdaglar (2009) analyzed the (sub)gradient descent ascent algorithm for convex-concave saddle point problems when the (sub)gradients are bounded over the constraint sets. Abernethy et al. (2019) presented a Hamiltonian gradient descent algorithm with last-iterate convergence under a “sufficiently bilinear” condition.

Several papers have studied special cases in the convex-concave setting. For the special case when the objective function is a composite bilinear form, $f(\mathbf{x},\mathbf{y})=g(\mathbf{x})+\mathbf{x}^{\top}A\mathbf{y}-h(\mathbf{y})$, Chambolle and Pock (2011) introduced a primal-dual algorithm that converges to a saddle point with the rate of $O(1/\epsilon)$ when the convex functions $g$ and $h$ are smooth. Nesterov (2005) proposed a smoothing technique and proved that the resulting algorithm achieves an improved rate with better dependence on Lipschitz constant of $\nabla g$ when $h$ is the convex and smooth function and $\mathcal{X},\mathcal{Y}$ are both bounded. He and Monteiro (2016) and Kolossoski and Monteiro (2017) proved that such result also hold when $\mathcal{X},\mathcal{Y}$ are unbounded or the space is non-Euclidean. Chen et al. (2014, 2017) generalized Nesterov’s technique to develop optimal algorithms for solving a class of stochastic saddle point problems and stochastic monotone variational inequalities. For a class of certain purely bilinear games where $g$ and $h$ are zero functions, Azizian et al. (2020) demonstrated that linear convergence is possible for several algorithms and their new algorithm achieved the tight bound. The second case is the so-called affinely constrained smooth convex problem, i.e., $\min_{\mathbf{x}\in\mathcal{X}}g(\mathbf{x}),\textnormal{s.t.}\ A\mathbf{x}=\mathbf{u}$. Esser et al. (2010) proposed a $O(\epsilon^{-1})$ primal-dual algorithm while Lan and Monteiro (2016) provided a first-order augmented Lagrangian method with the same $O(\epsilon^{-1})$ rate. By exploiting the structure, Ouyang et al. (2015) proposed a near-optimal algorithm in this setting.

Preliminaries

In this section, we clarify the notation used in this paper, review some background and provide formal definitions for the class of functions and optimality measure considered in this paper.

1 Minimax optimization

Furthermore, $\phi$ is $\mu$-strongly-concave if $-\phi$ is $\mu$-strongly-convex. If we set $\mu=0$, then we recover the definitions of convexity and concavity for a continuous differentiable function.

we assume that $f(\cdot,\mathbf{y})$ is convex for each $\mathbf{y}\in\mathcal{Y}$ and $f(\mathbf{x},\cdot)$ is concave for each $\mathbf{x}\in\mathcal{X}$. Here $\mathcal{X}$ and $\mathcal{Y}$ are both convex and bounded. Under these conditions, the Sion’s minimax theorem (Sion, 1958) guarantees that

Furthermore, there exists at least one saddle point (or Nash equilibrium) $(\mathbf{x}^{\star},\mathbf{y}^{\star})\in\mathcal{X}\times\mathcal{Y}$ such that the following equality holds true:

Therefore, for any point $(\hat{\mathbf{x}},\hat{\mathbf{y}})\in\mathcal{X}\times\mathcal{Y}$, the duality gap $\max_{\mathbf{y}\in\mathcal{Y}}f(\hat{\mathbf{x}},\mathbf{y})-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\hat{\mathbf{y}})$ forms the basis for a standard optimality criterion. Formally, we define

A point $(\hat{\mathbf{x}},\hat{\mathbf{y}})\in\mathcal{X}\times\mathcal{Y}$ is an $\epsilon$-saddle point of a convex-concave function $f(\cdot,\cdot)$ if $\max_{\mathbf{y}\in\mathcal{Y}}f(\hat{\mathbf{x}},\mathbf{y})-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\hat{\mathbf{y}})\leq\epsilon$. If $\epsilon=0$, then $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is a saddle point.

Nonconvex-concave setting:

If $\epsilon=0$, then $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is a stationary point.

We note that this notion of stationarity of $f$ (Definition 3.5) is closely related to an optimality notion in terms of stationary points of the function $\Phi(\cdot):=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ for nonconvex-concave functions. We refer readers to Appendix A.1 for more discussion.

2 Nesterov’s accelerated gradient descent

The following theorem provides an upper bound on the gradient complexity of AGD; i.e., the total number of gradient evaluations to find an $\epsilon$-optimal point in terms of function value.

Algorithm Components

In this section, we present two main algorithm components. Both of them are crucial for our final algorithms to achieve near-optimal convergence rates.

Our first component is the Accelerated Proximal Point Algorithm (APPA, Algorithm 2) for minimizing a function $g(\cdot)$. Comparing APPA with classical AGD (Algorithm 1), we note that both of them have momentum steps which yield acceleration. The major difference is in Line 4 of Algorithm 2, where APPA solves a proximal subproblem

We present an inexact version in Algorithm 2 where we tolerate a small error $\delta$ in terms of the function value in solving the proximal subproblem (4). That is, the solution $\mathbf{x}_{t}$ satisfies

We conclude that APPA has a unique advantage over AGD in settings where $g$ does not have a smoothness property but the proximal step (4) is easy to solve. These settings include LASSO (Beck and Teboulle, 2009), as well as minimax optimization problems (as we show in later sections).

2 Accelerated Solver for Minimax Proximal Steps

In minimax optimization problems of the form (1), we are interested in solving the following proximal subproblem as follows,

which is equivalent to solving the following minimax problem:

For a generic strongly-convex-strongly-concave function $g(\cdot,\cdot)$, solving a minimax problem is equivalent to solving a maximin problem, due to Sion’s minimax theorem:

A straightforward way of solving the maximin problem is to use a double-loop algorithm which solves the maximization and minimization problems on two different time scales. Specifically, the inner loop performs AGD on function $g(\cdot,\mathbf{y})$ to solve the inner minimization; i.e., to compute $\Psi(\mathbf{y}):=\min_{\mathbf{x}\in\mathcal{X}}g(\mathbf{x},\mathbf{y})$ for each $\mathbf{y}$, and the outer loop performs Accelerated Gradient Ascent (AGA) on the function $\Psi(\cdot)$ to solve the outer maximization. Since the algorithm aims to solve a maximin problem we use AGA-AGD, and we name the algorithm Maximin-AG2. See Algorithm 3 for the formal version of this algorithm. We also incorporate Lines 8-9 to check termination conditions, which ensures that the output achieves the desired optimality. The theoretical guarantee for Algorithm 3 is given in the following theorem.

Accelerating Convex-Concave Optimization

In this section, we present our main results for accelerating convex-concave optimization. We first present our new near-optimal algorithm and its theoretical guarantee for optimizing strongly-convex-strongly-concave functions. Then, we use simple reduction arguments to obtain results for strongly-convex-concave and convex-concave functions.

With the algorithm components from Section 4 in hand, we are now ready to state our near-optimal algorithm. Algorithm 4 is a simple combination of Algorithm 2 and Algorithm 3. Its outer loop performs an inexact APPA to minimize the function $\Phi(\cdot):=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$, while the inner loop uses Maximin-AG2 to solve the proximal subproblem (5), which is equivalent to solving (6). At the end, after finding a near-optimal $\mathbf{x}_{T}$, Algorithm 4 performs another AGD on the function $-f(\mathbf{x}_{T},\cdot)$ to find a near-optimal $\mathbf{y}_{T}$. The theoretical guarantee for the algorithm is given in the following theorem.

2 Strongly-convex-concave setting

Our result in the strongly-convex-strongly-concave setting readily implies a near-optimal result in the strongly-convex-concave setting. Consider the following auxiliary function for an arbitrary $\mathbf{y}_{0}\in\mathcal{Y}$ which is defined by

By construction, it is clear that the difference between $f$ and $f_{\epsilon,\mathbf{y}}$ is small in terms of function value:

This implies, according to Definition 3.4, that any $(\epsilon/2)$-saddle point of function $f_{\epsilon,\mathbf{y}}$ is also a $\epsilon$-saddle point of function $f$, and thus it is sufficient to only solve the problem $\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{x}\in\mathcal{Y}}f_{\epsilon,\mathbf{y}}(\mathbf{x},\mathbf{y})$. Finally, when $f$ is a $\mu_{\mathbf{x}}$-strongly-convex-concave function, $f_{\epsilon,\mathbf{y}}$ becomes $\mu_{\mathbf{x}}$-strongly-convex-$\epsilon/(2D_{\mathbf{y}}^{2})$-strongly-concave, which can be fed into Algorithm 4 to obtain the following result.

3 Convex-concave setting

Similar to the previous subsection, when $f$ is only convex-concave, we can construct following strongly-convex-strongly-concave function $f_{\epsilon}$:

which can be fed into Algorithm 4 to obtain the following result.

where $f_{\epsilon}$ is defined as in (8).

Accelerating Nonconvex-Concave Optimization

In this section, we present methods for accelerating nonconvex-concave optimization. Similar to Section 5, we first present our algorithm and its theoretical guarantee for optimizing nonconvex-strongly-concave functions. We then use a simple reduction argument to obtain results for nonconvex-concave functions. This section present results using the stationarity of the function $f$ (Definition 3.5) as an optimality measure. Please see Appendix A for additional results using the stationarity of the function $\Phi(\cdot):=\max_{y\in\mathcal{Y}}f(\cdot,\mathbf{y})$ as the optimality measure (Definition A.1 and A.5).

Our algorithm for nonconvex-strongly-concave optimization is described in Algorithm 5. Similar to Algorithm 4, we still use our accelerated solver Maximin-AG2 for the same proximal subproblem in the inner loop. The only minor difference is that, in the outer loop, Algorithm 5 only uses the Proximal Point Algorithm (PPA) on function $\Phi(\cdot):=\max_{y\in\mathcal{Y}}f(\cdot,\mathbf{y})$ without acceleration (or momentum steps). This is due to fact that gradient descent is already optimal among all first-order algorithm for finding stationary points of smooth nonconvex functions (Carmon et al., 2019a). The standard acceleration technique will not help for smooth nonconvex functions. We presents the theoretical guarantees for Algorithm 5 in the following theorem.

2 Nonconvex-concave setting

Our result in the nonconvex-strongly-concave setting readily implies a fast result in the nonconvex-concave setting. Consider the following auxiliary function for an arbitrary $\mathbf{y}_{0}\in\mathcal{Y}$:

Conclusions

This paper has provided the first set of near-optimal algorithms for strongly-convex-(strongly)-concave minimax optimization problems and the state-of-the-art algorithms for nonconvex-(strongly)-concave minimax optimization problems. For the former class of problems, our algorithms match the lower complexity bound for first-order algorithms (Ouyang and Xu, 2019; Ibrahim et al., 2019; Zhang et al., 2019) up to logarithmic factors. For the latter class of problems, our algorithms achieve the best known upper bound. In the future research, one important direction is to investigate the lower complexity bound of first-order algorithms for nonconvex-(strongly)-concave minimax problems. Despite several striking results on lower complexity bounds for nonconvex smooth problems (Carmon et al., 2019a, b), this problem remains challenging as solving it requires a new construction of “chain-style” functions and resisting oracles.

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 Additional Results for Nonconvex-Concave Optimization

In this section, we present our results for nonconvex-concave optimization using stationary of $\Phi(\cdot):=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ (Definition A.1 and Definition A.5) as the optimality measure.

One approach, inspired by nonconvex optimization, is to equivalently reformulate problem (1) as the following nonconvex minimization problem:

and define an optimality notion for the local surrogate of global optimum of $\Phi$. In robust learning, $\mathbf{x}$ is the classifier while $\mathbf{y}$ is the adversarial noise. Practitioners are often only interested in finding a robust classifier $\mathbf{x}$ instead of an adversarial response $\mathbf{y}$ to each data point. Such a stationary point $\mathbf{x}$ precisely corresponds to a robust classifier that is stationary to the robust classification error.

We call $\hat{\mathbf{x}}$ an $\epsilon$-stationary point of a smooth function $\Phi$ if $\left\|\nabla\Phi(\hat{\mathbf{x}})\right\|\leq\epsilon$. If $\epsilon=0$, then $\hat{\mathbf{x}}$ is called a stationary point.

In contrast, when $f(\mathbf{x},\cdot)$ is merely concave for each $\mathbf{x}\in\mathcal{X}$, $\Phi$ is not necessarily smooth and even not differentiable. A weaker sufficient condition for the purpose of our paper is the weak convexity.

A.2 Nonconvex-strongly-concave setting

In the setting of nonconvex-strongly-concave function, we still use Algorithm 5. Similar to Theorem 6.1, we can obtain a guarantee, which finds a point $\hat{\mathbf{x}}$ satisfying $\|{\nabla\Phi(\hat{\mathbf{x}})}\|\leq\epsilon$ in the same number of iterations as in Theorem 6.1.

A.3 Nonconvex-concave setting

We can similarly reduce the problem of optimizing a nonconvex-concave function to the problem of optimizing a nonconvex-strongly-concave function. The only caveat is that, in order to achieve the near-optimal point using Definition A.5 as optimality measure, we can only add a $O(\epsilon^{2})$ term as follows:

Appendix B Proofs for Algorithm Components

In this section, we present proofs for our algorithm components.

We divide the proof into three parts. In the first part, we show that the output $\hat{\mathbf{x}}$ satisfies $g(\hat{\mathbf{x}})\leq\min_{\mathbf{x}\in\mathcal{X}}g(\mathbf{x})+\epsilon$. In the second part, we derive the sufficient condition for guaranteeing the stopping criteria in Algorithm 1. In the third part, we derive the gradient complexity of the algorithm using the condition derived in the second part.

Summing up the above two inequalities and rearranging yields that

Part II.

Putting these pieces together yields the desired sufficient condition as follows,

Part III.

We proceed to derive the gradient complexity of the algorithm using the condition in Eq. (14). Since Algorithm 1 is exactly Nesterov’s accelerated gradient descent, standard arguments based on estimate sequence [Nesterov, 2018] implies

Therefore, the gradient complexity of Algorithm 1 to guarantee Eq. (14) is bounded by

B.2 Proof of Theorem 4.1

Proof. Using the definition of $\mathbf{x}_{t}$ in Algorithm 2, we have

Putting these pieces together yields that

Putting these pieces together with $\kappa\geq 1$ yields the desired inequality. $\Box$

The remaining proof is based on Lemma B.1. Indeed, we have

Using the Young’s inequality again, we have

Putting Eq. (B.2)-Eq. (20) together with $\kappa\geq 1$, we have

Combining Eq. (16) and Eq. (B.2) yields that

Repeating the above inequality yields that

Since the tolerance $\delta\leq\epsilon\kappa^{-3/2}/84$, we conclude that the iteration complexity of Algorithm 2 to guarantee that $g(\mathbf{x}_{T})-\min_{\mathbf{x}\in\mathcal{X}}g(\mathbf{x})\leq\epsilon$ if there exists an absolute constant $c>0$ such that

B.3 Proof of Theorem 4.2

Before presenting the main proof, we define the following important functions:

All the above functions are well defined since $g(\cdot,\cdot)$ is strongly convex-concave. We provide their complete characterization in the following structural lemma.

Under the assumptions imposed in Theorem 4.2, we have

A function $\mathbf{y}_{g}^{\star}(\cdot)$ is $\kappa_{\mathbf{y}}$-Lipschitz.

A function $\mathbf{x}_{g}^{\star}(\cdot)$ is $\kappa_{\mathbf{x}}$-Lipschitz.

In the second part, we get the sufficient condition for guaranteeing the stopping criteria in Algorithm 3. In the third part, we estimate an upper bound for the gradient complexity of the algorithm using the condition derived in the second part. For the ease of presentation, we denote $(\mathbf{x}_{g}^{\star},\mathbf{y}_{g}^{\star})$ as the unique solution to the minimax optimization $\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{y}\in\mathcal{Y}}g(\mathbf{x},\mathbf{y})$.

By the definition of $\Phi_{g}$, the inequality in Eq. (22) can be rewritten as follows,

Using the Young’s inequality, we have $(\mathbf{x}-\mathbf{x}_{T})^{\top}(\hat{\mathbf{x}}-\mathbf{x}_{T})\leq\|\mathbf{x}-\mathbf{x}_{T}\|^{2}+(1/4)\|\hat{\mathbf{x}}-\mathbf{x}_{T}\|^{2}$. Putting these pieces together yields with $\mathbf{x}=\mathbf{x}_{g}^{\star}$ yields that

In what follows, we prove that $\Phi_{g}(\hat{\mathbf{x}})\leq\min_{\mathbf{x}\in\mathcal{X}}\Phi_{g}(\mathbf{x})+\epsilon$ if the following stopping conditions hold true,

Indeed, we observe that $\|\mathbf{x}_{T}-\mathbf{x}_{g}^{\star}\|\leq\|\mathbf{x}_{T}-\mathbf{x}_{g}^{\star}(\mathbf{y}_{T})\|+\|\mathbf{x}_{g}^{\star}(\mathbf{y}_{T})-\mathbf{x}_{g}^{\star}(\mathbf{y}_{g}^{\star})\|+\|\mathbf{x}_{g}^{\star}(\mathbf{y}_{g}^{\star})-\mathbf{x}_{g}^{\star}\|$. By definition, we have $\mathbf{x}_{g}^{\star}(\mathbf{y}_{g}^{\star})=\mathbf{x}_{g}^{\star}$. Also, $\mathbf{x}_{g}^{\star}(\cdot)$ is $\kappa_{\mathbf{x}}$-Lipschitz. Therefore, we have

First, we bound the term $\|\mathbf{x}_{T}-\mathbf{x}_{g}^{\star}(\mathbf{y}_{T})\|$. Since $g(\cdot,\mathbf{y}_{T})$ is $\mu_{\mathbf{x}}$-strongly convex, we have

It remains to bound the term $\|\mathbf{y}_{T}-\mathbf{y}_{g}^{\star}\|$. Indeed, we have $\nabla\Psi_{g}(\mathbf{y}_{T})=\nabla_{\mathbf{y}}g(\mathbf{x}_{g}^{\star}(\mathbf{y}_{T}),\mathbf{y}_{T})$ and

Putting these pieces together with Eq. (25) and Eq. (28) yields that

Summing up the above two inequalities and rearranging yields that

Plugging Eq. (28) and Eq. (31) into Eq. (26) yields that

Plugging Eq. (28) and Eq. (31) into Eq. (27) yields that

Putting these pieces together Eq. (23) yields the desired result.

Part II.

Furthermore, $\nabla\Psi_{g}(\mathbf{y}_{T})=\nabla_{\mathbf{y}}g(\mathbf{x}^{\star}(\mathbf{y}_{T}),\mathbf{y}_{T})$ and

Also, Eq. (24) guarantees that Eq. (28) holds true. Then we have

Putting these pieces together yields the desired condition as follows,

Part III.

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

The remaining proof is based on the modification of Nesterov’s techniques [Nesterov, 2018, Section 2.2.5]. Indeed, we define the estimate sequence as follows,

We apply the inductive argument to prove,

It follows from the recursive rule for $\Gamma_{t}$ and its canonical form that

The recursive rule for $\mathbf{v}_{t}$ can be achieved by solving $\nabla\Gamma_{t+1}(\mathbf{v}_{t+1})=0$. Then we have

Then we conclude the recursive rule for $\Gamma_{t}^{\star}$ by plugging the recursive rule for $\mathbf{v}_{k}$ into the above equality. By the induction, Eq. (33) holds true when $t=T-1$ which implies

Applying Lemma B.3 with $t=T$ and $\mathbf{y}=\mathbf{y}_{T-1}$ further implies that

Putting these pieces together yields that

On the other hand, Lemma B.3 and the update formula for $\Gamma_{t}$ implies that

Since $\kappa_{\mathbf{x}},\kappa_{\mathbf{y}}\geq 1$, we have

Repeating the above inequality yields that

Now it suffices to establish the gradient complexity of the two AGD subroutines at each iteration. In particular, we use the gradient complexity of the AGD subroutine to guarantee that $g(\hat{\mathbf{x}})\leq\min_{\mathcal{X}}g(\mathbf{x})+\epsilon$ is bounded by

Appendix C Proofs for Convex-Concave Settings

In this section, we present proofs for all results in Section 5.

First, we note that Minimax-APPA in Algorithm 4 can be interpreted as an inexact accelerated proximal point algorithm Inexact-APPA with the inner loop solver Maximin-AG2 and AGD. Using Theorem 3.6 and Theorem 4.1, the point $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ satisfies

We let $\Phi(\cdot)=\max_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ and note that $\Phi$ is $\mu_{\mathbf{x}}$-strongly convex function. Since $f$ is $\mu_{\mathbf{x}}$-strongly-convex-$\mu_{\mathbf{y}}$-strongly-concave, the Nash equilibrium $(\mathbf{x}^{\star},\mathbf{y}^{\star})$ is unique and $\mathbf{x}^{\star}=\mathop{\rm{argmin}}_{\mathbf{x}\in\mathcal{X}}\Phi(\mathbf{x})$. Therefore, we have

Since $f(\hat{\mathbf{x}},\cdot)$ is $\mu_{\mathbf{y}}$-strongly concave, Nesterov [2018, Theorem 2.1.5] implies that

Since $\mathbf{y}^{\star}(\cdot)=\mathop{\rm{argmax}}_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$ is $\kappa_{\mathbf{y}}$-Lipschitz (cf. Lemma B.2), $\|\mathbf{y}^{\star}-\mathbf{y}^{\star}(\hat{\mathbf{x}})\|^{2}=\|\mathbf{y}^{\star}(\mathbf{x}^{\star})-\mathbf{y}^{\star}(\hat{\mathbf{x}})\|^{2}\leq\kappa_{\mathbf{y}}^{2}\|\hat{\mathbf{x}}-\mathbf{x}^{\star}\|^{2}$. Thus, we have

Let $\Psi(\cdot)=\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\cdot)$. By the definition of $\hat{\mathbf{y}}$, the following inequality holds true for any $\mathbf{y}\in\mathcal{Y}$,

Furthermore, we call the solver Maximin-AG2 at each iteration. Using Theorem 4.2 and $\delta=\epsilon/(10\kappa_{\mathbf{x}}\kappa_{\mathbf{y}})^{4}$, the number of gradient evaluations at each iteration is bounded by

Recalling $D=\max\{D_{\mathbf{x}},D_{\mathbf{y}}\}<+\infty$, we conclude that the total number of gradient evaluations is bounded by

C.2 Proof of Corollary 5.2

Since the function $f(\mathbf{x},\cdot)$ is concave for each $\mathbf{x}\in\mathcal{X}$, we have

Putting these pieces together yields that $\max_{\mathbf{y}\in\mathcal{Y}}f(\hat{\mathbf{x}},\mathbf{y})-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\hat{\mathbf{y}})\leq\epsilon$.

C.3 Proof of Corollary 5.3

Since the function $f(\mathbf{x},\cdot)$ is concave for each $\mathbf{x}\in\mathcal{X}$, we have

Putting these pieces together yields that $\max_{\mathbf{y}\in\mathcal{Y}}f(\hat{\mathbf{x}},\mathbf{y})-\min_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\hat{\mathbf{y}})\leq\epsilon$.

Appendix D Proofs for Nonconvex-Concave Settings

In this section, we present proofs for all results in Section 6 and Section A

Putting Eq. (34), Eq. (35) and Eq. (D.1) together with the Cauchy-Schwarz inequality yields

Summing up the above inequality over $t=0,1,\ldots,T-1$ and dividing it by $T$ yields that

Putting these pieces together yields that

Therefore, we conclude that the total number of gradient evaluations is bounded by

D.2 Proof of Corollary 6.2

This implies that the following statement holds for all $(\mathbf{x},\mathbf{y})\in\mathcal{X}\times\mathcal{Y}$ that

D.3 Proof of Theorem A.7

Using the same argument as in Theorem 6.1, we have

Putting Eq. (37), Eq. (38) and Eq. (39) together with the Cauchy-Schwarz inequality yields

Summing up the above inequality over $t=0,1,\ldots,T-1$ and dividing it by $T$ yields that

Therefore, we conclude that the total number of gradient evaluations is bounded by

D.4 Proof of Corollary A.8

Recall that the function $\bar{f}_{\epsilon}$ is defined by

This implies that the following statement holds for all $(\mathbf{x},\mathbf{y})\in\mathcal{X}\times\mathcal{Y}$ that

Using Theorem A.7 and letting $\mathbf{y}_{\epsilon}^{\star}(\cdot)=\mathop{\rm{argmin}}_{\mathbf{y}\in\mathcal{Y}}\bar{f}_{\epsilon}(\cdot,\mathbf{y})$, we have

Putting these pieces together yields that

Since a point $(\hat{\mathbf{x}},\mathbf{y}_{\epsilon}^{\star}(\hat{\mathbf{x}}))$ satisfies that

Appendix E Proof of Technical Lemmas

In this section, we provide complete proofs for the lemmas in the paper.

We provide a proof for an expanded version of Lemma A.4.

E.2 Proof of Lemma A.6

E.3 Proof of Lemma B.2

Summing up Eq. (40) with $\mathbf{y}=\mathbf{y}_{g}^{*}(\mathbf{x}^{\prime})$ and Eq. (41) with $\mathbf{y}=\mathbf{y}_{g}^{*}(\mathbf{x})$ yields

Since $g(\mathbf{x},\cdot)$ is $\mu_{\mathbf{y}}$-strongly concave, we have

Summing up the above two inequalities yields that

Therefore, we conclude that the function $\mathbf{y}_{g}^{*}(\cdot)$ is $\kappa_{\mathbf{y}}$-Lipschitz.

Part (b):

Since $g(\cdot,\mathbf{y})$ is $\mu_{\mathbf{x}}$-strongly convex for each $\mathbf{y}\in\mathcal{Y}$, we have

Therefore, the function $\Phi_{g}$ is $\mu_{\mathbf{x}}$-strongly convex.

Part (c):

Summing up Eq. (42) with $\mathbf{x}=\mathbf{x}_{g}^{*}(\mathbf{y}^{\prime})$ and Eq. (43) with $\mathbf{x}=\mathbf{x}_{g}^{*}(\mathbf{y})$ yields

Since $g(\cdot,\mathbf{y})$ is $\mu_{\mathbf{x}}$-strongly convex, we have

Summing up the above two inequalities yields that

Therefore, we conclude that the function $\mathbf{x}_{g}^{*}$ is $\kappa_{\mathbf{x}}$-Lipschitz.

Part (d):

Since $g(\mathbf{x},\cdot)$ is $\mu_{\mathbf{y}}$-strongly concave for each $\mathbf{x}\in\mathcal{X}$, we have

Therefore, the function $\Psi_{g}$ is $\mu_{\mathbf{y}}$-strongly concave.