Proximal Gradient Descent-Ascent: Variable Convergence under KŁ Geometry

Introduction

Minimax optimization is a classical optimization framework that has been widely applied in various modern machine learning applications, including game theory Ferreira et al., (2012), generative adversarial networks (GANs) Goodfellow et al., (2014), adversarial training Sinha et al., (2017), reinforcement learning Qiu et al., (2020), imitation learning Ho and Ermon, (2016); Song et al., (2018), etc. A typical minimax optimization problem is shown below, where $f$ is a differentiable function.

A popular algorithm for solving the above minimax problem is gradient descent-ascent (GDA), which performs a gradient descent update on the variable $x$ and a gradient ascent update on the variable $y$ alternatively in each iteration. Under the alternation between descent and ascent updates, it is much desired that GDA generates sequences of variables that converge to a certain optimal point, i.e., the minimax players obtain convergent optimal policies. In the existing literature, many studies have established the convergence of GDA-type algorithms under various global geometries of the objective function, e.g., convex-concave geometry ($f$ is convex in $x$ and concave in $y$) Nedić and Ozdaglar, (2009), bi-linear geometry Neumann, (1928); Robinson, (1951) and Polyak-Łojasiewicz (PŁ) geometry Nouiehed et al., (2019); Yang et al., (2020). Some other work studied GDA under stronger global geometric conditions of $f$ such as convex-strongly-concave geometry Du and Hu, (2019) and strongly-convex-strongly-concave geometry Mokhtari et al., (2020); Zhang and Wang, (2020), under which GDA is shown to generate convergent variable sequences. However, these special global function geometries do not hold for modern machine learning problems that usually have complex models and nonconvex geometry.

Recently, many studies characterized the convergence of GDA in nonconvex minimax optimization, where the objective function is nonconvex in $x$. Specifically, Lin et al., (2020); Nouiehed et al., (2019); Xu et al., 2020b ; Boţ and Böhm, (2020) studied the convergence of GDA in the nonconvex-concave setting and Lin et al., (2020); Xu et al., 2020b studied the nonconvex-strongly-concave setting. In these general nonconvex settings, it has been shown that GDA converges to a certain stationary point at a sublinear rate, i.e., $\|G(x_{t})\|\leq t^{-\alpha}$ for some $\alpha>0$, where $G(x_{t})$ corresponds to a certain notion of gradient. Although such a gradient convergence result implies the stability of the algorithm, namely, $\lim_{t\to\infty}\|x_{t+1}-x_{t}\|=0$, it does not guarantee the convergence of the variable sequences $\{x_{t}\}_{t},\{y_{t}\}_{t}$ generated by GDA. So far, the variable convergence of GDA has not been established for nonconvex problems, but only under (strongly) convex function geometries that are mentioned previously Du and Hu, (2019); Mokhtari et al., (2020); Zhang and Wang, (2020). Therefore, we want to ask the following fundamental question:

Q1: Does GDA have guaranteed variable convergence in nonconvex minimax optimization? If so, where do they converge to?

In fact, proving the variable convergence of GDA in the nonconvex setting is highly nontrivial due to the following reasons: 1) the algorithm alternates between a minimization step and a maximization step; 2) It is well understood that strong global function geometry leads to the convergence of GDA. However, in general nonconvex setting, the objective functions typically do not have an amenable global geometry. Instead, they may satisfy different types of local geometries around the critical points. Hence, it is natural and much desired to exploit the local geometries of functions in analyzing the convergence of GDA. The Kurdyka-Łojasiewicz (KŁ) geometry provides a broad characterization of such local geometries for nonconvex functions.

The Kurdyka-Łojasiewicz (KŁ) geometry (see Section 2 for details) Bolte et al., (2007; 2014) parameterizes a broad spectrum of the local nonconvex geometries and has been shown to hold for a broad class of practical functions. Moreover, it also generalizes other global geometries such as strong convexity and PŁ geometry. In the existing literature, the KŁ geometry has been exploited extensively to analyze the convergence rate of various gradient-based algorithms in nonconvex optimization, e.g., gradient descent Attouch and Bolte, (2009); Li et al., (2017) and its accelerated version Zhou et al., (2020) as well as the distributed version Zhou et al., 2016a . Hence, we are highly motivated to study the convergence rate of variable convergence of GDA in nonconvex minimax optimization under the KŁ geometry. In particular, we want to address the following question:

Q2: How does the local function geometry captured by the KŁ parameter affects the variable convergence rate of GDA?

In this paper, we provide comprehensive answers to these questions. We develop a new analysis framework to study the variable convergence of GDA in nonconvex-strongly-concave minimax optimization under the KŁ geometry. We also characterize the convergence rates of GDA in the full spectrum of the parameterization of the KŁ geometry.

We consider the following regularized nonconvex-strongly-concave minimax optimization problem

where $f$ is a differentiable and nonconvex-strongly-concave function, $g$ is a general nonconvex regularizer and $h$ is a convex regularizer. Both $g$ and $h$ can be possibly nonsmooth. To solve the above regularized minimax problem, we study a proximal-GDA algorithm that leverages the forward-backward splitting update Lions and Mercier, (1979); Attouch et al., (2013).

We study the variable convergence property of proximal-GDA in solving the minimax problem (P). Specifically, we show that proximal-GDA admits a novel Lyapunov function $H(x,y)$ (see Proposition 2), which is monotonically decreasing along the trajectory of proximal GDA, i.e., $H(x_{t+1},y_{t+1})<H(x_{t},y_{t})$. Based on the monotonicity of this Lyapunov function, we show that every limit point of the variable sequences generated by proximal-GDA is a critical point of the objective function.

Moreover, by exploiting the ubiquitous KŁ geometry of the Lyapunov function, we prove that the entire variable sequence of proximal-GDA has a unique limit point, or equivalently speaking, it converges to a certain critical point $x^{*}$, i.e., $x_{t}\to x^{*},y_{t}\to y^{*}(x^{*})$ (see the definition of $y^{*}$ in Section 2). To the best of our knowledge, this is the first variable convergence result of GDA-type algorithms in nonconvex minimax optimization.

Furthermore, we characterize the asymptotic convergence rates of both the variable sequences and the function values of proximal-GDA in different parameterization regimes of the KŁ geometry. Depending on the value of the KŁ parameter $\theta$, we show that proximal-GDA achieves different types of convergence rates ranging from sublinear convergence up to finite-step convergence, as we summarize in Table 1 below.

2 Related work

Stochastic GDA algorithms: Lin et al., (2020); Yang et al., (2020); Boţ and Böhm, (2020) analyzed stochastic GDA, stochastic AGDA and stochastic APGDA, which are direct extensions of GDA, AGDA and APGDA to the stochastic setting respectively. Variance reduction techniques have been applied to stochastic minimax optimization, including SVRG-based Du and Hu, (2019); Yang et al., (2020), SPIDER-based Xu et al., 2020a , STORM Qiu et al., (2020) and its gradient free version Huang et al., (2020). Xie et al., (2020) studied the complexity lower bound of first-order stochastic algorithms for finite-sum minimax problem.

KŁ geometry: The KŁ geometry was defined in Bolte et al., (2007). The KŁ geometry has been exploited to study the convergence of various first-order algorithms for solving minimization problems, including gradient descent Attouch and Bolte, (2009), alternating gradient descent Bolte et al., (2014), distributed gradient descent Zhou et al., 2016a ; Zhou et al., 2018a , accelerated gradient descent Li et al., (2017). It has also been exploited to study the convergence of second-order algorithms such as Newton’s method Noll and Rondepierre, (2013); Frankel et al., (2015) and cubic regularization method Zhou et al., 2018b .

Problem Formulation and KŁ Geometry

In this section, we introduce the problem formulation, technical assumptions and the Kurdyka-Łojasiewicz (KŁ) geometry. We consider the following regularized minimax optimization problem.

Throughout the paper, we adopt the following standard assumptions on the problem (P).

Function $f(\cdot,\cdot)$ is $L$-smooth and function $f(x,\cdot)$ is $\mu$-strongly concave;

Function $h$ is proper and convex, and function $g$ is proper and lower semi-continuous.

We note that the strong concavity of $f(x,\cdot)$ in item 1 can be relaxed to concavity, provided that the regularizer $h(y)$ is $\mu$-strongly convex. In this case, we can add $-\frac{\mu}{2}\|y\|^{2}$ to both $f(x,y)$ and $h(y)$ such that 1 still holds. For simplicity, we will omit the discussion on this case.

Next, we present some important properties regarding the function $\Phi(x)$ and the mapping $y^{*}(x)$. The following proposition from Boţ and Böhm, (2020) generalizes the Lemma 4.3 of Lin et al., (2020) to the regularized setting. The proof can be found in Appendix A. Throughout, we denote $\kappa=L/\mu$ as the condition number and denote $\nabla_{1}f(x,y),\nabla_{2}f(x,y)$ as the gradients with respect to the first and the second input argument, respectively. For example, with this notation, $\nabla_{1}f(x,y^{*}(x))$ denotes the gradient of $f(x,y^{*}(x))$ with respect to only the first input argument $x$, and the $x$ in the second input argument $y^{*}(x)$ is treated as a constant.

Let 1 hold. Then, the mapping $y^{*}(x)$ and the function $\Phi(x)$ satisfy

Mapping $y^{*}(x)$ is $\kappa$-Lipschitz continuous;

Function $\Phi(x)$ is $L(1+\kappa)$-smooth with $\nabla\Phi(x)=\nabla_{1}f(x,y^{*}(x))$.

As an intuitive explanation of Proposition 1, since the function $f(x,y)-h(y)$ is $L$-smooth with respect to $x$, both the maximizer $y^{*}(x)$ and the corresponding maximum function value $\Phi(x)$ should not change substantially with regard to a small change of $x$.

Throughout, we refer to the limiting subdifferential as subdifferential. We note that subdifferential is a generalization of gradient (when $h$ is differentiable) and subgradient (when $h$ is convex) to the nonconvex setting. In particular, any local minimizer of $h$ must be a critical point.

where $\varphi^{\prime}$ is the derivative of function $\varphi:[0,\lambda)\to\mathds{R}_{+}$, which takes the form $\varphi(t)=\frac{c}{\theta}t^{\theta}$ for certain universal constant $c>0$ and KŁ parameter $\theta\in(0,1]$.

The KŁ geometry characterizes the local geometry of a nonconvex function around the set of critical points. To explain, consider the case where $h$ is a differentiable function so that $\partial h(x)=\nabla h(x)$. Then, the KŁ inequality in eq. 1 becomes $h(x)-h_{\Omega}\leq\mathcal{O}(\|\nabla h(x)\|^{\frac{1}{1-\theta}})$, which generalizes the Polyak-Łojasiewicz (PL) condition $h(x)-h_{\Omega}\leq\mathcal{O}(\|\nabla h(x)\|^{2})$ Łojasiewicz, (1963); Karimi et al., (2016) (i.e., KŁ parameter $\theta=\frac{1}{2}$). Moreover, the KŁ geometry has been shown to hold for a large class of functions including sub-analytic functions, logarithm and exponential functions and semi-algebraic functions. These function classes cover most of the nonconvex objective functions encountered in practical machine learning applications Zhou et al., 2016b ; Yue et al., (2018); Zhou and Liang, (2017); Zhou et al., 2018b .

The KŁ geometry has been exploited extensively to analyze the convergence of various first-order algorithms, e.g., gradient descent Attouch and Bolte, (2009); Li et al., (2017), alternating minimization Bolte et al., (2014) and distributed gradient methods Zhou et al., 2016a . It has also been exploited to study the convergence of second-order algorithms such cubic regularization Zhou et al., 2018b . In these works, it has been shown that the variable sequences generated by these algorithms converge to a desired critical point in nonconvex optimization, and the convergence rates critically depend on the parameterization $\theta$ of the KŁ geometry. In the subsequent sections, we provide a comprehensive understanding of the convergence and convergence rate of proximal-GDA under the KŁ geometry.

Proximal-GDA and Global Convergence Analysis

In this section, we study the following proximal-GDA algorithm that leverages the forward-backward splitting updates Lions and Mercier, (1979); Attouch et al., (2013) to solve the regularized minimax problem (P) and analyze its global convergence properties. In particular, the proximal-GDA algorithm is a generalization of the GDA Du and Hu, (2019) and projected GDA Nedić and Ozdaglar, (2009) algorithms. The algorithm update rule is specified in Algorithm 1, where the two proximal gradient steps are formally defined as

Let 1 hold and define the Lyapunov function $H(z):=\Phi(x)+g(x)+{(1-\frac{1}{4\kappa^{2}})}\|y-y^{*}(x)\|^{2}$ with $z:=(x,y)$. Choose the learning rates such that $\eta_{x}\leq\frac{1}{\kappa^{3}(L+3)^{2}}$, $\eta_{y}\leq\frac{1}{L}$. Then, the variables $z_{t}=(x_{t},y_{t})$ generated by proximal-GDA satisfy, for all $t=0,1,2,...$

We first explain how this Lyapunov function is introduced in the proof. By eq. 19 in the supplementary material, we established a recursive inequality on the objective function $(\Phi+g)(x_{t+1})$. One can see that the right hand side of eq. 19 contains a negative term $-\|x_{t+1}-x_{t}\|^{2}$ and an undesired positive term $\|y^{*}(x_{t})-y_{t}\|^{2}$. Hence, the objective function $(\Phi+g)(x_{t+1})$ may be oscillating and cannot serve as a proper Lyapunov function. In the subsequent analysis, we break this positive term into a difference of two terms $\|y^{*}(x_{t})-y_{t}\|^{2}-\|y^{*}(x_{t+1})-y_{t+1}\|^{2}$, by leveraging the update of $y_{t+1}$ for solving the strongly concave maximization problem. After proper rearranging, this difference term contributes to the quadratic term in the Lyapunov function.

We note that the Lyapunov function $H(z)$ is the objective function $\Phi(x)+g(x)$ regularized by the additional quadratic term $(1-\frac{1}{4\kappa^{2}})\|y-y^{*}(x)\|^{2}$, and such a Lyapunov function clearly characterizes our optimization goal. To elaborate, consider a desired case where the sequence $x_{t}$ converges to a certain critical point $x^{*}$ and the sequence $y_{t}$ converges to the corresponding point $y^{*}(x^{*})$. In this case, it can be seen that the Lyapunov function $H(z_{t})$ converges to the desired function value $(\Phi+g)(x^{*})$. Hence, solving the minimax problem (P) is equivalent to minimizing the Lyapunov function. More importantly, Proposition 2 shows that the Lyapunov function value sequence $\{H(z_{t})\}_{t}$ is monotonically decreasing in the optimization process of proximal-GDA, implying that the algorithm continuously makes optimization progress. We also note that the coefficient $(1-\frac{1}{4\kappa^{2}})$ in the Lyapunov function is chosen in a way so that eq. 4 can be proven to be strictly decreasing. This monotonic property is the core of our analysis of proximal-GDA.

Based on Proposition 2, we obtain the following asymptotic properties of the variable sequences generated by proximal-GDA. The proof can be found in Appendix C.

Based on Proposition 2, the sequences $\{x_{t},y_{t}\}_{t}$ generated by proximal-GDA satisfy

The above result shows that the variable sequences generated by proximal-GDA in solving the problem (P) are asymptotically stable. In particular, the last two equations show that $y_{t}$ asymptotically approaches the corresponding maximizer $y^{*}(x_{t})$ of the objective function $f(x_{t},y)+g(x_{t})-h(y)$. Hence, if $x_{t}$ converges to a certain critical point, $y_{t}$ will converge to the corresponding maximizer.

Discussion: We note that the monotonicity property in Proposition 2 further implies the convergence rate result $\min_{0\leq k\leq t}\|x_{k+1}-x_{k}\|\leq\mathcal{O}(t^{-1/2})$ (by telescoping over $t$). When there is no regularizer, this convergence rate result can be shown to further imply that $\min_{0\leq k\leq t}\|\nabla\Phi(x_{k})\|\leq\mathcal{O}(t^{-1/2})$, which reduces to the Theorem 4.4 of Lin et al., (2020). However, such a convergence rate result does not imply the convergence of the variable sequences $\{x_{t}\}_{t},\{y_{t}\}_{t}$. To explain, we can apply the convergence rate result $\|x_{t+1}-x_{t}\|\leq\mathcal{O}(t^{-1/2})$ to bound the trajectory norm as $\|x_{T}\|\leq\|x_{0}\|+\sum_{t=0}^{T-1}\|x_{t+1}-x_{t}\|\approx\sqrt{T}$, which diverges to $+\infty$ as $T\to\infty$. Therefore, such a type of convergence rate does not even imply the boundedness of the trajectory. In this paper, our focus is to establish the convergence of the variable sequences generated by proximal-GDA.

All the results in 1 imply that the alternating proximal gradient descent & ascent updates of proximal-GDA can achieve stationary points, which we show below to be critical points.

Let 1 hold and choose the learning rates $\eta_{x}\leq\frac{1}{\kappa^{3}(L+3)^{2}}$, $\eta_{y}\leq\frac{1}{L}$. Then, proximal-GDA satisfies the following properties.

The function value sequence $\{(\Phi+g)(x_{t})\}_{t}$ converges to a finite limit $H^{*}>-\infty$;

The sequences $\{x_{t}\}_{t},\{y_{t}\}_{t}$ are bounded and have compact sets of limit points. Moreover, $(\Phi+g)(x^{*})\equiv H^{*}$ for any limit point $x^{*}$ of $\{x_{t}\}_{t}$;

Every limit point of $\{x_{t}\}_{t}$ is a critical point of $(\Phi+g)(x)$.

The proof of 1 is presented in Appendix D. The above theorem establishes the global convergence property of proximal-GDA. Specifically, item 1 shows that the function value sequence $\{(\Phi+g)(x_{t})\}_{t}$ converges to a finite limit $H^{*}$, which is also the limit of the Lyapunov function sequence $\{H(z_{t})\}_{t}$. Moreover, items 2 & 3 further show that all the converging subsequences of $\{x_{t}\}_{t}$ converge to critical points of the problem, at which the function $\Phi+g$ achieves the constant value $H^{*}$. These results show that proximal-GDA can properly find critical points of the minimax problem (P). Furthermore, based on these results, the variable sequences generated by proximal-GDA are guaranteed to enter a local parameter region where the Kurdyka-Łojasiewicz geometry holds, which we exploit in the next section to establish stronger convergence results of the algorithm.

Variable Convergence of Proximal-GDA under KŁ Geometry

We note that 1 only shows that every limit point of $\{x_{t}\}_{t}$ is a critical point, and the sequences $\{x_{t},y_{t}\}_{t}$ may not necessarily be convergent. In this section, we exploit the local KŁ geometry of the Lyapunov function to formally prove the convergence of these sequences. Throughout this section, we adopt the following assumption.

Regarding the mapping $y^{*}(x)$, the function $\|y^{*}(x)-y\|^{2}$ has a non-empty subdifferential, i.e., $\partial_{x}(\|y^{*}(x)-y\|^{2})\neq\emptyset$.

Note that in many practical scenarios $y^{*}(x)$ is sub-differentiable. In addition, 2 ensures the sub-differentiability of the Lyapunov function $H(z):=\Phi(x)+g(x)+{(1-\frac{1}{4\kappa^{2}})}\|y-y^{*}(x)\|^{2}$. We obtain the following variable convergence result of proximal-GDA under the KŁ geometry. The proof is presented in Appendix E.

Let 1 & 2 hold and assume that $H$ has the KŁ geometry. Choose the learning rates $\eta_{x}\leq\frac{1}{\kappa^{3}(L+3)^{2}}$ and $\eta_{y}\leq\frac{1}{L}$. Then, the sequence $\{(x_{t},y_{t})\}_{t}$ generated by proximal-GDA converges to a certain critical point $(x^{*},y^{*}(x^{*}))$ of $(\Phi+g)(x)$, i.e.,

2 formally shows that proximal-GDA is guaranteed to converge to a certain critical point $(x^{*},y^{*}(x^{*}))$ of the minimax problem (P), provided that the Lyapunov function belongs to the large class of KŁ functions. To the best of our knowledge, this is the first variable convergence result of GDA-type algorithms in nonconvex minimax optimization. The proof logic of 2 can be summarized as the following two key steps.

Step 1: By leveraging the monotonicity property of the Lyapunov function in Proposition 2, we first show that the variable sequences of proximal-GDA eventually enter a local region where the KŁ geometry holds;

Step 2: Then, combining the KŁ inequality in eq. 1 and the monotonicity property of the Lyapunov function in eq. 4, we show that the variable sequences of proximal-GDA are Cauchy sequences and hence converge to a certain critical point.

Convergence Rate of Proximal-GDA under KŁ Geometry

In this section, we exploit the parameterization of the KŁ geometry to establish various types of asymptotic convergence rates of proximal-GDA.

We obtain the following asymptotic convergence rates of proximal-GDA under different parameter regimes of the KŁ geometry. The proof is presented in Appendix F. In the sequel, we denote $t_{0}$ as a sufficiently large positive integer, denote $c>0$ as the constant in Definition 2 and also define

Under the same conditions as those of 2, the Lyapunov function value sequence $\{H(z_{t})\}_{t}$ converges to the limit $H^{*}$ at the following rates.

If KŁ geometry holds with $\theta=1$, then $H(z_{t})\downarrow H^{*}$ within finite number of iterations;

If KŁ geometry holds with $\theta\in(\frac{1}{2},1)$, then $H(z_{t})\downarrow H^{*}$ super-linearly as

If KŁ geometry holds with $\theta=\frac{1}{2}$, then $H(z_{t})\downarrow H^{*}$ linearly as

If KŁ geometry holds with $\theta\in(0,\frac{1}{2})$, then $H(z_{t})\downarrow H^{*}$ sub-linearly as

where C=\min\Big{[}\frac{1-2\theta}{8Mc^{2}},d_{t_{0}}^{-(1-2\theta)}\big{(}1-2^{-(1-2\theta)}\big{)}\Big{]}>0.

It can be seen from the above theorem that the convergence rate of the Lyapunov function of proximal-GDA is determined by the KŁ parameter $\theta$. A larger $\theta$ implies that the local geometry of $H$ is ‘sharper’, and hence the corresponding convergence rate is orderwise faster. In particular, the algorithm converges at a linear rate when the KŁ geometry holds with $\theta=\frac{1}{2}$ (see the item 3), which is a generalization of the Polyak-Łojasiewicz (PL) geometry. As a comparison, in the existing analysis of GDA, such a linear convergence result is established under stronger geometries, e.g., convex-strongly-concave Du and Hu, (2019), strongly-convex-strongly-concave Mokhtari et al., (2020); Zhang and Wang, (2020) and two-sided PL condition Yang et al., (2020). In summary, the above theorem provides a full characterization of the fast convergence rates of proximal-GDA in the full spectrum of the KŁ geometry.

Moreover, we also obtain the following asymptotic convergence rates of the variable sequences that are generated by proximal-GDA under different parameterization of the KŁ geometry. The proof is presented in Appendix G.

Under the same conditions as those of 2, the sequences $\{x_{t},y_{t}\}_{t}$ converge to their limits $x^{*},y^{*}(x^{*})$ respectively at the following rates.

If KŁ geometry holds with $\theta=1$, then $(x_{t},y_{t})\to(x^{*},y^{*}(x^{*}))$ within finite number of iterations;

If KŁ geometry holds with $\theta\in(\frac{1}{2},1)$, then $(x_{t},y_{t})\to(x^{*},y^{*}(x^{*}))$ super-linearly as

If KŁ geometry holds with $\theta=\frac{1}{2}$, then $(x_{t},y_{t})\to(x^{*},y^{*}(x^{*}))$ linearly as

If KŁ geometry holds with $\theta\in(0,\frac{1}{2})$, then $(x_{t},y_{t})\to(x^{*},y^{*}(x^{*}))$ sub-linearly as

To the best of our knowledge, this is the first characterization of the variable convergence rates of proximal-GDA in the full spectrum of the KŁ geometry. It can be seen that, similar to the convergence rate results of the function value sequence, the convergence rate of the variable sequences is also affected by the parameterization of the KŁ geometry.

Conclusion

In this paper, we develop a new analysis framework for the proximal-GDA algorithm in nonconvex-strongly-concave optimization. Our key observation is that proximal-GDA has a intrinsic Lyapunov function that monotonically decreases in the minimax optimization process. Such a property demonstrates the stability of the algorithm. Moreover, we establish the formal variable convergence of proximal-GDA to a critical point of the objective function under the ubiquitous KŁ geometry. Our results fully characterize the impact of the parameterization of the KŁ geometry on the convergence rate of the algorithm. In the future study, we will leverage such an analysis framework to explore the convergence of stochastic GDA algorithms and their variance-reduced variants.

Acknowledgement

The work of T. Xu and Y. Liang was supported partially by the U.S. National Science Foundation under the grants CCF-1900145 and CCF-1909291.

References

Supplementary material

Appendix A Proof of Proposition 1

We first prove item 1. Since $f(x,y)$ is strongly concave in $y$ for every $x$ and $h(y)$ is convex, the mapping $y^{*}(x)=\arg\max_{y\in\mathcal{Y}}f(x,y)-h(y)$ is uniquely defined. We first show that $y^{*}(x)$ is a Lipschitz mapping. Consider two arbitrary points $x_{1},x_{2}$. The optimality conditions of $y^{*}(x_{1})$ and $y^{*}(x_{2})$ imply that

Setting $y=y^{*}(x_{2})$ in eq. 12, $y=y^{*}(x_{1})$ in eq. 13 and summing up the two inequalities, we obtain that

Since $\partial h$ is a monotone operator (by convexity), we know that $\langle u_{2}-u_{1},y^{*}(x_{2})-y^{*}(x_{1})\rangle\geq 0$. Hence, the above inequality further implies that

Next, by strong concavity of $f(x_{1},\cdot)$, we have that

Adding up the above two inequalities yields that

The above inequality shows that $\|y^{*}(x_{1})-y^{*}(x_{2})\|\leq\kappa\|x_{2}-x_{1}\|$, and item 1 is proved.

which implies that $\Phi(x)$ is $L(1+\kappa)$-smooth.

Appendix B Proof of Proposition 2

Consider the $t$-th iteration of proximal-GDA. By smoothness of $\Phi$ we obtain that

On the other hand, by the definition of the proximal gradient step of $x_{t}$, we have

Next, consider the term $\|y^{*}(x_{t})-y_{t}\|$ in the above inequality. Note that $y^{*}(x_{t})$ is the unique minimizer of the strongly concave function $f(x_{t},y)-h(y)$, and $y_{t+1}$ is obtained by applying one proximal gradient step on it starting from $y_{t}$. Hence, by the convergence rate of proximal gradient ascent algorithm under strong concavity, we conclude that with $\eta_{y}\leq\frac{1}{L}$,

Rearranging the equation above and recalling the definition of the Lyapunov function H(z):=\Phi(x)+g(x)+\Big{(}1-\frac{1}{4\kappa^{2}}\Big{)}\|y-y^{*}(x)\|^{2}, we have

When $\eta_{x}<\kappa^{-3}(L+3)^{-2}$, using $\kappa\geq 1$ yields that

As a result, eq. (4) can be concluded by substituting eq. (23) into eq. (22).

Appendix C Proof of 1

To prove the first and third items of 1, summing the inequality of Proposition 2 over $t=0,1,...,T-1$, we obtain that for all $T\geq 1$,

Therefore, we must have $\lim_{t\to\infty}\|x_{t+1}-x_{t}\|={\lim_{t\to\infty}\|y_{t}-y^{*}(x_{t})\|=}0$.

Appendix D Proof of 1

We first show that $\{(\Phi+g)(x_{t})\}_{t}$ has a finite limit. We have shown in Proposition 2 that $\{H(z_{t})\}_{t}$ is monotonically decreasing. Since $H(z)$ is bounded below, we conclude that $\{H(z_{t})\}_{t}$ has a finite limit $H^{*}>-\infty$, i.e., \lim_{t\to\infty}(\Phi+g)(x_{t})+{\Big{(}1-\frac{1}{4\kappa^{2}}\Big{)}}\|y_{t}-y^{*}(x_{t})\|^{2}=H^{*}. Moreover, since $\|y_{t}-y^{*}(x_{t})\|\overset{t}{\to}0$, we further conclude that $\lim_{t\to\infty}(\Phi+g)(x_{t})=H^{*}$.

Next, we prove the second item. Since $\{H(z_{t})\}_{t}$ is monotonically decreasing and $H(z)$ has compact sub-level set, we conclude that $\{x_{t}\}_{t},\{y_{t}\}_{t}$ are bounded and hence have compact sets of limit points. Next, we derive a bound on the subdifferential. By the optimality condition of the proximal gradient update of $x_{t}$ and the summation rule of subdifferential in Corollary 1.12.2 of Kruger, (2003), we have

Now consider any limit point $x^{*}$ of $x_{t}$ so that $x_{t(j)}\overset{j}{\to}x^{*}$ along a subsequence. By the proximal update of $x_{t(j)}$, we have

Taking limsup on both sides of the above inequality and noting that $\{x_{t}\}_{t},\{y_{t}\}_{t}$ are bounded, $\nabla f$ is Lipschitz, $\|x_{t+1}-x_{t}\|\overset{t}{\to}0$ and $x_{t(j)}\to x^{*}$, we conclude that $\lim\sup_{j}g(x_{t(j)})\leq g(x^{*})$. Since $g$ is lower-semicontinuous, we know that $\lim\inf_{j}g(x_{t(j)})\geq g(x^{*})$. Combining these two inequalities yields that $\lim_{j}g(x_{t(j)})=g(x^{*})$. By continuity of $\Phi$, we further conclude that $\lim_{j}(\Phi+g)(x_{t(j)})=(\Phi+g)(x^{*})$. Since we have shown that the entire sequence $\{(\Phi+g)(x_{t})\}_{t}$ converges to a certain finite limit $H^{*}$, we conclude that $(\Phi+g)(x^{*})\equiv H^{*}$ for all the limit points $x^{*}$ of $\{x_{t}\}_{t}$.

Next, we prove the third item. To this end, we have shown that for every subsequence $x_{t(j)}\overset{j}{\to}x^{*}$, we have that $(\Phi+g)(x_{t(j)})\overset{j}{\to}(\Phi+g)(x^{*})$ and there exists $u_{t}\in\partial(\Phi+g)(x_{t})$ such that $u_{t}\overset{t}{\to}\mathbf{0}$ (by eq. 25). Recall the definition of limiting sub-differential, we conclude that every limit point $x^{*}$ of $\{x_{t}\}_{t}$ is a critical point of $(\Phi+g)(x)$, i.e., $\mathbf{0}\in\partial(\Phi+g)(x^{*})$.

Appendix E Proof of 2

We first derive a bound on $\partial H(z)$. Recall that H(z)=\Phi(x)+g(x)+{\Big{(}1-\frac{1}{4\kappa^{2}}\Big{)}}\|y-y^{*}(x)\|^{2}, and that $\|y^{*}(x)-y\|^{2}$ has non-empty subdifferential $\partial_{x}(\|y^{*}(x)-y\|^{2})$. We therefore have

where the first inclusion follows from the scalar multiplication rule and sum rule of sub-differential, see Proposition 1.11 & 1.12 of Kruger, (2003). Next, we derive upper bounds on these sub-differentials. Based on Definition 1, we can take any $u\in\widehat{\partial}_{x}(\|y^{*}(x)-y\|^{2})$ and obtain that

where (i) and (ii) use the fact that $y^{*}$ is $\kappa$-Lipschitz based on Proposition 1, and the limsup in (iii) is achieved by letting $z=x+\sigma u$ with $\sigma\to 0^{+}$ in (ii). Hence, we conclude that $\|u\|\leq 2\kappa\|y^{*}(x)-y\|$. Since $\partial_{x}(\|y^{*}(x)-y\|^{2})$ is the graphical closure of $\widehat{\partial}_{x}(\|y^{*}(x)-y\|^{2})$, we have that

Then, utilizing the characterization of $\partial(\Phi+g)(x)$ in eq. 24, we obtain that

where (i) uses Proposition 1 that $\nabla\Phi(x_{t+1})=\nabla_{1}f(x_{t+1},y^{*}(x_{t+1}))$ and that $y^{*}$ is $\kappa$-Lipschitz, (ii) uses eq. 21 and the inequality that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}~{}(a,b\geq 0)$ and (iii) uses $\kappa\geq 1$.

Rearranging the above inequality and utilizing eq. 27, we obtain that for all $t\geq t_{0}$,

By concavity of the function $\varphi$ (see Definition 2), we know that

where (i) uses Proposition 2 and eq. 28, (ii) uses the inequality that $a^{2}+b^{2}\geq\frac{1}{2}(a+b)^{2}$.

where the final step uses the inequality that $2ab\leq(Ca+\frac{b}{C})^{2}$ for any $a,b\geq 0$ and $C>0$ (the value of $C$ will be assigned later). Taking square root of both sides of the above inequality and telescoping over $t=t_{0},\ldots,T-1$, we obtain that

where the final steps uses $\varphi(s)=\frac{c}{\theta}s^{\theta}$ and the fact that $H(z_{T})-H^{*}\geq 0$. Since the value of $C>0$ is arbitrary, we can select large enough $C$ such that \frac{1}{C}\Big{(}\frac{1}{\eta_{x}}+(L+4\kappa)^{2}(1+\kappa)\Big{)}<\frac{1}{2} and $\frac{1}{C}(L+4\kappa)<\frac{1}{2\kappa}$. Hence, the inequality above further implies that

Moreover, this implies that $\{x_{t}\}_{t}$ is a Cauchy sequence and therefore converges to a certain limit, i.e., $x_{t}\overset{t}{\to}x^{*}$. We have shown in 1 that any such limit point must be a critical point of $\Phi+g$. Hence, we conclude that $\{x_{t}\}_{t}$ converges to a certain critical point $x^{*}$ of $(\Phi+g)(x)$. Also, note that $\|y^{*}(x_{t})-y_{t}\|\overset{t}{\to}0$, $x_{t}\overset{t}{\to}x^{*}$ and $y^{*}$ is a Lipschitz mapping, so we conclude that $\{y_{t}\}_{t}$ converges to $y^{*}(x^{*})$.

Appendix F Proof of 3

Recall that we have shown that for all $t\geq t_{0}$, the KŁ property holds and we have

Throughout the rest of the proof, we assume $t\geq t_{0}$. Substituting eq. 30 into the above bound yields that

where the second inequality uses the definition of $M$ in eq. 5.

Substituting eq. 4 and $\varphi^{\prime}(s)=cs^{\theta-1}$ ($c>0$) into eq. (31) and rearranging, we further obtain that

Defining $d_{t}=H(z_{t})-H^{*}$, the above inequality further becomes

Next, we prove the convergence rates case by case.

(Case 1) If $\theta=1$, then eq. 32 implies that $d_{t-1}-d_{t}\geq\frac{1}{2Mc^{2}}>0$ whenever $d_{t}>0$. Hence, $d_{t}$ achieves 0 (i.e., $H(z_{t})$ achieves $H^{*}$) within finite number of iterations.

(Case 2) If $\theta\in(\frac{1}{2},1)$, since $d_{t}\geq 0$, eq. (32) implies that

Note that $\theta\in(\frac{1}{2},1)$ implies that $\frac{1}{2(1-\theta)}>1$, and thus the inequality above implies that $H(z_{t})\downarrow H^{*}$ at the super-linear rate given by eq. (6).

which implies that d_{t}\leq\Big{(}1+{\frac{1}{2Mc^{2}}}\Big{)}^{-1}d_{t-1}. Therefore, $d_{t}\downarrow 0$ (i.e., $H(z_{t})\downarrow H^{*}$) at the linear rate given by eq. (7).

(Case 4) If $\theta\in(0,\frac{1}{2})$, consider the following two subcases.

If $d_{t-1}\leq 2d_{t}$, denote $\psi(s)=\frac{1}{1-2\theta}s^{-(1-2\theta)}$, then

where (i) uses $d_{t}\leq d_{t-1}$ and $-2(1-\theta)<-1$, and (ii) uses eq. (32).

where we use $-(1-2\theta)<0$, $d_{t-1}>2d_{t}$ and $d_{t}\leq d_{t_{0}}$.

By substituing the definition of $\psi$, the inequality above implies that $H(z_{t})\downarrow H^{*}$ in a sub-linear rate given by eq. (8). ∎

Appendix G Proof of 4

(Case 1) If $\theta=1$, then based on the first case of Appendix F, $H(z_{t})\equiv H^{*}$ after finite number of iterations. Hence, for large enough $t$, Proposition 2 yields that

which implies that $x_{t+1}=x_{t}$ and $y_{t}=y^{*}(x_{t})$ for large enougth $t$. Hence, $x_{t}\to x^{*}$ and $y_{t}\to y^{*}(x^{*})$ within finite number of iterations.

(Case 2) If $\theta\in(\frac{1}{2},1)$, denote $A_{t}=\|x_{t+1}-x_{t}\|+\frac{1}{2\kappa}\|y_{t}-y^{*}(x_{t})\|$. Then, based on the definition of $M$ in eq. 5, we have

Hence, eqs. (28) & (40) and $\varphi^{\prime}(s)=cs^{\theta-1}$ imply that

Using the inequality that $a^{2}+b^{2}\geq\frac{1}{2}(a+b)^{2}$ and recalling the definition of $A_{t}$ and $\varphi(s)=\frac{c}{\theta}s^{\theta}$, the above inequality further implies that

Substituting eq. 41 into eq. 42 and using $H(z_{t+1})-H^{*}\geq 0$ yield that

Note that eq. 43 holds for $t\geq t_{0}$. Since $A_{t}\to 0$, there exists $t_{1}\geq t_{0}$ such that $C_{1}A_{t_{1}}\leq e^{-1}$. Hence, by iterating eq. 43 from $t=t_{1}+1$, we obtain

where (i) uses the inequalities that $\frac{1}{2(1-\theta)}>1$ and that $s\geq t\geq t_{1}+1$, and (ii) uses the fact that \sum_{s=0}^{\infty}\exp\Big{[}1-\Big{(}\frac{1}{2(1-\theta)}\Big{)}^{s}\Big{]}<+\infty is a positive constant independent from $t$. Therefore, the convergence rate (9) can be directly derived as follows

where (i) uses the Lipschitz property of $y^{*}$ in Proposition 1, and (ii) uses eqs. (44) & (45).

(Case 3 & 4) Notice that eq. 42 still holds if \theta\in\big{(}0,\frac{1}{2}\big{]}. Hence, if $A_{t}\geq\frac{1}{2}A_{t-1}$, then eq. 42 implies that

Otherwise, $A_{t}\leq\frac{1}{2}A_{t-1}$. Combining these two inequalities yields that

Notice that the inequality above holds whenever $t\geq t_{0}$. Hence, telescoping the inequality above yields

which along with $A_{T}\geq 0$, $H(z_{T+1})-H^{*}\geq 0$ implies that

Letting $t=t_{0}$ and $T\to\infty$ in the above inequality yields that $\sum_{s=t_{0}}^{\infty}A_{s}<+\infty$. Hence, by letting $T\to\infty$ and denoting $S_{t}=\sum_{s=t}^{\infty}A_{s}$ in eq. 46, we obtain that

(Case 3) If $\theta=1/2$, eq. 7 holds. Substituting eq. 7 and $\theta=1/2$ into eq. 47 yields that

is a positive constant independent of $t$.

Notice that when $\frac{1}{4}+\frac{1}{8Mc^{2}}\geq 1$,

and when $\frac{1}{4}+\frac{1}{8Mc^{2}}<1$,

Since either of the two above inequalities holds, combining them yields that

Substituing the above inequality into eq. 48 yields that

The two above inequalities yield the linear convergence rate (10).

(Case 4) If $\theta\in(0,\frac{1}{2})$, then eq. 8 holds. Substituting eq. 8 into eq. 47 yields that for some constant $C_{3}>0$,

where (i) denotes $t_{1}=\lfloor(t-t_{0})/2\rfloor$, (ii) uses the inequality that $\sum_{s=t_{1}+1}^{t-t_{0}}2^{s}<\sum_{s=0}^{t-t_{0}}2^{s}<2^{t-t_{0}+1}$. Therefore, the sub-linear convergence rate eq. 11 follows from the following inequalities.