Refining Adaptive Zeroth-Order Optimization at Ease
Authors: Yao Shu
Qixin Zhang
Kun He
Zhongxiang Dai
Venue: ICML 2025 poster (2025)
Keywords: Adaptive Method
Zeroth-Order Optimization
Variance Reduction
Convergence
Primary area: optimization->zeroorder_and_blackbox_optimization
TL;DR: We introduce R-AdaZO, a novel approach that improves the convergence of existing adaptive ZO methods by effectively leveraging moment information.

Abstract: Recently, zeroth-order (ZO) optimization plays an essential role in scenarios where gradient information is inaccessible or unaffordable, such as black-box systems and resource-constrained environments. While existing adaptive methods such as ZO-AdaMM have shown promise, they are fundamentally limited by their underutilization of moment information during optimization, usually resulting in underperforming convergence. To overcome these limitations, this paper introduces *Refined Adaptive Zeroth-Order Optimization* (R-AdaZO). Specifically, we first show the untapped variance reduction effect of first moment estimate on ZO gradient estimation, which improves the accuracy and stability of ZO updates. We then refine the second moment estimate based on these variance-reduced gradient estimates to better capture the geometry of the optimization landscape, enabling a more effective scaling of ZO updates. We present rigorous theoretical analysis to show **_(a)_** *the first analysis* to the variance reduction of first moment estimate in ZO optimization, **_(b)_** *the improved second moment estimates* with a more accurate approximation of its variance-free ideal, **_(c)_** *the first variance-aware convergence framework* for adaptive ZO methods, which may be of independent interest, and **_(d)_** *the faster convergence* of R-AdaZO than existing baselines like ZO-AdaMM. Our extensive experiments, including synthetic problems, black-box adversarial attack, and memory-efficient fine-tuning of large language models (LLMs), further verify the superior convergence of R-AdaZO, indicating that R-AdaZO offers an improved solution for real-world ZO optimization challenges.

Refining Adaptive Zeroth-Order Optimization at Ease
Yao Shu Qixin Zhang
Kun He
Zhongxiang Dai
Abstract
1. Introduction
Recently, zeroth-order (20) optimization plays an essential role in scenarios where gradient informa- tion is inaccessible or unaffordable, such as black- box systems and resource-constrained environ- ments. While existing adaptive methods such as ZO-AdaMM have shown promise, they are fun- damentally limited by their underutilization of mo- ment information during optimization, usually re- sulting in underperforming convergence. To over- come these limitations, this paper introduces Re- fined Adaptive Zeroth-Order Optimization (R- AdaZO). Specifically, we first show the untapped variance reduction effect of first moment estimate on ZO gradient estimation, which improves the accuracy and stability of ZO updates. We then refine the second moment estimate based on these variance-reduced gradient estimates to better cap- ture the geometry of the optimization landscape, enabling more effective scaling of ZO updates. We present rigorous theoretical analysis to show (I) the first analysis to the variance reduction of first moment estimate in ZO optimization, (II) the improved second moment estimates with a more accurate approximation of its variance-free ideal, (III) the first variance-aware convergence frame- work for adaptive ZO optimizers, which may be of independent interest, and (IV) the faster con- vergence of 'R-AdaZO than existing baselines like ZO-AdaMM. Our extensive experiments, in- cluding synthetic problems, -bx adversarial attack, and memory-efficient fine-tuning of large language models (LLMs), further verify the su- perior convergence of R-AddZO,, indicating that R-AdaZO offers an improved solution for real- world ZO optimization challenges.
Zeroth-ories (ZO) optimization has emerged as an indis- pensable technique at the forefront of machine learning, addressing critical challenges where gradient information is either unavailable or computationally prohibitive. This necessity stems from the prevalence of black-box optimiza- tion problems, such adversarial attacks (Ru al., 2020; Hiranandani et al., 2021), and resource- constreecnn envi- ronments, like fine-tuning large language models (LLMM) on memory-limited devices (Malladi et al., 2023; Zhang et al., 2024b). Consequently, ZO optimization algorithms, which rely solely on function evaluations, have become a crucial alternative to traditional gradient-based methods. Despite the growing body of research in ZO optimization, significant portion of existing methods adapt stochastic gradient descent (SGD) updates to the 70 setting (Liu et al., 201 8a;b; Shu et al., 2023; 2024). This reliance on SGD, however, will lead to performance limitations, especially in complex and non-convex optimization landscapes. The need for more adaptive and versatile update mechanisms is hence evident. However, the exploration of adaptive strategies beyond SGD-based updates remains surprisingly limited.
While adaptive methods such as ZO-AdaMM (Chen et al., 2019; Nazari et al., 2020) have demonstrated potential in addressing the missing adaptivity in zeroth-order optimiza- tion, they are fundamentally limited by their underutiliza- tion of moment information, often resulting in suboptimal convergence rates. This limitation in fact arises from their reliance noisy and high- variance gradient estimates de- rived solely from function evaluations-2 stark contrast to the first-order (FO) methods that leverage direct and more stable gradients. This issue becomes even more pronounced in high-dimensional and complex settings.
To address this critical limitation, we introduce Refined Adaptive Zeroth-Order Optimization (R-AdaZO), novel approach that effectively capitalizes moment information through two key innovations. First, R-AdaZO is the first to analyze the untapped but inherent variance reduction effect of the first moment estimates on the gradient estimates in Zo optimization, leading to more accurate and stable ZO updates. This is accomplished through the integration of historical gradient estimates, which effectively averages out the estimation noise (Sec. 4.1). Second, R-AdaZO refines
'Hong Kong University of Science and Technology (Guangzhou) 'Nanyang Technological University 'Huazhong Uni- versity of Science and Technology "The Chinese University of Hong Kong, Shenzhen. Correspondence to: Zhongxiang Dai <daizhongxxang @cu...edu...>..
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Refining Adaptive Zeroth-Order Optimization at Ease
the second moment using these variance-reduced gradient estimates, enabling better adaptation the underlying ge- ometry of the optimization landscape and facilitating more effective scaling of ZO updates (Sec. 4.2).
2005) or coordinate-wise perturbations (Lian et al., 2016). These methods often have noisy gradient estimation. To address this, Cheng et al. (2021) introduce prior-guided gradient estimation, which leverages previous estimates to improve the current one, effectively smoothing the estima- tion noise. Recently, Shu et al. (2023; 2024) propose using kernel methods to learn a surrogate model of the objective function from historical function values, allowing for more accurate gradient estimation. Another line of work has fo- cused on linear interpolation strategies for more accurate estimates by reusing queries from prior iterations to reduce complexity while maintaining sample quality (Wang et al., 2024b). Note that this paper does not aim to introduce a new gradient estimation approach, but focus on developing ad- vanced update rules that are applicable to all these existing estimation methods.
Beyond simply presenting R-AdaZO, we provide a thor- ough analysis that combines rigorous theoretical guarantees with extensive empirical validation, demonstrating its ef- fectiveness. Specificallly, we first provide the assumptions used in our theoretical analysis (Sec. 5.1). We then theoreti- cally analyze that incorporating first-moment estimates into Zo optimization significantly reduces the variance, leading to more stable and reliable ZO updates, and theoretically demonstrate that our refined second moment estimates pro- vide a more accurate approximation of its corresponding variance-free ideal (Sec. 5.2). We further introduce the first variance-aware framework to prove the convergence of adaptive 70 optimization methods, which is not limited to our specific method and can be used to analyze a wider range of similar algorithms, and theoretically prove that R-AdaZO converges faster than established baseline meth- ods, such as ZO-AdaMM, demonstrating its efficiency in optimization (Sec. 5.3). Through extensive experiments, including synthetic problems (Sec. 1. black-box adversar ial attack (Sec. 6.2), and memory-effieient LLM (Sec. 6.3), we demonstrate that R-AdaZO consistently out- performs existing methods in practice, exhibiting superior convergence.
ZO Update Rules. Building upon the estimated gradients from various ZO estimation methods, ZO optimizers often directly adopt update rules from first-order (FO) optimiza- tion. E.g., a large portion of existing ZO optimizers use stochastic gradient descent (SGD) and its variants as their update mechanism (Ghadimi & Lan, 2013; Ghadimi et al.. 2016; Nesterov & Spokoiny, 2017; Liu et al., 201 2019; Cheng et al., 2021; Shu al., 2023). While simple to apply, the slow convergence of SGD has motivated few efforts (Chen et al., 2019; Nazari et al., 2020; Jiang et al., 2024) to explore the use of adaptive methods, such as Adam (Kingma & Ba, 2015), as the ZO update rule. However, these attempts often autel-u the moment information inherent in adap- tive methods when applied to 70 optimization, leading to suboptimal convergence. This paper addresses this critical issue by proposing refined update rules that are specifically designed to better leverage moment information, ultimately leading to more efficient ZO optimization.
To summarize, our contributions in this work include:
We propose R-AdaZO enhance the utilization of mo- ment information in ZO optimization and significantly improve the convergence of adaptive ZO optimizers.
We theoretically show (1) the first analysis to the variance reduction of first moment estimates in ZO optimization, (II) the effects of our refined second moment estimates, (III) the first variance-Aware convergence framework for adaptive ZO methods, which may be of independent inter- est, and (IV) the improved convergence of R-AdaZO.
3. Background
This paper tackles stochastic zeroth-order (ZO) optimiza- tion problem, aiming to minimize the expected value of a function, defined as:
We use extensive empirical validation to show the consis- tent performance gains of R-AdaZO over baselines.
2. Related Work
min F(0) 2 E5 [)) OER
Recent ZO optimization research focuses on two key areas: Zo gradient estimation and ZO update rules.
where O E IRd and f0: {) is a scalar-valued function whose evaluation depends on the parameters 0 and a random vari- able & sampled from an underlying distribution. Crucially, we have access only function evaluations f(0 {) and not its gradient V fof E). Throughout this paper, we adopt the following notational conventions. Vectors are represented in boldface, c.g., 0, and scalar constants are denoted by upper- case letters, e.g., L. All vector operations are assumed to be element-wise unless explicitly stated otherwise. We denote by V,F the partial derivative of function F with respect to
ZO Gradient Estimation. Since ZO optimization only relies on function values, gradient estimation is essential for effective optimization. A common approach is to use finite difference approximations under input perturbations. Nes- terov& & Spokoiny (2017) propose to use Gaussian random noise perturbations, demonstrating theoretical convergence with smooth perturbations. Other methods also propose to use uniform sampling from the unit sphere (Flaxman et al.,
2

---

Refining Adaptive Zeroth-Order Optimization at Ease
the i-th coordinate.
Algorithm 1 120-AdaMM
ZO Gradient Estimation. In ZO optimization, the ab- sence of direct access to gradients, denoted as Vof E), necessitates the use of gradient estimation techniques that rely solely on function evaluations. A widely used method is to approximate gradients using finite differences. E.g., let random vectors {u, | be drawn uniformly from the sphere gd of unit ball B" a common ZO gradient esti- mator, which is used throughout this paper, can be formed as:
Input: 31 B2. S. n.
Initialize: O,z ma: 1op
for iteration E [T] do
9t - ff Et)
m, - f,m,-1 + (1 3t)
V, - 82 + (1- -2)
02 + 0 - 1) m,
Vu.ts
Output: Or
f(0 puni E) 5(0:E) u
E)(,E) A
(2)
Algorithm 2 R-AdaZO
Input: 8,82, (,
where μ > is smoothing parameter, and K is the number of random vectors. While this paper utilizes this specific ZO gradient estimator as its foundation, the proposed method is extensible to other ZO gradient estimators as well.
Initialize: 0,. ma; v0
for iteration E [T] do
9: V ff Et)
m, + B, m, + (1 - B.)g:
V, + U,U111 + (1 m2)
Adaptive ZO Optimization. ZO optimization methods with a fixed step size typically suffer from slow conver- gence. To address this, adaptive methods like Z0-AdaMM (Chen et al., 2019) are used, which incorporate momentum using first moment estimates and per-parameter learning rates using second moment estimates. Specifically, in ZO- AdaMM, the parameter updates are computed as follows for every iteration / (see also Algo. 1):
0 001 1 Vo,ts
Output: Or
updates (Sec. 4.1). We then apply these variance-reduced estimates to construct a refined second moment, enabling more effective scaling of ZO updates (Sec. 4.2).
m, - -,mm,-1 + (1- 31)g. 0 - 0- + (1-Ba) 32)g
(First Moment Est.) (Second Moment Est.)
4.1. Variance Reduction in First Moment Estimates
First moment estimation, while conventionally used for con- vergence speedup, inherently serve as a variance reduction mechanism for noisy gradients. To show this, consider the following standard first moment estimate with 31 E (0, 1):
m,
0, < 02 11 V0, +
(ZO Update)
(3)
where 9: ((,,.) defined in (2), B B2 E (0, 1) are exponential decay rates for moment estimates, and Ç is small constant to prevent dividing by zero.
m, + 3,m,- + - (B)
(4)
where m, is the estimated first moment at iteration t and 9: is the gradient estimate at 0,- via (2). Intuitively, this up- date averages the current noisy gradient estimate with past, correlated estimates. This averaging process effectively smooths out noise in gradient estimates, thereby reducing variance. For example, averaging two independent noisy gradient estimates (ie, m;-1 and gt) of variance o² results in a variance of [s + (1 - B, 300" which is less than o². While current and past gradient estimates are not fully in- dependent in practice, their local correlation still enables variance reduction through this averaging, which we will show theoretically Sec. 5.
However, while these adaptive ZO approaches have shown promise, they often underutilize the moment information in the context of ZO optimization: (a) They typically treat first moment estimate m, as standard velocity accumulation in FO optimization, failing to consider its underlying variance reduction effect in 7.0 optimization by accumulating infor- mation from previous gradient estimates. (b) They fail to apply this variance- reduced gradient estimates to refine the second moment estimate U, causing a less effective scaling of ZO updates.
4. Refined Adaptive ZO Optimization
While this variance reduction effect has been proven in FO optimization (Liu et al., 2020), it is significantly more cru- cial in 70 optimization. Unlike FO methods that compute gradients directly with relatively low variance, ZO optimiza- tion approximates gradients using function evaluations (as in (2)). resulting in inherently noisier estimates. This dis- parity underscores the critical importance of the variance
To address the underutilization of momentum information in existing adaptive 70 optimization methods, we introduce R-- AdaZO (Refined Adaptive Zeroth-Order Optimization). Specifically, we first analyze the untapped variance reduc- tion effect of first moment estimates on ZO gradient es- timation, which is important for accurate and stable ZO
3

---

Refining Adaptive Zeroth-Order Optimization at Ease
reduction effect of first moment estimates in ZO optimiza- tion, a connection we are the first identify. We further provide theoretical support for this in Sec. 5.
for moment estimates and ZO updates (excluding function evaluations), and the same memory footprint of O(d) ZO- AdaMM for moment estimates, where K is the number of function evaluations and d is the dimension of parameter 6.
4.2. Refinement to Second Moment Estimates
Ease of Implementation. A key advantage of R-AdaZO is its simple implementation. The core change involves up- dating the second moment estimate using the squared first moment estimate, a one-line change for existing adaptive ZO optimizers. This minimal change enables easy integra- tion and fast deployment, while improving convergence.
The second key innovation of R-AdaZO lies in its refined second moment estimate, which is crucial for the adaptivity in ZO optimization. Existing adaptive ZO methods (Chen et al., 2019; Nazari et al., 2020) update the second moment estimate directly using the squared noisy gradient estimates:
2 = 1, + (1 32)g
(5)
5. Theoretical Analysis
However, this approach can be suboptimal in the ZO setting owing to the inherent high variance of the gradient estimates in (2), which could lead to unstable and unreliable second moment estimates. We thus propose to address this issue by simply leveraging the setianc-reedceed gradient informa- tion from the first moment. That is, we update the second moment estimate as below, which interestingly shares simi- lar form with RMSProp (Hinton, 2012).
This section presents a theoretical foundation for the efficacy of R-AdaZO. We structure our analysis as follows: First, we introduce the required assumptions and preliminaries (Sec.5.1). Second, prove the variance reduction in first moment estimate and the improvement of our refined second moment in R-AdaZO (Sec. 5.2). Finally, we present the first variance-aware convergence framework for adaptive Zo methods and demonstrate the improved convergence of R-AdaZO over other baselines (Sec. 5.3). To ease our proof, we primarily provide the theoretical analysis for (2) with Unif([d-]
= 12 + (1 - (L)-2))m) m2)
(6)
The first moment estimate, as revealed in Sec. 4.1, acts as variance reduction mechanism by averaging historical gra- dient information. Using the squared first moment estimate then probably provides smoothed and more stable second moment estimate. This refinement therefore may enable more accurate representation for the underlying geometry of the optimization landscape, resulting in more effective scal- ing of ZO updates and thus accelerated convergence. Specif- ically, consider a scenario where E [/, = [[g,] but m, has significantly lower variance than 9, due to the smoothing effect, given the same 1/ we can see that the refined e, in (6) achieves a smaller expected value compared to the standard one in (5). Hence, the update step (see (7)) using this refined v, in (6) is likely to be larger, allowing the algo- rithm to move faster towards the optimum. This claim will be rigorously established in Sec. 5.
5.1. Assumptions and Preliminaries
Our theoretical framework is built upon two fundamental assumptions concerning the non-convex function F. We im- pose bounded function value as well as coordinate-wise Lipschitz smoothness (Assump. 1), with a bounded variance of function values (Assump. 2). Of note, coordinate-wiss Lipschitz smoothness is commonly used in the analysis of FO adaptive gradient methods, e.g., (Zhang et al., 2024a; Wang et al., 2024a).
Assumption 1. V0, 0' E Rd and Vi E [d],
[((0,E] SC, V.F(O) - (,F(')) S L 1 0'll
(8)
(9)
4.3. Final Algorithm
Assumption 2. 40 E R
Given the first and second moment estimates in (4) and (6) respectively, R-AdaZO updates parameters by:
RE [[((0 - = so²
(10)
m. 0, 0.=0.-1 - Ve, +
(7)
Directly establishing the convergence of R-AdaZO through the function F' presents a primary challenge for adaptive ZO methods, due to the bias (i.e., E \ E) + VF()))
where 17 is the base learning rate and Ç is a small constant for numerical stability. This update rule adaptively scales the effective learning rate based on the local geometry while incorporating the pariance-reduced gradient estimates. The complete R-AdaZO algorithm is detailed in our Algo. 2.
arising from the gradient estimation in (2). Thus, we pro- pose to prove the convergence of R-AdaZO with respect to the randomized smoothing function F,, (Duchi et al., 2012) defined in (11) where u is a random vector drawn uniformly from a unit ball B" and μ > 0 is a smoothing parameter. Of note, 70 gradient (2) with u ~ Unif(Sd-1) in fact leads to
Computational and Memory Complexity. R-AdaZO incurs the same computational cost of O per iteration
4

---

Refining Adaptive Zeroth-Order Optimization at Ease
an unbiased gradient estimation for this smoothing function, which we will show in Lemma 5.1 below.
Remark. To the best of our knowledge, this theorem pro- vides the first fundamental variance-bias decomposition for the first moment estimate in adaptive ZO algorithms. The variance, given by 1-8, >², arises from the randomness in 1+0;
(0) - E uuz" [F(O + pra]
(11)
gradient estimator (2) and reduces Σ² in (15) by a factor of 1-9, 143, which can be further improved with a large 91- This thus theoretically demonstrates the variance reduction effect of first moment estimate in (4), which goes beyond increasing K to reduce variance. The bias, stemming from the difference between current and past estimates, can be reduced by using a small learning rate 1/. which limits the magnitude of update steps, or a small 31, which reduces the influence of past estimates. So, this decomposition unveils a fundamental trade-off controlled by the utilization (i.e.. B1) of past estimates between variance and bias. Particularly, when B = 0, (17) simplifies to (15).
We introduce the following Lemma 5.1 (proof in Appx. A.I) to justify why Fp,, instead of F. servers better choice for the convergence framework of adaptive ZO methods. Lemma 5.1. Given (2) with u ~ Unif((t-)), let Assump. 1 hold, v0 E TR" and Vi E [d],
E
(((,,)) = (0),
(12)
E [ - (0)l VF, S
Sulvd.
(13)
Remark. Lemma 5.1 establishes that (a) FI is the expec- tation of the gradient estimate in (2), thereby overcoming the bias challenge mentioned above, and (b) the discrepancy between F and V is bounded above by O(w), implying that the convergence of R-AdaZO with respect V can be casily derived after obtaining the results with respect to F,,
We then theoretically show that our refined second moment update in (6) is likely to be more accurate approximation to its variance-fire ideal in (18) and hence may better capture the underlying geometry of optimization landscape than (5) used in ZO-AdaMM, with the following Thm. 5.4 (proof in Appx. A.4) and Cor. 3.5 (proof in Appx. A.5).
H. In light of these, F2 will be good choice for the convergence framework of adaptive ZO methods.
In addition, we provide the following Lemma 5.2 (proof in Appx. A.2) to ease our proof.
V1, = 3/ vo,s + (1- -
(, 2 (18)
Lemma 5.2. Given (2) with u ~ Unif((s-)), let Assump. 1 hold, vO, 0' E B² and Vi E [d],
7=1
Theorem 5.4. Given second moment estimate (6), with As- sump. 1, 2, Vt 2 1 and Vi E [d].
V (,) (,F,
s T. 1.110 0'1l
(14)
- V,F, []]
- 8(0² + c²yd
(15)
8. 81
Kμ²
E [1,3]
S B3 Vo. + (1 (1- E3
(1 (1-
Remark. Lemma 5.2 establishes that (a) F2 exhibits the same Lipschitz smoothness as F, and (b) the gradient vari- ance associated with 70 optimization can be substantially large, particularly when K < d and μ is small. Therefore, variance reduction is critical for improved Zo optimization.
(1+
1
B1 Σ (1-
E
[.F2(0,-)))
(19)
Corollary 5.5. Given second moment estimate in (5), with
Assump. 2, Vi 2 and Vi E [d],
5.2. Analysis on First and Second Moment Estimates
E [v,.]] $ 81 Poti + (1+
We first theoretically show the underlying variance reduction effect of first moment estimate in (4) using variance 2 defined below in Thm. 5.3 (proof in Appx. A.3).
(1+ 3,)
3 Σ (1 -1- (2)0
E
(,
e D²]
(20)
Σ² 8(02 + +O2y
(16)
Kμ²
Remark. Thm. 5.4 introduces a novel variance-deppndent
upper bound for our refined second moment estimate (6). Compared with the bound (20) in Cor. 5.5 for the conven- tional estimate (5), our (6) reduces the influence of gradient estimation variance x (in green) by a factor of 1-2,, This
Theorem 5.3. Given first and second moment estimates (4) and (6) respectively, with Assump. 1, 2, Vt 2 1, Vi e [d],
- I+3,
E |mm - (.F,(0
is crucial in 70 optimization where X² is typically large. While our estimate introduces a bias (in orange), it is small with a small learning rate 7). Note that (18) represents the variance- free ideal, which the conventional estimate (5) and our refined estimate (6) aims to approximate. Comparing
1- 9 9 +
(1 + n
+ B
V F 00
1+ (1-B)(0 B2)
Variance
Squared Bias
(17)
5

---

Refining Adaptive Zeroth-Order Optimization at Ease
the bounds in (19) and (20) with (18), our refined estimate (6) better approaches this ideal than (5), particularly when - dominates, thanks to its reduced impact of >²" This thus enables a better capture of geometry information during optimization and probably leads to improved optimization.
strengthening the understanding of convergence behavior for adaptive ZO methods
Leveraging Lemma 5.6, we then proceed to bound the terms A and (B in Lemma 5.7 (proof in Appx. A.7) and Lemma 5.8 (proof in Appx. A.8), respectively. These results rely on the following definition of V resulted from Thm. 5.4.
5.3. Variance-Aware Convergence Analysis
3 + (1 222
This section presents the first variance- convergence framework for adaptive ZO methods, particularly focusing on the convergence of R-AdaZO and ZO-AdaMM. We first bound the averaged gradient norm of the smoothed function, Fu.. as step towards bounding the averaged gra- dient norm of the original function F. Inspired by (Zhang et al., 2024a), the core proof idea lies in applying Hölder's 's inequality to decomposes this target into two components (Lemma 5.6): One involving the averaged square root norm of second moment estimate that will be variance-dependen and another involving a normalized gradient norm by second moment estimate. The subsequent analysis then focuses on bounding these two components using Lemma 5.7 and Thm. 5.8, respectively. The first component, i.e., the averaged square root norm of second moment, can be upper-bounded with Thm. 5.4 (see Lemma 5.7). The second component, ie., the normalized gradient norm with second moment, is shown to of order O(e²) (see Thm. 5.8). By combining these bounds and incorporating the connection between FF and V. in Lemma 5. we arrive at the final convergence results for R-AdaZO (Thm. 5.9) and ZO-AdaMM (Thm. 5.10).
V28 - | (1 BA)
(22)
(1 - (1) 32)
Varionce
Squared Bias
Lemma 5.7. Given first and second moment estimates (4) and (6) respectively, with Assump. 1, 2, VI 2 1, E [d],
T E
+5] S
V
32 Uz
T
t=
(1 3.vvv 1 v B - B₂) T
Vd+
E [1]
(23)
Remark. Lemma 5.7 demonstrates that A in Lemma 5.6 is variance-dependent. Specifically, A is asymptotically dom- inated by V as T + co, because + ErD E VF, (0.) gradually decreases during optimization. This highlights that the asymptotic behavior of A is governed by both the bias and variance present in the first moment estimate (4).
Theorem 5.8 (Informal). Given Assump. 1, 2, let 3- ~ O OO2),, and T ~ O(c the following holds for R-AdaZO if Bi < / B2, B2 2 2: mo,+ = 0, vo, > 0,
We first introduce Lemma 5.6 (proof in Appx. A.6).
VF C 111
Lemma 5.6. Vt Z 1, we have that
Se.
(24)
B2 1 +c
||| V (0)111
T
Remark. Of note, Thm. 5.8 attains the same rate of O( /
1=0
(Chen et al., 2019; Nazari al., 2020) achieve that
T-1
VFF F
12
E
V B2 w2ll
+
5
E
T 0
IE
VF (0,
S.
T
T
B2
+
T
1=0
1=
By incorporating Lemma 5.1, Lemma 5.7, and Thm. 5.8 into Lemma 5.6, we derive the following convergence for R- AdaZO (Thm. 5.9, proof in Appx. A.9) and ZO-AdaMM (Thm. 5.10, proof in Appx. A.10), respectively.
(21)
Remark. Chen et al. (2019); Nazari et al. (2020) bound B solely to demonstrate the convergence of adaptive ZO methods. However, we argue that this bound alone fail to include the effects of second moment estimate and therefore provides incomplete convergence information. In contrast, Lemma 5.6 allows us to include the effects of second mo- ment (i.e.. ) and directly bound more relevant quantity, T t + E (..))l Note that this metric is a more widely accepted convergence criteria in optimization theory, directly measuring the distance to a stationary point (Arje- vani et al., 2023; Zhang et al., 2024a). Overall, Lemma 5.6 enables us to provide a variance-an aware convergence analysis,
Theorem 5.9 (Informal). Given Assump. 1, 2, let 1 - Bg ~ O(2), 7 O(e), and T ~ O(e We have the following for R-AdaZO if 3 S VB2, B2 Z 1/2 and Vi E [d], mo, = O, Vo,i > 0,
(1 1+ 2+ (Vi+Vva)
E IVF
VB 10 (3))
+ +LLv
(25)
where V is defined in (22).
6

---

Refining Adaptive Zereth-Orrer Optimization at Ease
Quadratic
Cubic
Levy
Rosenbrock
Optimality Gap (log scalc)
000000000
Z0-SGD
14
ZD-signSGD
5
ZD-RMSPIPP
AdaMM
12-
R-AdaZO
0-
00000000000 0000
0 0000009999
0-0----0-0 CHCCC-HHHH
20000
40000
0
20000
40000
0
20000
40000
20000
40000
Iters (7)
Iters (7)
Iters (7)
liers (T)
Figure I: Convergence comparison among different adaptive ZO optimizers for various synthetic functions, in which y-axis represents the log-scale optimality gap F(0)- ming' F(0") and r-axis is the number of iterations T.. Each curve denotes the mean from 3 independent runs.
Theorem 5.10 (Informal). Given Assump. 1, 2, let 1
(a) First Moment
(b) Second Moment
32 OE²),, 17 OE²), and T O(E OtE)). We have the following for ZO-AdaMM if B1 S VF2, B2 2 1/2 and Vi E [d], mo = 0, 0,, > 0,
600
Cosine Siualsrity
0.08
10
Relative Error
D
10
)
D(
01
0.04
200-
10
JC
01
T
1- (1+ 3iVd 2+ (Vstvva) E [VF
0.02
T
V 32)
0.00
0.993
0.9
0.993
8. = 0.7
(e) (ori)
K2 (ours)
HLLv
(26)
Figure 2: Effects of (a) first and (b) second moment under varying 81 during the convergence of Quadratic function. Here, 9: and m, corresponds to the results from the esti- mated gradient in (2) and the first moment in (4), and v, (ori) and v, (ours) are results of the second moment esti- mates defined in (5) and (6) respectively. The y-axis in (a) represents the cosine similarity between It or m, and the true gradient F(( while the y-axis (b) denotes the relative error between v, in (5) or (6) and the v, computed using the square of the true gradient V F(O,..)..
where 2 A |Poll + (1+ E
Variance
Remark. To the best of our knowledge, our Thm. 5.9 and Thm. 5.10 are the first analyses to explicitly incorporate the impact of second moment estimate (measured by V V) that is irttance-depndeent into the convergence of adaptive 70 methods. Specifically, Thm. 5.9 and Thm. 5.10 demon- strate that the convergence of # E E [[IIFF(O)]] typ- ically exhibits a dependence of (vVe)) in adaptive 70 methods, highlighting the importance of an improved sec- ond moment estimate with reduced variance. This explains the advantage of R-AdaZO over other adaptive ZO meth- ods like ZO-AdaMM thanks to our refined second mo- ment estimate (6) achieving reduction of at most 1-8, T+ on V. Moreover, Thm. 5.9 implies that a larger 31 typically leads to an improved convergence of R-AdaZO especially when variance Σ² dominates. Comparing Thm. 5.9 and Cor. 5.10, we observe that R-AdaZO achieves a speedup for the convergence of averaged gradient
black-box adversarial attack (Sec. 6.2), as well as memory- efficient fine-tuning of large language models (Sec. 6.3), to empirically support the superior efficacy of our R-AdaZO (Algo. 2).
6.1. Synthetic Functions
On Convergence. We first compare the convergence of R-AdaZO with ZO-SGD, ZO-signSGD (Liu et al., 2019), ZO-AdaMM, and ZO-RMSProp, an integration of RM- SProp (Hinton, 2012) and ZO gradient estimator, using four synthetic functions with d-10 including Quadratic, Cubic, Levy, and Rosenbrock function. We refer Appx. B.1 for more details. The results are in Fig. 1, showing that R- AdaZO generally achieves significantly faster convergence while maintaining competitive optimality gaps compared to other baselines. The consistent gain of R-AdaZO across most synthetic functions suggests that R-AdaZO robust
of O (Vi+e, 1-8
1+8,
norm primarily when variance x dominates. These will be further empirically supported by the experiments in our Sec. 6 below.
6. Experiments
In this section, we conduct extensive experiments on various tasks in practice, including synthetic functions (Sec. 6.1),
7

---

Refining Adaptive Zeroth-Order Optimization at Ease
(a) OPT-1.3B (SST-2)
(b) OPT-13B (SST-2)
(c) OPT-13B (Copa)
(d) OPT-1.3B (SST-2)
-X-
Z0-RMSPrup
70-AdsMM
0.8
- ZO-RMSPup
70-AAMM
2.2
- 20-RMSPOp
20-A4MM
-b- A 0.6
-X- A 0.5
Thining Loss
R-Ad20
R-Ad20
R-Ad220
0.6
- 04 0.9
0.4
1.8
0.4
0.4
4 29%
3.75%
1.6
2. 114
0.2
0.2
O
2500
5000
7500
2500
5000
7500
2500
5000
7500
2500
5000
7500
Iters (I)
Iters (I)
Iters (Z)
Iters (Z)
Figure 3: (a-c) Training loss comparison among various adaptive ZO optimizers for the fine-tuning of LLMs under different model sizes and different dataset. (d) Training loss comparison of varying 31 in R-AdaZO on OPT-1.3B and SST-2 (Socher et al., 2013). Each curve denotes the mean from 3 independent runs.
to the structure of the underlying problem. Furthermore, Fig. I reveals notable similarity in the convergence behavior of ZO-AdaMM and ZO-RMSProp across all four bench- mark functions. contrast, R-AdaZO consistently demon- strates substantial speedup compared to ZO-RMSProp. These results imply that the first moment itself contributes minimally to the convergence gains for adaptive ZO opti- mization, and underscores the critical role of our refined second moment estimate in achieving the superior perfor- mance of R-AdaZO.
Table 1: Comparison of the number of iterations to achieve a successful black-box adversarial attack. Each cell represents mean + standard deviation from five independent runs.
Measurement
ZO-RMSProp
ZO-AdaMM
R-AdaZO
# Iters (x10") Speedup
15.6+3.2
15,5+4.1
2.9+0.8
1.0x
1.0x
5.4x
trade-off is likely due to the loose bound we derived for our refined second moment.
On First Moment. We further conduct an experimental analysis understand how 81 affects first moment estimates during the optimization process of the Quadratic function. In Fig. 2 (a), we present the results, using cosine similarity to measure the alignment between the estimated gradient g. or the estimated first moment m,, and the true gradient (() The results indicate that the estimated first mo- ment m, exhibits better cosine similarity than 9t. resulting from its variance reduction effect, as proven in Thm. 5.3. Moreover, we observe that increasing 01 generally enhances this variance reduction. However, excessively high values of 31 result in minor decrease in similarity. This trend is consistent with the trade-off discussed in Thm. 5.3.
6.2. Black -ox Adversarial Attack
We further investigate the performance of R-AdaZO within the realm of black-box adversarial attacks, a key application area for zeroth-order optimization (Cheng et al., 2021; Shu et al., 2023). In this context, the objective is to find opti- mal perturbation å that causes a black-box model to misclas- sify an input image x when perturbed to x + 8. Following the practice in (Shu et al., 2023), we also present a compar- ative analysis of the number of iterations required for suc- cessful black-box adversarial attacks on an image from the MNIST dataset (Lecun et al., 1998), using ZO-RMSProp. ZO-AdaMM, and R-AdaZO in Tab. 1 (experimental setup in Appx. B.2). As shown in the table, ZO-RMSProp and ZO-AdaMM exhibit similar performance, requiring an av- erage of approximately 15.6 and 15.5 thousand iterations, respectively. The standard deviations of the iteration counts were similar as well, about 3200 to 4100 iterations. These align with our results in Sec. 6.1. On the other hand, R- AdaZO requires a significantly lower number of iterations with an average of only 2900, and smaller standard devia- tion of 800 iterations, suggesting a faster and more stable convergence. The speedup achieved by R-AdaZO, i.c., a speedup of 5.4x compared to the baseline ZO-RMSProp. is also highlighted in Tab. 1. These findings thus further underscore the superior efficacy of R-AdaZO.
On Second Moment. We further conduct an experimen- tal analysis to understand how 3, affects second moment estimates during the optimization process of the Quadratic function. Figure 2(b) compares the second moment esti- mates, u, (ori) from (5) and v, (ours) from (6), using the relative error against the second moment estimate based on the squared ground truth (V (V) The results demon- strate that our refined second moment estimate, vy (ours), significantly reduces the relative error compared to the stan- dard second moment estimate, v, (ori), which therefore en- ables the capture of more accurate geometry information during optimization. Interestingly, increasing values of $1 generally lead to a lower relative error, trend that contrasts with the behavior of first moment estimates. This lack of a
8

---

Refining Adaptive Zeroth-Order Optimization at Ease
6.3. Memory-Efficiiet LLM Fine-Tuning
Cox, D. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In Proc. NeurIPS, 2019.
Recent interest memory-efficient fine-tuning of large lan- guage models using ZO optimization (Malladi et al., 2023; Zhang et al., 2024b) motivates our of this setting to further demonstrate the superiority of R-AdaZO over other adaptive ZO optimization algorithms (experimental setup in Appx. B.3). The results in Fig. 3(a-c) show that, for both OPT-1.3B and OPT-13B models (Zhang et al., 2022) and dataset SST-2 (Socher et al., 2013) and Copa (Roemmele al., 20 R-AdaZO converges significantly faster than ZO-RMSPropp and ZO-AdaMM on SST-2 dataset, achiev- ing a speedup of x x for OPT-1.3B and x.75x for OPT- 13B to reach the same training loss. The optimization curves of ZO-RMSProp and ZO-AdaMM are indistinguishable, indicating the similar convergence behavior we have seen in Sec. 6.1 and Sec. 6.2. These empirical results strongly more efficient and effective adap- tive ZO optimizer. In addition, the results in Fig. 3(d) show that R-AdaZO typically enjoys an improved convergence when a larger 31 is applied. which aligns with the insights provided by our Thm. 5.9.
Cheng, S., Wu, G., and Zhu, J. On the convergence of prior- guided zeroth-order optimization algorithms. Proc. NewrIPS, 2021.
Duchi, J. C., Bartlett, P. L., and Wainwright, M. J. Ran- domized smoothing for stochastic optimization. SIAM J. Optim., 22(2):774-70,, 2012.
Flaxman, A., Kalai, A. T., and McMahan, H. Online con- vex optimization in the bandit setting: Gradient descent without gradient. In Proc. SODA, 2005.
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. On-
line convex optimization in the bandit setting: gradient descent without a gradient. arXiv:es/0408007, 2004.
support R-AdaZO
Ghadimi, S. and Lan, G. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23(4):2341 1-668, 2013.
Ghadimi, S., Lan, G., and Zhang, H. Mini-batch stochastic approximation methods for nonconvex stochastic com- posite optimization, Math. Program., 155(1-22 (225-)))6 2016.
7. Conclusion
In conclusion, this work introduces R-AdaZO, novel approach that addresses the critical limitations of existing adaptive ZO methods by effectively leveraging moment in- formation. Through rigorous theoretical analysis, we have demonstrated the inherent variance reduction effect of first moment estimates on 70 gradient estimates, leading to more stable and accurate updates, as well as the improved accuracy of our refined second moment estimates. Further- more, we establish the first variance-awarg convergence framework for adaptive ZO methods and prove the superior convergence rate of R-AdaZO. The consistent empirical performance gains of R-AdaZO across diverse applications underscore its potential as a powerful and practical solution for real-world ZO optimization challenges.
Hinton, G. Neural networks for machine learning lecture 6a, 2012. http: http//wwwwcssoooo...oooo//o.o www.:ctttttoooooooooo .ew.ontttoddd///oooooo -ti
1ec6.
Hiranandani, G., Mathur, J., Narasimhan, H., Fard, M. M., and Koyejo, S. Optimizing black-box metrics with itera- tive example weighting. In Proc. ICML, 2021.
Jiang, S., Chen, Q., Pan. Y., Xiang, Y.. Lin, Y., Wu, X., Liu, C., and Song, X. Zo-adamu optimizer: Adapting perturbation by the momentum and uncertainty in zeroth- order optimization. In Proc. AAAI, 2024.
Impact Statement
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Proc. ICLR, 2015.
This paper presents work whose goal is to advance the field of zeroth-order optimization and machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Lecun, Y., Bottou, L., Bengio, Y., and Haffner. P. Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, pp. 2278-2324, 1998.
References
Lian, X., Zhang, H., Hsieh, C., Huang, Y., and Liu, comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first- order. In Proc. NIPS, 2016.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N. and Woodworth, B. E. Lower bounds for non-convex stochastic optimization. Math. Program., 199(1):165- 214, 2023.
Liu, S., Kailkhura, B., Chen, P., Ting, P., Chang, S., and Amini, L. Zeroth-order stochastic variance reduction for nonconvex optimization. In Proc. NeurIPS, 2018a.
Chen, X., Liu, S., Xu, K., Li, X., Lin, X., Hong, M., and

---

Refining Adaptive Zereth-Order Optimization at Ease
Liu, S., Li, X., Chen, P., Haupt, J. D., and Amini, L. Zeroth- order stochastic projected gradient descent for nonconvex optimization. In Proc. GlobalSIP, 2018b.
Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et al. Opt: Open pre-trained transformer language models. arXiv:2205.0066 2022.
Liu, S., Chen, P., Chen, X., and Hong, M. signsgd via zeroth-order oracle. In Proc. ICLR, 2019.
Zhang, Y., Li, P., Hong, Li, Zhang, Y., Zheng, W., Chen, P., Lee, D., Yin, W., Hong, M., Wang, Z., Liu, S., and Chen, T. Revisiting zeroth-order optimization for memory-efficiet LLM fine-tuning: A benchmark. In Proc. ICML, 2024b.
Liu, Y., Gao, Y., and Yin, W. An improved analysis of stochastic gradient descent with momentum. In NewrIPS, 2020.
Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, D., Chen, D., and Arora, S. Fine-tuning language models with just forward passes. In Proc. NeurlPS, 2023.
Nazari, P., Tarzanagh, D. A., and Michailidis, G. Adaptive first-and zeroth-order methods for weakly convex stochas- tic optimization problems. arXiv:2005.09260 2020.
Nesterov, Y. E. and Spokoiny, V. G. Random gradient-free minimization convex functions. Found. Comput. Math., 17(2):577-566, 2017.
Roemmele, M., Bejan, C. A., and Gordon, A. Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning, 2011.
Ru, B., Cobb, A. D., Blaas, A., and Gal, Y. Bayesopt adversarial attack. In Proc. ICLR, 2020.
Shu, Y., Dai, Z., Sng, W., Verma, A., Jaillet, P., and Low, B. K. H. Zeroth-order optimization with trajectoryinfoormed informed derivative estimation. In Proc. ICLR, 2023.
Shu, Lin, X., Dai, Z., and Low, B. K. H. Federated zeroth-order optimization using trajectory-informed sur- rogate gradients. In Workshop Differentiable Almost Everything (ICML), 2024.
Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C. Ng, A. Y., and Potts, C. Recursive deep models for semantic compositionality over sentiment treebank. In Proc. EMNLP, 2013.
Wang, B., Fu, J., Zhang, H., Zheng, N., and Chen, W. Clos- ing the gap between the upper bound and lower bound of adam's 's iteration complexity. In Proc. NeurlPS, 2024a.
Wang, X., Qin, X., Yang, X., and Yan, J. Relizo: Sample zeroth-order optimiza-
reusable linear tion. In Proc. NeurIPS, 2024b.
Zhang, Q. Zhou, Y., and Zou, S. Convergence guar- antees for rmsprop and adam in generalized-smooth non-convex optimization with affine noise variance. orXiv:2404.01436, 2024a.
10

---

Refining Adaptive Zereth--Orrr Optimization at Ease
A. Proofs
A.1. Proof of Lemma 5.1
Based on the definition ((, (2), we first prove (12) in Lemma 5.1 as below,
(() d
[(0 (uz
5(0:E)
E
B
uhk
K
F(O + p
F(0))
K
11 -8
Ub
my
Ukk
k=1
(27)
FF
(0)
where the third equality is due to the fact that E al., 2004) with Fj. defined on unit ball I shown in (11).
- F(0-)uu)) Ub
(F, which comes from Lemma in (Flaxman
We then prove (13) in Lemma 5.1 as below,
E VF( - VF, (F
E VF(0))
VF(O + pm)]
( VF pm))
(28)
12 EE [ulV
18
ulva
where (a) comes from the Leibniz's Rule, (b) results from Jensen's inequality, (c) is based on Assump. and (d) is due to the fact that ||a||| < 1. We therefore conclude proof for Lemma 5.1.
A.2. Proof of Lemma 5.2
With Leibniz's Rule, Jensen's 's inequality, and (d) Assump. 1, the following holds for (14) in Lemma 5.2:
V -
V.F,0')
[F(O pu) F(0', + nmm]
E w
V.F(0 pm) v.F(B' + (mmi
(29)
E B
[V.F nm) V.F(O' + [amil
$ L 0 8'1

---

Refining Adaptive Zeroth-Orrer Optimization at Ease
We finally prove (15) in Lemma 5.2 below,
2
E
-) - (.F
d²
K
f(0 purk E) 2x,s - E agn
F(O + palr)
2k.6 1)
[(0.5)
F(0)
u 1)
27
E
Uk E au
K²
P
P F(O + pu)s))
K
f(O + p. 5)
whr)) 1)
f(0.E)
F(O)) u 1)
Σ
E
Ukii B, Bst
ukii E Buy -S"
1
μ
2d
1
5(0 + jurke E) -F(O + wUnk))
F(O + (w)k))
F(O + (cls
E
U
E
K²
1
P
E( F(O)
Ukii + F(O)
F(()) ux
1)
E
Uusi
E Bui
1
1
1
( 4d K
1(0 + pu E) -F(O + pa)e)
2
[((0 + srlg))
F(O prl uk.
27
K
11
Ug.55
+
uk
Menga-1
+
((
F(O)
2
F(()
F(0))
27
E
Ukii
+
Un
uu uy
uki
1.
re
4d 2 K
F(O + (
2
F())
27
E
U +
+
Wkit
+
K k=1
11
1r
( 8 Dd
1² K
(30)
Here, (a) is due to the fact that E s
F(O++uu
2b
(F,
which comes from Lemma 1 in (Flaxman et al., 2004)
with Fu defined on a unit ball Bd as shown in (11), and the fact that E -
F(O) 2 = 0. In addition, (b) comes from
the independence among {u and (c), (d) are from Cauchy-Schwarz/ inequality. Besides, (e) results from Assump.
and the definition of variance. Finally, (f) is due Assump. and the fact that E proof for Lemma 5.2.
2 [
1/d. We therefore conclude
A.3. Proof of Thm. 5.3
We first show the following variance reduction effect in first moment estimate based on the definition of D² in (16):
E
m,, E mm.ml
E
B1)
Σ
(v.f((
(1 3,)² Σ
(2(t-T)
V.f(O,-11 V.F,
(31)
(e) (1 81)(1 - 8
1 31
(4) 1 B1 32
1 + B1
where (b) comes from the independence among {Er ft= and (c) results from Lemma 5.2.
Remark. As suggested by (31), the standard bias correction term (i.c., 1 -8)) in Adam (Kingma & Ba, 2015) is intentionally excluded to avoid compromising the variance reduction effect.
12

---

Refining Adaptive Zeroth-Order Optimization at Ease
We then show the bias in the first moment estimate as below,
1
E
E
m
V F
(0._.)
11
(a)
E
11
31)
8
1 $i
(
1 81
Σ
E
(V, (0, -.F,(0))))) (V.F -...00) -v,
T,T =1
(9)
(1 8
2
2
Σ
E - + - [V -.FF))---1)))
1 8
2
T,T
4
3
2 1
8
(1 -
8
V.FF -
(32)
8
1- 31
==1
(
(1- 11- 1-1
Σ
STB E 11,01- -0-11
8
7=1
69
(1 - 1 1/
Σ 3 (t-
d
m
E
Bi T=1
U0,i + 6
1=1 8
(1 TPd
Σ (1-
(1 B1)(1 - -B2)
(1 + 13))
(1 (0011-1)000 31)
where (c) is from Cauchy-Schreee Schwarz inequality, (d) is from the sum of geometric series, (e) is from (14) in Lemma 5.2, (f) is based on the update rule in (7) and Cauchy-Schward incquality, (g) is due to the fact that (h) results from the following:
m S m Finally,
B1 (1 (1+8) B1 (t 1) + (2t2 + 2t 1)8(+ -p
B B1
2 g
S
(33)
(1 (1- 3,)
(1 31)
By putting the results above together, we then conclude our proof for Thm. 5.3 as below:
E
m
(0) E [mc.e]
E
m
+ E [m],c]] - (0.1))
( E
m E [m,.. 22 E | [
V.F, (0,1)(
(34)
(c)
M E [m.,.] 11 [|]
+ (1- Btt E
1 8
Elm,, V.F%,(0,0)) 0/ + + ( (0,,))
2 E
(4) 1- 31 x² +
(1 3,)
+ E (0. 13
1+ (1- 3,) Bz)
where (b) comes from the independence between mizi -
[
and E [mas]] - (,F,(0,-1) with respect to {E (c)
is due the fact that (a + b)2² < (1 1-81
0² +
1
+
b²
-
13

---

Refining Adaptive Zerdttt-rrer Optimization at Ease
A.4. Proof of Thm. 5.4
Based on our Thm. 5.3, we naturally can bound m as below
m 21 |] EE |
1)]
< (1+B))
- -V.P + (1+ 1
31
E
(V.
(35)
- (1 - 81)23 + 81 (1(1+ + 3,
(1 + 31)
+
B E
(1- (1 32)
As v1,; is the moving average of mi,; we conclude our proof for Thm. 5.4 as below
[ = K. (3002 + (1 - 82 m
(1 (1-BI)E* + B1(1 (1++3))
(1 +1 81)² (1+3)²
E (0.
$ E 11320/-1.8 + (1-
(1 (1-3) (1 32)
3
(36)
(1 - -1)= [1++8))
(1+
S 81200,s + Σ (1 B2)
E
V Fx [[F
(1 (1-3))(132)) 32)
11
S 020 + (11-1110 (1) + (1 + (1+
Σ
(1--82)82 E (0.11))
(1- (1) 32)
31
7=1
A.5. Proof of Cor. 5.5
Similar to the proof in Appx. A.4, let gt = (((=-))) we have
E
gt.1
27
= E
gt.
v.Fr(0,-1)
+ (
31
+1++1++111011 1, 59
1+
E [1
1
1+ 81 + $7
E
gt. (.
Br
(37)
(1 81)
(1+ 31)2
2
E
V.F, (0 (1.-))
1 + 31
+ 8
B1
Consequently,
E [e. =E( [B + (1- (1))9i
< <1[320 1,] +11 - (2)
(1+
x2 +
(1+
E
V p (0, -1[]]
(0)-))))
11+B7+ + $
11
(38)
S S.o0. + (1+ 11)
(1+ 31) (1+
Σ (1 12) E
V (0.1))
1+8 + 87
-=1
(1 + 31)
$ 2 1 (1+ +
Σ (1 - 22) E
B1
1=1
which concludes our proof for Cor. 5.5.
14

---

Refining Adaptive Zerotth-rrrr Optimization at Ease
A.6. Proof of Lemma 5.6
By applying Hölder's inequality twice, we have the following
T-1 BIIV +
I
v 3/ 1lll + 5 1)
| P. (0))
2
E
B2
1
+
7
20
v B2 |100 || + 5 1)
(0.F)(.)) 113
$)
Σ
E
v
B2
| +c) 3
E
(39)
7.9
+5] )
[+)))
B/ 20 + )
T
E
32
22
E
t=
1=0
which concludes our proof.
A.7. Proof of Lemma. 5.7
Based on (34), (35), and (36), we have
2e = 1,, + (1 - 32) my
S $1200111 + (1 - 81) (1 + 31) | 1 (1F) 2 (1+ 3, 11) V (.()))))))))))
= -,000111 + -11 {2)
(1+ B1) [m,,- -E EE [m,.] 1 (m, - E (m,))) (B [ma,]] ((F(((--1)
+ +(1-81)
1
Blm - (011) + V. [.F (1+ 31
1
111 (.-1(0
1 3
31
S 53/00.+ + Σ
(1- 132)) (1 + Bi) (I,..-E [m,,,,]] +2 2 (m, - E mm,)) )) (E [m,,] (.F1(0,-1))
r=1
+ (1
1
E m (
+ (1+
31 [
1- 3
(40)
Consequently,
T-1
V 3/ |el| + s]
T 1=0
(0)
T-1
V +
ΣΣ
E 12
T
1=0
(41)
1 1 31
+
VB&V+ +
v3, Σ /1
E [V.
( VC++ (1+3:)v 1
Σ E [|VF
VB -B2) T
where (a), (b) comes from the fact that
v Eim aj < DE= Va In addition, (b) also results from Jensen's inequality by
getting the square root of (0,,)) within the upper bound of v,,; first (i.c., (40)) and taking expectation over it later, and (c) is due to the sum of geometric series. Finally, (c) is also the consequence of the sum of geometric series.
15

---

Refining Adaptive Zerett--Orrr Optimization at Ease
A.8. Proof of Thm. 5.8
Inspired by the proof of Adam (Kingma & Ba, 2015) in FO optimization (Wang al., 2024a; Zhang et al., 2024a), we focus on the study of the potential function F (x1) with 2; defined below:
22 0 -3///B20.-1
(42)
1- 3111332
Consequently,
31/V32
2, - 1 1-81/VB
(0, 9.-1)
(43)
and
01+1 0 3./v525 (0. 0(-1)
144 2,-
- 1-31/v8
(44)
m//41// 1/ 1441 + 5 + m m. /220n
1 1-31/BB2
According the Lipschitz smoothness of function Fr the following holds conditions on F,, i.e., the stochastics up iteration t:
Vdl. 2
E (T & (x,) + +E (VF, (x,), x2) [F,] +
E
1 - 1111215,
(45)
We first reframe the second term on the RHS of (45) as below using the update rule in (7):
E 2041, x1) [F.]
E
[VFF 0z), - - mx) [F + E (FF - (0,) - -x,) [Fe
E [ (F,((0)) (0.). -n(1 - 3 / O,, E141)
Fr +I (F,,(0)), - /ve+i + + + n/m, / +
(1 3
32 +
1 B1/ 3//v/2
(.)
n m B2u, + B35 - m, / +5
+
F + (VF (0,), Fe+1 x.) Fr
1- B1/
(46)
We then bound the ① 1D.2... 3 and 4 term above separately. To begin with, we have the following based on the expectation
of & f0 E++1):
V (O)). -7(1 3,
/ SO,, (111)/ 122 +
① e B.
Fr
1- 31/V32
(47)
-n(1- -B1)
(.))
Σ
1-3///6
1B2 +C
16

---

Refining Adaptive Zrreth-Orrerr Optimization at Ease
In addition, 2 can be upper bounded below:
-1m
/ U41 + + m V220 +
A
(0.))
F2
1 1 -1/v/82
(1- Bo 32)m m
E
F,
B1/V32
VI+1I + 15/B200 B206s + CCV B200 +S+ Ve+1. + ()
IN
(.F.(
-1 F2mi+t.
"
E
Fr
B1/V32
3/2 : +
B2 + +C+ VVOLL +
WV
"
[.F2,
70
E
vI - 32m
Fr
B1/V32
270 B2ui, +
2 B2 +
V1. + +5+ v /utti + -
BBB
/mit
(1-32) 32) 2
Σ
"
E
(VB20r, + +S+ + voet1A + +c) (1)
Fi
1
B1/V32
270 1 +5
2/ 12 +5
(48)
1m1
V.F, (0,) 2
YBB
2
B1/V32
Yo / 12 +5
2
C (B2ue, + V0tti+++0 + F/ 1
1441,i - 32
x E
U141. + B3
[.F((00)1
BB
m mit1..1FF
(
E
Vuttis + (1)
F
B1/V322
2 PooVB BRUE, +C
2
V2uUe +5
Σ n(1-B,)
(..2(
d
Anc² d2
1
E
F,
4(1 81/VBB,
1320i+C +5
(1 (1- 11-3/VB5011 - 3i
(B20 +
Mo+is +
|msti.a| Vorsiits
m
where (a) is due to the update rule of second moment estimate in (6), (b) results from
(c)
2ob² (d) is from the update rule in (6). (f) can be obtained by choosing To = I-3 and v /B2ue.5 + + > VT. v1 31 mr m 12
from ab 270 2 and (g) results from (35) and (50) below.
K s(0 + uugziE) 5(0;5)
v.((0,))
=
u
K
d
K
f(0 + uugz {) - [(0;E)
(49)
K
11
h=1
2Cd
<
m
= (1- 81) Σ - v ff (--1))))
S (1 - 31) Σ - V
(50)
2Cd
$ p
17

---

Refining Adaptive Zerdtt-OOrer Optimization at Ease
Let 2/2 1, ① can be bounded as below:
m
u3 + +325 7,,,m
/V22 +
- E
(0.)
F
1- 1/31/B32
11,1
(1 - 32)5 m
12
BBUU, + 325 V B3 + [(( /2 + B2C + v BBu0ri + 5)
n
B2V
VB2U.i+ (())
1 81/BB2
+
(51)
13Ive
(1 32)
B1/VB2
271 V B2 +
B/Bee +
1SIVS
7 (1 -32)d
B1/VBB
2/V B200,1 +
2(1 /2/1322)
i=1
11(1 31)
(0,)
n1 B22dd
4(1 - 152
m B2 +C
(1
where (b) results from
m m and 232 2 1, (c) is from ab S a² Voitt
2m + 716"
2 and (e) is obtained by choosing
1 m,
28, 71 1-2,
Finally, ④ is bounded as below:
E (V:, VF,((e)) F241 - -xt) [F(]
B1 3.1./V32
0 O0, - 1 (O,, 02-1,8)
E
10--0.111
F,
B1/vBL
1 1.1//////
IA3
L/2//32
100 0
0,-111
Vdl 0.+1. Oc.i?
10, -
0-111
va
O
2
+
+ 1../v 3
Fe
81/V32)
2vd
2
2vd
2
B/LVA/VB2
(1++28// /v B2)
EE |10, - -0-111 |Fi]
+3 |10 0,11² Fi
2(1 - 2./v52)²
L Vd/VB2
Σ
1 11+281/v 12
E
mi,i
Fr C
+
m
Fr
2(1 - 31133)22
Ves
U
+
iml
(52)
where (a) is from (43), (44), Cauchy-Schward inequality, and the Lipschitz smoothness of Fp. in Lemma 5.2. In addition, a² yab²
(b) is from ab < 2va 2
and (d) is based on the update rule (7).
we finally bound the last term on the RHS of (45) as below:
dd.. E ||4411 2
VaL
1
E
1 0.,
2(1
/1/V33/
VOL
E 22
0z,1 2 |F]
00,, 0
2(1
31/VB8)
VdL 2
m
m
E
F,
+
31/V3,)
De+1.8
Ve,i
(53)
18

---

Refining Adaptive Zereth-Order Optimization at Ease
By introducing (47), (48), (51), (52), (53) into (45), let B1 S B2,, m,,i 0, v0,3
O. have the following
E ( - E (x))))
t=0
S 2(1 - 311332)
1111 -1)
T-1
ΣΣ E
V F (0.) 21
ΣΣ 2(1 - 31/
3vāli²
T-1
E
mi+1
+
12 + {
Ue+1.5 +
5V
T-1
ΣΣ
miss
+
T-1 d
(1- 3 (1) BiD E
4n 2 d²
2(1 31/vB2)
V1.5 +
[BBuurs +
1=0 1=1
1=0 i=1
n - 32)2// T (1 31/vB2) 31)
(11 31)
T-1 d
V (.F+( 27
AVOL
d
In ((8 Vo,s
00 +4C2 u0² /vo,s)
ΣΣ E
< 2(1 - B1/ (22)
+ 22
+
V V22U +
(1 (1-31/v
7
1- 1-B2
1=0 1=1
1=1 no (1 12)
cncCd d
1
T(1 B2)
+T (1- 311 31)
T
- 81-8/1B)111- 21
V5
VS
(54)
where the last inequality comes from the following (55) and (57).
T-2
1 VOLLIt
1
- E
B2 +
v B2
No,
12 +
V +
(vr +
T-1
VB₂
Σ E
+
VC
V
B2414111 +6
VB2 +
1=1
T(1
B₂)
VC
V5
(55)
Moreover, due to the fact that Ita 2 In(1 a). the following holds:
(1- m,)m
(1 - B2) B2
21. (1-Bg) Bo)m
(1 - B2)
14.5
U1i1
< In 1+
In
In
In (B2)
Ut
1 + 0e,4 -r,-(11 (11--1mmii,
(1.
U4 - (1 - m,
B2
01-1.
(56)
Given the results above and 232 2 1, we have
E
Mi.
5
1
(E
[In (UT,s)
In (vo.i) - -T B2)
Vei + (
1
82
1=0
< 1
UTT ) + (b2))
In
E
(57)
32
Vn.i
1
3 Ua,i
+ 4C28 d2/11²
<
In
+ 2T
32
Vo.i
where the second inequality is due to In a S a and last inequality comes from (50).
19

---

Refining Adaptive Zeroth-Order Optimization at Ease
Define A (x))
Fi by re-arranging (54), we have
d In ((05 00 + +4C2dP/1² /woos)
T-1 d T t= 1m1
(O.)
27
-11-3//V324
8LIVA d
E
S
Σ
+2 +2)
+
V [
nf 31)
(1 - 81/v322 32) (1- 83))
T(1 r(1-5)) (2)
802d3
1
+ 1- 122 ) + 2.39 (1 - 32)d
(1- 11)22
TVV
Vc
(1 (1-3,)²
(58)
By choosing 1- B2-
8C2d"
28
2/3 OEE), (2
16LdVa
2/3 O(e²) and
11) v<
(1-8))
T = 3e
1/118/1/ 12)
80282 (1-8,) VE
BLyva
Ei=1
In (33 No., +400 dp /v /mb.t))
))
OlE 4)
1(1-8)
(1-8//88-11--8
(1-Ba)
can simply have the following,
VF (0)1
[..1( (BzuL,t +
E
ΣE E
56
(59)
T
B2 U1
+
where the first inequality is due to the fact that E3 (a//E,
= a. b,b, S La/b; We therefore conclude our
proof of Thm. 5.8.
A.9. Proof of Thm. 5.9
By introducing (41) and (59) into Lemma 5.6, we have
B2 1o +3) )
( E
B [|
(011))
E
T
T 1=0
B/ 11 +5
(60)
V[+Vd+
(1+3) 1
[[VF, 2
E
V - 32) T
By applying the formula for the root of square equation, we have the following
R [[VF,,00) S (1+ 6² + (VC+vVaje.
(61)
T
(31(1-3))
which concludes our proof for Thm. 5.9.
A. Proof of Thm. 5.10
We first introduce Lemma A.1 and Lemma A.2 from (Wang al., 2024a):
Lemma A.1 (Lemma 6 in (Wang al., 2024a)). The following inequality holds for ZO-AdaMM
if0 < B < <1,
My,i
1- 3
(62)
Vo, +
VI B2
87/12
20

---

Refining Adaptive Zerothh-rrrr Optimization at Ease
Proof. Let -r, A (0,(00, we have
(1 (1) -= $1
m4,i
Maji Ve,i
Jr.i
00.5
+
1(1 B2) Ex= $2 gr,
t-T
V - 12 7 2
gr,.| V -t= (8112)
1 1- $
(63)
V1 32
V
Σナ=o $2 gi
1 B1
1 1- (8918/)
v1
12 V
where (a) is due to the Cauchy-Schwarz inequality.
Lemma A.2 (Lemma 5 in (Wang et al., 2024a)). The following inequality holds for 70-AdaMMM ifo < B <B2 <1,
B₂) mi; < 31- 1 +
(mn
UT Vn
T In 82
(64)
(1 - 322
Proof. Let Ir, A (,J(O,, Sr41), similar to (56), we have,
(1 B2) g
VT 1%
< In
-I'm B2-
(65)
21 +
Besides,
my,i
my,i
< (1-18 (1-B1) Σ
t
3
97.1
S (1 31) Σ
$1
gr.1
(66)
Ue, +
v U2
Ut
v32
U7.1
Therefore, we have,
(1 32) mi.s
(1- (1 -1)
T-1
Σ
Σ
31
9
24 + +
VB2
V
(=0
1=
7=
(
1-2 (1 - B,) Σ
Σ
8
3
t-r
VB,
VB2
77.5
<(1 82)
(1- T-1
ΣΣ
3
g
2
1- 8//V22
VB2
(67)
( (1- 32)
(1 (1-3))
T T-1
Σ
B
9
1- 81/VB2
VB2
T=0 t=r
(1 - -1)
T-1 (1 32) gh,
B1/v33)
Ve.i
(4) (1 (1-3))2
In
UT
Tin 32
- 13)
Ug
where (a) comes from Cauchy- Schwarz inequality and (c) is due to (65). In (b) we exchange the order of summation over t and 7.
21

---

Refining Adaptive Zeroth-Order Optimization at Ease
Following the proof idea in Appx. A.7, have the following for 20-AdaMM,
E
32
1/e
T-1 ΣΣ
V +
(68)
T-1
1+ 31
V T
ΣΣ
VBV +
Σ
v By
1=0
r=1
2 V (1+ Bivvd
E VF,,
VB B₂) T
t=0
where 2 A |1o|= + (1 B1)
K²²
In addition, following the proof idea in Appx. A.8, we have
E
xx) [Fr
(0.) -n(1 - 31 O,,, E1t1)
mm++1/ 1// 1 + + nm 11/ 1B20 +
E
F, +E VF (0.).
F,
(1 (1-311 /1llB1/B222/ B20, +(
1- 3./////
!
(F, n3 m. /ttl/BB20
B2U, + 325 - 11,3 hlllm./BBBBBB B22 + (
+
F. + (VF, VF,(0,) Je+1 - xx) Fr
1 P1/
4
(69)
where each item be upper bounded as below.
①- - 71 - 31)
V (..)) 2
Σ E
8///B/222 1=1
B2ore +C
n11 (1)
(0.1
4n/(1 C2
1
EE
F,
4(1 81/vB2)
13200 +
(1 (1 32/32)11
1320r +6
Vestie
3 < 11-BB)
(O))
- (1-31/V33)) - -89132)
4(1 111-81 -1///3)
V +
4 L V// /32
(1+22// 23, 23///8//// B2 E
Di.i + |Fr +E
mi,i
m
2
[Fr 1)
2(1 3//33/
D441, +
(70)
Here, both 2 and 3 results from Lemma A.
22

---

Refining Adaptive Zeroth-Order Optimization at Ease
Finally, we have
E F (1(412) - E (xx)))
1=0
< 2(1 Bz)
1 - -11
ΣΣ E
T-1
AVdLi (1 - R₂)²
Σ
d
In (82 vo,s + +40²dd 2//1²) /w0.s)
+ 2T
VB2u, +
(1 1/.3///3/
1 1- 32
(=0 i=1
1=1
4n(1 - C2 d
T(1 T(1-B2) Ba)
) T n (1
+
(1 (1- (1/3//3) 12)
V5
VC
(11 - 18132)
(71)
Define A 2 (x1)) Fi by re-arranging the result above, we have
In (5S v0,s + +4C2&/1²) /00.2)
(0,) 27
211-81/V32)
8LAVA(1 B1)
d
Σ
E
S
+2 +
T t=0
V2 5
nT(1 B1)
(1-81/V32)
T(1 12)
1=1
i=1
8C2d2
-113a)
2,89 (1 - -B2)dV3
(1 81132112 2
TVV +
+v²
VT
1- -//1/2
(72)
By choosing 1 1 B2 = (1-B (Da)
+ 20
2/3 ~ 0 = 16LAVAL-AA)
2/3 ~ O and
1-3//00
(1-31/132)*
T = 3c 2 2(1 221-B./VE A
+ 8C28
+
8LA a(r/((1-3))
Σd
[n((055 [1n((8500,+1104 v0,
//2n)//o.)) )/00.))
))
O we can
(1-)))
(1-0918001 vE.
(1- /22)
(1-82)
simply have the following,
(0,)
T- d
V V.Fa (0,) 27
E
E
Se
(73)
B2
12
+
BBuE, +
t=0
By introducing (68) and (73) into Lemma 5.6, we have
T (001)
T-1
(+ E
|VF,,0,)11
T E
B2 10l1oll [Vsllbaal+ +s}
T
v Be 11 +
1=0
1=0
(74)
VS+
(1+ 31)a 1
Σ
E
e
( -
t=0
By applying the formula for the root of square equation, we have the following
(1+8)vd 2+ (VT+ VVd)e, c.
Σ
(0) - (B -3))
(75)
which concludes our proof for Thm. 5.10.
23

---

Refining Adaptive Zerett--rrrr Optimization at Ease
B. Experiments
B.1. Experimental Setup of Synthetic Functions
Let input = [0.]/=1- the Quadratic, Cubic, Levy, and Rosenbrock functions applied in our synthetic experiments are given below:
F(O) 2 1=1
0
(Quadratic)
03
F(0)= Σ
10,13
(Cubie)
(76)
d-1 Σ
F(0)= = sin 2 (Tw,) ) +
[1 - 1)² (1 11 (Tw; + 1)) + (wa - 1)² (1 (1+ sin sin? (2TTa))
10
(Levy)
1=2
d-1
F(0)
Σ
100(0:41 - 0²)² + (1-0,)²
(Rosenbrock)
where W, = ++ Note that all functions have the same minimum of zero, i..., min F(0) = 0. For a fair comparison, we employ the same initialization and hyperparameters: B1 = 0.9, B2 = 0.99 and K 10, 7) 0.001, 1 0.005, for all methods.
B.2. Experimental Setup of Black-Box Adversarial Attack
For the black-box adversarial attack experiment on the MNIST dataset, we use the same fully trained deep neural networks from (Shu al., 2023) and adopt Lo constraint of 0.2 on the input perturbation. For fair comparison, we employ the 0.01, μ 0.005, for all methods.
same hyperparameters: B1 0.9, 32 0.99 and K
B.3. Experimental Setup of Memory-Efficiint LLM Fine-Tuning
For the memory-efficient LLM fine-tuning on OPT- 1.3B and OPT-13B on SST-2 dataset (Socher al., 2013), we adopt the same configurations in (Malladi et al., 2023) and choose to fine-tune LLMs with LoRA adapters. For fair comparison, employ the same hyperparameters: B1 0.9, 82 0.99 and K 7 0.00005, μ 0.001, for all methods.
24


Reviews:
[{"review_id": "bjhNOH67hV", "reviewer": "Reviewer_FBQc", "summary": "This paper proposes an improvement over existing adaptive-gradient methods for zeroth-order optimization (ZO). \nIn ZO optimization, to minimize a function $\\min_{\\theta \\in \\mathbb{R}^d} F(\\theta)$ where $F(\\theta) = \\mathbb{E} [ f (\\theta;\\xi)] $, we can only access noisy function values $f(\\theta;\\xi)$. ZO methods use a finite difference of functions as an approximation of the gradient : $\\hat{\\nabla}f(\\theta;\\xi) \\triangleq \\frac{d}{K}\\sum_{k=1}^K \\frac{f(\\theta +\\mu u_k;\\xi) - f(\\theta;\\xi)}{\\mu}u_k$, where $u_k\\overset{iid}{\\sim}Unif(\\mathbb{S}^{d-1})$ and $\\mathbb{S}^{d-1}$ is the $d$-dimensional sphere with a fixed $\\mu>0$.\n\nZO methods suffer with high noise variance for their estimated gradients especially for high dimensions $d\\gg K$. And this \n\n1. The authors claim that momentum methods, however, offer some sort of \"automatic variance-reduction\" to handle this. \n\n\n2. Existing baselines which use momentum, for instance the ZO-AdaMM(Chen et al 2019), that uses  $\\hat{\\nabla}f(\\theta;\\xi)$, instead of the true gradient in Adam, however, do not take advantage of this fact. The authors propose a small modification of ZO-AdaMM, to get R-AdaZO(Algorithm 2), that estimates the second moment as $v_t \\gets \\beta_2 v_{t-1} + (1 - \\beta_2)m_t^2$, where $m_t$ is the momentum term. Note that AdaMM uses, $v_t \\gets \\beta_2 v_{t-1} + (1-\\beta_2)g_t^2$, where $g_t$ is the ZO estimate of gradient.\n\n3. **Theory**: \n    1. The authors show that estimates of second moment $v$ are smaller for R-AdaZO than ZO-AdaMM by incorporating the variance reduction due to momentum (Theorem 5.4 and Corollary 5.5).\n    2. The authors use a \"variance-aware\" convergence analysis for non-convex $F$, by bounding norm of $\\nabla F_{\\mu}(\\theta)$ where $F_{\\mu}(\\theta) = \\mathbb{E}_{u\\sim Unif(\\mathbb{S}^{d-1})}[F(\\theta + \\mu u)]$ is the appropriate objective for ZO methods. They show that existing analysis of ZO-AdaMM is limited as it considers only one term of the upper bound on gradient norm obtained by a Holder's inequality in Lemma 5.6.\n    3. In Theorem 5.9 and Corollary 5.10, they show that their method obtains a strictly smaller error in gradient norm than ZO-AdaMM with the difference being an additive term of $\\sqrt{V}$ for R-AdaZO v/s $\\sqrt{\\hat{V}}$ for AdaMM, with $\\sqrt{\\frac{V}{\\hat{V}}} = \\mathcal{O}(\\sqrt[4]{\\frac{1-\\beta_1}{1+\\beta_1}})$.\n\n4. **Experiments**: \n    1. For optimizing synthetic loss functions(Fig 1), fine-tuning an LLM (Fig 3) or performing a black-box adversarial attack (Table 1) their method is significantly faster than baselines AdaMM and RMSProp with ZO gradient estimates.\n    2. In Figure 2, they show that the error in first moment $m_t$ and second moment $v_t$ wrt true gradients is much smaller for their method. They also show its behavior for different $\\beta_1$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their diligent, detailed, and constructive feedback, and appreciate the time and effort invested . We found the comments very helpful and address each point below.\n\n---\n> Incomplete proof\n\nThank you for highlighting the need for clarity regarding Corollary 5.10 (ZO-AdaMM). You are correct; its proof requires adaptation from Theorem 5.9 due to the different second moment update rule ($v_t$). While our overall variance-aware framework (Lemma 5.6, Eq. 45/46) remains applicable, the specific bounds for terms ①-④ within Eq. (46) must be re-evaluated using ZO-AdaMM's $v_t$.\n- **Terms ① (Eq. 47) & ④ (Eq. 52):** The bounds analogous to (47) and (52) hold for ZO-AdaMM.\n- **Terms ② (Eq. 48) & ③ (Eq. 51):** We can adapt **Lemma 6 from Zhang et al. (2024a)**, which provides a bound for $|m_{t,i}| / \\sqrt{v_{t,i}+\\zeta}$ in the context of standard Adam (where $v_t$ uses $g_t^2$). Applying this lemma (adapted for the ZO variance $\\Sigma^2$) allows us to obtain bounds analogous to those derived through (48) and (51), although the constants involved will differ.\n\nFor bounding the summation terms analogous to (56)/(57) in the ZO-AdaMM proof, we leverage **Lemma 7 from Zhang et al. (2024a)**, which handles sums involving $v_t$ based on $g_t^2$. Combining above, we can rigorously derive the rate in Cor 5.10. This rate depends on $\\hat{V}$ (reflecting the $g_t^2$ update, Cor 5.5), confirming R-AdaZO's theoretical advantage via the smaller variance term $V$ (Thm 5.4).\n\nDue to rebuttal space limits, we provide this proof sketch; a full derivation referencing these adapted steps will be included in the appendix of the revision. Thank you again for your careful analysis.\n\n> Justification of Assumptions\n\nRegarding Assumption 1 (8): While the upper bound is strong (especially for quadratics/unbounded domains), it's a common theoretical tool (like bounded gradients in Chen et al., 2019) essential for controlling variance and deriving convergence guarantees in non-convex stochastic settings. Our theory relies on this standard simplification, but experiments confirm R-AdaZO's practical robustness where it doesn't strictly hold globally.\n\n> Final Convergence Rate\n\nYou're right, the overall speedup requires the variance term ($V$ vs $\\hat{V}$) to dominate. We contend this is common in ZO due to high estimation noise, making R-AdaZO's better variance handling crucial. Pinpointing exact dominance conditions is hard, but our analysis highlights the structural gain against this main ZO challenge. We'll clarify the remark on Page 7 to state the speedup applies primarily when variance dominates, matching typical ZO scenarios and our results.\n\n> Methods And Evaluation Criteria:\n\nThank you for the feedback and suggestions. Regarding Fig 2(a), cosine similarity visualizes the improved *directional alignment* of $m_t$, complementing the squared error theory. Metrics in Fig 2 are averaged over the trajectory. We will clarify this rationale and the averaging. We also agree the black-box attack justification needs explicit motivation (its relevance as a key ZO application due to lack of gradient access for attackers) and will add it. These clarifications will be incorporated.\n\n> Theoretical Claims & Other Comments\n\nThank you for your meticulous review and for carefully checking all the proofs. We appreciate you pointing out these minor errors in the explanations. We understand they don't affect the core correctness of the proofs, and we will certainly correct these textual issues in the revised version.\n\n> Essential References Not Discussed\n\nThank you for the feedback and for acknowledging our discussion of key references. We appreciate you suggesting the additional references on smoothing (Nesterov 2005, Duchi et al. 2012) and will certainly incorporate them into our related work section.\n\n> Dependence on dimension $d$\n\nThank you for highlighting dimension $d$ dependence. Our analysis uses coordinate-wise Lipschitz, standard for adaptive methods but differing from Euclidean Lipschitz (e.g., Chen et al. 2019), making direct $d$ comparison complex. While $d$ is implicit in our terms, our focus was demonstrating variance reduction and the refined second moment's benefit under this framework, not optimizing $d$ dependence. Achieving sharp $d$ bounds is a valuable, challenging direction for future research.\n\n> Extension to gaussian\n\nYou are correct, our proofs leverage properties of the uniform sphere estimator simplifying bounds like Eq. (50). Gaussian smoothing's different statistics require adapted tools and assumptions (e.g., concentration inequalities) for analysis. Adapting our framework needs re-derivation, not a quick fix, though R-AdaZO's core principles should still apply.\n\n> Questions\n\nAll the remaining questions will be addressed in our revised version due to space limit.\n\n---\nWith our elaboration, we hope our response has addressed your concerns and increased your opinions of our work.", "claims_and_evidence": "Several theoretical claims are justified by corresponding Theorems and Corollaries mentioned in the Summary as well the Remarks following them. The theoretical claims that are problematic or not justified are explained below --\n\n1. **Incomplete proof for Corollary 5.10**: Corollary 5.10 provides the performance of the baseline ZO-AdaMM under the authors' proposed variance-aware convergence analysis. The authors do not provide its proof and claim that it can be obtained by simply following the proof of Theorem 5.9, which is their method R-AdaZO. I do not think this is the case, as several steps in proof of Theorem 5.9 utilize the exact update of R-AdaZO and might not work for ZO-AdaMM with a different update. These steps are  -- i) Eqn. (46), which is the main bound in the descent Lemma, specifically terms $2$ and $3$, ii) Eq. (56) and (57) which basically bound the convergence rate for $T$ update steps. These are important steps in the proof of R-AdaZO and without any explanation of how these would be addressed for the baseline ZO-AdaMM, it is unclear if the claimed rate in Corollary 5.10 is actually achieved for ZO-AdaMM, and if it is indeed worse theoretically than R-AdaZO. This is one of the main reasons for my rejection, and I would be willing to change my assessment if the authors can provide this proof.\n\n2. **Justification of Assumptions** The assumption that the function values are always bounded in Assumption 1 is extremely strong. Several works assume a lower bound on the function value, but assuming an upper bound on the function forces some form of subgaussian tails on it. If the domain of models $\\theta$ was a closed compact subset $\\Theta$ of $\\mathbb{R}^d$, then this assumption could be justified. Even then, the authors would need to specify the value of $\\mu$ so that any noisy evaluation $\\theta + \\mu u$ is not outside $\\Theta$. Note that none of the synthetic functions used in their experiments except the rastrigin function are unbounded for  $\\theta \\in \\mathbb{R}^d$. Note that this also doesn't hold for a quadratic function.\n\n\n3. **Final Convergence Rate** Assuming that Corollary 5.10 is actually correct and the authors provide a proof in their rebuttal, it still does not imply a speed-up in terms of the final convergence rates for R-AdaZO compared to ZO-AdaMM theoretically, as the error terms where these two algorithms differ might not be the dominant term in error. The authors should thus write down precise conditions when this does not happen, in terms of $d, \\beta_1, \\beta_2,\\zeta,\\mu$ and the initialization $m_0, v_0$. Further, the authors should check what is the maximum possible speedup possible in convergence rate in terms of $\\epsilon$ instead of keeping the speedup in terms of $\\beta_1$ for only additive terms? Note that in the current form in Remark on Page 7, R-AdaZO does not denote a speed-up as long as the terms of $\\hat{V}$ and $V$ are not the dominant error terms in Theorem 5.9 and Corollary 5.10, as only then do they actually decide the convergence speed.  \n\n\n**Experiments**: Note that the experimental performance for their method is significantly better than baselines for both synthetic and real tasks as demonstrated in Figures 1 and 3.", "methods_and_evaluation_criteria": "The experiments on synthetic data and finetuning had all the sufficient details.\n\n- **Is cosine similarity a good metric in Fig 2(a)?**: In Fig 2(a), the authors compare the cosine similarity between actual gradient $\\nabla f(\\theta)$ and the momentum estimate $m$ from ZO-AdaMM and R-AdaZO. In Theorem 5.3, they bound the expected squared error coordinate-wise for this quantity, so measuring cosine similarity instead of squared difference does not seem appropriate. Further, for both Fig 2(a) and (b), we don't know if the error is measured using momentum at a specific time of the algorithm or averaged over the algorithm's trajectory. This detail is important for momentum as it might not have kicked in early in the algorithm and saturated if measured very late.\n\n\n- **No justification for black-box attack experiments**: I don't understand the reason for testing an optimization algorithm on black-box attack. The authors only state \"Following the practice in (Shu et al 2023)\" in Line 367 2nd column as the justification. In (Shu et al 2023), I would the actual reason for this, as black-box attacks are an important application for ZO optimization, as an adversary can only access the function values during attack. I think the authors should mention this justification in their paper as well.", "theoretical_claims": "Yes, I checked all the proofs.\nApart from the issues mentioned in \"Claims and Evidences\" section, there are several minor mistakes in the proof. These errors are mostly in explanations not in the equations and they don't break the proof.\n- Lines 561 and 562 should have $\\leq$ instead of $=$ as a Cauchy-Schwarz inequality is used.\n- Line 927 : The authors used $\\frac{a}{1+a} \\leq \\ln(1+a)$ in Eq (56) and (57) but wrote down the inequality $\\ln(1+a) \\leq a$.\n- Line 963 : The inequality should be $\\sum a_i/b_i \\geq  \\sum_i a_i/\\sum_i b_i$ for $b_i \\geq 0$, which is what the authors actually used. They mentioned the inequality in the opposite direction.", "experimental_designs_or_analyses": "Yes, I checked all the experimental designs and analyses.", "relation_to_broader_scientific_literature": "Crucially, the authors use the variance-reduction properties of momentum first observed in (Liu et al 2020) for first-order optimization, i.e., with access to gradients. Using this insight for the problem of adaptive ZO optimization, shows that simply applying ZO gradient estimates to Adam is suboptimal and the small change in R-AdaZO actually results in better convergence.", "essential_references_not_discussed": "I think most essential references were discussed. They have a  showed that the variance-reduction was observed originally in (Liu et al 2020), but they were the first ones to use it for ZO updates. Further, they discussed the main baseline for adaptive ZO optimization : ZO-AdaMM (Chen et al 2019). They missed a few old references on the smoothing, which is exactly ZO optimization but the analysis utilizes smoothness of the resultant function $F_\\mu$ (Nesterov 2005, Duchi et al 2012). Note that the \"variance-aware convergence analysis\" mentioned in Section 5.3 seems to be analysis in terms of the smoothed objective $F_{\\mu}$ which has been performed in the references I mentioned, although not for Adam-style adaptive algorithms. \n\n**References**\n- (Nesterov 2005) Smooth minimization of non-smooth functions. Math Programming.\n- (Duchi et al 2012) Randomized Smoothing for Stochastic Optimization. SIAM J. OPT.", "other_strengths_and_weaknesses": "1. **Dependence on dimension $d$**: Note that the authors have not explicitly characterized the optimal dependence on the dimension $d$ in Theorems 5.9 and Corollary 5.10. Note that the noise variance in ZO is high because it grows with $d$. In adaptive Adam-style optimization, the goal is to use different learning rates for different coordinates and the analysis is on a per-coordinate basis. Therefore, for ZO in Adam-style algorithms, the dependence of error on dimension $d$ is extremely important. Further, several steps of the analysis involve changing norms from coordinate-wise to $\\ell_2$, so I suspect the dimension dependence is not good. Note that the error in baseline ZO-AdaMM (Chen et al 2019) for the term $B$ in Lemma 5.6 was $\\frac{\\sqrt{d}}{\\sqrt{T}}$, thus giving a $\\frac{d}{\\epsilon^2}$ error bound. Can the authors provide sharp bounds in terms of $d$ as well?\n\n\n\n\n2. **Extension to gaussian smoothing distribution**: The authors sample the random vectors for gradient estimate from a uniform distribution on the sphere. Instead if the random vectors were sampled from a gaussian distribution, which in high dimensions is extremely similar to a uniform distribution, the proofs would not go through as several terms bounds won't hold, for instance Eq (50). Is there an easy fix for this gaussian extension or are the methods designed specifically for uniform distribution on the sphere with bounded function values (Assumption 1).", "other_comments_or_suggestions": "- **Writing**: Some parts of the writing can be improved. For instance, there is some repetition of the main claims verbatim atleast $4-5$ times in the paper. See the following typos --\n    1. The unit sphere in $d$ dimensions is referred to as $\\mathbb{S}$ instead of the standard $\\mathbb{S}^{d-1}$. If non-standard notation is used, it should be specified in the problem setup (Section 3).\n    2. The exact formulation of optimality gap (in terms of either gradients, function values or iterate distance) in the synthetic experiments was not specified.\n    3. Line 919 RHS of first equation: $\\frac{1}{\\sqrt{\\beta_2}v_{0,i}+\\zeta}$ -> $\\frac{1}{\\sqrt{\\beta_2 v_{0,i} + \\zeta}}$.\n    4. Line 858: $\\frac{|m_{t,i}|}{\\sqrt{1-\\beta_2}|m_{t+1,i}|}$ -> $\\frac{|m_{t,i}|}{\\sqrt{1-\\beta_2}|m_{t,i}|}$.\n    5. Line 587 : Missing reference -> Eq (16).\n\nOverall, I am leaning towards rejection due to the main issues in the \"Claims and Evidence\" section. I'm willing to change my assessment if they can address them.", "questions_for_authors": "- How do the proposed methods perform in comparison to other ZO methods that keep track of the history instead (Shu et al 2023)? Are both these techniques completely orthogonal, so that they can be combined to obtain a \"variance-reduced\" ZO that uses historical estimates? \n- As a follow-up for the previous question, are there minmax lower bounds in terms of number of function evaluations for this ZO model, like (Duchi et al 2015)? These could tell us if the obtained method is optimal or if there is room for improvement?\n- Why is there a mismatch between theory and practice in Figure 2(b) for large $\\beta_1$? Can you further expand on why the loose bound is still good for convergence analysis?\n\n\n\n**References**--\n- (Duchi et al 2015) Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations. Trans on Info. Theory.", "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": "fFFU07Lr3L", "reviewer": "Reviewer_6KdC", "summary": "The authors take a closer look at the Adam update rule in the context of Zero-Order Neural Network training and identify a specific change to the second-moment update rule that provides improved convergence theoretically and empirically. \nTheir experimental sections contains synthetic experiments as well as neural-network based experiments.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to Reviewer 6KdC for the positive assessment and valuable feedback! We particularly appreciate the recognition that \"Many good papers stem from simple ideas, such as this one\". We would like to address your concerns below.\n\n---\n> I find formulations such as \"we theoretically show that [...] is likely to be [...] and may better [...]\" to be problematic. I would suggest to clearly separate what is theoretically shown versus what is speculation\n\nThank you for this crucial suggestion regarding the precision of our claims. We agree completely. In the revised manuscript, we will meticulously differentiate between:\n- Formally proven theoretical results: Statements directly supported by theorems and proofs within the paper.\n- Heuristic arguments or intuitions: Explanations for why certain phenomena might occur, clearly marked as such.\n- Empirical observations: Findings derived solely from experimental results. \n\nWe will ensure the language clearly reflects these distinctions throughout the paper for improved accuracy and clarity.\n\n> I'd love to see a more detailed evaluation across more elements from the ZO-Bench suite (https://github.com/ZO-Bench/ZO-LLM) than OPT on SST2.\n\nFollowing your suggestion, we have expanded our evaluation using the ZO-Bench suite. We benchmarked R-AdaZO against ZO-AdaMM on the Copa dataset using the OPT-13B model, adhering to the ZO-Bench setup. The results (loss values) are presented below:\n\n**Performance on Copa (OPT-13B):**\n| Copa   | $T=1 \\times 10^3$ |$T=2 \\times 10^3$|$T=3 \\times 10^3$|$T=4 \\times 10^3$|$T=5 \\times 10^3$|$T=6 \\times 10^3$|$T=7 \\times 10^3$|$T=8 \\times 10^3$|$T=9 \\times 10^3$|$T=10 \\times 10^3$|\n|---------|--------|---------|---------|---------|---------|---------|---------|---------|---------|---------|\n|ZO-AdaMM | 2.527|2.352|2.133|2.004|1.938|1.636|1.579|1.716|1.529|1.696 |\n|R-AdaZO| 2.527|2.051|1.521|1.584|1.482|**1.297**|1.420|1.531|1.405|1.640 |\n\nThese results demonstrate that R-AdaZO exhibits significantly faster convergence compared to ZO-AdaMM on this extended LLM fine-tuning task. This provides further evidence for the effectiveness of R-AdaZO on diverse tasks within the ZO-Bench framework.\n\n> In addition, theoretical analysis showcased a significant influence of $\\beta_1$. It would be interesting to see if that is reflected in the convergence of LLM fine-tuning.\n\nThank you for pointing out this connection between our theory and empirical results. To investigate this, we performed an ablation study on the effect of $\\beta_1$ for R-AdaZO during LLM fine-tuning. We used the SST2 dataset with the OPT-1.3B model, following the setup in Section 6.3, varying only $\\beta_1$.\n\n**Performance on SST2 (OPT-1.3B) with varying $\\beta_1$ for R-AdaZO:**\n| SST2   | $T=1 \\times 10^3$ |$T=2 \\times 10^3$|$T=3 \\times 10^3$|$T=4 \\times 10^3$|$T=5 \\times 10^3$|$T=6 \\times 10^3$|$T=7 \\times 10^3$|$T=8 \\times 10^3$|$T=9 \\times 10^3$|$T=10 \\times 10^3$|\n|---------|--------|---------|---------|---------|---------|---------|---------|---------|---------|---------|\n|$\\beta_1=0.3$ | 1.063|0.736|0.490|0.612|0.414|0.429|0.389|0.265|0.276|0.187 |\n|$\\beta_1=0.6$ | 1.063|0.675|0.387|0.493|0.330|0.360|0.388|0.232|0.282|0.229 |\n|$\\beta_1=0.9$ | 1.063|0.462|0.178|0.289|0.165|0.329|0.251|0.138|0.255|0.161 |\n\nThe results clearly show that the choice of $\\beta_1$ significantly impacts performance, empirically validating the implications of our theoretical analysis in the context of LLM fine-tuning. Specifically, a larger value of $\\beta_1=0.9$ consistently leads to faster convergence and achieves lower loss values throughout the fine-tuning process compared to smaller values ($\\beta_1=0.3,0.6$). This confirms that the theoretical insights regarding $\\beta_1$ translate to practical benefits in this application domain.\n\n---\nThank you again for the valuable feedback. We will integrate the discussed clarifications and new experimental findings into the revision. We hope our clarification will address your concerns and further improve your opinion of our work.", "claims_and_evidence": "The authors claim a new update rule for ZO optimization, the use-fullness of which is well supported. \nThey further claim new theoretical insights, which I didn't parse completely. I find formulations such as \"we theoretically show that [...] is likely to be [...] and may better [...]\" to be problematic. I would suggest to clearly separate what is theoretically shown versus what is speculation. \nThe final claim concerns experimental validation, which is convincing.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I followed the theoretical claims of section 5.1 and 5.1, but did not check 5.3.\nI did not check the proofs in the appendix.", "experimental_designs_or_analyses": "Yes. I see no obvious issues.", "relation_to_broader_scientific_literature": "The wider scientific literature on ZO is focussed on variance-reduction through various theoretical and empirical observations and improvements. This paper specifically is orthogonal to many of these papers and focusses on a single straight-forward change to the Adam update rule.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Many good papers stem from simple ideas, such as this one. I see no obvious weakness.", "other_comments_or_suggestions": "Line 284 left: \"to decompose\"", "questions_for_authors": "While the experimental evaluation is varied, it is not very extensive. \nI'd love to see a more detailed evaluation across more elements from the ZO-Bench suite (https://github.com/ZO-Bench/ZO-LLM) than OPT on SST2. In addition, theoretical analysis showcased a significant influence of $\\beta_1$. It would be interesting to see if that is reflected in the convergence of LLM fine-tuning. Should the authors expand on their experimental evaluation as mentioned, I will consider raising my score.", "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": "Oj62hTEQc5", "reviewer": "Reviewer_MyoC", "summary": "The paper introduces a zero-order optimization technique called R-AdaZO. Specifically, it makes a simple yet seemingly effective modification to ZO-AdaMM. By replacing the second moment estimation term $g_t$ in ZO-AdaMM with $m_t$, R-AdaZO achieves variance reduction compared to ZO-AdaMM and demonstrates a faster convergence rate. The theoretical analysis is thorough.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to Reviewer MyoC for the positive and constructive feedback! We appreciate that the reviewer highly recognizes that our paper is **simple yet effective** and our theoretical analysis is **comprehensive**. We would like to address your comments as follows.\n\n---\n\n> ...the authors should provide a more detailed comparison with other common zero-order optimization (ZO) methods...\n\nWe appreciate the reviewer's suggestion to provide a more detailed comparison with common zero-order optimization (ZO) methods. Following this recommendation, we have benchmarked our R-AdaZO against ZO-SGD and ZO-signSGD on the Quadratic and Levy functions, using the experimental setup detailed in Section 6.1.\n\n**Quadratic Function Performance:**\n| Quadratic        | $T=1 \\times 10^4$ | $T=2\\times10^4$ | $T=3\\times10^4$ | $T=4\\times10^4$ | $T=5\\times10^4$ |\n|---------|--------|---------|---------|---------|---------|\n|ZO-SGD| 5038.056|5028.611|5019.293|5009.897|4997.447 |\n|ZO-signSGD| 3644.077|1983.347|834.561|190.489|2.159 |\n|**R-AdaZO**| **756.743**|**0.599**|**0.029**|**0.030**|**0.030** |\n\n**Levy Function Performance:**\n| Levy       | $T=1 \\times 10^4$ | $T=2\\times10^4$ | $T=3\\times10^4$ | $T=4\\times10^4$ | $T=5\\times10^4$ |\n|---------|--------|---------|---------|---------|---------|\n|ZO-SGD| 6661.504|6625.426|6589.794|6553.917|6506.384 |\n|ZO-signSGD| 4017.191|1579.627|779.139|606.901|562.197 |\n|**R-AdaZO**| **795.038**|**575.398**|**560.107**|**558.741**|**558.716** |\n\nAs demonstrated in the tables, R-AdaZO consistently and significantly outperforms both ZO-SGD and ZO-signSGD. Regarding the ReLIZO approach: While ReLIZO presents a valuable technique for enhancing *ZO gradient estimation*, our current work's primary focus is on improving the *ZO update mechanism*. Integrating R-AdaZO with advanced gradient estimators like ReLIZO is an interesting direction for future research, which we plan to explore subsequently. We believe maintaining this focus clarifies the specific contributions of R-AdaZO in this submission.\n\n> Could you provide a detailed performance comparison between R-AdaZO and ZO-AdaMM with longer iterations (where both methods converge)?\n\nThank you for this insightful question regarding the long-term convergence behavior. To address this, we have extended the comparison between R-AdaZO and ZO-AdaMM, running the experiments for 6 times the number of iterations used in the main paper, maintaining the settings from Section 6.1.\n\n**Quadratic Function Performance (Extended Iterations):**\n| Quadratic        | $T=37500$|$T=41250$|$T=45000$|$T=48750$|$T=52500$|$T=56250$|$T=60000$ |\n|---------|--------|---------|---------|---------|---------|---------|---------|\n|ZO-AdaMM | 28.972|2.509|0.101|0.027|0.026|0.026|0.026 |\n|R-AdaZO| 0.030|0.030|0.030|0.029|0.030|0.030|0.030 |\n\n**Levy Function Performance (Extended Iterations):**\n| Levy   | $T=37500$|$T=41250$|$T=45000$|$T=48750$|$T=52500$|$T=56250$|$T=60000$ |\n|---------|--------|---------|---------|---------|---------|---------|---------|\n|ZO-AdaMM | 584.637|572.480|565.976|562.638|561.050|560.467|560.252 |\n|R-AdaZO| 557.904|557.821|557.816|557.824|557.824|557.823|557.811 |\n\nAs shown in the results above, even with significantly more iterations, R-AdaZO achieves a final performance level that is comparable to, and in the case of the Levy function, slightly better than that of ZO-AdaMM.\n\n---\n\nWe thank the reviewer for the valuable input and we will incorporate these discussions into our revised version. We hope our clarification will address your concerns and improve your opinion of our work.", "claims_and_evidence": "The authors provide theoretical analysis to prove the claimed variance reduction effect. During my review, I did not identify any obvious issues (though the validation was not extremely detailed).", "methods_and_evaluation_criteria": "Yes, the proposed method aims to improve the convergence speed of zero-order optimization, and the experiments conducted are reasonable.", "theoretical_claims": "Yes, I verified some of the theoretical proofs. The assumptions and lemmas used are consistent with prior work in the zero-order optimization (ZO) field, and I did not find obvious issues.", "experimental_designs_or_analyses": "Yes, the experiments conducted (synthetic function optimization, image black-box adversarial attacks, and LLM fine-tuning) are common application areas for zero-order optimization.", "relation_to_broader_scientific_literature": "The paper introduces a new zero-order optimization algorithm based on ZO-AdaMM, aiming to improve the convergence speed of zero-order optimization methods. This is largely consistent with previous approaches in the field.", "essential_references_not_discussed": "In my opinion, while ZO-AdaMM is an important baseline for this paper, the authors should provide a more detailed comparison with other common zero-order optimization (ZO) methods to demonstrate the effectiveness of their approach. This includes methods like ZO-SGD (already cited by the authors), as well as ZO-SignSGD [1] and ReLIZO [2].\n\n[1] Liu S, Chen P Y, Chen X, et al. SignSGD via Zeroth-Order Oracle. In International Conference on Learning Representations, 2019.\n\n[2] Wang X, Qin X, Yang X, et al. ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-Order Optimization. Advances in Neural Information Processing Systems, 2024, 37: 15070-15096.", "other_strengths_and_weaknesses": "**Strengths**:\n1. The paper introduces a simple yet effective modification to ZO-AdaMM, accelerating the convergence of zero-order optimization (ZO) through variance reduction.\n2. The theoretical analysis is comprehensive.\n3. Due to the simplicity of the proposed method, I conducted my own tests on functions like Rosenbrock. With smaller parameter dimensions (i.e., 20, 50), the proposed method shows acceleration over ZO-AdaMM. (Although, after a longer number of iterations, it may perform worse than ZO-AdaMM, likely due to the bias introduced as analyzed by the authors.) In such cases, as the parameter dimension increases, the proposed method demonstrates better scalability, as evidenced by the experiments in the paper.\n\n**Weaknesses**:\n1. I believe the authors should include comparisons with additional ZO methods to further illustrate the effectiveness of their approach. See \"Essential References Not Discussed.\" The current experiments only compare the baseline ZO-AdaMM and the ZO-RMSprop, which is essentially similar to ZO-AdaMM.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. See weaknesses. I am curious about the performance of other ZO methods under the same experimental setup used by the authors.\n2. Could you provide a detailed performance comparison between R-AdaZO and ZO-AdaMM with longer iterations (where both methods converge)? For example, using the synthetic function in Figure 1.", "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:

Meta-review: This paper proposes R-AdaZO, a refined adaptive zeroth-order optimization method. R-AdaZO exploits the variance reduction effect of the first moment estimate to enhance the accuracy and stability of gradient-free updates and refines the second moment estimate to better capture the geometry of the optimization landscape. Theoretical analysis provides variance-aware convergence guarantees and demonstrates faster convergence compared to existing methods. Extensive experiments on synthetic tasks, black-box adversarial attacks, and memory-efficient fine-tuning of large language models confirm the practical effectiveness of R-AdaZO.

All reviewers acknowledged the soundness of the proposed techniques, the theoretical analysis, and the strength of the experimental results. One reviewer raised concerns about aspects of the theoretical analysis, including restrictive assumptions and suboptimal dependence on the dimensionality d. Another two reviewers noted the absence of evaluations on the ZO-Bench suite and the limited number of baselines. The authors have responded to these concerns in the rebuttal by providing additional analysis and experiments.

Given the overall contributions and the authors’ responsiveness in addressing key concerns, we believe the strengths of the submission outweigh its limitations. We therefore recommend acceptance, and encourage the authors to revise the manuscript in line with the reviewers’ feedback and their rebuttal commitments.
Decision: Accept (poster)