The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
Authors: Dmitry Kovalev
Alexander Gasnikov
Venue: NeurIPS 2022 Accept (2022)
Keywords: convex optimization
minimax optimization
saddle point problems
optimal algorithms

Abstract: In this paper, we revisit the smooth and strongly-convex-strongly-concave minimax optimization problem. Zhang et al. (2021) and Ibrahim et al. (2020) established the lower bound $\Omega\left(\sqrt{\kappa_x\kappa_y} \log \frac{1}{\epsilon}\right)$ on the number of gradient evaluations required to find an ϵ-accurate solution, where κx and κy are condition numbers for the strong convexity and strong concavity assumptions. However, the existing state-of-the-art methods do not match this lower bound: algorithms of Lin et al. (2020) and Wang and Li (2020) have gradient evaluation complexity $\mathcal{O}\left(\sqrt{\kappa_x\kappa_y} \log^3 \frac{1}{\epsilon}\right)$ and $\mathcal{O}\left( \sqrt{\kappa_x\kappa_y}\log^3 (\kappa_x\kappa_y)\log\frac{1}{\epsilon}\right)$, respectively. We fix this fundamental issue by providing the first algorithm with $\mathcal{O}\left(\sqrt{\kappa_x\kappa_y} \log \frac{1}{\epsilon}\right)$ gradient evaluation complexity. We design our algorithm in three steps: (i) we reformulate the original problem as a minimization problem via the pointwise conjugate function; (ii) we apply a specific variant of the proximal point algorithm to the reformulated problem; (iii) we compute the proximal operator inexactly using the optimal algorithm for operator norm reduction in monotone inclusions.

The First Optimal Algorithm for Smooth and Strongly-CoveexSttronly-yCC Minimax Optimization
Dmitry Kovalev
Alexander Gasnikov MIPT RAS! HSE
KAUST dakovalev1@gmail. com
gasuikov@yandex.
Abstract
In this paper, we revisit the smooth and optimization problem. /Zhang et al. (202T) and Ibrahim et al. (2020) established the lower bound Q (Rggky log )) on the number of gradient evaluations required and By are condition numbers for the
minimax
to find an e-accurate solution, where
strong convexity and strong concavity assumptions. However, the existing state- of-the-art methods do not match this lower bound: algorithms of Lin et al. (2020)
and Wang and Li (2020) have gradient evaluation complexity O ( (VRgg log" 2)
and O (VrigAiy log" (Kig log 2). respectively. We fix this fundamental issue by providing the first algorithm with ( (yiaty log 2) gradient evaluation complexity. We design algorithm in three steps: (i) reformulate the original problem as minimization problem via the pointwise conjugate function; (ii) we apply specific variant of the proximal point algorithm to the reformulated problem; (iii) we compute the proximal operator inexactly using the optimal algorithm for operator norm reduction in monotone inclusions.
Introduction
In this paper, we revisit the smooth and strongly-oovee--rrooll--mmae minimax optimization problem of the form
min max r(z) + F(z, (z. v) 9(y),
yER"v
where F(x, v): Rd x R4 IR is continuously differentiable function, r(z): Rd - U f {oo and g(v): dy + R U { are proper lower semi-continuous convex functions. Problem has been actively studied in economics, game theory. statistics and computer science (Başar and Olsder 1998 Roughgarden] 2010 Von Neumann and Morgenstern, 1947 Facchinei and Pang 2003
Berger 2013). Recently, many applications of this problem appeared machine learning, including
adversarial training (Madry et al. 2017, Sinha et al., 2017). prediction and regression problems (Taskar et 2005 Xu et 2009). reinforcement learning (Du et al. 2017 Dai al., (018) and
generative advesraial networks Arjovsky et al. (2017); Goodfellow et al (2014).
In our paper, focus the case when function far y) is strongly convex in x and strongly concave in y. There are several reasons to consider this function class. First, this setting is fundamental and
"King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
Mascow Institute of Physics and Technology, Dolgoprudny, Russia Institute for System Programming RAS, Research Center for Trusted Artificial Intelligence, Moscow, Russia National Research University Higher School of Economics, Moscow, Russia
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison of the state-of-the-art algorithms for solving smooth and strongly-convex strongly-coneave minimax problems in the number of gradient evaluations required find an c-accurate solution (Definition 1
Reference
Gradient Complexity
Tseng (2000)
Nesterov and Scrimali (2006)
O (max {liz Kiy log :)
Gidel et (2018)
Alkousa et al.
(0099)
O (min {Fe /Bry/ig May My Mor log
Lin et al.
2020
O (v Kintiyy log" 1
Wang and Li
(0200)
O (y log" (Ke log
Algorithm
(This paper)
O ( (ogliy log
Lower Bound
Zhang et al.
2021
Ibrahim et al.
2020
52 (BoKKy log 2)
studied by most existing works on minimax optimization Second, efficient algorithms initially developed for convex optimization often show state-of-the-are performance in non-convex applications (Kingma and Ba, 2014, Reddi al., 2019 Duchi et al. (011). Finally, we will further see that this fundamental setting is utterly understudied and lacks answers to even the most basic questions such as "What is the best possible algorithm for solving a problem in this setting?"
1.1 Related Work
Until recently, the best-known gradient evaluation complexity of solving problem O (max (Kg, Ky) log )) (Tseng 2000; Nesterov and Scrimali, 2006 Gidel et al. 2018). where Riz and Ky denote the condition numbers of functions f(:,)) y) and f(x ") respectively. The first attempt to provide an algorithm with an "accelerated" convergence rate was the work of Alkousa et al..
II was
2019 They provided an algorithm with O (min (Nz Ni Rz log 2) gradient evaluation complexity. This result was subsequently improved up to O ( Ky log L) by Lin et al. (2020) and O (yi log"(<e (ky) log 2) by Wang and Li (2020). However, these results do not match the lower complexity bound 52 (yRa,y log +) established by Zhang et al. (2021): Ibrahim et al. 2020). Hence, we have the following fundamental open problem:
Can we design algorithm that achieves the lower gradient evaluation complexity bound in smooth and hatpos/-ooooeeesstnn------
minimax optimization?
is worth mentioning that this open question was answered positively the works Kovalev et al. [202T); Thekumparampil et al. (2022): Jin et al. (202) in the case of minimax problems with bilinear coupling, i.c., when F(x, y) p(z) + Ay (y)). where p(z) and q(y) are smooth and strongly convex functions, and A is a d₂ x d, matrix. However, the algorithm provided in this work does not apply the general minimax problem (
1.2 Main Contributions
We develop the first optimal algorithm for solving problem (T) in the smooth and strongly-convex- strongly-coneet concave regime, which is the main contribution of this work. We split the algorithm development in three steps:
(i) In Section we reformulate problem I as a particular minimization problem.
"oss existing works minimax optimization study the convex convex-concave
However, this setting can be
easily reduced to strongly-conee weapll--oovex--teeee -strsssstt-ooooottee case via the regularization technique (Lin et al. 2020). "In contrast to smooth convex-concave minimax optimization, the answer to this question for smooth convex minimization was given by Nesterov 1983] several decades ago.

---

(ii) In Section
we develop a specific variant of the accelerated proximal point algorithm (Algorithm which will be used as a baseline for the optimal algorithm construction.
(ii) In Section 5 we develop an optimal algorithm for operator norm reduction in monotone in- clusion problems, which will be used for the proximal operator computation Algorithm
In the final S we summarize these three steps by describing the optimal algorithm construction and showing that the complexity of the proposed algorithm matches the lower bound.
As mentioned before, in Section 5] we develop an optimal algorithm for operator norm reduction
in composite monotone inclusion problems of the form (22). which is the second main contribution
of this work. To the best of our knowledge, there is only one optimal algorithm of Yoon and Ryu
(2021). which works for Lipschitz-continuous operators only, i.e. when B(u) 0 in problem (22) In contrast to this, our algorithm works in the composite case with general maximally monotone operator (tu).
Concurrent work of Carmon et al. (2022). In their recent concurrent paper, Carmon et al. (002)
developed an efficient variant of the Catalyst method (Lin et al. 2015) called RECAPP. In contrast to the original Catalyst method, RECAPP does not suffer from extra logarithmic factors in the complexity. When applied to the minimax optimization problem ( RECAPP achieves the optimal complexity O (Vizzy log :)- Hence, RECAPP is another optimal algorithm for solving smooth sonnggly-ccoeeesttnngyyyy-ooo
minimax optimization problems. However, the work of Carmon eet al. (2022) appeared on arXiv and was published at ICML 2022 later than the first version of this paper appeared arXiv.
2 Preliminaries
The following assumptions formalize the smoothness, strong convexity, and strong concavity proper- ties of function f(x,,))
Assumption 1. Function F(x, y) is -t-stnnggly convex in x, where Ptz > O. That is, the following
inequality holds for all æ Z2 E Rd,, y E Rdv
F v) 2 F F(11. v) + F(F, x1) + (Mz/2)l(xz x1ll².
(2)
Assumption 2. Function F(x,y) is My strongly concave in y. where My > O. That is, the following inequality holds for all E Rd= U1, V/2 E R&:
F(r, S F(x, v1) + ((, - wn) - (1y/ 2)) - 1111 Assumption 3. Function F(x,1) v) is L-smooth. That is, the following inequality holds for all
(3)
T2.02 Rds, $1, 4/2 Rd*:
VF (1) F2 v2) < L² (1 22 + +1 -221l))
(4)
Under these assumptions, by K2 L and Ky ..= ((),)) and F(x, -), respectively. The following assumption formalizes the properties of regularizers r(x) and g(v).
L, we denote the condition numbers of functions
Assumption 4. Functions r(z) and g(v) are convex, lower semi-contimuous and proper, i.e., there exist & E Rdd, " E Rdy such that r(f), g(v) < +o0.
By (x", v²) E Rdd Rd, denote the solution of problem ( which is characterized via the first-order optimality conditions
V,F(x', E Or(x"), V vyF(x",'" v²) E 0g(y").
(5)
Note that there exists a unique solution to the problem due to the strong convexity and strong concavity assumptions (Assumptions and Hence, for any point (x.y) E Rd RR can squared
distance to the solution || |a0=x" x+ +F y² 1|2 as an optimality criterion. We formalize it through
the following definition.
Definition 1. We call a pair of vectors (x. E dR x Rd an e-accurate solution of problem ① given accuracy e if satisfies
for
||
x 12 2 byy 11 se
(6)
3

---

3 Step I: Reformulation via Pointwise Conjugate Function
In this section, reformulate problem ① particular convex minimization problem. This reformulation will be beneficial because minimization problems are typically easier to solve than minimax optimization problems.
3.1 Pointwise Conjugate Function
We start by introducing the pointwise conjugate function which will be the main component of our problem reformulation. Let function F(x,y). y): Rd Rd,, IR defined as
F(r,v) F F(r,))
Mar ||0|| My llvll
One can observe that function F(z, v) is smooth, convex in and concave in due to Assumptions to Now, the pointwise conjugate function G(z, y): RR x RRd + is defined as follows:
|
G(z, 3) sup wE
(cx 2) r(x) f(x, v) + g(v)
(8)
One observe that for fixed y E RRd,, function G(::y) is nothing else but the Fenchel conjugate of function r(-) + F(.,)) g(y). Moreover, function G(z, y) is de- fined as pointwise supremum of family of convex and lower semi-continuous functions (v., y) (z, 2) - r(x) Fxx, y) g(v) x E R²= Hence, G(z,)) y) also convex and lower semi-continuous function. The following lemma provides characterization of the subdifferential of pointwise conjugate function.
Lemma 1. Let Z, E Rd, and E IRd be arbitrary vectors that satisfy
V (x, E 0r(x), w + V (x, F 0g(u). F(x, v) g and (z, w) E aG((.v).
(9)
Then, G(2.g)
3.2 Reformulation of the Minimax Optimization Problem
Now, we introduce the following minimization problem:
P(z.y) 1/ ||=12 My |lll G(2,y)
min A yER
(10)
2
out that this minimization problem be seen reformulation of problem justified by the following lemma.
This is Lemma 2. Problem (10) has unique solution (z", Rdd Rdy, where
=-a
(11)
and (x", .y") the unique solution of problem
Lemma 2 implies that if we find an approximate solution (2,8) E Rd x Bd to problem pair of vectors (-1= z, y) E dR x IRd will be an approximate solution to the original minimax problem.
I0
The idea of reformulating the minimax optimization problem as a minimization problem is not new and has been used in the state-of-the-arr works Li et al. (2020); Wang and Li (2020); Alkousa cet al. (2019). However, their reformulation is different from ours and has several disadvantages. In particular, it does not allow for building the optimal algorithm for solving problem (I. We provide detailed discussion of this in the Appendix.
Step II: Accelerated Proximal Point Method
In this section, we develop the main algorithmic framework for solving problem 100
which is
formalized as Algorithm We give the intuition behind the development of Algorithm 2
and provide
its theoretical analysis. Further, in Section 6 we will use this algorithmic framework to develop the first optimal algorithm for solving main problem (
Recall that for convex function h(x). Fenchel conjugate is detined ht (z) sup,,((z,)) h(x)).

---

Algorithm Accelerated Gradient Method
1: input: 2 = E Rd 30 of E Rd
2: parameters: a E (0, 1. 7/ fy 0z Oy > 0, KE (1,,.....
3: for k == 0. 1,2..... K
do
4:
(= gg
k) a(2", yy) + (111oa) (1))( uf)
5:
2f k+l 2g 02 V.V.Pee P
6:
y ++1 59 0g V, P
7:
x+1 2 + 7zH4 (2) x²) m=002 (2/ 2gg
y g+l oft + Nylly(yg
5t) B (v) 2
9: end for
10: output: (x*88")
Algorithm 2 Accelerated Proximal Point Algorithm
1: input: 20 = = E Rd, 3d = 5/ E Rd,
2: parameters: a E (0, 11. 12. fly Og > O, K E 21,
3: for =0,,,,2,..... K do
4: (zg, k) = a(z", )) + (1 - (z)
5: Find (x)) (+ .Vy .8 k+l =² (
k+l k+1 )
1 E Rd Rd Rdd Rd that satisfy [8]
6:
g+1 t + MaMe (2f
k+1 + Mh 1=- 2ttt)
7: y = n + (ully(y yr) - my ( ++ + 1y8f
8: end for
9: output: (2* )
4.1 Nesterov Acceleration
It is well-known that Accelerated Gradient Method of Nesteroo (1983 2003) is the optimal algorithm for solving smooth Sttooggly)coonee minimization problems. Therefore, we could try to apply this method to solving problem (TO), which is formalized as Algorithm]] I Note that we used the notation H4s = Ue in Algorithm I which the strong convexity parameter of P(2, v) in 2. Unfortunately. ..5,,,0 wy) can undefined. means that function P(z,y) y) can non-smooth, and the gradient V P(z
Algorithm | cannot be applied to problem (10)
4.2 Morcau-Yosida Regularization
In order to avoid the issues caused by the non-smoothness of function P(z, y). we use the Moreau- Yosida regularization (Moreau 1962 Yosida 2012). Consider function 0y (z, y) defined in the following way:
min po (2,8) * Y+ER*
11y || 2112 + 20,
y1 P(=+,t"**
(12)
20
where 0z,0, > O. Function p0..0y (2, y) is called the Moreau envelope of function P(z, y). The Moreau envelope has two crucial properties. First, it is smooth function. Second, it has the same minimizers as function P(2,y).
(²")")= arg min
p0 (2, v).
(13)
xER* xER*,.yER<
The latter means that could apply Accelerated Gradient Method problem 13 which would give us an efficient algorithm for solving problem (10). Further, we are going to construct such an algorithm.
4.3 Construction of the Algorithm
We start the construction of our algorithm by computing the gradient V (2 the Moreau-Yonr Yosida regularization (Lemaréchal and Sagastizábal 1997) suggests that the gradient of
v.)) The theory of
5

---

the Moreau envelope can be computed in the following way:
0 (= 24 + 0g [vg )イイ
p0s.00 (etg ugt) =
(14)
where (z)t), .// 1/-1) E Rd x Rd is computed via the following auxiliary minimization problem:
( (2) .y ++1) arg min zER's,yERdy 20 || =0
20, 1lv
1/ P(z,
(15)
Further, we choose parameter 02 - |ー² - Mr and write the first-order optimality conditions for this problem using the definition of function P(z, y):
M (2 2 + ps 2 K+1 8,7 (1f 6+1 , + Mybl
E - .y t)
(16)
The latter condition involves the subdifferential (G (G(2)))). y). Hence, we can rewrite this condition using Lemma 1 which provides the characterization of (G
(af(att) .y ) E Or(att)),
k+1 Mz (2) k+1 2g) + uz 28 k+1
(17)
(agtt :Vf + E @g(()(t) k+1 where rf k+l E Rdd and w
k+1 f
A+1 + 0g (u/ -//) + pylBf k+1 0.
w
E Rddy are auxiliary vectors. From (77 we get
Mr (2) k+l
-2)) = -xx) (x + Mr + 2tt))
0y (vf
k+1 v5) -c + mual(+))
which we plug into lines
and of Algorithm
Finally, replace the computation of (z)+t k+| 1 V/f 1) lines 5 and of Algorithm | using condi-
tion 17). It turns out that we can use the following relaxed version of condition (17) without hurting the convergence properties of the resulting algorithm:
k+
V F(r ,ft1) E or(z)t1),
f
k+1
v Fattt
k+1 .yf
k+1) E 0g(1)*
(18)
8
22 + 02 0 <
g ||ay k-1 + -z= - 111 + (1/l - -//1?
where A and A are defined as follows:
A * + Mx k+1 :ee =g)g)
2 (1)
(19)
A w k-1 + MoUf
k+1 + +0, (1/ k+1 -1/1)
4.4 Convergence of the Algorithm
After applying all the modifications mentioned above Algorithm I we obtain Algorithm 2 Theorem provides the iteration complexity of Algorithm 2 The proof of Theorem | in the Appendix.
can be found
Theorem 1. Let 11. be defined as
ns = 12/2, ny min (1/(2pg)) 0g/ (2a))
(20)
Then, to find an e-accurate solution of problem ① Algorithm requires the following number of iterations:
K K max a 0yHty log
(21)
In this case, the e-accurate solution will be given as (-M 1 2 "),, where (z "y² the output of Algorithm 2
"To be precise, Lemma I limplies the relation 17
16 rather than the equivalence 17
+ 16 However,
this is not an issue because provide the intuition behind the algorithm development in this section. The rigorous proof's postponed to the Appendix.

---

Algorithm 3 Extra Anchored Gradient for Monotone Inclusions
1: input: u'' E Rd
2: parameters: X 0, (1,2, 1,, c (0,
3: u JAp(u XA(u-1))
4: a = A(u²)
5: 6 {(" XA(uA 1 - -u²) do
D b E B(u")
6: for = 0, 1,1. .....
7:
1211/2 u¹ + Be(u0 u²) X(a' + bb)
8:
u' JAB(u' l + =e( -u') )A(u(t1/2)
9: a' e+1 = 1(u
10: be+1 = H(u' + Be( u²) - >A(u(t1/2) 1
D bt B(utt))
11: end for
12: output: (u" T + +
b D E B(u")
Unfortunately, Algorithm 2 cannot be applied to solving problem ① in its current form because it requires finding vectors k+1 :Mf k+1 _++1 wh+1) that satisfy condition (18) line 5 at each iteration. Further, we will show that finding these vectors can be seen finding an approximate solution particular monotone inclusion problem. algorithm for solving such monotone inclusions. In Section [ we will show how to combine this algorithm with Algorithm and obtain the first optimal algorithm for solving main problem (I).
.zf
Section []] we will provide an optimal
Step III: Operator Norm Reduction in Monotone Inclusions
In this section, we consider the following monotone inclusion problem:
find Rdd such that 0 0 A(u")") + B(u").
(22)
where A(u), B(u): : Rd Rd are maximally monotone mappings. We are interested in the case when A(u) is single-valued and Lipschitz continuous. The properties operators A(u) and (u)) formalized through the following assumptions.
Assumption 5. Mapping A(u): Fd + Rd is single-valued. M M-Lipschitz and monotone. That is, for all U1, U2 E Rdd (A(u1) A( (22)), ), u1 u2) 2 0 and [[A(u1) - A(u2)l S M M|[u u2ll.
Assumption Mapping B(u): Rdd = R2 is maximally monotone and possibly multivalued. That is, mapping B(u) satisfies the following conditions:
1. (u) is monotone, i.e., for all u1, u2 dom B, bi B(i)), B(uz) the following inequality holds: (u1 U2 b2) 2 0, where dom B {u E Rd B(u) + 0}. bj
2. The graph gphB {u,,b) 6) ddd Rd b B(u)} is not properly contained in the graph of any other monotone mapping Rdd
Note that mapping A(u) is also maximally monotone because is monotone and continuous (Rock) afellar and Wets 2009 Example 12.7). Further, we will use an operator JAB(u). I2 Rd which detined as
a+ E (u)(u) if and only if X >- u B(w*):
(23)
where À > O. This mapping is called the resolvent of mapping (u)). The maximal monotonicity of B(u) implies that the resolvent (An(u) is single-valued for all u E Rdd (Rockafellar and Wets 2009
Theorem 12.12).
Now, we are ready to present Algorithm 3 for solving monotone inclusion problem (22) The design of our algorithm is based the Extra Anchored Gradient Algorithm of Yoon and Ryu (021))
The critical difference between the algorithm of Yoon and Ryu (2021) and Algorithm 3 is that the
algorithm of Yoon and Ryu (2221) can be applied to problem (22) in the case ( {0) only.
Therefore, our Algorithm 3 can be seen as an extension of the algorithm of Yoon and Ryu 2021 for
general monotone inclusion problems of the form (22).
The following theorem provides the convergence guarantees for Algorithm theorem can be found in the Appendix.
The proof of the
7

---

Theorem 2. Assume that there exists at least single solution u² to problem (22 Let Sr be defined
as follows
Be = 2/ 3)-
(24)
Let X be defined as
A 1/(V5M).
(25)
Then, the following inequality holds
288M2
||a" 1 (T + 1)2 1lu u=.
(26)
where a² = A(u²) and b² B(w²).
6 Final Step: The First Optimal Algorithm for Minimax Optimization
In this section, we construct the first optimal algorithm for solving main problem In order to do this, we use Algorithm to compute vectors (I² .Vf A+1 -++1_ Further, we describe the construction of our algorithm in detail.
,2 w on line 5 of Algorithm
6.1 Construction of the Algorithm
As mentioned in Section Algorithm_caame cannot be applied to solving problem (T) in its current form because it requires finding the vectors satisfying condition (18) on line SIat each iteration. Further, we will show how to do this using Algorithm 3 Let IR R x IRdv, For each k E 1.2.......
consider operators A (u)): Rdd - Rd and B(u): IRd = Rdd defined as follows:
(u) = VTaa (z.
B(u) = { To (o.
by (rdr(x),b) by )olu))
(27)
where Yas Tv > O are parameters, variable u E Id is defined as
-~ 1/21/2 x. 7 1/2y), where (x.y) E Rdd Rddy
(28)
and operators a (x, y): Rd + ndd and az w): Rd + Rd are defined
dx v) V (1r, v) He (x 16 =
2
(29)
a (z, 8) = vV, (z, + Hyy + oy (y vT))
One can observe that operators **(n) and Bu)) satisfy Assumptions and 6 This is justified by the following lemma.
Lemma 3. Operator (u), defined by 27 is monotone and M -Liischhizz where M is given as
M 2 max (Ta (T. 17
(30)
Operator B(u), defined by 17 is maximally monotone.
Now, we are ready to construct the first optimal algorithm for solving main problem T which is formalized Algorithm 4 (it be found in the Appendix). In order to do this,
Al- gorithm 3 to perform the computations on line 5 of Algorithm 2 Consider the k-th iteration of
Algorithm 2 and replace line 5 of Algorithm 2 with the lines of Algorithm using the notation w' (7 R.t. 7v
, 1/2 ( for E (-,,0,1,2, .....
In addition, we replace the for-loop of Algorithm 3 with the while-loop that iterates until the following condition satisfied (see line [T Algorithm
I hxt) 1/21112 + Yo rollat (a 1, =.t)) 12:- <
(31)
S 7z lla 111 v - 111
8

---

Algorithm 4 FOAM: The First Optimal Algorithm for Minimax Optimization
1: input: 20 = = E R 3d = of E Rd,
2: parameters: a E (0, 1. 1/; fy. By > 0, {8,) C CO, 1), 2, Yr. To > O. Ke (1,
3: for kark- 0. .,...... K do
4:
(2g) v = a(zz ) + (1 (zy wf)
5:
(I 1) (-1 us 1
zk0 An() 1 gg Vg)
6:
Ya 2a (a (x= -1 . .yy 1))
7:
5.0 = , Ag(.) (1) k, - Tyday (x_--1,
7. (2 2e (2 .8 b 1,,,,1111
-1
8:
840
1
=4:0)
9:
To (1"M-1 Mo Aay 11
- D4:
10:
==0 0
11:
while condition [31 is not satisfied do
12:
2.141122 Rit + (x xh.1)
Y Maa hho) +b.
13:
1/ y + (y ghdt) Ma ,y +
b).0)
k141 = prox Ar(-) (x + 3r (x - In..) - - (x k2411/22 1/2 1
14:
15:
y ;, Ey + (r 0. -hh.t- - ( (2h,tt1/22
1/2 ggg.gg... g/.++1/22)
16:
be
Ted (otiit + Be (x h.0 - 2h11) Toda" (xthat( (xt:et1/22 1/2 gh - xhhet1)
I
Tod (y + Be k.0 hh) - -yy (x (whhet12
1//) g1
18:
t= t ++1
19:
end while
20:
t =
(xt+), 1+1 ) = (x .
21:
(2kt), w 1+ (xr (x++11 ./ 1 bz Pa .2ttt) - -by.')
22:
23:
st1 zt + +ott (2) - -²-) no ( f + Ho 2g 2g)2)
k+1
24:
yht1 1/th + 1ylliy و, y²) - By ( t + py kt)
end for
26:
output: (-p . )
We also set the initial iterates to - -1g 1k
"g and yt. 2/ on line 5 of Algorithm k+1 1++
and use
the output of the inner while-loop to compute vectors (ar411, . =-
+1)
lines 21 and 22
of Algorithm 4 Now, if we define parameters 7ay fy in the following way:
Yr 8p
0y:
(32)
then condition 31 line I of Algorithm becomes equivalent to condition (18
line of k+1 computed on lines 21 and 22 of Algorithm
Algorithm 2 Hence, vectors (z7 x+1 [+1
k
y
2
w
satisfy condition
(18) which implies that Algorithm is special case of Algorithm
6.2 Complexity of the Algorithm
It remains establish the gradient evaluation complexity of Algorithm 4 First, we need estimate the number of iterations performed by the inner whilc-loop of Algorithm 4 which is equal to th defined on line of Algorithm 4 Recall that the inner while-loop was constructed out of the lines of Algorithm 3 Hence, we can use Theorem 2 to provide an upper bound on t This is done by the following lemma.
Lemma 4. Assume the following choice of the parameters of Algorithm 4 stepsize X is defined by parameter M is defined by (30), sequence [3r] is defined by parameters To and Ty
are defined by 332 Then, th < T, where T is given as
T = max + 0, -.
(33)
Now, we are ready to provide the final gradient complexity of Algorithm 4 It is done by the following theorem.

---

Theorem 3. Let parameters of Algorithm The defined as follows: min (1, Bylly). 0, = 84z²
stepsizes nı and Fy are defined by (20). parameters "in and Ny are defined by 32 parameters ( [i are defined by (24). Then, to find an e-accurate solution of problem L Algorithm requires the following number gradient evaluations:
L
)
L
log log- 2)
max
(34)
Corollary 1. Without loss of generality and y in problem (T. Hence, Algorithm 4 has the following gradient evaluation complexity:
assume piz Z My otherwise we just swap variables
(
(Witp log :)
o
(35)
Acknowledgements
The work of A. Gasnikov was 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 (00000730331PSQ0000 agreement with the Ivannikov Institute for System Programming of the Russian Academy Sciences dated November 2, 2021 No. 70-2021-00142.
and the
References
Alkousa, M., Dvinskikh, D., Stonyakin, F., Gasnikov, A., and Kovalev, D. (2019). Accelerated methods for composite non-bilinear saddle point problem. arXiv preprint
Arjovsky, M., Chintala, S., and Bottou, L. (2017). Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223 PMLR.
Başar, T. and Olsder, J. (1998). Dynamic noncooperative game theory. SIAM.
Berger, J. O. (2013). Statistical decision theory and Bayesian analysis. Springer Science & Business Media.
Carmon, Y., Jambulapatii, A., Jin, Y., and Sidford, A. (2022). Recapp: Crafting more efficient catalyst for convex optimization. In International Conference Machine Learning, pages 6685-2685. PMLR.
Dai, B., Shaw, A., Li, L., Xiao, L., He, N., Liu, Z., Chen, J., and Song, L. (2018). Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference Machine Learning, pages 1125-115 1134. PMLR.
Du, S. S., Chen, J., Li, L.,, Xiao, L.,, and Zhou, D. (2017). Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pages 1049-1058. PMLR.
Duchi, J., Hazan, E.,, and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7).
Facchinei, F. and Pang, J.-S. (2003). Finite-dimensionul variational inequalities and complementarity problems. Springer.
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, (2018). A variational inequality perspective on generative adversarial networks, arXiv preprint 1802. 1802.10052 1055I.
Goodfellow, I., Pouget-Abadie, J.. Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A.. and Bengio, Y. (2014). Generative adversarial nets. Advances neural information processing systems, 27.
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.
10

---

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:2202.04440.
Kingma, P. and Ba, J. (2014), Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6985
Kovalev, D., Gasnikov, A., and Richtárik, P. (2021). Accelerated primal-dual gradient method for smooth and
saddle-point problems with bilinear coupling. arXiv preprint
arXiv:21
Lemaréchal, C. and Sagastizábal, C. (1997). Practical aspects of the moreau-yosida regularization: Theoretical preliminaries. SIAM journal on optimization, 7(2):367-385
Lin, H., Mairal, J., and Harchaoui, Z. (2015). A universal catalyst for first-order optimization. Advances in neural information processing systems, 28.
Lin, T., Jin, C., and Jordan, M. I. (2020). Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779. PMLR.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2017). Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706. 06083.
Moreau, J. J. (1962). Fonctions convexes duales et points proximaux dans un espace hilbertien. Comptes rendus hebdomadaires des séances de l'Académie des sciences, 255:2897-2899.
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 Ssyr, volume 269, pages 543-547.
Reddi, S. J., Kale, S., and Kumar, S. (2019). On the convergence of adam and beyond. arXiv preprint 190400970
Rockafellar, R. T. and Wets, R. J.-B. (2009). Variational analysis, volume 317. Springer Science & Business Media.
Roughgarden, T. (2010). Algorithmic game theory.
Communications of the ACM, 53(7):78-86
Sinha, A., Namkoong, H., and Duchi, J. (2017). Certifialle distributional robustness with principled adversarial training. arXiv preprint arXivv/710 11..07000..11. 10
Taskar, B., Lacoste-Julien, S., and Jordan, M. (2005). Structured prediction via the extragradient method. Advances in neural information processing systems, 18.
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 4281-4300 PMLR.
Tseng, P. (2000). A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2)431-446.
Von Neumann, J. and Morgenstem, O. (1947). Theory of games and economic behavior, 2nd rev.
Wang, Y. and Li. J. (2020). Improved algorithms for convex-concave minimax optimization. Advances in Neural Information Processing Systems, 33:4800-4810.
Xu, H., Caramanis, C., and Mannor, S. (2009). Robustness and regularization of support vector machines. Journal of machine learning research, 10(7).
Yoon, T. and Ryu, E. K. (2021). Accelerated algorithms for smooth convex-concave minimax problems with o (1/k) 2) rate on squared gradient norm. In International Conference on Machine Learning, pages 1099-12109. PMLR.

---

Yosida, K. (2012). Functional analysis. Springer Science & Business Media.
Zhang, J., Hong, M., and Zhang, S. (2021). On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming.
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": "Wh4jqDBxBHj", "reviewer": "Reviewer_LxoR", "summary": "This paper proposes a novel algorithm for the smooth and strongly-convex-strongly-concave minimax problem. The proposed method first reformulates the minimax problem as a particular minimization problem, and then solves the reformulated problem by a variant of the proximal point algorithm. The algorithm computes the proximal operator inexactly by extra anchored gradient method.", "questions": "I would appreciate it if authors can discuss whether the proposed algorithm is still optimal in the setting mentioned in the weakness part, and what is the main difficulties in the analysis under such assumption.\n", "limitations": "The proposed algorithm is a double loop algorithm, which may be less practical than single loop algorithms.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The studied problem is very important since convex-concave minimax optimization have many applications in machine learning area.\n2. The paper is well-written and easy to follow.\n3. The technical contribution is solid. The proposed framework is novel and it achieves the optimal gradient complexity.\n\nWeakness:\n\nNotice that Wang and Li (2020) provide a more elaborate analysis on the smoothness. Specifically, they assume the objective function is $(L_x,L_{xy},L_y)$-smooth, rather than use a unified smoothness $L=\\max \\\\{ L_x,L_{xy},L_y \\\\} $. Whether the proposed method is still optimal under such assumption is unknown, but this is not a critical point to address.\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": "S-QdGZmdK_", "reviewer": "Reviewer_scRz", "summary": "This paper firstly proposed the optimal first-order algorithm for the smooth and strongly-convex-strongly-concave minimax optimization problem with different parameters of strong convexity and strong concavity.", "questions": "See the Weaknesses in \"Strengths And Weaknesses\".", "limitations": "There is no potential negative societal impact of their work.\n\nPlease see suggestions in \"Strengths And Weaknesses\".", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper proposed an optimal algorithm for strongly-convex-strongly-concave minimax optimization with different parameters of convexity and concavity. The main idea is reformulating the minimax problem by pointwise conjugate function and Moreau-Yosida Regularization. Interestingly, Extra Anchored Gradient method can obtain a sufficient accurate solution of the sub-problem in O(1) complexity. As a result, the total first-order oracle complexity of the algorithm matches the lower bound.\n\nAlthough all components are well-studied, applying them to establish the optimal algorithm is non-trivial. I believe the theoretical contribution of this paper is valuable.  \n\n\nWeaknesses: \n1. The implementation of the proposed algorithm is complicated. It has two-loops and a plenty of parameters. I wonder whether it could perform well in practice. \n2. The analysis in this paper only differ the parameters of strong convexity and strong concavity, but the lower bound of Zhang et al. (2021) also consider the different parameters of smoothness. Is the algorithm still optimal in Zhang et al’s more general setting?\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": "EqmuneCihZh", "reviewer": "Reviewer_H9Wz", "summary": "This paper studies the optimization of the smooth and and strongly-convex-strongly-concave minimax objective. The proposed algorithm meets the previously established lower bound on the number of gradient evaluations required, thereby being the first optimal algorithm for this class of problem. \n", "questions": "N.A.", "limitations": "As above. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is notable that the work of  Wang and Li (2020) is close to optimality with the extra multiplicative term $\\log(\\kappa_x \\kappa_y)^3$, yet having simpler algorithmic structure. On the other hand, the proposed algorithm in this paper has the merit of being the theoretically optimal algorithm, but it can become complicated to implement in practice. It would be nice if the authors can have some experiments just as a simple proof-of-work. \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": "2Vux6mFlKkr", "reviewer": "Reviewer_hsnC", "summary": "Proposes algorithm to solve smooth and strongly-convex-strongly-concave minimax problem of the form $\\min_x \\min_y r(x) + F(x, y) - h(y)$. Here $r$ and $h$ are proximable and $F$ is differentiable, $L$ smooth and strongly-convex-strongly-concave. The main idea is to convert the minimax problem into an equivalent strongly convex minimization problem and then solve it by applying accelerated GD on it’s Moreau envelope. Gradient of the Moreau envelope is approximated using a new generalization of the recently proposed Extra Anchored Gradient method for making gradients of minimax objectives small.", "questions": "1. The title and message of the paper is misleading and exaggerated because they ignore the fact that there exist another very common parameterization of the same minimax problem which allows for different Lipschitz smoothness parameter in $xx$, $yy$ and $xy$ blocks. Most of the papers considered in the Table 1 consider this parameterization. Further, under this parameterization the proposed method is not optimal. I definitely got confused while reading the paper. I recommend the authors to reconsider their message and the title to avoid any misconceptions, and appropriately discuss these other parameterizations.\n  - one of the “holy grails” of smooth minimax optimization is the recovery of optimal convex rates in the limit $L_{xy} \\to 0$, $L_{yy} \\to 0$ when $L_{yy}/\\mu_{yy} = 1$. This is not possible in the stricter parameterization studied in this paper. Please discuss this as a limitation.\n\n2. “open question was answered positively in the work of Kovalev et al. (2021) in the case of minimax problems with bilinear coupling”: There are two other papers also which solve this same problem [A, B]. These papers are particularly related and may be more closer to this paper than Kovalev et al. (2021) because the reformulation in eqns (7-8) are similar to [Eqn 14, A] and [Eqn 13, B]. The main idea of this paper to work in the dual space of either the $x$ or the $y$ variable is related to the dualization done in [A, B]. Please appropriately give credit and compare your ideas to these methods.\n\n3. In the proof of Theorem 1, LHS of the final result (eg: initial sub-optimality gap in P(z, y)) is never fully computed in terms of the original problem parameters, gaps and distances. This may end up being a minor issue, but please make your proof more rigorous.\n\n4. Abstract is hand-wavy when stating the complexity is $O(\\sqrt{\\kappa_x \\kappa_y} \\log(1/\\epsilon))$. Checking the proof of Theorem 1, some $\\log(\\mu_x)$ and $\\log(\\mu_y)$ terms are missing. Please make the results more rigorous. \n\n5. There will be numerical instability because of $\\mu_x^{-1} = \\theta_x^{-1}$ when $\\mu_x$ is very small. Does the authors have a solution for this issue? Note that (proximal) mirror-prox can achieve a sub-optimal linear convergence rate using a stable stepsize=4/L, without any numerical instability. Please discuss this limitation in the paper.\n\n6. Out of curiosity, is it possible to use a similar formulation as (13 ) when the minimax objective is not strongly monotone on one of the sides? Currently the reformulation only works for strongly-convex-strongly-convex problems.\n\n[A] Thekumparampil et al., Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization. https://arxiv.org/abs/2201.07427 (also at AISTATS 2022)\n\n[B] Jin et al., Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. https://arxiv.org/abs/2202.04640 (also at COLT 2022)", "limitations": "Limitations were not discussed. See above for ideas.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Pros\n1. Under the assumptions of the paper, the algorithm is better than baselines because they tighten the cubic- or square-log factors in the complexity to just log factor.\n2. Great presentation of the main ideas of the algorithm and proof sketch of Algorithm 1.\n3. The reformulation of strongly-convex-strongly-concave minimax problem to strongly-convex minimization seems novel and could be potentially useful elsewhere too.\u0010 However, there are concerns about missing related work.\n4. Problem formulation is general. So it can capture both constrained and unconstrained problems, however the paper doesn’t discuss it as such.\n\n\n### Potential for improvement\n1. The title and message of the paper is misleading and exaggerated because they ignore the fact that there exist another very common parameterization of the same minimax problem which allows for different Lipschitz smoothness parameter in $xx$, $yy$ and $xy$ blocks. See below.\n\n2. Can greatly improve the related works section. To give some examples, please discuss papers which separately consider $L_x$, $L_y$ and $L_{xy}$ Lipschitz constants. Also two very related works on bilinear coupling (see [A, B] below) are missing and they need to be discussed.\n\n3. Proof and results are not fully rigorous. See below.\n\n4. There will be numerical instability because of $\\mu_x^{-1}$ when $\\mu_x$ is very small. See below. ", "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