PaZO: Preconditioned Accelerated Zeroth-Order Optimization for Fine-Tuning LLMs
Authors: Hanzhen Zhao
Shihong Ding
Cong Fang
Zhouchen Lin
Venue: NeurIPS 2025 poster ()
Keywords: zeroth-order optimization
fine-tuning LLMs
preconditioner
Primary area: optimization

Abstract: This paper introduces PaZO, a preconditioned accelerated zeroth-order optimization algorithm for fine-tuning large language models (LLMs).      First, we theoretically demonstrate the necessity of preconditioning in zeroth-order optimization, proving that zeroth-order stochastic gradient descent (ZO-SGD) alone fails to achieve the ideal convergence rate.     Building on this, we propose a Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA) and theoretical version of PaZO, and demonstrate that setting the order of preconditioner as $-1/2$ in PSPSA yields the improved convergence rate for PaZO.     Moreover, we design a practical version of PaZO that stabilizes training via diagonal Hessian estimate and moving average technique.  Extensive experiments on diverse downstream tasks with models like RoBERTa-large and OPT show PaZO’s effectiveness.  Compared to other zeroth-order baselines, PaZO achieves better performance across models and tasks.

PaZO: Preconditioned Accelerated Zeroth-Order Optimization for Fine-Tuning LLMs
Cong Fang 1.2
Hanzhen Zhao' hzzhao@pku. edu. cn
Shihong Ding' dingshihong@stu, pku. edu. cn
fangcong@pku.ede edu. cn
Zhouchen Lin 1,233 zlin@pku. edu. on
State Key Lab of General AI, School of Intelligence Science and Technology, Peking University
2 Institute for Artificial Intelligence, Peking University
3 Pazhou Laboratory (Huangpu), Guangzhou, Guangdong, China
Abstract
This paper introduces PaZO, a preconditioned accelerated zeroth-order optimization algorithm for fine-tuning large language models (LLMs). First, we theoretically demonstrate the necessity of preconditioning in zeroth-order optimization, proving that zeroth-order stochastic gradient descent (ZO-SGD) alone fails to achieve the ideal convergence rate. Building on this, we propose Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA) and theoretical version of PaZO, and demonstrate that setting the order of preconditioner as -1/2 in PSPSA yields the improved convergence rate for PaZO. Morcover, design practical version PaZO that stabilizes training via diagonal Hessian estimate and moving average technique. Extensive experiments diverse downstream tasks with models like RoBeRTa-large and OPT show PaZO's effectiveness. Compared to other zeroth- order baselines, PaZO achieves better performance across models and tasks. Code is available at (Codel
Introduction
Fine-tuning pre-trained large language models (LLMs) has become one the dominant method- ologies for adapting models specialized downstream tasks [19] and aligning them with human instructional preferences [42). However, as models are scaled up [I] the memory overhead extremely
increases during fine-tuning, since computing gradients during backpropagation needs cache model activations and historical gradients (c.g., for Adam-based optimization (28). ceaameter-efficieee
fine-tuning (PEFT) methods (29) 31 23 reduce memory overhead by fine-tuning only a small number of extra parameters but still need to cache large quantities of activations. Recently,
optimization algorithms (ZO) 37 59 58) have enabled the fine-tuning of LLMs with billions of parameters single consumer- grade GPU, due to their requirement for only forward passes to estimate gradients, without backpropagation and the storage of activations. Lightweight memory has solidified its role as a critical methodology for fine-tuning tasks in resource-constraingg scenarios.
As research zeroth-order optimization methods for fine-tuning LLMs advances, whether precondi- tioning zeroth-order algorithms with higher-order information can enhance optimization efficiency has become pivotal challenge, since adaptive first-order optimizers such Adam 28 and Adam W
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

35). which can be regarded as preconditioned algorithms with (diagígog) show improvement on convergence speed. However, for zeroth-order optimization, one cannot directly estimate the Hessian by first-order information. Direct adaptation of Adam to zeroth-order algorithms (e.g., 70-Adam (58]) introduces large variances and has significant impact on the fine-tuning performance [59]. Moreover, Hessian-informed perturbation for estimating zeroth-order information [59 55) is a significant methodological advancement, but how to incorporate Hessian information into the perturbation process to obtain the best convergence speed and performance remains a significant challenge.
as preconditioner,
When we delve into and rethink the preconditioned zeroth-order optimization problems, the more pressing challenge lies in whether preconditioned zeroth-order optimization methods can truly achieve a provable convergence rate from a theoretical perspective. This problem may appear counterintuitive, but mature theoretical research [2 17 on first-order methods has substantiated the following facts: for least squares regression, only SGD can achieve the near-optimal convergence rate (d/TT) and match the lower bound when ignoring the logarithmic term, which indicates that at least for this problem, preconditioning techniques provide no improvement on convergence, as SGD has already attained the information-theorriic limit of the problem. Therefore, whether this conclusion for zeroth-order optimization remains determines the effect of preconditioning techniques in zeroth-order optimization. Moreover, even if we posit that precondition holds effectiveness for zeroth-order optimization, how to appropriately apply preconditioning techniques emerges as another challenge. Specifically, determining the optimal order of the preconditioner to guarantee the fastest convergence rate becomes a critical consideration. Finally, from the practical perspective, how to estimate Hessian information through zeroth-order perturbation stochastic approximation integrate abundant information, ensure stability and control memory overhead is also a challenge in practice. Based on the three above, we think that the following three problems demand reasonable resolution in preconditioned zeroth-order optimization for fine-tuning LLMs:
A. Do we truly need preconditions in zeroth-order optimization?
B. If the answer to question A is "yes", how to achieve the fastest convergence by selecting the optimal order of the preconditioner?
C. How to effectively estimate Hessian information through zeroth-order perturbations in practice and improve fine-tuned model performance on downstream tasks?
In this paper, we provide reasonable answers to the three questions above. We propose a precondi- tioned accelerated zeroth- fodderordrrrde optimization algorithm PaZO, with a theoretical guarantee to obtain a faster convergence rate by selecting the optimal order of preconditioner, and better empirical performance on wide range of downstream tasks for fine-tuning L.LMs. Our contributions are:
1. (Answer to Question A.) We construct general Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA) and corresponding algorithm PaZO (Theoretical Form 3.2) with any given order of Hessian information H - Our theoretical analysis quadratic functions Theorem 3.5 demonstrates that only ZO-SGD (a = 0) cannot achieve the fastest convergence rate. We need preconditions in zeroth-order optimization.
2. (Answer to Question B.) We provide the convergence analysis of PaZO for general objective functions. The result in Theorem 3.8 demonstrates that PaZO can achieve the fastest convergence rate if and only if we select a = 1/2. In other words, we need to use H 1-12 in PSPSA (or H-1 as the preconditioner) to accelerate zeroth-order optimization.
3. (Answer to Question C.) We propose PaZO (Practical Form, Algorithm I for fine-tuning LLMs, with unbiased diagonal Hessian estimation incorporating current zeroth-order gradi- ent information and moving average techniques ensure stability in practice. We conduct extensive experiments across different models (RoBERTa-large OPT- different meth- ods (FT, LoRA, prefix), and different downstream tasks to verify the effect of the PaZO. Results show PaZO achieves better performance across models, tasks and PEFT methods.
Notations. Let (-) and (2-) denote upper and lower bounds, respectively, with a universal constant, while Ō(-) and 52(-) ignore polylogarithmic dependencies. For functions f and g: f S denotes f == =((g: f 2 g denotes f Zigg); f x indicates 9 S f g. We use Amaz (-) and Amin (-) to

---

denote the largest and smallest eigenvalue of matrix, respectively. Let |00|A denote the Mahalanobis (semi) norm where A is positive semi-defiiite matrix ||0) A V T A0. We use 0 denote the minimizer, i.e. l* - argming f()).
2 Related Work
Zeroth-order Optimization: Zeroth-order optimization, is to estimate the gradient by just forward passes. substantial body of theoretical research has been devoted to the detailed analysis conver-
gence rates in zeroth-order optimization in convex settings (3 16 26 39
44 46) and non-convex [53]. Representative method SPSA 488 demonstrates strong performance in challenging settings
like non-convex multi-agent optimization [2] 50] and black-box adversarial example generation
10 33 Notably, McZO (37] pioneers the adaptation of classical ZO-SGD for LLM fine-tuning,
matching conventional performance while drastically cutting memory consumption. Then various
following works [58] 59
12 49 try to improve zeroth-order optimizers for efficient fine-tuning. However, whether and how precondition works in zeroth-order optimization is still lack of discussion.
Enhanced Optimizers with Hessian: Researchers focus on how to incorporate second-order infor- mation to provide acceleration for gradient descent during the training. For example, (9 40) utilized curvature information as the preconditioner, (38) applied diagonal Hessian as the preconditioner; (36) estimated the Hessian information with conjugate gradient. Sophia (3) introduced lightweight esti- mate of the diagonal Hessian for pre- training. However, these methods can only be used for first-order methods with heavy GPU-memory overhead. HiZOO (59) has been proposed preconditioned acroth-order optimizer for fine-tuning LLMs. However, how to effectively leverage preconditioning information in zeroth-order optimization to accelerate convergence remains understudied.
Theoretical Insights of PaZO
Preconditioned methods in first-order optimization have been generally studied (40,
28 32)
However, few works discuss the necessity, potential and limitation preconditioned zeroth- orddr optimization. In this section, we to clarify two questions below from the theoretical perspective.
A. Do we truly need preconditions in zeroth-order optimization?
B. If the answer to question A is "yes", how to achieve the fastest convergence by selecting the optimal order of the preconditioner?
We provide theoretical insights into the two questions A and B. First, show the necessity of using preconditions in zero-order optimization, since only ZO-SGD (48 cannot achieve the potential ideal convergence rate (dd//T) for least squares (as stated Theorem 3.5 while the first-order SGD can match the optimal rate Ód/TT) without preconditions 17 This difference indicates that preconditions play a key role in ZO, especially. Second, we propose general Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA) using H as preconditioner with any given order and Hessian H to extend traditional SPSA 48 for zeroth-order gradient estimate. We provide the convergence analysis of the preconditioned zeroth-order optimization with PSPSA in Theorem 3.8
The results explicitly direct us choose the optimal to obtain the fastest rate.
3.1
Problem Setup
We consider the standard stochastic unconstrained minimization problem as:
min DER f()) = E (E(x.))~ F(0;; (F()) vx))
where the expectation is taken over the data distribution (x, y) D. Given the Hessian matrix H, at the decision point 0r, we first define the following general Preconditioned Simultancous Perturbation Stochastic Approximation (PSPSA) as:
Definition 3.1 (Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA)). Given model with parameters 0 e Fd and the loss function F, PSPSA estimates the zeroth-order
3

---

stochastic gradient (f.)) at (x,,30 ve) as
F (x), F(O, + ,H, "u; (xe, Mc)) F(, ,rd," "u; (xr,,1e))
H uu
(2)
2/
where E IR and u (0, La), is the perturbation scale, H2 is the Hessian matrix at O,, and is the precondition order.
E 2 2
With the estimated zeroth-order stochastic gradient generated by PSPSA, the preconditioned zeroth- order optimization algorithm can be stated as follows:
Definition 3.2 (Preconditioned Accelerated Zeroth-order Optimization, PaZO (Theoretical Form)). PaZO is an optimizer with learning rate that updates parameters
0. = 0 F((( (x+, Uc)),
where FO.: (Xt, v.) is the PSPSA gradient estimate at 0e with H.,
PSPSA and PaZO can be regarded as the general preconditioned extension of the existing zeroth-order perturbation approximation and algorithms. Intuitively, ignoring the higher-order infinitesimal term of μ. we obtain the expectation the PSPSA gradient estimate as
2
(0,) H."' 2/
(((: (xL, ui)]
Eu
H
a = H, 2 f(.).
(4)
which indicates that the PSPSA gradient estimate is equivalent to a H, 2a preconditioned gradient.
When a PSPSA degenerates to SPSA [88] and PaZO is reduced ZO-SGD.
We introduce the assumption below to construct the relation between the outer product the gradient and the Hessian for analysis.
Assumption 3.3 (Unbiased Estimate of Hessian). We assume that the expectation of the outer product of F(0", (x. 3) is the unbiased estimate of H" as:
E FF (x, v F(0": (x, [xx, H
(5)
where 0* is a minimizer of the objective f()), and H* the Hessian defined 0*.
Assumption 3.3 is common assumption when considering stochastic gradient descent 11
24 25
especially for least squares regression 17 24 whose Hessian is fixed and can be exactly calculated.
3.2 Case Study: Least Squares Regression
First, we try to provide an intuitive answer to the question A. We consider a representative case of f: least squares regression, whose optimization dynamic can be clear and meticulously calculated due to the fixed Hessian as:
1 (y- (0, x))
F(O; (x, v))
(6)
2C
We have access stochastic gradients zeroth-order obtained by PSPSA with sampling example (Xe, y1) ~ DD These examples satisfy
(0", x) +e,
where e is a noise on the example pair with E(e] O and E| = 0², and 0* minimizer of
the objective. Note that the Hessian of the objective H def V2 f(0) = E[xx T.. The following estimate holds
E V F (x, F(O"; (x, 9))
E 2 xx
C H'
(7)
C
By setting C= 2², we exactly obtain the result in Assumption 3.3
The analytical tractability
of (6) offers deeper theoretical insights. Specifically, previous studies [17 demonstrate that for first-order algorithms the optimal rate achieves (d/TT) and construct the lower bound, where d is the dimension of problems and T the iteration steps. Moreover, the studies show that only SGD can match the near-optimal rate with only the difference of logarithmic terms. In other words, for least

---

squares regression and first-order stochastic algorithms, only SGD is enough with any precondition making no effect of acceleration. When turning to zeroth-order optimization, intuitively, we think the ideal convergence rate achieves (d² (T) since in zeroth-order optimization we can only access one-dimension information per step. Varieties of theoretical studies of zeroth-order algorithms (2) 41 also show d times slower convergence rate than first-order ones. However, the results stated in
Theorem 3.5 indicate that only ZO-SGD is not enough.
Assumption 3.4 (Fourth Moment Conditions). Suppose B is a positive semi-definite matrix, and consider data vector x. It satisfies Ex [xx Bxx 3xxxBxxX]]
O (tr (H*B) H*).
Theorem 3.5 (Convergence Rate of PaZO on Least Squares). Suppose we are given access to the PSPSA, running PaZO for least squares regression (6) satisfying Assumption 3.4 with a learning rate
satisfying Aminn (HH)) 2afT n min
min (0) 2uy J for 2T
(H-)) 2n)1 Amax (H* [
Amax (Hr(
tr (H
steps with T rate:
(1-1 Amman (H*) allows PaZO achieve the following convergence
Amin
27 Σ
- f(00) (1 ummin ((=)) A
D. 22n +
f
100 - 1' H-
(8)
n
T
where Dr = (r (HH)) Ir ((H+)2-2a) and a is the precondition order defined in PSPSA.
Theorem (..) provides an affirmative answer to question A. Since the first term decays exponentially with T, the rate depends the second term Da/T, which is trade-off between tr ((H ) 20-1)) and ((H+)1-20)) 2xx Through Cauchy-Schward inequality, we have D& 2 d,, where the equality holds if and only if 1/2. In other words, only ZO-SGD is not enough match the ideal rate Óld /T). Therefore. Theorem 3.5 demonstrates that different from first-order algorithms, we need preconditions in zeroth-order optimization.
Moreover, we consider the convergence analysis with approximate Hessian H, in PSPSA. When the gap between H, and H2 can well controlled, we can also achieve the fastest rate when a = 1/2. The detailed assumption and analysis are shown in Appendix B
3.3 General Functions
Second, we propose the theoretical analysis for general smooth functions. Based on the affirmative answer to question A provided by Theorem 3.5 we conducted a more in-depth analysis of general functions, thereby establishing more reasonable solution question B. We may also obtain the results under approximate Hessian. For convenience, we assume its exact.
Assumption 3.6 (Gradient Uniform Continuity). For For any given sample pair (x. y) ~ DD the stochastic gradient of the objective V F(O;; u)) satisfies uniform continuity.
Assumption 3.7 (General Hessian Smooth). For any given 0,, O2 and a' [11,1], the Hessian of the objective H(0,) and (02) are invertible and satisfy
Ha' (0,) - -H' (02)| S pla' ||0 02
is the generalization form of Lipschitz continuity of Hessian. When a = 1, it reduces to Hessian Lipschitz continuity. We use it to limit the gap between H in PSPSA and (H*)- 20 -2n When the objective is strongly convex, the Hessian is naturally invertible. while for others we assume its invertible property. We propose the convergence rate of general functions in Theorem 3.8
Assumption 3.7
Theorem 3.8 (Convergence Rate of PaZO on General Functions). Suppose we are given access to the
PSPSA, running PaZO for general fenerionnnttins (I) satisfying Assumption 3.3 3.6 L.6and33. with a learning
Amaz ((H) )2 2n
rate satisfying Xmam (H 2ayT S 17 S Ames((HF)) 2a for 2T steps with T 2 Amii ((~) 2n
1 where H is full-rank and 0, 1 1| < for any t E [T, 2T - 1] and p [0, 3] allows PaZO to
achieve the following asymptotic convergence rate:
2T-1
0. ]
1(0") S (1 Ammin (H
1-20) yr
E
f
1100 00112 (-)
T
T
(9)
tr ((H))22 tr ((H))
+
Err,
T
5

---

Algorithm PaZO (Practical Form)
Require:
parameters è {0, E RR loss C R + R, running steps T. perturbation scale j. learning rate schedule 7/. smooth scale 31, .2, initialized diagonal Hessian Σn = I, random seed s, random number generator, Hessian reset frequency To
for 1. 1, 1,.... 7' do
Step I: Perturb Parameters through Diagonal Hessian
Sample batch B DD and random seed
L( B))
0 < PerturbParametersS.. J4, E7-12
4 C(0; B)
< PerturbParameters(... -2p, E, 1
8_ < C(0: B3)
0 +- PerturbParameterss μt, -,
[Reset parameters before descent)
Step 2: Estimate Diagonal Hessian
- (f+ - + E
1/2 4/24
[Estimate unbiased zeroth-orde gradient)
Σ - (1 - B1) + 31 -digg 8)) 1/2
(Adding information from ZO gradient)
Σ. = 2nza (c+ + +l_ - 22 Σ (diag(u - 1)
(Estimate unbiased diagonal Hessian)
Step 3: Take Moving Average and Reset Diagonal Hessian
Σ, - (1- - 82) + 3/ EEp
(ake moving average of diagonal Hessian]
if t%To = 0 then
Σ; <-1 I
FFrequently reset diagonal Hessian]
end if
Step 4: Update the Parameters
Reset random number generator with seed
(For sampling u,
preconditioned grad + (4+ f-)+ E, 1/2 22u for 0: C do
{ Ussin Σ 1 as preconditioner)
Sample u, ~ N It,) 0: +- 0, m preconditioned _grad +u; end for end for
where Err O (npe) npen 2|a++ co + pEd gaal) represents the higher-order infinitesimal term, and is the precondition order defined in PSPSA.
We observe that the dominant term of the rate in Theorem 3.8 aligns with the rate in Theorem 3.5 which further demonstrates the generalized validity our analysis on the role of preconditioning in zeroth-order optimization: for general problems, selecting
0 alone induces a slower convergence rate than the optimal choice a = 1/2. Moreover, the Err defined as the higher-order infinitesimal
mpdn 2|a/+1 + 1r=e0 + 17 pGo p=) ) that negligibly impacts the convergence rate of the
term O npe
dominant term. When T grows, we can choose the smaller 7) to obtain the controlled Thr.Thus, Theorem 3.5 can be regarded as special case of Theorem 3.8 and we propose the proof in detail in Appendix By selecting a = 1/2, PaZO achieves the fastest convergence rate Ô (d² (d²/T) compared with MeZO for general functions, providing reasonable answer to question B.
4 Algorithm for Fine-Tuning LLMs in Practice
In this section, introduce PaZO (Practical Form) in Algorithm for fine-tuning LLMs in practice. We provide an answer to the question below.
C. How to effectively estimate Hessian information through zeroth-order perturbations in practice and improve fine-tuned model performance downstream tasks?

---

Algorithm 2 PerturbParameters
Require: model parameters θ (0, R²), perturbation scale J4, diagonal Hessian Σ, 1/2
random seed 8, a random number generator
Reset random number generator with seed for 0; E @ do
{ {For sampling u,
Sample u, (N Id,)
0: + 0, + no= 1/2
(Modify parameters in place)
end for
Specifically, apply the theoretically optimal order of preconditioner H H- in the PSPSA process. Then we estimate diagonal Hessian with incorporating the current zeroth-order gradient information and moving average techniques through the same PSPSA process for estimating the preconditioned zeroth-order gradient. Our algorithm can divided into four steps.
Step I. Perturb Parameters through Diagonal Hessian. First, we apply PSPSA to our practical algorithm to obtain the preconditioned zeroth-order gradient. Inspired by our theoretical results, we 1112 the preconditioner in the PSPSA process, where Σ is the estimated diagonal Hessian. Through twice forward passes of PSPSA we obtain
4 = F μΣ u/ (x, = F μΣ 1/2 (x, y))
Moreover, we run another additional forward pass before adding perturbation to obtain L F(;; (x, 3)) for estimating Σ in the following steps.
Step II. Estimate Diagonal Hessian. We try to estimate the diagonal Hessian through L,, and f, with (dd) memory cost against (dd) ) for the full Hessian. Specifically, in the theoretical analysis of the Hessian-awand zeroth-order optimization [53], they demonstrate that
A A
Eu~N((0LL))
H.
(10)
where H is the Hessian matrix, and A is any given positive definite matrix. Thus, letting Σ positive definite diagonal matrix and setting A = E-1, we obtain the diagonal version of 10)
-1,
as
2 u L HH uu (diag u) I) = diag (H).
(11)
We use l- and l to estimate I. Through Talyor expansion, we have
112 I + 0(p))
4 F(0; (x, v)) + (VF(0: u)), Σ zu)
+
2
(12)
2
{_ = F(0: (x, v)) - ~ u)) Σ ) +
+ 011²)
2
Thus, obtain I by the combination of f,, l_ and as
4 + l- - 28 I O()).
(13)
112
Moreover, incorporating the current gradient information into preconditioner is demonstrated to be effective in first-order optimizers
28
35)
We additionally estimate
Σ
1/2
g (e+ (-)
un uu (x, (VF(:((x.))) O(n)
2/1
as an unbiased zeroth-order gradient and incorporate diag(g o g) as a correction item to integrate local first-order estimated information into E, through moving average mechanism as
Σ = ((1 B + 31 diag diag²(go og) 1/2
Then we use
|1 to update the diagonal Hessian as
Σ
1
(f+ + l- - 26) E (diag(u o u) -1)) -
(14)
21
7

---

Step III. Take Moving Average and Reset Diagonal Hessian. In practice, we empirically discover the instability of the estimated diagonal Hessian. To solve this problem, we take the moving average of the historical estimate and the current one to maintain the smoothness and stability of Σ, as
Σ, (1 - 82) + 82 Ex),
(15)
where [ means taking the absolute values of Σg to maintain positive definite. Moreover, when the iteration step exceeds threshold, excessive accumulated historical information may no longer positively contribute. Therefore, we reset the Σ frequently after some steps.
Step IV. Update the Parameters. Finally, we layer-wisely compute the preconditioned gradient by PSPSA, where the gradient estimate is equivalent to a E-1 preconditioned zeroth-order gradient.
Remark 4.1. For 31. we first clarify that the correction term ğ 9 introduced to mitigate training instability caused by outliers from the stochastic zeroth-order oracle. Specifically, since the precondi- tioner order is set to a 1/2, excessively small values in the diagonal Hessian estimate can lead to nunerical instability (e.g.. NaN values) during training. This correction term promotes numerical alignment between gradient magnitudes and adaptive curvature scaling, similar to the mechanism in Adam. However, applying such a correction introduces bias into Eq. (14). By choosing a small 31 to constrain this bias, we observe that this nearly negligible term enhances estimation robusiness against outliers and ensures training stability. As shown in Appendix C.7 setting Bi too large (e.g.. I or 10-2) causes optimization divergence and results NaNs, as the correction term introduces non-negligible bias. Conversely, when 81 is too small (e.g.. 0 or close to 0), the correction fails to take effect, potentially leading to numerical instability and NaNs. Only within an appropriate range 10-100 10) does the algorithm achieve stable and reasonable performance.
(around 10 to 10
For 32, is designed reduce the high variance Hessian estimates from the zeroth-order oracle. For the Hessian estimate En at step t, a small B2 ensures that the cumulative variance from the k=0 remains controlled, thereby enabling lower-variance and more stable updates
sequence {E 1t=1 during training. similar hyperparameter configuration is adopted other zeroth-order fine-tuning optimizers, such as in (59%. Our experimental results further confirm that, under identical parameter settings, PaZO improves the performance of fine-tuned model across tasks.
Experiment
We conduct experiments on both masked LMs (RoBERTa-large. 350M 34 and large-scale generative
LMs (OPT-1.3B (57) with zero-shot learning, linear probing (LP (22 ). in-context learning (ICL (8)
full-parameter tuning and PEFT including LoRA (23) and prefix-tuning 31] (see Appendix C for
details). We compare PaZO with other representative zeroth-order optimizers including MeZO and HiZoO (see Appendix CC44 for details). We first show that PaZO achieves significant improvement over zero-shot, ICL, and LP. Compared with first-order optimizers (FT), PaZO drastically reduces the memory cost while maintaining comparable performance. Moreover, PaZO realizes better performance compared with MeZO and HiZOO. Detailed settings are presented in Appendix C.2
5.1 Masked Language Models
We conduct experiments for RoBERTa-large (350M) on sentiment classification, natural language inference, and topic classification tasks. We sample examples per class for l = 16, running zeroth- shot learning. LP. fine-tuning, MeZO and PaZO. We summarize the results in Table D First, we show that: (1) PaZO works significantly better than zero-shot and LP: (2) PaZO achieves comparable performance to FT. Moreover, we show the better performance of PaZO compared with MeZO.
PaZO achieves better performance compared with MeZO. As shown in Table D PaZO achieves improved performance average across all the datasets, tasks and PEFT (we choose the best results from LoRA and prefix-tuning). For sentiment tasks, the improvement of PaZO is universal, while for NLI and topic tasks the improvement is evident on MNLI and TREC with 9.3% and 5.4%.
5.2 Generative Language Models
We extend the experiments to the OPT 1.3B model (57 on classification and multiple-choice tasks on different datasets (see Appendix C.I for details). We randomly sample 1000, 500, and 1000 examples
8

---

Table 1: Experiments on RoBERTa-large (350M parameters. k=16). We use zero-shot learning, linear probing (LP), full-parameter fine-tuning with Adam, MeZO and PaZO on six downstream tasks. We also PEFT methods including LoRA and prefix tuning with Adam, MeZO and PaZO respectively, All reported numbers are averaged accuracy (standard deviation) across 5 runs.
Task Type
SST-2
SST-S
SNLI
MNLI
RTE
TREC topic
Average
sentiment
natural language inference
Zero-shot
79.0
35.5
50.2
48.8 56.5 (+:2.5)
51.4 59.4 (#:5.3)
32.0
49.5
LP
76.0 (+:288
40.3 (#:1.)
(=277)
51.3 (+:.55
58.3
FT
90.9 (+1.7)
44.8 (#16
67.5(+2.4)
58.2 (+3.1)
66.4 (+7.2)
85.0
68.8
FT (PEFT)
91.9 (11.0)
43.2 (#1.1)
65.5 (-8.8)
57.1 (#1.3)
65.5 (1:19)
79.8 (+:15)
67.2
MeZO
90.5 (21)2)
42.3 (4:2.1)
66.7 (=3.3)
51.6 (1:3.0)
64.0 (d:3.3
70,2 (1:14
64.2
MeZ0 (PEFT)
91.3 (1:100)
42.4 (#2.5)
62.7 (.))
55.6 (#:2.0)
60.5 (#:366
73.4 (#:366
64.3
PaZO
91.4 (+0.8)
44.6 (#1.7)
66.7 (=2.6)
56.4 (12.11)
63.2
70.8 (+:2.0)
65.6
PaZO (PEFT)
91.3 (1003)
42,9 (10.5)
62.4 (=1.6)
55.8 (+:.7)
61.5 (4:22)
77.4 (4:3.5)
65.2
Table 2:
Performance comparison with MeZO and HiZOO. We fine-tune OPT- on different downstream datasets and evaluate the performance, applying LoRA and prefix-tuning.
Task Type
SST-2
BoolQ
CB
ReCoRD
RTE
WIC
WSC
COPA
MultiRC
Average
classification
multiple choice
McZ0
88.5
63.4
67.8
72.3
66.1
60.6
57.6
76.0
56.3
67.6
MeZO (LoRA)
88.5
63.0
60.7
70.6
59.9
58.2
54.8
77.0
58.9
65.7
MeZO (prefix)
91.3
64.1
67.9
71.0
62.5
54,2
51.2
75.0
57.2
66.0
Hizoo
88.5
61.4
67.9
71.9
64.3
62.2
62.5
59.3
67.9
HiZOO (LoRA)
88.5
63.1
69.6
72.5
64.6
60.6
54.8
76.0
58.9
67.6
HiZOO (prefix)
91.3
63.6
67.9
70.9
63.2
53.8
75.0
54.5
66.4
PaZO
89.0
63.4
69.6
72.1
66.4
63.2
61.5
75.0
57.6
68.6
PaZO (LoRA)
88.5
63.4
73.2
72.1
62.8
58.2
54.8
77.0
58.9
67.7
PaZO (prefix)
91.3
63.4
67.9
71.0
62.3
53.8
57.7
75.0
57.2
66.6
for training, validation, and test sets, respectively, for each dataset. We run MeZO, HiZOO and PaZO for 20K steps, and compare the performance with different zeroth-order optimizers in Table 2
PaZO achieves SOTA performance compared with other zeroth-order optimizers. As shown in Table 2 PaZO achieves SOTA performance compared to other zeroth-order optimizer baselines including MeZO and HiZOO. Specifically, for average performance, PaZO achieves all-round improvement beyond MeZO and HiZOO, matter the full-parameter version, the LoRA version the prefix-tunin version. For single-task performance, PaZO and its peft version show advantages in the vast majority of tasks and have little gaps in other tasks.
5.3 Memory Usage and Wall-clock Time Analysis
Memory Usage, As shown in Figure PaZO has more memory overhead compared to MeZO because of the storage of the diagonal Hessian, and maintains the memory overhead compared to HiZOO. However, PaZO also exhibits extreme saving of memory compared to first-order optimizers, specifically, up to 6x compared to standard FT and 3 x compared to FT ppeffi--uningg)
Wall-clock Time.
As shown in Figure 2 PaZO spends 1.5x time per step compared with MeZO, and same time per step compared with HiZOO, since preconditioned optimizers need an additional forward pass for estimating diagonal Hessian. In Figure 2 Modell means we use LoRA and Model2 means we use prefix-tuning -uning. Considering the accelerated convergence rate of PaZO with fewer steps to obtain the same loss, PaZO achieves better performance with acceptable extra time cost.

---

1000
1. general considerations" In: IMA Journal of Applied Mathematics 6.1 (1970), pp. 76-90. Zero Zero
MeZO
Hizoo
PaZO
FT
Peak Memory (GB)
FTtprefix)
RoBERTa-L
0.2091s
0.3020s
0.3046s
RoBERTa-LI
0.1338s
0.1993s
0.2013s
Pazo
RoBERTa-L2
0.1254s
0.1869s
0.1892s
OPT-1.3B
0.2564s
0.3812s
0.3837s
4x
OPT-1.3B1
0.1664s
0.2798s
0.28578
OPT-1.3B2
0.1572s
0.2374s
0.2419s
10
Figure Wallclock time per step among McZO, HiZOO and PaZO. The increase in wallclock time per step for PaZO compared McZO less than 1.5 times across different model sizes. All results are measured on the same dataset (SST-2) and GPUs (24GB 3090), with each result averaged over 100 steps.
2.78
170
# Parrametrs
Figure 1: GPU peak memory overhead with dif- ferent OPT models and tuning methods Mul- tRRC (400 tokens example on average). See Appendix C.5 for details.
6
Conclusion
In this work, we propose PaZO, a preconditioned accelerated zeroth-order optimization method for fine-tuning LLMs. We theoretically analyze the necessity of preconditions in ZO, and demonstrate the optimal order preconditioners to achieve the fastest convergence rate. We propose the practical form of PaZO and extensive experiments different models and tasks show the effectiveness.
7
Acknowledgements
Z. Lin was supported by National Key R&D Program of China (2022DD160030D), the NSF China (No. 62276004) and the State Key Laboratory of General Artificial Intelligence. C. Fang was supported by National Key R&D Program of China (20227D0160300) and the NSF China (No. 92470117 and No. 62376008).
References
[1] Josh Achiam et al. "Gpt-4 technical report". In: arXiv preprint arXiv:2303.0872 (2023).
[2] Alekh Agarwal, Ofer Dekel, and Lin Xiao. "Optimal algorithms for online convex optimization with multi-point bandit feedback." In: Colt. Citeseer. 2010, pp. 28-40.
[3] Alekh Agarwal et al. "Information-thhooetiee lower bounds on the oracle complexity of convex optimization". In: Advances in Neural Information Processing Systems 22 (2009).
[4] Shun-ichi Amari et al. "When does preconditioning help or hurt generalization?" In: arXiv
preprint arXiv: 10732 (2020).
[5] Francis Bach and Eric Moulines. "Non-strongly-cone smooth stochastic approximation with convergence rate O (1/n)". In: Advances in neural information processing systems 26 (2013).
[6] Luisa Bentivogli et al. "The Fifth PASCAL Recognizing Textual Entailment Challenge." In:
TAC 7.8 (2009), p. 1.
[7] Samuel Bowman et al. "A large annotated corpus for learning natural language inference".
In: arXiv preprint arXiv: 500..0080000 053366 (2015).
[8] Tom Brown al. "Language models are few-shot learners". In: Advances in neural information processing systems 33 (2020), pp. 1877-1901.
[9]
Charles George Broyden. "The convergence of class of double-rank minimization algorithms
[10] HanQin Cai et al. "A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization". In: International Conference on Machine Learning. PMLR. 2021, pp. 1993- 1203.
[11] Pin-Ya Yu Chen et al. "Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models". Proceedings of the 10th ACM workshop on artificial intelligence and security. 2017, pp. 15-26.
10

---

[12] Yiming Chen et al. "Enhancing zeroth-orde order fine-tuning for language models with low-rank structures". In: arXiv preprint arXiv:2410.07690 (2024).
[13] Christopher Clark et al. "Boolq; Exploring the surprising difficulty natural yes/no questions". In: arXiv preprint arXiv: /905./0444 (2019).
[14] Ido Dagan, Oren Glickman, and Bernardo Magnini. "The paseal recognising textual entailment challenge". In: Machine learning challenges workshop. Springer. 2005, pp. 177-190.
[15] Marie-Cathering De Marneffe, Mandy Simons, and Judith Tonhauser. "The commitment- bank: lnvestigating projection in naturally occurring discourse". In: proceedings of Sinn und Bedeutung. Vol. 23. 2. 2019, pp. 107-124.
[16] John C Duchi al. "Optimal rates for zero-order convex optimization: The power of two function evaluations". In: IEEE Transactions on Information Theory 61.5 (2015), pp. 2788-
2806.
[17] Rong Ge "The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares". In: Advances in neural information processing systems 32 (2019).
[18] Danilo Giampiccolo et al. "The third pascal recognizing textual entailment challenge". In: Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing. 2007,
pp. 1-9.
[19] Suchin Gururangan et "Don't stop pretraining: Adapt language models domains and tasks". In: arXiv preprint arXiv:2004. 10964 (2020).
[20] R Bar Haim et al. "The second pascal recognising textual entailment challenge". In: Proceed- ings of the Second PASCAL Challenges Workshop on Recognising Textual Entiilmnt. Vol. 2006. pp. 785-794.
[21] Davood Hajinezhad and Michael M Zavlanos. "Gradient-free multi-agent nonconvex nons- mooth optimization". In: 2018 IEEE Conference on Decision and Control (CDC). IEEE. 2018, pp. 4939-4944
[22] Kaiming He et al. "Masked autoencoders are scalable vision learners". In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022, pp. 16000-16009.
[23] Edward J Hu et al. "Lora: Low-rank adaptation of large language models." In: ICLR 1.2 (2022),
p. 3.
[24] Prateek Jain et al. "Accelerating stochastic gradient descent for least squares regression". In: Conference On Learning Theory. PMLR. 2018, pp. 545-604.
[25] Prateek Jain et al. "Parallelizing stochastic approximation through mini-batching and tail- averaging". In: arXiv preprint arXiv:1610.03771 (2016).
[26] Kevin G Jamieson, Robert Nowak, and Ben Recht. "Query complexity of derivative-free optimization". In: Advances in Neural Information Processing Systems 25 (2012).
[27] Daniel Khashabi et al. "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 Linguistics: Human Language Technologies,
Volume 1 (Long Papers). 2018, pp. 252-262.
[28] Diederik P Kingma. "Adam: A method for stochastic optimization". In: arXiv preprint arXiv:/412.6988 (2014).
[29] Brian Lester, Rami Al-Rfou, and Noah Constant. "The power of scale for parameter-efficien prompt tuming". In: arXiv preprint arXiv:2104.0886 (2021).
[30] Hector J Levesque, Ernest Davis, and Leora Morgenstern. "The Winograd schema challenge." " In: KR 2012 (2012), 13th.
[31] Xiang Lisa Li and Percy Liang. "Prefix-tuning: Optimizing continuous prompts for generation". In: arXiv preprint 2 (2021).
[32] Hong Liu et "Sophia: A scalable stochastic second-order optimizer for language model pre-training". In: arXiv preprint arXiv:2305. 14342 (2023).
[33] Sijia Liu et al. "signSGD via zerothoorderr oracle". In: International conference on learning
representations. 2019.
[34] Yinhan Liu et al. "Roberta: A robustly optimized bert pretraining approach". In: arXiv preprint 1XXi:1997..1199 (2019).
[35] Ilya Loshchilov and Frank Hutter. "Decoupled weight decay regularization". In: arXiv preprint arXiv:1711.05101 (2017).

---

[36] George D. Magoulas, Michael N. Vrahatis, and George S Androulakis. "Improving the conver- gence of the backpropagation algorithm using learning rate adaptation methods". In: Neural Computation 11.7 (1999), pp. 1769-1796.
[37] Sadhika Malladi et al. "Fine-tuning language models with just forward passes". In: Advances in Neural Information Processing Systems 36 (2023), pp. 53038-53075.
[38] James Martens et al. "Deep learning via hessian-free optimization." " In: leml. Vol. 27. 2010,
pp. 735-742.
[39] Arkadij Semenović Nemirovskij and David Borisovich Yudin. "Problem complexity and method efficiency in optimization". In: (1983).
[40] Yurii Nesterov and Boris T Polyak. "Cubic regularization of Newton method and its global performance". In: Mathematical programming 108.1 (2006), pp. 177-205.
[41] Yurii Nesterov and Vladimir Spokoiny. "Random gradient-free free minimization of convex func- tions". In: Foundations of Computational Mathematics 17.2 (2017), pp. 527-566. [42] Long Quyang et al. "Training language models to follow instructions with human feedback". In: Advances in neural information processing systems 35 (2022), pp. 27730-27744.
[43] Mohammad Taher Pilehvar and Jose Camacho-Collados. "WiC: the word-in-context dataset for evaluating context-sensitive meaning representations".. In: arXiv preprint arXiv: 09121 (2018).
[44] Maxim Raginsky and Alexander Rakhlin. "Information-basee complexity, feedback and dynamics in convex programming". In: IEEE Transactions on Information Theory 57.10 (2011), pp. 7036-7056.
[45] Melissa Roemmele, Cosmin Adrian Bejan, and Andrew Gordon. "Choice of Plausible Alternatives: An Evaluation of Commonsense Causal Reasoning." In: AAAI spring symposium:
logical formalizations of commonsense reasoning. 2011, pp. 90-95.
[46] Ohad Shamir. "An optimal algorithm for bandit and zero-order convex optimization with two-point feedback". In: Journal of Machine Learning Research 18.52 (2017), pp- 1-11.
[47] Richard Socher et al. "Recursive deep models for semantic compositionality over sentiment treebank".. In: Proceedings of the 2013 conference on empirical methods in natural language processing. 2013, pp. 1631-1642.
[48] James C Spall. "Multivariate stochastic approximation using simultaneous perturbation gradient approximation". In: IEEE transactions on automatic control 37.3 (1992), pp. 332- 341.
[49] Yan Sun et al. "TeZO: Empowering the Low-Rankness the Temporal Dimension in the Zeroth-Order Optimization for Fine-tuning LLMs". In: arXiv preprint 1900 (2025).
[50] Yujie Tang, Junshan Zhang, and Na Li. "Distributed zero-order algorithms for nonconvex multiagent optimization". In: IEEE Transactions on Control of Network Systems 8.1 (2020),
pp. 269-2811.
[51] Ellen M Voorhees and Dawn M Tice. "Building a question answering test collection". In: Proceedings of the 23rd annual international ACM SIGIR conference on Research and devel- opment in information retrieval. 2000, pp. 200-207.
[52] Alex Wang et al. "Superglue: A stickier benchmark for ceneral-purposs language understanding
systems". In: Advances in neural information processing systems 32 (2019).
[53] Zhongruo Wang et al. "Zeroth-ordes -oderr algorithms for nonconvex minimax problems with im- proved complexities". In: arXiv preprint arXiv:2001.0r 07889990999999.... (2020).
[54] Adina Williams, Nikita Nangia, and Samuel R Bowman. "A broad-coverage challenge corpus for sentence understanding through inference". In: arXiv preprint arXiv: (2017). [55] Haishan Ye. "Mirror natural evolution strategies". In: arXiv preprint arXiv:2308. (2023). [56] Sheng Zhang et al. "Record: Bridging the gap between human and machine commonsense reading comprehension". In: arXiv preprint arXiv: 1810, /2885 (2018).
[57] Susan Zhang et al. "Opt: Open pre-trained transformer language models". In: arXiv preprint arXiv::205.. 2200:2205.01068 (2022).
[58] Yihua Zhang al. "Revisiting zeroth-order optimization for memory-efficient Ilm fine-tuning: A benchmark". In: arXiv preprint arXiv:2402.11533 (2024).
[59] Yanjun Zhao et al. "Second-order fine-tuning without pain for llms: A hessian informed zeroth-order optimizer". In: arXiv preprint 1521: (2024).
12

---

A Proof of Theorem 3.5 and Theorem 3.8
We prove Theorem 3.5 and Theorem 3.8 by three steps below. First, we rewrite the update form to obtain the coupled recursive formula of (0., 0") (0t, 0¹) ignoring higher-order infinitesimal
terms. Second, we obtain the estimation of the sum of (0t, 07)(;, 0*) with 4 and l2 from T
- 01) on 0", we obtain the results in Theorem to 27 - 1. Finally, by Taylor expansion of EE=r
3.5 and Theorem
Specifically, Theorem 3.5 can be regarded as a special case of Theorem 3.8 Thus we employ a generalized proof framework to establish the proofs of the two Theorems above. The main body of our proof addresses general function (as stated in Theorem 3.8), while the least squares (Theorem distinctly labeled "Least Squares" for clarity.
3.5
Proof. Step I. We first rewrite the update rule from
0-11 = 0, -
(16)
to separate the decay term and higher-order term as below
i 0+11 0" 0. 0" 7) (FF(0; (x,,0)) (H') ( f((())
(I (I-n/( (H-) (I-) (00)))))0000000--000))0) - 0*)
(17)
+1 (H*) 1-20) 1 (0, 0²) - E (x + (H²) 2 -H- (7))
+ E ( v.)) (F(O, (x4: (x+:
Denoting Q- I- I 12 with < (m-)(- have Q* 0. For any T s l2
S 27, by recursive formula 17). we have
, 0- = -Q")t (0 --) +B+C +C
(18)
where
41 B =
Σ QQ")² 12 -0-)--0") 5x (H") (1-)))=(((07))
1=1
and
h C=n
[ 1
VF (xc- Bo.
(x)-,,,) (19)
Then we denote Ve == (0:. - 0 (0,, - -TT) by the recursive formula 32 obtain the expectation of V f1,t2 below. When fzz, have
from 0,, to O we
E V d2 (Q*)* 2 V 12 + O 3 1),
(20)
(1 V f2. ] + Err
where the second term in the first equality is from BiO,, T²)T. We obtain
B(O,, T < B B(O., - 0
1o
1-112101 + 1|0 - 1-))²) ||0 0-' [10:11)
mpE
Ø=1
0 np (50
2|a/+1 + <?))
13

---

In (a) we apply the Assumption 3.7 (F (xe, 3c)) = (H*)-22 2 f():) and Vi(00) to
B and obtain that for any / (/, 1 have
(H)) 2n f(,) (H)) ff(0") - (H) (0, --)
0') |HH) (V - 0-) ))|
(HH) 2n -H" ))) ff())))
(21)
S 0 0l 0" | pp| 0²)
Thus, we denote Err = O up c0
2|al+1
+ 1) to represent the higher-order infinitesimal term.
Similarly, when 1 < 12, we have
E V - E VV, ((Q))=-0) + Err.
(22)
Then we compute the recursive formula when & 12. Applying L2 t 1 to the recursive formula 32 and take the expectation of two sides, we have
E [[Ve.. Q' 11-111111 1.1- (Q*) + B Err,
(23)
where E
VF((,, -1 -1, -1)) The second term is from E [CC the third term Err is form E [ABT BAT + BB which the order of
E FF (x,, Uer
O 0- I); and E [ACT BCT C.A + CBB = 0. We calculate the second term as
Σ3 = _8 - 8 -
(24)
where - FF(O; 1, 11)) F( (x, Ut. Then we obtain that Σ9 - E. is on the order of (Eso) due to the gradient uniform continuity in Assumption
3.6 For simplicity, we denote (F, (Xt, -1,-111 Db, -1) F. and O0": (xe, -1 Vr. -1)
F
3 1- E VF. F. - AF
E
VF
E
A F2
(25)
For the first term we have
V F AF' F+
R
(H,) "m un (H,) F: um (H,)
(H') (H))
(H*)
E (He) (He) "VA A (HH.) uu (H.)
(H')
(H.))"m uu (H.) -VF (H (H')- ( V
(H) uu (H)) (H)))
Due to Assumption
3.6,
we have
Eall
< EE
V
F, (H,)
(H;) -- (H') mn (H')~a)]
+ E
VV F; - FT (H*) uu (H')-a
E
F, - V=F²) (H,) (H,) - (H") uu
(H*)-a))
+ +E V F" ((H.) (H,)
(H*) (H")~*))
(26)
+ E (V F; FFF mu
V 0, 0 -
+ E pl 0, 211
E 0*1)
50 ped
2/al + t0
14

---

Similarly we have
E||ca| < 0 (pe 2 + +00))
(27)
Thus
0 ((p2 +co) 1). For the term E
VF,
E
V
Fe
we
have
AF B TT = ( ((0))(H))22
<
- V/(0")11 1)
(28)
3 20(00-1 I).
Thus we have E ΣΣT 11 =
+ <o)) =0((m)) 1).
Then we obtain
B [
Ex g" T
+ +0 ((ppp) | + 60 1)
=
E (H))
uu (H*) -VVF) F* (H*) (H*)-auu 1111 (H*) [+]
+]+++]++ + +0 @(ppp
2|al + +co) .I)
En (H)) (H*)
" (H*) (H*) [ + O (ppr 2/a + 60) 1).
where in the second equality we use E VF (x,
and VF (x
Ut, -t)-)) (H*)-"ul (H'')==F((" (x1 1, Ut, -1)) when ignoring the higher-order in- finitesimal term of jr; in the third equality we use Assumption 3.3 Denoting M Eu (H*) -uu "H') uu (H*) -a] we have
E [ Q'E V - (Q') M + Err 0 (n² (ped
2|0l + +co) tco).1) .I)
(29)
Q -Ia + 7 M' + Err.
In summary, we obtain the recursive formula of E V Vatta as
(Q (Q*)*==B ta + Err
if > 12
E [Ve, t..
Q T V -1 (Q)) + M + Eir
if 1 = lg if f1 < t2
(30)
((Q
Err
where Err = O ((nee) + npen 2
2|a|+1
Ee + 7² pen
pE 2/a1) 1).
Least Squares. For least squares regression (6 with o², we notice that the Hessian matrix is fixed as H = _. E(xx and the gradient can be written as
1 VF (X), = T (Vr (0,, xx))
σ (00 -0, +
(31)
x1x, (0: 0-)
EXi o²
r²
Thus we have E ( (x,, 9c)) = (H*) (0, 0r) Thus the second term in the second
equality in (17) is O. The recursive formula of 0,, and ,,, can be exactly obtained as
0, 0" = (Q 12 (0 - 0*)
11-22
(Q)
VF (x
VF(O,, (XL, Vt. -i)).
7
j=1
15

---

for any 1t < to S 2T. Then we similarly obtain the expectation of Ve,ta when t > 82 as
a[ = (Q*)* ( [V wa,
(32)
due to E|C(O,, - 0 without Err. When 12, obtain
E E -V
+ B [
(33)
where & = FF(FF, (0:,-0i (Xt, (-- ())))1))))
FF -si (/.- -)). For quadratic functions,
have He = H". Thus directly obtain
E tr [HEEET)] $ tr² ((H)))-20) tr (H (V tr (H'),
(34)
where the last inequality derived from the assumption that Ex, [x,x] Bx when B and H" share the same orthonormal basis for least squares regression. Thus we obtain the exact recursive formula of EV[t,,, t1.ta] for least squares regression as
(tr (H H
Q (Q")+==E [V s2
if > l/
E [V 1
(Q) +
h = 12,
(35)
E V ((Q)) (2-1)))-)))
if t2.
where ((V (V,,- := -10
0 (
(H*) 20 M
Step IL In this step, we obtain the estimate of the sum of IE (a for t and to from T to 27' 1. First, by the recursive formula (30). we have
min
E E[ (1.t2] = (Q') "07" T [T. ((9))--7) tmp
"M)
Err
Tzy.22
In this step, we try estimate
Σxr-1 It
- Specifically, for any [T,27 1], denote
Ie,t (1) = (00))
((--))---11 Thus we have
2T-1
2T
Σ (t) 172
Σ (Q") (I- (1-(())"
4,6=#11
4=t+1
1 (II (1-(QQ) -I- ( M ( (1-(Q))---)
where we first calculate the sum of l from ( to 27 - given [ then compute the sum of ( from t + 1 to 2T 1. Both use the matrix-formen summation formula for geometric series. We obtain that
2T-1 2T-1
Σ
Σ
(t)
(Tr(t))T(((-'>>>>> (I-Q))-)
T= h,,==111
2T-1
1
2T 1 2*) M (M-QQ))
Q4)
27-1
77
Q MM' (I-Q ( (1-0)))(((00)))4)))
((Q))
2T-1
+ 2
Σ
- (1-Q)-11) (1-Q)))((0))")4)))
(
16

---

where Σn L1, .1 I1
Ei=r Eim+s= (t). Then, applying Lemma D.3 with M
Q"Q and M M to (36). we obtain
27-1 27-1
Σ
Σ
= )
(1- 20) M (H-))(1-220)
1= 4,b
(I-
(I (I- ( M (H-))
(I- Q*) -1=)))ー)) T. (I- (Q)))) (H-)-(1-2a))) M (HH)) T (1-
27-1
12)22---11 (H*) (1 21 (H (1-0)) T ((Q7)2T-(-1)"
t=T
We notice that with 1) 2 Amin ( (H* 1 1-123 Q" 1 (1 mmmin (H*))-20)) I 3 I. Thus have
27-1 2T
Σ
Σ
(1 20 2n (11))-(122))
t= 11,9=11+1
27-1 +
M (HH))-1-20)) T ((Q)) (Q))2T---
1=T
T + (1 nmmii (H*) (H*))-2a))
(H') (H*)-(1-20)M* ((H)) T
(1 min (H+)1 ((1))12aa))"
T + Ammn (H+))1-2)) (H*) (H*)-(1-20)) M (1H-)-(1-20))
The last equality is due to mpmmin ((H))1-20) I 17 Amer ((H) 20
I 1.
Step III. In this step, we finish the convergence analysis of Theorem expansion of f (7 -1 0:) at 0" as below:
3.8
We first utilize the Taylor
2T 2T-1
1 2T
T
2T
f
Σ
0,
S f(0) + 1
Σ
(,
0r)
H"
ΣΣ
Σ
(0))
00
0.-
(36)
T
T
T
since vf(0") O. Then we take the expectation of both sides of (36 and obtain
1 T
27
Σ 0.
)
110))
(0)
S
E
tr
H
2T-1
Σ (0
-0)
7
1
2T-1
Σ
(0.-0-0))
(0.
2
:=T
27'-1 1 Σ
2T-1
tr
H E
Vindaa
2T
(=T
27'-1
2T-1
tr
HrE
Σ
Ien (t)
27
ir ((H*)
10-1 VT:T) + Err
+ 27,2722
2N6 Mmmi
(HH))_ 2T
tr (H") [V,,,))
1772
1
1
+ 2T
21 21 ((H)) Da + 1/12 Da + Err,
where D.. tr H (H- ((H))-1122)) 1) and Err o On + mpr 2|a|+1
1Peo + pe )l To obtain the inequality (a), we use a Ha = ir (Haa T) for any vector a and
17

---

matrix H. (b) is derived from combining 36) with the recursive expression of E Vr,r in (30 when given T. By integrating (36) with the recursive computation procedure for tr ((H))aa- |[ (rr)).
we have the inequality (c).
Next, we compute the trace expression tr (1-2))
2n M
) through the fol-
lowing derivation:
))) tr (HH))a-1.MM)
H HH' (1---MM0
(37)
where M satisfies:
M = Eun [HH) uu
(H*)-a)
(38)
0 ( ((H))1-20))
Inequality (d) is derived from the fact that E[Auu Buu A N O (A)T(r() when
(0 and A, B E Rdxd share the same orthonormal basis. Thus, combing 37 and (38 we
obtain
Ir (1 20) M (HH))-(-20))) ir ((H))a-1))
((H*) (H2))
(39)
In the end, we have
1 2T-1
) s(0') x (1 Mmmin 221))
E
Σ 0: 0.)
br ((H)))-22))
1/272
1/T2
1=T
(40)
tr (
1H2)
+ Err.
T
We complete the proof of Theorem 3.8. Least Squares. For least squares regression, we obtain
( 87) )
2T-1
]
27-1
27-1
E
f T
Σ 0: 1(0")
(e)
1
E
tr
H
T Σ
0 8')
1=T
t=T
T=T
2T-1
tr
1/72
(0) (1
Ammn (H*))-20))
(H 2 (Vo.o) + Da
(41)
nT
where D. = H (H-)) ((H')-(1-20) By a Ha ir (Haa) T) for any vector
and matrix H, have inequality (a). (b) follows from the recursive expression of [Va.1)] in 35 and (c) is obtained from the estimation
tr 2 (V...) < tr (H))
((Q))T
t-1
0r - 0/))) ( (H))) (1Q9)----1)
+ 2
Σ
0
E
2 [-
20 (Q 1''--- (1
+
tr
(H*)
#=0
II
(1
Mmii (HH))1-2a) tr (HH*)
(Vo.o)) + DDa..
(42)
18

---

for any & E [T: 2T 11, where (d) is derived from combining the following recursion
E 0, 0-] = tr (E ..)) Str QQ E V (===,t-1
+1² tr (H)) tr (H)) 1-)) tr (V. (M')
(1 Amin (HH)) ir (V.-1,-11) + 1 (M"),
(43)
with explicit computational procedures applied parameters I and II, where (e) is achieved through Awin (H))
the setting of step size that 1) S Amaz (H (Hr(() ( According to (41), we complete
the proof of Theorem 3.5
B Extensive Analysis under Approximate Hessian
In this section, we further consider the PSPSA using approximate Hessian H2 to replace H,. Previous work] shows that without exact calculation, approximate Hessian can be obtained through zeroth- order oracles with controlled gap between H, and H. Specifically, for least squares regression, due to H, = H", we formally propose the Assumption B. below to characterize the approximate error of Hessian.
Assumption B.1. Given a > the Hessian estimation matrix H. satisfies
H
-HH)) S ac
(44)
With Assumption B. we obtain the convergence rate of PaZO with approximate Hessian for least squares regression Theorem B.2 The complexity estimating Hessian can lower bounded by the rate in Theorem B.2 since we only need to estimate the Hessian one time for least squares regression due to H, H
Theorem B.2. Suppose E 1/2] and the Hessian approximation error defined in Assumption B.1 satisfies S ((((H))))1/(aa) Xuinn where k(H²) = Amuxx (H*)/ Amiu (H*). Consider
running PaZO with approximate Hessian H, satisfying Assumption B. B.1 for the least squares regression
problem (6) under Assumption 3.4 with learning rate satisfying = Ô (Omin 22-
for T iterations. Then PaZO acheves the following convergence rate:
E -110--0'111 $ (1- (Amin (H*)) 1100 0 PT + 3d (m(H))) 2-44
(45)
T
where a is the precondition order defined in PSPSA.
In Theorem B.2 the first term decays exponentially as T, and the dominant term of the rate is 3dfo² (k(H))) An /T. Since k is defined as the condition number of a given positive definite and the equality holds if and only if a 1/2. This result
matrix, notice that (x(H+))2 2-4a amazingly aligns with the results in Theorem 3.5 which demonstrates that the optimal selection of a in PSPSA is 1/2. Without an effect preconditioner, ZO-SGD only achieves O d2 o² (k(H*))² /T), not matching the ideal rate Ô (TT). We provide the proof of Theorem B.2 as follows.
Proof. According to the update rule
Q = - (x,, 9)),,
(46)
'Qinn Yu et al. "Stochastic Zeroth-Ordes Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity". In: arXiv preprint arXiv:2406.1966 19617 (2024).
19

---

we have
(a)
E 1
SE IE
110. 0' H- -2nlE { (0 0" H H H (0. 07)
H
+ 17 22² H, 2n H
110 - 1 H
+ 1 tr (H, 2 H0)
(b)
1 21/ (Amin H )) )a= E
2a
|00 - 0" ||
Amax H c
2n
E
10: 0
20 (H+)
2cx)
(H')
min
tr (H*)
1
110:
(22a (H*)
22a)
tr tr(H*) ) 2
+ 211 21100
(r? ((H*)
+
min
(H*)
2
min (H*)
(0)
1 17 (Amin (H')|
E 110 00
+ 0 ((H*)1-2a)
where (a) is derived from Assumption 3.4
(b) follows the fact Amin HH 20 (A (H*) 220)
and | 2a
(H*) 2a
20x
2a (H))
2²x) 2 (H²)). and (c) is obtained from the
setting of and Assumption B.1 obtain
According to the recursive expression of E ||0, 1 H- we
E
10r
0r
0T H-
$ <11-
(mmin(H')))
(Amin (H*))²
110 1
3no²
tr?
((H) 20) (-2))
(47)
11 2a (H*)
By applying the chosen value of (47). we complete the proof.
C Experiment Setup
C.1 Dataset
For RoBERTa-large, we consider classification datasets: SST-2 47 SST-5 [7 TREC (51), MNLI
(44. SNLI (7). and RTE 200 14 [8.6) 6). We follow (37) to limit the test set with 1,000 examples for fast iteration. For training and validation, we set i 16, which means that we have 16 examples per
class for both training and validation.
For OPT- we consider the SuperGLUE dataset collection 52 including: BoolQ 13
CB 15
CОРA 45 J. MultiRC (27]. ReCoRD (56). RTE [20 14 [8
WiC (43) and WSC 30
We also
consider SST-2 (47 and report the results on the above 9 dataset with randomly sampling 1,000
examples for training, 500 examples for validation, and 1,000 examples for testing.
C.2 Hyperparameters
We use the hyperparameters in Table for experiments on RoBERTa-large. Previous work (37 shows that the choice of seems not significantly impact the performance, and using a larger batch size consistently yielded faster optimization. We use the hyperparameters in Table for zeroth-order methods on 1.3B..3B. We use linear learning scheduling for first-order fine-tuning methods with backpropagation, and constant learning rate for all zeroth-order methods.
For RoBERTa- large experiments, we evaluate the model on validation sets every 1/10 of total training steps and save the best validation checkpoint. All FT experiments use 1K steps and zeroth-order methods use 100K steps. For OPT-1.3B experiments, we evaluate the model on validation sets every 1/5 of the total training steps and save the best validation checkpoint, All zeroth-order methods in experiments use 20K steps.
20

---

Algorithm 3 MeZO
Require: parameters θ {0, E Rd),, loss C R + R, running steps T, perturbation scale μ4,
learning rate schedule 7/. random seed random number generator
for t = 1, ..., do
Step I: Perturb Parameters through Diagonal Hessian
Sample batch 8 C 'D and random seed 8
0 <- PerturbPParameters(.... jr,
4 + L(0; B)
< PerturbParameterss(.. -2p,
E- + L(0; B)
0 < PerturbParamettrss(. μl, s)
Step 2: Update the Parameters
Reset random number generator with seed projected _grddeddddddd_ddd + (f+ 2
for 0:
do
Sample (O. Ia,) 0: + 0, T projected_gres grad *u1
end for end for
C.3 Parameter-efficien Fine-tuning
Storing and fine-tuning a large language model for each downstream task can be quite costly. Parameter-efficient fine-tuning (PEFT) techniques help mitigate this issue: instead of fine-tuning all model parameters, PEFT only modifies small percentage of additional parameters (usually less than 1%) and often achieves comparable better performance
[23 3TJ. The zeroth-order optimizer is compatible with PEFT methods because it can operate on any subset of the model parameters. We conduct experiments with the following two common PEFT methods: LoRA [3 and prefix-tuning
31
LoRA [33 enhances linear layer during fine-tuning by adding tunable low-rank delta. Initially, the linear layer is defined as Wx + during pre-training, where W E Rmxn, During fine-tuning. LoRA introduces two smaller matrices A E Rmxr and B Rex= such that < min(m,n)) Consequently, the modified linear layer becomes
a AB x b. (
(48)
where a and r are hyperparameters. Aand are trained on the downstream tasks while W frozen at its pre-trained value. is empirically small and we choose = 8 and a 16 in our experiments.
Prefix-tuning (31) a technique where prefix m tunable representations added at each layer, while the remaining parts of the model are frozen. These added representations function new keys and values, serving as additional context during the attention operation. The initialization of these tunable representations involves randomly sampling tokens from the vocabulary and passing them through the L.MSs to obtain their keys and values at various attention layers. In our experiments, setting m = 5 proved sufficient to achieve good performance most tasks.
C.4 Zeroth-order Optimziers
Zeroth-order optimization for fine-tuning LLMs has become matter of concern recently, showing great potential for reducing the memory overhead during fine-tuning tasks. We introduce two representative zeroth-order optimizers: MeZO [37] and HiZOO [59], and explain that they are both special case of the PSPSA we propose with a specific choice a.
MeZO (37] is stated in Algorithm 3, with Simultaneous Perturbation Stochastic Approximation or SPSA [48 to estimate the zeroth-order stochastic gradient with two forward passes. When μu -+ it can be regarded to use 1-rank stochastic gradient for the update. From the perspective of PSPSA, MeZO can be regarded to set a = PSPSA, as we state in Algorithm 3 with "preconditioner".
21

---

Table 3: The hyperparameter grids used for RoBERTa-large experiments. MeZO and PaZO uses constant learning rate schedule. All MeZO and PaZO experiments use 100K steps.
Experiment
Hyperparameters
Values
MeZO
Batch size
64
Learning
{le- 7, le 6, le- 5}
1e-3
Weight Decay
0
MeZO (prefix)
Batch size Learning rate
64 {le 2, 5e-3, 1e-3)
le-1
Weight Decay # prefix tokens
0
5
McZO (LoRA)
Batch size Learning rate
64
{le-5, 5,-5, le-4)
le-3
Weight Decay (r,a)
0.1
(8, 16)
PaZO
Batch size Learning rate
64
{lc 7, 6, 1e 5]
le-3
Weight Decay
0
PaZO (prefix)
Batch size Learning rate
64
{1e 2, 22,5e-3. 1e-3)
le-1
Weight Decay # prefix tokens
0
5
PaZO (LoRA)
Batch size Learning rate
64
{1e-5, 5, 5e-5, 5, 1e-4)
le-3
Weight Decay (r,a)
0.1
(8, 16)
FT
Batch size
(2, 1,8
Learning rate
{le 5, 5,3e-5, 5e-5) 0
Weight Decay
FT (prefix)
Batch size
16,
16, 32}
Learning rate
{le-2 2, 2, 5e-2)
Weight Decay # prefix tokens
0
5
FT (LoRA)
Batch size
(4,8, 16)
Learning rate (r, a.)
{lu- 1, 3e-ee-44. 5e 4]
(8, 16)
is stated Algorithm 4 with preconditioned SPSA with H-1/2 as the preconditioner in the perturbation, and H as the preconditioner in the estimated stochastie gradient. In other words, HiZoO can be regarded as setting selection of is 1/2, however, we empirically show the best performance PaZO compared with MeZO and HiZOO with the same hyperparameter setting through our experiments.
HiZOO 159
1/2 in PSPSA. In our theoretical analysis, the optimal
C.5 Details about Memory Usage
We show the detailed peak memory overhead results in Table set the per-device batch size to to obtain the minimum peak memory overhead of the corresponding models and methods, We also do not turn on any advanced memory-saving options, e.g., gradient checkpointing. We directly use Nvidia's mvidia-smi command to monitor the GPU peak memory overhead.
22

---

Table 4: The hyperparameter grids used for OPT-1.3B experiments. All weight decay is set to 0. PaZO uses 20K steps and constant learning rates.
Experiment
Hyperparameters
Values
MeZO
Batch size
16 {1e-6, 5e-5. 1e-73
Learning rate
/
1e-3
MeZO (prefix)
Batch size Learning rate f4
{5e 2, 1e-2, 5e 5e-3)
1e-1
prefix tokens
5
MeZO (LoRA)
Batch size
16
Learning rate
(le 5e 5e-5, 1e-5)
1e-2
(r, (x)
(8, 16)
HiZOO
Batch size
Learning rate f
{1e-6, 6, 5e-7, le-7)
le-3
HiZOO (prefix)
Batch size Learning rate μ
16
15e 2, 1e-1, 5e
le-1
prefix tokens
HiZOO (LoRA)
Batch size Learning rate
{le- 4, 5e-5, 1e-5)
1e-2
(r,
(8, 16)
PaZO
Batch size Learning rate
16
(le 5e 1e-
1e-3
PaZO (prefix)
Batch size
16
Learning rate
[5e le 1elel-255
5e 33
1e-1
prefix tokens
5
PaZO (LoRA)
Batch size Learning rate
16
{le- 5e-55-55 1e-5)
fA
1e-2
(r, ax)
(8, 16)
Table 5: Peak memory on the MultiRC (average tokens=400) dataset.
Method
zero-shot/Me20
PaZO
ICL
FT
(prefix)
1.3B
IxA6000 (4GB)
Ax (9GB)
IxA6000 (6GB)
IxA6000 (27GB)
IxA6000 (19GB)
2,7B
IxA6000 (7GB)
IxA6000 (14GB)
1xA6000 (8GB)
2xA6000 (55GB)
1xA6000 (29GB)
6.7B
IxA6000 (14GB)
IxA6000 (30GB)
IxA6000 (16GB)
4xA6000 (156GB)
1xA6000 (46GB)
13B
IxA6000 (26GB)
2xA6000 (54GB)
IxA6000 (29GB)
8xA6000 (316GB)
4xA6000 (158GB)
C.6 Wall-clock Time
We report the steps and wall-clock time required reach 60% accuracy on representative task RTE in Table 6, These results support our claim that PaZO achieves better convergence speed than existing zeroth-order methods by leveraging an ideal choice of the preconditioner order. Both the required number of steps and the total training time to reach the target accuracy are smaller for PaZO, validating our theoretical insights. Moreover, although the per-step cost of PaZO is slightly higher than MeZ0-ay as we transparently report in Figure -his is more than offset by its improved convergence rate. In particular, PaZ: reduces the total wall-clock time by approximately 10% compared to McZO, demonstrating that it is efficient in practical settings.
23

---

Algorithm 4 HiZOO
Require: parameters θ = {0; E } loss L : R + R, step budget T, perturbation scale μ4,
learning rate schedule ne. smooth scale 3,, diagonal Hessian Eg
1: for t 1,..... ..., do
2: Sample batch B C D and random seed
3: f < L(0; 5)
4: 0 PerturbParametersS(.. p. E 8)
5:
+ -- [(0; B3)
6:
0 + PerturbParameters((.. -2,, 2 8)
7: L C(0;B)
8: θ + PerturbParameters(6 1//2 s)
9: E, 1 (c+ + 2 uu Σ --1
2n²²
E, (1-04)
04 - + 91 diag E
11: projected Beartedggddd___ - (e+ (-) E. /2
12: Reset random number generator with seed 8
for 0g E O do
14: Sample u; ~ (0, Ia,)
0: < 0; 1/** projected_gget grad su;
16: end for
end for
Table 6: Steps and wall-clock time required to reach 60% accuracy for OPT-1.3B on RTE,
MeZO
HiZOO
PaZO
Steps
15000
10000
9000
Wall-clock Time (s)
3848
3785
3453
C.7 Ablation Experiments
We conduct experiments to research the influence of Л3 and (3 in the practical version of PaZO in Algorithm [ Specifically, we use PaZO to fine-tune OPT-1.3B model on SST2. We fix 31 1e 8 and change 32 from 0 to le- 10 first. Then we fix 32 = 1c-8 and change 31 from 0 to le- 1c-10. We report the results in Table 7
The results show that PaZO is sensitive to the smooth hyperparameters 31 and $2. The excessive choice of will seriously affect the convergence, due the large variance of g o g, while too small choice of 31 also affects the performance since it takes little information of g. The choice of 33 is relatively lenient, but still needs to be the same order of the learning rate 77. The best choice of 83 may vary across different dataset. In our experiment, we uniformly set 31 and B3 as 1e-8 for fair comparison.
We also conduct an ablation study on the effect of the reset period To in Table 8 In this experiment, the SST2 dataset, while varying
fine-tune the OPT-1.3B model and evaluate its performance the value To E {64, 128, 256, 512) and co (without resetting). We aim to examine how the frequency of resetting the moving average of the preconditioning matrix influences training stability and final accuracy. The results show that as the number of iterations increases, the error the Hessian estimation obtained from the zeroth-order oracle tends to accumulate over steps. This accumulated error may grow with the number of iterations. Therefore, when no resetting mechanism is used (as in the case of in the table above), the performance drop when overly old historical accumulated error may mislead the current update direction, ultimately harming final performance. On the other hand, considering that Σ is initialized as the identity matrix I. there exists a gap between I and the Hessian H" When the resetting frequency is too small (e.g., 128), the information accumulated in Σ; is insufficient to effectively bridge this gap. The inaccurate estimation similarly leads to worse final model performance. The hyperparameter To plays the role of trade-off between error accumulation and Hessian estimation accuracy. Our experimental results also indicate that the model achieves the best performance when To falls within certain range.

---

Table 7: Influence of 31 and 32 in Algorithm 1 for OPT-1.3B on SST2.
B1 (82)
le-2
le-4
1e-6
1e-8
le-10
fixed B1 1e-8
NaN
NaN
NaN
88.9
(+0.3)
89.0 (=
89.0 (+0.2)
fixed B2 = 1e-8 8
NaN
NaN
NaN
NaN
89.0 (=0.1)
88.9 (+0.2)
Table 8: Influence of To in Algorithm
I Toor OPT-1.3B on SST2.
To
64
128
256
512
00
88.5
88.8
89.0
88.3
87.7
D Auxiliary Lemmas
Lemma D.I. For matrix A E IR and vectors E 1m NRR R" if + uo is invertible, we have
(A + uv 7) =A - (v, U2)
(ng U2) AA fnn
02
+ + U2) (u U2)
-1 (1 v. A Atui) fzug.
(49)
where u1 + U2 with un (A), u2 1 (A) and v 0i U2 with U1 col T), U2 1 col(AT ). In addition, can obtain that (A + Auv -u X (u, U2) for any À > 0.
Lemma D.2. We assume matrix M M & I - (c) @ M where M Rmx" Ci E R", C2 E TR and M E Rdxd is symmetric, and matrix M E 1ædxd is positive semi-definite. Given positive semi definiee matrix we suppose that the max singular value of M strictly smaller than 1, and matrices B and M share a common set of orthonormal eigenvectors. Specifically, their spectral decompositions can be expressed as:
PAP-1
M = PAPAP-1
where P E Raxd is an orthogonal matrix, and 7 and A are real diagonal matrices. Then we oblain
tr (IIm & B)M's ((dd)) & M) (' S BaaldB) tr
(50)
where CM and Pm
two positive constants depend on M.
Proof. We prove estimation Eq. 50 at first. There exists an orthonormal matrix P E Raxd such that M PAP-1 where A diag λ ... Aaj. Therefore, we have that
M (Lm @ P diag M -dicict .M - ---cce Q (Im @ P
(51)
where Q mdd is orthogonal matrix. For simplicity, we denote D diag(M
Tdiciot, . -Mdcccre and D. M 7Aseic.. Therefore, we can obtain
M ((dd)) s0 M) (M (a) (Im & Q)QTD (P PP-MP-T- (dd (d (DT)QQQQ [Im 3 PT)
(Im P)Q AQ [Im & P
(52)
where
A A
A
Add
with Aij mm satisfies Aij (P-1MP T) Dr D DDJ for any i, [1 d], (a) is derived
from the fact that
(Im X p-1) ((ddT) @ M) (Im 8 P-T)) = (dd) @ 1PP-MP--
and
Q Q(dd") 2 x MP "M-
8P-MMP-11
")=") Q
=P-'MP x (dd
25

---

According to the property of Q. we have
tr (Im & B) (Im @ P [Im & PP)) tr [PPPTT)
(53)
where Á E Rdxd satisfies Aij = (P MP D)y (D.d, Djd) for any i,j E [1 : d]. Since
P BP A, we derive that
[PPAPT) & [P BPI S Cm CM P 11 B 7MM) ( tr(M)
(54)
for any positive semi-definit matrix Rdxd, where (b) follows from the fact that
D = (Im & P QM' (Im & P)Q e, @ d,
(55)
where 6 &Rd denotes vector whose element the i-th position is equal while the elements in all remaining positions are equal to 0, and the assumption that the max singular value of M is strictly smaller than 1.
Lemma D.3. We assume matrix M = M @ la (cie)) & M where M E Rmxmm E R C2 Th and M E TRdxa, and matrix M RRddd is symmetric. M also symmetric, and both M and M invertible, we have
M ((cie) & MM) T = =|ee2211 (c22 @ M (M'MM-))
(56)
where C2 = C21 + C22, C21 E col(MT and C22 1 col(MT
Proof. Similarly, there exists an invertible matrix P E Raxd such that M = PAP-1 where diag(>1. A1, ... >a)- Therefore, we have that
M (Im & QT diag [ Aiciot M Aacics Q (Im 8 PP1), (57)
where Q Rmdxmdd is an orthogonal matrix. For simplicity, denote D diag (M AIcicT .... M + ) Furthermore, we can obtain that
M M-1 (((ce) Ø M) M
= =Lm & P ((ccc)) @ (P-IMP-T)QQ' -T (Im PP)).
(58)
Since Q is, in fact, coordinate transformation matrix, we have
Q (()cc)) @ (P-MMP-T) Q = =(p (P-1MM) 'MP-T) @ (c1cT) Therefore, we can derive that
Aul
A Aid
D ((P ((P- ((--MMPT) MP-T) @ (cicT)) D-T
(59)
Ad
Add
by using Lemma D.1 where Aij E Rm and
P MP T ij M + xccc)) (aic) (M+A)))cc)
Ai
=I x 1 (P 1P-'MP- }, c22c22.
(60)
According to the property of Q we obtain
Q D ((P-MMP-)
(c1cT] D - q-
|cal " (c22022)
(A-'P-'MP-
'MP- -M--' (61)
Combining Eq. (58) and Eq. (61) we complete the proof.
26

---

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: the abstract, we briefly introduce our contribution while in the Introduction we propose the three problems focus and our three contributions followed behind "Our contributions are".
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 be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification: the experiment part we compare the per-step time cost and analyze the reason method is slower than the baseline per-step due an additional forward pass.
Guidelines:
The answer NA means that the paper has 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 separate "I "Limitations" section in 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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or 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 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 in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
27

---

Answer: [Yes]
Justification: We provide all the assumptions in the "Theoretical Insights of PaZO" section, and provide complete proof in 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 they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the details of our experiments in Appendix C including the models, dataset, methods and hyperparameters use for reproducibility.
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 to 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 to either make it possible for others to 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 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, other means that appropriate to the research performed.
also be provided via detailed
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) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
28

---

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]
We are organizing our code and will make it public after the organization is completed.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
oliccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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
//nips.ccpublle pwwppppguuuiieeeeep hetpc///uuudess/eeeuubuiiiii SroodeSubiissi.e ssiiiiolcccy for more details.
The authors should provide instructions 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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 provide the details of our experiments in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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 average results with the form (=std) in Table I
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, 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).
29

---

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
If 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: In Appendix C.5 we provide the compute resources to reproduce the experi- ments with different scales and methods.
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 as 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 or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttps://neuripee http://wwwrpp.ccccoooiiiicaaaaaa inte
Answer: [Yes]
Justification: Our research is with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss that our algorithm can save memory cost when fine-tuning LLMs.
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.
30

---

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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper poses no 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 to usage guidelines or 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 the paper that produced the models and dataset we use.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, 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.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
31

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is 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: [Yes]
Justification: We will make our algorithms and fine-tuned models public after the organiza- tion is completed with formal documents and codes.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 the main paper.
According to the NeurIPS Code 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [Yes]
Justification: This paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
32

---

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
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that 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.
Answer: [Yes]
Justification: The aim of research is efficiently fine-tune pre-trained LLMs with lower memory cost, with faster speed compared with other zeroth-order methods.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to LLM policy for what should or should not be described.
33


Reviews:
[{"review_id": "27qyqDEsbD", "reviewer": "Reviewer_Gw49", "summary": "The paper introduces PaZO, a preconditioned accelerated zeroth-order optimization algorithm designed for fine-tuning large language models (LLMs) without backpropagation. The authors address three core challenges: (A) whether preconditioning is necessary in zeroth-order optimization, (B) how to optimally apply preconditioning for fastest convergence, and (C) how to practically estimate Hessian information to improve performance. They theoretically prove that zeroth-order stochastic gradient descent (ZO-SGD) alone is suboptimal and that using a preconditioner of order −1/2 yields the best convergence rate. PaZO incorporates this insight into a practical algorithm using diagonal Hessian estimates and moving averages for stability. Extensive experiments on models like RoBERTa-large and OPT-1.3B across various tasks and parameter-efficient fine-tuning (PEFT) methods demonstrate that PaZO outperforms existing zeroth-order methods (e.g., MeZO, HiZOO) in both accuracy and memory efficiency, achieving state-of-the-art results with manageable computational overhead.", "questions": "- How does PaZO compare to MeZO and FO methods on more recent LLMs, such as Llama 3?\n- Can the authors show learning curves of the experiments reported in Tables 1 and 2, it would be curious to see how fast each method converges.", "limitations": "The authors did not properly asses the limitations of their work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is well written, and tackles an important problem: efficient LLM fine-tuning\n- The authors rigorously prove that standard zeroth-order stochastic gradient descent (ZO-SGD) cannot achieve the optimal convergence rate, establishing the necessity of preconditioning in zeroth-order optimization. They introduce a generalized framework—Preconditioned Simultaneous Perturbation Stochastic Approximation (PSPSA)—and derive convergence bounds for both quadratic and general smooth functions. A key strength is the identification of the optimal preconditioning order (α = 1/2), which is shown to yield the fastest convergence rate. These results are supported by detailed proofs and assumptions, including extensions to scenarios with approximate Hessians.\n- The authors present a practical algorithm, PaZO, and demonstrate its effectiveness empirically across a wide range of downstream tasks,  model architectures, and fine-tuning strategies.\n\nWeaknesses:\n- The practical version of PaZO is not so practical. It strongly resembles HiZOO, with slight differences in estimating the Hessian, and introduces extra hyperparameters ( $T_0$, $\\beta_1$ and $\\beta_2$) that are not properly studied. The choice of $T_0$ is not properly ablated, and Table 6 in the appendix shows that the PaZO is highly sensetive to the choices of $\\beta_1$ and $\\beta_2$. \n- The authors claim that PaZO maintains the memory efficiency of HiZOO, but Figure 1 does not show the memory overhead of HiZOO.\n- The performance improvement of PaZO over HiZOO is only demonstrated for OPT (and not RoBERTA). For OPT, the improvement does not seem to be significant.", "was_revised": true, "final_justification": "After the authors' rebuttal most of my questions/concerns have been addressed, and I have updated my score from 4 to 5.", "rebuttal": "# Response to Reviewer Gw49\n\nWe sincerely thank the reviewer Gw49 for the constructive and thoughtful feedback. We greatly appreciate your recognition of our work and your valuable suggestions. We provide point-by-point responses to each of your comments.\n\n## 1. The hyperparameters in the practical version of PaZO (regarding Weaknesses 1)\n\nThank you very much for pointing out this important issue and helping us improve the clarity of our presentation. First, we would like to clarify that although our algorithm shares some structural similarities with HiZOO in terms of estimating the Hessian diagonal, there is a fundamental difference in the core design. Specifically, our method is guided by theoretical analysis, which leads to the choice of the preconditioner order $\\alpha=1/2$ in contrast to HiZOO’s $\\alpha=-1/2$. This results in essential differences in how the optimization trajectory evolves. While the Hessian estimation procedures may appear similar, the use of the preconditioner are theoretically justified and practically distinct in PaZO.\n\nWe also sincerely thank the reviewer for pointing out that our discussion of hyperparameters could be more comprehensive. We now provide additional clarification. First, we correct a typo in Table 6 of the appendix: the second column in the first row should be 1 instead of 0. We apologize for the confusion this may have caused. Then, regarding the role of the hyperparameters, it is sensitive to $\\beta_1, \\beta_2$ because $\\beta_1$ controls the strength of the additive correction to the Hessian diagonal estimate. This correction ensures that the scaling effect in our algorithm behaves similarly to Adam-style updates, helping maintain numerical stability during training. $\\beta_2$ governs the moving average applied to the Hessian diagonal estimates. This is a common technique to stabilize estimates over time and smooth the update directions from the zeroth-order oracle.\n\n$T_0$ determines the frequency at which the preconditioner is reset. We agree that the original manuscript lacked a dedicated ablation for this parameter. We have now conducted additional experiments to investigate the effect of varying $T_0$, and we provide the results and analysis below.\n\nIn this experiment, we fine-tune the OPT-1.3B model and evaluate its performance on the SST2 dataset, while varying the value $T_0 \\in\\{64, 128,256, 512 \\} $ and $\\infty$ (without resetting). We aim to examine how the frequency of resetting the moving average of the preconditioning matrix \ninfluences training stability and final accuracy. The results are summarized in the table below:\n\n\n| $T_0$| 64| 128 |256 | 512 | $\\infty$ |\n| -- | -- |--| -- | -- | -- | \n|SST2  |88.5|88.8 |89.0 | 88.3| 87.7|\n\nThe reason behind this design and observation is as follows. As the number of iterations increases, the error in the Hessian estimation obtained from the zeroth-order oracle tends to accumulate over steps. This accumulated error may grow with the number of iterations. Therefore, when no resetting mechanism is used (as in the case of $\\infty$ in the table above), the performance drop when overly old historical accumulated error may mislead the current update direction, ultimately harming final performance. On the other hand,  considering that $\\Sigma$ is initialized as the identity matrix $I$, there exists a gap between $I$ and the Hessian $H^*$. When the resetting frequency is too small (e.g., 128), the information accumulated in $\\Sigma_t$ is insufficient to effectively bridge this gap. The inaccurate estimation similarly leads to worse final model performance. The hyperparameter $T_0$ plays the role of a trade-off between error accumulation and Hessian estimation accuracy. Our experimental results also indicate that the model achieves the best performance when $T_0$ falls within a certain range. We will discuss more about the ablation study on $T_0$ in the camera-ready version. Thank you again for your feedback.\n\n\n## 2. The memory overhead comparison between PaZO and HiZOO (regarding Weaknesses 2)\n\nThank you for pointing out the missing comparison in Figure 1. Our statement that PaZO maintains the memory efficiency of HiZOO is meant in the literal sense: both HiZOO and PaZO incur additional memory overhead primarily due to storing the diagonal estimate of the Hessian, which is of the same size in the same model. Therefore, the peak memory consumption of the two algorithms is nearly identical. For example, when fine-tuning OPT-1.3B on MultiRC, both PaZO and HiZOO have a peak memory usage of approximately 9 GB. We will update Figure 1 in the camera-ready version to include HiZOO for completeness and clarity. Thank you again for your careful review.\n\n## 3. More comparison of PaZO with another methods (regarding Weakness 3 and Question 1)\n\nWe sincerely apologize for the limited scope of our experiments due to hardware constraints. However, we believe that the existing results are still indicative of the strengths of our method. While the improvement of PaZO over HiZOO on OPT is not dramatic, it is consistent across the majority of tasks. Moreover, PaZO shows improvement over HiZOO under different tuning paradigms, including LoRA and prefix tuning. This consistency suggests that the advantage of PaZO is not limited to a specific task or setup, but rather stems from a more principled design. This aligns well with the goal of our work to investigate how to better utilize preconditioning in zeroth-order optimization, and our theoretical analysis, which motivates a carefully chosen preconditioning order. We have indeed considered conducting experiments on LLaMA3. However, due to current hardware limitations, we were unable to properly apply this model. Now we are actively working to overcome these constraints and are making every effort to complete the experiments. If time permits, we may be able to report partial results during the review process, and we will include the complete results in the camera-ready version. We sincerely thank the reviewer for raising this point and appreciate your understanding.\n\n## 4. The learning curve of experiments (regarding Question 2)\n\nWe sincerely thank the reviewer for raising this important question. However, due to the rebuttal policy, we are unfortunately not allowed to include any PDF files or external links in our response, and thus we are unable to directly provide the learning curves here. However, we would like to explain that all of our experiments are conducted in fine-tuning tasks. This means that, rather than focusing solely on minimizing the final loss value, our primary objective is to improve the performance of the fine-tuned model on downstream tasks—as shown in Tables 1 and 2. For fine-tuning, a lower loss does not necessarily imply better task performance. \n\nAs an alternative way, we can briefly describe an example of the validation loss v.s. steps: considering fine-tuning OPT-1.3B on RTE, the steps by which the validation loss achieves 0.62 are roughly 8000, 6000 and 5000 of MeZO, HiZOO and PaZO, respectively. These illustrate the efficiency of PaZO compared to others to some degree. We will include detailed learning curves for the experiments in Tables 1 and 2 in the camera-ready version to better illustrate the training dynamics of different methods.\n\n\nOnce again, we sincerely thank the reviewer Gw49 for the thoughtful comments and constructive suggestions. We have carefully addressed each of the concerns raised, and we truly appreciate the opportunity to clarify and improve our work. We are grateful for the reviewer’s recognition of our contributions.  We would be deeply grateful if the reviewer Gw49 could consider a higher score."}, {"review_id": "CKbSZh5d0i", "reviewer": "Reviewer_bWDk", "summary": "This paper introduces PaZO, a preconditioned zeroth-order optimization algorithm designed for the memory-efficient fine-tuning of LLMs. The authors provide a solid theoretical foundation, demonstrating the necessity of preconditioning in ZO optimization to achieve faster convergence. They derive the optimal preconditioner and develop a practical algorithm that estimates the diagonal Hessian using only forward passes. The experiments show that PaZO outperforms existing ZO methods like MeZO and HiZOO and achieves performance comparable to first-order fine-tuning while using significantly less memory.", "questions": "To strengthen the claims about \"convergence speed\", could you provide practical \"time-to-accuracy\" results? For example, on a representative task like SST-2, how much wall-clock time does it take for PaZO, MeZO, and FT to reach 95% of their respective final accuracies?", "limitations": "I did not see potential negative societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros:\n\n- The practical PaZO algorithm is an application of the theoretical insights. The design choices, such as estimating the diagonal Hessian to maintain O(d) memory and using moving averages and resets for stability, are well-justified and make the algorithm practical for fine-tuning modern LLMs.\n\n- The core theoretical strength is not just that the authors prove preconditioning is necessary, but that they derive the optimal form of the preconditioner from a formal convergence analysis. The technical argument in Theorem 3.5 is particularly elegant. \n\n- The paper's main strength lies in its rigorous theoretical analysis. It methodically answers three key questions about preconditioning in ZO optimization. The convergence analysis in Theorems 3.5 and 3.8 provides a clear, formal justification for why preconditioning is necessary and demonstrates that using the inverse square root of the Hessian (H^{-1/2}) as a preconditioner is optimal for achieving the fastest convergence rate. This is a significant theoretical contribution.\n\nCons:\n\n- The authors are transparent about PaZO's per-step time, noting it is about 1.5x slower than MeZO due to an additional forward pass (Figure 2). They argue this is offset by a better convergence rate. However, the analysis would be much stronger with a direct comparison of the total time (or number of steps) required to reach a target accuracy. A plot of accuracy vs. wall-clock time for PaZO against the baselines would more directly substantiate the claim of overall faster training.\n\n- While the theoretical framework is novel, some components of the practical algorithm in Section 4 are based on existing techniques. For example, estimating the Hessian diagonal via forward passes and using moving averages to stabilize training are known methods. The main novelty is the specific formulation justified by the theory for alpha = 1/2, which is a strong contribution, but the practical implementation itself is a clever combination of established components rather than a completely new mechanism.", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer bWDk\n\nWe sincerely thank reviewer bWDk for the positive evaluation and thoughtful comments on our work. We greatly appreciate your recognition of the theoretical contribution and the careful reading of both the algorithm design and the empirical results. We find the comments valuable in helping us improve the clarity of the paper. We provide detailed responses to each of the raised concerns in the following part, and we will incorporate the corresponding revisions and discussions into the camera-ready version.\n\n## 1. Report on wall-clock time v.s. accuracy (regarding Cons 1 and Question)\n\nWe sincerely thank the reviewer for proposing this important point. We fully agree that comparing the wall-clock time to reach a target accuracy would more directly demonstrate the overall training efficiency of PaZO. However, due to rebuttal policy constraints, we regret that we are unable to include any PDF figures or external links in our response, and therefore cannot directly present the accuracy vs. wall-clock time plot at this stage. As a complementary reference you mentioned, we instead report the steps and wall-clock time (in seconds) required to reach 60% accuracy on a representative task RTE in the table below:\n\n|  |  MeZO | HiZOO|  PaZO | \n| -- | -- | -- | -- |  \n|Steps | 15000 | 10000| 9000 | \n|Wall-clock Time (s) |  3848| 3785|3453| \n\nThese results support our claim that PaZO achieves better convergence speed than existing zeroth-order methods by leveraging an ideal choice of the preconditioner order. Both the required number of steps and the total training time to reach the target accuracy are smaller for PaZO, validating our theoretical insights. Moreover, although the per-step cost of PaZO is slightly higher than MeZO—as we transparently report in the paper—this is more than offset by its improved convergence rate. In particular, PaZO reduces the total wall-clock time by approximately 10% compared to MeZO, demonstrating that it is not only theoretically sound but also efficient in practical settings. We will include these additional wall-clock time comparisons and corresponding wall-clock time v.s. steps plots in the camera-ready version.\n\n## 2. The components of our algorithm and our main contributions (regarding Cons 2)\n\nWe sincerely thank the reviewer for the insightful comment. As you mentioned, some components of our practical implementation, such as diagonal Hessian estimation via zeroth-order oracles and the use of moving averages, are adapted from existing techniques. However, as emphasized in the Introduction, our main focus lies in addressing three questions including:\n(1) Is preconditioning theoretically beneficial in zeroth-order optimization?\n(2) If so, what is the optimal order to obtain ideal convergence?\n(3) How can we translate this theoretical insight into practical algorithm design? While previous works have proposed related techniques and components, they do not provide clear theoretical answers to the above questions. In contrast, our work presents a novel analysis framework that leads to a principled justification for preconditioning in zeroth-order optimization, particularly when the preconditioner order is set to $\\alpha=1/2$, and demonstrates how this insight can be effectively implemented in practice. We believe that this new perspective offers substantial theoretical and practical value, and may serve as a useful work for better understanding and further advancing the field of zeroth-order optimization.\n\nWe sincerely appreciate the reviewer’s positive evaluation of our work. Your thoughtful comments and recognition of both the theoretical contributions and practical relevance of PaZO are highly encouraging to us. We will incorporate the additional experimental details on wall-clock time above into the camera-ready version to further strengthen the presentation. We would be deeply grateful if the reviewer bWDk could consider a higher score."}, {"review_id": "1f1sthtDES", "reviewer": "Reviewer_DhFc", "summary": "The paper proposes a preconditioned accelerated zeroth-order method, PaZO, for fine-tuning LLMs. Theoretically, the paper justifies the use of preconditioners for ZO methods by showing the convergence rate gap between with and without Hessian preconditioning. Motivated by the theory, the paper proposes a practical realization of PaZO using diagonal Hessian estimate and moving average. Numerical experiments on masked LLMs and generative LLMs demonstrate the memory and timestep efficiency of PaZO compared to first-order methods and ZO methods without preconditioning acceleration.", "questions": "1. In Theorem 3.5, can you provide more explanation on the relation between $D_\\alpha$ and $d^2$? In particular, how does the lower bound scale with $\\alpha$? While the paper claims that $\\alpha=0$ leads to strict inequality and is thus suboptimal, it would be better to have more explicit characterizations. \n\n2. In Theorem 3.8, how large is $\\epsilon_0$? It seems to be treated as small so that $Err$ represents high-order errors, but how is it guaranteed? \n\n3. In Appendix C.6, Table 6, why are $\\beta_1$ and $\\beta_2$ so small (around $10^{-8}$)? This would be a particular issue given that many LLMs use low precision (e.g., bfloat16) during training to save memory, and $10^{-8}$ seems to be too small. This makes the results less convincing. \n\n4. How much more memory overhead does PaZO have compared to MeZO? Figure 1 uses a log scale, which makes such a comparison less transparent. \n\n5. Is it possible to plot the validation loss vs steps? It would better illustrate the efficiency of PaZO compared to other methods. \n\n6. What are the standard deviations in Table 6? From the numbers, PaZO seems to have marginal improvement over HiZOO, especially in the LoRA and prefix settings.", "limitations": "1. Sensitivity to $\\beta_1$ and $\\beta_2$ should be mentioned in the main text, as they are important hyperparameters and are abnormally small.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: \n\n1. Reducing the memory usage for LLM fine-tuning is an important topic and has significance in practice. \n\n2. The paper is properly framed under questions A, B and C. It provides their method along with the motivating theory. \n\nWeaknesses: \n\nWhile the paper is well structured, its content leaves many puzzles lacking explanations. See Questions.", "was_revised": true, "final_justification": "The authors' detailed responses address my questions.", "rebuttal": "# Response to Reviewer DhFc\n\nWe sincerely thank the reviewer DhFc for the thoughtful and constructive feedback. We appreciate the time and effort spent in evaluating our work. We provide detailed responses to each of the raised concerns in the following part, and we will incorporate the corresponding revisions and discussions into the camera-ready version.\n\n## 1. The explanation on the relation between $D_\\alpha$ and $d^2$ (regarding Question 1)\nThanks for your question on our clarification. In Theorem 3.5, the key parameter is $\\alpha$. We define $\\beta=2\\alpha-1$. Let $\\lambda\\_1 \\geq \\lambda\\_2 \\geq \\cdots \\geq \\lambda\\_d > 0$ denote the eigenvalues of $\\mathbf{H}\\^*$. Consequently, $D\\_\\alpha$ can be written as:\n$$\nD_{\\alpha}= \\left(\\sum_{i=1}^d\\lambda_i^{\\beta}\\right)\\cdot\\left(\\sum_{i=1}^d\\lambda_i^{-\\beta}\\right).\n$$\n\n**Derivation of the Lower Bound.**  Applying the Cauchy-Schwarz inequality yields $D_{\\alpha}\\geq d^2$. Equality holds if and only if $\\beta=0$ (which corresponds to $\\alpha=1/2$), at which point $D_{\\alpha}$ attains its theoretical minimum value of $d^2$.\n\n**Strict Inequality for $\\alpha\\neq 1/2$.** When $\\alpha\\neq 1/2$ (i.e.,$\\beta\\neq 0$), the equality condition for the Cauchy-Schwarz inequality – namely, that all eigenvalues $\\lambda_i$ must be equal – is generally not satisfied (unless the model is isotropic). Consequently, $D_{\\alpha}>d^2$ strictly. Moreover, the magnitude of $D_{\\alpha}$ relative to $d^2$ increases under two conditions: (1) as $|\\beta|$ increases (i.e., as $\\alpha$ deviates further from 1/2), and (2) as the dispersion of the Hessian eigenvalues $\\{\\lambda_i\\}$ increases.\n\n## 2. The scale of $\\epsilon_0$ and the guarantee (regarding Question 2)\nWe thank the reviewer for highlighting this crucial assumption. The quantity $\\epsilon_0$, introduced in the proof of Theorem 3.8, serves to bound the expected distance between $\\mathbf{\\theta}_t$ and $\\mathbf{\\theta}^*$.\n\n**Definition and Guarantee of** \\$\\epsilon\\_0\\$\nThe magnitude of \\$\\epsilon\\_0\\$ reflects the degree to which the parameters \\$\\mathbf{\\theta}\\_t\\$ (for \\$t \\geq T\\$) approach the optimal solution $\\mathbf{\\theta}^*$ after \\$T\\$ iterations. Specifically, we assume that at iteration step \\$t\\$, the expectation satisfies:\n\n$$\n\\mathbb{E}\\left[\\|\\mathbf{\\theta}_t - \\mathbf{\\theta}^*\\|^p\\right] \\leq \\epsilon_0^p.\n$$\n\nThis inequality defines a neighborhood of radius \\$\\epsilon\\_0\\$ around \\$\\boldsymbol{\\theta}^\\*\\$ within which the algorithm iterates. The achievability of such a neighborhood size \\$\\epsilon\\_0\\$ is guaranteed by the algorithm's prior convergence properties.\n\n**Prior Convergence Properties and the Scale of $\\epsilon_0$.** Established analyses of Stochastic Gradient Descent (SGD) for non-convex optimization problems (e.g., [1-3]) demonstrate that, under appropriate conditions, the iterates $\\mathbf{\\theta}_t$ converge globally—either with high probability or in expectation—to a neighborhood containing the global optimum $\\mathbf{\\theta}^*$.\n\n$\\epsilon_0$ can typically be bounded by a polynomial function of the step size $\\eta$. By selecting a sufficiently large total iteration number $T$, we can ensure that $\\epsilon_0$ becomes sufficiently small. This, in turn, guarantees that the higher-order term $\\bar{\\textbf{Err}}$\nin Equation (9) is asymptotically negligible relative to the dominant error term.\n\n## 3. The scale of \\$\\beta\\_1\\$ and \\$\\beta\\_2\\$ in practice and the relation to low precision (regarding Question 3 and Limitations 1)\n\nThank you for pointing out the lack of clarification about the choice of \\$\\beta\\_1\\$ and \\$\\beta\\_2\\$. We explain the necessity of small choices of \\$\\beta\\_1\\$ and \\$\\beta\\_2\\$ in practice. For \\$\\beta\\_1\\$, we first want to clarify that the correction term \\$\\tilde g \\circ \\tilde g\\$ is designed to reduce the instability of training caused by the outliers from zeroth-order oracle with randomness. Specifically, due to the order of preconditioner is \\$-1/2\\$ (\\$\\alpha=1/2\\$), too small value in the diagonal estimated Hessian may cause numerical instability (NaN) in training process. The correction term encourages numerical alignment between gradient magnitude and adaptive curvature scaling like Adam. However, applying such a correction causes bias in Equation (14). By the choice of small \\$\\beta\\_1\\$ to control the bias, we find that such an almost negligible term enhances the robustness of the estimation against outliers and ensure the stability of training. As the results in ablation study, when \\$\\beta\\_1\\$ is set too large (e.g., 1, 1e-2), the optimization diverges and results in NaNs, because the proportion of correction term is too large to introduce non-negligible bias. When \\$\\beta\\_1\\$ is too small (e.g., 0 or approaching 0), the correction term fails to take effect, which may lead to numerical instability during training and result in NaNs. Only in a proper range (around \\$1e\\text{-}8\\$ to \\$1e\\text{-}10\\$) does the algorithm yield reasonable performance.\n\nFor \\$\\beta\\_2\\$, it is originated from the large variance of estimated Hessian by zeroth-order oracle. We propose a non-strict analysis of variance to clarify it further as below.\nFrom an intuitive (though informal) perspective, consider the update rule:\n\\$\\Sigma\\_t = (1 - \\beta\\_2)\\Sigma\\_{t-1} + \\beta\\_2 |\\widehat{\\Sigma}\\_t|\\$,\nwhere \\$\\widehat{\\Sigma}\\_t\\$ denotes the current estimate of the (diagonal) Hessian, and the initialization \\$\\Sigma\\_0 = I\\$. Since the iterative update forms the moving average, \\$\\beta\\_2\\$ effectively controls the sensitivity to new information and hence the variance of the sequence \\${\\Sigma\\_t}\\$. Specifically, due to the identity initialization, the influence of \\$\\Sigma\\_0 = I\\$ remains dominant unless \\$\\beta\\_2\\$ is set large. In particular, when \\$\\beta\\_2\\$ is small, the update rule behaves approximately as:\n\n$$\n\\Sigma_t \\approx (1 - \\beta_2)^t I + \\beta_2 \\sum_{k=0}^{t-1} (1 - \\beta_2)^k |\\widehat{\\Sigma}_{t-k}|,\n$$\n\nwhich can be interpreted as a weighted combination of the initial value \\$I\\$ and a series of estimated observations.\nWe consider the variance of \\$\\Sigma\\_t\\$ above by the analysis on the second term (though not a completely strict analysis, as some correlations are ignored, we hope to provide some intuition here). The expectation of each \\$\\widehat{\\Sigma}\\_{t-k}\\$ can be directly obtained as:\n\n$$\n\\mathbb{E}\\left[\\underbrace{\\frac{1}{2}u^\\top \\widehat\\Sigma^{-\\frac{1}{2}} \\mathbf{H} \\widehat\\Sigma^{-\\frac{1}{2}} u}_{\\mathcal{I}} \\cdot \\widehat\\Sigma\\left(\\text{diag}(uu^\\top) - I\\right)\\right] = \\text{diag}(\\mathbf{H}).\n$$\n\nThus, we can obtain the variance of each coordinate \\$i\\$ of \\$\\widehat \\Sigma\\$ as:\n\n$$\n\\text{Var}[\\hat h_{ii}] \\approx \\widehat\\Sigma_{ii}^2 \\mathbb{E}\\left[\\mathcal{I}^2 (u_i^2 -1)^2 \\right] - H_{ii}^2 = \\frac{\\widehat\\Sigma_{ii}^2}{4} \\sum_{j,k,s,t} A_{jk} A_{st} \\mathbb{E}[u_ju_ku_su_t(u_i^2-1)^2] - H_{ii}^2,\n$$ \n\n\nwhere \\$\\hat h = \\mathcal{I}{\\widehat\\Sigma}\\left(\\text{diag}(uu^\\top) - I\\right)\\$, \\$A = \\widehat\\Sigma^{-1/2}H\\widehat\\Sigma^{-1/2}\\$.\nNoticing that when \\$u \\sim \\mathcal{N}(0,1)\\$, the coupling term \\$\\mathbb{E}\\[u\\_ju\\_ku\\_su\\_t(u\\_i^2-1)^2]\\$ is not 0 with special choice of \\$j,k,s,t\\$. For example, only considering the terms where \\$j=s\\$ and \\$k=t\\$, and denoting for any \\$k \\leq t\\$, \\$\\max\\_i (\\widehat\\Sigma\\_k)\\_{ii} \\leq B\\$, we have:\n\n$$\n\\text{Var}[\\widehat\\Sigma_k] \\approx \\mathcal{O}(d^2B^2).\n$$\n\n**It means that some values in estimated Hessian is numerically too large to introduce the risk of obtaining outliers in training.**\nTo solve this, considering:\n\n$$\n\\beta_2 \\sum_{k=0}^{t-1} (1 - \\beta_2)^k = 1 - (1 - \\beta_2)^t,\n$$\n\na small \\$\\beta\\_2\\$ yields the controlled variance of the second term to ensure a lower-variance, more stable update in the training process. Meanwhile, small \\$\\beta\\_2\\$ still ensures that the Hessian estimates are valid from a global perspective, because when \\$t \\to \\infty\\$, the first term \\$(1 - \\beta\\_2)^t \\to 0\\$ and the second term \\$\\beta\\_2 \\sum\\_{k=0}^{t-1} (1 - \\beta\\_2)^k \\to 1\\$.\nSimilar hyper-parameter setting is used in another zeroth-order optimizers for fine-tuning like \\[4]. Our experimental results also demonstrate that under the same parameter configurations, PaZO improves the performance of fine-tuned model across tasks. We will mention the sensitivity and choice of \\$\\beta\\_1\\$ and \\$\\beta\\_2\\$ in the main text of camera-ready version.\n\n---\n\nMoreover, your concerns about how small hyperparameters are combined with low precision training like bfloat16 are extremely important. The experiment setting in zeroth-order optimization is a little different while low-precision formats like bfloat16 are widely adopted in first-order optimization to reduce memory usage. **In both the pioneering work of applying zeroth-order optimization to large language model finetuning \\[5], as well as subsequent follow-up studies such as \\[4], experiments are by default conducted in fp32 without bfloat16 to ensure numerical stability and reliable convergence.** We follow the default experimental setting for fair comparison. Specifically, zeroth-order methods already lead to a significant reduction in memory usage due to its bp free—often far more than what bfloat16 achieves in standard first-order methods. In a sense, zeroth-order optimization can be viewed as an aggressive strategy to trade off between precision and memory efficiency at the algorithmic level. When applying bfloat16 in the context of zeroth-order optimization, the choice of hyperparameters may need to be adjusted accordingly to prevent loss of numerical precision. We believe this is an interesting direction for future research, but it is out of the scope of this paper.\n\n\n\n\n\n\n\nDue to space limitations, I will immediately post the responses to the remaining questions starting from the next stage. Thank you for your insightful comments again."}, {"review_id": "jT4B6jeuYZ", "reviewer": "Reviewer_HFxg", "summary": "This paper investigates the role of preconditioning in zeroth-order optimization for memory-efficient fine-tuning of large language models and introduces PaZO. The authors define a general PSPSA estimator that perturbs parameters with preconditioner $H^{-\\alpha}$ and prove that only choosing $\\alpha = 1/2$ yields the optimal convergence rate. The authors then proposes a practical algorithm named PaZO that utilizes diagonal Hessian estimator via three forward-pass perturbations. Empirical evaluation across multiple downstream tasks and models demostrate the effectiveness of the proposed algorithm.", "questions": "1. While estimating the diagonal Hessian matrix, 1) why do we need to incorporate $diag( \\tilde{g} \\circ  \\tilde{g})$ as a correction item to integrate local first-order estimated information into $\\Sigma_{t-1}$ through moving average mechanism? 2) why $\\tilde{\\Sigma}$ is computed through $((1-\\beta_1) \\Sigma_{t-1}^2 + \\beta_1 \\cdot diag( \\tilde{g} \\circ  \\tilde{g}))^{1/2}$, not $(1-\\beta_1) \\Sigma_{t-1} + \\beta_1 diag( \\tilde{g} \\circ  \\tilde{g})$. 3) In theory, such correction is not applied in estimating the term $\\mathcal{I}$ while computing $\\Sigma_t$, which makes Equation. (14) no longer an unbiased estimation to the diagonal Hessian. 4) In practice, the authors conducted an ablation experiment on studying the influence of parameter choice of $\\beta_1$, why too small choice of $\\beta_1$ (including 0) result  in NaN. From my understanding, setting $\\beta_1$ to be zero will make PaZO similar as that in HiZOO. In this ablation study, I can't figure out the real effect of incorporating the estimated gradient as a correction.\n\n2. Apart from the correction term, another difference between PaZO and HiZOO is the periodical reset mechanism for diagonal Hessian estimation. However, there is no ablation study design for this mechanism. Why this this step is necessary?", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The authors give the answer to an important question regarding the necessity of preconditioning in ZO and identify the optimal order in preconditioner.\n\n2. The three-point perturbation scheme combined with gradient-based correction and periodic reset is a novel, lightweight way to incorporate second-order information without prohibitive memory.\n\n3. Extensive empirical evaluation on both masked (RoBERTa-large) and generative (OPT-1.3B) models across a diverse suite of NLP tasks, demonstrating robustness of PaZO.\n\nWeakness:\n1. There are several formulation mistakes in estimating the diagonal Hessian. The RHS of Equation (11) should be $diag(H)$. The LHS of Equation (13) should be $\\ell_{+} + \\ell_{-} - 2\\ell$.\n\n2. Some hyperparameter choices (e.g., reset period $T_0$ schedule) are introduced without intuitive justification.", "was_revised": true, "final_justification": "I have no additional questions and thank you for the detailed response, which has resolved my previous concerns.", "rebuttal": "# Response to Reviewer HFxg\n\nWe sincerely thank the reviewer HFxg for their thorough insightful feedback and constructive suggestions. We deeply appreciate the effort you dedicated to assessing our work.  We address the main concerns raised by the reviewer HFxg point by point.\n\n## 1. Correct some typos (regarding Weakness 1 and Question 1)\nWe thank the reviewer for pointing out the typos. We have carefully re-checked all symbols, equations, and tables throughout the paper. Below, we list all the corrections we identified and will incorporate them in the camera-ready version:\n| Location | Original Text                        | Corrected Text                                                              |\n| -------- | ------------------------------------ | ---------------------------------------------------------------------------------- | \n| Equation (11) | $\\mathbb{E}\\left[\\underbrace{\\frac{1}{2}u^\\top \\mathbf{\\Sigma}^{-\\frac{1}{2}} \\mathbf{H} \\mathbf{\\Sigma}^{-\\frac{1}{2}} u}_{\\mathcal{I}} \\cdot  \\mathbf{\\Sigma}\\left(diag(uu^\\top)  - \\mathbf{I}\\right)\\right] = \\mathbf{H}$ | $\\mathbb{E}\\left[\\underbrace{\\frac{1}{2}u^\\top \\mathbf{\\Sigma}^{-\\frac{1}{2}} \\mathbf{H} \\mathbf{\\Sigma}^{-\\frac{1}{2}} u}_{\\mathcal{I}} \\cdot  \\mathbf{\\Sigma}\\left(diag(uu^\\top)  - \\mathbf{I}\\right)\\right] = diag(\\mathbf{H})$ |\n| Equation (13) | $\\frac{\\ell_+ +\\ell_- -\\ell}{\\mu^2} = \\mathcal{I} + \\mathcal{O}(\\mu)$ | $\\frac{\\ell_+ +\\ell_- -2\\ell}{\\mu^2} = \\mathcal{I} + \\mathcal{O}(\\mu)$ |\n| \"Adding information from ZO gardient\" in Algorithm 1 and below line 223 | $\\mathbf{\\tilde\\Sigma} =\\left( (1-\\beta_1)\\mathbf{\\Sigma}_{t-1}^2 + \\beta_1 \\cdot diag(\\tilde{g} \\circ \\tilde{g}) \\right)^{1/2}$ | $\\mathbf{\\tilde\\Sigma} =\\left( (1-\\beta_1)\\mathbf{\\Sigma}_{t-1}^2 + \\beta_1 \\cdot diag^2(\\tilde{g} \\circ \\tilde{g}) \\right)^{1/2}$ |\n| the first row, second column in Table 6 | 0 | 1|\n\n\nWe acknowledge that some of these typos may have caused confusion and may be directly responsible for the series of concerns you raised in **Question 1**. We sincerely apologize for this and now proceed to clarify your questions in detail. Regrettably, the rebuttal process does not allow us to submit a revised manuscript. Nevertheless, we will make sure to fix all the aforementioned issues and include a detailed discussion in response to your concerns in the final camera-ready version.\n\n## 2. The necessity of the correction term in estimating the diagonal Hessian (regarding Question 1, (1)) \n\nIn summary, this correction term can reduce the instability of training caused by the outliers from zeroth-order oracle with randomness. Specifically, due to the order of preconditioner is $-1/2$ ($\\alpha=1/2$), too small value in the diagonal estimated Hessian may cause numerical instability (NaN) in training process. The correction term encourages numerical alignment between gradient magnitude and adaptive curvature scaling, similar in spirit to adaptive methods like Adam [1] and Adafactor [2]. To illustrate the issue more intuitively, we offer some insights through a non-strict analysis below.\n\n\nIn practice, we first obtain $\\ell_+$, $\\ell_-$ and $\\ell$ through three forward pass. We obtain three numerical finite values and then $\\mathcal{I}$, which, although dependent on $u$, are treated as a fixed scalar in our experiments. Thus if we do not have the correction term, we have $$\\mathbb{E}\\left[\\mathbf{\\Sigma}\\left(diag(uu^\\top)  - \\mathbf{I}\\right)\\right] \\approx 0,$$\n\nwhich means that in practice, we may obtain some extremely small values close to zero, causing the numerical outliers (NaN) considering the order $-1/2$. When adding the correction term, similarly ignoring the scaler, we have $$\\mathbb{E}\\left[\\mathbf{\\Sigma}\\left(\\mathbf{I}+diag(uu^\\top)\\right)\\left(diag(uu^\\top)  - \\mathbf{I}\\right)\\right] \\approx 2\\mathbf{\\Sigma},$$\n\nwhich means that $\\Sigma_{t}$ is numerical remains numerically consistent with $\\Sigma_{t-1}$. Thus we obtain a more stable update of $\\Sigma$, which helps ensure the stability of training in our experiments. Moreover, we control the scale of correction term via $\\beta_1$, which means that we can achieve numerical stability with only a small-scale correction term.\n\n\n## 3. Why we compute $\\mathbf{\\tilde\\Sigma} =\\left( (1-\\beta_1)\\mathbf{\\Sigma}_{t-1}^2 + \\beta_1 \\cdot diag^2(\\tilde{g} \\circ \\tilde{g}) \\right)^{1/2}$ (regarding Question 1, (2) and (3))\n\nWe sincerely apologize for the typo that we forgot the order of $diag$. As you mentioned, it is common to use linear-weighted average form $\\mathbf{\\tilde\\Sigma} = (1-\\beta_1)\\mathbf{\\Sigma}_{t-1} + \\beta_1 \\cdot diag(\\tilde{g} \\circ \\tilde{g}) $. However, in zeroth-order optimization, we observe that root-sum-square average $\\sqrt{A^2+B^2}$ performs better compared with $A+B$. First, $\\sqrt{A^2+B^2}$ is bounded by $A+B$ as $\\frac{A+B}{\\sqrt{2}} \\leq \\sqrt{A^2+B^2} \\leq A+B$, which means that the two are close in order of magnitude. Second,  the square-root form acts as a soft maximum. When $A$ is close to $B$, $\\sqrt{A^2+B^2}$ are within the same order of magnitude, differing only by a constant factor. When $A \\gg B$ or $B \\gg A$, $\\sqrt{A^2 + B^2}$ behaves like a softmax operator, approximating the larger value.\n\n\n\n As you mentioned, applying such a correction causes bias in Equation (14). However, in practice, by the softmax operator $\\sqrt{A^2+B^2}$ and the choice of $\\beta_1$, we find that the deviation from unbiasedness is negligible empirically. On the contrary, such an almost negligible term enhances the robustness of the estimation against outliers, which is critical for the stability of zeroth-order optimization.\nWe believe that for theory-inspired algorithms, making empirically motivated adjustments when applying them to practical tasks is both reasonable and necessary, so we named the algorithm \"practical form\" in Algorithm 1.\n\n## 4. The choice of $\\beta_1$ in the ablation study (regarding Question 1, (4))\n\nAt first we clarify that even though setting $\\beta_1 =0$, PaZO is **not similar** to HiZOO due to the different order of estimated diagonal Hessian (different setting of $\\alpha$). One of the most important contributions of this work is to demonstrate that the ideal choice of $\\alpha$ is $-1/2$ instead of $0$ for MeZO and $1/2$ for HiZOO, no matter what $\\beta_1$ we select. After correcting the typo in Table 6, we state the results of ablation study as below for OPT-1.3B on SST2.\n\n| $\\beta_1$ | 1 | 1e-2 |1e-4 |1e-6 | 1e-8 |1e-10 | 0 |\n| -- | -- | -- | -- | -- | -- | -- | -- |\n| setting $\\beta_2$ = 1e-8 | NaN | NaN | NaN| NaN | 89.0 | 88.9 | NaN |\n\nThe results show that when $\\beta_1$ is set too large (e.g., 1, 1e-2), the optimization diverges and results in NaNs, because the proportion of correction term is too large to introduce non-negligible bias. When $\\beta_1$ is too small (e.g., 0 or approaching 0), the correction term fails to take effect, which may lead to numerical instability during training and result in NaNs. Only in a proper range (around $1e\\text{-}8$ to $1e\\text{-}10$) does the algorithm yield reasonable performance. This behavior confirms our discussion earlier about the necessity of correction term, as we state in \"2. The necessity of correction term\". The use of a carefully chosen $\\beta_1$ serves as a regularization mechanism, stabilizing the training process.\n\n## 5. Ablation study about $T_0$ (regarding Weakness 2 and Question 2)\n\nWe briefly explain why we reset the $\\Sigma$ frquently from line 228 to line 230 in the main body of our paper.  This idea has been considered in periodic error feedback resetting used in optimization with communication compression [4].\n\nAs a supplement, we an ablation study on the effect of the reset period \n$T_0$.\nIn this experiment, we fine-tune the OPT-1.3B model and evaluate its performance on the SST2 dataset, while varying the value $T_0 \\in\\{64,128,256, 512 \\} $ and $\\infty$ (without resetting). The results are summarized in the table below:\n\n| $T_0$| 64| 128 |256 | 512 | $\\infty$ |\n| -- | -- |--| -- | -- | -- | \n|SST2  |88.5|88.8 |89.0 | 88.3| 87.7|\n\n\nThe reason behind this design and observation is as follows. As the number of iterations increases, the error in the Hessian estimation obtained from the zeroth-order oracle tends to accumulate over steps. This accumulated error may grow with the number of iterations. Therefore, when no resetting mechanism is used (as in the case of $\\infty$ in the table above), the performance drops. On the other hand,  considering that $\\Sigma$ is initialized as the identity matrix $I$, there exists a gap between $I$ and the Hessian $H^*$. When the resetting frequency is too small (e.g., 128), the information accumulated in $\\Sigma_t$ is insufficient to effectively bridge this gap. The hyperparameter $T_0$ plays the role of a trade-off between error accumulation and Hessian estimation accuracy. Our experimental results also indicate that the model achieves the best performance when $T_0$ falls within a certain range. We will discuss more about the ablation study on $T_0$ in the camera-ready version.\n\nWe sincerely thank the reviewer HFxg for the constructive and insightful feedback. We greatly appreciate the opportunity to improve our work through this review process, and we would be truly grateful if the reviewer HFxg could consider a positive adjustment to the scores.\n\n\n## Reference\n[1] Kingma D P, Ba J. Adam: A method for stochastic optimization[J]. arXiv preprint arXiv:1412.6980, 2014.\n\n[2] Shazeer N, Stern M. Adafactor: Adaptive learning rates with sublinear memory cost[C]//International Conference on Machine Learning. PMLR, 2018: 4596-4604.\n\n[3] Chen X, Liu S, Xu K, et al. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization[J]. Advances in neural information processing systems, 2019, 32.\n\n[4] Xie X, Lin Z, Toh K C, et al. Loco: Low-bit communication adaptor for large-scale model training[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025."}]

Author rebuttal:

Meta-review: This paper proposes PaZO, a preconditioned accelerated zeroth-order optimization method for fine-tuning LLMs. The work contributes both theoretical insights and a practical algorithm that incorporates diagonal Hessian estimates and moving averages for stability. Experiments demonstrate advantages over zeroth-order baselines like MeZO and HiZOO.

During the discussion, one reviewer stressed that PaZO’s practical design closely resembles HiZOO, raising concerns about algorithmic novelty. Additional issues included formulaic errors, hyperparameter sensitivity, and limited experimental breadth -- improvements are most evident on OPT, less so on RoBERTa, with no evaluation on newer LLMs (e.g., LLaMA3). While the authors addressed efficiency concerns in rebuttal, complete evidence is needed for the revised version. 

Despite reservations about novelty and presentation, the paper offers solid theoretical contributions. Given that ZO fine-tuning relies only on model queries and represents a promising direction, and with overall ratings turning positive after rebuttal, the AC believes the work will interest both optimization and LLM communities. The AC strongly encourages the authors to incorporate the planned clarifications and additional results in the revised version.
Decision: Accept (poster)