FZOO: Fast Zeroth-Order Optimizer for Fine‑Tuning Large Language Models towards Adam‑Scale Speed
Authors: Sizhe Dang
yangyangGuo
Yanjun Zhao
Xiaodong Zheng
Guang Dai
Ivor Tsang
Haishan Ye
Venue: ICLR 2026 Poster (2026)
Keywords: Zeroth‑order optimization
Large language models
Fine‑tuning
Adaptive step size
Batch gradient estimation
Memory efficiency
Primary area: foundation or frontier models, including LLMs
TL;DR: FZOO achieves fine‑tuning speed within the same order of magnitude as Adam for LLMs while using only inference‑level GPU memory.

Abstract: Fine-tuning large language models (LLMs) often faces GPU memory bottlenecks: the backward pass of first-order optimizers like Adam increases memory usage to more than 10 times the inference level (e.g., 633~GB for OPT-30B). Zeroth-order (ZO) optimizers avoid this cost by estimating gradients only from forward passes, yet existing methods like MeZO usually need tens of times more steps to converge. Can this trade-off between speed and memory in ZO be fundamentally improved? Normalized-SGD, for instance, demonstrates strong empirical performance with greater memory efficiency than Adam. In light of this, we introduce FZOO, a Fast Zeroth-Order Optimizer towards Adam-Scale Speed. On the one hand, FZOO reduces the total forward passes needed for convergence by employing batched one-sided estimates that adapt step-sizes based on the standard deviation of batch losses. On the other hand, it accelerates per-batch computation through the use of Rademacher random vector (±1) perturbations, which also enables further speedups through batched evaluation. Extensive experiments on diverse models (including RoBERTa-large, the OPT family (350M-66B), Phi-2, and Llama3) across 11 varied downstream tasks validate FZOO's effectiveness. On average, FZOO outperforms MeZO by +3% in accuracy while requiring 3$\times$fewer forward passes. Notably, for the RoBERTa-large model, FZOO achieves average improvements of +5.6% in accuracy and 18$\times$reduction in forward passes compared to MeZO, achieving convergence speeds comparable to Adam. We also provide theoretical analysis proving FZOO’s formal equivalence to a normalized-SGD update rule and establishing its convergence guarantees. Beyond full-parameter tuning, FZOO plugs smoothly into PEFT techniques, unlocking even larger memory savings. Taken together, our results make single-GPU, high-speed, full-parameter fine-tuning realistic today and point toward future work on memory-efficient pre-training. Code: https://github.com/DKmiyan/FZOO

Published as a conference paper at ICLR 2026
FZOO: FAST ZEROTH-ORDER OPTIMIZER FOR FINE- TUNING LARGE LANGUAGE MODELS TOWARDS
ADAM-SCALE SPEED
Sizhe Dang,, Yangyang Guo", Yanjun & Xiaodong Zheng
Xi'an Jiaotong University fdarknightl118, yangyangguo, yanjun.zhar zhao, xiaodongzheng) (stu. edu. on
Guang Dai
Ivor Tsang
SGIT AI Lab, State Grid Corporation of China guang gmmal com
CFAR and IHPC, Agency for Science, Technology and Research (A*STAR) Ivor sooo__tsaggaasseee edu.sg
Haishan Yet
Xi'an Jiaotong University & SGIT AI Lab, State Grid Corporation of China yehaishanéxjtu.
wdw.iitt.eeuu.coom... edu.on
ABSTRACT
Fine-tuning large language models (LLMs) often faces GPU memory bottlenecks: the backward pass of first-order optimizers like Adam increases memory usage to more than 10 times the inference level (c.g., 633 GB for OPT-30B). Zeroth-order (ZO) optimizers avoid this cost by estimating gradients only from forward passes, yet existing methods like MeZO usually need tens of times more steps to converge. Can this trade-off between speed and memory in ZO be fundamentally improved? Normalized-SGDI for instance, demonstrates strong empirical performance with greater memory efficiency than Adam. In light of this, we introduce FZOO, a Fast Zeroth-Ordes Optimizer towards Adam-Scale Speed. On the one hand, FZOO reduces the total forward passes needed for convergence by employing batched one-sided estimates that adapt step-sizes based on the standard deviation of batch losses. On the other hand, it accelerates per-batch computation through the use Rademacher random vector (=1) perturbations, which also enables further speedups through batched evaluation. Extensive experiments on diverse models (including RoBERTa-large, the OPT family (350M-66B), Phi-2, and Llama3) across varied downstream tasks validate FZOO's effectiveness. outperforms MeZO by +3% in accuracy while requiring xx fewer forward passes. Notably, for the RoBERTa-large model, FZOO achieves average improvements of +5.6% in accuracy and 18x reduction in forward passes compared to MeZO, achieving convergence speeds comparable to Adam. We also provide theoretical analysis proving FZOO's formal equivalence to normalized-See SGD update rule and establishing its convergence guarantees, Beyond full-parameter tuning, FZOO plugs smoothly into PEFT techniques, unlocking even larger memory savings. Taken together, our results make single-GPU, high-speed, full- full-parameter fine- uning realistic today and point toward future work on memory-efficient pre- training. Code: https:: thtbb thub. com Satn///Kiyyaa/aaaa
average, FZOO
INTRODUCTION
Large language models (LLMs) have become the workhorse of natural-language and multi-modal applications (Devlin et al., 2019; Gururangan al., 2020; Ouyang et al., 2022), yet they often require
Equual contribution. This work was completed at SGIT AI Lab, State Grid Corporation of China. "orresponning author.

---

Published as a conference paper at ICLR 2026
RoBEnTa-large On MNLI
ROBERTH- On RTE
RoBERTa-large On SNLI
107
MeZ0 Adam
M+70
10"
M.20
10"1
10"1
F200
10-1
Adam
Adam
10
30"
10
10
10
10-1
10-4
10
10
10"
500
1500 1750
250
1000
500
1500 1750
Forward Steps(X100)
Forward StepsiX100)
Forward StepsiX190)
Figure 1: Performance of MeZO, Adam and FZOO on different tasks when fine-tuning RoBERTa- large model. For the sake of uniform comparison, we convert Adam's 's backward pass into 3 forward passes. FZOO is 18x faster than MeZ0 in forward steps, and Adam 20x faster than Me70.
additional fine-tuning to excel on downstream tasks. Current practice relies on first-order optimizers such as Adam (Kingma Ba, 2015), whose backward pass stores all activations and gradients, linearly multiplying the memory cost-fine-tuiig an OPT-30B model then consumes 633 GB of GPU memory, more than 10x its inference memory cost. This creates the memory wall that now limits model training in resource-constraine
scenarios.
Two main strategies have been explored to overcome this wall. Purameter-efficent tuning (PEFT) (Hu et al., 2022; Li & Liang, 2021; Dettmers et al., 2023; Zhao et al., 2024; Pan et al., 2024) (e.g., LoRA (Hu et al., 2022)) updates only a small subset of weights and thus lowers memory cost, but it still requires the backward pass and can lag full-parameter tuning (FT) on some difficult tasks. The other approach turns to zeroth-order (ZO) optimization (Malladi et al., 2023; Zhao et al., 2025c): methods such as Me7O (Malladi al., 2023) use multiple forward passes to replace the backward pass when estimating gradients. This brings the memory overhead of fine-tuning down to the inference level, but this benefit comes with significant trade-off in speed, as convergence is often about 20x slower than Adam on RoBERTa-large (Figure I). Does the use of zeroth-order methods always lead to a trade-off between speed and memory?
We believe the answer is no. This is because ZO performance can be substantially enhanced in three key areas: (i) Adaptive Step-Sizes. While Adam uses costly momentum for adaptive steps, normalized-SGD adapts efficiently via gradient normalization without this overhead. Existing 70 methods, however, use inefficient fixed step-sizes for LLM fine-tuning. (ii) Efficient perturbation. Furthermore, each ZO gradient estimate typically requires multiple forward queries. However, the overall speed of this multi-query process is limited by the cost of conventional perturbation sampling (e.g.. Gaussian noise); because many perturbations must be generated, this compute does not diminish even with batched execution, and can not utilize hardware parallelism. (iii) Engineering Optimization. Theoretically, one Adam step is twice as fast as MeZO step (Adam's backward pass takes roughly three times longer than a forward pass (Alman & Song, 2024), making Adam equivalent to four forward passes versus McZO's two). Yet, due to insufficient forward pass optimizations, McZO's s actual per-step exccution often exceeds Adam's ss Taken together. these observations suggest that a well-engineered ZO optimizer could achieve Order-of-magnitudde Adam-like convergence speed with inference-level memory cost.
To harness these opportunities for ZO enhancement, we introduce FZOO, a Fast Zeroth- Order Optimizer. FZOO achieves its significant speed-up up through two primary strategies: First, it reduces total convergence passes by employing batched one-sided estimates, where the standard deviation of batch losses informs an adaptive step-size rule. Second, it accelerates each batch computation using efficient Rademacher random-vector perturbations (=),,, enabling batched parallelism for query evaluations. Specifically, our contributions are:
1. FZOO, novel ZO optimizer that uniquely adapts principles from normalized-SOa to the ZO regime. is designed to move towards Adam-scale convergence speed while operating at inference-level memory usage.
2. We provide rigorous theoretical backing for FZOO, including formal proof of its equiv- alence to a normalized-Ser SGD update rule and a comprehensive analysis establishing its convergence guarantees under standard conditions.
2

---

Published as a conference paper at ICLR 2026
3. Extensive FT experiments diverse models (RoBERTa-lange, OPT family Phi-2, and Llama3) across 11 downstream tasks demonstrate FZOO's superior efficiency. On average, FZOO surpasses the MeZO baseline by +3% in accuracy with 3x fewer forward passes. Notably, as show in Fig. for the RoBERTa-large model achieves average improvements of +5.6 % in accuracy and an 18x reduction in forward passes compared to McZO, reaching effective convergence speeds comparable to Adam.
4. FZOO exhibits strong practical utility, smoothly integrating with PEFT techniques (Dettmers et al., 2022a;b) to unlock even larger memory savings. Furthermore, it effectively optimizes both differentiable and non-differentiable objectives during FT.
RELATED WORKS
We provide brief overview of first-order, zeroth-order and batch-based zeroth-order optimizers for large language models; see Appendix for details.
First-order adaptive methods Standard LLM optimizers include SGD and its refinements (Duchi et al., 2011) 1) like Adam (Kingma Ba, 2015), which uses memory-intensive momentum for its adaptive step-sizes. AdamW (Loshchilov & Hutter, 2019) improves generalization by refining weight decay. Inspiringly, methods like normalized-Se -SG (Bernstein et al., 2018) also adapt steps effectively, often rivaling Adam's performance but crucially without this significant momentum overhead, offering a key insight for our work.
Zeroth-order optimizers ZO methods sidestep back-prop by estimating gradients with only forward passes. The classic SPSA estimator (Spall, 1992) has powered applications from distributed con- trol (Tang al., 2021; Hajinezhad & Zavlanos, 2018) () black-box adversarial attacks (Chen et al., 2017; Cai et al., 2021; Liu et al., 2019a; Ye et al.. 2019). MeZO (Malladi et al., 2023) first showed that such forward-only updates can fine-tune LLMs high accuracy while cutting GPU memory by several times (up to 12x). HiZOO (Zhao et al., 2025c) augments MeZO with diagonal Hessian cues to accelerate convergence.A recent benchmark (Zhang et al., 2024) catalogues many other 7O estimators.
Batch-based zeroth-order optimizers batch-oris oriente refinement ZO methods estimates gra- dients by evaluating batch of forward step. Recent work like ReLIZO (Wang et al., 2024) reuses or correlates directions to boost sample efficiency. Augmented Random Search (Mania al., 2018) and Evolution Strategies (Sun al., 2022a;b) adopt similar copulation-baser updates. Notably, DeepZero (Chen et al., 2023) proposes a framework to scale up ZO optimization via coordinate-wist parallelization and feature reuse, which shares the similar philosophy of activation recycling with our work.
METHODS
In the following, first briefly review the classical zeroth-order gradient estimator employed in MeZO (Section 3.1). We then present the complete workflow of our FZOO optimizer (Section 3.2), shown in Figure 2, introduce parallel perturbation strategy that accelerates computation (Section 3.3), and finally offer theoretical analysis of the proposed method (Section 3.4, 3.5).
3.1 PRELIMINARIES
Consider labelled dataset D {(1,, !P and mini-batch B C. of size B. Let Rd denote all trainable parameters of the LLM, and let L(0; B3) be the empirical loss on B.
Definition 3.1 (Classical ZO gradient estimation). Given perturbation radius and Rd sampled as z ~ (O, Ia). Classical ZO estimates the gradient on B via
L( = L(0 ez; B) L(e ez; B) z
22
VL(O:
(I)
2e Averaging equation 1 over i.i.d. draws {2)] yields the n-ZO estimator v = N V.L.
Computational cost. A single ZO estimate needs exactly two forward passes and does not store activations for backpropagation. Me70 keeps memory usage the inference level by passing random
3

---

Published as a conference paper at ICLR 2026
Algorithm FZOO
Require: parameters 0 E R loss L IRd + I. step budget 7', perturbation scale batch size N, learning rate schedule {m,
1: for t = 1..... do
2: L, 0, seeds < BuichPerturbbaramctterre&& e, N)
3: std < standard deviation of
4: projected sorrectedggraddeee +- (E L(0; B)) std)
5:
BuchhppannPPumnote(iprjeette
seeds, 0, m7c)
6: end for
7:
function BATCHPERTURRIPRRMMTTRRR
c, .N)
8:
Sample batch B C D; obtain input X and first layer weights W())
9:
Initialize random seeds seeds {s!....,SN)
10:
Generate perturbation vectors u using seeds
11:
Compute unperturbed activations F(1) t w
Compute perturbed activations: y, <- F(1) + +((uxX,, i= I....,N
12:
Concatenate activations ( + [1) Y
13:
14:
for = 2, 3, ..... do
15:
F(i) t Wiily(i-1)
> Compute unperturbed activations at layer
p() <- c(ub(-1))
Compute perturbations layer D Compute perturbed activations in parallel at layer
17:
Y t F(5) pb) 18: end for
19: + L(Y(finat); B))
> Compute final losses in parallel
20: return 0, seeds
21: end function
22: function BATCHUUDATTPPRRRPTTRRRRRP
seeds, 0, 1))
23:
for idæ. 8 E enumerat e (seeds) do
Reset random number generator with seed 25: for 0, E 0 do
For sampling
Uniform Uniform((+1,-11)
27:
8, - 0; projected lecjected_grrdddd
28:
end for
29:
end for
30:
end function
seeds instead of full perturbation z. McZO further observes that choosing N > improves statistical stability but increases computation by factor of N; therefore it fixes N 1.
From Classical ZO to ZO-SGD. Replacing the prok-ppoon gradient in SGD with the Classical ZO estimate gives the geroth-order update 0.+1 0 т) L (.): McZO realises this update in-place with the memory tricks above and serves the baseline for our forthcoming improvements.
3.2 FAST ZEROTII-ORDE OPTIMIZATION
MeZO employs fixed learning Instead, FZOO dynamically tunes its step size using the standard deviation of loss values gathered from multiple forward passes within each mini-batch. For the enhanced computational efficiency, FZOO also incorporates a one-sided gradient estimation strategy and we first utilize Rademacher random vectors for perturbations. Letting u1...., uN be N i.idd Rademacher random vectors (u has the same shape as each layer's weight W(i),, we construct our gradient estimation by function value queries
4
L(O, eu;; B.), and to L(0r;
That is, the gradient estimate is then computed by averaging one-sided difference estimates
N Σ (1: 1o)4.
9: = eN
(2)
1=1
4

---

Published as a conference paper at ICLR 2026
0 Eli
F000
Loss
Loss
Estimate gradient
BitPerturb
44 -Uniform((+L -11, -1})
Loss
Layer_ I
Layer 2
Layer N
Calculation Per layer
Loss
Fixed part(share)
Input
Loss
Layer_
Layer
Layer_N
Perturbed part
Figure Structure of the of FZOO. The bottom half depicts the toy example of the efficient implementation of batched forward passes.
The estimated variance of is computed as:
of
4
1 N
Σ
4
(3)
Our FZ00 updates the parameters according to equation 2 and equation 3:
0.+1 0:
(4)
a
where 7/ the step size. The detailed implementation of FZOO listed Algorithm 1.
The equation 4 shows that FZOO receives larger steps flat regions (where is small) and smaller steps at steep regions, mirroring Adam-style adaptivity while keeping memory at the inference level.
3.2.1 MOVTIVATION OF FZOO
Adaptive first-order methods often estimate local curvature to scale updates. Similar adaptivity can be achieved by methods like normalized-SGD (Bernstein al., 2018), which adjusts step sizes by normalizing the gradient, making it more memory-efficient compared to Adam. The parameter update follows normalized-SGD:
Jt
0++1 = 0, 'e
(5)
FZOO is inspired by normalized-SGni Proposition 3.2 shows that of 1g.l2.e2. NN- which implies that FZOO is an extension normalized-SGID to the 70 domain.
e2.
N-1
Variants. FZOO-R re-uses half of the losses from the previous mini-batch: o, Sta(( U ()) achieving a full-batch variance estimate with only half the forward evaluations.
3.3 EFFICIENT IMPLEMENTATION OF BATCHED FORWARD PASS
separate forward pass, which cannot The original ZO pipeline applies perturbation and then take advantage of batch parallel computing. For layer j we split the computation into an unperturbed part FÚ) and a perturbation part p()) Using Gaussian noise forces two full matrix-vector products, so batching recovers little speed-up. Replacing the noise with Rademacher vector(#:1) u, changes only the sign bits: p() is produced by bit-level sign flip that degenerates into single add / subtract, so the kernel issues additions instead of a second metrix-vector multiply, making markedly faster because addition is cheaper than multiplication (Williams al., 2009; Chen et al., 2020).

---

Published as a conference paper at ICLR 2026
Let X be the input and let WD) denote the weight matrix of layer j. For the first layer compute
F(4) X, r F (u,X), ) ,,,,,
and we stack the perturbed outputs along the batch dimension: y = [M ( 1
Let y(--)) be the concatenated activations from the previous layer and U diag diag(U1... ........ UN) the block-diagonal sign matrix that broadcasts the u; across the batch axis. For subsequent layers
(j 2 2) we compute
pO) wúy
pld) e (UYÚ-1)
yτ F() + p())
By executing the N per-layer matrix multiplications in parallel, the wall-clock time is reduced by factor compared with sequential evaluation. Combining advantage of parallel computing (p). Rademacher vector perturbations (r), and the one-sided estimator's halved forward count (f) yields the overall speed-up
x min(p:r)
OPT-125M with N 8, our batched scheme(minn(p;)) delivers a 1.92x speed-up over the "8 perturbations + 8 forward passes" baseline.
3.4 EQUIVALENCE TO NORMALIZED-SON
Proposition 3.2. Let the stochustic gradient estimation gt. defined in equation and the variance o defined in equation 3. Then it holds that
E |1 12
N
+ - N
[VL(
' and Yt O(e)
(6)
E [ =2 [V B))l + with S -(e))
(7)
Remark 3.3. Comparing equation and equation 6, and ignoring the perturbation terms Çr and Y (which are higher-order terms with respect to c), we can obtain that:
N + d 6 [o:]
E ||011]
N
Since N+d-1 -2 is a constant independent of the iteration number, gt. can be regarded as a kind N of normalized stochastic gradient, scaled by a constant factor. This theoretically establishes the connection between FZOO and normalized-SGD.
de
3.5 CONVERGENCE ANALYSIS
Assumption 3.4. Suppose that the loss function T.) is C-smooth, that is, for any 01, 02 E IRd,
holds that L(02) < L(e1) + (VL(0:), 02 01) + 102 - 0111
Assumption 3.5 (Bounded Variance). The stochastic gradient V (., B) has bounded variance:
| [3] < [|VL(0)112 + +
where 122 a constant. The above a standard assumption for stochastic gradient descent. Theorem 3.6 (Convergence of FZOO). Let the objective function L(0) be L-smooth, and Assump- tion 3.5 hold. The update rule 0.41 8 ni9t, where the effective step size тソt d: satisfies Iodz. and the learning rate factor 1) is set as 17 -/. Then, after T iterations, the FZOO algorithm satisfies:
1 T 47- (100)) L(0') + Σ [IVL(1))
AdLo, 222
&C 22
NdC 222
Σ
T [=1
VT
N
8N
2
[=l
where 8" denotes the optimal solution (minimum) of L(0), and a. = maxie(I.....) 0t-
This theorem shows that the FZO0 algorithm converges to stationary point whose gradient norm
close to zero. Especially, our thcorem shows that to find obtain + Σi, [[V < = with
[
E > 0, it requires T O(E²² which matches the convergence rate of stochastic gradient descent for nonconvex optimization.

---

Published as conference paper at ICLR 2026
Table 1: Experiments on RoBERTa-large (350M parameters, k=16). All reported numbers are averaged accuracy across 5 runs. In notations like (2 x M), M represents the memory overhead required for inference. All methods are evaluated under fixed forward-step budget aligned with McZO: 200k steps for RoBERTa-large and 40k steps for other models.
Task Type
SST-2
SST-5
SNLI
MNLI
RTE
TREC topic
Average
sentiment
natural language inference
Zero-shot
79.0
35.5
50.2
48.8
51.4
32.0
49.5
LP
76.0
40.3
66.0
56.5
59.4
51.3
58.3
HiZOO (2 x M)
93.2
46.2
74.6
64,9
66.8
79.8
70,9
ZO-Adam (3 x M)
90.3
38.8
69.1
59.2
61.4
52.4
61.7
(6 x M)
91.9
47.5
77.5
70.0
66.4
85.0
74.9
MeZO(prefix)
90.8
45.8
71.6
63.4
65.4
80.3
69.6
(iZ00(prefix)
92.3
47.2
68.8
61.6
65.4
82.0
69.6
F700(prefix)
92.9
43.7
70.8
67.0
64.6
82.8
70.3
Me7O
90.5
45.5
68.5
58.7
64.0
76.9
67.4
FZOO
93.3
47.6
75.9
64.9
67.9
78.8
71.4
4 EXPERIMENTS
Large language models (LLMs) fall into two architectural families. els-BERT (Devlin et al., 2019), ALBERT (Lan et al., 2020), etc.-tackle language understanding and are trained with masked-token objective (Section 4. 4). Decoder-only models GPT (Radford et al., 2019; Brown et al., 2020), OPT (Zhang et al., 2022), LLaMA (Touvron et al., 2023), Phi (Li al., 2023; Gunasckar et al., 2023), and others-focur on text generation and are trained autoregres- sively (Section 4.2). We benchmark FZO0 under fall-parameter fine-tuning on both model families, covering differentiable and non non-differentiabbe tasks (Section 4.3), report memory and wall-clock speed (Section 4.4), and compare it with standard ZO baselines (Section 4.5). Section 4.6 further shows that FZOO complementary to parameter-effictee 2021). For fair comparison with prior ZO baselines that do not employ batched perturbations, main experiments use the non-parallel variant in Algorithm and speed is reported as the number of forward passes.
Encoder-decoder mod-
methods such as prefix-tuning (Li & Liang,
llama33 On BooiQ
OPT-136 On Boold
Phi2 On BoolQ
MoZO
0.70
MaZO
0.05
FZOO
0.60
0.50
0.50
0.45
0.40
0.30
McZO
0.30
50
300
150
200
230
300
350
400
100
150
200
230
300
350
400
30
300
130
200
350
300
Forward StepsiX100)
Forword StepscX100)
Forward StepsiX3001
Figure 3: Training loss curves when using MeZO and FZOO to fine-tune different LLMs.
4.1 MASKED LANGUAGE MODELS
We perform experiments on RoBERTa-large (350M) (Liu al., 2019b) across three NLP task paradigms: sentence classification, multiple choice and text generation. Following the experimental setup (Malladi al., 2023), we investigate both few-shot and many-shot settings, sampling examples per class with & 16 (results in Table I) and l 512 (results in Appendix D.I).
According to prior analysis, the cost of a single backpropagation is roughly three times that of forward pass (Alman & Song, 2024), making each Adam update equivalent to four forward propagations. As shown in Figure 1, FZOO reduces loss significantly faster than MeZO, achieving an acceleration ratio of 18x. With additional 1.92 parallel speedup. FZOO potentially surpass Adam wall-clock efficiency. Moreover, its convergence rate closely approaches that of Adam, underscoring FZOO's strong training efficiency.

---

Published as a conference paper at ICLR 2026
Table 1 shows that when optimizing the RoBERTa-large model with MeZO and FZOO, the perfor- mance of FZO0 is on average 5.9% higher than that McZO on multiple datasets across different outperform outperforms McZO more than 10.7 % in both the SNLI and MNLI dataset, showing comparable performance to HiZOO.
NLP tasks. Specifically, FZOO
compaaaaaaa three different models (with 1000 examples) Classification (SST-2, RTE, CB. BoolQ, WSC, WIC, MultiRC); Multiple Choice (COPA, ReCoRD); Generation (SQuAD, DROP). We highlight the best results between MeZO, HiZOO-L and FZOO in bold to facilitate comparison.
Table 2: Experiments
Model
Method
SST-2
RTE
CB
BoolQ
WSC
WIC
MultiCC
COPA
ReCoRD
SQUAD
DROP
Average
Phi-2
Adam
84.4
61.6
79.0
68.8
59.6
67.7
77.8
84.0
68.7
90.4
41.1
71.2
Phi-2
McZO
86.6
67.1
75.0
72.4
59.6
54.4
78.2
86.0
71.7
85.7
37,8
70.7
68,9
75.2
72.1
36.2
Phi-2
FZOO
87.4
70.4
83,9
79.3
61.5
56.7
81.3
86.0
72.0
86.7
37.4
73.0
Llama3
Adam
94.6
80.7
94.6
83.3
64.4
71.6
84.7
89.0
86.9
89.7
58.4
81.6
Llama3
McZO
92.2
74.4
69.6
76.7
63.5
57.8
77.6
88.0
85.6
86.7
57.1
75.4
HiZ00-L
75.1
77.1
85.6
87.7
49.4
75.2
Llama3
FZOO
94.3
77.6
69.6
81.8
65.4
60.8
81.5
88.0
85.3
87.9
56.5
77.2
OPT-13B
Adam
92.1
79.1
71.4
77.0
63.5
69.6
76.2
88.0
81.0
84.5
31.3
74,0
OPT-13B
McZO
91.4
66.1
66.0
67.6
63.5
59.4
57.3
88.0
81.7
84.7
30.9
68.8
OPT-13B
HiZ0O-L
92.1
68,2
67.9
81.1
63.6
22.7
67.0
OPT-13B
F2O0
93.7
71.1
69.6
72.2
63.5
60.5
66.0
87.0
81.0
84.8
28.7
70.7
4.2
OUTO-REGRESSIVE LANGUAGE MODELS
Next, we expand the scope of our experiments by testing the Phi-2(2.7B), Llama3(8B) and OPT(13B) models the same NLP tasks. The results of the experiment in Table 2 show that FZOO outperforms MeZO in most cases, with an average accuracy increase of 2.75%. Aside from the ReCoRD and DROP datasets, FZOO surpasses MeZO in nearly all other cases.
FZOO significantly accelerates convergence speed during fall-parameter tuning, As shown in Figure FZOO only achieves 8x speedup over Me70 on average in the context of full parameter tuiing, but also has lower training loss. In addition, FZOO ultimately achieved a higher absolute accuracy improvement of 7.4% than McZO on the BoolQ task.
FZOO is able to adapt to large models with up to 66B parameters and maintains excellent performance. As shown in Table 3, on the OPT-66B model, FZOO outperforms MeZO with up to 13.2% % increase and 2.43% % increase on average.
4.3 TRAINING WITH KON-DIFFERENTIBLE OBJECTIVES
Our proposed FZOO estimates the gradient by performing multiple forward propagation processes, so the objective function can be non-differentiable function. Based on the MeZO (Malladi et al., 2023) setup. conduct some experiments using F1 the optimization objective. As shown in Table 4. FZOO performs consistently well across OPT models of different scales, surpassing both McZO and HiZ0O-L, and achieving average Fl improvement of 5.53% over McZO.
Table 4: Non-differentiable optimization objectives Table 3: Experiments the OPT-30B and OPT-66B (both of them use FT).
(F1): : Performance on the SQuAD.
Task
SST-2
RTE
WSC
WIC
Average
Model
OPT
30B McZO
63.5
Size
125M
1.3B
2.7B
6.7B
13B
Average
30B HiZ0O-L
00.3
69.3
63.5
53.4
69.3
3R F700
91.2
69.3
63.5
60.2
71.1
Zero-shot
9.7
27.2
29.9
36.6
46.2
29.9
66B McZO
91.2
65.7
63.5
58.9
69.8
MeZO
44.1
72.2
77.6
80.1
78.5
70.5
6GB HiZ0O-L
88.9
66.4
59.6
HiZ00-I.
37.6
79.5
69.7
66R F700
93.6
74.4
58.6
59.2
71.5
FZOO
$1.0
74.6
81.8
79.8
84.7
74.4
4.4 MEMORY USAGE AND TIME EFFICIENCY ANALYSIS
Memory Usage As shown in Figure 4, FZOO and MeZO have the same inference-level memory and do not need to store additional content like HiZOO. Even if Adam is trained with PEFT like prefix, it still requires several times more memory than FZOO.
8

---

Published as a conference paper at ICLR 2026
Zero-shot
Table 5: Wallclock time per step between Adam, McZO and FZOO(N=8). See Ap-
ICL
Adam
Memory (GB)
Adlmn(prefii) HiZOO
33x
pendix F for more.
100
F200
Method
OPT-125M
RoBERTaalarge
Adam
0.1982s
0.3930s
0.5814s
10
MeZO
0.1368s
0.4305%
0.7218s
FZOO
0.3835s
0,6052s
1 1.6628s
Table 6: Actual and potential speedup of FZOO for different tasks. Adam commonly achieves 20x speedup than MeZO.
#Farameters
Figure 4: GPU memory consumption with different OPT models and tuning methods on MultiRC (400 tokens per example on average). More details can found in Appendix E.
Task
SNLI
COPA
WIC
CB
FZOO
20x
10x
9x
8x
Potential
40x
20x
18x
16x
Time Efficiency Adaptive step-size scheduling delivers to 20 speed-up in total steps over MeZO (Table 6). One FZOO step bundles forward passes-4.5x more than MeZO-yet consumes only 3x the wall-clock time (Appendix F), highlighting the gain from parallel implementation.
4.5 COMPARISON WITH ZO VARIANTS AND HYBRID FRAMEWORKS
We also compare FZOO with wider range of ZO optimization methods (Zhang al., 2024). As shown in Table 7, FZOO consistently outperforms all baselines. Compared to ZO-Adam, our FZOO achieves an average accuracy improvement of 5.77% under full-parameter tuning, and 4.21 % under prefix-tuning, while using 40.5% % of the GPU memory.
Table 7: Performance comparison on SoT2RRober-Large and OPT-1.3B) and COPA(OPT-13B) using different 70 methods. Memory and runtime cost are multiples of ZO-SGD.
Model/Task
Roberts-Land Large
OPT-1-3B
OPT-13B
Average
Memory
Runtime
prefix
FT
prefix
FT
prefix
ZO-SGD
89.4
90.0
90.8
91.4
90.0
79.0
88.4
1.0x
1.0x
ZO-SGD-MMT
89.6
89.1
85.2
91.2
87.0
85.0
87.8
1.56x
1.0x
ZO-SGD-Com
89.6
89.1
88.3
88.1
82.0
84.0
86.8
1.0x
2.49x
Z0-SGDD-Sign
52.5
53.6
87.2
89.5
80.0
78.0
73.4
1.0x
1.0x
ZO-Adam
89.8
90,2
84.4
91.4
82.0
79.0
86.1
2.47x
1.0xx
HiZOO
93.2
92.7
90.7
91.4
88.0
87.0
90.5
2.04x
1.37x
HiZOO-L
92.5
92.7
90.7
91.4
88.0
87.0
90.4
1.12x
1.39x
FZOO
93.3
92.9
90.7
91.7
87.0
87.0
90.4
1.0x
0.56x
Integration with Hybrid FO-ZO Methods. We further demonstrate the orthogonality of FZOO by integrating into the hybrid OristtOrdee/eertth Order framework Addax (Li et al.). By simply replacing the internal McZO component in Addax with FZOO, evaluated the performance OPT-2.7B across two distinct hyperparameter settings (Setting A favors FO; Setting B favors ZO). As shown in Table 8, FZOO consistently serves superior "drop-in" replacement: it improves Addax's 's average accuracy from 72.71 to 74.11 Setting A, and from 68.37 to 71.16 Setting B, confirming that FZOO can effectively enhance existing hybrid strategies.
Table 8: Comparison with Hybrid FO-ZO Method (Addax) on OPT-2.7B across 11 tasks. Setting A and B denote different hyperparameters for balancing FO/ZO usage. *Average Setting excludes ReCoRD due to sequence length constraints.
Methed
Setting
SST-2
RTE
CB
BoolQ
WSC
WIC
MultiRC COPA
ReCoRD SQuAD
DROP
Average
Addax (McZO)
Set
94.2
81.6
92.9
75.3
$2.9
64.4
69.4
81.0
75.2
84.4
28.6
72.7
Addax (FZO0)
Set
78.3
76.4
56.7
74.1
84.8
30.0
Addax (MzZO)
B
92.2
79,8
92.9
63.1
61.5
61.6
44.5
82.0
81.5
24.6
68.4"
Addax (FZOO)
Set B
93,6
76.5
96.4
75.7
59.6
57.4
61.4
84,0
82.3
24.6
71.2'

---

Published as a conference paper at ICLR 2026
4.6
ORTHOGONALITY AND HYPERPARAMETER ANALYSIS
Orthogonality Verification (FT vs PEFT)
Influence of batch N
0.30
0.85
50
0.80
0.75
Accurety
20.70
10
2..5
Uhede:0
hatx
0.55
Un-de-22
Reet 512
035
1B 1m-24
0053
3KU
RTC
82
K26
Figure 5: FZOO (prefix) vs PEFT (prefix) on Roberta-large. More results can be found in Appendix D.I.
Figure 6: Accuracy Comparison under Differ- Perturbation Batch Sizes N for FT. The relevant results are in Appendix G.I.
Orthogonality to Fine- Fine-Tuning Strategies Our method an optimization algorithm that focuses on how to update parameters, and is orthogonal to fine-tuning strategies that decide which parameters to update. We validate its compatibility by FT or Prefix on the roberta-large model.
Influence of the Number of Perturbations N per Step To further explore the trade-off between computational efficiency and convergence performance the optimizer, we conducted a systematic evaluation OPT-125M using the SST-2 dataset. As shown in Figure 6, increasing the number of perturbations per step can improve accuracy under certain hyperparameter settings, but also raises per-step computational cost.
CONCLUSION
We introduce FZOO, zeroth-order optimizer that delivers order-of-magnitude Adam-like con- vergence speed for fine-tuning LLMs with inference-scale memory. By using batched one-sided estimates and accelerated per-batel computations, FZOO reduces forward passes and converges in far fewer steps than MeZO. It also integrates seamlessly with PEFT, offering superior performance and practical fine-tuning efficiency.
Reproducibility Statement. We provide anonymous code and configuration files, together with the license and datasets, at https: ht////nnooouuuu. 4open secieneee/ee FFF00000997 Additional theoretical details appear in Appendix B. Detailed experimental settings and further results organized in Appendices D,E.F,G, corresponding to the main experiments, efficiency analysis, and ablations, respectively.
ACKNOWLEDGMENTS
This work supported in part by National Key Research and Development Project of China under Grant 1222FF1100000 National Natural Science Foundation of China under Grant 72471 185, and Science and Technology Project of State Grid Shaanxi Electric Power Company Limited under Grant 5226PX250001.
REFERENCES
Mengting Ai, Tianxin Wei, Sirui Chen, and Jingrui He. Nirvana: Structured pruning reimagined for large language models compression. arXiv preprint arXiv:2509. 14200 2025a.
Mengting Ai, Tianxin Wei, Yifan Chen, Zhichen Zeng, Ritchie Zhao, Girish Varatkar, Bita Darvish Rouhani, Xianfeng Tang, Hanghang Tong, and Jingrui He. Resmoe: Space-efficient compression of mixture of experts 1lms via residual restoration. arXiv preprint arXiv:2503.06881, 2025b.
Josh Alman and Zhao Song. The fine-grained complexity gradient computation for training large language models. arXiv preprint 240i::2402.04497,, 2024.
10

---

Published as a conference paper at ICLR 2026
Gabriel Belouze. Optimization without backpropagation. arXiv preprint 20Xfv2200.066302, 2022.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-11, 2018.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss,, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Hanqin Cai, Yuchen Lou, Daniel Mckenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1193- PMLR, 18-24 Jul 2021.
Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffenderfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training. arXiv preprint trXiv:2310000000 2023.
Hanting Chen, Yunhe Wang, Chunjing Xu, Boxin Shi, Chao Xu, Qi Tian, and Chang Xu. Addernet: Do we really need multiplications in deep learning? In Proceedings of the IEEF/CVF conference on computer vision and pattern recognition, pp. 1468-1477. 2020.
Pin-V Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. New York, NY, USA, 2017. Association for Computing Machinery. ISBN 978 450352024, doi: 10.1 111453/28572.3144445 URL httph:tt///ette //doi org/10..///. 10. 1 1145/1/41 /1/445/3/2222 .1 3140448.
Yiming Chen, Yuan Zhang, Liyuan Cao, Kun Yuan, and Zaiwen Wen. Enhancing zeroth-order fine-tuning for language models with low-rank structures. urXiv preprint arXiv:2410.076698 2024.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International contretteiolcoocceenencc conference machine learning, pp. 2260-2268. PMLR, 2020.
Longchao Da, Tiejin Chen, Zhuoheng Li, Shreyas Bachiraju. Huaiyuan Yao, Li Li, Yushun Dong, Xiyang Hu, Zhengzhong Tu, Dongjie Wang, et al. Generative ai in transportation planning: A survey. arXiv preprint arXiv:2503.07158, 2025.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. GPT3.int80) 8-bit matrix multiplication for transformers at scale. In Advances in Neural Information Processing Systems, 2022a.
Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 8-bit optimizers via biock-wise quantization. In International Conference on Learning Representations, 2022b.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized Ilms, 2023.
Jacob Devlin, Ming- Ming-Wei
Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Associa- tion for Computational Linguistics, 2019. https: //aps://appa
/ semanticscholar.......e.ccc org/
CorpusID: 52967399.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12(mu11::121122555 jul 2011. ISSN 1532-4435.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth- order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341 02:::2341-3363 2013.

---

Published as a conference paper at ICLR 2026
Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scale hyperparameters via automated learning algorithm. arXiv preprint arXiv:2102.09026 2021.
Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Harkirat Singh Behl, Xin Wang, Sébastien Bubeck, Ronen Eldan, Adam Tauman Kalai, Yin Tat Lee, and Yuanzhi Li. Textbooks are all you need, 2023.
Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A. Smith. Don't stop pretraining: Adapt language models to domains and tasks. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. -342, 2020.
Davood Hajinezhad and Michael M. Zavlanos. Gradient-free multi-agent nonconvex nonsmooth optimization. 2018 IEEE Conference on Decision and Control (CDC), pp. 4939-4944, 2018. URL https://agg /api......// ..l.sseemee www.ntiisccooeooceee.oe
org/CorpusID 58669445.
Filip Hanzely, Dmitry Kovalev, and Peter Richtarik. Variance reduced coordinate descent with acceleration: New method with a surprising application to finite-sum sum problems. In International Conference on Machine Learning, pp. 4039-4048, PMLR, 2020.
Chang He, Zhaoye Pan, Xiao Wang, and Bo Jiang. Riemannian accelerated zeroth-order algorithm: improved robustness and lower query complexity. arXiv preprint arXiv:2405.057/3, 2024.
Thomas A Hogan and Bhavya Kailkhura. Universal decision-based black- box perturbations: Breaking siweiity-ttruuhhooobseee
defenses. arXiv preprint arXiv:1811.03733. 2018.
Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022. URL https: //opp//ev/ee..eee/eeeoee net.eeewwweeeeeeeeeeee..ee.eeeee forum?
id=nzevKeeFYE9.
Wenyang Hu, Yao Shu, Zongmin Yu, Zhaoxuan Wu, Xiaoqiang Lin, Zhongxiang Dai, See-Kiong Ng. and Bryan Kian Hsiang Low. Localized zeroth-order prompt optimization. Advances in Neural Information Processing Systems, 37:86309-86345 2024.
Gangshan Jing, He Bai, Jemin George, Aranya Chakrabortty, and Piyush K Sharma. Asynchronous distributed reinforcement learning for lqr control via zeroth-order block coordinate descent. IEEE Transactions on Automatic Control, 69 1):7524-7539, 2024.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), San Diega, CA, USA, 2015.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020. URL https: owwpreveeneeeeeee/eeeeeee net/ forum? id=HleA7AEtvss
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference on Natural Language Processing (Volume 1: Long Pupers), pp. 4582-4597, Online, August 2021. Association for Computational Linguistics. doi: 10. 18613/811/2222 acl-long.3333 URL hwtpt:tpps... aawaaaaannllllooooo ogy. .rgg ww2.0.cc11-........ 353.
Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee. Textbooks all you need ii: phi-1.5 technical report, 2023.
Zeman Li, Xinwei Zhang, Peilin Zhong, Yuan Deng, Meisam Razaviyayn, and Vahab Mirrokni. Addax: Utilizing zeroth-order gradients to improve memory efficiency and performance of sgd for fine-tuning language models. In The Thirteenth International Conference on Learning Representa- fions.
12

---

Published as a conference paper at ICLR 2026
Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference on Learning Representations, 2019a. URL https://api. semanticschon wwt.sshhhw......ooo...e.eee
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, arXiv preprint arXiv: 1907. / 1692, 2019b.
Yong Liu, Zirui Zhu, Chaoyu Gong, Minhao Cheng, Cho-Jui Hsieh, and Yang You. Sparse mezo: Less parameters for better performance in zeroth-order IIm fine-tuning. arXiv preprint arXiv:2402.1573
2024.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence Learning Representations, 2019. URL https:tpp///ccc...t. / net formmirr Bkg6RiCqY7.
Shaocong Ma and Heng Huang. Revisiting zeroth-order optimization: Minimum-variance two-point estimators and directionally aligned perturbations. In The Thirteenth International Conference on Learning Representations, 2025.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https:/ http:::://ppperevveeee net/ forum? id=Vota6rFhBQ.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides a competitive approach reinforcement learning, 2018. URL /tttps:/aarxiv.ortt org. hat///b////// /1003. 07055.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Rui Pan, Xiang Liu, Shizhe Diao, Renjie Pi, Jipeng Zhang, Chi Han, and Tong Zhang. Lisa: Layerwise importance sampling for memory-efficient large language model fine-tuning, 2024.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- lional mathematics and mathematical physics, 4(5):1-17, 1964.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Marco Rando, Cesare Molinari, Silvia Villa, and Lorenzo Rosasco. Stochastic zeroth order descent with structured directions. Computational Optimization and Applications, 89(3)=691-727, 2024.
Tao Ren, Zishi Zhang, Jinyang Jiang, Guanghao Li, Zeliang Zhang, Mingqian Feng, and Yijie Peng. Flops: Forward learning with optimal sampling. arXiv preprint arXiv:2410.05966, 2024.
Tao Ren, Zishi Zhang, Zehao Li, Jingyang Jiang, Shentao Qin, Guanghao Li, Yan Li, Yi Zheng, Xinping Li, Min Zhan, et al. Zeroth-order informed fine-tuning for diffusion model: recursive likelihood ratio optimizer. arXiv preprint arXiv:2502.00633 2025.
Weijia Shao and Sahin Albayrak. Adaptive zeroth-order optimisation of nonconvex composite objectives. In International Conference on Machine Learning, Optimization, and Data Science, pp. 573-595. Springer, 2022.
Yao Shu, Zhongxiang Dai. Weicong Sng, Arun Verma, Patrick Jaillet, and Bryan Kian Hsiang Low. Zeroth-order optimization with trajectory-informet derivative estimation. In The Eleventh International Conference Learning Representations, 2023.
J.C. Spall. Multivariate stochastic approximation using a simultancous perturbation gradient approxi- mation. IEFF Transactions Automatic Control, 37(3):332-31, 1992. doi: 10999 19632.
13

---

Published as a conference paper at ICLR 2026
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuanjing Huang, and Xipeng Qiu. BBTv2: Towards a gradient- free future with large language models. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 0013-99669999 2022a.
Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu. Black-box tuning for banguage-model-as-tee -seeevivee. In International Conference on Machine Learning, pp. 20841-20855, 2022b.
Yujie Tang. Junshan Zhang, and Na Li, Distributed zero-order algorithms for nonconvex multiagent optimization. IEEE Transactions on Control of Network Systems, 8(1):269-281, 2021. doi: 20.10099
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, 139771 2023. URL https: //ap:///pppp http:/ppp.aaaiisssieeeemm semanticscholar org/
Corpus 25121:::7729900
Yun-Yun Tsai, Pin- Yu Chen, and Tsung- Yi Ho. Transfer learning without knowing: Reprogramming black-box machine learning models with scarce data and limited resources. In International Conference on Machine Leurning, pp. 9614-9624. PMLR, 2020.
Xiaoxing Wang, Xiaohan Qin, Xiaokang Yang, and Junchi Yan. ReLIZO: Sample reusable linear interpolation-basee zeroth-order optimization. In The Thirty- Anmual Conference Neural Information Processing Systems, 2024. URL https:/ wwwp//ppppeeee.eeooo/oe net. wateeefoouuaee forum? dim yzviAnpvU6.
Samuel Williams, Andrew Waterman, and David Patterson. Roofline an insightful visual performance model for multicore architectures. Communications of the ACM, 52(4):65-76, 2009.
Huaiyuan Yao, Longchao Da, Vishnu Nandam, Justin Turnau, Zhiwei Liu, Linsey Pang, and Hua Wei. CoMAL:: Collaborative Multi-Agent Large Language Models for Mixed-Autonomy Traffic, pp. 418 doi:
URL https: /epubs. siam. org/ dooi/
abs/ /1/
Huaiyuan Yao, Pengfei Li, Bu Jin, Yupeng Zheng, An Liu, Lisen Mu, Qing Su, Qian Zhang, Yilun Chen, and Peng Li. Lilodriver: A lifelong learning framework for closed-loop motion planning in long-tail autonomous driving scenarios. arXiv preprinl arXiv:2505. 17209, 2025a.
Huaiyuan Yao, Wanpeng Xu, Justin Turnau, Nadia Kellam, and Hua Wei. Instructional agents: Lim agents on automated course material generation for teaching faculties. arXiv preprint DrXiv:2508.19611 2025b.
Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth- order optimization for black-box adversarial attack, 2019.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li. Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. Opt: Open pre-trained transformer language models, 2022.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang Wenqing Zheng, Pin- Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-efficiet LLM fine-tuning: A benchmark. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller. Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 Proceedings of Machine Leurning Reseurch, pp. 59173-59190. PMLR, 21-27 Jul 2024. URL https: http:///pcccecc...//////// mlr w.l..ppres/vv252 2225//haag2222 html.
Zijun Zhang. Improved adam optimizer for deep neural networks. In 2018 JEEE/ACM 26th international symposium on quality of service (IWQoS), pp. 1-2. leee, 2018.
14

---

Published as a conference paper at ICLR 2026
Jiawei Zhao, Zhenyu Zhang. Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficient Ilm training by gradient low-rank projection. In International Conference Learning Representations, 2024.
Kai Zhao, Yanjun Zhao, Jiaming Song, Shien He, Lusheng Zhang, Qiang Zhang, and Tian- jiao Li. Saber: Switchable and balanced training for efficient Ilm reasoning. arXiv preprint arXiv:2508. 10026, 2025a.
Lina Zhao, Jiaxing Bai, Zihao Bian, Qingyue Chen, Yafang Li, Guangbo Li, Min He, Huaiyuan Yao, and Zongjiu Zhang. Autonomous multi-modal I1m agents for treatment planning in focused ultrasound ablation surgery. arXiv preprint arXiv:2505.2 24188, 2025b.
Yanjun Zhao, Ziqing' Ma, Tian Zhou, Mengni Ye, Liang Sun, and Yi Qian. Geformer: An ef- ficient solution for accurate and scalable long-term multivariate time series forecasting. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Man- agement, CIKM '23, pp. 3464-3473, New York, NY, USA, 2023. Association for Comput- ing Machinery. ISBN 9798400701245. doi: 10.144/3583880.6111166 URL https: //doi. /1//////0..111//3888383333333331
Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor W. Tsang. Second-order fine-tuning without pain for llms: hessian informed zeroth-order optimizer. In International Conference on Learning Representations, 2025c.
15

---

Published as a conference paper at ICLR 2026
A RELATED WORKS
A.1 GRADIENT-BASHE OPTIMIZATION METHODS
Large language models (LLMs) have demonstrated remarkable performance across a wide range of applications (Zhao et al., 2023; Ai al., 2025b; Zhao et al., 2025a). Standard optimizers such as SGD remain the mainstream choice for fine-tuning LLMs, but their reliance on backpropagation leads to significant memory overhead. Improvements to SGD generally fall into two categories: (1) adaptive learning rate schemes, such as AdaGrad (Duchi et al., 2011) and Adam (Kingma & Ba, 2015), and (2) accelerated schemes, such as Polyak heavy-ball (Polyak, 1964). Both approaches make use of the accumulated past gradient information to achieve faster convergence. ND-Adam (Zhang, 2018), as an improved version of Adam, significantly improves the generalization performance of the model by more precisely controlling the update direction and step size. NIGT (Cutkosky & Mehta, 2020) combines the momentum mechanism with normalized-SGD (Bernstein et al., 2018), achieving excellent empirical performance in tasks such as ResNet-50 and BERT pre-training. This method does not rely on any second-order statistics and has significantly improved memory efficiency compared to popular optimizers such as Adam. Although these methods effectively reduce some computational and storage overheads while improving adaptability and generalization capabilities, they are still essentially first-order optimization frameworks and still rely backpropagation and gradient information.
A.2 GRADIENT-FREF OPTIMIZATION METHODS
Gradient-free optimization estimates gradients by leveraging loss differences, thereby eliminating the need for backpropagation and intermediate activation storage (Ren et al., 2025; Yao et al., 2025a; Ren et al., 2024). With provable convergence guarantees, these methods have attracted considerable attention and have been successfully applied to a wide range of machine learning tasks, including adversarial attacks, transfer learning, and reinforcement learning, among others (Tsai et al., 2020; Shu et al., 2023; Da et al., 2025; Jing et al., 2024; Chen et al., 2023; Gu et al., 2021; Hogan & Kailkhura, 2018; Yao et al.; Zhao et al.,, 2025b; Ai et al., 2025a)
To reduce memory consumption during large language model fine-tuning, Malladi et al. (Malladi et al., 2023) introduced MeZO, which applies the classical ZO stochastic gradient descent algo- rithm Ghadimi & Lan (2013) to fine-tune pretrained LLMs without relying on backpropagation. Building on this, HiZOO Zhao al. (2025c) incorporates diagonal Hessian information accelerate convergence, albeit at the cost of doubled memory usage and additional hyperparameters. More recently, Sparse-MeZO Me Liu al. (2024) proposes a memory- maintains memory usage comparable to standard inference. To address the issue that existing zeroth- order methods struggle capture the low-rank gradient structures commonly found in large language model (LLM) fine-tuning wuwtinng-nruuutinggggggg in performance degradation (Chen et al., 2024; Yao et al., 2025b) proposes a low-rank ZO gradient estimator and introduces a novel algorithm, LOZO, which can effectively model such structures. Compared with the vanilla ZO-SGD method, both LOZO and its variant LOZO-M achieve improved performance. (He et al., 2024) propose a Riemannian accelerated zeroth-order algorithm with enhanced robustness, addressing the commonly observed issues of slow and unstable convergence in practical zeroth-order optimization. (Hu et al., 2024) propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO), which incorporates Neural Tangent Kernelbased derived Gaussian process into standard zeroth-order optimization for an efficient search of well well-performing local optima in prompt optimization. However, none of the evaluated methods are yet capable of matching Adam-level speed under strict inference- memory constraints.
ZO fine-tuning strategy that
A.3 ZEROTHI-ORDER OPTIMIZATION WITH STRUCTURED PERTURBATIONS
While standard ZO methods typically rely on Gaussian or spherical smoothing, several works have explored structured or directional perturbations to improve query efficiency. (Belouze, 2022) investigated the use of Rademacher random vectors for gradient estimation without backpropagation. However, their approach lacks the variance-basse based normalization mechanism employed in method; without this normalization, Rademacher perturbations yield performance comparable to standard Gaussian noise used in MeZ0 (?), falling short of the convergence speed achieved by FZOO.
16

---

Published as a conference paper at ICLR 2026
Other approaches introduce more complex structures. (Rando et al., 2024) proposed updating parameters using structured directions derived from orthonormal matrices. Although theoretically sound, this method requires constructing and storing large orthonormal matrices (d x N), incurring significant memory overhead that contradicts the primary goal of memory-efficient LLM fine-tuning. Similarly, (Ma & Huang, 2025) introduced Directionally Aligned Perturbations (DAP) minimize variance. However, DAP is specifically derived for two-point estimators and introduces additional computational overhead for vector projections (O(d) operations), which prevents it from leveraging the efficient bit-level sign flips possible with Rademacher vectors in batched settings. Furthermore, (Shao Albayrak, 2022) applied Gaussian perturbations within zeroth-order mirror descent framework. This approach targets non-convex composite optimization problems, whereas LLM fine- tuning typically formulated as a smooth non-convex problem, making the additional complexity of mirror descent unnecessary compared to our streamlined normalized update.
17

---

Published as a conference paper at ICLR 2026
B DETAILED CONVERGENCE ANALYSIS
B.1 PROPERTIES OF RADEMACHER RANDOM VECTOR
Lemma B.1. Letting I E R be a constant vector and {us [mm); be d-dimensional Rademacher
random vectors, then it holds that
N
E
Σ
U.
u
N(N + d ||=
(8)
Proof. It holds that
E
M4 u
=E
x u.u uju,
N
E
Σ
T Uyu, x- =1/i11?
E uuuu xx] E uu x1)
N
=I
Σ
x T
Uzu x 1|1511
E [u T [o]
[unzee ar))
=N]||=1| (N2 N)) ||-0|
=N(N + d - 1) |=01
Lemma B.2. Letting u, 'ss be Rademacher random vector, then it holds that
N
N
27
E
VL(O, B),
N Uj
Σ
(N - (N-1))[V[(,BB))
(9)
1=1
Proof. It holds that
1
VL(0,B), 24
N Σ Uj
(10)
(L B), 2 + V[(0, B),
Σ U4
(11)
7=1
Σ
1
(12)
N
2
VV B3, u2)²
V B),
(13)
N
18

---

Published as a conference paper at ICLR 2026
Furthermore,
{
N
27
N
N
E
VL(0, B),
Σ
Uj
(L((,, u,) (V), un)
i=1
N
E LV B3, 2
+
E (V B), u4) (VL(0, u))
E
(VL(O,B), uz)
NN (V,
Thus,
Σ
E
VI((0)),
1 N
Σ "j
(1 (1- N
Σ E
N
(V B), m.²] (N - 1) B))²
B.2 PROPERTIES OF 9: AND
By the Taylor's expansion, we have
L(e eu,, 13) = L(9) + c c u.) +a(8, eu, B))
(14)
where a08, cu,, B) A L( + cu,, B) (L(0) + c (VL(0, u.)). By the C-smoothness, we can obtain that
Le
dLc²
|a(0, eu;, B3] < 2
||u:11
(15)
2
where the last equality is because u4 E (-1,
Lemma B.3. Letting the estimated variance ae defined in equation 3, then, it holds that
B B = [L ( +
(16)
with
1 N
al0, cuj; B)) 2
= N
a(0, cus, BB)
Σ
N
1=1
N
N
N a(f, cuy. B))
+ N -
VI(0, u4
(a(0, ((,0,cu;, cu;,
Σ
N
N ==1
1=1
j=1
and
L2
K
2dN LE3 |VV
2
Proof. First, have
1
L(O + ewg B)
L(O euj; 13)
N
equation 14 "[(0) + (VI B), u.) + a(0,Eui
Eui, B)
(L(O) + (VL(0, uz) + aa(0, euj, B))
N
N
N
VL(O,B), 04 N
Σ
Uj
+ a0, eu; B)
au e0,e B).
N
j
19

---

Published as a conference paper at ICLR 2026
2
N
L(e + c,,, B)
L(e + eug, B)
N j=1
2
Σ 1=1
+ Bi
N (L(
N
2
Nv.
1
2
Σ
Uj
+
B
VL(O, B), u
Σ
Uj
Bs
N
N j=1
i=1
j=1
where we use 3, a al0, eut, B)
1
Σラ= j=1
N
a0,, B).
Furthermore, it holds that
N
N
Σ
=
1
1
00, eu;, B) S
N
4
1=1
and
Σ Uj /
1
1
equation 15
V VL(0,B),u u.
Σ
Uj
Be
S
N
V B),
|B:ll
dNLe VL(0. B)
N
N
Therefore, we can obtain that
1 N
2
N
VL(0,B),u
Uj
+ B + e
VL
Σ
us
B:
N
N ==1
N
==1
equation 22 |/V, [] +5
Finally, we have
1 N
N + N - Σ
N Σ
K N - Σ
p
VL(A,B),
N Uj
B,
1=1
2=1
==1
C2
2d.
V BB]l
2
Lemma B.4. Letting the stochastic gradient estimation gt. defined in equation then it satisfies the following properties
N Jt
=
u.u VL(O,, + Te
(17)
N
1=1
with
1
d3 C22
(00, eu;, B) and R [T]]
(18)
N
4N
Proof. By the definition of ge in equation 2, we can obtain that
N L(0 + eu,, B) L(0, us
equation
gt
1=1
N
N
equation
14
unu VL +
(0, eu,, B)
N
i=1
N
1
u.u LL +
N
1=1
20

---

Published as a conference paper at ICLR 2026
Furthermore,
E
E (e-
10-3a(0,- ewz, eu; B))² -[uu:]]
N
i=1
de-
equation 15
22²
[a euj, B]]
S
N
4N
Lemma B.5. Letting the stochastic gradient estimation 9t defined in equation 2, then its norm satisfies that
N + d 1
19:e1
Lo,,,, +
(19)
with
de
[a² euj, Bi] + de [u VL(0, B)a(0, eu,, B)]
Tt
N
(N 1)E
(V B), E B) u,,)
N
Furthermore, it hols that
LC22
had
S
+
B.
B:)
4N
Proof. First, we have
N
2
N
l1ael1
1
Σ
u
VL B)
+
( a00, B))² B)) ||u/11
N2
N2
1=1
+
mn
E a [L
cu, 1), u.)
N2
N
1
n.u VL(O, B)
Σ
1 al0, eu,, B3))
N2
N
+
mn VL(O,B), - a(0 BB uj)
N2
1=1
We also have
N Σ
u.u VL B))
N(N + d 1V
Furthermore, it holds that
N
N
B) uz)
N
" LL (), a00 eu,, B) wi)
+E
(nnu, VL(O, (a(0,,,,, B) - u,)
=de
[u ( (TTT(0,))xol (), em,, B)] + N(N 1)c
(VI(0, B), E [a enj B) uz}:
Thus,
N + d
2 E [a²(0, B)]
E
[1ah11]]]
N VL 2)
N -
d1
(N - 1)E-
E [uT VL ()a eu,, B))
(V 13), E [a(0, eu,
(a(0,eu,, -))))
N
21

---

Published as a conference paper at ICLR 2026
Finally,
hi S de
de
N [ [a cuj, B)]
E i
VL(0, VL(8,B)a(( (0, cu,, B)]
N
+ (N 1)
(VL(0, B), (a eu, B) w,ا>
N
equation 15 de
2
&C'C
+ de-
dLE²
dCe?
S
N N [VL(0,,
+ V B.)
2 1122
N
4
2
d 2
L |V B.)
2N + 2
4N
d C
dL B.
.,)ll
4N
which concludes the proof.
B.3 PROOF OF PROPOSITION 3.2
Proof. Lemma B.3 and Lemma B.5 imply the result of Proposition 3.2.
B.4 PROOF OF THEOREM 3.6
Proof. First, have
E (KV VL(0.) -BITT equation 18
[VL(0.)]
L2
(20)
2
2
8N
where the first inequality is because of the Cauchy's inequality. It also holds that
2dCo, V
VL
NdC 31p22
(V,, BC..))e-IVVLLOO.BBB)
1c
<
(21)
N
2
Thus, by the L-smoothness of (O)), have
Co,
20p2
E B] (L(),) प,; LE ( L(Oe,, (,000))99 g.)و +
[|
2
equation "((O,) - (O.)),
Σ uui VLTTLLOO, B:) + +t ) )> N
1
Loi
[10.11
+
E
2
3
=L(O,) पo; -IE 'E
[(()))1
+ n,; E (V(() -T.)] | +
E
[19.812
2
equation 20equation
170 L(O,)
E
|VL(0))1
170 -1 &e C22
+
N + d -
Lo, 112
E
L B.)
V
2
8N
N
2
d L o, 22
+ dL 0, - [V, B
+
8N
equation
I(0,) 10,
E [|VL(1))1
110
2dCo 212
.. (IVL(O.,
8N
N
2dho, 2, |IT,(O,, B0)1
+ LL 0, 2
NdC 31pe
8N
N
2
equation
L(0,) 10 E
|IVL(ON11
4dLo, 2112
E
|I
+
4dCo, 21222
N
N
o 0 o, 2R
Nd o, 3IPEE
+
8N
2
4dLo, 21
d L 21p22
NdC o. ?12E?
<L(O,) n0 E ||V((0))1
N
8N
2
22

---

Published as a conference paper at ICLR 2026
where the last inequality is because of step size satisfies nj, We can represent above equation as follows:
S
NN.
16d2
no,
E
|VL - (L))) - L(0++1)) +
AdLor31'')
NdL
N
8N
2
Telescoping above equation, we can obtain that
1
7 |VL(0))1
L(01) - L(07)
T
4dLo, 21222
L'o 3
NdC
21/²?
E
+
T
T
TN
8TN
2T
t=1
t=1
Furthermore,
T
T
[VL(()))
S T
Σ
E
[[VL(())
T
o.
4T.
(L(01) - L(0'))
40. Σ
/4dLoi "1122
d LL'00" 2122
od
T/T
TN
8TN
27
By setting 1)
obtain that
VT'
40. VT
T
[ddLo 2222
222
Nd
262
[[V]())))
S
(10))-100)
+
Σ
N
8N
2
(22)
23

---

Published as a conference paper at ICLR 2026
Algorithm 2 FZOO-R
Require: parameters 0 E R., loss L IRd + I. step budget 7', perturbation scale batch size N, learning rate schedule {m
1: Initialize 1-1 <- /)
> To store previous losses
2: for = 1,... do
3:
l, 0, seeds <- BatchPerrurb/aaameteenn.. 6, N)
4: if 1111 is not empty then
5:
std standard deviation of concat(E,(_)
6: else
7:
std t standard deviation of
8: end
9: projected_grate +- (e L(): std)
10:
L
> Save the current loss
11:
BacellpdaaPPrrannterrrriiieeeedd seeds, 0, mje)
12: end for
function BATCHPERTURBBPAAMMEEEE
6, .N)
14: Sample batch B C DD obtain input X and first layer weights W(()
Initialize random seeds seeds {s........ ......... sy
16:
Generate perturbation vectors { N
using seeds
17:
Compute unperturbed activations [[1) <- W
Compute perturbed activations: y, F(1) + e(u;X), I,..,,N
Concatenate activations ( + [y]]] :..
19:
for j = 2, 3,.... do
21:
FÚI + W(
Compute unperturbed activations at layer Compute perturbations at layer >> Compute perturbed activations in parallel at layer
22:
p() t c(uY(i-1))
23:
( t FGt + p()
end for
25: E L(Y(iina));; B3)
> Compute final losses in parallel
26: return E, seeds
27: end function
28: function BATCIUDAATEPAAMETRRqqrcccedd
seeds, 0, 1))
29:
for idz, E enumerat e (sceds) do
30:
Reset random number generator with seed do
D For sampling u
31:
for 0, E
32:
u ~ Uniform((+
0 0, 17 projected_ggrade
34:
end for
end for
36: end function
C FZOO VARIANTS
C.1 FZOO-R
Although FZOO accelerates training convergence through adaptive step size adjustment, each update requires multiple forward passes. To reduce the computational overhead per update, we propose loss reuse variant FZOO-R. Instead of performing the full recommended number of forward passes for each update, we halve it. FZOO-R estimates the gradient direction solely based these few forward passes, while reusing loss values from the previous update to adjust the step size. The detailed procedure is deseribed in Algorithm 2. We visualize the loss curves of FZOO-R and FZOO in Figure 7. On most datasets, FZOO-R achieves comparable convergence to FZOO while requiring only half the update time per step.
24

---

Published as a conference paper at ICLR 2026
opt125m On WSC
opt125m On MultiRC
op:125m On MultiCC
0.70
0.8
F200
F200 R
F200 R
0.7
0.72
0.72
8
0.60
0.60
0.80
2.04
Step:0X100)
SteosiX100)
Staps/X100)
Figure 7: Loss curves opt- 125m between FZOO and FZOO-R.
C.2 FZOO WITHOUU PARALLEL
To facilitate controlled evaluation, we release non-parallel variant of FZOO, allowing for clearer comparison of the total step-count reduction ratio against baselines such as MeZO, as illustrated Algorithm 3. In this version, the perturbation noise sampled from a Rademacher random vector (+1),, ensuring that, apart from the removal of parallel optimization, all other components remain identical to the original FZOO. Note. Gaussian sampling benefits from dedicated optimized kernels, whereas Py Torch currently lacks specialized routine for Rademacher sampling. Hence, generating Rademacher noise via torch. torch.randint (0, 2, size-param, data a. size devi cerpcceparre am. data. device, dtype=param.date data. dtype) dtype) 2 is slower than
Gaussian sampling.
25

---

Published as a conference paper at ICLR 2026
Algorithm 3 FZOO without parallel
Require: parameters E I2d, loss : Rd IR step budget T,, perturbation scale e, batch size N, learning rate schedule {m/
1: for ===,,, 1,..., do
2:
seeds <- BaichPertrrrraanetteee... N)
3: sld 4- standard deviation of E
4:
projected lereeceedggrddd__ee - (e L(): std)
5:
buchuupllcPtamneeerrrggitttedddd seeds, 0, m7)
6: end for
7:
function BATCH/ERTURRPPAMEEERRR.. 6, N)
8: Sample batch B 'D
9: for
N do
Sample random seed s and append to seeds
11:
PerturbParametter//e c,
12:
Append L(O; B)
13:
PerturhParameters// -6, 8) D Reset parameters before forward pass
14:
end for
15:
return seeds
16:
end function
function PERTUROPARAMETTERC.
18: Reset random number generator with seed
D For sampling
for f₂ E A do
20:
Uniform ((+1mm(((111))))
0, + 02 eu
Modify parameters place
22: end for
23: return 0
24: end function
25: function BACCHUPPAAEPARRMEEETT(rCCCCC _grdd seeds, 0, 1))
26:
for idz, E enumerate(sceds. do
27:
Reset random number generator with seed for 0, E do
b For sampling
28:
29:
Uniform ((1,0)mm((11
- 0, 17 projected gradide
31:
end for
32:
end for 33: end function
26

---

Published as a conference paper at ICLR 2026
D EXPERIMENTS ON LLMS
D.1 DETAILED EXPERIMENTS ON ROBERTA-LARGE
We perform FZOO experiments on the RoBERTa-large model using the hyperparameters listed in Table 9, For learning rate scheduling and early stopping strategies, a constant learning rate is used in all FZOO experiments.
Table 9: The hyperparameter grids used for RoBERTa-large experiments. FZOO uses constant learning rate schedule.
Experiment
Hyperparameters
Values
FZO0
Batch size
Learning rate
1e-4 le-4
Weight Decay
FZ00 (prefix)
Batch size Learning rate 1 Weight Decay # prefix tokens
64
{1 {le- 2, le-1) [le 2, le-1)
5
Table 10: Experiments on RoBERTa-large (350M parameters, k=512). For MeZO we report the
results reproduced.
Task Type
SST-2
SST:5
SNLI
MNLI natural language inference
RTE
TREC topic
Average
sentiment
Zero-shot
79.0
35.5
50.2
48.8
51.4
32.0
49.5
LP
91.3
51.7
80.9
71.5
73.1
89.4
76.3
FT
91.9
47.5
77.5
70.0
66.4
85.0
73.1
FT (prefix)
91.9
47.7
77.2
66.5
66.6
85.7
72.6
McZO
93.3
53.2
83.0
78.3
78.6
94.3
80.1
McZO (prefix)
93.3
53.6
82.9
75.6
77.2
88.2
78.4
HiZOO
95.5
53.2
82.6
77.7
80.0
94.6
80.6
HiZOO (prefix)
96.1
54,2
85.7
79.7
77.3
93.9
81.2
FZOO
94.2
55.1
84.6
79.9
79.1
95.6
81.4
F700 (prefix)
96.1
51.5
83.1
81
76.5
95.8
80.7
RoBERTa-large On SST-2
RoBERTa-Iarge On sst-5
MeZO
MeZO
10-1
FZOO
10-
FZOO
10-2
10-2
10
10-2
l055
10-4
10-5
10
10.
10-6
10-7
10
1750 2000
2000
Forward Steps(X100)
Forward Steps(X100)
Figure 8: Loss curves on loBERTa-large between Me70 and FZO0.
In Table 10 show the full experiment results. Additionally, we plot more loss curves to compare with MeZO. As shown in Figure 8, we can see that FZOO can greatly accelerate the training process MeZO, which verifies the robustness of FZ00
27

---

Published as a conference paper at ICLR 2026
OPT:138
OPT-138
OPT-138 RTE
0.70
Ma70
Mo20
F2O0
0.14
0.63
2.0
0.10
0.00
0.66
0.54
Mcz0
24
F200
Staps0K100)
Forward
Stop:00100)
SQUAD
Me20
Me20
Me20
1.2
F200
F200
0.8
0.3
0.2
0,4
50
150
130
205
250
200
250
400
30
120
130
200
250
500
320
400
30
120
130
200
250
350
339
400
Forwerd StepwDX100)
Forwerd Steas/X100
Forwerd Steps/X100)
Figure 9: Loss curves on OPT.
D.2 MORE RESULTS ON VARIOUS LLMS
We use the hyperparameters in Table 11 for FZOO experiments on OPT. Full results for OPT-2.7B and OPT- 125M are in Table 12. We also provide the relative loss curves of fine-tuning OPT-13B in Figure 9. We also provide several loss curves of fine-tuning Phi-2(2.7B) and Llama3(8B) in Figure and Figure!
Table 1I: The hyperparameter grids used for OPT experiments. All weight decay set to FZOO uses constant learning rates.
Experiment
Hyperparameters
Values
FZOO
Batch size
16 {le 5, 5e-5, 1e- 5e
Learning rate f
le-3, 3, 5, le-4
FT with Adam
Batch size
8 5e 8e-5)
Learning Rates
Table 12: Experiments on OPT-2.7B and 125M. The best results are highlighted in bold for better comparison. We highlight the best results between FZOO and MeZO in bold to facilitate comparison.
Model
Method
SST-2
BoolQ
WSC
WIC
MultiRC
COPA
ReCoRD
SQuAD DROP
Average
OPT-2.7B
McZO
92.2
38.8
62.5
64.0
53.8
54.2
58.4
76.0
75.0
77.6
25.3
63.4
OPT-2.7B
FZ00
93.6
69.0
62.5
70.8
57.7
57.5
65.5
83,0
76.2
81.8
26.5
67.6
OPT-125M
McZO
81.8
55.6
67.9
60.0
60.6
54.1
58.7
64.0
52.3
44.1
14.2
55.8
OPT-125M
FZOO
84.5
60.7
67.9
61.8
60.6
57.4
61.1
64.0
50.7
51.0
15.9
57.8
E DETAILS ABOUT MEMORY USAGE
Here we show the detailed numbers of memory profiling results Table 13. We did not turn on any advance memory-saving options, e.g.. gradient checkpointing. We set the per-device batch size as 1 to test the minimum hardware requirement to run the model with specific optimization algorithms. We use Nvidia's nvidia smi command monitor the GPU memory usage.
28

---

Published as a conference paper at ICLR 2026
Phi2 On Copa
Phi2 On MultiCC
Phi2 On RTE
0.75
2.1
F200
0.7
F200
1.9
0.05
0.60
1.7
0.55
0.4
0.50
F200
1.5
105
150
200
250
305
350
400
50
100
150
200
250
303
350
400
50
100
150
200
250
300
350
450
Forward StepsOX100)
Forward StepsDX100)
Forward Steps/X100)
Figure 10: Loss curves on Phi-2 between MeZO and FZOO.
llama3 On CB
llama3 On WIC
llam33 On RIE
Mczo
1.2
MeZO
MazO
F2OO
F2O0
FZOO
1.0
1.0
0.9
0.6
2.4
0.7
0.0
0.2
0.3
403
Steps0X100)
Steps0(100)
SteasiX100)
Figure 11: Loss curves on Llama3 between MeZ0 and FZOO.
Table 13: Memory usage on the MultiRC (average tokens=400) dataset. Results of ICL and full- parameter tuning are from MeZO(Malladi al., 2023).
Method
xero-sho(FZ00((FT)
HiZOO(FT)
Adam(Prefix)
ICL
Adam(FT)
I.3B
IxA100 (4GB)
IxA100 (7GB)
IxA100 (19GB)
IxA100 (6GB)
IxA100 (27GB)
2.7B
IxA100 (7GB)
IxA100 (13GB)
IxA100 (29GB)
1xA100 (8GB)
1xA100 (55GB)
6.7B
IxA100 (14GB)
IxA100 (29GB)
IxA100 (46GB)
IxA100 (16GB)
2xA100 (156GB)
13B
IxA (26GB)
IxA 100 (53GB)
2x 100 (158GB)
IXA 100 (29GB)
4xA 100 (3
30B
1xA100 (58GB)
2xA100 (118GB)
4xA100 (315GB)
IxA100 (62GB)
8xA100 (633GB)
66B
2xA100 (128GB)
3xA100 (246GB)
8xA100
2xA IxA100 (134GB)
16xA100
F DETAILS ABOUT WALLCLOCK TIME EFFICIENCY
As shown in Table 14, to avoid introducing additional overheads such as inter-GPU communication, results are measured on the same dataset (RoBERTa-large use SST-2 and OPT use COPA) and GPUs (80GB A A100), with each result averaged over 100 steps. "BS" refers to batch size. For the relatively smaller RoBERTa-Large model, we used BS=64, while for other models, we used BS=16.
Table 14: Wallclock time per step between Adam, MeZO and FZ0O(N=8).
Method
OPT-125M
RoBERTa-large
OPT-1.3B
Adam
O.393)s(BS=44) 0.1982s(BS=16)
0.5814s(BS=16)
MeZO
0.1368xBBS=16)
0.4305)(BS=64)
0.7218<(BS=16)
FZOO w/o parallel
0.6941<(BS=16
3.1925<(BS=16) (.0773<BBS=64)
FZOO
0.3835((BS=1)
0.6052<(BS=6))
1.6628<(BS=16)
G DETAILS ABOUT ABLATION EXPERIMENTS
G.1 INFLUENCE OF NUMBER OF PERTURBATION DIRECTIONS USED IN EACH UPDATE
We performed an ablation study the perturbation batch size the SST-2 dataset using the OPT- 125M model. As shown in Table 15, we observed that a batch size of 8 shows the best average performance among all tested configurations. While some other settings perform well in certain cases,
29

---

Published as a conference paper at ICLR 2026
batch size 8 offers good trade-off between stability and effectiveness, suggesting that moderate number perturbations per step benefits the zeroth-order optimization process.
Table 15: Ablations on OPT-125M using SST-2 dataset.
Batch Size
(5e-5,1e-3)
(2e-4.5e-5)
(5e-4,1e-4)
(le-5,1e-4)
(Ie-4,le33)
(5e-5,5e-55
(5e-5,le-4)
Average
0.8154
0.4908
0,4908
0,4908
0.7901
0.8165
0.4908
0.6484
0,8360
0.7798
0.6261
0.8349
0.8211
0.8417
0.8372
0.8026
8
0.8429
0,8521
0.7626
0.8028
0.8440
0.8326
0.8417
0.8278
16
0.8326
0.8567
0.8211
0.7110
0,8440
0,8452
0.8349
0.8244
32
0,7982
0.8498
0.8429
0.5734
0.8268
0.8154
0.8119
0.7945
G.2
ABLATION ON NORMALIZATION AND PERTURBATION TYPES
To further disentangle the sources of improvement in FZOO, we conducted ablation studies to verify our design choices regarding the perturbation distribution and the normalization mechanism. As discussed in our rebuttal, the efficiency of FZOO stems from two orthogonal sources: the adaptive step size via normalization (which improves convergence rate) and the implementation of batched perturbations (which improves wall-clock time). Figure 12 visualizes these comparisons using OPT-125M on the SST-2 task.
Gaussian vs. Rademacher Perturbations. As shown in the left panel of Figure 12, we compare the performance of FZOO implemented with Gaussian noise versus Rademacher vectors. The loss curves indicate that the two distributions perform comparably in terms of convergence trajectory, with Rademacher achieving slightly higher final accuracy. This observation confirms that the specific choice of perturbations is not the primary factor for convergence speed. Therefore, our preference for Rademacher vectors is justified by system efficiency: as detailed in Section 3.3, the discrete nature of Rademacher vectors allows for bit-level sign flips, making batched perturbations computationally cheaper and easier to vectorize than Gaussian noise.
Impact of Normalization. The right panel of Figure 12 highlights the critical role of the normalization term. We compare the full FZOO algorithm against an ablation variant where the puriance-based normalization is removed (i.c., updating with unnormalized estimated gradients). The results show stark contrast: without normalization, the algorithm suffers from significantly slower convergence and struggles to minimize the loss effectively within the same iteration budget. This confirms that the normalization mechanism is the dominant component responsible for the fast convergence properties of FZOO.
Perturb Ablation: OPT125m On SST-2
Norm Ablation: OPT125m On SST-2
FZOO ACC=B5.9
1.2
FZOO(Gauss perturb) ACC=85.3
0.8
1095
loss
0.8
FZOO ACC-85.9
0.6
FZOO(w/o Norm) ACC=51.3
WhM MMMM/NN
0.4
0.4
0.2
0.2
0
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
Forward Steps(X100)
Forward Steps(X100)
Figure 12: Ablation studies on OPT-125M (SST-2). Left: Effect of perturbation distribution. Right: Effect variance-based normalization.
30

---

Published as a conference paper at ICLR 2026
H DISCUSSION
MeZO: Mitigating Loss Upturn via Scheduler
FZOO: Mitigating Loss Upturn via Scheduler
1.1
MeZO(w/o scheduler)
FZOO(w/o scheduler)
1.0
MeZO(with scheduler)
FZOO(with scheduler)
0.9
1ogs
0.8
lo53
0.7
0.6
0.5
0.4
0.4
0
50
100
150
200
250
300
350
400
50
100
150
200
250
300
350
400
Forward Steps(X100)
Forward Steps(X100)
Figure 13: Loss stability amalysis on OPT- OPT-125m(SST-22) Applying cosine learning rate scheduler climinates the late-stage loss upturn in both MeZO (Left) and FZOO (Right), confirming that the phenomenon is due to the constant step size in ZO optimization.
H.1 TASKS WHERE FZOO LAGS FO
Across our experiments, harder generative long-context language tasks tend to show larger gaps between ZO methods (FZOO, MeZO, HiZOO) and full first-order fine-tuning, whereas short-context classification usually shows smaller gaps. This also motivates future hybrid FO+ZO strategies (FO on small of sensitivity-critical parameters, ZO elsewhere).
H.2 CONVERGENCE DISCUSSION (THEOREM 3.6) AND THE ROLE OF NORMALIZATION
(a) Positioning Theorem 3.6 relative to existing ZO theory. the one-step descent chains of FZOO, MEZO, and HIZOO:
Let L(0) be L-smooth, We compare
FZO0: E[L(0++1) & L(O,) 170
V
4
4d C 11
(d
Ndc
+
1100 2g2
(23)
8N
2
MeZO:
E[L(0(41) < ((0)) (L(()) C L B)||
(24)
HiZOO: E[L(0(41)] < L(O.) |VL + 2n ((trEt)) Bw) + +(12).
(25)
Ignoring the higher-order terms on the right-hand side, we want the negative term on the right-hand side to be as large possible (so that the overall right-hand side is small as possible). Hence the key comparison lies in the three terms
noT
n ||V
For FZOO, the effective coefficient obeys
not
16dL
Thus smaller smoothness constant L. (a flatter region) allows a larger admissible value of 177 making the leading descent term na, [V,)), larger in magnitude and the update faster.
Me7. uses the term v/l V (1.)) its descent term does not automatically grow in flatter regions.
HiZOO scales the gradient by the diagonal Hessian Σ,; this curvature shaping is orthogonal to F700's normalization but requires storing/estimating E, and extra forward pass.
31

---

Published as a conference paper at ICLR 2026
(b) Effect of the normalization term. On OPT-125M in early experiments. removing the normal- ization 17Z00-w/o NORM) yields lower final accuracy ((2pp) and requires 3x more forward steps to reach the same accuracy.
H.3 o-119ell RELATION
Lemma B.3:
N + -
[[
(VI + +m,
= 0
N
Lemma B.5:
E 0
E²
VL
B:) + Se
= ((5))
Eliminating || between Lemma B.3 and B.5 gives, to leading order,
N
E B E
E [[]
N+d-1
hence
N N + d -
Te R EV
|1
(up to lower-order terms).
In code we use
E² N of ||
which preserves the correct scaling in introduces standard degrees-of-freedon correction, and works stably in practice.
H.4 THE ET o, TERM IN THEOREM 3.6
Lemma B.3 gives
B[o = e VL B.)
V + Se
G> O.
(26)
Define
G max E V VI,
G min E VI, B)]]
In stochastic optimization Gmin > 0 (Hanzely et al., 2020; Bottou et al., 2018) because a mini-batch gradient retains finite variance even at an optimum. From equation 26, for all
G2 min + Ge S of S G2 max + Gr-
(27)
Let Ç sup, & (finite in setting). Then
Σ
T G²G2 min
0² < G22 max + S.
(28)
+5²
t=1
Combining the two bounds in equation 28 yields
C2 max +
Σ o s VT
V
C2 min +
O(VT).
(29)
Because is chosen small (Sec. 4.2), the constant inside the square root in equation 29 is close 1. Inequality equation 29 shows that the product term grows most like vT.
32

---

Published as a conference paper at ICLR 2026
H.5 ANALYSIS OF LOss DYNAMICS AND STABILITY
We address the observation regarding the increasing loss curves in the later stages of training (e.g.. Figure 3a, Figure 10c). This phenomenon is primarily attributed to the intrinsic stochasticity of zeroth-order optimization combined with a constant learning rate schedule. Unlike first-order methods where gradients vanish near local minima, ZO gradient estimates are dominated by the variance of random perturbations when the true gradient norm is small. Consequently, constant step size can occasionally propel the model out of a sharp minimum (a "stochastic escape"), leading to loss upturn.
We emphasize that this is general characteristic of ZO methods rather than a specific flaw of FZOO. To validate this and demonstrate simple mitigation, applied a cosine learning rate scheduler both MeZO and FZOO. As shown in Figure 13, loss upturn is effectively eliminated in both methods when the learning rate decays appropriately, confirming that the instability is easily manageable without compromising the method's 's effectivencss.
LLM USAGE
We used large language models only as ceneral-purpose assist tools for minor grammar and wording suggestions. They were not involved in idea wwwucption.exprrmeeen design or result selection. All technical content and claims were authored and verified by the authors.
33


Reviews:
[{"review_id": "4Td7mr0Y8U", "reviewer": "Reviewer_1YPH", "summary": "This paper introduces FZOO, a fast zeroth-order optimizer designed to reduce GPU memory in LLM fine-tuning. FZOO employs two primary strategies: it uses batched one-sided estimates to adapt its step-sizes based on loss variance and it utilizes Rademacher random-vector perturbations to accelerate per-batch computation. The authors demonstrate FZOO's effectiveness with experiments and provide theoretical convergence guarantees.", "questions": "1. Could the authors provide results for Adam fine-tuning in their experiments to serve as a baseline comparison?\n2. Would it be possible for the authors to include an experimental comparison with Addax [1]? Given that Addax is a prominent hybrid FO-ZO method, this comparison would provide valuable context for the proposed approach.\n3. Could the authors provide a more detailed explanation of the term $d$ in their theoretical results? Specifically, clarification is needed on why  $d$ in Theorem 3.6 denotes the per-layer input width rather than the total number of model parameters, as the latter is a more common definition in this context.\n\nI would be willing to reconsider my score if these concerns are satisfactorily addressed.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. FZOO introduces a novel implementation that estimates more accurate zeroth-order gradients using batched one-sided estimates and Rademacher random-vector perturbations. This approach eliminates the two forward passes required by MeZO.\n2. In experiments, FZOO demonstrates both improved speed-ups and higher model quality.\n3. Similar to the original MeZO, FZOO is orthogonal to PEFT techniques.", "weaknesses": "1. I am unclear on the convergence results in Theorem 3.6 due to an apparent inconsistency in the definition of $d$ . The main text defines $d$ as the total number of model parameters; however, Appendix H. 1 clarifies that $d$ represents the per-layer input width, not the total parameter count. It is surprising that the zeroth-order method's convergence rate would be independent of the total number of model parameters.\n2. The paper do not discuss and compare with an important, closely related line of work: hybrid first-order (FO) and zeroth-order (ZO) methods (e.g., [1,2]). A notable example, Addax [1], which adaptively combines FO and ZO gradient estimations based on input sequence length, is particularly relevant and warrants comparison.\n\n[1] Li, Zeman, et al. \"Addax: Utilizing zeroth-order gradients to improve memory efficiency and performance of sgd for fine-tuning language models.\" arXiv preprint arXiv:2410.06441 (2024).\n\n[2] Chen, Jiahe, and Ziye Ma. \"VAMO: Efficient Large-Scale Nonconvex Optimization via Adaptive Zeroth Order Variance Reduction.\" arXiv preprint arXiv:2505.13954 (2025).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nbSQIa3daJ", "reviewer": "Reviewer_pkyA", "summary": "The paper introduces FZOO, a zeroth‑order optimizer for LLM fine‑tuning that (i) uses batched one‑sided function evaluations and an adaptive step size normalized by the batch loss standard deviation, linking its update to normalized‑SGD, (ii) accelerates each step via Rademacher (±1) perturbations that enable efficient batched parallelism. Experiments show FZOO typically beats MeZO by ~+3% accuracy while using ~3× fewer forward passes across various datasets and tasks. On RoBERTa‑large reports Adam‑like convergence at inference‑level memory, with accompanying proofs of normalized‑SGD equivalence and convergence guarantees.", "questions": "1. Theorem 3.6 requires d framed as “parameter dimension”, what is the correct setting?\n\n2. The advertised 1.92× speedup (OPT‑125M, N=8) compares against an 8‑perturbation sequential baseline, realistic strong baselines like MeZO with N=1 or two‑sided ZO with efficient batching. what causes this inflation?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. FZOO brings normalized‑SGD’s normalization into the ZO regime by scaling updates with the batch loss standard deviation and using one‑sided estimates, making ZO steps both more stable and step‑efficient.\n\n2. The paper proves a formal link to normalized‑SGD and a convergence guarantee under standard smoothness/variance assumptions\n\n3. Rademacher (±1) perturbations enable per‑layer sign‑flip/add operations and batched parallelism, yielding speed‑up.\n\n4. Strong empirical gains across scales and tasks, and Inference‑level memory footprint", "weaknesses": "1. 3.3 argues Rademacher allows “bit‑level” sign flips so additions replace multiplies, there is no roofline or kernel profile to substantiate “addition beats multiply” benefits at scale.\n\n2. The paper compares to prefix‑tuning, but omits head‑to‑head QLoRA/LoRA+Adam under matched memory/throughput budgets, which are widely used and could potentially alter the claimed end‑to‑end efficiency picture.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wcUI4jxAC3", "reviewer": "Reviewer_ovaX", "summary": "This paper studies the memory and convergence tradeoff in zeroth-order optimization. The paper proposes FZOO (Fast Zeroth-Order Optimizer), a novel optimization method designed to fine-tune large language models with inference-level memory usage while achieving Adam-like convergence speed. The method combines batched Rademacher random perturbation with adaptive learning rate to mimic normalized-SGD (and Adam) behavior. The paper shows that the proposed algorithm converges in $O(\\sqrt{d}/\\sqrt{T})$ by properly choosing learning rate and perturbation stepsize.\n\nNumerical results shows that the proposed method outperforms existing MeZO method in both final accuracy and convergence speed.", "questions": "Please address the above weakness, especially the comparison with other structural perturbation methods.\n\nAlso, in the equations on page 20, I think some expectations are missing.\n\nThe final steps on page 21 (from line 1904 to lines 1104) do not look correct to me. I think a V term is missing in the first term, and thus, the main theorem 3.6 is incorrect. \n\nBy having the term $\\sigma_*/\\sqrt{(\\bar{\\sigma}_t^{-2})^{1/2}} \\geq 1$, it seems like the normalization is slowing down the convergence?", "limitations": "", "rating": 2, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposed a novel approach to compute the activations for the perturbed model with Rademacher perturbation. The proposed method speeds up the loss computation.\n2. The paper proposed using the batched loss variance to normalize the stepsize, which enables accelerated convergence speed.\n3. The paper demonstrated promising numerical results showing FZOO outperforms MeZO and HiZOO in multiple settings.", "weaknesses": "1. Missing discussion on the effect of normalization with estimated variance. The author should further compare the convergence results with and without normalization. The current discussion in section 3.4 is insufficient to demonstrate the usefulness of the normalization. As we know, normalized SGD actually fails to converge to a stationary solution in specific problems.\n\n2. Missing reference to existing ZO algorithms that use structured/directional perturbation. E.g., [R1-R4]. The proof technique is standard for ZOO with either Normal or Rademacher random perturbation.\n\n3. The paper should compare the proposed FZoo method with other structural perturbation methods or variance-reduced methods.\n\n[R1] Belouze, G. Optimization without backpropagation, 2022. URLhttps://arxiv.org/abs/2209.06302.\n\n[R2] Rando M, Molinari C, Villa S, Rosasco L. Stochastic zeroth order descent with structured directions. Computational Optimization and Applications. 2024 Dec;89(3):691-727.\n\n[R3] Ma S, Huang H. Revisiting zeroth-order optimization: Minimum-variance two-point estimators and directionally aligned perturbations. In The Thirteenth International Conference on Learning Representations 2025.\n\n[R4] Shao, W., Albayrak, S. (2023). Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives. In: Nicosia, G., et al. Machine Learning, Optimization, and Data Science. LOD 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HMoOSYq0Y0", "reviewer": "Reviewer_jSd5", "summary": "This paper presents a new zeroth-order optimizer leveraging the idea from normalized-SGD. In comparison to the zeroth-order optimizer of MeZO,  the authors propose the following changes: (1) Generate the perturbation using Rademacher random vectors instead of a Gaussian distribution; (2) Average multiple one-sided difference estimates instead of using one two-sided difference estimate; (3) Normalize the gradient its estimated standard deviation; (4) Enable efficient implementation via batched forward pass.\n\nThe authors show that the proposed method can achieve better performance with a greatly improved the convergence rate.", "questions": "1. All the files under https://anonymous.4open.science/r/FZOO-5927 show the error message of \"The requested file is not found.\".\n\n2. This paper doesn't include an extensive ablation study. In particular, the reviewer wonders which change contributes the most for improving the convergence speed. It seems the normalization step is the most important one. Does normalization + Gaussian perturbation work? Could the authors run further ablation studies to test the effectiveness of each proposed change?\n\n3. It seems that averaging multiple estimates naturally enables using one-sided difference estimates. Have the authors tested the difference between averaging over N one-sided estimates v.s. averaging over N/2 two-sided estimates?\n\n4. Could the authors elaborate a bit more on why batching recovers little speed-up for MeZO?\n\n5. It would be useful to also compare against Addax (https://openreview.net/forum?id=QhxjQOMdDF).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well-written, clear, and, easy to follow. The proposed method is elegant, simple, but effective.\n\n2. FZOO shows sizable improvements over MeZO in both convergence speed and model quality.\n\n3. The authors conduct extensive experiments to support the effectiveness of the proposed method.", "weaknesses": "1. This paper doesn't have an extensive ablation study to test the effectiveness of each proposed change. (The ablation study only tests the effect of N, the number of perturbation directions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)