Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures
Authors: Yiming Chen
Yuan Zhang
Liyuan Cao
Kun Yuan
Zaiwen Wen
Venue: ICLR 2025 Poster (2025)
Keywords: zeroth-order optimization
large language model fine-tuning
stochastic optimization
Primary area: optimization
TL;DR: We propose a new zeroth-order algorithm with low-rank gradient estimation structures, enhancing the fine-tuning of large language models.

Abstract: Parameter-efficient fine-tuning (PEFT) significantly reduces memory costs when adapting large language models (LLMs) for downstream applications. However, traditional first-order (FO) fine-tuning algorithms incur substantial memory overhead due to the need to store activation values for back-propagation during gradient computation, particularly in long-context fine-tuning tasks. Zeroth-order (ZO) algorithms offer a promising alternative by approximating gradients using finite differences of function values, thus eliminating the need for activation storage. Nevertheless, existing ZO methods struggle to capture the low-rank gradient structure common in LLM fine-tuning, leading to suboptimal performance. This paper proposes a low-rank ZO gradient estimator and introduces a novel **lo**w-rank **ZO** algorithm (LOZO) that effectively captures this structure in LLMs. We provide convergence guarantees for LOZO by framing it as a subspace optimization method. Additionally, its low-rank nature enables LOZO to integrate with momentum techniques while incurring negligible extra memory costs. Extensive experiments across various model sizes and downstream tasks demonstrate that LOZO and its momentum-based variant outperform existing ZO methods and closely approach the performance of FO algorithms.

Published as a conference paper at ICLR 2025
ENHANCING ZEROTH-ORDER FINE-TUNING FOR LAN- GUAGE MODELS WITH LOW-RANK STRUCTURES
Yiming Chen Yuan Zhang Liyuan Cao Kun Yuan 3& Zaiwen Wen"
Pekkin University, Beijing, China; *Nanjing University, Nanjing, China
$ AI for Science Institute, Beijing, China
Equal contributions *Corresponding author: kunyuan@pku. edu.
ABSTRACT
Parameter-effiiient fine-tuning (PEFT) significantly reduces memory costs when adapting large language models (LLMs) for downstream applications. However, traditional first-order (FO) fine-tuning algorithms incur substantial memory over- head due to the need to store activation values for back-propagation during gra- dient computation, particularly in long-context fine-tuning tasks. Zeroth-order (ZO) algorithms offer promising alternative by approximating gradients using finite differences of function values, thus eliminating the need for activation stor- age. Nevertheless, existing ZO methods struggle to capture the low-rank gradient structure common in L.M fine-tuning, leading to suboptimal performance. This paper proposes low-rank ZO gradient estimator and introduces novel low- rank Zo algorithm (LOZO) that effectively captures this structure in LLMs. We provide convergence guarantees for LOZO by framing tion method. Additionally, its low-rank nature enables LOZO to integrate with momentum techniques while incurring negligible extra memory costs. Exten- sive experiments across various model sizes and downstream tasks demonstrate that LO7O and its momentum-ben variant outperform existing 70 methods and closely approach the performance of FO algorithms.
subspace optimiza-
INTRODUCTION
Large language models (LL.Ms) have demonstrated exceptional performance across a wide range of domains (Solaiman et al. 2019 Brown 2020 Achiam et al. (023). To adapt LLMS for specific downstream applications, fine-tuning pre-trained models has become the de facto approach (Guru- rangan et al. 2020; (anh al.
2021). Parameter-efficient fine-tuning (PEFT) methods, such those proposed by (Hu et al. 2021 Lester et al. 2021), aim to reduce memory consumption by freezing most are-trained weights and updating only subset of parameters. However, even with these ap- proaches, first-order (FO) optimization algorithms like stochastic gradient descent (SGD) (Amaril 1993] and Adam (Kingmal 2014) still encounter substantial memory overhead due the need to store activation values for back pooc-proaagation during gradient computation. This issue becomes even more pronounced in long-context settings where activations dominate memory usage.
To enhance memory efficiency, a promising alternative is the use of zeroth-order (ZO) algorithms (Spall 1992). Unlike FO methods, ZO algorithms do not require direct gradient computation. In- stead, they approximate gradients using finite differences of function values, eliminating the need for back pack-propagation and the storage of activation values, which leads substantial memory savings. 70 algorithms have been extensively studied over the past few decades (Duchi et al. 2015 Nesterov & Spokoiny| 2017]] Berahas et al. 2022) and were recently applied to fine-tuning L.MMs for the first time in (Malladi et al. 2023), where the authors adapt the classical ZO stochastic gradient descent (ZO-SGD) algorithm Ghadimmi & Lan 2013) to a memory-efficient variant known as the McZO algorithm. As demonstrated (Malladi et al.) 2023), the MeZO algorithm can reduce memory costs to quarter of those incurred by standard SGD.
However, ZO algorithms still face several challenges when fine-tuning LLMs. A primary concern is the substantial discrepancy in the matrix rank between estimated ZO gradients and true FO gradients. Extensive literature reports that FO gradients generated during backpropagation in L.M fine-tuning

---

Published as a conference paper at ICLR 2025
exhibit a low-rank structure (Malladi et al.) 2023 Zhao et al. 2024a] Hao et al. 2024). In contrast, the ZO gradients in MeZO are derived from a perturbation matrix sampled from a Gaussian dis- result in a performance gap between ZO
tribution, which is nearly fill-rank. This discrepancy and FO algorithms. Another challenge is constructing momentum algorithms using 70 gradients. Since 70 gradients are typically full-rank, the resulting momentum variable also becomes full-rank, leading to significant overhead in storing the momentum (Malladi et al. 2023) Zhhang et al.) [024]] Chen et al. 2019). This overhead offsets the memory efficiency gained through ZO algorithms.
It is evident that the above challenges arise from the full-rank structure of ZO gradient estimates. To address these issues, this work presents novel strategy for the gradient approximation based on finite differences of function values. Specifically, we propose a low-rank matrix-wise gradient estimator (LGEE) scheme and a new variant of the ZO-SGD algorithm that capitalizes on this ap- proach. This ensures that our 70 gradient estimator consistently retains low-rank structure, fluc- tuating within a low-dimensional subspace across iterations. As result, our estimator more aceu- rately approximates the low-rank FO gradient employed in LLM fine-tuning, leading to improved empirical performance. Moreover, the low-rank ZO gradient facilitates the use of low-rank mo- mentum variables, significantly reducing memory usage compared to conventional ZO momentum algorithms. Our contributions can be summarized as follows:
We propose a low-rank ZO gradient estimator. Unlike traditional coordinate wise or ran- domized approaches, our approach derives the 70 gradient using low-rank perturbation matrix, ensuring that the approximated gradient retains a low-rank structure. Our derived 70 gradient closely resembles the FO gradient structure in L.LM fine-tuning.
We develop two novel low-rank ZO algorithms for LLM fine-tuning: Low-rank ZO-SGD (LOZO) and its momentum- based variant LOZO-M. A critical component in these algo- rithms is the lazy sampling strategy, where the low-rank random perturbation matrix is sampled over multiple steps, rather than at each iteration. This allows the ZO algorithm to sufficiently explore low-rank subspace over longer period, preventing per-iteration abrupt changes to model parameters and enhancing fine-tuning performance. Moreover, LOZO-M incurs negligible additional memory overhead for storing momentum.
We establish convergence guarantees for LOZO under common assumptions in stochas- tic ZO optimization. A key insight from our convergence analysis is that LOZO can be viewed as a subspace optimization method employing a standard ZO gradient estimator. This method iteratively solve the fine-tuning problem by alternating between different low- rank subspaces progressively improve the overall solution.
We conduct extensive experiments across various model scales (ranging from 350M to 66B) and downstream tasks, including classification, multiple-choice, and generation. LOZO and LOZO-M outperform zero-shot, ICL, MeZO, and MeZO-LoRA in most tasks, while maintaining the same storage overhead as MeZO.
1.1 RELATED WORK
Zeroth-order optimization. Zeroth-order (ZO) optimization typically employs finite difference of function values to approximate gradients. Since it does not require gradient computation, ZO methods have been widely applied in various machine learning (ML) domains, including adversarial attack and defense (Ilyas et al. 2018: Zhao et 2019 Tu et al.) 2019) Zhang et al. (022b), model-
agnostic contrastive explanations (Dhurandhar et al.) 2019), and AutoML (Wang al. (022). ZO
algorithms have been derived from FO methods in numerous studies, such as ZO-SGD Ghadimi & 2019a). Ad-m (Chen al. 2019). and ZO-SVRG (Liu et al. 2018 al. 2019), J among others ii et al. 6216 L al. 2020). Although straightforward, these adaptations often exhibit high variance and slow convergence because of the dimensionality
Lan 2013 Liu et al.
the model. To
address this, techniques such sparse gradient exploitation (Balasubramanian & Ghadimil 2018
Cai et al., 2022) and feature reuse in deep neural networks (Chen et al. (2023) have been proposed, highlighting the potential of ZO optimization in large-scale ML problems.
Memory-efficient fine-tuning. A range of memory-efficient methods have been proposed to en- hance the accessibility of LLM fine-tuning. For instance, LoRA (Hu et al. 2021) introduces low- rank perturbations to pre-trained model weights, utilizing only a few trainable parameters while achieving performance comparable full fine-tuning. Other approaches (Zhao et al. 2024a Hao
2

---

Published as a conference paper at ICLR 2025
et al. 2024 Muhamed et al. 2024) compress gradients by projecting them into subspaces, thereby reducing the memory required for storing optimizer states. In contrast to first-order (FO) algorithms, zeroth-order (ZO) algorithms (Malladi al. (023) have gained considerable attention for their ef- ficiency, as they avoid storing activation values. To accelerate 70 fine-tuning, Gautam et al. (2024) introduced ZO-SVRG for L.M fine-tuning, while Zhhao al. (2024b) employed 70 methods to approximate a natural gradient algorithm. Although these approaches improve convergence, they often incur increased memory costs. To address this trade-off, [Lu et al. (2024) proposed incorpo- rating sparse mask into ZO iterations to reduce dimensionality and expedite fine-tuning, albeit at the cost of some aceuracy. [i et al. (2024) explored hybrid approach, combining FO gradients with ZO estimators in each iteration. Complementing these efforts, Zhang et al. (2024) provide comprehensive benchmark of various ZO-based algorithms for LLM fine-tuning.
PRELIMINARIES
This section provides an overview of ZO optimization and the commonly used ZO gradient estima- tors. We also introduce the McZO algorithm (Malladi et al. 2023) used in LLM fine-tuning.
2.1 ZEROTH-ORDER (ZO) OPTIMIZATION
We consider the following optimization problem:
min f(X) (F): X
(1)
where X represents the set of trainable parameters with dimension For example, in the LLM fine-tuning process, we can express X [Xe]f= where Xe _ denotes the f-th weight matrix and C is the number of layers. The function F( is the loss function that depends on random variable ç.
The ZO method estimates gradients using only function evaluations, without requiring direct access gradient information. Two commonly employed gradient estimation schemes are the determin- istic Coordinate-wise Gradient Estimation (CGE) (Lian et al.) 2016 Chen et al. 2023) and the
Randomized vector-wise Gradient Estimation (RGE) (Spall 1992; Duchi et al. 2015 Nesterov &
Spokoiny 2017). These are formally defined as:
(CGE) VF(X;E) = F(X + EE F(X -EEiEE E.
(2)
2e
1=1
(RGE) FF(X;E) : F(X + 2Z - F(X - =ZiE) Z.
(3)
2e
The scalar denotes the perturbation magnitude, which influences the accuracy of the gradient approximation. Both E, and Z are of the same dimensions as X. The quantity E; is a basis vector/matrix with its i-th element set one and other elements set to zero, whereas the elements of Z are randomly generated, typically sampled independently from standard normal distribution. extension the RGE method is the RGRGE approach. Here, the RGE computed times independently, and the final gradient estimate is obtained by averaging these estimations.
Utilizing these gradient estimators, the ZO-SGD method is implemented through the following iter- ative scheme:
++1 X aVF(X':e))
(4)
where denotes the step size, also termed the learning rate, and V represents the gradient esti- mated with ZO information.
2.2 SEMORY-EFFICIER ZO-SGD (MEZO)
The standard implementation of ZO-SGD incurs substantial memory costs. For example, when con- structing the gradient estimator using the RGE scheme, the traditional ZO-SGD method requires memory store the perturbation matrix Z. To mitigate this memory overhead, the McZO method (Malladi et al. 2023) was introduced as a memory- memory-efficient variant of ZO-SGD. Unlike the standard approach, MeZ0 avoids storing the entire perturbation matrix Z. Instead, the algorithm performs
3

---

Published as a conference paper at ICLR 2025
Singular Value Q Mabriy Graident for Layer
Singular Value V Mstrix Gra over Stop
10a
Step
Layer
Log Singuiar Value
Step 50
Log Singuiar Value
Layer
Step 100
Layer 8
10-1
Stop 200
10
Layer 12
30
Step 210
100
Layer 16
10-
10-1
110-1
10:5
60
80
60
80
1.00
Index
Index
Figure 1: The low-rank structure of the gradients encountered in the fine-tuning of LLMs, demonstrated using the OPT-1.3B model with the COPA dataset, where the gradient matrices have dimensions of 2048 x 2048. For both figures, we report only the 100 largest singular values. Left: Singular value distribution of the gradient of the attention Q matrix layer across different training steps. Right: Singular value distribution of the gradient of the attention matrix across different layers at training step 50.
both the perturbation and ZO-SGD updates in place and employs technique of saving the ran- dom seed used to generate Z, allowing it to be regenerated when necessary. While this introduces additional computational costs, significantly reduces memory usage.
3 LOW-RANK ZEROTH-ORDER GRADIENT ESTIMATOR
LLM gradients exhibit low-rank structures. The low-rank structure of neural networks has been
extensively investigated in previous literature (Li et al. 2018 Larsen al. 202T). These studies suggest that loss landscapes exist within an intrinsic dimension, implying that model weights can be optimized within low-rank subspace. Furthermore, additional researches (Sagun al.] 2017 Gur- Ari et al. 2018) have demonstrated that stochastic gradients dynamically converge remarkably small subspace, especially when fine-tuning LLMs (Zhang et al. 2023). Recent work (Zhao et al, 2024a) also provides theoretical evidence that the gradient matrix becomes low-rank during LLM training and fine-tuning. Figure [
investigates the rank of the gradient matrix during LLM fine- tuning. The left plot demonstrates that the gradient matrix remains low-rank across training steps, while the right plot shows that this low-rank property persists across different layers.
Existing ZO methods are ineffective at capturing low-rank structures. Commonly used ZO gradient estimators like CGE and RGE cannot capture the low-rank structure of the true gradients during LLM fine-tuning. The RGE scheme produces estimated gradient that is essentially projection of the true gradient onto standard normal random matrix Z, which is almost always full rank. On the other hand, although the CGE scheme can approximate the full true gradient, requires evaluating the loss function d times per iteration, making it impractical for large-scale problems. As a result, existing ZO algorithms (Ghadimi & Lan, 2013; Liu et al. 2019a Chen et al. 2019 Liu
et al. 2018 Ji et al., 2019 Balasubramanian & Ghadimi 2018 Cai et al. [022] Chen et al. 2023
Malladi et al. 2023 Zhang et al. al. 2024)) which rely on either CGE or RGE, fail to effectively account for the low-rank structure inherent in the gradient matrix during LLM fine-tuning.
Low-rank Zo gradient estimator (LGE). To bridge this gap, we propose a matrix-wise Z0 gra- dient estimator, LGE, that preserves the low-rank structure in gradients. In LLM fine-tuning, let X= {Xe]e_ represent the model's weights, where X₁ E Xm is the weight matrix the l-th layer. We sample matrices, U₃ TM and V E R x from standard normal distributions, where re < min (mi, ne). The LGE for partial gradient of the f-th weight matrix defined as
Fx = F((X, + eU.V Jf (iE) - F(IX, - eU.V? /f (
(UVV /re).
(5)
26
The scaling factor 1 1/r: is introduced to ensure that LGE is an unbiased estimator the true gradient
0 (see Proposition A.I. Defining U (Un) V (Vile r {re) 1r and
F((:; 5)= == (vx, F(X; T we express X +UVT = (X, +u. )_ and UVT /r: CtVV/rreffe Using these notations, LGE can be written into more compact form:
F(X + : F(X :UVT.)
(LGE)
(F(X:E)=
(UVT /r).
(6)
2e
4

---

Published as a conference paper at ICLR 2025
Using the definition in 5 we observe that the gradient matrix Fx,F(X; has a rank of at most Te, effectively capturing the low-rank structure of the FO gradient in LLM fine-tuning.
LOW-RANK ZEROTH-ORDER SGD
This section introduces LOZO, novel low-rank Zo algorithm for LLM fine-tuning. LOZO can be interpreted as a ZO subspace optimization method that leverages a standard gradient estimator. Based on this key insight, we establish convergence guarantees for LOZO.
4.1 ALGORITHM DEVELOPMENT
Vanilla recursion. Following the LGE definition (). we introduce the LGE operator
LGE(X, U, v,,,,,),,,....... F(X + eUV"; :E) F(X <UVT; : (UV*/r).
To solve problem 1. the vanilla recursion with the LGE scheme is as follows. For any / 2 0, X X avF(X'; where VF(X': = LGE(X', U², "V,,V',, rr),)
(8)
In practice, we only need to store Ug and Vi for each layer f, and we apply the perturbation (6) and the update (8) layer by layer, eliminating the need to retain the full gradient estimator U. Since re < min(m, ). the additional memory required for storing Uz and Vj is negligible. Moreover, memory costs can be further reduced using the random seed technique (Malladi et 2023). Instead of storing Ue and Vi directly, only the random seeds sy and sy used to generate them are saved. Whenever Ug and Vy are needed, the seeds s and sy are used to regenerate these matrices, thereby eliminating the need for their storage. While this approach reduces memory usage, it introduces additional poatting-pint operations (flops) due to the regeneration process.
Lazy sampling strategy. the main recursion 8), the variable X is updated within the subspace spanned by U and V each iteration t. However. if U and V are resampled at every iteration, the subspace will shift too frequently. This limits the algorithm's 's ability to adequately explore one low-rank subspace over longer period, potentially causing abrupt changes in the model parameters X at each iteration and degrading fine-tuning performance.
Additionally, ZO methods capture less information about the true gradient compared to FO algo- rithms, necessitating more iterations to achieve similar performance. In other words, multiple Zo steps may be required match the progress of single FO step. This suggests that maintaining low-rank structure in the gradient estimator at each step is insufficient; instead, the cumulative sum of gradient estimators over several consecutive iterations must also preserve low-rank structure.
The motivations outlined above lead us to propose a lazy sampling strategy. While U is sampled at every iteration E, we only sample V every iterations, where v > represents the chosen period duration. During the iterations
(kv...., (k 1) 1} for each period k. the matrix (k) remains fixed, thus restricting the model update to the subspace spanned by (k), This leads to proposed 1.70 algorithm, whose update rule for any 2 0 is defined as:
X = X' a (FF('; where (F(X'; = LGE(X', U (V, ((,,,, (9)
With the lazy sampling strategy, 5t) consistently lies within the subspace determined by ((k) for any t E [kv,..., (k- - 1)v-1} 1J. Therefore, the accumulation of the estimated gradients over these consecutive steps, which can be viewed more accurate approximation of the true gradient in single FO step, has a rank that does not exceed r. When = 1, the LOZO update rule (9) reduces to the standard recursion LOZO can be implemented Algorithm I with memory efficiency.
Hyperparameter tuning. The parameter v, which defines the number of steps over which X is updated within the same subspace, is critical for performance and should be set to moderate value. is too small, frequent subspace shifts may lead to abrupt model changes, while a y that is too large limits the algorithm to focus on only few subspaces, potentially reducing generalization. The parameter r defines the rank the gradient estimator. Since the true gradient rank is unknown, we typically set r as a small constant that is significantly less than both my and ng avoid additional memory overhead. In our experiments, we set ra = r through all layers. The typical choices for the parameters 2, 4, 8 and 50, 100.
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: Low-rank ZO-SGD (LOZO)
Input: parameters X, loss function E) step budget T, perturbation scale e, learning rate sample interval y and rank (re)-
for t = 0, 0.....
do foreach X X do
Sample Ug E R from the standard normal distribution
if mod y 0 then
Sample V22 E I from the standard normal distribution; // Resample Vi
X +- Perturbation X, {U,, Ve));
F+ f ;
X <- Perturbation X, 2e, (U6, Ve));
F- + ;)
X +- Perturbation(X, c,, (Uz, Vi));
// Reset parameters // Calculate finite difference
c (F+ - /2E;
foreach X; X do
X - X1 a c(U&V? /m:)
// Update parameters in place
Function Perturbation (X, (Ue, V:)):
foreach X E X do
L X -Xe++ eU'V?"
Modify parameters in place
return X
4.2 LOZO ESSENTIALLY A ZEROTH-ORDER SUBSPACE OPTIMIZATION METHOD
This section offers an in-depth understanding on LOZO, showing that it can be interpreted as a ZO subspace optimization method. This interpretation provides an insight into why LOZO can effectively solve problem ( even with low-rank gradient estimates and lazy sampling strategy.
Random coordinate minimization. We begin by revisiting the classical coordinate minimization algorithm for gigh-dimensional optimization problems. Consider the unconstrained minimization problem min 4 {=x). where the dimension is exceedingly large. A commonly used and effi cient method to tackle this problem is the coordinate minimization algorithm. Let 7 := [er;.... ea] be the d-dimensional identity matrix, where e; represents the i-th basis vector. The random coordi- nate minimization algorithm then iterates follows:
by arg min (f b.bbee. bee))) where is u(11.....0
(10)
BER
1 b
Ciss
(11)
where æ0 is the initialized variable. The coordinate minimization algorithm has strong convergence
guarantees, as demonstrated in studies such (Hong et al. 2017 Tseng 2001 Wright 2015).
Random subspace minimization. Analogous to random coordinate minimization, the random sub- space minimization approach is to solve optimization problems involving large matrix variables. To solve problem [D.i.e i.e. minx f (X) EEg (XX;E)) we can employ the following recursions
B = arg min ([x (R) ( (8)
where (A) follows normal distribution,
(12)
X (k+1) = (k) + (V
(13)
Here, V is a low-rank matrix and B a matrix variable with much smaller size than X. For example, in the f-th layer, the matrix variable B, has dimensions my x re, while X₂ has dimensions m, x ng. The random subspace optimization approach addresses the original problem [ by solving series of subproblems that involve significantly smaller matrix variables, as shown 12
zo subspace optimization method. To solve the k-th subproblem in 12). we apply the standard
ZO-SGD and iterate for steps. The result is then used as inexact solution (12), followed by the update step in (3).. Specifically, the update rule for the ZO subspace method is given by:
1k (k.+) - B F (kkee) (V(K)
(k..))). (
=0, ....V (14a)

---

Published as a conference paper at ICLR 2025
( = (x) + (( (v())))
(14b)
Here, we initialize B (R,0) O. the superscript k indicates that the recursion is solving the k-th subproblem in (12. is the step size, and V WBB F( + (V g(h.)) is computed using the RGE scheme. Specifically, we sample U (1,,s) from normal distribution and compute:
BBF B (k))) :(( F(X (8) (8.)) t (V())) -1x
(15)
g(h.e))
Urkk,))
2
Equivalence between ZO subspace method and LOZO algorithm. The ZO subspace method [14) is equivalent to the LOZO algorithm (9) when the step size y a/r, as will be shown below. If both algorithms are initialized identically, i... X (x),, by comparine the update rules for X in LOZO (9) and 66. and for B the ZO subspace method (4a)) and (15 it straightforward holds when = kv + 8 and 8 E {0, "o.1,....))) (see the detailed derivation in Appendix A.2).. Thus, we have X = (R) for any k which implies the equivalence between these two methods.
to see that X X (K) + (k.+)
4.3 CONVERGENCE ANALYSIS
Based on the aforementioned interpretation, we can establish convergence guarantees for the LOZO algorithm. We adopt the following assumptions, which are standard in stochastic optimization.
Assumption 4.1. For any &, the function F(X;E) is differentiable with respect to X. Furthermore,
The gradient V F F is uniformly L-Lipschitz continuous, i.e., VX,Y, Y.
[VF((;E) VF(Y: E\Il < L|| YII, AA,
(16)
where |X|| EE (|Xel? for any X = (Xi)
The stochastic gradient is unbiased and has bounded variance, i.e., VX,
E[VF((XE) Vf(X) and EI - VI(X))I
(17)
Assumption 4.2. The random matrix V (V) drawn from distribution such that V IeI and VVV reI for each L.
Remark 4.3. Given that ny >> Te practice, when each Ve is drawn from standard normal distribution, it typically holds that VTVi s nzI. However, to rigorously satisfy Assumption 4.2
each V₁ should be drawn from a Haar distribution or as a random coordinate matrix (see (Kozk et al. 2023), Examples I and 2 for more details).
The following theorem establishes the convergence rate of the L070 algorithm, with the detailed proof provided in Appendix B
Theorem 4.4. Under Assumptions 4.1 and 4.2 and letting T Kv, with suitable choices of a and the sequence of the kv-th variables X generated by LOZO converges at the following rate:
(1
12 5o
AoLdo² T
DoLdv
E
+
(18)
K
T
where Do = f(x)) - fr, d= Ef (men3/rr) and d EF meng.
Difference between LOZO and MeZO-LoRA. Theorem 4.4 implies LOZO solves minx f(X) := [F(x; {)] directly even when using low-rank gradient estimates. In contrast, the MeZO-LoRA approach, which combines MeZO (Malladi et al.) 2023) and LoRA (Hu et al. 2021). solves minA, B. f(X + AB) == [x AB Notably, MeZO-LoRA can only optimize the low- rank adapters A and B, without the capability to optimize the full parameter X. This distinction explains why LOZ0 outperforms MeZ0-LoRA in most of empirical studies.

---

Published as a conference paper at ICLR 2025
4.4 LOZO WITH MOMENTUM
Momentum technique requires additional memory overhead. The momentum technique is widely used in modern deep learning to reduce gradient variance and accelerate the convergence of training. The ZO-SGD with momentum (ZO-SGD-M) iteration can be expressed as follows:
M 3M + +1 (V=(( X -x'aMM'
(19)
where M {Mi) is the momentum term, 8 is the momentum coefficient, and VF("'; denotes the 70 estimated gradient at iteration t. Compared with the vanilla ZO-SGD, ZO-SGD- M introduces additional memory overhead since it requires storing the momentum term, which is proportional to the size of the model.
The LOZO-M algorithm introduces negligible memory overhead. We can integrate the proposed LOZO algorithm with the momentum technique (LOZO-M) without the memory overhead issue. To simplify the formulation, we denote the finite difference of function values at iteration where t E (ku,..., (k + 1)2-1))1 1}. as c². The gradient estimator for the LOZO algorithm, as introduced in (U /r)²
9.. can then be represented as F
We now introduce LOZO-M, the memory-efficiet version of ZO-SGD with momentum. The key observation that (k) remains fixed for t E {kv...., (k + 1)F 1}.. Consequently, it suffices to accumulate e instead of the full gradient estimator ;F((*;<)) for updating the momentum, thereby significantly reducing memory overhead. The update rule is expressed follows:
N = 3N + - B),',, X = X (V /r)"
(20)
where N (kV(()) /r) corresponds to the original momentum. When updating X compute (V((() /r) layer by layer and discard the result immediately after updating the weights of each layer. Consequently, compared with the vanilla ZO-SGD-M (19). LOZO-M (20) only requires stor-
ing N (N)) Since re & min(m,, ne), the additional memory overhead is negligible.
Momentum projection. When (k) is updated, additional step is required. Specifically, due resam- pling, while the momentum from the previous step is N (V /r) Thus, we cannot update the momentum by simply combining c'U and N as per (20). To address this, we project the old momentum onto the new subspace spanned by V (k+1) before updating N We compute:
(k + 1)v, the gradient estimator FX"X:: :t) takes the form ct (VU((V((+)))
! arg min |N -
By doing this, the projected momentum N N /r)"" becomes good approximation of the momentum from the previous step, taking the same form as the gradient estimator :' Therefore, we use / to replace < in the momentum update (20) at = (k + 1)v, Given that V Ve as T for any e (see Remark 4.3). the solution is N = N (V /n), where n = [nelf The detailed LOZO-M algorithm is provided in Algorithm
5 EXPERIMENTS
This section evaluates the performance of our algorithm across multiple tasks, including the Super- GLUE benchmark (Wang al., 2019) and other datasets, as detailed in Appendix(C.. We compare our L.000 and 1.0Z0-M algorithms with MeZO (Malladi et al. 2023) as well as its variants, and other baselines including zero-shot and in-context learning (ICI.) approaches. We also test full fine-
tuning and LoRA using the gradient-basee Adam method [Kingma 2014). referred to FT and FT-LoRA, respectively.
Our experiments evaluate the algorithms on language models (LMs) of various scales, including RoBERTa-lare (Liu et al. (019b) and large autoregressive LMs such as OPT-13B, 30B, and 66B (Zhang et al. 2022a). We also test LLaMA models (Touvron et al. 2023) of varying scales, with the results presented in Appendix DD3 For a fair comparison, we conduct full grid search of the
parameters provided in (Malladi et al. 2023) and select the best results for MeZO and its variants.
8

---

Published as a conference paper at ICLR 2025
5.1 MEDIUM- SIZED MASKED LANGUAGE MODELS
We conduct experiments employing RoBERTa-large on tasks including sentiment classification, nat- ural language inference and topic classification. To mitigate the effects of random variability, all experimental results reported in this subsection are the means of the outcomes resulted from five different random seeds.
LOZO outperforms MeZO and MeZO-LoRA on the majority of datasets and achieves perfor- mance comparable to FT. As shown in Figure 2 our algorithm demonstrates performance gain on the three listed datasets, with particularly significant improvement on the MNLI dataset, surpass- ing both MeZO and MeZO-LoRA. The performance gap between LOZO and FT generally less than I 1,, and with a larger k; LOZO can further narrow this gap and even exceed its performance. We provide the complete results RoBERTa-large Appendix D.I
LOZO-M consumes similar memory usage to LOZO while delivering superior performance compared to MeZO and MeZO-Adam. We measure the actual memory consumption during the training of RoBERTa-large using LOZO, MeZO, and their respective variants evaluate the mem- ory efficiency of our methods. As shown in Table | the additional memory overhead introduced by the momentum technique in LOZO is negligible. In contrast, MeZO fails to achieve this efficiency.
Algorithm
MNLI
SNLI
Accuracy (%)
Memory Usage (GB)
Accuracy (%)
Memory Usage (GB)
LOZO
61.6
2.83
73.4
2.83
LOZO-M
62.7
2.84
74.0
2.84
MeZO
56.7
3.00
68.5
3.00
Me70-M
58.9
5.89
69.6
5.89
MeZO-Adam
62.6
7.42
72.7
7.42
Table 1: Accuracy and memory consumption of LOZO and McZO with their respective variants.
MeZo-LaRA
FT-LORA
LOZO
LOZO-M
k-16
90
75
85
70
Accuracy (96
80
(95)
75
60
70
60
50
SNL
MNLI
RTE
SNLI
MNLI
RTE
Figure 2: Comparison of the performance of different algorithms on RoBERTa-larg across three tasks (SNLI, MNLI, and RTE), with the left panel corresponding to k = 512 and the right panel corresponding to k 16. Detailed numerical results provided in Table S
Task
SST-2
RTE
BoolQ
WSC
WiC
MultiRC
COPA
ReCoRD
SQuAD
DROP
Zero-shot
58.8
38.5
80.0
46.2
ICL
87.0
62.1
66.9
39.4
50.5
53.1
87.0
82.3
75.9
29.5
MeZO
91.3
68.1
59.4
88.0
81.8
31.3
McZO-LoRA
89.6
67.9
67.8
73.5
63.5
60.2
61.3
84.0
81.5
82.1
31.3
LOZO
91.7
70.4
69.6
71.9
63.5
60.8
63.0
89.0
81.3
84.9
30.7
FT
91.8
70.9
76.9
63.5
70.1
71.1
79.0
84.9
31.3
Table Experiments on OPT-13B (with 1000 examples). ICL: in-context learning: FT: full fine-tuning with Adam. The best results are shown bold except for FT.

---

Published as a conference paper at ICLR 2025
5.2 LARGE AUTOREGRESS LANGUAGE MODELS
To further evaluate the effectiveness of LOZO on large language models, extend study the OPT models (Zhang et al., 2022a) with billions of parameters (13B, 30B and 66B). The results are presented in Table and Table
Compared to MeZO and MeZO-LoRA, LOZO demonstrates a clear improvement across the majority of datasets. For instance, LOZO achieves notable performance gains on OPT-30B and OPT-66B, as presented in Table outperforming MeZO and other baselines in most tasks. Further- more, the results fable(2indicate that LOZO only surpasses MeZO and MeZO-LoRA but also approaches the performance exhibited by FT on most cases.
LOZO yields faster convergence rates across different model scales, including 13B, 30B and 66B. As illustrated in Figure 3 the proposed method consistently achieves faster convergence across various datasets and model scales. For example, the WIC dataset with the OPT-66B configuration, the LOZO algorithm requires only half the number of training epochs to achieve the same training loss as that of the MeZO method, while simultaneously exhibiting smaller loss oscillations.
Task
SST-2
RTE
BoolQ
WSC
WiC
SQuAD
30B zero-shot
56.7
52.0
39.1
38.5
50.2
46.5
30B ICL
81.9
66.8
66.2
56.7
51.3
78.0
30B MeZO
90.7
64.3
68.2
63.5
56.3
86.1
30B LOZO
92.8
65.3
72.3
64.4
57.2
85.6
66B zero-shot
57.5
67.2
66.8
43.3
50.6
48.1
66B ICL
89.3
65.3
62.8
52.9
54.9
81.3
66B McZO
92.0
71.5
73.8
64.4
57.8
84.0
66B LO70
92.5
74.0
74.5
63.5
59.4
85.8
Table 3: Experiments on OPT-30B and ОРТ-66B on SuperGLUE benchmark. Our results show that LOZO is superior on most tasks compared the other baselines. The best results are shown in bold.
244
MAZU
Mado
0.22
MA2O
57-
30
0.2
2.6
Figure 3: Left: Loss curves of OPT-13B on SQuAD dataset. Middle: Loss curves of OPT-30B on SST-2
datasct. Right: Loss curves of OPT-66B on WIC dataset.
CONCLUSION AND LIMITATIONS
This paper introduces the LOZO and LOZO-M algorithms, which are novel zeroth-order (ZO) meth- ods for fine-tuning language models. Specifically, the LOZO algorithm employs a gradient estimator with low-rank structure, closely mirroring the true gradient in first-order (FO) methods. We further demonstrate that the LOZO algorithm is equivalent to a 70 subspace method, forming the basis for convergence results. By combining LOZO with the commonly used momentum technique, develop the LOZO-M algorithm, which incurs almost no additional memory overhead. Both LOZO and LOZO-M achieve improved performance compared the vanilla ZO-SGD method.
One limitation of our work is the challenge of designing a method that integrates LOZO with the Adam optimizer without incurring additional memory costs. Additionally, minor fluctuations in the loss are observed towards the end of the training process, potentially due to the lazy sampling strategy. Addressing these issues is left for future work.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The computational resource was provided by the Center for Intelligent Computing, Great Bay In- stitute for Advanced Study, Dongguan, China. This work was supported in part by National Key Research and Development Program of China under the grant numbers 2024YFA101290 2024YFA1012903. and the National Natural Science Foundation of China under the grant num- bers 12331010, 12288101, 12401408 and W2441021. We also thank the anonymous reviewers for their valuable feedback.
and
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.087744 2023.
Shun-ichi Amari Backpropagation and stochastic gradient descent method. Neurocomputing, (4-5):185-196, 1993.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic opti- mization via conditional gradient and gradient updates. Advances in Neural Information Process- ing Systems, 31, 2018.
Roy Bar-Haim, Ido Dagan, Bill Dolan, Lisa Ferro, Danilo Giampiccolo, Bernardo Magnini, and Idan Szpektor. The second pascal recognising textual entailment challenge. Proceedings of the second PASCAL challenges workshop on recognising textual entailment, volume 1. Citeseer, 2006.
Luisa Bentivogli, Peter Clark, Ido Dagan, and Danilo Giampiccolo. The fifth pascal recognizing textual entailment challenge. TAC, 7(8):1, 2009.
Albert S Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations derivative-free optimization. Foundations of Computational Mathematics, 22(2):507-560) 2022.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher Manning. large anno- tated corpus for learning natural language inference. arXiv preprint arXiv:1508.05328 2015.
Tom B Brown. Language models are few-shot learners. arXiv preprint ArXiv:2005. 14165, 2020.
HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang, Zeroth-order regularized opti- mization (zoro); Approximately sparse gradients and adaptive sampling. SIAM Journal on Opti- mization, 32(2):687-714, 2022.
Aochuan Chen, Yimeng Zhang, Jinghan Jia, James Diffenderfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training. arXiv preprint arXhv:2310.02025, 2023.
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. Advances in neural infor- mation processing systems, 32, 2019.
Christopher Clark, Kenton Lee, Ming- Wei Chang, Tom Kwiatkowski. Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint /905. 10044, 2019.
Ido Dagan, Oren Glickman, and Bernardo Magnini. The pascal recognising textual entailment challenge. In Machine learning challenges workshop, pp. 177-190. Springer, 2005.
Catre-Catterine De Marneffe, Mandy Simons, and Judith Tonhauser. The commitmentbank: In- vestigating projection in naturally occurring discourse. In proceedings of Sinn und Bedeutung, volume 23, pp. 107-124, 2019.
11

---

Published as a conference paper at ICLR 2025
Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin-Yo Chen, Karthikeyan Shan- mugam, and Ruchir Puri. Model agnostic contrastive explanations for structured data. arXiv preprint wrXivv9966.00 2019.
Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. arXiv preprint urXiv:/903.00161. 2019.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1(5)27788 28026 2015.
Tanmay Gautam, Youngsuk Park, Hao Zhou, Parameswaran Raman, and Wooseok Ha. Variance- reduced zeroth-order methods for fine-tuning language models. arXiv preprint arXiv:2404.0808 2024.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM journal on optimization, 23(4):2341 2013.
Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and William B Dolan. The third pascal rec- ognizing textual entailment challenge. In Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing, pp. 1-9, 2007.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in tiny subspace. arXiv preprint vrXiv:/8/2.00455: 2018.
Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A Smith. Don't stop pretraining: Adapt language models domains and tasks. arXiv preprint arXiv:2004. 10964, 2020.
Yongchang Hao, Yanshuai Cao, and Lili Mou. Flora: Low-rank adapters are secretly gradient compressors. arXiv preprint arXiv:2402.0323 2024.
Mingyi Hong. Xiangfeng Wang, Meisam Razaviyayn, and Zhi-Quan Luo. Iteration complexity analysis of block coordinate descent methods. Mathematical Programming, 163:85-114, 2017.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2/06.09683 2021.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International conference on machine learning, pp. 2137- 2146. PMLR, 2018.
Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algo- rithms and analysis for nonconvex optimization. In International conference on machine learning, pp. 3100-3109. PMLR, 2019.
Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth. Look- ing 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 Com- putational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 252-262, 2018.
Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
David Kozak, Cesare Molinari, Lorenzo Rosasco, Luis Tenorio, and Silvia Villa. Zeroth-order op- timization with orthogonal random directions. Mathematical Programming, 199(1)1119--121, 2023.
Brett W Larsen, Stanislav Fort, Nic Becker, and Surya Ganguli. How many degrees of freedom do we need to train deep networks: a loss landscape perspective. arXiv preprint arXiv:2107.05800 2021.
12

---

Published as a conference paper at ICLR 2025
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-effciient prompt tuning. arXiv preprint arXiv:2104.08691, 2021.
Hector Levesque, Emest Davis, and Leora Morgenstern. The winograd schema challenge. In Thir- leenth international conference on the principles of knowledge representation and reasoning. 2012.
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint arXiv:/804.08838 2018.
Zeman Li, Xinwei Zhang, and Meisam Razaviyayn. Addax: Memory-efficien, fine-tuning of lan- guage models with a combination bawward-backwerr and forward-only passes. In 5th Workshop on practical ML for limited/low resource settings, 2024.
Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first- order. Advances in Neural Information Processing Systems, 29, 2016.
Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Sijia Liu, Pun-Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference on Learning Representations, 2019a.
Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod K Varshney. A primer on zeroth-order optimization signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43 54, 2020.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1907.1997..11999 2019b..
Yong Liu, Zirui Zhu, Chaoyu Gong, Minhao Cheng, Cho-Jui Hsieh, and Yang You. Sparse mezo: Less parameters for better performance in zeroth-order Ilm fine-tuning. arXiv preprint arXiv:2402.15755 15751, 2024.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems,
2023.
Aashiq Muhamed, Oscar Li, David Woodruff, Mona Diab, and Virginia Smith. Grass: Compute effi- cient low-memory Ilm training with structured sparse gradients. arXiv preprint a7Xi, 2024.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Mohammad Taher Pilchvar and Jose Camacho-Collados. Wic: the word-in-context dataset for eval-
uating context-sensitive meaning representations. arXiv preprint arXiv: 2018.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint 100.v2060..05250, 2016.
Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S Gordon. Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In 2011 AAAI spring symposium series, 201 1.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint 140.:1700004454. 2017.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adver- sarial winograd schema challenge at scale. Communications of the ACM, 64(9)999-106, 2021.
13

---

Published as a conference paper at ICLR 2025
Victor Sanh, Albert Webson, Colin Raffel, Stephen H Bach, Lintang Sutawika, Zaid Alyafeai, An- toine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, et al. Multitask prompted training enables sero task generalization. arXiv preprint arXiv:2110.08207, 2021.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language pro- cessing, pp. 1631-1642, 2013.
Irene Solaiman, Miles Brundage, Jack Clark, Amanda Askell, Ariel Herbert- Jeff Wu, Alec Radford, Gretchen Krueger, Jong Wook Kim, Sarah Kreps, et Release strategies and the social impacts of language models. arXiv preprint (rxXiv:998.09200 2019.
James C Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332 341, 1992.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.0920 009,0888, 2023.
Paul Tseng. Convergence
block coordinate descent method for nondifferentiable minimization. Journal of optimization theory and applications, 109:475-4991 2001.
Chun-Chan Chun Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-bass zeroth order optimization method for attack- ing black-box neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 742-749, 2019.
Ellen M Voorhees and Dawn M Tice. Building question answering test collection. In Proceed- ings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pp. 200-207, 2000.
Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for general-purposs language understanding systems. Advances in neural information processing systems, 32, 2019.
Xiaoxing Wang, Wenxuan Guo, Jianlin Su, Xiaokang Yang. and Junchi Yan. Zarts: On zero-order optimization for neural architecture search. Advances in Neural Information Processing Systems, 35:12868 12880, 2022.
Adina Williams, Nikita Nangia, and Samuel R Bowman. A broad-coverage challenge corpus for sentence understanding through inference. arXiv preprint (eXX:v:704.0542222 2017.
Stephen J Wright. Coordinate descent algorithms. Mathematical programmingg (51(3))3334 2015.
Sheng Zhang, Xiaodong Liu, Jingjing Liu, Jianfeng Gao, Kevin Duh, and Benjamin Van Durme. Record: Bridging the gap between human and machine commonsense reading comprehension. arXiv preprint arXiv: 10810.2288. 12885, 2018
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0000 2022a.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yin-Yu Chen, Jason D Lee, Wotao Yin, Mingyi Hong, et al. Revisiting zeroth-order optimization for memory-efficient Ilm fine-tuning: A benchmark. arXiv preprint arXivv2402.11599 2024.
Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu. How to robustify black-box ml models? zeroth-order optimization perspective. arXiv preprint 273.422003.14195. 2022b.
Zhong Zhang. Bang Liu, and Junming Shao. Fine-tuning happens in tiny subspaces: Exploring intrinsic task-specific subspaces of pre-trained language models. The 61st Annual Meeting Of The Association For Computational Linguistics, 2023.
14

---

Published as a conference paper at ICLR 2025
Jiawei Zhao, Zhenyu Zhang, Beidi Chen, Zhangyang Wang, Anima Anandkumar, and Yuandong Tian. Galore: Memory-efficient Ilm training by gradient low-rank projection. arXiv preprint arXiv:2403.03507, 2024a.
Pu Zhao, Sijia Liu, Pin- Yu Chen, Nghia Hoang, Kaidi Xu, Bhavya Kailkhura, and Xue Lin. On the design of black-box adversarial examples by leveraging gradient-free optimization and operator splitting method. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 121-130, 2019.
Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor W Tsang. Second-order fine-tuning without pain for Ilms: A hessian informed zeroth-order optimizer. arXiv preprint arXiv:2402.15173, 2024b.
A
MORE COMMENTS
A.1 UNBIASENESS OF LGG
In the proposed LOZO algorithm, we employ LGE to approximate the gradient. The following proposition demonstrates that the LGE scheme is unbiased as e + O.
Proposition A.1. If F();E) differentiable with respect to X, the LGE in 5 is an unbiased estimator of X F {X; when + 0.
Proof. For simplicity, we omit the random variable & in this proof. Under the differentiability as- sumption, for any set of real matrices { (Xx,)== with the same dimensions X, we have
F([X, + +cxX)
F F(X) - (Vx exx)) 0.
lim
Now, since Vx, F(X) from
can be written
F([X; + cU ) F(X)
De F(X)
2E
F((X; cU (
F(X)
Vx, F(X). -cUVV)
UVVT TE.
2c
Vvx F(X),
we have
lim E V x, F(X)
-E Σ (x, U(X)
Since all elements of (Ur, Vole are i.i.d. Gaussian variables, we can further deduce that
lim c
4 x F(x)
= L (V
The element row and column of this expression is
[V x. F(X), UNVT).V
E
my
me
0F(X)
Σ
Uelpp 1edd IVelj=
Tt
o[Xepp
(21)
1 (
(F(X)
E ri 0[Xiles
0.X,lis
Therefore, we conclude that
lim E
Vx,F(x))
F(X)
15

---

Published as a conference paper at ICLR 2025
A.2 EQUIVALENCE BEWTWEEN LOZO AND ZO SUBSPACE METHOD
We present the detailed proof of the equivalence between LOZO algorithm ( and the ZO subspace method (4). Let X be the 1-th iteration point of LOZO, and let X be the k-th iteration point of the outer loop the ZO subspace method (14b). We now show that X = (²) holds the -0))
initialization of both algorithms is the same, i.e., X
We now introduce Y (k,s) = (b) B (k.)) (V ( When the step size satisfies y = a/r, using the update rules for B from 14a and 15
derive the update rule for Y, which is:
F(Y (k.0) eU (k.s) (k))) (( eU((i.a) (V))))?)
= (k,,)) (k(++))
U(hho) (V(6))
2e
, Vs E {0, .M V _V-13 1}. (k,kk)) a: LGE((Y((..) U(k,ss ((k), r, ,,
(22)
This update rule for Y aligns with that for X in the LOZO algorithm. Thus, once Y X()
Xke it follows that (k,9) = + (V(()T Xkr+s for all {0, 1...., v). Therefore,
( (A) + B (1.,) (V X (1++ Thus, the relation X X holds for any k. given that X X
A.3 DETAILS OF LOZO-M
We present the detailed LOZO-M algorithm in Algorithm? Compared to the LOZO algorithm, the main difference the addition of the momentum term update.
2
Algorithm 2: Low-rank ZO-SGD with Momentum (LOZO-M)
Input: parameters X, loss function E) step budget T, perturbation scale learning rate a, momentum parameter B, sample interval v and rank (rz).
foreach X₂ E X do
L N₂ 1 0:
// Initialize momentum
for t ....., 1 do
foreach X₂ E X do
Sample U/ E Rexxx: from the standard normal distribution;
if mod v 0) then
Mg + NeVi:
Sample V/2 E Rruxr from the standard normal distribution; // Resample V
No+ + 1 M,V&: // Project momentum onto the new subspace nz
X Perturbation c, (Ug, V&));
F4 + F(X:E);
X Perturbation X, 2e, (Ur, Vi));
F_ < F(X:E);
X Perturbation X.c, (Ue, Ve))::
// Reset parameters // Calculate finite difference
c (F4 /
foreach X, E X do
N₂ 8N: + (1 B) die
// Update momentum in place
X X. (NeV /re::
// Update parameters in place
Function Perturbation (X,c, (Un, Vi)): foreach X, X do X < X :U:V:::
Modify parameters in place
return X;
B CONVERGENCE ANALYSIS
In this section, we present the convergence analysis of the LOZO algorithm and provide detailed proof of Theorem Without loss of generality, focus the where the number of layers is
16

---

Published as a conference paper at ICLR 2025
== 1. Consequently, the problem ①
reduces minx f(X) == Be|F(X::)) where X E R=
To simplify the notation, we define the following terms:
Gx.v(B: = P(X + ;V) (x,( = f(X + BV
VGx,v(B:E) == ( + +cU) -xv(BBeU)) With these definitions, the subspace minimization problem
2e
12
can be reformulated as follows:
min 9x. (x) B
EggGGx, (B:E)
(23)
As demonstrated in Section 4.2 our proposed LOZO algorithm is equivalent to solving the subprob- lem (23) using ZO-SGD with the LGE scheme for steps, followed by update of the weight matrix. Specifically, by applying the following update rule:
B(ss+1) = (k,,)) at BG x00, (B(s)) ((h,))) Vo E (0, I...., 1},
(24a)
=(+1)= + (V()))
(24b)
follows that X (k) for any k; where X represents the kv-th iteration point of the LOZO
algorithm. For the remainder of the proof, we will use Xkv in place of (x) (4).
Under Assumption 4.2 the following properties hold, which can be straightforwardly derived:
|AV || (tr(AVTVAT) Alll,
| = VIVTVII2= = vn.
where E Rm is any matrix. For simplicity, we will not explicitly reference these properties when they are used.
To construct the convergence result, our analysis is divided into two parts. First, we analyze the convergence of ZO-SGD (24)) for solving (3 with fixed X and V. Next, assess the impact of updating X and resampling V. and establish the global convergence result for LOZO algorithm.
To begin the first part, introduce some preliminary lemmas. All of these lemmas assume fixed X and V, so we will omit the subscripts of (B) and Gx.v (B; {) when there is no risk of confusion. The following lemma establishes the desirable properties of the objective function in (3). which are necessary for the convergence of the iteration given in (24a).
Lemma B.1. Under Assumptions 4.1 and 4.2 the following properties hold:
The function Gx,v (B:g) is uniformly L-smooth with a constant L = nL.
(B; is an unbiased estimator of Vxx,v(B)), and its variance is bounded by E (B: - V9x.v(B))l
where x² no.
Proof. Given any &, since F(X. is differentiable and X + UVT is linear function of U, the function Gx,v (U: also differentiable, and we have:
VGx,v(B.E) = VF- + BV
Thus, follows that:
(BI.)( (Bx. VV BBV .VV - VF(X + B&V VVVlle IVF +BV . VF(X B.V* ,
< L |elV/12
nL B1 BZlle.
17

---

Published as a conference paper at ICLR 2025
The second property holds because
Egl (VV (oXI(
B + UV) VS(X + VV
V/(X s VF//VF(XX +UV :E) VV-X + +UV ||
s o IV =no?
The following lemma, which bounds the second moment of the gradient estimator, is necessary for proving the convergence of ZO-SGD. Lemma B.2. For the gradient estimator (B:E). the following bound holds:
Ey (Bx & |mr]l VGxx m
Proof. The triangle inequality provides the following bound:
(BI 2Ey IVG() (VG(B:)), 2 I
To bound the first term, Assumption 4.1 leading the following inequalities:
i.c2
GGB++U;; -) -(VC)) -
|
2
L
|
2
Combining these inequalities, we obtain:
G(B C(B
Le 2
|
2e
Multiplying by U on both sides and taking the expectation with respect to U yields:
I'e2 S Ey |U11 S immmr + 4)
Ey -VC
m2
4
In the final inequality, we use the fact I&r UU mr(mr + 2)(rr + 4). The second term can be calculated directly, giving us:
Ey VV UyUl| (mr + V) (
Combining these inequalities completes the proof.
We now introduce the Gaussian smoothing function as follows:
(B) = Ey (Bx.v( +U)]] 1 (B 1110 dU.
The following lemma outlines several properties of the Gaussian smoothing function.
Lemma B.3 (Section in (Nesterov & Spokoiny 2017)). For the Gaussian smoothing function
gx.v (B), the following properties hold:
(B:l (B).
(xv(B) L-smooth.
(B) (B) < imne"
Vox. VÆx.v (B).((B)l3 immre?
18

---

Published as a conference paper at ICLR 2025
Proof. We only prove the last claim. The remaining claims and their proofs can be found in (Nes- terov & Spokoiny 2017).
V
|u (Vg(B + eU) Vg(B))
Ev Vg - VB(
< i |U]| = mrr..
In the first inequality, we apply Jensen's inequality, and the second inequality derives from the Ż- smoothness of 9(B)..
Now we are able to establish the convergence for solving problem 23 using the update rule (2aa) The following lemma bounds the expected difference between any B and Ba.
Lemma B.4. If the step size condition 1622 mura? following inequality holds:
is satisfied, then for any t v, the
Eugg [B -0--11 1 S 64mv2
+ 24mva2 + 2642 me u2a
BU.e
(B
To simplify the notation, we use E to denote the expectation taken over both U and &. By the triangle inequality, we have the following:
Proof.
E| B++ - 1 E B²
(v((B B
E Bt
Vg -B8
|
E
-
1
BI BO +
va
VI (
||
B 51)1
,
Next, we use Lemmas B.2 and
B.3 to bound the last two terms:
B|B' 1O1 2va²
B|
11
V
v
6ma² 2
+
EE|
V + ::7 2 vv²
B - - + 8mva? 2
1 + v-1
E
Vg(B'))
6ma²z²
m
2re2vc?
16 mva2
B + 16mva2
1 1 1-1
E Vg
6ma2
mre re2vv
Applying the step size condition
m
we obtain:
w-
+ 16mwa2
BI -
1
<
1 +
EllB² 1
w-1
6ma 20²
m
By induction, we have:
2
)
16mwaa
2ma22²
E|] B'
12 1 +
V
+ me
64mv2
24mwa222
E
+
In the last inequality, we use the fact that Ex11
(1+
< 4v for
19

---

Published as a conference paper at ICLR 2025
The following lemma provides bound on the function value of 23 over iteration steps of the update rule (24)).
Lemma B.s. 1fe step size satisfies the condition 32 S 1, then the following holds:
(- va + 18Imu2a2
(B,) -xxy s
Bugg (
+ vo?
+ 2Lmre,
where L and 8² are defined in Lemma B.1
Proof. We continue use E to denote the expectation taken over both U and g. We begin with the following inequality, which is derived from the T-smoothness of ge (B):
Eg' )B*) S (BV), B" BB)- + 2 _ - 11
ك Σ (BCBB")) + La²
2,2 E
Σ
For the first term on the right-hand side, we have:
B(Vg (BBBBB''''BBB"") = Σ
B(V (BV
1=0
Σ
(BV
1=
"Vg
(B") (B)) (B9)
EIV (
BlVg (B')
(B"))
2r
2r
L w
imme²
va B 4r
1/22 +
Σ
B
2r
The first inequality follows from (a,b) <
||||2++|b00 and the final inequality holds due to Lemmas
B.I
and B.3
For the second term, we have:
La²
E
EvG(B'
1p
La²
E
Σ
GG((' - -V
| +
iva²
E B (B*)),
2r
2
1=0
t=
La
Lvaz w-1
E
(
V
+
(B')
2
22
1020 1-1
Lva 1-1
E
Σ E
V
6ima²
iva? 2-
VG : M +
+
Σ (B
8Lmva?
+ 6Lmō"va² + m 2220
E||
B
20

---

Published as a conference paper at ICLR 2025
16
16 m-1
Vg
E|| 1B
t=0
6Lmåd vo?
The first equation holds due the independence of U and ç¹ for each while the third and fourth inequalities follow from Lemmas B.2 and B.3] respectively. Combining the above results and con-
sidering the condition 32Lmva & 1, we obtain:
16tmv2a² +
1.aa m-1 )|?
- - (B9)) =
va 4r
E Vg
+
Σ
E|
1
r
t=0
Simoōva"
L2m
2
Applying Lemma B.4 and again considering the condition 32īmva S 1, we have:
18Lmv²a2
ElIV + 7imo²va imrr?.
- s
4r
Finally, by applying Lemma
B.3 once again, we can complete our proof.
Now we have established the bound for solving the subproblem (3 Next, we investigate the
impact of updating X and resampling V and establish the convergence result for proposed LOZO algorithm. This leads to the following theorem.
Theorem B.6 (Theorem 4.4). Under Assumptions 4./ and 4.2 and assuming the step size a S
WaLLmn'' when applying the proposed LOZO al algorithm to solve problem 7 and letting T = Kv,
the following inequality holds:
K-1
8Ao Ta
56Lmn
16Lmnre
E
K
va
0=
where Do = f(X²) - f Furthermore, if we choose
DOv
56T Lmn
144Lmmv +
16T Lmar'
D
then it holds that:
1 K
1 (7ooLmn' < 16
2592A Lmmw
E
T
T
Proof. Recalling the update rule 24 it follows that
9x vool (B")= = f(Xkv + Bik (k)) (v(K))) ((x(+))))) Ixm. vaa (B") = f(xku).
Moreover, note that Vgxeu, (Bo) V v By applying Lemma B.5
we obtain:
+ 18Lmv2
Ey ([ - -((xbr) s
va 4r
Ev.el Buxel
Lmmō2
+ 2imre..
Taking the expectation (k), and noting that (KV (V (by Assumption 4.2 ((k) is independent of k we have:
E E(f(r(++)))) -((x")) - (- va + 18Lmv² E |X(*')]
21

---

Published as a conference paper at ICLR 2025
7Lmō² + 2lmre?.
Note that T = Kv. Rearranging the inequality above and summing over K gives:
( 18Lmva
Ao Ta
7Lmō²a
2mmre
ElVs
+
k=
Considering the step size condition 144îmva & and using L = nL and 0² = noo we complete the proof.
C EXPERIMENTAL DETAILS
C.I DATASETS
For RoBERTa-large, we evaluate the performance on six NLP tasks: SST-2 (Socher et al. 2013)
SST-5 (Socher et al. 2013), SNLI (Bowman et al., 2015). MNLI (Williams et al. 2017). RTE
DDgan et al. 2005 Bar Haim et al.) [006 Giampiccolo et al. 2007 Bentivogli et al. 2009). TREC Voorhees Tice 2000). We adopt two settings: = 16 and 512, which require and 512
examples per class, respectively, during both the training and validation stages.
For OPT, we conduct experiments on the following datasets: SST-2, RTE, CB (De Marneffe et al.) 2019), BoolQ (Clark et al. 2019). WSC (Levesque et al. 2012), WiC (Pilehvar & Camacho- Collados 2018), MultiRC (Khashabi et al. 2018), COPA (Roemmele et al. 2011). ReCoRD (Zhang
al. 2018), 8), SQuAD (Rajpurkar al. 2016), DROP (Dua et al. 2019)).
For the LLaMA model, we evaluate its performance on the SST-2, WiC, COPA, SQuAD, and Wino- Grande Sakaguchi et al. 2021) datasets.
Experiment
Hyperparameters
Values
LOZO
Batch size
64
Learning rate (k=16)
1e-6
Learning rate (k=512)
2e-7
Rank (r)
{4,8)
Interval (v)
{50, 100}
1e-3
Weight Decay
0
Mc70
Batch size
64
Learning rate
{1e-7h 7, 1e- 6, le-5) 5)
1e-3
Weight Decay
0
McZO-LoRA
Batch size
64
Learning rate
{le-5, 5, 5e-5, 5, le-4)
1e-3
Weight Decay (r,
0.1
(8, 16)
FT
Batch size
{8}
Learning rate
{le-5, 5, 3e- 5e-5)
Weight Decay
0
FT-LORA
Batch size
{8}
Learning rate ar)
{1e-4, 4, 3e-4, 5e-4) (8, 16)
Table 4: The hyperparameter grids used for RoBERTa-large experiments. The learning rate of the LOZ0 algorithm refers to a/r. For LOZO-M, introduce an additional parameter, 31, which is searched over the range (0.5, 0.7, 0.9).
22

---

Published as a conference paper at ICLR 2025
Experiment
Hyperparameters
Values
LOZO
Batch size Learning rate
16 {1e-6, le-7)
(le-3, le-4)
Rank (r)
{1, 2, 4) {50, 100)
Interval (v)
MeZO
Batch size Learning rate
16
(1e-6, 6, le- or (le- 6, 5e-5ee77 7, 1e-ee-)) 7) for SQuAD and DROP
1e-3
MeZO-LoRA
Batch size Learning rate
16
(le-4,5e 1ee-4.5--55 5e (le 4, 5e 5, le 1e-5) for SQuAD and DROP
1e-2
(r,
(8, 16)
FT
Batch size
Learning rate
[le 5, 5, Se- -)
Table 5: The hyperparameter grids used for OPT experiments. The learning rate of the LOZO algorithm refers a/r.
Experiment
Hyperparameters
Values
LOZO
Batch size
16
Learning rate (k=16)
le-7
Rank (r)
[2, 4)
Interval (V)
(50, 100)
e
le-3
Weight Decay
0
Mc20
Batch size
16
Learning rate
11e-7,1e-6}
le-3
Weight Decay
0
FT
Batch size
{8}
Learning rate
{le 6, 1e-7]
FI-LORA
Batch size Learning
{8]
{le 1le-1,1e-55 1e-5]
(r, (r)
(8, 16)
Table 6: The hyperparameter grids used for LLaMA experiments. The learning rate of the LOZO algorithm
refers to a/r.
C.2 HYPERPARAMETERS
In this section, we present the hyperparameter search grids support the reproducibility of our experiments using the RoBERTa-large, OPT, and LLaMA models. Both MeZO and LOZO utilize constant learning rate schedule, whereas FT and FT-LoRA adopt linear learning rate schedule.
For Me7O, LOZO, and their respective variants, we conduct 100K training steps, evaluating the model every 10K steps for the RoBERTa-large model; 20K training steps with evaluations every 4K steps for the OPT model; and 20K training steps, evaluating every 500 steps for the LLaMA model. For all gradient-based algorithms, adhere the configurations described in (Malladi al. 2023
Zhang et al. 2024).
C.3 ABLATION STUDY
In this section, explore how the choice of rank and the lazy update interval v affect the perfor- mance of our algorithm. We begin by examining the impact of v and r using the SST-2, COPA and RTE datasets the OPT-1.3b model. To illustrate the impact of different values of and on the
23

---

Published as a conference paper at ICLR 2025
convergence rate, present a plot of loss versus epochs in Figure Also, list the accuracy and training loss across different rank r and v/ for the three datasets in Table
Loop vs Epoch RTE docacet opt 36 acroes different
ooe Epoch on SST-2 decoset ope. 36 scroes different
0.77
02-
16:33
18 0.77
0.40
0.55
0.2
160
110
550
Epocks
Epods
Figure 4: Left: Loss curves of OPT-1.3B on RTE dataset across different rank r. Right: Loss curves of OPT-
1.3B on SST-2 dataset across different value
SST-2
CОРА
RTE
Accuracy
loss
Accuracy
loss
Accuracy
loss
50
88.1
0.45
73.0
1.93
56.7
0.68
100
89.0
0.46
74.0
2.18
56.7
0.68
1
55.0
0.79
74.0
2.58
50.9
0.70
50
93.0
0.37
74.0
2.04
61.0
0.69
100
92.1
0.37
71.0
2.05
58.1
0.68
200
92.7
0.37
77.0
2.05
62.1
0.67
500
91.7
0.37
75.0
2.05
62.8
0.67
50
91.3
0.35
76.0
1.99
57.4
0.69
100
92.0
0.35
75.0
1.97
57.8
0.69
50
88.5
0,48
71.0
2.03
55.0
0.71
100
88.9
0.45
73.0
2.03
56.3
0.71
Table 7: Performance and loss across different values and on SST-2, COPA and RTE datascts.
small value can negatively impact convergence. For datasets where the loss exhibits signif- icant decrease during fine-tuning, very small y values can hinder the model's convergence, leading degraded performance on the datasets. For example, with a rank of 2 and training loss reaches 0.79, nearly double that of other settings, as shown in Table 7 In addition, as exhibits different training dynamics compared to larger values, where
the final
shown in Figure 4 the training loss either remains unchanged or even increases.
small v value may not affect the model's performance on the test dataset. In contrast, for datasets where the loss remains stable or decreases only slightly, the performance degradation caused by small y values is minimal and less noticcable. The COPA dataset serves as a typical example, with the loss remaining nearly unchanged during training and unaffected by extremely small values. As is comparable to that of other settings.
shown in Table the accuracy with a rank and
A large rank that a larger rank starts with a higher loss, requiring additional training epochs to reach the same loss compared to those small rank
moderately slow down the training. The left panel of Figure demonstrates
small rank r leads to a decline model performance. When setting the rank to r = 1, consistently results in suboptimal performance across all three tasks.
24

---

Published as a conference paper at ICLR 2025
D MORE EXPERIMENTAL RESULTS
D.1 ROBERTA-LARGE EXPERIMENTS
We present the complete results for RoBERTa-large. As shown in Table 8 our LOZO method and its variant, LOZO-M, outperform other gradient-free methods almost all datasets.
Task
SST-2
SST-5
SNLI
MNLI
RTE
TREC
Type
sentiment
natural language inference
topic
Zero-shot
79.0
35.5
50.2
48.8
51.4
32.0
Gradient-free methods: = 16
MeZO
86.3 (8.0)
40.8 (2.5)
68.5 (4.2)
56.7 (3.4)
58.6 (9.5)
62.4 (10.2)
McZO-LoRA
88.4 (1.6)
38.9 (2.0)
67.0 (3.3)
56.8 (1.0)
59.7 (4.5)
(5.1)
LOZO
88.0 (5.8)
41.1 (2.8)
73.00
61.6 (4.6)
(911
(7.4)
LOZO-M
88.0 (5.8)
42.9 (1.5)
74.0 (4.0)
62.7 (4.5)
60.2 (8.4)
82.2 (5.2)
Gradient- basen methods: 16
FT
(5.3)
44.0 (1.7)
72.7 (5.7)
63.4 (4.3)
61.3 (5.3)
83.7 (4.7)
FT-LoRA
92.7 (0.9)
45.5 (1.4)
71.6 (4.5)
59.4 (4.6)
61.4 (6.9)
75.8 (7.8)
Gradient-free methods: k 512
MeZO
93.7 (0.4)
53.9 (1.9)
84.8 (1.1)
76.6
76.8 (3.1)
95.0 (0.4)
MeZO-LoRA
91.7 (0.2)
45.1
(1.1)
(0.9)
(0.8)
(1.9)
1O00
94.1 (0.7)
53.0 (0.4)
(0.8)
80.4 (1.0)
79.7 (2.0)
(0.4)
LOZO-M
94.3 (0.8)
52.6 (0.3)
84,9 (1.1)
80.5 (0.7)
79.7 (1.6)
95.5 (0.5)
Gradient- based methods: à = 512
FT
94.4 (0.6)
55.7 (1.6)
88.3 (0.8)
84.8 (0.7)
82.7 (1.I)
97.2 (0.3)
FI-LORA
91.9 (2.1)
52.4 (1.2)
84.8 (0.6)
74.8 (3.4)
81.2 (1.6)
96.1 (0.6)
Table Experimental results on RoBERTa-large (350M), reported numbers are averaged accuracy (stan- dard deviation). LOZO and LOZO-M outperforms MeZO and MeZO-LoRA by considerable margin and approaches FT performance.
D.2 OPT EXPERIMENTS
have also applied the LOZO-M algorithm the OPT-13B model, with results presented Table The numerical results indicate that incorporating the momentum technique further enhances the performance of LOZO across various tasks, even when applied to large model scales.
9
Task
SST-2
RTE
CB
WSC
COPA
SQuAD
LOZO
91.7
70.4
69.6
63.5
89.0
84.9
LOZO-M
92.5
73.6
69.6
64.4
90.0
83.3
Table 9: Comparison the performance LOZO momentum variant on OPT-13B.
RTE
MultiRC
Task
Memory
Consumed GPUs
Memory
Consumed GPUs
LOZO
27.0 GB
1x A800
26.9 GB
1x A800
LOZO-M
27.4 GB
1x A800
27.3 GB
1x A800
MeZO
27.4 GB
1x A800
27.3 GB
1x A800
MeZO-M
51.7 GB
1x A800
52.1 GB
1x A800
FT-LoRA
79.0 GB
1x A800
102,4 GB
2x A800
FT
250.0 GB
A800
315.2 GB
4x A800
Table 10: Comparison of memory costs for LOZO, McZO, their momentum variants, and gradient-basee based
methods on OPT-13B.
25

---

Published as a conference paper at ICLR 2025
In Table 10 evaluate the minimum memory requirements for two datasets OPT-13B, set- ting the per-device batch size to to determine the minimum hardware requirements for running the model with different optimization algorithms. The results demonstrate that LOZO exhibits the lowest memory consumption, particularly when compared to FO methods. Notably, the momentum- enhanced I.7O0 variant (LO77-M) incurs minimal additional memory overhead, unlike its coun- terpart, McZO-M, which requires significantly more memory.
In Figure [ we compare the convergence rates of our proposed LOZO algorithm with MeZO on two additional tasks. We also present a comparison of wall-clock times on GPUs. Despite having similar computational complexities, LOZO converges faster than McZO, resulting in reduced wall- clock time.
Ma20
M+20
LOZO
Dooe
LO20
LOZO
Figure 5: Top: Loss curves with respect to epochs for OPT-13B (SST2) and OPT-30B (Copa), Bottom: Loss curves with respect time for the same configurations.
LLaMA-7B
LLaMA-13B
LLaMA-70B
Task
SST-2
WiC
COPA
SQUAD
WG
SST-2
WG
WG
LOZO
94.8
57.2
85.0
90.3
66.0
93.6
67.6
72.1
MeZO
91.6
56.3
86.0
90.0
64.3
92.1
67.2
72.1
FT-LoRA
95.1
69.4
84.0
91.2
70.9
95.5
76.6
50.4
FT
94.2
72.3
83.0
90.6
64.4
96.4
73.3
Table 11: Experimental results on LLaMA models of varying sizes. The superior results achieved by methods are highlighted bold. "WG" refers to the WinoGrande dataset. Due to limited computational resources, FT was not tested on LLaMA-70B.
LLaMA-7B
LLaMA-70B
Task
Memory
Consumed GPUs
Memory
Consumed GPUs
LOZO
14.1 GB
1x A800
135.5 GB
2x A800
MeZO
14.3 GB
1x A800
136.0 GB
2x A800
FT-LORA
32.7 GB
1x A800
187.2 GB
3x A800
FT
281.6 GB
4x A800
640 + GB
> 8x A800
Table 12: Comparison of memory costs for LOZO, McZO, and gradient- based methods on LLaMA models of varying scales for the MultiRC task with per-device batch size of 1. Due limited computational resources, the results for FT LLaMA 70B are approximate.
26

---

Published as a conference paper at ICLR 2025
D.3 LLAMA EXPERIMENTS
We conducted experiments on the LLaMA model of varying sizes, comparing our proposed LOZO algorithm with MeZO and gradient-based algorithms. The results, presented in Table 1T strate that our algorithm outperforms MeZO on most tasks.
demon-
In Table 12 we compare the memory requirements of LOZO. MeZO, and gradient- based methods with a per-device batch size of 1 for fine-tuning LLaMA-7B and LLaMA-70B models on the Mul- tRRC dataset. The results demonstrate that as the model scale increases, the memory efficiency gap between ZO and gradient-basse methods widens significantly.
27


Reviews:
[{"review_id": "WcZiIjcysI", "reviewer": "Reviewer_DRFS", "summary": "The paper introduces low-rank zeroth-order optimization algorithms, called LOZO and LOZO-M, for memory-efficient fine-tuning of large language models (LLM). The authors claim that by utilizing a low-rank unbiased gradient estimator, LOZO and LOZO-M perform comparably to first-order (FO) methods while outperforming existing zeroth-order (ZO) approaches in term of memory and accuracy. The paper provides convergence guarantees and extensive experimental results to support these claims.", "questions": "1. Could you provide direct comparisons with FFT and FT-LORA in term of memory usage? This would strengthen your claim of LOZO's memory efficiency relative to FO methods.\n\n2. How do LOZO and LOZO-M perform on tasks beyond SuperGLUE, especially ones tailoring to long-context? This would demonstrate their adaptability and robustness across various applications, and their ability to handle long-context.\n\n3. How do LOZO and LOZO-M perform on different models, especially larger ones? This benchmark would further provide insights into their scalability.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a novel algorithm to addresses a critical limitation of ZO methods which is the inability to capture low-rank gradient structures effectively. The application of momentum without substantial memory overhead is innovative. These features are valuable for fine-tuning LLMs in memory-constrained environments. LOZO and LOZO-M achieves comparable performance to traditional FO FFT methods and outperforms existing ZO methods shows that the proposed algorithms can be viable alternatives to widely used FO approaches. The rigorous convergence provides valuable insights into the understanding of LOZO.", "weaknesses": "The paper lacks direct memory comparisons with full fine-tuning (FFT) and FT-LoRA methods. This weakens the claim that LOZO and LOZO-M outperforms FO approaches in term of memory efficiency.\n\nFurthermore, the paper primarily focuses on SuperGLUE benchmarks which is limited. Expanding experiments to more tasks would help demonstrate the generalizability of LOZO across different NLP tasks.\n\nNext, one of the main claims of the paper is the ability of LOZO's to handle long-context tasks. However, focusing on SuperGLUE benchmarks only doesn't support this claim.\n\nFinally, testing LOZO and LOZO-M on different types of models, especially, larger models would provide a stronger case for their scalability. Currently, the authors only test the proposed methods on one model family.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iat8rXEwRH", "reviewer": "Reviewer_MNxM", "summary": "The authors propose a novel zeroth-order optimization method for fine-tuning. The proposed method consumes significantly less memory while maintaining (and sometime even improving) the quality when compared with other FT methods including MeZO (another zeroth order method), ICL and LoRA methods. The core contribution is the \"lazy sampling strategy\" where the perturbation matrix for gradient estimation is sampled over several training steps, rather than each iteration. This ensures that the model sufficiently explores low rank sub space, without abrupt changes in the parameters at each iteration step. Extensive Experimentation on large scale OPT models show the efficacy of the approach.", "questions": "1) Line 268-269. Is there a justification for the chose hyper-parameter values of N and r? Are there ablation results for the same?\n2) Figure 3 : Are there loss curves for other datasets at 13B and 30B scale to understand the scaling behavior?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1) Well motivated approach, clearly outlines the shortcoming of other zeroth order approaches, like MeZO.\n2) Proposed algorithm is well written, clear and the core concepts are presented well. The \"lazy sampling strategy\" is novel and interesting. \n3) The paper proposes momentum variant and provides convergence analysis by interpreting LOZO as subspace optimization method by employing ZO gradient estimator.\n4) Extensive experiments on both medium scales and large scale LLMs are convincing in terms of quality gains and memory savings.", "weaknesses": "1) The experiments are performed on OPT based LLMs. It would be good to see what kind of memory savings and quality improvements the method gets on SoTA models like Llama.\n2) Additionally, the LLM evaluations are not exhaustive and lack eval suites around critical benchmarks around reasoning, MATH, Instruction following etc. \n3) An Ablation study on hyper-parameter choices for N and r for critical evals maybe helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mMVkFTwcUW", "reviewer": "Reviewer_4TZ5", "summary": "The manuscript presents a approach to parameter-efficient fine-tuning (PEFT) of large language models (LLMs) using zeroth-order (ZO) optimization. The authors propose a low-rank ZO gradient estimator and introduce a new algorithm called LOZO, which captures the low-rank gradient structure common in LLM fine-tuning. The paper provides convergence guarantees for LOZO, frames it as a subspace optimization method, and demonstrates its effectiveness through extensive experiments across various model sizes and downstream tasks.", "questions": "Questions:\n\n1. How do the memory savings of LOZO when applied to larger models and datasets, such as OPT-13B or Llama-70B?\n\n2. Have there been any experiments conducted to assess the impact of this fine-tuning method on the complex capabilities of LLMs, such as instruction following and reasoning?\n\n3. Are there any experiemnts to demonstrate the improvements in  speed of training and convergence when comparing LOZO with current methods?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1. theoretical guarantees: The manuscript introduces a low-rank ZO gradient estimator and algorithm (LOZO) that addresses the memory inefficiency issue associated with traditional first-order fine-tuning methods for LLMs.\n\n2. Clear Structure and Writing: The manuscript is well-organized, with a clear presentation of the problem, methodology, experiments, and results.", "weaknesses": "Weaknesses:\n\n1. **Marginal improvements for memory**: While the manuscript emphasizes the superior memory efficiency of the LOZO algorithm over MeZO, the proposed advantage is not convincingly demonstrated. The potential improvements in memory usage could be predominantly attributed to MeZO's zeroth-order optimization approach, with LOZO offering only marginal enhancements. As illustrated in Table 1, the memory usage is reduced from a range of approximately 3 to 7.42 GB for MeZO to 2.84 GB for LOZO, which does not present a substantial difference to assert the claimed memory efficiency advantage of LOZO. \n\n2. **Experiments insufficient**: Furthermore, the study's benchmark does not encompass key capabilities of LLMs, such as common sense reasoning (MMLU) and complex reasoning tasks (GSM8k). There is a concern that this proposed fine-tuning approach might not effectively enhance the LLM's high-level cognitive abilities.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FDqbaSpTDU", "reviewer": "Reviewer_FzN7", "summary": "The paper studies the way to improve the performance of zeroth-order fine-tuning by doing perturbation in a low-rank space. The paper provide detailed theoretical proof for the convergence of the proposed algorithm and experimental results with similar setup as the previous ZO fine-tuning paper on model up to 30B.", "questions": "My main questions are listed in the weakness section, here is a few of additional concerns:\n- For Fig. 3, I have similar confusion about the total training steps. From my understanding, LOZO has an additional interval in each epoch. So LOZO has more training steps actually?\n- I would appreciate it if the author could provide an evaluation loss vs. wall-time figure to demonstrate the effectiveness of the proposed method. Specifically, this would validate that the low-rank perturbation helps improve convergence speed with respect to training time, which is more critical than the number of training steps.\n- The improvement in experiments is limited, considering the large variance of ZO method even between runs with different random seeds.\n- How about LoZO-M perform on the large-scale model, just curious. I understand this is not the main purpose of your work and wondering if the momentum is becoming less important on large-scale models due to the large variance of ZO estimation.\n\n\nGenerally, I think this paper provides a solid method to improve the convergence of the ZO method. Further, clarifying experiments and including more discussion may benefit the reader of this paper.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The method proposed in this paper is interesting, which is inspired by the work on gradient low-rank structure. Also, the lazy sampling and LOZO-M methods are interesting to be considered. I quickly went through the proof for the convergence rate and it seems correct and reasonable, which provide solid support for the new subspace and lazy sampling method proposed in this paper.", "weaknesses": "Given the good theoretical foundation of this paper, my main concerns are about the parts of the experiment:\n- I'm a bit confused about the total training steps for LoZO and other baselines like MeZO in the experiments. For example, in Figure 2, I'm not sure if the k represents epoch here as mentioned in the previous section, or similar to the MeZO paper, represents the number of shots. Also, I'm wondering what the total number of training steps here for LoZO and MeZO? Furthermore, it seems LOZO uses a different learning rate compared with MeZO, according to Table 4, which may make the comparison unfair. \n\n- Still, for Fig. 2, I'm wondering why the MeZO-LoRA is performing worse than MeZO, as fewer trainable parameters should improve the ZO convergence rate according to the eq. (18) in the draft. I have extra two concerns here. First, this is different from the observation in Table 18 of MeZO paper, where MEZO-LoRA is performing better in most cases Second, I think it's reasonable that MEZO-LoRA fails to help on model larger than maybe 1B, where there are a lot of trainable parameters even with LoRA. But for small-size models like Roberta, MeZO-LoRA is reasonable to perform better with only 0.8 M parameters needing to be optimized. I would appreciate if the author could further explain this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)