Improved Algorithms for Convex-Concave Minimax Optimization

Introduction

In this paper, we study the following minimax optimization problem

This problem can be thought as finding the equilibrium in a zero-sum two-player game, and has been studied extensively in game theory, economics and computer science. This formulation also arises in many machine learning applications, including adversarial training , prediction and regression problems , reinforcement learning and generative adversarial networks .

We study the fundamental setting where $f$ is smooth, strongly convex w.r.t. $\mathbf{x}$ and strongly concave w.r.t. $\mathbf{y}$. In particular, we consider the function class $\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$, where $m_{\mathbf{x}}$ is the strong convexity modulus, $m_{\mathbf{y}}$ is the strong concavity modulus, $L_{\mathbf{x}}$ and $L_{\mathbf{y}}$ characterize the smoothness w.r.t. $\mathbf{x}$ and $\mathbf{y}$ respectively, and $L_{\mathbf{x}\mathbf{y}}$ characterizes the interaction between $\mathbf{x}$ and $\mathbf{y}$ (see Definition 2). The reason to consider such a function class is twofold. First, the strongly convex-strongly concave setting is fundamental. Via reduction , an efficient algorithm for this setting implies efficient algorithms for other settings, including strongly convex-concave, convex-concave, and non-convex-concave settings. Second, Zhang et al. recently proved a gradient complexity lower bound \Omega\Bigl{(}\sqrt{\frac{L_{\mathbf{x}}}{m_{\mathbf{x}}}+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}+\frac{L_{\mathbf{y}}}{m_{\mathbf{y}}}}\cdot\ln\left(\frac{1}{\epsilon}\right)\Bigr{)}, which naturally depends on the above parameters. This lower bound is also proved by Ibrahim et al. . Although their result is stated for a narrower class of algorithms, their proof actually works for the broader class of algorithms considered in .

In this work, we propose new algorithms in order to address these two issues. Our contribution can be summarized as follows.

For general functions in $\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$, we design an algorithm called Proximal Best Response (Algorithm 4), and prove a convergence rate of

It achieves linear convergence, and has a better dependence on condition numbers when $L_{\mathbf{x}\mathbf{y}}$ is small (see Theorem 3 and the red line in Fig. 1).

We obtain tighter upper bounds for the strongly-convex concave problem and the general convex-concave problem, by reducing them to the strongly convex-strongly concave problem (See Corollary 1 and 2).

We also study the special case where $f$ is a quadratic function. We propose an algorithm called Recursive Hermitian-Skew-Hermitian Split (RHSS($k$)), and show that it achieves an upper bound of

Details can be found in Theorem 4 and Corollary 3. We note that the lower bound by Zhang et al. holds for quadratic functions as well. Hence, our upper bound matches the gradient complexity lower bound up to a sub-polynomial factor.

Preliminaries

1. For any $\mathbf{y}$, $\nabla_{\mathbf{x}}f(\cdot,\mathbf{y})$ is $L_{\mathbf{x}}$-Lipschitz; 2. For any $\mathbf{x}$, $\nabla_{\mathbf{y}}f(\mathbf{x},\cdot)$ is $L_{\mathbf{y}}$-Lipschitz;

3. For any $\mathbf{x}$, $\nabla_{\mathbf{x}}f(\mathbf{x},\cdot)$ is $L_{\mathbf{x}\mathbf{y}}$-Lipschitz; 4. For any $\mathbf{y}$, $\nabla_{\mathbf{y}}f(\cdot,\mathbf{y})$ is $L_{\mathbf{x}\mathbf{y}}$-Lipschitz.

In this work, we are interested in function that are strongly convex-strongly concave and smooth. Specifically, we study the following function class.

In the case where $f(\mathbf{x},\mathbf{y})$ is twice continuously differentiable, denote the Hessian of $f$ at $(\mathbf{x},\mathbf{y})$ by $\mathbf{H}:=\left[\begin{matrix}\mathbf{H}_{\mathbf{x}\mathbf{x}}&\mathbf{H}_{\mathbf{x}\mathbf{y}}\\ \mathbf{H}_{\mathbf{y}\mathbf{x}}&\mathbf{H}_{\mathbf{y}\mathbf{y}}\end{matrix}\right]$. Then $\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$ can be characterized with the Hessian; in particular we require $m_{\mathbf{x}}\mathbf{I}\preccurlyeq\mathbf{H}_{\mathbf{x}\mathbf{x}}\preccurlyeq L_{\mathbf{x}}\mathbf{I}$, $m_{\mathbf{y}}\mathbf{I}\preccurlyeq-\mathbf{H}_{\mathbf{y}\mathbf{y}}\preccurlyeq L_{\mathbf{y}}\mathbf{I}$ and $\|\mathbf{H}_{\mathbf{x}\mathbf{y}}\|_{2}\leq L_{\mathbf{x}\mathbf{y}}$.

For notational simplicity, we assume that $L_{\mathbf{x}}=L_{\mathbf{y}}$ when considering algorithms and upper bounds. This is without loss of generality, since one can define $g(\mathbf{x},\mathbf{y}):=f((L_{\mathbf{y}}/L_{\mathbf{x}})^{1/4}\mathbf{x},(L_{\mathbf{x}}/L_{\mathbf{y}})^{1/4}\mathbf{y})$ in order to make the two smoothness constants equal. It is not hard to show that this rescaling will not change $L_{\mathbf{x}}/m_{\mathbf{x}}$, $L_{\mathbf{y}}/m_{\mathbf{y}}$, $L_{\mathbf{x}\mathbf{y}}$ and $m_{\mathbf{x}}m_{\mathbf{y}}$, and $L=\max\{L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}}\}$ will not increase. Hence, we can make the following assumption without loss of generality. Note that this rescaling also does not change the lower bound.

$f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$, and $L_{\mathbf{x}}=L_{\mathbf{y}}$.

The optimal solution of the convex-concave minimax optimization problem $\min_{\mathbf{x}}\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ is the saddle point $(\mathbf{x}^{*},\mathbf{y}^{*})$ defined as follows.

For strongly convex-strongly concave functions, it is well known that such a saddle point exists and is unique. Meanwhile,the saddle point is a stationary point, i.e. $\nabla f(\mathbf{x}^{*},\mathbf{y}^{*})=0$, and is the minimizer of $\phi(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$. For the design of numerical algorithms, we are satisfied with a close enough approximate of the saddle point, called $\epsilon$-saddle points.

$(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is an $\epsilon$-saddle point of $f$ if $\max_{\mathbf{y}}f(\hat{\mathbf{x}},\mathbf{y})-\min_{\mathbf{x}}f(\mathbf{x},\hat{\mathbf{y}})\leq\epsilon.$

Alternatively, we can also characterize optimality with the distance to the saddle point. In particular, let $\mathbf{z}^{*}:=[\mathbf{x}^{*};\mathbf{y}^{*}]$, $\hat{\mathbf{z}}:=[\hat{\mathbf{x}};\hat{\mathbf{y}}]$, then one may require $\|\hat{\mathbf{z}}-\mathbf{z}^{*}\|\leq\epsilon$. This implies thatSee Fact 4 in Appendix A for proof.

In this work we focus on first-order methods, that is, algorithms that only access $f$ through gradient evaluations. The complexity of algorithms is measured through the gradient complexity: the number of gradient evaluations required to find an $\epsilon$-saddle point (or get to $\|\hat{\mathbf{z}}-\mathbf{z}^{*}\|\leq\epsilon$).

Related Work

There is a long line of work on the convex-concave saddle point problem. Apart from GDA and ExtraGradient , other algorithms with theoretical guarantees include OGDA , Hamiltonian Gradient Descent and Consensus Optimization . For the convex-concave case and strongly-convex-concave case, lower bounds have been proven by . For the strongly-convex-strongly-concave case, the lower bound has been proven by and . Some authors have studied the special case where the interaction between $\mathbf{x}$ and $\mathbf{y}$ is bilinear and variance reduction algorithms for finite sum objectives .

The special case where $f$ is quadratic has also been studied extensively in the numerical analysis community . One of the most notable algorithms for quadratic saddle point problems is Hermitian-skew-Hermitian Split (HSS) . However, most existing work do not provide a bound on the overall number of matrix-vector products.

The convex-concave saddle point problem can also be seen as a special case of variational inequalities with Lipschitz monotone operators . Some existing algorithms for the saddle point problem, such as ExtraGradient, achieve the optimal rate in this more general setting as well .

Going beyond the convex-concave setting, some researchers have also studied the nonconvex-concave case recently , with the goal being finding a stationary point of the nonconvex function $\phi(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$. By reducing to the strongly convex-strongly concave setting, has achieved state-of-the-art results for nonconvex-concave problems.

Let us first consider the extreme case where $L_{\mathbf{x}\mathbf{y}}=0$. In this case, there is no interaction between $\mathbf{x}$ and $\mathbf{y}$, and $f(\mathbf{x},\mathbf{y})$ can be simply written as $h_{1}(\mathbf{x})-h_{2}(\mathbf{y})$, where $h_{1}$ and $h_{2}$ are strongly convex functions. Thus, in this case, the following trivial algorithm solves the problem

In other words, the equilibrium can be found by directly playing the best response to each other once.

Now, let us consider the case where $L_{\mathbf{x}\mathbf{y}}$ is nonzero but small. In this case, would the best response dynamics converge to the saddle point? Specifically, consider the following procedure:

Let us define $\mathbf{y}^{*}(\mathbf{x}):=\operatorname*{arg\,max}_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ and $\mathbf{x}^{*}(\mathbf{y}):=\operatorname*{arg\,min}_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$. Because $\mathbf{y}^{*}(\mathbf{x})$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{y}}$-Lipschitz and $\mathbf{x}^{*}(\mathbf{y})$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{x}}$-Lipschitz See Fact 1 in Appendix A for proof.,

Thus, when $L_{\mathbf{x}\mathbf{y}}^{2}<m_{\mathbf{x}}m_{\mathbf{y}}$, (2) is indeed a contraction. In fact, we can further replace the exact solution of the inner optimization problems with Nesterov’s Accelerated Gradient Descent (AGD) for constant number of steps, as described in Algorithm 1.

The following theorem holds for the Alternating Best Response algorithm. The proof of the theorem, as well as a detailed version of Algorithm 1 can be found in Appendix B.

If $g\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$ and $L_{\mathbf{x}\mathbf{y}}\leq\frac{1}{2}\sqrt{m_{\mathbf{x}}m_{\mathbf{y}}}$, Alternating Best Response returns $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that

and the number of gradient evaluations is bounded by (with $\kappa_{\mathbf{x}}=L_{\mathbf{x}}/m_{\mathbf{x}}$, $\kappa_{\mathbf{y}}=L_{\mathbf{y}}/m_{\mathbf{y}}$)

Note that when $L_{\mathbf{x}\mathbf{y}}$ is small, Zhang et al’s lower bound can be written as $\Omega\left(\sqrt{\kappa_{\mathbf{x}}+\kappa_{\mathbf{y}}}\ln(1/\epsilon)\right)$. Thus Alternating Best Response matches this lower bound up to logarithmic factors.

2 Accelerated Proximal Point for Minimax Optimization

In the previous subsection, we showed that Alternating Best Response matches the lower bound when the interaction term $L_{\mathbf{x}\mathbf{y}}$ is sufficiently small. However, in order to apply the algorithm to functions with $L_{\mathbf{x}\mathbf{y}}>\frac{1}{2}\sqrt{m_{\mathbf{x}}m_{\mathbf{y}}}$, we need another algorithmic component, namely the accelerated proximal point algorithm .

For a minimax optimization problem $\min_{\mathbf{x}}\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$, define $\phi(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$. Suppose that we run the accelerated proximal point algorithm on $\phi(\mathbf{x})$ with proximal parameter $\beta$: then the number of iterations can be easily bounded, while in each iteration one needs to solve a proximal problem $\min_{\mathbf{x}}\left\{\phi(\mathbf{x})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t}\|^{2}\right\}$. The key observation is that, this is equivalent to solving a minimax optimization problem $\min_{\mathbf{x}}\max_{\mathbf{y}}\left\{f(\mathbf{x},\mathbf{y})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t}\|^{2}\right\}$. Thus, via accelerated proximal point, we are able to reduce solving $\min_{\mathbf{x}}\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ to solving $\min_{\mathbf{x}}\max_{\mathbf{y}}\left\{f(\mathbf{x},\mathbf{y})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t}\|^{2}\right\}$.

The following theorem can be shown for Algorithm 2. The proof can be found in Appendix C, and is based on the proof of Theorem 4.1 in .

The number of iterations needed by Algorithm 2 to produce $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that

is at most ($\kappa=\beta/m_{\mathbf{x}}$)

3 Proximal Alternating Best Response

With the two algorithmic components, namely Alternating Best Response and Accelerated Proximal Point in place, we can now combine them and design an efficient algorithm for general strongly convex-strongly concave functions. The high-level idea is to exploit the accelerated proximal point algorithm twice to reduce a general problem into one solvable by Alternating Best Response.

In order to deal with the case where $L_{\mathbf{x}\mathbf{y}}<\max\{m_{\mathbf{x}},m_{\mathbf{y}}\}$, we shall choose $\beta_{1}=\max\{L_{\mathbf{x}\mathbf{y}},m_{\mathbf{x}}\}$ for the first level of proximal point, and $\beta_{2}=\max\{L_{\mathbf{x}\mathbf{y}},m_{\mathbf{y}}\}$ for the second level of proximal point. In this case, the total gradient complexity bound can be shown to be

A formal description of the algorithm is provided in Algorithm 4, and a formal statement of the complexity upper bound is provided in Theorem 3. The proof is deferred to Appendix D.

Assume that $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$. In Algorithm 4, the gradient complexity to produce $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

4 Implications of Theorem 3

Theorem 3 improves over the results of Lin et al. in two ways. First, Lin et al.’s upper bound has a $\ln^{3}(1/\epsilon)$ factor, while our algorithm enjoys linear convergence. Second, our result has a better dependence on $L_{\mathbf{x}\mathbf{y}}$. To see this, note that when $L_{\mathbf{x}\mathbf{y}}\ll L$, $\frac{L_{\mathbf{x}}}{m_{\mathbf{x}}}+\frac{L\cdot L_{\mathbf{x}\mathbf{y}}}{m_{\mathbf{x}}m_{\mathbf{y}}}+\frac{L_{\mathbf{y}}}{m_{\mathbf{y}}}\ll\frac{L_{\mathbf{x}}}{m_{\mathbf{x}}}+\frac{L^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}+\frac{L_{\mathbf{y}}}{m_{\mathbf{y}}}\leq\frac{3L^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}.$ This is also illustrated by Fig. 1, where Proximal Best Response (the red line) significantly outperforms Lin et al.’s result (the blue line) when $L_{\mathbf{x}\mathbf{y}}\ll L$. In particular, Proximal Best Response matches the lower bound when $L_{\mathbf{x}\mathbf{y}}>L_{\mathbf{x}}$ or when $L_{\mathbf{x}\mathbf{y}}<\max\{m_{\mathbf{x}},m_{\mathbf{y}}\}$; in between, it is able to gracefully interpolate the two cases.

As shown by Lin et al. , convex-concave problems and strongly convex-concave problems can be reduced to strongly convex-strongly concave problems. Hence, Theorem 3 naturally implies improved algorithms for convex-concave and strongly convex-concave problems.

The precise statement as well as the proofs can be found in Appendix F. We remark that the reduction is for constrained minimax optimization, and Theorem 3 holds for constrained problems after simple modifications to the algorithm.

We can see that proximal best response has near optimal dependence on condition numbers when $L_{\mathbf{x}\mathbf{y}}>L_{\mathbf{x}}$ or when $L_{\mathbf{x}\mathbf{y}}<\max\{m_{\mathbf{x}},m_{\mathbf{y}}\}$. However, when $L_{\mathbf{x}\mathbf{y}}$ falls in between, there is still a significant gap between the upper bound and the lower bound. In this section, we try to close this gap for quadratic functions; i.e. we assume that

The reason to consider quadratic functions is threefold. First, the lower bound instance by is a quadratic function; thus, this lower bound applies to quadratic functions as well, so it would be interesting to match the lower bound for quadratic functions first. Second, quadratic functions are considerably easier to analyze. Third, finding the saddle point of quadratic functions is an important problem on its own, and has many applications (see and references therein).

Our assumption that $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$ now becomes assumptions on the singular values of matrices: $m_{\mathbf{x}}\mathbf{I}\preccurlyeq\mathbf{A}\preccurlyeq L_{\mathbf{x}}\mathbf{I}$, $m_{\mathbf{y}}\mathbf{I}\preccurlyeq\mathbf{C}\preccurlyeq L_{\mathbf{y}}\mathbf{I}$, $\|\mathbf{B}\|_{2}\leq L_{\mathbf{x}\mathbf{y}}$. In this case, the unique saddle point is given by the solution to a linear system

Throughout this section we assume that $L_{\mathbf{x}}=L_{\mathbf{y}}$ and $m_{\mathbf{x}}<m_{\mathbf{y}}$, which are without loss of generality, and that $m_{\mathbf{y}}<L_{\mathbf{x}\mathbf{y}}$, as otherwise proximal best response is already near-optimal.

We now focus on how to solve the linear system $\mathbf{J}\mathbf{z}=\mathbf{b}$, where $\mathbf{J}:=\left[\begin{matrix}\mathbf{A}&\mathbf{B}\\ -\mathbf{B}^{T}&\mathbf{C}\end{matrix}\right]$ is positive definite but not symmetric. A straightforward way to solve this asymmetric linear system is apply conjugate gradient to solve the normal equation $\mathbf{J}^{T}\mathbf{J}\mathbf{z}=\mathbf{J}^{T}\mathbf{b}$. However the complexity of this approach is $O\left(\frac{L}{\min\{m_{\mathbf{x}},m_{\mathbf{y}}\}}\right)$, which is much worse than the lower bound. Instead, we utilize the Hermitian-Skew-Hermitian Split (HSS) algorithm , which is designed to solve positive definite asymmetric systems. Define

where $\alpha$ and $\beta$ are constants to be determined. Let $\mathbf{z}_{t}:=[\mathbf{x}_{t};\mathbf{y}_{t}]$. Then HSS runs as

Here $\eta>0$ is another constant. In this procedure, it can be shown that

The key observation of HSS is that the equation above is a contraction.

Define $M(\eta):=\left(\eta\mathbf{P}+\mathbf{S}\right)^{-1}\left(\eta\mathbf{P}-\mathbf{G}\right)\left(\eta\mathbf{P}+\mathbf{G}\right)^{-1}\left(\eta\mathbf{P}-\mathbf{S}\right)$. ThenHere $\rho(\cdot)$ stands for the spectral radius of a matrix, and $sp(\cdot)$ stands for its spectrum.

Lemma 1 provides an upper bound on the iteration complexity of HSS, as in the original analysis of HSS . However, it does not consider the computational cost per iteration. In particular, the matrix $\eta\mathbf{P}+\mathbf{S}$ is also asymmetric, and in fact corresponds to another quadratic minimax optimization problem. The original HSS paper did not consider how to solve this subproblem for general $\mathbf{P}$. Our idea is to solve the subproblem recursively, as explained in the next subsection.

2 Recursive HSS

In this subsection, we describe our algorithm Recursive Hermitian-skew-Hermitian Split, or RHSS($k$), which uses HSS in $k-1$ levels of recursion. Specifically, RHSS($k$) calls HSS with parameters $\alpha=m_{\mathbf{x}}/m_{\mathbf{y}}$, $\beta=L_{\mathbf{x}\mathbf{y}}^{-\frac{2}{k}}m_{\mathbf{y}}^{-\frac{k-2}{k}}$, $\eta=L_{\mathbf{x}\mathbf{y}}^{\frac{1}{k}}m_{\mathbf{y}}^{\frac{k-1}{k}}$. In each iteration, it solves two linear systems. The first one, which is associated with $\eta\mathbf{P}+\mathbf{G}$, can be solved with Conjugate Gradient as $\eta\mathbf{P}+\mathbf{G}$ is symmetric positive definite. The second one is associated with

which is equivalent to a quadratic minimax optimization problem. RHSS($k$) then makes a recursive call RHSS($k-1$) to solve this subproblem. When $k=1$, we simply run the Proximal Best Response algorithm (Algorithm 4). A detailed description of RHSS($k$) for $k\geq 2$ is given in Algorithm 5.

Our main result for RHSS($k$) is the following theorem. Note that for an algorithm on quadratic functions, the number of matrix-vector products is the same as the gradient complexity.

There exists constants $C_{1}$, $C_{2}$, such that the number of matrix-vector products needed to find $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is at most

If $k$ is chosen as a fixed constant, the comparison of (6) and the lower bound is illustrated in Fig. 1. One can see that as $k$ increases, the upper bound of RHSS($k$) gradually fits the lower bound (as long as $k$ is a constant).

By optimizing $k$, we can also show the following corollary.

When $k=\Theta\left(\sqrt{\ln\left(\frac{L^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}\right)/\ln\ln\left(\frac{L^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}\right)}\right)$, the number of matrix vector products that RHSS($k$) needs to find $\mathbf{z}_{T}$ such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

In other words, for the quadratic saddle point problem, RHSS($k$) with the optimal choice of $k$ matches the lower bound up to a sub-polynomial factor.

The proof of both Theorem 4 and Corollary 3 can be found in Appendix G.

Conclusion

In this work, we studied convex-concave minimax optimization problems. For general strongly convex-strongly concave problems, our Proximal Best Response algorithm achieves linear convergence and better dependence on $L_{\mathbf{x}\mathbf{y}}$, the interaction parameter. Via known reductions , this result implies better upper bounds for strongly convex-concave and convex-concave problems. For quadratic functions, our algorithm RHSS($k$) is able to match the lower bound up to a sub-polynomial factor.

In future research, one interesting direction is to extend RHSS($k$) to general strongly convex-strongly concave functions. Another important direction would be to shave the remaining sub-polynomial factor from the upper bound for quadratic functions.

Broader Impact

This work is purely theoretical and does not present foreseeable societal consequences.

Acknowledgments and Disclosure of Funding

The research is supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, and the Zhongguancun Haihua Institute for Frontier Information Technology, Turing AI Institute of Nanjing and Xi’an Institute for Interdisciplinary Information Core Technology. The authors thank Kefan Dong, Guodong Zhang and Chi Jin for helpful discussions.

References

Appendix A Some Useful Properties

In this section, we review some useful properties of functions in $\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$. Some of the facts are known (see e.g., , ) and we provide the proofs for completeness.

Suppose $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$. Let us define $\mathbf{y}^{*}(\mathbf{x}):=\operatorname*{arg\,max}_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$, $\mathbf{x}^{*}(\mathbf{y}):=\operatorname*{arg\,min}_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$, $\phi(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ and $\psi(\mathbf{y}):=\min_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$. Then, we have that

$\mathbf{y}^{*}$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{y}}$-Lipschitz, $\mathbf{x}^{*}$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{x}}$-Lipschitz;

$\phi(\mathbf{x})$ is $m_{\mathbf{x}}$-strongly convex and $L_{\mathbf{x}}+L_{\mathbf{x}\mathbf{y}}^{2}/m_{\mathbf{y}}$-smooth; $\psi(\mathbf{y})$ is $m_{\mathbf{y}}$-strongly concave and $L_{\mathbf{y}}+L_{\mathbf{x}\mathbf{y}}^{2}/m_{\mathbf{x}}$-smooth.

1. Consider arbitrary $\mathbf{x}$ and $\mathbf{x}^{\prime}$. By definition, $\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))=\nabla_{\mathbf{y}}f(\mathbf{x}^{\prime},\mathbf{y}^{*}(\mathbf{x}^{\prime}))=\mathbf{0}$. By the definition of $(L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$-smoothness, $\|\nabla_{\mathbf{y}}f(\mathbf{x}^{\prime},\mathbf{y}^{*}(\mathbf{x}))\|\leq L_{\mathbf{x}\mathbf{y}}\|\mathbf{x}-\mathbf{x}^{\prime}\|$. Thus

This proves that $y^{*}(\cdot)$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{y}}$-Lipschitz. Similarly $\mathbf{x}^{*}(\cdot)$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{x}}$-Lipschitz.

2. By Danskin’s Theorem, $\nabla\phi(\mathbf{x})=\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y}^{*}(\mathbf{x}))$. Thus, $\forall\mathbf{x},\mathbf{x}^{\prime}$

On the other hand, $\forall\mathbf{x},\mathbf{x}^{\prime}$,

Thus $\phi(\mathbf{x})$ is $m_{\mathbf{x}}$-strongly convex and \Bigl{(}L_{\mathbf{x}}+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{y}}}\Bigr{)}-smooth. By symmetric arguments, one can show that $\psi(\mathbf{y})$ is $m_{\mathbf{y}}$-strongly concave and \Bigl{(}L_{\mathbf{y}}+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{x}}}\Bigr{)}-smooth. ∎

Let $\mathbf{z}:=[\mathbf{x};\mathbf{y}]$ and $\mathbf{z}^{*}:=[\mathbf{x}^{*};\mathbf{y}^{*}]$. Then

This can be easily proven using the AM-GM inequality. ∎

By properties of strong convexity , $\forall\mathbf{x},\mathbf{y}$

Here $\phi(\cdot)=\max_{\mathbf{y}}f(\cdot,\mathbf{y})$, $\psi(\cdot)=\min_{\mathbf{x}}f(\mathbf{x},\cdot)$. By Proposition 1, $\phi$ is $m_{\mathbf{x}}$-strongly convex while $\psi$ is $m_{\mathbf{y}}$-strongly concave. Hence

It follows that $\|\nabla f(\mathbf{x},\mathbf{y})\|\geq\min\{m_{\mathbf{x}},m_{\mathbf{y}}\}\|\mathbf{z}-\mathbf{z}^{*}\|$. On the other hand,

As a result $\|\nabla f(\mathbf{x},\mathbf{y})\|^{2}\leq L\left(\|\mathbf{x}-\mathbf{x}^{*}\|+\|\mathbf{y}-\mathbf{y}^{*}\|\right)^{2}\leq 4L^{2}\|\mathbf{z}-\mathbf{z}^{*}\|^{2}$.

Let $\hat{\mathbf{z}}=[\hat{\mathbf{x}};\hat{\mathbf{y}}]$. Then $\|\hat{\mathbf{z}}-\mathbf{z}^{*}\|\leq\epsilon$ implies

Define $\phi(\mathbf{x})=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ and $\psi(\mathbf{y})=\min_{\mathbf{x}}f(\mathbf{x},\mathbf{y})$. Then

By Fact 1, $\phi$ is $(L_{\mathbf{x}}+L_{\mathbf{x}\mathbf{y}}^{2}/m_{\mathbf{x}})$-smooth while $\psi$ is $(L_{\mathbf{y}}+L_{\mathbf{x}\mathbf{y}}^{2}/m_{\mathbf{x}})$-smooth. Since $\phi(\mathbf{x}^{*})=\psi(\mathbf{y}^{*})$, $\nabla\phi(\mathbf{x}^{*})=\mathbf{0}$, $\nabla\psi(\mathbf{y}^{*})=\mathbf{0}$,

Nesterov’s Accelerated Gradient Descent is an optimal first-order algorithm for smooth and convex functions. Here we present a version of AGD for minimizing an $l$-smooth and $m$-strongly convex functions $g(\cdot)$. It is a crucial building block for the algorithms in this work.

The following classical theorem holds for AGD. It implies that the complexity is $O\left(\sqrt{\kappa}\ln\left(\frac{1}{\epsilon}\right)\right)$, which greatly improves over the $O\left(\kappa\ln\left(\frac{1}{\epsilon}\right)\right)$ bound for gradient descent.

([33, Theorem 2.2.3]) In the AGD algorithm,

Appendix B Proof of Theorem 1

We will start by giving a precise statement of Algorithm 1.

If $g\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$ and $L_{\mathbf{x}\mathbf{y}}<\frac{1}{2}\sqrt{m_{\mathbf{x}}m_{\mathbf{y}}}$, Alternating Best Response returns $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that

using ($\kappa_{\mathbf{x}}=L_{\mathbf{x}}/m_{\mathbf{x}}$, $\kappa_{\mathbf{y}}=L_{\mathbf{y}}/m_{\mathbf{y}}$)

The basic idea is the following. Because $\mathbf{y}^{*}(\cdot)$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{y}}$-Lipschitz and $\mathbf{x}^{*}(\cdot)$ is $L_{\mathbf{x}\mathbf{y}}/m_{\mathbf{x}}$-Lipschitz (Fact 1),

By a standard analysis of accelerated gradient descent (Lemma 2), since $\hat{\mathbf{x}}_{t+1}=\mathbf{x}^{*}(\mathbf{y}_{t})$ is the minimum of $f(\cdot,\mathbf{y}_{t})$ and $\mathbf{x}_{t}$ is the initial point,

Define $C:=4\sqrt{m_{\mathbf{y}}/m_{\mathbf{x}}}$. By adding (7) and $C$ times (8), one gets

Since $\max\{m_{\mathbf{x}}/m_{\mathbf{y}},m_{\mathbf{y}}/m_{\mathbf{x}}\}\leq L_{\mathbf{x}}/\min\{m_{\mathbf{x}},m_{\mathbf{y}}\}$,

The theorem follows from this inequality. ∎

Appendix C Proof of Theorem 2

Assume that $M\geq 20\kappa\sqrt{2\kappa+\frac{L}{m_{\mathbf{x}}}+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}}\left(1+\frac{L}{m_{\mathbf{y}}}\right).$ The number of iterations needed by Algorithm 2 to produce $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that

is at most ($\kappa=\beta/m_{\mathbf{x}}$)

Before proving the theorem, we would first state the inexact accelerated proximal point algorithm , which is the basis of Algorithm 2.

The following two lemmas about the inexact APPA algorithm follow from the proof of Theorem 4.1 in an earlier version of the paper. Here we provide their proofs for completeness.

Suppose that $\{(\mathbf{x}_{t},\hat{\mathbf{x}}_{t})\}_{t\geq 0}$ are generated by running the inexact APPA algorithm on $g(\cdot)$. Then $\forall t\geq 1,\forall\mathbf{x}$,

Define $\mathbf{x}^{*}_{t}:=\operatorname*{arg\,min}_{\mathbf{x}}\{g(\mathbf{x})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t-1}\|^{2}\}$. By the $m$-strong convexity of $g(\cdot)$, we have $\forall\mathbf{x}$,

Also, since $g(\mathbf{x})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t-1}\|^{2}$ is $(2\beta+m)$-strongly convex,

Suppose that $\{\mathbf{x}_{t}\}_{t\geq 0}$ is generated by running the inexact APPA algorithm on $g(\cdot)$. There exists a sequence $\{\Lambda_{t}\}_{t\geq 0}$ such that

$\Lambda_{0}-g(\mathbf{x}^{*})\leq 2(g(\mathbf{x}_{0})-g(\mathbf{x}^{*}))$

$\Lambda_{t+1}-g(\mathbf{x}^{*})\leq\left(1-\frac{1}{2\sqrt{\kappa}}\right)\left(\Lambda_{t}-g(\mathbf{x}^{*})\right)+11\kappa\delta_{t+1}$

Let us slightly abuse notation, and define a sequence of functions $\{\Lambda(\mathbf{x})\}_{t\geq 0}$ first:

The sequence $\{\Lambda_{t}\}_{t\geq 0}$ in the lemma is then defined as $\Lambda_{t}:=\Lambda_{t}(\mathbf{x}^{*})$. Note that later we do not need to make use of the explicit definition of $\Lambda_{t}$.

From the definition, Property 2 is straightforward, as

Now, let us show $\Lambda_{t}\geq\min_{\mathbf{x}}\Lambda_{t}(\mathbf{x})\geq g(\mathbf{x}_{t})$ using induction. Let $\mathbf{w}_{t}:=\operatorname*{arg\,min}_{\mathbf{x}}\Lambda_{t}(\mathbf{x})$ and $\Lambda_{t}^{*}:=\min_{\mathbf{x}}\Lambda_{t}(\mathbf{x})$. Observe that $\Lambda_{t}(\mathbf{x})$ is always a quadratic function of the form $\Lambda_{t}(\mathbf{x})=\Lambda^{*}_{t}+\frac{m}{4}\|\mathbf{x}-\mathbf{w}_{t}\|^{2}$. Then the following recursions hold for $\mathbf{w}_{t}$ and $\Lambda_{t}^{*}$:

The recursion for $\mathbf{w}_{t+1}$ can be derived by differentiating both sides in the recusion of $\Lambda_{t}(\mathbf{x})$, while the recursion for $\Lambda^{*}_{t+1}$ can be derived by plugging the recursion for $\mathbf{w}_{t+1}$ into $\Lambda^{*}_{t+1}=\Lambda_{t+1}(\mathbf{w}_{t+1})$.

Now, assume that $\Lambda_{t}^{*}\geq g(\mathbf{x}_{t})$ for $t\leq T-1$. Then

Applying Lemma 3 with $\mathbf{x}=\mathbf{x}_{T-1}$ yields

and the recursive rule for $\mathbf{w}_{t}$, we get

Meanwhile, when $t=0$, $\mathbf{x}_{t}=\hat{\mathbf{x}}_{t}=\mathbf{w}_{t}=\mathbf{x}_{0}$. Thus, by induction, we have for any $t$, $(\mathbf{x}_{t}-\hat{\mathbf{x}}_{t})+\frac{1}{2\sqrt{\kappa}}(\mathbf{w}_{t}-\hat{\mathbf{x}}_{t})=0.$ As a result $\Lambda^{*}_{T}\geq g(\mathbf{x}_{T})$. Again, by induction, this holds for all $T$. This proves Property 1 in the lemma.

Let us now focus on the final property. Combining Lemma 3 and the recursion for $\Lambda_{t}(\mathbf{x})$,

Define $\phi(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$ and $\hat{L}:=L+L_{\mathbf{x}\mathbf{y}}^{2}/m_{\mathbf{y}}$. Then $\phi(\mathbf{x})$ is $m_{\mathbf{x}}$-strongly convex and $\hat{L}$-smooth. Observe that

Thus Algorithm 2 is an instance of the inexact APPA algorithm on $\phi(\mathbf{x})$ with proximal parameter $\beta$ and strongly convex module $m_{\mathbf{x}}$, and with

Here we used the fact that, for a $L$-smooth function $g(\cdot)$ whose minimum is $\mathbf{x}^{*}$, $g(\mathbf{x})-g(\mathbf{x}^{*})\leq\frac{L}{2}\|\mathbf{x}-\mathbf{x}^{*}\|^{2}$. Define $C_{1}:=\|\mathbf{x}_{0}-\mathbf{x}^{*}\|+\|\mathbf{y}_{0}-\mathbf{y}^{*}\|$ and $C_{0}:=44\kappa\sqrt{\kappa}\frac{\hat{L}+2\beta}{2}C_{1}^{2}$. Let us state the following induction hypothesis

It is easy to verify that with our choice of $C_{0}$ and $C_{1}$, both (14) and (15) hold for $t=0$.

Now, assume that (14) and (15) hold for $\tau=1,2,\cdots,t$. Define $\mathbf{y}^{*}(\cdot):=\operatorname*{arg\,max}_{\mathbf{y}}f(\cdot,\mathbf{y})$. By Fact 1, $\mathbf{y}^{*}(\cdot)$ is $(L/m_{\mathbf{y}})$-Lipschitz. Thus

Note that by Lemma 4 and the induction hypothesis (14)

By the $m_{\mathbf{x}}$-strong convexity of $\phi(\cdot)$ (Fact 1),

By (16), (15) and the fact that $M\geq 20\kappa\sqrt{2\kappa+\frac{\hat{L}}{m_{\mathbf{x}}}}(1+L/m_{\mathbf{y}})$

Therefore (15) holds for $t+1$. Meanwhile, by (13) and Lemma 4,

Thus (14) also holds for $t+1$. By induction on $t$, we can see that (14) and (15) both hold for all $t\geq 0$.

Appendix D Proof of Theorem 3

Assume that $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$. In Algorithm 4, the gradient complexity to produce $(\mathbf{x}_{T},\mathbf{y}_{T})$ such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

We start the proof by verifying $f(\mathbf{x},\mathbf{y})+\beta_{1}\|\mathbf{x}-\hat{\mathbf{x}}\|^{2}-\beta_{2}\|\mathbf{y}-\hat{\mathbf{y}}\|^{2}$ can indeed be solved by calling ABR($\cdot$,$[\mathbf{x}_{0};\mathbf{y}_{0}]$,$1/M_{2}$, $2\beta_{1}$, $2\beta_{2}$, $3L$, $3L$). Observe that $L_{\mathbf{x}\mathbf{y}}\leq\beta_{1},\beta_{2}\leq L$. Since $f(\mathbf{x},\mathbf{y})+\beta_{1}\|\mathbf{x}-\hat{\mathbf{x}}\|^{2}-\beta_{2}\|\mathbf{y}-\hat{\mathbf{y}}\|^{2}$ is $2\beta_{1}$-strongly convex w.r.t. $\mathbf{x}$ and $2\beta_{2}$-strongly concave w.r.t. $\mathbf{y}$, we can see that $\frac{1}{2}\sqrt{2\beta_{1}\cdot 2\beta_{2}}\geq L_{\mathbf{x}\mathbf{y}}$. We can also verify that $f(\mathbf{x},\mathbf{y})+\beta_{1}\|\mathbf{x}-\hat{\mathbf{x}}\|^{2}-\beta_{2}\|\mathbf{y}-\hat{\mathbf{y}}\|^{2}$ is $3L$-smooth, which follows from the fact that $L+\max\{2\beta_{1},2\beta_{2}\}\leq 3L$.

Therefore, we can apply Theorem 1 and conclude that at line $5$ of Algorithm 3

where $(\mathbf{x}^{*}_{t},\mathbf{y}^{*}_{t}):=\min_{\mathbf{x}}\max_{\mathbf{y}}\{g(\mathbf{x},\mathbf{y})-\beta_{2}\|\mathbf{y}-\mathbf{y}_{t-1}\|^{2}\}$, Here $g(\mathbf{x},\mathbf{y})$ refers to the argument passed to Algorithm 3, which in our case has the form $f(\mathbf{x},\mathbf{y})+\beta\|\mathbf{x}-\hat{\mathbf{x}}_{t^{\prime}-1}\|^{2}$. and such $(\mathbf{x}_{t},\mathbf{y}_{t})$ is found in a gradient complexity of

Next, we verify that Algorithm 3 is an instance of Algorithm 2 on the function $\hat{g}(\mathbf{x},\mathbf{y}):=-g(\mathbf{y},\mathbf{x}).$ Notice that

That is, $\min_{\mathbf{x}}\max_{\mathbf{y}}\left\{g(\mathbf{x},\mathbf{y})-\|\mathbf{y}-\hat{\mathbf{y}}\|^{2}\right\}$ has the same saddle point as $-g(\mathbf{x},\mathbf{y})+\beta\|\mathbf{y}-\hat{\mathbf{y}}\|^{2}$. Thus, we only need to verify that

where $(m^{\prime}_{\mathbf{x}},m^{\prime}_{\mathbf{y}},L^{\prime}_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L^{\prime}_{\mathbf{y}})$ are parameters for $f(\mathbf{x},\mathbf{y})+\beta_{1}\|\mathbf{x}\|^{2}$, and $L^{\prime}=\max\{L_{\mathbf{x}\mathbf{y}},L^{\prime}_{\mathbf{x}},L^{\prime}_{\mathbf{y}}\}$. Note that $m^{\prime}_{\mathbf{x}}\geq m_{\mathbf{x}}+2\beta_{1}$, $m^{\prime}_{\mathbf{y}}=m_{\mathbf{y}}$, $L^{\prime}_{\mathbf{x}}=L^{\prime}_{\mathbf{y}}\leq L+2\beta_{1}$, $L_{\mathbf{x}\mathbf{y}}\leq\beta_{1},\beta_{2}\leq L$. Thus

Therefore, Algorithm 3 is indeed an instance of Inexact APPA (Algorithm II). Notice that by the stopping condition of Algorithm 3,

Thus in this case Algorithm 3 must return. By Theorem 2, we can see that Algorithm 3 always returns in at most

Finally, we verify that Algorithm 4 is an instance of Algorithm 2 on $f(\mathbf{x},\mathbf{y})$ with parameter $\beta_{1}$. Note that by (19), we only need to verify that

Therefore Algorithm 4 is indeed an instance of Algorithm 2 on $f(\mathbf{x},\mathbf{y})$. As a result, by Theorem 2, the number of iterations needed such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

We now compute the total gradient complexity. Recall that $\beta_{1}=\max\{m_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}}\}$, while $\beta_{2}=\max\{m_{\mathbf{y}},L_{\mathbf{x}\mathbf{y}}\}$. By (21), (20) and (D), the total gradient complexity of Algorithm 4 to reach $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

If $L_{\mathbf{x}\mathbf{y}}\geq\max\{m_{\mathbf{x}},m_{\mathbf{y}}\}$, then $\beta_{1}=\beta_{2}=L_{\mathbf{x}\mathbf{y}}$, so

Now consider the case where $L_{\mathbf{x}\mathbf{y}}<\max\{m_{\mathbf{x}},m_{\mathbf{y}}\}$. Without loss of generality, assume that $m_{\mathbf{x}}\leq m_{\mathbf{y}}$. Suppose that $L_{\mathbf{x}\mathbf{y}}<m_{\mathbf{y}}$, then $L=L_{\mathbf{x}}$, $\beta_{2}=m_{\mathbf{y}}$, while $\beta_{1}\leq m_{\mathbf{y}}$. Hence

Thus, in either case, $\sqrt{\frac{L(\beta_{1}+\beta_{2})}{m_{\mathbf{x}}m_{\mathbf{y}}}}=O\left(\sqrt{\frac{L_{\mathbf{x}}}{m_{\mathbf{x}}}+\frac{L\cdot L_{\mathbf{x}\mathbf{y}}}{m_{\mathbf{x}}m_{\mathbf{y}}}+\frac{L_{\mathbf{y}}}{m_{\mathbf{y}}}}\right)$. We conclude that the total gradient complexity of Algorithm 4 to find a point $\mathbf{z}_{T}=[\mathbf{x}_{T};\mathbf{y}_{T}]$ such that $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

Appendix E Application to Constrained Problems

For Algorithm 3 and 4, the modified versions are presented below. The only significant change is the addition of a projected gradient descent-ascent step in line 5-6 of Algorithm 3 and line 5-6 and 9-10 of Algorithm 4.

For Algorithm 1, the only necessary modification is to add projection steps to the Accelerated Gradient Descent Procedure. The reason for the extra gradient step on line 2 is technical. From the original analysis [33, Theorem 2.2.3], it only follows that

For constrained problems, $f(\mathbf{x}_{1})-f(\mathbf{x}^{*})\leq\frac{L}{2}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|^{2}$ does not hold. However, with the initial projected gradient step, it can be shown that $\|\mathbf{x}_{1}-\mathbf{x}^{*}\|\leq\|\mathbf{x}_{0}-\mathbf{x}^{*}\|$ and that $f(\mathbf{x}_{1})-f(\mathbf{x}^{*})\leq\frac{L}{2}\|\mathbf{x}_{0}-\mathbf{x}^{*}\|^{2}$ (see Lemma 6). Thus

For Algorithm 3 and 4, the modified versions are presented below.

The most significant change is the addition of a projected gradient descent-ascent step in line 5-6 of Algorithm 3 and line 5-6 and 9-10 of Algorithm 4. The reason for this modification is very similar to that of the initial projected gradient descent step for AGD. For unconstrained problems, a small distance to the saddle point implies a small duality gap (Fact 4); however this may not be true for constrained problems, since the saddle point may no longer be a stationary point. This is also true for minimization: if $\mathbf{x}^{*}=\operatorname*{arg\,min}_{\mathbf{x}\in\mathcal{X}}g(\mathbf{x})$ where $g(\mathbf{x})$ is a $L$-smooth function $g(\mathbf{x})-g(\mathbf{x}^{*})\leq\frac{L}{2}\|\mathbf{x}-\mathbf{x}^{*}\|^{2}$ may not hold.

Fortunately, there is a simple fix to this problem. By applying projected gradient descent-ascent once, we can assure that a small distance implies small duality gap. This is specified by the following lemma, which is the key reason why our result can be adapted to the constrained problem.

Suppose that $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$, $(\mathbf{x}^{*},\mathbf{y}^{*})$ is a saddle point of $f$, $\mathbf{z}_{0}=(\mathbf{x}_{0},\mathbf{y}_{0})$ satisfies $\|\mathbf{z}_{0}-\mathbf{z}^{*}\|\leq\epsilon$. Let $\hat{\mathbf{z}}=(\hat{\mathbf{x}},\hat{\mathbf{y}})$ be the result of one projected GDA update, i.e.

Then $\|\hat{\mathbf{z}}-\mathbf{z}^{*}\|\leq\epsilon$, and

The proof of Lemma 5 is deferred to Sec. E.3.

Because we would use Lemma 5 to replace (13) in the analysis of Algorithm 3 and 4, we would need to accordingly increase $M_{1}$ to $\frac{120L^{3.5}}{m_{\mathbf{x}}^{2}m_{\mathbf{y}}^{1.5}}$ and $M_{2}$ to $\frac{200L^{3}}{m_{\mathbf{x}}m_{\mathbf{y}}^{2}}$. Apart from this, another minor change in Algorithm 3 is that it would terminate after a fixed number of iterations instead of based on a termination criterion. The number of iterations is chosen such that $\|\mathbf{x}_{T}-\mathbf{x}^{*}\|+\|\mathbf{y}_{T}-\mathbf{y}^{*}\|\leq\frac{1}{M_{1}}\left[\|\mathbf{x}_{0}-\mathbf{x}^{*}\|+\|\mathbf{y}_{0}-\mathbf{y}^{*}\|\right]$ is guaranteed.

E.2 Modification of Analysis

We now claim that after modifications to the algorithms, Theorem 3 holds for constrained cases.

(Modified) Assume that $f\in\mathcal{F}(m_{\mathbf{x}},m_{\mathbf{y}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$. In Algorithm 4, the gradient complexity to find an $\epsilon$-saddle point

The proof of this theorem is, for the most part, the same as the unconstrained version. Hence, we only need to point out parts of the original proof that need to be modified for the constrained case.

To start with, Theorem 1 holds in the constrained case. The proof of Theorem 1 only relies on the analysis of AGD and the Lipschitz properties in Fact 1, and both still hold for constrained problems. (See [25, Lemma B.2] for the proof of Fact 1 in constrained problems.)

As for Theorem 2, the key modification is about (13). As argued above, (13) uses the property $g(\mathbf{x})-g(\mathbf{x}^{*})\leq\frac{L}{2}\|\mathbf{x}-\mathbf{x}^{*}\|^{2}$, which does not hold in constrained problems, since the optimum may not be a stationary point. Here, we would use Lemma 5 to derive a similar bound to replace (13). Note that originally (13) is only used to derive $\delta_{t}\leq\frac{\hat{L}+2\beta}{2}\epsilon_{t}^{2}.$ Using Lemma 5, we can replace this with

Accordingly, we can change $C_{0}$ to $44\kappa\sqrt{\kappa}\cdot 2L\left(1+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}\right)C_{1}^{2}$, and the assumption on $M$ to $M\geq 20\kappa\sqrt{\frac{4L}{m_{\mathbf{x}}}\left(1+\frac{L_{\mathbf{x}\mathbf{y}}^{2}}{m_{\mathbf{x}}m_{\mathbf{y}}}\right)}\left(1+\frac{L}{m_{\mathbf{y}}}\right)$. Then Theorem 2 would hold for the constrained case as well.

Finally, as for Theorem 3, we need to re-verify that $M_{1}$ and $M_{2}$ satisfy the new assumptions of $M$ in order to apply Theorem 2. Observe that

It follows that the number of iterations needed to find $\|\mathbf{z}_{T}-\mathbf{z}^{*}\|\leq\epsilon$ is

It follows from Lemma 5 that the duality gap of $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is at most

Resetting $\epsilon$ to $\sqrt{\frac{\epsilon\min\{m_{\mathbf{x}},m_{\mathbf{y}}\}^{2}}{4L^{3}}}$ proves the theorem.

E.3 Properties of Projected Gradient

By Corollary 2.2.1 , $(\mathbf{x}_{0}-\hat{\mathbf{x}})^{T}(\mathbf{x}_{0}-\mathbf{x}^{*})\geq\frac{1}{2}\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|^{2}$. Therefore

Meanwhile, note that $\hat{\mathbf{x}}=\operatorname*{arg\,min}_{\mathbf{x}\in\mathcal{X}}\left\{\nabla g(\mathbf{x}_{0})^{T}\mathbf{x}+\frac{L}{2}\|\mathbf{x}-\mathbf{x}_{0}\|^{2}\right\}$. By the optimality condition and the $L$-strong convexity of $\nabla g(\mathbf{x}_{0})^{T}\mathbf{x}+\frac{L}{2}\|\mathbf{x}-\mathbf{x}_{0}\|^{2}$, we have

This can be seen as a special case of Proposition 2.2 . Define the gradient descent-ascent field to be $F(\mathbf{z}):=\left[\begin{matrix}\nabla_{\mathbf{x}}f(\mathbf{x},\mathbf{y})\\ -\nabla_{\mathbf{y}}f(\mathbf{x},\mathbf{y})\end{matrix}\right]$. Note that the $\hat{\mathbf{z}}$ can also be written as

Now, define $\mathbf{z}^{\prime}=(\mathbf{x}^{\prime},\mathbf{y}^{\prime})$ to be

In other words, $\mathbf{z}^{\prime}=\operatorname*{arg\,min}_{\mathbf{z}\in\mathcal{X}\times\mathcal{Y}}\left\{L\|\mathbf{z}-\mathbf{z}_{0}\|^{2}+F(\hat{\mathbf{z}})^{T}\mathbf{z}\right\}.$ By the optimality condition and $2L$-strong convexity of $L\|\mathbf{z}-\mathbf{z}_{0}\|^{2}+F(\hat{\mathbf{z}})^{T}\mathbf{z}$, for any $\mathbf{z}\in\mathcal{X}\times\mathcal{Y}$,

Similarly, by optimality of $\hat{\mathbf{z}}$,

Here we used the fact that for any $\mathbf{z}_{1}$, $\mathbf{z}_{2}$, $\|F(\mathbf{z}_{1})-F(\mathbf{z}_{2})\|\leq 2L\|\mathbf{z}_{1}-\mathbf{z}_{2}\|$. Note that (by convexity and concavity)

If we choose $\mathbf{x}$ and $\mathbf{y}$ to be $\mathbf{x}^{*}(\hat{\mathbf{y}})$ and $\mathbf{y}^{*}(\hat{\mathbf{x}})$, we can see that

By Corollary 2.2.1 , $\left(\mathbf{x}_{0}-\hat{\mathbf{x}}\right)^{T}(\mathbf{x}_{0}-\mathbf{x}^{*})\geq\frac{1}{2}\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|^{2}$. Therefore

Similarly, $\|\hat{\mathbf{y}}-\mathbf{y}^{*}\|\leq\|\mathbf{y}_{0}-\mathbf{y}^{*}\|$. Thus

Appendix F Implications of Theorem 3

In this section, we discuss how Theorem 3 implies improved bounds for strongly convex-concave problems and convex-concave problems via reductions established in .

Let us consider minimax optimization problem $\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{y}\in\mathcal{Y}}f(\mathbf{x},\mathbf{y})$, where $f(\mathbf{x},\mathbf{y})$ is $m_{\mathbf{x}}$-strongly convex with respect to $\mathbf{x}$, concave with respect to $\mathbf{y}$, and $(L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}})$-smooth. Here, we assume that $\mathcal{X}$ and $\mathcal{Y}$ are bounded sets, with diameters $D_{\mathbf{x}}=\max_{\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}}\|\mathbf{x}-\mathbf{x}^{\prime}\|$ and $D_{\mathbf{y}}=\max_{\mathbf{y},\mathbf{y}^{\prime}\in\mathcal{Y}}\|\mathbf{y}-\mathbf{y}^{\prime}\|$.

Recall that $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is an $\epsilon$-saddle point of $f$ 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$. We now show that a $(\epsilon/2)$-saddle point of $f_{\epsilon,\mathbf{y}}$ would be an $\epsilon$-saddle point of $f$. Let $\mathbf{x}^{*}(\cdot):=\operatorname*{arg\,min}_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x},\cdot)$ and $\mathbf{y}^{*}(\cdot):=\operatorname*{arg\,max}_{\mathbf{y}\in\mathcal{Y}}f(\cdot,\mathbf{y})$. Obviously, for any $\mathbf{x}\in\mathcal{X}$, $\mathbf{y}\in\mathcal{Y}$,

Thus, if $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is a $(\epsilon/2)$-saddle point of $f_{\epsilon,\mathbf{y}}$, then

Thus, to find an $\epsilon$-saddle point of $f$, we only need to find an $(\epsilon/2)$-saddle point of $f_{\epsilon,\mathbf{y}}$. We can now prove Corollary 1 by reducing to (the constrained version of) Theorem 3.

Observe that $f_{\epsilon,\mathbf{y}}$ belongs to $\mathcal{F}(m_{\mathbf{x}},\frac{\epsilon}{D_{\mathbf{y}}^{2}},L_{\mathbf{x}},L_{\mathbf{x}\mathbf{y}},L_{\mathbf{y}}+\frac{\epsilon}{D_{\mathbf{y}}^{2}})$. Thus, by Theorem 3, the gradient complexity of finding a $(\epsilon/2)$-saddle point in $f_{\epsilon,\mathbf{y}}$ is Here it is assumed that $\epsilon$ is sufficiently small, i.e. $\epsilon\leq\max\{L_{\mathbf{x}\mathbf{y}},m_{\mathbf{x}}\}D_{\mathbf{y}}^{2}$.

It can be shown that for any $\hat{\mathbf{x}}\in\mathcal{X}$,

Similarly, for any $\hat{\mathbf{y}}\in\mathcal{Y}$,

Therefore, if $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is an $(\epsilon/2)$-saddle point of $f_{\epsilon}$, it is an $\epsilon$-saddle point of $f$, as