text:
\begin{document}

\title{Fast Objective \& Duality Gap Convergence for Nonconvex-Strongly-Concave Min-Max Problems}

\author{\name Zhishuai Guo\thanks{Equal Contribution}
        \email zhishuai-guo@uiowa.edu \\
        \addr The University of Iowa \\
        \name Zhuoning Yuan\footnotemark[1]
        \email zhuoning-yuan@uiowa.edu\\
        \addr The University of Iowa \\
        \name Yan Yan\footnotemark[1]
        \email yanyan.tju@gmail.com\\
        \addr The University of Iowa \\
        \name Tianbao Yang \email tianbao-yang@uiowa.edu\\
        \addr  The University of Iowa \\
        }

\maketitle

\begin{abstract}
This paper focuses on stochastic methods for solving smooth non-convex strongly-concave min-max problems, which have received increasing attention  due to their potential applications in deep learning (e.g., deep AUC maximization).
However, most of the existing algorithms are slow in practice, and their analysis revolves around the convergence to a nearly stationary point.
We consider leveraging the  Polyak-\L ojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantee. Although PL condition has been utilized for designing many stochastic minimization algorithms, their applications for non-convex min-max optimization remains rare.
In this paper, we propose and analyze proximal epoch-based methods, and establish fast convergence in terms of both {\bf the primal objective gap and the duality gap}. Our analysis is interesting in threefold: (i) it is based on a novel Lyapunov function that consists of the primal objective gap and the duality gap of a regularized function; (ii) it only requires a weaker PL condition for establishing the primal objective convergence than that required for the duality gap convergence; (iii) it yields the optimal dependence on the accuracy level $\epsilon$, i.e., $O(1/\epsilon)$. We also make explicit the dependence on the problem parameters and explore regions of weak convexity parameter that lead to improved dependence on condition numbers.
Experiments on deep AUC maximization demonstrate the effectiveness of our methods. Our method (MaxAUC) achieved an AUC of 0.922 on private testing set on {\bf CheXpert competition}.
\end{abstract}

\setlength{\abovedisplayskip}{3pt}
\setlength{\belowdisplayskip}{0pt}

\setlength{\textfloatsep}{5pt}
\vspace*{-0.2in}
\section{Introduction}
\vspace*{-0.1in}
Min-max optimization has a broad range of applications in machine learning. In this paper, we consider a family of min-max optimization where the objective function is non-convex in terms of the min variable and is strongly concave in terms of the max variable. It covers a number of important applications in machine learning, such as deep AUC maximization \cite{liu2019stochastic} and distributionally robust optimization (DRO) \cite{namkoong2016stochastic,namkoong2017variance,rafique2018non}.  In particular,  we study stochastic gradient methods for solving the following {\bf non-convex strongly-concave (NCSC)} min-max  saddle-point problem:
\begin{align}\label{eqn:op}
    \min\limits_{x\in \R^d} \max\limits_{y\in Y} f(x, y),
\end{align}
where $Y\subseteq\R^{d'}$ is closed convex set, $f(x, y)$ is smooth, non-convex in $x$ and strongly concave in $y$.
We assume the optimization is only through a stochastic gradient oracle that for any $x, y$ returns unbiased stochastic gradient $(\mathcal G_x(x, y; \xi), \mathcal G_y(x, y; \xi))$, i.e.,  $\E[\mathcal G_x(x, y; \xi)] = \nabla f_x(x, y)$ and $\E[\mathcal G_y(x, y; \xi)] = \nabla f_y(x, y)$.

Stochastic algorithms for solving~(\ref{eqn:op}) have been studied in some recent papers~\cite{lin2019gradient,lin2020near,liu2019stochastic,rafique2018non,DBLP:journals/corr/abs-2002-05309,yang2020global}. However, most of them are slow in  practice~\cite{lin2019gradient,lin2020near,nouiehed2019solving,rafique2018non,DBLP:journals/corr/abs-2002-05309} by suffering from a high order iteration complexity, while others hinge on a special structure of the objective function  for constructing the update~\cite{liu2019stochastic}.  {\it How to improve the convergence for non-convex strongly-concave min-max problems remains an active research area.}  There are two lines of work trying to improve the iteration complexity of stochastic algorithms for NCSC min-max optimization.  The first line is to leverage the geometrical structure of the objective function, in particular the   Polyak-\L ojasiewicz (PL) condition~\cite{liu2019stochastic,yang2020global}.  The second line is to consider a finite-sum structure of the objective function and leverage variance-reduction techniques~\cite{luo2020stochastic,yang2020global}. While variance-reduction technique is promising in theory, it usually yields more complicated algorithm (e.g., requires computing full gradient or mega mini-batch size)  and marginal benefit in deep learning~\cite{defazio2019ineffectiveness}.
Hence, in this paper we will follow the first line to improve the convergence by leveraging the   Polyak-\L ojasiewicz (PL) condition of the objective function.

Although PL condition has been utilized extensively to improve the convergence for minimization problems~\cite{allen2018convergence,arora2018convergence,charles2017stability,du2018gradient,hardt2016identity,karimi2016linear,lei2017non,li2018learning,li2017convergence,li2018simple,nguyen2017stochastic,polyak1963gradient,reddi2016stochastic,wang2018spiderboost,zhou2018stochastic,zhou2017characterization}, its application to non-convex min-max problems remains rare~\cite{liu2019stochastic,nouiehed2019solving,yang2020global}.
Liu et al.~\cite{liu2019stochastic} considered solving a NCSC formulation of deep AUC maximization under a PL condition  of the primal objective and established a fast convergence rate for the primal objective gap. However, their algorithms are tailored to AUC maximization problems and it remains unclear how to extend them to handle general NCSC min-max problems without any special structure. Yang et al.~\cite{yang2020global} considered a more general family of objective function that satisfies PL conditions in terms of both $x$ and $y$, and established convergence for stochastic alternating gradient descent ascent method. However, it remains unclear whether its convergence  can be further improved by leveraging the strong concavity of the objective function in terms of $y$. In this paper, we address these questions by developing stochastic methods that are more generic than~\cite{liu2019stochastic} and enjoy faster convergence than~\cite{yang2020global}.  The key results of this paper are summarized below:
\begin{itemize}[leftmargin=*]
\item{\bf Algorithms.} We propose and analyze generic epoch-wise stochastic primal-dual methods, which in design are similar to practical stochastic gradient methods for deep learning.  In particular, the step sizes are decreased geometrically in an epoch manner.
\item {\bf Analysis.} We conduct a novel analysis of the proposed stochastic methods by establishing fast convergence in terms of both {\it the primal objective gap} and {\it the duality gap} under different PL conditions. Our analysis is based on a novel Lyapunov function that consists of the primal objective gap and the duality gap of a regularized problem. For the convergence of the primal objective gap, we only require a weaker PL condition defined on the primal objective. For the convergence of the duality gap, we assume the objective function satisfies a pointwise PL condition in terms of $x$.
\item {\bf Improvements.} Compared with~\cite{liu2019stochastic}, our algorithms are more generic and simpler, and enjoy the same order of iteration complexity  for deep AUC maximization under the same PL condition. Compared with~\cite{yang2020global}, our convergence results  enjoy better iteration complexities in terms of dependence on the strong concavity parameter for both the objective gap and the duality gap. We also explore possibilities to improve the convergence when the objective function is weakly convex in $x$ with a small weak-convexity parameter.
\end{itemize}
\vspace*{-0.1in}
We demonstrate the effectiveness of the proposed methods on deep AUC maximization.

\setlength{\textfloatsep}{5pt}

\begin{table}[t]
\caption{Comparison of sample complexities for achieving $\epsilon$-Objective Gap and and $\epsilon$-Duality Gap. $P(x)$ is $L$-smooth and is assumed to obey $\mu$-PL condition,  $f(x, y)$ is $\ell$-smooth in terms of $x$ and $y$, is $\mu_y$ strongly concave in terms of $y$, satisfies $x$-side $\mu_x$-PL condition (for duality gap convergence only). $^*$ marks the results that are not available in the original work but are derived by us.}
\begin{center}
\begin{tabular}{ c|c|c|c|c}
\hline
& \multicolumn{2}{|c|}{Objective Gap} & \multicolumn{2}{|c}{Duality Gap} \\
\hline
& Stoc-AGDA \cite{yang2020global}  & Ours & Stoc-AGDA \cite{yang2020global}  & Ours \\
\hline
$L = \ell+\frac{\ell^2}{\mu_y} $
& $O\left(\frac{\ell^5}{\mu^2 \mu_y^4 \epsilon}\right)$
& $\widetilde{O}\left(\frac{\ell^4}{\mu^2 \mu_y^3 \epsilon}\right)$
& $O\left(\frac{\ell^7}{\mu^2\mu_x \mu_y^5 \epsilon}\right)^*$
& $\widetilde{O}\left(\frac{\ell^5}{\mu^2 \mu_x \mu_y^3 \epsilon}\right)$\\
\hline
$L<\ell+\frac{\ell^2}{\mu_y}$
& $O\left(\frac{\ell^5}{\mu^2 \mu_y^4 \epsilon}\right)$
& $\widetilde{O}\left(\frac{(L+\ell)^2}{\mu^2 \mu_y\epsilon }\right)$
& $O\left(\frac{\ell^7}{\mu^2\mu_x \mu_y^5 \epsilon}\right)^*$
& $\widetilde{O}\left(\frac{(L+\ell)^2 \ell}{\mu^2\mu_x \mu_y\epsilon}\right)$ \\
\hline
\end{tabular}
\end{center}
\label{tab:compare_with_two_sided_PL}
\end{table}
\vspace*{-0.1in}
\section{Related Work}
\vspace*{-0.1in}
{\bf Nonconvex min-max optimization.}
Recently, there has been an increasing interest on nonconvex min-max optimization \cite{jin2019minmax,lin2018solving,lin2019gradient,liu2020towards,lu2019hybrid,nouiehed2019solving,rafique2018non,sanjabi2018solving}.
Below, we focus on related works on stochastic optimization for non-convex concave min-max problems.  Rafique et al.~\cite{rafique2018non} propose stochastic algorithms for solving non-smooth weakly-convex and concave problems based on a proximal point method \cite{rockafellar1976monotone}.
They established a convergence to a nearly stationary point of the primal objective function in the order of $O(1/\epsilon^6)$, where $\epsilon$ is the  level for the first-order stationarity. When the objective function is strongly concave in terms of $y$ and has certain special structure, they can reduce the iteration complexity to $O(1/\epsilon^4)$. The same order iteration complexity was achieved in~\cite{DBLP:journals/corr/abs-2002-05309} for weakly-convex strongly-concave problems without  a special structure of the objective function.  Lin et al.~\cite{lin2019gradient} analyzed  a single-loop stochastic gradient descent ascent method for smooth non-convex (strongly)-concave min-max problems. Their analysis yields an iteration complexity of $O(1/\epsilon^8)$ for smooth non-convex concave problems and  $O(1/\epsilon^4)$ for smooth non-convex strongly-concave problems. Improved first-order convergence for smooth finite-sum problems has been established by leveraging variance-reduction techniques  in~\cite{arXiv:2001.03724,rafique2018non}. However, none of these works explicitly use the PL condition to improve the convergence. Directly applying PL condition to the first-order convergence result leads to an iteration complexity worse than $O(1/\epsilon)$ for the objective gap.

{\bf PL Games.}  PL conditions have been considered in min-max games. For example, \cite{nouiehed2019solving} assumed that $h_x(y) = - f(x, y)$ satisfies PL condition for any $x$, which is referred to as {\bf $y$-side PL condition}. The authors utilize the condition to design deterministic multi-step gradient descent ascent method for finding a first-order stationary point. In contrast, we consider the objective is strongly concave in terms of $y$, which is stronger than $y$-side pointwise PL condition. Recently,  Liu et al.~\cite{liu2018fast} assume a PL condition for a NCSC formulation of deep AUC maximization, in which the PL condition is defined over the primal objective $P(x) = \max_{y\in Y}f(x, y)$, which is referred to as {\bf primal PL condition}. They established an iteration complexity  of $O(1/\epsilon)$ for the primal objective gap convergence only. However, their algorithm and analysis are not applicable to a general NCSC problem without a special structure. In contrast, our algorithm is more generic and simpler as well, and we derive stronger convergence result in terms of the duality gap. In addition, our analysis is based on a novel Lyapunov function that consists of the primal objective gap and the duality gap of a regularized function, which allows us to establish the convergence of both the primal objective gap and the duality gap.

 More recently,  \cite{yang2020global} considered a class of smooth non-convex non-concave problems, which satisfy both the $y$-side PL condition and $x$-side  PL condition~\footnote{We notice that the $x$-side PL condition can be replaced by the primal PL condition for their analysis.}.  They established a global convergence for a Lyapunov function $P(x_t) - P_* + \lambda (P(x_t) - f(x_t, y_t))$ for a constant $\lambda$, which directly implies the convergence for the primal objective gap. After some manipulation, we can also derive the convergence for the duality gap. This work is different from \cite{yang2020global} in several perspectives: (i) their algorithm is based on alternating gradient descent ascent method with polynomially decreasing or very small step sizes, in contrast our algorithm is based on  epoch-wise stochastic methods with geometrically decreasing step sizes. This feature makes our algorithm more amenable to deep learning applications, which allows us to achieve {\bf the state-of-the-art result on the validation data of the Stanford CheXpert competition} in terms of AUC measure; (ii) we make use of strong concavity of the objective function in terms of $y$ and develop stronger convergence results. In particular, our iteration complexities have better dependence on condition numbers.
We compare these convergence results  on both objective gap and duality gap in Table \ref{tab:compare_with_two_sided_PL}.

Finally, we note that there are a lot of research on deep learning to justify the PL condition.
PL condition of a risk minimization problem has been shown to hold globally or locally on some networks
with certain structures, activation or loss functions \cite{allen2018convergence,arora2018convergence,charles2017stability,du2018gradient,hardt2016identity,li2018learning,li2017convergence,zhou2017characterization}.
For example, in \cite{du2018gradient}, they have shown that if the width of a two layer neural network is sufficiently large, PL condition holds within a ball centered at the initial solution and the global optimum would lie in this ball.
\cite{allen2018convergence} further shows that in overparameterized deep neural networks with ReLU activation, PL condition holds for a global optimum around a random initial solution.

\vspace*{-0.1in}

\section{Preliminaries and Notations}
\vspace*{-0.1in}
We denote by $\|\cdot\|$ the Euclidean norm of a vector.

A function $h(x)$ is $\lambda$-strongly convex on $X$ if for any $x, x'\in X$, $\partial h(x')^{\top} (x-x') + \frac{\lambda}{2}\|x - x'\|^2 \leq h(x) - h(x')$.
A function $h(x)$ is $\rho$-weakly convex on $X$ if for any $x, x'\in X$,
$\partial h(x')^{\top} (x - x') - \frac{\rho}{2} \|x-x'\|^2 \leq h(x) - h(x')$. $h(x)$ is $L$-smooth if its gradient is $L$-Lipchitz continuous, i.e., $\|\nabla h(x) - \nabla h(x')\|\leq L\|x - x'\|, \forall x, x'\in X$. A $L$-smooth function is also a $L$-weakly convex function.  A smooth function $h(x)$ satisfies $\mu$-PL condition on $\R^d$, if for any $x\in \R^d$ there exists $\mu>0$ such that $\|\nabla h(x)\|^2\geq 2\mu(h(x) - h(x_*))$, where $x_*$ denotes a global minimum of $h$.

$(x_*, y_*)$ is called a saddle-point of a min-max game $\min_{x\in X}\max_{y\in Y}f(x, y)$ if it satisfies $f(x_*, y)\leq f(x_*, y_*)\leq f(x, y_*)$. $(x_*, y_*)$ is called a global minimax point of a min-max game $\min_{x\in X}\max_{y\in Y}f(x, y)$ if it satisfies $f(x_*, y)\leq f(x_*, y_*)\leq \max_{y\in Y}f(x, y)$.
For simplicity, we let $z= (x, y)^{\top}$, $Z=\R^d\times Y$, $F(z) = (\nabla_x f(x, y), - \nabla_y f(x, y))^{\top}$ and $\mathcal G(z;\xi) = (\nabla_x f(x, y; \xi), - \nabla_y f(x, y; \xi))^{\top}\in\R^{d+d'}$. We abuse the notations $\|z\|^2 = \|x\|^2 + \|y\|^2$ and $\|F(z) - F(z')\|^2 =\|\nabla_x f(x, y) - \nabla_x f(x', y')\|^2+ \|\nabla_y f(x, y)- \nabla_y f(x', y')\|^2 $. Let $P(x)=\max_{y\in Y}f(x, y)$.  The primal objective gap of a solution $x\in X$ is defined as $P(x) - \min_{x\in X}P(x)$. The duality gap of a solution $(x, y)$ is defined as $Gap(x, y) = \max_{y'\in Y}f(x, y') - \min_{x'\in X}f(x', y)$.
Below, we state some assumptions that will be used  in our analysis.
\begin{assumption}\label{ass1}
(i) $F$ is $\ell$-Lipchitz continuous, i.e., $\|F(z) - F(z')\| \leq \ell \|z - z'\|$, for any $z, z'\in Z$
(ii) $f(x, y)$ is $\mu_y$-strongly convex in $y$ for any $x$;
(iii) $P(x)=\max_{y\in Y}f(x, y)$ is $L$-smooth and has a non-empty optimal set.
(iv) there exists $(x_0, y_0)\in X\times Y$ and $\epsilon_0$ such that $Gap(x_0, y_0) \leq \epsilon_0$;
\end{assumption}
\vspace*{-0.1in}
{\bf Remark:} Assumption~\ref{ass1}(i) implies that $f(x,y)$ is $\ell$-smooth in terms of $x$ for any $y\in Y$.  Note that under Assumption~\ref{ass1}(i) and (ii), we can derive that $P(x)$ is $(\ell+\ell^2/\mu_y)$-smooth~\cite{lin2019gradient}. However, we note that the smoothness parameter $L$ could be much smaller than $(\ell+\ell^2/\mu_y)$, and hence we keep  dependence on $L$, $\ell$, $\mu_y$ explicitly.
For example, consider $f(x,y) = x^{\top}y - \frac{\mu_y}{2}\|y\|^2 -(\frac{1}{2\mu_y} - \frac{L}{2})\|x\|^2$, $Y=\R^{d'}$ with $L\ll 1\ll 1/\mu_y$. Then we can see that $F(z)$ is $\ell = (1+\frac{1}{\mu_y}  - L)$-Lipchitz continuous.
However, $P(x) =  \frac{L}{2}\|x\|^2$ is $L$-smooth function and $L$ could be much smaller than $\ell+\ell^2/\mu_y$.

The following assumption is assumed regarding the stochastic gradients unless specified otherwise.
\begin{assumption}\label{ass2}
There exists $\sigma>0$ such that $\E[\|\nabla_x f(x, y; \xi) - \nabla_x f(x, y)\|^2]\leq \sigma^2$ and $\E[\|\nabla_y f(x, y; \xi) - \nabla_y f(x, y)\|^2]\leq \sigma^2$.
\end{assumption}
\vspace*{-0.1in}{\bf Remark: } We can also impose a different (non-typical) assumption on stochastic gradients in order to use simple stochastic gradient update that is more interesting to practitioners, i.e., there exists $B>0$ such that  $\E[\|\nabla_x f(x, y; \xi)\|^2]\leq B^2$ and $\E[\|\nabla_y f(x, y; \xi)\|^2]\leq B^2$.

We use Assumption~\ref{ass3} for proving the convergence of the primal objective gap, and use Assumption~\ref{ass4} for proving the convergence of the duality gap.
\begin{assumption}\label{ass3}
$P(x) = \max\limits_{y\in Y} f(x, y)$ satisfies $\mu$-PL condition.
\end{assumption}
\begin{assumption}\label{ass4}
$h_y(x) = f(x, y)$ satisfies $x$-side $\mu_x$-PL condition for any $y\in Y$, i.e., $\|\nabla_x f(x, y)\|^2\geq 2\mu_x(f(x, y) - \min_x f(x,y))$, for any $x, y\in Y$.
\end{assumption}
It is not difficult to show that $\mu_x$-PL condition of $f(x,y)$ is weaker than $\mu$-PL condition of $P(x)$ under strong concavity of $f(x,y)$ in terms of $y$.
\begin{lemma}[\cite{yang2020global}]
If  $f(x, y)$ satisfies $x$-side $\mu_x$-PL condition on $\R^d$ and is strongly concave in $y$,  then $P(x)=\max_{y\in Y}f(x, y)$  satisfies $\mu$-PL condition for some $\mu\geq \mu_x$.
\label{lem:primal_PL}
\end{lemma}
We can also construct a function that does not obey $x$-side  $\mu_x$-PL condition but satisfies $\mu$-PL condition. Let us consider $f(x, y)= xy - \frac{1}{2}y^2 - \frac{1}{4}x^2$ and $Y=\R$. First, we show that $\mu_x$-PL condition does not hold. To this end, fix $y=1$, we can see that $|\nabla_x f(x, y)|^2 = (1-x/2)^2$, and $\min_{x\in X} f(x, 1) = \min_{x}x(1-x/4) -  \frac{1}{2}= - \infty$. Hence, for $x=2+\epsilon$, we have $|\nabla_x f(x, y)|^2=(\epsilon/2)^2$ and $f(x, 1) - \min_{x\in X} f(x, 1) =  \infty$. However, there exists no constant $\mu_x$ such that $|\nabla_x f(x, y)|^2\geq \mu_x(f(x, 1) - \min_{x\in X} f(x, 1))$ for $\epsilon\rightarrow 0$. Second, we show that $P(x)=\max_{y}f(x, y) = \frac{x^2}{4}$ satisfies $\mu$-PL condition with $\mu = 1/2$.
This argument together with Theorem~\ref{thm:1} implies that our result for the convergence of the primal objective gap only requires a weaker $\mu$-PL condition other than the $x$-side $\mu_x$-PL condition imposed in~\cite{yang2020global}.

In order to explore possibilities for deriving faster convergence, we could leverage the weak convexity of $f(x, y)$ in terms of $x$.
\begin{assumption}\label{ass5}
$f(x, y)$ is $\rho$-weakly convex in terms of $x$ for any $y\in Y$ with $0<\rho\leq \ell$.
\end{assumption}
\vspace*{-0.1in}For example, consider $f(x, y) = \ell x^{\top}y - \frac{\mu_y}{2}\|y\|^2 - \frac{\rho}{2}\|x\|^2$ with $\rho\leq  \ell$. Then $F(z)$ is $(\ell+\max(\rho,\mu_y))$-Lipchitz continuous. However, $f(x,y)$ is $\rho$-weakly convex in terms of $x$ for any $y$.

\vspace*{-0.1in}
\section{Algorithms and Main Results}
\vspace*{-0.1in}
Let $\Pi_{z_0}(\mathcal G)\in Z$ and $\Pi^r_{z_0}(\mathcal G)\in Z$ be defined as
\begin{align*}
\Pi_{\bar z}(\mathcal G) = \arg\min_{z\in Z} \mathcal G^{\top}z + \frac{1}{2}\|z - \bar z\|^2, \quad \Pi^{\gamma}_{\bar z, x_0}(\mathcal G) = \arg\min_{z\in Z} \mathcal G^{\top}z + \frac{1}{2}\|z - \bar z\|^2 + \frac{\gamma}{2}\|x - x_0\|^2.
\end{align*}

We present the proposed stochastic method in Algorithm~\ref{alg:main}. We would like to point out our method follows the proximal point framework analyzed in \cite{liu2019stochastic,rafique2018non,DBLP:journals/corr/abs-2002-05309}. In particular, the proposed method includes multiple consecutive epochs. In each epoch, we employ a stochastic algorithm to solve the  following proximal problem approximately:
\begin{align}
f_k(x, y) = f(x, y) + \frac{\gamma}{2} \|x - x_0\|^2,
\end{align}
where $\gamma$ is an appropriate regularization parameter to make $f_k$ to be strongly-convex and strongly concave.
The reference point $x_0$ is updated after each epoch, i.e., after each  inner loop.

However, there are some key differences between the proposed method from that are analyzed in ~\cite{liu2019stochastic,rafique2018non,DBLP:journals/corr/abs-2002-05309}. We highlight the differences below. First, our method explicitly leverage the PL condition of the objective function by decreasing $\eta_k, 1/T_k$ geometrically (e.g, $e^{-\alpha k}$ for some $\alpha>0$). In contrast, \cite{rafique2018non,DBLP:journals/corr/abs-2002-05309} proposed to decrease  $\eta_k, 1/T_k$ polynomially (e.g., $1/k$). Second, the restating point and the reference point $(x_{k-1}, y_{k-1})$ is simply the averaged solution of stochastic updates in our employed stochastic algorithm $\mathcal A$.  In contrast, \cite{liu2019stochastic,rafique2018non} assumed a special structure of the objective function and leverage its structure to compute a restarted solution for $y$. This makes our method much simpler to be implemented.

For stochastic algorithm $\mathcal A$, one can employ many stochastic primal-dual algorithms to solve $\min_{x}\max_{y}f_k(x,y)$. We consider three algorithms with different stochastic updates. Stochastic optimistic gradient descent ascent (OGDA) update (option I) yields an algorithm with provable convergence result that is more interesting to theoreticians, which was originated from stochastic mirror prox method proposed by~\cite{
juditsky2011solving}.  Stochastic gradient descent ascent (SGDA) update (option II) and adaptive stochastic gradient (AdaGrad) update (option III) are mostly interesting to practitioners.

\begin{algorithm}[t]
\caption {Proximal Epoch Stochastic Method: PES-$\mathcal A$}
\begin{algorithmic}[1]
\STATE{Initialization: $x_0\in \R^d, y_0 \in Y, \gamma, T_1, \eta_1$}
\FOR{$k=1,2, ..., K$}

\STATE{$x_0^k = x_{k-1}$, $y_0^k = y_{k-1}, f_k(x, y) = f (x, y) + \frac{\gamma}{2} \|x - x_0^k\|^2$}
\STATE{Option I \& III: $ (x_k, y_k)$ = $\mathcal A(f_k, x^k_0, y^k_0, \eta_k, T_k)$}
\STATE{Option II: $(x_k, y_k)$ = $\mathcal A(f, x^k_0, y^k_0, \eta_k, T_k, \gamma)$}
\STATE{\color{red}decrease $\eta_k$  geometrically by a constant factor, increase $T_k$ accordingly}
\ENDFOR
\STATE{Return $(x_K, y_K)$.}
\end{algorithmic}
\label{alg:main}
\end{algorithm}
\vspace*{-0.1in}
\begin{algorithm}[t]
\caption {Stochastic Algorithm $\mathcal A$
($f, x_0, y_0, \eta, T, \gamma$)}
\begin{algorithmic}
\STATE{Initialization:
$\tilde{z}_0 = z_0= (x_0, y_0) $}

\STATE Let $\{\xi_0, \xi_1,\ldots, \xi_T\}$
be independent random variables, let $ \mathcal G(z; \xi)$ be stochastic gradient of $f(z)$
\FOR{$t=1, ..., T$}

\STATE {Option I: \text{OGDA update:}} {$z_{t} = \Pi_{\tilde{z}_{t-1}}(\eta \mathcal G(z_{t-1}; \xi_{t-1})) $}, \quad {$\tilde z_{t} = \Pi_{\tilde{z}_{t-1}}(\eta \mathcal G(z_{t}; \xi_t)) $},
\STATE {Option II: \text{SGDA update:} $z_t = \Pi^{\gamma\eta}_{z_{t-1}, x_0}(\eta \mathcal G(z_{t-1}; \xi_{t-1})) $}

\STATE {Option III: \text{AdaGrad update:}} please refer to  Algorithm~\ref{alg:adagrad}
\ENDFOR
\RETURN{\color{red} $\bar{x} = \frac{1}{T}  \sum\limits_{t=1}^{T} x_t, \bar{y} = \frac{1}{T}  \sum\limits_{t=1}^{T} y_t$.}
\end{algorithmic}
\label{alg:subroutine}
\end{algorithm}

\subsection{Main Results}
\vspace*{-0.1in}

Below, we present our main convergence results of Algorithm~\ref{alg:main} by employing stochastic OGDA update. Let $\text{Gap}_k(x, y) = \max\limits_{y'\in Y} f(x, y')- \min\limits_{x'\in X} f(x', y)$ be the duality gap of $(x, y)$ on $f_k$.

\vspace*{-0.1in}
\begin{theorem}\label{thm:1}
Consider Algorithm \ref{alg:main} that uses Option I: OGDA update in subroutine Algorithm \ref{alg:subroutine}.
Suppose Assumption \ref{ass1}, \ref{ass2}, \ref{ass3}, \ref{ass5} hold.
Take $\gamma = 2\rho$ and
denote $\hat{L} = L + 2\rho$ and $c = 4\rho+\frac{248}{53} \hat{L} \in O(L + \rho)$.
Define $\Delta_k = P(x_0^k) - P(x_*) + \frac{8\hat{L}}{53c}\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-(k-1)\frac{2\mu}{c+2\mu})
\leq \frac{1}{2\sqrt{2}\ell}$, $T_k = \frac{212}{\eta_0 \min\{\rho, \mu_y\}}
\exp\left((k-1)\frac{2\mu}{c+2\mu}\right)$.
After $K \geq  \max\left\{\frac{c+2\mu}{2\mu}\log \frac{4\epsilon_0}{\epsilon},
\frac{c+2\mu}{2\mu} \log \frac{208\eta_0 \hat{L}K\sigma^2}{(c+2\mu)\epsilon} \right\}$ stages, we can have $\E[\Delta_{K+1}] \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left( \max\left\{\frac{\ell(L+\rho) \epsilon_0}{\mu\min\{\rho, \mu_y\} \epsilon},
\frac{(L + \rho)^2 \sigma^2} {\mu^2 \min\{\rho,\mu_y\} \epsilon} \right\} \right)$.
\label{thm:ogda_primal}

\end{theorem}
\vspace*{-0.1in}
\noindent\textbf{Remark. } This result would imply that it takes $\widetilde{O}\left(\frac{(L+\ell)^2}{\mu^2\mu_y \epsilon}\right)$ iterations to reach an $\epsilon$-level objective gap by setting $\rho=\ell$ (i.e., $f(x,y)$ is $\ell$-weakly convex in terms of $x$ under Assumption~\ref{ass1}).
With the worse-case value of $L=\ell + \frac{\ell^2}{\mu_y}$ (i.e.,  the $\ell$-smoothness of $f(x,y)$ and $\mu_y$-strongly concavity can imply the $\ell + \ell^2/\mu_y$-smoothness of $P(x)$~\cite{nouiehed2019solving}) , the total iteration complexity would be no greater than $\widetilde{O}\left(\frac{\ell^4}{\mu^2\mu^3_y \epsilon} \right)$. This is better than the iteration complexity of stochastic AGDA method in the order of ${O}\left(\frac{\ell^5}{\mu^2\mu^4_y \epsilon} \right)$~\cite{yang2020global}.

Note that the above result is achieved by analysis based on a novel Lyapunov function that consists of the primal objective gap $P(x_0^k) - P(x_*)$ and the duality gap of the proximal function $f_k(x, y)$. As a result, we can induce the convergence of duality gap of the original problem under Assumption~\ref{ass4}.

\begin{corollary} \label{cor:1}
Under the same setting as in Theorem \ref{thm:ogda_primal}, and suppose Assumption \ref{ass4} holds as well.
To achieve $\E[Gap(x_K, y_K)] \leq \epsilon$,
the total number of iteration is \\ $\widetilde{O}\left(\max\left\{\frac{(\rho/\mu_x+1)\ell(L+\rho)\epsilon_0}{\mu \min\{\rho, \mu_y\} \epsilon}, \frac{(\rho/\mu_x+1)(L + \rho)^2 \sigma^2}{\mu^2  \min\{\rho,\mu_y\}  \epsilon} \right\}\right)$.
\label{cor:ogda_duality}

\end{corollary}
\noindent\textbf{Remark. } Note that compared with the iteration complexity of the primal objective gap convergence, the iteration complexity of the duality gap convergence  is worse by a factor of $\rho/\mu_x+1$. When $f(x, y)$ is $\ell$-weakly convex with $\rho=\ell$, the iteration complexity for having $\epsilon$-level duality gap is  $\widetilde{O}\left(\frac{(L+\ell)^2\ell}{\mu^2\mu_x\mu_y \epsilon}\right)$, which reduces to  $\widetilde{O}\left(\frac{\ell^5}{\mu^2\mu_x\mu_y^3 \epsilon}\right)$ for the worst-case value of $L$. This result is better than the iteration complexity of stochastic AGDA method in the order of ${O}\left(\frac{\ell^7}{\mu^2\mu_x\mu_y^5 \epsilon} \right)$ that is derived by us based on the result  of~\cite{yang2020global} (c.f. Lemma~\ref{lem:agda} in the Supplement).  In addition, when $f(x,y)$ is $\rho$-weakly convex with $\mu_x<\rho<\mu_y$, the iteration complexity for having $\epsilon$-level duality gap is $\widetilde{O}\left(\frac{(L+\ell)^2}{\mu^2\mu_x \epsilon}\right)$.
Further, when $\rho<\mu_x$, we can set $\rho=\mu_x$ and then the iteration complexity for having $\epsilon$-level duality gap is $\widetilde{O}\left(\frac{(L+\ell)^2}{\mu^2\min\{\mu_x, \mu_y\} \epsilon}\right)$.
\vspace*{-0.1in}
\subsection{More Improvements}
\vspace*{-0.1in}
We can further improve the convergence result when $\rho$ is smaller than $O(\mu)$.
\begin{theorem}\label{thm:2}
Suppose Assumption \ref{ass1}, \ref{ass2}, \ref{ass3}, \ref{ass5} hold and $0<\rho \leq \frac{\mu}{8}$.
Take $\gamma = \frac{\mu}{4}$.
Define $\Delta_k = 475(P(x_0^k) - P(x_*)) + 57\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-\frac{k-1}{16}) \leq \frac{1}{2\sqrt{2}\ell}$, $T_k = \frac{384}{\eta_0 \min\{\mu/8, \mu_y\}}\exp\left(\frac{k-1}{16}\right)$.
After $K = \max\left\{16\log \frac{1200\epsilon_0}{\epsilon},
16\log \frac{15600\eta_0  K \sigma^2}{\epsilon} \right\}$ stages, we can have $\E[\Delta_{K+1}] \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left(\frac{ \max\{\ell \epsilon_0, \sigma^2\}}{\min\{\mu, \mu_y\}\epsilon} \right)$.
\label{thm:ogda_primal_rho<mu}

\end{theorem}

\begin{corollary}\label{cor:2}
Under the same setting as in Theorem \ref{thm:ogda_primal_rho<mu} and suppose Assumption \ref{ass4} holds as well.
To achieve $\E[\text{Gap}(x_K, y_K)] \leq \epsilon$,
the total number of iteration is $\widetilde{O}\left( \left(\frac{\mu}{\mu_x}+1\right)\frac{ \max\{\ell\epsilon_0,  \sigma^2\}}{\min\{\mu, \mu_y\}\epsilon} \right)$.
\label{cor:ogda_dual_rho<mu}

\end{corollary}

{\bf Remark: } Compared with results in Theorem~\ref{thm:1} and Corollary~\ref{cor:1}, the sample complexities in Theorem~\ref{thm:2} and Corollary~\ref{cor:2} have better dependence on $\mu, \mu_y$. In addition, by setting $\mu=\mu_x$, the rate in Corollary~\ref{thm:2} becomes $O(\frac{ 1}{\min\{\mu_x, \mu_y\}\epsilon} )$, which   matches that established in~\cite{DBLP:journals/corr/abs-2002-05309} for $\mu_x$-strongly convex and $\mu_y$-strongly concave problems. But we only require $x$-side $\mu_x$-PL condition  instead of $\mu_x$-strongly convex in terms of $x$.

Finally, we highlight the results of using SGDA and AdaGrad updates in $\mathcal A$.  The convergence results of using SGDA update are almost similar to the results presented above except that $\sigma^2$ is replaced by the upper bound $B^2$ of stochastic gradients, i.e., there exists $B>0$ such that  $\E[\|\nabla_x f(x, y; \xi)\|^2]\leq B^2$ and $\E[\|\nabla_y f(x, y; \xi)\|^2]\leq B^2$. This is a more restrictive assumption but holds in many practical applications~\cite{JMLR:v15:hazan14a,duchi2011adaptive}. The convergence results of using AdaGrad updates are  more interesting. In particular, the dependence on $1/\epsilon$ can be further reduced if the growth rate of the stochastic gradients is slow.

In particular, we have the following theorem regarding AdaGrad.

\begin{theorem}(Informal)
Suppose Assumption \ref{ass1},  \ref{ass3}, \ref{ass5} hold and define a constant $c = 4\rho + \frac{248}{53}\hat{L} \in O(L + \rho)$.
$g^k_{1:T_k}$ denotes the cumulative matrix of gradients in $k$-th epoch.
Suppose $\|g^k_{1:T_k, i}\|_2 \leq \delta T^{\alpha}_k$ and with $\alpha\in(0,1/2]$.

Then by setting parameters appropriately,

PES-AdaGrad has the total iteration complexity is
$\widetilde{O}\left( \left(
\frac{\delta^2 (L+\rho)^2 (d+d')}{\mu^2 \min\{\rho, \mu_y\} \epsilon}\right)^{\frac{1}{2(1-\alpha)}} \right)$ in order to have $\E[\Delta_{K+1}] \leq \epsilon$.
\label{thm:ada_primal}

\end{theorem}
\vspace*{-0.1in}
{\bf Remark: }  The improvements lies at when the stochastic gradient grows slowly, the sample complexity has a better dependence than $1/\epsilon$, i.e. $O(1/\epsilon^{1/(2(1-\alpha)})\leq O(1/\epsilon)$.  We present more results regarding duality gap in the supplement.

\begin{algorithm}[t]
\caption {Adagrad Min-Max($f, x_0, y_0, \eta, T$)}
\begin{algorithmic}

\STATE{$z_1 = (x_0, y_0), g_{1:0} = [~]$}
\FOR{$t=1, ..., T$}

\STATE{Update $g_{1:t} = [g_{1:t-1}, \G(z_t;\xi_t)], \text{~and~} s_{t, i} = \|g_{1:t, i}\|_2 $}
\STATE{Set $H_{t} = \delta I + \text{diag}(s_{t}), \psi_{t} (z) = \frac{1}{2}\langle z-z_0, H_{t}(z-z_0) \rangle$}
\STATE{$z_{t+1} = \arg\min\limits_{z\in Z} \eta z^T \left(  \frac{1}{t}\sum\limits_{\tau=1}^{t}\G(z_{\tau}; \xi_{\tau})\right)+ \frac{1}{t}\psi_{t} (z)$}
\ENDFOR

\end{algorithmic}
\label{alg:adagrad}
\end{algorithm}
\vspace*{-0.15in}
\section{Experiments}
\vspace*{-0.1in}

We first compare with several baselines on benchmark data. Then we present the results of our AUC maximization method on the CheXpert competition.

\begin{figure}[t]
\centering
\hspace{-0.1in}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_5_C2.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_71_C2.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_83_C2.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_91_C2.eps}

\hspace{-0.1in}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_5_C10.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_71_C10.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_83_C10.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_91_C10.eps}

\hspace{-0.1in}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_5_C100.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_71_C100.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_83_C100.eps}
\includegraphics[scale=0.22]{AUC/AUC_v2/auc_plot_p_0_91_C100.eps}

\vspace*{-0.1in}
\caption{Comparison of testing AUC on  Cat\&Dog, CIFAR10, CIFAR100.}
\label{fig:0}
\end{figure}
{\bf Comparison on Benchmark Data.} We compare our algorithms, PES-OGDA (Option I), PES-SGDA (Option II), PES-AdaGrad (Option III), for solving  the AUC maximization problem as in \cite{liu2019stochastic}, with five baseline methods, including stochastic gradient method (SGD) for solving a standard minimization formulation with cross-entropy loss, Stoc-AGDA \cite{yang2020global},  PGA (algorithm 1~\cite{rafique2018non}),  PPD-SG and PPD-AdaGrad~\cite{liu2019stochastic} for solving the same AUC maximization problem.
 We learn ResNet-20 \cite{he2016identity} with an ELU activation function.

For the parameter settings, we use a common stagewise stepsize for SGD, i.e., the initial stepsize is divided by 10 at 40K, 60K iteration.  For PPD-SG and PPD-AdaGrad, we follow the instructions in their works, i.e., $T_{s}=T_{0} 3^{k}, \eta_{s}=\eta_{0} / 3^{k}$ and $T_0, \eta_0$ and $\gamma$ are tuned in $[500 \sim 2000]$, $[0.1, 0.05, 0.01, 0.001]$, and $[100 \sim 2000]$, respectively. For Stoc-AGDA, the stepsize strategy follows $\frac{\tau_1}{\lambda+t} $, $\frac{\tau_2}{\lambda+t}$ for the dual and primal variables, respectively, where $\tau_1 \ll \tau_2$. The initial values $\tau_1, \tau_2$, $\lambda$ are tuned in $[1, 5, 10, 15]$, $[5, 10, 15, 20]$, and $[1e3, 1e4]$, respectively. For our methods, we adopt the same strategy as PPD-SG and PPD-AdaGrad to tune the  parameters, e.g., $T_0, \eta_0,$ \text{and} $\gamma$.

We conduct the experiments on three benchmark datasets i.e., Cat\&Dog (C2), CIFAR10 (C10), CIFAR100 (C100) which have 2, 10, 100 classes, respectively. To fit our task, we convert them into imbalanced datasets following the instructions in \cite{liu2019stochastic}. We firstly construct the binary dataset by splitting the original dataset into two portions with equal size (50\% positive: 50\% negative) and then we randomly remove $90\%, 80\%, 60\%$ data from negative samples on training data, which generate the imbalanced datasets with a positive:negative ratio of 91/9, 83/17, 71/29, respectively. We keep the testing data unchanged. We set the batch size to 128 for all datasets.

The testing AUC curve of all algorithms are reported in Figure \ref{fig:0}, where the sample complexity indicates the number of samples used in the training up to 80K iterations. From the results, we can see that SGD works better (or similar to) than AUC-based methods on the balanced data (50\%). However, PES-SGDA and PES-AdaGrad generally outperform  SGD when the data is imbalanced,  and outperforms PGA and Stoc-AGDA in almost all cases. In addition, the proposed methods performs similarly sometimes better than PPD-SG/PPD-AdaGrad except on C100 (91\% positive ratio).

This is not surprising since PPD-SG/PPD-AdaGrad are designed for AUC maximization under the same PL condition by leveraging its structure and extra data samples for computing a restarted dual solution. In contrast, our algorithms directly use averaged dual solution for restarting.  When the positive ratio is $91\%$ on C100, we observe that PPD-AdaGrad performs better than our algorithms,  showing that using the extra data samples may help in the extreme imbalanced cases. We also observe that the Stoc-AGDA performs worst in all cases with $O(\frac{1}{t})$ stepsize. For our methods, PES-SGDA and PES-AdaGrad perform generally better than PES-OGDA.

{\bf CheXpert Competition.} We also apply the proposed methods to a real-world application, \textbf{CheXpert competition}~\cite{irvin2019chexpert}, which aims to identify multiple lung and chest diseases. The dataset consists of over 200,000 chest X-rays images  of 65,240 patients, where each image is labeled  from a total of 14 labels denoting the presence of 14 common chest radiographic observations. For evaluation, only  5 selected diseases as shown in Table \ref{table:chexpert} are used~\cite{irvin2019chexpert}.

We first compare our AUC maximization method with the base networks trained by Adam for minimizing the cross-entropy loss. To this end, we train 5 base networks DenseNet121, DenseNet161, DensNet169, DensNet201, Inception-renset-v2 for each disease individually by Adam. We also use the unlabeled data with label smoothing for training the base models similar to~\cite{pham2019interpreting}.  Then we adopt the feature layers of these 5 base networks and add a classifier layer for AUC maximization, and train 5 networks  by our method PES-AdaGrad. In Table~\ref{table:chexpert} we show the results of AUC maximization and the base models trained by Adam for DenseNet121 and DenseNet 161. It shows that our AUC maximization method can improve AUC by 1\% on average. This is significant by considering that top 10 performers in the leaderboard only differ by $0.1\%$~\footnote{\url{https://stanfordmlgroup.github.io/competitions/chexpert/}}.

 Finally, we compare the ensemble model averaged over 5 neural networks by our AUC maximization method with the state-of-the-art result on CheXpert competition~\cite{pham2019interpreting}.

 It is notable that the current winner~\cite{pham2019interpreting} use all diseases and conditional training that incorporates the hierarchical   taxonomy of 14 diseases to train deep networks, and they use an ensemble of 6 networks. In contrast, we only use the 5 diseases and train deep networks for each disease separately without using the domain knowledge. The final results in Table~\ref{table:chexpert} show that our ensemble model by AUC maximization has a better validation AUC than the current winner, and also improves the ensemble of based models trained by Adam by 1\% on average. From the table, we also see that our method achieves the highest AUC on Edema, Consolidation, Atelectasis, competitive AUC on Pleural Effusion and slightly worse AUC on Cardiomegaly. On August 4, 2020, we submitted our models (\textbf{MaxAUC}) for evaluation on private testing set and the results ranks 35th on the CheXpert competition with an AUC of 0.922 on private testing set.

\begin{table}[t]
\caption{Comparison of AUC performance on Chexpert validation set. }

\centering
\scalebox{0.9}{
\begin{tabular}{lllllll}
\hline
Method & Cardiomegaly & Edema  & Consolidation & Atelectasis & Pleural E. & Mean   \\ \hline
DenseNet121-base   &0.891	&0.950	&0.951	&0.899	&0.950          & 0.928 \\
DenseNet121-MaxAUC   & 0.901        & 0.954  & 0.954        & 0.910       & 0.957          &  0.935  \\
\hline
DenseNet161-base   	&0.879	&0.950	&0.942	&0.897	&0.951          & 0.924  \\
DenseNet161-MaxAUC   & 0.895        & 0.953  & 0.954        & 0.901       & 0.956          & 0.932  \\
\hline

\#1 as of 06/03/2020~\cite{pham2019interpreting}   & \textbf{0.910}        & 0.958  & 0.957        & 0.909       & \textbf{0.964}          & 0.940  \\
{Ensemble (base)} & 0.898   & 0.956  & 0.960      & 0.906      & 0.936          & 0.936 \\
\textbf{Ensemble (MaxAUC)} & 0.907   & \textbf{0.965}  & \textbf{0.965}        & \textbf{0.920}       & 0.963          & \textbf{0.945} \\ \hline

\end{tabular}}
\label{table:chexpert}
\end{table}

\vspace*{-0.1in}
\section{Conclusion}
\vspace*{-0.1in}
In this paper, we have presented generic stochastic algorithms for solving non-convex and strongly concave min-max optimization problems.
We established convergence for both the objective gap and the duality gap under PL conditions of the objective function.  The experiments on deep AUC maximization have demonstrated the effectiveness of our methods.

\bibliography{reference}

\newpage
\appendix

\section{Convergence of Duality Gap by Stoc-AGDA Algorithm}
\vspace*{-0.1in}
To compare our algorithm with Stoc-AGDA in terms of convergence of duality gap, we derive the following lemma based on Theorem 3.3 of \cite{yang2020global}.
\begin{lemma}\label{lem:agda}
Supposes Assumption \ref{ass1}, \ref{ass3} hold.
Stoc-AGDA would reach a $\epsilon$-duality gap by an iteration complexity of  $O\left(\frac{\ell^7}{\mu^2\mu_x\mu_y^5\epsilon}\right)$.
\label{lem:implied_by_yang2020global}
\end{lemma}
\begin{proof}[Proof of Lemma   \ref{lem:implied_by_yang2020global}]
\cite{yang2020global} defines the measure as following potential function,
\begin{align}
\begin{split}
P_t = E[P(x_t) - P(x_*)] + \frac{1}{10} E[P(x_t) - f(x_t, y_t)].
\end{split}
\end{align}
By Theorem 3.3 of \cite{yang2020global}, in Stoc-AGDA, $P_t \leq \hat{\epsilon}$ after $O\left(\frac{\ell^5}{\mu^2 \mu_y^4  \hat{\epsilon}}\right)$ iterations.
Thus, it directly follows that the objective gap will be less than $\hat{\epsilon}$ after $O\left(\frac{\ell^5}{\mu^2 \mu_y^4 \hat{\epsilon}}\right)$ iterations,  i.e.,
\begin{align}
\begin{split}
P(x_t) - P(x_*) \leq P_t \leq \hat{\epsilon}.
\end{split}
\end{align}

Besides, we also have
\begin{align}
f(x_t, \hat{y}(x_t)) - f(x_t, y_t) = P(x_t) - f(x_t, y_t) \leq 10\hat{\epsilon}
\end{align}
after $O\left(\frac{l^5}{\mu^2 \mu_y^4 \hat{\epsilon}}\right)$ iterations.

By the $\mu_y$-strongly concavity of $f(x, \cdot)$, we have
\begin{align}
\begin{split}
\|y_t - \hat{y}(x_t)\|^2 \leq \frac{f(x_t, \hat{y}(x_t)) - f(x_t, y_t)}{2\mu_y} \leq \frac{5\hat{\epsilon}}{\mu_y}
\end{split}
\end{align}
and
\begin{align}
\begin{split}
\|\hat{y}(x_t) - y_*\|^2
&\leq \frac{f(x_t, \hat{y}(x_t)) - f(x_t, y_*)}{2\mu_y} \\
&\leq \frac{f(x_t, \hat{y}(x_t)) - f(x_*, y_*) + f(x_*, y_*) - f(x_t, y_*)}{2\mu_y} \\
&\leq \frac{f(x_t, \hat{y}(x_t)) - f(x_*, y_*)}{2\mu_y} \\
& = \frac{P(x_t) - P(x_*)}{2\mu_y} \leq \frac{\hat{\epsilon}}{2\mu_y}.
\end{split}
\end{align}

Thus,
\begin{align}
\begin{split}
\|y_t - y_*\|^2 \overset{(a)}{\leq} 2\|y_t - \hat{y}(x_t)\|^2 + 2\|\hat{y}(x_t) - y_*\|^2 \leq \frac{11\hat{\epsilon}}{\mu_y},
\end{split}
\end{align}
where $(a)$ holds since $\|\mathbf{a} - \mathbf{b}\|^2 = \|\mathbf{a} - \mathbf{c} + \mathbf{c} - \mathbf{b}\|^2 \leq 2\|\mathbf{a} - \mathbf{c}\|^2 + 2\|\mathbf{c} - \mathbf{b}\|^2$.

Since $f(\cdot, \cdot)$ is $l$-smooth and $f(\cdot, y)$ satisfies $\mu_x$-PL condition for any $y$, we know $D(y) = \min\limits_{x'} f(x', y)$ is smooth with coefficient $ \ell + \frac{\ell^2}{\mu_x} \leq \frac{2\ell^2}{\mu_x}$
\cite{nouiehed2019solving,yang2020global}.
Thus,
\begin{align}
\begin{split}
f(x_*, y_*) - f(\hat{x}(y_t), y_t)  = D(y_*) - D(y_t)
\leq \frac{2 \ell^2}{2\mu_x} \|y_t - y_*\|^2 \leq \frac{11\ell^2\hat{\epsilon}}{\mu_x\mu_y}.
\end{split}
\end{align}

Then we know the duality gap is
\begin{align}
\begin{split}
f(x_t, \hat{y}(x_t)) - f(\hat{x}(y_t), y_t)
&= f(x_t, \hat{y}(x_t)) - f(x_*, y_*) + f(x_*, y_*) - f(\hat{x}(y_t), y_t)  \\
&\leq \hat{\epsilon} + \frac{11\ell^2\hat{\epsilon}}{\mu_x \mu_y}.
\end{split}
\end{align}
To make the duality gap less than $\epsilon$, we need $\hat{\epsilon} \leq O\left(\frac{\mu_x \mu_y \epsilon}{\ell^2}\right)$.
Therefore, it takes $O\left(\frac{\ell^7}{\mu^2\mu_x\mu_y^5\epsilon}\right)$ iterations to have a $\epsilon$-duality gap for the Algorithm Stoc-AGDA that has been proposed in \cite{yang2020global}.
\end{proof}

\section{Convergence Analysis of Option II: SGDA}
We present the convergence rate of primal gap and duality gap if SGDA update is used in Algorithm \ref{alg:subroutine}.
Since the proof is similar to the version with Option I: OGDA
as update, we include the proof in later sections together with the version using OGDA update.

\begin{comment}
\begin{algorithm}[ht]
\caption {Gradient Descent Ascent (GDA)
($f, x_0, y_0, \eta, T, \gamma$)}
\begin{algorithmic}
\STATE{Intialization:}
\FOR{$t=1, ..., T$}
\STATE{Compute $\G_{x, t} = \partial_x f(x_t, y_t; \xi_t)$ and
$\G_{y, t} = \partial_y f(x_t, y_t; \xi_t)$ }
\STATE{$x_{t} = \arg\min\limits_{x\in X} x^{\top} \G_{x, t} + \frac{1}{2\eta}\|x - x_t\|^2 + \frac{\gamma}{2} \|x - x_0\|^2$,}
\STATE{$y_{t} = \arg\min\limits_{y\in Y} -y^{\top} \G_{y, t}
+ \frac{1}{2\eta} \|y-y_0\|^2$},
\ENDFOR
\RETURN{$\left(\bar{x} = \frac{1}{T}
\sum\limits_{t=1}^{T} x_t,
\bar{y} = \frac{1}{T}
\sum\limits_{t=1}^{T} y_t\right)$.}
\end{algorithmic}
\label{alg:GDA}
\end{algorithm}
\end{comment}

\begin{theorem}
Consider Algorithm \ref{alg:main} that uses Option I: SGDA update in subroutine Algorithm \ref{alg:subroutine}.
Suppose Assumption \ref{ass1}, \ref{ass3} \ref{ass5} hold.
Assume $\|\partial_x f(x, y; \xi)\|^2\leq B^2$ and $\|\partial_y f(x, y; \xi)\|^2\leq B^2$.
Take $\gamma = 2\rho$ and
denote $\hat{L} = L + 2\rho$ and $c = 4\rho+\frac{248}{53} \hat{L} \in O(L + \rho)$.
Define $\Delta_k = P(x_0^k) - P(x_*) + \frac{8\hat{L}}{53c}\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-(k-1)\frac{2\mu}{c+2\mu})\leq \frac{1}{\rho}$, $T_k = \frac{212 C_1}{\eta_0 \min\{\rho, \mu_y\}}\exp\left((k-1)\frac{2\mu}{c+2\mu}\right)$.
After $K = \max\left\{\frac{c+2\mu}{2\mu}\log \frac{4\epsilon_0}{\epsilon},
\frac{c+2\mu}{2\mu} \log \frac{80 \eta_0 \hat{L}KB_2}{(c+2\mu)\epsilon} \right\}$ stages, we can have $\Delta_{K+1} \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left(
\frac{(L + \rho)^2 B^2} {\mu^2 \min\{\rho,\mu_y\} \epsilon}\right)$.
\label{thm:gda_primal}
\end{theorem}

\begin{corollary}
Under the same setting as in Theorem \ref{thm:gda_primal} and suppose Assumption \ref{ass4} holds aw well.
To reach an $\epsilon$-duality gap, it takes a total iteration complexity of $\widetilde{O}\left(
\frac{(L + \rho)^2(\rho/\mu_x+1) B^2} {\mu^2 \min\{\rho,\mu_y\} \epsilon}\right)$.
\label{cor:gda_duality}
\end{corollary}

\begin{theorem}
Suppose Assumption \ref{ass1}, \ref{ass4}, \ref{ass5} hold and $0<\rho \leq \frac{\mu}{8}$.
Assume $\|\partial_x f(x, y; \xi)\|^2\leq B^2$ and $\|\partial_y f(x, y; \xi)\|^2\leq B^2$ .
Take $\gamma = 2\rho$.
Define $\Delta_k = 475(P(x_0^k) - P(x_*)) + 57\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-\frac{k-1}{16}) \leq \frac{1}{\rho}$, $T_k = \frac{768}{\eta_0 \min\{\mu/8, \mu_y\}}\exp\left(\frac{k-1}{16}\right)$.
After $K = \max\left\{16\log \frac{1200\epsilon_0}{\epsilon},
16\log \frac{6000\eta_0  K B^2}{\epsilon} \right\}$ stages, we can have $\Delta_{K+1} \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left( \frac{B^2}{\min\{\mu, \mu_y\} \epsilon}\right)$.
\label{thm:gda_primal_rho<mu}

\end{theorem}

\begin{corollary}
Under the same setting as in Theorem \ref{thm:gda_primal_rho<mu} and suppose Assumption \ref{ass4} holds as well.
To reach an $\epsilon$-duality gap, it takes total iteration complexity of
$\widetilde{O}\left(\frac{(\mu/\mu_x+1) B^2}{\min\{\mu, \mu_y\} \epsilon}\right)$.
\label{cor:gda_duality_rho<mu}

\end{corollary}

\section{One Epoch Analysis of OGDA}
We need the following lemmas from \cite{nemirovski2004prox}.
\begin{lemma}[Lemma 3.1 of \cite{nemirovski2004prox}]
\label{nemi2004_lemma3.1}
For $z_0 \in Z$, let $w_1 = \Pi_{z_0}(\zeta_1)$, $w_2 = \Pi_{z_0}(\zeta_2)$.
For any $z \in Z$,
\begin{align}
\begin{split}
\langle \zeta_2, w_1 - z \rangle \leq
\frac{1}{2} \|z-z_0\|^2 - \frac{1}{2}\|w_2 -z\|^2
- \frac{1}{2} \|w_1 - z_0\|^2 - \frac{1}{2} \|w_1 - w_2\|^2 + \|\zeta_1 - \zeta_2\|^2. \hfill
\end{split}
\end{align}
\end{lemma}

\begin{lemma}[Corollary 2 of \cite{juditsky2011solving}]
Let $\zeta_1, \zeta_2, ...$ be a sequence, we define a corresponding sequence $\{v_t \in Z \}_{t=0}^{T}$ as
\begin{align}
\begin{split}
v_t = P_{v_{t-1}; Z} (\zeta_{t}), v_0 \in Z,
\end{split}
\end{align}
we have for any $u \in Z$,
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T} \left\langle \zeta_t, v_{t-1}-u  \right\rangle \leq \frac{1}{2}\|v_0 - u\|^2 +  \frac{1}{2}\sum\limits_{t=1}^{T}\|\zeta_t\|^2.
\end{split}
\end{align}
\label{nemirovski:cor2}
\end{lemma}

Next we present the lemma that guarantees the converge of one call of Algorithm \ref{alg:subroutine} with Option I: OGDA update.
\begin{lemma}
\label{lem:ogda_sub}
Suppose $f(x, y)$ is convex-concave and Assumption \ref{ass2} holds.
By running Algorithm \ref{alg:subroutine} with OGDA update and input $(f, x_0, y_0, \eta\leq \frac{1}{4\sqrt{3}\ell}, T)$, we have
\begin{align}
\begin{split}
\E[f(\bar{x}, \hat{y}(\bar{x})) - f(\hat{x}(\bar{y}), \bar{y})]
&{\leq} \frac{1}{\eta T}\E(\|\hat{x}(\bar{y}) - x_{0}\|^2 + \|\hat{y}(\bar{x}) - y_{0}\|^2)
+ 13 \eta\sigma^2.
\end{split}
\end{align}
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:ogda_sub}]
Applying Lemma \ref{nemi2004_lemma3.1} with $z_0 = \Tilde{z}_{t-1}$,
$\zeta_1 = \eta \G(z_{t-1}; \xi_{t-1})$,
$\zeta_2 = \eta \G(z_t; \xi_t)$,
and accordingly $w_1 = z_t$, $w_2 = \tilde{z}_t$,
we get for any $z\in Z$,
\begin{align}
\begin{split}
\langle \G(z_t;\xi_t), z_t - z\rangle
\leq&  \frac{1}{2\eta} [\|z-\tilde{z}_{t-1}\|^2
- \|\Tilde{z}_t-z\|^2]
- \frac{1}{2\eta}[\|z_t - \Tilde{z}_{t-1}\|^2
+ \|z_t - \Tilde{z}_{t} \|^2 ]\\
& + \eta \|\G(z_{t-1}; \xi_{t-1}) - \G(z_t; \xi_t)\|^2
\end{split}
\end{align}

Taking average over $t = 1, ..., T$ and by the convexity of $f(x, y)$ in $x$,
we have for any $x \in X$,
\begin{align}
\begin{split}
\frac{1}{T} \sum\limits_{t=1}^{T} \langle \G(z_t;\xi_t),
z_t - z \rangle \leq &
\frac{\|z - \tilde{z}_0\|^2 }{2\eta T}
- \frac{1}{2\eta T} \sum\limits_{t=1}^{T} (\|z_t - \Tilde{z}_{t-1}\|^2
+ \|z_t - \Tilde{z}_t\|^2 ) \\
&
+ \frac{\eta}{T}\sum\limits_{t=1}^{T} \|\G(z_{t-1};\xi_{t-1}) - \G(z_t; \xi_t)\|^2 \\
\leq & \frac{\|z - z_0\|^2 }{2\eta T}
- \frac{1}{2\eta T} \sum\limits_{t=1}^{T} (\|z_t - \Tilde{z}_{t-1}\|^2
+ \|z_t - \Tilde{z}_t\|^2 )
+ \frac{3\eta }{T} \sum\limits_{t=1}^{T}
\|F(z_{t-1}) - F(z_t)\|^2  \\
& + \frac{3\eta }{T} \sum\limits_{t=1}^{T} ( \|\G(z_{t}; \xi_{t}) - F(z_t)\|^2
+ \|\G(z_{t-1};\xi_{t-1}) - F(z_{t-1})\|^2 )
\end{split}
\label{local:sgdae_grad_x_1}
\end{align}
where the last inequality is due to $\left\|\sum\limits_{k=1}^{K} \mathbf{a}_k\right\|^2 \leq K\sum\limits_{k=1}^{K}\left\|\mathbf{a}_k\right\|^2 $.

Note that
\begin{align}
\begin{split}
&\sum\limits_{t=1}^T (\|z_t - \Tilde{z}_{t-1}\|^2 + \|z_t - \Tilde{z}_t\|^2)
=\sum\limits_{t=0}^{T-1} \|z_{t+1} - \Tilde{z}_t\|^2
 + \sum\limits_{t=1}^T \|z_t - \Tilde{z}_t\|^2 \\
& = \sum\limits_{t=1}^{T-1} \|z_{t+1} - \Tilde{z}_t\|^2 + \|z_1 - \Tilde{z}_0\|^2
 + \sum\limits_{t=1}^{T-1} \|z_t - \Tilde{z}_t\|^2
 \geq \frac{1}{2}\sum\limits_{t=1}^{T-1} \|z_t - z_{t+1}\|^2 + \|z_1 - \Tilde{z}_0\|^2\\
& \geq \frac{1}{2}\sum\limits_{t=0}^{T-1} \|z_t - z_{t+1}\|^2
= \frac{1}{2}\sum\limits_{t=1}^{T} \|z_{t-1} - z_{t}\|^2
\end{split}
\label{local:yi_ineuqality_x}
\end{align}

By the $l$-smoothness of $f(x, y)$, we have
\begin{align}
\begin{split}
\|F(z_{t-1}) - F(z_t)\|^2 = &
\|\nabla_x f(x_t, y_t) - \nabla_x f(x_{t-1}, y_{t-1})\|^2
+ \|\nabla_y f(x_t, y_t) - \nabla_y f(x_{t-1},  y_{t-1})\|^2 \\
\leq &
2 \|\nabla_x f(x_t, y_t) - \nabla_x f(x_t, y_{t-1})\|^2 + 2\|\nabla_x f(x_t, y_{t-1}) - \nabla_x f(x_{t-1}, y_{t-1})\|^2\\
&+  2 \|\nabla_y f(x_t, y_t) - \nabla_y f(x_t, y_{t-1})\|^2 + 2\|\nabla_y f(x_t, y_{t-1}) - \nabla_y f(x_{t-1}, y_{t-1})\|^2 \\
\leq & 2l^2 \|y_t - y_{t-1}\|^2 + 2l^2 \|x_t - x_{t-1}\|^2 + 2l^2 \|y_t - y_{t-1}\|^2 + 2l^2 \|x_t - x_{t-1}\|^2 \\
= & 4l^2 \|z_{t-1} - z_{t}\|^2.
\end{split}
\end{align}

Denote $\Theta_{t} = F(z_t) - \G(z_t;\xi_t)$.
With the above two inequalities, (\ref{local:sgdae_grad_x_1}) becomes
\begin{align}
\begin{split}
& \frac{1}{T} \sum\limits_{t=1}^{T} \langle \G(z_t; \xi_t),
z_t - z \rangle\\
& \leq \frac{\|z - z_0\|^2 }{2\eta T}
- \frac{1}{4\eta T} \sum\limits_{t=1}^{T} \|z_{t-1} - z_t\|^2
+ \frac{12 \eta l^2}{ T} \sum\limits_{t=1}^{T} \|z_{t-1} - z_{t}\|^2
 + \frac{3\eta }{T} \sum\limits_{t=1}^{T} ( \|\Theta_{t}\|^2
+ \|\Theta_{t-1}\|^2 ) \\
&\leq \frac{\|z - z_0\|^2 }{2\eta T}
+ \frac{3\eta }{T} \sum\limits_{t=1}^{T} ( \|\Theta_{t}\|^2
+ \|\Theta_{t-1}\|^2 ) \\
\end{split}
\label{local:sgdae_grad_x_2}
\end{align}
where the last inequality holds because $\eta \leq \frac{1}{4\sqrt{3}l}$.

Define a virtual sequence $\{\hat{z}_t \in X\}_{t=0}^T$ as
\begin{align}
\begin{split}
\hat{z}_t = \Pi_{\hat{z}_{t-1}}(\eta\Theta_t),  \hat{z}_0 = z_0.
\end{split}
\end{align}
Applying Lemma \ref{nemirovski:cor2} with $\zeta_t =\eta \Theta_{t}= \eta( F(z_t) - \G(z_t; \xi_t)), v_t = \hat{z}_t$ and $u = z$, we have for any $z\in Z$,
\begin{align}
\begin{split}
\frac{1}{T} \sum\limits_{t=1}^T \langle \Theta_{t}, \hat{z}_{t-1} - z\rangle \leq \frac{1}{2\eta T} \|z_0 - z\|^2
+ \frac{\eta}{2T} \sum\limits_{t=1}^{T} \|\Theta_{t}\|^2.
\end{split}
\label{local:sgdae_grad_to_stoc_x}
\end{align}
Using (\ref{local:sgdae_grad_x_2}) and  (\ref{local:sgdae_grad_to_stoc_x}), we get
\begin{align}
\begin{split}
& \frac{1}{T} \sum\limits_{t=1}^T \langle F(z_t), z_t - z \rangle
=  \frac{1}{T} \sum\limits_{t=1}^T
[\langle\G(z_t; \xi_t), z_{t} - z\rangle \!
+ \langle \Theta_{t}, z_t - z\rangle]\\
& = \frac{1}{T} \sum\limits_{t=1}^T \langle\G(z_t; \xi_t), z_{t} - z\rangle \!
+ \frac{1}{T} \sum\limits_{t=1}^T  \langle\Theta_{t}, z_{t}\! -\! \hat{z}_{t-1}\rangle
 +\! \frac{1}{T} \sum\limits_{t=1}^T  \langle\Theta_{t}, \hat{z}_{t-1}\! - z\rangle  \\
& \leq \frac{1}{\eta T} \|z_0 - z\|^2
+ \frac{\eta}{T} \sum\limits_{t=1}^{T}  \left(\frac{7}{2}\|\Theta_{x, t}\|^2
+ 3\|\Theta_{x, t-1}\|^2 \right) +\! \frac{1}{T} \sum\limits_{t=1}^T \langle\Theta_{x,t}, x_{t}\! -\! \hat{x}_{t-1}\rangle
\end{split}
\label{local:sgdae_grad_x_before_expecation}
\end{align}

Note
\begin{align*}
\E[\langle\Theta_{t}, z_t - \hat{z}_{t-1} \rangle | z_t, \hat{z}_{t-1}, \Theta_{t-1}, ..., \Theta_{0}] = 0
\end{align*}
and by Assumption \ref{ass2}
\begin{align*}
\E[ \|\Theta_{t}\|^2|z_t,\tilde{z}_{t-1}, \Theta_{t-1}, ...,  \Theta_{0}] \leq 2\sigma^2.
\end{align*}
Thus, taking expectation on both sides of (\ref{local:sgdae_grad_x_before_expecation}), we get
\begin{small}
\begin{align}
\begin{split}
\E\left[\frac{1}{T} \sum\limits_{t=1}^T \langle F(z_t), z_{t} - z\rangle \right]
\leq& \frac{1}{\eta T} \E\left[ \|z_0 - z\|^2 \right]
+ 13\eta\sigma^2 .
\end{split}
\label{local:sgdae_grad_x}
\end{align}
\end{small}

By the fact $f(x, y)$ is convex-concave,
\begin{align}
\begin{split}
\E[f(\Bar{x}, y) - f(x, \Bar{y})] \leq & \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} (f(x_t, y) - f(x, y_t))\right] \\
=& \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} (f(x_t, y) - f(x_t, y_t) + f(x_t, y_t) - f(x, y_t))\right] \\
\leq & \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} (
\langle-\partial_y f(x_t, y_t), y_{t}\! -\! y\rangle  +
\langle\partial_x f(x_t, y_t), x_{t}\! -\! x\rangle
)\right] \\
= & \E\left[\frac{1}{T}\sum\limits_{t=1}^{T}\langle F(z_t), z_t - z\rangle\right]
\leq \frac{1}{\eta T}E[\|z_0 - z\|^2] + 13\eta \sigma^2.
\end{split}
\label{local:sgdae_grad_y}
\end{align}
Then we can conclude by plugging in $z = (x, y) = (\hat{x}(\bar{y}), \hat{y}(\bar{x}))$.
\end{proof}

\section{Proof of Theorem \ref{thm:ogda_primal} and  Theorem \ref{thm:gda_primal}}
Before we prove these two theorems, we first present two lemmas from \cite{yan2020sharp} and we introduce Theorem \ref{thm:appendix_unify_3} that unifies the proof of  Theorem \ref{thm:ogda_primal} and  Theorem \ref{thm:gda_primal}.

\begin{lemma} [Lemma 1 of \cite{yan2020sharp}]
Suppose a function $h(x, y)$ is $\lambda_1$-strongly convex in $x$ and $\lambda_2$-strongly concave in $y$.
Consider the following problem
\begin{align*}
\min\limits_{x\in X} \max\limits_{y\in Y} h(x, y),
\end{align*}
\label{lem:Yan1}
where $X$ and $Y$ are convex compact sets.
Denote $\hat{x}_h (y) = \arg\min\limits_{x'\in X} h(x', y)$
and $\hat{y}_h(x) = \arg\max\limits_{y' \in Y} h(x, y')$.
Suppose we have two solutions $(x_0, y_0)$ and $(x_1, y_1)$.
Then the following relation between variable distance and duality gap holds
\begin{align}
\begin{split}
\frac{\lambda_1}{4} \|\hat{x}_h(y_1)-x_0\|^2 + \frac{\lambda_2}{4}\|\hat{y}_h(x_1) - y_0\|^2 \leq&
\max\limits_{y' \in Y} h(x_0, y') - \min\limits_{x' \in X}h(x', y_0) \\
&+ \max\limits_{y' \in Y} h(x_1, y') - \min\limits_{x' \in X} h(x', y_1)
\end{split}
\end{align}
\end{lemma}

\begin{lemma}[Lemma 5 of \cite{yan2020sharp}]
We have the following lower bound for $\text{Gap}_k(x_k, y_k)$
\begin{align*}
\text{Gap}_k(x_k, y_k) \geq \frac{3}{50}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) + \frac{4}{5}(P(x_0^{k+1}) - P(x_0^k)),
\end{align*}
\label{lem:Yan5}
\end{lemma}
where $x_0^{k+1} = x_k$ and $y_0^{k+1} = y_k$.

We will introduce the following theorem that can unify the proof of Theorem \ref{thm:ogda_primal} and Theorem \ref{thm:gda_primal} since their have pretty similar forms of bounds in solving the subproblem.
\begin{theorem}
Suppose Assumption \ref{ass1} and Assumption  \ref{ass3} hold.
Assume we have a subroutine in the $k$-th epoch of Algorithm \ref{alg:main} that can return $x_k, y_k$ such that
\begin{align}
\begin{split}
\E[\text{Gap}_k(x_k, y_k)]
\leq \frac{C_1}{\eta_k T_k} \E[\|x - x_0^k\|^2 + \|y - y_0^k\|^2]
+ \eta_k C_2,
\end{split}
\label{equ:thm:appendix_unify_3_sub}
\end{align}
where $C_1$ and $C_2$ are constants corresponding to the specific subroutine.
Take $\gamma = 2\rho$ and
denote $\hat{L} = L + 2\rho$ and $c = 4\rho+\frac{248}{53} \hat{L} \in O(L + \rho)$.
Define $\Delta_k = P(x_0^k) - P(x_*) + \frac{8\hat{L}}{53c}\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-(k-1)\frac{2\mu}{c+2\mu})$, $T_k = \frac{212 C_1}{\eta_0 \min\{\rho, \mu_y\}}\exp\left((k-1)\frac{2\mu}{c+2\mu}\right)$.
After $K = \max\left\{\frac{c+2\mu}{2\mu}\log \frac{4\epsilon_0}{\epsilon},
\frac{c+2\mu}{2\mu} \log \frac{16\eta_0 \hat{L}KC_2}{(c+2\mu)\epsilon} \right\}$ stages, we can have $\Delta_{K+1} \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left(\max\left\{\frac{(L+\rho)C_1 \epsilon_0}{\eta_0 \mu\min\{\rho, \mu_y\} \epsilon},
\frac{(L + \rho)^2 C_2} {\mu^2 \min\{\rho,\mu_y\} \epsilon} \right\}\right)$.
\label{thm:appendix_unify_3}
\end{theorem}

\begin{proof}[Proof of Theorem \ref{thm:appendix_unify_3}]
Since $f(x, y)$ is $\rho$-weakly convex in $x$ for any $y$, $P(x) = \min\limits_{y'\in Y} f(x, y')$ is also $\rho$-weakly convex.
Taking $\gamma = 2\rho$, we have
\begin{align}
\begin{split}
P(x_{k-1}) &\geq P(x_k) + \langle \partial P(x_k), x_{k-1} - x_k\rangle - \frac{\rho}{2} \|x_{k-1} - x_k\|^2 \\
& = P(x_k) + \langle \partial P(x_k) + 2 \rho (x_k - x_{k-1}), x_{k-1} - x_k\rangle + \frac{3\rho}{2} \|x_{k-1} - x_k\|^2 \\
& \overset{(a)}{=} P(x_k) + \langle \partial P_k(x_k), x_{k-1} - x_k \rangle + \frac{3\rho}{2} \|x_{k-1} - x_k\|^2 \\
& \overset{(b)}{=}  P(x_k) - \frac{1}{2\rho} \langle \partial P_k(x_k), \partial P_k(x_k) - \partial P(x_k) \rangle + \frac{3}{8\rho} \|\partial P_k(x_k) - \partial P(x_k)\|^2 \\
& = P(x_k) - \frac{1}{8\rho} \|\partial P_k(x_k)\|^2
- \frac{1}{4\rho} \langle \partial P_k(x_k), \partial P(x_k)\rangle + \frac{3}{8\rho} \|\partial P(x_k)\|^2,
\end{split}
\label{local:P_weakly}
\end{align}
where $(a)$ and $(b)$ hold by the definition of $P_k(x)$.

Rearranging the terms in (\ref{local:P_weakly}) yields
\begin{align}
\begin{split}
P(x_k) - P(x_{k-1}) &\leq \frac{1}{8\rho} \|\partial P_k(x_k)\|^2 + \frac{1}{4\rho}\langle \partial P_k(x_k), \partial P(x_k)\rangle - \frac{3}{8\rho} \|\partial P(x_k)\|^2 \\
&\overset{(a)}{\leq} \frac{1}{8\rho} \|\partial P_k(x_k)\|^2
+ \frac{1}{8\rho} (\|\partial P_k(x_k)\|^2 + \|\partial P(x_k)\|^2) - \frac{3}{8\rho} \|P(x_k)\|^2 \\
& = \frac{1}{4\rho}\|\partial P_k(x_k)\|^2 - \frac{1}{4\rho}\|\partial P(x_k)\|^2\\
& \overset{(b)}{\leq} \frac{1}{4\rho} \|\partial P_k(x_k)\|^2 - \frac{\mu}{2\rho}(P(x_k) - P(x_*))
\end{split}
\end{align}
where $(a)$ holds by using $\langle \mathbf{a}, \mathbf{b}\rangle \leq \frac{1}{2}(\|\mathbf{a}\|^2 +  \|\mathbf{b}\|^2)$, and $(b)$ holds by the $\mu$-PL property of $P(x)$.

Thus, we have
\begin{align}
\left(4\rho+2\mu\right) (P(x_k) - P(x_*)) - 4\rho (P(x_{k-1}) - P(x_*)) \leq \|\partial P_k(x_k)\|^2.
\label{local:nemi_thm_partial_P_k_1}
\end{align}

Since $\gamma = 2\rho$, $f_k(x, y)$ is $\rho$-strongly convex in $x$ and $\mu_y$ strong concave in $y$.
Apply Lemma \ref{lem:Yan1} to $f_k$, we know that
\begin{align}
\frac{\rho}{4} \|\hat{x}_k(y_k) - x_0^k\|^2 + \frac{\mu_y}{4} \|\hat{y}_k(x_k) - y_0^k\|^2 \leq \text{Gap}_k(x_0^k, y_0^k) + \text{Gap}_k(x_k, y_k).
\end{align}

By the setting of $\eta_k = \eta_0  \exp\left(-(k-1)\frac{2\mu}{c+2\mu}\right)$, and
$T_k = \frac{212 C_1}{\eta_0 \min\{\rho, \mu_y\}} \exp  \left((k-1)\frac{2\mu}{c+2\mu}\right)$, we note that $\frac{C_1}{\eta_k T_k} \leq \frac{\min\{\rho,\mu_y\}}{212}$.
Applying (\ref{equ:thm:appendix_unify_3_sub}), we have
\begin{align}
\begin{split}
&\E[\text{Gap}_k(x_k, y_k)]
\leq \eta_k C_2
+ \frac{1}{53} \E\left[\frac{\rho}{4}\|\hat{x}_k(y_k) - x_0^k\|^2 + \frac{\mu_y}{4}\|\hat{y}_k(x_k) - y_0^k\|^2 \right]
\\
& \leq \eta_k C_2 + \frac{1}{53} \E\left[\text{Gap}_k(x_0^k, y_0^k) + \text{Gap}_k(x_k, y_k)\right].
\end{split}
\end{align}

Since $P(x)$ is $L$-smooth and $\gamma = 2\rho$, then $P_k(x)$ is $\hat{L} = (L+2\rho)$-smooth.
According to Theorem 2.1.5 of \cite{DBLP:books/sp/Nesterov04}, we have
\begin{align}
\begin{split}
& \E[\|\partial P_k(x_k)\|^2] \leq 2\hat{L}\E(P_k(x_k) - \min\limits_{x\in \mathbb{R}^{d}} P_k(x)) \leq 2\hat{L}\E[\text{Gap}_k(x_k, y_k)] \\
& = 2\hat{L}\E[4\text{Gap}_k(x_k, y_k) - 3\text{Gap}_k(x_k, y_k)] \\
&\leq 2\hat{L} \E \left[4\left(\eta_k C_2+  \frac{1}{53}\left(\text{Gap}_k(x_0^k, y_0^k) + \text{Gap}_k(x_k, y_k)\right)\right) - 3\text{Gap}_k(x_k,y_k)\right] \\
& = 2\hat{L} \E \left[4\eta_k C_2 +   \frac{4}{53}\text{Gap}_k(x_0^k, y_0^k) - \frac{155}{53}\text{Gap}_k(x_k, y_k)\right]
\end{split}
\label{local:nemi_thm_P_smooth}
\end{align}

Applying Lemma \ref{lem:Yan5} to  (\ref{local:nemi_thm_P_smooth}), we have
\begin{align}
\begin{split}
& \E[\|\partial P_k(x_k)\|^2] \leq 2\hat{L} \E \bigg[4\eta_k C_k + \frac{4}{53}\text{Gap}_k(x_0^k, y_0^k) \\
&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- \frac{155}{53} \left(\frac{3}{50} \text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) + \frac{4}{5} (P(x_0^{k+1}) - P(x_0^k))\right) \bigg] \\
& = 2\hat{L}\E \bigg[4\eta_k C_2 \!+ \! \frac{4}{53}\text{Gap}_k(x_0^k, y_0^k) \!-\! \frac{93}{530}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) \!-\!
\frac{124}{53} (P(x_0^{k+1}) - P(x_0^k)) \bigg].
\end{split}
\end{align}

Combining this with  (\ref{local:nemi_thm_partial_P_k_1}), rearranging the terms, and defining a constant $c = 4\rho + \frac{248}{53}\hat{L} \in O(L+\rho)$, we get
\begin{align}
\begin{split}
&\left(c + 2\mu\right)\E [P(x_0^{k+1}) - P(x_*)] + \frac{93}{265}\hat{L} \E[\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})] \\
&\leq \left(4\rho + \frac{248}{53} \hat{L}\right) \E[P(x_0^{k}) - P(x_*)]
+ \frac{8\hat{L}}{53} \E[\text{Gap}_k(x_0^k, y_0^k)]
+ 8 \eta_k \hat{L}C_2  \\
& \leq c \E\left[P(x_0^k) - P(x_*) + \frac{8\hat{L}}{53c} \text{Gap}_k(x_0^k, y_0^k)\right] + 8 \eta_k \hat{L}C_2
\end{split}
\end{align}

Using the fact that $\hat{L} \geq \mu$,
\begin{align}
\begin{split}
(c+2\mu) \frac{8\hat{L}}{53c} = \left(4\rho + \frac{248}{53}\hat{L} + 2\mu\right)\frac{8\hat{L}}{53(4\rho + \frac{248}{53}\hat{L})} \leq \frac{8\hat{L}}{53} + \frac{16\mu \hat{L}}{248\hat{L}} \leq \frac{93}{265} \hat{L}.
\end{split}
\end{align}

Then, we have
\begin{align}
\begin{split}
&(c+2\mu)\E \left[P(x_0^{k+1}) - P(x_*) + \frac{8\hat{L}}{53c}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})\right] \\
&\leq c \E \left[P(x_0^{k}) - P(x_*)
+  \frac{8\hat{L}}{53c}\text{Gap}_{k}(x_0^{k},  y_0^{k})\right]
+ 8 \eta_k \hat{L}C_2.
\end{split}
\end{align}

Defining $\Delta_k = P(x_0^{k}) - P(x_*) +  \frac{8\hat{L}}{53c}\text{Gap}_{k}(x_0^{k}, y_0^{k})$, then
\begin{align}
\begin{split}
&\E[\Delta_{k+1}] \leq \frac{c}{c+2\mu} \E[\Delta_{k}] +  \frac{8\eta_k \hat{L} C_2}{c+2\mu}
\end{split}
\end{align}

Using this inequality recursively, it yields
\begin{align}
\begin{split}
& E[\Delta_{K+1}] \leq \left(\frac{c}{c+2\mu}\right)^K E[\Delta_1]
+ \frac{8 \hat{L} C_2}{c+2\mu} \sum\limits_{k=1}^{K} \left(\eta_k \left(\frac{c}{c+2\mu}\right)^{K+1-k} \right)
\end{split}
\end{align}

By definition,
\begin{align}
\begin{split}
\Delta_1 &= P(x_0^1) - P(x^*) + \frac{8\hat{L}}{53c}\widehat{Gap}_1(x_0^1, y_0^1) \\
& = P(x_0) - P(x^*) + \left( f(x_0, \hat{y}_1(x_0)) +  \frac{\gamma}{2}\|x_0 - x_0\|^2 -  f(\hat{x}_1(y_0), y_0) - \frac{\gamma}{2}\|\hat{x}_1(y_0) - x_0\|^2 \right) \\
& \leq \epsilon_0 + f(x_0, \hat{y}_1(x_0)) - f(\hat{x}(y_0), y_0) \leq 2\epsilon_0.
\end{split}
\end{align}
Using inequality $1-x \leq \exp(-x)$,
we have
\begin{align*}
\begin{split}
&\E[\Delta_{K+1}] \leq \exp\left(\frac{-2\mu K}{c+2\mu}\right)\E[\Delta_1] + \frac{8 \eta_0 \hat{L} C_2} {c+2\mu}
\sum\limits_{k=1}^{K}\exp\left(-\frac{2\mu K}{c+2\mu}\right) \\
&\leq 2\epsilon_0 \exp\left(\frac{-2\mu K}{c+2\mu}\right)
+ \frac{8 \eta_0 \hat{L} C_2 }{c+2\mu}
K\exp\left(-\frac{2\mu K}{c+2\mu}\right)
\end{split}
\end{align*}

To make this less than $\epsilon$, it suffices to make
\begin{align}
\begin{split}
& 2\epsilon_0 \exp\left(\frac{-2\mu K}{c+2\mu}\right) \leq \frac{\epsilon}{2}\\
& \frac{8 \eta_0 \hat{L} C_2 }{c+2\mu}
K\exp\left(-\frac{2\mu K}{c+2\mu}\right) \leq \frac{\epsilon}{2}
\end{split}
\end{align}

Let $K$ be the smallest value such that $\exp\left(\frac{-2\mu K}{c+2\mu}\right) \leq \min \{ \frac{\epsilon}{4\epsilon_0},
\frac{(c+2\mu)\epsilon}{16 \eta_0 \hat{L} K C_2}\}$.
We can set $K = \max\bigg\{\frac{c+2\mu}{2\mu}\log \frac{4\epsilon_0}{\epsilon},
\frac{c+2\mu}{2\mu}\log \frac{16 \eta_0 \hat{L} K C_2} {(c+2\mu)\epsilon} \bigg\}$.

Then, the total iteration complexity is
\begin{align*}
\sum\limits_{k=1}^{K}T_k &\leq O\left( \frac{212 C_1}{\eta_0\min\{\rho,\mu_y\}}
\sum\limits_{k=1}^{K}\exp\left((k-1)\frac{2\mu}{c+2\mu}\right) \right)\\
& \leq O\bigg(\frac{212C_1}{\eta_0\min\{\rho,\mu_y\}}  \frac{\exp(K\frac{2\mu}{c+2\mu}) -  1}{\exp(\frac{2\mu}{c+2\mu})-1}  \bigg)\\
& \overset{(a)}{\leq} \widetilde{O}   \left(\frac{cC_1}{\eta_0\mu\min\{\rho,\mu_y\}}  \max\left\{\frac{\epsilon_0}{\epsilon},
\frac{\eta_0 \hat{L} K C_2}
{(c+2\mu)\epsilon} \right\}\right) \\
& \leq  \widetilde{O}\left(\max\left\{\frac{(L+\rho)C_1 \epsilon_0}{\eta_0 \mu\min\{\rho, \mu_y\} \epsilon},
\frac{(L + \rho)^2 C_2} {\mu^2 \min\{\rho,\mu_y\} \epsilon}\right\} \right)

\end{align*}
where $(a)$ uses the setting of $K$ and $\exp(x) - 1\geq x$, and $\widetilde{O}$ suppresses logarithmic factors.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:ogda_primal}]
With the above theorem, Theorem \ref{thm:ogda_primal} directly follows.
Noting Lemma \ref{lem:ogda_sub}, we can plug in $\eta_0 = \frac{1}{2\sqrt{2}l}$, $C_1 = 1$ and $C_2 = 13\sigma^2$ to Theorem \ref{thm:appendix_unify_3}.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:gda_primal}]
We need the following lemma to bound the convergence of the subproblem at each stage,

\begin{lemma}[Lemma 4 of \cite{yan2020sharp}]
Suppose Assumption \ref{ass1} holds, $\|\partial_x f(x_t, y_t; \xi_t)\|^2 \leq B^2$ and $\|\partial_y f(x_t, y_t; \xi_t)\|^2 \leq B^2$.
Set $\gamma = 2\rho$.
By running Algorithm \ref{alg:main} with Option II: SGDA, it holds  for $k\geq 1$,
\begin{align*}
\begin{split}
E[\text{Gap}_k(x_k, y_k)] \leq 5B^2 + \frac{1}{T_k}\bigg\{\left(\frac{1}{\eta_k} + \frac{\rho}{2} \right)E[\|\hat{x}_k(y_k) - x_0^k\|^2] + \frac{1}{\eta_k}E[\|\hat{y}_k(x_k) - y_0^k\|^2] \bigg\}.
\end{split}
\end{align*}
\label{lem:Yan4}
\end{lemma}

Using this lemma , we can set $\gamma = 2\rho$ and
$\eta_0 = \frac{1}{\rho}$.
Then it follows that
\begin{align*}
\begin{split}
E[\text{Gap}_k(x_k, y_k)] \leq 5\eta_k B^2
+
\frac{2}{\eta_k T_k} \left(E[\|\hat{x}_k(\bar{y}_k) - x_0^k\|^2] + E[\|\hat{y}_k(\bar{x}_k) - y_0^k\|^2\right).
\end{split}
\end{align*}

We can plug in $\eta_0 \leq \frac{1}{\rho}$,  $C_1 = 2$ and $C_2 = 5B^2 $ to Theorem \ref{thm:appendix_unify_3}.
And the conclusion follows.
\end{proof}

\section{Proof of Theorem \ref{thm:ogda_primal_rho<mu} and Theorem \ref{thm:gda_primal_rho<mu}}
We first present a lemma by plugging in Lemma 8 of \cite{yan2020sharp}.
And then we a theorem that can unify the proof of Theorem  \ref{thm:ogda_primal_rho<mu} and Theorem \ref{thm:gda_primal_rho<mu}.
In the last, we prove Theorem \ref{thm:ogda_primal_rho<mu} and Theorem \ref{thm:gda_primal_rho<mu}.

\begin{lemma}[Lemma 8 of \cite{yan2020sharp}]
Suppose $f(x, y)$ is $\frac{\mu}{8}$-weakly convex in $x$ for any $y$ and set $\gamma = \frac{\mu}{4}$.
Thus, $f_k(x, y)$ is $\frac{\mu}{8}$-strongly convex in $x$.
Then $\text{Gap}_k(x_k, y_k)$ can be lower bounded by the following inequalities
\begin{align}
\text{Gap}_k(x_k, y_k) \geq \left(3 - \frac{2}{\alpha}\right) \text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) - \frac{\mu \alpha}{8(1-\alpha)}\|x_0^{k+1} - x_0^{k}\|^2, (0<\alpha\leq 1)
\end{align}
and
\begin{align}
\text{Gap}_k(x_k, y_k) \geq P(x_0^{k+1}) - P(x_0^k) + \frac{\mu}{8} \|x_k-x_0^k\|^2, where ~ P(x) = \max\limits_{y' \in Y} f(x, y').
\end{align}
\label{lem:Yan8}
\end{lemma}

\begin{theorem}
Suppose $0<\rho \leq \frac{\mu}{8}$
and suppose Assumption \ref{ass1}, \ref{ass2}, \ref{ass3}, \ref{ass5} hold.
Assume we have a subroutine in the $k$-th epoch of Algorithm \ref{alg:main} that can return $x_k, y_k$ such that
\begin{align}
\begin{split}
\E[\text{Gap}_k(x_k, y_k)]
\leq \frac{C_1}{\eta_k T_k} \E[\|x - x_0^k\|^2 + \|y - y_0^k\|^2]
+ \eta_k C_2,
\end{split}
\label{equ:thm:appendix_unify_rho<mu_sub}
\end{align}
where $C_1$ and $C_2$ are constants corresponding to the specific subroutine.
Take $\gamma = \frac{\mu}{4}$.
Define $\Delta_k = 475(P(x_0^k) - P(x_*)) + 57\text{Gap}_k(x_0^k, y_0^k)$.
Then we can set $\eta_k = \eta_0  \exp(-\frac{k-1}{16}) \leq \frac{1}{2\sqrt{2}l}$, $T_k = \frac{384C_1}{\eta_0 \min\{\mu/8, \mu_y\}}\exp\left(\frac{k-1}{16}\right)$.
After $K = \max\left\{16\log \frac{1200\epsilon_0}{\epsilon},
16\log \frac{1200\eta_0  K C_2}{\epsilon} \right\}$ stages, we can have $\Delta_{K+1} \leq \epsilon$.
The total iteration complexity is
$\widetilde{O}\left(\max\left\{\frac{C_1 \epsilon_0}{\eta_0\min\{\mu, \mu_y\}\epsilon},  \frac{C_2}{\min\{\mu, \mu_y\} \epsilon}\right\}\right)$.
\label{thm:appendix_unify_rho<mu}
\end{theorem}

\begin{proof}[Proof of Theorem \ref{thm:appendix_unify_rho<mu}]
We have the following relation between $P(x_0^k) - P(x_*)$ and $\text{Gap}_k(x_0^k, y_0^k)$,
\begin{align}
\begin{split}
P(x_0^k) - P(x_*) &= f(x_0^k, \hat{y}(x_0^k)) - f(x_*, y_*) \leq f(x_0^k, \hat{y}(x_0^k)) - f(x_*, y_0^k) \\
&= f(x_0^k, \hat{y}(x_0^k)) + \frac{\gamma}{2}\|x_0^k - x_0^k\|^2 - f(x_*, y_0^k) - \frac{\gamma}{2}\|x_* - x_0^k\|^2 + \frac{\gamma}{2} \|x_* - x_0^k\|^2\\
&= f_k(x_0^k, y(x_0^k)) - f_k(x_*, y_0^k) + \frac{\gamma}{2}\|x_* - x_0^k\|^2 \\
& \leq \hat{f}_k(x_0^k, \hat{y}_k(x_0^k))
- f_k(\hat{x}_k(y_0^k), y_0^k) + \frac{\gamma}{2} \|x_* - x_0^k\|^2\\
&= \text{Gap}_k(x_0^k, y_0^k) + \frac{\gamma}{2}\|x_* - x_0^k\|^2\\
&\overset{(a)}{\leq} \text{Gap}_k(x_0^k, y_0^k)
+ \frac{\gamma}{4\mu}(P(x_0^k) - P(x_*))
\end{split}
\end{align}
where $(a)$ holds due to the $\mu$-PL condition of $P(x)$.
Since we take $\gamma = \frac{\mu}{4}$,  we know that $1 - \frac{\gamma}{4\mu} = \frac{15}{16}$.
Then it follows that
\begin{align}
P(x_0^k) - P(x_*) \leq \frac{16}{15}\text{Gap}_k(x_0^k, y_0^k).
\label{local:nemi_P_to_Gap_k}
\end{align}

Since $\rho < \frac{\mu}{8}$ and $\gamma = \frac{\mu}{4}$, we know that ${f}_k(x, y)$ is $\lambda_x = \frac{\mu}{8}$-strongly convex in $x$.
By the setting $\eta_k = \eta_0 \exp \left(-\frac{k-1}{16}\right), T_k = \frac{384C_1}{\eta_0\min\{\lambda_x, \mu_y\}}  \exp\left(\frac{k-1}{16}\right)\}$, we note that $\frac{C_1}{\eta_k T_k} \leq \frac{\min\{\lambda_x, \mu_y\}}{384}$.
Applying \ref{equ:thm:appendix_unify_rho<mu_sub}, we have

\begin{align}
\begin{split}
\E[\text{Gap}_k(x_k, y_k)] &{\leq}
\eta_k C_2
+ \frac{1}{96} \left(\frac{\lambda_x}{4}\E[\|\hat{x}_k(y_k)-x_0^k\|^2]
+ \frac{\mu_y}{4} \E[\|\hat{y}_k(x_k) - y_0^k\|^2] \right) \\
&{\leq} \eta_k C_2
+ \frac{1}{96}E[\text{Gap}_k(x_0^k, y_0^k)]
+ \frac{1}{96}E[\text{Gap}_k(x_k, y_k)]
\end{split}
\end{align}

where the last inequality follows from Lemma
\ref{lem:Yan1}.
Rearranging the terms, we have
\begin{align}
\begin{split}
\frac{95}{96} \E[\text{Gap}_k(x_k, y_k)]
\leq \eta_k C_2
+ \frac{1}{96}\E[\text{Gap}_k(x_0^k, y_0^k)] .
\end{split}
\label{local:nemi_hat_gap_k}
\end{align}
Since $\rho\leq \frac{\mu}{8}$, $f(x, y)$ is also $\frac{\mu}{8}$-weakly convex in $x$.
Then we use Lemma \ref{lem:Yan8} to lower bound the LHS of (\ref{local:nemi_hat_gap_k}) with $\alpha = \frac{5}{6}$,
\begin{align}
\begin{split}
&\frac{95}{96} \text{Gap}_k(x_k, y_k) =\frac{95}{576}\text{Gap}_k(x_k, y_k) + \frac{475}{576} \text{Gap}_k(x_k, y_k) \\
& \overset{(a)}{\geq} \frac{95}{576}\left(\frac{3}{5} \text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) -\frac{5}{8}\mu \|x_0^{k+1} - x_0^{k}\|^2\right) \\
&~~~~~~ + \frac{475}{576} (P(x_0^{k+1}) - P(x_*)) + \frac{475}{576}(P(x_*) - P(x_0^k)) + \frac{475}{576}\frac{\mu}{8}\|x_0^k - x_0^{k+1}\|^2\\
&= \frac{57}{576}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) + \frac{475}{576}(P(x_0^{k+1})-P(x^*)) \\
& ~~~~~~ - \frac{475}{576}\cdot \frac{15}{16}(P(x_0^k)-P(x_*)) - \frac{475}{576}\left(1-\frac{15}{16}\right)(P(x_0^k) - P(x^*)) \\
&\overset{(b)}{\geq} \frac{57}{576}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) + \frac{475}{576}(P(x_0^{k+1})-P(x_*)) \\
&~~~~~~ - \frac{475}{576}\cdot \frac{15}{16}(P(x_0^k)-P(x_*)) - \frac{475}{576}\cdot\frac{1}{15} \text{Gap}_k(x_0^k, y_0^k)
\end{split}
\label{local:nemi_LHS_hat_gap_k}
\end{align}
where $(a)$ uses Lemma \ref{lem:Yan8} and $(b)$ uses (\ref{local:nemi_P_to_Gap_k}).
Combining (\ref{local:nemi_hat_gap_k}) and (\ref{local:nemi_LHS_hat_gap_k}), we get
\begin{align}
\begin{split}
&\E\left[\frac{475}{576}(P(x_0^{k+1})-P(x_*)) +  \frac{57}{576}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) \right] \\
&\leq \E\left[ \eta_k C_2
+ \frac{475}{576}\cdot \frac{15}{16}(P(x_0^k)-P(x_*)) +  \frac{475}{576}\cdot\frac{1}{15} \text{Gap}_k(x_0^k, y_0^k)
+\frac{1}{96} \text{Gap}_k (x_0^k, y_0^k) \right]\\
&\leq \eta_k C_2
+ \frac{15}{16}\E\left[\frac{475}{576}(P(x_0^k)-P(x_*)) + \frac{57}{576}\text{Gap}_k (x_0^k, y_0^k) \right]
\end{split}
\end{align}
Defining $\Delta_k = 475(P(x_0^k)-P(x_*)) + 57\text{Gap}_k (x_0^k, y_0^k)$, we have
\begin{align}
\E[\Delta_{k+1}] \leq 600 \eta_k C_2
+ \frac{15}{16} \E[\Delta_k]
\leq \exp\left(-1/16\right)\E[\Delta_{k}] + 600 \eta_k C_2
\end{align}
and

\begin{align}
\begin{split}
\Delta_1 &= 475(P(x_0^1) - P(x_*)) + 57\text{Gap}_1(x_0^1, y_0^1) \\
& = 475(P(x_0) - P(x_*)) + 57\left( f(x_0, \hat{y}_1(x_0)) + \frac{\gamma}{2}\|x_0 - x_0\|^2 - f(\hat{x}_1(y_0), y_0) - \|\hat{x}_1(y_0) - x_0\|^2 \right) \\
& \leq 475\epsilon_0 + 57 \left( f(x_0, \hat{y}_1(x_0)) - f(\hat{x}(y_0), y_0) \right)  \leq 600 \epsilon_0 .
\end{split}
\end{align}

Thus,
\begin{align}
\begin{split}
\E[\Delta_{K+1}] &\leq \exp\left(-K/16\right)\Delta_1 + 600 C_2 \sum\limits_{k=1}^{K} \eta_k \exp\left(-(K+1-k)/(16)\right) \\
&= \exp\left(-K/16\right)\Delta_1 + 600C_2\sum\limits_{k=1}^{K} \left(\eta_0  \exp\left(-K/16\right)\right) \\
&\leq 600\epsilon_0 \exp\left(-K/16\right) + 600 \eta_0 C_2 K\exp\left(-K/16\right)
\end{split}
\end{align}

To make this less than $\epsilon$, we just need to make
\begin{align}
\begin{split}
& 600\epsilon_0 \exp\left(-K/16\right) \leq \frac{\epsilon}{2} \\
&600 \eta_0 C_2 K \exp\left(-K/16\right) \leq \frac{\epsilon}{2}
\end{split}
\end{align}
Let $K$ be the smallest value such that $\exp\left(\frac{-K}{16}\right) \leq  \min\{\frac{\epsilon}{1200\epsilon_0}, \frac{\epsilon}{1200\eta_0 C_2 K}\}$.
We can set $K = \max\left\{ 16\log\left(\frac{1200\epsilon_0}{\epsilon}\right) , 16\log\left(\frac{1200\eta_0
C_2 K}{ \epsilon}\right) \right\}$.

Then the total iteration complexity is
\begin{align}
\begin{split}
\sum\limits_{k=1}^{K} T_k
&\leq O\left(\frac{384 C_1}{\eta_0\min\{\lambda_x, \mu_y\}}  \sum\limits_{k=1}^{K} \exp\left(\frac{k-1}{16}\right) \right) \\
&\leq {O}\left( \frac{384C_1}{\eta_0 \min\{\lambda_x, \mu_y\}} \frac{\exp\left(\frac{K}{16}\right) - 1}{\exp\left(\frac{1}{16}\right) - 1}\right) \\
&\leq \widetilde{O}\left(\max\left\{\frac{C_1 \epsilon_0}{\eta_0\min\{\mu, \mu_y\}\epsilon},  \frac{KC_2}{\min\{\mu, \mu_y\} \epsilon}\right\}\right)\\
&\leq \widetilde{O}\left(\max\left\{\frac{C_1  \epsilon_0}{\eta_0\min\{\mu, \mu_y\}\epsilon},  \frac{C_2}{\min\{\mu, \mu_y\} \epsilon}\right\}\right)\\
\end{split}
\end{align}
\end{proof}
\vspace*{-0.3in}
\begin{proof}[Proof of Theorem \ref{thm:ogda_primal_rho<mu}]
Plugging in Theorem  \ref{thm:appendix_unify_rho<mu} with $\eta_0 = \frac{1}{2\sqrt{2}\ell}$, $C_1 = 1$ and $C_2 = 5B^2$, we get the conclusion.
\end{proof}
\vspace*{-0.25in}
\begin{proof}[Proof of Theorem \ref{thm:gda_primal_rho<mu}]
We can plug in $\eta_0 = \frac{1}{\rho}$,  $C_1 = 2$ and $C_2 = 5B^2 $ to Theorem \ref{thm:appendix_unify_3}.
And the conclusion follows.
\end{proof}
\vspace*{-0.1in}

\section{One Epoch Analysis of AdaGrad}
In this section, we analyze AdaGrad in solving the strongly convex-strongly concave problem.
Define $\|u\|_H = \sqrt{u^T H u}$, $\psi_0(z) = 0$, $\psi_{T}^{*}$ to be the conjugate of $\frac{1}{\eta} \psi_{T}$, i.e., $\psi_{t}^{*}(z) = \sup\limits_{z'\in Z} \{\langle z, z'\rangle - \frac{1}{\eta}\psi_{t}(z')\}$.

We first present a supporting lemma,
\begin{lemma}
For a sequence $\zeta_1, \zeta_2, ...$, define a sequence $\{u_t \in Z\}_{t=0}^{T+1}$ as
\begin{align}
\begin{split}
u_{t+1} = \arg\min\limits_{u\in X} \frac{\eta}{t} \sum\limits_{\tau=1}^{t} \langle \zeta_{\tau}, u\rangle +\frac{1}{t} \psi_{t}(u) , u_0 = z_0
\end{split}
\end{align}
where $\psi_{t}(\cdot)$ is the same as defined in Algorithm \ref{alg:adagrad}.
Then for any $u\in Z$,
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \zeta_{t} , u_t - u\rangle \leq \frac{1}{\eta}\psi_{T}(u) + \frac{\eta}{2} \sum\limits_{t=1}^{T}\|\zeta_{t}\|^2_{\psi_{t-1}^{*}}
\end{split}
\end{align}
\label{lem:ada_sequence}
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:ada_sequence}]
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T} \langle \zeta_{t}, u_t - u\rangle
& = \sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t \rangle
- \sum\limits_{t=1}^{T}\langle \zeta_{t}, u \rangle
- \frac{1}{\eta}\psi_{T}(u) + \frac{1}{\eta} \psi_{T}(u) \\
& \leq \frac{1}{\eta} \psi_{T} (x)
+ \sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t \rangle + \sup\limits_{u\in Z}
\bigg\{\left\langle -\sum\limits_{t=1}^{T} \zeta_{t}, u \right\rangle -\frac{1}{\eta} \psi_{T}(u) \bigg\}\\
& = \frac{1}{\eta} \psi_{T}(u)
+ \sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t \rangle
+ \psi_{T}^{*}
\left(-\sum\limits_{t=1}^{T} \zeta_{t}\right).
\end{split}
\label{local:ada_sequence_50}
\end{align}

Note that
\begin{small}
\begin{align}
\begin{split}
\psi_{T}^{*}\left(-\sum\limits_{t=1}^{T} \zeta_{t}\right)
& \overset{(a)}{=} \left\langle -\sum\limits_{t=1}^{T} \zeta_{t}, u_{T+1} \right\rangle
 - \frac{1}{\eta} \psi_{T} (u_{T+1})
 \overset{(b)}{\leq} \left\langle -\sum\limits_{t=1}^{T} \zeta_{t}, u_{T+1} \right\rangle
 - \frac{1}{\eta} \psi_{T-1} (u_{T+1}) \\
& \leq \sup\limits_{u\in Z}\bigg\{\left\langle -\sum\limits_{t=1}^{T}\zeta_{t}, u\right\rangle - \frac{1}{\eta}\psi_{T-1}(u)\bigg\}
= \psi_{T-1}^{*}\left(-\sum\limits_{t=1}^{T} \zeta_{t} \right) \\
& \overset{(c)}{\leq} \psi_{T-1}^{*}
\left(-\sum\limits_{t=1}^{T-1} \zeta_{t}\right)
+ \left\langle -\zeta_{T}, \nabla \psi^{*}_{T-1}
\left(-\sum\limits_{t=1}^{T-1} \zeta_{t}\right) \right\rangle + \frac{\eta}{2}\|\zeta_{T}\|^2_{\psi^{*}_{T-1}},
\end{split}
\label{local:ada_sequence_51}
\end{align}
\end{small}
where $(a)$ holds due to the updating rule, $(b)$ holds since $\psi_{t+1}(u)\geq \psi_t(u)$, $(c)$ uses the fact that $\psi_t(u)$ is 1-strongly convex w.r.t. $\|\cdot\|_{\psi_t} = \|\cdot\|_{H_t}$ and hence $\psi_{t}^{*}(\cdot)$
is $\eta$-smooth w.r.t. $\|\cdot\|_{\psi_{t}^*}=\|\cdot\|_{(H_{t})^{-1}}$.

Noting $\nabla \psi_{T-1}^{*}\left(-\sum\limits_{t=1}^{T-1}
\zeta_{t}\right) = u_{T}$ and adding $\sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t\rangle$ to both sides of (\ref{local:ada_sequence_51}),
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t \rangle + \psi_{T}^{*}
\left(-\sum\limits_{t=1}^{T} \zeta_{t}\right)
\leq \sum\limits_{t=1}^{T-1} \langle \zeta_{t} , u_t\rangle
+ \psi_{T-1}^{*}\left(-\sum\limits_{t=1}^{T-1} \zeta_{t}\right)
+ \frac{\eta}{2}\|\zeta_{T}\|^2_{\psi^{*}_{T-1}}
\end{split}
\label{local:ada_sequence_52}
\end{align}
Using (\ref{local:ada_sequence_52}) recursively and noting that $\psi_{0}(u) = 0$, we have
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \zeta_{t}, u_t\rangle + \psi_{x, T}^{*}\left(-\sum\limits_{t=1}^{T} \zeta_{t}\right) \leq \frac{\eta}{2} \sum\limits_{t=1}^{T} \|\zeta_{t}\|^2_{\psi_{t-1}^{*}}
\end{split}
\label{local:ada_sequence_53}
\end{align}

Combining (\ref{local:ada_sequence_50}) and (\ref{local:ada_sequence_53}), we have
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \zeta_{t} , u_t - u\rangle \leq \frac{1}{\eta}\psi_{T}(u) + \frac{\eta}{2} \sum\limits_{t=1}^{T}\|\zeta_{t}\|^2_{\psi_{t-1}^{*}}
\end{split}
\end{align}
\end{proof}

\begin{lemma}
Suppose $f(x, y)$ is convex-concave.
And also assume $\|\G_{t}\|_{\infty} \leq \delta$. \\
Set $T \geq M \max\{ \frac{\delta + \max_i \|g_{1:T, i}\|}{m},
m\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|\}$.
By running Algorithm \ref{alg:adagrad} with input ($f, x_0, y_0, \eta, T$), we have
\begin{align}
\begin{split}
E[\text{Gap}(\bar{x}, \bar{y})] &\leq  \frac{m}{\eta M}(\|z - z_0\|^2) + \frac{4 \eta}{m M}.
\end{split}
\end{align}
\label{lem:adagrad}
\end{lemma}
\begin{proof}
Applying Lemma \ref{lem:ada_sequence} with $\zeta_t = \G_{t}$ and $u_t = z_t$, for any $z\in Z$,
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \G_{t} , z_t - z\rangle \leq \frac{1}{\eta}\psi_{T}(z) + \frac{\eta}{2} \sum\limits_{t=1}^{T}\|\G_{t}\|^2_{\psi_{t-1}^{*}}
\end{split}
\end{align}

By Lemma 4 of \cite{duchi2011adaptive}, we know that $\sum\limits_{t=1}^{T}\|\G_{t}\|^2_{\psi_{t-1}^{*}} \leq 2\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|$.
Hence, for any $z \in Z$
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \G_{t} , z_t - z\rangle &\leq
\frac{1}{\eta} \psi_{T}(z) +
\eta\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|_2 \\
& = \frac{\delta \|z_0 - z\|^2}{2\eta} + \frac{\langle z_0 - z, \text{ diag }(s_{T})(z_0 - z) \rangle}{2\eta}
+\eta\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\| \\
& \leq \frac{\delta + \max_i \|g_{1:T, i}\|}{2\eta} \|z_0 - z\|^2 + \eta\sum\limits_{i=1}^{d+d'}
\|g_{1:T, i}\|
\end{split}
\label{local:first_part_55}
\end{align}

Then, we define the following auxiliary sequence $\{\hat{z}_t \in Z\}_{t=0}^{T}$,
\begin{align}
\begin{split}
\hat{z}_{t+1} = \arg\min\limits_{z\in Z} \frac{\eta}{t}\sum\limits_{\tau=1}^{t}
\langle F(z_t) - \G(z_t;\xi_t)), z \rangle
+ \frac{1}{t} \psi_{t}(z), \hat{z}_0 = z_0.
\end{split}
\end{align}

Denote $\Theta_{t} = F(z_t) - \G(z_t; \xi_t)$.
Applying Lemma \ref{lem:ada_sequence} with $\zeta_t = \Theta_{t}$ and $u_t = \hat{z}_t$,
we have
\begin{align}
\begin{split}
\sum\limits_{t=1}^{T}\langle \Theta_{t} , \hat{z}_t - z\rangle &\leq \frac{1}{\eta}\psi_{T}(z) + \frac{\eta}{2} \sum\limits_{t=1}^{T}\|\Theta_{t}\|^2_{\psi_{t-1}^{*}} \\
&\leq \frac{\delta + \max_i \|g_{1:T, i}\|}{2\eta} \|z_0 - z\|^2
+ \frac{\eta}{2} \sum\limits_{t=1}^{T}\|\Theta_{t}\|^2_{\psi_{t-1}^{*}}
\end{split}
\label{local:ada_aux_5}
\end{align}

To deal with the last term in the above inequality, we have in expectation that
\begin{align}
\begin{split}
&\E\left[\sum\limits_{t=1}^{T}\|\Theta_{t}\|^2_{\psi_{t-1}^{*}} \right]
= \sum\limits_{t=1}^{T} \E\left[\|\Theta_{t}\|^2_{\psi_{t-1}^{*}} \right] \\
&= \sum\limits_{t=1}^{T}  (\E\left[\|\G(z_t;\xi_t)\|^2_{\psi^*_{t-1}}\right] - \|F(z_t)\|_{\psi^*_{t-1}}^2) \\
&\leq \E\left[\sum\limits_{t=1}^{T}\|\G(z_t;\xi_t)\|^2_{\psi_{t-1}^{*}} \right]
\leq 2\E\left[\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\| \right],
\end{split}
\label{local:ada_V^2_to_E^2}
\end{align}
where the second equality uses the fact that $\E[\G(z_t;\xi_t)] = F(z_t)$ and the last inequality uses Lemma 4 of \cite{duchi2011adaptive}.

Thus,
\begin{align}
\begin{split}
& \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle F(z_t), z_t - z\rangle\right]
= \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \G(z_t;\xi_t), z_t - z\rangle\right] +
\E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \Theta_{t},  z_t - z\rangle\right] \\
& = \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \G(z_t;\xi_t), z_t - z\rangle\right] +
\E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \Theta_{t},  z_t - \hat{z}_t\rangle\right]
+ \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \Theta_{t},  \hat{z}_t - z\rangle\right] \\
& \overset{(a)}{\leq} E\left[\frac{\delta + \max_i \|g_{1:T, i}\|}{\eta T} \|z_0 - z\|^2\right] + 2\frac{\eta}{T} \E\left[\sum\limits_{i=1}^{d} \|g_{1:T, i}\| \right]
+ \E\left[\frac{1}{T}\sum\limits_{t=1}^{T} \langle \Theta_{t}, z_t - \hat{z}_t \rangle\right]\\
& = \E\left[\frac{\delta + \max_i \|g_{1:T, i}\|}{\eta T} \|z_0 - z\|^2\right] + 2\frac{\eta}{T} \E\left[\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\| \right]
\end{split}
\label{local:ada_grad_x}
\end{align}
where the last equality holds because $\E[\langle \Theta_{t}, z_t - \hat{z}_t\rangle| z_{t}, \hat{z}_t, \Theta_{t-1}, ..., \Theta_{0}] = 0$, and $(a)$ uses (\ref{local:first_part_55}), (\ref{local:ada_aux_5}) and (\ref{local:ada_V^2_to_E^2}).

Then for any $x\in X$ and $y\in Y$,
\begin{align}
\begin{split}
\E[f(\Bar{x}, y) - f(x, \Bar{y})] \leq &
\E\left[\frac{1}{T} \sum\limits_{t=1}^T (f(x_t, y) - f(x, y_t)) \right] \\
= & \E\left[\frac{1}{T} \sum\limits_{t=1}^T (f(x_t, y) - f(x_t, y_t) + f(x_t, y_t) - f(x, y_t))\right] \\
\leq & \E\left[\frac{1}{T} \sum\limits_{t=1}^T ( \langle - \partial_y f(x_t, y_t), y_t - y\rangle + \langle \partial_x f(x_t, y_t), x_t - x\rangle )\right] \\
=& \E \left[ \frac{1}{T}\sum\limits_{t=1}^{T} \langle F(z_t), z_t - z\rangle \right]\\
\overset{(a)}{\leq} & \E\left[\frac{\delta + \max_i \|g_{1:T, i}\|}{\eta T} \|z_0 - z\|^2\right] + 2\frac{\eta}{T} \E\left[\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\| \right] \\
\overset{(b)}{\leq} & \frac{m}{\eta M}\E[\|x_0 - x\|^2 + \|y_0 -y\|^2] + \frac{4 \eta}{m M}
\end{split}
\end{align}
where $(a)$ uses (\ref{local:ada_grad_x}), and the last inequality uses the setting that $T = M \max\left\{ \frac{\delta + \max_i \|g_{1:T, i}\|}{m},
m\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|
\right\}$.
Then we can conclude by plugging in $(x, y) = (\hat{x}(\bar{y}), \hat{y}(\bar{x}))$.
\end{proof}

Now we can prove the Theorem \ref{thm:ada_primal}.
\begin{proof}[Proof of Theorem \ref{thm:ada_primal}]
By analysis in proof of Theorem \ref{thm:ogda_primal}, we have the following inequalities that do not depend on the  optimization algorithm
\begin{align}
\begin{split}
\left(1+\frac{\mu}{2\rho}\right)(P(x_k) - P(x_*))
- (P(x_{k-1}) - P(x_*)) \leq \frac{1}{4\rho}\|\partial P_k(x_k)\|^2,
\end{split}
\label{local:ada:smooth_weakly}
\end{align}
\begin{align}
\begin{split}
\text{Gap}_k(x_k, y_k)
\geq \frac{3}{50}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})
+ \frac{4}{5}(P(x_0^{k+1}) - P(x_0^k))
\end{split}
\label{local:G:20_ada}
\end{align}
and
\begin{align}
\begin{split}
\frac{\rho}{4}\|\hat{x}_k(y_k) - x_0^k\|^2
+ \frac{\mu_y}{4} \|\hat{y}_k(x_k) - y_0^k\|^2
\leq \text{Gap}_k(x_0^k, y_0^k)
+ \text{Gap}_k(x_k, y_k).
\end{split}
\end{align}

Set $m = 1/\sqrt{d+d'}$, $\eta_k = \eta_0  \exp\left(-\frac{(k-1)}{2}\frac{2\mu}{c+2\mu}\right)$,
$M_k = \frac{212m }{\eta_0 \min\{\rho, \mu_y\}}
\exp\left( \frac{(k-1)}{2} \frac{2\mu}{c+2\mu}\right)$.
Note that,
\begin{align}
\begin{split}
T_k =& M_k \max\left\{ \frac{\delta + \max_i \|g_{1:T, i}\|}{m},
m\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|
\right\} \\
\leq& M_k \left\{ \frac{\delta + \delta T^{\alpha}}{m}, m(d+d') \delta T_k^{\alpha}\right\} \\
\leq & 2\sqrt{d+d'}\delta M_k T_k^{\alpha}
\end{split}

\end{align}
Thus, $T_k \leq (2\sqrt{d+d'}\delta M_k) ^{\frac{1}{1-\alpha}}$.

Noting $\frac{m}{\eta_k M_k} \leq \frac{\min\{\rho, \mu_y\}}{212}$, we can plug in Lemma \ref{lem:adagrad} as
\begin{align}
\begin{split}
\E[\text{Gap}_k({x}_k, {y}_k)] \leq
\E\left[\frac{4\eta_k}{m M_k}\right]
+ \frac{1}{53}\E\left[\text{Gap}_k(x_0^k, y_0^k)
+ \text{Gap}_k({x}_k, {y}_k) \right]
\end{split}
\end{align}

\begin{align}
\begin{split}
& \E[\|\partial P_k(x_k)\|^2] \leq 2\hat{L}\E[P_k(x_k) - \min\limits_{x\in \mathbb{R}^d}P_k(x)]
\leq 2\hat{L} \E[\text{Gap}_k(x_k, y_k)] \\
& = 2\hat{L}\E[4\text{Gap}_k(x_k, y_k)
    - 3\text{Gap}_k(x_k, y_k)] \\
& \leq 2\hat{L} \E\left[ 4\left(\frac{4\eta_k}{m M_k}
+ \frac{1}{53}\left(\text{Gap}_k(x_0^k, y_0^k)
+ \text{Gap}_k(x_k, y_k) \right) \right)
- 3\text{Gap}_k(x_k, y_k)\right] \\
& = 2\hat{L} \E \left[ 16 \frac{\eta_k}{m M_k}
+  \frac{4}{53}\text{Gap}_k(x_0^k, y_0^k)
- \frac{155}{53} \text{Gap}_k(x_k, y_k)
\right]\\
&\leq 2\hat{L} \E \left[ 16\frac{\eta_k}{m M_k} +  \frac{4}{53}\text{Gap}_k(x_0^k, y_0^k)
-  \frac{93}{530}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})
- \frac{124}{53}(P(x_0^{k+1}) - P(x_0^k)) \right],
\end{split}
\end{align}
where the last inequality uses (\ref{local:G:20_ada}).
Combining this with (\ref{local:ada:smooth_weakly}) and arranging terms, with a constant $c = 4\rho + \frac{248}{53}\hat{L}$, we have
\begin{align}
\begin{split}
& (c + 2\mu) \E[P(x_0^{k+1}) - P(x_*)]
+ \frac{93\hat{L}}{265}\E[\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})]
\\
&\leq c\E[ P(x_0^k) - P(x_*)] + \frac{8\hat{L}}{53}\E [\text{Gap}_k(x_0^k, y_0^k)] + \frac{32 \eta_k \hat{L}}{m M_k}
\end{split}
\end{align}
Then using the fact that $\hat{L} \geq \mu$, by similar analysis as in proof of Theorem \ref{thm:ogda_primal}, we have
\begin{align}
\begin{split}
&(c+2\mu)\E \left[P(x_0^{k+1}) - P(x_*) + \frac{8\hat{L}}{53c} \text{Gap}_{k+1}(x_0^k, y_0^k)\right] \\
&\leq c \E\left[P(x_0^k) - P(x_*)
+ \frac{8\hat{L}}{53c}\text{Gap}_k(x_0^k, y_0^k) \right]
+ \frac{32 \eta_k \hat{L}}{m M_k}  \\
\end{split}
\end{align}

Defining $\Delta_k = P(x_0^k) - P(x_*) + \frac{8\hat{L}}{53c}\text{Gap}_k(x_0^k, y_0^k)$, then
\begin{align}
\begin{split}
\E[\Delta_{k+1}] \leq \frac{c}{c+2\mu} \E[\Delta_k]
+ \frac{32 \eta_k \hat{L}}{(c+2\mu) m M_k}.
\end{split}
\end{align}

Noting $\Delta_1 \leq 2\epsilon_0$ and $(1-x) \leq \exp(-x)$,
\begin{align}
\begin{split}
\E [\Delta_{k+1}]  &\leq \left(\frac{c}{c+2\mu}\right)^K \E[\Delta_1 ]
+ \frac{32\hat{L}}{(c+2\mu)m}
\sum\limits_{k=1}^{K}\frac{\eta_k}{M_k} \left( \frac{c}{c+2\mu} \right)^{K+1-k}\\
& \leq 2\epsilon_0 \exp\left(\frac{-2\mu K}{c+2\mu}\right)
  + \frac{32\hat{L} \eta_0^2 \min(\rho, \mu_y)}{212m^2 (c+2\mu)} \sum\limits_{k=1}^{K}
  \exp\left((k-1) \frac{2\mu}{c+2\mu} \right)
  \exp\left(-\frac{2\mu (K+1-k)}{c+2\mu}\right) \\
& \leq 2\epsilon_0 \exp\left(\frac{-2\mu K}{c+2\mu}\right)
  + \frac{8\eta^2_0 \hat{L}\min(\rho, \mu_y)}{53m^2 (c+2\mu)} K   \exp\left(-\frac{2\mu K}{c+2\mu}\right)
\end{split}
\end{align}

To make this less than $\epsilon$, we just need to make
\begin{align}
\begin{split}
&2\epsilon_0 \exp\left(\frac{-2\mu K}{c+2\mu}\right)  \leq \frac{\epsilon}{2} \\
&\frac{8\eta^2_0 \hat{L}\min(\rho, \mu_y)}{53 m^2 (c+2\mu)} K
\exp\left(-\frac{2\mu K}{c+2\mu}\right)  \leq \frac{\epsilon}{2}.
\end{split}
\end{align}
Let $K$ be the smallest value such that
$\exp\left(\frac{-2\mu K}{c+2\mu}\right) \leq \min\{\frac{\epsilon}{4\epsilon_0},
\frac{53 m^2 (c+2\mu)\epsilon}{16\eta_0^2
\hat{L}\min(\rho, \mu_y)K}
\}$.
We can set $K = \max \left\{ \frac{c+2\mu}{2\mu}\log\left(\frac{4\epsilon_0}{\epsilon}\right),
\frac{c+2\mu}{2\mu} \log \left(\frac{16\eta^2_0 \hat{L}
\min(\rho , \mu_y) K}{53 m^2 (c+2\mu)\epsilon}\right)
\right\}$.

Recall
\begin{align}
\begin{split}
T_k \leq (2 \sqrt{d+d'} \delta M_k)^{\frac{1}{1-\alpha}}
\leq \left[
\frac{424 \delta}{\eta_0 \min\{\rho, \mu_y\}}\exp\left(\frac{(k-1)}{2} \frac{2\mu}{c+2\mu}\right)\right]^{\frac{1}{1-\alpha}}
\end{split}
\end{align}

Then the total number of iteration complexity is
\begin{align}
\begin{split}
\sum\limits_{k=1}^{K} T_k &\leq {O}
\left( \sum\limits_{k=1}^{K}
\left[\frac{\delta}{\eta_0
\min\{\rho, \mu_y\}} \exp\left(\frac{(k-1)}{2} \frac{2\mu}{c+2\mu}\right) \right]^{\frac{1}{1-\alpha}} \right) \\
&\leq {O} \left( \sum\limits_{k=1}^{K}
\left(\frac{\delta}{\eta_0 \min\{\rho, \mu_y\}}\right)^{\frac{1}{1-\alpha}} \exp\left(\frac{k-1}{2(1-\alpha)} \frac{2\mu}{c+2\mu}\right) \right)\\
& \leq {O} \left(
\left(\frac{\delta}{\eta_0 \min\{\rho, \mu_y\}}\right)^{\frac{1}{1-\alpha}}
\frac{\exp\left(K\frac{2\mu}{2(1-\alpha)(c+2\mu)} - 1\right)} {\exp\left(\frac{2\mu}{2(1-\alpha)(c+2\mu)}\right) - 1} \right)\\
& \overset{(a)}{\leq}  {O} \left(
\left(\frac{\delta}{\eta_0 \min\{\rho, \mu_y\}}\right)^{\frac{1}{1-\alpha}}
\left(\frac{c+2\mu}{2\mu}\right)^{\frac{1}{2(1-\alpha)}}
\left(\max\left\{\frac{4\epsilon_0}{\epsilon}, \frac{16\eta_0^2 \hat{L} \min(\rho, \mu_y) K}
{53\epsilon m^2 ( c+\mu)} \right\}\right)^{\frac{1}{2(1-\alpha)}}
\right) \\
&\leq \widetilde{O}\left( \left(\max\left\{
\frac{\delta^2c}{\eta_0^2\mu(\min\{\rho, \mu_y\})^2},
\frac{\delta^2 \hat{L}c (d+d')}{\mu^2 \min\{\rho, \mu_y\} \epsilon} \right\} \right)^{\frac{1}{2(1-\alpha)}} \right) \\
&\leq \widetilde{O}\left( \left(
\frac{\delta^2 (L+\rho)^2 (d+d')}{\mu^2 \min\{\rho, \mu_y\} \epsilon} \right)^{\frac{1}{2(1-\alpha)}} \right) \\
\end{split}
\end{align}

where $(a)$ uses the inequality that $\exp(ax) - 1 \geq x^a$ for any $0< a <1$ and $x > 0$, noting that $0< \frac{2\mu}{c+2\mu} < 1$ and $\frac{1}{2(1-\alpha)} > 0$.
\end{proof}

\section{More Analysis on Option III: AdaGrad}
We have already shown in Theorem \ref{thm:ada_primal} about the convergence of primal gap for our Algorithm with Option III: Adagrad update.
In this section, we show a corollary about the convergence of duality gap based on Theorem \ref{thm:ada_primal}.
What is more, in parallel with our analysis on Option I: OGDA update, we show some convergence results under the condition that $\rho\leq \frac{\mu}{8}$.

\begin{corollary}
Under same setting as in Theorem \ref{thm:ada_primal} and suppose Assumption \ref{ass4} holds as well.
To reach an $\epsilon$-duality gap, the total iteration duality gap is $\widetilde{O}\left(\left(\frac{\rho}{\mu_x}+1\right)   \left(
\frac{\delta^2 (L+\rho)^2 (d+d')}{\mu^2 \min\{\rho, \mu_y\} \epsilon}\right)^{\frac{1}{2(1-\alpha)}}
\right)$.
\label{cor:ada_dual}
\end{corollary}

\begin{theorem}
Suppose Assumption \ref{ass1},  \ref{ass4}, \ref{ass5} hold and $\rho\leq \frac{\mu}{8}$.
Define a constant $c = 4\rho + \frac{248}{53}\hat{L} \in O(L + \rho)$.
$g^k_{1:T_k}$ denotes the cumulative matrix of gradients $g_{1:T}$ in $k$-th epoch.
Suppose $\|g^k_{1:T_k, i}\|_2 \leq \delta T^{\alpha}_k$ and with $\alpha\in(0,1/2]$.

Then by setting $\gamma = 2\rho$, $m = 1\sqrt{d+d'}$, $\eta_k = 2\eta_0 \exp\left(-\frac{(k-1)}{2}\frac{2\mu}{c+2\mu}\right)$,  $M_k = \frac{212m}{\eta_0 \min(\ell, \mu_y)} \exp\left(\frac{k-1}{2}\frac{2\mu}{c+2\mu}\right)$, and $T_k = M_k \max\left\{\frac{\delta + \max_i\|g^k_{1:\tau, i}\|_2}{2m}, m\sum\limits_{i=1}^{d+d'}\|g^k_{1:\tau, i}\|_i \right\}$, and after $K = \max \left\{ \frac{c+2\mu}{2\mu}\log\left(\frac{4\epsilon_0}{\epsilon}\right),
\frac{c+2\mu}{2\mu} \log \left(\frac{16\eta^2_0 \hat{L}
\min(\rho, \mu_y) K}{53 m^2(c+2\mu)\epsilon}\right)
\right\}$ stages, we have
$\Tilde{O}\left( \left(
\frac{\delta^2 (d+d') }{\min\{\mu, \mu_y\} \epsilon}
\right)^{\frac{1}{2(1-\alpha)}} \right)$.
\label{thm:ada_primal_rho<mu}
\end{theorem}

\begin{corollary}
Under same setting as in Theorem \ref{thm:ada_primal_rho<mu} and suppose Assumption \ref{ass4} holds as well.
To reach an $\epsilon$-duality gap, the total iteration duality gap is
$\Tilde{O}\left( \left(\frac{\mu}{\mu_x}+1\right)\left(
\frac{\delta^2 (d+d') }{\min\{\mu, \mu_y\} \epsilon}
\right)^{\frac{1}{2(1-\alpha)}} \right)$.
\label{cor:ada_dual_rho<mu}
\end{corollary}

\section{Proof of Theorem \ref{thm:ada_primal_rho<mu}}
\begin{proof}[Proof of Theorem \ref{thm:ada_primal_rho<mu} ]
By analysis in the Proof of Theorem  \ref{thm:ogda_primal_rho<mu}, we know that when $\rho < \frac{\mu}{8}$ and $\gamma = \frac{\mu}{4}$,
\begin{align}
\begin{split}
P(x_0^k) - P(x_*) \leq \frac{16}{15}\text{Gap}_k(x_0^k, y_0^k).
\end{split}
\end{align}
and ${f}_k(x, y)$ is $\lambda_x = \frac{\mu}{8}$-strongly convex in $x$.

Set $m = 1/\sqrt{d+d'}$, $\eta_k = \eta_0  \exp\left(-\frac{(k-1)}{32}\right)$,
$M_k = \frac{384 m }{\eta_0 \min\{\lambda_x, \mu_y\}}
\exp\left( \frac{(k-1)}{32} \right)$.
Note that,
\begin{align}
\begin{split}
T_k =& M_k \max\left\{ \frac{\delta + \max_i \|g_{1:T, i}\|}{m},
m\sum\limits_{i=1}^{d+d'} \|g_{1:T, i}\|
\right\} \\
\leq& M_k \left\{ \frac{\delta + \delta T^{\alpha}}{m}, m(d+d') \delta T_k^{\alpha}\right\} \\
\leq & 2\sqrt{d+d'} \delta M_k T_k^{\alpha}
\end{split}

\end{align}
Thus, $T_k \leq (2\sqrt{d+d'} \delta M_k) ^{\frac{1}{1-\alpha}}$.

Since $\frac{m}{\eta_k M_k} \leq \frac{\min\{\lambda_x, \mu_y\}}{384}$, we can apply Lemma \ref{lem:adagrad} to get
\begin{align}
\begin{split}
\E[\text{Gap}_k(x_k, y_k)] &\leq \frac{4\eta_k}{m M_k}
+ \frac{1}{96} \left(\frac{\lambda_x}{4}\E[\|\hat{x}_k(y_k) - x_0^k\|^2] + \frac{\mu_y}{4}\E[\|\hat{y}_k(x_k) - y_0^k\|^2]\right) \\
&\leq \frac{4\eta_k}{m M_k}
+ \frac{1}{96} \E[\text{Gap}_k(x_0^k, y_0^k)]
+ \frac{1}{96} \E[\text{Gap}_k(x_k, y_k)],
\end{split}
\end{align}
where the last inequality follows from Lemma \ref{lem:Yan1}. Rearranging terms, we have
\begin{align}
\begin{split}
\frac{95}{96} \E[\text{Gap}_k (x_k, y_k)]
\leq \frac{4\eta_k}{m M_k}
+ \frac{1}{96} \E[\text{Gap}_k(x_0^k, y_0^k)].
\end{split}
\label{local:ada_rho<mu_gap_1}
\end{align}

Since $\rho \leq \frac{\mu}{8}$, $f(x, y)$ is also  $\frac{\mu}{8}$-weakly convex in $x$.
Then, similar to the analysis in proof of Theorem \ref{thm:ogda_primal_rho<mu}, we use Lemma \ref{lem:Yan8} to lower bound the LHS of
(\ref{local:ada_rho<mu_gap_1}) with $\alpha = \frac{5}{6}$,
\begin{align}
\begin{split}
\frac{95}{96} \text{Gap}_k(x_k, y_k) \geq&
\frac{57}{576}\text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1})
+ \frac{475}{576}(P(x_0^{k+1}) - P(x_*)) \\
& - \frac{475}{576}\cdot \frac{15}{16} (P(x_0^k) - P(x_*))
- \frac{475}{576} \cdot   \frac{1}{15}\text{Gap}_k(x_0^k, y_0^k)
\end{split}
\label{local:ada_rho<mu_gap_2}
\end{align}
Combining (\ref{local:ada_rho<mu_gap_1}) and (\ref{local:ada_rho<mu_gap_2}), we get
\begin{align}
\begin{split}
&\E\left[\frac{475}{576}(P(x_0^{k+1}) - P(x_*))
+ \frac{57}{576} \text{Gap}_{k+1}(x_0^{k+1}, y_0^{k+1}) \right]\\
&\leq \frac{4\eta_k}{m M_k}
+ \frac{475}{576} \cdot \frac{15}{16} \E[P(x_0^k) - P(x_*)]
+ \frac{475}{576}\cdot \frac{1}{15} \E[\text{Gap}_k(x_0^k, y_0^k) ]
+ \frac{1}{96} \E[\text{Gap}_k(x_0^k, y_0^k)]\\
&\leq \frac{4\eta_k}{m M_k}
+ \frac{15}{16} \E \left[\frac{475}{576} (P(x_0^k) - P(x_*))
+ \frac{57}{576} \text{Gap}_k(x_0^k, y_0^k) \right]
\end{split}
\end{align}
Defining $\Delta_k = 475(P(x_0^k) - P(x_*)) + 57\text{Gap}_k(x_0^k, y0^k)$, we have
\begin{align}
\begin{split}
\E[\Delta_{k+1}] \leq \frac{15}{16} \E[\Delta_k] + \frac{4\eta_k}{m M_k} \leq \exp\left(-\frac{1}{16}\right)\E[\Delta_k] +  \frac{4\eta_k}{m M_k}
\end{split}
\end{align}
and $\Delta_1 \leq 600\epsilon_0$.

Thus,
\begin{align}
\begin{split}
\E[\Delta_{K+1}] \leq &  \exp\left(-\frac{K}{16}\right)\Delta_1
+ \frac{4}{m}\sum\limits_{k=1}^{K} \frac{\eta_k}{M_k} \exp\left(-\frac{K+1-k}{16}\right) \\
= & \exp\left(-\frac{K}{16}\right)\Delta_1
+ \frac{\eta_0^2 \min\{\lambda_x, \mu_y\}}{96 m^2}
\sum\limits_{k=1}^{K} \exp\left(-\frac{K}{16}\right) \\
\leq & 600\epsilon_0 \exp\left(-\frac{K}{16}\right)
+ \frac{\eta_0^2 \min\{\lambda_x, \mu_y\}}{96 m^2}
K \exp\left(-\frac{K}{16}\right) \\
\end{split}
\end{align}
To make this less than $\epsilon$, we just need to make
\begin{align}
\begin{split}
&600\epsilon_0 \exp\left(-\frac{K}{16}\right)  \leq \frac{\epsilon}{2} \\
&\frac{\eta_0^2 \min\{\rho, \mu_y\}}{96 m^2}
K \exp\left(-\frac{K}{16}\right) \leq \frac{\epsilon}{2}.
\end{split}
\end{align}
Let $K$ be the smallest value such that $\exp\left(\frac{-K}{16}\right) \leq \min\{\frac{\epsilon}{1200\epsilon_0},
\frac{48m^2 \epsilon}{\eta_0^2 \min\{\rho, \mu_y\}K}\}$.

Recall $T_k \leq (2\sqrt{d+d'}\delta M_k) ^{\frac{1}{1-\alpha}} = \left(\frac{768\delta}{\eta_0
\min\{\lambda_x, \mu_y\}} \exp\left(\frac{k-1}{32} \right)\right)^{\frac{1}{1-\alpha}}$.

Then the total iteration complexity is
\begin{align}
\begin{split}
\sum\limits_{k=1}^{K} T_k\leq & O
\left(\sum\limits_{k=1}^{K} \left[\frac{\delta}{\eta_0 \min\{\lambda_x, \mu_y\}} \exp \left(\frac{k-1}{32}\right) \right]^{\frac{1}{1-\alpha}} \right) \\
\leq & O\left( \sum\limits_{k=1}^{K}
\left(\frac{\delta}{\eta_0 \min\{\lambda_x,  \mu_y\}}\right)^{\frac{1}{1-\alpha}}
\exp \left(\frac{k-1}{32(1-\alpha)}\right) \right)\\
\leq& O\left(\left(\frac{\delta}{\eta_0 \min\{\lambda_x,  \mu_y\}}\right)^{\frac{1}{1-\alpha}}
\frac{\exp\left(\frac{K}{2(1-\alpha)\cdot 16}\right) - 1}
{\exp\left(\frac{1}{2(1-\alpha) \cdot 16}\right) - 1} \right) \\
\leq & \Tilde{O} \left(\left(\frac{\delta}{\eta_0 \min\{\lambda_x,  \mu_y\}}\right)^{\frac{1}{1-\alpha}} \left( \max\left\{
\frac{\epsilon_0}{\epsilon},
\frac{\eta_0^2 \min\{\lambda_x, \mu_y\} K}{m^2 \epsilon} \right\}\right)^{\frac{1}{2(1-\alpha)}} \right)  \\
\leq & \Tilde{O}\left( \left(  \max\left\{
\frac{\delta^2 \epsilon_0}{\eta_0^2 (\min\{\mu, \mu_y\})^2\epsilon}
,
\frac{\delta^2 (d+d') }{\min\{\mu, \mu_y\} \epsilon} \right\}
\right)^{\frac{1}{2(1-\alpha)}} \right) \\
\leq & \Tilde{O}\left( \left(
\frac{\delta^2 (d+d') }{\min\{\mu, \mu_y\} \epsilon}
\right)^{\frac{1}{2(1-\alpha)}} \right)
\end{split}
\end{align}
\end{proof}

\section{Proof of Corollary \ref{cor:ogda_duality},
\ref{cor:gda_duality}, \ref{cor:ada_dual}
}
\begin{proof}
Let $(x_*, y_*)$ denote a saddle point solution of $\min\limits_{x\in \mathbb{R}^d} \max\limits_{y\in Y} f(x, y)$ and $x_{K+1}^* = \min\limits_{x\in \mathbb{R}^d} P_k(x)$.

Note that $x_0^{K+1} = x_{K}, y_0^{K+1} = y_K$.
Suppose we have $\E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] \leq \hat{\epsilon}$ after $K$ stages.

Noting $\gamma = 2\rho$,

$f_k(x, y)$ is $\rho$-strongly convex and $\mu_y$-strongly concave.
By Lemma \ref{lem:Yan1}, we know that
\begin{align}
\begin{split}
\E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \leq \frac{4}{\rho} 2 \E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] \leq \frac{8\hat{\epsilon}}{\rho}.
\end{split}
\end{align}

Since $\partial_x {f}_{K+1}(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) = \partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) + \gamma (\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}) = 0$, we have
\begin{align}
\begin{split}
\E[\|\partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})\|^2] = \gamma^2 \E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \leq 32\rho\hat{\epsilon}
\end{split}
\end{align}

Using the $\mu_x$-PL condition of $f(\cdot, y_0^{K+1})$ in $x$,
\begin{align}
\begin{split}
\E \left[ f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) - f(\hat{x}(y_0^{K+1}),  y_0^{K+1}) \right]
 \leq \E\left[ \frac{\|\partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})\|^2}{2\mu_x} \right] \leq \frac{16\rho\hat{\epsilon}}{\mu_x}.
\end{split}
\end{align}

Hence,
\begin{align*}
\begin{split}
&\E \left[\text{Gap}(x_0^{K+1}, y_0^{K+1})\right] = \E\left[ f(x_0^{K+1}, \hat{y}(x_0^{K+1})) - f(\hat{x}(y_0^{K+1}), y_0^{K+1}) \right] \\
& = \E\bigg\{ f(x_0^{K+1}, \hat{y}(x_0^{K+1}))+\frac{\gamma}{2} \|x_0^{K+1} - x_0^{K+1}\|^2 - f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) - \frac{\gamma}{2} \|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2 \\
&~~~+ f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})- f(\hat{x}(y_0^{K+1}), y_0^{K+1}) + \frac{\gamma}{2} \|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2 \bigg\} \\
& = \E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] +  \E[f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})- f(\hat{x}(y_0^{K+1}), y_0^{K+1})] \\
&~~~ + \frac{\gamma}{2} \E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \\
& \leq \hat{\epsilon} +  \frac{16 \rho \hat{\epsilon}}{\mu_x} + 8\hat{\epsilon} \leq O\left(\frac{\rho\hat{\epsilon}}{\mu_x} +  \hat{\epsilon}\right).
\end{split}
\end{align*}

To have $\text{Gap}(x_0^{K+1}, y_0^{K+1})  \leq \epsilon$, we need $\hat{\epsilon} \leq O\left(\left(\frac{\rho}{\mu_x} + 1\right)^{-1}\epsilon\right)$.
Plug $\hat{\epsilon}$ into Theorem \ref{thm:ogda_primal},  \ref{thm:ada_primal}, \ref{thm:gda_primal},
we can prove Corollary \ref{cor:ogda_duality},  \ref{cor:ada_dual}, \ref{cor:gda_duality}, respectively.
\end{proof}

\section{Proof of Corollary \ref{cor:ogda_dual_rho<mu}, \ref{cor:gda_duality_rho<mu}, \ref{cor:ada_dual_rho<mu}}
\begin{proof}
Let $(x_*, y_*)$ denote a saddle point solution of  $\min\limits_{x\in \mathbb{R}^d} \max\limits_{y\in Y} f(x, y)$ and $x_{K+1}^* = \min\limits_{x\in \mathbb{R}^d} P_k(x)$.

Note that $x_0^{K+1} = x_{K}, y_0^{K+1} = y_K$.
Suppose we have $\E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] \leq \hat{\epsilon}$ after $K$ stages.

By the setting $\rho \leq \frac{\mu}{8}$ and $\gamma = \frac{\mu}{4}$,

$f_k(x, y)$ is $\frac{\mu}{8}$-strongly convex and $\mu_y$-strongly concave.
By Lemma \ref{lem:Yan1}, we know that
\begin{align}
\begin{split}
\E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \leq \frac{64}{\mu} \E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] \leq \frac{64\hat{\epsilon}}{\mu}.
\end{split}
\end{align}

Since $\partial_x {f}_{K+1}(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) = \partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) + \gamma (\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}) = 0$, we have
\begin{align}
\begin{split}
\E[\|\partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})\|^2] = \gamma^2 \E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \leq 4\mu\hat{\epsilon}.
\end{split}
\end{align}

Using the $\mu_x$-PL condition of $f(\cdot, y_0^{K+1})$ in $x$,
\begin{align}
\begin{split}
\E \left[ f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) - f(\hat{x}(y_0^{K+1}),  y_0^{K+1}) \right]
 \leq \E\left[ \frac{\|\partial_x f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})\|^2}{2\mu_x} \right] \leq  \frac{2\mu\hat{\epsilon}}{\mu_x}.
\end{split}
\end{align}

Hence,
\begin{align*}
\begin{split}
&\E \left[\text{Gap}(x_0^{K+1}, y_0^{K+1})\right] = \E\left[ f(x_0^{K+1}, \hat{y}(x_0^{K+1})) - f(\hat{x}(y_0^{K+1}), y_0^{K+1}) \right] \\
& = \E\bigg\{ f(x_0^{K+1}, \hat{y}(x_0^{K+1}))+\frac{\gamma}{2} \|x_0^{K+1} - x_0^{K+1}\|^2 - f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1}) - \frac{\gamma}{2} \|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2 \\
&~~~+ f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})- f(\hat{x}(y_0^{K+1}), y_0^{K+1}) + \frac{\gamma}{2} \|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2 \bigg\} \\
& = \E[\text{Gap}_{K+1}(x_0^{K+1}, y_0^{K+1})] +  \E[f(\hat{x}_{K+1}(y_0^{K+1}), y_0^{K+1})- f(\hat{x}(y_0^{K+1}), y_0^{K+1})] \\
&~~~ + \frac{\gamma}{2} \E[\|\hat{x}_{K+1}(y_0^{K+1}) - x_0^{K+1}\|^2] \\
& \leq \hat{\epsilon} +  \frac{2 \mu \hat{\epsilon}}{\mu_x} + 8\hat{\epsilon} \leq O\left(\frac{\mu\hat{\epsilon}}{\mu_x} +   \hat{\epsilon}\right).
\end{split}
\end{align*}

To have $\text{Gap}(x_0^{K+1}, y_0^{K+1})  \leq \epsilon$, we need $\hat{\epsilon} \leq O\left(\left(\frac{\mu}{\mu_x} +  1\right)^{-1}\epsilon\right)$.
Plug $\hat{\epsilon}$ into Theorem\ref{thm:2}, \ref{thm:gda_primal_rho<mu}, \ref{thm:ada_primal_rho<mu}
we can prove Corollary \ref{cor:ogda_dual_rho<mu},  \ref{cor:gda_duality_rho<mu}, \ref{cor:ada_dual_rho<mu}, respectively.
\end{proof}
\end{document}

config: arxiv