A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems

Introduction

We consider the following minimax optimization problem:

Minimax optimization problems have been studied for many years, but most previous works focused on convex-concave minimax problems, i.e., $f(x,y)$ is convex with respect to $x$ and concave with respect to $y$ Nedic ; Boyd ; Chen . Under this setting, Nemirovski Nemi2004 proposed a mirror-prox algorithm which returns an $\varepsilon$-saddle point within the complexity of $\mathcal{O}(1/\varepsilon)$ when $\mathcal{X}$ and $\mathcal{Y}$ are bounded sets. Nesterov Nes2007 developed a dual extrapolation algorithm which owns the same complexity bound as in Nemi2004 . Monteiro and Svaiter Mon2010 ; Mon2011 extended the complexity result to unbounded sets and composite objectives by using the hybrid proximal extragradient algorithm with a different termination criterion. Tseng Tseng2008 proved the same result using a refined convergence analysis. Abernethy et al. Abernethy presented a Hamiltonian gradient descent algorithm with last-iterate convergence under a “sufficient bilinear” condition. A few other papers have studied special cases in the convex-concave setting, for more details, we refer to Chen ; Chen2017 ; Dang ; He2016 ; Lan2016 ; Lin2020 ; Ouyang2015 ; Ouyang2019 and the references therein.

As mentioned earlier, another interesting class of minimax problems is the (strongly) convex-nonconcave setting of (P), i.e., $f(x,y)$ is (strongly) convex w.r.t. $x$ and nonconcave w.r.t. $y$. However, for any given $x$, to solve the inner maximization subproblem, i.e., $\max_{y\in\mathcal{Y}}f(x,y)$, is already NP-hard. Due to this reason, almost all the existing nested-loop algorithms will lose their theoretical guarantees since they need to solve the inner subproblem exactly, or approximately with an error proportional to the accuracy $\varepsilon$. Most existing single-loop algorithms, e.g., HiBSA or GDmax, will also get stuck, since they require the solution of the inner maximization problem. One possible alternative approach would be to switch the order of the “$\min$” and “$\max$” operators. However, in general, $\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\ f(x,y)\not=\max\limits_{y\in\mathcal{Y}}\min\limits_{x\in\mathcal{X}}\ f(x,y)$ when $f(x,y)$ is nonconvex w.r.t. $x$ or nonconcave w.r.t. $y$. The set of stationary points for these problems obtained by switching the order of “$\min$” and “$\max$” could also be different under some criterions, e.g., $\|\nabla\Phi(\cdot)\|\leq\varepsilon$ with $\Phi(\cdot)=\max_{y\in\mathcal{Y}}f(\cdot,y)$ which is meaningful when $f(\cdot,y)$ is strongly concave with respect to $y$ as defined in Lin2020 . Whereas the set of stationary points for the above two problems might the same (e.g., in terms of the stationarity of $f$), the algorithms applied to these problems may have drastically different trajectories and would converge to quite different solutions.

Contributions. In this paper, we focus on single-loop algorithms for solving nonconvex-concave and convex-nonconcave minimax problems. Our main contributions are as follows.

We propose a simple and unified single-loop Alternating Gradient Projection (AGP) algorithm for solving both nonconvex-(strongly) concave and (strongly) convex-nonconcave smooth minimax problems. At each iteration, only simple gradient projection steps are employed for updating $x$ and $y$ alternatively.

We analyze the gradient complexity of the proposed unified AGP algorithm under four different settings. For the nonconvex-concave setting, we show that an $\varepsilon$-stationary point of $f$ can be obtained in $\mathcal{O}\left(\varepsilon^{-2}\right)$ (resp. $\mathcal{O}\left(\varepsilon^{-4}\right)$) iterations for nonconvex-strongly concave (resp. nonconvex concave) minimax problems. To the best of our knowledge, these represent the state-of-the-art single loop algorithms under nonconvex-concave setting. Secondly, we show that the gradient complexity to obtain an $\varepsilon$-stationary point of $f$ is $\mathcal{O}\left(\varepsilon^{-2}\right)$ (resp., $\mathcal{O}\left(\varepsilon^{-4}\right)$) under the strongly convex-nonconcave (resp., convex-nonconcave ) setting. To the best of our knowledge, these are the first two theoretically guaranteed convergence results reported in the literature under these settings. Existing single-loop algorithms under both nonconvex-concave and convex-nonconcave settings are summarized in Table 1.

As shown in Table 1, AGP matches the best-known $O(\epsilon^{-2})$ complexity for the nonconvex-strongly concave setting, whereas for the general nonconvex-concave setting, it improves the best-known complexity for single-loop algorithms from $O(\epsilon^{-6})$ to $O(\epsilon^{-4})$. A key step in our development is to construct a suitable potential function which involves function value plus some distance between two adjacent iterates for the nonconvex-strongly concave and strongly convex-nonconcave case, whereas an additional quadratic regularization term of $x$ or $y$ is needed for the general nonconvex-concave and convex-nonconcave case (see Lemma 3.4 and Lemma 4.4). To the best of our knowledge, this is the first time that such potential functions have been constructed for solving minimax problems. Moreover, the functional descent results in Lemmas 3.1, 3.3, 4.1, and 4.3 have not been reported before and appear to be novel from our point of view. It should be noted that the complexity of AGP does not match the best-known $O(\epsilon^{-2.5})$ complexity possessed by nested-loop algorithms for the general nonconvex-concave case. One possible reason is that only one gradient projection step is employed for solving the inner problem in single loop algorithms, and hence the error associated with the gradient for the outer problem will be larger than that for nested loop algorithms and such errors will accumulate as the algorithms proceeds. This also explains why their iteration complexity analysis might be more difficult than that of nested-looped algorithms. It is not evident to us whether or not this complexity bound obtained for single-loop algorithms can be further improved. Nevertheless, due to its simplicity and the fact that it does not require the input and fine-tuning of too many algorithmic parameters, the proposed AGP algorithm can numerically outperform the state-of-the-art nested loop algorithms as shown in Section 6.

Furthermore, AGP provides a flexible algorithmic framework that can be easily generalized to solve more complicated minimax problems. Based on the basic idea of the AGP algorithm, we propose a block alternating proximal gradient (BAPG) algorithm for solving more general nonsmooth multi-block nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems. Each BAPG iteration requires only simple proximal gradient steps to update each block of the multi-block variables alternatively. We prove the gradient complexity of the proposed BAPG algorithm under these four different settings. To the best of our knowledge, existing algorithms (especially the ones with nested loop) can hardly be extended to these more complicated multi-block settings and these complexity results have not been obtained before.

The rest of this paper is organized as follows. In Section 2, we propose a unified alternating gradient projection (AGP) algorithm for nonconvex-(strongly) concave and (strongly) convex-concave minimax problems, and we then analyze the corresponding gradient complexity for four different settings in Section 3 and Section 4. We propose a block alternating proximal gradient (BAPG) algorithm for solving more general nonsmooth multi-block nonconvex-(strongly) concave and (strongly) convex-nonconcave minimax problems, and also establish the corresponding gradient complexity for four different settings in Section 5. We report some numerical results in Section 6 and make some concluding remarks in the last section.

A continuously differentiable function $f(\cdot)$ is called $\theta$-strongly convex if there exists a constant $\theta>0$ such that for any $x,y\in\mathcal{X}$,

If $-f$ satisfies (1.1), $f(\cdot)$ is called $\theta$-strongly concave. A pair $(x^{*},y^{*})$ is a Nash equilibrium (or equivalently a saddle point) of function $f$, if $\forall x\in\mathcal{X},$ $\forall y\in\mathcal{Y}$,

A pair $(x^{*},y^{*})$ is a local Nash equilibrium (or equivalently a local saddle point) of $f$, if there exists $\delta>0$ such that for any $(x,y)$ in $\mathcal{X}\times\mathcal{Y}$ and $\|x-x^{*}\|\leq\delta,\|y-y^{*}\|\leq\delta$, (1.2) is satisfied. A pair $(x^{*},y^{*})$ is an $\varepsilon$-first-order Nash equilibrium of function $f$, if $\mathcal{X}(x^{*},y^{*})\leq\varepsilon$ and $\mathcal{Y}(x^{*},y^{*})\leq\varepsilon$, where

An Alternating Gradient Projection Algorithm for (P)

In this section, we propose a unified alternating gradient projection (AGP) algorithm that will be used later for solving a few different classes of (P). Each iteration of the proposed AGP algorithm consists of two gradient projection steps for updating both $x$ and $y$. Instead of the original function $f(x,y)$, at the $k$-th iteration, AGP uses the gradient of a regularized version of the original function, i.e.,

where $b_{k}\geq 0$ and $c_{k}\geq 0$ are two regularization parameters. More specifically, for a given pair $(x_{k},y_{k})\in\mathcal{X}\times\mathcal{Y}$, AGP minimizes a linearized approximation of $f_{k}(x,y_{k})$ plus some regularized terms to update $x_{k}$ as follows:

where $\mathcal{P}_{\mathcal{X}}$ is the projection operator onto $\mathcal{X}$ and $\beta_{k}>0$ denotes a stepsize parameter. Similarly, it updates $y_{k}$ by maximizing a linearized approximation of $f_{k}(x_{k+1},y)$ minus some regularized terms, i.e.,

where $\mathcal{P}_{\mathcal{Y}}$ is the projection operator onto $\mathcal{Y}$ and $\gamma_{k}>0$ is another stepsize parameter. The proposed AGP method is formally stated in Algorithm 1, where sequences $\{\beta_{k}\}$, $\{b_{k}\}$, $\{\gamma_{k}\}$, $\{c_{k}\}$ and the stopping rule in Step 4 will be specified later in each of the different problem settings to be studied.

Observe that if we set $b_{k}=0$ and $c_{k}=0$, the AGP algorithm is exactly the alternating version of the GDA algorithm, which is rather natural and has been widely used by practitioners for solving minimax problems, e.g., in generative adversarial networks. However, to the best of our knowledge, even for the alternating GDA algorithm, the convergence for solving (P) has never been established before in the literature. Moreover, if $b_{k}$ or $c_{k}$ is not equal to , AGP algorithm is completely new. It turns out that $b_{k}$ or $c_{k}$ plays a very crucial role to guarantee the convergence of AGP when solving general nonconvex-concave or convex-nonconcave minimax problems.

Before we prove the iteration complexity of AGP algorithm for solving (P), we define the stationarity gap as the termination criterion as follows.

At each iteration of Algorithm 1, the stationarity gap for problem (P) w.r.t. $f(x,y)$ is defined as:

We denote $\nabla{G}_{k}:=\nabla{G}(x_{k},y_{k})$, $(\nabla G_{k})_{x}:=\beta_{k}(x_{k}-\operatorname{\mathcal{P}_{\mathcal{X}}}(x_{k}-\frac{1}{\beta_{k}}\nabla_{x}f(x_{k},y_{k})))$, and $(\nabla G_{k})_{y}:=\gamma_{k}(y_{k}-\operatorname{\mathcal{P}_{\mathcal{Y}}}(y_{k}+\frac{1}{\gamma_{k}}\nabla_{y}f(x_{k},y_{k})))$.

Note that the widely used metrics for convex-concave minimax problems such as the min-max value or the distance to the set of optimal solutions of the min-max problem are not applicable in nonconvex cases. For the latter cases we call $(x_{k},y_{k})$ an $\varepsilon$-stationary point of $f(x,y)$ if $\|\nabla G(x_{k},y_{k})\|\leq\varepsilon$ with $\nabla G(x_{k},y_{k})$ being defined as in Definition 2.1, which has been widely used as the optimality measure, e.g., Lin2020 ; Lu . In the absence of constraints, $\|\nabla G(x_{k},y_{k})\|\leq\varepsilon$ reduces to the standard condition $\|\nabla_{x}f(x_{k},y_{k})\|\leq\varepsilon$ and $\|\nabla_{y}f(x_{k},y_{k})\|\leq\varepsilon$ for unconstrained problems. The vector $\nabla G(x_{k},y_{k})$ also refers to gradient mapping at $(x_{k},y_{k})$, see Nes2013 for the details.

At each iteration of Algorithm 1, the stationarity gap for problem (P) w.r.t. $f_{k}(x,y)$ is defined as:

We also need to make the following assumption about the smoothness of $f(x,y)$.

$f\left(x,y\right)$ has Lipschitz continuous gradients, i.e., there exist positive scalars $L_{22}$, $L_{12}$, $L_{11}$, $L_{21}$ such that for any $x,\bar{x}\in\mathcal{X}$, $y,\bar{y}\in\mathcal{Y}$,

We denote $L:=\max\{L_{11},L_{22},L_{12},L_{21}\}$.

Under this assumption, we can first prove the following lemma for estimating bounds on changes in the function value when $x_{k}$ or $y_{k}$ is updated at each iteration in Algorithm 1.

Suppose that Assumption 2.1 holds. Let $\{(x_{k},y_{k})\}$ be a sequence generated by Algorithm 1. Then we have

Firstly, by the optimality condition for (2.4), we have

By Assumption 2.1, the gradient of $f$ is Lipschitz continuous, implying that

Adding (2.8) and (2.9), we can easily show that

This completes the proof of (2.6). By the optimality condition for (2.5), we have

By Assumption 2.1, the gradient of $f$ is Lipschitz continuous, implying that

The result (2.7) then follows by adding (2.10) and (2.11).

In the following two sections, we will establish the iteration complexity of the AGP algorithm under four different problem settings. Although there are some different technical details under different problem settings, the main process used in these proofs is similar. Firstly, we estimate a bound on the change of function values between two adjacent iterates, shown as in Lemmas 3.1, 3.3, 4.1 and 4.3 respectively. Then, we estimate an upper bound on the weighted distance between two adjacent pairs of iterates by constructing a suitable potential function according to different properties of the objective function, shown as in Lemmas 3.2, 3.4, 4.2 and 4.4 respectively. Finally, by using those upper bounds, we prove the complexity of the algorithm through some careful parameter selection, shown as in Theorems 3.1, 3.2, 4.1 and 4.2.

Complexity Analysis for Nonconvex-Concave Minimax Problems

In this subsection, we analyze the iteration complexity of Algorithm 1 for solving nonconvex-strongly concave minimax optimization problems, i.e., $f(x,y)$ is nonconvex w.r.t. $x$ for any fixed $y\in\mathcal{Y}$, and $\mu$-strongly concave w.r.t. $y$ for any given $x\in\mathcal{X}$. Under this setting, $\forall k\geq 1$, we set

in Algorithm 1, and simplify the update for $x_{k}$ and $y_{k}$ as follows:

which is exactly the alternating version of GDA algorithm. Our goal in the remaining part of this subsection is to establish the iteration complexity of Algorithm 1 under the nonconvex-strongly concave setting.

We now establish an important recursion for the AGP algorithm.

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.1). If $\eta>L_{11}$, then we have

The optimality condition for $y_{k}$ in (3.3) implies that $\forall y\in\mathcal{Y}$ and $\forall k\geq 1$,

On the other hand, by replacing $k$ with $k-1$ and choosing $y=y_{k+1}$ in (3.5), we obtain

which, in view of the fact that $f\left(x,y\right)$ is $\mu$-strongly concave w.r.t. $y$ for any given $x\in\mathcal{X}$, then implies that

Denoting $v_{k+1}:=\left(y_{k+1}-y_{k}\right)-\left(y_{k}-y_{k-1}\right)$, we can write the first inner product term in the r.h.s. of (3.1) as

Next, we estimate the three terms in the right hand side of (3.1) respectively. By Assumption 2.1 and the Cauchy-Schwarz inequality, we can bound the first two terms according to

For the third term, by $\mu$-strongly-concavity of $f$ with respect to $y$,

Plugging (3.1)-(3.13) into (3.1) and rearranging the terms, we conclude that

By setting $\beta_{k}=\eta$, $b_{k}=0$ in (2.6) of Lemma 2.1 and the assumption $\eta>L_{11}$, we have

The proof is completed by combining (3.1) with (3.15).

One may want to take the telescoping sum of (3.1) in order to provide a bound on $\sum_{k}(\|x_{k+1}-x_{k}\|^{2}+\|y_{k+1}-y_{k}\|^{2})$. However, since $(1/\rho+\rho L_{22}^{2})/2\geq L_{22}\geq\mu$, the coefficient of the third term in the r.h.s. of (3.1) is always positive. As a result, we need to further refine this relation as shown below.

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.1). Also let us denote

which together with (3.1) then imply that

By plugging (3.11),(3.12),(3.19) into (3.1), and using the identity $\frac{1}{\rho}\langle v_{k+1},y_{k+1}-y_{k}\rangle=\frac{1}{2\rho}\|y_{k+1}-y_{k}\|^{2}+\frac{1}{2\rho}\|v_{k+1}\|^{2}-\frac{1}{2\rho}\|y_{k}-y_{k-1}\|^{2}$, we conclude that

Multiplying $\frac{4}{\rho\mu}$ on both sides of (3.1) and using the definition of $S_{k+1}$, we obtain

It then follows from (3.1) in Lemma 3.1 and the definition of $F_{k}$ that

We are now ready to establish the iteration complexity for the AGP algorithm in the nonconvex-strongly concave setting. In particular, letting $\nabla G\left(x_{k},y_{k}\right)$ be defined as in Definition 2.1 and $\varepsilon>0$ be a given target accuracy, we provide a bound on $T(\varepsilon)$, the first iteration index to achieve an $\varepsilon$-stationary point, i.e., $\|\nabla G(x_{k},y_{k})\|\leq\varepsilon$, which is equivalent to

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.1). If the relations $\eta>L_{11},\eta>L_{12}^{2}\rho+\frac{4L_{12}^{2}}{\rho\mu^{2}},\ \mbox{and}\ \rho\leq\frac{\mu}{4L_{22}^{2}}$ are satisfied, then it holds that

where $d_{1}:=\min\left\{\frac{\eta}{2}-\frac{\rho L_{12}^{2}}{2}-\frac{2L_{12}^{2}}{\rho\mu^{2}},\frac{3\mu-\rho L_{22}^{2}}{2}+\frac{\mu-4\rho L_{22}^{2}}{2\rho\mu}\right\}/\max\left\{\eta^{2}+2L_{12}^{2},\frac{2}{\rho^{2}}\right\}$ and $\underline{F}:=\underline{f}-(\mu+\frac{7}{2\rho}-\frac{\rho L_{22}^{2}}{2}-\frac{2L_{22}^{2}}{\mu})\sigma_{y}^{2}$ with $\underline{f}:=\min_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$ and $\sigma_{y}:=\max\{\|y_{1}-y_{2}\|\mid y_{1},y_{2}\in\mathcal{Y}\}$.

It follows immediately from (3.1) and (3.2) that

On the other hand, by (3.3) and the triangle inequality, we obtain that

By combining (3.23) and (3.1), and using the Cauchy-Schwarz inequality, we obtain

Observing that $d_{1}>0$. Multiplying both sides of (3.25) by $d_{1}$, and using (3.2) in Lemma 3.2, we have

Summing up the above inequalities from $k=1$ to $k=T(\varepsilon)$, we obtain

Note that by the definition of $F_{k+1}$ in Lemma 3.2, we have

where the inequality follows from the definitions of $\underline{f}$ and $\sigma_{y}$, and the facts that $S_{k}\geq 0$ ($\forall k\geq 1$) and $\mu+\frac{7}{2\rho}-\frac{\rho L_{22}^{2}}{2}-\frac{2L_{22}^{2}}{\mu}\geq 0$ due to the selection of $\rho$. We then conclude from (3.27) that $\sum_{k=1}^{T\left(\varepsilon\right)}{d_{1}\|\nabla G_{k}\|^{2}}\leq F_{1}-F_{T\left(\varepsilon\right)+1}\leq F_{1}-\underline{F}$ which, in view of the definition of $T(\varepsilon)$, implies that $\varepsilon^{2}\leq(F_{1}-\underline{F})/(T(\varepsilon)\cdot d_{1})$ or equivalently, $T\left(\varepsilon\right)\leq(F_{1}-\underline{F})/(d_{1}\varepsilon^{2})$.

A few remarks are in place for the results obtained in Theorem 3.1. First, in view of Theorem 3.1, the gradient complexity of Algorithm 1 to obtain a stationary point that satisfies $\|\nabla G(x_{k},y_{k})\|\leq\varepsilon$ is given by $\mathcal{O}(L^{2}\varepsilon^{-2})$ under the nonconvex-strongly concave setting. Second, under this setting, very few single-loop algorithms have been investigated although a few other existing algorithms can achieve similar complexity bound. In particular, it seems that even the complexity bound for the GDA algorithm remains unknown under this setting when $\mathcal{X}$ and $\mathcal{Y}$ are both convex compact sets. Compared to the state-of-the-art algorithm in Lin2020 , we improve the complexity for the nonconvex-strongly concave setting by a logarithmic factor, since we do not need to solve the inner problem at each iteration. Third, as mentioned earlier, Algorithm 1 is a single-loop alternating gradient projection method with constant stepsizes, which is very easy to implement in practice.

2 Complexity Analysis for General Nonconvex-Concave Setting

In this subsection, we analyze the iteration complexity of Algorithm 1 for solving (P) under the general nonconvex-concave setting. Under this setting, $\forall k\geq 1$, we set

where $\bar{\eta}>0$, $\bar{\rho}>0$ are two constants, and $\bar{\beta}_{k}$ are stepsize parameters to be defined later. We need to make the following assumption on the parameters $c_{k}$.

$\{c_{k}\}$ is a nonnegative monotonically decreasing sequence.

By Assumption 2.1 and $\nabla_{y}f_{k-1}\left(x,y\right)=\nabla_{y}f\left(x,y\right)-c_{k-1}y$, we have

Denoting $L_{22}^{{}^{\prime}}=L_{22}+c_{1}$, by Assumption 3.1 and (3.2), we have

It then follows from the above inequality and the strong concavity of $f_{k-1}\left(x_{k},y\right)$ w.r.t. $y$ (Theorem 2.1.12 in Nestrov ) that

This is a key inequality that we will use to establish some important recursions for the AGP method under the nonconvex-concave setting in the following two results. This is also one of the key differences between the proof for the nonconvex-strongly concave setting and the one for the nonconvex-concave setting.

Suppose that Assumptions 2.1 and 3.1 hold. Let $\{(x_{k},y_{k})\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.28). If $\forall k,\bar{\beta}_{k}>L_{11}$ and $\bar{\rho}\leq\frac{2}{L_{22}^{{}^{\prime}}+c_{1}}$, then

The optimality condition for $y_{k}$ in (2.5) implies that, $\forall y\in\mathcal{Y}$, $\forall k\geq 1$,

On the other hand, by replacing $k$ with $k-1$ and choosing $y=y_{k+1}$ in (3.32), we obtain

The concavity of $f_{k}(x_{k+1},y)$ w.r.t. $y$ together with (3.34) then imply that

where $v_{k+1}=y_{k+1}-y_{k}-(y_{k}-y_{k-1})$. We now provide bounds on the inner product terms of (3.2). Firstly, by the definition of $f_{k}(x_{k+1},y_{k})$ and $f_{k-1}(x_{k},y_{k})$, Assumptions 2.1 and 3.1, and the Cauchy-Schwarz inequality, we have

Secondly, by the Cauchy-Schwarz inequality,

Plugging (3.2)-(3.39) into (3.2), and using the definition of $f_{k}(x_{k+1},y_{k+1})$ and $f_{k}(x_{k+1},y_{k})$ and the assumption $\frac{\bar{\rho}}{2}\leq\frac{1}{L_{22}^{{}^{\prime}}+c_{1}}$, we obtain

By setting $\beta_{k}=\bar{\eta}+\bar{\beta}_{k}$, $b_{k}=0$ in (2.6) of Lemma 2.1 and the assumption $\bar{\beta}_{k}>L_{11}$, we have

The result in (3.3) then follows by adding (3.2) and (3.41).

It turns out that from Lemma 3.3 we can not obtain an upper bound on the positively weighted sum of $\|x_{k+1}-x_{k}\|^{2}$ and $\|y_{k+1}-y_{k}\|^{2}$ to provide an upper bound for $\|\nabla G_{k}\|$. We need to further refine this result in (3.3) to overcome this difficulty. In particular, we obtain below a new inequality as in (3.2) to further investigate the relation between $\|x_{k+1}-x_{k}\|^{2}$ and $\|y_{k+1}-y_{k}\|^{2}$. Then by using this new inequality, we construct a new potential function as shown in the following important result for Algorithm 1. Note that in Lemma 3.2 we have constructed a potential function which involves the function value plus some distance between two adjacent iterates for the nonconvex-strongly concave cases, whereas in the following lemma an additional quadratic regularization term, i.e., $\|y_{k+1}\|^{2}$, is added to construct another potential function for the general nonconvex-concave case.

Suppose that Assumptions 2.1 and 3.1 hold. Let $\{(x_{k},y_{k})\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.28). Also let us denote

Similar to (3.2) in Lemma 3.3, (3.44) can be rewritten as

Using an argument similar to the proof of (3.2)-(3.39), the relation in (3.2), and the Cauchy-Schwarz inequality, we conclude from the above inequality that

for any $a_{k}>0$. Observing by $c_{1}\leq L_{22}^{{}^{\prime}}$, and Assumption 3.1, we have

Combining $\bar{\rho}\leq\frac{2}{L_{22}^{{}^{\prime}}+c_{1}}$ and rearranging the terms in (3.2), we obtain

By multiplying $\frac{16}{\bar{\rho}c_{k}}$ on both sides of the above inequality, we then obtain

Setting $a_{k}=\frac{c_{k}}{2}$ in the above inequality, and using the definition of $\mathcal{S}_{k+1}$ and (3.42), we have

Combining (3.2) and (3.3) in Lemma 3.3, and using the definition of $\mathcal{F}_{k+1}$, we conclude

We are now ready to establish the iteration complexity for the AGP algorithm to achieve an $\varepsilon$-stationary point in the general nonconvex-concave setting.

Suppose that Assumption 2.1 holds. Let $\{(x_{k},y_{k})\}$ be a sequence generated by Algorithm 1 with parameter settings in (3.28). If $\bar{\rho}\leq\frac{1}{10L_{22}}$, $\tau>\max\{\frac{19^{2}(L_{11}+2\bar{\eta}-\bar{\rho}L_{12}^{2})}{20^{2}\cdot 16\bar{\rho}L_{12}^{2}},2\}$, $c_{k}=\frac{19}{20\bar{\rho}k^{\text{1/}4}},k\geq 1$, then for any given $\varepsilon>0$,

where $d_{2}=\mathcal{F}_{2}-\underline{\mathcal{F}}+(8\cdot 2^{1/4}+\frac{19}{40})\frac{\hat{\sigma}_{y}^{2}}{\bar{\rho}}$, $\bar{d}_{1}=\frac{8\tau^{2}}{(\tau-2)^{2}}+\frac{19^{4}\left(2\left(\bar{\rho}L_{12}^{2}-\bar{\eta}\right)^{2}+2L_{12}^{2}\right)}{64\cdot 20^{4}\bar{\rho}^{2}(\tau-2)^{2}L_{12}^{4}}$, $d_{3}=\max\{\bar{d}_{1},\frac{19^{2}}{1440\sqrt{2}(\tau-2)\bar{\rho}^{2}L_{12}^{2}}\}$, $\hat{\sigma}_{y}:=\max\{\|y\|\mid y\in\mathcal{Y}\}$, $\underline{\mathcal{F}}:=\underline{f}-\left(2^{13/4}+15+\frac{19}{40}\right)\frac{\hat{\sigma}_{y}^{2}}{\bar{\rho}}$ with $\underline{f}:=\min_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$.

By $\bar{\rho}\leq\frac{1}{10L_{22}}$ and $c_{k}=\frac{19}{20\bar{\rho}k^{\text{1/}4}},\forall k\geq 1$, let us denote $\bar{\beta}_{k}=\bar{\rho}L_{12}^{2}+\frac{16\tau L_{12}^{2}}{\bar{\rho}c_{k}^{2}}-2\bar{\eta}$, $\alpha_{k}=\frac{8(\tau-2)L_{12}^{2}}{\bar{\rho}c_{k}^{2}}$, we can easily see that the relations in (3.42) are satisfied. It follows from the selection of $\bar{\beta}_{k}$ and $\alpha_{k}$ that

This observation, in view of Lemma 3.4, then immediately implies that

We can easily check from the definition of $f_{k}(x,y)$ that

By replacing $f$ with $f_{k}$, $\eta$ with $\bar{\beta}_{k}+\bar{\eta}$, similar to (3.23) and (3.1), we immediately obtain that

Combining (3.49) and (3.50), and using the Cauchy-Schwarz inequality, we have

Since both $\alpha_{k}$ and $\bar{\beta}_{k}$ are in the same order when $k$ becomes large enough, it then follows from the definition of $\bar{d}_{1}$ that $\forall k\geq 1$,

Combining the previous two inequalities in (3.2) and (3.51), we obtain

Denote $d_{k}^{(2)}=\frac{1}{\max\left\{\bar{d}_{1}\alpha_{k},\frac{20}{9\bar{\rho}}\right\}}$. By multiplying $d_{k}^{(2)}$ on the both sides of (3.53), and using (3.2), we have

where the last inequality follows since $d_{k}^{(2)}$ is a decreasing sequence. Denoting

Note that by the definition of $\mathcal{F}_{k+1}$ in Lemma 3.4, we have

where $\underline{f}:=\min_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$. We then conclude from (3.2) that

On the other hand, if $k\geq\frac{19^{4}\hat{\sigma}_{y}^{4}}{10^{4}\bar{\rho}^{4}\varepsilon^{4}}$, then $c_{k}=\frac{19}{20\bar{\rho}k^{1/4}}\leq\frac{\varepsilon}{2\hat{\sigma}_{y}}$. This inequality together with the definition of $\hat{\sigma}_{y}$ then imply that $c_{k}\|y_{k}\|\leq\frac{\varepsilon}{2}$. Therefore, there exists a

According to Theorem 3.2, we can show that, by specifying $\gamma_{k}$ and $c_{k}$ as in the order of $k^{1/2}$ and $1/k^{1/4}$, the gradient complexity of Algorithm 1 to obtain an $\varepsilon$-stationarity point of $f$ in the nonconvex-concave setting can be bounded by $\mathcal{O}(L^{4}\varepsilon^{-4})$. In this setting the stepsize for updating $x_{k}$ is in the order of $k^{-1/2}$, while the one for updating $y_{k}$ is a constant at iteration $k$.

Note that for solving unconstrained bilinear minimax problem, the alternating GDA algorithm with any fixed step size will cause recurrence Bailey2020 . In the classic convex optimization literature, such a divergence issue was usually handled by incorporating averaging, smoothing, or direct acceleration techniques (see, e.g., Sections 3.5-3.8 and Sections 4.3-4.5 of Lan2020book ). However, the proposed AGP algorithm for nonconvex minimax problems is not equivalent to the alternating GDA algorithm, since a regularized version of the original function is incorporated, and a variable stepsize policy has been used for the nonconvex-concave setting. Hence, the results of our paper do not contradict with existing ones.

Complexity Analysis for Convex-Nonconcave Minimax Problems

In this section, we establish the convergence of AGP algorithm for the cases where $f$ is convex w.r.t. $x$, but possibly nonconcave w.r.t. $y$. These are important minimax problems but the studies on their solution methods are still quite limited. Although there exists some symmetry between nonconvex-concave and convex-nonconcave minimax problems, the complexity analysis of the same AGP algorithm for nonconvex-concave setting cannot be trivially extended to that for convex-nonconcave setting.

In this subsection, we analyze the iteration complexity of Algorithm 1 for solving strongly convex-nonconcave minimax optimization problems (P), i.e., $f(x,y)$ is $\theta$-strongly convex w.r.t. $x$ for any fixed $y\in\mathcal{Y}$, and nonconcave w.r.t. $y$ for any given $x\in\mathcal{X}$. Under this setting, $\forall k\geq 1$, we set

in Algorithm 1, and simplify the update for $x_{k}$ and $y_{k}$ as follows:

Our goal in the remaining part of this subsection is to establish the iteration complexity of Algorithm 1 under the strongly convex-nonconcave setting. The convergence analysis for this setting is different from that of the nonconvex-strongly concave setting in Section 3.

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.1). If $\nu>L_{22}$, then we have

Similar to (3.5)-(3.7) in the proof of Lemma 3.1, by the optimality condition for $x_{k}$ in (4.2) implies that $\forall x\in\mathcal{X}$ and $\forall k\geq 1$,

which, in view of the fact that $f\left(x,y\right)$ is $\theta$-strongly convex w.r.t. $x$ for any given $y\in\mathcal{Y}$, then implies that

Denoting $m_{k+1}:=\left(x_{k+1}-x_{k}\right)-\left(x_{k}-x_{k-1}\right)$, by Assumption 2.1, the Cauchy-Schwarz inequality and the $\theta$-strongly convexity of $f$ w.r.t. $x$, we can estimate the first inner product term in the r.h.s. of (4.1) as

Plugging (4.10) and (4.11) into (4.1) and rearranging the terms, we conclude that

By setting $\gamma_{k}=\nu$, $c_{k}=0$ in (2.7) of Lemma 2.1 and the assumption $\nu>L_{22}$, we have

The proof is completed by combining (4.1) with (4.13).

Next, we further refine this relation in (4.1) as shown below. Note that in Lemma 3.2 we have constructed a potential function for the nonconvex-strongly concave case, whereas in the following lemma, an additional term involving the distance between two adjacent iterates, i.e., $\|x_{k+1}-x_{k}\|^{2}$, is added to construct another potential function for the strongly convex-nonconcave case.

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.1). Denote

which together with (4.9) then imply that

where the second inequality is similar to the proof of (4.10) except that for the first term in the r.h.s., we use $\langle\nabla_{x}f(x_{k},y_{k})-\nabla_{x}f\left(x_{k},y_{k-1}\right),x_{k+1}-x_{k}\rangle\geq-\frac{L_{21}^{2}}{2\theta}\|y_{k}-y_{k-1}\|^{2}-\frac{\theta}{2}\|x_{k+1}-x_{k}\|^{2}$. By using the identity $\frac{1}{\zeta}\langle m_{k+1},x_{k}-x_{k+1}\rangle=\frac{1}{2\zeta}\|x_{k}-x_{k-1}\|^{2}-\frac{1}{2\zeta}\|x_{k+1}-x_{k}\|^{2}-\frac{1}{2\zeta}\|m_{k+1}\|^{2}$, we conclude from (4.17) that

Multiplying $\frac{4}{\zeta\theta}$ on both sides of (4.1) and using the definition of $\hat{S}_{k+1}$, we obtain

The proof is completed by (4.1) in Lemma 4.1 and the definition of $\hat{F}_{k}$.

We are now ready to establish the iteration complexity for the AGP algorithm in the strongly convex-nonconcave setting.

Suppose that Assumption 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.1). If the relations $\nu>L_{22},\nu>L_{21}^{2}\zeta+\frac{4L_{21}^{2}}{\zeta\theta^{2}},~{}\zeta\leq\frac{\theta}{4L_{11}^{2}}$ are satisfied, then $\forall\varepsilon>0$, it holds that

where $\hat{d}_{1}:=\tfrac{\min\left\{\tfrac{\nu}{2}-\tfrac{\zeta L_{21}^{2}}{2}-\tfrac{2L_{21}^{2}}{\zeta\theta^{2}},\tfrac{3\theta-\zeta L_{11}^{2}}{2}+\tfrac{\theta-4\zeta L_{11}^{2}}{2\zeta\theta}\right\}}{\max\left\{\tfrac{1}{\zeta^{2}}+2L_{12}^{2},2\nu^{2}\right\}}$ and $\overline{F}=\bar{f}+(\theta+\frac{7}{2\zeta}-\frac{\zeta L_{11}^{2}}{2}-\frac{2L_{11}^{2}}{\theta})\sigma_{x}^{2}$ with $\overline{f}:=\max_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$ and $\sigma_{x}=\max\{\|x_{1}-x_{2}\|\mid\forall x_{1},x_{2}\in\mathcal{X}\}$.

On the other hand, similar to the proof of (3.1), by (4.3) and the triangle inequality, and the nonexpansiveness of the projection operator $\operatorname{\mathcal{P}_{\mathcal{Y}}}$, we conclude that

By combining (4.20) and (4.21), and using the Cauchy-Schwarz inequality, we obtain

Observing that $\hat{d}_{1}>0$. Multiplying both sides of (4.22) by $\hat{d}_{1}$, and using (4.2) in Lemma 4.2, we have

Summing up the above inequalities from $k=1$ to $k=T(\varepsilon)$, we obtain

Note that by the definition of $\hat{F}_{k+1}$ in Lemma 4.2, we have

where the last inequality follows from the definitions of $\bar{f}$ and $\sigma_{x}$, and $\theta+\frac{7}{2\zeta}-\frac{\zeta L_{11}^{2}}{2}-\frac{2L_{11}^{2}}{\theta}\geq 0$ due to the selection of $\zeta$. We then conclude from (4.24) that $\sum_{k=1}^{T\left(\varepsilon\right)}{\hat{d}_{1}\|\nabla G_{k}\|^{2}}\leq\bar{F}-\hat{F}_{1}$ which, in view of the definition of $T(\varepsilon)$, implies that $\varepsilon^{2}\leq(\bar{F}-\hat{F}_{1})/(T(\varepsilon)\cdot\hat{d}_{1})$ or equivalently, $T\left(\varepsilon\right)\leq(\bar{F}-\hat{F}_{1})/(\hat{d}_{1}\varepsilon^{2})$.

Theorem 4.1 shows that the number of gradient evaluations performed by Algorithm 1 to obtain an $\varepsilon$-stationary point of $f$ is bounded by $\mathcal{O}\left(L^{2}\varepsilon^{-2}\right)$ under the strongly convex-nonconcave setting. To the best of our knowledge, this is the first theoretical guarantee that has been obtained in the literature for solving this class of minimax problems.

2 Complexity Analysis for Convex-Nonconcave Setting

In this subsection, we analyze the iteration complexity of Algorithm 1 applied to the general convex-nonconcave setting, for which $f(x,y)$ is convex w.r.t. $x$ for any fixed $y\in\mathcal{Y}$, and nonconcave w.r.t. $y$ for any given $x\in\mathcal{X}$. Under this setting, $\forall k\geq 1$, we set

where $\bar{\gamma}_{k}$ and $q_{k}$ are stepsize parameters to be defined later. We need to make the following assumption on the parameters $q_{k}$.

$\{q_{k}\}$ is a nonnegative monotonically decreasing sequence.

By Assumption 2.1 and $\nabla_{x}f_{k-1}\left(x,y\right)=\nabla_{x}f\left(x,y\right)+q_{k-1}x$, we have

Denoting $L_{11}^{{}^{\prime}}=L_{11}+q_{1}$, by Assumption 4.1 and (4.26), we have

It then follows from the above inequality and the strong convexity of $f_{k-1}\left(x,y_{k-1}\right)$ w.r.t. $x$ (Theorem 2.1.12 in Nestrov ) that

By using the strong convexity of $f_{k-1}\left(x,y_{k-1}\right)$ w.r.t. $x$ instead of the strong concavity of $f_{k-1}\left(x_{k},y\right)$ w.r.t. $y$, this inequality provides a lower bound for the inner product instead of an upper bound shown as in (3.2). This is a key inequality that we will use to establish some important recursions for the AGP algorithm under the convex-nonconcave setting in the following two results.

Similar to Lemma 4.1, we first provide an estimate on the increase of the function values from $f(x_{k},y_{k})$ to $f(x_{k+1},y_{k+1})$.

Suppose that Assumption 2.1 and 4.1 hold. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.25). If $\forall k,\bar{\gamma}_{k}>L_{22}$ and $\bar{\zeta}\leq\frac{2}{L_{11}^{{}^{\prime}}+q_{1}}$, then

Similar to (4.5)-(4.9) in the proof of Lemma 4.1, by replacing $f$ with $f_{k}$, $\zeta$ with $\bar{\zeta}$ respectively, and setting $\theta=0$, we obtain that

Next, we prove lower bound for the four terms in the r.h.s. of (4.2) which are different from that in Lemma 4.1. By using the convexity of $f_{k-1}\left(x,y_{k-1}\right)$ w.r.t $x$ instead of the concavity of $f_{k-1}\left(x_{k},y\right)$ w.r.t $y$, the opposite side Cauchy-Schwarz inequality, and replacing $\bar{\rho},c_{k},c_{k-1},L_{12}$, $L_{22}^{{}^{\prime}}$ by $\bar{\zeta},q_{k},q_{k-1},L_{21}$, $L_{11}^{{}^{\prime}}$ respectively, Assumptions 2.1 and 4.1, similar to the proof of (3.2)-(3.2) we conclude that

Plugging (4.2)-(4.33) into (4.2), and by the definition of $f_{k}(x_{k+1},y_{k})$ and $f_{k}(x_{k},y_{k})$ and $\frac{\bar{\zeta}}{2}\leq\frac{1}{L_{11}^{{}^{\prime}}+q_{1}}$, we conclude that

By setting $\gamma_{k}=\bar{\nu}+\bar{\gamma}_{k}$, $c_{k}=0$ in (2.7) of Lemma 2.1 and the assumption $\bar{\gamma}_{k}>L_{22}$, we have

The proof is completed by combing (4.34) and (4.35).

We need to further refine the relation in (4.3) in order to establish the convergence of the AGP algorithm as shown below. Note that in Lemma 4.2 we have constructed a potential function which involves the function value plus some distance between two adjacent iterates for the strongly convex-nonconcave case, whereas in the following lemma an additional quadratic regularization term, i.e., $\|x_{k+1}\|^{2}$, is added to construct another potential function for the general convex-nonconcave case.

Suppose that Assumptions 2.1 and 4.1 hold. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.25). Denote

Similar to the proof of (4.16), by replacing $f$ with $f_{k}$, we have

Using an argument similar to the proof of (4.2)-(4.33), and the Cauchy-Schwarz inequality, we conclude from the above inequality that

where $\bar{a}_{k}>0$. Observing that $q_{1}\leq L_{11}^{{}^{\prime}}$ and by Assumption 4.1, we have

By $\bar{\zeta}\leq\frac{2}{L_{11}^{{}^{\prime}}+q_{1}}$ and Assumption 4.1, rearranging the terms in (4.2), we obtain

By multiplying $\frac{16}{\bar{\zeta}q_{k}}$ on both sides of the above inequality, we then obtain

Setting $\bar{a}_{k}=\frac{q_{k}}{2}$ in the above inequality, and using the definition of $\hat{\mathcal{S}}_{k+1}$ and (4.36), we have

The proof is completed by combining (4.2) and (4.3) in Lemma 4.3, and using the definition of $\hat{\mathcal{F}}_{k+1}$.

Note that the proof of Lemma 4.4 is different from that of Lemma 3.4, since different potential functions, i.e., $\hat{\mathcal{F}}_{k+1}$ and $\mathcal{F}_{k+1}$ respectively, are used to establish the convergence of the proposed algorithms. The construction of these potential functions is the key step for our convergence analysis of AGP algorithms. We are now ready to establish the iteration complexity for the AGP algorithm to achieve an $\varepsilon$-stationary point for solving (P) under general convex-nonconcave setting.

Suppose that Assumptions 2.1 holds. Let $\{\left(x_{k},y_{k}\right)\}$ be a sequence generated by Algorithm 1 with parameter settings in (4.25). If $\bar{\zeta}\leq\frac{1}{10L_{11}}$, $\tau>\max\{\frac{19^{2}(L_{22}+2\bar{\nu}-\bar{\zeta}L_{21}^{2})}{20^{2}\cdot 16\bar{\zeta}L_{21}^{2}},2\}$, $q_{k}=\frac{19}{20\bar{\zeta}k^{\text{1/}4}},k\geq 1$, then for any given $\varepsilon>0$,

where $\hat{\sigma}_{x}:=\max\{\|x\|\mid x\in\mathcal{X}\}$,

$\hat{d}_{4}:=\max\{\hat{D}_{1},\frac{10+20\bar{\zeta}^{2}L_{21}^{2}}{9\bar{\zeta}p_{2}}\}$ with $\hat{\mathcal{D}}_{1}:=\tfrac{16\tau^{2}}{(\tau-2)^{2}}+\tfrac{19^{4}(\bar{\zeta}L_{21}^{2}-\bar{\nu})^{2}}{16\cdot 20^{4}(\tau-2)^{2}L_{21}^{4}\bar{\zeta}^{2}}$, $\hat{\mathcal{F}}_{0}:=\bar{f}+\left(2^{13/4}+15+\frac{19}{40}\right)\frac{\hat{\sigma}_{x}^{2}}{\bar{\zeta}}$ with $\bar{f}:=\max_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$.

By $\bar{\zeta}\leq\frac{1}{10L_{11}}$,$q_{k}=\frac{19}{20\bar{\zeta}k^{\text{1/}4}},\forall k\geq 1$, let us denote $\bar{\gamma}_{k}=\bar{\zeta}L_{21}^{2}+\frac{16\tau L_{21}^{2}}{\bar{\zeta}(q_{k+1})^{2}}-2\bar{\nu}$, $p_{k}=\frac{8(\tau-2)L_{21}^{2}}{\bar{\zeta}(q_{k+1})^{2}}$, it can be easily checked that the relations in (4.36) are satisfied. It follows from the selection of $\bar{\gamma}_{k}$ and $p_{k}$ that

This observation, in view of Lemma 4.4, then immediately implies that

We can easily check from the definition of $f_{k}(x_{k},y_{k})$ that

Since both $p_{k}$ and $\bar{\gamma}_{k}$ are in the same order when $k$ becomes large enough, it then follows from the definition of $\hat{D}_{1}$ that $\forall k\geq 1$,

Combining the previous two inequalities in (4.42) and (4.41), we obtain

Denote $\hat{d}_{k}^{(2)}=\frac{1}{\max\left\{\hat{D}_{1}p_{k},\frac{10+20\bar{\zeta}^{2}L_{12}^{2}}{9\bar{\zeta}}\right\}}$. By multiplying $\hat{d}_{k}^{(2)}$ on the both sides of (4.43), and using (4.2), we get

Note that by the definition of $\hat{\mathcal{F}}_{k+1}$ in Lemma 4.4, we have

where $\bar{f}:=\max_{(x,y)\in\mathcal{X}\times\mathcal{Y}}f(x,y)$. We then conclude from (4.2) that

Using the assumptions $q_{k}=\frac{19}{20\bar{\zeta}k^{1/4}}$ and $p_{k}=\frac{2\cdot 40^{2}\bar{\zeta}(\tau-2)L_{21}^{2}\sqrt{k+1}}{19^{2}}$, (4.47) and the fact $\sum_{k=2}^{\hat{T}(\varepsilon)}1/\sqrt{k+1}\geq\sqrt{\hat{T}(\varepsilon)}-2$ , we conclude that $\frac{\varepsilon^{2}}{4}\leq\frac{2\cdot 40^{2}\bar{\zeta}(\tau-2)L_{21}^{2}\hat{d}_{3}\hat{d}_{4}}{19^{2}\left(\sqrt{\hat{T}(\varepsilon)}-2\right)}$ or equivalently,

On the other hand, if $k>\frac{19^{4}\hat{\sigma}_{x}^{4}}{10^{4}\bar{\zeta}^{4}\varepsilon^{4}}$, then $q_{k}=\frac{19}{20\bar{\zeta}k^{1/4}}\leq\frac{\varepsilon}{2\hat{\sigma}_{x}}$, this inequality together with the definition of $\hat{\sigma}_{x}$ then imply that $q_{k}\lVert x_{k}\rVert\leq\frac{\varepsilon}{2}$. Therefore, there exists a

Theorem 4.2 shows that the number of gradient evaluations performed by Algorithm 1 to obtain an $\varepsilon$-stationary point of $f$ which satisfies (4.36) is bounded by $\mathcal{O}\left(L^{4}\varepsilon^{-4}\right)$ under the general convex-nonconcave setting. To the best of our knowledge, this is the first theoretical guarantee that has been obtained in the literature for solving this class of minimax problems. As mentioned in Section 1, it is difficult to extend existing algorithms, especially those nested-loop methods, for minimax optimization to the general convex-nonconcave setting. One possible approach would be to switch the order of the “$\min$” and “$\max$” operators. However, in general, $\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\ f(x,y)\not=\max\limits_{y\in\mathcal{Y}}\min\limits_{x\in\mathcal{X}}\ f(x,y)$ when $f(x,y)$ is nonconvex w.r.t. $x$ or nonconcave w.r.t. $y$. Even if the set of stationary points for the above two problems are the same, e.g., by using the same stationarity criterion as in this paper, the algorithm applied to these problems will converge to different solutions. This can be seen by applying the unified AGP algorithm to solve $\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\ f(x,y)$ and $\max\limits_{y\in\mathcal{Y}}\min\limits_{x\in\mathcal{X}}\ f(x,y)$. The AGP algorithm will likely converge to different stationary points because different potential functions (i.e., $\mathcal{F}_{k+1}$ and $\hat{\mathcal{F}}_{k+1}$ in Lemma 3.6 and Lemma 4.6) have to be applied for analyzing the convergence of AGP for solving these two problems.

For nonconvex-strongly concave or strongly convex-nonconcave setting, the AGP algorithm with properly chosen parameters is actually equivalent to the alternating GDA algorithm. By constructing suitable potential function, i.e., $F_{k+1}$, we were able to show the $O(\epsilon^{-2})$ iteration complexity of this method. Whereas for nonconvex-concave or convex-nonconcave setting, where $b_{k}$ or $c_{k}$ is not equal to , AGP algorithm is completely new and the selection of these parameters $b_{k}$ or $c_{k}$ plays a very crucial role to guarantee the convergence of the APG method. In these cases, the key step in our proof is also to construct a suitable potential function, i.e., $\mathcal{F}_{k+1}$ and $\hat{\mathcal{F}}_{k+1}$ with $b_{k}$ or $c_{k}$ playing a very crucial role (see Lemma 3.6 and Lemma 4.6 respectively). To our best knowledge, this is the first time that such potential functions have been constructed for solving minimax problems.

Block-wise Nonsmooth Nonconvex Minimax Problems

In this section, we consider a more general block-wise nonsmooth minimax problem as follows.

Note that (BP) reduces to (P) if we set $K_{1}=K_{2}=1$, $h_{i}(\cdot)=0$ and $g_{j}(\cdot)=0$, which means that (P) is a special case of (BP). There exist very few known existing nested-loop algorithms that are proposed to solve (BP) with multi-block structure. However, the minimax problems with block structure are important in machine learning and signal processing, e.g., distributed training Lu .

The difficulty to solve (BP) comes from two aspects. One is that for any given $j$, $f(x,y^{(1)},y^{(2)},\cdots,y^{(K_{2})})$ is nonconcave w.r.t. $y^{(j)}$ for any given $x$ and other blocks of $y$, i.e., $y^{(1)},y^{(2)},\cdots,y^{(j-1)},y^{(j+1)}$, $\cdots$, $y^{(K_{2}-1)}$ and $y^{(K_{2})}$. For any given $x$, to solve the inner maximization subproblems with respect to $y^{(j)}$ is already NP-hard. Due to this reason, almost all the existing nested-loop algorithms will lose their theoretic guarantees since they need to solve the inner subproblem exactly, or approximately with an error proportional to the accuracy $\varepsilon$, unless we can exchange the order of “$\min$” and “$\max$” operators. However, in general, $\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\ l(x,y)\not=\max\limits_{y\in\mathcal{Y}}\min\limits_{x\in\mathcal{X}}\ l(x,y)$ when $f(x,y)$ is nonconvex w.r.t. $x$ or nonconcave w.r.t. $y$. Although $\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\ l(x,y)$ and $\max\limits_{y\in\mathcal{Y}}\min\limits_{x\in\mathcal{X}}\ l(x,y)$ share the same stationary point set, when we use the same algorithm to solve them, it may converge to different stationary points. Another difficulty comes from the multi-block structure. To the best of our knowledge, there are very few nested-loop algorithms (and complexity results) for solving the aforementioned multi-block structure nonconvex minimax problems before our work. On the other hand, single loop algorithms do not need to solve the inner subproblem, and can be easily generalized to handle the multi-block structure.

Similar to the idea of AGP algorithm, we propose a block alternating proximal gradient algorithm (BAPG) to solve (BP). Instead of the original function $l\left(x,y\right)$, the BAPG algorithm uses the gradient of a regularized version of the original function, i.e.,

where $\bar{f}_{k}\left(x,y\right)=f\left(x,y\right)+\frac{\hat{b}_{k}}{2}\sum_{i=1}^{K_{1}}\|x^{(i)}\|^{2}-\frac{\hat{c}_{k}}{2}\sum_{j=1}^{K_{2}}\|y^{(j)}\|^{2}$ with regularization parameters $\hat{b}_{k}\geq 0$ and $\hat{c}_{k}\geq 0$ at the $k$th iteration. Before presenting the detailed algorithm, we give some notations as follows. We denote two proximity operators for $x^{(i)}$ and $y^{(j)}$ as follows,