Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications
Authors: Weixin An
Yuanyuan Liu
Fanhua Shang
Hongying Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: zeroth-order algorithms
minimax problems
robustness
complexity
regression
Primary area: optimization
TL;DR: We propose a robust and faster zeroth-order algorithm to solve nonconvex minimax problems.

Abstract: Many zeroth-order (ZO) optimization algorithms have been developed to solve nonconvex minimax problems in machine learning and computer vision areas. However, existing ZO minimax algorithms have high complexity and rely on some strict restrictive conditions for ZO estimations. To address these issues, we design a new unified ZO gradient descent extragradient ascent (ZO-GDEGA) algorithm, which reduces the overall complexity to $\mathcal{O}(d\epsilon^{-6})$ to find an $\epsilon$-stationary point of the function $\psi$ for nonconvex-concave (NC-C) problems, where $d$ is the variable dimension. To the best of our knowledge, ZO-GDEGA is the first ZO algorithm with complexity guarantees to solve stochastic NC-C problems. Moreover, ZO-GDEGA requires weaker conditions on the ZO estimations and achieves more robust theoretical results. As a by-product, ZO-GDEGA has advantages on the condition number for the NC-strongly concave case. Experimentally, ZO-GDEGA can generate more effective poisoning attack data with an average accuracy reduction of 5\%. The improved AUC performance also verifies the robustness of gradient estimations.

Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications
Weixin An', Yuanyuan Fanhua Shang"; Hongying L
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, School of Artificial Intelligence, Xidian University, China College of Intelligence and Computing, Tianjin University, China Medical School, Tianjin University, China
4 *eng Cheng Lab, Shenzhen, China
weixinanut@163.c com, yyliu@xiiii x dididia edu. en, fhshanget ju. edu. en, hyliu20090t fu..dueedeee... edu.
Abstract
Many zeroth-order (ZO) optimization algorithms have been developed to solve nonconvex minimax problems in machine learning and computer vision However, existing ZO minimax algorithms have high complexity and rely on some strict restrictive conditions for ZO estimations. To address these issues, we design a new unified ZO gradient descent extragradient ascent (ZO-GDEGA) algorithm, which reduces the overall complexity to Ode B) find an e-stationary point of the function v for sinconvex-concary (NC-C) problems, where d is the variable di- mension. To the best of our knowledge, ZO-GDEGA is the first ZO algorithm with complexity guarantees to solve stochastic NC-C problems. Moreover, ZO-GDEGA requires weaker conditions on the 70 estimations and achieves more robust theoret- ical results. As by-product, ZO-GDEGA has advantages on the condition number for the NC-strongly concave case. Experimentally, ZO-GDEGA can generate more effective poisoning attack data with an average accuracy reduction of 5%. The improved AUC performance also verifies the robustness of gradient estimations.
Introduction
We mainly consider general regularized minimax problem:
min max V (x,y) v) g(x) + f(z,v) h(v)).
ZERI yERd
where f IRduxdy + R is nonconvex in concave in and f-smooth, R. + R and h Rd + R are convex but maybe nonsmooth functions. The problem (I) appears many scenarios of machine learning, such as adversarial attack to regularized deep neural networks, regularized fair learning, and robust training [7 [3]. this paper, we focus on the black-box setting of Problem ( where gradients are estimated by only functional values.
In the black-box setting. some evolutionary algorithms such [46 have achieved good performance. However, they usually lack complexity analysis and may never converge to a solution due to patholog- ical behavior (33). Thus, ZO algorithms with convergence guarantees came into being, For example, ZO algorithms provide an alternative to higher-order optimization methods for solving robust network training with gradient or curvature regularization [37 13). Besides, ZO algorithms have also made
considerable progress in escaping from saddle points 56
"Corresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

As for the black- box problem 1 ZO algorithms provide an access for solving it where the gradients are computationally infeasible or expensive, such as the Area Under Curve (AUC) maximization [4
with the ReLU activation and generating poisoning data to evaluate the black-box models 22
33 61
In these scenarios, 70 algorithms become one of the best choices. For example, 33 proposed 70-Min-Max for solving NC-strongly concave (NC-SC) data poisoning attack problems.
More practically, it is desired solve Problem ( under weaker conditions such as general concavity and more tolerant smoothing parameters of ZO estimators. But existing ZO algorithms such as (50 have high overall complexity for NC-C problems, and require picky smoothing parameters to ensure convergence, which weakens the robustness. On the other hand, the stochastic loss is actually more common [28). But there is no ZO algorithm to solve the stochastic NC-C problem (T). which motivates us to fill this gap. Thus, we summarize our motivations as follows:
Can design 70 algorithm to achieve lower overall complexity with more weaker requirements on ZO estimators for NC-C problems?
Due to the lack of research on stochastic ZO algorithms in the NC-C setting, can we develop new stochastic ZO algorithm with theoretical guarantees?
Table 1: Comparison of the overall ZO oracle complexity of single-loop algorithms to find an e-stationary point of f (Definition 3p or & (Definition 2 K = f/μu denotes the condition number, = dg + dy and (-) hides logarithmic terms. Abbreviation: Settings (Set.), Algorithms (Algs.). Regular (Reg.). Theorem (The.).
Sct.
Algs.
s/1b Reg.
p1. U1²
Deterministic
Stochastic
150
f Ix, Iy
Odd O(d,)e)))))
Odde -8 + 100
Unknown
NC
[51
f
Ix.Iy
Odd O(d
O 4))
Unknown
1b
O(d,' O(d,')))
Odcc-8)
Unknown
C
The. 2
1b 9, h
()
Old 8 +dd +
The.
vb 9. h
O(d7"3e), O(d,05)
0
NC
(33
[ Ix, Iy
O(x O (171))
O -0)
[19
vb Ix, Iy
0 d, Vi d,dss)
Ol1tib0014 On-'de-a)
SC
[47
vb 0,
0k=-2d- ) O d 1.cc)
dl O(N2dE-3 Ox +rddy)
The.
vb
9. h
Old ON 0.5 1,)))e)
About the column "Reg.", we transform Problem (1) into three models by setting different regularizers g and h: (i) When and h are both O, Problem T1 is transformed into min, max, (z. v) = f(x, v). (ii) When g (-(-) (-) and A = I-).). where Ie is the indicator function of the convex compact set C. Problem [ is transformed into min.c.x maxzey (x, y) = f(x, 8). (iil) When g = Ix(() and h = ||y||. Problem is transformed into minzex maxy (xx, 8) = [xx y) - ally] 1.
I Larger smoothing parameters (41 and jlz imply that algorithms can tolerate rougher 7.0 estimations, which means stronger robustness. In some cases, robustness has greater impact on algorithm performance than overall complexity. as shown in Table[]ello..
For NC-C problems, [50] [5] depend on an extra monotonically decreasing regular parameter sequence and 50 also depends on Assumption [ Our Theorem does not depend these assumptions.
The work [5] only achieves e-stationary point J. According to [31 Proposition 4. 12] and our analysis, requires the overall complexity of O(ds, + dyye ?) to find an e-stationary point of db.
Our contributions. In this paper, we propose unified algorithm to answer the above two questions. Our contributions can be summerized as follows.
We design a unified single-loop ZO-GDEGA algorithm to solve the NC-C minimax problem dynamics to assist in
faster and more robustly. Specifically, we introduce the idea of continuous designing the update rules of dual variable y. which plays a key role in complexity analysis. Moreover, we analyze ZO-GDEGA by developing a concise theoretical framework, which reduces the overall complexity of finding generalized e-stationary point of the function & to O(dd, + dy)e even without the Lipschitz continuity assumption, as shown in Table []
To the best of our knowledge, the stochastic ZO-GDEGA is the first 70 stochastic algorithm with theoretical guarantees for solving NC-C problems, which for the first time finds a generalized e-stationary point of de with an overall complexity of O(dee + dd,==), as shown in Table |
2

---

Our ZO- GO-GDEGA algorithm is more tolerant to the ZO estimations. Specifically, ZO-GDEGA allows a larger tolerance (e) for smoothness parameters μl and μ2 compared with existing methods, as shown in Table | which enhances the robustness of 7.0 algorithms.
As a by-prouuct, ZO-GDEGA applied NC-SC problems obtain competitive complexity results ( + dyy)- and ((r"(d, + (ddy))=+) for deterministic and stochastic settings, respectively,
Finally, the poisoning attack experiment shows that the poisoned data generated by ZO-GDEGA can reduce the accuracy by 2.1% %%7%%% compared to baselines. The AUC maximization task shows that our algorithms can improve AUC performance by 0.4-5.4 units under rough ZO estimation.
2
Preliminaries and Related Work
This section provides several notations and definitions, and discusses some related works.
2.1 Notations
I| and || II denote the & norm and nn-mrmm of a vector, respectively. || Ilao denotes the &x- norm of a vector, i.e., ||>|||>> maxi [ara]. We denote a (b) if S Cb for some constant C> > 0, any subgradient of g(.) at by Ög(x), a ZO estimator of f(-) at x by V for the gradient fz)x), the regularized coupling function by [' y) == f(x, y) - h(y), the max function
by (xx) == max,(f(z, y) - h(y) and the regularized max function by (x(x) == g(x) + 2(x).
Definition 1. function f(,,) is E-smooth, i.e. [ V ./)l S el( v) (/)l
2.2 Related Work
ZO algorithms for nonconvex minimax optimization. For solving NC-SC minimax problems, some single-loop ZO algorithms have been presented. For example, B3] proposed the Z0-Min-Mal by integrating alternating stochastic Gradient Descent Ascent (GDA) method and ZO estimators, which finds an c-stationary point with the overall complexity Or (in:de--) when g(x) = Ixx with
and hly) (z). [47] proposed the ZO-GDA for solving the deterministic problem g(x) = 0 and h(y) = I (v). and the ZO overall oracle complexity is bounded by O de Its stochastic variant, ZO-SGDA, can achieve the overall 70 oracle complexity (xsdde Recently, 19 proposed an Acc-ZOMDA algorithm based on momentum acceleration techniques and further reduced the overall ZO oracle complexity. However, these algorithms have relatively strict restrictions on ZO estimators, as shown in Table which affects their performance, as shown in Table
As for NC-C problems, to the best of our knowledge, the only work proposed in (50) designs ZO-AGP algorithm with the ZO oracle complexity O(dz O(d=E=&dd, 10). ), but it only considers the deterministic setting when = (z), h(y) = [y)), and X' and y are two convex compact sets, which limits its application to some scenarios such as regularized robust neural network training (21). More recently, new version of ZO-AGP [5T] has been presented during the preparation of our work, which achieves lower complexity under the same constraints, but its theoretical results are still in terms of the coupling function f instead of the stronger definition in terms of 1/, shown in Table T while our analysis is in terms of s/ and achieves lower complexity.
Extragradient methods. The extragradient (EG) method was first proposed in 27 for solving convex-concave saddle point problems and it adopts the gradient at the current point x, to find an intermediate point 14+1/2 and then uses the gradient at x4+1/2 /2 to determine the next iteration point It-1- Specifically, at iteration t,
1/+1/2 = proxo (st T/e (zf(z)),
Ft+1 = prox The (x. T/ (=f(2e11/2))
(2)
where prox. (z) A arg mins {g(2) + 27 1|2- On the one hand, the extra proximal gradient
step guides the optimization process, which allows to escape cycling trajectories of the simultaneous
gradient flow [23 and consider curvature information 40]. Compared with various GDA methods
such as [3 (55 many works have shown the advantages of the first-order (FO) EG structure, such as handling noisy gradients in the convex-concan
[26] 1 and NC-SC(C) 35 settings, but there is no insight into the 7.0 setting. On the other hand, in univariate convex optimization, the EG method has made considerable progress inspired by continuous time dynamic theory, and it can be explained as
3

---

an approximation of the more robust Barkward-Eulee discretization [8] whereas gradient descent is variant of the classical forward- Ealler discretization (9] Based on the two facts above, we aim to explore the performance of the EG structure in 70 minimax optimization to improve both theoretical
and practical performance for solving the black-box problem ①
Lower bounds for minimax optimization. For minimization problems, the lower bounds on ZO methods justify that the dependence on the dimension is inevitable without additional assumptions 12. For minimax problems, will there be a similar conclusion? So far, researchers focus on the
lower bounds of FO methods. For example, the lower bounds are Si convex-concave (C-C) and SC-SC settings, respectively. For NC-SC problems, there is also lower bound for the FO setting [59 30). But to the best of our knowledge, there is no work proving lower bound for ZO algorithms solving NC minimax problems. This paper focuses on another aspect and provides the upper bound for ZO algorithms solving NC minimax problems.
41 and (?())) [58] for
Upper bounds for minimax optimization. For the NC-C setting, GDA [1], Altemating GDA (AGDA) 4 and GDmax [25 are analyzed to guarantee convergence. So far, the best complexity bound for FO deterministic NC-C problems (e The works [60] 20 have further extended to the stochastic setting. For example, SAPD+ (60) achieved the complexity bound of O(e D()-)), which
matches that of the deterministic case. For the NC-SC setting, the works [3 49 proved the advanced
bound of (x:56-)) SAPD+ achieved another advanced complexity bound of O(se-)).
In minimizing optimization, the complexity of ZO methods is usually times that of corresponding FO methods [2). In this sense, our results match the upper bound in the deterministic NC-C setting, Unfortunately, there is similar conclusion in the minimax optimization yet. On the other hand, existing ZO methods such as [49 (50) focus on modifying existing FO algorithms,, while this paper focuses on designing ZO minimax algorithms directly improve performance.
3 ZO-GDEGA for NC-C Problems
In this section, we design unified single-loop Zo gradient descent extragradient ascent (ZO- GDEGA) algorithm for solving the NC-C problem ① analysis throughout this section.
The following assumptions are made for our
Assumption 1. We assume f(x,,) is concave for given I.
Assumption 2. 4 The regularizers g and are proper, convex and lower semicontinuous.
1. Additionally, g is either Lg Li-Lipschitz continuous on its domain, which is assumed to be open, or the indicator of nonempty, convex and closed set. Either of those assumptions guarantees the bound
llproxf (z) x1| S 7Lg
(3)
holds for any 7 >> O and all x E dom g (in the case of the indicator the statement is trivially true).
2. Furthermore, it has bounded domain dom h such that the diameter of dom h is bounded by Die
Similar to [4, we also use the extension of the classical Danskin's 's theorem based on Assumptions I and 2 to guarantee that the solution set Y (x) = {y"ly" E arg max, [f 3) h(y))} is non- empty for Vz gdd and & (z) is é-weakly convex. Based on these facts, we propose and analyze our ZO-GDEGA algorithm for solving the NC-C problem in deterministic and stochastic settings.
3.1 ZO-GDEGA in the Deterministic Setting
We first approximate the FO gradient by ZO randomized gradient estimators. Then, we propose the ZO-GDEGA algorithm to solve the black-box NC-C problem (T). Our algorithms are single-loop and more easily scalable compared to nested-loop algorithms such (32).
zo randomized gradient estimators. We introduce the ZO randomized gradient estimators as follows: vzf(z,y)= = 1 dc( f(x.))) V V fz y) 1 Σ (() -(a.))
Mt
where {u, Rd and (2 C Rd are i.i.d. random direction vectors drawn uniformly from the unit Fuclidean spheres, respectively. μn and μl2 are smoothing parameters, the conditions on which are strict in existing algorithms such as [5T], while our algorithms allow them to be ((e), as shown in Table I The randomness caused by vectors u, and is coupled in the alternating
Rd

---

updates of z and y and undoubtedly increases the difficulty of complexity analysis. We introduce two smooth functions fu, (x, y) E., (f + nn y)] and (z, y) = E, [f y + [22]] to bridge the 70 estimators and the FO gradient, thereby assisting in complexity analysis as shown in Fig.
Algorithm Deterministic Zeroth-Ordis Orderr Gradient Descent Extragradient Ascent Algorithm
Initialize: 20, 20 yo. step sizes T/u and Tly.
I: for t = 0....... T -1 do
V (x), ze) for NC-C case;
2: V. (())
L1+1 = prox (I+ - -1a V P(x)));
V w1) for NC-SC case;"
3: 2141 = -rrxx (ye + ny V v
VI+1 = prox (yt + Bly V (I141,
4: end for
5: Randomly draw å from 21,..., or at uniform.
Output: A.
To improve performance, we integrate the EG structure and the 70 randomized gradient estimators, and propose the ZO-GDEGA algorithm. Specifically, contains proximal gradient descent step and two proximal gradient ascent steps, shown in Algorithm !
3.1.1 Update rule of
Algorithm| updates æ by minimizing the following linearized approximation,
1 = arg min(g(() + (xr Te, J zx)) + 2n || xel
(4)
x
where 2, is an auxiliary variable and its update rule is given later. Our design for updating 24+1 relies only the previous point Tt, and does not require 42+1/2 in the standard EG method (
3.1.2 EG update rule of y--
The quality of the solution set Y=(x) plays a key role on complexity. To take full advantage of the EG structure based on the concavity w.r.t. y, integrate it into the update of y. which guides new high-level idea from the continuous time dynamic perspective.
A high-level idea. Here we show intuition for the advantages of our algorithm. If h is "simple", in the sense that the proximal operator has a closed-for -ooem solution [6] Without loss of generality, we consider the case of huy) = O. In this case, the proximal operator becomes the identity transformation. In fact, one-step ZO estimation w.r.t. y can be viewed as the discretization the stochastic continuous- time dynamic (t)= = vtt==V,ffe fXX, (t)) with the limit 7y + 0. To get more robust and accurate solutions, use the backward-Eules instead of forward- Euler discretization to solve this dynamic. An exact backward-Eulee step implies the discretization y = Ue By V yf [ Vt+1), but obtaining Vt+11 in such a manner could be computationally prohibitive. Instead, we opt for an extra gradient ascent step 2++1 = Yt + fy V / yt) to first approximate y/+1 once as shown in the 3rd line of Algorithm I. which be viewed as "trial" step. Then, use the 70 oracle point (#141, #(+1) to approximate one-step backward- Eullrr discretization shown in the end of the 3rd line, which is one of the reasons why our ZO-GDEGA algorithm is more robust than [51]
3.1.3 Advantages over Existing Methods.
Compared with existing works, ZO-GDEGA algorithm has the following three main advantages:
Stronger robustness. About ZO estimators, ZO-GDEGA can tolerate smoothness parameters μ1 and #2 of size OEe), whereas existing ZO algorithms have stricter restrictions smoothness parameters such as OEet) as shown in Table [ which is the fundamental reason why ZO-GDEGA improves the robustness. Specific proof' and experimental verifications are in subsequent sections.
Lower per-iteration complexity. Compared with the standard EG method 35 Algorithm Donly uses the EG structure for the update of instead of both x and y, which reduces per-iteration complexity and maintains the same iteration complexity as the standard EG method. In fact, our ZO-GDEGA algorithm is easily extended to an FO method, which still reduces the computation cost and maintains the corresponding theoretical result. Since this paper mainly focuses on the 7.0 case, the FO variant of Algorithm is shown in the Appendix.
5

---

More extensive applications. The proximal operators generalize the projection operators in existing works such as [ST]. Compared with [2T] our -O-GGE does not require additional compactness of the domains, which significantly extend the applicabilityy
3.2 ZO-GDEGA in the Stochastic Setting
We consider that f is stochastic function on distribution D, i.e. f(z y) Bg~D (z, E), and we can only access the stochastic function values f (z, yi E). In this case, we introduce the stochastic ver- sion of 7O estimators: [ (z, 1 b,
y: (i) i ト ((=tmra,.99) - (x..0())) uj as well as fz, y: I2). where I {( |/ In = 1E,
denote mani-batch sets of 61 and 62
Li.dd samples. According to [9]. Ev,,, (x, [x)] V (x. y) and E (V,,,,V,,, v (r. y: I2) V Vyz (Ir, v) with U = {w: th and V= (u; /2 and we need the common Assumptions 6 and in ZO stochastic optimization. Due to the page limit, we place Assumptions 6 and 7 in the Appendix.
Assumption 3. The variance of the Zo stochastic estimators bounded, i.e. Eu,c [ (x,
Valea (z, v) S of, E.ggl
y ( 5) - yyJna (x. w)ll S o..
Based on the above analysis and Algorithm [T] we design stochastic variant of ZDEGAA as shown in Algorithm 2 in the Appendix. The main difference between Algorithms 2 and | is that the ZO estimators are replaced by their stochastic versions. In fact, for NC-C minimax problems, stochastic ZO-GDEGA is the first stochastic ZO algorithm and we prove its complexity in Section S
4 ZO-GDEGA for NC-SC Problems
In this section, we provide two by-products of our ZO-GDEGA algorithm for the NC-SC setting, as also shown in Algorithms I and 2 We design and analyze them based on Assumption 4 Assumption 4. We assume f far :) is p-strongly concave in y for a given x. Moreover, the regularizers g and are proper, convex and lower semicontinuou.
know that the max function ((x) (x+ 1)e-smotth, where = l/p 2 1 is the condition number, which plays a key role in our analysis. Note that there are two main differences between our ZO-GDEGA for solving NC-SC and NC-C problems follows:
Based Assumption
Due to the strong concavity, there is no need to use the intermediate point 24 to update 1++1. but directly use the ZO estimators at the point (Ie, M1) to accelerate updating, which contributes to achieve competitive complexity under weaker restrictions on μ4 and μ22 thereby enhancing robustness.
The solution set Y (xx) is singleton, which consists of a single element y" (I). thus we can use the quantity 5, := 1,y+ y" (xx))l to measure the quality of proximal ZO extragradient ascent steps.
In summary, we propose a unified ZO algorithm for solving black-box NC minimax problems, which outperforms existing 70 algorithms. Next, rigorously analyze its complexity.
5
Theoretical Analysis
In this section, we first define two types of generalized e-stationary points termination criteria. Then, we provide the complexity results of our ZO-GDEGA to find an c-stationary point.
5.1 Termination Criteria
We generalize two classical definitions of c-stationary point in 31 and 32
as follows.
Definition 2. In the NC-C setting, point is e-stationary point of an Ê-weakly convex function b if its Moreau envelope th 1///2((1) satisfies || / S In the NC-SC setting, a point x is an c-stationary point of a function va if d0st(0, (0,,0))),))))))))))))))))))))))) $
Definition 3. A pair of points (x. v) is an c-stationary point of the coupling function f if we have [[(x felx (1/E)V / w))]
[| 1l S where G(z, v) = fly prox (1/2) v, v))l
211/2e(()) (xr is the Moreau envelope of (xx) if (1/20(x) min.. ( fllw } for each Rd

---

Based on [31 Proposition 4.11 and 4.12), the following two propositions clarify the relationship between the generalized Definitions 2 and
Proposition 1. Under Assumptions and if point (ā, i) is e² (((DDi)-statioarryy point in terms
of Definition 3 point î is an O - point in terms of Definition 2
Proposition2 2. Under Assumption 4
if a point (ă, y) is an e/ e/t-staatinnary point in terms of Definition point & is ((e) -(tttttaty point in terms of Definition 2
3
Thus, we can draw a similar conclusion as in 31: The e-stationary point definition of eb is stronger than that of f. To obtain tighter complexity bounds, we analyze 20 algorithms for the first time based on e-stationary point definition of & (i.e., Definition
5.2 Complexity Analysis for NC-SC Problems
We first analyze the complexity of ZO- GO-GDEGA for the NC-SC setting in deterministic and stochastic cases. Our analysis is non-trivial extension of the proofs in 31 due to the following challenges.
Key technical challenges. In this case, bounding Et=o 5g is a key step. But the proximal operators and the ZO EG structure make it much more difficult to bound this term than existing works. To address this challenge, we propose to establish the upper bound on Ei=od 5; in terms of E || x1+1ll (see the Appendix for details), which also reduces the overall complexity's 's dependence on and results in the coefficients of μs and μü being only (1) and (K), thereby weakening their dependence K. and enhancing robustness. Here directly give the complexity results.
Theorem 1. We choose stepsizes 7/2 S 256x"" fly 21 μm = (dd)'c) and μtz O(K 1/2 cc. Under Assumption 4 our ZO-GDEGA can find an e-stationary point in terms of Definition 2 i.e. miss dist(-òg( (z()), (x()))) c, with the overall ZO oracle complexity O (dg + dy) E-))
for deterministic and (O (dg + rdy)) for stochastic settings.
Theorem shows that ZO-GDEGA allows for larger l4 and J12 than compared algorithms (see Table D.. which means that our algorithms can tolerate rougher Z0 estimations. Besides, our complexity bounds have the weaker dependence than them. Thus, even our by-products have some advantages. Moreover, this analysis also builds bridge for analyzing the NC-C setting.
5.3
Complexity Analysis for NC-C Problems
In this part, we analyze ZO-GDEGA in the NC-C setting. We provides two perspectives: continuity- agnostic (more relaxed condition) and continuity-dependent (better bound) analysis.
5.3.1 Continuity-Agnoste Complexity Analysis.
We first analyze the complexity for the NC-C setting based on Theorem and smooth technology in
38.. By adding a smoothing term, we approximate the NC-C problem 11 with the following NC-SC
model: min, max, (z. y) = g(x) + fx, y) h(y)), where f(z y) fx, y) - + ğll and given arbitrary ÿ E dom h. Based on Theorem and careful selection of A. Theorem ensures that 2O-GDEGA can find an e-stationary point for the NC-C problem (I)
Theorem 2. Under Assumptions D and our Z0-GDEGA applied to the approximate NC-SC model with js O(e2 ((DD))) can guarantee generate an e-stationary point x. for the NC-C problem (.. i.e., / I c, with overall complexity ((dd, dyyc and Od + dye 10) for the deterministic and stochastic settings, respectively.
Based on stronger Definition 2 Theorem 2 ensures that our ZO-GDEGA can achieve lower complexity for NC-C problems without relying on any extra assumptions, such as continuity and decreasing sequence assumptions, whereas (50] 51 depend on least one of them. Besides, Theorem 2 inherits the advantages of our analysis for Theorem I i.c., enhancing robustness and reducing complexity.
5.3.2 Better Bounds with Continitt--dependent.
We also analyze our ZO-GDEGA algorithm for solving the NC-C problem (T) under the Lipschitz continuity assumption, which is common in NC-C optimization such as 31 35 43 4
7

---

Assumption (Continuity). f(x, v) is G- G-Lipcchitz continuous in for Vy E dom h, Vx, x' E Rd= satisfies that (x, y) [(x', ( y) & G
x x'1
In the case of (if) in Table [1 5
immediately by the smoothness and choosing G = 4Dx + Dy} + VVz ye Il. where maX || x²'l - Dx and maxy.y'e lly - y Dy. Thus, ZO-GDEGA still work without Assumption i this case. For the general problem (I)
we use G' for generalization and give proof sketch. Detailed proofs are provided in the Appendix.
Proof sketch. We first analyze the recursive relationship between the Moreau envelopes 1/1 (1)) and (1+22(2(+1) based on the ZO gradient descent step. Then, estimate the tricky error term A, (z²) [' 21) measure the upper bound of the ZO EG ascent steps. Based on these results, we obtain the overall complexity for solving the NC-C problem [[ In deterministic and stochastic settings, we provide tighter results than Theorem respectively.
Deterministic Setting. Lemma B.13 providee the recursive re- lationship between eا / (2(+1)
Ascent oG V..
Auas ((Fc)s) Pes
VVF(x,)) VV..-.VVV.. V.
10,00
and /1/22 (1te. Our algorithms use more concise ZO estimation gradient descent step instead of EG structure to update Thus, the tricky term f (/) 1/)
Lauzn B.13: Prociral Descent Ouar (sa.)) Hayer (4)
Prodine BG Descert yar (ass) uar (6)
(xy) (uyg)
TTT a Goll
Priee Cull so
Firstorder EG Olahdarinia et 2002)
OurZ0-GDEGA
(=f(x 1l can be re-
Figure 1: Comparison of two proof sketches.
moved in our analysis compared
with the standard EG method in (35 as shown in Fig. Lemma B.15 proves that Σ E[A,] can be well controlled by carefully choosing Πy More importantly, our analysis makes the coefficients of μ and μz independent of e, which eases their dependence enhancing the robustness. Now, we begin to provide tighter results.
compared with 157), thereby
Theorem 3. Under Assumptions 2 and 5 (
if q1 = dg. 92 92= dy. Bl 1//3v3)(3), T2 = OcE,,, our deterministic ZO-GDEGA can find an e-stationary point of v. i.e.
and μ22 = O
Vay
E V V Se, for the NC-C setting with the overall complexity O + dy) 6). T 1=0
Theorem 3 shows that our ZO-GDEGA achieves the same overall complexity as Theorem 2 and further weakens the constraints smoothing parameters under the continuity assumption. Note that ZO-GDEGA is the first ZO algorithm with convergence guarantees to find an e-stationary point of th. Meanwhile, our analysis can be easily extended to the stochastic setting.
Stochastic Setting, Due to the page limit, we directly provide results for stochastic ZO-GDEGA.
Theorem 4. Under assumptions I 2 3 and if we choose the suitable parameters such # O(e)
and μ2 (E), our stochastic ZO-GDEGA algorithm can find an e-stationary point in terms of Definition 2 with lower overall complexity Odde + ddy=*) than Theorem
Theorem shows that the overall complexity can be further reduced, and we can still choose μ and μl2 to be O(e) to enhance the robustness. Note that we provide theoretical guarantees for the stochastic black-box NC-C setting for the first time. In summary, our ZO-GDEGA shows excellent theoretical properties for solving NC-C problems and competitiveness for solving NC-SC problems.
Experiments
In this section, we conduct black-box data poisoning attack and AUC maximization experiments. Due to the page limit, more experimental details and results are provided in the Appendix. Our codes are available: httpps//ggithbb.co wtwplluw.coom/m/eeeeeee WeixiinAAnZO--DDEE....
6.1 Data Poisoning Attack
Data poisoning attack is one of the most common black-box attack methods 29 42
The purpose of the attacker when the model parameter w well-trained, adding a perturbation å on the training data that makes the loss functions large possible, and then such poisoned training data
8

---

Fo-AGP
1.00
Aaiuoni geg gots wn
Z0-APP:
Objective valuee 5.00 (k))))))
20 GDBBA: q-5 (Ours)
20. GDBGG: q-20 (Ours)
20.AGP: a=20
0.90
FO-MGP
FO-AGP
0.85
20-AGP qm5
20-GGP qm5
Z0-50L5A (Ours)
20-60L5K qub (Buns)
20-AGP: q-20
20-GDEGA: q-20 (Ouns)
0.75
20-GDECA: 4-20 (Ours)
10'
10'
10"
10
q-3
20-AGP
zo GDEGA: c-5 (Ours)
0.50
70-CDFGA (Burs)
Tugling arc
0.85
0.85
Zo.AGP: q-20
20-CIEGA or
lesting socuracy
0.85
0.80
Poison
0.70
0.75
20 AGP: q-5
ZO-GDEGA:
0.75
0.70
AGP: Q-20
0.70
0.65
0.65
Z0-CDEGA:: 2-20 (Ours)
0.60
10"
15 ratio
Iteratioon
(seconds)
Comparison of the results for the logistic regression model attacked by poisoned data generated by ZO-AGP and ZO-GDEGA the synthetic dataset.
Figure 2:
0.85
zo NGP: q-5
Zo- CD-CDEGA: q-5
Training securnc
0.85
Reeting SEOURC
0.80
accuracy
0.775
0.800
Z0-AGP: 4-20
zo GDEGA 9- (Ours)
0.80
0.750
0.75
No Poison
20 AGP: qu45
0.75
20 045
No Poison
0.725
GDEGG: qu5
0.70
GG/ (Ours)
0.700
0.70
20-AGP: q-20
Z0-GDECA; 2- (Ours)
20-0DECA: 4-20 (Curs]
0.675
0.65
0.650
2:00
400
600
800
CPU time (seconas)
Figure 3: Comparison the attack results data poisoning attack on the large-scale epsilon test dataset.
(s: + 8,44) will reduce the model accuracy. Therefore, it is usually required for attackers to optimize the following objective function,
max min (1 w) == For w; D.r); Sr 6
(5)
where Der Der.p Dtr.e denotes the training dataset including n i.i.d samples, Dtr,p and Dir.c denote the poisoned and clean subsets of Drr, respectively. We choose the cross-entropy loss to optimize 8 and Note that Problem (5) can be rewritten the NC-C (1 by setting g(-) Tr ()), (x.)) = 0, and
f1- Therefore, it can be solved by our Z0-GDEGA algorithm.
Datasets. We validate ZO-GDEGA
synthetic dataset and the epsilon_test dataset.
Synthetic datasets: We generate dataset D {s;, 2.000 with feature vector 8; E -R0000 from Gaussian distribution (00 I) and split it into 70% training and 30% test samples. The label f, = 1 if 1/1 (0) w +m.)) > 0.5, otherwise 4 where n, (0 10-3) is random noise, and set w² = 1 as the ground truth.
)
The epsilon_ter it into 70% training samples and 30% testing samples.
d It contains 100,000 samples of 2,000 dimensions, and we also split
Experimental Settings & Baselines. We set r= = 2, μ2 = 2 x 10 and poisoning ratio [Dmpl/|PPrr 0.1, and choose mini-batch size b b2 100 and
by 10 for the
synthetic c and eps los_tosntttts datasets, respectively. The baseline for solving Problem (5) is ZO-AGP, Note that here we replace the 7.0 estimators in deterministic 70-AGP with corresponding stochastic versions and choose the same hyperparameter settings for fair comparison.
Results. We use the poisoned data generated by the baselines and our ZO-GDEGA attack the training procedure of the logistic regression model, and the experimental results on the synthetic

---

and apsilon__ _ees datasets are shown in Figs. 2 and respectively. The experiment in each case was carried out in 10 independent trials with random initialization and the shaded area around the line indicates the standard deviation. From Fig. 2 we find that our 70-GDEGA can converge faster than baselines terms of stationary gap and objective value - f1. From the training accuracy subfigure, both our ZO-GDEGA and the baselines (black-box attack) converge, and achieve near- optimal solution compared to the FO-AGP algorithm (white-box attack) [52]. As for testing accuracy, it can be seen that compared with ZO-AGP, the poisoned data generated by our ZO-GDEGA are always more effective in reducing the accuracy the logistic regression model in terms of both iterations and CPU time, which also confirms that our ZO-GDEGA achieves lower complexity than ZO-AGP, Besides, under different poisoning ratios, ZO-GDEGA can reduce the model accuracy by 2.1%-7.6% than ZO-AGP in terms of attack performance. From Fig. B observe that ZO-GDEGA algorithm also performs about 8.0% lower than ZO-AGP on the epsi lon_test dataset, which further verifies the superiority of our algorithm in the large-scale real-world datasets.
6.2 AUC Maximization
AUC is defined as the area under the ROC curve, which is a performance indicator measure the pros and cons of machine learning model. However, it is generally difficult to optimize the AUC value directly on the training task, but instead optimize the following minimax problem:
min max Eg Pf a, b. b;))]
(6)
| | oST,
where Tu and ry are the radius of the projection balls, s = (s, drawn independently from the distribution P, and f(0, a. b, s; is defined as in [53). When choose the multilayer perception (MLP) model, Problem (6) becomes a NC-SC problem. The non-differentiable point of the nonlinear function such ReLU causes some non-differentiable modules of the classifier, and the ZO algo- rithms are one of the techniques to solve this issue [15. Note that our ZO-GDEGA is the first ZO algorithm to attempt to solve the AUC maximization problem.
Experimental Settings & Baselines. We conduct experiments on the MNIST, Bashion-MIIS
Table 2: The average AUC performance with different μı and μ2 the MNIST and Fashion on-MiIS datasets, where μn = #2- Results on dataset i jeenn are provided in the Appendix.
and ijennl
datasets. Following [54), we use their training and testing sets but convert the classes of the data into two classes by randomly splitting them into two groups. We implement ZO-SGDA (7),
Datasets N1 (p(2)
MNIST
Fashicn-Min
0.001
0.01 0.05
0.001 0.01 0.05
ZO-SGDA
91.67
91.81 88.12
91.62
90.19
87.27
Z0-Min-Max
92.25
92.01 88.56
90.80
91.58 83.23
20-Min-Max (33, Ace-ZOMDA [19] and our ZO-GDEGA to solve Problem (6) with Leaky ReLU, We choose a
Acc-ZOMDA
92.45
92.58 89.35
92.97 91.65 87.75
ZO-GDEGA
91.60 92.60 89.70 91.97 92.23 88.66
two-layer MLP as the classification model, and set mini-batch b, b2 256, 9 =
02 10,
Ya = 2 and step sizes
Fly = 0.1 to train all the methods for 200 epochs.
Results. We show the average AUC performance from 10 independent trials with random initialization in Table It shows that at small μ1 and μ2, our ZO-GDEGA algorithms perform competitively compared with the baselines. At larger μ4 and μlz ZO-GDEGA can improve AUC performance by 0.4-5.4 units than baselines, which indicates that our algorithms are more robust to smoothing parameters and robustness may be more important than overall complexity in some cases when using Zo oracle to approximate gradients.
7 Conclusions and Future Work
In this paper, we proposed a unified ZO-GDECI algorithm for solving black-box nonconvex minimax problems, which reduces the overall complexity and improves robustness. The experimental results match our theoretical analysis, which is reflected by the fact that ZO-GDEGA can obtain more effective attacks and improve AUC performance robustly. In summary, ZO-GDEGA achieves better performance than related algorithms and promotes the development of ZO optimization theory. the future, we will extend our algorithm to mon-smooth and federated learning settings as in 45 44
10

---

8 Acknowledgments
We want thank the anonymous reviewers for their valuable suggestions and comments. This work was supported by the National Key Research and Development Program of China (No. 2023YFF0906204), National Natural Science Foundation of China (No. 62276182), and Peng Cheng Lab Program (No. PCL2023A08).
References
min-max [1] K Antonakopoulos. Adaptive extra sitra-gradient methods for min max optimization and games, In International Conference on Learning Representations, volume 3, page 7, 2021.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 214-223, 2017.
[3] Amir Beck and Mare Teboulle. A fast iterative shrinkage-threshoolinng algorithm for linear inverse problems. Siam J Imaging Sciences, 2(1):183-2022 2009.
[4] Radu Ioan Bot and Axel Böhm. Alternating moximall-gradiens steps for (stochastic) nonconvex- concave minimax problems. SIAM Journal on Optimization, 13(3):1884-1911 2023.
[5] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[6] Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 1001200-45.. 201
[7] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26, 2017.
[8] Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang. Accelerated schemes for class of variational inequalities. Mathematical Programming, 165:113-149, 2017.
[9] Jelena Diakonikolas and Lorenzo Orecchia. Accelerated extra-gradient descent: A novel accelerated first-order method. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94, 2018.
[10] Dmitriy Drusvyatskiy and Adrian S. Lewis. Error bounds, quadratic growth, and linear con- vergence of proximal methods. Mathematics of Operations Research, page moor.2017.088. 2016.
[11] John Duchi and Yoram Singer. Efficient online and batch learning using forward backward splitting. Journal of Machine Learning Research, 10(18)22899-29 2934, 2009.
[12] John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (((5):778-2800)) 2015.
[13] Chris Finlay and Adam M Oberman. Scaleable input gradient regularization for adversarial robustness. Machine Learning with Applications, 3: 3:100 2021.
[14] Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the adaamattion-aaativee variants of the admm: iteration complexity perspective. Journal of Scientific Computing, 76:327-363, 2018.
[15] Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang Gradientless descent: High-dimensional zeroth-order optimization. In International Conference on Learning Representations, 2019.
[16] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint 4rXiv:1412.6572,20 2014.

---

[17] Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017.
[18] Hairer, SP Nørsett, and G Wanner. Solving ordinary differential equations i: Nonstiff problems, 1993.
[19] Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization. The Journal of Machine Learning Research, 23(1):1616-163) 2022.
[20] Feihu Huang, Xidong Wu, and Zhengmian Hu. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. In International Conference on Artificial Intelligncee and Statistics, pages 2365-2388 PMLR, 2023.
[21] Feihu Huang, Xidong Wu, and Heng Huang. Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 34: 10431- 10443, 2021.
[22] Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversar- ial attacks with bandits and priors. International Conference on Learning Representations. number 2019, 2019.
[23] Samy Jelassi, Carles Domingo-Enrich, Damien Scieur, Arthur Mensch, and Joan Bruna. Ex- tragradient with player sampling for faster nash equilibrium finding. In Proceedings of the International Conference on Machine Learning, 2020.
[24] Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International conference on machine learning, pages 3 3100-3109, 2019.
[25] 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.
[26] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[27] Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[28] Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28(2010), 2019.
[29] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks on factorization-base collaborative filtering. Advances in neural information processing systems, 29, 2016.
[30] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for min-max optimization. Advances in Neural Information Process- ing Systems, 34: 114:1792-1800 2021.
[31] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for Sancoonvex-concane minimax problems. In International Conference on Machine Learning, pages 6083-6093, 2020.
[32] Tianyi Lin, Chi Jin, and Michael Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779 2020.
[33] Sijia Liu, Songtao Lu, Xiangyi Chen, Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, and Una-May O' Reilly. Min-max optimization without gradients: Convergence and applications to black-box evasion and poisoning attacks. International conference on machine learning. pages 6282-6293, 2020.
12

---

[34] Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex-stronge strongly-concawy minimax problems. Advances in Neural Information Processing Systems, 33:20566-
[35] Mahdavinia, Y Deng, H Li, and M Mahdavi. Tight analysis of extra-gradient and optimistic gradient methods for nonconvex minimax problems. Neural Information Processing Systems, 2022.
[36] Aryan Mokhtari, Asuman H Ozdaglar, and Sarath Pattathil. Convergence rate of o( 1/k) for optimistic gradient and extragradient methods smooth convex-concave saddle point problems. SIAM Journal on Optimization, 30(4):3230-3251) 2020.
[37] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9078-9086, 2019.
[38] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103:127-152, 2005.
[39] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):277-566, 2017.
[40] Trong Phong Nguyen, Edouard Pauwels, Emile Richard, and Bruce W Suter. Extragradient method in optimization: Convergence and complexity. Journal of Optimization Theory and Applications, 1 176: 162 2018.
[41] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-coneave bilinear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
[42] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pages 506-519, 2017.
[43] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakby-convex--concce min- max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, 37(3): 2022.
[44] Marco Rando, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. An optimal structured zeroth- order algorithm for non-smooth optimization. Advances in Neural Information Processing Systems, 36, 2024.
[45] Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimiza- tion: Improved convergence analyses and algorithms. In International Conference on Machine Learning, pages 19730.19730. PMLR, 2022.
[46] Adam Slowik and Halina Kwasnicka.
Evolutionary algorithms and their applications to engi- neering problems. Neural Computing and Applications, 32:12363-12379, 2020.
[47] Zhongruo Wang, Krishnakumar Balasubramaniaan, Shiqian Ma, and Meisam Razaviyayn. Zeroth- order algorithms for nonconvex wwr.sssttooolyyccceeee minimax problems with improved complexi- ties. Journal of Global Optimization, pages 1-32, 2022.
[48] Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. Siam Journal on Optimization, 24(4), 2014.
[49] Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. 2020.
[50] Zi Xu, Jingjing Shen, Ziqi Wang. and Yuhong Dai. Zeroth-order alternating randomized gradient projection algorithms for general nonconvex-coneave minimax problems. arXiv preprint NXXi:2108.00477 2021.
13

---

[51] Zi Xu. Ziqi Wang, Jingjing Shen, and Yuhong Dai. Derivative-Foe free alternating projection algorithms for general eerconvex-concayy minimax problems. SIAM Journal on Optimization. 34(2):1879-15) 2024.
[52] Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradi- ent projection algorithm for nonconvex-coneee concave and Mathematical Programming, pages 1-72, 2023.
minimax problems.
[53] Zhenhuan Yang. Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Dif- ferentially private sgda for minimax problems. In Uncertainty in Artificial Intelligence, pages 2192-2202, 2022.
[54] Yiming Ying, Longyin Wen, and Siwei Lyu. Stochastic online auc maximization. In Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[55] Guodong Zhang. Yuanhao Wang. Laurent Lessard, and Roger Grosse, Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 7639-7679, 2022.
[56] Hualin Zhang, Huan Xiong, and Bin Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. Advances in Neural Information Processing Systems, 35:38332- 38344, 2022.
[57] Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. A single-loop smoothed gradient descent-ascent algorithm for nonconvex-coneave min-max problems. Advances neural information processing systems, 33:7377-7389, 2020.
[58] Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901-995) 2022.
[59] Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconvex-stronge! corrovel--ccocvveeeeee minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492 PMLR, 2021.
[60] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems. Advances in Neural Information Processing Systems, 35:21668-216811 2022.
[61] Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu. How robustify black-box ml models? a zeroth-order optimization perspective. In International Conference on Learning Representations, 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See the sections Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the sections Experiments, Conclusions and Future Work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
Please see the section Theoretical Analysis.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
46

---

Answer:
[Yes]
Justification:
Please see the section Experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (httpss//nips.c/ppbbicc guiddes/CodeSubiissionPoo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wttpaiccggguieeeoooooooooiiiiiie
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
47

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see the section Experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::/leerr..ccccpaphc/hhiiiice
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., -,, if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is of theoretical nature. The main contribution is to improve robustness and reduce complexity. There are no positive and negative societal impacts from this work, and as result we did not discuss it.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
48

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We used public datasets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswithcode, pepersswihhcdde.com/ltatszes has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
49

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We describe the data generation method in detail in the experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
50


Reviews:
[{"review_id": "7uyJYkA7qI", "reviewer": "Reviewer_JCfr", "summary": "In this paper, the authors establish a unified framework of zeroth-order optimization for nonconvex-concave minimax optimization problems in both deterministic and stochastic settings. This framework is based on the gradient descent-extragradient ascent algorithm. They claim that their algorithms require weaker assumptions on the zeroth-order estimator, while achieve competitive iteration complexity compared with the existing work. Besides, they provide some numerical experiments to verify the effectiveness of the proposed algorithms.", "questions": "Similar to aforementioned concerns on example, the experiments of poisoning data attack is a clear application that zeroth-order can be used. My question is whether it is possible to use first-order method in some cases? If this is the application that no first-order method can be used, then my previous conern on weakness can be addressed. I don't here mean that the authors should have compare zeroth-order method to first-order method in performance, since it is completely reasonable that first-order method outperforms zeroth-order and even it holds, nothing negative will impact the contribution of the paper.", "limitations": "This paper is mostly a theoretical work, no negative societal impact may result in.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Main advantages can refer to the Summary. Besides, this paper has a good organization, which makes the readers reading easily. Numerous experiments including abundant baselines and datasets are provided to illustrate the effectiveness of the proposed algorithm.", "weaknesses": "In the stochastic setting, the authors make the bounded variance assumption on the zeroth-order estimator in Assumption 3. It seems that the assumption makes the proof very similar to first-order method. It is true that the zeroth-order methods are used when computing derivative are not possible, but does this assumption rules out the most challenging technical part in the proof?\nThis paper has proposed zeroth-order method that is motivated by application scenes when the objective function is not smooth enough to enable one to compute the gradient. But there is no specific examples provided that such method plays a prominent role while the first-order method is not applicable. Since there is a definite trade-off when zeroth-order method are used compared to first-order, the smooth parameter is another factor that should be considered in using zeroth-order method. So I think providing a concrete application that zeroth-order method is inevitable will help convincing the importance of the algorithm in application.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful thoughts and comments! Below we will clarify the two points in the review.\n\n### **About Assumption 3.**\n\nFirstly, analyzing ZO algorithms has the following two main difficulties compared to analyzing first-order methods. That is, we need to bound two error terms, the error $||\\hat\\nabla_x f(x,y;\\zeta) - \\nabla_x f_{\\mu_1}(x,y)||$ (or $||\\hat\\nabla_y f(x,y;\\xi) - \\nabla_y f_{\\mu_2}(x,y)||$) and $||\\nabla_x f_{\\mu_1}(x,y) - \\nabla_x f(x,y)||$ (or $||\\nabla_y f_{\\mu_2}(x,y) - \\nabla_y f(x,y)||$). We first bound the first error by Assumption 3. The same assumption also appears in the classic work [1]. In this paper, we mainly focus on solving the second difficulty. We handle the second error of the ZO EG estimates by constructing reasonable recursions. Taking the NC-C setting as an example, our Proposition 6 plays a key role and clarifies that the EG structure can result in the coefficient $\\mathcal{O}(1)$ for $\\mu_2$ and $\\mathcal{O}(\\eta_x^2\\eta_y)$ for $\\mu_1$ (please see the inequality B.130 for detail), which allows us to choose larger smoothing parameters (i.e., $\\mu_1 = \\mathcal{O}(\\epsilon)$ and $\\mu_2 = \\mathcal{O}(\\epsilon)$) than existing methods, thus achieving more robust performance.\n\nSecondly, due to the introduction of EG and proximal operator in our ZO-GDEGA, our first-order analysis framework still faces difficulties. That is, the EG and proximal operator of our algorithm make the analysis framework more difficult. Taking the NC-SC setting as an example, we propose to establish the upper bound on $\\sum_{t=0}^T\\delta_t$ in terms of $\\sum_{i=0}^T||x_i - x_{i+1}||^2$ to construct a recursive relation, thereby achieving competitive complexity and enhanced robustness.\n\nIn summary, there are still many challenges in our ZO theoretical analysis, except for Assumption 3. To address these difficulties, we provide corresponding solutions in our analysis framework. We will also provide a better upper bound for Assumption 3 in our future work.\n\n### **The first-order methods can not be used for the poisoning data attack application**\n\nBecause attackers do not know the internal structure of the model, this application is a black box. Thus, the first-order methods can not access gradient information and are not applicable. We will clarify this in the revised version as well. \n\n[1]  Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization. The Journal of Machine Learning Research, 2022", "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": "", "extra_scores": {}}, {"review_id": "X0K1sbV1Kr", "reviewer": "Reviewer_Rz6B", "summary": "This paper proposes zeroth-order method called ZO-GDEGA to find a near-stationary point for nonconvex-concave minimax optimization, with complexity guarantee. The proposed method is also extended to stochastic setting, being the first work on ZO method on stochastic NC-C problem. The method has weaker requirement on ZO gradient estimate, thus also has better dependency on condition number in the special case of NC-SC. Numerical results on data poisoning attack and AUC maximization show the proposed method is comparable and usually slightly better than compared baselines.", "questions": "1. Please address [Weaknesses 1].\n\n2. Please address [Weaknesses 2].", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. This work designs a unified single-loop ZO method for NC-C minimax, with better complexity and more robust allowance on ZO gradient estimate. The proposed idea of continuous-time dynamics to assist with updates of dual variable and its related analysis is novel. Overall complexity is proposed, with solid and rigorous proof, under weak assumptions such as not requiring lipschitz continuity, more tolerant ZO gradient, which also results in good complexity in the NC-SC special case.\n\n2. The proposed method can be extended to stochastic setting, with first-ever complexity in this case.", "weaknesses": "1. Complexity (deterministic NC-C): The work claims the $O(d\\epsilon^{-6})$ complexity of the proposed method is a 'reduced' complexity, however to the best of my knowledge, this is not the best-known complexity of ZO method on NC-C minimax. Even for single-loop methods, the existing method in [43] shown by table 1 has a better $O(d\\epsilon^{-4})$ complexity. Intuitively, only a complexity as good as this existing $O(d\\epsilon^{-4})$ is near-optimal, because first-order methods on NC-C minimax have $O(\\epsilon^{-4})$ complexity. Although assumption-wise, as this work claims, [43] has the extra assumption of 'decreasing regular parameter sequence', and also requires more accurate ZO gradient on the primal variable, but in my opinion, the extra assumption above is not too restrictive, and requiring more accurate ZO gradient would only cost a constant multiple of queries thus would not affect overall complexity. Therefore, the $O(d\\epsilon^{-6})$ complexity in this work is not good enough, and is in fact worse than certain existing single-loop ZO methods.\n\n2. Complexity (stochastic NC-C): I acknowledge this is the first-ever complexity of ZO method on stochastic NC-C minimax. However, the \n$O(d_x \\epsilon^{-6} + d_y \\epsilon^{-8})$ dependence is not near-optimal, since first-order methods on such problem just have $O( \\epsilon^{-6})$ complexity. ** Update: typo fixed, from $O(d \\epsilon^{-6})$ to $O(\\epsilon^{-6})$.\n\n3. Listed numerical results show the proposed method is similar and generally only slightly better than compared baselines. The difference is not significant in both experiments.\n\n4. Overall, both theoretical complexities and numerical results does not surpass existing methods, thus the contribution may not be strong enough for NeurIPS standard.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful comments! Below we will clarify the three points in the review.\n\n### **Response 1. Complexity (deterministic NC-C)**\n\n$\\bullet$ **Our ZO-GDEGA achieved the reduced complexity.** The key reason for different complexity is different complexity metrics. That is, our method can achieve the complexity of $\\mathcal{O}(\\epsilon^{-6})$ under a more difficult convergence criterion compared with [43]. As we discussed in the tablenote $4$ of Table 1, the work [43] achieved an $\\epsilon$-stationary point of $f$. According to [27, Proposition 4.12] and our Propositions 1 and 2, the $\\epsilon$-stationary point in terms of $f$ is weaker than that of $\\psi$. Thus, [43] found a weaker $\\epsilon$-stationary point with lower gradient complexity. For a fair comparison, we can convert their complexity in terms of $f$ into complexity in terms of $\\psi$, that is, **[43] requires the overall complexity of $\\mathcal{O}((d_x + d_y)\\epsilon^{-8})$ to find an ${\\epsilon}$-stationary point of $\\psi$. In this sense, our ZO-GDEGA algorithm reduced the complexity of existing methods.**\n\n$\\bullet$ **Assumptions.** In addition to satisfying the assumption `decreasing regular parameter sequence', the work [43] requires smaller smoothing parameters (i.e., more accurate ZO gradient) to achieve their gradient complexity. There are two dilemmas. Firstly, the constant multiple of queries may require a lot of experimental verification. Secondly, although satisfactory accuracy ZO gradient can be achieved through constant multiple of queries, smoothing parameters are required to the order of $\\mathcal{O}(\\epsilon^{2})$, which is more sensitive than that of our ZO-GDEGA, which means weaker robustness than our methods. In summary, [43] requires the assumption ``decreasing regular parameter sequence'' and has weaker robustness. In the experiment, we also found that the ZO-AGP [43] is more sensitive to smoothing parameters than our ZO-GDEGA. Please see Fig. C.8 in the Appendix for details.\n\n### **Response 2. Complexity (stochastic NC-C)**\n\nTo the best of our knowledge, the state-of-the-art complexity of the first-order algorithm is $\\mathcal{O}(\\epsilon^{-6})$ [1][2] for solving stochastic NC-C problems, but there is currently no lower bound for ZO algorithms solving stochastic NC-C problems. One of the contributions of this paper is that our ZO-SGDA **firstly** achieves the complexity of $\\mathcal{O}(d_x\\epsilon^{-6} + d_y\\epsilon^{-8})$ in the stochastic NC-C setting. As the complexity of ZO methods is usually $d$ times that of first-order methods [3], there may be a gap for NC minimax problems. We will bridge this gap by recursive momentum variance reduction technology [4] in our future work. \n\n### **Response 3. Significant improvements in theory and experiment**\n\nIn the data poisoning attack experiment, our ZO-GDEGA can reduce the accuracy by about 2\\%-8\\% compared with the baseline, which is a significant improvement. In this experiment, **the lower the accuracy, the better the algorithm performs**. More experimental results and analysis are provided in the Appendix. In summary, our theoretical complexities and numerical results outperform existing methods.\n\n[1] Non-convex min-max optimization: Provable algorithms and applications in machine learning[J]. ArXiv, abs/1810.02060, 2018.\n\n[2] Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems[J]. Advances in Neural Information Processing Systems, 2022, 35: 21668-21681.\n\n[3] Optimal rates for zero-order convex optimization: The power of two function evaluations[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2788-2806.\n\n[4] Momentum-based variance reduction in non-convex sgd[J]. Advances in neural information processing systems, 2019, 32.", "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": "", "extra_scores": {}}, {"review_id": "sodT3xFzO6", "reviewer": "Reviewer_hV36", "summary": "The paper studies zeroth-order methods for nonconvex-(strongly)-concave minimax optimization. The achieved rates improve previous results and tolerate much larger choice of the smoothing parameters. The proposed methods also perform well for some empirical tasks.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Minimax optimization is an important problem that has many applications in machine learning and related areas. In many settings, gradients are hard to estimate or impossible to obtain, which motivates the study of zeroth-order methods. Moreover, nonconvex-concave minimax is itself a class of nonconvex nonsmooth optimization, which is considered as challenge problems in the related literature. The paper proposes new algorithms with improved convergence results compared with previous work for this challenge class of the problem.", "weaknesses": "1. I think a discussion on lower bounds can improve the understanding and position of this work. For example, lower bounds on zeroth-order methods justify the dependence on the dimension is inevitable without additional assumptions [1]. This, together with lower bounds for minimax optimization, e.g., [2], provide lower bounds for the considered problem class, which suggest the foundamental limits of this problem and whether the complexity can be further improved.\n\n2. A discussion of the best known upper bounds for first-order methods could also help. As far as I know, the best rate for first-order nonconvex-concave minimax optimization is also $\\epsilon^{-6}$ [3]. The authors can do some additional literature review and check whether my statement is correct. As the complexity of zeroth-order methods is usually d times that of first-order methods, this suggests the results in this paper match the state-of-the-arts. For nonconvex-strongly-concave minimax optimization, [3] achieves a rate of $\\kappa\\epsilon^{-4}$, which suggests that the upper bounds in this paper can possibly be improved.\n\n3. Have the authors considered to use two-point estimators to construct zeroth-order gradient estiimators? In some cases, two-point estimators give better rates [4]. The paper mentions that for the NC-SC case there is no need to use $z_t$ to update $x_{t+1}$ but $y_t$ instead. However, there is $z_t$ involved in the update of $y_t$. Are there any typos in the statement of the algorithm? Also, I suggest to add dimension in the complexity stated in the abstract. Otherwise, this could be misleading.\n\nI did not have time to carefully check every step in the proof. If the results are correct, I think they make enough contributions to the related literature. Therefore, I will keep a low confidence score.\n\nReferences\n\n[1] Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 2015.\n\n[2] The complexity of nonconvex-strongly-concave minimax optimization. UAI, 2021.\n\n[3] SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems. NeurIPS, 2022.\n\n[4] An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. JMLR, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would to thank the reviewer for the insightful comments! Below we will clarify the four points in the review. \n\n### **Response 1. Lower Bounds.**\n\nWe will add the following discussion about the lower bound to our revised version.\n\nFor minimization problems, the lower bounds on ZO methods justify the dependence on the dimension is inevitable without additional assumptions [1]. For minimax problems, some researchers focus on the lower bound of first-order methods. For example, the lower bounds are $\\Omega(\\epsilon^{-1})$ [2] and $\\widetilde\\Omega(\\kappa)$ [3] for convex-concave and strongly-convex-strongly-concave settings, respectively.  For NC-SC minimax problems, there is a lower bound $\\mathcal{O}(\\sqrt{\\kappa}\\epsilon^{-2})$ of first-order methods [4][5]. Corresponding to minimization optimization [1], there may be a lower bound $\\mathcal{O}((d_x + d_y)\\sqrt{\\kappa}\\epsilon^{-2})$ for ZO minimax optimization. Unfortunately, to the best of our knowledge, there is no work proving a lower bound for ZO algorithms solving NC-SC minimax problems. On the contrary, our work provides the upper bound for ZO algorithms solving NC minimax problems. Thus, more research is needed. \n\n### **Response 2. Upper Bounds.**\n\nFor the NC-C setting, GDA [6], AGDA [7] and GDmax [8, 9] are analyzed to guarantee convergence. To the best of our knowledge,  the best complexity for first-order deterministic NC-C optimization is $\\mathcal{O}(\\epsilon^{-6})$. The works [10, 11] have further extended to the stochastic setting and achieved the complexity matching that of the deterministic setting. For example, SAPD+ [10] achieved the gradient complexity of $\\mathcal{O}(L^3\\epsilon^{-6})$. As the complexity of ZO methods is usually $d$ times that of first-order methods [1], in this sense, it suggests our results $\\mathcal{O}((d_x + d_y)\\epsilon^{-6})$ match the state-of-the-arts in the deterministic setting.\n\nFor the stochastic NC-SC setting, SGDA, SAGDA and SODGA all achieved the gradient complexity of $\\mathcal{O}(\\kappa^3\\epsilon^{-4})$. The works [12][13] reduced the complexity to $\\mathcal{O}(\\kappa^3\\epsilon^{-3})$. Recently, SAPD+ has achievesd a complexity of $\\mathcal{O}(\\kappa\\epsilon^{-4})$, which suggests that the upper bounds in this paper can possibly be improved. Unfortunately, there is no similar conclusion as in [1] for NC minimax problems so far. Moreover, existing ZO methods such as [13][14] mainly focus on trivial extensions of existing first-order algorithms, while this paper focuses on designing ZO minimax algorithms and directly improving the robustness and convergence rate, which is a non-trivial extension. \n\nWe will add the discussion of upper bounds for first-order methods to our revised version.\n\n### **Response 3. Other Questions.**\n\nTo address your concern, we try to analyze our algorithm under two-point estimation, and we find that our algorithm still maintains the advantages of two-point estimation, that is, the second moment of gradient estimate is essentially linear in the dimension $d_x + d_y$. In our revised version, we will clarify this. \n\nUpdating $x_{t+1}$ does not require the intermediate point $\\{z_t\\}$, but the sequence $\\{z_t\\}$ is needed as an intermediate point to update $y$. Thus, this is not a typo. \n\nBesides, we will add dimension to the complexity stated in the abstract of the revised version.\n\n### **Response 4. Our proof is correct.** \n\nAfter our careful inspection, we believe that all our proofs are correct. \n\n[1] Optimal rates for zero-order convex optimization: The power of two function evaluations[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2788-2806.\n\n[2] Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems[J]. Mathematical Programming, 2021, 185(1): 1-35.\n\n[3] On lower iteration complexity bounds for the saddle point problems[J]. arXiv preprint.—2018.—https://arxiv. org/pdf, 1812.\n\n[4] The complexity of nonconvex-strongly-concave minimax optimization[C]//Uncertainty in Artificial Intelligence. PMLR, 2021: 482-492.\n\n[5] Complexity lower bounds for nonconvex-strongly-concave min-max optimization[J]. Advances in Neural Information Processing Systems, 2021, 34: 1792-1804.\n\n[6] On gradient descent ascent for nonconvex-concave minimax problems[C]//International Conference on Machine Learning. PMLR, 2020: 6083-6093.\n\n[7] Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems[J]. SIAM Journal on Optimization, 2023, 33(3): 1884-1913.\n\n[8] Minimax optimization: stable limit points of gradient descent ascent are locally optimal (2019). arXiv preprint arXiv:1902.00618.\n\n[9] What is local optimality in nonconvex nonconcave minimax optimization? In International conference on machine learning, pages  4880–4889. PMLR, 2020.\n\n[10] Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems. Advances in Neural Information Processing  Systems, 35:21668–21681, 2022.\n\n[11] Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 2365–2389. PMLR, 2023.\n\n[12] Stochastic recursive gradient descent ascent for stochastic nonconvex-strongly-concave minimax problems[J]. Advances in Neural Information Processing Systems, 2020, 33: 20566-20577.\n\n[13] Enhanced first and zeroth order variance reduced algorithms for min-max optimization[J]. 2020.\n\n[14] Zeroth-order alternating randomized gradient projection algorithms for general nonconvex-concave minimax problems[J]. arXiv preprint arXiv:2108.00473, 2021.", "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": "", "extra_scores": {}}, {"review_id": "kttiCmB03B", "reviewer": "Reviewer_4438", "summary": "They design a new unified ZO gradient descent extragradient ascent (ZO-GDEGA) algorithm, which reduces the overall complexity to find an ε-stationary point of the function ψ for nonconvex-concave (NC-C) problems. ZO-GDEGA is the first ZO algorithm with complexity guarantees to solve stochastic NC-C problems.", "questions": "See in the Weakness part", "limitations": "None", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical section is very thorough and comprehensive.", "weaknesses": "(1)The paper lacks detailed link of code implementation.\n(2)While the paper effectively addresses the NC-C problem from a theoretical perspective, it should also provide more experimental details and demonstrate that the NC-C problem exists within the experimental models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Response 1. The detailed link of code.** \n\nWe provide the code of the data poisoning attack experiment on the epsilon\\_test dataset. We have sent this code sample as an anonymized link to the AC. We will make our code public.\n\n### **Response 2. The proof of the NC-C problem (5).**\n\nProblem (5) is a NC-C problem which can be proved as follows. \n\nFor Problem (5) (please see the C.1 in the Appendix for detail), we let $\\mathcal{L}(\\delta,w;s_i) = \\frac{1}{1 + e^{-(s_i + \\delta)^\\top w}}$ and $\\mathcal{G}(w):= t_i\\log(\\mathcal{L}(\\delta,w;s_i)) + (1-t_i)(\\log (1 - \\mathcal{L}(\\delta,w;s_i)))$. We prove that the function $\\mathcal{G}(w)$ is general convex as follows. \n$$\\frac{\\partial \\mathcal{G}}{\\partial w} = t_i\\frac{1}{\\mathcal{L}}\\frac{\\partial \\mathcal{L}}{\\partial w} - (1-t_i) \\frac{1}{1-\\mathcal{L}}\\frac{\\partial \\mathcal{L}}{\\partial w} = t_i(1+e^{-(s_i + \\delta)^\\top w})\\frac{(s_i + \\delta)e^{-(s_i + \\delta)^\\top w}}{(1+e^{-(s_i + \\delta)^\\top w})^2} - (1-t_i)\\frac{1 + e^{-(s_i + \\delta)^\\top w}}{e^{-(s_i + \\delta)^\\top w}}\\frac{(s_i + \\delta)e^{-(s_i + \\delta)^\\top w}}{(1+e^{-(s_i + \\delta)^\\top w})^2} $$ $$= t_i\\frac{(s_i + \\delta)e^{-(s_i + \\delta)^\\top w}}{1+e^{-(s_i + \\delta)^\\top w}} - (1-t_i) \\frac{s_i + \\delta}{1+e^{-(s_i + \\delta)^\\top w}} = t_i((s_i + \\delta) - \\frac{s_i + \\delta}{1+e^{-(s_i + \\delta)^\\top w}}) - (1-t_i) \\frac{s_i + \\delta}{1+e^{-(s_i + \\delta)^\\top w}}$$\n$$ = t_i(s_i + \\delta) - \\frac{s_i + \\delta}{1 + e^{-(s_i + \\delta)^\\top w}}.$$ Furthermore, $\\frac{\\partial^2 \\mathcal{G}}{\\partial^2 w} = \\frac{(s_i + \\delta)^2e^{-(s_i + \\delta)^\\top w}}{(1+e^{-(s_i + \\delta)^(s_i + \\delta)^\\top w})^2} \\geq 0$. This Hessian matrix is positively semi-definite. Thus, the function $\\mathcal{G}(w)$ is general convex and $f_1(\\delta, w)$ is general convex w.r.t. $w$. Thus, Problem (5) can be written as the NC-C formula (1) by setting $g(\\cdot)=I_{\\Vert\\delta\\Vert_{\\infty}\\leq r_x}$,  $h(\\cdot) \\equiv 0$, and  $f = -f_1$.\n\nFor more experimental details, please refer to the Appendix, where we describe the selection of hyperparameters and more experimental results and analysis.", "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": "", "extra_scores": {}}, {"review_id": "6f6qR4RJEH", "reviewer": "Reviewer_A7AZ", "summary": "In this paper, a unified single-loop zeroth-order gradient descent extragradient ascent (ZO-GDEGA) algorithm to solve the nonconvex-concave minimax problem faster and more robustly. The theoretical analysis is provided to guarantee an overall complexity of $O(\\epsilon^{-6})$. The experimental results on the data poisoning attack task and the AUC maximization task are shown to validate the practical performance of the proposed method.", "questions": "1. Please see weakness [1]. Can you provide more details to explain how the zeroth-order gradient estimator makes the original analysis of the first-order method more challenging?\n2. Is it possible to further reduce the complexity with respect to $\\epsilon$ for the NC-C problem by integrating variance reduction with the proposed ZO-GDEGA algorithm?", "limitations": "I did not see any negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. In this paper, the authors propose a zeroth-order algorithm that achieves lower complexity under the nonconvex-concave condition.\n2. The first convergence analysis of stochastic zeroth-order algorithm under the nonconvex-concave condition is provided.\n3. For nonconvex strongly-concave problems, the complexity with respect to the condition number is improved.", "weaknesses": "1. In section 2 related work, the complexity of first-order minimax algorithms is not discussed. To my understanding, the error of the zeroth-order gradient can be bounded by parameters $\\mu_1$ and $\\mu_2$ that are set as small as $O(\\epsilon)$. Therefore, the analysis should not change a lot based on the analysis of the first-order counterpart, which probably undermines the novelty and contribution.\n2. In ref [18] (Huang et al 2022), variance reduction is used to improve the complexity with respect to $\\epsilon$. The contribution of this paper will be further stronger if this part is also considered.\n3. The figures in the experiments section is too small and some curves are covered by the legends. I understand the space is limited but maybe some sections could be rearranged to the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful thoughts and comments! Below we will clarify the two points in the review. \n\n### **Response 1.**\n\n**Related works for first-order methods.**\n\nExisting works mainly focus on first-order (FO) methods for solving NC minimax problems. For the NC-SC setting, GDA [1] and AGDA [2] both achieve $\\mathcal{O}(\\kappa^2\\epsilon^{-2})$ ($\\mathcal{O}(\\kappa^3\\epsilon^{-4})$) gradient complexity in deterministic (sochastic) setting to find an $\\epsilon$-stationary point. Lin et.al [3] proposed a multi-loop Minimax-PPA algorithm, which further improves the complexity to $\\mathcal{O}(\\sqrt{\\kappa}\\epsilon^{-2})$. For the NC-C setting, GDA [1] and AGDA [2] both achieve a gradient complexity of $\\mathcal{O}(\\epsilon^{-6})$ and $\\mathcal{O}(\\epsilon^{-8})$ for the deterministic and stochastic settings. SAPD+ [4] has reduced the gradient complexity to $\\mathcal{O}(\\epsilon^{-6})$ for the stochastic setting. The above analysis is all measured with the max function $\\Phi$. Xu et.al [5] considered the $\\epsilon$-stationary point in terms of $f$ and proposed AGP  to achieve a gradient complexity of $\\mathcal{O}(\\epsilon^{-4})$ on this weaker measure, but did not consider the stochastic setting. FO algorithms inspired the design of ZO algorithms. However, existing ZO methods such as [5][6] mainly focus on trivial extensions of existing FO algorithms, while we focus on designing ZO minimax algorithms and directly improving the robustness and convergence rate, which is a non-trivial extension.\n\n**In our main paper, we stated the challenges. To address your concerns about our contributions, we clarify them and improve discussion of challenges as follows.**\n\nWe propose a faster, more robust, and theoretically guaranteed algorithm framework that can solve wider applications.\n\n**Stronger robustness.** We find that the smoothing parameter bounds have a key impact on the ZO algorithms for black-box minimax problems. Previous research did not focus on this key issue. We designed a novel ZO-GDEGA algorithm to weaken restrictions on the smoothing parameters (see Table 1), which enhances the robustness. Our ZO-GDEGA has also been extended to novel FO methods, which are shown in Algorithms 3 and 4 in the Appendix. Thus, our algorithm is a **non-trivial** extension of the existing FO algorithms.\n\n**Lower complexity.** We develop a new and concise analysis framework to prove that our ZO-GDEGA can achieve lower complexity and it is the first ZO algorithm with theoretical guarantees for solving stochastic NC-C problems. \n\n**Analysis of Challenges.** For minimax problems, the errors $||\\hat\\nabla_x f(x,y) - \\nabla_x f(x,y)||$ and $||\\hat\\nabla_y f(x,y) - \\nabla_y f(x,y)||$ are coupled with each other, which leads to difficult parameter selection. Taking the NC-C setting as an example, the recursion $||\\hat x_{t+1} - x_t||$ requires $||\\hat\\nabla_y f(x,y) - \\nabla_y f(x,y)||$ and $\\Delta_t$ requires $||\\hat\\nabla_x f(x,y) - \\nabla_x f(x,y)||$. We handle them by constructing reasonable recursions and step sizes. Our Proposition 6 plays a key role and clarifies that the EG structure can result in the coefficient $\\mathcal{O}(1)$ for $\\mu_2$ and $\\mathcal{O}(\\eta_x^2\\eta_y)$ for $\\mu_1$, which allows to choose reasonable step sizes and larger smoothing parameters than existing methods, thus achieving more robust performance. \n\nEven our analysis for the FO counterpart still faces difficulties due to the EG and the proximal operator. In the NC-SC setting, we propose to establish the upper bound on $\\sum_{t=0}^T\\delta_t$ in terms of $\\sum_{i=0}^T||x_i - x_{i+1}||^2$ to construct the recursive relation of $y$, thereby achieving enhanced robustness. In the NC-C setting, we creatively proposed Proposition 6 to handle the proximal operator and EG structure, thereby resulting in the reasonable recursion w.r.t. $y$.\n\n**Wider applications.** We expand the scope of existing black-box minimax problems by considering more general regularizers rather than being limited to $g=\\mathcal{I_X},f=\\mathcal{I_Y}$, which can be instantiated as data poisoning attack, AUC maximization, and robust neural network training (see C.3 in the Appendix) problems. \n\t\n**Better experimental results.** Our algorithms can find much more effective attack perturbation $\\delta$ and perform more robustly.\n\n### **Response 2.  Integrating variance reduction with the proposed ZO-GDEGA can further reduce the complexity.**\n\nTaking the NC-SC as an example, we provide an idea. We can use the ZO recursive momentum variance-reduced stochastic gradients as follows:\n$$\nu_t = \\alpha_t \\hat\\nabla_x f(x_t, y_t; \\xi)  + (1-\\alpha_t)(\\hat\\nabla_x f(x_t, y_t;\\xi) - \\hat\\nabla_x f(x_{t-1}, y_{t-1}; \\xi) + u_{t-1}),\n$$ to update $x$, as well as $y$, where $\\alpha_t \\in (0, 1]$. When $\\alpha_t = 1$, $u_t$ will degenerate a vanilla ZO stochastic gradients. In theoretical analysis, since STORM's analysis [7] can effectively reduce the complexity with respect to $\\epsilon$, we can refer to their analysis and design Lyapunov function $\\phi = f(x_t, y_t) + \\mathcal{O}(\\frac{1}{L^2\\eta_x})||u_t - \\nabla_x f(x_t,y_t)||^2 + \\mathcal{O}(\\frac{1}{L^2\\eta_y})||v_t - \\nabla_y f(x_t,y_t)||^2$ to analyze the complexity, and thus the complexity can be reduced. As for the NC-C setting, we will also think about how to design Lyapunov functions to analyze complexity.\n\nWe will rearrange tables and figures in our revised version.\n\n[1] On gradient descent ascent for nonconvex-concave minimax problems\n\n[2] Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems[J]\n\n[3] Near-optimal algorithms for minimax optimization\n\n[4] Sapd+: An accelerated stochastic method for nonconvex-concave minimax problems. \n\n[5] DERIVATIVE-FREE ALTERNATING PROJECTION ALGORITHMS FOR GENERAL NONCONVEX-CONCAVE MINIMAX PROBLEMS\n\n[6] Enhanced first and zeroth order variance reduced algorithms for min-max optimization[J]. 2020.\n\n[7] Momentum-based variance reduction in non-convex sgd", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for the detailed reviews.  We were asked by the reviewer 4438 to provide code. Our code can be available at the link https://anonymous.4open.science/r/ZO-GDEGA-2F6E

Meta-review: The paper introduces a Zeroth-Order Gradient Descent Extragradient Ascent (ZO-GDEGA) algorithm, which is designed to solve nonconvex-concave (NC-C) minimax optimization problems. The proposed algorithm has iteration complexity of  O(epsilon^-6) to find ϵ-stationary point.  The algorithm requires weaker conditions on zeroth-order gradient estimations compared to previous methods, offering a more broad/robust theoretical result. It also shows advantages in the nonconvex-strongly concave (NC-SC) case. Experimentally, the paper validates the the performance of ZO-GDEGA through numerical experiments on data poisoning attacks and AUC maximization. 

The reviewers found the theoretical analysis rigorous and in line with the claims of the paper.  The reviewers also appreciate the relaxed conditions required for applying the theoretical analysis. The experiments are found in line with the message of the paper, demonstrating the relevance of the theory in practical scenarios discussed. As noted by some of the reviewers, the improvements over [43] needs further discussion. I encourage the authors to clarify this improvement further as mentioned in their response (You can use [27, Proposition 4.12] or a a clear version of it with more discussions in arxiv 2002.07919). The reviewers also noted that the paper can improve by including discussions on lower bounds and connections to first-order methods.
Decision: Accept (poster)