Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling
Authors: Dmitry Kovalev
Alexander Gasnikov
Peter Richtárik
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
saddle-point problems
minimax optimization

Abstract: In this paper we study the convex-concave saddle-point problem $\min_x \max_y f(x) + y^\top\mathbf{A}x - g(y)$, where $f(x)$ and $g(y)$ are smooth and convex functions. We propose an Accelerated Primal-Dual Gradient Method (APDG) for solving this problem, achieving (i) an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound (Zhang et al., 2021), and (ii) an accelerated linear convergence rate in the case when only one of the functions $f(x)$ and $g(y)$ is strongly convex or even none of them are. Finally, we obtain a linearly convergent algorithm for the general smooth and convex-concave saddle point problem $\min_x \max_y F(x,y)$ without the requirement of strong convexity or strong concavity.

Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling
Dmitry Kovalev KAUST* Takovalev1@gmall com
Alexander Gasnikov MIPT ISP RAS, HSE gasnikov@yandex.rr
Peter Richtárik KAUST richtarik@gmail.com com
Abstract
In this paper study the convex-concave saddle-point problem min, max, f(x) y" Ax g(v), where f(x) and g(y) smooth and convex functions. We propose an Accelerated Primal-Dual Gradient Method (APDG) for solving this problem, achieving (i) an optimal linear convergence rate in the strongly- convex-strongly- concave regime, matching the lower complexity bound (Zhang et al., 2021), and (ii) accelerated linear convergence rate in the case when only of the functions (xx and ( strongly convex or even none of them are. Finally, we obtain a linearly convergent algorithm for the general smooth and convex-concave saddle point problem min, max, F(r, y) without the requirement of strong convexity or strong concavity.
Introduction
In this paper we revisit the well studied smooth convex-concave saddle point problem with a bilinear coupling function, which takes the form
min max F(x,y) = f(x) + T Ar -9()).
ZERds yERdy
where (x): Rd - IR and g(y): Rd + R are smooth and convex functions, and A RRd is coupling matrix.
Problem TT) has large number of application, some of which briefly introduce.
1.1 Empirical risk minimization
A classical application is the regularized empirical risk minimization (ERM) with linear predictors. which is a classical supervised learning problem. Given data matrix A [aI..... an Bxx where a, Rdd is the feature vector of the i-th data entry, goal is to find solution of
min fxx) ((Ar),
where f(z) : Rd + IR is convex regularizer, É(y) 1 + IR is a convex loss function, and x E Rd a linear predictor. Alterantively, one can solve the following equivalent saddle-point reformulation
"King Abdullah University of Science Technology, Thuwal, Saudi Arabia
MMoccow Institute of Physics and Technology. Dolgoprudny, Russia
l Institute System Programming RAS, Research Center Trusted Artificial Intelligence, Moscow, Russia National Research University Higher School of Economics, Moscow, Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of problem 2):
min max f(x)+ + y -
- (
(3)
The saddle-point reformulation is often preferable. For example, when such formulation admits finite sum structure (Zhang and Lin 2015 Wang and Xiao 2017). this may reduce the communication complexity in the distributed setting (Xiao et.l. 2019), and one may also better exploit the udnerlying sparsity structure (Lei et al. 2017).
1.2 Reinforcement learning
In reinforcement learning (RL) we are given sequence {(8,, de, Tt, 8t+1 1==1 generated by a policy t, where 8, the state at time step l, dt is the action taken time step / by policy and ry the reward after taking action (4 A key step in many RL algorithms is to estimate the value function of given policy π, which is defined as
(*(s)= =B
Σ r'
8,
where E (0. 1) is discount factor. A common approach to this problem is to use a linear approximation (s) 6(s) x, where (0()) is a feature vector of a state s. The model parameter x often estimated by minimizing the mean squared projected Bellman error
min Ar - b
(5)
where C- C-
"6 (s;) and A = C- (()))((()+))))) One can observe that it is hard to apply gradient-based methods to problem (5) because this would require one to compute inverse of the matrix C. In order to tackle this issue, one can solve an equivalent saddle-point reformulation proposed by Du et al. (2017) instead. This reformulation given by
min max 2y Arr llvlle 2b
and is an instance of problem matrix inversion.
Solving this reformulation with gradient methods does not require
1.3 Minimization under affine constraints
Next, consider the problem of convex minimization under affine constraints,
min f(x),
Ar=b
where & E rangeA. A. This problem covers a wide range of applications, including inverse problems in imaging (Chambolle and Pock 2016), sketched learning-type applications. (Keriven al. 2018).
network flow optimization (Zargham et al. 2013) and optimal transport (Peyré et al.
2019).
Another important application of problem is decentralized distributed optimization Kovalev et al.
2020 Scaman et al. [017]] Li et al., [2020] Nedic et al.] 2017] Arjevani et al. 2020 Ye ct al. 2020).
[2017]Arjevani
In this setting, the distributed minimization problem is often reformulated
min (
Inn)
Σ (1(s)) 1=1
(8)
where fxz) is a function stored locally by a computing node i E {1...., the Laplacian matrix of graph representing the communication network. The constraint enforces consensus among the nodes: T1
.n and W E Rx** is
Zn.
One can observe that problem is equivalent to the saddle-point formulation
min max f(x) + Az y b.
(9)
which is another instance of problem [ State-of-the-art methods often focus on this formulation
instead of directly solving (7). In particular, Salim et al. (202T) and Kovalev et al. (2020) obtained optimal algorithms for solving 7 and (8) using this saddle-point approach.

---

Table 1: Comparison of method (APGD, Algorithm with existing state-of-the-art algorithms for
solving problem ① in the different cases described in section
Strngg--oomwex-tttnnyyy-ooonee (section 5.1
Algorithm
max
Leu Villy
log 1
Lower bound
O maxx
Lx
Lxx
Ley Vialy
log :
Zhang et al. 2022b
Mo
Xie et al. 2021
DIPPA
max
Mi PSPy
Lon VPici
log 1
Proximal Best Response
mmax
Eu
Ley Pally
log
Wang and Li 2020
Aa
Affinely constrained minimization case (section 5.2
Algorithm
Liza
L.
log
Lower bound
Lon
log !
Salim et al. 2021
Mzy
ps
OPAPC
Les
log
Kovalev et al. 2020
Pxp
Strongly-comve--coment case (section 5.3
Algorithm
o max
Lu
Leex Hap
Lix
log
Pxy
May
Lower bound
N/A
Alt-GDA
O max
12 pa,
log
Zhang et al. 2021a
Bilinear case (section
5.4
Algorithm
o
12
log 1
Miv
Lower bound
Lea log )
Ibrahim et al. 2020
Azizian et al. 2020
Loun log 1
Miyu
Convex-concave case (section 5.5
L. Lr Lon Háv
12 Miu
Algorithm
max
log
Lower bound
N/A
1.4 Bilinear min-max problems
Unconstrained bilinear saddle-poin problems of the form
min max a. J y Ax - bTy
(10)
#gR4a yER"
are another special case of problem [ one where both fz) and g(y) are linear functions. While such problems do not usually play an important role in practice, they are often good testing ground for thcoretical purposes (Gidel et al. 2019 Azizian et al. 2020 Zhang et al. 2202a Mokhtari et al.
2020 Daskalakis al. 2018 Liang and Stokes 2019).
2 Literature Review and Contributions
In this work we are interested in algorithms able to solve problem 1 with a linear iteration complexity. That is, we are interested in methods that can provably find an e-accurate solution of problem (T) in number of iterations proportional to log (see Definitions and 3). This is typically achieved when

---

functions f(x) and ((x) are assumed to be strongly convex (see Definition the celebrated extragradient method of Korpelevicch (176)).
I An example of this is
Recent work has shown that linear iteration complexity can be achieved also in the less restrictive case when only of the functions f (ax and g(x) is strongly convex. This was first shown by Du and Hu (2019), and later improved on by Zhang et al. (202Ia).
However, and this the starting point of our research, the best of our knowledge, there are no algorithms with linear iteration complexity in the case when neither (()) nor g(x) is strongly convex.
2.1 Acceleration
Loosely speaking, we say that an algorithm is non-accelerated if its iteration complexity is propor- tional to at least the first power of the condition numbers associated with the problem, such as '=/p= and fw/My, where L and Ly stants (see Assumption and Assumption (2. In contrast, the iteration complexity of an accelerated algorithm is proportional to the square root of such condition numbers, e.g. VTT/pe= and v /Tu/pg
smoothness constants, and jır and My are strong convexity con-
There were several recent attempts design accelerated algorithms for solving problem ① (Xie iet al. 2021; Wang and Li, 2020 [Alkousa et al. (222)). These attempts rely on stacking multiple algorithms top of each other, and result in complicated methods. For example, [in et al. (2020) use a non-accelerated algorithm as a sub-routine for the inexact accelerated proximal-pone approach allows them to obtain accelerated algorithms for solving problem (I in a straightforward and tractable way. However, this approach has significant brawbacks: the algorithms obtained this way have (i) additional logarithmic factors in their iteration complexity, and (ii) complex nested structure with the requirement to manually set inner loop sizes, which is a byproduct of the design process based combining multiple algorithms. This drawback limits the performance of the resulting algorithms in theory, and requires additional fine tuning in practice.
method. This
A philosophically different approach to designing such algorithms-one that adopt in this work-is is to attempt to provide a direct acceleration of a suitable algorithm for solving problem I similarly to what Nesterov (1983) did for convex minimization problems. While this technically more demanding, algorithms obtained this way typically don't have the aforementioned drawbacks. Hence, we follow the latter approach in this work.
2.2 Main contributions
In this work we propose an Accelerated Primal-Dual Gradient Method (APDG; Algorithm 1 for solving problem ( and provide a theoretical analysis of its convergence properties (Theorem T In particular, we prove the following results.
(i) When both functions f(x and g(y) are strongly convex, Algorithm achieves the optimal linear convergence rate, matching the lower bound obtained by Zhang et al. (2021b). To the best of our knowledge, Algorithm| iis the first optimal algorithm in this regime.
(ii) We establish linear convergence of Algorithm T in the case when only one of the functions f (a)) g is strongly convex, and A a full row full column rank matrix, respectively. This improves upon the results provided by Du and Hu 2019); Zhang et al. (2021a).
(iii) We establish linear convergence of the Algorithm I in the case when neither of the functions I (x) nor π(y) is strongly convex, and the matrix A is square and full rank. To the best of our knowledge, Algorithm i the first algorithm achieving linear convergence in this setting.
Table I provides brief comparison of the complexity of Algorithm (Theorem 1 with the current state the art. Please refer to section for detailed discussion of this result and comparison with related work.

---

2.3 General min-max problem and additional contributions
In our work we also consider the saddle-poine problem
min max F(z, v), yER*
(11)
where F(x, y): Rd dR - IR is smooth function, which is convex in and concave in y. One can observe that the main problem ( is a special case of this more general problem (II).
As an additional contribution, we propose Gradient Descent-Ascent Method with Extrapolation (GDAE) for solving the general convex-concave saddle-point problem (11) and provide theoretical analysis of its convergence properties.
ii When the function Fxx, y) is strongly convex in a and strongly concave in GDAE achieves linear convergence rate, which recovers the convergence result of Cohen al. (2020).
(ii) Under certain assumptions the way the variables æ: and y are coupled by the function F(x, y), we establish linear convergence of GDAE in the case when the function F(I, y) is boongly-oonee--oncee
just convex-concave To the best of our knowledge, GDAE is the first algorithm achieving linear convergence under such assumptions.
sonve--strongly-connee
Please refer the Appendix for detailed description of these results and related work.
Basic Definitions and Assumptions
We start by formalizing the notions of smoothness and strong convexity of a function.
Definition 1. Function h(z): Fd + RR is L-smooth and u-strongly convex for L 2 2 0. for all 21, 22 E Rd the following inequality holds:
1 1 =212 < <D D2 22) - ブ || 22112
(12)
2
Above, D2(21, 22) h(21) - h(22) - (Vh(22) - -2) is the Bregman divergence associated with the function h(z).
We are now ready to state the main assumptions that we impose problem ①I. We start with Assumptions I and 2 that formalize the strong-convexity and smoothness properties of functions f(x)
and g(y).
Assumption 1. Function f (x) is L--shhoth and Pe-Strongly convex for L, pr 0. Assumption 2. Function g(y) is Ly-smooth and py--trongly convex for Ly 2 My 0.
Note, that μ4 and My are allowed to be zero. That is, both f(x) and g(y) are allowed to be non-strongly convex.
The following assumption formalizes the spectral properties of matrix A. Assumption 3. There exist constants Tory >> Pay: Hyy 2 O such that
min (AAT)
Vgly) range for all E TRd otherwise
2 Pay
Amin Amin(AA (AAT)
min (A ATAA A)
Vf(x) E raageAT for all x E Rdd otherwise
May
2
<
Amii A (ATA)
L2 ay
Amax (A TA)=
>maax (AAT).
where Amin (-), X xt matrix, respectively, and range denotes the range space of matrix.
(-) and Amax (-) denote the smallest, smallest positive and largest eigenvalue of
5

---

By S C IR x R we denote the solution set of problem (x ,y"" satisfies the first-order optimality conditions
Note that (x", E S if and only if
V=F(=",'" vz(==) A y 0, v,F(2".8") Vg(yy) ) Az O.
(13)
Our main goal is to propose an algorithm for finding a solution to problem T Numerical iterative algorithms typically find an approximate solution of given problem. We formalize this through the following definition.
Definition 2. Let the solution set S be nonempty. We call a pair of vectors (x,y) E Rd x TR
e-accurate solution of problem T for given accuracy > 0 if it satisfies
min max {1| x= 112 lly y v01 S. (2 (="))")ES
(14)
We also want to propose an efficient algorithm for solving problem (.) That is, we want to propose an algorithm with the the lowest possible iteration complexity, which we define next.
The iteration complexity of an algorithm for solving problem ① is the number of iterations the algorithm requires to find an e-accurate solution of this problem. At each iteration the algorithm is allowed perform O(1) computations of the gradients ff(x) and Vg(y) and matrix-vector multiplications with matrices A and A
Definition 3.
4 Accelerated Primal-Dual Gradient Method
Algorithm APDG: Accelerated Primal-Dual Gradient Method
1: Input: x E rangeA yd E rangeA, Tas Tyy Oka Orys Ar By >
0, Tay Typ Ow, By E (0, 1].
E (0,1)
2: 2 = =xx"
3: vj
=
4: for k 0. 1. 2, do
5:
n = 1
0ly / k-1)
6:
T
+ (1 T₂ )
7:
1 = T b + (1 w
8:
x² + nr (x
x²)
NEB.AT(AN (Ax* - -Vo(t))) The (Vf(zt) - v
9:
+1 1²th + a
y²
AAB VV+((()))) - (Vg())) Ar
10:
k+1 1tz + t (x x²
11: yf y + oy - )
12:
end for
In this section present the Accelerated Primal-Dual Gradient Method (APDG; Algorithml I for solving problem IT. First, we prove an outline of the key ideas used in the development of this algorithm.
4.1 Algorithm development strategy
First, we observe that problem equivalent to the problem of finding a zero of a sum of two monotone operators, G1, G2: R x Rd + Rd x BRd, defined as
G1 (z, v) (v) Vg(y)),
(15)
G2: (z, + (A y, Ar).
(16)
Indeed, Gi(z", (("""""))>>>>"""""")))"( + G2(2", (a"""""'"' v²) = is just another way to write the optimality conditions 13
The Forward Backward algorithm. A natural way to tackle this problem is via Forward Backward algorithm (Bauschke and Combettes)
201 Ib, the iterates which have the form
(a k+1 x
1 Jc. ((x" y²) GI v²))
(17)

---

where the operator JG, is the inverse of the operator I + G2, and I is the identity operator. Note that Jc, can be written as JG, (æ. v) + (art yy*), where (x+ .yt E Rd== x TR is a solution of the linear system
x A y y Ar
(18)
Linear extrapolation step. Next, notice that the computation of operator Jc, requires solving the linear system (T8). This is expensive and has be done each iteration of the Forward Backward algorithm. Let us instead consider the related problem
A Vm
(19)
y = y + Az
where ymm E R. is a newly introduced variable. It's easy observe that (19) equivalent to (18) when Vm. y² Next, notice that choosing Vm = y makes (19) easy to solve. However, it turns out that the convergence analysis of an algorithm with this approximation may challenging (Zhang
et al. 2021a), especially if we want to combine it with other techniques, such acceleration. Our key idea is to propose a better alternative: the linear extrapolation step
ym = y + O y/
(20)
where y E Rdy corresponds to obtained from the previous iteration of the Forward Backward algorithm, and (0. is an extrapolation parameter. The linear extrapolation step was introduced by Chambolle and Pock 2011 in the analysis of the Primal-Dus Hybrid Gradient algorithn
Nesterov acceleration. Next, we note that operator G1 is equal to the gradient of the (potential) function (I + f(z) + m(y) function. This function is smooth and convex due Assumptions ] and This allows us to incorporate the Nesterov acceleration mechanism in the Forward Backward algorithm. Nesterov acceleration known to be a powerful tool which allows improve convergence properties of gradient methods (Nesterov 1983 2003
4.2 Convergence of the algorithm
We are now ready study the convergence properties of Algorithm We are interested in the case when the following condition holds:
min (max (May Myz max {py, May }} > 0.
(21)
In this case one can show that the solution set S of problem holds in this case, as captured by the following lemma.
T is nonempty. Moreover, strong duality
Lemma Let Assumptions and 3 and condition primal problem
21 hold. Let p be the optimal value of the
min o
(22)
and let d be the optimal value of the dual problem
d = max yER
[D(y) - ( (-AAA)
(23)
Then p= d is finite and (x" vy) E S if and only if x² is a solution of the primal problem (2 and y" is solution of the dual problem 23
Under the aforementioned conditions, Algorithm Aagrithmmaachieees linear convergence. That is, the iteration complexity is proportional log 1
'The solution [8] can be written a closed form and requires to compute an inverse matrix (I+ A) (I + AA )-1 where I is the identity matrix of an appropriate size.
'However, the Primal- -ual Hybrid Gradient algorithm is not applicable in our case since it requires to compute the proximal operator of f(z) and g(y) at each iteration. Moreover, Chambolle and Pock (2011) established linear convergence of this algorithm in the coongly-convex-stroree concave setting only.
7

---

Theorem 1. Let Assumptions 2 and 3 and condition (21) hold. Then there exist parameters of Algorithm 7 such that iteration complexity for finding an e-accurate solution of problem
min (Ta. To, Te La} log )
(24)
where To, Thy To: Ta are defined
Lx
Ly
Lay Vuully S:
Ly
Lay
L
L ay
To = max
Тo = max
By
May
Pay
p
V Luaby
Lay
12 Ly
Laaky Lay
D 1
I Pary
To max
Ta max
Pyn
Myr
By
PxyHuy
and > 0 is some constant, Lus Pæs Lays Mys Layy Pays Hyz-
which does not depend on E, but possibly depends on
5 Discussion of Theorem
I and Related Work
In this section we comment on the iteration complexity result for Algorithm provided Theorem We consider important and illustrative special cases of this complexity result and draw connections with the existing results in the literature.
5.1 Strongly convex and strongly concave case
In this case Mas My > O. We can always assume May Myr = O in Assumption has iteration complexity given by
Then, Algorithm 1
Le
by
Luy Wirlly
max
log
(25)
Mx
My
This improves the current ttate-of-the-at results
L2 p My
L 13 Hall
Lay Vuntly
1 log
max
(26)
E
due to Xie et al. 20021) and
Tex
Try
Tozg To log
: c
δ max
(27)
Mafty
due to Wang and Li (2020), where Ö hides additional logarithmic factors, and L max ( Lex, Lyg Lay ). Moreover, our result (55 matches the lower complexity bound provided by Zhang et al. (2021b). Hence, Algorithm iis optimal this regime.
Apart from our work, algorithms that achieve optimal complexity 25 were developed in three independent works by [Thekumparampil et al. (2022); [Jin et al. (2022); Du al. (002)). However, to the best of our knowledge these works were published or appeared on arXiv in 2022, while our work appeared on arXiv in 2021. Hence, Algorithm i the first algorithm which achieves the lower complexity bound (25) for smooth and weweel-oooeeesstoogyycoooom concngy saddle- aoidee-point problems with bilinear coupling.
5.2 Altinely-constrainted minimization case
In this case μ4z > and = 0. Firstly, we consider the case when I., = 0, i.e., g(y) a linear function. Then, problem (1) is equivalent to the smooth and strongly-convex affinely-constrained minimization problem Algorithm enjoys the linear convergence rate
Lar
Lx
L2
max
log
(28)
May
22

---

where Pay
This result recovers the complexity of the APAPC algorithm (Kovalev et al. 2020). possible incorporate the Chebyshev acceleration
X (AA
0 due to Assumption
mechanism (Arioli and Scott 2014) into Algorithm for solving problem 7 to obtain the improved complexity
Lay Mzy
L log
(29)
Par
This matches the complexity of the OPAPC algorithm of Kovalev et al. (020); Salim et al. (202)
which was shown be optimal (Salim al. 2021
Scaman et al. (007)
5.3 Strongly convex and concave case
We also allow Ly > i.c. function gly) is a general, not necessarily linear, smooth and convex function. is is often possible that May > 0 due to Assumption for instance, when A is full row rank matrix. Then, Algorithm enjoys the following linear iteration complexity:
Lay
Lo
T aay
!
max
log
(30)
May
Mary
Px
This case was previously studied by Du and Hu 22119) Du et al. (2017) Zhang et al. 2021a Du
and Hu 2019) provided an analysis for an algorithm called LDAG and established its iteration complexity
L p
max
log
(31)
This result is substantially worse than our complexity (30 Subsequently, ZZhang al. (2021a) provided an improved analysis for the Sim-GDA algorithm, obtaining the complexity
possibly due to suboptimal analysis.
max
log
(32)
They also studied the Alt-GDA method, obtaining the complexity
L2
max
log
(33)
May
where L max Ly Lay). However, these results local, i.e., they valid only if the initial iterates of these algorithms are close enough to the solution of problem (I. Moreover, these results still worse than rate (30) because Sim-GDA and Alt-GDA do not utilize the Nesterov acceleration mechanism, while our Algorithm does.
5.4 Bilinear case
In this case frr By = T., by 0. That is, functions f(x) and g(v) are linear. Then,
problem ( turns into the bilinear min-max problem (10), and / = 1 A (A (ATA) A) > 0 due
Assumption 3 The iteration complexity Algorithm becomes
log
(34)
22
This recovers the results of Daskalakis al. (2018) Liang and Stokes (019): Gidel al. (2018 2019); Mishchenko et al. (2020): Mokhtari et al. (2020) for the bilinear min-max problem (10). However, this result is worse than the complexity lower bound
Luy log ! 1)
(35)
May
obtained the work of Ibrahim et al. 2200)), which was reached by Azizian al. (2020); Du et al. (2022
"ee provide these results for completeness. The result of Azizian et al. 2020) is better than our result 34
for Algorithm (eooith because they specifically focus on solving the bilinear min max problem (10). while Algorithm
aims solve the much more general convex-concave saddle-poin problem (I)

---

5.5 Convex-concave case
In this case My = μrr is often possible that Pay = Mau due Assumption for example, when A is square and full rank matrix. Then, the iteration complexity of Algorithm becomes
( max
Vee Laz
L
log
(36)
pizy
which is still linear. This complexity result generalizes the result (34) for bilinear min-max problems it allows for general, not necessarily linear, convex and smooth functions f(x) and g(z). To the best of our knowledge, Algorithm| is the first algorithm which can achieve linear convergence for smooth and non-strongly convex non-strongly concave min-max problems with bilinear coupling.
Acknowledgements
The work of Alexander Gasnikov supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000001733332P5500000 and the agreement with the Iyannikov Institute for System Programming of the Russian Academy of Sciences dated November 2, 2021 No. 70-2021-00142.
References
Alkousa, M., Gasnikov, A., Dvinskikh, D., Kovalev, D., and Stonyakin, F. (2020). Accelerated methods for saddle-point problem. Computational Mathematics and Mathematical Physics, 60(11):1777-189.
Arioli, M. and Scott, J. (2014). Chebyshev acceleration of iterative refinement. Numerical AlgoriicaAAgoorthhnnss, 66(3):591-608.
Arjevani, Y., Bruna. Can, B., Gürbüzbalaban. M., Jegelka, S., and Lin, (2020). Ideal: Inexact decentralized accelerated augmented lagrangian method. arXiv preprint arXiv:2006.06733.
Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. (2020). Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Inselligence and Statistics, pages 1705-1715. PMLR.
Bauschke, H. H. and Combettes, P. L. (2011). Convex Analysis and Monotone Operutor Theory in Hilbert Spaces. Springer.
Chambolle, A. and Pock, T. (2011). A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40( 100115120
Chambolle, A. and Pock, T. (2016). An introduction to continuous optimization for imaging. Acta Numerica, 25:161-319.
Cohen, M. B., Sidford, A., and Tian, K. (2020). Relative lipschitzness in extragradient methods and direct recipe for acceleration. arXiv preprint 1.055:2011.06572..
Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. (2018). Training gans with optimism. In International Conference Learning Representations (ICLR 2018).
Du, S. S., Chen, J., Li, L., Xiao, I.., and Zhou, D. (2017). Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049-1058. PMLR.
Du, S. S., Gidel, G., Jordan, M. I,, and Li, C. (2022). Optimal extragradient-basee based bilinearly-coupled saddle-point optimization. arXiv preprint arXiv:2006.08573.
Du, S. S. and Hu, W. (2019). Linear convergence of the primal-dual gradient method for convex- coneave saddle point problems without strong convexity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 196-205. PMLR.
10

---

Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. (2018)) A variational inequality perspective on generative adversarial networks, arXiv preprint
Gidel, G., Hemmat, R. A., Pezeshki, M., Le Priol, R., Huang, G., Lacoste-Julien, S., and Mitliagkas, I. (2019). Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR.
Ibrahim, A., Azizian, W., Gidel, G., and Mitliagkas. I. (2020). Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning, pages 4583-4593 PMLR.
Jin, Y., Sidford, A., and Tian, K. (2022). Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods. arXiv preprint arXiv:220.004640.
Keriven, N., Bourrier, A., Gribonval, R., and Pérez, P. (2018). Sketching for large-scale learning of mixture models. Information and Inference: A Journal of the IMA, 7(3):4775508
Korpelevich, G. M. (1976). The extragradient method for finding saddle points and other problems. Matecon, 12:747-756.
Kovalev, D., Salim, A., and Richtárik, P. (2020). Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33.
Lei, Q. Yen, E.H.,, Wu, C.-y.. Dhillon, I. S., and Ravikumar, P. (2017). Doubly greedy primal- coordinate descent for sparse empirical risk minimization. In International Conference on Machine Learning, pages 2034-2042. PMLR.
Li, H., Lin, Z., and Fang, Y. (2020). Optimal accelerated variance reduced extra and diging for strongly convex and smooth decentralized optimization. arXiv e-prints, pages arXiv-2009.
Liang, T. and Stokes, J. (2019). Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMLR.
Lin, T., Jin, C., and Jordan, M. I. (2020). Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738 2779. PMLR.
Mishchenko, K., Kovalev, D., Shulgin, E., Richtárik, P., and Malitsky, Y. (2020). Revisiting stochastic extragradient. In International Conference on Artificial Intelligence and Statistics, pages 4573- 4582. PMLR.
Mokhtari, A., Ozdaglar, A., and Pattathil, S. (2020). unified analysis extra- extra-gradient gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pages 1497-1507. PMLR.
Nedic, A., Olshevsky, A., and Shi, W. (2017). Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optinization, 27(4):297-2233.
Nesterov, Y. (2003). Introductory lectures on convex optimization: A basic course, volume 87. Springer Science Business Media.
Nesterov, Y. and Scrimali, L. (2006). Solving strongly monotone variational and quasi-variational inequalities.
Nesterov, Y. E. (1983). A method for solving the convex programming problem with convergence rate o (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pages 543-547.
Peyré, G., Cuturi, M., et al. (2019). Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 116--6)355-607.
Salim, A., Condat, I.., Kovalev, D., and Richtárik, (2021). An optimal algorithm for strongly convex minimization under affine constraints. arXiv preprint arXiv:2102.11079

---

Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization networks. international conference on machine learning, pages 3027-3036. PMLR.
Thekumparampil, K. K., He, N., and Oh, S. (2022). Lifted primal-dual method for bilinearly coupled smooth minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 1381-4308. PMLR.
Wang, J. and Xiao, L. (2017). Exploiting strong convexity from data with primal-dual first-order algorithms. In International Conference on Machine Learning, pages 3694-3702. PMLR.
Wang, Y. and Li, J. (2020). Improved algorithms for convex-concave minimax optimization. arXiv preprint ar arXiv:2006.0633 06359.
Xiao, I.,, Yu, A. W., Lin, Q., and Chen, W. (2019). Dscovr: Randomized primal-dual block coordinate algorithms for asynchronous distributed optimization. The Journal of Machine Learning Research, 20(1):1634-1611.
Xie, G., Han, Y., and Zhang, Z. (2021). Dippa: An improved method for bilinear saddle point problems. arXiv preprint arXiv:2103.082777
Ye, H., Luo, L., Zhou, Z.,, and Zhang. T. (2020). Multi-consensus decentralized accelerated gradient descent. arXiv preprint arXiv:2005.0079)
Zargham, M., Ribeiro, A., Ozdaglar, A., and Jadbabaie, A. (2013). Accelerated dual descent for network flow optimization. IEEE Transactions on Automatic Control, 59(4):905 -200.
Zhang, G., Wang, Y., Lessard, I.., and Grosse, R. (2021a). Don't fix what ain't broke: Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. arXiv preprint a1X1v:2102.09468
Zhang, J., Hong, M., and Zhang. S. (2021b). On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, pages 1-35.
Zhang, Y. and Lin, X. (2015). Stochastic primal-dual coordinate method for regularized empirical risk minimization. In International Conference on Machine Learning, pages 353-361. PMLR.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No]
(c) Did you discuss any potential negative societal impacts of your work? [No] This is theoretical work with no forseeable negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] Assumptions to
|
(b) Did you include complete proofs of all theoretical results? [Yes] see Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "kNWVp4VjeS", "reviewer": "Reviewer_uksx", "summary": "The paper proposes APDG, an accelerated algorithm in solving the smooth convex-concave saddle-point problem. The main contribution is to show linear convergence rate of APDG under various settings: strongly-convex-strongly-concave, strongly-convex-concave with full-column rank matrix A and convex-concave with full rank square matrix A.", "questions": "1.\tIs it possible to prove the optimality of APDG under strongly-convex-concave and convex-concave setting?\n2.\tThere is a gap between the rate of APDG and the lower bound under bilinear case. Is the rate of APDG tight or the gap is merely an artifact of the analysis techniques?\n3.\tCompare the rate of APDG with other methods under convex-concave setting.\n4.\tProvide numerical results to show the empirical performance of APDG.\n", "limitations": "NA.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: APDG combines two techniques, linear extrapolation and Nesterov’s acceleration to obtain linear rate for various saddle-point problems. The rate matches the lower bound under strongly-convex-strongly-concave setting and show improved rate on the setting of strongly-convex-concave with full column rank A. \n\nCons: The major contribution seems to be the strongly-convex-strongly-concave case, but the improvement is only a small difference of \\sqrt{L/L_{xy}} compared to Wang and Li (2020), which seems to be incremental. For strongly-convex-concave setting, it is unclear \nwhether APDG is optimal.\nFor convex-concave setting, as far as I could see, this is NOT the first linear convergence result under the smooth convex-concave problem with square full rank matrix A. PDHG, EGM and PPM all can be shown to exhibit linear convergence under this setting. Besides, when A is square and full rank, the results can even be adapted to nonconvex-noncave setting with A is large enough.\nAPDG is not optimal even in the simple bilinear case. It has a worse dependence on condition number on bilinear case compared with the optimal method. \nThere is no numerical experiment to demonstrate the empirical benefit of APDG compared with other popular primal-dual methods under these various settings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Xy4QQQUmezP", "reviewer": "Reviewer_GTc5", "summary": "This work studies the smooth convex-concave saddle-point problem with a form of separation and bilinear coupling and proposed a new algorithm named Accelerated Primal-Dual Gradient Method. This achieves an optimal linear convergence rate in the strongly-convex-strongly-concave regime, matching the lower complexity bound [Zhang et al., 2021]. It is even more interesting that the proposed algorithm achieves a linear convergence rate when at least one of the functions $f(x)$ and $g(y)$ is nonstrongly convex. Lastly, the authors introduce a linearly convergent algorithm for the general smooth and convex-concave saddle point problem $\\min_{x} \\max_{y} F(x, y)$ without the requirement of strong convexity or strong concavity.", "questions": "The authors seem to have not discussed anything relevant to a stochastic oracle. Is the result extendable to this case based on your algorithm? Some discussions would be helpful, at least.", "limitations": "This is a theoretical work and I do not find any limitations.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\nThe results in this paper provide the first accelerated convergence rate that matches the lower bound of [Zhang et al., 2021]. Especially I like the detailed discussion of complexity with literature in Section 5 and algorithm development in Section 6.2 which is educative and can be of independent interest. I enjoyed reading this paper very much.\n\n**Weakness**\nI did not have the chance to check all details, but upon my high-level checking the correctness of the main result is promising, and I do not think there is any weakness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6fZNknGB7Sj", "reviewer": "Reviewer_K3so", "summary": "- The authors proposed an accelerated primal dual gradient based algorithm that achieves the optimal lower bound, for the convex-concave saddle-point problem. \n- The authors proposed an algorithm that converges linearly with relaxed conditions on strong convexity or strong concavity. ", "questions": "- It will be helpful to provide some potential extensions / future directions to this work. ", "limitations": "- The proposed algorithms did not actually improve any bounds achieved by existing algorithms. \n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Solid theorems and analysis have been provided for the proposed algorithms.\n- The proposed algorithm achieves optimal bounds in different scenarios. \n\nWeaknesses:\n\n- The proposed algorithms did not actually improve any bounds achieved by existing algorithms. [UPDATE: This is not a 100% accurate statemnet. I have ignored the log factor in my intial comparison of the bounds. See the authors' comments for details.]\n- The proposed algorithm is solely for achieving the lower bound, while falling short of practical usefulness. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "4akZLXMF2s", "reviewer": "Reviewer_DLDA", "summary": "This paper presents an accelerated primal-dual algorithm for smooth convex-concave saddle-point problems of the form \n$$\n\\min_{x}\\max_{y}F(x,y)=f(x)+y^{\\top}Ax-g(y).\n$$\nThe proposed approach exploits the variational inequality formulation of this problem with single-valued operator $V(x,y)=[\\nabla_{x}F(x,y),-\\nabla_{y}F(x,y)]$. The derivation of the algorithm combines a standard Forward-Backward iteration with a linear extrapolation step that essentially allows to perform sequential implementations. The main result of the paper is a linear convergence result, in dependence of problem parameters, which covers the merely convex-concave case.\n", "questions": "Is there any algorithm closely related to the one introduced here? \n\nWhat is the reason introducing Algorithm 2 when the main algorithm in the paper is (apparently?) completely different? \n\nIs there any reason to restrict to the bilinear saddle point problem? Could the algorithm be formulated for general saddle point problems. ", "limitations": "no discussion of negative societal impact. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n+ The main message of the paper is clearly stated and well related to the existing literature. \n+ The authors spent a significant effort to explain the relation of the results of the paper with the existing results. \n\nWeaknesses: \n\n- The derivation of the algorithm is not natural to me. The explanation given in the main paper is not giving any insight in how the iterates are constructed. \n\n- The presentation of the paper is very confusing. The main Algorithm proposed is Algorithm 1. This algorithm is motivated by a combination of Forward-backward steps and a linear extrapolation step. Unfortunately, the derivation of the algorithm is not very transparent, and I am still not very confident that I have understood what is going on here. Appendix A contains a different algorithm (Algorithm 2) whose construction is, however, very clear. I cannot see a direct relationship between the two, so assume the material in the Appendix should be treated as a separate result, independent of the rest of the paper. This is not clear from reading of the paper and leaves the reader puzzled how one should read Appendix A. Even worse, Algorithm2 is an alternating versions of the operator extrapolation technique that has been studied recently in a sequence of papers. One important contribution is Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation, https://arxiv.org/abs/2011.02987. A Bregman extension can be found in Hui Zhang,\nExtragradient and extrapolation methods with generalized Bregman distances for saddle point problems,\nOperations Research Letters, Volume 50, Issue 3, 2022, Pages 329-334. \n\n- The proof is very long and technical. Given the short time available for reviews, it is impossible to check for correctness. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept