\section{Introduction}
Consider the following general nonsmooth nonconvex minimax optimization problem with coupled linear constraints:
	\begin{equation}\label{problem:1}
		\min_{x\in\mathcal{X}}\max\limits_{\substack{ y\in\mathcal{Y}\\Ax+By\unlhd c}}\{f(x,y)+h(x)-g(y)\},\tag{P}
	\end{equation}
	where $\mathcal{X}\subseteq \mathbb{R}^n$ and $\mathcal{Y}\subseteq \mathbb{R}^m$ are nonempty convex and compact sets, $f(x,y): \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$ is a smooth function and possibly nonconvex in $x$, $h(x):\mathbb{R}^{n}\rightarrow \mathbb{R}$ and $g(y): \mathbb{R}^{m}\rightarrow \mathbb{R}$ are some proper convex continuous possibly nonsmooth functions, $A\in\mathbb{R}^{p\times n}$, $B\in\mathbb{R}^{p\times m}$ and $c\in\mathbb{R}^{p}$; $\unlhd$ denotes $\le$ or $=$. We use $[Ax+By]_i\unlhd [c]_i$ to denote the $i$th constraint, and define $\mathcal{K}:= \{1,\dots , p\}$ as the index set of the constraints.

When $A=0$, $B=0$, $c=0$, $h(x)=0$ and $g(y)=0$, \eqref{problem:1} degenerates into the following special minimax optimization problem:
\begin{equation}\label{min}
	\min \limits_{x\in \mathcal{X}}\max \limits_{y\in \mathcal{Y}}f(x,y),
\end{equation}
which has been a focus of research in machine learning, signal processing, statistics, economics and many other research fields \cite{Berger,Facchinei,Ghosh,Sanjabi,Wu,Yang} recently. Many applications can be formulated into \eqref{min}, including the power control and transceiver design problem in signal processing \cite{Lu}, reinforcement  learning \cite{Cai,Moriarty,Qiu}, the adversarial attack to deep neural networks(DNNs) \cite{Chen}, distributed nonconvex optimization \cite{Giannakis,Mateos}, robust learning over multiple domains \cite{Qian}.  We call \eqref{min} a (non)convex-(non)concave minimax problem if $f(x, y)$ is (non)convex in $x$ and (non)concave in $y$. Many works for (strongly) convex-(strongly) concave \cite{Lan2016,Mokhtari,Nemirovski,Nesterov2007,Thek2022}, nonconvex-(strongly) concave \cite{Lin2019,Lin2020,Lu,Pan,Xu,Xu21,Zhang} and nonconvex-nonconcave \cite{Bohm,DiakonikolasEG,Doan,Lee,Sanjabi18,SongOptDE} minimax problem have been studied before. Lin et al.\cite{Lin2020} proposed an accelerated algorithm for solving nonconvex-strongly concave minimax problem \eqref{min}. The algorithm can find an $\varepsilon$-stationary point within $\tilde{\mathcal{O}}\left(\sqrt{\kappa_y}\varepsilon ^{-2} \right)$ iterations, which is the best known complexity bound under this setting.

Problem \eqref{problem:1} is more challenging than \eqref{min}, and it is NP-hard even when $f(x, y)$ is strongly-convex in $x$ and strongly-concave in $y$~\cite{Tsaknakis}. Even for the smooth case of \eqref{problem:1}, i.e., $h(x)=0$ and $g(y)=0$, few algorithms have been proposed to solve this class of problems. In \cite{Tsaknakis}, a family of efficient algorithms named multiplier gradient descent(MGD) are proposed for solving smooth version of \eqref{problem:1}, which achieves the iteration complexity of $\tilde{\mathcal{O}}\left( \varepsilon ^{-2} \right)$ when $f(x,y)$ is strongly convex with respect to $x$ and strongly concave with respect to $y$.
Dai et al. \cite{Dai} proposed a proximal gradient multi-step ascent descent method (PGmsAD) for nonsmooth convex-strongly concave bilinear coupled minimax problems with linearly euqality constraints when $\mathcal{X}=\mathbb{R}^n$ and $\mathcal{Y}=\mathbb{R}^m$, which achieves the iteration complexity bound of $\mathcal{O}(\varepsilon^{-2}\log(1/\varepsilon))$ to obtain an $\varepsilon$-stationary point. To the best of our knowledge, there is no algorithm with theoretical complexity guarantee for nonconvex-(strongly) concave or nonconvex-linear minimax problems with coupled linear constraints up to now.

\textbf{Contributions.}
We focus on single loop algorithms for solving nonsmooth nonconvex minimax problems with coupled linear constraints. The main contribution of this paper can be summarized as follows.

\begin{itemize}
	\item For nonconvex-concave minimax problem \eqref{problem:1} with linear coupled equality or inequality constraints, we first prove the strong duality with respect to $y$ under some feasibility assumption. Before our results, instead of convex minimax problems, we have never seen any strong duality results with respect to $y$ for solving nonconvex minimax problems with coupled linear constraints.
	\item  Based on the strong duality, we then propose a primal dual alternating proximal gradient (PDAPG) algorithm and a primal dual proximal gradient (PDPG-L) algorithm for solving problem \eqref{problem:1} under nonconvex-(strongly) concave and nonconvex-linear settings, respectively. They are both single loop algorithms.
	\item We show that to obtain an $\varepsilon$-stationary point for problem \eqref{problem:1}, the number of iterations of the proposed PDAPG algorithm is upper bounded by $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) for solving nonsmooth nonconvex-strongly concave (resp. nonconvex-concave) minimax problems with coupled linear constraints, and the corresponding complexity for PDPG-L algorithm is upper bounded by $\mathcal{O}\left( \varepsilon ^{-3} \right)$ for solving nonsmooth nonconvex-linear minimax problems with coupled linear constraints. To the best of our knowledge, they are the first two algorithms with theoretically guaranteed iteration complexity results for these three classes of minimax problems.
	\item Even for nonconvex-strongly concave minimax problems without linear coupled constraints, the lower bound of the iteration complexity results of first order method to obtain an $\varepsilon$-stationary point is $\mathcal{O}\left( \varepsilon ^{-2} \right)$. In this sense, the proposed PDAPG algorithm is optimal for solving nonsmooth nonconvex-strongly concave  minimax problems with coupled linear constraints.
	\item Under the nonconvex concave setting, the iteration complexity result of the proposed PDAPG algorithm for solving \eqref{problem:1} matches that of the AGP algorithm~\cite{Xu} and the smoothed GDA algorithm~\cite{Zhang}, which are the two best known single loop algorithms in the sense of iteration complexity for solving \eqref{min}, i.e., general nonconvex-concave minimax problems without linear coupled constraints.
\end{itemize}

\subsection{Related Works}
In this subsection, we first give a brief review on the related first order methods for solving minimax optimization problem \eqref{min}.

Under convex-concave setting of \eqref{min}, there are many existing works. For instance, Nemirovski \cite{Nemirovski} proposed a mirror-prox method with complexity of $\mathcal{O}(\varepsilon^{-1})$ in terms of duality gap when $\mathcal{X}$ and $\mathcal{Y}$ are bounded sets. Nesterov~\cite{Nesterov2007} proposed a dual extrapolation algorithm which owns $\mathcal{O}(\varepsilon^{-1})$ iterations. Mokhtari et al. \cite{Mokhtari} established an overall complexity of $\mathcal{O}(\kappa\log(1/\varepsilon))$ for both extra-gradient(EG) and optimistic gradient descent ascent(OGDA) methods in bilinear and strongly convex-strongly concave settings. Thekumparampil et al. \cite{Thek2022} proposed a lifted primal-dual method for  bilinearly coupled strongly convex-strongly concave minimax problem, which achieve the iteration complexity of $\mathcal{O}(\log(1/\varepsilon))$. For more related results, we refer to \cite{Chen2017,Chen,Dang,Gidel2019,He2016,Lan2016,Lin2020,Ouyang2015,Ouyang2019,Tominin,Zhang22} and the references therein.

For nonconvex-strongly concave minimax problem \eqref{min}, various algorithms have been proposed in recent works \cite{Bot,Huang,Jin,Lin2019,Lu,Rafique,Zhang2021}, and all of them can achieve the iteration complexity of $\tilde{\mathcal{O}}\left( \kappa_y^2\varepsilon ^{-2} \right)$ in terms of stationary point of $\Phi (\cdot) = \max_{y\in \mathcal{Y}} f(\cdot, y)$ (when $\mathcal{X}=\mathbb{R}^n$), or stationary point of $f(x,y)$,  where $\kappa_y$ is the condition number for $f(x,\cdot)$. Furthermore, Lin et al.\cite{Lin2020} proposed an accelerated algorithm which can improve the iteration complexity to $\tilde{\mathcal{O}}\left(\sqrt{\kappa_y}\varepsilon ^{-2} \right)$.

For general nonconvex-concave minimax problem \eqref{min}, there are two types of algorithms, i.e., multi-loop algorithms and single-loop algorithms. Various multi-loop algorithms have been proposed in \cite{Kong,Lin2020,Nouiehed,Ostro,Rafique,Thek2019}. The best known iteration complexity in terms of stationary point of $f(x,y)$ for multi-loop algorithms is $\tilde{\mathcal{O}}\left( \varepsilon ^{-2.5} \right)$, which can be achieved by \cite{Lin2020}. All these multi-loop algorithms either utilize multiple accelerated gradient ascent steps to update $y$ that can solve the inner subproblem exactly or inexactly, or further do similar acceleration for $x$'s update by adding regularization terms to the inner objective function, and thus are relatively complicated to be implemented.
On the other hand, fewer studies focus on single-loop algorithms for nonconvex-concave minimax problems. One classical method is the gradient descent-ascent (GDA) method, which employs a gradient descent step to update $x$ and a gradient ascent step to update $y$ simultaneously at each iteration. Many other GDA-type algorithms have been analyzed in \cite{Chambolle,Daskalakis17,Daskalakis18,Gidel2019,Gidel18-2,Ho2016}. Lin et al. \cite{Lin2019} proved that the iteration complexity of GDA  to find an $\varepsilon$-stationary point of $\Phi (\cdot) = \max_{y\in \mathcal{Y}} f(\cdot, y)$ is $\tilde{\mathcal{O}} (\varepsilon^{-6})$ when $\mathcal{X}=\mathbb{R}^n$ and $\mathcal{Y}$ is a convex compact set. Lu et al. \cite{Lu} proposed the hybrid block successive approximation (HiBSA) algorithm, which can obtain the iteration complexity of $\tilde{\mathcal{O}}\left( \varepsilon ^{-4} \right)$ in terms of $\varepsilon$-stationary point of $f(x,y)$ when $\mathcal{X}$ and $\mathcal{Y}$ are convex compact sets. However, for updating $y$, HiBSA has to solve the subproblem of maximizing the original function $f(x, y)$ plus some regularization terms for a fixed $x$. Pan et al. \cite{Pan} proposed a new alternating gradient projection algorithm for nonconvex-linear minimax problem with the iteration complexity of $\mathcal{O}\left( \varepsilon ^{-3} \right)$. Xu et al. \cite{Xu} proposed a unified single-loop alternating gradient projection (AGP) algorithm for solving nonconvex-concave and convex-nonconcave minimax problems, which can find an $\varepsilon$-stationary point with the iteration complexity of $\mathcal{O}\left( \varepsilon ^{-4} \right)$ for smooth and nonsmooth cases. Zhang et al. \cite{Zhang} proposed a smoothed GDA algorithm which also achieves the iteration complexity of $\mathcal{O}\left( \varepsilon ^{-4} \right)$ for general nonconvex-concave minimax problems, and can achieve the iteration comlexity of $\mathcal{O}\left( \varepsilon ^{-2} \right)$ for a class of special nonconvex-linear minimax problems.

For nonconvex-nonconcave minimax problem \eqref{min}, Sanjabi et al. \cite{Sanjabi18} proposed a multi-step gradient descent-ascent algorithm which finds an $\varepsilon$-first order Nash equilibrium in $\mathcal{O}(\varepsilon^{-2}\log\varepsilon^{-1})$ iterations when a one-sided Polyak-{\L}ojasiewicz (PL) condition is satisfied. Yang et al. \cite{Yang} showed the alternating GDA algorithm converges globally at a linear rate for a subclass of nonconvex-nonconcave objective functions satisfying a two-sided PL inequality. Song et al. \cite{SongOptDE} proposed an optimistic dual extrapolation (OptDE) method with the iteration complexity of $\mathcal{O}\left( \varepsilon^{-2} \right)$, if a weak solution exists. Hajizadeh et al. \cite{Hajizadeh} showed that a damped version of extra-gradient method linearly converges to an $\varepsilon$-stationary point of nonconvex-nonconcave minimax problems that the nonnegative interaction dominance condition is satisfied. Zhang et al. \cite{Zhang2022} proposed a doubly smoothed gradient descent ascent method for general nonconvex-noncave minimax problem, and the algorithm has an iteration complexity of $\mathcal{O}\left( \varepsilon^{-4} \right)$. For more related results, we refer to \cite{Bohm,Chinchilla,Cai,DiakonikolasEG,Doan,Grimmer,Jiang,Lee}.

Next, we briefly review some existing works that focus on zeroth-order algorithms for solving minimax optimization problem \eqref{min}. For instance,  Beznosikov et al. \cite{Beznosikov} proposed a zeroth-order saddle-point algorithm  for convex-concave minimax problem with the iteration complexity of $\mathcal{O}\left( \varepsilon ^{-2} \right)$. Wang et al. \cite{Wang} proposed a zeroth-order GDA algorithm and a zeroth-order gradient descent multi-step ascent  algorithm for nonconvex-strongly concave minimax optimization problem, and the total complexity is $\mathcal{O}\left(\kappa^{5}\left(n+m\right) \varepsilon^{-2}\right)$ and $\mathcal{O}\left(\kappa\left(n+\kappa m \log \left(\varepsilon^{-1}\right)\right) \varepsilon^{-2}\right)$, respectively, where $\kappa$ is the condition number for $f(x,\cdot)$. Huang et al. \cite{Huang} proposed an accelerated zeroth-order momentum descent ascent  method  with the total complexity of $\mathcal{O}\left(\kappa^{3}\left(n+m\right)^{3 / 2} \varepsilon^{-3}\right)$. Xu et al. \cite{Xu21} proposed a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems, which can obtain the iteration complexity $\mathcal{O}(\varepsilon^{-4})$, and the number of function value estimation is bounded by $\mathcal{O}(\varepsilon^{-6})$ per iteration.
Shen et al. \cite{Shen} proposed another zeroth-order alternating randomized gradient projection algorithm for smooth nonconvex-linear minimax problems, which can obtain the iteration complexity $\mathcal{O}(\varepsilon^{-3})$, and the number of function value estimation per iteration is bounded by $\mathcal{O}(\varepsilon^{-2})$. For more details, we refer to \cite{Liu,Roy,Sadiev,Xu20}.
\subsection{Organization}
The rest of this paper is organized as follows. In Section 2, we first establish the strong duality with respect to $y$ under some feasibility assumption for nonconvex-concave minimax problem \eqref{problem:1} with linear coupled equality or inequality constraints. Then, we propose a  primal dual alternating proximal gradient (PDAPG) algorithm for nonsmooth nonconvex-(strongly) concave minimax problem with coupled linear constraints, and then prove its iteration complexity. In Section 3, we propose another primal dual proximal gradient (PDPG-L) algorithm for nonsmooth nonconvex-linear minimax problem with coupled linear constraints, and also establish its iteration complexity. Numerical results in Section 4 show the efficiency of the two proposed algorithms. Some conclusions are made in the last section.
\subsection{Notations}
For vectors, we use $\|\cdot\|$ to represent the Euclidean norm and its induced matrix norm; $\left\langle x,y \right\rangle$ denotes the inner product of two vectors of $x$ and $y$. $[x]_i$ denotes the $i$th component of vector $x$. $(x;y)$ represents the vector $\left(\begin{array}{c}x\\y\end{array}\right)$. $\mathbb{R}_{+}^p$ is defined as $p$-dimensional positive real vector space. We use $\nabla_{x} f(x,y,z)$ (or $\nabla_{y} f(x, y,z)$, $\nabla_{z} f(x, y,z)$) to denote the partial derivative of $f(x,y,z)$ with respect to $x$ (or $y$, $z$) at point $(x, y,z)$, respectively,  and $\nabla_{x,z} f(x,y,z)$ to denote $\left(\begin{array}{c}\nabla_{x} f(x,y,z)\\\nabla_{z} f(x,y,z)\end{array}\right)$.
	 We use the notation $\mathcal{O} (\cdot)$ to hide only absolute constants which do not depend on any problem parameter, and $\tilde{\mathcal{O}}(\cdot)$ notation to hide only absolute constants and log factors. A continuously differentiable function $f(\cdot)$ is called $L$-smooth if there exists a constant $L> 0$ such
that for any given $x,y \in \mathcal{X}$,
\begin{equation*}
	\|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|.
\end{equation*}
A continuously differentiable function $f(\cdot)$ is called $\mu$-strongly convcave if there exists a constant $\mu> 0$ such
that for any $x,y \in \mathcal{X}$,
\begin{equation*}
	f(y)\le f(x)+\langle \nabla f(x),y-x \rangle-\frac{\mu}{2}\|y-x\|^2.
\end{equation*}

\section{Nonconvex-(Strongly) Concave Minimax Problems with Coupled Linear Constraints}\label{sec2}

\subsection{Dual Problem and Strong Duality for $y$}
It is difficult to directly solve the primal problem \eqref{problem:1} since the coupled linear constraints make the inner and outer problem being tightly coupled. By using the Lagrangian function of problem \eqref{problem:1}, we obtain the dual problem of \eqref{problem:1}, i.e.,
\begin{align}\label{problem:2}
\min_{\lambda\in\Lambda} \min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\},\tag{D}
\end{align}
where $$L(x,y,\lambda):=f(x,y)-\lambda^\top(Ax+By-c),$$ and $\Lambda=\mathbb{R}_{+}^p$ if $\unlhd$ is $\le$, $\Lambda=\mathbb{R}^p$ if $\unlhd$ is $=$. We give the following feasibility assumption for the inequality constraints case.
\begin{ass}\label{fea}
When $\unlhd$ is $\le$ in \eqref{problem:1}, for every $x\in\mathcal{X}$, there exists a vector $y\in relint(\mathcal{Y})$ such that $Ax+By-c\le0$, where $relint(\mathcal{Y})$ is the set of all relative interior points of $\mathcal{Y}$.
\end{ass}
The strong duality of problem \eqref{problem:1} with respect to $y$ is established in the following theorem. For the sake of completeness, we give its proof, although it is similar to that of Theorem 2 in \cite{Tsaknakis}.

\begin{thm}\label{dual}
Suppose $f(x,y)$ is a concave function with respect to $y$, and Assumption \ref{fea} holds. Then the strong duality of problem \eqref{problem:1} with respect to $y$ holds, i.e.,
\begin{align*}
  &\min_{x\in\mathcal{X}}\max_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\{f(x,y)+h(x)-g(y)\
  =\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}.
\end{align*}
\end{thm}
\begin{proof}
When $\unlhd$ is $\le$,  $\Lambda=\mathbb{R}_{+}^p$, and for any pair $(x,y)\in\mathcal{X}\times\mathcal{Y}$, if there exists an index $i$ such that $[Ax+By-c]_i>0$, then we have
\begin{align}\label{dual:2}
  &\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
  =&f(x,y)+h(x)-g(y)+\min_{\lambda\in\Lambda}\left\{-\lambda^\top(Ax+By-c)\right\}=-\infty.
\end{align}
If $Ax+By-c\le 0$, then
\begin{align}\label{dual:3}
  \min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}=f(x,y)+h(x)-g(y).
\end{align}
Thus, combining \eqref{dual:2} and \eqref{dual:3}, we obtain
\begin{align}\label{dual4}
  &\max_{y\in\mathcal{Y}}\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
=&\max_{\substack{y\in\mathcal{Y}\\Ax+By\le c}}\left(\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\right)\nonumber\\
=&\max_{\substack{y\in\mathcal{Y}\\Ax+By\le c}}\left\{f(x,y)+h(x)-g(y)\right\}.
\end{align}
When $\unlhd$ is $=$, $\Lambda=\mathbb{R}^p$. For any pair $(x,y)\in\mathcal{X}\times\mathcal{Y}$, if there exists an index $i$ such that $[Ax+By-c]_i\neq0$, then we have
\begin{align}\label{dual:e2}
  &\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
  =&f(x,y)+h(x)-g(y)+\min_{\lambda\in\Lambda}\left\{-\lambda^\top(Ax+By-c)\right\}=-\infty.
\end{align}
If $Ax+By-c=0$, then
\begin{align}\label{dual:e3}
  \min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}=f(x,y)+h(x)-g(y).
\end{align}
Combining \eqref{dual:e2} and \eqref{dual:e3}, we get
\begin{align}\label{dual5}
  &\max_{y\in\mathcal{Y}}\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
=&\max_{\substack{y\in\mathcal{Y}\\Ax+By\le c}}\left(\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\right)\nonumber\\
=&\max_{\substack{y\in\mathcal{Y}\\Ax+By\le c}}\left\{f(x,y)+h(x)-g(y)\right\}.
\end{align}
By \eqref{dual4} and \eqref{dual5}, we have
\begin{align}\label{dual:4}
  &\max_{y\in\mathcal{Y}}\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\
=\max_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\left\{f(x,y)+h(x)-g(y)\right\}.
\end{align}
Since $f(x,y)$ is a concave function with respect to $y$, by Sion’s minimax theorem (Corollary 3.3 in \cite{Sion}), $\forall x\in\mathcal{X}$, we have
\begin{align}\label{dual:5}
  &\max_{y\in\mathcal{Y}}\min_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\
  =\min_{\lambda\in\Lambda}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}.
\end{align}
Combining \eqref{dual:4} and \eqref{dual:5}, we obtain
\begin{align*}
  &\max_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\left\{f(x,y)+h(x)-g(y)\right\
  =\min_{\lambda\in\Lambda}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\},
\end{align*}
which implies that
\begin{align}\label{dual:6}
  &\min_{x\in\mathcal{X}}\max_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\left\{f(x,y)+h(x)-g(y)\right\}\nonumber\\
  =&\min_{x\in\mathcal{X}}\min_{\lambda\in\Lambda}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
  =&\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}.
\end{align}
The proof is completed.
\end{proof}

For any given proper convex function $h(\cdot)$ and a convex compact set $\mathcal{Z}$, we denote the following proximity operator,
\begin{align*}
	\operatorname{Prox}_{h,\mathcal{Z}}^{\alpha}(\upsilon)&:=\arg\min\limits_{z\in \mathcal{Z}} h(z)+\frac{\alpha}{2}\|z-\upsilon \|^2,

\end{align*}
where $\alpha>0$.  We then define the $\varepsilon$-stationary point of problem \eqref{problem:1} as follows.
\begin{defi}\label{gap-f}
	For some given $\alpha>0$, $\beta>0$ and $\gamma>0$, denote 	\begin{equation*}
		\nabla G^{\alpha,\beta,\gamma}\left( x,y,\lambda \right) :=\left( \begin{array}{c}
			\alpha\left( x-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x-\frac{1}{\alpha}\nabla _xL\left( x,y,\lambda  \right) \right) \right)\\
			\beta\left( y-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y+ \frac{1}{\beta} \nabla _yL\left( x,y,\lambda \right) \right) \right)\\
			\frac{1}{\gamma}\left( \lambda-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla_{\lambda}L(x,y,\lambda)\right)\right)\\
		\end{array} \right) .
	\end{equation*}
Then for any given $\varepsilon>0$, if there exists a $\lambda$ such that $\nabla G^{\alpha,\beta,\gamma}\left( x,y,\lambda \right)=0$ or $\|\nabla G^{\alpha,\beta,\gamma}\left( x,y,\lambda \right)\|\le \varepsilon$,  we call the point $(x,y)$ is a stationary point or an $\varepsilon$-stationary point of problem \eqref{problem:1} respectively.

\end{defi}

Note that $\Lambda=\mathbb{R}^p$ if $\unlhd$ is $=$. Thus, if there exsit only equality constraints, $\|\nabla G^{\alpha,\beta,\gamma}(x,y,\lambda)\|\leq\varepsilon$ implies that the violation of the constraint at $(x,y,\lambda)$ also satisfies the given accuracy, i.e., $\|Ax+By-c\|\leq \varepsilon$. If there also exist some inequality constraints, we also provide an upper bound for the violation of the constraint at $(x,y,\lambda)$ in the following lemma.

\begin{lem}\label{lem2.1}
Suppose $\Lambda=\mathbb{R}_{+}^p$. If $\|\nabla G^{\alpha,\beta,\gamma}(x,y,\lambda)\|\leq\varepsilon$ and $\lambda \geq 0$, for any  $i\in\mathcal{K}$, we have
\begin{align*}
	\max\{0,[Ax+By-c]_i\}\leq \varepsilon.
\end{align*}
\end{lem}

\begin{proof}
	If $\|\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)\|\le\varepsilon$, by Definiton \ref{gap-f}, we immediately have
	\begin{align}
		\frac{1}{\gamma}\|\lambda
		-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla_{\lambda}L(x,y,\lambda)\right)\|\le\varepsilon.\label{lem2.1:2}
	\end{align}
 If $[Ax+By-c]_i\le 0$, then $\max\{0,[Ax+By-c]_i\}=0\leq \varepsilon$. Otherwise, if $[Ax+By-c]_i> 0$, by $\Lambda=\mathbb{R}_{+}^p$, then we have
	\begin{align}
		&\frac{1}{\gamma}\left|[\lambda -\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla_{\lambda}L(x,y,\lambda)\right)]_i\right|\nonumber\\
		=&\frac{1}{\gamma}|[\lambda]_i-\max\{0,[\lambda+\gamma(Ax+By-c)]_i\}|\nonumber\\
		=&\frac{1}{\gamma}|[\lambda]_i-[\lambda]_i-\gamma[Ax+By-c]_i|
		=[Ax+By-c]_i.\label{lem2.1:4}
	\end{align}
	Combining \eqref{lem2.1:2}  and \eqref{lem2.1:4}, we obviously obtain $\max\{0,[Ax+By-c]_i\}\le\varepsilon$ which completes the proof.
\end{proof}

\begin{thm}\label{thm2.2}
	Suppose $f(x,y)$ is a concave function with respect to $y$, and Assumption \ref{fea} holds. A point $(x^*,y^*)$ is a stationary point of problem \eqref{problem:1} if and only if there exists a $\lambda^*$ such that $(x^*,y^*,\lambda^*)$ is a stationary point of problem \eqref{problem:2}.
\end{thm}
\begin{proof}
	By \eqref{dual:4}, we know that the problem $\max\limits_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\left\{f(x,y)+h(x)-g(y)\right\}$ is equivalent  to the problem $\max\limits_{y\in\mathcal{Y}}\min\limits_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}$. Hence, problem \eqref{problem:1} is equivalent  to the following problem
	\begin{align}
		\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\min\limits_{\lambda\in\Lambda}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}.\label{thm2.2:1}
	\end{align}
	By \eqref{thm2.2:1}, we have that $(x^*,y^*,\lambda^*)$ is a stationary point of problem \eqref{thm2.2:1} if and only if $(x^*,y^*,\lambda^*)$ is a stationary point of problem \eqref{problem:2}, and the proof is then completed.
\end{proof}

\subsection{A Primal Dual Alternating Proximal Gradient Algorithm}

By strong duality shown in Theorem \ref{dual} and Theorem \ref{thm2.2}, instead of solving \eqref{problem:1}, we propose a primal dual alternating proximal gradient (PDAPG) algorithm for solving \eqref{problem:2}.
At each iteration of the proposed PDAPG algorithm, it performs a proximal gradient step for updating $y$ and $x$, respectively and a gradient projection step for updating $\lambda$ for a regularized version of $L(x,y,\lambda)$, i.e.,
\begin{align}
	L_k(x,y,\lambda)&=L(x,y,\lambda)-\frac{\rho_k}{2}\|y\|^2,\label{sc:1}
\end{align}
where $\rho_k\ge0$ is a regularization parameter.
More detailedly, at the $k$th iteration of the proposed algorithm, the update for $y_k$ is as follows,
\begin{align*}
y_{k+1}&={\arg\max}_{y\in \mathcal{Y}}\langle  \nabla _y L_k\left( x_{k},y_k,\lambda_k \right),y-y_k \rangle  -\frac{\beta}{2}\| y-y_k \| ^2-g(y)\nonumber\\
&= \operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_k+\frac{1}{\beta} \nabla _y L\left( x_{k},y_k,\lambda_k \right) -\frac{\rho_k}{\beta} y_k\right),
\end{align*}
where $\beta >0$ is a parameter which will be defined later. The update for $x_k$ is that
\begin{align*}
x_{k+1}&={\arg\min}_{x\in \mathcal{X}}\langle  \nabla _x L_k\left( x_{k},y_{k+1},\lambda_k \right) ,x-x_k \rangle  +\frac{\alpha_k}{2}\| x-x_k \| ^2+h(x)\nonumber\\
&= \operatorname{Prox}_{h,\mathcal{X}}^{\alpha_k} \left( x_k - \frac{1}{\alpha_k} \nabla _xL\left( x_{k},y_{k+1},\lambda_k \right) \right),
\end{align*}
where $\alpha_k > 0$ is a parameter which will be defined later. The update for $\lambda_k$ is that
\begin{align*}
 \lambda_{k+1}&=\mathcal{P}_{\Lambda}\left(\lambda_k-\gamma_k\nabla_{\lambda}L(x_{k+1},y_{k+1},\lambda_k)\right),
\end{align*}
 where $\mathcal{P}_{\Lambda}$ is the projection operator onto $\Lambda$. The proposed PDAPG algorithm is formally stated in Algorithm \ref{alg:1}.
\begin{algorithm}[t]
	\caption{(PDAPG)}
	\label{alg:1}
	\begin{algorithmic}
		\STATE{\textbf{Step 1}:Input $x_1,y_1,\lambda_1,\beta,\alpha_1,\gamma_1$; Set $k=1$.}

		\STATE{\textbf{Step 2}:Perform the following update for $y_k$:
			\qquad \begin{equation}\label{update-y}
y_{k+1}=\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_k+\frac{1}{\beta} \nabla _y L\left( x_{k},y_k,\lambda_k \right) -\frac{\rho_k}{\beta} y_k\right).
\end{equation}}
		\STATE{\textbf{Step 3}:Perform the following update for $x_k$:
			\qquad	\begin{equation}\label{update-x}
x_{k+1}=\operatorname{Prox}_{h,\mathcal{X}}^{\alpha_k} \left( x_k - \frac{1}{{\alpha_k}}  \nabla _xL\left( x_{k},y_{k+1},\lambda_k \right) \right).
\end{equation}}
        \STATE{\textbf{Step 4}:Perform the following update for $\lambda_k$:
        				\qquad	\begin{equation}\label{update-lambda}
 \lambda_{k+1}=\mathcal{P}_{\Lambda}(\lambda_k+\gamma_k(Ax_{k+1}+By_{k+1}-c)).
	\end{equation}}
		\STATE{\textbf{Step 5}:If some stationary condition is satisfied, stop; otherwise, set $k=k+1, $ go to Step 2.}

	\end{algorithmic}
\end{algorithm}

Note that PDAPG is a single loop algorithm. When $f(x,y)$ is a general concave function with respect to $y$, PDAPG is a brand new algorithm. We set $\rho_k=0$ when $f(x,y)$ is strongly concave with respect to $y$. Even for nonconvex-strongly concave minimax problem, PDAPG is different from PGmsAD in \cite{Dai} and MGD in  \cite{Tsaknakis} that are both multi-looped algorithms.  Moreover, $x_{k+1}$ is used to update $\lambda_k$ in Algorithm \ref{alg:1} instead of $x_k$ which is used in PGmsAD algorithm.  Algorithm \ref{alg:1} can solve both smooth and nonsmooth minimax problem with coupled linear constraints, whereas MGD is only proposed to solve the smooth version of \eqref{problem:1}.

Before we analyze the iteration complexity of Algorithm \ref{alg:1}, we need to make the following assumption about the smoothness of $f(x,y)$.
\begin{ass}\label{ass:Lip}
	The function $f(x,y)$ has Lipschitz continuous gradients and there exist a constant $L>0$ such that for any $x, x_1, x_2\in \mathcal{X}$, and $y, y_1, y_2\in \mathcal{Y}$, we have
	\begin{align*}
		\| \nabla_{x} f\left(x_1, y\right)-\nabla_{x} f\left(x_2, y\right)\| &\leq L\|x_{1}-x_{2}\|,\\
		\|\nabla_{x} f\left(x, y_1\right)-\nabla_{x} f\left(x, y_2\right)\| &\leq L\|y_{1}-y_{2}\|,\\
		\|\nabla_{y} f\left(x, y_1\right)-\nabla_{y} f\left(x, y_2\right)\| &\leq L\|y_{1}-y_{2}\|,\\
		\|\nabla_{y} f\left(x_1, y\right)-\nabla_{y} f\left(x_2, y\right)\| &\leq L\|x_{1}-x_{2}\|.
	\end{align*}
\end{ass}

\subsection{Nonconvex-Strongly Concave Setting}
In this subsection, we prove the iteration complexity of Algorithm \ref{alg:1} under the nonconvex-strongly concave setting, i.e., $f(x,y)$ is $\mu$-strongly concave with respect to $y$ for any given $x\in\mathcal{X}$. Under this setting, $\forall k \ge 1$, we set
\begin{equation}
	\alpha_k=\alpha,\quad \gamma_k=\gamma, \quad \rho_k=0.
\end{equation}
Before proving the global error bound, we first denote
\begin{align*}
\Phi(x,\lambda)&:=\max_{y\in\mathcal{Y}}L(x,y,\lambda),\\
y^*(x,\lambda)&:=\arg\max_{y\in\mathcal{Y}}L(x,y,\lambda).
\end{align*}
By Lemma 24 in \cite{Nouiehed}, $\Phi(x,\lambda)$ is $L_\Phi$-Lipschitz smooth with $L_\Phi=L+\frac{L^2}{\mu}$ under the $\mu$-strong concavity of $L(x,y,\lambda)$. Moreover,  by $\mu$-strong concavity of $L(x,y,\lambda)$ with respect to $y$ and Lemma B.2 in \cite{Lin2020},  for any given $x$ and $\lambda$ we have
\begin{align}
\nabla_x\Phi(x,\lambda)&=\nabla_x L(x, y^*(x,\lambda),\lambda),\label{gradx:nsc}\\
\nabla_\lambda\Phi(x,\lambda)&=\nabla_\lambda L(x, y^*(x,\lambda),\lambda)\label{gradla:nsc}.
\end{align}
\begin{lem}\label{lem:eb}
Suppose that Assumption \ref{ass:Lip} holds and $f(x,y)$ is $\mu$-strongly concave with respect to $y$. Let $\eta=\frac{(2\beta+\mu)(\beta+L)}{\mu\beta}$, then
	\begin{align}\label{lem:eb:1}
	\|y-y^*(x,\lambda)\|\le\eta\left\| y-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y+ \frac{1}{\beta} \nabla _yL\left( x,y,\lambda \right) \right)\right\|.
	\end{align}
\end{lem}
\begin{proof}
Firstly, $g(y)$ is a closed convex function and $-L(x,y,\lambda)$ is a convex function with $L$-Lipschitz continuous gradient with respect to $y$. Secondly, by the strongly convexity of $\varphi(x, y, \lambda):=-L(x,y,\lambda)-g(y)$, it has a nonempty set $S$ of minimizers with respect to $y$ in $\mathcal{Y}$ and satisfies the quadratic growth condition $\varphi(x, y, \lambda)\ge\varphi^*+\frac{\mu}{2}dist^2(y,S)$, where $dist(y,S):=\inf_{z\in S}\|z-y\|$ and $\varphi^*=\min_{y\in \mathcal{Y}} \varphi(x, y, \lambda)$. Thus, by Corollary 3.6 in \cite{Drusvyatskiy}, the proof is completed.
\end{proof}

Next, we show the relation between the stationary point defined in Definition \ref{gap-f} and that defined in \cite{Tsaknakis}. More detailedly, we prove that an $\varepsilon$-stationary point of \eqref{problem:1} shown in Definition \ref{gap-f} is also a $(b_1\varepsilon,b_2\varepsilon)$-approximate stationary solution of \eqref{problem:1} that shown in Definition 4 in \cite{Tsaknakis} with $b_1>0$ and $b_2>0$,  when $h(x)\equiv0$, $g(y)\equiv0$, and $f(x,y)$ is a strongly convex and a strongly concave function with respect to $x$ and $y$, respectively. Before that, we give the Definition 4 in \cite{Tsaknakis} as follows.
\begin{defi}\label{gap-h}($(\varepsilon,\delta)$-approximate Stationary Solution~\cite{Tsaknakis}).
	For any given $\varepsilon>0$ and $\delta$,	a point $(x,y,\lambda)$ is a $(\varepsilon,\delta)$-approximate stationary solution of problem \eqref{problem:1} if it holds that
	\begin{align*}
		&\frac{1}{\gamma}\left\| \lambda-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla H(\lambda)\right)\right\|\le\varepsilon,\\
		& \|x-x^*(\lambda)\|^2+\|y-y^*(x^*(\lambda),\lambda)\|^2\le\delta^2,
	\end{align*}
	where $\gamma>0$ is a constant independent of $\varepsilon$ and $\delta$, and
	\begin{align*}
		H(\lambda)&=\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}L(x,y,\lambda), \\
		x^*(\lambda)&=\arg\min_{x\in\mathcal{X}}\Phi(x,\lambda).
	\end{align*}
\end{defi}
\begin{thm}\label{st}
	Suppose that Assumption  \ref{ass:Lip} holds. If $f(x,y)$ is a $\mu_x$-strongly convex and a $\mu_y$-strongly concave function with respect to $x$ and $y$ with modulas of $\mu_x$ and $\mu_y$, respectively, $h(x)\equiv0$ and $g(y)\equiv0$, then we have that an $\varepsilon$-stationary point of \eqref{problem:1} is also a $(b_1\varepsilon,b_2\varepsilon)$-approximate stationary solution of \eqref{problem:1}. That is
	if $\|\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)\|\le\varepsilon$, then
	\begin{align*}
		&\frac{1}{\gamma}\left\| \lambda-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla H(\lambda)\right)\right\|\le b_1\varepsilon,\\
		& \|x-x^*(\lambda)\|^2+\|y-y^*(x^*(\lambda),\lambda)\|^2\le b_2^2\varepsilon^2,
	\end{align*}
	where $b_1=1+\frac{\eta_y\|B\|}{\beta}+\left(\|A\|+\frac{\|B\|L}{\mu_y}\right)\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)$, $\eta_x=\frac{(2\beta+\mu_x)(\beta+L_\Phi^{'})}{\mu_x\beta}$, $L_\Phi^{'}=L+\frac{L^2}{\mu_y}$, $\eta_y=\frac{(2\beta+\mu_y)(\beta+L)}{\mu_y\beta}$ and $b_2=\sqrt{\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)^2+\left(\frac{\eta_y}{\beta}+\frac{L}{\mu_y}\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)\right)^2}$.
\end{thm}

\begin{proof}
	By the triangle inequality, we first have
	\begin{align}
		\|y-y^*(x^*(\lambda),\lambda)\|
		\le \|y-y^*(x,\lambda)\|+\|y^*(x,\lambda)-y^*(x^*(\lambda),\lambda)\|.\label{st:1}
	\end{align}
On the one hand, by global error bound condition \eqref{lem:eb:1} in Lemma \ref{lem:eb} the definiton of $\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)$, we get
	\begin{align}
		\|y-y^*(x,\lambda)\|
		\le&\eta_y\left\| y-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y+ \frac{1}{\beta} \nabla _yL\left( x,y,\lambda \right) \right)\right\| \nonumber\\
		\leq& \frac{\eta_y}{\beta}\|\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)\|
		\le\frac{\eta_y}{\beta}\varepsilon.\label{st:2}
	\end{align}
On the other hand, by Lemma 4 in \cite{Tsaknakis}, we obtain
	\begin{align}
		\|y^*(x,\lambda)-y^*(x^*(\lambda),\lambda)\|
		\le\frac{L}{\mu_y}\|x-x^*(\lambda)\|.\label{st:3}
	\end{align}
By plugging \eqref{st:2} and \eqref{st:3} into \eqref{st:1}, we have
	\begin{align}
		\|y-y^*(x^*(\lambda),\lambda)\|
		\le \frac{\eta_y}{\beta}\varepsilon+\frac{L}{\mu_y}\|x-x^*(\lambda)\|.\label{st:4}
	\end{align}
	Since that $f(x,y)$ is a strongly convex function w.r.t $x$, similar to the proof of Lemma \ref{lem:eb},
	we can get that
	\begin{align}
		\|x-x^*(\lambda)\| \le\eta_x\left\| x-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _x\Phi\left( x,\lambda \right) \right)\right\|.\label{st:4.5}
		\end{align}
	By \eqref{gradx:nsc}, the definition of $\Phi(x,\lambda)$, the triangle inequality and the nonexpansive property of the proximity operator, we have
	\begin{align}
	     &\left\| x-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _x\Phi\left( x,\lambda \right) \right)\right\|\nonumber\\
		=&\left\| x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _xL\left( x,y^*(x,\lambda),\lambda \right) \right)\right\|\nonumber\\
		\le&\left\|\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _xL\left( x,y,\lambda \right) \right)-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _xL\left( x,y^*(x,\lambda),\lambda \right) \right)\right\|\nonumber\\
		&+\left\| x-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}\left( x- \frac{1}{\alpha} \nabla _xL\left( x,y,\lambda\right) \right)\right\|\nonumber\\
		\le&\frac{ L}{\alpha}\|y-y^*(x,\lambda)\|+\frac{1}{\alpha}\|\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)\|\nonumber\\
		\le&\left(\frac{\eta_y L}{\alpha\beta}+\frac{1}{\alpha}\right)\varepsilon.\label{st:5}
	\end{align}
 Combining \eqref{st:4}, \eqref{st:4.5} and \eqref{st:5}, we obtain
	\begin{align}
		& \|x-x^*(\lambda)\|^2+\|y-y^*(x^*(\lambda),\lambda)\|^2\nonumber\\
		&\le\left[\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)^2+\left(\frac{\eta_y}{\beta}+\frac{L}{\mu_y}\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)\right)^2\right]\varepsilon^2.\label{st:5.5}
	\end{align}
Next, by the triangle inequality and the nonexpansive property of the proximity operator, we have
	\begin{align}
		&\frac{1}{\gamma}\left\| \lambda-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla H(\lambda)\right)\right\|\nonumber\\
		\le&\frac{1}{\gamma}\left\| \lambda-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla_\lambda L(x,y,\lambda)\right)\right\|+\frac{1}{\gamma}\left\|\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla_\lambda L(x,y,\lambda)\right)-\mathcal{P}_{\Lambda}\left(\lambda-\gamma\nabla H(\lambda)\right)\right\|\nonumber\\
		\le&\|\nabla G^{\alpha,\beta,\gamma}( x,y,\lambda)\|+\|\nabla_\lambda L(x,y,\lambda)-\nabla H(\lambda)\|\nonumber\\
			\le&\varepsilon +\|\nabla_\lambda L(x,y,\lambda)-\nabla H(\lambda)\|.\label{st:6}
				\end{align}
			By Lemma 1 in \cite{Tsaknakis}, we have $\nabla H(\lambda)=-Ax^*(\lambda)-By^*(x^*(\lambda),\lambda)+c$. Then, by the triangle inequality and using \eqref{st:4}, \eqref{st:4.5} and \eqref{st:5}, we obtain
			\begin{align}
				& \|\nabla_\lambda L(x,y,\lambda)-\nabla H(\lambda)\|\nonumber\\
		= &\|A(x-x^*(\lambda))+B(y-y^*(x^*(\lambda),\lambda))\|\nonumber\\
		\le&\left[\frac{\eta_y\|B\|}{\beta}+\left(\|A\|+\frac{\|B\|L}{\mu_y}\right)\left(\frac{\eta_y\eta_x L}{\alpha\beta}+\frac{\eta_x}{\alpha}\right)\right]\varepsilon.\label{st:7}
	\end{align}
The proof is completed by combing \eqref{st:5.5}, \eqref{st:6} and \eqref{st:7}.
\end{proof}

Next, we provide an upper bound estimate of the difference between $\Phi(x_{k+1},\lambda_{k+1})$ and $\Phi(x_k,\lambda_k)$.
\begin{lem}\label{lem1}
	Suppose that Assumption \ref{ass:Lip} holds. Let $\{\left(x_k,y_k\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1},
	then $\forall k \ge 1$, and for any $a>0$, $b>0$,
	\begin{align}\label{lem1:iq1}
	  &\Phi(x_{k+1},\lambda_{k+1}) -\Phi(x_k,\lambda_k)\nonumber \\
\leq& \langle  \nabla _xL( x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle+\frac{(L+\beta)^2\eta^2}{2\beta^2}\left(\frac{L^2}{a}+\frac{2\|B\|^2}{b} \right)\|y_{k+1}-y_k\|^2 \nonumber \\
&+\left(\frac{\|B\|^2L^2\eta^2}{b\beta^2}+\frac{a+L_\Phi}{2}\right)\|x_{k+1}-x_k\|^2+\frac{ b+L_\Phi}{2}\|\lambda_{k+1}-\lambda_k\|^2\nonumber \\
&+\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle.
	\end{align}
\end{lem}

\begin{proof}
Since that $\Phi(x, \lambda)$ is $L_\Phi$-smooth with respect to $x$ and by \eqref{gradx:nsc}, we have that
	\begin{align} \label{lem1:2}
	&\Phi(x_{k+1},\lambda_{k})-\Phi(x_{k},\lambda_k)\nonumber\\
\le &\langle \nabla _x\Phi(x_{k},\lambda_k) ,x_{k+1}-x_k \rangle  +\frac{L_\Phi}{2}\|x_{k+1}-x_k\|^2\nonumber\\
=&\langle \nabla _xL(x_{k},y^*(x_k,\lambda_k),\lambda_k) ,x_{k+1}-x_k \rangle  +\frac{L_\Phi}{2}\|x_{k+1}-x_k\|^2\nonumber\\
=&\langle \nabla _xL(x_{k},y^*(x_k,\lambda_k),\lambda_k)-\nabla _xL(x_{k},y_{k+1},\lambda_k) ,x_{k+1}-x_k \rangle  +\frac{L_\Phi}{2}\|x_{k+1}-x_k\|^2\nonumber\\
&+\langle \nabla _xL(x_{k},y_{k+1},\lambda_k) ,x_{k+1}-x_k \rangle.
	\end{align}
By the Cauchy-Schwarz inequality, for any $a>0$, we have
 	\begin{align}
&\langle \nabla _xL(x_{k},y^*(x_k,\lambda_k),\lambda_k)-\nabla _xL(x_{k},y_{k+1},\lambda_k) ,x_{k+1}-x_k \rangle\nonumber\\
=&\langle \nabla _xf(x_{k},y^*(x_k,\lambda_k))-\nabla _xf(x_{k},y_{k+1}) ,x_{k+1}-x_k \rangle\nonumber\\
\le&\frac{L^2}{2a}\|y_{k+1}-y^*(x_k,\lambda_k)\|^2+\frac{a}{2}\|x_{k+1}-x_k\|^2.\label{lem1:3}
\end{align}
By \eqref{lem:eb:1} in Lemma \ref{lem:eb}, we further have
	\begin{align}\label{lem1:4}
	&\|y_{k+1}-y^*(x_k,\lambda_k)\
\le \eta\left\| y_{k+1}-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_k,y_{k+1},\lambda_k \right) \right)\right\|.
	\end{align}
By \eqref{update-y}, the non-expansive property of the proximity operator $\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}(\cdot)$ and Assumption \ref{ass:Lip}, we obtain
	\begin{align}\label{lem1:5}
&\left\| y_{k+1}-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_k,y_{k+1},\lambda_k \right) \right)\right\|\nonumber\\
= &\left\| \operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k}+ \frac{1}{\beta} \nabla _yL\left( x_k,y_{k},\lambda_k \right) \right)-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_k,y_{k+1},\lambda_k \right) \right)\right\|\nonumber\\
\le&\|y_{k+1}-y_k\|+\frac{1}{\beta}\|\nabla _yL\left( x_k,y_{k+1},\lambda_k \right)-\nabla _yL\left( x_k,y_{k},\lambda_k \right)\|\nonumber\\
=&\|y_{k+1}-y_k\|+\frac{1}{\beta}\|\nabla _yf\left( x_k,y_{k+1}\right)-\nabla _yf\left( x_k,y_{k} \right)\|\le\frac{L+\beta}{\beta}\|y_{k+1}-y_k\|.
	\end{align}
Combing \eqref{lem1:3}, \eqref{lem1:4} and \eqref{lem1:5}, we get
 	\begin{align} \label{lem1:3:2}
&\langle \nabla _xL(x_{k},y^*(x_k,\lambda_k),\lambda_k)-\nabla _xL(x_{k},y_{k+1},\lambda_k) ,x_{k+1}-x_k \rangle\nonumber\\
\le&\frac{L^2\eta^2(L+\beta)^2}{2a\beta^2}\|y_{k+1}-y_k\|^2+\frac{a}{2}\|x_{k+1}-x_k\|^2.
	\end{align}
 By plugging \eqref{lem1:3:2} into \eqref{lem1:2}, we have
	\begin{align}\label{lem1:6}
&\Phi(x_{k+1},\lambda_{k})-\Phi(x_{k},\lambda_k)\nonumber\\
\le&\frac{L^2\eta^2(L+\beta)^2}{2a\beta^2}\|y_{k+1}-y_k\|^2+\frac{a+L_\Phi}{2}\|x_{k+1}-x_k\|^2\nonumber\\
&+\langle \nabla _xL(x_{k},y_{k+1},\lambda_k) ,x_{k+1}-x_k \rangle.
	\end{align}
On the other hand, $\Phi(x, \lambda)$ is $L_\Phi$-smooth with respect to $\lambda$ and \eqref{gradla:nsc}, we have
	\begin{align} \label{lem1:7}
	&\Phi(x_{k+1},\lambda_{k+1})-\Phi(x_{k+1},\lambda_k)\nonumber\\
\le &\langle \nabla _\lambda\Phi(x_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle  +\frac{L_\Phi}{2}\|\lambda_{k+1}-\lambda_k\|^2\nonumber\\
=&\langle \nabla _\lambda L(x_{k+1},y^*(x_{k+1},\lambda_k),\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle  +\frac{L_\Phi}{2}\|\lambda_{k+1}-\lambda_k\|^2\nonumber\\
=&\langle \nabla _\lambda L(x_{k+1},y^*(x_{k+1},\lambda_k),\lambda_k)-\nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle\nonumber\\
&+\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle+\frac{L_\Phi}{2}\|\lambda_{k+1}-\lambda_k\|^2.
	\end{align}
Next, we estimate the first term in the right hand side of \eqref{lem1:7}. By the Cauchy-Schwarz inequality, for any $b>0$ we obtain
 	\begin{align} \label{lem1:8}
&\langle \nabla _\lambda L(x_{k+1},y^*(x_{k+1},\lambda_k),\lambda_k)-\nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle\nonumber\\
=&-\langle B(y^*(x_{k+1},\lambda_k)-y_{k+1}) ,\lambda_{k+1}-\lambda_k \rangle\nonumber\\
\le&\frac{\|B\|^2}{2b}\|y_{k+1}-y^*(x_{k+1},\lambda_k)\|^2+\frac{b}{2}\|\lambda_{k+1}-\lambda_k\|^2.
	\end{align}
By \eqref{lem:eb:1} in Lemma \ref{lem:eb}, we further have
	\begin{align}
	&\|y_{k+1}-y^*(x_{k+1},\lambda_k)\|\nonumber\\
\le &\eta\left\| y_{k+1}-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_{k+1},y_{k+1},\lambda_k \right) \right)\right\|.\label{lem1:9}
	\end{align}
By \eqref{update-y}, the non-expansive property of the proximity operator $\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}(\cdot)$ and Assumption \ref{ass:Lip}, we obtain
	\begin{align}\label{lem1:10}
&\left\| y_{k+1}-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_{k+1},y_{k+1},\lambda_k \right) \right)\right\|\nonumber\\
= &\left\| \operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k}+ \frac{1}{\beta} \nabla _yL\left( x_k,y_{k},\lambda_k \right) \right)-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_{k+1}+ \frac{1}{\beta} \nabla _yL\left( x_{k+1},y_{k+1},\lambda_k \right) \right)\right\|\nonumber\\
\le&\|y_{k+1}-y_k\|+\frac{1}{\beta}\|\nabla _yL\left( x_{k+1},y_{k+1},\lambda_k \right)-\nabla _yL\left( x_k,y_{k},\lambda_k \right)\|\nonumber\\
\le&\frac{L+\beta}{\beta}\|y_{k+1}-y_k\|+\frac{L}{\beta}\|x_{k+1}-x_k\|.
	\end{align}
By combing \eqref{lem1:9} and \eqref{lem1:10} and using the fact $(a+b)^2\le 2a^2+2b^2$, we get
	\begin{align}\label{lem1:11}
	&\|y_{k+1}-y^*(x_{k+1},\lambda_k)\|^2\nonumber\\
\le &\frac{2(L+\beta)^2\eta^2}{\beta^2}\|y_{k+1}-y_k\|^2+\frac{2L^2\eta^2}{\beta^2}\|x_{k+1}-x_k\|^2.
	\end{align}
By combining \eqref{lem1:7}, \eqref{lem1:8} and \eqref{lem1:11}, we have
	\begin{align} \label{lem1:iq13}
	&\Phi(x_{k+1},\lambda_{k+1})-\Phi(x_{k+1},\lambda_k)\nonumber\\
\le&\frac{\|B\|^2(L+\beta)^2\eta^2}{b\beta^2}\|y_{k+1}-y_k\|^2
+\frac{\|B\|^2L^2\eta^2}{b\beta^2}\|x_{k+1}-x_k\|^2\nonumber\\
&+\frac{b+L_\Phi}{2}\|\lambda_{k+1}-\lambda_k\|^2+\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k) ,\lambda_{k+1}-\lambda_k \rangle.
	\end{align}
The proof is then completed by adding \eqref{lem1:6} and \eqref{lem1:iq13}.
\end{proof}

Next, we provide an lower bound for the difference between $L(x_{k+1},y_{k+1},\lambda_{k+1})$ and $L(x_k,y_k,\lambda_k)$.
\begin{lem}\label{lem2}
	Suppose that Assumption \ref{ass:Lip} holds. Let $\{\left(x_k,y_k\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1},
	then $\forall k \ge 1$,
	\begin{align}\label{lem2:iq1}
	  &L(x_{k+1},y_{k+1},\lambda_{k+1})-L( x_{k},y_{k},\lambda_k)\nonumber \\
\geq&\left(\beta-\frac{L}{2}\right)\|y_{k+1}-y_k\|^2-\frac{L}{2}\| x_{k+1}-x_{k} \|^2+\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_{k} \rangle\nonumber\\
&+\langle\xi_{k+1},y_{k+1}-y_k \rangle+\langle \nabla _{x}L(x_{k},y_{k+1},\lambda_k),x_{k+1}-x_{k} \rangle,
	\end{align}
where $\xi_{k+1}\in\partial g(y_{k+1})$.

\end{lem}

\begin{proof}
  The optimality condition for $y_k$ in \eqref{update-y} implies that $\forall y\in \mathcal{Y}$ and $\forall k\geq 1$,
	\begin{equation}\label{lem2:2}
		\langle \nabla _yL(x_{k},y_k,\lambda_k)-\beta(y_{k+1}-y_k)-\xi_{k+1},y-y_{k+1} \rangle \le 0,
	\end{equation}
where $\xi_{k+1}\in\partial g(y_{k+1})$. By choosing $y=y_k$ in \eqref{lem2:2}, we have
	\begin{equation}\label{lem2:3}
		\langle \nabla _yL(x_{k},y_k,\lambda_k),y_{k+1}-y_k \rangle \ge \beta\|y_{k+1}-y_k\|^2+\langle\xi_{k+1},y_{k+1}-y_k \rangle.
	\end{equation}
By  Assumption \ref{ass:Lip}, the gradient of $L(x,y,\lambda)$ is Lipschitz continuous with respect to $y$, which implies that
	\begin{align}\label{lem2:4}
	  &L(x_{k},y_{k+1},\lambda_k)-L( x_{k},y_{k},\lambda_k)\nonumber\\
\ge& \langle \nabla _{y}L(x_{k},y_{k},\lambda_k),y_{k+1}-y_{k} \rangle -\frac{L}{2}\| y_{k+1}-y_{k} \|^2\nonumber\\
\ge&\left(\beta-\frac{L}{2}\right)\|y_{k+1}-y_k\|^2+\langle\xi_{k+1},y_{k+1}-y_k \rangle,
	\end{align}
where the last inequality is by \eqref{lem2:3}. Similarly, since that the gradient of $L(x,y,\lambda)$ is Lipschitz continuous with respect to $x$, we obtain
	\begin{align}\label{lem2:5}
	  &L(x_{k+1},y_{k+1},\lambda_k)-L( x_{k},y_{k+1},\lambda_k)\nonumber\\
\ge& \langle \nabla _{x}L(x_{k},y_{k+1},\lambda_k),x_{k+1}-x_{k} \rangle -\frac{L}{2}\| x_{k+1}-x_{k} \|^2.
	\end{align}
On the other hand, it can be easily checked that
	\begin{align}\label{lem2:iq6}
	  &L(x_{k+1},y_{k+1},\lambda_{k+1})-L( x_{k+1},y_{k+1},\lambda_k)\nonumber\\
=& \langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_{k} \rangle.
	\end{align}
The proof is then completed by adding \eqref{lem2:4}, \eqref{lem2:5} and \eqref{lem2:iq6}.
\end{proof}

We now establish an important recursion for the Algorithm \ref{alg:1}.
\begin{lem}\label{lem3}
	Suppose that Assumption \ref{ass:Lip} holds. Denote
	\begin{align*}
    S(x,y,\lambda)&=2\Phi(x,\lambda)-L(x,y,\lambda)+h(x)+g(y).
	\end{align*}
	Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1}, then $\forall k \geq 1$,
    \begin{align}\label{lem3:1}
    &S(x_{k+1},y_{k+1},\lambda_{k+1})-S( x_{k},y_{k},\lambda_k)\nonumber \\
    \le&-\left(\alpha-\frac{L^3}{(L+\beta)^2}-\frac{L(L+\beta)^2\eta^2}{\beta^2}
    -\frac{L^2}{\mu}-\frac{3L}{2}\right)\|x_{k+1}-x_k\|^2 \nonumber \\
&-\left(\frac{1}{\gamma}-\frac{2\|B\|^2(L+\beta)^2\eta^2}{L\beta^2}-L-\frac{L^2}{\mu} \right)\|\lambda_{k+1}-\lambda_{k}\|^2-\left(\beta-\frac{5L}{2}\right)\|y_{k+1}-y_k\|^2.
    \end{align}
\end{lem}

\begin{proof}
	Denote 	$S_1(x,y,\lambda)=2\Phi(x,\lambda)-L(x,y,\lambda)$.
Combining \eqref{lem1:iq1} and \eqref{lem2:iq1}, we obtain
    \begin{align}\label{lem3:iq2}
    &S_1(x_{k+1},y_{k+1},\lambda_{k+1})-S_1( x_{k},y_{k},\lambda_k)\nonumber \\
    \le&-\left(\beta-\frac{L}{2}-\frac{(L+\beta)^2\eta^2}{\beta^2}\left(\frac{L^2}{a}+\frac{2\|B\|^2}{b} \right)\right)\|y_{k+1}-y_k\|^2 \nonumber \\
&+\left(\frac{2\|B\|^2L^2\eta^2}{b\beta^2}+a+L_\Phi+\frac{L}{2}\right)\|x_{k+1}-x_k\|^2\nonumber \\
&+\left(b+L_\Phi \right)\|\lambda_{k+1}-\lambda_k\|^2+\langle  \nabla _xL( x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle\nonumber\\
&-\langle\xi_{k+1},y_{k+1}-y_k \rangle+\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_{k} \rangle,
    \end{align}
where $\xi_{k+1}\in\partial g(y_{k+1})$. The optimality condition for $\lambda_k$ in \eqref{update-lambda} implies that
	\begin{equation}\label{lem3:iq3}
		\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k)+\frac{1}{\gamma}(\lambda_{k+1}-\lambda_{k}),\lambda-\lambda_{k+1} \rangle \ge 0.
	\end{equation}
By choosing $\lambda=\lambda_k$ in \eqref{lem3:iq3}, we have
	\begin{equation}\label{lem3:iq4}
		\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k)+\frac{1}{\gamma}(\lambda_{k+1}-\lambda_{k}),\lambda_k-\lambda_{k+1} \rangle \ge 0.
	\end{equation}
By combining \eqref{lem3:iq2} and \eqref{lem3:iq4}, we have
    \begin{align}\label{lem3:2}
    &S_1(x_{k+1},y_{k+1},\lambda_{k+1})-S_1( x_{k},y_{k},\lambda_k)\nonumber \\
    \le&-\left(\beta-\frac{L}{2}-\frac{(L+\beta)^2\eta^2}{\beta^2}\left(\frac{L^2}{a}+\frac{2\|B\|^2}{b} \right)\right)\|y_{k+1}-y_k\|^2 \nonumber \\
&+\left(\frac{2\|B\|^2L^2\eta^2}{b\beta^2}+a+L_\Phi+\frac{L}{2}\right)\|x_{k+1}-x_k\|^2\nonumber \\
&-\left(\frac{1}{\gamma}- b-L_\Phi \right)\|\lambda_{k+1}-\lambda_k\|^2+\langle  \nabla _xL( x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle\nonumber\\
&-\langle\xi_{k+1},y_{k+1}-y_k \rangle.
    \end{align}
The optimality condition for $x_k$ in \eqref{update-x} implies that $\forall x\in \mathcal{X}$ and $\forall k\geq 1$,
	\begin{equation}\label{lem3:3}
		\langle \nabla _xL(x_{k},y_{k+1},\lambda_k)+\alpha(x_{k+1}-x_k)+\zeta_{k+1},x-x_{k+1} \rangle \ge 0,
	\end{equation}
where $\zeta_{k+1}\in\partial h(x_{k+1})$. By choosing $x=x_k$ in \eqref{lem3:3}, we have
	\begin{equation}\label{lem3:4}
		\langle \nabla _xL(x_{k},y_{k+1},\lambda_k),x_{k+1}-x_k \rangle \le -\alpha\|x_{k+1}-x_k\|^2-\langle\zeta_{k+1},x_{k+1}-x_k \rangle.
	\end{equation}
Plugging \eqref{lem3:4} into \eqref{lem3:2}, we obtain
    \begin{align}\label{lem3:5}
    &S_1(x_{k+1},y_{k+1},\lambda_{k+1})-S_1( x_{k},y_{k},\lambda_k)\nonumber \\
    \le&-\left(\beta-\frac{L}{2}-\frac{(L+\beta)^2\eta^2}{\beta^2}\left(\frac{L^2}{a}+\frac{2\|B\|^2}{b} \right)\right)\|y_{k+1}-y_k\|^2 \nonumber \\
&-\left(\alpha-\frac{2\|B\|^2L^2\eta^2}{b\beta^2}-a-L_\Phi-\frac{L}{2}\right)\|x_{k+1}-x_k\|^2\nonumber \\
&-\left(\frac{1}{\gamma}- b-L_\Phi \right)\|\lambda_{k+1}-\lambda_k\|^2-\langle\zeta_{k+1},x_{k+1}-x_k \rangle-\langle\xi_{k+1},y_{k+1}-y_k \rangle.
    \end{align}
Utilizing the convexity of $h(x)$ and $g(y)$, and by the definition of subgradient, we have $h(x_{k})-h( x_{k+1})\ge\langle\zeta_{k+1},x_{k}-x_{k+1} \rangle$ and $g(y_{k})-g( y_{k+1})\ge\langle\xi_{k+1},y_{k}-y_{k+1} \rangle.$
    Plugging them into \eqref{lem3:5} and using the definition of $S(x,y,\lambda)$, we obtain
    \begin{align}\label{lem3:6}
    &S(x_{k+1},y_{k+1},\lambda_{k+1})-S( x_{k},y_{k},\lambda_k)\nonumber \\
    \le&-\left(\beta-\frac{L}{2}-\frac{(L+\beta)^2\eta^2}{\beta^2}\left(\frac{L^2}{a}+\frac{2\|B\|^2}{b} \right)\right)\|y_{k+1}-y_k\|^2 \nonumber \\
&-\left(\alpha-\frac{2\|B\|^2L^2\eta^2}{b\beta^2}-a-L_\Phi-\frac{L}{2}\right)\|x_{k+1}-x_k\|^2\nonumber \\
&-\left(\frac{1}{\gamma}- b-L_\Phi \right)\|\lambda_{k+1}-\lambda_k\|^2.
    \end{align}
The proof is then completed by $L_\Phi=L+\frac{L^2}{\mu}$ and choosing $a=\frac{L(L+\beta)^2\eta^2}{\beta^2}$ and $b=\frac{2\|B\|^2(L+\beta)^2\eta^2}{L\beta^2}$ in \eqref{lem3:6}.
\end{proof}

Let $\nabla G^{\alpha,\beta,\gamma}\left( x_k,y_k,\lambda_k \right)$ be defined as  in Definition \ref{gap-f}, we provide an upper bound on $\| \nabla G^{\alpha,\beta,\gamma}(x_k,y_k,\lambda_k)\|$ in the following lemma.

\begin{lem}\label{lem4}
	Suppose that Assumption \ref{ass:Lip} holds. Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1}. Then $\forall k \geq 1$,
	\begin{align}\label{lem4:1}
	&\|\nabla G^{\alpha,\beta,\gamma}( x_k,y_{k},\lambda_k)\|^2\nonumber\\
	\le& (\beta^2+2L^{2}+3\|B\|^2)\|y_{k+1}-y_k\|^2+(2\alpha^2+3\|A\|^2)\|x_{k+1}-x_k\|^2\nonumber\\
    &+\frac{3}{\gamma^2}\|\lambda_{k+1}-\lambda_k\|^2.
	\end{align}

\end{lem}

\begin{proof}
By \eqref{update-y}, we immediately obtain
	\begin{equation}\label{lem4:2}
	\left\| \beta\left( y_k-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_k+ \frac{1}{\beta} \nabla _yL\left( x_k,y_k,\lambda_k\right) \right) \right) \right\|=\beta\|y_{k+1}-y_k\|.
	\end{equation}
	On the other hand, by \eqref{update-x} and the Cauchy-Schwartz inequality, we have
	\begin{align}\label{lem4:3}
	&\|	\alpha ( x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}( x_k-\frac{1}{\alpha}\nabla _xL\left( x_k,y_k,\lambda_k \right) ) )\|\nonumber\\
	\le &\alpha \| \operatorname{Prox}_{h,\mathcal{X}}^{\alpha}( x_k-\frac{1}{\alpha} \nabla _xL(x_{k},y_{k+1},\lambda_k) )-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha}( x_k-\frac{1}{\alpha} \nabla _xL(x_{k},y_{k},\lambda_k) )\|\nonumber\\
&+\alpha\| x_{k+1}-x_k\|\nonumber\\
	\leq & \alpha\|x_{k+1}-x_k\| +L\|y_{k+1}-y_k\|,
	\end{align}
where the last inequaliy is by the nonexpansive property of the projection operator and Assumption \ref{ass:Lip}. By \eqref{update-lambda}, the Cauchy-Schwartz inequality and the nonexpansive property of the projection operator,  we obtain
	\begin{align}\label{lem4:4}
	&\|\frac{1}{\gamma}\left( \lambda_k -\mathcal{P}_{\Lambda}\left(\lambda_k-\gamma\nabla_{\lambda}L(x_k,y_k,\lambda_k)\right)\right)\|\nonumber\\
	\le &\frac{1}{\gamma}\left\| \mathcal{P}_{\Lambda}\left(\lambda_k-\gamma\nabla_{\lambda}L(x_{k+1},y_{k+1},\lambda_k)\right)-
\mathcal{P}_{\Lambda}\left(\lambda_k-\gamma\nabla_{\lambda}L(x_k,y_k,\lambda_k)\right)\right\|\nonumber\\
&+\frac{1}{\gamma}\| \lambda_{k+1}-\lambda_k\|\nonumber\\
	\leq & \frac{1}{\gamma}\|\lambda_{k+1}-\lambda_k\|+\|A\|\|x_{k+1}-x_k\| +\|B\|\|y_{k+1}-y_k\|.
	\end{align}
Combing \eqref{lem4:2}, \eqref{lem4:3} and \eqref{lem4:4}, and using Cauchy-Schwarz inequality, we complete the proof.
\end{proof}

 Then we obtain the following Theorem that provide a bound on $T(\varepsilon)$, where $T(\varepsilon):=\min\{k \mid \|\nabla G^{\alpha,\beta,\gamma}(x_k,y_k,\lambda_k)\|\leq \varepsilon \}$ and $\varepsilon>0$ is a given target accuracy. Note that $\Lambda=\mathbb{R}^p$ if $\unlhd$ is $=$. Thus, if there are only the equality constraints, $\|\nabla G^{\alpha,\beta,\gamma}(x_k,y_k,\lambda_k)\|\leq\varepsilon$ implies that the violation of the constraint at $(x_k,y_k,\lambda_k)$ also satisfies the given accuracy, i.e., $\|Ax_{k}+By_{k}-c\|\leq \varepsilon$. If there are also some inequality constraints, we also provide an upper bound for the violation of the constraint at $(x_k,y_k,\lambda_k)$.

\begin{thm}\label{thm1}
	Suppose that Assumptions \ref{fea} and \ref{ass:Lip} hold. Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1}. Let $\eta=\frac{(2\beta+\mu)(\beta+L)}{\mu\beta}$. If
  	\begin{align}\label{thm1:1}
	&\beta>\frac{5L}{2}, \alpha>\frac{L^3}{(L+\beta)^2}+\frac{L(L+\beta)^2\eta^2}{\beta^2}
    +\frac{L^2}{\mu}+\frac{3L}{2},\nonumber\\
    &\frac{1}{\gamma}>\left(\frac{2\|B\|^2(L+\beta)^2\eta^2}{L\beta^2}+L+\frac{L^2}{\mu} \right),
	\end{align}
then $\forall \varepsilon>0$, we have
	$$ T\left( \varepsilon \right) \le \frac{d_2}{\varepsilon ^2 d_1},$$
		where $d_1:=\frac{\min\{\alpha-\frac{L^3}{(L+\beta)^2}-\frac{L(L+\beta)^2\eta^2}{\beta^2}
		-\frac{L^2}{\mu}-\frac{3L}{2},\ \beta-\frac{5L}{2},\ \frac{1}{\gamma}-\frac{2\|B\|^2(L+\beta)^2\eta^2}{L\beta^2}-L-\frac{L^2}{\mu}\} }{\max \{ \beta^2+2L^{2}+3\|B\|^2,\ 2\alpha^2+3\|A\|^2,\ 3/\gamma^2\} }$, $d_2:=S(x_{1},y_{1},\lambda_{1})-\underbar{S}$ with $\underbar{S}:=\min_{\lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}S(x,y,\lambda)$.
Moreover, for any $i\in\mathcal{K}$, if $k\ge T(\varepsilon)$, we have $$\max\{0,[Ax_{k}+By_{k}-c]_i\}\leq \varepsilon.$$
\end{thm}

\begin{proof}
By \eqref{thm1:1}, it can be easily checked that $d_1>0$. By multiplying $d_1$ on the both sides of \eqref{lem4:1} and using \eqref{lem3:1} in Lemma \ref{lem3}, we get
	\begin{align}
	d_1\|\nabla G^{\alpha,\beta,\gamma}( x_k,y_{k},\lambda_k)\|^2
	\le S(x_{k},y_{k},\lambda_{k})-S(x_{k+1},y_{k+1},\lambda_{k+1}).\label{thm1:5}
	\end{align}
    Summarizing both sides of \eqref{thm1:5} from $k=1$ to $T(\varepsilon)$, we then obtain
    \begin{align}
    &\sum_{k=1}^{T\left( \varepsilon \right)}{d_1\|\nabla G^{\alpha,\beta,\gamma}( x_k,y_{k},\lambda_k) \| ^2}
\le S(x_{1},y_{1},\lambda_{1})-S(x_{T(\varepsilon)+1},y_{T(\varepsilon)+1},\lambda_{T(\varepsilon)+1}).\label{thm1:6}
    \end{align}
Next we proof $\underbar{S}$ is a finite value.
By the definition of $\Phi(x,\lambda)$ and $S(x,y,\lambda)$ in Lemma \ref{lem3}, we have
    \begin{align*}
    S(x,y,\lambda)&=2\Phi(x,\lambda)-L(x,y,\lambda)+h(x)+g(y)\\
    &=2\max_{y\in\mathcal{Y}}L(x,y,\lambda)-L(x,y,\lambda)+h(x)+g(y)\\
    &\ge\max_{y\in\mathcal{Y}}L(x,y,\lambda)+h(x)+g(y).
    \end{align*}
Then, we immediately get
    \begin{align}
    &\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}S(x,y,\lambda)\nonumber\\
\ge&\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}
    \left\{\max_{y\in\mathcal{Y}}L(x,y,\lambda)+h(x)+g(y)\right\}\nonumber\\
\ge&\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}\left\{\max_{y\in\mathcal{Y}}L(x,y,\lambda)+h(x)\right\}
    +\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}g(y)\nonumber\\
    =&\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)\right\}
    +\min_{y\in\mathcal{Y}}g(y),\label{thm1:6.5}
    \end{align}
    where the second inequality is by the fact that $\min_x\left\{f_1(x)+f_2(x)\right\}\ge\min_x f_1(x)+\min_x f_2(x)$. By \eqref{thm1:6.5} and the fact that $\max_y f_1(y)+\max_y f_2(y)\ge\max_y\{f_1(y)+f_2(y)\}$, we get
    \begin{align}
    &\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}S(x,y,\lambda)-2\min_{y\in\mathcal{Y}}g(y)\nonumber\\
    \ge&\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)-g(y)\right\}\nonumber\\
    =&\min_{x\in\mathcal{X}}\max_{\substack{y\in\mathcal{Y}\\Ax+By\unlhd c}}\{f(x,y)+h(x)-g(y)\} >-\infty,\label{thm1:7}
    \end{align}
    where the second last equality is by Theorem \ref{dual}, and the last inequality is by the assumption that  $\mathcal{X}$ and $\mathcal{Y}$ are convex and compact sets. Also, we have $\min_{y\in\mathcal{Y}}g(y)>-\infty$, and thus $\min\limits_{\lambda\in\Lambda}\min\limits_{x\in\mathcal{X}}\min\limits_{y\in\mathcal{Y}}S(x,y,\lambda)>-\infty$.  Then, by \eqref{thm1:6} we obtain
    \begin{align*}
    \sum_{k=1}^{T\left( \varepsilon \right)}{d_1\|\nabla G^{\alpha,\beta,\gamma}( x_k,y_{k},\lambda_k) \| ^2}\le S(x_{1},y_{1},\lambda_{1})-\underbar{S}=d_2.
    \end{align*}
    In view of the definition of $T(\varepsilon)$, the above inequality implies that $\varepsilon ^2\le \frac{d_2}{T( \varepsilon )d_1}$ or equivalently, $T\left( \varepsilon \right) \le \frac{d_2}{\varepsilon ^2 d_1}$. This completes the first part of the proof.

       Next, we will show the constraint violation is small at $(x_k,y_k,\lambda_k)$ when $\unlhd$ is $\le$.
   If $k\ge T(\varepsilon)$, $\|\nabla G^{\alpha,\beta,\gamma}( x_k,y_{k},\lambda_k)\|\le\varepsilon$, then by Lemma \ref{lem2.1},  we have $\max\{0,[Ax_{k}+By_{k}-c]_i\}\le\varepsilon$ which completes the proof.
\end{proof}

\begin{re}
 Denote $\kappa=L/\mu$. If we set $\beta=3L$, by Theorem \ref{thm1} we have that $\eta=\mathcal{O}(\kappa)$, $\alpha=\mathcal{O}(\kappa^2)$ and $1/\gamma=\mathcal{O}(\kappa^2)$, which imlies that the number of iterations for Algorithm \ref{alg:1} to obtain an $\varepsilon$-stationary point of \eqref{problem:1} is bounded by $\mathcal{O}\left(\kappa^2\varepsilon ^{-2} \right)$ under the nonconvex-strongly concave setting.
\end{re}

\subsection{Nonconvex-Concave Setting}
In this subsection, we prove the iteration complexity of Algorithm \ref{alg:1} under the nonconvex-concave setting. $\forall k\ge 1$, we first denote
\begin{align}
	\Psi_k(x,\lambda)&=\max_{y\in\mathcal{Y}}L_k(x,y,\lambda),\label{sc:2}\\
	\tilde{y}_k^*(x,\lambda)&=\arg\max_{y\in\mathcal{Y}}L_k(x,y,\lambda).\label{sc:3}
\end{align}
We also need to make the following assumption on the parameter $\rho_k$.
\begin{ass}\label{muk}
	$\{\rho_k\}$ is a nonnegative monotonically decreasing sequence.
\end{ass}

\begin{lem}\label{sc:lem1}
	Suppose that Assumption \ref{ass:Lip} holds. Denote
	\begin{align*}

		M_k(x,y,\lambda)&=2\Psi_k(x,\lambda)-L_k(x,y,\lambda)+h(x)+g(y).
	\end{align*}
	Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1}. Setting $\eta_k=\frac{(2\beta+\rho_k)(\beta+L)}{\rho_k\beta}$, then $\forall k \geq 1$,
	\begin{align}
		&M_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})-M_k( x_{k},y_{k},\lambda_k)\nonumber \\
		\le&-\left(\alpha_k-\frac{L^3}{(L+\beta)^2}-\frac{L(L+\beta)^2\eta_k^2}{\beta^2}
		-\frac{L^2}{\rho_k}-\frac{3L}{2}\right)\|x_{k+1}-x_k\|^2 \nonumber \\
		&-\left(\frac{1}{\gamma_k}-\frac{2\|B\|^2(L+\beta)^2\eta_k^2}{L\beta^2}-L-\frac{L^2}{\rho_k} \right)\|\lambda_{k+1}-\lambda_{k}\|^2\nonumber\\
		&-\left(\beta-\frac{5L}{2}\right)\|y_{k+1}-y_k\|^2+(\rho_k-\rho_{k+1})\sigma_y^2,\label{sc:lem1:1}
	\end{align}
	where $\sigma_y=\max\{\|y\| \mid y\in\mathcal{Y}\}$.
\end{lem}

\begin{proof}
	Similar to the proof of Lemma \ref{lem3}, by replacing $\alpha$ with $\alpha_k$, $\gamma$ with $\gamma_k$, $\mu$ with $\rho_k$, $\eta$ with $\eta_k$, respectively, we have
	\begin{align}
		&M_k(x_{k+1},y_{k+1},\lambda_{k+1})-M_k( x_{k},y_{k},\lambda_k)\nonumber \\
		\le&-\left(\alpha_k-\frac{L^3}{(L+\beta)^2}-\frac{L(L+\beta)^2\eta_k^2}{\beta^2}
		-\frac{L^2}{\rho_k}-\frac{3L}{2}\right)\|x_{k+1}-x_k\|^2 \nonumber \\
		&-\left(\frac{1}{\gamma_k}-\frac{2\|B\|^2(L+\beta)^2\eta_k^2}{L\beta^2}-L-\frac{L^2}{\rho_k} \right)\|\lambda_{k+1}-\lambda_{k}\|^2\nonumber\\
		&-\left(\beta-\frac{5L}{2}\right)\|y_{k+1}-y_k\|^2.\label{sc:lem1:2}
	\end{align}
	On the other hand, by \eqref{sc:1}, \eqref{sc:2} and \eqref{sc:3}, we obtain
	\begin{align}
		&M_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})-M_k( x_{k+1},y_{k+1},\lambda_{k+1})\nonumber \\
		=&2(\Psi_{k+1}(x_{k+1},\lambda_{k+1})-\Psi_{k}(x_{k+1},\lambda_{k+1}))-L_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		&+L_k(x_{k+1},y_{k+1},\lambda_{k+1}))\nonumber\\
		=&2(L_{k+1}(x_{k+1},\tilde{y}_{k+1}^*(x_{k+1},\lambda_{k+1}),\lambda_{k+1})-L_{k}(x_{k+1},\tilde{y}_k^*(x_{k+1},\lambda_{k+1}),\lambda_{k+1}))\nonumber\\
		&+\frac{\rho_{k+1}-\rho_k}{2}\|y_{k+1}\|^2\nonumber\\
		\le&2(L_{k+1}(x_{k+1},\tilde{y}_{k+1}^*(x_{k+1},\lambda_{k+1}),\lambda_{k+1})-L_{k}(x_{k+1},\tilde{y}_{k+1}^*(x_{k+1},\lambda_{k+1}),\lambda_{k+1}))\nonumber\\
		&+\frac{\rho_{k+1}-\rho_k}{2}\|y_{k+1}\|^2\nonumber\\
		=&(\rho_k-\rho_{k+1})\|\tilde{y}_{k+1}^*(x_{k+1},\lambda_{k+1})\|^2+\frac{\rho_{k+1}-\rho_k}{2}\|y_{k+1}\|^2\nonumber\\
		\le&(\rho_k-\rho_{k+1})\sigma_y^2,\label{sc:lem1:3}
	\end{align}
	where the last inequality holds since $\{\rho_k\}$ is a nonnegative monotonically decreasing sequence. The proof is completed by adding \eqref{sc:lem1:2} and \eqref{sc:lem1:3}.
\end{proof}

Similar to the proof of Theorem \ref{thm1}, we then obtain the following theorem which provides a bound on $T(\varepsilon)$, where $T(\varepsilon):=\min\{k \mid \|\nabla G^{\alpha_k,\beta,\gamma_k}(x_k,y_k,\lambda_k)\|\leq \varepsilon \}$ and $\varepsilon>0$ is a given target accuracy.

\begin{thm}\label{sc:thm1}
	Suppose that Assumptions \ref{fea}, \ref{ass:Lip} and \ref{muk} hold. Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:1}. Set  $\alpha_k=\frac{L^3}{(L+\beta)^2}+\frac{L\tau(L+\beta)^4(2\beta+\rho_k)^2}{\beta^4\rho_k^2}
	+\frac{\tau L^2}{\rho_k}+\frac{3L}{2}$, $\frac{1}{\gamma_k}=\frac{[2\|B\|^2+L^2(\tau-1)](L+\beta)^4(2\beta+\rho_k)^2}{L\beta^4\rho_k^2}+L+\frac{L^2\tau}{\rho_k}$ with $\rho_k=\frac{2(L+\beta)}{k^{1/4}}$, and $\beta>\frac{5L}{2}$, $\forall k\geq 1$. Then for any given $\varepsilon>0$,
	$$T( \varepsilon)\le \max\left\{\frac{4\tilde{d}_3^2\tilde{d}_4^2L^2(\tau-1)^2[2(L+\beta)^3(L+2\beta)^2+L\beta^4]^2}{\beta^8(L+\beta)^2\varepsilon^4},\frac{256(L+\beta)^4\sigma_y^4}{\varepsilon^4}\right\},$$
	where $\tilde{d}_1=\frac{8\tau^2}{(\tau-1)^2} + \frac{\frac{8L^6\beta^4}{(L+\beta)^4}+12L^2\beta^4+3\|A\|^2\beta^4}{L^2(L+\beta)^4(\tau-1)^2}+\frac{2\tau^2L^4\beta^4}{L^2(L+\beta)^6(\tau-1)^2}$, $\tilde{d}_2=\frac{9[2\|B\|^2+L^2(\tau-1)]^2}{L^2(\tau-1)^4} + \frac{9L^2\beta^4((L+\beta)^2+\tau^2L^2)}{L^2(L+\beta)^6(\tau-1)^2}$, $\tilde{d}_4=\max\left\{\frac{(\beta^2+2L^{2}+3\|B\|^2)\rho_1}{(\beta-\frac{5L}{2})L^2(\tau-1)}, \tilde{d}_1, \tilde{d}_2\right\}$ and $\tilde{d}_3=M_{1}(x_{1},y_{1},\lambda_1)-\underline{M}+\rho_1\sigma_y^2$ with $\underline{M}:=\min\limits_{\lambda\in\Lambda}\min\limits_{x\in\mathcal{X}}\min\limits_{y\in\mathcal{Y}}M_k(x,y,\lambda)$ and $\tau>1$.
	Moreover, for any  $i\in\mathcal{K}$, when $k\ge \tilde{T}(\varepsilon)$, we have
	$$\max\{0,[Ax_{k}+By_{k}-c]_i\}\leq \varepsilon.$$
\end{thm}

\begin{proof}
	Firstly, we denote
	\begin{equation*}
		\nabla \bar{G}^{\alpha_k,\beta,\gamma_k}_k\left( x_k,y_k,\lambda_k \right) =\left( \begin{array}{c}
			\alpha_k\left( x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\alpha_k}\left( x_k-\frac{1}{\alpha_k}\nabla _xL\left( x_k,y_k,\lambda_k \right) \right) \right)\\
			\beta\left( y_k-\operatorname{Prox}_{g,\mathcal{Y}}^{\beta}\left( y_k+ \frac{1}{\beta} \nabla _yL_k\left( x_k,y_k,\lambda_k\right) \right) \right)\\
			\frac{1}{\gamma_k}\left( \lambda_k-\mathcal{P}_{\Lambda}\left(\lambda_k-\gamma_k\nabla_{\lambda}L(x_k,y_k,\lambda_k)\right)\right)
		\end{array} \right).
	\end{equation*}
	It then can be easily checked that
	\begin{equation}
		\|\nabla G^{\alpha_k,\beta,\gamma_k}( x_{k},y_{k},\lambda_{k}) \|\le\|\nabla \bar{G}^{\alpha_k,\beta,\gamma_k}_k\left( x_{k},y_{k},\lambda_{k} \right) \|+\rho_{k}\|y_{k}\|.\label{sc:thm1:2}
	\end{equation}
	Next, we give the upper bound of $\|\nabla \bar{G}^{\alpha_k,\beta,\gamma_k}_k\left( x_k,y_k,\lambda_k \right)\|$. Similar to the proof of Lemma \ref{lem4}, by replacing $\alpha$ with $\alpha_k$, $\gamma$ with $\gamma_k$, respectively, we have
	\begin{align}
		&\|\nabla  \bar{G}^{\alpha_k,\beta,\gamma_k}_k( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& (\beta^2+2L^{2}+3\|B\|^2)\|y_{k+1}-y_k\|^2+(2\alpha_k^2+3\|A\|^2)\|x_{k+1}-x_k\|^2\nonumber\\
		&+\frac{3}{\gamma_k^2}\|\lambda_{k+1}-\lambda_k\|^2.\label{sc:thm1:3}
	\end{align}
	Let $\vartheta_k=\frac{L(L+\beta)^2\eta_k^2(\tau-1)}{\beta^2}
	+\frac{L^2(\tau-1)}{\rho_k}$ with $\tau>1$. It can be easily checked that $\alpha_k-\frac{L^3}{(L+\beta)^2}-\frac{L(L+\beta)^2\eta_k^2}{\beta^2}
	-\frac{L^2}{\rho_k}-\frac{3L}{2}=\vartheta_k$ and $\frac{1}{\gamma_k}-\frac{2\|B\|^2(L+\beta)^2\eta_k^2}{L\beta^2}-L-\frac{L^2}{\rho_k}=\vartheta_k$ by the settings of $\alpha_k$ and $\gamma_k$. In view of Lemma \ref{sc:lem1}, then we immediately obtian
	\begin{align}
		&\vartheta_k\|x_{k+1}-x_{k}\|^2+\vartheta_k\|\lambda_{k+1}-\lambda_{k}\|^2+\left(\beta-\frac{5L}{2}\right)\| y_{k+1}-y_{k} \|^2\nonumber\\
		\le&M_{k}(x_{k},y_{k},\lambda_k)-M_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+(\rho_k-\rho_{k+1})\sigma_y^2.\label{sc:thm1:4}
	\end{align}
	It follows from the definition of $\tilde{d}_1$ that $\forall k\ge 1$,
	\begin{align*}
		&\frac{2\alpha_k^2+3\|A\|^{2}}{\vartheta _k^2} \nonumber\\
		=&  \frac{2\left(\frac{L^3}{(L+\beta)^2}+\frac{L\tau(L+\beta)^2\eta_k^2}{\beta^2}
			+\frac{\tau L^2}{\rho_k}+\frac{3L}{2}\right)^2+3\|A\|^{2}}{\left(\frac{L(L+\beta)^2\eta_k^2(\tau-1)}{\beta^2}
			+\frac{L^2(\tau-1)}{\rho_k}\right)^2}\nonumber\\
		\leq& \frac{\frac{8L^6}{(L+\beta)^4}+\frac{8L^2(L+\beta)^4\eta_k^4\tau^2}{\beta^4}+\frac{8\tau^2L^4}{\rho_k^2}+12L^2+3\|A\|^2}{\frac{L^2(L+\beta)^4\eta_k^4(\tau-1)^2}{\beta^4}}\nonumber\\
		=& \frac{8\tau^2}{(\tau-1)^2} + \frac{\frac{8L^6\beta^4}{(L+\beta)^4}+12L^2\beta^4+3\|A\|^2\beta^4}{L^2(L+\beta)^4\eta_k^4(\tau-1)^2}+\frac{8\tau^2L^4\beta^4}{L^2(L+\beta)^4\eta_k^4\rho_k^2(\tau-1)^2}\le\tilde{d}_1,
	\end{align*}
	where the last inequality holds since $\eta_k>\frac{2(L+\beta)}{\rho_k}=k^{1/4}\ge1$. It also follows from the definition of $\tilde{d}_2$ that $\forall k\ge 1$, we have $\frac{3}{\gamma_k^2}\le\tilde{d}_2\vartheta_k$. Then \eqref{sc:thm1:3} can be rewritten as
	\begin{align}
		&\|\nabla  \bar{G}^{\alpha_k,\beta,\gamma_k}_k( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& (\beta^2+2L^{2}+3\|B\|^2)\|y_{k+1}-y_k\|^2+\tilde{d}_1\vartheta_k^2\|x_{k+1}-x_k\|^2\nonumber\\
		&+\tilde{d}_2\vartheta_k^2\|\lambda_{k+1}-\lambda_k\|^2.\label{sc:thm1:5}
	\end{align}
	Setting $d_k^{(2)}=\frac{1}{\max\{\frac{\beta^2+2L^{2}+3\|B\|^2}{\beta-\frac{5L}{2}}, \max\{\tilde{d}_1, \tilde{d}_2\}\vartheta_k\}}$, then multiplying $d_k^{(2)}$ on the both sides of \eqref{sc:thm1:5} and combining \eqref{sc:thm1:4}, we then conclude that
	\begin{align}
		&d_k^{(2)}\|\nabla  \bar{G}^{\alpha_k,\beta,\gamma_k}_k( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& M_{k}(x_{k},y_{k},\lambda_k)-M_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+(\rho_k-\rho_{k+1})\sigma_y^2.\label{sc:thm1:6}
	\end{align}
	Denoting $\tilde{T}_1(\varepsilon)=\min\{k \mid \| \nabla \bar{G}^{\alpha_k,\beta,\gamma_k}_k(x_k,y_{k},\lambda_k) \| \leq \frac{\varepsilon}{2}, k\geq 1\}$. By summing both sides of \eqref{sc:thm1:6} from $k=1$ to $\tilde{T}_1(\varepsilon)$, we obtain
	\begin{align}
		&\sum_{k=1}^{\tilde{T}_1(\varepsilon)}d_k^{(2)}\|\nabla  \bar{G}^{\alpha_k,\beta,\gamma_k}_k( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& M_{1}(x_{1},y_{1},\lambda_1)-M_{\tilde{T}_1(\varepsilon)+1}(x_{\tilde{T}_1(\varepsilon)+1},y_{\tilde{T}_1(\varepsilon)+1},\lambda_{\tilde{T}_1(\varepsilon)+1})+\rho_1\sigma_y^2.\label{sc:thm1:7}
	\end{align}
	Next, we prove $\underline{M}$ is a finite value. By the definition of $M_k(x,y,\lambda)$ in Lemma \ref{sc:lem1} and  the definition of $\Psi_k(x,\lambda)$, we have
	\begin{align}
		&M_k(x,y,\lambda)+\max_{y\in \mathcal{Y}}\frac{\rho_k}{2}\|y\|^2\nonumber\\
		=&2\Psi_k(x,\lambda)-L_k(x,y,\lambda)+h(x)+g(y)+\max_{y\in \mathcal{Y}}\frac{\rho_k}{2}\|y\|^2\nonumber\\
		\ge&\max_{y\in \mathcal{Y}}L_k(x,y,\lambda)+\max_{y\in \mathcal{Y}}\frac{\rho_k}{2}\|y\|^2+h(x)+g(y)\nonumber\\
		\ge&\max_{y\in \mathcal{Y}}L(x,y,\lambda)+h(x)+g(y),\label{sc:thm1:8}
	\end{align}
	where the last inequality is by the fact that $\max_y f_1(y)+\max_y f_2(y)\ge\max_y\{f_1(y)+f_2(y)\}$. Simlilar to the proof of Theorem \ref{thm1}, we conclude $\min\limits_{\lambda\in\Lambda}\min\limits_{x\in\mathcal{X}}\min\limits_{y\in\mathcal{Y}}M_k(x,y,\lambda)>-\infty$.  We then conclude from \eqref{sc:thm1:7} that
	\begin{align}
		\sum_{k=1}^{\tilde{T}_1(\varepsilon)}d_k^{(2)}\|\nabla  \bar{G}^{\alpha_k,\beta,\gamma_k}_k( x_k,y_{k},\lambda_k)\|^2
		\le M_{1}(x_{1},y_{1},\lambda_1)-\underline{M}+\rho_1\sigma_y^2=\tilde{d}_3.\label{sc:thm1:9}
	\end{align}
	Note that $\vartheta_k\ge\frac{L^2(\tau-1)}{\rho_1}$, then we have $\tilde{d}_4\ge\max\left\{\frac{\beta^2+2L^{2}+3\|B\|^2}{(\beta-\frac{5L}{2})\vartheta_k}, \max\{\tilde{d}_1, \tilde{d}_2\}\right\}$ by the definition of $\tilde{d}_4$ which implies that $d_k^{(2)}\ge\frac{1}{\tilde{d}_4\vartheta_k}$. By multiplying $\tilde{d}_4$ on the both sides of \eqref{sc:thm1:9}, we have
	\begin{align}
		\frac{\varepsilon^2}{4}\le\frac{\tilde{d}_3\tilde{d}_4}{\sum_{k=1}^{\tilde{T}_1(\varepsilon)}\frac{1}{\vartheta_k}}.\label{sc:thm1:10}
	\end{align}
	Note that $\rho_k=\frac{2(L+\beta)}{k^{1/4}}\le2(L+\beta)$, and thus by the definition of $\eta_k$, we have $\eta_k\le\frac{2(L+2\beta)(L+\beta)}{\rho_k\beta}$. Then we obtain $\sum_{k=1}^{\tilde{T}_1(\varepsilon)}\frac{1}{\vartheta_k}\ge\sum_{k=1}^{\tilde{T}_1(\varepsilon)}\frac{2\beta^4(L+\beta)k^{-1/2}}{L(\tau-1)[2(L+\beta)^3(L+2\beta)^2+L\beta^4]}$. Using the fact that $\sum_{k=1}^{\tilde{T}_1( \varepsilon)}1/k^{1/2}\ge\tilde{T}_1( \varepsilon)^{1/2}$, we conclude that
	\begin{align}
		\tilde{T}_1( \varepsilon)\le \left(\frac{2\tilde{d}_3\tilde{d}_4L(\tau-1)[2(L+\beta)^3(L+2\beta)^2+L\beta^4]}{\beta^4(L+\beta)\varepsilon^2}\right)^{2}.
	\end{align}
	On the other hand, if $k\ge\frac{256(L+\beta)^4\sigma_y^4}{\varepsilon^4}$, then $\rho_k\le\frac{\varepsilon}{2\sigma_y}$. This inequality together with the definition of $\sigma_y$ then imply that $\rho_k\|y_k\|\le\frac{\varepsilon}{2}$. Therefore, there exists a
	\begin{align*}
		T( \varepsilon)\le \max\left\{\frac{4\tilde{d}_3^2\tilde{d}_4^2L^2(\tau-1)^2[2(L+\beta)^3(L+2\beta)^2+L\beta^4]^2}{\beta^8(L+\beta)^2\varepsilon^4},\frac{256(L+\beta)^4\sigma_y^4}{\varepsilon^4}\right\}
	\end{align*}
	such that $\|\nabla G^{\alpha_k,\beta,\gamma_k}( x_{k},y_{k},\lambda_{k}) \|\le\|\nabla \bar{G}^{\alpha_k,\beta,\gamma_k}_k\left( x_{k},y_{k},\lambda_{k} \right) \|+\rho_{k}\|y_{k}\|\le\varepsilon$. By Lemma \ref{lem2.1}, we also can show the constraint violation is small at $(x_k,y_k,\lambda_k)$, that is for any $i\in\mathcal{K}$, if $k\ge \tilde{T}( \varepsilon)$, $\max\{0,[Ax_{k}+By_{k}-c]_i\}\leq \varepsilon$. The proof is then completed.
\end{proof}

\section{Nonconvex-Linear Minimax Problem with Coupled Linear Constraints}
In this section, we consider the problem \eqref{problem:1} with $g(y)=0$ and  $f(x,y)$ is a linear function with respect to $y$, i.e.,
\begin{equation}\label{problem:NC-L}
	\min_{x\in\mathcal{X}}\max\limits_{\substack{ y\in\mathcal{Y}\\Ax+By\unlhd c}}\{f(x,y)+h(x)\}.\tag{NC-L}
\end{equation}
Note that under the nonconvex-linear setting, the strong duality of problem \eqref{problem:NC-L} with respect to $y$ holds by Theorem \ref{dual} and Theorem \ref{thm2.2}.  Similar to that in Section \ref{sec2}, by using the Lagrangian function of problem \eqref{problem:NC-L}, we obtain the dual problem of \eqref{problem:NC-L}, i.e.,
\begin{align}
	\min_{\lambda\in\Lambda} \min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\left\{L(x,y,\lambda)+h(x)\right\}\tag{NC-LD},\label{3:dual}
\end{align}
where $L(x,y,\lambda)=f(x,y)-\lambda^\top(Ax+By-c)$.
We then propose another primal dual proximal gradient algorithm (PDPG-L) for solving problem \eqref{3:dual}.
At each iteration of the proposed algorithm, the inner maximization problem for $y$'s update is to solve a regularized version of $L(x,y,\lambda)$ plus $h(x)$. More detailedly, at the $k$th iteration, $y_k$ is updated by the following formula that
\begin{align}
	y_{k+1}={\arg\max}_{y\in \mathcal{Y}}L(x_k,y,\lambda_k)-\frac{q_k}{2}\|y\|^2-\frac{p_k}{2}\|y-y_k\|^2,\label{y-update-NCL}
\end{align}
where $q_k>0$ and $p_k\geq 0$ are regularization parameters which will be defined later.
Denote
\begin{align}
	\bar{L}_k(x,y,\lambda)=L(x,y,\lambda)-\frac{q_k}{2}\|y\|^2-\frac{p_k}{2}\|y-y_k\|^2.
\end{align}
Note that, \eqref{y-update-NCL} can be efficiently solved since that $\bar{L}_k(x,y,\lambda)$ is a strongly concave quadratic function with respect to $y$ when $f(x,y)$ is linear with respect to $y$. Similar to that in Algorithm \ref{alg:1}, a proximal gradient step and a projected gradient step is used to update $x$ and $\lambda$, respectively. The only difference is that Algorithm \ref{alg:2} updates $x$ and $\lambda$ simultaneously. The proposed PDPG-L algorithm is formally stated in Algorithm \ref{alg:2}.
\begin{algorithm}[t]
	\caption{(PDPG-L)}
	\label{alg:2}
	\begin{algorithmic}
		\STATE{\textbf{Step 1}:Input $x_1,y_1,\lambda_1,q_1,p_1,\bar{\alpha}_1,\bar{\gamma}_1$; Set $k=1$.}

		\STATE{\textbf{Step 2}:Perform the following update for $y_k$:
			\qquad \begin{equation}\label{2:update-y}
				y_{k+1}={\arg\max}_{y\in \mathcal{Y}}L(x_k,y,\lambda_k)-\frac{q_k}{2}\|y\|^2-\frac{p_k}{2}\|y-y_k\|^2.
		\end{equation}}
		\STATE{\textbf{Step 3}:Perform the following update for $x_k$ and $\lambda_k$:
			\qquad	\begin{align}
				x_{k+1}&=\operatorname{Prox}_{h,\mathcal{X}}^{\bar{\alpha}_k} \left( x_k - \frac{1}{\bar{\alpha}_k}  \nabla _xL\left( x_{k},y_{k+1},\lambda_k \right) \right). \label{2:update-x}\\
				\lambda_{k+1}&=\mathcal{P}_{\Lambda}(\lambda_k+\bar{\gamma}_k(Ax_{k}+By_{k+1}-c)).\label{2:update-lambda}
		\end{align}}
		\STATE{\textbf{Step 4}:If some stationary condition is satisfied, stop; otherwise, set $k=k+1, $ go to Step 2.}

	\end{algorithmic}
\end{algorithm}

Before we analyze the iteration complexity of Algorithm \ref{alg:2} for solving \eqref{problem:NC-L},
we first prove that $\bar{L}_k(x,y,\lambda)$ is a smooth function in the following lemma.
\begin{lem}\label{Lk-lip}
	Suppose that Assumption \ref{ass:Lip} holds. Let $L_B=L+\|B\|$, $L_A=L+\|A\|$, then for any given $x, x_1, x_2\in \mathcal{X}$, $y, y_1, y_2\in \mathcal{Y}$, and $\lambda, \lambda_1, \lambda_2\in \Lambda$, we have
	\begin{align*}
		\|\nabla_y\bar{L}_k(x_1,y,\lambda_1)-\nabla _y\bar{L}_k(x_{2},y, \lambda_{2})\|
		\le&L_B\|(x_2;\lambda_{2})-(x_1;\lambda_{1})\|,\\
		\|\nabla_{x,\lambda}\bar{L}_k(x_1,y,\lambda_1)-\nabla _{x,\lambda}\bar{L}_k(x_{2},y, \lambda_{2})\|
		\le&L_A\|(x_2;\lambda_{2})-(x_1;\lambda_{1})\|,\\
		\|\nabla_{x,\lambda}\bar{L}_k(x,y_1,\lambda)-\nabla _{x,\lambda}\bar{L}_k(x,y_2, \lambda)\|\le&L_B\|y_1-y_2\|.
	\end{align*}
Also, if we replace $\bar{L}_k(x,y,\lambda)$ with $L(x,y,\lambda)$, the above three results hold.
\end{lem}

\begin{proof}
	By the definition of $\bar{L}_k(x,y,\lambda)$ and $L(x,y,\lambda)$, we have
	\begin{align*}
		&\|\nabla_y\bar{L}_k(x_1,y,\lambda_1)-\nabla _y\bar{L}_k(x_{2},y, \lambda_{2})\|=\|\nabla_yL(x_1,y,\lambda_1)-\nabla _yL(x_{2},y, \lambda_{2})\|\nonumber\\

		=&\|\nabla_yf(x_1,y)-\nabla _yf(x_{2},y)-B^\top(\lambda_1-\lambda_{2})\|
		\le L_B\|(x_2;\lambda_{2})-(x_1;\lambda_{1})\|,
	\end{align*}
where the last inequality is due to Assumption \ref{ass:Lip}. Similarly,  by the definition of $\bar{L}_k(x,y,\lambda)$ and $L(x,y,\lambda)$ and Assumption \ref{ass:Lip}, we get
	\begin{align*}
	&\|\nabla_{x,\lambda}\bar{L}_k(x_1,y,\lambda_1)-\nabla _{x,\lambda}\bar{L}_k(x_{2},y, \lambda_{2})\|=\|\nabla_{x,\lambda}L(x_1,y,\lambda_1)-\nabla _{x,\lambda}L(x_{2},y, \lambda_{2})\|\nonumber\\
	=&\left\|\begin{array}{c}\nabla_xf(x_1,y)-\nabla _xf(x_{2},y)-A^\top(\lambda_1-\lambda_{2})\\
		-A(x_1-x_{2})
		\end{array}\right\|
	\le L_A\|(x_2;\lambda_{2})-(x_1;\lambda_{1})\|,
\end{align*}
and
	\begin{align*}
	&\|\nabla_{x,\lambda}\bar{L}_k(x,y_1,\lambda)-\nabla _{x,\lambda}\bar{L}_k(x,y_2, \lambda)\|=\|\nabla_{x,\lambda}L(x,y_1,\lambda)-\nabla _{x,\lambda}L(x,y_2, \lambda)\|\nonumber\\
	=&\left\|\begin{array}{c}\nabla_xf(x,y_1)-\nabla _xf(x,y_2)\\
		-B(y_1-y_{2})
	\end{array}\right\|	\le L_B\|y_1-y_2\|,
\end{align*}
which completes the proof.
\end{proof}
We then denote
\begin{align}
	\Phi_k(x,\lambda)&=\max_{y\in\mathcal{Y}}\bar{L}_k(x,y,\lambda),\label{add:3.1}\\
	y_k^*(x,\lambda)&=\arg\max_{y\in\mathcal{Y}}\bar{L}_k(x,y,\lambda).\label{add:3.2}
\end{align}
By strong concavity of $\bar{L}_k(x,y,\lambda)$ with respect to $y$ and Lemma B.2 in \cite{Lin2020},  for any given $x$ and $\lambda$, we have
\begin{align}
	\nabla_x\Phi_k(x,\lambda)&=\nabla_x \bar{L}_k(x, y_k^*(x,\lambda),\lambda),\label{gradx:nl}\\
	\nabla_\lambda\Phi_k(x,\lambda)&=\nabla_\lambda \bar{L}_k(x, y_k^*(x,\lambda),\lambda)\label{gradla:nl}.
\end{align}
Similar to the proof of Lemma 24 in \cite{Nouiehed}, we prove that $\Phi_k(x,\lambda)$ is a smooth function in the following lemma for the sake of completeness.

\begin{lem}\label{4:lem1}
	Suppose that Assumption \ref{ass:Lip} holds, then $\Phi_k(x,\lambda)$ is $(L_A+\frac{L_B^2}{q_k+p_k})$-smooth with respect to $(x; \lambda)$.
\end{lem}

\begin{proof}
		By the definition of $ \Phi_k(x,\lambda)$, \eqref{gradx:nl}, \eqref{gradla:nl} and the Cauhy-Schwarz inequality, we get
	\begin{align}
		&\|\nabla_{x,\lambda} \Phi_k(x_{k+1},\lambda_{k+1})-\nabla_{x,\lambda} \Phi_k(x_{k},\lambda_{k})\|\nonumber\\
		=&\|\nabla_{x,\lambda} \bar{L}_k(x_{k+1},y^*_k(x_{k+1},\lambda_{k+1}),\lambda_{k+1})-\nabla_{x,\lambda} \bar{L}_k(x_{k},y^*_k(x_{k},\lambda_{k}),\lambda_{k})\|\nonumber\\
		\le&\|\nabla_{x,\lambda} \bar{L}_k(x_{k+1},y^*_k(x_{k+1},\lambda_{k+1}),\lambda_{k+1})-\nabla_{x,\lambda} \bar{L}_k(x_{k+1},y^*_k(x_{k},\lambda_{k}),\lambda_{k+1})\|\nonumber\\
		&+\|\nabla_{x,\lambda} \bar{L}_k(x_{k+1},y^*_k(x_{k},\lambda_{k}),\lambda_{k+1})-\nabla_{x,\lambda} \bar{L}_k(x_{k},y^*_k(x_{k},\lambda_{k}),\lambda_{k})\|\nonumber\\
		\le&L_B\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|+L_A\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|,\label{4:lem1:10}
	\end{align}
	where the last inequality is by Lemma \ref{Lk-lip}. Next, we give the upper bound of the first term in the right hand of \eqref{4:lem1:10}.
Note that $\bar{L}_k(x_k,y,\lambda_k)$ is $(q_k+p_k)$-strongly concave with respect to $y$, which implies that
	\begin{align}
		&\bar{L}_k(x_k,y^*_k(x_{k+1},\lambda_{k+1}),\lambda_k)-\bar{L}_k(x_k,y^*_k(x_{k},\lambda_{k}),\lambda_k)\nonumber\\
		\le&\langle \nabla_y\bar{L}_k(x_k,y^*_k(x_{k},\lambda_{k}),\lambda_k),y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \rangle\nonumber\\
		&-\frac{q_k+p_k}{2}\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|^2,\label{4:lem1:2}
	\end{align}
	and
	\begin{align}
		&\bar{L}_k(x_k,y^*_k(x_{k},\lambda_{k}),\lambda_k)-\bar{L}_k(x_k,y^*_k(x_{k+1},\lambda_{k+1}),\lambda_k)\nonumber\\
		\le&\langle \nabla_y\bar{L}_k(x_k,y^*_k(x_{k+1},\lambda_{k+1}),\lambda_k),y^*_k(x_{k},\lambda_{k})-y^*_k(x_{k+1},\lambda_{k+1}) \rangle\nonumber\\
		&-\frac{q_k+p_k}{2}\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|^2.\label{4:lem1:3}
	\end{align}
	By the definition of $y^*_k(x_{k},\lambda_{k})$ in \eqref{add:3.2}, we have that $\forall y\in \mathcal{Y}$ and $\forall k\geq 1$,
	\begin{equation}
		\langle \nabla _y\bar{L}_k(x_{k},y^*_k(x_{k},\lambda_{k}),\lambda_k),y-y^*_k(x_{k},\lambda_{k}) \rangle \le 0.\label{4:lem1:4}
	\end{equation}
	By choosing $y=y^*_k(x_{k+1},\lambda_{k+1})$ in \eqref{4:lem1:4}, we have
	\begin{equation}
		\langle \nabla _y\bar{L}_k(x_{k},y^*_k(x_{k},\lambda_{k}),\lambda_k),y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \rangle \le 0.\label{4:lem1:5}
	\end{equation}
	Adding \eqref{4:lem1:2} and \eqref{4:lem1:3}, and combining \eqref{4:lem1:5}, we obtain
	\begin{align}
		&(q_k+p_k)\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|^2\nonumber\\
		\le&\langle \nabla_y\bar{L}_k(x_k,y^*_k(x_{k+1},\lambda_{k+1}),\lambda_k),y^*_k(x_{k},\lambda_{k})-y^*_k(x_{k+1},\lambda_{k+1}) \rangle.\label{4:lem1:6}
	\end{align}
	On the other hand, the definiton of $y^*_k(x_{k+1},\lambda_{k+1})$ in \eqref{add:3.2} implies that $\forall y\in \mathcal{Y}$ and $\forall k\geq 1$,
	\begin{equation}
		\langle \nabla _y\bar{L}_k(x_{k+1},y^*_k(x_{k+1},\lambda_{k+1}),\lambda_{k+1}),y-y^*_k(x_{k+1},\lambda_{k+1}) \rangle \le 0.\label{4:lem1:7}
	\end{equation}
	By choosing $y=y^*_k(x_{k},\lambda_{k})$ in \eqref{4:lem1:7}, we have
	\begin{equation}
		\langle \nabla _y\bar{L}_k(x_{k+1},y^*_k(x_{k+1},\lambda_{k+1}),\lambda_{k+1}),y^*_k(x_{k},\lambda_{k})-y^*_k(x_{k+1},\lambda_{k+1}) \rangle \le 0.\label{4:lem1:8}
	\end{equation}
	Adding \eqref{4:lem1:6} and \eqref{4:lem1:8} and by Lemma \ref{Lk-lip},  we obtain
	\begin{align*}
		&(q_k+p_k)\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|^2\nonumber\\
		\le&\langle \nabla_y\bar{L}_k(x_k,y^*_k(x_{k+1},\lambda_{k+1}),\lambda_k)-\nabla _y\bar{L}_k(x_{k+1},y^*_k(x_{k+1},\lambda_{k+1}), \lambda_{k+1}),\nonumber\\
		&\quad y^*_k(x_{k},\lambda_{k})-y^*_k(x_{k+1},\lambda_{k+1}) \rangle\nonumber\\
		\le&L_B\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|\cdot \|y^*_k(x_{k},\lambda_{k})-y^*_k(x_{k+1},\lambda_{k+1})\|,
	\end{align*}
	which implies that
	\begin{align}
		\|y^*_k(x_{k+1},\lambda_{k+1})-y^*_k(x_{k},\lambda_{k}) \|
		\le\frac{L_B}{q_k+p_k}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|.\label{4:lem1:9}
	\end{align}
The proof is then completed by combining \eqref{4:lem1:10} and \eqref{4:lem1:9}.
\end{proof}

Next, we provide an upper bound of  $\Phi_{k+1}(x_{k+1},\lambda_{k+1})-\Phi_k(x_k,\lambda_k)$.

\begin{lem}\label{4:lem2}
	Suppose that Assumption \ref{ass:Lip} holds. Let $\{\left(x_k,y_k\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:2},
	then $\forall k \ge 1$,
	\begin{align}
		& \Phi_{k+1}(x_{k+1},\lambda_{k+1})-\Phi_k(x_{k},\lambda_{k})\nonumber\\
		\le&\langle \nabla_x \bar{L}_k(x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle+\langle \nabla_\lambda \bar{L}_k(x_k,y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_k\rangle\nonumber\\
		&+\frac{1}{2}\left(L_A+\frac{L_B^2}{q_k+p_k}+\frac{2L_B^2}{q_{k}}\right)\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2\nonumber\\
		&+p_k\|y_{k+1}-y_k\|^2+\frac{p_k-p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2+\frac{q_k-q_{k+1}}{2}\|y_{k+2}\|^2.\label{4:lem2:1}
	\end{align}
\end{lem}

\begin{proof}
	Since that $\Phi_k(x,\lambda)$ is $\left(L_A+\frac{L_B^2}{q_k+p_k}\right)$-smooth with respect to $(x;\lambda)$ by Lemma \ref{4:lem1}, and by \eqref{gradx:nl}, \eqref{gradla:nl} and $y_{k+1}=y^*_k(x_{k},\lambda_{k})$, we obtain that
	\begin{align}
		&\Phi_k(x_{k+1},\lambda_{k+1})-\Phi_k(x_{k},\lambda_{k})\nonumber\\
		\le&\left[\begin{array}{c}
			\nabla_x\Phi_k(x_{k},\lambda_{k})\\
			\nabla_\lambda\Phi_k(x_{k},\lambda_{k})
		\end{array} \right] ^\top\left[\begin{array}{c}
			x_{k+1}-x_k\\
			\lambda_{k+1}-\lambda_k
		\end{array} \right]\nonumber\\
		&+\frac{1}{2}\left(L_A+\frac{L_B^2}{q_k+p_k}\right)\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2\nonumber\\
		=&\langle \nabla_x \bar{L}_k(x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle+\langle \nabla_\lambda \bar{L}_k(x_k,y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_k\rangle\nonumber\\
		&+\frac{1}{2}\left(L_A+\frac{L_B^2}{q_k+p_k}\right)\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2.\label{4:lem2:2}
	\end{align}
 On the other hand, by \eqref{add:3.1}, \eqref{add:3.2} and \eqref{2:update-y},  we have
	\begin{align}
		&\Phi_{k+1}(x_{k+1},\lambda_{k+1})-\Phi_k(x_{k+1},\lambda_{k+1})\nonumber\\
		=&\bar{L}_{k+1}\left(x_{k+1},y^*_{k+1}(x_{k+1},\lambda_{k+1}),\lambda_{k+1}\right)-\bar{L}_{k}\left(x_{k+1},y^*_{k}(x_{k+1},\lambda_{k+1}),\lambda_{k+1}\right)\nonumber\\
		\le&\bar{L}_{k+1}(x_{k+1},y_{k+2},\lambda_{k+1})-\bar{L}_k(x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		=&\bar{L}_{k+1}(x_{k+1},y_{k+2},\lambda_{k+1})-\bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+\frac{q_k-q_{k+1}}{2}\|y_{k+1}\|^2\nonumber\\
		&+\frac{p_k}{2}\|y_{k+1}-y_k\|^2.\label{4:lem2:3}
	\end{align}
Next, we estimate the upper bound of the right hand side of \eqref{4:lem2:3}. By $(q_{k+1}+p_{k+1})$-strong concavity of $\bar{L}_{k+1}(x,y,\lambda)$ with respect to $y$, we have
	\begin{align}
		&\bar{L}_{k+1}(x_{k+1},y_{k+2},\lambda_{k+1})-\bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		\le&\langle\nabla_y \bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1}),y_{k+2}-y_{k+1}\rangle-\frac{q_{k+1}+p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2.\label{4:lem2:4}
	\end{align}
	The optimality condition for $y_{k+1}$ in \eqref{2:update-y} implies that $\forall y\in \mathcal{Y}$ and $\forall k\geq 1$, we have
	\begin{align}
		\langle\nabla_y \bar{L}_{k}(x_{k},y_{k+1},\lambda_{k}),y-y_{k+1}\rangle\le 0.\label{4:lem2:5}
	\end{align}
	Setting $y=y_{k+2}$ in \eqref{4:lem2:5} and plugging it into \eqref{4:lem2:4}, and by the defintion of $\bar{L}_{k+1}(x,y,\lambda)$ and $\bar{L}_{k}(x,y,\lambda)$, we then obtain
	\begin{align}
		&\bar{L}_{k+1}(x_{k+1},y_{k+2},\lambda_{k+1})-\bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		\le&\langle\nabla_y \bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})-\nabla_y \bar{L}_{k}(x_{k},y_{k+1},\lambda_{k}),y_{k+2}-y_{k+1}\rangle\nonumber\\
		&-\frac{q_{k+1}+p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2\nonumber\\
		=&\langle\nabla_y L(x_{k+1},y_{k+1},\lambda_{k+1})-\nabla_y L((x_{k},y_{k+1},\lambda_{k}),y_{k+2}-y_{k+1}\rangle\nonumber\\
		&+p_k\langle y_{k+1}-y_k,y_{k+2}-y_{k+1}\rangle+(q_k-q_{k+1})\langle y_{k+1},y_{k+2}-y_{k+1}\rangle\nonumber\\
		&-\frac{q_{k+1}+p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2.\label{4:lem2:6}
	\end{align}
By the Cauchy-Schwarz inequality and Lemma \ref{Lk-lip}, we get
	\begin{align}
		&\langle\nabla_y L(x_{k+1},y_{k+1},\lambda_{k+1})-\nabla_y L((x_{k},y_{k+1},\lambda_{k}),y_{k+2}-y_{k+1}\rangle\nonumber\\
		\le&\frac{L_B^2}{q_{k}}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2+\frac{q_{k}}{2}\|y_{k+2}-y_{k+1}\|^2,\label{4:lem2:7}
	\end{align}
	and
	\begin{align}
		\langle y_{k+1}-y_k,y_{k+2}-y_{k+1}\rangle\le\frac{1}{2}\left[\|y_{k+1}-y_k\|^2+\|y_{k+2}-y_{k+1}\|^2\right].\label{4:lem2:8}
	\end{align}
Note that
	\begin{align}
		&\langle y_{k+1},y_{k+2}-y_{k+1}\rangle=\frac{1}{2}\left[\|y_{k+2}\|^2-\|y_{k+1}\|^2-\|y_{k+2}-y_{k+1}\|^2\right].\label{4:lem2:9}
	\end{align}
	Plugging \eqref{4:lem2:7}-\eqref{4:lem2:9} into \eqref{4:lem2:6} and rearranging the terms, we have
	\begin{align}
		&\bar{L}_{k+1}(x_{k+1},y_{k+2},\lambda_{k+1})-\bar{L}_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		\le&\frac{L_B^2}{q_{k}}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2+\frac{q_k-q_{k+1}}{2}\left[\|y_{k+2}\|^2-\|y_{k+1}\|^2\right]\nonumber\\
		&+\frac{p_k-p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2+\frac{p_k}{2}\|y_{k+1}-y_k\|^2.\label{4:lem2:10}
	\end{align}
	Plugging \eqref{4:lem2:10} into \eqref{4:lem2:3} and rearranging the terms, we get
	\begin{align}
		&\Phi_{k+1}(x_{k+1},\lambda_{k+1})-\Phi_k(x_{k+1},\lambda_{k+1})\nonumber\\
		\le&\frac{L_B^2}{q_{k}}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2+p_k\|y_{k+1}-y_k\|^2+\frac{p_k-p_{k+1}}{2}\|y_{k+2}-y_{k+1}\|^2\nonumber\\
		&+\frac{q_k-q_{k+1}}{2}\|y_{k+2}\|^2.\label{4:lem2:11}
	\end{align}
	The proof is completed by adding \eqref{4:lem2:2} and \eqref{4:lem2:11}.
\end{proof}

We now establish an important recursion for Algorithm \ref{alg:2}.
\begin{lem}\label{4:lem3}
	Suppose that Assumption \ref{ass:Lip} holds. Denote
	\begin{align*}
		V_k(x,y,\lambda)=2\Phi_k(x,\lambda)-L(x,y,\lambda)+h(x),\ \forall k \ge 1.
	\end{align*}
	Let $\{\left(x_k,y_k\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:2}, then
	\begin{align}
		&V_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})-V_k(x_{k},y_{k},\lambda_k)\nonumber\\
		\le&-\frac{q_k-2p_k}{2}\| y_{k+1}-y_{k} \|^2+\frac{q_k}{2}\left(\|y_k\|^2-\|y_{k+1}\|^2\right)+(p_k-p_{k+1})\|y_{k+2}-y_{k+1}\|^2\nonumber\\
		&-\left(\bar{\alpha}_k-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}\right)\|x_{k+1}-x_{k}\|^2+(q_k-q_{k+1})\|y_{k+2}\|^2\nonumber\\
		&-\left(\frac{1}{\bar{\gamma}_k}-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}\right)\|\lambda_{k+1}-\lambda_{k}\|^2.\label{4:lem3:1}
	\end{align}
\end{lem}

\begin{proof}
	By choosing $y=y_k$ in  \eqref{4:lem2:5}, we have
	\begin{equation}
		\langle \nabla _y\bar{L}_k(x_{k},y_{k+1},\lambda_k),y_k-y_{k+1} \rangle \le 0.\label{4:lem3:3}
	\end{equation}
	Note that $\bar{L}_k(x,y,\lambda)$ is $(q_k+p_k)$-strongly concave with respect to $y$, by \eqref{4:lem3:3}, we have  that
	\begin{align}
		&\bar{L}_k(x_{k},y_{k},\lambda_k)-\bar{L}_k( x_{k},y_{k+1},\lambda_k)\nonumber\\
		\le& \langle \nabla _{y}\bar{L}_k(x_{k},y_{k+1},\lambda_k),y_{k}-y_{k+1} \rangle -\frac{q_k+p_k}{2}\| y_{k+1}-y_{k} \|^2\nonumber\\
		\le&-\frac{q_k+p_k}{2}\| y_{k+1}-y_{k} \|^2.\label{4:lem3:4}
	\end{align}
By the definition of $\bar{L}_k(x,y,\lambda)$ and \eqref{4:lem3:4}, we get
	\begin{align}
		&L(x_{k},y_{k},\lambda_k)-L( x_{k},y_{k+1},\lambda_k)\nonumber\\
		\le&-\frac{q_k+2p_k}{2}\| y_{k+1}-y_{k} \|^2+\frac{q_k}{2}\left[\|y_k\|^2-\|y_{k+1}\|^2\right].\label{4:lem3:5}
	\end{align}
	By Lemma \ref{Lk-lip}, we obtain that
	\begin{align}
		&L(x_{k+1},y_{k+1},\lambda_{k+1})-L( x_{k},y_{k+1},\lambda_k)\nonumber\\
		\ge&\left[\begin{array}{c}
			\nabla_x L(x_{k},y_{k+1},\lambda_{k})\\
			\nabla_\lambda L(x_{k},y_{k+1},\lambda_{k})
		\end{array} \right] ^\top\left[\begin{array}{c}
			x_{k+1}-x_k\\
			\lambda_{k+1}-\lambda_k
		\end{array} \right]-\frac{L_A}{2}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2.\label{4:lem3:6}
	\end{align}
	By adding \eqref{4:lem3:5}  and \eqref{4:lem3:6}, we have
	\begin{align}
		&L(x_{k},y_{k},\lambda_k)-L( x_{k+1},y_{k+1},\lambda_{k+1})\nonumber\\
		\le&-\frac{q_k+2p_k}{2}\| y_{k+1}-y_{k} \|^2+\frac{q_k}{2}\left[\|y_k\|^2-\|y_{k+1}\|^2\right]\nonumber\\
		&-\langle \nabla_x \bar{L}_k(x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle-\langle \nabla_\lambda \bar{L}_k(x_k,y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_k\rangle\nonumber\\
		&+\frac{L_A}{2}\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2.\label{4:lem3:7}
	\end{align}
	Combining \eqref{4:lem3:7} and \eqref{4:lem2:1}, we obtain
	\begin{align}
		&(2\Phi_{k+1}(x_{k+1},\lambda_{k+1})-L( x_{k+1},y_{k+1},\lambda_{k+1}))-\left(2\Phi_k(x_{k},\lambda_{k})-L(x_{k},y_{k},\lambda_k)\right)\nonumber\\
		\le&-\frac{q_k-2p_k}{2}\| y_{k+1}-y_{k} \|^2+\frac{q_k}{2}\left(\|y_k\|^2-\|y_{k+1}\|^2\right)+(p_k-p_{k+1})\|y_{k+2}-y_{k+1}\|^2\nonumber\\
		&+\langle \nabla_x \bar{L}_k(x_k,y_{k+1},\lambda_k),x_{k+1}-x_k \rangle+\langle \nabla_\lambda \bar{L}_k(x_k,y_{k+1},\lambda_k),\lambda_{k+1}-\lambda_k\rangle\nonumber\\
		&+\left(\frac{3L_A}{2}+\frac{L_B^2}{q_k+p_k}+\frac{2L_B^2}{q_{k}}\right)\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2+(q_k-q_{k+1})\|y_{k+2}\|^2.\label{4:lem3:8}
	\end{align}
	Similar to the proof of \eqref{lem3:iq3}, \eqref{lem3:iq4},\eqref{lem3:3} and \eqref{lem3:4} in Lemma \ref{lem3}, by replacing $\alpha$ with $\bar{\alpha}_k$, $\gamma$ with $\bar{\gamma}_k$, respectively, we obtain
	\begin{equation}
		\langle \nabla _\lambda L(x_{k+1},y_{k+1},\lambda_k)+\frac{1}{\bar{\gamma}_k}(\lambda_{k+1}-\lambda_{k}),\lambda_k-\lambda_{k+1} \rangle \ge 0,\label{4:lem3:9}
	\end{equation}
	and
	\begin{equation}
		\langle \nabla _xL(x_{k},y_{k+1},\lambda_k),x_{k+1}-x_k \rangle \le -\bar{\alpha}_k\|x_{k+1}-x_k\|^2-\langle\zeta_{k+1},x_{k+1}-x_k \rangle,\label{4:lem3:10}
	\end{equation}
	where $\zeta_{k+1}\in\partial h(x_{k+1})$. Utilizing the convexity of $h(x)$ and by the definition of subgradient, we have $h(x_{k})-h( x_{k+1})\ge\langle\zeta_{k+1},x_{k}-x_{k+1} \rangle$.
	By plugging this inequality, \eqref{4:lem3:9} and \eqref{4:lem3:10} into \eqref{4:lem3:8}, and using the definiton of $V_k(x,y,\lambda)$ and the fact that $\|(x_{k+1};\lambda_{k+1})-(x_{k};\lambda_{k})\|^2=\|x_{k+1}-x_{k}\|^2+\|\lambda_{k+1}-\lambda_{k}\|^2$, we obtain
	\begin{align*}
		&V_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})-V_k(x_{k},y_{k},\lambda_k)\\
		\le&-\frac{q_k-2p_k}{2}\| y_{k+1}-y_{k} \|^2+\frac{q_k}{2}\left(\|y_k\|^2-\|y_{k+1}\|^2\right)+(p_k-p_{k+1})\|y_{k+2}-y_{k+1}\|^2\nonumber\\
		&-\left(\bar{\alpha}_k-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}\right)\|x_{k+1}-x_{k}\|^2+(q_k-q_{k+1})\|y_{k+2}\|^2\\
		&-\left(\frac{1}{\bar{\gamma}_k}-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}\right)\|\lambda_{k+1}-\lambda_{k}\|^2,
	\end{align*}
	which completes the proof.
\end{proof}

Similar to the proof of Theorem \ref{thm1}, then we obtain the following Theorem that provide a bound on $\hat{T}(\varepsilon)$, where $\hat{T}(\varepsilon):=\min\{k \mid \|\nabla \mathcal{G}^{\bar{\alpha}_k,L,\bar{\gamma}_k}(x_k,y_k,\lambda_k)\|\leq \varepsilon \}$ and $\varepsilon>0$ is a given target accuracy,
$$\nabla \mathcal{G}^{\bar{\alpha}_k,L,\bar{\gamma}_k}\left( x_k,y_k,\lambda_k \right) =\left( \begin{array}{c}
	\bar{\alpha}_k\left( x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\bar{\alpha}_k}\left( x_k-\frac{1}{\bar{\alpha}_k}\nabla _xL\left( x_k,y_k,\lambda_k \right) \right) \right)\\
	L\left( y_k-\mathcal{P}_{\mathcal{Y}}\left( y_k+ \frac{1}{L} \nabla _yL\left( x_k,y_k,\lambda_k\right) \right) \right)\\
	\frac{1}{\bar{\gamma}_k}\left( \lambda_k-\mathcal{P}_{\Lambda}\left(\lambda_k-\bar{\gamma}_k\nabla_{\lambda}L(x_k,y_k,\lambda_k)\right)\right)
\end{array} \right) .$$
We also need to make the following assumption on the parameters $q_k$ and $p_k$.
\begin{ass}\label{qk}
	$\{q_k\}$ and $\{p_k\}$ are nonnegative monotonically decreasing sequences.
\end{ass}

\begin{thm}\label{4:thm1}
	Suppose that Assumptions \ref{fea}, \ref{ass:Lip} and \ref{qk} hold. Let $\{\left(x_k,y_k,\lambda_k\right)\}$ be a sequence generated by Algorithm \ref{alg:2}. Set  $\bar{\alpha}_k=\frac{3L_A}{2}+\frac{14\tau L_B^2}{5q_k}$, $\bar{\gamma}_k=\frac{1}{\bar{\alpha}_k}$ with $q_k=\frac{L}{2k^{1/3}}$,  $p_k=\frac{q_k}{4}$, $\forall k\geq 1$. Then for any given $\varepsilon>0$,
	$$ \hat{T}( \varepsilon)\le \max\left\{\frac{(112\bar{d}_2\bar{d}_3(\tau-1)L_B^2)^{3/2}}{5\sqrt{5}L^{3/2} \varepsilon^3},\frac{L^3\delta_y^3}{\varepsilon^3}\right\},$$
	where $\delta_y=\max\{\|y\| \mid y\in\mathcal{Y}\}$, $\bar{d}_2=\max\{\bar{d}_1,\frac{20(9L^2+\|B\|^2)}{7(\tau-1)L_B^2}\}$ with $\bar{d}_1=\frac{4\tau^2}{(\tau-1)^2}+\frac{225L^2L_A^2}{392(\tau-1)^2L_B^4 }$,  $\bar{d}_3=V_1(x_{1},y_{1},\lambda_{1})-\underbar{V}+L\delta_y^2$, $\underbar{V}:=\min_{\lambda\in\Lambda}\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}V_k(x,y,\lambda)$, and $\tau>1$.
	Moreover, for any  $i\in\mathcal{K}$, when $k\ge \hat{T}(\varepsilon)$,
	$$\max\{0,[Ax_{k}+By_{k}-c]_i\}\leq \varepsilon.$$
\end{thm}

\begin{proof}
	Firstly, we denote
	\begin{equation*}
		\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k\left( x_k,y_k,\lambda_k \right) =\left( \begin{array}{c}
			\bar{\alpha}_k\left( x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\bar{\alpha}_k}\left( x_k-\frac{1}{\bar{\alpha}_k}\nabla _xL\left( x_k,y_k,\lambda_k \right) \right) \right)\\
			L\left( y_k-\mathcal{P}_{\mathcal{Y}}\left( y_k+ \frac{1}{L} \nabla _y\bar{L}_k\left( x_k,y_k,\lambda_k\right) \right) \right)\\
			\frac{1}{\bar{\gamma}_k}\left( \lambda_k-\mathcal{P}_{\Lambda}\left(\lambda_k-\bar{\gamma}_k\nabla_{\lambda}L(x_k,y_k,\lambda_k)\right)\right)\\
		\end{array} \right).
	\end{equation*}
	It then can be easily checked that
	\begin{equation}
		\|\nabla \mathcal{G}^{\bar{\alpha}_k,L,\bar{\gamma}_k}( x_{k},y_{k},\lambda_{k}) \|\le\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k\left( x_{k},y_{k},\lambda_{k} \right) \|+q_{k}\|y_{k}\|.\label{4:thm1:2}
	\end{equation}
	Next, we give the upper bound of $\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k\left( x_k,y_k,\lambda_k \right)\|$. By \eqref{2:update-y}, the nonexpansiveness of the projection operator and the triangle inequality, we immediately obtain
	\begin{align}
		&\|L( y_k-\mathcal{P}_{\mathcal{Y}}( y_k+ \frac{1}{L} \nabla _y\bar{L}_k\left( x_k,y_k,\lambda_k\right) )) \|\nonumber\\
		\le&L\|\mathcal{P}_{\mathcal{Y}}( y_{k+1}+ \frac{1}{L} \nabla _y\bar{L}_k\left( x_k,y_{k+1},\lambda_k\right) )-\mathcal{P}_{\mathcal{Y}}( y_{k}+ \frac{1}{L} \nabla _y\bar{L}_k\left( x_k,y_{k},\lambda_k\right))\|\nonumber\\
		&+L\|y_{k+1}-y_k\|\nonumber\\
		\le&(3L+q_k+p_k)\|y_{k+1}-y_k\|
		\le4L\|y_{k+1}-y_k\|,\label{4:thm1:3}
	\end{align}
	where the last inequality is due to that $q_k\le L/2$ and $p_k\le L/2$. On the other hand, similar to the proof of \eqref{lem4:3} and \eqref{lem4:4} in Lemma \ref{lem4}, we obtain
	\begin{align}
		&\|\bar{\alpha}_k( x_k-\operatorname{Prox}_{h,\mathcal{X}}^{\bar{\alpha}_k}( x_k-\frac{1}{\bar{\alpha}_k}\nabla _xL\left( x_k,y_k,\lambda_k \right)))\|\nonumber\\
		\leq& \bar{\alpha}_k\|x_{k+1}-x_k\| +L\|y_{k+1}-y_k\|,\label{4:thm1:4}
	\end{align}
	and
	\begin{align}
		\|\frac{1}{\bar{\gamma}_k}( \lambda_k-\mathcal{P}_{\Lambda}(\lambda_k-\bar{\gamma}_k\nabla_{\lambda}L(x_k,y_k,\lambda_k)))\|
		\leq  \frac{1}{\bar{\gamma}_k}\|\lambda_{k+1}-\lambda_k\|+\|B\|\|y_{k+1}-y_k\|.\label{4:thm1:5}
	\end{align}
	By combining \eqref{4:thm1:3}, \eqref{4:thm1:4} and \eqref{4:thm1:5}, and the Cauchy-Schwarz inequality, we get
	\begin{align}
		&\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& (18L^{2}+2\|B\|^2)\|y_{k+1}-y_k\|^2+2\bar{\alpha}_k^2\|x_{k+1}-x_k\|^2+\frac{2}{\bar{\gamma}_k^2}\|\lambda_{k+1}-\lambda_k\|^2.\label{4:thm1:6}
	\end{align}
	Let $\theta_k=\frac{14(\tau-1)L_B^2}{5q_k}$ with $\tau>1$. It can be easily checked that $\bar{\alpha}_k-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}=\theta_k$ and $\frac{1}{\bar{\gamma}_k}-\frac{3L_A}{2}-\frac{L_B^2}{q_k+p_k}-\frac{2L_B^2}{q_{k}}=\theta_k$ by the settings of $\bar{\alpha}_k$ and $\bar{\gamma}_k$. In view of Lemma \ref{4:lem3}, then we immediately obtian
	\begin{align}
		&\theta_k\|x_{k+1}-x_{k}\|^2+\theta_k\|\lambda_{k+1}-\lambda_{k}\|^2+\frac{q_k}{4}\| y_{k+1}-y_{k} \|^2\nonumber\\
		\le&V_k(x_{k},y_{k},\lambda_k)-V_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+\frac{q_k}{2}\left[\|y_k\|^2-\|y_{k+1}\|^2\right]\nonumber\\
		&+\frac{1}{4}(q_k-q_{k+1})\|y_{k+2}-y_{k+1}\|^2+(q_k-q_{k+1})\|y_{k+2}\|^2\nonumber\\
		\le&V_k(x_{k},y_{k},\lambda_k)-V_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+\frac{q_k}{2}\|y_k\|^2-\frac{q_{k+1}}{2}\|y_{k+1}\|^2\nonumber\\
		&+\frac{1}{4}(q_k-q_{k+1})\|y_{k+2}-y_{k+1}\|^2+(q_k-q_{k+1})\|y_{k+2}\|^2,\label{4:thm1:8}
	\end{align}
	where the last inequality holds since $\{q_k\}$ is a nonnegative monotonically decreasing sequence. On the other hand, by the definition of $\bar{d}_1$, $\forall k\ge 1$, we have $\bar{d}_1\ge \frac{2\bar{\alpha}_k^2}{\theta_k^2}$, and then \eqref{4:thm1:6} can be rewritten as
	\begin{align}
		&\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_kv( x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le& (18L^{2}+2\|B\|^2)\|y_{k+1}-y_k\|^2+\bar{d}_1\theta_k^2\|x_{k+1}-x_k\|^2+\bar{d}_1\theta_k^2\|\lambda_{k+1}-\lambda_k\|^2.\label{4:thm1:9}
	\end{align}
 Multiplying $\frac{1}{\bar{d}_2\theta_k}$ on the both sides of \eqref{4:thm1:9} and combining \eqref{4:thm1:8}, using the definiton of $\delta_y$, we then conclude that
	\begin{align}
		&\frac{1}{\bar{d}_2\theta_k}\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k(x_k,y_{k},\lambda_k)\|^2\nonumber\\
		\le&V_k(x_{k},y_{k},\lambda_k)-V_{k+1}(x_{k+1},y_{k+1},\lambda_{k+1})+\frac{q_k}{2}\|y_k\|^2-\frac{q_{k+1}}{2}\|y_{k+1}\|^2\nonumber\\
		&+\frac{3}{2}(q_k-q_{k+1})\delta_y^2.\label{4:thm1:10}
	\end{align}
Denote $\bar{T}(\varepsilon)=\min\{k \mid \| \nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k(x_k,y_{k},\lambda_k) \| \leq \frac{\varepsilon}{2}, k\geq 1\}$. By summing both sides of \eqref{4:thm1:10} from $k=1$ to $\bar{T}(\varepsilon)$, we obtain
	\begin{align}
		&\sum_{k=1}^{\bar{T}\left( \varepsilon \right)}{\frac{1}{d_2\theta_k}\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k( x_k,y_{k},\lambda_k) \| ^2}\nonumber\\
		\le& V_1(x_{1},y_{1},\lambda_{1})-V_{\bar{T}(\varepsilon)+1}(x_{\bar{T}(\varepsilon)+1},y_{\bar{T}(\varepsilon)+1},\lambda_{\bar{T}(\varepsilon)+1})+\frac{q_1}{2}\|y_1\|^2+\frac{3q_1}{2}\delta_y^2.\label{4:thm1:11}

	\end{align}
	Next, we prove $\underline{V}$ is a finite value. By the definition of $V_k(x,y,\lambda)$ in Lemma \ref{4:lem3} and  the definition of $\Phi_k(x,\lambda)$, we have
	\begin{align}
		&V_k(x,y,\lambda)+2\max_{y\in \mathcal{Y}}\frac{q_k}{2}\|y\|^2+2\max_{y\in \mathcal{Y}}\frac{p_k}{2}\|y-y_k\|^2\nonumber\\
		=&2\Phi_k(x,\lambda)+2\max_{y\in \mathcal{Y}}\frac{q_k}{2}\|y\|^2+2\max_{y\in \mathcal{Y}}\frac{p_k}{2}\|y-y_k\|^2-L(x,y,\lambda)+h(x)\nonumber\\
		=&2\max_{y\in \mathcal{Y}}\bar{L}_k(x,y,\lambda)+2\max_{y\in \mathcal{Y}}\frac{q_k}{2}\|y\|^2+2\max_{y\in \mathcal{Y}}\frac{p_k}{2}\|y-y_k\|^2-L(x,y,\lambda)+h(x)\nonumber\\
		\ge&2\max_{y\in \mathcal{Y}}L(x,y,\lambda)-L(x,y,\lambda)+h(x),\label{4:thm1:12}
	\end{align}
	where the last inequality is by the fact that $\max_y f_1(y)+\max_y f_2(y)\ge\max_y\{f_1(y)+f_2(y)\}$. Simlilar to the proof of Theorem \ref{thm1}, we conclude $\min\limits_{\lambda\in\Lambda}\min\limits_{x\in\mathcal{X}}\min\limits_{y\in\mathcal{Y}}V_k(x,y,\lambda)>-\infty$. By the definiton of $q_k$ and $\delta_y$, we obtain
	\begin{align*}
		\sum_{k=1}^{\bar{T}\left( \varepsilon \right)}{\frac{1}{\bar{d}_2\theta_k}\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k( x_k,y_{k},\lambda_k) \| ^2}
		\le V_1(x_{1},y_{1},\lambda_{1})-\underbar{V}+L\delta_y^2=\bar{d}_3.
	\end{align*}
	In view of the definition of $\bar{T}\left( \varepsilon \right)$, we have
	\begin{align*}
		\frac{\varepsilon^2}{4}\le \frac{\bar{d}_3}{\sum_{k=1}^{\bar{T}\left( \varepsilon \right)}{\frac{1}{\bar{d}_2\theta_k}}}.
	\end{align*}
	Since that $q_k=\frac{L}{2k^{1/3}}$, then $\theta_k=\frac{28k^{1/3}(\tau-1)L_B^2}{5L}$. Using the fact that $\sum_{k=1}^{\bar{T}( \varepsilon)}1/k^{1/3}\ge \bar{T}( \varepsilon)^{2/3}$, we conclude that $\frac{\varepsilon^2}{4}\le \frac{28\bar{d}_2\bar{d}_3(\tau-1)L_B^2}{5L\bar{T}( \varepsilon)^{2/3}}$ or equivalently,
	\begin{align}\label{4:thm1:13}
		\bar{T}( \varepsilon)\le \left(\frac{112\bar{d}_2\bar{d}_3(\tau-1)L_B^2}{5L\varepsilon^2}\right)^{3/2}.
	\end{align}
	On the other hand, if $k\ge\frac{L^3\delta_y^3}{\varepsilon^3}$, then $q_k\le\frac{\varepsilon}{2\delta_y}$, this inequality together with the definition of $\delta_y$ then imply that $q_k\|y_k\|\le\frac{\varepsilon}{2}$. Therefore, there exists a
	\begin{align}\label{4:thm1:14}
		\hat{T}( \varepsilon)\le \max\left\{\frac{(112\bar{d}_2\bar{d}_3(\tau-1)L_B^2)^{3/2}}{5\sqrt{5}L^{3/2} \varepsilon^3},\frac{L^3\delta_y^3}{\varepsilon^3}\right\}
	\end{align}
	such that $\|\nabla \mathcal{G}^{\bar{\alpha}_k,L,\bar{\gamma}_k}( x_{k},y_{k},\lambda_{k}) \|\le\|\nabla \bar{\mathcal{G}}^{\bar{\alpha}_k,L,\bar{\gamma}_k}_k\left( x_{k},y_{k},\lambda_{k} \right) \|+q_{k}\|y_{k}\|\le\varepsilon$. By Lemma \ref{lem2.1}, we also can show the constraint violation is small at $(x_k,y_k,\lambda_k)$,that is for any $i\in\mathcal{K}$, if $k\ge 	\hat{T}( \varepsilon)$, $\max\{0,[Ax_{k}+By_{k}-c]_i\}\leq \varepsilon$. The proof is then completed.
\end{proof}

\begin{re}
	Theorem \ref{4:thm1} implies that the number of iterations for Algorithm \ref{alg:2} to obtain an $\varepsilon$-stationary point of problem \eqref{problem:NC-L} is bounded by $\mathcal{O}\left(\varepsilon ^{-3} \right)$. We mention that if we set $p_k=0$, Theorem \ref{4:thm1} also holds.
\end{re}

\section{Numerical Results}
In this section, we first consider a bilinear minimax problem with coupled linear constraints as follows.
\begin{align}
	\min _{x\in \mathcal{X}}  \max _{y\in \mathcal{Y}} & \quad xy\\\label{testpro2}
	\mbox { s.t. } & \quad Ax+By\leq c,\nonumber
\end{align}
where $\mathcal{X}=\{x \mid \|x\|\le2\}$, $\mathcal{Y}=\{y \mid \|y\|\le2\}$.
Note that $(0,0)$ is the unique stationary point. We set $q_k=\frac{1}{k^{1/3}}$, $p_k=0$, $1/\bar{\alpha}_k=\bar{\gamma}_k=\frac{1}{k^{1/3}}$ in PDPG-L. All the stepsizes for MGD and PGmsAD algorithms are set to be 0.3. The initial point of all algorithms is chosen as $(1,1)$, $A$ and $B$ are randomly generated in the interval $[0, 2]$, we set $c=2A+2B$. Figure \ref{Fig.linear} shows the sequences generated by three algorithms, we find that both MGD algorithm and PGmsAD algorithm fall into a limit cycle, whereas
PDPG-L approaches the unique stationary point.
\begin{figure}[H]
	\centering
	\subfigure{

		\includegraphics[width=0.5\textwidth]{images/figure1.png}}
	\caption{ Sequences generated by three algorithms}
	\label{Fig.linear}
\end{figure}
Secondly, we test the proposed PDAPG algorithm with MGD\cite{Tsaknakis} algorithm, PGmsAD\cite{Dai} algorithm for solving an adversarial attack in network flow problems~\cite{Tsaknakis}, formulated as the following minimax problem:
\begin{align}
	\max _{y\in \mathcal{Y}}  \min _{x\in \mathcal{X}} & \quad \sum_{(i, j) \in E} q_{i j}\left(x_{i j}+y_{i j}\right) x_{i j} -\frac{\eta}{2}\|y\|^2\\
	\mbox { s.t. } & \quad \mathbf{x}+\mathbf{y} \leq \mathbf{p}\label{testprob}
\end{align}
where $\mathcal{X}= \{x\mid 0 \leq \mathbf{x} \leq \mathbf{p}, \sum_{(i, t) \in E} x_{i t}=r_t, \sum_{(i, j) \in E} x_{i j}-\sum_{(j, k) \in E} x_{j k}=0, \forall j \in V \backslash\{s, t\}\}$, $\mathcal{Y}=\{y\mid 0 \leq \mathbf{y} \leq \mathbf{p}, \sum_{(i, j) \in E} y_{i j}=b\}$, $V$ and $E$ is the set of vertices and edges of a directed graph $G=(V, E)$, respectively, $s$ and $t$ denote the source and sink node respectively, and $r_t$ is the total flow to sink node $t$, $\mathbf{x}=\left\{x_e\right\}_{e \in E} \in \mathbb{R}^{|E|}$ and $\mathbf{p}=\left\{p_e\right\}_{e \in E} \in \mathbb{R}^{|E|}$ denote the vectors of flows and the capacities at edge $e$, respectively, and $\mathbf{y}=\left\{y_e\right\}_{e \in E}$  denote the set of flows controlled by the adversary, $\eta>0$, $q_{ij}>0$ is the unit cost at edge $(i,j)\in E$ and $b > 0$ is its total budget.

 We set $\eta=0.05$,  $1/\beta=0.8$, $1/\alpha=0.6$, $\gamma=0.5$ in PDAPG. All the stepsizes for MGD are set to be 0.5 which is same as that in \cite{Tsaknakis}. We set $\alpha_y=0.8$, $\alpha_x=0.6 $ for PGmsAD algorithm which is the same as that of PDAPG algorithm. Following the same setting with that in \cite{Tsaknakis}, the capacity $p_{ij}$ and the cost coefficients $q_{ij}$ of the edges are generated uniformly at random in the interval [1, 2],  and total flow $r_t$ is $d\%$ of the sum of capacities of the edges exiting the source with $d$ being a parameter to be chosen.

We define the following relative increase of the cost as performance measure, i.e.,
$$\rho=\frac{q_{att}-q_{cl}}{q_{cl}},$$
where $q_{cl}$ and $q_{att}$ denote the minimum cost before and after the attack, respectively. The higher the increase of the minimum cost the more successful the attack. We compare the relative total cost increase of the three tested algorithms for solving \eqref{testprob} with different $b$. For each given $b$, all the three algorithms are run for 15 times with randomly chosen $p_{ij}$ and $q_{ij}$ which means 15 graphs with different capacity and cost vectors.

Figure \ref{Fig.total cost} shows the average of the relative total cost increase of three tested algorithms over 15 independent runs. The shaded part around lines denotes the standard deviation over 15 independent runs.
We can find that the proposed PDAPG algorithm slightly outperforms the MGD algorithm, and is similar to that of the PGmsAD algorithm.

\begin{figure}[t]
	\centering
	\subfigure[n=15, p=0.75, d=10]{

		\includegraphics[width=0.45\textwidth]{images/f1.png}}
	\subfigure[n=15, p=1, d=10]{

		\includegraphics[width=0.45\textwidth]{images/f2.png}}
	\subfigure[n=15, p=0.75, d=20]{

		\includegraphics[width=0.45\textwidth]{images/f3.png}}
	\subfigure[n=15, p=1, d=20]{

		\includegraphics[width=0.45\textwidth]{images/f4.png}}
	\subfigure[n=20, p=0.75, d=30]{
		\includegraphics[width=0.45\textwidth]{images/f5.png}}
	\subfigure[n=20, p=1, d=30]{
		\includegraphics[width=0.45\textwidth]{images/f6.png}}
	\subfigure[n=20, p=0.75, d=40]{
		\includegraphics[width=0.45\textwidth]{images/f7.png}}
	\subfigure[n=20, p=1, d=40]{
		\includegraphics[width=0.45\textwidth]{images/f8.png}}
	\caption{Relative total cost increase of three algorithms}
	\label{Fig.total cost}
\end{figure}

\section{Conclusions}
 In this paper, we consider nonsmooth nonconvex-(strongly) concave and nonconvex-linear minimax problems with coupled linear constraints which are widely used in many fields such as machine learning, signal processing etc. For nonconvex-concave minimax problem \eqref{problem:1} with linear coupled equality or inequality constraints, we first prove the strong duality with respect to $y$ under some feasibility assumption, which is the first strong duality result with respect to $y$ for solving nonconvex minimax problems with coupled linear constraints. Based on the strong duality, we then propose a single looped primal dual alternating proximal gradient (PDAPG) algorithm and a single looped primal dual proximal gradient (PDPG-L) algorithm for solving problem \eqref{problem:1} under nonconvex-(strongly) concave and nonconvex-linear settings, respectively. We demonstrate the iteration complexity of the two algorithms are $\mathcal{O}\left( \varepsilon ^{-2} \right)$ (resp. $\mathcal{O}\left( \varepsilon ^{-4} \right)$) under nonconvex-strongly concave (resp. nonconvex-concave) setting and $\mathcal{O}\left( \varepsilon ^{-3} \right)$ under nonconvex-linear setting to obtain an $\varepsilon$-stationary point, respectively. To the best of our knowledge, they are the first two algorithms with iteration complexity guarantee for solving nonconvex minimax problems with coupled linear constraints. Moreover, the proposed PDAPG algorithm is optimal for solving nonconvex-strongly concave minimax problems with coupled linear constraints. Numerical experiments for adversarial attacks on network flow problems show the efficiency of the proposed algorithms.