Robust and Faster Zeroth-Order Minimax Optimization: Complexity and Applications

Authors: weixin  an
yuanyuan  liu
fanhua  shang
hongying  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 05:24:51

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.

Main paper: 
 introduction: 
 We mainly consider a general regularized minimax problem:EQUATIONwhere f : R dx×dy → R is nonconvex in x, concave in y and ℓ-smooth, g : R dx → R and h : R dy → R are convex but maybe nonsmooth functions. The problem (1) appears in many scenarios of machine learning, such as adversarial attack to regularized deep neural networks, regularized fair learning, and robust training [7, 13] . In this paper, we focus on the black-box setting of Problem (1) , where the gradients are estimated by only functional values.In the black-box setting, some evolutionary algorithms such as [46] have achieved good performance. However, they usually lack complexity analysis and may never converge to a solution due to pathological 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] .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 [54] with the ReLU activation and generating poisoning data to evaluate the black-box models [22, 33, 61] . In these scenarios, ZO algorithms become one of the best choices. For example, [33] proposed ZO-Min-Max for solving NC-strongly concave (NC-SC) data poisoning attack problems.More practically, it is desired to solve Problem (1) 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 (1) , which motivates us to fill this gap. Thus, we summarize our motivations as follows:• Can we design a ZO algorithm to achieve a 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 a new stochastic ZO algorithm with theoretical guarantees?Table 1 : Comparison of the overall ZO oracle complexity of single-loop algorithms to find an ϵ-stationary point of f (Definition 3) or ψ (Definition 2). κ = ℓ/µ denotes the condition number, d = dx + dy and O(•) hides logarithmic terms. Abbreviation: Settings (Set.), Algorithms (Algs.), Regular (Reg.), Theorem (The.).Set. Algs. f /ψ Reg. 1 1 About the column "Reg.", we transform Problem (1) into three models by setting different regularizers g and h: (i) When g and h are both 0, Problem (1) is transformed into minx maxy Ψ(x, y) = f (x, y). (ii) When g = IX (•) and h = IY (•), where IC is the indicator function of the convex compact set C, Problem (1) is transformed into minx∈X maxy∈Y Ψ(x, y) = f (x, y). (iii) When g = IX (•) and h = ∥y∥1, Problem (1) is transformed into minx∈X maxy Ψ(x, y) = f (x, y) -α∥y∥1. 2 Larger smoothing parameters µ1 and µ2 imply that algorithms can tolerate rougher ZO estimations, which means stronger robustness. In some cases, robustness has a greater impact on algorithm performance than overall complexity, as shown in Table 2 below. 3 For NC-C problems, [50, 51] depend on an extra monotonically decreasing regular parameter sequence and [50] also depends on Assumption 5. Our Theorem 2 does not depend on these assumptions. 4 The work [51] only achieves an ϵ-stationary point of f . According to [31, Proposition 4 .12] and our analysis, [51] requires the overall complexity of O((dx + dy)ϵ -8 ) to find an ϵ-stationary point of ψ.µ 1 , µ 2 2 Deterministic Stochastic NC - C 3 [50] f I X , I Y O(d -1 x ϵ 2 ), O(d -1 y ϵ 3 ) O(d x ϵ -8 +d y ϵ -10 ) Unknown [51] f I X , I Y O(d -0.5 x ϵ 2 ), O(d -0.5 y ϵ) O(dϵ -4 ) Unknown ψ O(d -1 x ϵ 4 ), O(d -1 y ϵ 2 ) O(dϵ -8 ) 4 Unknown The. 2 ψ g, h O(d -1 x ϵ), O(d -1 y ϵ 2 ) O(dϵOur contributions. In this paper, we propose a 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 (1) faster and more robustly. Specifically, we introduce the idea of continuous-time dynamics to assist in 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 a generalized ϵ-stationary point of the function ψ to O((d x + d y )ϵ -6 ), even without the Lipschitz continuity assumption, as shown in Table 1 .• To the best of our knowledge, the stochastic ZO-GDEGA is the first ZO stochastic algorithm with theoretical guarantees for solving NC-C problems, which for the first time finds a generalized ϵ-stationary point of ψ with an overall complexity of O(d x ϵ -6 + d y ϵ -8 ), as shown in • Our ZO-GDEGA algorithm is more tolerant to the ZO estimations. Specifically, ZO-GDEGA allows a larger tolerance O(ϵ) for smoothness parameters µ 1 and µ 2 compared with existing methods, as shown in Table 1 , which enhances the robustness of ZO algorithms.• As a by-product, ZO-GDEGA applied to NC-SC problems can obtain competitive complexity results O(κ 2 (d x + d y )ϵ -2 ) and O(κ 2 (d x + κd y )ϵ -4 ) 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.9% 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. 
preliminaries and related work: 
 This section provides several notations and definitions, and discusses some related works.∥ • ∥ and ∥ • ∥ 1 denote the ℓ 2 -norm and ℓ 1 -norm of a vector, respectively. ∥ • ∥ ∞ denotes the ℓ ∞ -norm of a vector, i.e., ∥x∥ ∞ = max 1≤i≤dx |x i |. We denote a = O(b) if a ≤ Cb for some constant C > 0, any subgradient of g(•) at x by ∂g(x), a ZO estimator of f (•) at x by ∇f (x) for the gradient ∇f (x), the regularized coupling function by Γ(x, y) := f (x, y) -h(y), the max function by Φ(x) := max y {f (x, y) -h(y)} and the regularized max function by ψ(x):= g(x) + Φ(x). Definition 1. The function f (•, •) is ℓ-smooth, i.e., ∥∇f (x, y) -∇f (x ′ , y ′ )∥ ≤ ℓ∥(x, y) -(x ′ , y ′ )∥.ZO algorithms for nonconvex minimax optimization. For solving NC-SC minimax problems, some single-loop ZO algorithms have been presented. For example, [33] proposed the ZO-Min-Max by integrating alternating stochastic Gradient Descent Ascent (GDA) method and ZO estimators, which finds an ϵ-stationary point with the overall complexity O(κ 6 dϵ -6 ), when g(x) = I X (x) and h(y) = I Y (y). [47] proposed the ZO-GDA for solving the deterministic problem (1) with g(x) ≡ 0 and h(y) = I Y (y), and the ZO overall oracle complexity is bounded by O(κ 5 dϵ -2 ). Its stochastic variant, ZO-SGDA, can achieve the overall ZO oracle complexity O(κ 5 dϵ -4 ). 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 1 , which affects their performance, as shown in Table 2 .As for NC-C problems, to the best of our knowledge, the only work proposed in [50] designs a ZO-AGP algorithm with the ZO oracle complexity O(d x ϵ -8 +d y ϵ -10 ), but it only considers the deterministic setting when g(x) = I X (x), h(y) = I 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, a new version of ZO-AGP [51] 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 ψ, as shown in Table 1 , while our analysis is in terms of ψ 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 t to find an intermediate point x t+1/2 and then uses the gradient at x t+1/2 to determine the next iteration point x t+1 . Specifically, at iteration t,EQUATIONwhere prox g γ (x) ≜ arg min z {g(z) + 1 2γ ∥z -x∥ 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 [31, 55] , many works have shown the advantages of the first-order (FO) EG structure, such as handling noisy gradients in the convex-concave [26, 1] and NC-SC(C) [35] settings, but there is no insight into the ZO 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 an approximation of the more robust backward-Euler discretization [18] , whereas gradient descent is a variant of the classical forward-Euler discretization [9] . Based on the two facts above, we aim to explore the performance of the EG structure in ZO minimax optimization to improve both theoretical and practical performance for solving the black-box problem (1) .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 Ω(ϵ -1 ) [41] and Ω(κ) [58] for convex-concave (C-C) and SC-SC settings, respectively. For NC-SC problems, there is also a lower bound for the FO setting [59, 30] . But to the best of our knowledge, there is no work proving a 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.Upper bounds for minimax optimization. For the NC-C setting, GDA [31] , Alternating GDA (AGDA) [4] and GDmax [25, 25] are analyzed to guarantee convergence. So far, the best complexity bound for FO deterministic NC-C problems is O(ϵ -6 ). The works [60, 20] have further extended to the stochastic setting. For example, SAPD+ [60] achieved the complexity bound of O(ϵ -6 ), which matches that of the deterministic case. For the NC-SC setting, the works [34, 49] proved the advanced bound of O(κ 3 ϵ -3 ). SAPD+ achieved another advanced complexity bound of O(κϵ -4 ).In minimizing optimization, the complexity of ZO methods is usually d times that of corresponding FO methods [12] . In this sense, our results match the upper bound in the deterministic NC-C setting. Unfortunately, there is no 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 to directly improve performance.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 are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
zo-gdega for nc-c problems: 
 In this section, we design a unified single-loop ZO gradient descent extragradient ascent (ZO-GDEGA) algorithm for solving the NC-C problem (1) . The following assumptions are made for our analysis throughout this section. Assumption 1. We assume f (x, •) is concave for a given x. Assumption 2. [4] The regularizers g and h are proper, convex and lower semicontinuous.1. Additionally, g is either L g -Lipschitz continuous on its domain, which is assumed to be open, or the indicator of a nonempty, convex and closed set. Either of those assumptions guarantees the boundEQUATIONholds for any γ > 0 and all x ∈ dom g (in the case of the indicator the statement is trivially true).2. Furthermore, h has a bounded domain dom h such that the diameter of dom h is bounded by D h .Similar to [4] , we also use the extension of the classical Danskin's theorem based on Assumptions 1 and 2 to guarantee that the solution setY * (x) := y * |y * ∈ arg max y {f (x, y) -h(y)} is non- empty for ∀x ∈ R dx and Φ(x) is ℓ-weakly convex.Based on these facts, we propose and analyze our ZO-GDEGA algorithm for solving the NC-C problem (1) in deterministic and stochastic settings.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 (1). Our algorithms are single-loop and more easily scalable compared to nested-loop algorithms such as [32] .ZO randomized gradient estimators. We introduce the ZO randomized gradient estimators as follows:∇x f (x, y) = 1 q1 q1 i=1 dx(f (x+µ1ui,y)-f (x,y)) µ1 u i , ∇y f (x, y) = 1 q2 q2 i=1 dy(f (x,y+µ2vi)-f (x,y)) µ2 v i , where {u i } q1i=1 ⊆ R dx and {v i } q2 i=1 ⊆ R dy are i.i.d. random direction vectors drawn uniformly from the unit Euclidean spheres, respectively. µ 1 and µ 2 are smoothing parameters, the conditions on which are strict in existing algorithms such as [51] , while our algorithms allow them to be O(ϵ), as shown in Table 1 . The randomness caused by vectors u i and v i is coupled in the alternating updates of x and y and undoubtedly increases the difficulty of complexity analysis. We introduce two smooth functionsf µ1 (x, y) = E u [f (x + µ 1 u, y)] and f µ2 (x, y) = E v [f (x, y + µ 2 v)]to bridge the ZO estimators and the FO gradient, thereby assisting in complexity analysis as shown in Fig. 1 .Initialize: x 0 , z 0 = y 0 , step sizes η x and η y .1:for t = 0, 1, . . . , T -1 do 2: ∇x F (x t ) = ∇x f (x t , z t ) for NC-C case; ∇x f (x t , y t ) for NC-SC case; ; x t+1 = prox g ηx (x t -η x ∇x F (x t )); 3:z t+1 = prox h ηy (y t + η y ∇y f (x t , y t )); y t+1 = prox h ηy (y t + η y ∇y f (x t+1 , z t+1 )); 4: end for 5: Randomly draw x from x 1 , . . . , x T at uniform. Output: x.To improve performance, we integrate the EG structure and the ZO randomized gradient estimators, and propose the ZO-GDEGA algorithm. Specifically, it contains a proximal gradient descent step and two proximal gradient ascent steps, as shown in Algorithm 1.Algorithm 1 updates x by minimizing the following linearized approximation,EQUATIONwhere z t is an auxiliary variable and its update rule is given later. Our design for updating x t+1 relies only on the previous point x t , and does not require x t+1/2 as in the standard EG method (2).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, we integrate it into the update of y, which guides a new high-level idea from the continuous-time dynamic perspective.A high-level idea. Here we show an intuition for the advantages of our algorithm. If h is "simple", in the sense that the proximal operator has a closed-form solution [6] . Without loss of generality, we consider the case of h(y) ≡ 0. 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 of the stochastic continuoustime dynamic Ẏ (t) = ∇y f (X, Y (t)) with the limit η y → 0. To get more robust and accurate solutions, we use the backward-Euler instead of forward-Euler discretization to solve this dynamic. An exact backward-Euler step implies the discretization y t+1 = y t + η y ∇y f (x t+1 , y t+1 ), but obtaining y t+1 in such a manner could be computationally prohibitive. Instead, we opt for an extra gradient ascent step z t+1 = y t + η y ∇y f (x t , y t ) to first approximate y t+1 once as shown in the 3 rd line of Algorithm 1, which can be viewed as a "trial" step. Then, we use the ZO oracle at point (x t+1 , z t+1 ) to approximate one-step backward-Euler discretization as shown in the end of the 3 rd line, which is one of the reasons why our ZO-GDEGA algorithm is more robust than [51] .Compared with existing works, our 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 O(ϵ), whereas existing ZO algorithms have stricter restrictions on smoothness parameters such as O(ϵ 4 ) as shown in Table 1 , which is the fundamental reason why ZO-GDEGA improves the robustness. Specific proofs and experimental verifications are in subsequent sections.• Lower per-iteration complexity. Compared with the standard EG method [35] , Algorithm 1 only uses the EG structure for the update of y 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 ZO case, the FO variant of Algorithm 1 is shown in the Appendix.• More extensive applications. The proximal operators generalize the projection operators in existing works such as [51] . Compared with [21] , our ZO-GDEGA does not require additional compactness of the domains, which significantly extend the applicability.We consider that f is a stochastic function on a distribution D, i.e., f (x, y) := E ξ∼D f (x, y; ξ), and we can only access the stochastic function values f (x, y; ξ). In this case, we introduce the stochastic version of ZO estimators: ∇x f (x, y;I 1 ) = 1 b1 b1 j=1 ∇x f (x, y; ζ j ) = 1 b1 b1 j=1 f (x+µ1uj ,y;ζj )-f (x,y;ζj ) µ1/dx u jas well as ∇y f (x, y; I 2 ), where I 1 = {ζ j } b1 j=1 , I 2 = {ξ j } b2 j=1 denote mini-batch sets of b 1 and b 2 i.i.d. samples. According to [19] ,E U,I1 [ ∇x f (x, y; I 1 )] = ∇ x f µ1 (x, y) and E V,I2 [ ∇y f (x, y; I 2 )] = ∇ y f µ2 (x, y) with U = {u i } b1 i=1 and V = {v i } b2i=1 , and we need the common Assumptions 3, 6 and 7 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 are bounded, i.e.,E u,ζ ∥ ∇x f (x, y; ζ) - ∇ x f µ1 (x, y)∥ 2 ≤ σ 2 1 , E v,ξ ∥ ∇y f (x, y; ξ) -∇ y f µ2 (x, y)∥ 2 ≤ σ 2 1 .Based on the above analysis and Algorithm 1, we design a stochastic variant of ZO-GDEGA, as shown in Algorithm 2 in the Appendix. The main difference between Algorithms 2 and 1 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 5.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 1 and 2. We design and analyze them based on Assumption 4. Assumption 4. We assume f (x, •) is µ-strongly concave in y for a given x. Moreover, the regularizers g and h are proper, convex and lower semicontinuous.Based on Assumption 4, we know that the max function Φ(x) is (κ+1)ℓ-smooth, where κ = ℓ/µ ≥ 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 as follows:• Due to the strong concavity, there is no need to use the intermediate point z t to update x t+1 , but directly use the ZO estimators at the point (x t , y t ) to accelerate updating, which contributes to achieve competitive complexity under weaker restrictions on µ 1 and µ 2 , thereby enhancing robustness.• The solution set Y * (x) is a singleton, which consists of a single element y * (x), thus we can use the quantity δ t := ∥y t -y * (x t )∥2 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 ZO algorithms. Next, we rigorously analyze its complexity. 
theoretical analysis: 
 In this section, we first define two types of generalized ϵ-stationary points as termination criteria. Then, we provide the complexity results of our ZO-GDEGA to find an ϵ-stationary point.We generalize two classical definitions of ϵ-stationary point in [31] and [32] as follows. Definition 2. In the NC-C setting, a point x is an ϵ-stationary point of an ℓ-weakly convex function ψ if its Moreau envelope 2 ψ 1/2ℓ (x) satisfies ∥∇ψ 1/2ℓ (x)∥ ≤ ϵ; In the NC-SC setting, a point x is an ϵ-stationary point of a function ψ if dist(0, ∂ψ(x)) ≤ ϵ. Definition 3. A pair of points (x, y) is an ϵ-stationary point of the coupling function f if we have∥G(x, y)∥ ≤ ϵ, where G(x, y) = ℓ[x -prox g 1/ℓ (x -(1/ℓ)∇ x f (x, y))] ℓ[y -prox h 1/ℓ (y + (1/ℓ)∇ y f (x, y))].Based Thus, we can draw a similar conclusion as in [31] : The ϵ-stationary point definition of ψ is stronger than that of f . To obtain tighter complexity bounds, we analyze ZO algorithms for the first time based on ϵ-stationary point definition of ψ (i.e., Definition 2).We first analyze the complexity of ZO-GDEGA for the NC-SC setting in deterministic and stochastic cases. Our analysis is a non-trivial extension of the proofs in [31] due to the following challenges.T t=0 δ t 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 T t=0 δ t in terms of T i=0 ∥x i -x i+1 ∥ 2 (see the Appendix for details), which also reduces the overall complexity's dependence on κ, and results in the coefficients of µ 2 1 and µ 2 2 being only O(1) and O(κ), thereby weakening their dependence on κ and enhancing robustness. Here we directly give the complexity results.Theorem 1. We choose stepsizes η x ≤ 1 256κ 2 ℓ , η y = 1 2ℓ , µ 1 = O(d -1x ϵ) and µ 2 = O(κ -1/2 d -1 y ϵ). Under Assumption 4, our ZO-GDEGA can find an ϵ-stationary point in terms of Definition 2, i.e., min 1≤t≤T dist(-∂g(x t ), ∇Φ(x t )) ≤ ϵ, with the overall ZO oracle complexity O(κ 2 (d x + d y )ϵ -2 ) for deterministic and O(κ 2 (d x + κd y )ϵ -4 ) for stochastic settings.Theorem 1 shows that ZO-GDEGA allows for larger µ 1 and µ 2 than compared algorithms (see Table 1 ), which means that our algorithms can tolerate rougher ZO estimations. Besides, our complexity bounds have the weaker κ dependence than them. Thus, even our by-products have some advantages. Moreover, this analysis also builds a bridge for analyzing the NC-C setting.In this part, we analyze ZO-GDEGA in the NC-C setting. We provides two perspectives: continuityagnostic (more relaxed condition) and continuity-dependent (better bound) analysis.We first analyze the complexity for the NC-C setting based on Theorem 1 and smooth technology in [38] . By adding a smoothing term, we approximate the NC-C problem (1) with the following NC-SC model: min x max y { Ψ(x, y) = g(x) + f (x, y) -h(y)}, where f (x, y) = f (x, y) -μ 2 ∥y -ŷ∥ 2 and given arbitrary ŷ ∈ dom h. Based on Theorem 1 and careful selection of μ, Theorem 2 ensures that ZO-GDEGA can find an ϵ-stationary point for the NC-C problem (1). Theorem 2. Under Assumptions 1 and 2, our ZO-GDEGA applied to the approximate NC-SC model with μ = O(ϵ 2 /(ℓD 2 h )), can guarantee to generate an ϵ-stationary point x ϵ for the NC-C problem (1), i.e., E∥∇ψ 1/2ℓ (x ϵ )∥ ≤ ϵ, with overall complexity O((d x + d y )ϵ -6 ) and O(d x ϵ -8 + d y ϵ -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 at least one of them. Besides, Theorem 2 inherits the advantages of our analysis for Theorem 1, i.e., enhancing robustness and reducing complexity.We also analyze our ZO-GDEGA algorithm for solving the NC-C problem (1) under the Lipschitz continuity assumption, which is common in NC-C optimization such as [31, 35, 43, 4] .Assumption 5 (Continuity). f (x, y) is G-Lipschitz continuous in x, i.e., for ∀y ∈ dom h, ∀x, x ′ ∈ R dx satisfies that ∥f (x, y) -f (x ′ , y)∥ ≤ G∥x -x ′ ∥.In the case of (ii) in Table 1 , Assumption 5 follows immediately by the smoothness and choosing G = ℓ(D X + D Y ) + ∥∇ x f (x ϵ , y ϵ )∥, where max x,x ′ ∈X ∥x -x ′ ∥ ≤ D X and max y,y ′ ∈Y ∥y -y ′ ∥ ≤ D Y . Thus, ZO-GDEGA still work without Assumption 5 in this case. For the general problem (1), we use G for generalization and give a proof sketch. Detailed proofs are provided in the Appendix.Proof sketch. We first analyze the recursive relationship between the Moreau envelopes ψ 1/2ℓ (x t ) and ψ 1/2ℓ (x t+1 ) based on the ZO gradient descent step. Then, we estimate the tricky error term ∆ t = Φ(x t ) -Γ(x t , z t ) to 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 (1) . In deterministic and stochastic settings, we provide tighter results than Theorem 2, respectively. ( , ) ( , )x t t x t t f x y f x y - - ∇ -∇Our ZO-GDEGA First-order EG (Mahdavinia et al., 2022)EQUATION) -𝑓𝑓(𝑥𝑥EQUATION) Deterministic Setting. Lemma B.13 provides the recursive relationship between ψ 1/2ℓ (x t+1 ) and ψ 1/2ℓ (x t ). Our algorithms use more concise ZO estimation gradient descent step instead of EG structure to update x. Thus, the tricky term ∥∇ x f (x t , y t ) -∇ x f (x t-1 , y t-1 )∥ 2 can be removed in our analysis compared with the standard EG method in [35] as shown in Fig. 1 . Lemma B.15 proves that T t=0 E[∆ t ] can be well controlled by carefully choosing η y . More importantly, our analysis makes the coefficients of µ 2 1 and µ 2 2 independent of ϵ, which eases their dependence on ϵ compared with [51] , thereby enhancing the robustness. Now, we begin to provide tighter results. Theorem 3. Under Assumptions 1, 2 and 5, ifΔ 𝑡𝑡+1 = 𝛻 𝑥𝑥 𝑡𝑡+1 -Γ(𝑥𝑥 𝑡𝑡+1 , 𝑧𝑧 𝑡𝑡+1 ) ˆ( , ) y f x y ∇ 2 ( , ) y f x y µ ∇ ( , ) y f x y ∇ ˆ( , ) x f x y ∇ 1 ( , ) x f x y µ ∇ ( , ) x f x y ∇q 1 = d x , q 2 = d y , η y = 1/( √ 3ℓ), η x = O(ϵ 4 ), µ 1 = O( ϵ √ dx ) and µ 2 = O( ϵ √ dy), our deterministic ZO-GDEGA can find an ϵ-stationary point of ψ, i.e., Theorem 3 shows that our ZO-GDEGA achieves the same overall complexity as Theorem 2 and further weakens the constraints on smoothing parameters under the continuity assumption. Note that ZO-GDEGA is the first ZO algorithm with convergence guarantees to find an ϵ-stationary point of ψ. 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 shows that the overall complexity can be further reduced, and we can still choose µ 1 and µ 2 to be O(ϵ) 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: https://github.com/Weixin-An/ZO-GDEGA.Data poisoning attack is one of the most common black-box attack methods [29, 42] . The purpose of the attacker is: when the model parameter w is well-trained, adding a perturbation δ on the training data that makes the loss functions as large as possible, and then such poisoned training data (s i + δ, t i ) will reduce the model accuracy. Therefore, it is usually required for attackers to optimize the following objective function,EQUATIONwhere D tr ≜ D tr,p ∪ D tr,c denotes the training dataset including n i.i.d samples, D tr,p and D tr,c denote the poisoned and clean subsets of D tr , respectively. We choose the cross-entropy loss to optimize δ and w. Note that Problem (5) can be rewritten as the NC-C (1) by setting g(•) = I ∥δ∥∞≤rx (•), h(•) ≡ 0, and f = -f 1 . Therefore, it can be solved by our ZO-GDEGA algorithm.Datasets. We validate ZO-GDEGA on a synthetic dataset and the epsilon_test dataset.• Synthetic datasets: We generate a dataset D = {s i , t i } 2,000 i=1 with feature vector s i ∈ R 100 from Gaussian distribution N (0, I) and split it into 70% training and 30% test samples. The labelt i = 1 if 1/(1 + e -(s ⊤ i w * +ni) ) > 0.5, otherwise t i = 0, where n i ∈ N (0, 10 -3) is random noise, and we set w * = 1 as the ground truth.• The epsilon_test dataset3 : It contains 100,000 samples of 2,000 dimensions, and we also split it into 70% training samples and 30% testing samples. 5) is ZO-AGP. Note that here we replace the ZO estimators in deterministic ZO-AGP with corresponding stochastic versions and choose the same hyperparameter settings for a fair comparison.Results. We use the poisoned data generated by the baselines and our ZO-GDEGA to attack the training procedure of the logistic regression model, and the experimental results on the synthetic and epsilon_test datasets are shown in Figs. 2 and 3 , 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 ZO-GDEGA can converge faster than baselines in terms of stationary gap and objective value -f 1 . From the training accuracy subfigure, both our ZO-GDEGA and the baselines (black-box attack) converge, and achieve nearoptimal 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 of 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. 3 , we observe that ZO-GDEGA algorithm also performs about 8.0% lower than ZO-AGP on the epsilon_test dataset, which further verifies the superiority of our algorithm in the large-scale real-world datasets.AUC is defined as the area under the ROC curve, which is a performance indicator to measure the pros and cons of a 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:EQUATIONwhere r x and r y are the radius of the projection balls, s = (s, t) is drawn independently from the distribution P, and f (θ, a, b, v; s) is defined as in [53] . When we choose the multilayer perception (MLP) model, Problem (6) becomes a NC-SC problem. The non-differentiable point of the nonlinear function such as ReLU causes some non-differentiable modules of the classifier, and the ZO algorithms 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. We conduct experiments on the MNIST, Fashion-MNIST and ijcnn1 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 [47] , ZO-Min-Max [33] , Acc-ZOMDA [19] and our ZO-GDEGA to solve Problem (6) with Leaky ReLU. We choose a two-layer MLP as the classification model, and set mini-batch b 1 = b 2 = 256, q 1 = q 2 = 10, r x = r y = 2 and step sizes η x = η y = 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 2 . It shows that at small µ 1 and µ 2 , our ZO-GDEGA algorithms perform competitively compared with the baselines. At larger µ 1 and µ 2 , 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. 
conclusions and future work: 
 In this paper, we proposed a unified ZO-GDEGA 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. In the future, we will extend our algorithm to non-smooth and federated learning settings as in [45, 44] . Guidelines: 
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 a 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 a result we did not discuss it.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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 in the package should be provided. For popular datasets, paperswithcode.com/datasets 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. 
 
 Appendix: • 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.ψ 1/2ℓ (x) is the Moreau envelope of ψ(x) if ψ 1/2ℓ (x) = minw{ψ(w) + ℓ∥w -x∥ 2 } for each x ∈ R dx .https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/ 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
This 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.
questions: 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: limitations: This paper is mostly a theoretical work, no negative societal impact may result in.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. Complexity (stochastic NC-C): I acknowledge this is the first-ever complexity of ZO method on stochastic NC-C minimax. However, the 
$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})$.

3. 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.

4. Overall, both theoretical complexities and numerical results does not surpass existing methods, thus the contribution may not be strong enough for NeurIPS standard.
questions: questions: 1. Please address [Weaknesses 1].

2. Please address [Weaknesses 2].
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.

3. 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.

I 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.

References

[1] Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 2015.

[2] The complexity of nonconvex-strongly-concave minimax optimization. UAI, 2021.

[3] SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems. NeurIPS, 2022.

[4] An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. JMLR, 2017.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: (1)The paper lacks detailed link of code implementation.
(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.
questions: questions: See in the Weakness part
limitations: limitations: None
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: 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?
2. 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: limitations: I did not see any negative societal impact.

Comments: title: Response to authors
Official Comment by Reviewer A7AZ
Response to authors
comment: We appreciate your review and valuable questions that improved our work.
We appreciate your review and valuable questions that improved our work.
We appreciate your review and valuable questions that improved our work.
We appreciate your review and valuable questions that improved our work.
We appreciate your review and valuable questions that improved our work.
Thanks for the detailed responses. I agree the proposed methods improves the complexities compared to existing zeroth-order methods, and that is good. My point of weakness, which still holds, was that the proposed complexities are not tight, worse than d * first-order complexities; where existing first-order methods have $\epsilon^{-4}$ complexity for deterministic NC-C and $\epsilon^{-6}$ complexity for stochastic NC-C. I hope the authors understand this point, and potentially tighten those zeroth-order bounds in future works.
With that being said, I carefully read the detailed analysis and additional experiments in the appendix, which made good efforts in making the theory and experiments comprehensive, and the analysis is nontrivial. Thus, I have increased my score from 5 to 6.
Thank you very much for the reply. After reading the rebuttal, I think my concerns are addressed and I have raised my rating to 6.
Thanks for your comments again. We will add the above valuable discussions in our revised version. **We try again to address the weaknesses you mentioned. We further clarified our contributions, and stated our challenges**.

### **Addressed the weakness**

**Deterministic NC-C.** Under the complexity metric $\psi$, the state-of-the-art gradient complexity is $\mathcal{O}(\epsilon^{-6})$ in the deterministic setting [27]. Thus, our ZO-GDEGA achieves the near-optimal gradient complexity $\mathcal{O}(d_x + d_y)\epsilon^{-6}$ in terms of metric $\psi$. As a comparison, [43] achieves the gradient complexity $\mathcal{O}(d_x + d_y)\epsilon^{-8}$ in terms of metric $\psi$. In this sense, our ZO-GDEGA is near-optimal and achieved the 'reduced' complexity.

**Stochastic NC-C.** One of our main contributions is that we **first** provide the provable complexity framework in the stochastic NC-C setting. Although near-optimal complexity may not (because to the best of our knowledge, no work proves that the complexity $\mathcal{O}(d\epsilon^{-6})$ can be achieved) be reached, our analysis opens the door to analyzing the ZO NC-C setting.

### **Our contributions**

We propose a faster, more robust, and theoretically guaranteed algorithm framework that can solve wider minimax applications.

**Stronger robustness.** Developing a ZO minimax algorithm for stronger robustness is challenging, as existing ZO algorithms require a demanding ZO estimate of the gradients, i.e., very small (e.g., $\mathcal{O}(\epsilon^{-3})$ [18] [42], $\mathcal{O}(\epsilon^{-2})$ [43]) smoothing parameters. We find that the smoothing parameter bounds have a key impact on the ZO algorithms for black-box minimax problems, which is shown in C.1.2 in the Appendix. 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) and offer the first provable guarantee. 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 algorithms.

**Lower complexity.** We develop a new and concise analysis framework to prove that our ZO-GDEGA can achieve lower complexity under the same complexity metrics. It is the **first** ZO algorithm with theoretical guarantees for solving stochastic NC-C problems. **Algorithms without theoretical guarantees are unstable and untrustworthy**. The stochastic version of ZO-AGP [5] has no provable complexity guarantees. Specifically, in the proof of deterministic ZO-AGP, some parameters are severely coupled, and the stochastic setting will further complicate its analysis, while our proof framework can be easily extended to the stochastic setting.

**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$ and $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.

**Better experimental results.** Our algorithms can find much more effective attack perturbation $\delta$ and perform more robustly.

### **Analysis of Challenges**

We propose a novel complexity analysis framework for ZO minimax optimization. For minimax problems, the errors $||\hat\nabla_x f(x,y;\zeta) - \nabla_x f(x,y)||$ and $||\hat\nabla_y f(x,y;\xi) - \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 the error $||\hat\nabla_y f(x,y;\xi) - \nabla_y f(x,y)||$ and $\Delta_t$ requires the error $||\hat\nabla_x f(x,y;\zeta) - \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.

Even 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$ in **Lemma B.9**, 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$.

[5] Derivative-free alternating projection 490 algorithms for general nonconvex-concave minimax problems. 2023.
Thanks for the reply, after the rebuttal I will keep my score and recommend acceptance for this submission.
Thank you for your time and valuable comments, especially regarding  **Assumption 3**，which is indeed strong and also used in most existing works, such as [1] and [3].  To address your concern, we further improved the variance bound and corresponding theoretical results of our algorithms.  
We first derive the following variance bound in the following inequalities (1) and (2) to replace **Assumption 3**.
$$
E[||\hat\nabla_x f(x,y;\zeta) - \nabla_xf_{\mu_1}(x,y)||^2] \leq \frac{2G^2}{b_1} + \frac{4d_xG^2 + \mu_1^2 \ell d_x^2}{b_1} 
\tag{1}
$$
 and 
$$
E[||\hat\nabla_y f(x,y;\xi) - \nabla_yf_{\mu_2}(x,y)||^2] \leq \frac{4\ell^2D_\mathcal{Y}^2}{b_2} + \frac{8d_y\ell^2D_\mathcal{Y}^2 + 2\mu_2^2 \ell d_y^2}{b_2} \tag{2}
$$
Furthermore, we use the (1) and (2) instead of **Assumption 3** under our analysis framework, and adjust these parameters  $b_1 = \mathcal{O}(d_xG^2\epsilon^{-2})$, $b_2 = \mathcal{O}(d_y\ell^3\kappa D_{\mathcal{Y}}^2\epsilon^{-2})$, and by adjusting the smoothing parameters $\mu_1 = \mathcal{O}(\epsilon/(d_xL_x))$, $\mu_2 = \mathcal{O}(\sqrt{\kappa}\epsilon/(d_yL_y))$, our ZO-GDEGA still obtains the complexity of **$\mathcal{O}(\kappa^2(d_x + d_y\kappa)\epsilon^{-4})$**  for the NC-SC problem.  As for the NC-C setting, we can set $b_1 = \mathcal{O}(d_x\ell G^2)$, $b_2 = \mathcal{O}(d_y\ell D_{\mathcal{Y}}^2\epsilon^{-2})$, and by setting the smaller smoothing parameters $\mu_1 = \mathcal{O}(\epsilon/d_x)$, $\mu_2 = \mathcal{O}(\epsilon/d_y)$, our ZO-GDEGA algorithm can still obtain the complexity of $\mathcal{O}(d_x\epsilon^{-6} + d_y\epsilon^{-8})$. 

Thus, these derivation shows that **Assumption 3** is a strong assumption. We will add this discussion in our revised version. 

[1] Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization. The Journal of Machine Learning Research, 2022

[2] Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks.

[3] Derivative-free alternating projection 490 algorithms for general nonconvex-concave minimax problems. 2023.
Thanks for your detailed response! I will increase my score to 6 because of these detailed discussions and the efforts you took during the rebuttal phase. I have no further comments.
I have read the authors' response. I suggest those valuable discussions could be added in appendix to clarify each contribution. While I agree with the theoretical claims in the rebuttal, however each weakness in my original comment still holds. Thus I will keep my score.