On Adaptivity in Zeroth-Order Optimization
Hassan Dbouk * 1 Nidham Gazagnadou * 1 Matthias Reisser * 1 Christos Louizos 1
arXiv:2605.03869v1 [cs.LG] 5 May 2026
Abstract
fine-tuning using only forward passes (Malladi et al., 2023), and are thus more memory and computationally efficient. In a nutshell, ZO optimization approximates the gradient through the loss difference at randomly-perturbed trainable parameters.
We investigate the effectiveness of adaptive zeroth-order (ZO) optimization for memoryconstrained fine-tuning of large language models (LLMs). Contrary to prior claims, we show that adaptive ZO methods such as ZO-Adam offer no convergence advantage over well-tuned ZOSGD, while incurring significant memory overhead. Our analysis reveals that in high dimensions, ZO gradients lack coordinate-wise heterogeneity, rendering adaptive mechanisms memory inefficient. Leveraging this insight, we propose MEAZO, a memory-efficient adaptive ZO optimizer that tracks only a single scalar for global step size adaptation. We support our method with theoretical convergence guarantees under standard assumptions. Experiments across multiple LLM families and tasks demonstrate that MEAZO matches ZO-Adam’s performance with the memory footprint of ZO-SGD. Additional experiments on synthetic quadratic problems and LLM fine-tuning further demonstrate MEAZO’s enhanced robustness to step size choices, particularly in grouped or block-structured optimization settings.
Due to the inherent stochasticity of parameter perturbations, ZO gradients exhibit high-variance leading to slower convergence in terms of number of optimization steps compared to first-order (FO) methods. However, each ZO step is typically less computationally intensive than the backpropagation step required by FO methods. Therefore, ZO vs. FO poses a trade-off in speed/energy to convergence given specific hardware constraints and task-specific characteristics. A substantial line of recent work aims to address this variance issue by introducing adaptive ZO algorithms, such as ZO-Adam and its variants (Chen et al., 2019; Nazari et al., 2020; Jiang et al., 2024; Shu et al., 2025). These methods mirror FO adaptive optimizers by tracking first and second moments of ZO gradients with the goal of improving convergence. In this work, we revisit this assumption and show that, contrary to prior claims, FO-style adaptivity provides limited benefits for ZO optimization in high-dimensional transformer models. Recent studies on FO training dynamics (Zhang et al., 2024a; Tomihari & Sato, 2025) demonstrate that Adam’s advantage over SGD arises from gradient heterogeneity: a strong coordinate-wise variation in gradient magnitudes. We provide evidence that ZO gradient estimates, due to the isotropic nature of random perturbations in high dimension, are essentially homogeneous. As a consequence, adaptive per-coordinate normalization has little meaningful structure to exploit.
1. Introduction Fine-tuning large language models (LLMs) can specialize their behavior to various use-cases: aligning to a specific domain, application, task (Gururangan et al., 2020) or integrating user preferences (Gao et al., 2024) are some examples thereof. Backpropagation is a standard but memory and computationally heavy fine-tuning algorithm, due to its need of activation caching and floating-point precision.
Building on this insight, we propose a memory-efficient adaptive zeroth-order (MEAZO) algorithm, which achieves global step size adaptivity by tracking only a single scalar for gradient normalization1 . This minimalist design enables MEAZO to match the memory footprint of ZO-SGD while retaining the convergence properties of ZO-Adam. Our experiments across multiple models and datasets show that properly tuned ZO-SGD already matches or surpasses ex-
Zeroth-order (ZO) methods on the other hand have recently gained attention in the LLM literature as they allow model 1
Qualcomm AI Research. [email protected]>.
Correspondence to:
<hd-
Preprint. May 6, 2026. Individual contributions highlighted in Appendix A. Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.
1
We show experimentally in Appendix E that first moment normalization is not required for adaptive ZO.
1
On Adaptivity in Zeroth-Order Optimization Validation Loss
isting adaptive ZO optimizers, and that MEAZO achieves performance comparable to ZO-Adam with negligible additional memory cost. Moreover, while ZO-SGD performs strongly when well tuned, MEAZO exhibits greater robustness to step size (learning rate) choices, making it a practical, stable, and scalable alternative for ZO fine-tuning in memory-constrained environments.
FO-Adam FO-SGD ZO-Adam ZO-SGD
2.5 2.0 1.5 0
2000
8000
10000
Figure 1. LoRA fine-tuning Llama-3.2 1B on XSum for various optimizers with optimal step size.
Notation. We adopt the following conventions. Vectors are denoted by bold lowercase letters (e.g., x, y). Matrices are denoted by bold uppercase letters (e.g., W, A, B). We use the following indexing notation: [x]k := xk to represent the k th entry of x.
Definition 2.3 (ZO Gradient Estimator). Given a function f : Rd → R, the q-sample zeroth-order (ZO) gradient estimator (Malladi et al., 2023) is defined as
Setup. We study the standard stochastic optimization problem: min F (x) := Eξ∼D [f (x; ξ)] , (1)
q X ˆ q (x) := 1 ∇f ∆fε (x; ui ) ui , ε q i=1
x∈Rd
where F : Rd → R is the objective function, ξ ∼ D denotes samples from a data distribution D, and f is the sample loss function. The variable x ∈ Rd is the d-dimensional parameter vector we aim to optimize. When clear from context, we drop the dependence on ξ and write f (x; ξ) as f (x) for simplicity.
(2)
where {ui }qi=1 are i.i.d. random direction vectors satisfying E[u] = 0,
E[uu⊤ ] = σId ,
and ε > 0 is the finite-difference perturbation scale. Variants of (2) exist (e.g., choice of sampling distribution2 , forward vs. central differences). Unless stated otherwise, we assume ui ∼ N (0, Id ). These choices typically have minor impact on performance, as ZO methods exhibit similar behavior under standard settings.
We will frequently use the notion of smoothness, as it is standard in non-convex optimization. In particular, we assume that the sample loss function is L-smooth: Definition 2.1 (L-smoothness). A differentiable function f : Rd → R is said to be L-smooth if its gradient is LLipschitz continuous, that is,
The estimator in (2) provides an unbiased estimate of the gradient of a smoothed version of the objective, defined as fε (x) := Ev∼Q f (x + εv) .
∀x, y ∈ Rd .
ZO Optimization. In the ZO setting, we aim to solve (1) without access to exact gradients of f . Instead, optimization relies solely on function evaluations. A central building block is the finite-difference approximation of the directional derivative:
The smoothing distribution Q depends on the perturbation scheme: for uniform perturbations, smoothing occurs over the unit ball B (Flaxman et al., 2004), whereas for Gaussian perturbations, smoothing is under a normal distribution (Nesterov & Spokoiny, 2017). This smoothing interpretation is key: ZO methods do not approximate the true gradient of f directly but rather the gradient of fε .
Definition 2.2 (Projected Gradient). For a point x ∈ Rd , a direction vector u ∈ Rd , and a perturbation magnitude ε > 0, the ZO projected gradient (finite-difference directional derivative) is defined as ∆fε (x; u) :=
6000
Steps
2. Problem Setup and Notation
∥∇f (x) − ∇f (y)∥ ≤ L∥x − y∥,
4000
Block Coordinate ZO. The estimator in (2) can suffer from high variance in high-dimensional settings. Several variance reduction techniques have been proposed, including block coordinate ZO (Zhang et al., 2024b), which partitions the parameter space into smaller blocks and estimates gradients within each block.
f (x + εu) − f (x − εu) ≈ u⊤ ∇f (x), 2ε
which provides a zeroth-order estimate of the directional derivative of f at x along the direction u (when f is differentiable).
Definition 2.4 (Grouped ZO Gradient). Let f : Rd → R be an objective function, and let {Xj }pj=1 be a partition of the coordinate set [d] := {1, . . . , d} into p disjoint blocks. For
Using this building block, we can construct an estimate of the full gradient through random sampling of direction vectors.
2
2
When u ∼ Uniform(S), the estimator is scaled by d
On Adaptivity in Zeroth-Order Optimization
Figure 2. Second moment estimate of FO-Adam, ZO-Adam and MEAZO across training on synthetic quadratic objectives.
each block Xj , define a binary mask vector mj ∈ {0, 1}d such that [mj ]k = 1 if k ∈ Xj and 0 otherwise. The block q-sample ZO gradient estimator is:
methods such as Adam in this setting introduces unnecessary complexity and computational overhead without providing meaningful benefits.
p q X X ˆ εq,p (x) = 1 ∆fε x; mj ⊙ ui (mj ⊙ ui ), (3) ∇f q i=1 j=1
Proposition 3.1 formalizes this intuition by analyzing the expected squared gradient: Proposition 3.1 (Gaussian). Let f : Rd → R be an Lˆ εq (x) denote the q-sample ZO smooth function, and let ∇f estimator in (2), where ui ∼ N (0, Id ) for all i ∈ [q] := {1, . . . , q}. Then in the ε → 0 limit we have: h i ˆ q (x)2 ≈ 1 ∥∇f (x)∥2 1d + ∇f (x)2 +∇f (x)2 , Eu ∇f ε q (5) 2 where (·) stands for the element-wise power of 2 and Eu denotes the expectation over u1 , . . . , uq .
where ui are i.i.d. random direction vectors and ⊙ denotes element-wise multiplication. When the partition consists of a single block, i.e., p = 1 and m1 = 1d , the grouped estimator in (3) reduces to the standard ZO estimator in (2).
3. Adaptivity and Zeroth-order Optimization
The proof of Proposition 3.1 appears in Appendix H.1, and the corresponding result for the uniform perturbation estimator is given in Appendix H.2. Proposition 3.1 reveals that the use of ZO gradient estimators introduces a bias in the expected squared gradient. This bias term scales as 1 2 q ∥∇f (x)∥ and vanishes as q → ∞. However, in practical settings where q ≪ d, and under the reasonable assumption that ∥∇f (x)∥2 grows with dimension d faster than 1/q, this bias becomes dominant. Importantly, the dominant component depends on the global gradient norm rather than individual coordinates, making it effectively coordinate-agnostic. The same observation also applies to Proposition H.1 with uniform perturbations. Consequently, using coordinate-wise adaptive optimizers (e.g., Adam) is misaligned with the underlying statistics, since the estimator tracks global rather than per-coordinate information in expectation.
Coordinate-wise adaptive optimizers, such as Adam (Kingma & Ba, 2014), have become the default choice for training and fine-tuning LLMs in first-order (FO) optimization settings. Their success stems from the ability to leverage per-coordinate gradient statistics, enabling effective step size adaptation across different dimensions. Specifically, Adam maintains bias-corrected exponential moving averages (EMAs) of the first moment, m̂t ∈ Rd , and second moment, v̂t ∈ Rd , of the gradient and updates parameters x ∈ Rd as: m̂t xt+1 = xt − η √ , (4) v̂t + ζ where η > 0 is the step size and ζ > 0 is a small quantity to improve numerical stability. This formulation allows Adam to adaptively scale updates for each coordinate based on historical gradient information.
Empirical Evidence. We validate our theory by examining performance and second-moment statistics from LoRA fine-tuning of Llama-3.2 1B on XSum (with tuned step sizes). Figure 1 shows that, after proper step size tuning, ZO-SGD matches the performance of ZO-Adam on XSum, despite Adam being the dominant optimizer in FO scenarios. This suggests that coordinate-wise adaptation provides little benefit in ZO settings.
This advantage does not naturally extend to the ZO optimization context, where such per-coordinate structure is absent. Unlike FO gradients, the estimator in (2) is dominated by randomness for practical values of q rather than per-coordinate gradient information. The estimator averages over only q random directions, where typically q ≪ d. Consequently, even when averaging, the signal remains highly isotropic and does not capture rich per-coordinate patterns. Consequently, applying coordinate-wise adaptive
To further understand dependence on d, Figure 2 shows the 3
On Adaptivity in Zeroth-Order Optimization
Algorithm 1 MEAZO Algorithm
This scalar tracks global curvature and enables adaptive step size scaling without sacrificing ZO’s simplicity.
1: Input: initial parameters x0 , objective function f , step
size η, decay rate β, number of noise samples q, distribution P , number of iterations T 2: Output: solution xT 3: Initialize: v0 4: for t ∈ {1, ..., T } do 5: sample mini-batch ξ 6: sample q noise vectors ui ∼ P 7: compute q projected gradient terms ∆fε (xt ; ui , ξ) 8: /∗ update vt Pq 9: g ← i=1 ∆fε (xqt ;ui ,ξ) 10: vt ← βvt−1 + (1 − β)g 2 ▷ bias correction (if v0 = 0) 11: v̂ ← 1−βvtt−1 12: /∗ update parameters Pq ∆fε (xt ;ui ,ξ) η 13: xt ← xt−1 − √v̂+ζ ui i=1 2εq 14: end for 15: return xT
Update Rule. The MEAZO update at iteration t is: ! q η 1X xt+1 = xt − √ ∆fε (xt ; ui )ui , v̂t + ζ q i=1 where v̂t is the bias-corrected EMA of gt2 , and ζ is a small constant for numerical stability. This preserves the benefits of adaptivity while keeping memory overhead comparable to ZO-SGD. 4.1. Theoretical Guarantees We consider the setup in Section 2, and state the following assumptions on the stochastic loss f (·; ξ) and its gradient ∇f (·; ξ): Assumption 4.1 (L-smoothness). The function f (·; ξ) : Rd → R is differentiable and L-smooth for all ξ for some L ≥ 0. Assumption 4.2 (Bounded Variance). There exists σ > 0 such that, for all ξ, h i 2 Eξ ∥∇f (x; ξ) − ∇F (x)∥ ≤ σ 2 , ∀x ∈ Rd , (6)
second-moment estimates (vt ) maintained by Adam and ZO-Adam in synthetic experiments, where we minimize a quadratic function across increasing dimensions. Experimental details are deferred to Appendix C. Figure 2 confirms that in small dimension, Adam and ZO-Adam maintain a similar second moment vector vt across training. As the dimension increases, Adam shows coordinate-wise variability, but all ZO-Adam’s second moment coordinates collapse to 2 a single value: ∥∇f (xt )∥ /q. This corroborates Proposition 3.1. We show similar narrowing of the ZO-Adam’s vt distribution in the case of LLM finetuning in Appendix E.1.
Assumption 4.3 (Bounded Gradients). There exists G > 0 such that with probability 1, 2
∥∇f (x; ξ)∥ ≤ G,
4. MEAZO Design Intuition. MEAZO (Algorithm 1) is inspired by adaptive methods like Adam but tailored for the ZO setting. In standard Adam, per-parameter first and second moments enable fine-grained adaptivity. However, as demonstrated in Sec. 3, perturbations are isotropic and directions change every iteration, making per-parameter statistics ineffective and wasting memory. Instead, MEAZO maintains a single global statistic of the squared averaged projected gradient norm:
Since the ZO gradient is an unbiased estimator of a smoothed version of the original objective (Flaxman et al., 2004; Nesterov & Spokoiny, 2017), our convergence analysis for MEAZO proceeds in two steps. First, we establish a general result for affine variance-bounded adaptive SGD (Theorem 4.4). Next, using Theorem 4.6, we lift this guarantee to the original objective, culminating in our main result for MEAZO (Algorithm 1) stated in Theorem 4.7.
q
gt =
(7)
Assumptions 4.1 and 4.2 are standard in analyzing the convergence of non-convex first-order SGD (Ward et al., 2020; Ghadimi & Lan, 2013). Although Assumption 4.3 is somewhat restrictive, since it excludes strongly convex functions, it remains common in the study of adaptive methods (Chen et al., 2019; Ward et al., 2020; Zaheer et al., 2018). Similar to prior work on ZO optimization (Shu et al., 2025), we develop formal guarantees for MEAZO (Algorithm 1) for the ZO estimator (2) with uniformly sampled perturbations over the unit sphere: u ∼ Uniform(S) where S := {a ∈ Rd : ∥a∥ = 1}. This restriction is without loss of generality: empirically (Appendix E.8) we observe that the choice of perturbation distribution does not impact model performance, and extending the analysis to Gaussian perturbations is straightforward.
Collectively, these findings suggest that coordinate-wise adaptive optimizers are wasteful in large-scale ZO finetuning contexts. Simpler methods like ZO-SGD not only reduce computational overhead, but also deliver superior or matching performance when tuned.
vt ≈ EMA gt2 ,
∀x ∈ Rd ,
1X ∆fε (xt ; ui ). q i=1 4
On Adaptivity in Zeroth-Order Optimization
Adaptive SGD with Affine Variance Bound. Consider this generic result on affine variance-bounded SGD with an adaptive step size:
However, their motivation is fundamentally different from ours. These works employ the affine-variance assumption because they aim to derive guarantees for AdaGrad-Norm under the least restrictive possible conditions (without assuming bounded gradients or bounded variance). In contrast, our EMA-based method requires the affine-variance assumption solely because zero-order (ZO) gradient estimators inherently produce it: even under standard variance-bounded noise, ZO gradients introduce an extra gradient-dependent term, yielding an affine-variance structure. Thus, this assumption is not a modeling choice but an unavoidable consequence of using ZO gradients.
Theorem 4.4 (Adaptive SGD with Affine Variance Bound). Let F : Rd → R be the population loss F (x) = Eξ∼D [f (x; ξ)] , where each sample loss f (x; ξ) is L-smooth and GLipschitz (equivalently, ∥∇f (x; ξ)∥ ≤ G for all x, ξ). Assume F is bounded from below by F ∗ , i.e., F ∗ = inf x F (x) > −∞. Suppose we have an unbiased stochastic gradient estimator g(x; ξ), i.e., Eξ∼D [g(x; ξ)] = ∇F (x), satisfying the affine variance bound h i 2 2 Eξ∼D ∥g(x; ξ) − ∇F (x)∥ ≤ σ02 + σ12 ∥∇F (x)∥ .
Smoothed Proxy Optimization. We now state this result on smoothed proxy optimization: Theorem 4.6 (Smoothed Proxy Optimization). Let F : Rd → R be an L-smooth function. For a centered smooth3 ing distribution h i P with bounded support and satisfying 2 Eu∼P ∥u∥ = C < ∞, define the smoothed objective:
Consider the adaptive SGD update xt+1 = xt − √
η g(xt ; ξt ), vt + ζ
Fε (x) = Eu∼P [F (x + εu)] ,
with stepsize η > 0, stability constant ζ > 0, and secondmoment tracker vt = β vt−1 + (1 − β) γt2 ,
where ε > 0 is the smoothing parameter. Assume the optimal values F ∗ = inf F (x),
0 < β < 1,
x∈Rd
where {γt }t≥0 is predictable (measurable w.r.t. the filtration generated by {xt , ξt }), satisfies 0 ≤ γt ≤ G, and obeys the condition 2
Eξt ∼D [γt nt | xt ] ≤ σ02 + (σ12 + 1) ∥∇F (xt )∥ ,
T −1 i 1 X h 2 E ∥∇Fε (xt )∥ ≤ K0 Fε (x0 ) − Fε∗ + K1 (10) T t=0
(8)
for some constants K0 , K1 ≥ 0. Then, for the original function F , it holds that T −1 i 1 X h 2 E ∥∇F (xt )∥ ≤ K0 F (x0 ) − F ∗ + K1 T t=0 + ε2 L2 C K20 + 2 . (11)
Then, after T iterations, T −1 i F (x0 ) − F ∗ σ2 1 X h 2 +α 0, E ∥∇F (xt )∥ ≤ 2α T t=0 ηT ζ
√
x∈Rd
are finite. Suppose an algorithm A generates iterates −1 {xt }Tt=0 such that
where nt := ∥g(xt ; ξt )∥ is the stochastic gradient norm. Assume the parameters (β, η, ζ) are chosen so that √ G(1 + σ12 ) 1 − β L η 1 max , (9) ≤ . ζ 2ζ 4
where α =
Fε∗ = inf Fε (x)
The proof of Theorem 4.6 is provided in Appendix H.3. Despite its simplicity, Theorem 4.6 is remarkably powerful: it enables us to transfer guarantees established for the smoothed proxy back to the original function, provided F is L-smooth and the smoothing distribution is well-behaved. As expected, in the ε → 0 limit, the guarantee on the smoothed proxy and the original function are identical.
βG + ζ.
Notice that the step size is normalized by an EMA of a scalar quantity γt satisfying condition (8). One way to understand why this condition is reasonable is to restrict γt to be the norm nt ; under this choice, the condition follows directly from the affine variance bound. The proof of Theorem 4.4 is provided in Appendix H.4. Remark 4.5. Affine-variance bounded adaptive SGD has been previously studied in (Faw et al., 2022; Attia & Koren, 2023) in the context of AdaGrad-Norm (Ward et al., 2020).
MEAZO. We can now state the main result: Theorem 4.7 (MEAZO). Under Assumptions 4.1, 4.2, and 3
5
Needed to apply Leibniz’s rule.
On Adaptivity in Zeroth-Order Optimization
of size O dq σ 2 around a stationary point. Unlike the previous noise term, the latter can be reduced by increasing the number of samples q. To get a convergence in O Td for the third ZO gradient estimation term, we require setting the perturbationmagni tude to a small value often proportional to ε = O √1dT , as also observed for ZO-AdaMM under non-convex assumptions (Chen et al., 2019).
4.3, define dε2 L2 σ02 = (8 + d) + 2q 4d − 1 . σ12 = q
2d − 1 + 1 σ2 , q
If the parameters β, η, ζ satisfy √ G(1 + σ12 ) 1 − β Lη 1 max , ≤ , ζ 2ζ 4
(12)
4.2. Grouped MEAZO MEAZO naturally extends to the grouped ZO estimator in (3). In block ZO, each block j produces its own projected gradient: q 1X ∆fε x; mj ⊙ ui , gj = q i=1
then after T iterations of Algorithm 1 with u ∼ Uniform(S), we have T −1 i 1 X h F (x0 ) − F ∗ σ02 2 E ∥∇F (xt )∥ ≤ 2α + T t=0 ηT 2ζ α +2 , + ε2 L2 ηT √ where α = βG + ζ.
allowing us to maintain a scalar vj per block. The grouped MEAZO update becomes: ! p q X 1X 1 p ∆fε x; mj ⊙ ui (mj ⊙ ui ) , v̂j + ζ q i=1 j=1
We defer the full proof of Theorem 4.7 to Appendix H.5. The core idea is to verify that the conditions of Theorem 4.4 hold, and then invoke Theorem 4.6 to lift the guarantee to the original objective F . Remark 4.8. Following the same proof architecture, we present an alternative derivation for vanilla ZO-SGD in Appendix H.7, which recovers the standard SGD rate in the limit as q → ∞.
providing block-level adaptivity without incurring perparameter memory costs. Efficient Implementation. Following the decomposition strategy in (Zhang et al., 2024b), we treat each decoder block as a single optimization block. To exploit the sequential structure of the network, we apply perturbations beginning at the first block, ending at the last block. To avoid recomputing the base activation for block j during each perturbation, we cache the unperturbed activation and reuse it for all queries within that block. This reduces redundant computation, especially for q > 1, while preserving correctness. See Appendix F for details.
We now derive the convergence rate we obtained and relate it to previous works. Its proof is deferred to Appendix H.6. Corollary 4.9 (MEAZO Convergence Rate). If the assumptions and conditions in Theorem 4.7 hold, then after T iterations of Algorithm 1 with u ∼ Uniform(S), the iterates satisfy F (x0 ) − F ∗ d d2 O + σ 2 + σ 2 + ε2 , (13) ηT q q
5. Experimental Results 5.1. Synthetic Problems Setup. We first consider two synthetic quadratic problems F (x) = 21 x⊤ Hx used in section D of (Orvieto & Gower, 2025). The Hessian H ∈ R9×9 has a 3 × 3 diagonal block structure. In the heterogeneous setting, the blocks have eigenvalues of different magnitudes, whereas in the homogeneous one, they share a similar spectrum. We minimize these functions with ZO-SGD, ZO-Adam and MEAZO4 in a Gradient Descent (GD) or a Block-Coordinate Gradient Descent (BCGD) (Tseng & Yun, 2009) manner.
where the O(·) notation hides constants independent of d, q, T, and σ 2 , and non-dominant terms in ε2 . We observe that the first term correspond to the standard convergence rate of FO Adam to a small neighborhood of size O σ 2 around a stationary point, proved in (Zaheer et al., 2018), which is often sufficient for large-scale machine learning problems in line with the risk-computation tradeoff emphasized by (Bottou, 2010). As defined in Assumption 4.2, the constant O σ 2 is inherent to the stochasticity of the gradients, which are themselves estimated with ZO gradients. Thus the second term implies a convergence of MEAZO to a small neighborhood
Results. As observed in recent works (Zhang et al., 2024a; Orvieto & Gower, 2025), adaptive optimizers like Adam 4 With abuse of notation as we use the true gradients on the full synthetic dataset.
6
On Adaptivity in Zeroth-Order Optimization Table 1. Evaluation metrics before and after 16-rank LoRA fine-tuning (L: Llama-3.2, Q: Qwen-3). Results are averaged over 3 seeds.
Method
L1B
XSum (ROUGE-L) Q0.6B
Q8B
L1B
SST-2 (Accuracy) Q0.6B
Q8B
L1B
SQuAD (F1) Q0.6B
Base
13.62
15.09
18.60
49.08
50.69
93.00
24.63
31.76
31.50
21.99±0.07 22.36±0.07 22.39±0.17 22.39±0.19
20.08±0.12 20.08±0.09 20.12±0.05 20.08±0.04
26.96±0.28 27.45±0.10 27.34±0.19 27.31±0.27
87.96±0.95 88.88±0.43 88.42±0.80 88.38±1.13
87.19±1.09 87.27±0.50 87.31±0.38 87.04±1.50
93.73±0.46 93.46±0.52 93.69±0.61 93.39±0.52
76.16±0.40 76.24±0.43 74.54±0.98 75.77±0.41
69.30±0.84 68.91±0.83 69.50±0.56 68.72±0.33
82.69±0.26 83.16±0.18 82.88±0.21 82.94±0.87
ZO-SGD ZO-Adam RAdaZO MEAZO
Table 2. Evaluation metrics before and after 20-token prompt tuning (L: Llama-3.2, Q: Qwen-3). Results are averaged over 3 seeds.
Function Value
Convergence Block ZO-SGD (lr=1.0e-04) Block ZO-Adam (lr=1.0e-01) Block MEAZO (lr=1.0e-01)
104 102
Method
100 10
Base ZO-SGD ZO-Adam RAdaZO MEAZO
−2
0
20000
40000
60000
Q8B
80000
XSum (ROUGE-L) L1B Q0.6B
SST-2 (Accuracy) L1B Q0.6B
SQuAD (F1) L1B Q0.6B
13.62
15.09
49.08
50.69
24.63
31.76
17.56±0.22 17.14±0.19 16.90±0.39 16.85±0.33
16.00±0.19 15.62±0.33 13.25±0.96 15.72±0.30
84.90±1.42 83.60±2.64 84.06±0.80 82.57±2.30
73.05±6.34 72.44±5.25 69.19±1.61 67.35±5.35
49.98±0.46 48.87±0.52 49.75±0.29 47.78±1.15
52.44±0.83 54.28±2.58 43.30±2.96 56.46±1.09
Iteration
Adam (Chen et al., 2019), and R-AdaZO (Shu et al., 2025), where R-AdaZO improves ZO-Adam stability by updating the second moment using the first moment rather than the raw gradient estimate. Full experimental details are provided in Appendix D. Additional results, including comparisons on OPT (Zhang et al., 2022b) with FZOO (Dang et al., 2025), ViT-B/16 (Wu et al., 2020) experiments on the Oxford Pets dataset, and further evaluations on Ministral 14B (Liu et al., 2026), are reported in Appendix E.
Final Loss
Step Size Robustness 1028 1019 1010 101
10−4
10−2
100
102
104
Normalized Step Size ( * ) η
ZO-SGD vs Adaptive Optimizers. We evaluate two PEFT approaches, prompt tuning and LoRA (Tables 12). In prompt-tuning, ZO-Adam shows a slight advantage in most tasks, consistent with a higher gradient heterogeneity in small parameter spaces (Prop. 3.1). Moving to the higher-dimensional LoRA setup: a well-tuned ZO-SGD matches or surpasses adaptive ZO methods, while our MEAZO performs on par with ZO-Adam, better visualized in Fig. 46 . These results show that per-coordinate adaptivity provides limited benefit in high-dimensional ZO training. We defer additional training and validation loss curves for all methods to Appendix E.3.
η
Figure 3. The performance of BCGD-ZO methods on heterogeneous block quadratics under convergence analysis (top) and step size robustness evaluation (bottom).
tend to perform better than SGD in the presence of a heterogeneous loss landscape. We confirm this behavior in the low-dimensional ZO setting, as visualized in Fig. 3 (top). Furthermore, we observe (Fig. 3 (bottom)) an increased robustness of ZO adaptive methods w.r.t. step size, something we study in further detail in section 5.2. Details and the homogeneous case are deferred to Appendix C.
Setup. We fine tune two model families, Llama 3 (Grattafiori et al., 2024) and Qwen 3 (Yang et al., 2025), across diverse datasets including SST-2, XSum, and SQuAD. We compare MEAZO against ZO-SGD (MeZO)5 , ZO-
Robustness. An often underexplored aspect of ZO optimization is robustness, particularly in the q = 1 regime. We revisit this question for LLM fine-tuning using ZO-SGD, ZO-Adam, and MEAZO on SQuAD. For all methods, we perform a fine-grained step size sweep (Appendix E.2), identify the best-performing step size η ∗ across seeds, and plot the best (left) and last (right) validation losses against the normalized step size (Fig. 5). The results show that adap-
5 MeZO (Malladi et al., 2023) is a memory efficient implementation of ZO-SGD.
6 Best performing runs based on lowest validation loss during training, assuming early stopping.
5.2. LLM Fine-tuning
7
On Adaptivity in Zeroth-Order Optimization ZO-SGD
SST-2
SQuAD
5.0
7.5
7.5
4.0
5.0
5.0
3.0
2.5
2.5
2.0
0.0
0.0
6.0
7.5
7.5
4.0
5.0
5.0
2.5
2.5
0.0
0.0
2.0
1.5
1.0
1.0
0.5
2.0
L1B
2.5
Q8B
Val. Loss
MEAZO
Q0.6B
Val. Loss
XSum
Val. Loss
-AdaZO
ZO-Adam
0.5 0.0 0
2500
5000
7500
10000
0
2500
Steps
5000
Steps
7500
10000
0
2500
5000
7500
10000
Steps
Figure 4. Performance comparison of zeroth-order methods for LoRA fine-tuning across models (L: Llama-3.2, Q: Qwen-3) and tasks using the best step size for each method (see Appendix E.2). Curves show averages over three seeds with shaded ±2 standard deviations.
tivity (ZO-Adam and MEAZO) substantially strengthens robustness by widening the stable learning-rate window and reducing performance degradation at suboptimal η, particularly for larger step sizes. While a well-tuned ZO-SGD can match or exceed adaptive methods, it remains comparatively brittle. MEAZO is consistently as robust as ZOAdam in both settings, while reducing memory. Similar trends are observed on SST-2 and XSum and are deferred to Appendix E.4.
step sizes, we analyze the evolution of the MEAZO scalar vt in Fig. 6 (bottom). In the grouped setting, MEAZO adapts to group-specific statistics and exhibits a clear and stable ordering of vt across group indices throughout training. Groups corresponding to earlier layers maintain larger vt values, leading to more conservative effective steps in regions where perturbations have stronger influence on the loss, while later-layer groups converge to smaller vt values that permit relatively larger steps. This behavior is consistent with prior observations that perturbations in earlier layers tend to exert greater influence on model behavior (Sakr & Shanbhag, 2018; Zhang et al., 2022a). Importantly, the overall temporal trajectory of vt remains similar across groups, indicating that the underlying optimization dynamics are preserved even as MEAZO adapts to heterogeneous parameter sensitivities.
Grouped ZO. Figure 6 presents our primary analysis of grouped (block) zeroth-order updates from (3) on adaptivity and stability, using Llama-3.2 1B fine-tuned on SQuAD as a representative setting. Results on additional models and datasets are deferred to Appendix E.5. We first examine the effect of grouping on optimization behavior. Grouping is a known variance reduction technique, and consistent with this intuition, the grouped variants converge faster in terms of number of steps than their non-grouped counterparts, as shown in Fig. 6 (top). This improvement does not translate to better raw FLOP efficiency, since grouped updates incur higher computational cost. Nevertheless, grouping reveals an important stability effect. Despite being a variance reduction method, grouped ZO-SGD can be brittle, particularly toward the end of training, where some random seeds numerically diverge. This instability is more clearly reflected in the step-size robustness curves, which we report in Appendix E.5.
6. Discussion and Future Work Please find a discussion of relevant related work in Appendix B. Our results show that well-tuned ZO-SGD can match or outperform adaptive methods like ZO-Adam, due to the lack of coordinate-wise structure in ZO gradients in high dimensions, which limits the utility of adaptivity. We also show that ZO-SGD is less robust to the choice of step size, where adaptive methods have an advantage. We believe this robustness is particularly valuable for edge-device personalization, where memory is limited, ZO fine-tuning can be executed using built-in inference engines, and data
Using the same experiments and their respective optimal 8
On Adaptivity in Zeroth-Order Optimization ZO-SGD
ZO-Adam
Convergence
MEAZO
ZO-SGD ZO-Adam MEAZO
1.5
Last
Val. Loss
Best
Q0.6B
Val. Loss
1.4 1.0 0.5
1.0 0.5
0.1
MEAZO Scalar vt G0 G1 G2 G3 G4 G5 G6 G7 G8
0.8 0.8 0.4
Value
Q8B
Val. Loss
1.2
0.6 0.4 0.2
0.0
G9 G10 G11 G12 G13 G14 G15 Global x 0.1
0.0
1.0
0
0.7 0.4
100
101
10−1
η
Norm. Step Size ( * )
Norm. Step Size ( * ) η
100
4000
6000
8000
10000
Figure 6. Convergence behavior of various optimizers (top) and evolution of the MEAZO scalar vt (bottom) during Llama-3.2 1B fine-tuning on SQuAD under grouped and non-grouped settings. For visualization clarity, the non-grouped vt is renormalized.
0.1 10−1
2000
Steps
L1B
Val. Loss
ZO-SGD-G ZO-Adam-G MEAZO-G
101 η
η
References
Figure 5. Robustness of ZO-SGD, ZO-Adam, and MEAZO to step size (η) initialization across models fine-tuned on SQuAD.
Attia, A. and Koren, T. Sgd with adagrad stepsizes: Full adaptivity with high probability to unknown parameters, unbounded gradients and affine variance. In International Conference on Machine Learning, pp. 1147–1171. PMLR, 2023. Berahas, A. S., Cao, L., Choromanski, K., and Scheinberg, K. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22(2):507–560, 2022.
heterogeneity across devices leads to differing optimal step sizes. Motivated by this, we introduce MEAZO, a scalar adaptive ZO method that achieves ZO-Adam-level performance with the memory efficiency of ZO-SGD and show its robustness across step sizes. Future directions include refining our convergence results to 0 rather than to a noisedominated neighborhood of a stationary point. We also consider extending MEAZO to subspace ZO frameworks to leverage adaptation (sparsity, block-coordinate descent, lowrank perturbations) (Park et al., 2025), as well as full-model fine-tuning, where the low-memory property of MEAZO is most pronounced.
Bottou, L. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT’2010: 19th International Conference on Computational StatisticsParis France, August 22-27, 2010 Keynote, Invited and Contributed Papers, pp. 177–186. Springer, 2010. Chen, X., Liu, S., Xu, K., Li, X., Lin, X., Hong, M., and Cox, D. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. Advances in neural information processing systems, 32, 2019.
Impact Statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, only one of which bears relevance here: ZO optimization specifically targets low-memory training environments and therefore opens an avenue for more researchers and practitioners with access to limited resources to participate in fine-tuning models.
Dang, S., Guo, Y., Zhao, Y., Ye, H., Zheng, X., Dai, G., and Tsang, I. Fzoo: Fast zeroth-order optimizer for finetuning large language models towards adam-scale speed. arXiv preprint arXiv:2506.09034, 2025. Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkottai, S., and Ward, R. The power of adaptivity in sgd: Self9
On Adaptivity in Zeroth-Order Optimization
tuning step sizes with unbounded gradients and affine variance. In Conference on Learning Theory, pp. 313– 355. PMLR, 2022.
with just forward passes. Advances in Neural Information Processing Systems, 36:53038–53075, 2023. Narayan, S., Cohen, S. B., and Lapata, M. Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization. ArXiv, abs/1808.08745, 2018.
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Nazari, P., Tarzanagh, D. A., and Michailidis, G. Adaptive first-and zeroth-order methods for weakly convex stochastic optimization problems. arXiv preprint arXiv:2005.09261, 2020.
Gao, G., Taymanov, A., Salinas, E., Mineiro, P., and Misra, D. Aligning llm agents by learning latent preference from user edits. Advances in Neural Information Processing Systems, 37:136873–136896, 2024.
Nesterov, Y. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Gao, X., Jiang, B., and Zhang, S. On the informationadaptive variants of the admm: an iteration complexity perspective. Journal of Scientific Computing, 76(1):327– 363, 2018.
Nesterov, Y. and Spokoiny, V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341–2368, 2013.
Orvieto, A. and Gower, R. In search of adam’s secret sauce. arXiv preprint arXiv:2505.21829, 2025.
Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A. et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Pan, Y. and Li, Y. Toward understanding why adam converges faster than sgd for transformers. arXiv preprint arXiv:2306.00204, 2023.
Gururangan, S., Marasović, A., Swayamdipta, S., Lo, K., Beltagy, I., Downey, D., and Smith, N. A. Don’t stop pretraining: Adapt language models to domains and tasks. arXiv preprint arXiv:2004.10964, 2020.
Park, S., Yun, J., Kim, S., Kundu, S., and Yang, E. Elucidating subspace perturbation in zeroth-order optimization: Theory and practice at scale. arXiv preprint arXiv:2501.19099, 2025.
Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., Chen, W., et al. LoRA: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
Parkhi, O. M., Vedaldi, A., Zisserman, A., and Jawahar, C. Cats and dogs. In 2012 IEEE conference on computer vision and pattern recognition, pp. 3498–3505. IEEE, 2012.
Jiang, S., Chen, Q., Pan, Y., Xiang, Y., Lin, Y., Wu, X., Liu, C., and Song, X. Zo-adamu optimizer: Adapting perturbation by the momentum and uncertainty in zeroth-order optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38 (16), pp. 18363–18371, 2024.
Rajpurkar, P., Zhang, J., Lopyrev, K., and Liang, P. SQuAD: 100,000+ questions for machine comprehension of text. In Su, J., Duh, K., and Carreras, X. (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383–2392, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/v1/D16-1264. URL https: //aclanthology.org/D16-1264.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. Lester, B., Al-Rfou, R., and Constant, N. The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691, 2021.
Sakr, C. and Shanbhag, N. An analytical method to determine minimum per-layer precision of deep neural networks. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1090– 1094. IEEE, 2018.
Liu, A. H., Khandelwal, K., Subramanian, S., Jouault, V., Rastogi, A., Sadé, A., Jeffares, A., Jiang, A., Cahill, A., Gavaudan, A. et al. Ministral 3. arXiv preprint arXiv:2601.08584, 2026.
Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2):107–194, 2011.
Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, J. D., Chen, D., and Arora, S. Fine-tuning language models 10
On Adaptivity in Zeroth-Order Optimization
Shu, Y., Zhang, Q., He, K., and Dai, Z. Refining adaptive zeroth-order optimization at ease. arXiv preprint arXiv:2502.01014, 2025. Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C. D., Ng, A., and Potts, C. 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 Computational Linguistics. URL https: //www.aclweb.org/anthology/D13-1170. Tomihari, A. and Sato, I. Understanding why adam outperforms sgd: Gradient heterogeneity in transformers. arXiv preprint arXiv:2502.00213, 2025. Tseng, P. and Yun, S. A coordinate gradient descent method for nonsmooth separable minimization. Mathematical Programming, 117(1):387–423, 2009. Ward, R., Wu, X., and Bottou, L. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219):1–30, 2020. Wu, B., Xu, C., Dai, X., Wan, A., Zhang, P., Yan, Z., Tomizuka, M., Gonzalez, J., Keutzer, K., and Vajda, P. Visual transformers: Token-based image representation and processing for computer vision. arXiv preprint arXiv:2006.03677, 2020. Yang, A., Li, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Gao, C., Huang, C., Lv, C. et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. Zaheer, M., Reddi, S., Sachan, D., Kale, S., and Kumar, S. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018. Zhang, C., Bengio, S., and Singer, Y. Are all layers created equal? Journal of Machine Learning Research, 23(67): 1–28, 2022a. Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V. et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022b. Zhang, Y., Chen, C., Ding, T., Li, Z., Sun, R., and Luo, Z. Why transformers need adam: A hessian perspective. Advances in neural information processing systems, 37: 131786–131823, 2024a. Zhang, Y., Li, P., Hong, J., Li, J., Zhang, Y., Zheng, W., Chen, P.-Y., Lee, J. D., Yin, W., Hong, M. et al. Revisiting zeroth-order optimization for memory-efficient llm finetuning: A benchmark. In International Conference on Machine Learning, pp. 59173–59190. PMLR, 2024b. 11
On Adaptivity in Zeroth-Order Optimization
A. Contributions Hassan Dbouk∗ Conceptualization; theory (formalism and mathematical proofs); devised the MEAZO algorithm; software; experimental design, execution, and management (LLM non-grouped and grouped settings, ViT); visualization (figures and tables); article writing; research discussions. Nidham Gazagnadou∗ Conceptualization; theory (formalism and mathematical proofs); bibliographic research on zeroth-order optimization; software; experimental design, execution, and management (LLM prompt-tuning, Qwen3-8B, synthetic experiments); article writing; research discussions. Matthias Reisser∗ Conceptualization; core software design (optimizers, grouping); experimental design, execution, and management (LLM non-grouped and grouped settings, Ministral); article writing; research discussions. Christos Louizos Conceptualization; supervision; theoretical guidance (including connections to Adam convergence); feedback on experimental design and manuscript; article writing; research discussions.
B. Related Work B.1. Zeroth-Order Gradient Estimation Theoretical foundations of ZO optimization were established in early works such as (Ghadimi & Lan, 2013) and (Nesterov & Spokoiny, 2017), which analyzed convergence properties of ZO-SGD using Gaussian perturbations, or the convergence in the online setting with perturbations sampled uniformly from the unit sphere (Flaxman et al., 2004). Recently, MeZO (Malladi et al., 2023) introduced a memory-efficient variant of ZO-SGD by storing scalar seeds instead of sampled perturbations, significantly reducing memory usage. Comprehensive benchmarking of ZO methods has been conducted by (Zhang et al., 2024b) to evaluate their empirical performance across tasks, highlighting trade-offs between estimator variance, convergence speed, and memory efficiency. B.2. Adaptive Zeroth-Order Methods To enhance convergence and robustness, adaptive ZO algorithms have incorporated techniques inspired by first-order optimization. ZO-AdaMM (Chen et al., 2019) and ZEMA (Nazari et al., 2020) introduced adaptive step sizes based on first and second moment estimates of the gradient approximation. However, these methods did not demonstrate theoretical convergence improvements over ZO-SGD in convex and non-convex constrained settings. Recent advances have focused on refining the use of momentum and variance reduction. ZO-AdaMU (Jiang et al., 2024) introduced adaptive momentum for perturbations, smoothing both gradient estimates and parameter updates. FZOO (Dang et al., 2025) jointly improved ZO gradient estimation, by combining Rademacher perturbations, and step size adaptation, using the standard deviation of the batch losses. R-AdaZO (Shu et al., 2025) leveraged variance-reduced gradient information embedded in the momentum to refine second moment estimates, leading to improved convergence on synthetic data.
C. Synthetic Quadratic Experimental Setup C.1. Second moment monitoring with increasing dimension ⊤ Objective functions. The experiment uses a block-structured quadratic function √ f (x) = 0.5x √Hx, where H is a blockdiagonal Hessian matrix. For a dimension d, the Hessian is constructed from d blocks of size d each. We consider the heterogeneous configuration: each block contains consecutive eigenvalues centered around exponentially increasing values (logarithmically spaced from 1 to 1000). For more details, we refer to Appendix D of (Orvieto & Gower, 2025) for the case of d = 9 that we use below and extend here for larger dimensions. This creates blocks with different curvature, which helps to visualize second moment coordinate-wise variability of Adam. This structure mimics real optimization landscapes where different parameter groups have different sensitivities.
Experiment. We track the evolution of the second moment vt (vector or scalar value for MEAZO) across 3 optimizers: FO-Adam, ZO-Adam and MEAZO. We run the experiment for 5 different problem dimensions: 9, 25, 49, 100 and 1024. All 12
On Adaptivity in Zeroth-Order Optimization
ZO-GD (Homogeneous) 104
ZO-SGD (η * =5.0e-05)
Function Value
103 10
ZO-BCGD (Homogeneous) ZO-SGD (η * =1.0e-04)
ZO-Adam (η * =5.0e-04)
10
ZO-Adam (η * =1.0e-03)
3
MEAZO (η * =5.0e-04)
2
MEAZO (η * =1.0e-03)
Threshold=0.001
101
Threshold=0.001
101
100 10−1
10−1 10−2
10−3
10−3
ZO-GD (Heterogeneous)
Function Value
104 10
ZO-BCGD (Heterogeneous)
ZO-SGD (η * =5.0e-05)
ZO-SGD (η * =1.0e-04)
104
ZO-Adam (η * =5.0e-04)
3
ZO-Adam (η * =1.0e-01)
MEAZO (η * =5.0e-04)
102
MEAZO (η * =1.0e-01)
Threshold=0.001
Threshold=0.001
102
101 100
100
10−1 10−2
10−2
10−3 0
25000
50000
75000
100000
Iteration
0
25000
50000
75000
100000
Iteration
Figure 7. Convergence of ZO methods on block homogeneous (top) vs heterogeneous (bottom) quadratics.
optimizers use the same learning rate 1e−4 until convergence to the same threshold 1e−3 with 10 noise samples for the ZO 2 methods. For ZO-Adam, we also monitor ∥∇f (xt )∥ /q at iteration t. C.2. Homogeneous vs Heterogeneous low-dimensional setting We exactly reproduce the problem of appendix D of (Orvieto & Gower, 2025). The only difference being that we do not introduce random batch samples stochasticity by sampling rows of the design matrix. Thus, the only source of randomness lies in the zeroth-order gradients approximation. To find the best step size for each run, we perform step size tuning over the grid {1e−6, 5e−6 . . . , 1e−1, 5e−1}, with 10 different seeds. For each of the displayed run, we display the average run over the 10 seeds along with a plus/minus standard deviation envelope (in log space). Curves are smoothed over a window of 10 step for better display of ZO-Adam and MEAZO. On the one hand, in the homogeneous case in Figure 7 (top), one can notice the similar performance of all three optimizers. On the other hand, Figure 7 (bottom) highlights the acceleration of the optimization with MEAZO, resp. ZO-Adam, when rescaling the step size per block, resp. per parameter within a block, in the presence of landscape heterogeneity. In Figure 8, we show the better robustness around the optimal step size of ZO adaptive methods, i.e., ZO-Adam and MEAZO, compared to ZO-SGD. In the heterogeneous setting, this robustness of ZO adaptive methods is even amplified by applying block-coordinate updates, as shown by way flatter curves for ZO-Adam and MEAZO in Figure 8 (bottom right) compared to Figure 8 (bottom left), than for ZO-SGD. 13
On Adaptivity in Zeroth-Order Optimization
ZO-GD (Homogeneous) 1031
Threshold=0.001 ZO-Adam (η * =5.0e-04)
MEAZO (η * =1.0e-03)
1012
107
106
101
100 10−3
10−2
10−1
100
101
102
103
104
10−3
ZO-GD (Heterogeneous) 1036
ZO-SGD (η * =5.0e-05) ZO-Adam (η * =5.0e-04)
24
10−2
10−1
100
101
102
103
104
ZO-BCGD (Heterogeneous)
Threshold=0.001
1030
Final Loss
ZO-Adam (η * =1.0e-03)
1018
1013
10
ZO-SGD (η * =1.0e-04)
1024
MEAZO (η * =5.0e-04)
1019
Threshold=0.001
1030
ZO-SGD (η * =5.0e-05)
1025
Final Loss
ZO-BCGD (Homogeneous) 1036
MEAZO (η * =5.0e-04)
1018
10
34
10
27
10
20
Threshold=0.001 ZO-SGD (η * =1.0e-04) ZO-Adam (η * =1.0e-01) MEAZO (η * =1.0e-01)
1013
1012
106
106
10−1
100 10−3
10−2
10−1
100
101
102
103
104
10−4
Norm. Step Size (η/η * )
10−2
100
102
104
Norm. Step Size (η/η * )
Figure 8. Step size robustness of ZO methods on block homogeneous (top) vs heterogeneous (bottom) quadratics.
D. LLM Fine-tuning Experimental Setup D.1. Training Details Unless stated otherwise, all models are trained for T = 10 000 steps with a batch size of 8 on single NVIDIA A100/H100 GPUs equipped with 80GB of memory. We employ a constant step size schedule throughout training, without applying weight decay or gradient norm clipping. For adaptive optimization methods, we use the default hyperparameters: β1 = 0.9 and β2 = 0.999. For zeroth-order (ZO) optimization methods, we adopt a fixed perturbation scale of ε = 1e−6 and use a single noise sample per mini-batch (q = 1). To ensure a fair comparison across optimization methods, we conduct extensive step size sweeps to identify the optimal initial step size for each optimizer, detailed in Appendix E.2. D.2. Classification Training Loss Zhang et al. (2024b) formulate classification for LLM fine-tuning using a multiclass contrastive objective: for each input, the model is paired with every verbalized label, computes an average log-probability score over the label tokens, and these scores are used as logits in a softmax cross-entropy loss. This explicitly contrasts the true label against all incorrect ones but requires evaluating C candidate sequences during training. In our setup, we instead treat classification (SST-2) as straightforward causal language modeling (CLM). During training, we provide only the ground-truth continuation (the correct verbalized label) and maximize its next-token likelihood (no negative labels and no classification loss). However, at evaluation time, we adopt the same procedure: for each class, we compute the same average log-probability score for its verbalized label and select the label with the highest score. Despite the simpler training objective, we find minimal degradation in final model performance. 14
On Adaptivity in Zeroth-Order Optimization Table 3. Summary of training configurations. For all experiments, LoRA uses rank r = 16. Prompt tuning uses 20 learned input tokens.
Method
Llama-3.2 1B
Qwen-3 0.6B
Qwen-3 8B
Ministral-3 14B
ViT-B/16
Base model #Total parameters
1 235 814 400
596 049 920
8 190 735 360
13 945 031 680
85 827 109
LoRA #Trainable parameters %Trainable parameters
1 703 936 0.1377%
2 293 760 0.3834%
7 667 712 0.0935%
11 403 264 0.0817%
618 277 0.7152%
Prompt tuning #Trainable parameters %Trainable parameters
40 960 0.0033%
20 480 0.0034%
– –
– –
– –
D.3. Models We download all pre-trained models from HuggingFace and load them in full precision (FP32) except for Ministral 14B loaded in BF16. For language tasks we consider Llama-3.2 1B (Grattafiori et al., 2024), Qwen-3 0.6B and 8B (Yang et al., 2025) and Ministral-3 14B Instruct (Liu et al., 2026). For the vision task, we finetune ViT-B/16 (Wu et al., 2020). The training configurations detailed below are summarized in Table 3. LoRA fine-tuning. For LoRA fine-tuning (Hu et al., 2022), we use a rank of r = 16, set the scaling factor to α = 16, and disable dropout. LoRA layers are attached to all query (Q) and value (V) projection matrices within each transformer decoder block. Our implementation is based on Hugging Face PEFT’s library7 . Prompt tuning. For prompt tuning (Lester et al., 2021), we append 20 trainable tokens to the input in embedding space and train for T = 20000 steps. We also rely on Hugging Face PEFT’s library. We initialize all our prompt’s embeddings with the following task-specific initialization prompt: • SST2: ”Sentiment task: classify text as positive or negative. Output only positive or negative.” • SQuAD: ”Extract answer from passage only using exact text span answering the question precisely and concisely.” • XSum: ”Summarize the article into one concise sentence capturing the main event, key facts, and essential context clearly.” D.4. Dataset Pre-processing For all datasets, we utilize their publicly available implementations from HuggingFace. For each model, we format every data point using its corresponding tokenizer’s chat template. SST-2. The SST-2 dataset (Socher et al., 2013) is pre-divided into training, validation, and test splits. However, since the original test set lacks labels, we reassign the original validation set as our test set. To construct a new validation set, we split the original training data (comprising 67 349 samples) into training and validation subsets using a 95/5 ratio. The chat template employed for training is illustrated in Box 1. For evaluation, we compute the accuracy on the full test set. XSum. The XSum (Narayan et al., 2018) dataset retains its original training, validation, and test splits. Prior to training, we filter out samples that exceed the predefined context length (e.g., 2048 tokens) after tokenization. This filtering process is tokenizer-dependent; using the Llama 3.2 tokenizer, we exclude 1,202 samples across all splits. We then select the first 50,000 training samples and the first 1,000 validation samples.The chat template used for training is shown in Box 2. For evaluation, we compute the ROUGE-L score on the full test set. SQuAD. The SQuAD dataset (Rajpurkar et al., 2016) includes only training and validation splits. Following the approach used for SST-2, we reassign the validation split as the test set. The original training set contains 87 599 samples, which we divide into training and validation subsets using a 95/5 split. From these, we select the first 50 000 training samples and the 7
https://huggingface.co/docs/peft
15
On Adaptivity in Zeroth-Order Optimization
Box 1: SST-2 Chat Template System Prompt You are a sentiment analysis assistant. You will be given a user provided phrase or sentence, and your job will be to output terrible if it has negative sentiment or great if it has positive sentiment. User Query Sentence: <$sentence> Assistant Response Sentiment: <$sentiment>
Box 2: XSum Chat Template System Prompt You are a writing assistant that helps with summarizing text. You write concise, one-sentence summaries based on a user-provided text or article. User Query Article: <$article> Assistant Response Summary: <$summary>
16
On Adaptivity in Zeroth-Order Optimization
first 1000 validation samples. The chat template used for training is shown in Box 3. For evaluation, we compute the F-1 score on the full test set. Box 3: SQuAD Chat Template System Prompt You are a question answering assistant. You will be given a user-provided context (paragraph or sentence), followed by a question. Your job will be to answer the question based on the paragraph or sentence. User Query Title: <$title> Context: <$context> Question: <$question> Assistant Response Answer: <$answer>
Oxford-Pets. To extend our experiments to vision tasks, we use the Oxford-IIIT Pet dataset (Parkhi et al., 2012), which consists of 37 cat and dog breeds with roughly 200 images per class, and evaluate performance on the 37-way fine-grained classification task.
17
On Adaptivity in Zeroth-Order Optimization
E. Additional Experiments E.1. Coordinate-wise Variability of the Second Moment: FO- vs ZO-Adam We examine the second-moment estimates (vt ) maintained by Adam at the final LoRA finetuning step (t = 10000) of a Llama-3.2 1B model on the XSum dataset. Table 4 reports the minimum, maximum, mean, standard deviation, and kurtosis of vt across all parameters (d = 1’703’936). FO-Adam exhibits large variability and high kurtosis, reflecting meaningful per-coordinate differences that justify adaptive scaling. In contrast, ZO-Adam shows nearly uniform values with low variance and kurtosis, confirming that its adaptive mechanism is largely redundant when the gradient signal is isotropic. Table 4. Statistics of the second moment vt at t = 10000 for Llama-3.2 1B fine-tuning on XSum (seed 0).
Statistic
ZO-Adam
FO-Adam
Min. Max. Mean Stan. Dev. Kurtosis
1.39 2.60 1.87 1.11 × 10−1 2.36 × 10−1
6.68 × 10−19 3.08 × 10−4 1.02 × 10−6 4.05 × 10−6 3.23 × 102
E.2. Step Size Sweeps To properly ensure well-tuned methods, we perform extensive step-size sweeps conducted over two stages. Coarse grid. We first sweep the step size over a coarse grid: η ∈ {1e−6, 5e−6, . . . , 1e−1}, running each configuration across three random seeds. We then select the step size that achieves the lowest average validation loss. Fine grid. Let η ⋆ be the best step size from the coarse sweep and let η − , η + be its adjacent coarse neighbors (extending the coarse grid by one virtual neighbor at the boundary if needed). We then enumerate candidate step sizes with integer mantissas within the bracket(s) (η − , η ⋆ ) and (η ⋆ , η + ), i.e., values of the form η = m × 10k with m ∈ {1, . . . , 9} whose magnitude lies within the bracket. When a bracket crosses a decade boundary, we enumerate the remaining integer-mantissa values in the lower decade and the leading values in the upper decade. Tables 5-6 summarizes the best-performing step sizes for LoRA and prompt tuning, respectively. Table 5. Optimal step sizes for 16-rank LoRA fine-tuning (L: Llama-3.2, Q: Qwen-3).
Method
L1B
XSum Q0.6B
Q8B
L1B
SST-2 Q0.6B
Q8B
L1B
SQuAD Q0.6B
Q8B
ZO-SGD ZO-Adam RAdaZO MEAZO
1e−4 2e−4 5e−5 2e−4
6e−5 2e−4 5e−5 2e−4
2e−4 4e−4 1e−4 4e−4
1e−4 3e−4 6e−5 3e−4
4e−5 2e−4 6e−5 3e−4
1e−4 6e−4 1e−4 6e−4
9e−5 2e−4 7e−5 2e−4
5e−5 3e−4 6e−5 3e−4
1e−4 4e−4 8e−5 4e−4
Table 6. Optimal step sizes for 20-token prompt tuning (L: Llama-3.2, Q: Qwen-3).
Method
XSum L1B Q0.6B
SST-2 L1B Q0.6B
SQuAD L1B Q0.6B
ZO-SGD ZO-Adam RAdaZO MEAZO
3e−4 6e−4 6e−5 2e−4
5e−4 9e−5 7e−4 9e−5
3e−4 6e−4 2e−4 9e−4
9e−4 1e−4 1e−3 9e−5
2e−4 1e−2 2e−3 9e−3
1e−3 7e−5 2e−3 7e−5
Remark E.1. As predicted by our theory, ZO-Adam and MEAZO behave extremely similarly in high dimension and require the same optimal learning rate in almost all cases. We also observe a similar behavior than in FO finetuning: ZO-Adam (and also MEAZO) can use larger learning rates than ZO-SGD as observed in (Pan & Li, 2023). 18
On Adaptivity in Zeroth-Order Optimization
E.3. Training Curves Due to space constraints in the main paper, we present additional loss curves in this appendix. Specifically, we show training loss curves for LoRA fine-tuning (Figure 9), as well as both training and validation loss curves for prompt tuning (Figures 10 and 11). Figure 9 reports the training loss dynamics of different zeroth-order methods for LoRA across models and tasks, using the best step size selected for each method. Overall, the trends are consistent with the results reported in the main paper and provide additional insight into the optimization behavior over the course of training. Figures 10 and 11 show the corresponding training and validation loss curves for prompt tuning. We observe that, particularly on Qwen-3 0.6B, prompt-tuning exhibits noticeably higher variance and less stable optimization under zeroth-order methods compared to LoRA. This instability is reflected in both the training dynamics and validation trends, and is consistent across multiple random seeds. ZO-SGD
XSum
MEAZO
SST-2
SQuAD
5.0
7.5
4.0
5.0
3.0
2.5
2.0
0.0
0.0
Training Loss
4.0
5.0
3.0
2.0
2.5
6.0 4.0
2.5
2.0
0.0
0.0
1.0
1.0
0.5
2.0
L1B
7.5
4.0
Q8B
6.0
Training Loss
2.0
6.0
Q0.6B
Training Loss
-AdaZO
ZO-Adam
0.5
0.0
1.5 0
2500
5000
Steps
7500
10000
0
2500
5000
Steps
7500
10000
0
2500
5000
7500
10000
Steps
Figure 9. Training loss curves for zeroth-order methods applied to LoRA fine-tuning across models (L: Llama-3.2, Q: Qwen-3) and tasks, using the best step size for each method. Curves show the mean over three seeds, with shaded regions denoting ±2 standard deviations.
19
On Adaptivity in Zeroth-Order Optimization
-AdaZO
ZO-Adam
XSum
MEAZO
SST-2
SQuAD 1.0
1.0
2.0
0.5
1.5
0.0
4.0
5.0
2.0
0.5
5.0
0.0 0
5000
10000 15000 20000
Q0.6B
2.5
L1B
Training Loss Training Loss
ZO-SGD
0.0 0
5000
10000 15000 20000
Steps
0
5000
Steps
10000 15000 20000
Steps
Figure 10. Training loss curves for zeroth-order methods applied to to prompt-tuning across models and tasks, using the best step size for each method. Curves show the mean over three seeds, with shaded regions denoting ±2 standard deviations.
ZO-SGD
1.0
2.0
0.5
4.0
5.0
1.0 0.5
5.0
0.0 5000
10000 15000 20000
Steps
SQuAD
Q0.6B
Val. Loss
SST-2
2.5
0
MEAZO
L1B
Val. Loss
XSum
2.0
-AdaZO
ZO-Adam
0.0 0
5000
10000 15000 20000
Steps
0
5000
10000 15000 20000
Steps
Figure 11. Validation loss curves for zeroth-order methods applied to prompt-tuning across models and tasks, using the best step size for each method. Curves show the mean over three seeds, with shaded regions denoting ±2 standard deviations.
20
On Adaptivity in Zeroth-Order Optimization
E.4. Robustness Curves We complete the step size robustness analysis by reporting results on the remaining datasets, SST-2 and XSum, in Figure 12 (the main paper reports SQuAD). Consistent with the SQuAD findings, adaptivity (ZO-Adam and MEAZO) substantially strengthens robustness by widening the stable learning-rate window and reducing performance degradation at suboptimal η, particularly for larger step sizes. While a well-tuned ZO-SGD can match or even exceed adaptive methods at its optimal step size, it remains comparatively brittle. MEAZO is consistently as robust as ZO-Adam across both datasets. ZO-SGD
Val. Loss
0.2
0.0
0.0
0.5
0.5
0.2
0.2
0.0
0.0
0.5
0.5
0.0
0.0
10−1
100
101 η
Norm. Step Size ( * ) η
10−1
100
101 η
Norm. Step Size ( * ) η
XSum (Last) 2.0
1.8
1.8
3.0
3.0
2.0
2.0
3.0
3.0
2.0
2.0
10−1
100
Q8B
0.2
XSum (Best) 2.0
Q0.6B
Val. Loss
SST-2 (Last)
MEAZO
L1B
Val. Loss
SST-2 (Best)
ZO-Adam
101
10−1
η
Norm. Step Size ( * )
Norm. Step Size ( * ) η
100
101 η
η
Figure 12. Robustness of ZO-SGD, ZO-Adam, and MEAZO to step size (η) initialization across models fine-tuned on SST-2 (left) and XSum (right).
21
On Adaptivity in Zeroth-Order Optimization
E.5. Grouping We present a comprehensive comparison of grouped versus non-grouped zeroth-order optimization for ZO-SGD, ZO-Adam, and MEAZO across Llama-3.2 1B and Qwen-3 0.6B, fine-tuned on SST-2 and SQuAD. This section complements the main paper results (Fig. 6), which focus on Llama-3.2 1B on SQuAD as a representative setting. ZO-SGD ZO-SGD-G
ZO-Adam ZO-Adam-G
MEAZO MEAZO-G
1.0 1.0 0.5 0.0
0.0
5.0
5.0
2.5
2.5
0.0
Q0.6B
Val. Loss
SQuAD L1B
Val. Loss
SST-2
0.0 0
2000
4000
6000
8000
10000
0
2000
Steps
4000
6000
8000
10000
Steps
Figure 13. Convergence behavior of various optimizers under grouped and non-grouped settings for LLM fine-tuning.
SQuAD G0 G1 G2 G3 G4 G5 G6 G7 G8
0.75 0.50 0.25
G9 G10 G11 G12 G13 G14 G15 Global x 0.01
0.8 0.6 0.4 0.2
G9 G10 G11 G12 G13 G14 G15 Global x 0.1
G0 G2 G4 G6 G8 G10 G12 G14
G16 G18 G20 G22 G24 G26 Global x 0.01
0.0
15
G0 G2 G4 G6 G8 G10 G12 G14
10 5
G16 G18 G20 G22 G24 G26 Global x 0.01
4 2
0
Q0.6B
MEAZO Scalar vt
0.00
G0 G1 G2 G3 G4 G5 G6 G7 G8
L1B
MEAZO Scalar vt
SST-2 1.00
0 0
2000
4000
6000
8000
10000
Steps
0
2000
4000
6000
8000
10000
Steps
Figure 14. Evolution of the MEAZO scalar vt during LLM fine-tuning under grouped and non-grouped settings. For visualization clarity, the non-grouped vt is renormalized.
Figure 13 reports validation loss as a function of optimization steps for all methods, models, and datasets. Consistent with the main paper, grouping acts as a variance reduction mechanism and leads to faster convergence in terms of steps across most settings. However, this improvement does not translate directly to FLOP efficiency due to the increased cost of grouped updates, an effect that is consistent across both Llama-3.2 1B and Qwen-3 0.6B models. Figure 14 shows the evolution of the per-group MEAZO scalar vt over training when grouping is enabled. Across all settings, earlier-layer groups consistently exhibit larger vt values than deeper-layer groups, indicating higher sensitivity to parameter perturbations and consequently more conservative effective step sizes. This stratification is particularly clear and stable in Llama-3.2 1B models, while it is more heterogeneous in Qwen-3 0.6B. Importantly, this behavior is not an optimizer artifact but reflects an intrinsic property of deep neural networks: perturbations in earlier layers tend to have a larger impact on the model’s output and loss, whereas later layers are comparatively more robust. As a result, adaptive control of step sizes across parameter groups aligns naturally with these layer-wise sensitivities. 22
On Adaptivity in Zeroth-Order Optimization ZO-SGD ZO-SGD-G
0.2
SQuAD (Best)
0.2
0.1
0.1
0.0
0.0
0.4
0.4
0.2
0.2
0.0
0.0
10−1
100
101 η
Norm. Step Size ( * ) η
SQuAD (Last)
1.0
1.0
0.8
0.8
0.5
0.5
0.2
0.2
0.0
0.0
1.0
1.0
0.5
0.5
0.0
10−1
100
101 η
Norm. Step Size ( * ) η
Q0.6B
Val. Loss
SST-2 (Last)
MEAZO MEAZO-G
L1B
Val. Loss
SST-2 (Best)
ZO-Adam ZO-Adam-G
0.0
10−1
100
101
10−1
η
Norm. Step Size ( * )
Norm. Step Size ( * ) η
100
101 η
η
Figure 15. Robustness of grouped and non-grouped ZO-SGD, ZO-Adam, and MEAZO to step size (η) initialization across models fine-tuned on SST-2 (left) and SQuAD (right).
Finally, Figure 15 compares step-size robustness for grouped and non-grouped variants. While grouped updates typically improve stability, grouped ZO-SGD remains brittle across several settings, particularly near the end of training, where some seeds exhibit numerical divergence. These robustness curves further support the conclusion that grouping, while not always computationally optimal, provides a tangible stabilizing effect that complements adaptive methods such as MEAZO.
23
On Adaptivity in Zeroth-Order Optimization Table 7. Pets accuracy before and after 16-rank LoRA fine-tuning. Results are averaged over seeds.
Method
Accuracy (%)
Best η
Base
3.65
-
78.64±1.05 79.52±0.89 76.76±1.30 79.55±1.07
2e−4 7e−4 2e−4 7e−4
ZO-SGD ZO-Adam RAdaZO MEAZO
E.6. More Models We present additional experiments beyond LLM fine-tuning, covering both vision and multimodal settings. In particular, we fine-tune a Vision Transformer (ViT-B/16, ∼86M parameters) on the Oxford-IIIT Pets dataset, and the multimodal Ministral 14B model on SQuAD. For both settings, we follow the same experimental protocol as in our LLM experiments, including three random seeds and the same two-stage step-size sweep procedure. ViT-B/16 on Oxford-IIIT Pets. We fine-tune ViT-B/16 using LoRA on the Oxford-IIIT Pets dataset. Figure 16 reports the training and validation loss curves at each method’s best step size, as well as robustness to step-size perturbations. Table 7 summarizes the final test accuracy for each method alongside the corresponding optimal step size. Validation Loss
Training Loss
4.0
ZO-SGD ZO-Adam MEAZO RAdaZO
Loss
3.0
2.0
1.0
0
2000
4000
6000
8000
10000
0
Steps
2000
4000
6000
8000
10000
Steps
(a) Loss curves
Best
Last
2.0
Val. Loss
1.8 1.5 1.2 1.0 0.8 10−1
101
100
10−1
η
101
100 η
Norm. Step Size ( * )
Norm. Step Size ( * )
η
η
(b) Robustness Figure 16. Training-loss dynamics and step-size robustness for zeroth-order methods on ViT-B/16 fine-tuning on Pets. (a) Training loss curves at each method’s best step size, showing the mean over three seeds with shaded regions denoting ±2 standard deviations. (b) Validation-loss robustness as a function of normalized step size η/η ∗ , where η ∗ is each method’s best step size.
Ministral 14B on SQuAD. Using the same setup, we fine-tune the multimodal Ministral 14B model on the SQuAD dataset. Figure 17 reports training and validation loss curves at the best step size for each method, as well as robustness to 24
On Adaptivity in Zeroth-Order Optimization Table 8. SQuAD F1 before and after 16-rank LoRA fine-tuning on Ministral-3 14B. Results are averaged over seeds.
Method
F1 (%)
Best η
Base
19.85
-
85.29±0.56 85.41±0.43 85.99±0.20 85.75±0.09
5e−5 2e−4 4e−5 2e−4
ZO-SGD ZO-Adam RAdaZO MEAZO
step-size perturbations. Final test performance and optimal step sizes are summarized in Table 8. Validation Loss
Training Loss ZO-SGD ZO-Adam MEAZO RAdaZO
4.0
Loss
3.0 2.0 1.0 0.0 0
2000
4000
6000
8000
10000
0
Steps
2000
4000
6000
8000
10000
Steps
(a) Loss curves
Best
Last
Val. Loss
2.0 1.5 1.0 0.5
10−1
101
100
10−1
η
101
100 η
Norm. Step Size ( * )
Norm. Step Size ( * )
η
η
(b) Robustness Figure 17. Training-loss dynamics and step-size robustness for zeroth-order methods on Ministral 14B fine-tuning on SQuAD. (a) Training loss curves at each method’s best step size, showing the mean over three seeds with shaded regions denoting ±2 standard deviations. (b) Validation-loss robustness as a function of normalized step size η/η ∗ , where η ∗ is each method’s best step size.
Conclusion. Overall, the conclusions drawn from our LLM experiments carry over to both the vision and multimodal settings. First, when properly tuned, ZO-SGD performs comparably to adaptive methods. Second, per-coordinate adaptivity offers no tangible benefit: scalar-based MEAZO closely tracks the performance of ZO-Adam. Finally, the primary advantage of adaptivity lies in improved robustness to step-size selection, rather than in per-coordinate scaling itself.
25
On Adaptivity in Zeroth-Order Optimization
E.7. Impact of β1 in Adaptive ZO Optimization In MEAZO (Alg. 1) we employ second moment normalization of the projected gradients only. MEAZO can be viewed as a compressed variant of ZO-Adam with β1 = 0, by design. The key quantity is the average projected gradient g (line 8), which captures directional information. In the update step (line 12), q X ∆fi (xt ; ξ)
η xt ← xt−1 − √ v̂ + ζ
i=1
q
! ui
,
each noise vector ui is weighted by its corresponding projected gradient. This ensures proper directional credit assignment. Replacing the sum with a single smoothed scalar would discard this structure and degrade the update quality. Figure 18 further supports this design choice: disabling β1 in ZO-Adam has little to no impact on convergence when fine-tuning Llama 3.2 1B on XSum. This reinforces our decision to avoid smoothed first-moment updates in MEAZO. = 1.5e = 1.5e = 2.0e = 2.0e = 2.5e = 2.5e = 3.0e = 3.0e = 3.5e = 3.5e = 4.0e = 4.0e = 4.5e = 4.5e
2.8
Validation Loss
2.6 2.4 2.2 2.0
04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0 04, 1 = 0.9 04, 1 = 0
1.8 1.6 0
2000
4000
Steps
6000
8000
10000
Figure 18. Validation loss curves for ZO-Adam with β1 = 0 and β1 = 0.9 across different step sizes during fine-tuning of Llama 3.2 1B on XSum.
26
On Adaptivity in Zeroth-Order Optimization
E.8. Perturbation Distribution Impact We examine how varying the perturbation distribution used in the ZO gradient estimator in (2) affects performance. Specifically, we consider normal perturbations (u ∼ N (0, Id )), uniform over the sphere (u ∼ Uniform(S)), Rademacher i.i.d. i.i.d. (ui ∼ {−1, 1}), and ternary perturbations (ui ∼ {−1, 0, 1}). As shown in Fig. 19, across ZO-SGD, ZO-Adam, R-AdaZO, and MEAZO, the choice of perturbation distribution has negligible effect on the optimization trajectory.
Validation Loss
1.2
MEAZO-N MEAZO-R MEAZO-T MEAZO-U -AdaZO-N -AdaZO-R -AdaZO-T -AdaZO-U
1.0 0.8 0.6 0.4
ZO-Adam-N ZO-Adam-R ZO-Adam-T ZO-Adam-U ZO-SGD-N ZO-SGD-R ZO-SGD-T ZO-SGD-U
0.2 0.0
0
2000
4000
6000
Steps
8000
10000
Figure 19. The impact of perturbation distributions on zero-order optimization methods for Llama-3.2 1B on SST-2: Normal, Rademacher, Ternary, and Uniform. Best seen in color.
27
On Adaptivity in Zeroth-Order Optimization
E.9. Comparison with FZOO (Dang et al., 2025) FZOO proposed an alternative way to dynamically tune the step size. Given a minibatch ξ at time step t, FZOO first computes q one-sided perturbed function evaluations {fi = f (xt + εui ; ξ)}qi=1 and one unperturbed evaluation f0 = f (xt ; ξ). Using these q + 1 evaluations, FZOO computes the following normalized update: q
gt =
1 X (fi − f0 )ui εqσt i=1
(14)
where σt = std({fi }) is the perturbed losses’ standard deviation. Using their publicly available code, we experimented with full model fine-tuning of OPT 1.3B (Zhang et al., 2022b) on SST-2 using their default hyperparameters for FZOO and ZO-SGD. To test our hypothesis that a well-tuned ZO-SGD can often match adaptive methods, we experimented with the following step size8 : ηZO-SGD = ηFZOO
T 1 X
T t=1
σt
−1
≈ 2.6 × 10−7
(15)
Computing (15) requires first running FZOO for T iterations with initial step size ηFZOO . We then collect all T standard deviation values {σt } and use that to guess an appropriate step size for ZO-SGD by normalizing ηFZOO with the mean of {σt }. Figure 20 demonstrates that ZO-SGD with a carefully selected step size via (15) can match the performance of FZOO, despite requiring 4.5×9 fewer forward passes per mini-batch. For completeness, we also run MEAZO with the same step size as FZOO (η = 1e−5), but with the same number of samples as ZO-SGD (q = 1). Figure 20 also plots the performance of our proposed MEAZO, demonstrating that it can match ZO-SGD with fewer perturbations than FZOO and without the need for careful step size tuning. Notably, we observe that reducing q for FZOO leads to instability, highlighting the sensitivity of its performance to the number of perturbations.
FZOO (q = 8, = 1e 5) ZO-SGD (q = 1, = 2.6e 7) MEAZO (q = 1, = 1e 5)
Validation Loss
0.8 0.7 0.6 0.5 0.4 0.3 0.2
0
2500
5000
7500
10000
Steps
12500
15000
17500
20000
Figure 20. Performance comparison of FZOO, MEAZO, and ZO-SGD in full-model fine-tuning of OPT-1.3B on the SST-2 dataset. Results were obtained using the publicly available FZOO code.
8
At the time of writing, the FZOO implementation did not normalize their update with ε appropriately, which lead us to re-scale (15) by multiplying with ε = 0.001. 9 ZO-SGD and MEAZO require 2q forward passes, whereas FZOO requires only q + 1 forward passes.
28
On Adaptivity in Zeroth-Order Optimization
F. Computational Analysis of Grouped ZO Consider a p-layer decoder-only transformer architecture. Computing the vanilla grouped ZO gradient in (2) requires 2qp decoder forward passes (ignoring the language modeling head and loss computation). In contrast, a naive implementation of the grouped ZO estimator in (3) would require 2qp2 forward passes, incurring an additional factor of p (e.g., p = 16 for LLaMA 3.2 1B). To reduce this overhead, we process the grouped ZO gradient from left to right using Alg. 2. By caching the prefix activation at each step, the total number of decoder forward calls becomes: (p − 1) + q
p X
2(p − j) = pq(p + 1) + p − 1,
(16)
j=1
which scales as O(qp2 ) but with a significantly smaller constant factor than the naive approach. For example, when q = 1 and p = 16, this results in roughly a 1.8× reduction in forward calls compared to the naive grouped implementation, at the cost of storing a single intermediate activation. Algorithm 2 Efficient Grouped ZO p
1: Inputs: initial input h0 ; full parameter vector x ∈ Rd ; partition {Xj }j=1 ; step size ε > 0; number of queries q
ˆ (x) ∈ Rd 2: Output: grouped ZO gradient estimate ∇f ˆ (x) ← 0 3: Initialize cache with prefix cache ← h0 ; ∇f 4: for j = 1 to p do 5: read prefix activation: hj−1 ← cache 6: compute hj from the unperturbed block j 7: cache ← hj 8: /∗ Sample block-local noise (j)
(j)
▷ update cache
draw u1 , . . . , uq ∈ R|Xj | i.i.d. from P b (j) ← 0 ∈ Rd Initialize ∇ for i = 1 to q do /∗ perturb layer j and compute f + (j) 13: x+ j ← xj + εui 14: f + ← forward layers j:p starting from hj−1 with x+ j and unperturbed xk>j 15: /∗ perturb layer j and compute f − (j) 16: x− j ← xj − εui 17: f − ← forward layers j:p starting from hj−1 with x− j and unperturbed xk>j 18: /∗ accumulate + − (j) b (j) ← ∇ b (j) + f − f ũ(j) 19: ∇ ▷ ũi ∈ Rd is its zero-padded version with nonzeros only on Xj i 2ε 20: end for 21: /∗ block contribution ˆ (x) ← ∇f ˆ (x) + 1 ∇ b (j) 22: ∇f q 23: /∗ evict old prefix 24: discard hj−1 ; retain only hj 25: end for 9: 10: 11: 12:
29
On Adaptivity in Zeroth-Order Optimization
G. General Definitions and Lemmas Let us state first useful optimization definitions and lemmas needed for our convergence proofs. Definition G.1 (L-smoothness). A differentiable function f : Rd → R is said to be L-smooth if its gradient is L-Lipschitz continuous, that is, ∥∇f (x) − ∇f (y)∥ ≤ L∥x − y∥, ∀x, y ∈ Rd . Equivalently, for all x, y ∈ Rd ,
L ∥y − x∥2 . (17) 2 Lemma G.2 (Lemma 1.2.3 of (Nesterov, 2013)). If a differentiable function f : Rd → R is L-smooth, then for all x, y ∈ Rd , L |f (y) − f (x) − ⟨∇f (x), y − x⟩| ≤ ∥y − x∥2 . (18) 2 Lemma G.3 (ZO Projected Gradient upper bound). Let x, u ∈ Rd and ε > 0. If a differentiable function f : Rd → R is L-smooth, then Lε f (x + εu) − f (x − εu) Lε 2 2 ⟨∇f (x), u⟩ − ∥u∥ ≤ ≤ ⟨∇f (x), u⟩ + ∥u∥ , (19) 2 2ε 2 which implies that Lε f (x + εu) − f (x − εu) 2 ≤ |⟨∇f (x), u⟩| + ∥u∥ . (20) 2ε 2 f (y) ≤ f (x) + ⟨∇f (x), y − x⟩ +
Proof. Applying (17) with y := x + εu leads to: f (x + εu) ≤ f (x) + ε⟨∇f (x), u⟩ +
Lε2 2 ∥u∥ . 2
Similarly, applying (18) with y := x − εu and multiplying the left-hand side by −1 gives −f (x − εu) ≤ −f (x) + ε⟨∇f (x), u⟩ +
Lε2 2 ∥u∥ . 2
Summing up the above two equations and dividing by 2ε proves to (19): f (x + εu) − f (x − εu) Lε 2 ≤ ⟨∇f (x), u⟩ + ∥u∥ . 2ε 2
(21)
One can also apply the proved inequality to u ← −u and multiply it by −1, which proves the left-hand side inequality of: ⟨∇f (x), u⟩ −
f (x + εu) − f (x − εu) Lε Lε 2 2 ∥u∥ ≤ ≤ ⟨∇f (x), u⟩ + ∥u∥ . 2 2ε 2
(22)
Applying the fact that for any A, M ∈ R and B ≥ 0, A − B ≤ M ≤ A + B =⇒ |M | ≤ |A| + B to inequalities in (22) concludes the proof. Lemma G.4 (Smoothing Transfer). Let F : Rd → R be a G-Lipschitz function. Then its smoothed - G-Lipschitzness version Fε (x) = Eu∼D F (x + εu) is also G-Lipschitz. Proof. Since F is G-Lipschitz, for any x, y ∈ Rd we have |F (x) − F (y)| ≤ G ∥x − y∥ . For the smoothed function Fε , consider |Fε (x) − Fε (y)| = |Eu∼D [F (x + εu) − F (y + εu)]| . By Jensen’s inequality and the Lipschitz property of F , |Fε (x) − Fε (y)| ≤ Eu∼D [|F (x + εu) − F (y + εu)|] ≤ Eu∼D [G ∥x − y∥] = G ∥x − y∥ . Hence Fε is G-Lipschitz. 30
On Adaptivity in Zeroth-Order Optimization
Lemma G.5 (Smoothing - L-smoothness Transfer). Let F : Rd → R be an L-smooth function. Then its smoothed version Fε (x) = Eu∼D F (x + εu) is also L-smooth. Remark G.6. The above lemma can be found in eq (12) of (Nesterov & Spokoiny, 2017) for normal perturbation, Lemma 4.1 (a) of (Gao et al., 2018) for uniform spherical perturbation. Proof. By Leibniz’s rule (differentiation under the expectation), we have ∇Fε (x) = Eu ∇F (x + εu) . For any x, y ∈ Rd , ∥∇Fε (x) − ∇Fε (y)∥ = Eu ∇F (x + εu) − ∇F (y + εu) . Applying Jensen’s inequality (since ∥ · ∥ is convex), we get ∥∇Fε (x) − ∇Fε (y)∥ ≤ Eu ∥∇F (x + εu) − ∇F (y + εu)∥ .
(a)
Since F is L-smooth, its gradient is L-Lipschitz, so ∥∇F (x + εu) − ∇F (y + εu)∥ ≤ L∥x − y∥.
(b)
Combining (a) and (b), we obtain ∥∇Fε (x) − ∇Fε (y)∥ ≤ L∥x − y∥. Hence, Fε is also L-smooth. Lemma G.7 (Smoothing - Function Error). Let F : Rd → R be an L-smooth function, and let P be any centered probability distribution. Define its smoothed version as Fε (x) = Eu∼P [F (x + εu)] ,
∀x ∈ Rd .
Then, for any x ∈ Rd , |Fε (x) − F (x)| ≤
h i ε2 2 LEu∼P ∥u∥ . 2
(23)
Proof. Let x, u ∈ Rd and ε > 0, by L-smoothness of F one has ε2 2 L ∥u∥ 2 i h ε2 2 =⇒ Eu∼P [F (x + εu) − F (x)] ≤ ε⟨∇F (x), Eu∼P [u]⟩ + LEu∼P ∥u∥ 2 h i ε2 P centered 2 ⇐⇒ Fε (x) − F (x) ≤ LEu∼P ∥u∥ . 2 F (x + εu) − F (x) ≤ ε⟨∇F (x), u⟩ +
(24)
By re-applying the above reasoning by inverting x and x + εu gives the symmetric bound. Lemma G.8 (Smoothing - Gradient Error). Let F : Rd → R be an L-smooth function, and let P be any probability distribution supported on a bounded set in Rd . Define its smoothed version as Fε (x) = Eu∼P [F (x + εu)] ,
∀x ∈ Rd .
Then, for any x ∈ Rd , ∥∇Fε (x) − ∇F (x)∥ ≤ εLEu∼P [∥u∥] .
(25)
Remark G.9. A similar proof scheme is used in (Berahas et al., 2022) to prove similar bounds for normal, eq. (2.10), and uniform distributions, eq. (2.35). 31
On Adaptivity in Zeroth-Order Optimization
Proof. We have ∥∇Fε (x) − ∇F (x)∥ = ∥∇Eu∼P [F (x + εu)] − ∇F (x)∥ Leibniz’s
∥Eu∼P [∇F (x + εu)] − ∇F (x)∥
=
= ∥Eu∼P [∇F (x + εu) − ∇F (x)]∥ Jensen’s
≤
Eu∼P [∥∇F (x + εu) − ∇F (x)∥]
L-smoothness
≤
εLEu∼P [∥u∥] .
Lemma G.10 (Smoothing - Stochastic Gradient Variance Bound). Let F : Rd → R be the population loss defined as F (x) = Eξ∼D [f (x; ξ)]
∀x ∈ Rd ,
(26)
where each individual sample loss f (.; ξ). Let P be any probability distribution supported on a bounded set in Rd . Let us recalled the definition of the smoothed version of F Fε (x) := Eu∼P [F (x + εu)] ,
∀x ∈ Rd ,
(27)
and similarly for f (., ξ) fε (x; ξ) := Eu∼P [f (x + εu; ξ)] ,
∀x ∈ Rd , ∀ξ.
d
(28) 10
Assume that, for all x ∈ R , the sample loss gradient is an unbiased estimate of the the full loss gradient , and that there exists σ > 0 such that, its variance is bounded by σ 2 , i.e., Eξ [∇f (x; ξ)] = ∇F (x), h i 2 Eξ ∥∇f (x; ξ) − ∇F (x)∥ ≤ σ 2 .
(29)
Then, for any x ∈ Rd , the smoothed sample loss gradient is also an unbiased estimator of the smoothed full loss and its variance of is also bounded by σ 2 , i.e., Eξ [∇fε (x; ξ)] = ∇Fε (x), h i 2 Eξ ∥∇fε (x; ξ) − ∇Fε (x)∥ ≤ σ 2 .
(30) (31)
Proof. Let x ∈ Rd . We have that the mean of the smoothed sample loss equals (28)
Eξ [∇fε (x; ξ)] = Eξ [∇Eu [f (x + εu; ξ)]]
Leibniz’ rule
=
(26)
(27)
∇Eu [Eξ [f (x + εu; ξ)]] = ∇Eu [F (x + εu)] = ∇Fε (x).
We also have that the variance of the smoothed sample loss equals h i h i 2 2 Eξ ∥∇fε (x; ξ) − ∇Fε (x)∥ = Eξ ∥∇Eu [f (x + εu; ξ) − F (x + εu)]∥ h i Leibniz’ rule 2 = Eξ ∥Eu [∇f (x + εu; ξ) − ∇F (x + εu)]∥ h h ii Jensen’s ineq. 2 ≤ Eξ Eu ∥∇f (x + εu; ξ) − ∇F (x + εu)∥ (29)
≤ σ2
10 If stochastic losses are regular enough, e.g., Eξ [∥∇f (x; ξ)∥] < ∞ such that dominated convergence theorem can be applied, then Eξ [∇f (x; ξ)] = ∇F (x).
32
On Adaptivity in Zeroth-Order Optimization
G.1. Uniform Perturbations In this section we will derive results for the q-uniform samples centered ZO estimator: q X f (x + εui ) − f (x − εui ) ˆ εq (x) = d ∇f ui , q i=1 2ε
(32)
where ui ∼ Uniform(S) with S = {u ∈ Rd : ∥u∥ = 1} being the unit sphere of dimensions d and ε > 0. We now state useful and known results. Definition G.11 (Uniform Smoothed Function). Let us denote by fε , the smoothed function over the unit ball B of dimensions d, that is for all x ∈ Rd fε (x) := Ev∼B [f (x + εv)] . (33) Remark G.12. This is the same definition as in eq. (4.1) of (Shalev-Shwartz, 2011) and eq. (50) of (Gao et al., 2018). Lemma G.13 (Unbiased ZO Gradient Estimate of the Smoothed Function). The ZO estimator in (32) provides an unbiased estimate of the gradient of the smoothed function fε defined in (33): h i ˆ εq (x) = ∇fε (x), EUq ∼(S)q ∇f (34) where Uq := {u1 , . . . , uq } denotes the q random vectors sampled i.i.d. from the unit sphere S. Proof. This is a direct consequence of Lemma 1 of (Flaxman et al., 2004) or of Lemma 4.4 of (Shalev-Shwartz, 2011) applied to u and −u.
33
On Adaptivity in Zeroth-Order Optimization
H. Omitted Proofs and Derivations H.1. Proof of Proposition 3.1 We provide the proof of Proposition 3.1 (restated below): ˆ εq (x) denote the q-sample ZO estimator in Proposition (Restated). Let f : Rd → R be an L-smooth function, and let ∇f (2), where ui ∼ N (0, Id ) for all i ∈ [q] := {1, . . . , q}. Then in the ε → 0 limit we have: h i ˆ εq (x)2 ≈ 1 ∥∇f (x)∥2 1d + ∇f (x)2 + ∇f (x)2 , (35) Eu ∇f q 2
where (·) stands for the element-wise power of 2 and Eu denotes the expectation over u1 , . . . , uq . Proof. We first note that from Lemma G.3, we have ∀u ∈ Rd : lim
ε→0
f (x + εu) − f (x − εu) = u⊤ ∇f (x). 2ε
(36)
Then, in the ε → 0 limit we have: q q q X f (x + εui ) − f (x − εui ) 1X ⊤ 1X ⊤ ˆ εq (x) = 1 ui ≈ ui ∇f (x) ui = g ui ui ∇f q i=1 2ε q i=1 q i=1
(37)
where g = ∇f (x) and we drop the dependency on x for clarity. Taking the expectation of the k th element squared, we get: !2 q h h ii (37) 1 X ˆ εq (x)2 g⊤ ui ui (38) Eu ∇f ≈ 2 Eu q k i=1 q q X X X 1 2 = 2 Eu (g⊤ ui )ui,k (g⊤ uj )uj,k (39) g⊤ ui u2i,k + q i=1 i=1 j̸=i
=
q 1 X
q 2 i=1
h Eu
⊤
g ui
2
u2i,k
i
q 1 XX Eu (g⊤ ui )ui,k (g⊤ uj )uj,k + 2 q i=1 j̸=i
Expanding the first term with v := ui ∼ N (0, Id ): h Ev
" d # X 2 2 2 i 2 g v vk = Ev gl vl vk ⊤
l=1
d X X = Ev gl2 vl2 + gl gs vl vs vk2 l=1
=
d X
l̸=s
X gl2 Ev vl2 vk2 + gl gs Ev vl vs vk2
l=1
l̸=s
|
{z
}
vanishes since odd moments = 0
X 2 2 = gk2 Ev vk4 + gl Ev vl Ev vk2 l̸=k
= gk2 · 3 +
X
gl2 · 1
l̸=k
= 3gk2 +
X
gl2
l̸=k
=
d X
gl2 + 2gk2
l=1
= ∥g∥2 + 2gk2 . 34
(40)
On Adaptivity in Zeroth-Order Optimization
For the second term, with v := ui , w := uj , i ̸= j: Ev,w (g⊤ v)vk (g⊤ w)wk = Ev (g⊤ v)vk · Ew (g⊤ w)wk (v ⊥ w) d d X X = ga Ev [va vk ] · gb Ew [wb wk ] a=1
=
d X
(41) (42)
b=1 d X ga δa,k · gb δb,k
a=1 = gk2 .
(43)
b=1
(44)
Plugging back into (38): 2 1 Eu ĝq (x) k ≈ 2 q(∥g∥2 + 2gk2 ) + q(q − 1)gk2 q 1 = 2 q∥g∥2 + 2qgk2 + q(q − 1)gk2 q ∥g∥2 2g 2 (q − 1)gk2 = + k + q q q (q + 1)gk2 ∥g∥2 + = q q 1 = ∥g∥2 + gk2 + gk2 . q Since g = ∇f (x), this matches the proposition in vector form: h i ˆ εq (x)2 ≈ 1 ∥∇f (x)∥2 1d + ∇f (x)2 + ∇f (x)2 . Eu ∇f q
H.2. Proof of Proposition H.1 We provide the proof of the following porpositio for the uniform perturbation case: ˆ q (x) denote the q-sample ZO estimator Proposition H.1 (Uniform). Let f : Rd → R be an L-smooth function, and let ∇f ε in (2), where ui ∼ Uniform(S) for all i ∈ [q] := {1, . . . , q}. Then in the ε → 0 limit we have: h i d ∥∇f (x)∥2 1 + 2∇f (x)2 q − 1 d q 2 ˆ + ∇f (x)2 (45) Eu ∇fε (x) ≈ q(d + 2) q 2
where (·) stands for the element-wise power of 2 and Eu denotes the expectation over u1 , . . . , uq . Proof. Let ui ∼ Uniform(S) be sampled from the unit sphere in Rd . By Lemma G.3 and in the ε → 0 limit, the q-sample ZO estimator becomes: q X ˆ εq (x) ≈ d (g⊤ ui )ui , (46) ∇f q i=1 where g = ∇f (x) for brevity. Taking the expectation of the k th element squared, we get: " q # h h ii X 2 2 d q 2 ⊤ ˆ ε (x) Eu ∇f ≈ 2 Eu (g ui )ui q k i=1 d2 = 2 q
q X
(47)
! ⊤ 2 2 X ⊤ Eu (g ui ) ui,k + Eu (g ui )ui,k (g⊤ uj )uj,k .
i=1
i̸=j
35
(48)
On Adaptivity in Zeroth-Order Optimization
For v ∼ Uniform(S), the moments are: E[vi2 ] =
1 , d
E[vi4 ] =
Thus: Ev (g⊤ v)2 vk2 = gk2 ·
3 , d(d + 2)
E[vi2 vj2 ] =
1 . d(d + 2)
X 1 ∥g∥2 + 2gk2 3 + gl2 · = . d(d + 2) d(d + 2) d(d + 2) l̸=k
For two independent samples v, w: 2 X g2 Ev,w (g⊤ v)vk (g⊤ w)wk = ga E[va vk ] = (gk /d)2 = k2 . d a Plugging back: 2 g2 d2 ∥g∥2 + 2gk2 Eu ĝq (x) k ≈ 2 q · + q(q − 1) · k2 . q d(d + 2) d Simplify: =
d(∥g∥2 + 2gk2 ) (q − 1)gk2 + . q(d + 2) q
And we obtain the vector form: h
ˆ εq (x)2 Eu ∇f
i
d ∥∇f (x)∥2 1d + 2∇f (x)2 q−1 ≈ + ∇f (x)2 . q(d + 2) q
36
On Adaptivity in Zeroth-Order Optimization
H.3. Proof of Theorem 4.6 We re-state and prove Theorem 4.6, which provides a guarantee on an objective function F while optimizing a smoothed proxy Fε : Theorem H.2 (Smoothed Proxy Optimization - Restated). Let F : hRd →i R be an L-smooth function. For a centered 2 smoothing distribution P with bounded support and satisfying Eu∼P ∥u∥ = C < ∞, define the smoothed objective: ∀x ∈ Rd ,
Fε (x) := Eu∼P [F (x + εu)] , where ε > 0 is the smoothing parameter. Assume the optimal values F ∗ = inf F (x),
Fε∗ = inf Fε (x)
x∈Rd
x∈Rd
−1 are finite. Suppose an algorithm A generates iterates {xt }Tt=0 such that T −1 i 1 X h 2 E ∥∇Fε (xt )∥ ≤ K0 Fε (x0 ) − Fε∗ + K1 T t=0
(49)
for some constants K0 , K1 ≥ 0. Then, for the original function F , it holds that T −1 i 1 X h 2 E ∥∇F (xt )∥ ≤ K0 F (x0 ) − F ∗ + K1 + ε2 L2 C K20 + 2 . T t=0
(50)
Proof. Let x, u ∈ Rd and ε > 0. First, observe that F (x + εu) ≥ F ∗ since F ∗ = inf z F (z). Taking expectation over u ∼ P gives Fε (x) = E [F (x + εu)] ≥ F ∗ . Consequently, the smoothed optimum satisfies Fε∗ = inf Fε (x) ≥ F ∗ . x
By Lemma G.8 (due to smoothness of both F and Fε ), we also have ∀x ∈ Rd : √ 2 2 ∥∇F (x)∥ ≤ (∥∇Fε (x)∥ + εL C)2 ≤ 2 ∥∇Fε (x)∥ + 2ε2 L2 C.
(51)
(52)
By Lemma G.7 we also have |F (x) − Fε (x)| ≤
ε2 LC. 2
(53)
Finally, we get: T −1 −1 h i (52) 1 TX i 1 X h 2 2 E ∥∇F (xt )∥ ≤ E ∥∇Fε (xt )∥ + 2ε2 L2 C T t=0 T t=0 (49)
≤ K0 Fε (x0 ) − Fε∗ + K1 + 2ε2 L2 C (53) ≤ K0 F (x0 ) − Fε∗ + K1 + ε2 L2 C K20 + 2 (51) ≤ K0 F (x0 ) − F ∗ + K1 + ε2 L2 C K20 + 2 .
H.4. Proof of Theorem 4.4 We first present a useful lemma that provides an upper bound on the expected squared norm of the zeroth-order (ZO) gradient, where the expectation is taken over the perturbation randomness: 37
On Adaptivity in Zeroth-Order Optimization
ˆ εq (x) be the zeroth-order (ZO) gradient estimator Lemma H.3 (ZO Estimator - Expected Squared Norm Bound). Let ∇f d defined in (32). If f : R → R is differentiable and L-smooth, then: 2 1 ε2 d2 2 1 2 2 q ˆ EUq ∼(S)q ∇fε (x) ≤ 2d ∥∇f (x)∥ + L + 1− ∥∇fε (x)∥ (54) q 2 q where ε > 0, fε is defined in (33) and Uq := {u1 , . . . , uq }. ˆ q (x) is an average of q i.i.d. estimators: Proof. First, note that ∇f ε q q 1X d X f (x + εui ) − f (x − εui ) ˆ εq (x) (32) ui =: ĝ(x, ui ). ∇f = q i=1 2ε q i=1
By independence of the perturbations, we get: " EUq ∼(S)q
q 1X
q i=1
2
ĝ(x, ui )
#
q X X 1 = 2 EUq ∥ĝ(x, ui )∥2 + ⟨ĝ(x, ui ), ĝ(x, uj )⟩ q i=1 i̸=j
! D E 1 qEu∼S ∥ĝ(x, u)∥2 + q(q − 1) Eu∼S [ĝ(x, u)] , Eu∼S [ĝ(x, u)] = q2 1 1 2 Eu [ĝ(x, u)] = Eu ∥ĝ(x, u)∥2 + 1 − q q 1 Lemma G.13 1 2 2 = Eu ∥ĝ(x, u)∥ + 1 − ∥∇fε (x)∥ . (55) q q ui ’s i.i.d.
Taking the expected norm squared of a single estimator: # " 2 f (x + εu) − f (x − εu) 2 u Eu∼S ∥ĝ(x, u)∥ = Eu d 2ε " # 2 f (x + εu) − f (x − εu) 2 2 = d Eu ∥u∥ 2ε 2 (20) ε 2 2 ≤ d2 Eu |⟨∇f (x), u⟩| + L ∥u∥ ∥u∥ 2 ε 2 u∈S 2 = d Eu |⟨∇f (x), u⟩| + L 2 (a+b)2 ≤2(a2 +b2 ) ε2 2 2 2 ≤ d Eu 2 ⟨∇f (x), u⟩ + L 2 ε2 d2 2 ⊤ L = 2d2 ∇f (x) Eu uu⊤ ∇f (x) + 2 2 2 ε d 2 2 = 2d ∥∇f (x)∥ + L . 2 Therefore, we get: EUq ∼(S)q
ˆ εq (x) ∇f
2
≤
1 q
2
2d ∥∇f (x)∥ +
ε2 d2 2 L 2
1 2 + 1− ∥∇fε (x)∥ . q
We also state the following result on the total variance of the norm of the ZO estimator: 38
(56)
(57) (58) (59) (60) (61) (62)
On Adaptivity in Zeroth-Order Optimization
Lemma H.4 (Affine Variance Bound and Unbiasedness for ZO Gradient Estimator). Let F : Rd → R be the population loss defined as F (x) = Eξ∼D [f (x; ξ)] ∀x ∈ Rd , where each individual sample loss f (.; ξ) is L-smooth. Let fε and Fε be their smoothed counterparts according to (33). Assume that, there exists σ > 0 such that, for all x ∈ Rd , the variance of the sample loss gradient satisfies h i 2 Eξ ∥∇f (x; ξ) − ∇F (x)∥ ≤ σ 2 , (63) ˆ q (x; ξ) be the zeroth-order (ZO) gradient estimator defined in (32) for uniform perturbations. Let q ∈ N∗ , ε > 0 and let ∇f ε d Then, for any x ∈ R , we have: i h ˆ q (x; ξ) = ∇Fε (x), Eξ,Uq ∇f (64) ε 2 2 2 dε L 2d − 1 4d − 1 2 ˆ εq (x; ξ) − ∇Fε (x) Eξ, Uq ∇f ≤ (8 + d) + + 1 σ2 + ∥∇Fε (x)∥ . (65) 2q q q Proof. The unbiasedness of (32) is already established due to Lemma G.13: h i h h ii ˆ εq (x; ξ) = Eξ EU ∇f ˆ εq (x; ξ) | ξ = Eξ [∇fε (x; ξ)] = ∇Fε (x). Eξ,Uq ∇f q
(66)
h i h i 2 2 2 We recall that the variance of a random vector X is given by Var (∥X∥) = E ∥X − E [X]∥ = E ∥X∥ − ∥E [X]∥ . We aim at computing the variance of our ZO stochastic gradient estimator: 2 (66) 2 2 q q ˆ ˆ Eξ,Uq ∇fε (x; ξ) − ∇Fε (x) = Eξ,Uq ∇fε (x; ξ) − ∥∇Fε (x)∥ . (67) Then, we focus on upper-bounding the first term of the variance decomposition 2 Lemma H.3 1 ε2 d2 2 1 2 2 ˆ εq (x; ξ) Eξ,Uq ∇f ≤ Eξ 2d ∥∇f (x; ξ)∥ + L + 1− ∥∇fε (x; ξ)∥ q 2 q h ε2 i (63) 2d 1 2 2 ≤ Eξ ∥∇fε (x; ξ)∥ ∥∇F (x)∥ + σ 2 + d2 L2 + 1 − q 2q q 2 Lemma G.10 2d + q − 1 ε 2 2 2d 1 2 2 2 ≤ σ + d L + ∥∇F (x)∥ + 1 − ∥∇Fε (x)∥ q 2q q q Lemma G.8 2d − 1 d 2 2 4d − 1 2 2 ≤ + 1 σ + (d + 8) ε L + + 1 ∥∇Fε (x)∥ q 2q q
(68)
Combining (67) and (68), we obtain Eξ,Uq
ˆ q (x; ξ) − ∇Fε (x) ∇f ε
2
≤
2d − 1 d 4d − 1 2 + 1 σ 2 + (d + 8) ε2 L2 + ∥∇Fε (x)∥ . q 2q q
We can now prove Theorem 4.4 (re-stated below): Theorem H.5 (Adaptive SGD with Affine Variance Bound). Let F : Rd → R be the population loss F (x) = Eξ∼D [f (x; ξ)] , where each sample loss f (x; ξ) is L-smooth and G-Lipschitz (equivalently, ∥∇f (x; ξ)∥ ≤ G for all x, ξ). Assume F is bounded from below by F ∗ , i.e., F ∗ = inf x F (x) > −∞. 39
On Adaptivity in Zeroth-Order Optimization
Suppose we have an unbiased stochastic gradient estimator g(x; ξ), i.e., Eξ∼D [g(x; ξ)] = ∇F (x), satisfying the affine variance bound h i 2 2 Eξ∼D ∥g(x; ξ) − ∇F (x)∥ ≤ σ02 + σ12 ∥∇F (x)∥ . Consider the adaptive SGD update xt+1 = xt − √
η g(xt ; ξt ), vt + ζ
with stepsize η > 0, stability constant ζ > 0, and second-moment tracker vt = β vt−1 + (1 − β) γt2 ,
0 < β < 1,
where {γt }t≥0 is predictable (measurable w.r.t. the filtration generated by {xt , ξt }), satisfies 0 ≤ γt ≤ G, and obeys the condition 2 Eξt ∼D γt ∥g(xt ; ξt )∥ xt ≤ σ02 + (σ12 + 1) ∥∇F (xt )∥ . (69) Assume the parameters (β, η, ζ) are chosen so that √ G(1 + σ12 ) 1 − β L η 1 max , ≤ . ζ 2ζ 4
(70)
Then, after T iterations, T −1 i p F (x0 ) − F ∗ σ02 1 X h 2 E ∥∇F (xt )∥ ≤ 2 β G + ζ + . T t=0 ηT 2ζ
(71)
Proof. Define gt := g(xt ; ξt ), and consider the descent lemma at iteration t: F (xt+1 ) ≤ F (xt ) − √
Lη 2 η 2 ⟨∇F (xt ), gt ⟩ + √ ∥gt ∥ vt + ζ 2( vt + ζ)2
(72)
Taking the expectation conditioned on xt : Eξt [F (xt+1 )|xt ] ≤ F (xt ) −ηEξt |
" # 2 ⟨∇F (xt ), gt ⟩ Lη 2 ∥gt ∥ | xt + Eξt √ | xt √ vt + ζ 2 ( vt + ζ)2 {z } {z } | A
(73)
B
Due to the dependence of vt on gt , evaluating A becomes tricky (compared to the non-adaptive SGD setting). We use a common trick with adaptive methods (Zaheer et al., 2018) of introducing a conditionally independent quantity v̂t given xt : 1 A = −ηE √ ⟨∇F (xt ), gt ⟩ | xt vt + ζ 1 1 1 √ √ = −ηE − + ⟨∇F (x ), g ⟩ | x √ t t t vt + ζ v̂t + ζ v̂t + ζ η 1 1 √ √ =− E [⟨∇F (xt ), gt ⟩ | xt ] + ηE −√ ⟨∇F (xt ), gt ⟩ | xt vt + ζ v̂t + ζ v̂t + ζ η 1 1 2 = −√ ⟨∇F (xt ), gt ⟩ | xt ∥∇F (xt )∥ + ηE √ −√ , vt + ζ v̂t + ζ | v̂t + ζ {z } C
(74)
where we used in the last equation the unbiasedness of the stochastic gradient estimator gt = g(xt ; ξt ). The first term is negative, so we need to only upper bound the second term C . Using v̂t = βvt−1 , we get: 40
On Adaptivity in Zeroth-Order Optimization
√ √ vt − v̂t √ ⟨∇F (xt ), gt ⟩ √ ( v̂t + ζ)( vt + ζ) vt − v̂t √ √ = ⟨∇F (xt ), gt ⟩ √ √ ( v̂t + ζ)( vt + ζ)( vt + v̂t )
C =
= (a)
≤
= (b)
≤
(75) (76)
(1 − β)γt2 p p p √ ( βvt−1 + ζ)( vt + ζ)( βvt−1 + (1 − β)γt2 + βvt−1 ) ! (1 − β)γt2 p ⟨∇F (xt ), gt ⟩ p √ ( βvt−1 + ζ)( vt + ζ)( (1 − β)γt2 ) ! p (1 − β)γt p ⟨∇F (xt ), gt ⟩ √ ( βvt−1 + ζ)( vt + ζ) ! p (1 − β)γt p G ∥gt ∥ ( βvt−1 + ζ)ζ
! ⟨∇F (xt ), gt ⟩
(77)
(78)
(79)
(80)
where (a) is due to dropping positive terms in the denominator and (b) follows from the Cauchy–Schwarz inequality and the global Lipschitz property. Plugging back we get:
A = −p ≤ −p
η
2
βvt−1 + ζ η
∥∇F (xt )∥ + ηE
h
C | xt
"
p
2
(1 − β)γt
(81) !
#
p G ∥gt ∥ | xt ( βvt−1 + ζ)ζ ! p (69) (1 − β) η 2 2 p ≤ −p ∥∇F (xt )∥ + η G σ02 + (σ12 + 1) ∥∇F (xt )∥ βvt−1 + ζ ( βvt−1 + ζ)ζ √ √ 2 η Gσ02 1 − β G(σ1 + 1) 1 − β 2 =p − 1 ∥∇F (xt )∥ + ζ ζ βvt−1 + ζ βvt−1 + ζ
∥∇F (xt )∥ + ηE
i
(82)
(83) (84)
As for the B term, we use the fact vt ≥ βvt−1 ≥ 0 and the affine variance bound to get:
" Eξt
# " # 2 2 ∥gt ∥ ∥gt ∥ | xt ≤ Eξt p | xt √ ( vt + ζ)2 ( βvt−1 + ζ)2 h i 1 2 Eξt ∥gt ∥ | xt ≤ p ( βvt−1 + ζ)ζ
(85) (86)
2
≤
σ02 + (1 + σ12 ) ∥∇F (x)∥ p ( βvt−1 + ζ)ζ
Plugging A and B : 41
(87)
On Adaptivity in Zeroth-Order Optimization
η
Eξt [F (xt+1 )|xt ] ≤ F (xt ) + p βvt−1 + ζ
√ √ G(σ12 + 1) 1 − β Gσ02 1 − β 2 − 1 ∥∇F (xt )∥ + ξ ξ 2
Lη 2 σ02 + (1 + σ12 ) ∥∇F (x)∥ p (88) 2 ( βvt−1 + ζ)ζ √ √ 2 G(1 + σ12 ) 1 − β Lη η ∥∇F (xt )∥ G 1−β Lη ησ02 p p = F (xt ) + −1+ + + ζ 2ζ ζ 2ζ βvt−1 + ζ βvt−1 + ζ (89) +
2
(70)
≤ F (xt ) −
η ∥∇F (xt )∥ ησ02 p + p 2 βvt−1 + ζ 2 βvt−1 + ζ
(90)
2
γ≤G
≤ F (xt ) −
η ∥∇F (xt )∥ ησ 2 √ + 0 2ζ 2( βG + ζ)
(91)
Re-arranging, taking the full expectation, and telescoping yields:
2
√
T −1 h i X ησ 2 η 2 E ∥∇F (xt )∥ ≤ F (x0 ) − E [F (xT )] + T 0 2ζ βG + ζ t=0
(92)
Which yields the desired result: T −1 i p F (x ) − F ∗ σ2 1 X h 0 2 E ∥∇F (xt )∥ ≤ 2 βG + ζ + 0 T t=0 ηT 2ζ
H.5. Proof of Theorem 4.7 Using Theorem 4.4, we can now show the main result (restated below): Theorem H.6 (MEAZO - Restated). Under Assumptions 4.1, 4.2, and 4.3, define 2d − 1 4d − 1 dε2 L2 2 (8 + d) + + 1 σ2 , σ12 = . σ0 = 2q q q If the parameters β, η, ζ satisfy
√ G(1 + σ12 ) 1 − β Lη 1 max , ≤ , ζ 2ζ 4
(93)
then after T iterations of Algorithm 1 with u ∼ Uniform(S), we have T −1 i 1 X h F (x0 ) − F ∗ σ02 α 2 2 2 E ∥∇F (xt )∥ ≤ 2α + +ε L +2 , T t=0 ηT 2ζ ηT where α =
√
βG + ζ.
Proof. To prove the main result, we need to show that the conditions in Theorem 4.4 are met, and then apply Theorem 4.6 to map the guarantee back to F . By Lemma G.5, both fε (·; ξ) and Fε are L-smooth. Likewise, by Lemma G.4, both fε (·; ξ) and Fε are G-Lipschitz. For the d ZO estimator in (32), we have the smoothing distribution to be the unit ball v ∼ Uniform(B), which implies C = d+2 . By Lemma H.4 we have h i ˆ εq (x; ξ) = ∇Fε (x), Eξ,Uq ∇f 42
(94)
On Adaptivity in Zeroth-Order Optimization
and
Eξ,Uq
ˆ εq (x; ξ) − ∇Fε (x) ∇f
2
≤
dε2 L2 (8 + d) + σ 2 2q | {z σ02
4d − 1 2d − 1 2 +1 + ∥∇Fε (x)∥ . q q } | {z }
(95)
σ12
Let γt be the tracked statistic in MEAZO:
q
γt =
1 X f (xt + εui ; ξt ) − f (xt − εui ; ξt ) q i=1 2ε
(96)
We have:
q
1 X f (xt + εui ; ξt ) − f (xt − εui ; ξt ) 0 ≤ γt ≤ q i=1 2ε q G-Lipschitz 1 X G ∥2εu ∥ i ≤ q i=1 2ε ui ∈ S 1
=
q X
q i=1
G
(97) (98) (99)
=G
(100)
Thus, we check for the condition:
h
Eξt ,Uq γt
v u i Holder’s v 2 u u q 2 q ˆ ˆ ∇fε (xt ; ξt ) | xt ≤ uEξt ,Uq γt | xt uEξt ,Uq ∇fε (xt ; ξt ) | xt u| {z }u u| t {z } t A B 43
(101)
On Adaptivity in Zeroth-Order Optimization
Conditioning on xt , we first upper bound A :
!2 q X 1 f (x + εu ; ξ ) − f (x − εu ; ξ ) t i t t i t A = Eξt ,Uq q i=1 2ε " 2 # f (xt + εu; ξt ) − f (xt − εu; ξt ) variance of mean of i.i.d. rule 1 Eξ ,u = q t 2ε " 2 # Lemma G.3 1 εL ≤ Eξ ,u |⟨∇f (xt ; ξt ), u⟩| + q t 2 (a+b)2 ≤2a2 +2b2 2 ε2 L2 2 ≤ Eξ ,u ⟨∇f (xt ; ξt ), u⟩ + q t 4 h i ε2 d2 L2 d≥1 2d2 2 ≤ Eξt ,u ⟨∇f (xt ; ξt ), u⟩ + q 2q h h ii ε2 d2 L2 2d2 2 Eξt Eu∼Uniform(S) ⟨∇f (xt ; ξt ), u⟩ | ξ + = q 2q h i ε2 d2 L2 2d 2 Eξ ∥∇f (xt ; ξt )∥ + = q t 2q ε2 d2 L2 Variance Bound 2d 2 ≤ ∥∇F (xt )∥ + σ 2 + q 2q ε2 d2 L2 Lemma G.8 2d 2 ≤ 2 ∥∇Fε (xt )∥ + 2ε2 L2 + σ 2 + q 2q 2 2 dε L 2d 4d 2 = (8 + d) + σ 2 + ∥∇Fε (xt )∥ 2q q q q≥1 dε2 L2 2d − 1 4d − 1 2 ≤ (8 + d) + σ 2 +1 + + 1 ∥∇Fε (xt )∥ 2q q q From the affine variance bound we derived, we have dε2 L2 2d − 1 4d − 1 2 B ≤ (8 + d) + σ 2 +1 + + 1 ∥∇Fε (xt )∥ 2q q q
(102)
(103)
(104) (105) (106) (107) (108) (109) (110) (111) (112)
(113)
Combining the two bounds, we obtain the condition: h i dε2 L2 2d − 1 4d − 1 2 q 2 ˆ Eξt ,Uq γt ∇fε (xt ; ξt ) | xt ≤ (8 + d) + σ +1 + + 1 ∥∇Fε (xt )∥ . 2q q q | {z } | {z } σ02
(114)
σ12 +1
d By our choice of β, η, ζ, we have satisfied the conditions required by Theorem 4.4. Applying Theorem 4.6 with C = d+2 ≤1 yields: √ T −1 i p F (x0 ) − F ∗ 1 X h σ02 βG+ζ 2 2 2 E ∥∇F (xt )∥ ≤ 2 β G + ζ + +ε L +2 . T t=0 ηT 2ζ ηT
44
On Adaptivity in Zeroth-Order Optimization
H.6. Proof of Corollary 4.9 We provide the proof of Corollary 4.9 restated below: Corollary H.7 (MEAZO Convergence Rate - Informal). If the assumptions and conditions in Theorem 4.7 hold, then after T iterations of Algorithm 1 with u ∼ Uniform(S), the iterates satisfy T −1 F (x ) − F ∗ i 1 X h 0 2 E ∥∇F (xt )∥ ≤ O + σ2 + T t=0 ηT | {z } Standard FO rate
d 2 σ q |{z}
Cross-stochastic gradient noise
+
d2 2 ε q | {z }
,
ZO gradient estimation error
where the O(·) notation hides absolute constants independent of d, q, T, and σ 2 , and non-dominant terms in ε2 . Proof. Recall from that with σ02
dε2 L2 (8 + d) + = 2q
2d − 1 + 1 σ2 . q
+ 1, then notice that 1 + σ12 = 1 + 4d−1 = dq . Let dq := 4d−1 q q Theorem 4.7 gives T −1 i 1 X h 2 E ∥∇F (xt )∥ T t=0 √ p F (x0 ) − F ∗ σ2 βG+ζ ≤2 βG+ζ + 0 + ε2 L2 +2 ηT 2ζ ηT √ ∗ 2 2 p F (x0 ) − F 2 β G + ζ dε L 2d − 1 =2 βG+ζ + (8 + d) + + 1 σ2 ηT 2ζ 2q q √ βG+ζ 2 2 +ε L +2 ηT 2 F (x0 ) − F ∗ dε d2 ε2 d 1 2 2 =O +O + +O +1 σ +O ε +2 ηT q q q ηT F (x0 ) − F ∗ d 2 ε2 dε2 d2 ε2 =O + σ2 + O σ +O + ε2 + + ηT q ηT q q 2 F (x0 ) − F ∗ d d =O + σ 2 + σ 2 + ε2 , ηT q q
where we started by expanding σ02 and then dropped non-dominant terms in ε2 .
45
On Adaptivity in Zeroth-Order Optimization
H.7. An Alternative Proof for ZO-SGD Using the same proof technique for MEAZO, we provide here an alternative proof for ZO-SGD. We first show this basic result for affine variance-bounded SGD: Theorem H.8 (SGD with Affine Variance Bound). Let F : Rd → R be the population loss defined as F (x) = Eξ∼D [f (x; ξ)] , where each individual sample loss f (x; ξ) is L-smooth. Assume that F is bounded from below by F ∗ , and that for stochastic samples ξ ∼ P, we have access to an unbiased sample gradient estimator that satisfies: h i 2 2 Eξ ∥g(x; ξ) − ∇F (x)∥ ≤ σ02 + σ12 ∥∇F (x)∥ Consider the SGD update: xt+1 = xt − ηg(xt ; ξt ), with constant step size η > 0. If we run SGD with η < (1+σ2 2 )L for T iterations, we have: 1
T −1 i D 1 X h Lησ02 2 + E ∥∇F (xt )∥ ≤ T t=0 2 − Lη (1 + σ12 ) ηT 1 − Lη (1 + σ 2 ) 2
(115)
1
where D = F (x0 ) − F ∗ > 0.
Proof. Define gt = g(xt ; ξt ), and consider the descent lemma at iteration t: F (xt+1 ) ≤ F (xt ) − η ⟨∇F (xt ), gt ⟩ +
Lη 2 2 ∥gt ∥ 2
(116)
Taking the expectation conditioned on xt : h i Lη 2 2 Eξt [F (xt+1 )|xt ] ≤ F (xt ) − ηEξt [⟨∇F (xt ), gt ⟩ | xt ] + Eξt ∥gt ∥ | xt 2 h i Lη 2 2 2 Eξt ∥gt ∥ | xt = F (xt ) − η ∥∇F (xt )∥ + 2 affine var. bound Lη 2 2 2 2 σ0 + (1 + σ12 ) ∥∇F (xt )∥ ≤ F (xt ) − η ∥∇F (xt )∥ + 2
(117) (118) (119)
Taking the full expectation yields: h i Lη 2 σ 2 Lη 2 0 1 + σ12 − 1 E ∥∇F (xt )∥ + 2 2
(120)
h i Lη 2 σ 2 Lη 2 0 1 + σ12 − 1 E ∥∇F (xt )∥ + 2 2
(121)
E [F (xt+1 )] ≤ E [F (xt )] + η Summing over t = 0, · · · , T − 1 and telescoping:
E [F (xT )] − F (x0 ) ≤
T −1 X t=0
η
46
On Adaptivity in Zeroth-Order Optimization
Assume 1 −
Lη(1+σ12 ) >0 2
2 =⇒ η < L(1+σ 2 ) , then dividing by T and re-arranging implies: 1
Lη 2 σ 2
T −1
0 1 X F (x0 ) − E [F (xT )] 2 2 + E [∥∇F (xt )∥] ≤ T t=0 ηT 1 − Lη (1 + σ 2 ) η 1 − Lη (1 + σ 2 )
1
2
(122)
1
2
=
Lησ02 F (x0 ) − E [F (xT )] + 2 − Lη (1 + σ12 ) 2 ηT 1 − Lη 2 (1 + σ1 )
≤
Lησ02 + 2 − Lη (1 + σ12 ) 2 ηT 1 − Lη 2 (1 + σ1 )
(124)
=
Lησ02 + 2 − Lη (1 + σ12 ) 2 ηT 1 − Lη 2 (1 + σ1 )
(125)
(123)
F (x0 ) − F ∗
D
Theorem H.9 (ZO-SGD). Let F : Rd → R be the population loss defined as F (x) = Eξ∼D [f (x; ξ)] , where each individual sample loss f (x; ξ) is L-smooth. Assume that for stochastic samples ξ ∼ D, the variance of the sample loss gradient satisfies h i 2 Eξ ∥∇f (x; ξ) − ∇F (x)∥ ≤ σ 2 . At iteration t, the gradient is approximated by the (32) with Uniform perturbations. Consider the ZO-SGD update: ˆ q (xt ; ξt ), xt+1 = xt − η ∇f ε with constant step size η > 0 and smoothing parameter ε > 0. Define 2d − 1 dε2 L2 σ02 = (8 + d) + + 1 σ2 , 2q q
σ12 =
4d − 1 . q
If we run SGD with η < (1+σ2 2 )L for T iterations, we have: 1
T −1 i ∗ 2 1 X h F (x ) − F Lησ 1 0 2 0 + + 2 E ∥∇F (xt )∥ ≤ + ε2 L2 T t=0 2 − Lη (1 + σ12 ) ηT 1 − Lη (1 + σ 2 ) 2LT η 1 − Lη (1 + σ 2 ) 1
2
2
1
(126) Proof. To prove the result for ZO-SGD, we need to show that the conditions in Theorem H.8 are met for the smoothed ˆ εq (x; ξ), and then apply Theorem H.2 to map the guarantee back to F . function Fε with ZO gradient estimate ∇f Step 1: Affine bound on the smoothed functions gradient. By assumption, sample loss functions f (·; ξ) are L-smooth and their gradient satisfies the variance bound w.r.t. the population loss gradient ∇F (·). So we can prove the affine variance ˆ εq (x; ξ) w.r.t. Fε by Lemma H.4, that is bound for ∇f h i ˆ εq (x; ξ) = ∇Fε (x), Eξ,Uq ∇f (127) and Eξ,Uq
ˆ q (x; ξ) − ∇Fε (x) ∇f ε
2
dε2 L2 ≤ (8 + d) + σ 2 2q | {z σ02
47
2d − 1 4d − 1 2 +1 + ∥∇Fε (x)∥ . q q } | {z } σ12
On Adaptivity in Zeroth-Order Optimization
Step 2: Convergence w.r.t. the smoothed population loss. By Lemma G.5, both fε (·; ξ) and Fε are L-smooth. Let us set η < (1+σ2 2 )L . So one can apply Theorem H.8, with the above (smoothed) stochastic gradient variance bound, to prove 1 the convergence of SGD w.r.t. Fε T −1 i 1 1 X h Lησ02 2 (Fε (x0 ) − Fε∗ ) + E ∥∇Fε (xt )∥ ≤ . T t=0 2 − Lη (1 + σ12 ) 2 ηT 1 − Lη | {z } 2 (1 + σ1 ) | {z } K1 K0
Step 3: Convergence w.r.t. the population loss. As the sample loss f (·, ξ) are L-smooth, the population loss F is L-smooth too. For the h ZOiestimator in (32), we have the smoothing distribution to be the unit ball v ∼ Uniform(B), which 2
implies C = Ev∼B ∥v∥
d d = d+2 . Therefore, from Theorem H.2 with C = d+2 ≤ 1, σ02 , σ12 , K0 and K1 as above, we get
2 after T iterations of ZO-SGD with η < L(1+σ 2) : 1
T −1 i ∗ 2 1 X h F (x ) − F Lησ 1 0 2 0 + + 2 . E ∥∇F (xt )∥ ≤ + ε2 L2 T t=0 2 − Lη (1 + σ12 ) ηT 1 − Lη (1 + σ 2 ) 2Lη 1 − Lη (1 + σ 2 ) 2
1
2
1
A useful sanity check is that, in the limit where q → ∞ (eliminating ZO variance) and ε → 0 (eliminating ZO bias), our bound reduces exactly to the classical SGD guarantee for L-smooth objectives with variance-bounded noise (Equation (2.4) of (Ghadimi & Lan, 2013)): T −1 i 1 X h F (x0 ) − F ∗ Lησ 2 2 + E ∥∇F (xt )∥ ≤ . T t=0 2 − Lη ηT 1 − Lη 2
48