Revisiting Zeroth-Order Optimization:  Minimum-Variance Two-Point Estimators and  Directionally Aligned Perturbations
Authors: Shaocong Ma
Heng Huang
Venue: ICLR 2025 Spotlight (2025)
Keywords: zeroth-order optimization
SGD
convergence analysis
Primary area: optimization
TL;DR: This paper discusses the minimum-variance condition for two-point zeroth-order gradient estimators and proposes a new random perturbation.

Abstract: In this paper, we explore the two-point zeroth-order gradient estimator and identify the distribution of random perturbations that minimizes the estimator's asymptotic variance as the perturbation stepsize tends to zero. We formulate it as a constrained functional optimization problem over the space of perturbation distributions. Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length. While existing research has largely focused on fixed-length perturbations, the potential advantages of directional alignment have been overlooked. To address this gap, we delve into the theoretical and empirical properties of the directionally aligned perturbation (DAP) scheme, which adaptively offers higher accuracy along critical directions. Additionally, we provide a convergence analysis for stochastic gradient descent using $\delta$-unbiased random perturbations, extending existing complexity bounds to a wider range of perturbations. Through empirical evaluations on both synthetic problems and practical tasks, we demonstrate that DAPs outperform traditional methods under specific conditions.

Published as a conference paper at ICLR 2025
REVISITING ZEROTH-ORDER OPTIMIZATION: VARIANCE TWO-POINT ESTIMATORS AND DIRECTIONALLY ALIGNED PERTURBATIONS
Shaocong Ma and Heng Huang* Department of Computer Science University of Maryland College Park, MD 20742, USA (scma0908) heng) é umd. edu
ABSTRACT
In this paper, we explore the two-point zeroth-ordes gradient estimator and iden- tify the distribution of random perturbations that minimizes the estimator's 's asymp- totic variance as the perturbation stepsize tends to zero. We formulate as con- strained functional optimization problem over the space of perturbation distribu- tions. Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining fixed length. While existing re- search has largely focused on fixed-length perturbations, the potential advantages of directional alignment have been overlooked. To address this gap, delve into the theoretical and empirical properties of the directionally aligned perturbation (DAP) scheme, which adaptively offers higher accuracy along critical directions. Additionally, we provide a convergence analysis for stochastic gradient descent using 8-unbiased random perturbations, extending existing complexity bounds a wider range of perturbations. Through empirical evaluations on both synthetic problems and practical tasks, we demonstrate that DAPs outperform traditional methods under specific conditions.
INTRODUCTION
Zeroth-order optimization (Z0O) has emerged as a crucial paradigm in machine learning and opti- mization, particularly in scenarios where gradient information unavailable or prohibitively expen- sive to compute. This approach has garnered significant attention in diverse applications, including black-box adversarial attacks on machine learning models (Papernot et al., 2017; Chen al., 2017; Kurakin et al., 2016; Cai et al., 2021), physical-informed neural networks with external black-box fine-tuning of large language models (Malladi et al., 2023; Zhang al., 2024; Gautam et al., 2024), and reinforcement learning (Choromanski et al., 2018: Lei al., 2022). recent years, the memory-
PDE solvers (Shen al., 2024: Ma et al., 2025), memory-
consideration mo- tivates the one-bit approach (Cai et al., 2022a) and the study the sparsity of the gradient (Cai et al., 2022b). The randomized method (Akhavan et al., 2022) has also emerged as a critical direction.
In this paper, we consider the following unconstrained stochastic optimization problem:
min f(x) = (x==)(<; zeRd
where the random data & is sampled from the underlying distribution E. and the objective function f(z) is defined as the expectation of the smooth individual loss function f(x;)). While traditional first-order methods utilize the stochastic gradient V f E) to update parameters, zeroth-order op- timization relies solely on function evaluations. A common approach in this context is to use the standard two-point estimator to approximate the gradient, given by:
f(;;
11. Lf(r wm; {) ((x;()] u
*This work was partially supported by NSF TIS 2347592, 2348169, DBI 2405416, CCF 2348306, CNS 2347617.

---

Published as a conference paper at ICLR 2025
where μ E RR, is the perturbation stepsize and v R is random vector, typically drawn from uniform distribution on the sphere or standard Gaussian distribution.
The theoretical analysis of zeroth-order optimization methods has been extensively studied in the existing literature. Numerous studies have provided valuable insights into the convergence proper- ties and performance guarantees of these methods under various conditions (Ghadimi & Lan, 2013; Duchi et al., 2015; Ji et al., 2019; Sahu et al., 2019; Coope & Tappenden. 2020; Kozak et al., 2023; Rando et al., 2024a;b). However, when studying algorithms like SGD in the zeroth-order setting, these analyses typically consider specific types of random perturbations, such as Gaussian or uni- form distributions. While this approach has yielded important theoretical results, often lacks comprchensive explanation for why these particular random perturbations are optimal with respect to the variance of gradient estimator, which suggests the need for more comprehensive framework that can accommodate broader class of random perturbations. This observation leads us to the central question in this paper:
QI: How can we determine the class of distributions of random perturba- tion in zeroth-order estimator to minimize its variance?
Contribution To address this central question, we develop novel approach based on solving the following constrained functional optimization problem:
min E www.vvlVV [[;; - V
s.t. Vve 8ld.
where f( E, () is the two-point gradient estimator for approximating the stochastic gradient fx(;; defined in Eq. (2), and 5 > 0 is given scaling constant. This optimization problem formulated over a functional space encompassing all probability distributions over R subject to linear constraint. The constraint follows the existing zeroth-order optimization literature (Kozak et al., 2023; Rando et al., 2024b), which ensures that the direction of the two-point gradient esti- mator is the same as the true gradient as the perturbation step μ is sufficiently small. Moreover, this constraint is linear in the distribution V when treating it as an integral with respect to a gen- eral measure dV. The solution this optimization problem reveals a broader condition such that the two-point gradient estimator achieves the minimum variance: either (a) the perturbation vector v should have a fixed length, or (b) the inner product between v and the true gradient Vf(x; E) should have fixed magnitude. These insights extend beyond specific type of distribution such as uniform distributions over the sphere, enabling us to characterize a more general class of effective perturbations. These findings naturally lead to second question:
Q2: Can we leverage these theoretical insights to design novel random perturbation schemes that outperform existing methods?
Contribution Existing literature reveals that most perturbation methods focus primarily on en- suring a fixed length for the perturbation vector v (for more details, we include brief discussion in Appendix A.2). contrast, we propose novel scheme based on our second condition: choosing the random perturbation such that
o)) f[
where 8 0 is a given constant. In practice, we replace the true stochastic gradient f v) with v).
its estimation V fz v). This new random perturbation offers several advantages: (1) It extends the minimum- variance random perturbation design, which particularly drawn by the theoretical interest. (2) When certain components of the gradient are large, our proposed method exhibits strong anisotropic behavior and presents higher accuracy in these directions. This characteristic indicates that our approach is more focused on effective dimensions, potentially leading to more efficient optimization in high-dimensional spaces with sparse gradients.
Lastly, to validate the empirical performance of our proposed perturbation scheme, we conduct extensive experiments across multiple domains to demonstrate the effectiveness of our proposed method. On synthetic optimization problems, we show that our approach achieves signifi- cantly higher accuracy in gradient estimation compared to standard methods. In language model fine-tuning tasks, apply method to optimize the OPT-1.3b model on the SST-2 dataset, demonstrating faster convergence and higher final accuracy relative to existing zeroth-order ap- proaches.
Contribution 3:
2

---

Published as a conference paper at ICLR 2025
1.1 PAPER STRUCTURE
The remainder of this paper is organized as follows: In Section 2, we analyze the two-point gra- dient estimator and derive the sufficient conditions for minimum-variance random perturbations. This analysis reveals two distinct classes of perturbations which minimize the asymptotic variance (as the perturbation step μ - 0) of two-point gradient estimation: fixed-length perturbations and directionally aligned perturbations (DAPs). In Section 3, we present the convergence analysis for SGD algorithm using d-unbiased random perturbations. We establish the complexity that matches the common dependence on the dimension d while extends to broader class of perturbations, in- cluding both traditional fixed-length methods and our proposed DAPs. In Section 4, we introduce the DAP in detail. We examine its unique properties, particularly their anisotropic behavior and ability to adapt to gradient magnitudes across different dimensions. We also present a practical al- gorithm for implementing DAPs. In Section 5, provide extensive experimental validation of our theoretical findings. We evaluate DAPs against traditional perturbation methods on both synthetic optimization problems and practical machine learning tasks.
2 THE DERIVATION OF MINIMUM- MINIMUM-VARIANCE RANDOM PERTURBATIONS
In this section, we consider the two-point gradient estimator for approximating the gradient V fax) and seek derive the minimum-variange random perturbation strategy.
In brasee optimization, the descent direction is the opposite of the gradient vector. This naturally leads the following unbiased assumption up scaling constant which ensures that the direction of estimated gradient is aligned with the true gradient:
Assumption 2.1 (ō- (6-Unbiasenness). Let the two-point gradient estimator for estimating the stochas- ric gradient (a;;) E) be {x; := и [f(x + pv; - f(x; {)] The distribution V satisfies the 8-unbiasedness if Eve = ôla, where La is the identity matrix with the dimension d.
It should be noted that the concept of unbiasedness here is in the asymptotic sense, which holds when - O. This assumption is commonly satisfied in existing zeroth-order optimization litera- ture. Many popular random perturbation distributions satisfy this assumption, including Gaussian perturbation (Ghadimi & Lan, 2013; Duchi et al., 2015; Nesterov & Spokoiny, 2017), uniform dis- tribution over a sphere (Lin et al., 2022; Duchi et al., 2015), random coordinate/direction sampling (Zhang et al., 2020; Coope & Tappenden, 2020; Kozak et al., 2023), and Rademacher distribution (Spall, 1987; 1992). Building on this ussumption, our next goal is to characterize the accuracy of < f( v) in approximating the true gradient [x E, v), which may lead to insights applicable across various perturbation schemes.
Let V be distribution such that for any ~ V. E[coT] = Sla, where La denotes the d x d identity matrix. The approximation error of the two-point zeroth-order gradient estimator for estimating V (z)) can be represented as:
E--v|V -V]((( = E
[ + uv) -VD)) 14
1
(n-0)
2 Enp vl [x)12
= =E.. V(
(ov T2 + (1 (6)-26)/VV/ (())(
where (i) applies the Taylor theorem
u) ne (M.(v). u) (Lemma C.9)
and assumes the perturbation step f sufficiently small.
Remark (Taylor Approximation Error). We note that the above approximation and the unbiasedness of the two-point gradient estimation require the perturbation step μ - O. This requirement is commonly made in practice such as the language model fine-tuning (Malladi et al., 2023) and other theoretical convergence analysis (Duchi et al., 2015). With making additional assumptions such as the L-smoothness (Assumption C.1), we can have more accurate upper bound which we will use in our final convergence analysis presented in Theorem 3.1 and Corollary 3.2. More explicitly, if the function f is L-smooth, then must have I-bbounded Hessian matrix. Therefore, we obtain
E f(zz)) v 2(x)] < V fxx) T (vo ( f(x) + (1 (01122)]1000 [(()) + + 1
3

---

Published as a conference paper at ICLR 2025
We will later bound the first term with respect to [Vf(2)]? For the last term, will make the perturbation step μ to be sufficiently small to control its magnitude. Due to the page limit, we include more detailed discussions the accumulative error caused by the gradient approximation and the Taylor approximation in Appendix F.
For notational convenience, we let a := Vx()). Our objective is to find the distribution V that minimizes the above expectation, formalized as:
min Ev-va (ve )²a
(3)
s.t. E = ôla-
The optimization problem we have formulated presents two significant challenges: (1) It requires us to optimize over an infiniteddimensional space of probability distributions, a task that demands sophisticated mathematical tools.(2) The constraint VEr-ve' 8la imposes specific second-order moment conditions the distribution, adding layer of complexity to our analysis. To address these challenges, we develop a novel analytical approach, described in the following theorem:
Theorem 2.2. Let be random vector following the distribution V with Eg- ôLa and E R be a fixed vector. Then
dō'1aal12 & Eu-va' (veT)2 & d'dlal + [al?
|a
2 PV +
VR + 46 - 1)pv.
2
where PV El|u||* - d2d The equality holds if one of the following conditions holds:
(a) |0| = =d d8 holds almost surely.
(b) (a ua)==== ō||a|| holds almost surely.
Remark. When the equality holds, the two-point gradient estimator defined Eq. (2) has the mini- mum variance // [x;; v) [=x))] (5 25 + +1) 1)[{/(=)]² O(4)).
Proof. The details can be found in Appendix B.I. Let f = (uTa)a da and [[u] - -8d)a.
Then we obtain
(E[g T fl) E Elgl?
where (i) applies the Gauchy-Schwarz inequality. Then obatin quadratic function with respect to the objective function En-va" (vuT)²u )aa By analyzing the equality condition of the Cauchy- Schwarz inequality (i.e. ff and g are linearly dependent), we obtain the sufficient and necessary condition for achieving the minimum variance.
On the Necessity Minimum Variance Conditions In our previous theorem (Theorem 2.2), only present the sufficient condition of achieving the asymptotic minimum variance as the per- turbation step μ tends to A simple counterexample demonstrates that this condition may not be necessary: consider mixed distribution that takes the DAP with probability p and the uniform per- turbation over the sphere with probability - p. Such a distribution would also achieve minimum variance while satisfying neither condition exclusively. Extending the condition sufficient and necessary condition would be an interesting but challenging topic. Here we present one potential scenario where we may obtain the necessary and sufficient condition: In the one-dimensional case, assuming the random perturbation satisfying Ev O and Ev² = 1. the unique distribution of achieving the minimum variance the Rademacher distribution, which is naturally derived by con- sidering the Taylor expansion. This case may further be extended to d-dimension with requiring all entries in the random perturbation to be mutually independent; however, this extension would be out of the scope of our paper and excludes many interesting random distributions. We will still stick to our d-unbiased perturbations (Assumption 2.1) in the remaining of our manuscript.
This theorem reveals two underexplored insights in zeroth-order optimization: (1) The performance of the two-point gradient estimator is significantly influenced by the fourth-order moment of the perturbation distribution V. Choosing V with infinite fourth-order moment can result in poorly performing zeroth-orde gradient estimator. This highlights the crucial role of perturbation choice in gradient estimation performance. In the meanwhile, when choosing the perturbation distribution V
4

---

Published as a conference paper at ICLR 2025
with the minimum variance, the complexity of SGD with two-point gradient estimation achieves the best known sample complexity, which we discuss further in Section 3. (2) The presented condition naturally leads to two distinct classes of random perturbations that achieve the minimum variance:
(a) Constant Magnitude Perturbations: This class of perturbations arises from the Constant Mag- nitude condition: ||u||2 d6. This condition gives rise to a diverse range of distributions, cluding:
Uniform distribution over sphere: e is uniformly distributed on the surface of a sphere with radius d, i.e., ||e| d.
Rademacher distribution: Each entry of is independently sampled as Us + with equal probability, resulting in ||u| 2 d5.
Random coordinate:
Vdõe,, where e; is standard basis vector chosen uniformly at random from e,, edt, ensuring ||||? = d5.
They all share the property of having a constant |=12, satisfying the condition (a) Theorem 2.2.
Surprisingly, the widely used Gaussian distribution & ~ [O, Ia) has kurtosis [[[ = d² + 2d > d?, which exceeds the minimum variance. Therefore, the Gaussian random perturbation doesn't I belong to the class of minimum-variance random perturbations, despite its popularity in many optimization algorithms.
[||
(b) Directionally Aligned Perturbations (DAPs): This class of perturbations stems from the con- dition: (a u)² = 8|[a||?. This condition suggests that a perturbation that minimizes the asymp- totic variance of two-point gradient estimator as μ 0 should be distributed the surface aTv + + all- This class of perturbations, while theoretically promising, remains largely underexplored in the existing literature on zeroth-order optimization. We note that in the prac- tice of zeroth order optimization, this condition not be imposed like it is, since ff))) is commonly not available. We provide further discussion of this class of perturbations, including potential sampling stratagies and practical considerations, in Section 4.
In the following sections, we will present the sample complexity of SGD under minimum-variane conditions for the two-point gradient estimator. Specifically, we will examine scenarios where Eq. (3) achieves the minimum value of d6 V ff(; l) Subsequently, we will explore the proper- ties of DAPs, which is rarely explored in the existing literature.
|
3 CONVERGENCE OF SGD WITH 5-UNBIASED RANDOM PERTURBATIONS
In existing literature, the approximation error of the gradient estimation F. f v) (xx) is often tailored to a specific type of random perturbation by utilizing the analytical form of the probability densities. By applying the upper bound obtained from Theorem 2.2, we are able to build a more general upper bound which maintains the desired dependence In summary, we analyze the convergence of Stochastic Gradient Descent (SGD) with 6-unbiased random perturbations for the optimization problem defined in Eq. (1) with smooth individual loss functions f(x:; E), on which we make several standard assumptions including the L-smoothness (Assumption C. and the strong convexity (Assumption C.2) detailed in Appendix C.I.
the dimension d.
To solve the optimization problem presented in Eq. (l), we employ the SGD algorithm. Starting from the initial parameter Ii, we repeatedly update the parameter with the update rule
F++1 Ft (m): v4)
for ( = 1. - where &. E is the data point used at 1-th update and V far Ee, wx) is the estimation of the true gradient (=(r with i sampled from the distribution V as defined in monitor min [ f=xx)] the minimum squared gradient
Eq. (2). For non-convex settings, norm of the objective function during training. For strongly convex settings, we track f(z)) - ff= the function value gap, where f := inf f(x). Both metrics standard in smooth optimization literature (Ghadimi & Lan, 2013). We also note that the quantity minigrer || [|V (xx) used in the non-convex setting is not easy check in the practice especially in the modern machine learning senario, since the parameter space would be extreamly large.
Now build the convergence analysis of SGD algorithm with 8-unbiased gradient estimators:
5

---

Published as a conference paper at ICLR 2025
Theorem 3.1. Suppose that Assumption 2.1 and Assumption C.I are satisfied. Let {xt)t=1 be the SGD dynamic solving Eq. (1) generated by the update rule Eq. (4). If the fourth-order moment of the random perturbation is finite (i.e. En-v|lelt < +00), then
(a) the learning rate 1 & min(
21 py then
(f(x))-1t) 8nr
+ 2n 5
min EEEET
V
LB Bv) + prav
where is the turongccovextie constant defined in Assumption C.2, PV Elluol av L Blll, By == 2 pv+1-20 20, and 1 := 2L x E ((} with f == inf f(r;
(b) If the learning rate satisfied, then
< minf 1. bc 1 and additionally, Assumption C.2 is
2L 1 26
Ef(xT)
< (1 (1-2 (f()))
2 cb (LB Bv) p²av),
where PV. av, Bv, and B² are as defined in (a).
Proof. The proof directly follows Khaled & Richtárik (2022) and Mishchenko et al. (2020) with ad- ditionally bounding the error term [V &, vt) V fxx)) using Theorem 2.2. See Appendix C.1 for details.
This convergence upper bound reveals two important insights that have not been comprehensively studied in existing literature:
(a) The impact of perturbation magnitude 8: A small-magnitude perturbation å consistently leads to more accurate approximation: According to Theorem 2.2, we are using the uniform distribu- tion over the sphere with 6 = 1, the approximation error lim Eu- f v) fz
the meanwhile, if we are using the uniform distribution over the sphere with 1/d, the approximation error is minimized and achieves lim E [ vz
(d /
ff(=)] = (1 - [/d]//((x))]) However, a small magnitude results in a 1 scale on the convergence upper bound presented in Theorem 3.1. As result, tuning the hyper- parameert doesn't 't change our theoretical complexity analysis; therefore, in the following corollary, we only consider the case where 1.
(b) The influence of fourth-order moment B|[u|] The fourth-order moment of the random pertur- bation EE] v) significantly impacts the convergence performance of the SGD algorithm, a phe- nomenon previously identified in the literature such as Duchi et al. (2015). Due to the influence of E|| our convergence analysis cannot guarantee that all 8-unbiased random perturbations can achieve the optimal dependence on dimension d as reported in existing lower bounds (e.g. consider any random distribution with the fourth-order moment d for some e >> 0). How- ever, demonstrated in Corollary 3.2, all perturbations that achieve minimum variance will attain this best-known dependence on d.
Corollary 3.2. Under the same assumptions as Theorem 3.1, let V achieve the minimum variance. Then
(a) Let 1, 1 0(5), and μ = O Then requires at most T & O($) ilerations to achieve minjeteT [xV <
(b) Suppose that Assumption C.2 is satisfied. Let 1, 1 1 and μ O(g). Then it requires at most T & (()) iterations to achieve Ef(rr) -
<c <<
By applying this result, we extend the best-known complexity for zeroth-order SGD for smooth objectives to much broader class of minimum-variance random perturbations, including the uni- form smoothing (Bach & Perchet, 2016), Rademacher distribution (Spall, 1987; 1992), coordinate descent (Cai et al., 2021), random subspace (Kozak et al., 2021), and the general orthogonal pertur- bations (Kozak et al., 2023). Notably, the results presented in existing literature are either tailored to specific type of random perturbation, cannot characterize the convergence of SGD under DAPs.

---

Published as a conference paper at ICLR 2025
Uriterm Nertuiattinn
Unborm Pentubattons
Dee (Beast end)
DAP (Esc Gradiin
DAP (hatmoote Gradiet))
DMP (Extineeed Conclett)
1200
1000
-2
600
Uniform Returbations
DSP (Doact Gradient)
DSP ibatimated Grassent)
PP0ns) (Teimatedd Cradlert)
v'0ts) ponx1 Gradiee)
915
-1.0
-0.
0.6
1.0
3.5
-15
-1.0
0.0
1.0 15
Figure 1: Illustration of the directional alignment property of DAP in d = 2 with estimating the gradient of ((x) = x22 at [0.1 1]" We sample 5000 random perturbations from the uniform distribution over the circle |x| 2 and DAPs with Vf(z) [0.2 2] in which 100 samples are illustrated in the left figure. When projecting DAPs onto different axes, we observe two distinct distributional patterns in the X-component and Y-component, demonstrating DAP's anisotropic nature. contrast, uniform perturbations maintain same distributions across projections.
DIRECTIONALLY ALIGNED PERTURBATIONS (DAPs)
In the previous section, we discussed the condition of achieving the minimum variance for approxi- mating the gradient V (zx) using a two-point gradient estimator defined in Eq. (2), We proved that a 5-unbiased random perturbation achieves the minimum asymptotic variance as ç + 0 has a fixed length or satisfies the following equation:
(v = (
(5)
We refer to the class of 8-unbiased random perturbations satisfying Eq. (5) as directionally aligned perturbations (DAP). While it has been shown that this class of random perturbations achieves min- imum variance, there is limited literature studying their empirical performance. The unknown true gradient could potentially hinder the application of DAP; however, also recognize several attrac- tive features of DAP in zero-order gradient estimation.
4.1 DIRECTIONALLY ALIGNED PROPERTY
The primary characteristic of DAP is its directional alignment property. Unlike uniform perturba- tions or other fixed-magnitude perturbation methods, DAP exhibits anisotropic behavior, meaning its effects vary depending on the direction of projection (as illustrated in Figure 1). This anisotropy is a direct consequence of DAP's design, which inherently leverages information from the objective function's local geometry to perform different perturbation behaviors, which is usually ignored by fixed-magnitude perturbation methods.
As result of the directional alignment property, when the true gradient has larger magnitude in a specific direction, DAP adaptively introduces low-variance perturbation in that direction, poten- tially leading to higher accuracy. This effect demonstrated Figure 2. This adaptive behavior of DAP may reduce noise in estimating gradients, particularly when the gradients are sparse or have varying magnitudes across different dimensions. We further validate this hypothesis and explore its implications in Section 5.
4.2 THE SAMPLING STRATEGY AND A PRACTICAL IMPLEMENTATION
While the theoretical properties DAP are appealing. their practical implementation presents sev- eral challenges. For the unknown gradient (=(x), we can always apply small batch of perturba- tions to obtain an estimated gradient V f()). However, even with an estimated gradient, sampling from the hyperplane (u Tv))))))2 = f=))² satisfying T = 8I, remains challenging. This necessitates the design of a specific sampling strategy address this issue. Moreover, the use of batch of function evaluations for gradient estimation raises a practical consideration about whether and how reuse these estimators.
7

---

Published as a conference paper at ICLR 2025
x-gradient
y-gradient
X-component of Gradient
Ycomponent of Gradient
Unferm
Figure 2: Comparison of gradient estimation performance with estimating the gradient of f(x)
oi + 22 at x [0.1 1] between Uniform perturbations and DAPs. The DAP exhibits notably smaller variance the y-direction where the true gradient has a larger magnitude, compared to the x-direction where the true gradient is close shows similar variance in both directions, regardless of the true gradient's magnitude.
In contrast, the uniform perturbation method
To address these issues, we propose the following practical approach sample from the DAP dis- tribution. Here, Algorithm describes the approach to generate the random vectors over the plane (vT (uTa)² ō||a| 2 satisfying Evv ōIa with given vector Rdd its correctness is proved in Proposition 4.1. And Algorithm 2 describes the practical zeroth-order gradient estimator using DAPs.
Algorithm 1: The algorithm for sampling from a hyper-plane
Algorithm 2: A practical implementation of gradient estimator using DAPs
Input: The vector a E IRd
Input: The dimension d, the batch size b
Generate random vector vini such that
/ Estimate the gradient */
V = òLd;
Use b//2 uniform perturbations to obtain
Generate independent random variable g uniformly from the set 1-,, +1};
the gradient estimator Vf(x);
/ *
Generate DAP
Project Vini onto the random plane
Use Vf(x)) as the input of Algorithm to
Pş = (v a = al);
obtain b//2 DAPs;
Use b//2 DAPs to obtain another gradient estimator ff());
Output: The projected random vector
== Projp, (Um))
Output: The gradient estimator
1 [V + Vf(x))
Proposition 4.1. Let be a random vector generated by Algorithm 1. Then it has the following properties: (a) (w a)² ô|a]? and (b) Br-yoo" 8Tg.
Proof. The proof is deferred to Appendix B.2.
This proposition confirms that sampling strategy yields the desired properties. These properties guarantee that the resulting output e minimizes the variance of two-point gradient estimator. In the next section, we will empirically evaluate our practical implementations in both synthetic and real-world examples.
5 EXPERIMENTS
To validate our theoretical findings and demonstrate the practical effectiveness of DAPs in zeroth- order optimization, conduct experiments on two different problem settings: synthetic examples
8

---

Published as a conference paper at ICLR 2025
and language model optimization. For each target function f, estimate its gradient using the zeroth-order estimator defined by different random perturbation under the batch size b:
1 c f((x) = pb Ev(+ pv.) (0000-((x))) f(x))e
(6)
where μ > 0 is the perturbation size and U; are random vectors independently drawn from distribu- tions according to the method used. For additional experiments, refer the reader to Appendix E
5.1 SYNTHETIC EXAMPLES
We first evaluate our proposed method the following two objective functions:
SQuaa (2) x Aur,
SProat (x:
where each entry A Rdxd independently sampled from the uniform distribution U[0,1 1J. The gradient of each objective function be explicitly evaluated; that is, (2) (A + AT)x and Prod zz) = [2203 Td, T3 ... Ed. ... 12 ... ..-11. We compare the performance of different random perturbations using the r-effective Mean-Square-Froor (r-MSB), which is defined as
T T=MSE(()f(;;)) v)) = o) - -[(C))
(7)
where E, is diagonal matrix such that
E- -11,--16 (
[f(>)||>> [f(=))
represents the direction with a larger gradient value, which is of greater interest to us. In this experiment, we set - = 10-4 for both figures in Figure 3. For the quadratic function, we force half of the entries in x be O, while for the product function, we set the first element of 0. This configuration ensures gradient sparsity; the product function represents an extremely sparse case where only one entry, d...3.... Ld,, non-zero. Our compared methods include the DAP with and without knowledge of the true gradient (Exact Gradient and Empirical Gradient), the Uniform Perturbation (where is uniformly distributed over the sphere with radius vd), and the Gaussian Perturbation (where 0 ~ La).
10a
10c
DAP (Exact Gradient)
DAP (Exact Gradient)
DAP (Estimated Gradient)
102
DAP (Estimated Gradient)
Uniform Perturbation
Uniform Perturbation
10a
Gaussian Perturbation
10
Gaussian Perturbation
10-6
T-MSE
T-MSE
10-10
10-14
100
10
10-22
10-1
10 10-26
32
64
128
256
512
2
16
32
Batch Size
Batch Size
Figure 3: Comparison of 7-MSF (defined in Eq. (7)) for different random perturbations on Quadratic (left) and Product (right) functions. Experiments perturbation stepsize μ = 10-4 The x-axis shows the batch size, and the y-axis shows the 7-MSE Lower 7-MSE indicates better gradient estimation accuracy along those more important directions.
conducted with the dimension d = 16 and

---

Published as a conference paper at ICLR 2025
The experiment yields three key insights: (1) When the gradient is known exactly, the DAP sistently outperforms classical random perturbations. As the batch size increases (to larger than b 32 for the quadratie function), we observe the same phenomenon in the estimator generated using A Agoorthhm 2. (2) When the gradient is extremely sparse, the DAP achieves significantly better accuracy along the effective direction.
5.2 LANGUAGE MODEL OPTIMIZATION
In this section, demonstrate the practical applicability of the DAP in optimizing the neural net- work. We apply it to the task of fine-tuning a pre-trained language model. Using zeroth-order optimization to fine-tune the LLMs has been active research field in recent years due its ef- fectiveness in saving memory (Malladi et al., 2023; Zhang et al., 2024; Gautam et al., 2024; Guo al., 2024); it allows for the adjustment of model parameters without requiring access to the full computational graph, which can be prohibitively large for modern language models.
We conducted experiments using the OPT-1.3b model (Zhang et al., 2022) for sentiment classifi- cation on the Stanford Sentiment Treebank (SST-2) dataset (Socher et al., 2013). To ensure fair comparison, we maintained consistent parameters across experiments: learning rate rj 10-4, per- turbation size Appendix D. As shown Figure 4, zeroth-order optimization using DAPs achieved superior per- formance compared to other random perturbation methods. Notably, found that this superior performance does not rely on a large batch size 6, demonstrating the practical effectiveness of DAP in real-worke applications.
10-5, and batch size b 2. Detailed experimental settings are provided in
0.9
DAP (Estimated Gradient)
Uniform Perturbation
0.8
Gaussian Perturbation
0.7
Training Loss
0.6
0.5
0.4
0.2
4000
6000
12000 16000 20000
Training Step
Figure 4: Performance comparison of different optimization methods for fine-tuning OPT-1.3b on SST-2. DAPs achieve empirically superior performance among other perturbations including the classical Gaussian smoothing and uniform smoothing.
6 CONCLUSION
In this work, we investigate zeroth-order optimization for smooth objective functions. We derive the conditions for random perturbations that minimize the variance of the two-point gradient estimator, revealing that in addition to traditional fixed-length random perturbations, directionally aligned per- turbations (DAPs) can also achieve the minimum asymptotic variance as f O. Our theoretical analysis extends best-known complexity bounds to encompass this broader class of perturbations, including DAPs. We explore the directionally aligned property of DAPs in gradient estimation and demonstrate their superior performance compared to traditional methods under specific conditions through experiments on both synthetic problems and language model fine-tuning tasks. These find- tools
ings not only advance our understanding of zeroth-orde optimization but also provide for improving gradient estimation. Our work opens up new avenues for research in zeroth-order methods and their applications in machine learning and optimization.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
David Acheson. Elementary fluid dynamics. Oxford University Press, 1990.
Arya Akhavan, Exgenii Chzhen, Massimiliano Pontil, and Alexandre Tsybakov. A gradient estima- tor via ll Il-randomization for online zero-order optimization with two point feedback. Advances in Neural Information Processing Systems, 35:7685-7696 2022.
Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pp. 257-283. PMLR, 2016.
Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-506 2022.
HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference on Machine Learning, pp. 1 1203-1203. PMLR, 2021.
HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang. one-bit, comparison- gradient estimator. Applied and Computational Harmonic Analysis, 60:242-2000 266, 2022a.
HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang. Zeroth-order regularized opti- mization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Opti- mization, 32(2)x687-714 2022b.
Yun-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 15 15-26, 2017.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning, pp. 970-978. PMLR, 2018
Ian D Coope and Rachael Tappenden. Gradient and hessian approximations in derivative free opti- mization. arXiv preprint arXiv:2001.08355 2020.
Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee, Swati Padmanabhan, and Guanghao Ye. A gra- dient sampling method with complexity guarantees for lipschitz functions in high and low dimen- sions. Advances in Neural Information Processing Systems, 35:6692-6700 2022.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory. 61(5):2788-288 2015.
Lawrence C Evans. Partial differential equations, volume 19. American Mathematical Society, 2022.
Lawrence C. Evans and Ronald F. Gariepy, Measure theory and fine properties of functions. CRC Press, 2015.
Robert Eymard, Thierry Gallouët, and Raphaèle Herbin. Finite volume methods. numerical analysis, 7:713-1018, 2000.
Handbook of
Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance-
reduced zeroth-order methods for fine-tuning language models. arXiv preprint arXiv:240.008080 2024.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):2341-2366 2013.
Wentao Guo, Jikai Long, Yimeng Zeng, Zirui Liu, Xinyu Yang. Yide Ran, Jacob R Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, et al. Zeroth-order fine-tuning 1lms with extreme sparsity. arXiv preprint 2rXiv:24066029111 2024.

---

Published as a conference paper at ICLR 2025
Jean-Baptist Hiriart- Hiriart-Urruty, Urruty, Jean-Jacques Strodiot, and V Hien Nguyen. Generalized hessian ma- trix and second-order optimality conditions for problems with c 1, data. Applied mathematics and optimization, 1 ((1):43-56, 1984.
Hugues Hoppe,
Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Mesh opti- mization. In Proceedings of the 20th annual conference on Computer graphics and interactive techniques, pp. 19-26, 1993.
Thomas W Hungerford. Algebra, volume 73. Springer Science & Business Media, 2012.
Kaiyi Ji, Zhe Wang. Yi Zhou, and Yingbin Liang. Improved zeroth-ordes variance reduced algo- rithms and analysis for nonconvex optimization. In International conference on machine learning, pp. 3100-3109. PMLR, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Machine Learning and Knowl- edge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pp. 795-811. Springer, 2016.
Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. Transactions on Machine Learning Research, 2022.
Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-dependene for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122): 1-14, 2024.
David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. A stochastic subspace approach to gradient-free optimization high dimensions. Computational Optimization and Applications, 79(2):339-366 2021.
David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Tenorio, and Silvia Villa. Zeroth-order optimization with orthogonal random directions. Mathematical Programming, 199(1-2)11179 1219, 2023.
2023.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint 1rXiv:1611.012.5 2016.
Yuheng Lei, Jianyu Chen, Shengbo Eben Li, and Sifa Zheng. Zeroth-order actor-critic. arXiv preprint arXiv:2201.122 12518, 2022.
Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35: 26160-26175, 2022.
Dinh The Luc. Taylor's formula for c"k,1 functions. SIAM Journal on Optimization, 5(3):659-669, 1995.
Shaocong Ma, James Diffenderfer, Bhavya Kailkhura, and Yi Zhou. Deep learning of pde correction and mesh adaption without automatic differentiation. Machine Learning, 114(3):61, Feb 2025. ISSN 1573-0565, doi: 10. 10.100077509994--3--674444 URL wtttt:tp///ddl http:///...ooo111.11/110000
s1C994- 0200440025-776655
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason DLee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-573 53075, 2023.
Leon Mirsky. A trace inequality of john neumann. Monatshefte für mathematik, 79(4):303-30) 1975.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 18:17399-17300 2020.
12

---

Published as a conference paper at ICLR 2025
Tamás F Móri, Vijay K Rohatgi, and GJ Székely. On multivariate skewness and kurtosis. Theory of Probability & Its Applications, 38(3):547-555 1994.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
Nicolas Papernot, Patrick McDaniel, lan Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp- 506-519, 2017.
Marco Rando, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. An optimal structured zeroth- order algorithm for non-smooth optimization. Advances in Neural Information Processing Sys- tems, 36, 2024a.
Marco Rando, Cesare Molinari, Silvia Villa, and Lorenzo Rosasco. Stochastic zeroth order descent with structured directions. Computational Optimization and Applications, pp. 1-37, 2024b.
Darren Rhea. The case of equality in the von neumann trace inequality. preprint, 2011.
Anit Kumar Sahu, Manzil Zaheer, and Soummya Kar. Towards gradient free and projection free stochastic optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3468-34644 3477. PMLR, 2019.
George AF Seber and Alan J Lee. Linear regression analysis. John Wiley & Sons, 2012.
Qianli Shen, Yezhen Wang, Zhouhao Yang. Xiang Li, Haonan Wang, Yang Zhang, Jonathan Scarlett, Zhanxing Zhu, and Kenji Kawaguchi. Memory-efficien gradient unrolling for large-scale bi-level optimization. arXiv preprint arXiv:2406. 14095, 2024.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642 Seattle, Washington, USA, October 2013. Association for Computa- tional Linguistics. URL https::/p//. www. acl org/ http//at//oooo11111/007//
James C Spall. stochastic approximation technique for generating maximum likelihood parameter estimates. In 1987 American control conference, pp. 1161-1167. IEEE, 1987.
James C Spall. Multivariate stochastic approximation using simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332-341, 1992.
Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference Machine Learning, pp. 11173-11182. PMLR, 2020.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li. Xi Victoria Lin, Opt: Open pre-trained transformer language models. arXiv preprint 205.0.2005.01068, 2022.
Yihua Zhang, Pingzhi Li, Junyuan Hong. Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yu Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang. Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-efficiee Ilm fine-tuning: A benchmark, 2024.
13

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Related Works
14
A.1 Related Results in Zeroth-Order Optimization
14
A.2 Common Choices of Random Perturbations
15
B Derivation of the Minimum- Variance Random Perturbation
15
B.1 Proof Theorem 2.2
16
Proof Proposition 4.1
B.3 Supporting Lemmas
C Convergence Analysis of Zeroth-Order SGD
19
C.I Proof of Theorem 3.1
20
C.2 Supporting Lemmas
21
D Details on Experiments Setup
24
E Additional Experiments
25
Comparison with Other Random Perturbations
25
Additional Practical Application: Mesh Optimization
F Discussions the Accumulative Errors
27
G Limitations
27
A RELATED WORKS
A.1 RELATED RESULTS ZEROTH-ORDER OPTIMIZATION
Convergence Analysis for ZOO The convergence of Stochastic Gradient Descent (SGD) has been extensively studied under various settings. Ghadimi & Lan (2013) established complexity results for computing approximate solutions using first-order and zeroth-order (gradient-free) in- formation with Gaussian smoothing. For smooth convex objective functions, Duchi al. (2015) obtained the optimal convergence upper bound for SGD under the zeroth-order optimization (ZOO) setting. Nesterov & Spokoiny (2017) provided the optimal convergence upper bound for Gaussian smoothing. In the realm of nonconvex optimization, Ji et al. (2019) proposed two new zeroth-order variance-reduced optimization algorithms, ZO-SVRG-Cond SeIG--Coord-aaal and ZO-SPIDER -oood, and provided improved analysis for the existing ZO-SVRG-Coom algorithm. These methods achieved better convergence rates and function query complexities than previous approaches. Berahas et al. (2022) derived convergence analyses for finite differences, linear interpolation, Gaussian smooth- ing, and uniform sphere smoothing methods. Recent studies have focused on non-smooth settings. Davis al. (2022) and Zhang et al. (2020) established the sample complexity for Lipschitz functions without assuming smoothness. Lin et al. (2022) derived the complexity upper bound of SGD while noting a vd scale compared to the smooth setting. Notably, Rando et al. (2024a) and Kornowski & Shamir (2024) revealed that by applying certain techniques, the non-smooth case is not inherently more challenging than the smooth case.
General Random Perturbations Kozak et al. (2021) introduces a stochastic subspace descent al- gorithm for high-dimensional optimization problems with costly gradient evaluations. This method offers theoretical convergence guarantees and demonstrates a more general class of random pertur- bations that have convergence guarantees. Kozak et al. (2023); Rando al. (2024b) later extends
14

---

Published as a conference paper at ICLR 2025
this concept more generalized orthogonal subspace method, which also presents the optimal dependence on the dimension parameter In a related study, Duchi et al. (2015) examines random perturbations with finite fourth-order momentum, which aligns closely with our findings. However, their analysis is limited to convex optimization, whereas our work explores non-convex optimization scenarios.
A.2 COMMON CHOICES OF RANDOM PERTURBATIONS
As observed in practice, the choice of distribution for the random perturbation vector v potentially impacts the performance of zeroth-order gradient estimators. In this subsection, we review four classical distributions below:
Gaussian Random Vector The Gaussian (or normal) distribution is widely used due to its theoret- ical properties (Nesterov & Spokoiny, 2017) and ease of sampling. In this case, each component of v is drawn independently from standard normal distribution: (0,, 1) for i = .,..,, d. More generally, the random vector can be sampled from a normal distribution with a given covariance matrix Σ; that is, U N(0,))
Uniform Random Vector Another common perturbation is the uniform random vector over the unit sphere. It has been shown in Duchi et (2015) that the uniform random vector achieves optimal dependence on the dimension d. To sample such random vector, it suffices to generate a vector with independent standard normal components and then normalize it to unit length. This method produces a vector uniformly distributed on the surface of the unit sphere.
Rademacher Random Vector The Rademacher distribution is widely used in the method known as Simultaneous Perturbation Stochastic Approximation (SPSA) (Spali, 1987; 1992). In this case, each component of is independently drawn from Rademacher distribution, taking values +1 or - with equal probability. This distribution is particularly useful for its simplicity in certain optimization settings.
Random Coordinate The random coordinate method (Ji al., 2019), also known as coordinate- wise perturbation, involves perturbing only one randomly selected coordinate at time. This ap- proach can be particularly effective in high-dimensional spaces where full-vector perturbations might be computationally expensive. To implement this, one randomly selects an index i E I,...,d and sets v = and vU = for all j * i. This method can lead to more stable estimates certain scenarios and is often used in large-scale optimization problems.
B DERIVATION OF THE MINIMUM VARIANCE RANDOM PERTURBATION
Our proof technique is mainly inspired by the following result taken from Theorem 1 (Móri et al., 1994), which indicates that E||b/| is minimized when the distribution V the uniform distribution over the ball ||C $ $1 d + || where == E.-V (11o[/2)) Here, we generalize its result by considering the 5-unbiasedness structure E.-vee 8la-
Lemma B.1. Let V be any distribution over Rd. Define E (1lu1120). Then
E w
> 52 ||>|
Proof. Let |2|2 - 5d and = sTv, where v is random vector from the distribution V and $ Evay [|0|| Then
|s|| - (Efg)² B (B|o) 82dd) ||s| (ETr(uu - 82dd) ||s|2.
Then we obtain
|| 82d8 & ETr(vcTy
By constructing appropriate f and g, will obtain the desired estimation Ea EaT(vu )a
15

---

Published as a conference paper at ICLR 2025
B.1 PROOF OF THEOREM 2.2
Proof. The proof logic mainly follows Lemma B.1. Here, we construct the desired f and y. First, notice that the equality
(a v)) a vvTa. a. Let ʃ = (v) aav da and = (1lul2 - ōd)a. By these definitions, we have
|l a (ve' T - ó1a) 8011a12 2a' T (ve ôdLaa a (vo / 20a vu a + 101a|2 2 - 2a T vo 26|aa /| a -E - -81a)a -20 la|2 + 82|a|2 20lla| 20||a||
E[v" ((vTa)>lol) -
|9|l [|]]² -dd=
g 2 [E]b]] ||| + 8 lla2)
f a' T (ve - òla)a ([eol -dd)
[(a - 303-6laa|(3) (|ull dd)
(a |1| - ||l] öd(a u)² + ōd|lal?
Ef = [a u) - ||al d82|a| do
E[a 10 do
Then obtain
[Ef g/ = [E(e -
E 9 2
E(e a) 2 ||ul1 8 [B]u| 8
where (i) applies the Cauchy-Schwarr inequality. For convenience, we define X E(uTa)aa 1012
E(u"a)/|u12.
Then this inequality is simplified as:
[X dd [aa
1a
X² + x [|
|aa 82 [B] |la3]]
X²_ 262d|a/| [[]||||] 0005--822 82 [a| x 8| "B|u/
X2_ - -[25-d|a 2 [[B]=|[- []] x 1 B|
Let 2C = d|l +
Then
|a|| [Bl|oa| - -82 + +dddaa]' [B][|][[B][]+
C 5 //ll/|=E = 5t |||a
82 ||||| [[B||]]]
dd + 82d]
|ali
[B ||]
60 8 8' [E||]] 8dd 82|1a| [E|y| 02
aa
|| - 8 d2 82 1) [B||/]| - 82, =0.
Therefore, obtain upper bound and lower bound for X:
x C+ v C 8a
x C=
ddl
Here, (i) additionally applies the following statement: We assume X = 02 8d for some distribution V and an error term с > 0. Then we conclude that E||i/| < sl, which is impossible. The detailed proof is given as follows:
16

---

Published as a conference paper at ICLR 2025
Since Ea (vv) vv d c, for an orthogonal linear transformation O, we have B(O*a) a) T vv vo (6'dlaa|? - e) 0 = 0,
Because {O*a)k-o forms basis of TR. we conclude E. (uv ToTTeT (d'd)a|)--c),, 02 by using Lemma B.2, where 0₂2 represents the zero matrix with the dimension d x d. This further leads to
for 1,2.....
TrE vo vu (8 c)Ta) Oa
E||u|* 8² aal cd < 6² ||al?
Therefore, X < a leads to contradiction.
In the remaining of this proof, we will derive the equality condition. By the Cauchy-Schwand inequality, the equality holds if and only if f 0, g 0, rg for some 0. We discuss each condition separately. Throughout this discussion, we assume *
ʃ 0: That is, (v a.vu da 0 holds almost surely. By timing a' on both sides, this condition becomes
(a va 8||a|1?
= O: That is, (1lvl12 - 5d)a = 0 holds almost surely. By setting A = (1v|2 5d) Ia in Lemma B.6, this equality holds if and only if
|0| = 5d.
f = rg for some r > 0: That is,
(c aav - da r r||ui|2 - ōdja.
We will show that this condition cannot hold. Assume it holds for some then for the v * O, we have
(v (TTa)² -aTTv r(] r(//o|1 5d)aTo
TT a = rr[|u|] 5d)
Ev T a
(B]|uul| 5d)
- 8 = 0.
For the case TTa a= 0, we directly take the expectation on both sides:
δa 0.
Then the proof completed.
B.2 PROOF OF PROPOSITION 4.1
Proof. We prove parts (a) and (b) of the proposition separately.
For part (a), show that (vTa) a)² ō||l² After projecting thu onto the plane
Ps e Rd a EVōlal.
the resulting vector v satisfies a Tu = Ev /o|aa|| Squaring both sides yields (e a)² (a) (5vōllal)) 81 a/ proving part (a).
For part (b), we prove that E v v[vv (a (aT
8Tg- We express in terms of vini as Vnai be the unit vector in the direction of a. We can rewrite e as w + Evo where w Uini (u' Umm) u is orthogonal to u. Computing Te and taking the expectation, get Eive ] E[w
Uim - [v0 Let u [a]
a
dur" T. The cross terms vanish due the independence of E and Vnni and because E[E] = 0. Expanding ww and taking expectations, using E Fimil = 0 and E 2m = 8Ld. we obtain:
E www ]
8Ta dwn. T duu T dun 8Ta 8un
Finally, we have F 1 = E[ww T + SUuT 8I, - Suu + SouT = 8I,, completing the proof of part (b) and the proposition.
17

---

Published as a conference paper at ICLR 2025
B.3 SUPPORTING LEMMAS
The following result can be found in Hungerford (2012). We omit its proof here. Lemma B.2. Let A Rdxd be matrix. Suppose x² Ax for all R&, then A must be skew-symmetric matrix (i.e. A -A). Moreover, if a symmetric matrix (i.e. A A, then A must be a zero matrix.
A stronger version of the following lemma is given by Mirsky (1975), The equality condition can be found in Rhea (2011).
Lemma B.3. Let A and B be positive semidefinite. Then Tr(AB) & (r))
Proof. Let Tr(A). Then
Tr(AB) Tr (ū)
Tr(Bl (al)) Tr(A)T((B).
Here, (i) applies the semidefinite of B and Tr(AB) Tr(BA); (ii) applies the operator monotonic- ity of the trace operator.
The following lemma gives the explicit representation of the projection of vector Rd hyper-plane in R. This result can also be found in Seber & Lee (2012).
Lemma B.4. Let P {r: u c) Rd be hyper-plane associated with fixed vector u T and a constant с E R. For a given vector v E Rd, suppose that Proj(v) denotes the orthogonal projection of onto P. Then
Proj(v) == u(u c)/1u1².
Proof. The projection is given by the following optimization problem
min weRd
2 w - w/
S.L.
"
The Lagrangian is given by
[(w, A) = -11u- -21 + N(w T u c).
The projection is solved as
Proj(u) = v - u(v" u c)/1lu/?
Lemma B.S. Let v be a random vector following the distribution and all entries are mutually
independent. Then
B (Tr((uu
Σ B + d(d - 1).
Proof. To prove this result, it requires to explicitly evaluate E.-V v (Tr((vuT)2)) Let
[U1, U2. va] We will evaluate E((vTT))) by considering the i-th row and j-th column of To (vv ()=
[1ee1, 0,22. .... of...., vaaaa
02tfy
(we)) ) (vo)).j-
18

---

Published as a conference paper at ICLR 2025
Then, the (t, entry of (vv 2 is
12
d
(vv) (ouT)? Y2, [Tve1 0.0....... ,,...............
uz. ...., Usva
Taking the expectation on both sides and applying the independence, we obtain
0 [[ + (d-1)
i i-
Here, the constraint EFuu' T La implies that B for all i. Therefore, we have
E ((Tr((uVT)))
[ [vx
=
(Bluf) + (d 1))
B + d(d - 1).
Lemma B.6. Let Aa 0.
Id and A be positive semi-definite matrix. Then a Aa 0 if and only if
Proof. Since A is positive semi-definite, can represent A A B², where B is also positive semi-definite matrix. Then
A (a TB) = la B 0.
By the definition of vector norm, this equality holds if and only if a B 0. We multiply B on both sides and obtain Aa
C CONVERGENCE ANALYSIS OF ZEROTH-ORDER SGD
Our proof is mainly adapted from Khaled & Richtárik (2022) and Mishchenko et al. (2020) with additionally considering the variance introduced by gradient estimation.
Assumption C.1. In the optimization problem given by Eq. (1), the individual loss function f(= Rd satisfies the following two properties:
(a) L-Smoothness; for all x, R.d.
f(y < f(1=E) vf(x;E) x) 2 x/?
(b) Lower boundedness; the infimum f == znd f(x:E) exists almost surely with E.
Though this assumption could be further weakened to the expected smoothness assumption the objective function (Khaled & Richtárik, 2022), the current version has covered a sufficiently broad class of functions, including many neural network structures. By Rademacher's theorem (Evans & Gariepy, 2015), the L-smoothness implies the
differentiabillty of the gradient v fa: E), which makes the standard Taylor theorem directly available for the individual loss f(x;
For strongly convex settings, a faster convergence rate is often guaranteed; it relies on an additional assumption the objective function [(x (x==
19

---

Published as a conference paper at ICLR 2025
Assumption C.2. In the optimization problem given by Eq. (1), the objective loss function f(x) Ef==f(0; E) satisfies the c-strongly convexity property: that is, for all x, y E IR
('y) > f(x) + ()(x)"
x|?
We note that this assumption could be further relaxed to the Solyak-Lojasiewices condition f(x)
f* < CPL f(x)) (Karimi et al., 2016).
C.I PROOF OF THEOREM 3.1
In this subsection, we present the main proof for Theorem 3.1. Theorem C.3 gives the proof for Part (a) and Theorem C.4 gives the proof for Part (b). First, re-state these theorem follows:
Theorem C.3. Suppose that Assumption C.I and Assumption 2. I are satisfied. Let {ate) be the SGD dynamic solving Eq. (1) generated by the update rule Eq. (4). If the learning rate & min 2T.' LV/212554+pV +28+1) 3. then
min [I (f(1))-
2m
LBB (1+ (vv p² u²av)
lEET
where PV Bg==f().
B|rl1 - -2 av 1.3 By 252d + pV + - 152, and B² == 2I
Proof. We start from Eq. (11) from Lemma C.8:
8n E V
< (1 + 4L3/) + 2v (Ef(x)) - -Ef( f*) (I 3v) n²² prav,
2
For convenience, we define
Ef(xr) f", Mi LB² + 3v) 122y2vv, and c
1 + 4L2r,² + 3rr. Then
8n
V <x cx 8T 87+1 MT
8n E
V || & 8 δr cx
6r or + Mr-1
2
5n 2
_ - x1 cc x M1.
x
We sum all together. Then
min E V) & e 80 +
max M,. IstsT
2 1EtsT
Putting back the shortcut notations (6, = Ef(x;) - f" M, = LB + Bv) + 17 uav and
c = + 12 + Bvr),, the above inequality solves the upper bound of min, E (xx))) )| as
min E ((x;)) gge
(f(x1) - (() + max M, 18t8
8n Ei=0
5n
2
(f(z)) 5m 1 1IBB((1 + (v) + 12)
8n
2i
T-1
1 + 1L2 + 2LT
2 24LL2Tp + 21 BL17)
4L221² + + (vn2))
(f(x)) - f*)
bn
41 + 212 (v) -1
20

---

Published as a conference paper at ICLR 2025
2n 8
LB (1+ Bv) udarl
LB
(1E3 (137P-21/00))))
4L2n
2 (4)
e
2n ((x1)) +
LB + 3v) + 12ov)
8
T
412 22238177
5
(1)
(f(z)) f*)
27
LB² (1 + 0v) + p²av]
+
δnʃT
where (i) applies 1 + ex and (1+ x)²
1 b Tr, (ii) applies the condition
T AL2 2223vv
on the learning rate 1) B is given in Lemma C.6, and ov, By are given in Lemma C.8.
Theorem C.4. Suppose that Assumption C.I, Assumption C.2, and Assumption 2.1 are satisfied. Let {1r] be the SGD dynamic solving Eq. (1) generated by the update rule Eq. (4). If the learning &c.
rate & mint 2T 47, 26" 26- then
Ef(eT) f < (1 ( (f(1)) 1*) "LB' (v) + prvv),
where PV = B|vl ddd av = wl By = 25 pV + - 25, and B = 2I( E Bx==fg).
Proof. We additionally apply the e-strong convexity assumption made on the objective function to the left-hand-sid of Lemma C.8:
)n((Ef((x)) f*) (1+ 4L' + 8v1) (Bf(rr) 5*) - (Bf( -
(LB² + Bv) paaaa
For convenience, we define 6 = Ex()) f Mj = LB + 3y) + p2p2avv and
1 - cōn 17² (4I2 2L² By). Then re-arranging this inequality leads to
8.+1 & rd, + M
< r 81
Mi
Putting back the shortcut notations, the above inequality solves the upper bound of Ef(xr) f as
1 - M
Ef(eT) 8t T T- (f(x1) f*) +
c 6n) T-1 (f(z1) - f+) + +))
2
cbn (
& (1
mn) (f(zI) - (*) / (LBB (3)))+++++)++)) 3v)+ 1rav),
where (i) applies the condition
&
T 20242++1+p
āc
C.2 SUPPORTING LEMMAS
The following two Jemmas (Lemma C.5 and Lemma C.6) directly taken from Proposition 2, Mishchenko et al. (2020). We adapt the statement to our notations and give an explicit expression for A and B in Lemma C.6.
21

---

Published as a conference paper at ICLR 2025
Lemma C.S. Suppose that Assumption C.I is satisfied. Then the objective function f(z) Eg-=f( E) is also L-soooth and lower bounded; that is,
(a) for all v IRd.
f()) & f(x) (y(x)( x) + = flv - x1?
(b) The infinum f int f(x) exists almost surely.
Lemma C.6. Suppose that Assumption C.I is satisfied. Then for any x Rd.
f(v; - & 2A(f(x) - f*) + B²,
(8)
where the constants A 2L and B v 21 - -g===l()
Proof. By Lemma 1 from Khaled & Richtárik (2022), Assumption C.I (a) implies that
()I < (z; - f2):
[V/(=)] & (z)) 1*).
Summing them together leads to
[[V)(==;) V E V/(x; +
4T f*) 21 Ee-=JE)
Defining A == 2L and B = - concludes the proof.
Bę-=
The following lemma (Lemma C.7) builds the per-iteration recursion.
Lemma C.7. Suppose that Assumption C. satisfied. Let { {xt} be the SGD dynamic solving Eq. (1)
generated by the update rule Eq. (4). If the learning rate 1) & 21' then
8n E Vf(i))1 & (1+ (2AAA) - f*) (Ef(#1+1) f*)
(9)
+ LB² LEL,,
where A and B are given in Lemma C.6, and
L = [V vi) - ff(==&))
(10)
denote the accuracy of of [xxx &,, v.) for estimating (x);
Proof. Starting with L-smoothness of the objective function f (Lemma C.5), obtain
I, f(z(+1) & f(z)) + (V.(())) 2441 - xz) || - -
2
=((x) f( [x)) v()x Lnd
@ f(x.) "
[f(2,)] || IV - Ea
2
bi²
V E,, 21)l
f(x)) ([Vs(x))) 21 Ln)) L,) 0.12
= f(x)) "[(((=))] 2 Lt) vf(xa) vf(x,)1
+ "
V Ee. 2
22

---

Published as a conference paper at ICLR 2025
R [(x)) - 201 [V 22 ((1) Tn)
- + [V
+ Vff/)) Vf(2,))
+ (
(Hi)) (x(411
$ Bg (zr) - (17 - 2 Eg - Ln) D VV((m)
2
2 Eg, Vf(xz) - (f(zzi
(iv)
(x,) (1 11²
Beg [f(2;))] - n/(1 Lg. (f(z)) (wio) 1) f
2
L 1/:10:1/0// V[(zz) + r24 Es, [[(x)) - Elaeii vz)1
+
2
E/(0+1) & Bf(xa) (1) 1
B [[ 711 - Lo) - 1)
2
B
[ x,)
2
(v) Ef(x))
6n ff()))1 2
v2 T ElV] fez Ee, v,)l
where (i) applies the identity 2a, b) = |a|2
bll2, (ii) applies the identity ||a + b|2
|all + |]6] + 2a, b). (iii) takes the expectation with respect to the data distribution
E. (iv)
applics the Taylor theorem (Lemma C.9) to expand f(z, + vva) - f(xx) around 2,, and (v) uses bn
1 o óLn² >
8n when 17 & z We further notice that
((V)(r)) Vf(e Ee, 01 = F - (((:E)) + Vf(nn()) - ff(n vi)l
< f(xz) - (f(= + 2E vf(nn() -
(1)
4A;(f(x;;) f²) + 2B² 2EL,,
where (i) applies ||a+ b|| < a| + 21 and (ii) applies Lemma C.6. Rearranging the inequality, we obtain
8n
Vf(z))1 < (1 + 2AL (Bf(z)) - pz) (Ef(#441) f*)
+ LB² + + LELL
where A and B are given in Lemma C.6.
The following lemma (Lemma C.8) additionally handles the variance of two-point gradient estimator
L, = |/ f (Iz;; &e, v.) V (xx; E2] using the upper bound from Theorem 2.2 in the per-iteration recursion.
Lemma C.8. Suppose Assumption 2.1 is satisfied. Under the same setting as Lemma C.7, if the learning rate 1j & 2L. then
87 E V
(1 (1+ 4L' + 2L2Bvm2 (Ef(x)) f*) -BF((((4))))) (11)
2
+ 3v) + + 2
where PV : E/ av = 1 wl By = 25dd + pV + 1 - 25, and B = 2I( Be-=f²).
Proof. By Theorem 2.2, we have for any E Rd
||al|
|a|2
Evsya (ou < 8ddla|2 +
2 pv +
2 V pt + 4 1)pv
VP
23

---

Published as a conference paper at ICLR 2025
2 pplaa?? -20 pv) lal
where PV ||/l| 62dd.. Then
E Vf(z;)) Vf(z)) & (1 (1
(26 + pV 1- 26) B
Similarly, we obtain
E] - vx(x,))1 < (26 d PV + + Vf 1 B|u1+
< 2L (20 PV +1 28) B (f(z: -
l (() + ~=2
2L (28 + pV +1 28)
L2p"Be111
+ B² d pv
-1-))
By Lemma C.7, have
8n E V
& (1+ (E)()))) - (00))(EB(CCC -B)()))())))) (*)
+ LB² +1² LBL.
where and are given in Lemma C.6, and L == [Vf(z,;,, E,, vy) - ( For notional convenience, we define Bv := 2 PV - 28. Combining both upper bounds, we obtain,
6n E EEVS(())) + (1+2AT 1*) (R - (*)
L22? + B2 (1+ + (B/(()) (B
1*) -
+ 1
It completes the proof.
Evaluating the bias of the two-point random smoothing estimator (Eq. (2)) only requires the gradient Vf(:E)) Rd + R to be locally Lipschitz continuous. Then will apply the following Taylor theorem -Hiriart-Urutty et al., 1984; Luc, 1995):
Lemma C.9 (Taylor's 's Theorem). the function Rd IR is continuously differentiable and has locally Lipschitz gradient, then there exists e E| y|c Rd and M. DD2 f(c( such that
- (VI(y), 4) 1 [ -), v).
Here, |x, yI represents the open rectangular defined by x, x. Rd.
Remark. Using the L-smoothness of f, we can show that there exists the upper bound
f(x + pm) f(x) < pm T ff(x) 1pl
It leads to the approximation of the zeroth-order gradient estimation for V V(():
vf(ze))
f(x pv) - f(x = ve Tv Lu 22
Therefore, the Mean Mean-Squared Squared Error (MSE) of (z; is bounded by
E ();;))) - [(()] & (x(x) (vo 'V + 26) v[)²) 23
D DETAILS ON EXPERIMENTS SETUP
This section outlines the information for replicating our experiments. All source codes, including visualization scripts, provided with submission.
24

---

Published as a conference paper at ICLR 2025
Hardware and System Environment We conducted our experiments cluster running RHEL8, equipped with Dual AMD EPYC 9124 processors and eight NVIDIA RTX 6000 Ada Gen- eration graphics cards. Our code tested using Python version 3.10.10. Additional dependencies are specified in the supplementary "requirements.xx" file.
Hyperparameters For the LLM fine-tuning task, employed the following hyperparameters::
Learning rate 10-4;
Perturbation size μ. 10-5;
Zeroth-order gradient estimation batch size 2;
Stochastic gradient updates batch size: 16.
E
ADDITIONAL EXPERIMENTS
In this section, we include additional experiments figures that are not presented in the main text.
E.1 COMPARISON WITH OTHER RANDOM PERTURBATIONS
In this subsection, additionally consider the Rademacher perturbation and the random coordinate perturbation in fine tuning the language model. To avoid the significant overlapping their training loss curves, also present the boxplot of their training loss within the last 5000 steps for better comparison.
0.9
Rademacher Perturbation
0.45
Coordinate Perturbation
Gaussian Perturbation
Uniform Perturbation
0.7
DAP (Estimated Gradient)
Training Loss
Training
0.5
0.25
0.3
0.20
0
4000
8000
12000 16000
20000
Training Step
0.15
DAP
Gausslan
Rademacher
Figure 5: Performance comparison of different optimization methods for fine-tuning OPT-1.3b on SST-2. Compared to Figure 4, we additionally include other two constant magnitude perturbations: Rademacher perturbation and Random coordinate perturbation. The left figure presents the boxplot of training losses within the last 5000 steps.
E.2 THE ADDITIONAL PRACTICAL APPLICATION: MESH OPTIMIZATION
In this subsection, we consider the mesh optimization problem (Hoppe et al., 1993). which serves as another application of the zeroth-order optimization with utilizing our proposed DAPs. To find the solution of the partial differentiable equations (PDEs), it commonly applies the numerical method such the finite volume method (Eymard et al., 2000). Such method requires pre-defined mesh to describe the critical points on the solution surface and the boundary condition. The mesh optimiza- tion problem is optimizing the pre-defined mesh to make the PDE solver have better performance by adjusting vertex positions, element connectivity, and local mesh density to minimize numerical emror and improve solution accuracy.
25

---

Published as a conference paper at ICLR 2025
In this experiment, we consider the mesh optimization problem of 2D Poisson's ' equation (Evans, 2022):
Ap= = f.
where pp R2 E and f I2 R are both twice differentiable continuous functions and A the Laplace operator (i.e. (z (121,,22,-00 22,...., ال= ) It commonly used to model the pressure field of the incompressible Navier-Stokes equation (Acheson, 1990). Its solution is illustrated in Figure 6; our goal is to optimize the coarse mesh to make the numerical solution over the given coarse mesh closer the solution the the high-resolution fine mesh.
Fine Mash
Coarse Mosh
0.08
0.1
0.005
0.000
003
0.005
0000
001
Figure 6: Numerical solutions of the Poisson equation Aş 1 with Dirichlet boundary conditions. The left panel compares two numerical solutions: one computed on fine mesh (20 x 20) and another on a coarse mesh (10 10). The right panel shows the difference between these solutions. The discrepancy is particularly pronounced at the corners, suggesting that denser vertices locating may be necessary in these regions for better accuracy.
The following figure applies the zeroth-order optimization method to minimize the Lx distance (i.e. the absolute error) between the interpreted numerical solution over the coarse mesh and the numerical solution over the fine mesh. The DAP method achieves better performance than the baseline approaches (including the uniform perturbation and the Gaussian perturbation).
0.0033
DAP (Estimated Gradient)
0.0032
Uniform Perturbation
Gaussian Perturbation
Max Absolute Error
0.0031
0.0030
0.0029
0.0028
0.0027
0.0026
50
100
150
200
250
Step
Figure 7: The training loss of the mesh optimization problem for minimizing the Lx distance (i.e. the max absolute error) between the interpreted numerical solution over the coarse mesh and the numerical solution over the fine mesh. We use the batch size 512, the perturbation step = 10 5 and the learning rate r 0.1.
We also visualize the estimated gradient at the beginning of the training. We use the two-point gradient estimator with the batch size b 100000 and μ 10-5 obtain the estimated ground truth gradient. As shown in Figure (Left), only the four corners of the mesh have significant weights. In this case, the anisotropy nature of the DAP leads to accurate estimation important vertices.
26

---

Published as a conference paper at ICLR 2025
Ground Truth
Unioom Pettubation
IEstimated Gradient
60
Figure 8: The illustration of the estimated gradient using the uniform perturbation and the DAP with the magnitude larger than 0.4. The batch size of obtaining the ground truth is b 100000. The batch size for obtaining the estimated gradient is 100.
F DISCUSSIONS ON THE ACCUMULATIVE ERRORS
When approximating the stochastic gradient Vf(x; {), the two-point gradient estimation naturally introduces additional approximation error. We have previously characterized this error term in the one-step improvement analysis:
();;) - V)(x)
& vp Vs(x) 00 ())()))))))++++))))))))))))))))) + 200 + L2 2 ul|
Elll"
1² (25 + 1 1 25) 12
We note that the gradient term [+) will be merged together in the convergence analysis we have built in Theorem C.3 and Theorem C.4. Our main focus falls into the last error term L 2 [ When telescoping the one-step iteration from Eq. (11), obtain
Accumulative Errors 2
mpaav
c5
for the strongly convex objective functions, where e is the strongly convex constant, is the learning rate, and ov T,3 u|
and
2n
Accumulative Errors pav
8
for the non-convex objective function, where 7 and ay defined above. Both error terms have been reflected the convergence upper bound and their dependence on μ²² is common in classical zeroth-order optimization literature (Kozak et al., 2023).
G LIMITATIONS
While theoretical and empirical results demonstrate the potential of DAPs, there aspects that warrant further investigation. First, when the dimension d is extremely large, the projection steps in sampling DAPs requires storing the full gradient estimates, which introduces additional memory overhead compared to simpler perturbation schemes like uniform or Gaussian perturbations. Sec- ond, while DAPs show advantages in scenarios with sparse gradients. they may not perform as well when dealing with dense gradients, as the error introduced by gradient estimation could potentially outweigh the benefits of directional alignment. Finally, although our experiments demonstrate the effectiveness of DAPs both synthetic problems and language model fine-tuning, we have not extensively tested the method across broader range of applications and problem settings, and the performance benefits may not generalize to all optimization scenarios.
27


Reviews:
[{"review_id": "oJAXo71f4I", "reviewer": "Reviewer_6hyB", "summary": "***Summary:***\nIn the paper the authors study (sufficient?) conditions on the  distribution of the sampling directions in order to build a two-point finite difference estimator of the gradient that is at the same time unbiased and with minimal variance. Then they state convergence results for SGD using this kind of estimators (in the non-convex and stronly-convex case), showing that they achieve the optimal complexity in terms of dimension. Finally they focus on DAP (directionally aligned perturbation), a new estimator which satisfies unbiasedness and minimal variance. They design an algorithm to implement it and show promising numerical experiments.", "questions": "1) P3, Theorem 2.2: the inequalities are clear, but it is not clear to me what you can deduce from them, as they give only a lower- and upper-bound on the quantity you want to minimize. Is it true that the variance is minimal if and only if $\\rho_V=0$? Or $\\rho_V=0$ is only a sufficient condition? Are conditions (a) and (b) sufficient conditions to get $\\rho_V=0$? Apparently no, since from (b) you can not get $\\rho_V=0$. To me, it is not completely clear the logic of the reasoning neither the statement. This is true especially in connection with the comment on Gaussian Smoothing at P4: does the fact that $\\rho_V>0$ imply that Gaussian Smoothing does not achieve minimal variance? From the inequalities of the Theorem you just know that the variance is lower-bounded and upper-bounded by two different quantities...\n\n2) P6, DAP: for the unknown gradient $\\nabla f(x)$, you can apply a small batch of perturbations to obtain an estimated gradient. Second level question: with which distribution do you sample $v$ for the estimator of the gradient used in DAP?\n\n\nMore bibliography:\n\n- Cai, Mckenzie, Yin, Zhang: Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling; SIAOPT 2022\n\n- Cai, Mckenzie, Yin, Zhang: A One-bit, Comparison-Based Gradient Estimator; ACHA 2022\n\n- Rando, Molinari, Villa, Rosasco: Stochastic Zeroth order Descent with Structured Directions; COAP 2024\n\n- The paper [Rando, Molinari, Villa, Rosasco: An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization] has been published in NeurIPS 2023\n\n- Akhavan, Chzhen, Pontil, B. Tsybakov: A gradient estimator via L1-randomization for online zero-order optimization with two point feedback; NeurIPS 2022\\\\\n\n***Minor comments:***\n\nP2: the formula in Contribution 1 is not correct, should be $\\nabla f(x;\\xi)$ without the $v$\n\nP2: explain why the constraint $\\mathbb{E} vv^T = \\delta I$ gives the unbiasedness of the gradient approximation (this is true only for $\\mu \\to 0$); why do you say it is a linear constraint?\n\nP3, L124: first line of the equation is wrong; in the second line, where is the second order term with $M_c(v)$? Explain better the approximation you make...\n\nP4, DPA: highlight that, in the practice of zeroth order optimization, this condition can not be imposed like it is, since $\\nabla f(x)$ is not available\n\nP4, L187: $a^Tv=\\pm \\sqrt{\\delta}\\|a\\|$\n\nP4, L206: $\\hat{\\nabla}f(x;\\xi)$ has not been defined, but only $\\hat{\\nabla}f(x;\\xi, v)$\n\nP4, L210: comment that the quantity $\\min_t \\|\\nabla f(x_t)\\|$ is not something you can check in the practice of zeroth order optimization; in particular, you don't know which one is the best iterate accordingly to the criterion $\\|\\nabla f(x_t)\\|$\n\nP4, L210: $f^*$ not defined\n\nP5, L222: $\\mathbb{E}_{\\xi} f^*_{\\xi}$ not defined\n\nP5, L226: say that $c$ is the strong-convexity constant (it appears only in the definition in the appendix)\n\nP5, L238: comment (a) is not clear to me\n\nP5, Corollary 3.2: \"If choosing\" is not correct (used twice); the bound $\\leq \\varepsilon$ has constants involved that are omitted\n\nP6, Fig. 1: the caption is not clear to me", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "***Main comments:***\nThe review of the literature is complete, the problem is meaningful and relevant, the theoretical results are significant, the proofs are correct. The paper is interesting and well-written, the presentation is both concise and comprehensible.", "weaknesses": "The paper is well written but there are some points with imprecise statements.  See the comments in the Questions box. \n\n1) The stochastic optimization setting (in $\\xi$) is not needed in the first part of the paper but only for SGD (Section 3), and it creates confusion.\n\n2) P3, Theorem 2.2: the inequalities are clear, but it is not clear to me what you can deduce from them, as they give only a lower- and upper-bound on the quantity you want to minimize.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dWmUHJ2xCe", "reviewer": "Reviewer_BjSg", "summary": "This paper studies the two-point zeroth-order gradient estimator, specifically focusing on the problem of identifying the optimal distribution of random perturbations that minimizes the estimator's variance. In Section 1, they briefly introduce the preliminary concepts and raise the motivating questions of the work. They first question whether it would be possible to determine the class of optimal distributions of random perturbations in a zeroth-order estimator to minimize its variance, and provide Theorem 2.2 as the answer. In Theorem 2.2, they introduce two sufficient conditions for the question, which are constant magnitude perturbations and a novel condition called directionally aligned perturbations (DAPs). In Section 4, they take a closer look at DAPs and provide a sampling strategy for practical implementation. Finally, in Section 5, they demonstrate the practical effectiveness of DAPs through two experimental setups with a synthetic example and language model optimization.", "questions": "- Could you provide the explanation related to the reviewer's questions in the weakness?\n\n- Is (a) and (b) in Theorem 2.2 sufficient conditions for achieving the minimum variance, or are they also necessary conditions?\n\n- It seems the authors claim in the remark about (a) of Theorem 3.1 that a small $\\delta$ leads to more gradient updates. However, it appears that Theorem 3.1 provides an upper bound result, so it may not serve as logical evidence for your discussion. Or do you have a lower bound result as well?\n\n\n**Minor questions:**\n- Is the definition of parameters in (a) and (b) of Theorem 3.1 the same? Is there a reason you are repeating them?\n- Did you try to write $< \\infty$ in line 215?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To the best of the reviewer's understanding, the core contributions of this paper are two parts:\n- This paper formalized the problem of characterizing the class of optimal distributions of random perturbations in a zeroth-order estimator to minimize its variance and provided sufficient conditions.\n- Based on the first contribution, they conceptualize the novel condition which they name DAPs, provide a way to use it practically, and demonstrate the effectiveness by experiment.\n\nThe reviewer thinks these are meaningful contributions. The paper also shows that the complexity of SGD with two-point gradient estimation achieves the best-known sample complexity when the perturbation distribution $V$ is chosen to achieve the minimum variance.\n\nAlso, the reviewer thinks the writing of the paper is overall nice.", "weaknesses": "This can be closer to a question than a weakness, however, the reviewer is confused about the underlying logic and contribution of Section 3. The reviewer may be missing some elementary points, but they are still confused about the sufficient and necessary condition for minimum variance.\n\n- The most confusing point was the relation between the fourth-order moment. In Theorem 2.2, as addressed in the Remark, it seems (2) has minimum variance when equality holds. But is the converse also true? It seems the terms related to the fourth-order moment only appear in the upper bound. If the converse doesn't hold, isn't the finiteness of the fourth-order moment neither a sufficient nor a necessary condition for achieving minimum variance? In this context, is the finiteness of the fourth-order moment an additional assumption (other than minimum variance) imposed to obtain the results in Section 3?\n  \n- The reviewer thinks the observation about the influence of the fourth-order moment addressed in the Remark of Theorem 3.1 can be meaningful by itself. However, the reviewer thought the main focus of the paper was the conditions for minimum variance and specifically DAPs. Yet, the first half of Section 3 seems to be just a convergence analysis of SGD, with the assumption of the finiteness of the fourth-order moment. According to the authors' explanation, the proof heavily relies on arguments considered in prior works.\n  \n- In short, what is the role of Theorem 3.1 in the overall context of the paper? It seems Theorem 2.2 is used in the proof; is it crucial? The reviewer thinks it would be better to address a quick overview of Section 3 in the overall context of the paper at the beginning of the section. The reviewer felt lost when first reading Section 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GXC63gIb3G", "reviewer": "Reviewer_F997", "summary": "This paper explores the two-point zeroth-order gradient estimator and identify the optimal distribution of random perturbations that minimizes the estimator's variance. This paper formulates it as a constrained functional optimization problem over the space of perturbation distributions. This paper reveals that optimal perturbations either maintain a fixed length or align directionally with the true gradient. While existing research has largely focused on fixed-length perturbations, the potential advantages of directional alignment have been overlooked. To address this gap, this paper delves into the theoretical and empirical properties of the directionally aligned perturbation (DAP) scheme, which adaptively offers higher accuracy along critical directions. Additionally, this paper provides a convergence analysis for stochastic gradient descent using $\\delta$-unbiased random perturbations, extending optimal complexity bounds to a wider range of perturbations. Through empirical evaluations on both synthetic problems and practical tasks, we demonstrate that DAPs outperform traditional methods under specific conditions.", "questions": "No.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper explores the two-point zeroth-order gradient estimator and identify the optimal distribution of random perturbations that minimizes the estimator's variance. This paper formulates it as a constrained functional optimization problem over the space of perturbation distributions. This paper reveals that optimal perturbations either maintain a fixed length or align directionally with the true gradient. While existing research has largely focused on fixed-length perturbations, the potential advantages of directional alignment have been overlooked. To address this gap, this paper delves into the theoretical and empirical properties of the directionally aligned perturbation (DAP) scheme, which adaptively offers higher accuracy along critical directions. Additionally, this paper provides a convergence analysis for stochastic gradient descent using $\\delta$-unbiased random perturbations, extending optimal complexity bounds to a wider range of perturbations. Through empirical evaluations on both synthetic problems and practical tasks, we demonstrate that DAPs outperform traditional methods under specific conditions.", "weaknesses": "I don't think the study over problem Eq. (3) is meaningful. \nUnder the theory of this paper, the random coordinate is better than Gaussian random vector.\nHowever, just as pointed out in Theorem 1 of  \"Fine-tuning language models with just forward passes'', the Gaussian random vector can provide a \"Dimension-Free Rate''.\nUnfortunately, the random coordinate can not  guarantee this ``Dimension-Free Rate'' even it is good under the thooery of this paper.\n\nThe experiments in this paper do not show significant advantages of DAP over other estimations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eNMD5i0uKW", "reviewer": "Reviewer_gWHS", "summary": "The paper studies the zeroth-order gradient estimator and identifies the optimal distribution of random perturbations that minimize the gradient estimator's variance.\nThe problem is formulated as a constrained optimization problem. And it is shown that the optimal perturbations maintain a fixed length or align directionally with true gradient.\nThese gives two classes of random perturbations that achieve the minimum variance : Constant magnitude perturbations and Directionally aligned perturbations.\nConvergence of SGD with both these classes of perturbations are proved. And some experimental results are shown.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The problem studied is of significant interest to the optimization community. And it shows two classes of random perturbations that give minimum variance.", "weaknesses": "In the main theorem (Theorem 2.2), what about only if part ? Does it happen that equality holds in theorem only if the given conditions (a) or (b) is satisfied ?\nA discussion of this would be interesting.\nThe experimental results are weak. Only one practical application of language model optimization is given.\nNo comparisons with other constant magnitude perturbations: random coordinate/direction sampling and Rademacher distribution are shown.\nWhy DAP perturbations give better performance than uniform perturbation in experiments is not clear. As the theorem says that theoretically both give minimum variance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KwWlUX0reD", "reviewer": "Reviewer_aCKy", "summary": "In this paper, the author(s) propose a new perspective on zeroth-order methods, focusing on an optimization problem that minimizes the variance. After carefully crafting the problem instance, based on constraints that are standard in literature, some comments on classic choices of fixed-length perturbations are made. This is the right motivation to proceed and advocate for  \"directionally aligned perturbations\", the other \"optimal choice\". In particular, the theorems derived in this branch for convergence of SGD under standard assumptions make explicit the role of higher moments of the distribution, while still recovering nice to parse upper bounds. To conclude, the author(s) come back to the directionally aligned perturbations and show some experiments for synthetic datasets and a Language task. The practical feasibility of their optimization problem is also discussed.", "questions": "1. Have you analyzed the impact of the Taylor approximation in your analysis? \n2. Have you analyzed the impact of the difference between theoretical analysis and estimating gradients in the wild? I acknowledge the experiment for the easy functions, where it is exact. \n3. Why would the assumption of isotropic noise $\\mathbb{E}[vv^\\top] = \\delta I_d$ be valuable in terms of perturbations? Why not something else?\n\n\n\nI am very open to changing my score once the issues I have raised are addressed!", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper presents a nice idea to describe a framework. The optimization problem set up is easily solvable, making the narrative flow. The result is approachable, clear, allowing to derive convergence rates that are expressive of all the dependencies on the various parameters. The plot converges towards \"defending\" these directionally aligned perturbations, which are of interest even simply because the standard choice is the other optimal one. By passing through simple examples, they are also able to experimentally verify their formulation. Overall a very standard but structured paper in optimization.", "weaknesses": "See also the questions below. \n\nThe main weakness is about wording: you claim you identify the optimal distribution in the abstract, while indeed you do not. I feel like the sentence should be adjusted. You find a sufficient condition for optimality subject to a construction of isotropic perturbations (you $\\delta$-unbiasedness) and a Taylor approximation. This to me is not identifying an optimal distribution, nor identifying anything optimal at all, if not only wrt your specific criterion, which then you would have to specify anyway. \n\nI feel like the other main weakness is experimental validation. I believe you have brought the best results you could find, and still, the improvement is marginal. For example, figure $3$ right is really an improvement in machine precision. Figure $4$ is more promising. I also acknowledge that we should not care about SOTA but about understanding, so this is a weakness that is not suggesting any further comment. \n\nThe other point is that you do not discuss the accumulation of errors when you (i)\n perform the Taylor approximation and (ii) perform the gradient estimation. I believe the two should be theoretically explored further to understand in restricted settings how much is lost wrt the convergence theorems. \n\nLastly, no limitations are discussed. \n\n\n###### Typos\nPlease do not count these as weaknesses. \n- You never define $\\nabla f(x; \\xi, v)$, (e.g. line 085), since the notation for derivatives variable, I would define it. \n- \"In the mean while\" (line 166), meanwhile; \n- The numbering of lists as $(1), (2)$ etc resembles a lot equations, not a typo but a potential source of anti-dynamic reading; \n- line 215, you say $< 0$, probably meant to be finite. \n- line 264 \"to a specific types of...\"\n- line 269 \"achiving\"\n- \"classitcal\" (line 472)\n- \"it solves the projection is...\" (line 864)\n- corollary 3.2 (b) the sentence is not correct logically. If we add the assumption by choosing further specific scalings we get the result, right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)