Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
Authors: Haochuan Li
Yi Tian
Jingzhao Zhang
Ali Jadbabaie
Venue: NeurIPS 2021 Poster (2021)
Keywords: min-max optimization
lower bound
oracle complexity

Abstract: We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2}\right)$ for deterministic oracles, where $\epsilon$ defines the level of approximate stationarity and $\kappa$ is the condition number. Our lower bound matches the best existing upper bound in the $\epsilon$ and $\kappa$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2} + \kappa^{1/3}\epsilon^{-4}\right)$. It suggests that there is a gap between the best existing upper bound $\mathcal{O}(\kappa^3 \epsilon^{-4})$ and our lower bound in the condition number dependence. 

Complexity Lower Bounds for Nonconvex-Stroogyy-Conee Min-Max Optimization
Haochuan Li Department of EECS MIT Cambridge, MA 02139 haochuan@mit edu
Yi Tian Department of EECS MIT Cambridge, MA 02139 yitian@mit, edu
Jingzhao Zhang Department of EECS MIT Cambridge, MA 02139 jzhzhang@mit.. edu
Ali Jadbabaie Department of CEE MIT Cambridge, MA 02139 jadbabaióm @iitttimiii...mm edu
Abstract
We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of f (Vkc-?) for deterministic oracles, where e defines the level of approximate stationarity and x is the condition number. Our lower bound matches the best existing upper bound in the and dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of D (VKE"" - + x1/3 It suggests that there is a gap between the best existing upper bound ( c and our lower bound the condition number dependence.
Introduction
In this paper, we study the oracle complexity lower bound of the following min-max optimization problem:
min max f(x; y);
(1)
#EX wE)
where X' C Rh and ) C Rhth are nonempty closed convex sets. Such problem arises in wide
range of applications. c.g., two-player zero-sum games (38), Generative Adversarial Networks [17]
robust optimization [4) including defending adversarial attacks [18] 29).
The research in min-max problems (T) has a long history. If f linear both æ and y, the problem is known as bilinear min-max optimization, for which von Neumann's 's min-max theorem (38] guarantees the existence of a saddle point, a point (x= v²) that satisfies strong duality (i.e. min min-max equals max- max-min). Later, Sion 44] generalized the statement to convex-concave functions under certain regularity conditions, which led to the theory of KKT conditions. Aside from studying the existence of strong duality, Nemirovski K3). Nesterov (36] proposed algorithms that can find approximate saddle points for to be worst-case optimal even for min-max problems with bilinear cross-term
objectives with an ((1/e) convergence rate. The rate was proven
Going beyond the assumption convex-concavity poses big challenge. In general nonconvex- nonconcave min-max optimization problems, saddle-point may not exist [22]. Defining notion of min-max points that simultaneously nontrivial and tractable is still an open question. one uses the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

standard definition of saddle points as in the strong duality problems, then determining its existence known be NP-hard [9) and finding an approximate local saddle point is PPAD-complet (9. Alternatively, a relaxed definition of min-max point known as Stackelberg equilibrium is guaranteed to exist 22] yet only local asymptotic convergence is known 22 47
Due to the lack of a well coll-formulated suboptimality measure for general suuconvex-nonconcan problems, recent research has considered problems with special structures. For example, Lin et al. 126 27 studied nonconvex-concave problems, Yang et al. [50] studied problems satisfying the Dolyak-Lojasiewice inequality, Diakonikolas et al. studied problems with weak Minty variational inequality solutions, Mangoubi and Vishnoi 33 considered an algorithm specific equilibrium.
Our work focuses on the analysis of gradient oracle complexity in the min-max setting. In the standard convex conncvee setup, Lin et al. [27] designed a set of algorithms that achieve near-optimal gradient complexity for all the three variants of convex-concave min-max optimization. However, in the nonconvex-concav setting, it is unclear whether their algorithm is optimal given that no matching lower bound exists. In this work, our main contribution is as follows:
We construct an explicit example on which no first-order zero-respecting algorithm can achieve less than Q2 (ie -2) oracle complexity for smooth nonconvex-strongly-coon problems, matching the Ö( -) complexity in [27].
We further extend our results to the stochastic(-oracle) setting, achieving the complexity lower bound Q2 Vir -2 + +x////554 Compared against the results in (26), our result suggests that the dependency on the condition number may not be optimal.
1.1 Related work
Upper bounds. Since standard gradient descent-ascent diverges for even the simplest case of bilinear zero-sum games, researchers proposed different variations achieve convergence in the convex-coneee setting, with possibly additional structures. One of the variations is known as extra- gradient method [24 46
49 which takes two gradient steps per iteration. Another line studies the optimistic gradient method [43
33
7
31 20) Mokhtari et al. [32] proposed unified analysis through the lens of proximal update. Some works 27 focused on accelerating the known rates in terms of the conditional number dependence. Golowich et al. [16] studied last iterate convergence. Lee et al. (25). Daskalakis et al. [TO], Wei et al. [48] studied two-player zero-sum stochastic games.
g 1.5
Convergence under the nonconvex-concave setup is less studied. Rafique et al. 42 studied proximal version of gradient methods. Lin et al. [26] studied gradient descent ascent with different time scales. Thekumparampil et al. [45 proposed an implicit algorithm for the nonconvex
setting. Many
other works also studied different variations of convergence 39
23 28
Lower bounds. Our work follows the complexity framework introduced by Nemirovski in the 1980s. The most classical lower bounds are due to Nemirovski and Nesterov, and are discussed in their textbooks (35.7 Recently, much progress was made 13
3 by extending the original analysis to the nonconvex setting. Our work builds upon these results. Another line of works studies lower bounds for quadratic problems in min-max setting and utilizes different framework sometimes known Stationary Canonical Linear Iterative (SCLI) 22 41 51 21 It exploits the closed-form updates for linear dynamics and studies convergence properties via the transition matrices.
Concurrently, Zhang et al. (52] and Han et al. [19 provided lower complexity bounds similar to ours in the deterministic other but different from ours. Their constructions can be roughly viewed as a simple addition of the quadratic instance in 41 and nonconvex component as in 66. Informally speaking, their v factor However, our construction is mainly inspired by the chain-like instance
setting. Their constructions are similar each
comes from the rate in in [5]. To obtain the v factor, we insert quadratic sub-chains into it to increase its length by a factor of Vk. One possible advantage of our construction is that the minimization and maximization variables are weakly coupled so that we may have more freedom to modify the component functions to extend our results to other settings such as the nonconvex conccvee function class. Zhang et al. (52) and Han et al. [19] also provided novel analyses with extensions to the upper and lower bounds the finite-sum setting, whereas we further extend our results to the stochastic setting.

---

Notation. We use bold lower-case letters to denote vectors and use 2; to denote the i-th coordinate of vector Let supp(æ)) == {i 2; # 0} denote the support of Let ||>||| and || loo denote its l2 and &o norm respectively. For matrix A, we use A., to denote its (i.j)-th entry and A its transpose. We use ||||| to denote its spectral norm and (ct(AA its determinant. We use calligraphic upper-case letters to denote sets, as X' and V. For a nonempty closed convex set E R let Px denote the Fuclidean projection onto X. We also minimization and maximization variables of function. For example, when we write f(x, 2; y). the 2 Preliminaries
Before introducing main results, describe the problem setup and algorithm complexity in this section. First, we introduce the notation. Next, we define the function class and algorithm class. Finally, we provide the formal definition of optimality measure and gradient complexity.
semi-comma besides commas split
means and the variables to minimize and is the variable maximize. Finally, standard (-) and !?() notation, with (-) and Q(-) further hiding log factors.
2.1 Function class
Our analysis focuses on the class of smooth nonconvex-stronglyyoomeee functions defined below. Definition 1. Given L 2 > 0 and A O, we use F(L, μ., A) to denote the set of all functions f: X y R. for some nonempty closed convex sets X C Imm and y IR" where m, n N, which satisfies the following assumptions:
1. f is L-smooth, that is, for every 21, X and yı V2 V
[V - f ya)ll2 L (1 y1) - (x22, v2)l12
2. For any fixed x E Ex f is y-strongly concave in y, that is, for any yı y/ E E
f(x; y1) S fx:; y2) Vuf(z; 82) (y1 y2) 2 1 3211:
3. fm (0) mingex fm (x) S A, where fm(x) == maxvey f(x; y):
For any fixed y E J potentially nonconvex in æ. Note that F(L,, nt, A) includes functions with domain on m 18." for all m.n E N, following the framework of dimension- convergence guarantees (34 37). In Section we will construct a hard instance with domain dimensions m, both growing inversely in the required accuracy e.
2.2 Algorithm class
In this section, we describe the algorithms of interest for the min min-max problems with the function class defined above. In particular, restrict analysis to first-order algorithms that optimize objectives using first-order oracles defined below.
Definition 2 (Deterministic first-order oracle). The deterministic first-order oracle of a differentiable function f X + R a mapping O x + (f(x), f for x E X.
Definition 3 (Stochastic first-order oracle). stochastic first-order oracle with bounded variance o² of differentiable function f X
a mapping O x + (f(x). gx) E)) for x E X, where & is a random variable satisfying Elg( }) fz) and [g { f=))) <²²
We say O is first-order oracle if it is a deterministic or stochastic first-order oracle.
Furthermore, consider first-order algorithms satisfying the zero-respecting assumption. Formally, we define first-order algorithms as follows.
Definition 4 (First-order algorithm). A first-order (zero-respecting) algorithm is one that for any function f X + R and its associated first-order oracle O, : (f(x), g), the (t + 1)-th iterate rl+1 satisfies
x 1+1 E Px(() supp(v) c U (supp(x*) U supp(g')) )
05i5t

---

Definition extendss the standard zero-respecting algorithms [5 to the constrained setting. It covers most existing first-order methods used in the literature including (projected) stochastic gradient descent, adaptive methods, and more importantly, the algorithms used in 26 27 which achieve the upper bounds for -esoonvee-strogly--ooo
min-max optimization the deterministic and stochastic settings, respectively. There is standard reduction from lower bound for vero-respecting algorithms to that for arbitrary deterministic algorithms with deterministic or even stochastic first- We defer this extension to future work.
order oracles [3 3].
2.3 Optimality via approximate stationarity
We measure the progress of solving the nonconvex-stroonly-coom problem via the gradient norm of the maximized function with respect to the minimization variable Following [14. define the notion of c-stationary points in presence of constraints as follows.
Definition 5. Let X be a nonempty closed convex set. A point a E X is said to be an c-stationary point of an L-smooth function f > IR
L | [ (1/L)Vf(()) x112 S.
Note that the algorithm studied in [26] also assumes bounded domain and used the same notion of stationarity. This definition of stationary points reduces |/ (Vx))) S c when Rd for some E N. For any f F(L, A), Definition applies to fm as it is Lm-smooth, where
Lm S by 226 Lemma 4.3].
Our goal of solving the senccnvee-strongly-eoo e-stationary point of fm- We show that deterministic first-order algorithm achieve less than O D(VRE" 2) gradient complexity for smooth minconve--ttrongly-oome
min-max optimization problem is to find an
problems, matching the (vK ?) complexity in [27] We further extend our result to the stochastic setting, achieving complexity lower bound 52( KE x3/3E-4)
3 Main results
In this section, present main results on the minimum number of gradient oracle calls required to find an e-stationary point. The results for deterministic and stochastic settings are presented the following two subsections respectively.
3.1 Lower bound first-order oracle complexity in the deterministic setting
Nonconvex--trongly-ccocem min-max optimization subsumes nonconvex optimization, the lower bound ((LA/e (e2) in nonconvex optimization (5) also holds for nonconvex-strongghe noncomnex--trrnggyyyoncee min-max optimization. However, compared with the Ö(L R upper bound (27]. a v factor is missing. Our main result below fills this gap, showing that the known rate by (26] is optimal up to log factors.
Theorem 1. For any p. A, O such that k L/u μ > 1. there exists function instance RT R" E F(L, u, A) for some m, IN with its deterministic first-order oracle such that for any first-order algorithm, we have [m (x²)lla > where fm(()) == mmx, f(x, y), whenever
L. K
2
where co is numerical constant.
Similar to the lower bound in [5), our lower bound applies to dimension free optimization in nature. That is, for a given e, we construct a hard instance with dimension O(1/e²), which can very large if é is small. The discussion on the proof is deferred until Section
3.2 Lower bound in the stochastic setting
In the stochastic setting, Arjevani et al. 3 provided lower bound of Ω (LAo?/e) for smooth nonconvex optimization which is special case of nonconvex-stronel. ettocngly-concave Our analysis improves this bound by factor of ///3 in Theorem
concave min-max optimization.

---

Theorem 2. For any p. L, A,E,0'> O such that x. == L/p 2 1, there exists function instance
f: X x - R in F(L, p. A) and a stochastic first-order oracle for with variance o² such that for any first-ordrr algorithm, we have IR. [Tmm |Px a. (1/T.ng [m) V [m()) x² x'112] where (m(()) = mmaxy (x, y), whenever
VR
x2/3302 et
S Co
where Lu the smoothness parameter of Jm and en numerical constant.
Lin et al. [26] provided an upper bound of O (4) Therefore, there is gap between our lower bound and their upper bound terms of the dependency on K.
In summary, our proposed lower bounds improve the known ones by multiplicative dependence on the condition number. Before proceeding discuss the concrete techniques, we first summarize the general framework for establishing lower bounds in the next section.
Framework for proving lower bound
In this section, we provide an outline for the proof of the lower bound in 37 and [5], which lay the foundation for our construction of the hard instance. Both works utilize the notion of zero-chains [5], which instantiates class of hard functions for optimization. We first define a zero-chain and then discuss how it is used to establish complexity lower bounds.
Definition (Zero-chain). We say a function f X + IR, where C gd, (first-order) (frr cero- for every 1 S i S d, supp(æ) = (i: [i:x;#0) C ( - 13 = supp(VS(()) C (1......)
supp(æ) for all æ E Rd i.c., projecting onto A' does not change its support. For example, this requirement holds when X' is a hypercube or the whole space Rd If we run a first-order algorithm zero-chain initialized at x assume to hold without loss of generality) with deterministic first-order oracle, then at each iteration, at most one new coordinate of æ becomes nonzero ("discovered"). Therefore, supp(æ') C (l.....4) (). Then we obtain lower complexity bound of T supposing can show good solution exists only if least coordinates are discovered.
Suppose the domain C. I2d satisfies supp(Px
(which we
Therefore, the key to proving a lower bound of first-order algorithms with deterministic oracle is to find a function f such that:
1. it is zero-chain that belongs to the function class we are interested in; and that
2. we cannot obtain an c-optimal solution if the /-th coordinate of ae zero for every & 2 T.
This is actually general strategy for proving lower bounds of first-order methods, used in the lower bound construction both by Carmon al. (5) for smooth nonconvex optimization and by us here for nonconvex-sie wawpanveee-stoonly--ooeee
min-max optimization.
In the stochastic setting, we utilize the generalized notion known as the probability-p zero-chain B to prove lower bound.
Definition (Probability-p zero-chain). function f - with stochastic firsttsti oracle O: (f(x), (xx {)) is probability-p zero-chain if
{
IP (suup((g(x E)) & f1...... 1p) IP (ssupp(g(x E)) (1.....1)
supp(æ) C (1,....i-1)
For probability-p zero-chain, at each iteration, most p if (upp(pxx())) = supp(æ) for all æ. Therefore, it takes at least 1/p steps in expectation to discover a new coordinate. Formally, the following lemma states that it takes O(T/p) iterations to reach the end of probability-p zero-chain with length T.
coordinate is discovered with probability at
Lemma (33 Lemma I]). Let f + R, where X g satisfying supp(Pxxx)) supp(æ) for all æ E Rº" be a probability-p zero-chain with a stochastic first-order oracle. For any first-order algorithm, have with probability at least - 6, x4 for all t Tllog(1/4)
2p
5

---

Therefore, the gradient complexity is enlarged by factor of 1/p compared with the deterministic setting. To obtain lower bound the stochastic setting, we first find zero-chain f satisfying the two requirements in the general strategy we presented above. Then we construct stochastic first- order oracle which discovers the next coordinate with probability p so that we obtain a probability-p zero-chain, Note that we can not choose an arbitrarily small since we need to ensure the variance of the stochastic oracle is bounded.
For the ease of exposition of our construction, we now briefly review the lower bound construction for smooth strongly- convvxx minimization by Nesterov [37 and that for smooth nonconvex optimization by Carmon et al. [S]. As we shall see in the next section, the hard functions in these two cases are the building blocks of our construction.
4.1 Smooth sarongllyconver minimization
Nesterov
37 constructed the following hard instance for smooth, strongly-convex functiion:
(0) μ(x= 11 (11 1)2 (o 1++1)²
|
2
Equivalently, (x) - (xt A
2x1 + 1)
#/2 a l| for the tri-diagonal matrix A given
by
-1 2 -1 -1 2
A =
is straightforward to verify that A is positive semi-definite and ||41 S 4. Hence, f is L-smooth and p-strongly-convex for L juk. Importantly, if supp(æ) (I....,, 1}, we can verify:
supp (V/* = supp (A U supp (z) (I....,i),
where the fact that supp (A*x) [1, ( because A is tri-diagonal matrix. Hence, by Definition 6, f a zero-chain. Based on the general strategy above, suffices to lower bound (x) - (x when fewer than T coordinates
non-zero. Note that the minimizer x* of f is VR+I" Then with fewer than T gradient oracles, for every 2 T, the
given by x = r where (-th coordinate of x is still zero. Therefore,
/K-1
36
n (=)
| x: 11
(xf)
1
Hence, to find solution satisfying (x( (xx) S e, need gradient complexity T 2 ((
4.2 Smooth nonconvex minimization
Another key component in our proof is lower bound the complexity of nonconvex functions. Part of our construction is derived from Carmon et al. S who constructed the following unscaled function
fic R R:
f (x) (1()))()))))) Σ
(4)
where the component functions
S 1/2
and (xx) = Ve f
212 dt.
V
exp (1 22-11
T > 1/2
The above function also has the zero-chain property defined in Following the general strategy discussed in the previous subsection, by appropriately rescaling Th so that it meets the requirement of the function class of interest, Carmon al. [5] derived lower bound of Tac == (1/e²) gradient
oracles. More details can be found in Appendix A

---

(3)
(b)
14
(d)
5=10
y0
3
82
2)
0
X2 0
%
Xr
Figure 1: Chains (a. b, d) correspond to f f frcss Jm. respectively. Arrows in different colors represent different types of connections between two variables. For example, blue arrow from u to corresponds to a term with (u u)² in the function. A red arrow corresponds to ((-u)((-v) (v)) Green and bold blue arrows are quadratic connections that need to be carefully designed. The effective length of bold blue arrow is n and that of all other arrows is 1.
Our construction
The hard examples discussed in the previous section show that one can easily construct an additive lower bound by making the objective the sum of functions f and f However, if we would like to improve the lower bound by a multiplicative factor in the condition number, it is far from obvious how one should compose f with fo We describe our approach the subsections below.
5.1 Construction of the hard instance in the deterministic setting
Before discussing the details of our construction to prove Theorem we first highlight the main difficulty and our approach at high level to provide insight and intuition. First, we need to pinpoint the main difficulty.
The main difficulty. Given the aforementioned lower bound strategy, we need to find zero-chain fne-se F(L, μl, A) as our hard instance. A natural way construct fie-se is combine the ideas from the hard instances in [37 and [5] The main challenge is how to find good way of combination such that the two components do not interfere with each other's essential properties and that their
strengths can be exploited multiplicatively to contribute to the lower bound.
The key idea. The novel combination structure propose illustrated in Figure | The body of the chain is like foe 4 which contains the minimization variables æ, z. Then we insert T fee-style 2 sub-chains with length n, which contain the maximization variable y. into the main chain in the way shown in Figure [fc.. Figure d() shows the function fme-s(()) (-) == max, (:;z)) obtained by maximizing y. Note that the effective length of chain (d) is O(nl)) O (KTT), for the largest allowed choice of n = O(VR). Therefore, supposing we can show that fire shares similar
properties to fine used in [5 we obtain a lower bound of Ωt (VrTne) = Ω (Vk/e²).
However, the requirement that fm 5nc-se behaves similarly to f poses another challenge as it basically means that the red arrows in chain (d) dominate the bold blue ones, although their numbers roughly equal. To overcome this challenge, we carefully design the green arrows directly and the bold blue arrows indirectly. We also need to restrict such that O(Vk).
Construction of the hard instance. given by
The formal expression of fuc-se (R² x RT-1) (1)
Fnc-sc (2, x;
(xx
(1)))((()))
+
[ (V(2))00 (1-2))((-2
1 (2,)
2=2
T
T-1
+
h(2,, Zit1: (())))))))))))))))))))))))))))
Σ
2 + c22211) (5)
7

---

where z, are the minimization variables and y (g()) ..... , ......((--))) D(T11), where each g E R", is the maximization variable. The last term of (5) indirectly affects the bold blue arrows in Figure dd). where e and are some parameters (not necessarily nonnegative) we choose later to obtain much simpler expression to analyze. The function h (IR x IR) TR + defined as
n-1
CC V
1 2y1
1(2, 2;
Σ
Ut 16+1)²
113112
2 zyn
2
2n
1=1
2-
= 2
n nn + + + V
b b..
(6)
where C
0 is large enough numerical constant specified later and bz,= z61
Here the term / b =,= characterizes the green arrows in Figure where the factor ensures
hmm (I,, 2) yaRy h(r, 2; has ((1) dependence as shown in Lemma The matrix
E IRax is defined as
1 -1
1 2 -1
=
-1 1
(7)
2
-1 1
which is the finite version of (3) in (37 's instance except that its (1, 1)-th and (n, n)-th entries are 1. This change is necessary in our example. Note that for fixed scalar variables x and z, h(x, 2; is n² sstrongly-concav Also, fne-se is [1(1--smoohh (Lemma 9b. Therefore, I(n?) implying
should choose O()R). We compute
C
(1
hm (x. max 2x,,;;;))))) 2;
b
+
b 2z.-.
(8)
yeR"
2n
n2
The following lemma shows that hm actually has much simpler expression. Lemma 4, Suppose n 2 10, we have
Im (xx, =) = - 0222
1
a1 -1.2
+
8
where 01, U2 > 0 are "almost" numerical constants. That is to say, although a1, 02 depends on n,, we have 0 < di 01 < and d2 S 02 S J2 and di, d2, J1, J2 numerical constants.
Choosing Ci C( ai) (1)/22 02 = C(a2 - a1)/8 and C 12/02, 02, we obtain Fae-so fi
x 2)
max gERn(T-1)
juc-se (x,2;1) 2;
T Σ (V(22) ((-)))((=1))))
T-1 + 6
= --V(1)((m)) +
(Z,))
Σ
Zi+1
1=1
We show in the appendix that fnesse shares similar properties to fuee Then prove Theorem ] by appropriately rescaling fo in the same way as done in [5]. The detailed proof is deferred in Appendix
5.2 Construction of the hard instance in the stochastic setting
We start this section by discussing why the techniques in do directly apply our construction in the deterministic setting. The following lemma from 3 shows how to construct probability-p zero-chain by constructing stochastic first-order oracle over a given zero-chain.
Lemma 5 (B Lemma 31). Let f X + R be zero-chain on X C RT. For E X. let
(x) == inf [T] I 0} be the next coordinate to discover. For (0, 1), define
(V.(()) i() V,f(x)
(x E)
otherwise,
8

---

where Ç ~ Bernoullipp) Suppose [ff(=)l & for all a E X. Then O a (f g {)) is a stochastic first-order oracle with bounded variance o² - G² - -p)pp. Also, f equipped with O is a probability-p zero-chain.
Therefore, a tempting way to obtain our hard instance in the stochastic setting is to construct probability-p zero-chain as in Lemma didrectly over fne-se However, as suggested by Lemma to ensure the variance of the oracle is bounded, we require / (x. f) I G for some bounded
G < Actually we need G O(1) to obtain nontrivial lower bound. However, fao-se has unconstrained quadratic component whose gradient is unbounded over the whole space. Therefore, we have to restrict its domain be a bounded hypercube. However, it turns out to be impossible to find any hypercube such that | ( 2; y) I (1) without losing the properties of fm.e To overcome this difficulty, need to carefully modify the quadratic components in frese i... the blue and green arrows in Figure [[c).
Formally, define the hypercube C c R as
||00| S RJ. Our hard instance in the stochastic setting, fresess (CT, C R2 are postive numerical constants to be set later, is given by
C (xc Rd
(n(T-1) nRa + R. where R1 and
gooness 2; = (V(1)((11)) + Σ (V-2)) ((zz)
T-1
+
( 2+11: (0) + Σ
[ল + 0224t1],
(10)
1=1
1=1
where
C
1
h (x, 2:
2 y
(n A y 6 by.
(11)
Here C, C1, C2, bz.= are the same as those in
5
11 liv), we are able to construct a probability-p zero-chain as in Lemma over the rescaled version of fine-se, According to Lemma to ensure the variance of the rescaled stochastic oracle bounded by σ², p has to at least (2(c2) /oc² Then we obtain a lower bound for the stochastic setting of
By verifying that V fne (x, 2:
S ((1) (Lemma
rff nc Ω
1/3
Ω
p
Note that the deterministic lower bound is Q L Therefore we derive a lower bound
which is special case of the stochastic setting.
VK
x² _2/202)) Ω
VK
1/3
Ω
max
Detailed analyses are deferred to Appendix D
6 Conclusion and discussion
In this paper, we proved lower bounds on both the deterministic and the stochastic oracle complexities of sonconvex-Stronglyyconnee
min-max optimization for first-order zero-respecting algorithms. Our lower bound in the deterministic setting matches the existing upper bound [27] up to log factors. However, there is still gap between our lower bound and the upper bound in (26] in the stochastic setting. How to close this gap is an open question. Apart from this, several other questions are worth consideration.
First, one immediate next step to check if the proposed lower bounds hold for arbitrary, potentially randomized algorithms. We believe that the results are likely to hold but may introduce unexpected

---

complications. Second, so far we have focused on nonconvex-strongee wtroossl-oooonaaaaae min-max optimization. However, it remains open what the tight lower bound in the more general nonconvex -ononce- concave min-max optimization. Moreover, what about nonconvex-nonconeave min-max optimization? To answer this question, good measure of the suboptimality is prerequisite. Last but not least, we only consider first-order oracles. It is also interesting to obtain lower bound for functions with higher-order smoothness and oracles.
7 Funding transparency statement
Funding in direct support of this work: ONR grant N00014-20-1-2380 MIT-IBM Watson grant, NSF BIGDATA grant 1741341, and IIIS young scholar fellowship.
References
[1] Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin, Alexander Gasnikov, and Dmitry Kovalev. Accelerated methods for composite non-bilinear saddle point problem. arXiv preprint arXiv:/906.000 03620, 2019.
[2] Yossi Arjevani and Ohad Shamir. On the iteration complexity of oblivious first-order optimiza- tion algorithms. In International Conference on Machine Learning, pages 908-916. PMLR, 2016.
[3] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1912::1912.022 2019.
[4] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009.
[5] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pages 1-50, 2019.
[6] Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical PracicccllPPoorrre Programming, 185(1-2), 2021.
[7] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40(1):120- 145, 2011.
[8] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv: 2017.
[9] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. arXiv preprint arXiv:2009.0900 09623, 2020.
[10] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. arXiv preprint 1rXiv:2101.04233. 2021.
[11] Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured camconnvex-nonconauu min-max optimization. In International Conference Artificial Intelligence and Statistics, pages 2746-2754. PMLR, 2021.
[12] M. El-Mikkawy. On the inverse of general tridiagonal matrix. Appl. Math. Comput., 150: 669-679, 2004.
[13] Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator, 2018.
[14] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, 2013.
10

---

[15] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. variational inequality perspective on generative adversarial networks. arXiv preprint arXiv: 1802. 10551, 2018.
[16] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory, pages 1758-1784. PMLR, 2020.
[17] Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv:1406.2661, 2014.
[18] lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572, 2014.
[19] Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. ArXiv, abs/2103.08280, 2021.
[20] Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the con- vergence of single-call stochastic extra-gradient methods. arXiv preprint arXiv:/908. 08465, 2019.
[21] Adam Ibrahim, Waiss Azizian, Gauthier Gidel, and Ioannis Mitliagkas. Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learning. pages 4583-4593 PMLR, 2020.
[22] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optimization? In International Conference on Machine Learning, pages 4880-4889. PMLR, 2020.
[23] Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving Manconvex-concant min-max problems. arXiv preprint arXiv: 13433, 2019.
[24] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[25] Chung-Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear last-iterate conver- gence for matrix games and stochastic games. arXiv preprint 07Xiv:2006.09517, 2020.
[26] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
[27] Tianyi Lin, Chi Jin, and Michael. I. Jordan. Near-optimal algorithms for minimax optimization, 2020.
[28] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. JEEE Transactions on Signal Processing, 18:3676-3691, 2020.
[29] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0608: 2017.
[30] Oren Mangoubi and Nisheeth K. Vishnoi. Greedy adversarial equilibrium: An efficient alterna- tive to manconvex-nonconeee min-max optimization, 2020.
[31] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Shemp Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.0260 2018.
[32] Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of o( 1/Kk for optimistic gradient and extragradient methods in smooth convex -oncave saddle point problems. SIAM Journal on Optimization, 30(4):3200-32511 2020.

---

[33] Arkadi Nemirovski. ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
with rate of convergence o (1/t) for variational inequali-
[34] Arkadi. S. Nemirovski and David. B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
[35] A. Nemirovsky. Information- complexity of linear operator equations. Complex, 153-175, 1992.
[36] Yu Nesterov. Smooth minimization of non non-smooth functions. Mathematical programming. 103 (1):127-152, 2005.
[37] Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
[38] Neumann. Zur theorie der gesellschaftssiiee.. Mathematische annalen, 100(1):295-320, 1928.
[39] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods, arXiv preprini arXiv:1902.0822 2019.
[40] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first- order nash equilibria in nonconvex-concave smooth min-max problems. arXiv preprint arXiv:2002.079199 2020.
[41] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, pages 1-35, 2019.
[42] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianhao Yang. Non-convex min-max op- timization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, 2018.
[43] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. arXiv preprint 131. 2013.
[44] Maurice Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):171-176 1958.
[45] Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. arXiv preprint arXiv: 20199
[46] Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):237-252, 1995.
[47] Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. arXiv preprint 1r11v:1910.07512. 2019.
[48] Chen-Ye Yu Wei, Chung- Mein Lee, Mengxiao Zhang, and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. arXiv preprint arXiv:2102.045: 04444440 2021.
[49] Abhay Yadav, Sohil Shah, Zheng Xu, David Jacobs. and Tom Goldstein. Stabilizing adversarial nets with prediction methods. arXiv preprint arXiv: /70.007775.764 2017.
[50] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimiza- tion for class of nonconvex-nonconeaa minimax problems. arXiv preprint 17X11.2002.09621, 2020.
[51] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the saddle point problems, 2020.
[52] Siqi Zhang. Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of smnconvex-strongly-conecc minimax optimization. arXiv preprint arXiv:2103.1 15888, 2021.
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? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No] This work of theoretical nature. The main contribution to provide theoretical complexity
lower bounds. There are no negative societal impacts from this work, and as result we did not discuss it.
(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
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 5 and Appendix
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 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) If 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 was obtained from people whose data you't 're using/curating? [N/A]
(e) 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": "upGu8JpvRpT", "reviewer": "Reviewer_aNZZ", "summary": "This paper proposed a novel first-order oracle lower complexity bound for finding stationary points of smooth min-max optimization problems where the objective function is nonconvex in min variable, and strongly concave in max variable. The lower bound of $\\Omega(\\sqrt{\\kappa}\\epsilon^{-2})$ in deterministic setting matches the recent upper bound (up to log factors), hence is nearly optimal. Another lower bound of $\\Omega(\\sqrt{\\kappa}\\epsilon^{-2} + \\kappa^{1/3}\\epsilon^{-4})$ is provided for stochastic oracles, suggesting that the best-known upper bound of $O(\\kappa^3\\epsilon^{-4})$ is far from optimal in the condition number dependence. Overall, this paper is nicely written. The authors did a fantastic job in reviewing SOTA results, and put the newly derived lower complexity bounds in context. High-level explanations of the construction idea was provided, which makes it much easier to understand the proof and the complexity bound. The obtained results, to the best of my knowledge, are new and significant.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I only have some minor comments. \n\nThroughout the paper, the authors assumed the algorithm to be zero-respecting (Definition 4) and claim that there is a standard reduction from a lower bound for zero-respecting algorithms to that for arbitrary deterministic algorithms [3][5]. However, these cited papers are mostly based on the classical resisting oracles initialized by Nemirovski, A.S (to my knowledge)\n\nNemirovski, A.S.: Information-based complexity of linear operator equations. J. Complexity 8(2), 153–175 (1992)\n\nNemirovsky, A.: On optimality of krylov’s information when solving linear operator equations. J. Complexity 7(2), 121–130 (1991)\n\nSuch resisting oracle seems not easily extended to study general min-max optimization problems beyond the quadratic case; see the following article. \n\nOuyang, Y. and Xu, Y. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Mathematical Programming volume 185,1–35 (2021). \n\nIt would be better to elaborate this issue more clearly in the paper. \n\nTheorem 2 is particularly interesting to me, especially the condition number dependence of $\\kappa^{1/3}$. Any intuition behind the order? Any insights on which algorithm might achieve this lower bound?  \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a great paper which presents its ideas clearly and proves a good result, and it should be accepted to NeurIPS. I have no further complaints.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "cCNdEHz6p0v", "reviewer": "Reviewer_wgu3", "summary": "This paper consider the lower oracle complexity bound of NC-SC min-max problems in deterministic and stochastic settings. Based on the zero-chain argument in previous first-order optimization literature, the authors proposed a novel hard instance construction and shows that the lower bounds are $\\mathcal{O}(\\sqrt{\\kappa}\\epsilon^{-2})$ for deterministic setting and $\\mathcal{O}(\\sqrt{\\kappa}\\epsilon^{-2}+\\kappa^{1/3}\\sigma^2\\epsilon^{-4})$ in stochastic case. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "As pointed out by authors, exploring the lower bound of NC-SC min-max optimization problem is natural and imporatant following many recent works on nonconvex optimization and NC-SC algorithms works. The flow of the paper is very clear.\n\nThe main technique of the lower bound proof comes from previous lower bound works on convex optimization [34,36] and nonconvex optimization [3,5,6,13], i.e. the zero-chain argument. While the detailed hard instance construction, in my opinion, is novel and inspiring, especially the design of the subchain, which formulate a multiplication in the dimension numbers to get the final lower complexity results.\n\nThis paper considers deterministic and stochastic cases, while as authors pointed out, there is already concurrent works on deterministic case with the same result, the analysis in the stochastic case should be the first nontrivial result specifically in NC-SC min-max literature, even though there is still a large gap in terms of the dependence on the condition number ($\\kappa^{1/3}$ vs. $\\kappa^3$), this result should still be important.\n\nSome problems:\n1. Line 599 in the Appendix, is it $||u'||$ and $||P_C(u')||$, rather than solely $u'$ and $P_C(u')$? Also I think it should be $||\\cdot||$, rather than the absolute value sign $|\\cdot|$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work does not involve issues related to the negative impact of society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 (sum of finite intervals)"}, "extra_text": {}}, {"review_id": "Ba_pJ8GKzn", "reviewer": "Reviewer_SL4u", "summary": "The paper aims to provide lower complexity bounds for nonconvex-strongly-concave (NC-SC) minimax optimization problems. It shows $\\Omega(\\sqrt{\\kappa}\\epsilon^{-2}) for the deterministic setting and $\\Omega\\left(\\sqrt{\\kappa} \\epsilon^{-2}+\\kappa^{1 / 3} \\epsilon^{-4}\\right)$ for the stochastic setting. The lower bound for the deterministic setting has been nearly matched by several upper bounds, so it should be tight. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "$\\textbf{Originality}$: I believe the work is original. The idea in section 5.1 to glue two zero chains is novel and interesting to me. \n\n$\\textbf{Clarity}$: The structure of the paper is well-organized. The writing is clear, except a few grammar errors, such as in line 177-178. \n\n$\\textbf{Significance}$: To discover the lower complexity bound in NC-SC is an important task. Stochastic algorithms are widely used in practice, but the lower bound in this setting is under-explored. This paper is an initial step. \n\n$\\textbf{Questions and comments}$: \n\n1. One of my concerns is the contribution of the results. Except [Zhang et. al., 2021], the following paper appearing on arxiv this April also provides the same results for the deterministic NC-SC problems:\n \"Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems:\nThe results and construction. arXiv preprint arXiv:2103.08280, 2021.\"\nTherefore, the lower bound for deterministic setting can be showed by various methods. For the result of stochastic setting, although the paper shows the first result with the dependency in $\\kappa$, it does not seem tight to me, and the gap with the upper bound remains. So I am not sure about the potential of this method. \n\n2. The stationarity measure used in the paper is $L_m\\left\\|P_{\\mathcal{X}}[x-(1 / L_m) \\nabla f(x)]-x \\right\\|_{2} \\leq \\epsilon$, where $L_m$ is the smoothness constant of the function $f_m = \\max_x f(x,y)$. I am not sure whether there is existing upper bound that can nearly achieve this when $x$ is constrained. On the other hand, the upper bound it compares to requires the domain of $y$ to be bounded, while the hard instance the paper uses in the deterministic lower bound has unconstrained $y$.\n\n3. Is it possible to extend the analysis to stochastic setting with the averaged smoothness assumption?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "8RXhIDvT6SV", "reviewer": "Reviewer_KB1h", "summary": "This paper establishes lower bounds for finding approximate stationary points of min_x max_y f(x;y), where f is nonconvex in x and strongly concave in y. With deterministic gradients, the lower bound matches the convergence rate of the accelerated \"Minimax-PPA\" algorithm from [Lin et al. '20b], settling the oracle complexity in this setting, combining the bump-function construction of [Carmon et al. '19] with the classic zero-chain construction for convex optimization. A stochastic gradient oracle is constructed, following the same stochastic zero-chain construction as [Arjevani et al. '19], providing a lower bound scaling as \\kappa^{1/3} / \\eps^4 times the variance. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "- This paper settles the oracle complexity of a problem that has seen a flurry of recent theoretical and empirical interest. It fills a clear gap in the literature, and leaves an interesting question about the possible suboptimality of the best known algorithm for the stochastic setting. The exposition is very clear.\n- My overall assessment of this paper depends on whether or not the cited work [Zhang et al. 21] (\"The complexity of nonconvex-strongly-concave minimax optimization\"), which appeared on arXiv on March 29, 2021, counts as concurrent. It is claimed that the proofs and construction are different, but from what I could tell, Zhang et al. also arrive at a \"zero-chain within zero-chain\" construction, and the proof is not that conceptually different.\n- [Zhang et al. '21] themselves refer to concurrent work which was posted 2 weeks prior ([Han et al. '21], \"Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction\"), which also has overlapping material.\n- The treatment of the pure stochastic (as opposed to finite-sum) case is still new, and the modification of the construction to get a stochastic oracle with bounded variance is fairly subtle. However, in my opinion this does not suffice as a standalone novelty.\n- If the authors could articulate the differences vs. these works more clearly, this would be helpful towards reaching a conclusion independent of the concurrency issue.\n\nSmall typos:\n- 247: \"effictive\"\n- 248: \"suppose\" -> \"supposing\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is purely theoretical in nature. The discussion of limitations is adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a complexity lower bound for first-order optima for smooth non-convex and strongly concave min-max problems. The reviewers were unanimous in their appreciation of the construction of the lower bound and the result of the paper. The main concern with the paper is the presence of concurrent work which decreases the novelty of the result of the paper. The reviewers have nevertheless found the paper solid and the improvements/differences somewhat nicely articulated. I strongly suggest the authors to highlight the differences between the paper and the exisiting works clearly in the final version. 
Decision: Accept (Poster)