# Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for
Solving Nonconvex Min-Max Problems

Thinh T. Doan Thinh T. Doan is with the Bradley Department of Electrical and
Computer Engineering, Virginia Tech, USA. Email<EMAIL_ADDRESS>
###### Abstract

There are much recent interests in solving noncovnex min-max optimization
problems due to its broad applications in many areas including machine
learning, networked resource allocations, and distributed optimization.
Perhaps, the most popular first-order method in solving min-max optimization
is the so-called simultaneous (or single-loop) gradient descent-ascent
algorithm due to its simplicity in implementation. However, theoretical
guarantees on the convergence of this algorithm is very sparse since it can
diverge even in a simple bilinear problem.

In this paper, our focus is to characterize the finite-time performance (or
convergence rates) of the continuous-time variant of simultaneous gradient
descent-ascent algorithm. In particular, we derive the rates of convergence of
this method under a number of different conditions on the underlying objective
function, namely, two-sided Polyak-Łojasiewicz (PŁ), one-sided PŁ, nonconvex-
strongly concave, and strongly convex-nonconcave conditions. Our convergence
results improve the ones in prior works under the same conditions of objective
functions. The key idea in our analysis is to use the classic singular
perturbation theory and coupling Lyapunov functions to address the time-scale
difference and interactions between the gradient descent and ascent dynamics.
Our results on the behavior of continuous-time algorithm may be used to
enhance the convergence properties of its discrete-time counterpart.

##  1 Introduction

In this paper, we consider the following min-max optimization problems

$\displaystyle\min_{x\in\mathbb{R}^{m}}\max_{y\in\mathbb{R}^{n}}f(x,y),$ (1)

where $f:\mathbb{R}^{m}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a
nonconvex function w.r.t $x$ for a fixed $y$ and (possibly) nonconcave w.r.t
$y$ for a fixed $x$. The min-max problem has received much interests for years
due to its broad applications in different areas including control, machine
learning, and economics. In particular, many problems in these areas can be
formulated as problem (1), for example, game theory [1, 2], stochastic control
and reinforcement learning [3, 4], training generative adversarial networks
(GANs) [5, 6], adversarial and robust machine learning [7, 8], resource
allocation over networks [9], and distributed optimization [10, 11]; to name
just a few.

In the existing literature, there are two types of iterative first-order
methods for solving problem (1), namely, nested-loop algorithms and single-
loop algorithms. Nested-loop algorithms implement multiple inner steps in each
iteration to solve the maximization problem either exactly or approximately.
However, this approach is not applicable to the setting when $f(x,y)$ is
nonconcave in $y$, since the maximization problem is NP-hard. Only finding a
stationary point of the maximization problem is likely to affect the quality
of solving the minimization problem.

On the other hand, single-loop algorithm simultaneously updates the iterates
$x$ and $y$ by using the vanilla gradient descent and ascent steps at
different time scales, respectively. As a result, this algorithm is applicable
to more general settings and more practical due to its simplicity in
implementation. However, single-loop algorithms may not converge in many
settings, for example, they fail to converge even in a simple bilinear zero-
sum game [12]. Indeed, theoretical guarantees of these methods are very
sparse.

Our focus in this paper is to study the continuous-time variant of the single-
loop gradient descent-ascent method for solving problem (1). Considering the
continuous-time variant will help us to have a better understanding about the
behavior of this method through studying the convergence of the corresponding
differential equations using Lyapunov theory. Such an understanding can then
be used to enhance the analysis of the discrete-time algorithms, as recently
observed in the single objective optimization counterpart [13, 14, 15, 16].
Our main contributions are summarized below.

Main Contributions. The focus of this paper is to study the performance of the
continuous-time gradient descent-ascent dynamics in solving nonconvex min-max
optimization problems. In particular, we derive the rates of convergence of
this method under a number of different conditions on the underlying objective
function, namely, two-sided Polyak-Łojasiewicz (PŁ), one-sided PŁ, nonconvex-
strongly concave, and strongly convex-nonconcave conditions. These rates are
summarized in Table 1 and presented in detail in Section 3, where we show that
our results improve the ones in prior works under the same conditions of
objective functions. The key idea in our analysis is to use the classic
singular perturbation theory and coupling Lyapunov function of the fast and
slow dynamics to address the time-scale difference and interactions between
the gradient descent and ascent dynamics. Proper choices of step sizes allows
us to derive improved convergence properties of the two-time-scale gradient
descent-ascent dynamics.

###  1.1 Related Works

#### Convex-Concave Settings.

Given the broad applications of problem (1), there are a large number of works
to study algorithms and their convergence in solving this problem, especially
in the context of convex-concave settings. Some examples include prox-method
and its variant [17, 18, 19, 20, 21], extragradient and optimistic gradient
methods [22, 23, 24, 25, 26, 27], and recently Hamiltonian gradient descent
methods [6, 12, 28]. Some algorithms in these settings have convergence rates
matched with the lower bound complexity; see the recent work [26] for a
detailed discussion.

#### Nonconvex-Concave Settings.

Unlike the convex-concave settings, algorithmic development and theoretical
understanding in the general nonconvex settings are very limited. Indeed,
finding the global optimality of nonconvex-nonconcave problem is NP-hard, or
at least as hard as solving a single nonconvex objective problem. As a result,
the existing literature often aims to find a stationary point of $f$ when the
max problem is concave. For example, multiple-loop algorithms have been
studied in [29, 30, 31, 32, 33]. Our work in this paper is closely related to
the recent literature on studying single-loop algorithm [34, 35, 36, 37, 38].
While these works study discrete-time algorithms, we consider continuous-time
counterpart. We will show that for some settings, our approach improves the
existing convergence results.

#### Other Settings.

We also want to mention some related literature in game theory [39, 40, 41,
42, 43], two-time-scale stochastic approximation [44, 45, 46, 47, 48, 49, 50,
51, 52, 53], reinforcement learning [54, 55, 56, 57, 58], two-time-scale
optimization [59, 60], and decentralized optimization [61, 62, 63, 64, 65, 66,
67]. These works study different variants of two-time-scale methods mostly for
solving a single optimization problem, and often aim to find global optimality
(or fixed points) using different structure of the underlying problems (e.g.,
Markov structure in stochastic games and reinforcement learning or strong
monotonicity in stochastic approximation). As a result, their techniques may
not be applicable to the context of problem (1) considered in the current
paper.

Notation. Given any vector $x$ we use $\|x\|$ to denote its $2$-norm. We
denote by $\nabla_{x}f(x,y)$ and $\nabla_{y}f(x,y)$ the partial gradients of
$f$ with respect to $x$ and $y$, respectively.

##  2 Two-Time-Scale Gradient Descent-Ascent Dynamics

For solving problem (1), we are interested in studying two-time-scale gradient
descent-ascent dynamics (GDAD), where we implement simultaneously the
following two differential equations

$\displaystyle\begin{aligned}
\dot{x}(t)&=\frac{d}{dt}x(t)=-\alpha\nabla_{x}f(x(t),y(t)),\\\
\dot{y}(t)&=\frac{d}{dt}y(t)=\beta\nabla_{y}f(x(t),y(t)),\end{aligned}$ (2)

Here, $\alpha,\beta$ are two step sizes, whose values will be specified later.
In the convex-concave setting, one can choose $\alpha=\beta$. However, as
observed in [68], choosing different step sizes achieves a better convergence
in the context of nonconvex problem. Indeed, we will choose $\alpha\ll\beta$
since in our settings studied in the following sections, the maximization
problem is often easier to solve than the minimization problem. In this case,
the dynamic of $y(t)$ is implemented at a faster time scale (using larger step
sizes) than $x(t)$ (using smaller step sizes). The time-scale difference is
loosely defined as the ratio $\alpha/\beta\ll 1$. Thus, one has to design
these two step sizes properly so that the method converges as fast as
possible.

Technical Approach. The convergence analysis of (2) studied in this paper is
mainly motivated by the classic singular perturbation theory [69]. The main
idea of our approach can be explained as follows. Since $y$ is implemented at
a faster time scale than $x$, one can consider $x(t)=x$ being fixed in
$\dot{y}$ and separately study the stability of the system $\dot{y}$ using
Lyapunov theory. Let $V_{2}$ be the Lyapunov function corresponding to
$\dot{y}$. When $\dot{y}$ converges to an equilibrium $y$ (e.g.,
$\nabla_{y}f(x,y)=0$), one can fix $y(t)=y$ and study the stability of
$\dot{x}$. Let $V_{1}$ be the corresponding Lyapunov function of $\dot{x}$. We
note that $V_{1}$ and $V_{2}$ both depend on $x$ and $y$, as a result, their
time derivatives are coupled through the dynamics in (2). Addressing this
coupling and the time-scale difference between the two dynamics is the key
idea in our approach. To do that, we will consider the following Lyapunov
function

$\displaystyle V(x,y)=V_{1}(x,y)+\frac{\gamma\alpha}{\beta}V_{2}(x,y),$ (3)

where $\alpha/\beta$ represents the time-scale difference, while the constant
$\gamma$ will be properly chosen to eliminate the impact of $x$ on the
convergence of $y$ and vice versa. Proper choices of these constants will also
help us to derive the convergence rates of (2). Similar approach has been used
in different settings of two-time-scale methods, see for example [53, 66].

We conclude this section by introducing two assumptions for our analysis
studied later.

######  Assumption 1.

The function $f(\cdot,\cdot)$ has Lipschitz continuous gradients for each
variable, i.e., there exist positive constants $L_{x}$, $L_{y}$, and $L_{xy}$
such that for all $x_{1},x_{2}\in\mathbb{R}^{m},y_{1},y_{2}\in\mathbb{R}^{n}$
we have

$\displaystyle\begin{aligned}
\|\nabla_{x}f(x_{1},y_{1})-\nabla_{x}f(x_{2},y_{2})\|&\leq
L_{x}\|x_{1}-x_{2}\|+L_{xy}\|y_{1}-y_{2}\|,\\\
\|\nabla_{y}f(x_{1},y_{1})-\nabla_{y}f(x_{2},y_{2})\|&\leq
L_{xy}\|x_{1}-x_{2}\|+L_{y}\|y_{1}-y_{2}\|.\end{aligned}$ (4)

######  Assumption 2.

Given any $x$ the problem $\max_{y}f(x,y)$ has a nonempty solution set ${\cal
Y}^{\star}(x)$, i.e., there exists $y^{\star}(x)\in{\cal Y}^{\star}(x)$ such
that

$\displaystyle
y^{\star}(x)=\arg\max_{y\in\mathbb{R}^{n}}f(x,y),\quad\text{where
}f(x,y^{\star}(x))\text{ is finite}.$

Table 1: Convergence rates of GDAD for solving (1) given some accuracy $\epsilon>0$. The abbreviations NCvex, NCave, SCvex, SCave, and PŁ stand for nonconvex, nonconcave, strongly convex, strongly concave, and Polyak-Łojasiewicz condtions, respectively. Condition number $\kappa$ is defined in (11), and $R$ is the size of compact set used in [33]. Objectives | Prior Works | This Paper
---|---|---
PŁ& PŁ |  ${\cal O}\left(\kappa^{3}\log(\frac{1}{\epsilon})\right)$ [36] | ${\cal O}\left(\kappa^{2}\log(\frac{1}{\epsilon}\right)$
NCvex & PŁ |  ${\cal O}\left(R^{2}L_{xy}\log(\frac{1}{\epsilon})\epsilon^{-2}\right)$ [33] | ${\cal O}\left(L_{xy}^{2}\epsilon^{-2}\right)$
NCvex & SCave |  ${\cal O}\left(L_{xy}^{2}\epsilon^{-2}\right)$ [37] | ${\cal O}\left(L_{xy}^{2}\epsilon^{-2}\right)$
SCvex & NCave |  ${\cal O}\left(L_{xy}^{2}\epsilon^{-2}\right)$ [37] | ${\cal O}\left(L_{xy}^{2}\epsilon^{-2}\right)$

##  3 Main Results

In this section, we present the main results of this paper, where we derive
the convergence rates of GDAD under different conditions on the objective
function $f(x,y)$. Our results are summarized in Table 1. First, our approach
improves the analysis in [36], where we show in Section 3.1 that for two-sided
PŁ functions the convergence of GDAD only scales with $\kappa^{2}$ instead of
$\kappa^{3}$ studied in [36]. Our result addresses the conjecture raised in
[36], where the authors state that such an improvement may not be possible.
Second, our analysis achieves a better result than the one in [33] for the
case of one-sided PL function by a factor of $\log(1/\epsilon)$. We note that
a nested-loop is studied in [33] while GDAD is a single-loop method. Finally,
our result is the same as the one in [37] when $f(x,y)$ is either strongly
concave in $y$ for fixed $x$. In Section 3.4, we will show that this
observation also holds when $f(x,y)$ is either strongly convex in $x$ and
nonconcave in $y$. Note that as compared to the analysis in [37], we use a
simpler analysis and simpler choice of step sizes to achieve these results.

###  3.1 Two-Sided Polyak–Łojasiewicz Conditions

We first study the convergence rates of GDAD when $f$ satisfies a two-sided
Polyak–Łojasiewicz (PŁ) condition, which is considered in [36] and stated here
for convenience.

######  Definition 1 (Two-Sided PŁ Conditions).

A continuously differentiable function
$f:\mathbb{R}^{m}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is called to
satisfy two-sided PŁ conditions if there exist two positive constants
$\mu_{x}$ and $\mu_{y}$ such that
$\mu_{x},\mu_{y}\leq\min\\{L_{x},L_{y},L_{xy}\\}$ the following conditions
hold for all $(x,y)\in\mathbb{R}^{m}\times\mathbb{R}^{n}$:

$\displaystyle\begin{aligned}
2\mu_{x}[f(x,y)-\min_{x}f(x,y)]&\leq\|\nabla_{x}f(x,y)\|^{2},\\\
2\mu_{y}[\max_{y}f(x,y)-f(x,y)]&\leq\|\nabla_{y}f(x,y)\|^{2}.\end{aligned}$
(5)

The two-sided PŁ condition, which we will assume to hold in this subsection,
is a generalized variant of the popular PŁ condition, proposed by [70] as a
sufficient condition to guarantee that the classic gradient descent method
converges exponentially to the optimal value of an unconstrained minimization
problem. As shown in [71], the PŁ condition also implies the quadratic growth
condition, i.e., given any $x$ we have

$\displaystyle\max_{z\in\mathbb{R}^{m}}f(x,z)-f(x,y)\geq\frac{\mu_{y}}{2}\|{\cal
P}_{{\cal Y}^{\star}(x)}[y]-y\|^{2},\quad\forall y\in\mathbb{R}^{m},$ (6)

where we assume that ${\cal Y}^{\star}(x)$ is a nonempty solution set of
$\max_{y}f(x,y)$ and ${\cal P}_{{\cal Y}^{\star}(x)}[y]$ is the projection of
$y$ to this set. More discussions on PŁ condition can be found in [71], while
some examples of functions satisfying the two-sided PŁ condition are given in
[36].

Our focus in this section is to show that GDAD converges exponentially to the
global min-max solution $(x^{\star},y^{\star})$ of $f$ under the two-sided PŁ
condition. To do that, we consider the following assumption and lemmas, which
are useful for our analysis considered later. We first consider an assumption
on the existence of $(x^{\star},y^{\star})$, a global min-max solution of $f$.

######  Assumption 3.

There exists a global min-max solution $(x^{\star},y^{\star})$ of $f$, i.e.,

$\displaystyle
x^{\star}=\arg\min_{x\in\mathbb{R}^{m}}f(x,y^{\star})\quad\text{and}\quad
y^{\star}=\arg\max_{y\in\mathbb{R}^{n}}f(x^{\star},y).$

Next, we consider the following lemma about the Lipschitz continuity of the
gradient of $f(x,y^{\star}(x))$, which is a variant of the well-known Danskin
lemma [72][Proposition B.25] and studied in [33][Lemma A.5].

######  Lemma 1.

Suppose that Assumptions 1– 3 hold. Then, the function $\max_{y}f(x,y)$ is
differentiable and its gradient $\nabla_{x}f(x,y^{\star}(x))$ is Lipschitz
continuous with a constant $L_{x}+\frac{L_{xy}}{\mu_{y}}$.

Finally, for our analysis we consider the following two Lyapunov functions

$\displaystyle V_{1}(x)$
$\displaystyle=\max_{y\in\mathbb{R}^{n}}f(x,y)-\min_{x\in\mathbb{R}^{m}}\max_{y\in\mathbb{R}^{n}}f(x,y),$
(7) $\displaystyle V_{2}(x,y)$ $\displaystyle=\max_{y}f(x,y)-f(x,y),$ (8)

where it is obvious to see that $V_{1}$ and $V_{2}$ are nonnegative. The time
derivatives of $V_{1}$ and $V_{2}$ over the trajectories $\dot{x}$ and
$\dot{y}$ are given in the following lemma, whose proof can be found in
Section 4.1.

######  Lemma 2.

Suppose that Assumptions 1– 3 hold. Then we have

$\displaystyle\dot{V}_{1}(x)$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{L_{xy}^{2}\alpha}{\mu_{y}}V_{2}(x,y).$
(9) $\displaystyle\dot{V}_{2}(x,y)$
$\displaystyle\leq-\beta\|\nabla_{y}f(x,y)\|^{2}+\frac{3\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{5L_{xy}^{2}\alpha}{\mu_{y}}V_{2}(x,y).$
(10)

As mentioned, the dynamics of $\dot{x}$ and $\dot{y}$ are implemented at
different time scales, where this difference is often loosely defined as the
ratio $\beta/\alpha>1$. To capture such time-scale difference in our analysis,
we will utilize the coupling Lyapunov function defined in (3). We denote by
$\mu=\min\\{\mu_{x},\mu_{y}\\}$ and the condition number

$\displaystyle\kappa=\frac{L_{xy}}{\mu}\geq 1.$ (11)

representing the condition number of $f(x,y)$. The convergence rate of GDAD
under the two-sided PŁ condition is formally stated in the following theorem.

######  Theorem 1.

Suppose that Assumptions 1– 3 hold. Let $\gamma,\alpha,\beta$ be chosen as

$\displaystyle\gamma=\frac{L_{xy}^{2}}{\mu_{y}^{2}},\quad\alpha=\frac{\mu^{2}}{10\mu_{x}L_{xy}^{2}},\quad\beta=\frac{\mu^{2}}{\mu_{x}\mu_{y}^{2}}\cdot$
(12)

Then we have for all $t\geq 0$

$\displaystyle V(x(t),y(t))\leq e^{-\frac{t}{20\kappa^{2}}}V(x(0),y(0)).$ (13)

###### Proof.

By (5) we have

$\displaystyle\|\nabla_{y}f(x,y)\|^{2}\geq
2\mu_{y}[\max_{y}f(x,y)-f(x,y)]=2\mu_{y}V_{2}(x,y).$

Thus, by using (9), (10), (3), and the preceding relation we have

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle=\dot{V}_{1}(x(t))+\frac{\gamma\alpha}{\beta}\dot{V}_{2}(x(t),y(t))$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y^{\star}(x(t)))\|^{2}+\frac{L_{xy}^{2}\alpha}{\mu_{y}}V_{2}(x(t),y(t))$
$\displaystyle\quad-2\mu_{y}\gamma\alpha
V_{2}(x(t),y(t))+\frac{3\gamma\alpha^{2}}{2\beta}\|\nabla_{x}f(x(t),y^{\star}(x(t)))\|^{2}+\frac{5L_{xy}^{2}\gamma\alpha^{2}}{\mu_{y}\beta}V_{2}(x(t),y(t))$
$\displaystyle=-\frac{\alpha}{4}\|\nabla_{x}f(x(t),y^{\star}(x(t)))\|^{2}-\frac{\mu_{y}\gamma\alpha}{2}V_{2}(x(t),y(t))$
$\displaystyle\quad-\left(\frac{1}{2}-\frac{3\gamma\alpha}{\beta}\right)\frac{\alpha}{2}\|\nabla_{x}f(x(t),y^{\star}(x(t)))\|^{2}$
$\displaystyle\quad-\left(\frac{3\mu_{y}\gamma}{2}-\frac{L_{xy}^{2}}{\mu_{y}}-\frac{5L_{xy}^{2}\gamma\alpha}{\mu_{y}\beta}\right)\alpha
V_{2}(x(t),y(t)).$ (14)

Using (12) we have

$\displaystyle\frac{1}{2}-\frac{3\gamma\alpha}{\beta}=\frac{1}{2}-\frac{3L_{xy}^{2}}{\mu_{y}^{2}}\frac{\mu^{2}}{10\mu_{x}L^{2}_{xy}}\frac{\mu_{x}\mu_{y}^{2}}{\mu^{2}}=\frac{1}{5},$
$\displaystyle\frac{3\mu_{y}\gamma}{2}-\frac{L_{xy}^{2}}{\mu_{y}}-\frac{5L_{xy}^{2}\gamma\alpha}{\mu_{y}\beta}=\frac{L_{xy}^{2}}{2\mu_{y}}-\frac{L_{xy}^{2}}{2\mu_{y}}=0,$

which when substituting into (14) and using (5) and
$y^{\star}(x)=\arg\max_{y}f(x,y)$ we obtain

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle\leq-\frac{\alpha}{4}\|\nabla_{x}f(x(t),y^{\star}(x(t)))\|^{2}-\frac{\mu_{y}\gamma\alpha}{2}V_{2}(x(t),y(t))$
$\displaystyle\leq-\frac{\mu_{x}\alpha}{2}\Big{[}\max_{y}f(x(t),y)-\min_{x}f(x,y^{\star}(x(t)))\Big{]}-\frac{\mu_{y}\gamma\alpha}{2}V_{2}(x,y)$
$\displaystyle\leq-\frac{\mu_{x}\alpha}{2}(\max_{y}f(x(t),y)-\min_{x}\max_{y}f(x,y))-\frac{\mu_{y}\gamma\alpha}{2}V_{2}(x,y)$
$\displaystyle=-\frac{\mu_{x}\alpha}{2}V_{1}(x(t))-\frac{\mu_{y}\beta}{2}\frac{\gamma\alpha}{\beta}V_{2}(x,y)$
$\displaystyle\leq-\frac{\mu_{x}\alpha}{2}(V_{1}(x(t))+\frac{\gamma\alpha}{\beta}V_{2}(x(t),y(t)))=-\frac{\mu_{x}\alpha}{2}V(x(t),y(t)),$

where the last inequality is due to

$\displaystyle\mu_{x}\alpha=\frac{\mu^{2}}{10L_{xy}^{2}}\leq\mu_{y}\beta=\frac{\mu^{2}}{\mu_{x}\mu_{y}}\cdot$

Taking the integral on both sides of the equation above immediately gives
(13), i.e.,

$\displaystyle V(x(t),y(t))\leq e^{-\frac{\mu_{x}\alpha
t}{2}}V(x(0),y(0))=e^{-\frac{t}{20\kappa^{2}}}V(x(0),y(0)).$

∎

###  3.2 Nonconvex–Polyak-Łojasiewicz Conditions

In this subsection, we consider an extension of the result studied in the
previous section, where we assume that the objective function $f(x,\cdot)$
satisfies the Polyak-Łojasiewicz condition given any $x$ and $f(\cdot,y)$ is
nonconvex given any $y$.

######  Assumption 4 (One-Sided PŁ Conditions).

We assume that $f:\mathbb{R}^{m}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
nonconvex in $x$ for any fixed $y$ and satisfies the PŁ condition in $y$ for
any fixed $x$, that is, there exists a positive constants $\mu_{y}$ such that
the following condition hold for any $x\in\mathbb{R}^{m}$:

$\displaystyle\begin{aligned}
2\mu_{y}[\max_{y}f(x,y)-f(x,y)]\leq\|\nabla_{y}f(x,y)\|^{2}.\end{aligned}$
(15)

Since $f$ satisfies only one-sided PŁ condition, we are giving up the hope to
find a global optimal solution of (1), as studied in Theorem 1. In stead, we
will show that GDAD will return a stationary point of $f$, as studied in [33].
Note that under Assumption 2 the result in Lemma 1 still holds since the work
in [33] only assumes one-sided PŁ condition. In addition, since we relax the
two-sided PŁ condition, we introduce the following two Lyapunov functions for
our analysis studied later.

$\displaystyle V_{1}(x,y)$
$\displaystyle=f(x,y)-\min_{x\in\mathbb{R}^{m}}\min_{y\in\mathbb{R}^{n}}f(x,y),$
(16) $\displaystyle V_{2}(x,y)$ $\displaystyle=\max_{y}f(x,y)-f(x,y),$ (17)

where it is obvious to see that $V_{1}$ and $V_{2}$ are nonnegative. The time
derivatives of $V_{1}$ and $V_{2}$ over the trajectories $\dot{x}$ and
$\dot{y}$ are given in the following lemma, whose proof is presented in
Section 4.2.

######  Lemma 3.

Suppose that Assumptions 1, 2, and 4 hold. Then we have

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle=-\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}+\beta\|\nabla_{y}f(x(t),y(t))\|^{2}.$
(18) $\displaystyle\dot{V}_{2}(x(t),y(t))$
$\displaystyle\leq-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}+\frac{L_{xy}^{2}\alpha}{\mu_{y}}V_{2}(x(t),y(t)).$
(19)

Similar to the previous subsection, we utilize the following coupling Lyapunov
function

$\displaystyle V(x,y)=V_{1}(x,y)+\frac{\gamma\alpha}{\beta}V_{2}(x,y),$ (20)

for some constant $\gamma$, which will be defined below. The convergence rate
of GDAD under the nonconvex-PŁ condition is formally stated in the following
theorem.

######  Theorem 2.

Suppose that Assumptions 1, 2, and 4 hold. Let $\gamma,\alpha,\beta$ be chosen
as

$\displaystyle\gamma=\frac{32L_{xy}^{2}}{\mu_{y}^{2}},\quad\alpha=\frac{1}{8L_{xy}^{2}},\quad\beta=\frac{1}{\mu_{y}^{2}}\cdot$
(21)

Then we have for all $T\geq 0$

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\frac{4L_{xy}\sqrt{V_{1}(x(0),y(0))+4V_{2}(x(0),y(0))}}{\sqrt{T}}\cdot$
(24)

###### Proof.

By using (18), (19), and (20) we have

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle=\dot{V}_{1}(x(t))+\frac{\gamma\alpha}{\beta}\dot{V}_{2}(x(t),y(t))$
$\displaystyle\leq-\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}+\beta\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\gamma\alpha\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{\gamma\alpha^{2}}{8\beta}\|\nabla_{x}f(x(t),y(t))\|^{2}+\frac{4L_{xy}^{2}\gamma\alpha^{2}}{\mu_{y}\beta}V_{2}(x,y)$
$\displaystyle=-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}-\frac{\gamma\alpha}{2}\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\frac{\gamma\alpha}{4}\|\nabla_{y}f(x(t),y(t))\|^{2}+\beta\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\frac{\gamma\alpha}{4}\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{4L_{xy}^{2}\gamma\alpha^{2}}{\mu_{y}\beta}V_{2}(x,y)$
$\displaystyle\quad-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}+\frac{\gamma\alpha^{2}}{8\beta}\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}-\frac{\gamma\alpha}{2}\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\frac{\gamma\alpha}{4}\|\nabla_{y}f(x(t),y(t))\|^{2}+\beta\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\frac{\mu_{y}\gamma\alpha}{2}\Big{(}1-\frac{4L_{xy}^{2}\alpha}{\mu_{y}^{2}\beta}\Big{)}V_{2}(x,y)-\frac{\alpha}{2}\Big{(}1-\frac{\gamma\alpha}{4\beta}\Big{)}\|\nabla_{x}f(x(t),y(t))\|^{2},$
(25)

where in the last inequality we use (15) to have

$\displaystyle\|\nabla_{y}f(x,y)\|^{2}\geq
2\mu_{y}[\max_{y}f(x,y)-f(x,y)]=2\mu_{y}V_{2}(x,y).$

Using (21) and the preceding relation we have

$\displaystyle\frac{-\gamma\alpha}{4}+\beta=-\frac{1}{\mu_{y}^{2}}+\frac{1}{\mu_{y}^{2}}=0,\quad
1-\frac{4L_{xy}^{2}\alpha}{\mu_{y}^{2}\beta}=\frac{1}{2}\quad\text{and}\quad
1-\frac{\gamma\alpha}{4\beta}=0,$

which when substituting into (25) gives

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}-\frac{\gamma\alpha}{2}\|\nabla_{y}f(x(t),y(t))\|^{2}.$

Taking the integral on both sides over $t\in[0,T]$ for some $T\geq 0$ and
rearranging we obtain

$\displaystyle\frac{\alpha}{2}\int_{t=0}^{T}\|\nabla_{x}f(x(t),y(t))\|^{2}dt+\frac{\gamma\alpha}{2}\int_{t=0}^{T}\|\nabla_{y}f(x(t),y(t))\|^{2}dt$
$\displaystyle\leq V(x(0),y(0)),$

which since $\gamma\geq 1$ and by using (21) gives

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\sqrt{\frac{2V(x(0),y(0))}{\alpha T}}$
$\displaystyle\leq\frac{4L_{xy}\sqrt{V_{1}(x(0),y(0))+4V_{2}(x(0),y(0))}}{\sqrt{T}},$

which concludes our proof. ∎

###  3.3 Nonconvex–Strongly Concave Conditions

In this subsection, we study the rate of GDAD when the function $f(x,y)$ is
nonconvex given any $y$ and strongly concave given any $x$. In particular, we
consider the following assumption.

######  Assumption 5.

The objective function $f(\cdot,y)$ is nonconvex for any given $y$ and
$f(x,\cdot)$ is strongly concave with constant $\mu_{y}>0$ for any given $x$.
The latter is equivalent to

$\displaystyle f(x,y_{1})-f(x,y_{2})-\langle\nabla
f(x,y_{2}),y_{1}-y_{2}\rangle\leq-\frac{\mu_{y}}{2}\|y_{1}-y_{2}\|^{2},\quad\forall
y_{1},y_{2}\in\mathbb{R}^{n}.$ (26)

For our analysis of in this section, we introduce the following two Lyapunov
functions

$\displaystyle V_{1}(x,y)$ $\displaystyle=f(x,y)-\min_{(x,y)}f(x,y)$ (27)
$\displaystyle V_{2}(x,y)$
$\displaystyle=\frac{1}{2}\|\dot{y}\|^{2}=\frac{1}{2}\|\beta\nabla_{y}f(x,y)\|^{2}.$
(28)

The time derivatives of $V_{1}$ and $V_{2}$ over the trajectories $\dot{x}$
and $\dot{y}$ are given in the following lemma, whose proof is presented in
Section 4.3.

######  Lemma 4.

Suppose that Assumptions 1 and 5 hold. Then we have

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle\leq-\frac{1}{\alpha}\|\dot{x}(t)\|^{2}+\frac{1}{\beta}\|\dot{y}(t)\|^{2}.$
(29) $\displaystyle\dot{V}_{2}(x(t),y(t))$ $\displaystyle\leq
L_{xy}\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\mu_{y}\beta\|\dot{y}(t)\|^{2}.$ (30)

We next derive the convergence rate of GDAD under Assumption 5 in the
following theorem, where we show that GDAD converges sublinear to a stationary
point of $f$.

######  Theorem 3.

Suppose that Assumptions 1 and 5 hold. Let $\gamma,\alpha,\beta$ be chosen as

$\displaystyle\gamma=\mu_{y}L_{xy}^{2},\quad\alpha=\frac{1}{L_{xy}^{2}},\quad\beta=\frac{4}{\mu_{y}^{2}}.$
(31)

Then we have for all $T\geq 0$

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\frac{L_{xy}\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{T}}+\frac{2L_{xy}\|\nabla_{y}f(x(0),y(0))\|}{\sqrt{\mu_{y}T}}\cdot$
(34)

###### Proof.

By using (29) and (30) we consider

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle=\dot{V}_{1}(x(t),y(t))+\frac{\gamma\alpha}{\beta}\dot{V}_{2}(x(t),y(t))$
$\displaystyle\leq-\frac{1}{\alpha}\|\dot{x}(t)\|^{2}+\frac{1}{\beta}\|\dot{y}(t)\|^{2}+L_{xy}\gamma\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|-\mu_{y}\gamma\alpha\|\dot{y}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}-\frac{\mu_{y}\gamma\alpha}{4}\|\dot{y}(t)\|^{2}-(\frac{\mu_{y}\gamma\alpha}{4}-\frac{1}{\beta})\|\dot{y}(t)\|^{2}$
$\displaystyle\quad-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}+L_{xy}\gamma\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{y}\gamma\alpha}{2}\|\dot{y}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}-\frac{\mu_{y}\gamma\alpha}{4}\|\dot{y}(t)\|^{2}$
$\displaystyle\quad-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}+L_{xy}\gamma\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{y}\gamma\alpha}{2}\|\dot{y}(t)\|^{2},$
(35)

where in the last equality we use (31) to have

$\displaystyle\frac{\mu_{y}\gamma\alpha}{4}-\frac{1}{\beta}=\frac{\mu_{y}^{2}}{4}-\frac{\mu_{y}^{2}}{4}=0.$

Using (31) one more time we obtain

$\displaystyle-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}+L_{xy}\gamma\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{y}\gamma\alpha}{2}\|\dot{y}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}+\mu_{y}L_{xy}\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{y}^{2}L_{xy}^{2}\alpha}{2}\|\dot{y}(t)\|^{2}\leq
0,$

which when using into (35) we obtain

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle\leq-\frac{1}{2\alpha}\|\dot{x}(t)\|^{2}-\frac{\mu_{y}\gamma\alpha}{4}\|\dot{y}(t)\|^{2}$
$\displaystyle=-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}-\frac{\mu_{y}\gamma\alpha\beta^{2}}{4}\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle=-\frac{\alpha}{2}\|\nabla_{x}f(x(t),y(t))\|^{2}-\frac{4L_{xy}^{2}\alpha}{\mu_{y}^{2}}\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\leq\frac{-\alpha}{2}\big{(}\|\nabla_{x}f(x(t),y(t))\|^{2}+\|\nabla_{y}f(x(t),y(t))\|^{2}\big{)},$

which when taking the integral on both sides over $t$ from $0$ to $T$ and
rearrange we obtain

$\displaystyle\frac{\alpha}{2}\int_{t=0}^{T}\big{(}\|\nabla_{x}f(x(t),y(t))\|^{2}+\|\nabla_{y}f(x(t),y(t))\|^{2}\big{)}dt\leq
V(x(0),y(0)).$

Thus, the preceding relation gives (34), i.e., for all $T>0$

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\frac{\sqrt{2V(x(0),y(0))}}{\sqrt{\alpha
T}}\leq\frac{\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{\alpha
T}}+\frac{\sqrt{2V_{2}(x(0),y(0))}}{\sqrt{\alpha T}}$
$\displaystyle=\sqrt{\frac{2V_{1}(x(0),y(0))}{\alpha
T}}+\sqrt{\frac{\gamma\alpha\beta\|\nabla_{y}f(x(0),y(0))\|^{2}}{\alpha T}}$
$\displaystyle=\frac{L_{xy}\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{T}}+\frac{2L_{xy}\|\nabla_{y}f(x(0),y(0))\|}{\sqrt{\mu_{y}T}}\cdot$

∎

###  3.4 Strongly Convex–Nonconcave Conditions

As mentioned, the single-loop GDA method is applicable to the convex-
nonconcave min-max problem, while the nested-loop GDA method is not. In this
section, we complete our analysis by studying the rate of GDAD when the
function $f(x,y)$ is strongly convex given any $y$ and nonconcave given any
$x$. In particular, we consider the following assumption.

######  Assumption 6.

The objective function $f(x,\cdot)$ is nonconcave for any given $x$ and
$f(\cdot,y)$ is strongly convex with constant $\mu_{x}>0$ for any given $y$.
The latter is equivalent to

$\displaystyle f(x_{1},y)-f(x_{2},y)-\langle\nabla
f(x_{2},y),x_{1}-x_{2}\rangle\geq\frac{\mu_{x}}{2}\|x_{1}-x_{2}\|^{2},\quad\forall
x_{1},x_{2}\in\mathbb{R}^{m}.$ (36)

For our analysis of in this section, we introduce the following two Lyapunov
functions

$\displaystyle V_{1}(x,y)$
$\displaystyle=\frac{1}{2}\|\dot{x}\|^{2}=\frac{1}{2}\|\alpha\nabla_{x}f(x,y)\|^{2}$
(37) $\displaystyle V_{2}(x,y)$ $\displaystyle=\max_{x,y}f(x,y)-f(x,y).$ (38)

The time derivatives of $V_{1}$ and $V_{2}$ over the trajectories $\dot{x}$
and $\dot{y}$ are given in the following lemma, whose proof is presented in
Section 4.4.

######  Lemma 5.

Suppose that Assumptions 1 and 6 hold. Then we have

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle\leq-\mu_{x}\alpha\|\dot{x}(t)\|^{2}+L_{xy}\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|.$
(39) $\displaystyle\dot{V}_{2}(x(t),y(t))$
$\displaystyle\leq\frac{1}{\alpha}\|\dot{x}(t)\|^{2}-\frac{1}{\beta}\|\dot{y}(t)\|^{2}.$
(40)

Since in the strongly convex-nonconcave setting the minimization problem is
easier to solve than the maximization problem, we consider the following
Lyapunov function

$\displaystyle V(x,y)=V_{2}(x,y)+\frac{\gamma\beta}{\alpha}V_{1}(x,y),$ (41)

where $\beta\ll\alpha$. In this case, $\dot{x}$ is updated at a faster time
scale than $\dot{y}$. Using this Lyapunov function, we now derive the
convergence rate of GDAD under Assumption 6 in the following theorem, which
basically is similar to the one in Theorem 3.

######  Theorem 4.

Suppose that Assumptions 1 and 6 hold. Let $\gamma,\alpha,\beta$ be chosen as

$\displaystyle\gamma=\mu_{x}L_{xy}^{2},\quad\alpha=\frac{4}{\mu_{x}^{2}},\quad\beta=\frac{1}{L_{xy}^{2}}.$
(42)

Then we have for all $T\geq 0$

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\frac{L_{xy}\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{T}}+\frac{2L_{xy}\|\nabla_{x}f(x(0),y(0))\|}{\sqrt{\mu_{x}T}}\cdot$
(45)

###### Proof.

By using (39) and (40) we consider

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle=\dot{V}_{2}(x(t),y(t))+\frac{\gamma\beta}{\alpha}\dot{V}_{1}(x(t),y(t))$
$\displaystyle\leq\frac{1}{\alpha}\|\dot{x}(t)\|^{2}-\frac{1}{\beta}\|\dot{y}(t)\|^{2}+L_{xy}\gamma\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\mu_{x}\gamma\beta\|\dot{x}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}-\frac{\mu_{x}\gamma\beta}{4}\|\dot{x}(t)\|^{2}-(\frac{\mu_{x}\gamma\beta}{4}-\frac{1}{\alpha})\|\dot{x}(t)\|^{2}$
$\displaystyle\quad-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}+L_{xy}\gamma\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{x}\gamma\beta}{2}\|\dot{x}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}-\frac{\mu_{x}\gamma\beta}{4}\|\dot{x}(t)\|^{2}$
$\displaystyle\quad-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}+L_{xy}\gamma\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{x}\gamma\beta}{2}\|\dot{x}(t)\|^{2},$
(46)

where in the last equality we use (42) to have

$\displaystyle\frac{\mu_{x}\gamma\beta}{4}-\frac{1}{\alpha}=\frac{\mu_{x}^{2}}{4}-\frac{\mu_{x}^{2}}{4}=0.$

Using (42) one more time we obtain

$\displaystyle-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}+L_{xy}\gamma\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{x}\gamma\beta}{2}\|\dot{x}(t)\|^{2}$
$\displaystyle=-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}+\mu_{x}L_{xy}\|\dot{y}(t)\|\|\dot{x}(t)\|-\frac{\mu_{x}^{2}L_{xy}^{2}\beta}{2}\|\dot{x}(t)\|^{2}\leq
0,$

which when using into (46) we obtain

$\displaystyle\dot{V}(x(t),y(t))$
$\displaystyle\leq-\frac{1}{2\beta}\|\dot{y}(t)\|^{2}-\frac{\mu_{x}\gamma\beta}{4}\|\dot{x}(t)\|^{2}$
$\displaystyle=-\frac{\beta}{2}\|\nabla_{y}f(x(t),y(t))\|^{2}-\frac{\mu_{x}\gamma\beta\alpha^{2}}{4}\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle=-\frac{\beta}{2}\|\nabla_{y}f(x(t),y(t))\|^{2}-\frac{4L_{xy}^{2}\beta}{\mu_{x}^{2}}\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle\leq\frac{-\beta}{2}\big{(}\|\nabla_{x}f(x(t),y(t))\|^{2}+\|\nabla_{y}f(x(t),y(t))\|^{2}\big{)},$

which when taking the integral on both sides over $t$ from $0$ to $T$ and
rearrange we obtain

$\displaystyle\frac{\beta}{2}\int_{t=0}^{T}\big{(}\|\nabla_{x}f(x(t),y(t))\|^{2}+\|\nabla_{y}f(x(t),y(t))\|^{2}\big{)}dt\leq
V(x(0),y(0)).$

Thus, the preceding relation gives (45), i.e., for all $T>0$

$\displaystyle\min_{0\leq t\leq
T}\left\|\begin{array}[]{cc}\nabla_{x}f(x(t),y(t))\\\
\nabla_{y}f(x(t),y(t))\end{array}\right\|$
$\displaystyle\leq\frac{\sqrt{2V(x(0),y(0))}}{\sqrt{\beta
T}}\leq\frac{\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{\beta
T}}+\frac{\sqrt{2V_{2}(x(0),y(0))}}{\sqrt{\beta T}}$
$\displaystyle=\sqrt{\frac{2V_{1}(x(0),y(0))}{\beta
T}}+\sqrt{\frac{\gamma\beta\alpha\|\nabla_{x}f(x(0),y(0))\|^{2}}{\beta T}}$
$\displaystyle=\frac{L_{xy}\sqrt{2V_{1}(x(0),y(0))}}{\sqrt{T}}+\frac{2L_{xy}\|\nabla_{x}f(x(0),y(0))\|}{\sqrt{\mu_{x}T}}\cdot$

∎

##  4 Proofs of Technical Lemmas

In this section, we present the analysis of all technical lemmas in the
previous sections.

###  4.1 Proof of Lemma 2

###### Proof.

For convenience, we denote by $y^{\star}(x)={\cal P}_{{\cal
Y}^{\star}(x)}[y]$, where recall that ${\cal Y}^{\star}(x)$ is the solution
set of $\max_{y}f(x,y)$ for a given $x$. We first show (9). The time
derivative of $V_{1}$ defined in (7) over the trajectory $\dot{x}$ in (2) is
given as

$\displaystyle\dot{V}_{1}(x)$
$\displaystyle=\frac{d}{dt}V_{1}(x)=\nabla_{x}f(x,y^{\star}(x))\dot{x}=-\alpha\langle\nabla_{x}f(x,y^{\star}(x)),\nabla_{x}f(x,y)\rangle$
$\displaystyle=-\alpha\|\nabla_{x}f(x,y^{\star}(x))\|^{2}-\alpha\langle\nabla_{x}f(x,y^{\star}(x)),\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\rangle$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{\alpha}{2}\|\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\|^{2}$
(47)
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{L_{xy}^{2}\alpha}{2}\|y-y^{\star}(x)\|^{2}$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{L_{xy}^{2}\alpha}{\mu_{y}}(\max_{y}f(x,y)-f(x,y)),$

where the first and second inequalities are due to the Cauchy-Schwarz
inequality and Assumption 1, respectively. In addition, the last inequality is
due to (6).

Next we show (10). Indeed, using (47) we have

$\displaystyle\dot{V}_{2}(x,y)$
$\displaystyle=\nabla_{x}f(x,y^{\star}(x))\dot{x}-\nabla_{x}f(x,y)\dot{x}-\nabla_{y}f(x,y)\dot{y}$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{\alpha}{2}\|\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\|^{2}-\beta\|\nabla_{y}f(x,y)\|^{2}$
$\displaystyle\quad+\alpha\|\nabla_{x}f(x,y)\|^{2}$
$\displaystyle\leq-\frac{\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}-\beta\|\nabla_{y}f(x,y)\|^{2}+\frac{\alpha}{2}\|\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\|^{2}$
$\displaystyle\quad+2\alpha\|\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\|^{2}+2\alpha\|\nabla_{x}f(x,y^{\star}(x))\|^{2}$
$\displaystyle=-\beta\|\nabla_{y}f(x,y)\|^{2}+\frac{3\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{5\alpha}{2}\|\nabla_{x}f(x,y)-\nabla_{x}f(x,y^{\star}(x))\|^{2}$
$\displaystyle\leq-\beta\|\nabla_{y}f(x,y)\|^{2}+\frac{3\alpha}{2}\|\nabla_{x}f(x,y^{\star}(x))\|^{2}+\frac{5L_{xy}^{2}\alpha}{\mu_{y}}(\max_{y}f(x,y)-f(x,y)),$

where the last inequality we use Assumption 1 and (6), similar to the last
inequality in $\dot{V}_{1}$ above. ∎

###  4.2 Proof of Lemma 3

###### Proof.

For convenience, we denote by $y^{\star}(x)={\cal P}_{{\cal
Y}^{\star}(x)}[y]$, where recall that ${\cal Y}^{\star}(x)$ is the solution
set of $\max_{y}f(x,y)$ for a given $x$. We first show (18). The time
derivative of $V_{1}$ defined in (16) over the trajectory $\dot{x}$ in (2) is
given as

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle=\frac{d}{dt}V_{1}(x(t),y(t))=\nabla_{x}f(x(t),y(t))\dot{x}+\nabla_{y}f(x(t),y(t))\dot{y}$
$\displaystyle=-\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}+\beta\|\nabla_{y}f(x(t),y(t))\|^{2}.$

Next we show (19). Indeed, using (2) we have

$\displaystyle\dot{V}_{2}(x(t),y(t))$
$\displaystyle=\nabla_{x}f(x(t),y^{\star}(x(t)))\dot{x}-\nabla_{x}f(x(t),y(t))\dot{x}-\nabla_{y}f(x(t),y(t))\dot{y}$
$\displaystyle=-\alpha\langle\nabla_{x}f(x(t),y^{\star}(x(t))),\nabla_{x}f(x(t),y(t))\rangle-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}$
$\displaystyle\quad+\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle=-\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}+\alpha\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle\quad-\alpha\langle\nabla_{x}f(x(t),y^{\star}(x(t)))-\nabla_{x}f(x(t),y(t)),\nabla_{x}f(x(t),y(t))\rangle$
$\displaystyle\leq-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{\alpha}{8}\|\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle\quad+2\alpha\|\nabla_{x}f(x(t),y^{\star}(x(t)))-\nabla_{x}f(x(t),y(t))\|^{2}$
$\displaystyle\leq-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{\alpha}{8}\|\nabla_{x}f(x(t),y(t))\|^{2}+2L_{xy}^{2}\alpha\|y^{\star}(x(t))-y(t)\|^{2}$
$\displaystyle\leq-\beta\|\nabla_{y}f(x(t),y(t))\|^{2}+\frac{\alpha}{8}\|\nabla_{x}f(x(t),y(t))\|^{2}+\frac{4L_{xy}^{2}\alpha}{\mu_{y}}V_{2}(x(t),y(t)),$

where the second inequality is due to the Cauchy-Schwarz inequality:
$2xy\leq(1/\eta)x^{2}+\eta y^{2}$ for any $\eta>0$. In addition, the last two
inequalities are due to Eqs. 1 and (6), respectively. ∎

###  4.3 Proof of Lemma 4

###### Proof.

We first show (29). Indeed, using (2)

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle=\frac{d}{dt}V_{1}(x(t),y(t))=\nabla_{x}f(x(t),y(t))\dot{x}+\nabla_{y}f(x(t),y(t))\dot{y}$
$\displaystyle=-\frac{1}{\alpha}\|\dot{x}(t)\|^{2}+\frac{1}{\beta}\|\dot{y}(t)\|^{2}.$

Next, we show (30). Using (2) and (28) we consider

$\displaystyle\dot{V}_{2}(x(t),y(t))$
$\displaystyle=\beta\langle\dot{y}(t),\frac{d}{dt}\nabla_{y}f(x,y)\rangle$
$\displaystyle=\beta\langle\dot{y}(t),\nabla_{yx}f(x(t),y(t))\dot{x}(t)+\nabla_{yy}f(x(t),y(t))\dot{y}(t)\rangle$
$\displaystyle=\beta\langle\dot{y}(t),\nabla_{yx}f(x(t),y(t))\dot{x}(t)\rangle+\beta\langle\dot{y}(t),\nabla_{yy}f(x(t),y(t))\dot{y}(t)\rangle$
$\displaystyle\leq
L_{xy}\beta\|\dot{y}(t)\|\|\dot{x}(t)\|-\mu_{y}\beta\|\dot{y}(t)\|^{2},$

where in the last inequality we use Assumptions 1 and 5 to have

$\displaystyle\|\nabla_{yx}f(x(t),y(t))\|\leq
L_{xy}\quad\text{and}\quad\nabla_{yy}f(x(t),y(t))\leq-\mu_{y}{\bf
I},\;\text{where }{\bf I}\text{ is the identity matrix}.$

∎

###  4.4 Proof of Lemma 5

###### Proof.

We first show (39). Using (2) and (37) we consider

$\displaystyle\dot{V}_{1}(x(t),y(t))$
$\displaystyle=-\alpha\langle\dot{x}(t),\frac{d}{dt}\nabla_{x}f(x(t),y(t))\rangle$
$\displaystyle=-\alpha\langle\dot{x}(t),\nabla_{xx}f(x(t),y(t))\dot{x}(t)+\nabla_{xy}f(x(t),y(t))\dot{y}(t)\rangle$
$\displaystyle=-\alpha\langle\dot{x}(t),\nabla_{xx}f(x(t),y(t))\dot{x}(t)\rangle-\alpha\langle\dot{x}(t),\nabla_{xy}f(x(t),y(t))\dot{y}(t)\rangle$
$\displaystyle\leq-\mu_{x}\alpha\|\dot{x}(t)\|^{2}+L_{xy}\alpha\|\dot{y}(t)\|\|\dot{x}(t)\|,$

where in the last inequality we use Assumptions 1 and 6 to have

$\displaystyle\|\nabla_{xy}f(x(t),y(t))\|\leq
L_{xy}\quad\text{and}\quad\nabla_{xx}f(x(t),y(t))\geq\mu_{x}{\bf
I},\;\text{where }{\bf I}\text{ is the identity matrix}.$

Next, we show (40). Indeed, using (2)

$\displaystyle\dot{V}_{2}(x(t),y(t))$
$\displaystyle=\frac{d}{dt}V_{2}(x(t),y(t))=-\nabla_{x}f(x(t),y(t))\dot{x}-\nabla_{y}f(x(t),y(t))\dot{y}$
$\displaystyle=\frac{1}{\alpha}\|\dot{x}(t)\|^{2}-\frac{1}{\beta}\|\dot{y}(t)\|^{2}.$

∎

##  5 Concluding Remarks

In this paper, we consider two-time-scale gradient descent-ascent dynamics for
solving nonconvex min-max optimization problems. Our main focus is to derive
the convergence rates of this method for different settings of the underlying
objective functions. Our techniques are mainly motivated by the classic
singular perturbation, where we show that our analysis improves the existing
results under the same conditions. A natural extension from this work is to
provide a better analysis for the discrete-time variant of GDAD. Another
interesting future direction is to consider the stochastic setting and its
accelerated counterpart.

## References

  * [1] T. Basar and G. J. Olsder, _Dynamic Noncooperative Game Theory, 2nd Edition_. Society for Industrial and Applied Mathematics, 1998.
  * [2] L. S. Shapley, “Stochastic games,” _Proceedings of the National Academy of Sciences_ , 1953.
  * [3] E. Altman, _Constrained Markov decision processes_. Chapman and Hall/CRC Press, 1999.
  * [4] J. Achiam, D. Held, A. Tamar, and P. Abbeel, “Constrained policy optimization,” in _Proceedings of the 34th International Conference on Machine Learning_ , vol. 70, 2017, pp. 22–31.
  * [5] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial networks,” _Commun. ACM_ , vol. 63, no. 11, p. 139–144, 2020.
  * [6] L. Mescheder, S. Nowozin, and A. Geiger, “The numerics of gans,” in _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , ser. NIPS’17, 2017, p. 1823–1833.
  * [7] A. Kurakin, I. J. Goodfellow, and S. Bengio, “Adversarial machine learning at scale,” in _5th International Conference on Learning Representations, ICLR_ , 2017.
  * [8] Q. Qian, S. Zhu, J. Tang, R. Jin, B. Sun, and H. Li, “Robust optimization over multiple domains,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, pp. 4739–4746, Jul. 2019.
  * [9] Y.-F. Liu, Y.-H. Dai, and Z.-Q. Luo, “Max-min fairness linear transceiver design for a multi-user mimo interference channel,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 9, pp. 2413–2423, 2013.
  * [10] G. Lan, S. Lee, and Y. Zhou, “Communication-efficient algorithms for decentralized and stochastic optimization,” _Mathematical Programming_ , vol. 180, pp. 237–284, 2020.
  * [11] T.-H. Chang, M. Hong, H.-T. Wai, X. Zhang, and S. Lu, “Distributed learning in the nonconvex world: From batch data to streaming and beyond,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 26–38, 2020.
  * [12] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, and T. Graepel, “The mechanics of n-player differentiable games,” in _Proceedings of the 35th International Conference on Machine Learning_ , vol. 80, 2018, pp. 354–363.
  * [13] W. Krichene, A. Bayen, and P. L. Bartlett, “Accelerated mirror descent in continuous and discrete time,” in _Advances in Neural Information Processing Systems_ , vol. 28, 2015.
  * [14] M. Raginsky and J. Bouvrie, “Continuous-time stochastic mirror descent on a network: Variance reduction, consensus, convergence,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_ , 2012, pp. 6793–6800.
  * [15] W. Su, S. Boyd, and E. J. Candès, “A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights,” in _Proceedings of the 27th International Conference on Neural Information Processing Systems_ , ser. NIPS’14, 2014, p. 2510–2518.
  * [16] J. Diakonikolas and L. Orecchia, “The approximate duality gap technique: A unified theory of first-order methods,” _SIAM Journal on Optimization_ , vol. 29, no. 1, pp. 660–689, 2019.
  * [17] A. Nemirovski, “Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems,” _SIAM Journal on Optimization_ , vol. 15, no. 1, pp. 229–251, 2004.
  * [18] Y. Malitsky, “Projected reflected gradient methods for monotone variational inequalities,” _SIAM Journal on Optimization_ , vol. 25, no. 1, pp. 502–520, 2015.
  * [19] Y. Wang and J. Li, “Improved algorithms for convex-concave minimax optimization,” in _Advances in Neural Information Processing Systems_ , vol. 33, 2020, pp. 4800–4810.
  * [20] A. Cherukuri, B. Gharesifard, and J. Cortés, “Saddle-point dynamics: Conditions for asymptotic stability of saddle points,” _SIAM Journal on Control and Optimization_ , vol. 55, no. 1, pp. 486–511, 2017.
  * [21] “Semi-global exponential stability of augmented primal–dual gradient dynamics for constrained convex optimization,” _Systems & Control Letters_, vol. 144, p. 104754, 2020.
  * [22] G. Korpelevich, “The extragradient method for finding saddle points and other problems,” _Matecon_ , vol. 12, pp. 747–756, 1976.
  * [23] A. Mokhtari, A. E. Ozdaglar, and S. Pattathil, “Convergence rate of o(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems,” _SIAM Journal on Optimization_ , vol. 30, no. 4, pp. 3230–3251, 2020.
  * [24] R. D. C. Monteiro and B. F. Svaiter, “On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean,” _SIAM Journal on Optimization_ , vol. 20, no. 6, pp. 2755–2787, 2010.
  * [25] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar, “Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems,” in _Proceedings of Thirty Third Conference on Learning Theory_ , vol. 125, 2020, pp. 1758–1784.
  * [26] T. Yoon and E. K. Ryu, “Accelerated algorithms for smooth convex-concave minimax problems with $o(1/k^{2})$ rate on squared gradient norm,” in _Proceedings of the 38th International Conference on Machine Learning_ , vol. 139, 2021, pp. 12 098–12 109.
  * [27] C. D. Dang and G. Lan, “On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators,” _Computational Optimization and Applications_ , vol. 60, pp. 277–310, 2015.
  * [28] J. Abernethy, K. A. Lai, and A. Wibisono, “Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization,” in _Proceedings of the 32nd International Conference on Algorithmic Learning Theory_ , vol. 132, 2021, pp. 3–47.
  * [29] K. K. Thekumparampil, P. Jain, P. Netrapalli, and S. Oh, “Efficient algorithms for smooth minimax optimization,” in _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [30] W. Kong and R. D. C. Monteiro, “An accelerated inexact proximal point method for solving nonconvex-concave min-max problems,” _SIAM Journal on Optimization_ , vol. 31, no. 4, pp. 2558–2585, 2021.
  * [31] H. Rafique, M. Liu, Q. Lin, and T. Yang, “Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning,” _Optimization Methods and Software_ , vol. 0, no. 0, pp. 1–35, 2021.
  * [32] T. Lin, C. Jin, and M. I. Jordan, “Near-optimal algorithms for minimax optimization,” in _Proceedings of Thirty Third Conference on Learning Theory_ , vol. 125. PMLR, 09–12 Jul 2020, pp. 2738–2779.
  * [33] M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn, “Solving a class of non-convex min-max games using iterative first order methods,” in _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [34] T. Lin, C. Jin, and M. Jordan, “On gradient descent ascent for nonconvex-concave minimax problems,” in _Proceedings of the 37th International Conference on Machine Learning_ , vol. 119. PMLR, 13–18 Jul 2020, pp. 6083–6093.
  * [35] S. Lu, I. Tsaknakis, M. Hong, and Y. Chen, “Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 3676–3691, 2020.
  * [36] J. Yang, N. Kiyavash, and N. He, “Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems,” in _Advances in Neural Information Processing Systems_ , vol. 33, 2020, pp. 1153–1165.
  * [37] Z. Xu, H.-L. Zhang, Y. Xu, and G. Lan, “A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems,” _ArXiv_ , vol. abs/2006.02032, 2020.
  * [38] J. Zhang, P. Xiao, R. Sun, and Z. Luo, “A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems,” in _Advances in Neural Information Processing Systems_ , vol. 33, 2020, pp. 7377–7389.
  * [39] N. Loizou, H. Berard, A. Jolicoeur-Martineau, P. Vincent, S. Lacoste-Julien, and I. Mitliagkas, “Stochastic Hamiltonian gradient methods for smooth games,” in _Proceedings of the 37th International Conference on Machine Learning_ , vol. 119, 2020, pp. 6370–6381.
  * [40] K. Zhang, Z. Yang, and T. Basar, “Policy optimization provably converges to nash equilibria in zero-sum linear quadratic games,” in _NeurIPS_ , vol. 32, 2019.
  * [41] S. Cen, Y. Wei, and Y. Chi, “Fast policy extragradient methods for competitive games with entropy regularization,” _ArXiv_ , vol. abs/2105.15186, 2021.
  * [42] J. Perolat, B. Piot, and O. Pietquin, “Actor-critic fictitious play in simultaneous move multistage games,” in _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , vol. 84, 2018, pp. 919–928.
  * [43] C. Daskalakis, D. J. Foster, and N. Golowich, “Independent policy gradient methods for competitive reinforcement learning,” in _Advances in Neural Information Processing Systems_ , vol. 33, 2020, pp. 5527–5540.
  * [44] V. S. Borkar, _Stochastic Approximation: A Dynamical Systems Viewpoint_. Cambridge University Press, 2008.
  * [45] V. R. Konda and J. N. Tsitsiklis, “Convergence rate of linear two-time-scale stochastic approximation,” _The Annals of Applied Probability_ , vol. 14, no. 2, pp. 796–819, 2004.
  * [46] G. Dalal, B. Szorenyi, and G. Thoppe, “A tale of two-timescale reinforcement learning with the tightest finite-time bound,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, pp. 3701–3708, Apr. 2020\.
  * [47] T. T. Doan and J. Romberg, “Linear two-time-scale stochastic approximation a finite-time analysis,” in _57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2019, pp. 399–406.
  * [48] H. Gupta, R. Srikant, and L. Ying, “Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning,” in _Advances in Neural Information Processing Systems_ , 2019.
  * [49] T. T. Doan, “Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation,” _SIAM Journal on Control and Optimization_ , vol. 59, no. 4, pp. 2798–2819, 2021.
  * [50] M. Kaledin, E. Moulines, A. Naumov, V. Tadic, and H.-T. Wai, “Finite time analysis of linear two-timescale stochastic approximation with Markovian noise,” in _Proceedings of Thirty Third Conference on Learning Theory_ , vol. 125, 2020, pp. 2144–2203.
  * [51] A. Mokkadem and M. Pelletier, “Convergence rate and averaging of nonlinear two-time-scale stochastic approximation algorithms,” _The Annals of Applied Probability_ , vol. 16, no. 3, pp. 1671–1702, 2006.
  * [52] T. T. Doan, “Finite-time convergence rates of nonlinear two-time-scale stochastic approximation under Markovian noise,” _arXiv preprint arXiv:2104.01627_ , 2021.
  * [53] ——, “Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance,” _arXiv preprint arXiv:2011.01868_ , 2020.
  * [54] V. S. Borkar, “An actor-critic algorithm for constrained Markov decision processes,” _Systems & control letters_, vol. 54, no. 3, pp. 207–213, 2005\.
  * [55] S. Bhatnagar and K. Lakshmanan, “An online actor–critic algorithm with function approximation for constrained Markov decision processes,” _Journal of Optimization Theory and Applications_ , 2012.
  * [56] S. Paternain, L. Chamon, M. Calvo-Fullana, and A. Ribeiro, “Constrained reinforcement learning has zero duality gap,” in _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [57] D. Ding, K. Zhang, T. Basar, and M. R. Jovanovic, “Natural policy gradient primal-dual method for constrained Markov decision processes.” in _NeurIPS_ , 2020.
  * [58] S. Zeng, T. T. Doan, and J. Romberg, “Finite-time complexity of online primal-dual natural actor-critic algorithm for constrained Markov decision processes,” _ArXiv_ , vol. abs/2110.11383, 2021.
  * [59] M. Wang, E. X. Fang, and H. Liu, “Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions,” _Mathematical Programming_ , vol. 161, no. 1, pp. 419–449, Jan 2017.
  * [60] S. Zeng, T. T. Doan, and J. Romberg, “A two-time-scale stochastic optimization framework with applications in control and reinforcement learning,” _ArXiv_ , vol. abs/2109.14756, 2021.
  * [61] S. Lee and A. Nedic, “Distributed random projection algorithm for convex optimization,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 7, no. 2, pp. 221–229, 2013.
  * [62] A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani, “An exact quantized decentralized gradient descent algorithm,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 19, pp. 4934–4947, 2019.
  * [63] T. T. Doan, S. T. Maguluri, and J. Romberg, “Convergence rates of distributed gradient methods under random quantization: A stochastic approximation approach,” _IEEE Transactions on Automatic Control_ , 2020.
  * [64] T. T. Doan, C. L. Beck, and R. Srikant, “On the convergence rate of distributed gradient methods for finite-sum optimization under communication delays,” _Proc. ACM Meas. Anal. Comput. Syst._ , vol. 1, no. 2, 2017.
  * [65] A. Dutta, A. M. Boker, and T. T. Doan, “Convergence rates of distributed consensus over cluster networks: A two-time-scale approach,” Available at: https://arxiv.org/abs/2104.07781, 2021.
  * [66] A. Dutta, N. Masrourisaadat, and T. T. Doan, “Convergence rates of decentralized gradient methods over cluster networks,” _arXiv preprint arXiv:2110.06992_ , 2021.
  * [67] M. M. Vasconcelos, T. T. Doan, and U. Mitra, “Improved convergence rate for a distributed two-time-scale gradient method under random quantization,” in _2021 IEEE Conference on Decision and Control (CDC)_ , 2021.
  * [68] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” in _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [69] P. Kokotović, H. K. Khalil, and J. O’Reilly, _Singular Perturbation Methods in Control: Analysis and Design_. Society for Industrial and Applied Mathematics, 1999.
  * [70] B. Polyak, “Gradient methods for the minimisation of functionals,” _Ussr Computational Mathematics and Mathematical Physics_ , vol. 3, pp. 864–878, 12 1963\.
  * [71] H. Karimi, J. Nutini, and M. Schmidt, “Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition,” in _Machine Learning and Knowledge Discovery in Databases_ , P. Frasconi, N. Landwehr, G. Manco, and J. Vreeken, Eds. Cham: Springer International Publishing, 2016, pp. 795–811.
  * [72] D. Bertsekas, _Nonlinear Programming: 2nd Edition_. Cambridge, MA: Athena Scientific, 1999.