PseuZO: Pseudo-Zeroth-Order Algorithm for Training Deep Neural Networks
Authors: Pengyun Yue
Xuanlin Yang
Mingqing Xiao
Zhouchen Lin
Venue: NeurIPS 2025 poster ()
Keywords: zeroth-order optimization
LLM fine-tuning
Primary area: deep_learning
TL;DR: We propose Pseudo-Zeroth-Order (PseuZO), a framework that estimates Jacobian matrices via model output differentiation and applies EMA for variance reduction, with theoretical convergence guarantees and empirical validation.

Abstract: Zeroth-order Optimization (ZO) has received wide attention in machine learning, especially when computing full gradient is expensive or even impossible. Recently, ZO has emerged as an important paradigm for memory-efficient fine-tuning of large language models (LLMs), circumventing the memory overhead of backpropagation. However, existing ZO gradient estimators exhibit dimension-dependent variance scaling as $\Theta(d)$, leading to dimension-dependent convergence rates without further assumptions on the objective function, which is prohibitive for large-scale LLM parameters. To address this problem, we present a Pseudo-Zeroth-Order (PseuZO) framework for optimizing composite objective functions, especially large-scale models: $ \min_{\mathbf{x} \in \mathcal{X}} \mathcal{F}(\mathbf{x})= \bbE_{\mathbf{z}} g\circ h(\mathbf{x};\mathbf{z}) $, where $h$ represents complex, high-dimensional representations and $g$ is a task-specific loss. While existing zeroth-order methods estimate gradients with final loss functions, our PseuZO algorithm estimate the Jacobian matrix of $h(\mathbf{x})$ with the model output $\mathbf{o}= h(\mathbf{x})$, and the gradient of the loss function on model output $\mathbf{e} = \nabla_{\mathbf{o}} g(\mathbf{o})$, and apply exponential moving average on Jacobian estimators to reduce the variance. Moreover, we use the sliding window technique to reduce memory costs. Our algorithm achieves an $O( \max \lbrace \alpha_1 L\epsilon^{-2}, \alpha_1 L \sigma_2^2\epsilon^{-4} \rbrace )$ convergence rate, where $\alpha_1$ is the effective dimension of $\mathcal{F}$.
  Experimental results demonstrate that PseuZO outperforms MeZO and MeZO-SVRG in classification, multiple choice and generation tasks in both full-parameter and PEFT fine-tuning settings by boosting convergence in the early stages of training. For instance, under the same computation time, with respect to SST2 task, PesuZO gets 9.8\% higher accuracy than MeZO (91.2\% v.s. 82.4\%). With the sliding window technique, our PseuZO achieves $70\%\sim80\%$ memory reduction compared to FO-SGD for different model sizes as PseuZO only introduced a small dimension-independent memory overhead, which enables efficient scaling of the model size. The code is available at https://github.com/YangBigMn/PseuZO.
$\newcommand{\bbE}{\mathbb{E}}$

PseuZO: Pseudo-Zeroth-Order Algorithm for Training Deep Neural Networks
Pengyun Yue",, Xuanlin Yang! Mingging Xiao! Zhouchen Lin
State Key Lab of General AI, School of Intelligence Science and Technology. Peking University IInstitute for Artificial Intelligence, Peking University
Pazhou Laboratory (Huangpu), Guangzhou, Guangdong, China
Microsoft Research Asia
Zhongguancun Academy
yuepyēpku edu. cn, www.auannnnnnnna.e pku. edu. en, fmingqing _iao, zlin]@pku. edu, cn
Abstract
Zeroth-order Optimization (ZO) has received wide attention in machine learning, especially when computing full gradient is expensive even impossible. Recently, Zo has emerged as an important paradigm for memory-efficient fine-tuning large language models (LLMs), circumventing the memory overhead of backpropagation. However, existing ZO gradient estimators exhibit dimension-dependent variance scaling (d). leading to ther assumptions on the objective function, which prohibitive for large-scale LLM parameters. To address this problem. present a Pseudo-Zeroth-On -rder (Pseu7O) framework for optimizing composite objective functions, especially large-scale models: minxe F(x)= EEg. (xxx2). where h represents complex, high-dimensional representations and g is a task-specific loss. While existing zeroth-order methods estimate gradients with final loss functions, our PseuZO algo- rithm estimate the Jacobian matrix of h(x) with the model output o = hxx), and the gradient of the loss function model output tial moving average on Jacobian estimators to reduce the variance. Moreover, we use the sliding window technique reduce memory costs. Our algorithm achieves an O mmax { a Le a, Laže +)3 convergence rate, where a₁ is the effective di- mension of F. Experimental results demonstrate that PseuZO outperforms MeZO and MeZO-SVRG in classification, multiple choice and generation tasks in both full- pallmmerrrttrr and PEFT fine-tuning settings by boosting convergence in the early stages of training. For instance, under the same computation time, with respect to SST2 task, PesuZO gets 9.8% higher accuracy than MeZO (91. v.s. 82.4%). With the sliding window technique, our PseuZO achieves 70% 80% memory duction compared to FO-SGD for different model sizes as PseuZO only introduced small dimension-independee
dependent convergence rates without fur-
Vog(o). and apply exponen-
memory overhead, which enables efficient scaling the model size. The code is available at https://github.com www..e///aaaggigi////ee///
Introduction
Zeroth-order optimization 445 20 36 has served as a core technique for problems where gradient
calculations impractical. These methods rely solely function evaluations, making them uniquely suited for black-box scenarios like adversarial attacks [ [5 reinforcement learning [ [4],
and hyperparameter tuning X 37 Compared to first-order and higher-order optimization methods,
"Equal contribution.
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

their key strength lies in avoiding gradient computations a critical advantage when optimizing complex systems where automatic differentiation is infeasible or prohibitively expensive. For modern deep neural networks, this approach significantly reduces memory demands by eliminating backpropagation 's computational and memory cost. Recent advances have reinvigorated zeroth-order methods as practical tools for deep neural network training, particularly in resource-constrained environments where traditional optimization strategies struggle to scale.
Large language models (LLMs) represent the pinnacle of deep neural network architectures, achieving state-of-the-art performance across diverse language understanding and generation tasks [ 60.
16.. The standard paradigm of pretraining on web-scale corpora followed by task-specific fine-tuning has become ubiquitous, enabling these models to adapt to specialized domains. However, conventional first-order fine-tuning approaches employing paraameerr optimization through backpropagation face critical scalability barriers: the memory overhead for storing optimizer states and activation values grows with model parameters and context length, becoming prohibitive for large-scale models. This challenge has driven the emergence of parameter-efficien fine-tuning (PEFT) techniques [1 that strategically update only subsets of model weights, Another way to reduce memory costs is using memory-efficient zeroth-order optimization (MeZO) M4). MeZO introduces a paradigm shift by operating purely through forward-pass evaluations. By eliminating backpropagation while maintaining competitive task adaptation capability, MeZO addresses the dual requirements of memory conservation and optimization stability in centtrre- scenarios, enabling the deployment of massive LLMs in practical applications.
25 B5 55
While zeroth-order optimization provides gradient-free alternative for fine-tuning large neural networks, its practical adoption faces fundamental limitations. Zeroth-order algorithms exhibit catastrophic performance when training from scratch. Even for fine-tuning tasks, the convergence rate of classical zeroth-order methods scales linearly with parameter dimension d, becoming prohibitive for modern architectures where d routinely exceeds 1020, This dimension dependence persists in practice even when leveraging low-effective dimensionality theories 56 or the sparsity of the model structure 24
In this paper, we propose Pseudo-Zeroth Order (PseuZO) framework for optimizing composite objective functions:
min Ez~DD h(x;
(I)
xEX
This problem formulation is prevalent in deep neural network training, where h represents complex, high-dimensional representations and g is a task-specific loss. Unlike traditional zeroth-order methods, PseuZO methods estimate the Jacobian matrix of h(x) with the model output h(x). Compared to the value of the composite function g h, the output of h provides more information about the function h. We also apply exponential moving average on Jacobian estimators reduce the variance. Finally, we obtain the gradient estimator with the Jacobian estimator and the gradient of the loss function on model output e (o. which can often be computed explicitly. We demonstrate the efficacy of PseuZO methods both theoretically and empirically. In theory, we prove that PseuZO method finds an e-stationary point with O (max Le az Loge =}) function evaluations, where a1 is the effective dimension of the objective function F. In our experiments. PseuZO not only converges faster, but also attains a precision improvement of up to 9.8% compared to MeZO. With extra memory
the sliding window technique, Pseu7.0 only needs small ciimension-inddeendeee overhead compared to MeZO, which enables efficient scaling of the model size. Additionally, we incorporate PseuZO with LoRA and prefix-tuning to show that PseuZO is also compatible with PEFT techniques.
We summarize our main contributions below:
1. We propose PseuZO optimization framework, which uses the differentiation of model outputs to compute a stochastic Jacobian estimator, and apply exponential moving average to reduce the variance. In practice, we use the sliding window technique to reduce memory costs.
2. We proved that the convergence rate of PseuZO method not explicitly dependent on the parameter size. We theoretically prove that our PseuZO optimization method finds an e-stationary point in O (max {an Le -2, on Loze -13) function evaluations, where on the effective dimension.

---

3. We conduct solid and comprehensive experiments which show that PseuZO outperforms ICL and MeZO across multiple tasks, including classification, custiiclassiiication and generation in terms of convergence speed. With the sliding window technique, PseuZO only shows a small fine-tuning tasks. Moreover, we find that PseuZO is compatible with PEFT like LoRA and prefix-tuning, and results show that PscuZO+PEFT also outperforms McZO+PEFT across classification, multi-classfficttoon and generation tasks in terms of convergence speed.
memory overhead compared to MeZO for instruction
2
Related work
Zeroth-order optimization. Zeroth-ordet optimization 45 20
66
has been widely studied in the
field of machine learning, and has been used in black-box optimization 22
[50] adversarial attacks 19.9 etc. Most zeroth-order methods are designed based on first-order 33 or higher-order methods
[50] and are often d times slower where d is the dimension of the problem. To mitigate the curse of dimensionality. several works proposed effective dimension (56] (4), and characterize the convergence rate with the effective dimension of the problem. Many studies also consider reformulating the neural network at relatively small scale to solve a simpler optimization problem
47 7 and then utilize block coordinate descent (BCD) or ADMM KK without the need for gradients. Recently, MeZO M4 successfully applied zeroth-order optimization to fine-tuning extremely large language models by efficiently estimating gradients in memory. After that, many works attempt to improve the performance of MeZO by reducing variance [ introducing estimated second-order information 660 In the research of Spike Neural Network (SNN), [54] used the model output to estimate the Jacobian matrix, but their work was designed from biological applicability, and was not able to save memory costs. Inspired by (54), we designed our PseuZO optimization framework.
330
Memory-efficient backpropagation. As LLMs are typically fine-tuned by first-order algorithms like SGD [22 and Adam (28]. many new methods or techniques have been proposed to solve the memory overhead problem, e.g. sparsifying gradients [46 [33] and quantization [15]. Other useful
techniques to save memory for activation values or optimizer states like Gradient Checkpoint [8],
Flash Attention 12 and Zero Redundancy Optimizer (ZeRO) A1 39 40) However, these methods
either sacrifice precision or require more computation time.
Gradient-free adaptation of LLMs. Language models can understand language and learn to communicate with humans after the pre-training phase. They can then generalize to tasks without training and this form adaptation that requires appropriate prompt designs is called in-context learning (ICL). Another paradigm to estimate first-order or second-order information only using inference. Besides MeZ0 estimating first-order information by two forward processes, HiZOO leverages three forward processes to estimate second-order information considering heterogeneous curvatures across different parameter dimensions [60]
3 Pseudo-Zerott-order algorithm framework
3.1 Zeroth-order algorithms
Zeroth-order algorithms are a class of optimization algorithms that do not require the computation of gradients. Instead, they rely noisy function value oracles to update the parameters. This makes them useful for problems where the computation of gradients is expensive or infeasible. Typically, zeroth-order methods use noisy function values to generate gradient estimators. Suppose the objective function is f R., + R. Two most common gradient estimators are RGE [36] and CGE [I]:
1 ʃ(x
u&:) f(x) E., CGE: v.f((x = Σ
ʃ(x + me::) f(x) e.
RGE: vaf((x=
9
/
(2)
where & ~ I) and {e,} a set of standard basis vector. When j + 0, CGE become the full gradient, and RGE tends to
fs(x)= =
(v)()),
3

---

This is an unbiased estimation of fx(), with variance @ (4) Without further assumptions on objective functions, optimizing with RGE CGE needs d times more zeroth-order oracles than optimizing with first-order methods using gradient oracles, severely limiting their upplicability in high-dimensional scenarios. However, if the objective function has low effective dimension sparsity structures, zeroth-order methods can achieve faster convergence rate [56 60).
3.2 Pseudo-zeroth-order algorithms
In this paper, we study the composite optimization problem:
min F(x) Egg(h(x;;)), where X' C RR, XEX
where h X - H C Rd defines the representation mapping and y H. - R+ is loss function. In machine learning, the representation mapping 124 + Rd is typically parameterized as a neural network h(x; z), where denotes the learnable parameters and z ~ D denotes the stochastic input data. The exact stochastic gradient admits the thcoretical decomposition:
[xF(xx) = EZND J (x:z) Vng(h(x;z))
(5)
Stnchentic Bundion
Upsiticen graabert <last
clp
The implementation stochastic first-order methods requires efficient computation of FxF((x via backpropagation through the compositional structure g h. While the outer loss g admits tractable gradient computation (Vng is typically fooedd-for),, the inner mapping's Jacobian J,, (x; z) becomes computationally intractable for deep nonlinear parameterizations.
Unlike standard zeroth-order (ZO) methods that solely utilize function evaluations of y o h, our key insight stems from the asymmetric differentiability inherent in composite optimization: While acquiring exact gradients through the inner mapping l(x;; z) remains computationally prohibitive due to computational constraints or non-di non-iiffeeeet operators, the gradient of the outer function can be explicitly or efficiently computed.
Our method exploits composite structure's 's asymmetric differentiability:
Outer gradient: Closed-form Vog(o) for o h((;; z);
Inner estimation: Zeroth-order approximation for h Jacobian.
The P70 gradient estimator combines both components:
P F(x;z) = [i(x (E:z) h(x;2)
(6)
where & ~ IO. As this converges P20 2) = (E TE e) EE J which is
an unbiased estimation of Vx()). To reduce the variance introduced by the random vector &, we propose a momentum-accelerate variant through exponential smoothing:
11(x + 2$:2) h(x;z)
A = (1 A1
E & + +AA
(7)
1
PZO
F(x:2) = Tee P
(8)
The full algorithm is shown in Algorithm
Remark 1. The gradient estimator of PseuZO P70 F(x;)) A theoretically outperforms
MeZO and its momentum variant in terms of both bias and variance, as detailed in Appendix D PseuZO has smaller variance compared to Me70 and Me70 with momenetum, and Me70 has an extra bias term caused by the curvature of g. These theoretical advantages demonstrate the effectiveness of the exact outer gradient and exponential smoothing of Jacobian estimations.

---

Algorithm Matrix-based PseuZO Algorithm
Require: Momentum factor B E (0,1), smoothing coefficient μ >> O, max iterations T, initial point
Xg
Ensure: Gradient estimate F z)
1: Initialize momentum buffer 1 f- E Rduu
2: for = 0 to T do
3: Sample random vector & ~ (0,1)
4: Compute forward difference Ao; f- hix: +1E: (
5: Receive noisy Jacobian estimator B, AorE Momentum update:
6:
7:
A₁ + (1 - B, + ArAr-1
> Exponential moving average
8:
Compute outer gradient e; Vog(h((;2z))
9:
Gradient projection: 4P20 F(x;; 2.) t- Af
10:
Update x: X++1
12 ( F(x:2:)
11:
end for
3.3
Convergence of PseuZO algorithm
In this subsection, we deviate from the exact realization of stochastic Jacobian estimators, and assume that the PseuZO algorithm receives a noisy Jacobian estimator in each step. Under this more general setting, we prove the convergence of PseuZO method. We first list some assumptions which are necessary for our analysis and has been widely adopted in research works on optimization:
Assumption 2. FE has continuous Hessian matrices H(x), and satisfy the following equations:
[X)))l I L, tr (H(x)) I an
where is the effective dimension of F. In the worst case, a1 dg-
Assumption 3. Denote F((x)) = vxg(h(x;;zz)) The randomness of the Jacobian estimator B, can be decoupled into the following parts:
B, = (J, D.)N, + M.,
(10)
where J, is the true Jucobian matrix of at X,, and:
N₁ represents the randomness introduced by the PZO Jacobian estimator:
EN, = I, E al I 3tr (M) ||a||3
(11)
where is arbitrary vector.
D: represents the randomness of data:
e,
ED, 0,
BIDDe e <oz;
(12)
M, represents the noise introduced by the two-point estimation of the function value, controlled by μ.
EIMM e. 1T
(dp + 6)
(13)
According to the analysis on the two-point gradient estimators in 36 B, /1(x++1(=))) h(x:z)
satisfies Assumption where & N NO. I). Now, we propose the informal version of our convergence theorem in Theorem For the formal version and the proof of Theorem please refer to the Appendix
T Theorem 4 (Informal). Under Assumption 2 Pand if p. and 9r satisfy certain conditions, Algorithm finds an 6-stationary point with O (axx (or Te on Lage -1) 11) function value computations.
Remark The convergence rate of Algorithm iis on times slower than the standard SGD algorithm, where an is not explicitly dependent the dimension of the problem.
5

---

3.4 Sliding window-based PseuZO algorithm
As is memory inefficient to store such large-scale tensor A, (outer product of Gaussian noise and an output tensor) introduced in PseuZO, we propose several techniques to reduce the memory cost and obtain Sliding Window-based PseuZO shown Algorithm
reciprocal descent
t-L+2
L-L+3
epoch
(a) sliding window
(b) lambda curve
Figure 1: (a) is schematic diagram of the sliding window with length L. We obtain the corresponding coefficients of all sliding window units by expanding the iterative L times. (b) is a variation curve with three cycles. Each cycle means a restart operation and when À is close zero, we set À = 0 to reduce time consumption.
Sliding window technique. To tackle the memory overhead of PseuZO, use sliding window to store random seeds and output tensors in the last few steps. When the sliding window shown in be
Figure Ta is determined, the corresponding coefficient for each unit in the sliding window obtained by expanding the EMA formula. On the one hand, we can resample the same Gaussian noise& & with the same seed there is need to store these random vectors
[4 On the other hand, as 0 < X < 1, especially when À is smaller, the weight for older information is close to zero in the
EMA step of PseuZO method. Therefore, truncate outdated information with the sliding window technique.
Changing the storage target. However, storing several output tensors with shape of the vocabulary size still unacceptable, as the vocabulary size is generally large among LLMs. So we choose to store the last hidden state with much smaller size and trace its path to the final loss to obtain its gradient without excessive memory overhead. For OPT1 13B, the last hidden state (i.e. the input tensor for Im head) size is 2048 while the vocabulary size is larger than 50000 58 Thus further reduce memory overhead caused by the sliding window.
Periodic dynamic changing of A. To meet the convergence requirements, À needs to gradually decrease to zero. We take advantage of restart operation to further boost convergence and thus À is designed in a periodic changing manner as shown in Figure [b When À approaches zero, PseuZO gradually degenerates to ZO method and thus we directly transform to McZO instead. If we consistently use PseuZO throughout the entire process, the time cost is roughly 2 x that of McZO. However, with appropriate design for X, the time cost can be reduced to almost the same as McZO.
Experiments
In this section, we evaluate Sliding Window-based PseuZO variety of typical fine-tuning tasks by comparing performance against McZO [4. McZO-SVRG 19, HiZ0O-L [60 and memory overhead against MeZO-SVRG memory usage of PseuZO is significantly smaller than MeZO-s SVRG and FO-SGD; 2) Through the sliding window technique, with fixed memory overhead that is independent of the model size compared to MeZO, PseuZO has much better performance than MeZO. MeZO-SVRG and HiZOO-L. 3) PseuZO is also compatible with PEFT techniques like LoRA 2 and prefix-tuning B1].
well FO-SGD. Experimental results show that: 1) The peak
Setup. We implement PseuZO, MeZO-SVRG and HiZOO-L in the MeZO framework with appropri- ate adjustment for fair comparison. We conduct comprehensive experiments in various tasks on large auto-regressive language models like 1.3B [X and the same prompt design as Me7.0 is utilized which is effective and fair for comparison for various datasets including GLUE 52 and SuperGLUE

---

Algorithm 2 Sliding Window-based PseuZO Algorithm
Require: Momentum factor formula X(I) E (0, 1), smoothing coefficient >> 0, max iterations T,
initial point Og. sliding window length L, coefficients {uxJk=1
Ensure: Gradient estimate FP20 F(;;))
1: Initialize the sliding window as deque ((maxlen=L)
2: for = 0 to T do
3: Update À X(t)
4: Compute coefficients Wg <- (1 A)
5:
Sample random seed 8 and corresponding vector & ~ (N,,
Compute forward difference Δo; f- A(x+ -
6:
7:
Compute outer gradient e, t Vog(h(x;;z))) Update sliding window D.append 8t, Ao.)
8:
9:
Gradient projection initialization: V!!e F(x; Ze) +
10:
for k 1 to L do
> Iterate sliding window
8, Ao D2 Resample & ~~ (0,10,
12:
13:
Accumulate F(r;)((x; f FPZ0 F(x;;))) (Ao, ex)
14: end for
15:
Update 6: 0141 t 01 - -
16: end for
Task Task type
SST-2
RTE
CB
BoolQ classification
WIC
MultiRC
CОРA mulltppe choice
ReCoRD
DROP
generation
Zero-shot
53.5
53.0
45.7
43.3
51.5
75.0
70.5
ICL
80.0
53.0
46.4
58.7
47.1
51.1
46.2
69.0
71.0
20.4
MeZO-SVRG
61.5
55.5
60.3
52.0
50.0
54.0
50.1
0.0
McZO (10K steps)
82.4
54.3
76.0
60.7
51.0
50.9
54,9
74.0
57.6
20.3
McZO (20K steps)
88.4
58.8
76.0
63.8
53.0
51.3
53.9
73.0
58.9
20.3
HiZ00-L
88.1
54.9
69.0
64.8
51.2
58.0
58.2
73.0
58.8
23.3
PseuZO (10K steps)
91.2
58.0
77.0
64.3
58.0
54.5
54.7
78.0
60.0
23.5
PscuZO (20K step)
90.7
63.3
67.0
57.0
59.7
60.6
60.9
FO-SGD
92.4
67.8
94.0
60.8
52.6
47.4
53.8
76.0
57.2
26.0
Table Experiments on OPT-1.3B with 1024 training samples and 512 evaluation samples. When training, for WSC, CB and COPA, they have much less total samples and thus we set aside 100 evaluation samples and use the rest for training. The bold number represents the highest evaluation performance excluding FO-SGD.
51 benchmarks. We run all experiments 10K steps and evaluate performance of the model every 2K steps for HiZ0O-L and MeZO-SVRG. In order to ensure that Me7O and PseuZO are sufficiently convergent, we run PseuZO and MeZO for 10K and 20K steps, respectively. We choose K 16 as the batch size and randomly select 1024 samples for training and 512 samples for evaluation. All experiments are run on single Nvidia A800 40GiB GPU.
Task
SST-2
RTE
CB
BoolQ
WSC
WIC
COPA
McZO
84.4
58.0
76.0
64.0
54.0
52.5
88.0
PseuZO (ours)
91.8
58.4
77.0
68.9
58.0
55.3
90.0
Table 2: Experiments OPT-6.7B for PseuZO versus Me7O. The bold number represents the better evaluation performance.

---

Task Task type
SST-2
RTE
CB
BoolQ classification
WSC
WIC
MultiRC
COPA _multipc choice
ReCoRD
DROP
generation
Me70+LORA
90.8
59.1
76.0
64.6
50.0
52.7
54.5
81.0
59.5
22.9
PscuZO+LoRA
91.2
58.8
79.0
65.8
51.0
51.8
54.3
83.0
60.2
25.7
McZO+prefix
71.0
51.7
45.0
57.6
54.0
50.6
50.8
75.0
57.4
15.5
PseuZO+prefix
80.7
53.1
71.0
61.7
49.0
51.0
52.7
75.0
57.8
21.2
Table 3: Experiments on OPT-1.3B for comparison between McZO+PEFT and PscuZO+PEFT. PEFT is either LoRA or prefix fine-tuning.
4.1 Auto regressive model performance
PseuZO performs much better than McZO, McZO-SVRG and HiZOO-L in the classification, multiple choice and generation tasks shown in Table | As MeZO-SVRG needs to traverse all samples to obtain the full-batch gradient IT. large numbers of iterations have an expensive memory overhead. However, MeZO-SVRG still performs worse than PseuZO, especially for multiple choice and generation tasks with small batch size and large full batch size. For HiZOO-L. (60), it not only requires three forward propagations, but also requires low-rank processing of matrix parameters, which increases the time overhead. In fact, running HiZOO-L and MeZO-SVRG for only 10K steps takes much longer than running PseuZO for 20K steps. As shown in Appendix D PseuZO takes advantage of the small bias and variance to achieve fast convergence, further reducing the gap with FO-SGD and even outperforms FO-SGD in many tasks.
required or it will
PseuZO is also compatible with other memory efficient techniques, like LoRA and prefix tuning, and the corresponding results are shown in Table 3 As both LoRA and prefix tuning have much fewer parameters to optimize (0.1% % and 0.01 % of the original number of parameters respectively for OPT1 (.)) so that the number of convergence steps required will be lower, the performance gap between MeZO+PEFT and PseuZO+PEFT is much smaller than that of MeZO and PseuZO.
4.2 Memory usage and time computation
fpsezzo
OPTI.3B
OPT2.7B
OPT6.7B
Mezo MVZD-SVfi
FO 590
10
9300
9600
9900
PZD
25
20
8700
9400
9700
20-
Memory
50
6800
8400
9300
15
10-
100
3600
7000
8700
150
400
5100
8000
opt-1.38
opt-2.7
opt-6.7B
opt-136
Model
Table 4: freeuo and its corresponding num- ber of the total steps to guarantee the time that does not exceed 10K execution time for MeZO.
Figure Memory overhead for different mod- els under various ZO algorithms and FO-SGD. * means out of memory.
PseuZO seales up to almost the same model size as Me70 can scale up to as PseuZO only introduces a small dimeensin-inndepeddett memory overhead. Memory usage for different scale models is illustrated in Figure 2 which verifies conclusion that compared to McZO, excessive memory overhead of PseuZO IS independent of the model size. Additionally, we also compare memory overhead for the different batch size and max length. As shown in Table 5] the memory requirement of PseuZO is more sensitive to the batch size and max length due to the sliding window. However, model size has greater impact memory, PseuZO still needs less memory than MeZO-SVRG (MeZO-SVRB needs to store full parameters during training (19).
The computation time required for each epoch of PseuZO is approximately twice that of each epoch of MeZO for OPT-1.3B but the gap for large scale models will gradually decrease. We fix the total steps of MeZO 10K and obtain the corresponding total steps of PseuZO for different
8

---

Memory Usage in GiB OPT-1.3B
Memory Usage GiB for OPT-6.7B
Fixed context length (cl=128)
Fixed batch size (bs=16)
Fixed context length (cl=128)
Fixed batch size (bs=16)
Method
he=16
bs=32
hum64
cl=256
cls512
he=16
baa32
bea64
cl=256
cls512
FO
30.30
McZO
5.35
7.58
11.87
9.06
17.03
17.09
20.35
27.51
21.28
27.01
SVRG
10.55
12.76
17.55
12.46
19.67
00M
PseuZO
7.61
10.58
17.85
11.69
19.36
18.08
23.22
33.52
25.16
32.74
Table Memory usage (GiB) comparison on BoolQ for different ZO methods with OPT1.3B and OPT-6.7B showing that PseuZO can scale up to larger models as MeZO.
Dataset
SPSA
Z0 sp
PscuZO
PscuZO (w/LL)
BP
MNIST
86.4 0.15
87.8 + 0.09
98.7 + 0.02
98.5 = 0.02
CIFAR-I0
41.3 + 0.74
42.6 + 0.69
82.5 0.15
88.7 + 0.13
89.9 - 0.06
CIFAR-100
5.39 + 0.69
7.61 0.73
61.4 0.14
68.5 0.13
71.9 = 0.09
Table 7: Training from scratch typical computer vision classification datasets for various feedback methods. We do not use local loss for MNIST as there are only two hidden layers.
Pseezo under the same computation time where Ppeezoo is the number of total epochs using PseuZO and results are shown in Table 4
4.3 Ablation study
As introduced before, our sliding window has four key factors denoted as 1) L: sliding window length: 2) fPsezoo: number of epochs to execute PseuZO for each cycle: 3) R: number of cycles: 4) X(t): the formula for À to descend with respect to epoch t. We perform ablation studies on SST2 to explore their individual impact on precision and the results are shown Figure 3 and Table 6 we keep À small constant like Amin = 0.1, the accuracy is close to that of MeZO. In fact, when 0, PseuZO gradually degenerates to MeZO without momentum. More ablation experiments, including MeZO with momentum and PseuZO without momentum, can be found in Appendix A We empirically found that performance is largely insensitive to the sliding window parameters. Since there is no need to set L, PPeuzo and R too large, smaller values are chosen to balance low memory and time overhead.
10
91.0
Accuracy (86)
A(t)
Accuracy($))
90.5
90.0
ful
Constantl
A(t)
Aum
83.9
89.5
Constanr2
X(1)
Auis
82.7
X(t)
Amax(!
90.3
Reciprocal
Avaa
r=
91.2
Figure 3: Ablation studies for L, Ipsea70 and R. "full" means using PseuZO for all epochs.
Table 6: Ablation study for different de- formula X(L) when < 4psea70.
4.4 Training from scratch
During ZO optimization, the variance introduced by the large number of parameters is difficult to control and thus an appropriate prompt design significant to guide generation [4 [9] for instruction fine-tuning. Furthermore, it remains problem for 70 algorithms like SPSA to train from scratch even for small datasets. However, with simple reformulation named Node Perturbation [2] PseuZO shows great performance these tasks. The reformulation details and further explanation

---

can be found in Appendix B As shown in Table 7 PseuZO in Node Perturbation manner outperforms SPSA and other signal feedback methods and with incorporation local learning (26). PseuZO can even perform well as BP. It demonstrates the potential of PseuZO to be used for more difficult but significant settings.
5
Conclusion
In this paper, we propose new algorithm framework PesuZO and apply to various instruction fine-tuning tasks for LLMs. According to our theoretical analyses, PseuZO finds e-stationary point in O maax {ai L a, ())e-1) function evaluations. Experimental results demonstrate that PseuZO outperforms MeZO and MeZO-SVRG among various tasks. We propose sliding window technique, making the memory overhead independent of the model size. As a limitation, PseuZO needs store the sliding window and the extra memory sensitive the batch size and max length. A possible fix to this problem is to add an low-dimension auxiliary layer as the new storing target. Though this method can further reduce memory overhead, it changes the model structure which might reduce its representation capability.
Acknowledgments and Disclosure of Funding
Z. Lin was supported by National Key R&D Program of China (2022D0110000), the NSF China (No. 62276004) and the State Key Laboratory of General Artificial Intelligence.
References
[1] Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even Faster Accelerated Coordinate Descent Using Non- Non-Uniform Sampling, May 2016. 1rXiv:1512.09103 [es, math, stat].
[2] Stephen H Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Fevry, et al. Promptsource: integrated development environment and repository for natural language prompts. arXiv preprint arXiv:2202.012733 2022.
[3] Luisa Bentivogli, Peter Clark, Ido Dagan, and Danilo Giampiccolo. The fifth pascal recognizing textual entailment challenge. TAC, 7(8):1, 2009.
[4] Andrew Brock, Soham De, and Samuel L Smith. Characterizing signal propagation to close the performance gap in unnormalized resnets. arXiv preprint arXiv:2101.08000 2021.
[5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877-1901, 2020.
[6] HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference Machine Learning, pages 1 1193-1200 1203. PMLR, 2021.
[7] Miguel Carreira-Perpinat and Weiran Wang. Distributed optimization of deeply nested systems. In Artificial Intelligence and Statistics, pages 10-19, PMLR, 2014.
[8] Yekun Chai, Shuohuan Wang, Yu Sun, Hao Tian, Hua Wu, and Haifeng Wang. Clip- tuning: Towards derivative-fre free prompt learning with mixture of rewards. arXiv preprint 1r 12050, 2022.
[9] 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. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26.
2017.
10

---

[10] Christopher Clark, Kenton Lee, Ming- Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprini arXiv: 10044, 2019.
Ming-Wei Wei Chang, Tom Kwiatkowski. Michael Collins, and
[11] Ido Dagan, Oren Glickman, and Bernardo Magnini. The pascal recognising textual entailment challenge. In Machine learning challenges workshop, pages 177-190. Springer, 2005.
[12] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344-16399, 2022.
[13] Marie-Catherine De Marneffe, Mandy Simons, and Judith Tonhauser. The commitmentbank: Investigating projection in naturally occurring discourse. In proceedings of Sinn und Bedeutung. volume 23, pages 107-124, 2019.
[14] Mingkai Deng. Jianyu Wang. Cheng-Ping Hsich, Yihan Wang, Han Guo, Tiammin Shu, Meng Song, Eric P Xing. and Zhiting Hu. Rlprompt: Optimizing discrete text prompts with reinforce- ment learning. arXiv preprint arXiv:2205. 125448 2022.
[15] Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 8-bit optimizers via block-wise quantization. arXiv preprint arXiv:21 2021.
[16] Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguisties: human language technologies, volume I (long and short papers), pages 4171-4186, 2019.
[17] Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gard- ner. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. arXiv preprini arXiv: 000.. 2019.
[18] Jianwei Feng and Dong Huang. Optimal gradient checkpoint search for arbitrary computa- tion graphs. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11433-11443 2021.
[19] Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance-reduced zeroth-order methods for fine-tuning language models. arXiv preprint arXiv:2404.08080. 2024.
[20] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization. 23(4):2341-233 -2368, 2013.
[21] Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and William B Dolan. The third pascal recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing, pages 1-9, 2007.
[22] Jean-Bastien Grill, Michal Valko, and Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. Advances in Neural Information Processing Systems, 28, 2015.
[23] Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, and Heng Huang. Optimizing large-scall scale hyperparameters via automated learning algorithm. arXiv preprint arXiv:2102.09026, 2021.
[24] Wentao Guo, Jikai Long, Yimeng Zeng. Zirui Liu, Xinyu Yang, Yide Ran, Jacob Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, et al. Zeroth-order fine-tuning of llms with extreme sparsity. arXiv preprint arXiv:2406.00 02913, 2024.
[25] Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. ICLR, 1(2):3, 2022.
[26] Jacques Kaiser, Hesham Mostafa, and Emre Neftci. Synaptic plasticity dynamics for deep continuous local learning (decolle). Frontiers in Neuroscience, 14:424, 2020.
11

---

[27] Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth. Looking beyond the surface: A challenge set for reading comprehension over multiple sentences. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long Papers), pages 252-262,, 2018.
[28] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[29] Hector Levesque, Emnest Davis, and Leora Morgenstem. The winograd schema challenge. KR, 2012:13th, 2012.
[30] Jia Li, Cong Fang. and Zhouchen Lin. Lifted proximal operator machines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4181-4188, 2019.
[3]] Xiang Lisa Li and Percy Liang, Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101 1000000,0 2021.
[32] Timothy P Lillicrap, Daniel Cownden, Douglas B Tweed, and Colin J Akerman, Random synap- tic feedback weights support enror backpropagation for deep learning. Nature communications, 7(1):13276, 2016.
[33] Zhouchen Lin, Risheng Liu, and Zhixun Su. Linearized alternating direction method with adaptive penalty for low-rank representation. Advances in Neural Information Processing Systems, 24, 2011.
[34] Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038-53075 2023.
[35] Fanxu Meng, Zhaohui Wang, and Muhan Zhang. Pissa: Principal singular values and singular vectors adaptation of large language models. Advances in Neural Information Processing Systems, 11:122033-121072 2024.
[36] Yurüi Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2)527-5566, 2017.
[37] Anthony Nguyen and Krishnakumar Balasubramaniann Stochastic zeroth-order functional con- strained optimization: Oracle complexity and applications. INFORMS Journal on Optimization, 5(3):256-277) 272, 2023.
[38] Mohammad Taher Pilehvar and Jose Comacho-Collados. Wic: the word-in-context dataset for evaluating context-sensitive meaning representations. arXiv preprint 18Xiv 0810, 2018.
[39] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory optimiza- tions toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-16. IEEE, 2020.
[40] Samyam Rajbhandari, Olatunji Ruwase, Jeff Rasley, Shaden Smith, and Yuxiong He. Zero- infinity: Breaking the gpu memory wall for extreme scale deep learning. In Proceedings of the international conference for high performance computing, networking, storage and analysis, pages 1-14, 2021.
[41] Jie Ren, Samyam Rajbhandari, Reza Yazdani Aminabadi, Olatunji Ruwase, Shuangyan Yang, Minjia Zhang, Dong Li, and Yuxiong He. (Zero-offload): Democratizing (billion-scale) model training. In 2021 USENIX Annual Technical Conference (USENIX ATC 21), pages 551-564, 2021.
[42] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[43] Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S Gordon. Choice of plausible alterna- tives: An evaluation of commonsense causal reasoning. In AAAI spring symposium: logical formalizations of commonsense reasoning, pages 90-95, 2011.
12

---

[44] Richard Socher, Alex Perelygin. Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference empirical methods in natural language processing. pages 1631-1642, 2013.
[45] James C Spall. A stochastic approximation algorithm for lanee-imeessional systems in the kiefer-wolfowitz setting. In Proceedings of the 27th IEEE Conference on Decision and Control, pages 1548. IEEE, 1988.
[46] Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang. meprop: Sparsified back propa- gation for accelerated deep learning with reduced overfitting. In International Conference on Machine Learning, pages 3299-3306 3308. PMLR, 2017.
[47] Gavin Taylor, Ryan Burmeister, Zheng Xu, Bharat Singh, Ankit Patel, and Tom Goldstein. Training neural networks without gradients: A scalable admm approach. In International conference on machine learning, pages 2722-2731. PMLR, 2016.
[48] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 33971, 2023.
[49] Chun-Chen Tu, Paishun Ting, Pin-Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: autoencoder-basee zeroth order optimization method for attacking black-box neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 742-749, 2019.
[50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[51] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for general-purpose language understanding systems. Advances in Neural Information Processing Systems, 32, 2019.
[52] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv: 18X4v:1804.0744 07461, 2018
[53] Bingzhen Wei, Xu Sun, Xuancheng Ren, and Jingjing Xu, Minimal effort back propagation for convolutional neural networks. arXiv preprint (at:::1700.088880 2017.
[54] Mingqing Xiao, Qingyan Meng, Zongpeng Zhang, Di He, and Zhouchen Lin. Online neeuo-zerooh-ordee training of neuromorphic spiking neural networks. arXiv preprint 2rXiv:2407.12516, 2024.
[55] Yibo Yang, Xiaojie Li, Zhongzhu Zhou, Shuaiwen Song, Jianlong Wu, Liqiang Nie, and Bernard Ghanem. Corda: Context-orian -oriented decomposition adaptation of large language models for task-aware parfmette-efffiieett fine-tuning, Advances in Neural Information Processing Systems, 17:71768-711 71791, 2024.
[56] Pengyun Yue, Long Yang, Cong Fang, and Zhouchen Lin. Zeroth-order optimization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning Theory, pages 4429 4472. PMLR, 2023.
[57] Sheng Zhang, Xiaodong Liu, Jingjing Liu, Jianfeng Gao, Kevin Duh, and Benjamin Van Durme. Record: Bridging the gap between human and machine commonsense reading comprehension. arXiv preprint arXiv:1810.111 12885, 2018
[58] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0106. 2022.
13

---

[59] Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu. How robustify black-bot box ml models? a zeroth-order optimization perspective. arXiv preprini arXiv:2203. 14195, 2022.
[60] Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor W Tsang. Second-order fine-tuning without pain for llms: A hessian informed zeroth-order optimizer. arXiv preprint arXiv:2402.15175 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our Abstract and Introduction section do not claim any contribution out of scope. All the contributions mentioned are supported the later sections, see Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of this work in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
We provide the full set of assumptions in Section 3 and complete (and correct) proof can be found in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The complete implementation details to reproduce our experimental results are described in the Appendix A
Justification:
B
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Our code is available at httpss//gghhub.oooom/ygggghhhhhu
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.c//pbbllt/uuuue/////////e CoodeSumii iimnisssionn ssi iesionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in the Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the mean and standard deviation values in Table by running each result for times with different seeds. For the other results, repeated experiments of fine-tuning for various tasks will consume too much time and computing resource.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the GPU type in the Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We obey the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our study about new Zeroth-order algorithm for neural networks. No societal impact is concerned by our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited all the papers whose datasets used in experiment. Details can be found in the Appendix A
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pawpess..ppwwiiiip... thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No experiment involves crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
No experiment involves crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [No]
Justification: We only use LLMs for writing, editing or formatting purposes.
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy hatt:p///eerrrppp.cc////eeeeeee/ for what should or should not described.
21


Reviews:
[{"review_id": "ujogyRa64u", "reviewer": "Reviewer_EVkm", "summary": "This paper introduces PseuZO, a pseudo-zeroth-order optimization algorithm designed to train large language models (LLMs) under constrained memory budgets. The core techniques of the proposed approach can be summarized as follows:\n\nTech 1: PseuZO decomposes the gradient using the chain rule (Eq. 5), where the gradient of the loss with respect to the last hidden state is computed in closed form, and the Jacobian of the last hidden state with respect to the remaining model parameters is approximated in a zeroth-order manner (Eq. 6);\nTech 2: A momentum-based variance reduction technique is employed (Eq. 7);\nTech 3: A sliding-window mechanism is introduced to further reduce memory usage (Section 3.4).\n\nThe authors provide a preliminary convergence analysis of the proposed method and evaluate its empirical performance across a variety of tasks, including classification, multiple-choice question answering, and text generation, under both full-parameter tuning and parameter-efficient fine-tuning (PEFT) settings.", "questions": "See weaknesses.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The paper is overall well-constructed and clearly written, making it easy to follow.\n2. The empirical evaluation is thorough and demonstrates promising improvements over the MeZO baseline across various tasks and settings.\n\nWeaknesses\n\n1. The proposed approach relies heavily on prior work [1], particularly in its use of gradient decomposition and variance reduction via momentum (Tech 1 and 2 in the summary above), as acknowledged by the authors in Lines 104–106. The primary novel contribution appears to be the sliding-window mechanism for memory reduction. However, this design alone may not be sufficiently innovative to meet the novelty threshold expected at a venue such as NeurIPS.\n2. The source of improvement over MeZO is not clearly identified. From a theoretical standpoint, the convergence analysis in Section 3.3 is preliminary and does not explicitly justify the advantage of the proposed technical components. The convergence rate still depends on the effective dimension and, in the worst case, on the full model dimensionality. From an empirical standpoint, important ablations are missing—specifically, comparisons with (a) MeZO + Momentum and (b) PseuZO without Momentum would help isolate the contributions of the core techniques and clarify where the observed gains originate.\n3. The set of baselines is limited and could be significantly strengthened. Recent work in scalable and memory-efficient zeroth-order optimization has produced several relevant baselines that should be considered for a more comprehensive comparison, such as: (a) Forward Gradient [2], which avoids two-point estimation errors at the cost of slightly more computation; (b) HiZOO-L [3], which introduces additional forward passes and compressed diagonal Hessian storage; and (c) DeepZero [4], which accounts for model sparsity. Given the rapid progress in the field, relying solely on vanilla MeZO and MeZO-SVRG as baselines does not provide a strong benchmark.\n\nTypo:\n\nEq 3: <x, ...> => <\\nabla f(x), ...>\n\n[1] Online Pseudo-Zeroth-Order Training of Neuromorphic Spiking Neural Networks, https://arxiv.org/pdf/2407.12516  \n[2] Gradients without Backpropagation, https://arxiv.org/abs/2202.08587  \n[3] Second-Order Fine-Tuning without Pain for LLMs: A Hessian Informed Zeroth-Order Optimizer, https://arxiv.org/pdf/2402.15173  \n[4] DEEPZERO: SCALING UP ZEROTH-ORDER OPTIMIZATION FOR DEEP MODEL TRAINING, https://arxiv.org/pdf/2310.02025", "was_revised": true, "final_justification": "See discussions.", "rebuttal": "# Response to Reviewer EVkm\n\n**Thank you for your insightful feedback.** We appreciate the time invested in evaluating our work and providing constructive suggestions. Below are our point-by-point responses addressing your concerns.\n\n---\n\n### **1. Novelty of Contribution**\n> The proposed approach relies heavily on prior work [1], particularly in its use of gradient decomposition and variance reduction via momentum (Tech 1 and 2 in the summary above), as acknowledged by the authors in Lines 104–106. The primary novel contribution appears to be the sliding-window mechanism for memory reduction. However, this design alone may not be sufficiently innovative to meet the novelty threshold expected at a venue such as NeurIPS.\n   \n**Response:**  \n\n**Core Innovation:** While [1] proposed gradient decomposition for **Spike Neural Networks (SNNs)**, our work addresses **fundamental challenges in LLMs**. When we apply exponential moving average to Jacobian matrices, traditional approaches that explicitly store the full Jacobian matrix (analogous to SGD with Momentum storing historical gradient vectors) incur prohibitive $O(d·M)$ memory overhead ($d$ = parameter dimension, $M$ = output layer dimension). Our sliding-window mechanism reduces the memory overhead while maintaining convergence guarantees—a critical advancement for memory-constrained fine-tuning.  \n\n**Theoretical Advancement:** [1] lacks rigorous convergence analysis, whereas we provide **non-asymptotic convergence guarantees** (Theorem 3) for non-convex objectives. This combination of algorithmic efficiency and theoretical foundation establishes a significant advancement beyond prior work.  \n\n---\n\n### **2. Source of Improvement over MeZO**  \n> The source of improvement over MeZO is not clearly identified. From a theoretical standpoint, the convergence analysis in Section 3.3 is preliminary and does not explicitly justify the advantage of the proposed technical components. The convergence rate still depends on the effective dimension and, in the worst case, on the full model dimensionality. From an empirical standpoint, important ablations are missing—specifically, comparisons with (a) MeZO + Momentum and (b) PseuZO without Momentum would help isolate the contributions of the core techniques and clarify where the observed gains originate.\n\n#### **2.1 Theoretical Analysis**  \n\n**About the effective dimension**: The effective dimension $\\alpha_1$ is **independent** of model size $d$ in theory and practice as shown in zeroth-order optimization studies [5,6,7]. $\\alpha_1$ captures the **intrinsic low-dimensional structure** of high-dimensional models.   \n\nWhile $\\alpha_1 = \\Theta(d)$ in pathological cases, this reflects a fundamental lower bound for zeroth-order optimization: $\\Theta(d)$ forward passes are unavoidable [8]. PseuZO achieves this bound but does not *exceed* it—we defer tighter analysis to future work.\n\n**Theoretical comparison to MeZO**: Consider a simplified setting where the Jacobian matrix $J$ is fixed. In each step, PseuZO receives a noisy Jacobian estimation $B_t = J + \\Xi_t$, and MeZO receieves $g_t = (J+\\Xi_t)^\\top e_t$. The noise $\\Xi_t$ satisfies $\\mathbb{E} \\Xi_t = 0$, $\\mathbb{E} \\Xi_t\\Xi_t^\\top = N$.\n   - PseuZO: $$A_t = (1-\\lambda) B_t + \\lambda A_{t-1}, x_{t+1}=x_t - \\eta A_t^\\top e_t.$$ \n   - MeZO (PseuZO without momentum degenerates to MeZO): $$x_{t+1}=x_t - \\eta B_t^\\top e_t.$$ \n   - MeZO with momentum: $$m_t = (1-\\lambda)B_t^\\top e_t + \\lambda m_{t-1}, x_{t+1}=x_t - \\eta m_t.$$\nWe compare the descent of the expected loss function: $$\\mathbb{E} f(x_{t+1}) - f(x_t) \\le \\langle\\nabla f(x_t), x_{t+1}-x_t\\rangle + \\frac{L}{2}\\|x_{t+1}-x_t\\| ^2.$$\n\nAfter expansion (see detailed derivation in the revised paper), we obtain:  \n\n- **PseuZO**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\frac{(1-\\lambda)(1-\\lambda^{2t})}{1+\\lambda} e_t^\\top N e_t,\n  $$  \n  or \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_t^\\top N e_t.\n  $$  \n- **MeZO**:  \n  $$\n  -\\eta \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} e_t^\\top N e_t.\n  $$  \n\n- **MeZO with Momentum**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_i^\\top N e_i.\n  $$  \n    \n**Key Insights**:  \n1. **PseuZO vs. MeZO**:  \n   Substituting $\\eta_t = \\eta(1-\\lambda^{t-1})$, PseuZO's descent is strictly larger than MeZO's when $\\lambda \\in (0,1)$ and $t \\geq 1$ due to the reduced noise term $\\frac{(1-\\lambda)(1-\\lambda^{2t})}{(1-\\lambda^{t-1})^2} < 1$. This demonstrates **momentum effectively suppresses gradient variance**.  \n\n2. **PseuZO vs. MeZO with Momentum**:  \n   PseuZO's noise term $e_t^\\top N e_t$ is smaller than MeZO-Momentum's $\\sum_i e_i^\\top N e_i$ because $e_i \\to 0$ near local minima (where $\\|e_i\\| \\gg \\|e_t\\|$ for $i < t$). This advantage stems from the **closed-form outer function** providing timely gradient information.  \n\nWe will include extended analysis in the full paper.\n\n#### **2.2 Empirical Ablations**  \nFor the ablations, we have added corresponding experiments based on your suggestion. For (a), we have tried different momentum coefficient scheduler for $\\lambda$ and chose the best performance for fair comparison. For (b), we set the sliding window size to 1 or $\\lambda=1$ to eliminate historical information. The results are shown below. we also add the results for MeZO and PseuZO in the table below.\n\n---\n\n### **3. Baseline Comparison**  \n> The set of baselines is limited and could be significantly strengthened. Recent work in scalable and memory-efficient zeroth-order optimization has produced several relevant baselines that should be considered for a more comprehensive comparison, such as: (a) Forward Gradient [2], which avoids two-point estimation errors at the cost of slightly more computation; (b) HiZOO-L [3], which introduces additional forward passes and compressed diagonal Hessian storage; and (c) DeepZero [4], which accounts for model sparsity. Given the rapid progress in the field, relying solely on vanilla MeZO and MeZO-SVRG as baselines does not provide a strong benchmark.\n\n**Response:**  \n**HiZOO-L [3] (Added Baseline):**  \nWe have included a detailed comparison with HiZOO-L [3]. HiZOO-L explicitly addresses memory constraints by introducing a compressed diagonal Hessian structure, making it a highly pertinent baseline. HiZOO-L needs three forward propagations, introducing a bigger time overhead. Additionally, we found that the Hessian-smooth parameter $\\alpha$ in [3] is actually not appropriate. We tried our best in finding correct hyper-parameters in order to get the best performance but yet, the loss of the DROP task explodes. Results are shown in the table below.\n\n**Excluded Baselines:**  \n- **Forward Gradient [2]**: MeZO's gradient estimation **converges to Forward Gradient when the finite-difference step size approaches zero**, as both rely on directional derivative estimation via single perturbations. This theoretical equivalence makes the comparison redundant. Additionally, its Jacobian-vector products incur extra memory overhead, conflicting with our memory-efficiency focus.  \n- **DeepZero [4]**: Emphasizes model sparsity under fixed parameter budgets, prioritizing parameter selection rather than memory reduction during tuning. Its objectives diverge from our core motivation of dynamic memory optimization for full-parameter fine-tuning.  \n\nFor these reasons, we focused our comparison on HiZOO-L, which aligns most closely with our core motivation. We thank the reviewer again for the suggestions and will consider expanding the comparison in future work.\n\n---\n\n**Experiment Results:**\n\n|TASK|SST2|RTE|CB|BoolQ|WSC|WIC|MultiRC|COPA|ReCoRD|DROP|\n|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|\n|MeZO|82.4|54.3|76.0|60.7|51.0|50.9|54.9|74.0|57.6|20.3|\n|MeZO+Momentum|81.4|53.9|78.0|60.5|51.0|50.8|54.9|75.0|57.8|22.1|\n|HiZOO-L|88.1|54.9|69.0|64.8|51.2|58.0|58.2|73.0|58.8|0.0|\n|PseuZO (without Momentum)|84.6|57.2|75.0|64.2|50.0|51.3|57.2|75.0|59.6|24.1|\n|PseuZO (ours)|91.2|58.0|77.0|64.3|58.0|54.5|54.7|78.0|60.0|23.5|\n\n---\n\n### **4. Typo**\n> Eq 3: <x, ...> => <\\nabla f(x), ...>\n\n**Response:**  We sincerely apologize for these typos. All spelling mistakes have been corrected in the revised manuscript.\n\n---\n\n**References:**\n\n[1] Online Pseudo-Zeroth-Order Training of Neuromorphic Spiking Neural Networks, https://arxiv.org/pdf/2407.12516\n\n[2] Gradients without Backpropagation, https://arxiv.org/abs/2202.08587\n\n[3] Second-Order Fine-Tuning without Pain for LLMs: A Hessian Informed \nZeroth-Order Optimizer, https://arxiv.org/pdf/2402.15173\n\n[4] DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training, https://arxiv.org/pdf/2310.02025\n\n[5] Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038–53075, 2023\n\n[6] Zeroth-order optimization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning Theory\n\n[7] Zeroth-order fine-tuning of llms with extreme sparsity. arXiv preprint arXiv:2406.02913, 2024.\n\n[8] Optimal rates for zero-order convex optimization: the power of two function evaluations. arXiv preprint arXiv:1312.2039, 2013."}, {"review_id": "VLwfppdbrf", "reviewer": "Reviewer_v71X", "summary": "This paper proposes a pseudo zero-order optimization framework, PseuZO, to address the issue that the variance of gradient estimation in conventional zero-order optimization increases linearly with the parameter dimension, which leads to slow convergence in high-dimensional settings. PseuZO decomposes composite objective functions, explicitly estimates the Jacobian matrix of model outputs, and employs exponential moving average (EMA) to reduce variance. In addition, a sliding window technique is used to reduce memory overhead. Theoretical analysis demonstrates that the convergence rate of PseuZO depends on the effective dimension rather than the explicit parameter dimension. Experimental results show that PseuZO outperforms MeZO and MeZO-SVRG on multiple tasks and achieves significantly lower memory consumption compared to traditional first-order methods.", "questions": "1．\tIn the experiments, only 10,000 training steps are performed, and MeZO may not have fully converged. Could the authors provide comparisons after sufficient convergence?\n2．\tFor more complex tasks, such as MultiRC or DROP with longer input texts, does the method incur higher wall-clock time? How does model scaling affect the method’s efficiency?\n3．\tCould the authors include experiments on more recent models, such as LLaMA or Qwen series?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1.\tBy decomposing the gradient of the composite function and leveraging Jacobian estimation of model outputs combined with EMA for variance reduction, the proposed method overcomes the dimensionality bottleneck of traditional zero-order optimization.\n2.\tThe authors prove that the convergence rate depends only on the effective dimension, rather than the parameter dimension, providing theoretical guarantees for high-dimensional optimization.\n3.\tThe superiority of PseuZO is demonstrated on multiple tasks, and its compatibility with PEFT techniques is also shown.\nWeaknesses\n1.\tExperiments are conducted only on the OPT model series. The effectiveness of the method on larger models or other architectures, such as Qwen, LLaMA, or DeepSeek, has not been validated.\n2.\tThe hyperparameter search space in the experiments is relatively limited, which may affect the fairness of the comparisons.", "was_revised": true, "final_justification": "The authors’ clarifications and additional evidence have partially addressed my concerns regarding the effectiveness of the proposed method. While the manuscript demonstrates the impact of context length on memory usage, it does not discuss the differences in wall-clock time across different tasks. Furthermore, the work lacks generalization experiments on the latest models. Taking into account the paper’s novelty, writing quality, and experimental evaluation, I have decided to maintain my score.", "rebuttal": "# Response to Reviewer v71X\n\n\n**Thank you for your insightful feedback.** We appreciate the time invested in evaluating our work and providing constructive suggestions. Below are our point-by-point responses addressing your concerns.\n\n---\n\n### **1: Convergence of MeZO**\n\n> In the experiments, only 10,000 training steps are performed, and MeZO may not have fully converged. Could the authors provide comparisons after sufficient convergence? \n   \n**Response:** Our core goal was to compare methods under *fixed total computation time* to highlight PseuZO’s efficiency. Nonetheless, we acknowledge the value of convergence-based comparisons. Below are results after training MeZO for 20,000 steps (double the original budget), alongside PseuZO under the original 10,000-step budget:\n|TASK|SST2|RTE|CB|BoolQ|WSC|WIC|MultiRC|COPA|ReCoRD|DROP|\n|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|\n|MeZO|82.4|54.3|76.0|60.7|51.0|50.9|54.9|74.0|57.6|20.3|\n|MeZO (20K steps)|88.4|58.8|76.0|63.8|53.0|51.3|53.9|73.0|58.9|20.3|\n|**PseuZO**|91.2|58.0|77.0|64.3|58.0|54.5|54.7|78.0|60.0|23.5|\n\n---\n\n### **2: Scalability to Complex Tasks** \n\n> For more complex tasks, such as MultiRC or DROP with longer input texts, does the method incur higher wall-clock time? How does model scaling affect the method’s efficiency?\n\n**Response:** While sequence length affects PseuZO’s overhead (due to tensor dot products), **forward propagation dominates compute time**. Crucially, PseuZO’s *added* overhead is **scale-invariant** w.r.t. model sizze. As model size grows, the relative overhead *decreases* since forward-pass cost scales with model parameters, while PseuZO’s perturbation mechanism remains constant-cost. Empirical validation is in **Table 4** in the paper, showing diminishing relative cost for larger models.  \n\n---\n\n### **3: Evaluation on Recent Models**  \n> Could the authors include experiments on more recent models, such as LLaMA or Qwen series?\n\n**Response:** \nWe agree that broader model evaluation would strengthen our contribution. We limited experiments to OPT models to ensure **architectural consistency** with baseline methods (MeZO/MeZO-SVRG [1,2]), which exclusively report OPT results. OPT-6.7B (the largest model we tested) exhibits consistent trends across tasks, demonstrating PseuZO’s scalability. We commit to extending experiments to LLaMA/Qwen in future work to further validate generality. \n   \n---\n\n### **4: Hyperparameter Search Space**  \n> The hyperparameter search space in the experiments is relatively limited, which may affect the fairness of the comparisons.\n\nOur hyperparameter selection for MeZO/MeZO-SVRG adheres to their original papers [1,2]. Specifically, we prioritized **learning rate** (the most impactful hyperparameter [1,2]) testing the performances in a large search space. Other parameters (e.g., perturbation scale) were fixed to values from [1,2] to ensure replication fidelity. We will nonetheless expand the search space for all parameters in the final version to further bolster rigor.  \n\n---\n\n**References:**\n[1] Fine-Tuning Language Models with Just Forward Passes, (https://arxiv.org/pdf/2305.17333)\n\n[2] Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models, (https://arxiv.org/pdf/2404.08080)"}, {"review_id": "j8sXmGBjrU", "reviewer": "Reviewer_NYqf", "summary": "This paper proposes a zero-order optimization framework called PseuZO for LLM training, which estimates the gradient with respect to model parameters based on the Jacobian matrix of the model output and the gradient of the loss function with respect to the model output. To reduce the variance, PseuZO applies exponential moving average ($\\lambda>0$ as the decay factor) on Jacobian estimators. Further, the sliding window technique and the hidden state storage strategy are adopted to control the memory usage introduced by the inner product of large-scale vectors in PseuZO. Besides, Periodic changing of $\\lambda$ is needed to accelerate convergence. Experiments on fine-tuning OPT models across multiple tasks and pretraining small vision models on MNIST and CIFAR datasets demonstrate the effectiveness of the proposed method.", "questions": "See Weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nQuality: The proposed method is technically feasible due to its clear implementation and the provided convergence guarantee.\n\nClarity: In general, the core ideas of this paper are easy to understand, and adequate information is given for readers to reproduce its results.\n\nOriginality: The idea of using Jacobian information to enhancing zero-order optimization is interesting.\n\nWeaknesses:\n\nClarity:\n1) Many spelling inaccuracies exist in this paper: In line 16, “meory” should be “memory”; in line 124, “themq” should be “them”; in line 261, “greaat” should be “great”.\n2) The explanation of function $\\mathcal{F}$ exists in Equation (4) (see line 135), while $\\mathcal{F}$ is cited in line 18 and 70. In line 162, the norm $|| \\cdot ||_{op}$ lacks definition.\n3) Equation (2) and Equation (3) are incorrect.\n\nQuality:\n1) This paper does not strictly verify the benefits of using Jacobian information of the model output in theory. Further, the ablation study (results in Table 6) shows that the better performance achieved by PseuZO is mainly due to the carefully designed scheduling of decay factor $\\lambda$. However, this scheduler can also be used in MeZO and no ablation experiment is given.\n2) The performance of MeZO reported in Table 1,2,3 is too low, making the claimed improvement doubtful (See Table 2 in [1], and Table 3 in [2]). Besides, experimental results on more models (like OPT-13B and LLaMA2-7B) and advanced zero-order optimizers (like SubZero [2] and LOZO [3]) should be given.\n3) The comparison of different optimizers on pretraining vision models shown in Table 7 seems unfair, because node perturbation and local learning methods are not universally adopted across all optimizers.\n\n[1] Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark. In ICML, 2024.\n\n[2] Zeroth-Order Fine-Tuning of LLMs in Random Subspaces. arXiv:2410.08989, 2024.\n\n[3] Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures. In ICLR, 2025.", "was_revised": true, "final_justification": "The experiments supplemented by the authors basically eliminated my doubts about the effectiveness of the proposed method. Despite the lack of comprehensive theoretical justification, the proposed method still provides valuable insights for enhancing zeroth-order optimization.  So I raise my score to 4: Borderline accept.", "rebuttal": "# Response to Reviewer NYqf\n**Thank you for your insightful feedback.** We appreciate the time invested in evaluating our work and providing constructive suggestions. Below are our point-by-point responses addressing your concerns.\n\n---\n\n### **1. Clarity Comments**\n\n> Many spelling inaccuracies exist in this paper: In line 16, “meory” should be “memory”; in line 124, “themq” should be “them”; in line 261, “greaat” should be “great”.\n> The explanation of function exists in Equation (4) (see line 135), while is cited in line 18 and 70. In line 162, the norm lacks definition.\n> Equation (2) and Equation (3) are incorrect.\n\n\n**Response:** We sincerely apologize for these errors. All spelling mistakes have been corrected in the revised manuscript. We will add the sample noise to Equation (2) and Equation (3) to make them correct.\n\n---\n\n\n### **2. Quality Comments:**\n#### **2.1. Theoretical benefits of Jacobian information:**\n> This paper does not strictly verify the benefits of using Jacobian information of the model output in theory.\n\n**Response:** We provide a theoretical comparison between PseuZO and MeZO velow. We show that PseuZO can achieve a better convergence rate than MeZO in a simplified setting. We believe this theoretical comparison shows the benefits of using Jacobian information.\n**Theoretical comparison to MeZO**: Consider a simplified setting where the Jacobian matrix $J$ is fixed. In each step, PseuZO receives a noisy Jacobian estimation $B_t = J + \\Xi_t$, and MeZO receieves $g_t = (J+\\Xi_t)^\\top e_t$. The noise $\\Xi_t$ satisfies $\\mathbb{E} \\Xi_t = 0$, $\\mathbb{E} \\Xi_t\\Xi_t^\\top = N$.\n   - PseuZO: $$A_t = (1-\\lambda) B_t + \\lambda A_{t-1}, x_{t+1}=x_t - \\eta A_t^\\top e_t.$$ \n   - MeZO: $$x_{t+1}=x_t - \\eta B_t^\\top e_t.$$ \n   - MeZO with momentum: $$m_t = (1-\\lambda)B_t^\\top e_t + \\lambda m_{t-1}, x_{t+1}=x_t - \\eta m_t.$$\nWe compare the descent of the expected loss function: $$\\mathbb{E} f(x_{t+1}) - f(x_t) \\le \\langle\\nabla f(x_t), x_{t+1}-x_t\\rangle + \\frac{L}{2}\\|x_{t+1}-x_t\\| ^2.$$\n\nAfter expansion (see detailed derivation in the revised paper), we obtain:    \n\n- **PseuZO**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\frac{(1-\\lambda)(1-\\lambda^{2t})}{1+\\lambda} e_t^\\top N e_t,\n  $$ \n or\n $$-\\eta (1-\\lambda^{t-1})\\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_t^\\top Ne_t.\n $$\n- **MeZO**:  \n  $$\n  -\\eta \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} e_t^\\top N e_t.\n  $$\n\n- **MeZO with Momentum**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_i^\\top N e_i.\n  $$\n\n**Key Insights**:  \n1. **PseuZO vs. MeZO**:  \n   Substituting $\\eta_t = \\eta(1-\\lambda^{t-1})$, PseuZO's descent is strictly larger than MeZO's when $\\lambda \\in (0,1)$ and $t \\geq 1$ due to the reduced noise term $\\frac{(1-\\lambda)(1-\\lambda^{2t})}{(1-\\lambda^{t-1})^2} < 1$. This demonstrates **momentum effectively suppresses gradient variance**.  \n\n2. **PseuZO vs. MeZO with Momentum**:  \n   PseuZO's noise term $e_t^\\top N e_t$ is smaller than MeZO-Momentum's $\\sum_i e_i^\\top N e_i$ because $e_i \\to 0$ near local minima (where $\\|e_i\\| \\gg \\|e_t\\|$ for $i < t$). This advantage stems from the **closed-form outer function** providing timely gradient information.  \n\nWe will include extended analysis in the full paper.\n\n#### **2.2. Ablation study:**\n> Further, the ablation study (results in Table 6) shows that the better performance achieved by PseuZO is mainly due to the carefully designed scheduling of decay factor. However, this scheduler can also be used in MeZO and no ablation experiment is given.\n\n**Response:** We agree that Table 6’s original presentation of decay factor schedulers ($\\lambda$) was ambiguous. Our intent was to demonstrate that:  \n   - Extreme $\\lambda$ values (e.g., $\\lambda = 0$ or $0.999$) degrade performance, validating the need for a scheduler.  \n   - Moderate fixed $\\lambda$ values (e.g., $\\lambda = 0.9$) already achieves good results (SST-2 accuracy: 90.6), but an annealing strategy further optimizes results.  \n\nFor fairness, we test MeZO+Momentum with its optimal scheduler.  we clarify that PseuZO (without Momentum) sets $\\lambda = 1$ and window size $= 1$ to exclude historical information.\n\n|TASK|SST2|RTE|CB|BoolQ|WSC|WIC|MultiRC|COPA|ReCoRD|DROP|\n|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|\n|MeZO|82.4|54.3|76.0|60.7|51.0|50.9|54.9|74.0|57.6|20.3|\n|MeZO+Momentum|81.4|53.9|78.0|60.5|51.0|50.8|54.9|75.0|57.8|22.1|\n|MeZO (20K steps)|88.4|58.8|76.0|63.8|53.0|51.3|53.9|73.0|58.9|20.3|\n|HiZOO-L|88.1|54.9|69.0|64.8|51.2|58.0|58.2|73.0|58.8|0.0|\n|PseuZO (without Momentum)|84.6|57.2|75.0|64.2|50.0|51.3|57.2|75.0|59.6|24.1|\n|**PseuZO**|91.2|58.0|77.0|64.3|58.0|54.5|54.7|78.0|60.0|23.5|\n\n#### **2.3. Performance discrepancies and model/scalability comparisons:**\n> The performance of MeZO reported in Table 1,2,3 is too low, making the claimed improvement doubtful (See Table 2 in [1], and Table 3 in [2]). Besides, experimental results on more models (like OPT-13B and LLaMA2-7B) and advanced zero-order optimizers (like SubZero [2] and LOZO [3]) should be given.\n\n**Response:**\n- **MeZO performance gap**: Our Table 1 results are lower than prior work [1][2] because we **fix total computation time** (10K steps for MeZO). When allowing MeZO to converge fully (20K steps), its accuracy approaches but still trails PseuZO.  \n- **Comparison with SubZero [4] and LOZO [5]**: While these are important advances, they focus on **sparse/low-rank approximations**, whereas PseuZO exploits **last-layer Jacobian information**. We included HiZOO-L [3] as a relevant baseline due to its similar goal (memory-efficient ZO). We will add SubZero/LOZO in future work.  \n- **Larger models (OPT-13B/LLaMA2-7B)**: Experiments on OPT-13B caused OOM on our A800 GPUs (even for MeZO). We prioritize OPT-1.3B/6.7B to establish scalability trends. PseuZO’s gains on OPT-6.7B confirm its efficacy at scale.  \n \n#### **2.4. Fairness in pretraining comparisons (Table 7):**\n\n> The comparison of different optimizers on pretraining vision models shown in Table 7 seems unfair, because node perturbation and local learning methods are not universally adopted across all optimizers.\n\n**Response:** \nWe clarify that:  \n   - **Node perturbation (NP)** and **local learning (LL)** are **compatible only with PseuZO** in ZO settings. SPSA uses weight perturbation (WP), while $\\text{ZO}_{\\text{sp}}$ uses NP but estimates gradients with a single point.  \n   - **LL requires layer-wise objectives**, which PseuZO supports via its Jacobian structure. Other methods lack this capability\n\nThe results are shown below:  \n\n\n|Dataset|SPSA (wp)|SPSA (np)|$\\text{ZO}_{\\text{sp}}$ (np)|PseuZO|SPSA (np and w/LL)|$\\text{ZO}_{\\text{sp}}$ (np and w/LL)|PseuZO (w/LL)|BP|\n|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|:-------|\n|MNIST|$86.4\\pm0.15$|$88.2\\pm0.02$|$87.8\\pm0.09$|$98.7\\pm0.02$|/|/|/|$98.5\\pm0.02$|\n|CIFAR10|$41.3\\pm0.74$|$43.0\\pm0.82$|$42.6\\pm0.69$|$82.5\\pm0.15$|$41.4\\pm0.96$|$41.7\\pm0.57$|$88.7\\pm0.13$|$89.9\\pm0.06$|\n|CIFAR100|$5.39\\pm0.69$|$7.65\\pm0.88$|$7.61\\pm0.73$|$61.4\\pm0.14$|$7.34\\pm0.54$|$7.29\\pm0.38$|$68.5\\pm0.13$|$71.9\\pm0.09$|\n\n---\n\n**References:**\n\n[1] Online Pseudo-Zeroth-Order Training of Neuromorphic Spiking Neural Networks, https://arxiv.org/pdf/2407.12516\n\n[2] Gradients without Backpropagation, https://arxiv.org/abs/2202.08587\n\n[3] Second-Order Fine-Tuning without Pain for LLMs: A Hessian Informed \nZeroth-Order Optimizer, https://arxiv.org/pdf/2402.15173\n\n[4] Zeroth-Order Fine-Tuning of LLMs in Random Subspaces. arXiv:2410.08989, 2024.\n\n[5] Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures. In ICLR, 2025."}, {"review_id": "ULj1rQdHDu", "reviewer": "Reviewer_n2bx", "summary": "This paper proposes an algorithm PseuZO based on zeroth-order gradient for deep learning. Rather than directly using the loss value to compute the zeroth-order gradient, this paper turns to optimize a composite objective function $g(h(x,z))$ where $h$ represents the output of a neural network and $g$ represents a loss function. PseuZO computes the zeroth-order gradient for the function $h$ and uses the closed-form for the function $g$ which is with respect to $h$, then combines them to obtain the gradient for the model update. Since the first-order momentum consumes large memory cost, this work also designs a variant algorithm based on the sliding window. The authors make a convergence analysis for PseuZO. In the fine-tuning experiments, PseuZO achieves greater performance than MeZO across different llms. In addition, the proposed algorithm only introduces little extra memory cost.", "questions": "1. In line 200, it says \"When $\\lambda$ approaches zero, PseuZO gradually degenerates to ZO method and thus we directly transform to MeZO instead\". In my opinion, when $\\lambda$ approaches zero, $u_k$ with large $k$ approaches zero, thus the stored gradient at time $k$ contributes little to the accumulated PseuZO gradient. Thus, the value of $\\lambda$ should only influence the weight in the accumulation step. How does it make PseuZO degenerate to ZO?\n\n2. In line 13 of Algorithm 2, why uses the zeroth-order gradient at time $k$ to multiply the outer gradient at time $t$?\n\n3. Lines 242-246 together with Table 6 are confusing. Does it mean that if using the same time consumed by MeZO to run 10k steps on OPT1.3B, PseuDO could run 9300 steps within 10 epochs, 8700 steps within 20 epochs? Why are the numbers of total steps and the steps within each epoch in the above results different from each other? Please explain this paragraph more detailedly.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper proposes an optimizer PseuZO for training deep neural networks. The authors decouple the traditional loss function to a composite form. This is an innovative point which is different from related works.\n\n2.\tThe statement of the idea is clear and the organization of the paper is reasonable.\n\n3.  The authors provide the detailed theoretical analysis for the proposed algorithm.\n\n4.  The experiments cover multiple metrics and contents, including the time and memory cost and the ablation study.\n\nWeaknesses:\n\n1.\tThis paper lacks the explanation or theoretical analysis to show that why PseuZO works or achieves improvement compared to baselines. Maybe the closed-form of the outer function contributes some accurate gradient information to the final gradient in PseuZO. I think the authors could discuss this point.\n\n2.\tIn lines 81-84, the authors state that \"the convergence rate of PseuZO is not explicitly dependent on the parameter size\". However, in the upper bound of the iterations to find an $\\epsilon$-stationary point, the coefficient \"$\\alpha_1$ is the effective dimension\". According to formula (6) and Assumption 1, $\\alpha_1$ may be equal to the parameter size. Thus, I think there exists conflict within the statement here. \n \n3.  This work proposes the sliding window-based PseuZO. The authors consider to store the last hidden state with a much smaller size. This is not reflected in Algorithm 2. Algorithm 2 uses the notations $\\theta$ to denote the parameter and $x$ to denote the training data, which are also not consistent with the problem setting and Algorithm 1. It is necessary to introduce that $||\\cdot||_{op}$ in Assumption 1 means the spectral norm.\n\n4.  The experiments are mainly conducted on tasks in GLUE and SuperGLUE. There lacks some complex tasks like reasoning.", "was_revised": true, "final_justification": "In the rebuttal and discussion period, my concerns have been addressed by the authors. They provide a theoretical analysis to explain the reason that PseuZO outperforms MeZO. Based on these, I increase my score to 3.", "rebuttal": "# Response to Reviewer n2bx\n**Thank you for your insightful feedback.** We appreciate the time invested in evaluating our work and providing constructive suggestions. Below are our point-by-point responses addressing your concerns.\n\n---\n\n### **Weakness 1. Theoretical analysis of PseuZO's improvement mechanism**\n\n> This paper lacks the explanation or theoretical analysis to show that why PseuZO works or achieves improvement compared to baselines. Maybe the closed-form of the outer function contributes some accurate gradient information to the final gradient in PseuZO. I think the authors could discuss this point.\n\n**Response:** We sincerely appreciate this insightful comment. We provide a theoretical comparison between PseuZO and MeZO to elucidate the roles of the **closed-form outer function** and **momentum**. For clarity, we analyze a simplified case with a fixed Jacobian matrix $J$. At step $t$, PseuZO receives a noisy Jacobian estimate $B_t = J + \\Xi_t$ (where $\\mathbb{E} \\Xi_t = 0$, $\\mathbb{E} \\Xi_t \\Xi_t^\\top = N$), while MeZO receives $g_t = (J + \\Xi_t)^\\top e_t$. The update rules are:\n\n   - PseuZO: $$A_t = (1-\\lambda) B_t + \\lambda A_{t-1}, x_{t+1}=x_t - \\eta A_t^\\top e_t.$$ \n   - MeZO (PseuZO without momentum degenerates to MeZO, see response below): $$x_{t+1}=x_t - \\eta B_t^\\top e_t.$$ \n   - MeZO with momentum: $$m_t = (1-\\lambda)B_t^\\top e_t + \\lambda m_{t-1},\\\\ x_{t+1}=x_t - \\eta m_t.$$\n\nThe expected loss descent is bounded by:  \n$$\n\\mathbb{E} f(x_{t+1}) - f(x_t) \\leq \\langle \\nabla f(x_t), x_{t+1} - x_t \\rangle + \\frac{L}{2} \\|x_{t+1} - x_t\\|^2.\n$$  \n\nAfter expansion (see detailed derivation in the revised paper), we obtain:  \n\n- **PseuZO**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\frac{(1-\\lambda)(1-\\lambda^{2t})}{1+\\lambda} e_t^\\top N e_t,\n  $$  \n  or \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_t^\\top N e_t.\n  $$  \n- **MeZO**:  \n  $$\n  -\\eta \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} e_t^\\top N e_t.\n  $$  \n\n- **MeZO with Momentum**:  \n  $$\n  -\\eta (1-\\lambda^{t-1}) \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda^{t-1})^2 \\|J^\\top e_t\\|^2 + \\frac{L\\eta^2}{2} (1-\\lambda)^2 \\sum_{i=1}^t \\lambda^{2(t-i)} e_i^\\top N e_i.\n  $$  \n    \n**Key Insights**:  \n1. **PseuZO vs. MeZO**:  \n   Substituting $\\eta_t = \\eta(1-\\lambda^{t-1})$, PseuZO's descent is strictly larger than MeZO's when $\\lambda \\in (0,1)$ and $t \\geq 1$ due to the reduced noise term $\\frac{(1-\\lambda)(1-\\lambda^{2t})}{(1-\\lambda^{t-1})^2} < 1$. This demonstrates **momentum effectively suppresses gradient variance**.  \n\n2. **PseuZO vs. MeZO with Momentum**:  \n   PseuZO's noise term $e_t^\\top N e_t$ is smaller than MeZO-Momentum's $\\sum_i e_i^\\top N e_i$ because $e_i \\to 0$ near local minima (where $\\|e_i\\| \\gg \\|e_t\\|$ for $i < t$). This advantage stems from the **closed-form outer function** providing timely gradient information.  \n\nWe will include extended analysis in the full paper.    \n\n---\n\n### **Weakness 2. Dependence of convergence rate on parameter size**\n\n> In lines 81-84, the authors state that \"the convergence rate of PseuZO is not explicitly dependent on the parameter size\". However, in the upper bound of the iterations to find an -stationary point, the coefficient \"is the effective dimension\". According to formula (6) and Assumption 1, may be equal to the parameter size. Thus, I think there exists conflict within the statement here.\n\n**Response:**\nWe thank the reviewer for highlighting this ambiguity. We clarify that the **effective dimension $\\alpha_1$** is *not explicitly dependent* on $d$ (parameter size). As established in prior work [1–3], the effective dimension $\\alpha_1$ is often independent on the model size across different models (e.g., linear regression, DNNS) in both theory and practice. $\\alpha_1$ captures the **intrinsic low-dimensional structure** of high-dimensional models.   \n\nWhile $\\alpha_1 = \\Theta(d)$ in pathological cases, this reflects a fundamental lower bound for zeroth-order optimization: $\\Theta(d)$ forward passes are unavoidable [4]. PseuZO achieves this bound but does not *exceed* it—we defer tighter analysis to future work.\n\n---\n\n### **Weakness 3. Algorithmic clarity and notation consistency**\n\n> This work proposes the sliding window-based PseuZO. The authors consider to store the last hidden state with a much smaller size. This is not reflected in Algorithm 2. Algorithm 2 uses the notations $\\theta$ to denote the parameter and $x$ to denote the training data, which are also not consistent with the problem setting and Algorithm 1. It is necessary to introduce that $\\|\\cdot\\|_{op}$ in Assumption 1 means the spectral norm.\n\n**Response**: We apologize for the confusion and will revise as follows:  \n\n1. **Notation Unification**: Use $x$ for parameters and $z$ for data in both algorithms.  \n2. **Spectral Norm**: Define $\\|\\cdot\\|_{op}$ as the spectral norm in Assumption 1.\n\nIn Algorithm 2, we actually store the differentiaiton of two last hidden states $\\Delta o_t = \\frac{h(x_t + \\mu\\xi_t;z_t)-h(x_t;z_t)}{\\epsilon}$, which is of the same size as $h(x_t;z_t)$. We will add this to the introduction of Algorithm 2.\n\n---\n\n### **Weakness 4. Experimentation scope**\n\n> The experiments are mainly conducted on tasks in GLUE and SuperGLUE. There lacks some complex tasks like reasoning.\n\n**Response:** Our focus is **memory-efficient zeroth-order optimization**, and GLUE/SuperGLUE provide rigorous benchmarks for this goal (e.g., MultiRC and DROP have sequence lengths >2048). This aligns with baselines (MeZO/MeZO-SVRG). We agree that reasoning tasks (e.g., MATH) are valuable and will explore them in future work.\n\n---\n\n### **Question 1. Degeneration to MeZO when $\\lambda = 0$**\n> In line 200, it says \"When approaches zero, PseuZO gradually degenerates to ZO method and thus we directly transform to MeZO instead\". In my opinion, when $\\lambda$ approaches zero, $u_k$ with large $k$ approaches zero, thus the stored gradient at time $k$ contributes little to the accumulated PseuZO gradient. Thus, the value of $\\lambda$ should only influence the weight in the accumulation step. How does it make PseuZO degenerate to ZO?\n\n**Response**: When $\\lambda = 0$, PseuZO's gradient estimator reduces to:  \n$$\ng_p = \\left( \\frac{h(x_t + \\mu \\xi_t; z_t) - h(x_t; z_t)}{\\mu} \\xi_t^\\top \\right)^\\top e_t.\n$$  \nAs $\\mu \\to 0$, we have:  \n$$\ng_p \\to (J_t \\xi_t \\xi_t^\\top)^\\top e_t = \\xi_t \\xi_t^\\top J_t^\\top e_t = \\xi_t \\xi_t^\\top \\nabla f(x_t; z_t),\n$$  \nwhich matches MeZO's estimator $g_m = \\langle \\nabla f(x_t; z_t), \\xi_t \\rangle \\xi_t$. Thus, PseuZO with $\\lambda = 0$ and $\\mu \\to 0$ is equivalent to MeZO.  \n\n---\n\n### **Question 2. Gradient multiplication in Algorithm 2 (Line 13)**\n\n> In line 13 of Algorithm 2, why uses the zeroth-order gradient at time $k$ to multiply the outer gradient at time $t$?\n\n**Response**: This implements the **sliding window accumulation**:  \n- The inner loop (over $k$) computes contributions from perturbations within the current window.  \n- The product $\\langle\\Delta o_k, e_t\\rangle$ correlates **differentiation of last hidden states** (at step $k$) with the *current* outer gradient $e_t$. This preserves gradient coherence without storing full Jacobians.\n\n\n---\n\n### **Question 3. Wall-clock time comparison (Table 6)**\n\n\n> Lines 242-246 together with Table 6 are confusing. Does it mean that if using the same time consumed by MeZO to run 10k steps on OPT1.3B, PseuDO could run 9300 steps within 10 epochs, 8700 steps within 20 epochs? Why are the numbers of total steps and the steps within each epoch in the above results different from each other? Please explain this paragraph more detailedly.\n\n**Response**: We believe that the reviewer is referring to Table 4. Table 4 compares **total steps achievable under fixed time** (equivalent to MeZO's 10k-step runtime). We run PseuZO for $t_{\\text{PseuZO}}$ epochs and switch to MeZO for the remaining epochs. Table 4 shows the total running steps.\n\n**References:**\n\n[1] Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36:53038–53075, 2023\n\n[2] Zeroth-order optimization with weak dimension dependency. In The Thirty Sixth Annual Conference on Learning Theory\n\n[3] Zeroth-order fine-tuning of llms with extreme sparsity. arXiv preprint arXiv:2406.02913, 2024.\n\n[4] Optimal rates for zero-order convex optimization: the power of two function evaluations. arXiv preprint arXiv:1312.2039, 2013."}]

Author rebuttal:

Meta-review: This paper introduces a new pseudo-zeroth-order optimization algorithm, PseuZO. In the initial review, the reviewers raised concerns about the significance of the experimental evaluations and theoretical proof, particularly in comparison with the MeZO method. In the rebuttal, the authors provided sufficient empirical and theoretical evidence to support the effectiveness of the PseuZO method. The AC believes that the authors have adequately addressed all concerns and encourages the authors to incorporate all discussions into the final version.
Decision: Accept (poster)