Faster Stochastic Algorithms for Minimax Optimization under Polyak-{\L}ojasiewicz Condition
Authors: Lesi Chen
Boyuan Yao
Luo Luo
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic minimax optimization
Polyak-Lojasiewicz condition

Abstract: This paper considers stochastic first-order algorithms for minimax optimization under Polyak-{\L}ojasiewicz (PL) conditions. 
We propose SPIDER-GDA for solving the finite-sum problem of the form $\min_x \max_y f(x,y)\triangleq \frac{1}{n} \sum_{i=1}^n f_i(x,y)$, where the objective function $f(x,y)$ is $\mu_x$-PL in $x$ and $\mu_y$-PL in $y$; and each $f_i(x,y)$ is $L$-smooth. We prove SPIDER-GDA could find an $\epsilon$-approximate solution within ${\mathcal O}\left((n + \sqrt{n}\,\kappa_x\kappa_y^2)\log (1/\epsilon)\right)$ stochastic first-order oracle (SFO) complexity, which is better than the state-of-the-art method whose SFO upper bound is ${\mathcal O}\big((n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$, where $\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$.
For the ill-conditioned case, we provide an accelerated algorithm to reduce the computational cost further. It achieves $\tilde{{\mathcal O}}\big((n+\sqrt{n}\,\kappa_x\kappa_y)\log^2 (1/\epsilon)\big)$ SFO upper bound when $\kappa_x\geq\sqrt{n}$. Our ideas also can be applied to the more general setting that the objective function only satisfies PL condition for one variable. Numerical experiments validate the superiority of proposed methods.

Faster Stochastic Algorithms for Minimax Optimization under Polyak-Lojasiewice Conditions
Lesi Chen School of Data Science Fudan University 1schen1 9@fudan. edu. cn
Boyuan Yao School of Data Science Fudan University byyao196fudan. edu.
Luo Luo" School of Data Science Fudan University luoluo@fudan edu. cn
Abstract
This paper considers stochastic first-order algorithms for minimax optimization under Polyak-Lojasiewicz (PL) conditions. We propose SPIDER-GDA for solv- ing the finite-sum problem of the form min, max, f(r, y) - fi y), where the objective function f(z y) is M in and My -L in y: and each fz y) is L-smooth. We prove SPIDER-GDA could find an e-approximate solu- tion within O ((n + k log(1 (1)) stochastic first-order oracle (SFO) com- plexity, which is better than the state-of-the-art method whose SFO upper bound is O(nn + n223 (2/3k) log(1/e)), where K.. L/pa and Ki L/ For the ill-conditioned case, we provide an accelerated algorithm to reduce the computa- tional cost further. It achieves Ö(nn + vn Kig log (1/()) SFO upper bound when Ky Z vn. Our ideas also can be applied to the more general setting that the objective function only satisfies PL condition for one variable. Numerical experiments validate the superiority of proposed methods.
Introduction
This paper focuses on smooth minimax optimization problem of the form
1 n Σ f((x,))
max f(z, v) #ER4s yERdy
min
which covers lot of important applications machine learning such reinforcement learning [10
42), AUC maximization [13 24
48 imitation learning [5] 32), robust optimization [IT]. causal
inference 28 game theory
29 and so on.
We are interested in the minimax problems under PL conditions 9 32
The PL condition
35
was originally proposed relax the strong convexity in minimization problem that is sufficient for achieving the global linear convergence rate for first-order methods. In machine learning community, has been successfully used analyze the convergence behavior for overparameterized neural networks 23 robust phase retrieval 440 and plenty of fundamental models [18] There are many popular minimax formulations only satisfy PL condition, but lack strong convexity (or strong concav- ity). The examples include PL-game [32]. robust least square [45), deep AUC maximization 24] and
generative adversarial imitation learning of LQR 55 32
Yang et al. [45] showed that the alternating gradient descent ascent (AGDA) algorithm linearly converges to the saddle point when the objective function satisfies two-sided PL condition. They also proposed the SVRG-AGDA method for the finite-sum problem (T), which could find c-approximate
'The corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: We present the comparison of SFO complexities under two-sided PL condition. Note that Yang et al. [45] named their stochastic algorithm as grrfancerredced--oe (VR-AGDA). Here we call it SVRG-AGDA to distinguish with other variance reduced algorithms.
Algorithm
Complexity
Reference
GDA/AGDA
(nkgkz log (1/e))
Theorem B.1
45
SVRG-AGDA
o (nn n / log (1/e))
45
SVRG-GDA 0 ((n + n 2/ Kig x log (1/c))
Theorem C.1
SPIDER-GDA
O ((n + / log (1/e))
Theorem 4.1
(VnKo log" (1/c)).
vn z Kiys Ky S v S Kifkyi Kighi 2 vn.
AccSPIDER-GDA
① (nKx log (1/c)):
Theorem 5.1
((n + Viniztn) log (1/e)),
solution within O( + Kg log (og( stochastic first-order oracle (SFO) calls P where Kx and Ky are the condition numbers with respect to PL condition for x and y respectively. The variance reduced technique in the SVRG-AGDA leads to better convergence rate than full batch AGDA whose SFO complexity is O ( log(1/e)). However, there are still some open questions left. Firstly, Yang al. 45 's theoretical analysis heavily relies on the alternating update rules. remains interesting whether a simultaneous version of GDA (or its stochastic variants) also has similar convergence results. Secondly, it is unclear whether the SFO upper bound obtain by SVRG-AGDA can be improved by designing more efficient algorithms.
For one-sided PL condition, we desire to find the stationary point of g(x) A max yER fxx y). since the saddle point may not exist. Nouiched al. [3] proposed the multi-step GDÀ method that
achieves the e-stationary point within (x Le log K e)) numbers of full gradient iterations. The
similar complexity also can be obtained by AGDA [45] Recently, Yang et al. 47 proposed the
Amoothed-AGDD that improves the upper bound into OKg 2) Both multi-step GDA Nouiehed
al. [32] and SmoAthed-AGDA (46) can be extended to online setting [14), but the formulation (I)
with finite-sum structure has not been explored.
In this paper, introduce variance reduced first-order method, called SPIDER-GDE which constructs the gradient estimator by stochastic recursive gradient and the iterations are based on simultaneous gradient descent ascent. We prove that SPIDER-GDA could achieve c-approximate solution of the two-sided PL problem of the form (1) within O ((n + /n Kzx²) log(1/e)) SFO calls, which has better dependency on than SVRG-AGDA 45 We also provide an acceleration framework to improve first-order methods for solving ill-conditioned minimax problems under PL conditions. The accelerated SPIDER GDA (AceSPIDER -DA) could achieve e-approximate solution within Ö(nn + /n Ky log (1/e)) SFO calls" when Ky 2 vn, which is the best known SFO upper bound for this problem. We summarize our main results and compare them with related work in Table D Without loss of generality, we always suppose K₂ 2 Ky. Furthermore, the proposed algorithms also work for minimax problem with one-sided PL condition. We present the results for this case in Table
2 Related Work
The minimax optimization problem can be viewed as the following minimization problem
min wERda
g(x)
A max vE
f(x, v)
A natural way to solve such problem is the multi-step GDA algorithm 21 double-loop iterations in which the outer loop can be regarded as running inexact gradient descent on
25 32 36 that contains
provided an SFO upper bound O + 2/2 max x2 x log(1/e)). which can refined O(1 + 2/3 x log(1/c)) by some little modification in proof.
"The original analysis 45
In this paper, the notation O(-) to hide the logarithmic factors of Kz, Ky but not l/c.

---

Table 2: We present the comparison of SFO complexities under one-sided PL condition.
Algorithm
Complexity
Reference
Multi-Step GDA
Onn ( llo((ky/e))
32
GDA/AGDA
O (nn
Theorem B.2
45
Smooothed-AGDA
o Le Le
47
SVRG-GDA
0 nn + n213 kig -2-
Theorem F.
SPIDER-GDA
0 nn + vnnig Ic 2)
Theorem 6.1
(Vi (og(tty//))
vn S Kiji
AceSPIDER-GDA
o (nLe i /E) (n + VEngLE
Ky S vn S nig
Theorem 6.2
ky S vn.
g(x) and the inner loop finds the approximate solution to max, f (zx y) for given æ. Another class of methods is the two-times wo--timescale (alternating) GDA algorithm [1 44 45 that only has single- loop iterations which update two variables with different stepsizes. The two-timescale GDA method can be implemented more easily and typically performs better than multi-step GDA empirically. Its convergence rate also can established by analyzing function g(x) but the analysis more challenging than the multi-step GDA.
The variance reduction is a popular technique improve the efficiency of stochastic optimization algorithms 12 7 12 16. 17
19
27
31 33 34 37439
43
49 [5]]. It is shown that solving
nonconvex minimization problems with stochastic recursive gradient estimator 12
16
3
43
has the optimal SFO complexity. In the context of minimax optimization, the variance reduced
algorithms also obtain the best-known SFO complexities in several settings [ 15 Specifically, the (near) optimal SFO algorithm for several convex-conees minimax problem has
25 26
been proposed 26), but the optimality for the more general case is still unclear 25 45
The Catalyst acceleration (0 is a useful approach to reduce the computational cost of ill-conditioned optimization problems, which is based on sequence of inexact proximal point iterations. Lin et al. [22] first introduced Catalyst into minimax optimization. Later, Luo et al. [26). Tominin al. 41). Yang al. [46] designed the accelerated stochastic algorithms for convex-concave and nonconvex-concave problem. Recently, Yang et al. 47 also applied this technique to one-sided PL setting.
3 Notation and Preliminaries
First all, we present the definition saddle point.
Definition 3.1. We say (x*, v²) E Rd Rdd is saddle point of function f Rdde x Rdy + R is holds that (x=,,) I f(x", v²) S fxx for any E IRds and y E Rd,
Then formally define the Koayak-Lojssiwiizz (PL) condition 33 as follows.
Definition 3.2. We say a differentiable function Rdd + satisfies J-PL for some μ > if [[V((=)]1² 2 2p(h(z) ming/er h(=')) holds for any E Rd..
Note that the PL condition does not require the strongly convexity and it can be satisfied even if the function is nonconvex [8].
We are interested in the finite-sum minimax optimization problem (1) under following assumptions. Assumption 3.1. We suppose each component fi R x R&d - B. is L-smooth, i.e., there exists constant L > 0 such that V/V fz y) - ff( y 22 < 12 (1 x'11 + lly s/ll²) holds for any I dd and y. y E Bdd. Assumption 3.2. We suppose the differentiable function f Rdd x Rdy + satisfies two-sided PL condition, i.e., there exist constants paz >> O and pay > O such that [(, 9) is PPL for any E Rdy and - fxxx )) is My P for any a dzd
3

---

Under Assumption 3.1 and 3.2, we define the condition numbers of problem ① with respect to PL conditions for x and as Kar L/p2 and Kiy - L/py respectively.
We also introduce the following assumption for the existence of saddle point. Assumption 3.3 (Yang et al. [45]). We suppose the function f Rd x R&,, + R has at least one saddle point (z" )- We also suppose that for any fixed y E Rd,, the problem minzeR*= f(z, y) has nonempty solution set and finite optimal value; and for any fixed E Rd=, the problem maxyeR's f(x, y) has a nonempty solution set and a finite optimal value.
The goal of solving minimax problem under two-sided PL condition is finding an e-approximate solution or e-saddle point that defined as follows.
Definition 3.3. We say x is an 6-approximate solution problem ! if holds that g(z) g(x*) S
where ((x) ) max max fa, y)-
Definition 3.4. Under Assumption 3.3 soy (Ir, y) is an e-saddle point of problem if holds
that || x 1|2 + 1²1 I for some saddle point (x",y")
We allow the saddle point does not exist for the problem with one-sided PI. condition. In such case, it is guaranteed that g(x) - yax (x,, y) is differentiable [32 Lemma A.5] and we target to find an e-stationary point of g(z)).
Definition 3.5. If the function Rdd +R R is differentiable, we say x is an e-stationary point of g if holds that Vg(())] S.
4 A Faster Algorithm for the Two-Sided PL Condition
We first consider the two-sided PL conditioned minimax problem of the finite-sum form ( under Assumption 3.1 and We propose novel stochastic algorithm, which we refer as SPIDER- GDA. The detailed procedure of our method is presented in Algorithm | SPIDER-GDA constructs the stochastic recursive gradient estimators
12 31
follows:
Σ iES.
B
Gy(Ee.. Vc,k)
- V (ffi (L) iE
Σ
GT G...AAA--)))...AA.............
B
simultancously updates two variables x and y by estimators G2 and Gy with different stepsizes Tu = 0(1 (I,, and T, @(1/L) /.) respectively. Huang et al. [6]] Luo et 225 Xian et 44 have studied the SPIDER-type algorithm for manconvex-stronglyycoom
problem and showed it converges to the stationary point of g(z) max f(z, y) sublinearly. However, solving the problem minimax problems with two-sided PL condition desires stronger linear convergence rate, which leads to our theoretical analysis be different from previous work.
We measure the convergence of SPIDER-GDA by the following Lyapunov function
AT&
VE, g( 9(x") +
(g(I),)) fIz,k Mr,))),
Ty
where x² arg minn g(x) and = (nz)). We can establish recursion for V., as follows
EMVKISE SE
Vr,0
To 16
M B
Σ
CC (m.,. x1
Arz
2
M B
IC (G,(E)..)..))))
16
Using the above inequality by setting M B v leads to the estimators G. (+,, Uc) and Gy (Gs, Vt) be sufficiently close to the exact gradient and converge to zero linearly, which indicates g( also converges to g(x") linearly. We formally provide the convergence result for SPIDER-GD. in the following theorem and its detailed proof is shown in appendix.
Theorem 4.1. Under Assumption 3./ 3.2 and 3.3 we run Algorithm with M = B Vn. 422A/ and T = [log{1/c)] Then the output (žr, .r) satisfies g(Ør) g(2*) < and g(rr) f0rr, ((rr < 24c in expectation; and it
Ty 1/(5L,,> >= 32 /12 Tr /y/ (4x K
takes more than O( + vn log(1/e)) SFO calls.

---

Algorithm SPIDER-GDA (S, (wo, uo). T, K, M, B, Ta, Ty)
1: Øo = I0, 3/ = y/o
2: for 1...., T do
3: 2t,0 Tt, 1/,00 1tr
4: for k = 0, ,............. ..... K- do
5: if mod (k, M) 0 then
6:
Gr(Te, Vt,k) = (aI vt,k)) Gy(Etk, Br,k) = Vaf B(
7:
8: else
9:
draw mini-batches S and Sy independently with both sizes of B.
10:
Ga (E $/ Eies, [V B.,e) V + G Gy(E,) = B Eies, Vyli(ELa. B, G
11:
end if
13:
21,++1 Jt,k To G2 G Vt.k)
14: Mr,k+1 yy + (Z Bt,k)
15: end for
16: choose (#++1, Dt+1) from (FILk k)) uniformly at random.
17:
end for
18: return (():
Algorithm 2 ACCSPIDER-GDA Ug Tr
2: for 0, 1,.1,...h 1 do
3: (IK+1, 21-1))k1))) = SPIDER-GDA + + (xl, 2k). K, M, By,
4: uk+1 = 0b+1 + 7(xx+1 mk)
5: end for
6: option (two-sided PL): return (IK.ИK)
7: option II (one-sided PL): return () chosen uniformly at random from {(Tk )
K km
Our results provide an SFO upper bound O(n (Tk log(1 (1/))) for finding an e-approximate solution that is better than the complexity O((n n//33 Kg my) log(1 (/))) derived from SVRG- AGDA [45]. is possible to use SVRG-type I7 49 estimators to replace the stochastic recursive estimators in Algorithm [ which results the algorithm SVRG-GDA, We can prove that SVRG-
kg GDA also has (((n + n R log(( log(1/<)) SFO upper bound that matches the theoretical result of SVRG-AGDA. We provide the details Appendix C
Further Acceleration with Catalyst
Both the proposed SPIDER-GIT GDA (Algorithm D and existing SVRG-AGDA 451 have the com- plexities more heavily depend the condition number of than the condition number of x. It is natural to ask can we make the dependency of two condition numbers balanced like the results in the croogllyconvex--tronnlyy introducing the Catalyst acceleration.
case 22 25 41 In this section, show it is possible by
To make acceleration possible, we need to assume the uniqueness of the optimal set for inner problem.
Assumption 5.1. We assume the inner problem maxyeR's f(x, 2) has unique solution.
5

---

We proposed the accelerated SPIDER- GDA (AceSPIDER (AMPPDER-DDA) in Algorithm 2 for reducing the computational cost further. Each iteration of the algorithm solve the following sub sub-problem
min max Fi( rel yERdy
min
g(x)
+ 2 1 us
(2)
xERd
2
by SPIDER-GDA (Algorithm T.. AceSPIDER-GDD has the following convergence result the sub-problem attain the required accuracy.
Lemma 5.1. Under Assumption 3.7 3.2 and 3.3 we run Algorithm 2 by 2L, 7 = and the
appropriate setting for the sub-prot cubb-roblem solver such that E[[ Ik + l
Us 14 S 6, where
(Ty, 8k) a saddle point of Fk-1 1 (k: 2 1) and we set the precision
put
6 11( AT.)T.
(3)
Then holds that
B[g(zs) -0(00))(())))))) " 233 + Meo
(g(2w)) -a()))))x))) +
The setting B (T) in Lemma 5.1 guarantees the sub-problem 2 has condition number of the order (1) for x. is more well-conditioned on z, we prefer to address the following equivalent problem
max min Fx(x,)) = min max yER ZERd,
(-Fx(r
(4)
yERdy mcR4s
Since (4) is a minimax problem satisfying two sided PL condition, we can apply SPIDER-GDA to solve it. And we can show that under Assumption 5.1 the saddle point (Tx, ÿk) of each Pa-1(k (k 2 1)
is unique (see Lemma E.2 in appendix) and we are able to obtain good approximation to it.
Lemma 5.2. Under Assumption 3.7
3.2 and and if we use Algorithm to solve each sub-problem max yER minzeRd. Fa(ar,) 9) 2 with 3 2T. M B /n,
1/(15L), x 288, To
Ta/ (24X), K /4224/ ( Th [log(1/0) 0x)) then it holds that
B|| 2 + l iu+1l1? < 7236 7 1EE(l - 2x112 2 11 5h 3l),
where (Tx; U&) is the unique saddle point of Fa-1 2 1).
For short summary, Lemma 5.1 means Algorithm 2 requires OKKr log(1/c)) numbers of inexact proximal point iterations to find an c-approximate solution of the problem. And Lemma E. tells us that each sub- cub-problem can be solved within SFO complexity of O (n + vnk,,) log(1 [1 0 Thus, the total complexity for AccSPIDER-OG -DAA becomes (((nK, + ((K,, log(1/e) log(1 (1/6))) Our next step is to specify &n which would lead to the total SFO complexity of the algorithm.
Theorem 5.1. Under Assumption 3.7
3.2 3.3 and 5. if we let = 0, 2L and use Algorithm 7
solve each sub- sub--robbem max, geR Fa
with M, B, Tz Ty. K defined as Lemma
5.2 and Te [log(1 [, where
min
(8-L),,6
k 2 1;
7236
1655 -
-1-1
8z-
(5)
6pp
k ==0, O,
(L
and 6 is followed by the definition in 33. Then Algorithm can return æk such that g( -x(xx*) S in expectation with no more than ([xx + ((kgKKy) log(1 (g/c)) log(KzKy//e) SFO calls.
Lemma 5.1 does not rely on the choice of sub- nub-problem solver, we can apply the acceleration framework in Algorithm by replacing SPIDER-GDA with other algorithms. We summarize the SFO complexities for the acceleration of different algorithms in Table
Extension to One-Sided PL Condition
In this section, we show the idea that SPIDER-GDA and its Catalyst acceleration also work for one-sided PL condition. We relax Assumption 3.2 and 3.3 to the following one.

---

Table 3: Accelerated results for different methods under two-sided PL condition.
Method
Before Acceleration
After Acceleration
GDA
OnnKak (og()/e))
(NKatty (1/e))
2/ K2 log (1/e))
n 1/3 2 Kyz
SVRG-GDA
O(n n² n=("))m))))))))) lont))
o (nri log (1/e)),
Ry S n 1/3 x Ky
no accelcration,
KaMy S n 1/3
Ô (VTnss log log (1/e))
vn Kiy
SPIDER-GDA
((n + (og)
Ô (nxa log (1/e)) no acceleration,
Ki S vn S Kiz
KzNyy S Vn.
Assumption 6.1. We suppose that (((,,)) is Py-PL any x E Rd=; the problem yER's [(x y) has nonempty solution set and an optimal value g(x) A max fx, y) is lower bounded, i.e.. we have g" inf z g(z) -00
We first show that the SFO complexity of SPIDER-GDA outperforms SVRG-GDA by a factor of (n1) Theorem 6.1
Theorem 6.1. Under Assumption 3.1 and 6. Let I = and M, B, Tz: Ty. X as defined in Theo- rem 4. and K = [644(Tze2)], then Algorithm I can guarantee the output & to satisfy [[Vg())] S
in expectation with no more than Onn + Vnng Le -2) SFO calls.
The AccSPIDER-GDA also performs better than SPIDER-GIE in one-sided PL condition for ill conditioned case. the following lemma, we show that AccSPIDER -DDADDERRGDDAAAAE could find an approximate stationary point if we solve the sub- uub-problem sufficiently accurate.
Lemma 6.1. Under Assumption 3.1 and 6.1 for some saddle point (ãx, 0k) of FR 1), where
it holds true that [B[[] Txl1? + 11ye- Uh 1| s
2
(6)
8 (22 + +1)
Let 3 2L, then for the output (#, 1) of Algorithm 2 it holds true that
E B < 83(g(zo) (Xo) 9*)
K
Compared with two-sided PL condition, the analysis of AceSPIDER-GIE is more complicated since the precision & at each round are different. By choosing the parameters of algorithm carefully, obtain the following results.
Theorem 6.2. Under Assumption 3.1
if we run Algorithm 2 by 7 0, = 2L and use Algorithm solve each sub-problem max,eRd, mingeRdo (1, y) (2 with M, B, Tux Ty. X, K and Ti (dependent 8) as in Theorem 5.7 and is followed by the defmiition in Lemma 6.1 then in expectation within O(n + VTx., Le - log(k.//t)
6.1 and 5.1
Algorithm can find & such that [[
SFO calls.
We can directly set /3 = 0 for Algorithm in the case of very large n and this case AceSPIDER- GDA reduces to SPIDER-GDA, The summary and comparison for the complexities for the one-sided PL condition shown in Table Besides, the algorithms of GDA and EVRG-GDA also can be accelerated with Catalyst framework and we present the corresponding results in Table
'The complexity for finding c-stationary point of SVRG-GDA in presented in Appendix
7

---

Table 4: Acceleration for different methods under one-sided PL condition.
Method
Before Acceleration
After Acceleration
GDA
O (nxILe
O (nRyLE log(Ks/c))
O 1/ KyyLe ToeLLe---ogghee (log(my/e))
n113 S Kyj
SVRG-GDA
O (n+ (n+nn//nn
o (nLe -2 log(Ms/())
my S 1/3 & Kag
no acceleration,
ni S n/13.
0 OVTinyLe (ogilyLe-og((u/e)))
vn S Nigi
SPIDER-GDA
O (n+ vTKeLe
(nLe==lo((rg(e))
By 2 v & rig
no acceleration,
x 2 vT.
7 Experiments
In this section, we conduct the numerical experiments to show the advantage of proposed algorithms and the source code is available We consider the following two player Stlyak-Lojasiwwiee game:
1 T Px x 2
1 z"
min max f(x, y)
Qy++ + TQy
Ry.
zERd weRd
where
1 P=
1 - ri and R=
PsP Q
1=1
We independently sample Pt, and r, from (0, Ep). Σq) and ( Σx) respectively. We set the covariance matrix Ep as the form of U DU such that U E Rdxr is column orthogonal matrix and D E IR is diagonal with r d. The diagonal elements of D are distributed uniformly in the interval [n. L] with O < < L. The matrix Σq is set by the similar way to Σp. We also let ΣR = 0.1VVT where each element of V E Rdxd is sampled from N 1) independently. Since the covariance matrices Σp and Σq are rank-deficient, it guaranteed that both P and Q are singular. Hence, the objective function is not strongly-conve two-sided Pl-condition 18) We set n 6000, 10, r 5, for all experiments; and let jr
and not strongly-concet
but it satisfies the
be 10-5 and 10 for two different settings.
We compare the proposed SPIDER-GDA (Algorithm I and AccSPIDER-GDD (Algorithm 2 with the baseline algorithm SVRG-AGDA [45] We let B = 1 and M = n for all of these algorithms and both of the stepsizes for x and y are tuned from {10-1, 10-2, 10--3, 1004 10 -- ".. For AccSPIDER, we set 8 L/ (20m) and 0.999. We present the results of the number of SFO calls against the norm of gradient and the distance to the saddle point in Figure and Figure It is clear that our algorithms outperform than baselines.
8 Conclusion and Future Work
In this paper, we have investigated stochastic optimization for PL conditioned minimax problem with the finite-sum objective. We have proposed the SPIDER-GDE algorithm, which reduces the dependency of the sample numbers in SFO complexity. Moreover, we have introduced a Catalyst scheme to accelerate our algorithm for solving the ill-conditioned problems. We improve the SFO upper bound of the state-of-the-art algorithms for both two-sided and one-sided PI. conditions.
However, the optimality of SFO algorithms for the PL conditioned minimax problem is still unclear. It is interesting to construct the lower bound for verifying the tightness of our results. It is also possible to extend our algorithm to online setting.
8

---

100
10
3 1'
SVRG SPIDER
SVRG SPIDER
AccSPIDER
AccSPIDER
10
1
10
10
5
#SFO
x 10
#SFO
x10
(a) Distance to saddle point
(b) Norm of gradient
Figure 1: The comparison for the case of μ 10-3
10
100
SVRG SPIDER AccSPIDER
SVRG SPIDER
will
AccSPIDER
10 2
1
1
10-4
2
4
0
4
#SFO
x
x
#SFO
x10
(a) Distance to saddle point
(b) Norm of gradient
Figure The comparison for the case of μ = 10-9
Acknowledgements
This work is supported by National Natural Science Foundation of China (No. 62206058) and
Shanghai Sailing Program (22YF1402900).
References
[1] Ahmet Alacaoglu and Yura Malitsky. Stochastic variance reduction for variational inequality methods. arXiv preprint arXiv:2102.08352, 2021.
[2] Zeyuan Allen-Zhu. Katyusha x: Practical momentum method for stochastic sum-of-nonconvex optimization. arXiv preprint arXiv:1802.03866 2018.
[3] Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In ICML, 2016.
[4] Zeyuan Allen-Zhu and Yang Yuan. Improved svrg for non-strongly-conve or sum-of-non- convex objectives. In ICML, 2016.
[5] Qi Cai, Mingyi Hong, Yongxin Chen, and Zhaoran Wang. On the global convergence of imitation learning: 2019.
for linear quadratic regulator. arXiv preprint arXiv: 191.v2190..03674,
[6] Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In NewrIPS, 2019.

---

[7] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. In NeurIPS, 2019.
[8] Aaron Defazio, Francis Bach, and Simon Lacoste-Julies SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In NIPS, 2014.
[9] Thinh T. Doan. Convergence rates of swo-time-scale gradient descent-ascent dynamics for solving nonconvex min-max problems. arXiv preprint arXiv:2112.09579, 2021.
[10] Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In ICML, 2017.
[11]
John Duchi and Hongseok Namkoong. Variance- based regularization with convex objectives. The Journal of Machine Learning Research, 20(1)) 2504, 2019.
[12] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In NeurIPS, 2018.
[13] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Communication-efficceen distributed stochastic auc maximization with deep neural networks. In ICML. 2020.
[14] Zhishuai Guo, Zhuoning Yuan, Yan Yan, and Tianbao Yang. Fast objective & duality gap con- vergence for nonconnex--troogly--omme min-max problems. arXiv preprint 20t.:220006.8889, 2020.
[15] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. arXiv preprint arXiv:2103.08288) 2021.
[16] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth- order and first- order momentum methods from mini minimax optimization. Journal of Machine Learning Research, 23(36) 1000 2022.
[17] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, 2013.
[18] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-lojasiewwe condition. In Joint European Conference Machine Learning and Knowledge Discovery in Databases. Springer, 2016.
[19] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In ICML, 2021.
[20] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion. In NIPS, 2015.
[21] Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML, 2020.
[22] Tianyi Lin, Chi Jin, and Michael I. Jordan. Near-optimal algorithms for minimax optimization. In COLT, 2020.
[23] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
[24] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. arXiv preprint arXiv: 10831, 2019.
[25] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-coom
minimax problems. In NeurIPS, 2020.
[26] Luo Luo, Guangzeng Xie, Tong Zhang, and Zhihua Zhang. Near optimal stochastic al- gorithms for finite-sum unbalanced convex- -onnave minimax optimization. arXiv preprint 21X1v.2106.0176,, 2021.
10

---

[27]
Julien Mairal. Incremental coniiaattiommmiiiiziiioon optimization with application to large-
scale machine learning. SIAM Journal on Optimization, 25(2):829-855 -55, 2015.
[28] Nicolai Meinshausen. Causality from a distributional robustness point view. In DSW. IEEE, 2018.
[29] John Nash. Two-person cooperative games. Econometrica: Journal of the Econometric Society, pages 128-140, 1953.
[30] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[31] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In ICML, 2017.
[32] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang. Jason D. Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. In NeurlPS, 2019.
[33] Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle- point problems. In NIPS, 2016.
[34] Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoc Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110):1 2020.
[35] Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal Vychisli- tel noi Matematiki Matematicheskoi Fiziki, 3(4):643-653, 1963.
[36] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimiza- tion: Provable algorithms and applications in machine learning. arXiv preprint:1110.0206 2018.
[37] Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In ICML, 2016.
[38] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1):83-112, 2017.
[39] Shai Shalev-Shwarte and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(2), 2013.
[40] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): 131- 2018
[41] Vladislav Tominin, Yaroslav Tominin, Ekaterina Borodich, Dmitry Kovalev, Alexander Gas- nikov, and Pavel Dvurechensky. On accelerated methods for saddle-point problems with composite structure. arXiv preprint arXiv:2103.09344 2021.
[42] Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, and Mingyi Hong. Multi-agent reinforcement learning via double averaging primal-dual optimization. In NeurIPS, 2018.
[43] Zhe Wang, Kaiyi Ji. Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In NeurlPS, 2019.
[44] Wenhan Xian, Feihu Huang, Yanfu Zhang, and Heng Huang. A faster decentralized algorithm for nonconvex minimax problems. In NeurlPS, 2021.
[45] Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-noncoocant minimax problems. In NewrIPS, 2020.
[46] Junchi Yang, Siqi Zhang, Negar Kiyavash, and Niao He. A catalyst framework for minimax optimization. In NeurIPS, 2020.
[47] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In AISTATS, 2022.
11

---

[48] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online AUC maximization. In NIPS, 2016.
[49] Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number independent access of full gradients. In NIPS, 2013.
[50] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In NeurlPS, 2018.
[51] Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng. Faster first-order methods for stochastic non- convex optimization on riemannian manifolds. In AISTATS, 2019.
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? [Yes] See Section g
(c) Did you discuss any potential negative societal impacts of your work? [No] The purpose of this work is for to provide better understanding of GDA on class of nonconvex-nonee nonconcave minimax optimization.
(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 of all theoretical results? [Yes] See Section 3
(b) Did you include complete proof's of all theoretical results? [Yes] See Appendix for details.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include the codes In the supplemental materials.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 7
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No] We wants to compare the training dynamic, and different trials may cause different numerical results, which not be observed clearly in one graph.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No] The experiments is certainly simple and easy to run under CPUs.
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 cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're usin//curating? [No] These datasets are common.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] These datasets common.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "nNOaK0o1L3", "reviewer": "Reviewer_NEh5", "summary": "The paper is devoted to non-convex stochastic (finite sum) saddle point problems under PL assumption (two-side and one-side). The paper proposes a new method based on the famous variance reduction SPIDER. A modification with acceleration via Catalyst is also given.", "questions": "1) Did the authors try to consider loopless variants of the SVRG (L - SVRG) and SPIDER (PAGE) methods? For minimization problems the proofs for them are simpler in my opinion. Perhaps it would be the same here. If such variants have not been considered, it could be explored as future works.\n\n2) For example, SVRG methods have a direct accelerated version - Katyusha or L-Katyusha. Did the authors try to design methods with direct acceleration, without envelopes? If not, it could be explored as future works.", "limitations": "No limitations and potential negative societal impact", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1) Solving non-convex stochastic problems is an important task. The paper is relevant and interesting.\n\n2) It is easy for me to follow the paper. The literary review is done on a quite good level.\n\n3) The paper improves on existing bounds in the literature. \n\n4) In my opinion, the way to get the result is not trivial. But perhaps if one use L-SVRG or PAGE (loopless modifications of SVRG and PAGE) as a base it would be easier.\n\n**Weaknesses:**\n\n1) Literature review: if we are talking about SPIDER it has a lot of analogues in the literature -- see Table 1 from\n\nLi, Z., Bao, H., Zhang, X. Richtarik, P. PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.\n\nI definitely ask for a citation of the next work, because it seems that SPIDER is just a version of SARAH: \n\nNguyen, L. M., Liu, J., Scheinberg, K., and Takac, M. SARAH: A novel method for machine learning problems using stochastic recursive gradient.\n\n2) The result of the paper is expected if one knows what estimates look like for minimization problems under PL conditions: \nGD --- SVRG --- SPIDER: $\\mathcal{O}\\left( n \\cdot L/\\mu\\right)$ --- $\\mathcal{O}\\left( n^{2/3} \\cdot L/\\mu\\right)$ --- $\\mathcal{O}\\left( \\sqrt{n} \\cdot L/\\mu\\right)$.\nFor saddle point problems we observe the same dependencies on $n$ -- GD and SVRG the results were already known.\n\n3) The PL condition does not seem to be particularly popular and widely researched (for saddle point problems), and its applicability to practical problems is slightly blurred (despite the fact that the authors give references to some works)\n\n**Verdict before discussions:**\n\nThe work makes an improvement on the available results for an important task but in not the most popular assumptions. The results are expected and understandable. I wouldn't be opposed to this work being presented at the conference, but I wouldn't be upset if it not. Borderline accept", "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": "WO4g3hPQ3Nv", "reviewer": "Reviewer_N7QK", "summary": "The paper studies minimax optimization under Polyak-Łojasiewicz (PL) conditions. Given a function $f(x, y) = \\frac{1}{n}\\sum_{i=1}^{n}f_i(x, y)$ that is $\\mu_x$-PL in $x$ and $\\mu_y$-PL in $y$, assuming that each $f_i$ is $L$-smooth, the algorithm provably finds an $\\epsilon$-approximate solution for $\\min_x\\max_y f(x, y)$ using $O((n + \\sqrt{n}\\kappa_x\\kappa^2_y)\\log(1/\\epsilon))$ queries to a stochastic first-order oracle, where $\\kappa_x = L/\\mu_x$ and $\\kappa_y = L/\\mu_y$ are the condition numbers. Prior bounds have a larger factor of $n^{2/3}$ instead of $\\sqrt{n}$ in front of the condition number. The authors also present an accelerated algorithm, which achieves a better query complexity of $\\tilde O(\\kappa_x\\kappa_y\\sqrt{n}\\log^2(1/\\epsilon))$ in the $\\kappa_x \\ge \\sqrt{n}$ case.\n\nThe first algorithm, termed \"SPIDER-GDA\", is a variance-reduced version of alternating gradient descent ascent. The second algorithm proceeds by using SPIDER-GDA as a basic solver, and applying Catalyst acceleration to it.\n\nIn addition, the authors discuss an extension of the techniques to the setting where the function only satisfies the PL condition in $y$ but not $x$. Experiments are performed on synthetic data (quadratic functions), and the proposed algorithms are shown to converge faster than a baseline of Yang et al. (2020).", "questions": "I have a few clarifying questions regarding the novelty and significance of the work, and I might update the rating based on the answer:\n\n1. What are the main differences between SPIDER-GDA and the SVRG-AGDA algorithm of Yang et al. (2020)? (E.g., is it about using a larger minibatch of size $B \\approx \\sqrt{n}$ instead of $B = 1$?)\n\n2. Are these changes novel? E.g., are they applied in other settings of stochastic first-order optimization? And if so, does this work involve a novel/different analysis?\n\n3. To what extent are these changes necessary? E.g., is there evidence proving/suggesting that the $n^{2/3}$ dependence is unavoidable for SVRG-AGDA?", "limitations": "The main limitation is that the optimality of the proposed algorithms remains unclear. This is stated by the authors in Section 8.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well written. I think the authors did a good job in motivating the problem, rigorously defining the problem setting, and presenting the results. Compared to the prior work of Yang et al. (2020), the query complexity of the new algorithms improves by a polynomial factor in theory, and is also shown to outperforming empirically. Overall, this is a solid and well-presented work.\n\nWeaknesses: On the negative side, the current paper is lacking in novelty and significance. Considering that: (1) the techniques used in the paper (variance reduction, alternating gradient descent ascent, Catalyst acceleration) are all well-known in the optimization literature; and (2) the query complexity obtained could still be far from optimal, I doubt whether the present work meets the bar.\n\nThe presentation could be further improved if the authors give more intuition/explanation behind the improvement from $n^{2/3}$ to $\\sqrt{n}$; see questions below.\n\nIn addition, there are a couple of possible math typos:\n- Page 1, Line 3: The optimization problem differs from (1) by a factor of $n$.\n- Page 1, Line 10: Should $\\log(1/\\epsilon)$ be $\\log^2(1/\\epsilon)$ instead?\n- Page 1, Line 10: It might be better to clarify what $\\tilde O$ notation hides: polylog factors in $\\kappa_x$, $\\kappa_y$ but not $1/\\epsilon$?\n- Page 4, Line 91: Extra $L^2$ in parentheses?\n- Page 7, Table 3: Missing \")\" for SPIDER-GDA, first case", "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": "GjngVzrmXCa", "reviewer": "Reviewer_dMKi", "summary": "This paper studies finite-sum minimax optimization problems under PL conditions. The SPIDER-GDA algorithm, which uses simultaneous Gradient Descent-Ascent as the backbone and SPIDER as its variance reduced gradient estimator, is proposed and analyzed, enjoying better guarantees than SVRG-based approaches. Catalyst acceleration and the one-sided PL extensions are also discussed.", "questions": "Is it possible to provide gradient complexity lower bounds for this setting?", "limitations": "Limitations of this work are adequately discussed.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The complexity guarantees improve the current state-of-the-art for both the two-sided and one-sided settings.\n- The algorithms are fairly easy to understand and implement. The two-sided and one-sided settings are handled with the same algorithms with different hyper-parameters.\n\nWeaknesses:\n- The setting for this paper is somewhat niche, considering the finite-sum case with PL conditions and no convexity. What are some good examples or justifications for this setting? (The numerical experiments in Sec. 7, for instance, are quadratic and convex-concave).", "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": "G4gNn4ofCoP", "reviewer": "Reviewer_vsqY", "summary": "This work studies a new algorithm for finite sum smooth minimax optimization which has guarantees for a certain class of nonconvex-nonconcave minimax problems, which is formalized by a Polyak-Lojasiewicz (PL) condition. This problem has been previously studied by [42], and the PL condition provides a broad class of optimization problems which are of deep interest to machine learning, including, e.g., deep AUC maximization. The new algorithm shows that a technique related to SPIDER, which reduces the variance of SGD by estimating differences in the SGD iterates, can improve the stochastic first order (SFO) oracle complexity for this problem by improving the previously known bound of $O((n + n^{2/3} \\kappa_x \\kappa_y^2)\\log\\frac1\\epsilon)$ to $O((n + n^{1/2} \\kappa_x \\kappa_y^2)\\log\\frac1\\epsilon)$. Further improvements are provided for ill-conditioned instances.", "questions": "Minor comments\n\n- Defintion 3.1: should say $y\\in\\mathbb R^{d_y}$\n- Assumption 3.1: is there an extra $L^2$ in the parentheses?\n- Line 427 (supplementary): typo “us a question thta whether”", "limitations": "This is largely a theoretical paper and has no potential for negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The obvious strength of this work is that it provides a direct improvement in the SFO oracle complexity for the smooth minimax optimization problem under PL conditions by improving previous results by poly(n) factors, which is significant. Because I do not work in the optimization literature, I could not tell what technical innovations were necessary to make this result possible, and it was not clear to me from the discussion of the paper either. In particular, the only conceptual message I got from the work was that “SPIDER-type algorithms can improve algorithms for PL minimax optimization beyond the previous SVRG-based algorithm.” This is certainly an important message, but I would appreciate more discussion and intuition on what this result implies in the broader theory of minimax optimization algorithms. For example, the authors point out previous works that apply SPIDER-type algorithms to minimax optimization, under different assumptions on the function being optimized, and mention that the technical details are different since earlier works converge sublinearly while the current work converges linearly; however, it is not clear to me how significant this difference is, since such differences already appear in basic analyses of vanilla gradient descent for convex vs strongly convex functions. In particular, SREDA in Luo et al. [23] achieve rates of the form $O(n\\log(\\kappa/\\epsilon) + n^{1/2}\\kappa^2 / \\epsilon^2)$, which seems very similar to the guarantee of the current paper, and a further discussion of the differences would be appreciated. \n\nPros\n\n- Direct improvements over previous work on an important problem in minimax optimization theory.\n- Extremely detailed and clean presentation of proofs in the supplementary material.\n\nCons\n\n- Lack of discussion which places the innovations in this work in the context of other work in minimax optimization.", "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