Simultaneous Computation and Memory Efficient Zeroth-Order Optimizer for Fine-Tuning Large Language Models

## Abstract

Abstract Fine-tuning is powerful for adapting large language models to downstream tasks, but it often results in huge memory usages.
A promising approach to mitigate this is using Zeroth-Order (ZO) optimization, which estimates gradients to replace First-Order (FO) gradient calculations, albeit with longer training time due to its stochastic nature.
By revisiting the Memory-efficient ZO (MeZO) optimizer, we discover that the full-parameter perturbation and updating processes consume over 50% of its overall fine-tuning time cost.
Based on these observations, we introduce a novel layer-wise sparse computation and memory efficient ZO optimizer, named LeZO.
LeZO treats layers as fundamental units for sparsification and dynamically perturbs different parameter subsets in each step to achieve full-parameter fine-tuning.
LeZO incorporates layer-wise parameter sparsity in the process of simultaneous perturbation stochastic approximation (SPSA) and ZO stochastic gradient descent (ZO-SGD).
It achieves accelerated computation during perturbation and updating processes without additional memory overhead.
We conduct extensive experiments with the OPT model family on the SuperGLUE benchmark and two generative tasks.
The experiments show that LeZO accelerates training without compromising the performance of ZO optimization.
Specifically, it achieves over 3 × 3\times 3 × speedup compared to MeZO on the SST-2, BoolQ, and Copa tasks.

## 1 Introduction

Large language models (LLMs) have shown remarkable capabilities in understanding and generating languages, and have been widely adopted in various applications (Brown et al., ; Wei et al., ; Rao et al., ; Wang et al., ).
To effectively adapt LLMs to downstream tasks, full-parameter fine-tuning has become crucial (Li & Liang, ; Lester et al., ; Hu et al., ; Malladi et al., ).
However, as the scale of LLMs continues to increase, the memory usage and computational cost of fine-tuning also escalate (Kaplan et al., ; Hoffmann et al., ), posing a significant challenge to the practical application of LLMs.

To address these challenges, researchers have proposed efficient fine-tuning methods, which can be categorized into forward-backward (Li & Liang, ; Hu et al., ; Ding et al., ; Pu et al., ; Xu et al., ) and forward-only (Zhang et al., ; Liu et al., ; Guo et al., ) approaches.
Forward-backward methods typically use First-Order (FO) optimizers (Robbins & Monro, ; Kingma & Ba, ), updating either partial model parameters or introducing small trainable modules to reduce memory usage.
However, the performance of these methods can hardly match full-parameter fine-tuning.
Dynamic update schemes (Brock et al., ; Liu et al., ; Pan et al., ) address this problem by dynamicly changing learnable parameter subsets, but they still require caching many activations.
In contrast, forward-only methods utilize Zeroth-Order (ZO) optimizers, which estimate gradients without back-propagation, thereby reducing the memory overhead associated with forward-backward methods.
Malladi et al. () first introduce a memory-efficient ZO optimizer (MeZO) for LLM fine-tuning.
ZO optimizers, however, exhibit higher stochasticity in gradient estimation compared to FO optimizers, and this stochasticity increases as the scale of tuned parameters grows (Wang et al., ; Balasubramanian & Ghadimi, ; Cai et al., ).
Consequently, MeZO requires significantly more computational cost than FO optimizers.

In this paper, we revisit MeZO and identify that its computational cost is primarily in the forward pass, perturbation, and updating stages.
Specifically, perturbation and updating account for over 50% of the total time when fine-tuning the OPT-13B model (Zhang et al., ) on the SST-2 task.
Simplifying these steps can accelerate MeZO.
One promising approach is to sparsify the tuned parameters,
which has been shown to be effective for FO optimization (Pan et al., ).

Inspired by these insights, we propose a layer-wise sparse and efficient zeroth-order optimizer (LeZO).
LeZO aims to improve computational efficiency without additional memory overhead.
We use layers as the basic unit of sparsity, dynamically updating the set of layers to be tuned at different fine-tuning steps.
We integrate this policy into Simultaneous Perturbation Stochastic Approximation (SPSA) and Zeroth-Order Stochastic Gradient Descent (ZO-SGD), which enables sparse ZO optimization through localized parameter perturbation and updating.
Over multiple steps, LeZO can achieve full-parameter fine-tuning.
LeZO accelerates computations because, during each step, the weights of untuned layers remain dense.
This allows us to skip perturbation and updating processes for those layers, thereby reducing floating-point computations.
Additionally, compared to MeZO, LeZO does not introduce extra memory overhead.
We employ a simple and efficient random selection strategy, avoiding the need for new parameter modules.

We evaluate our approach by fine-tuning models from the OPT family on the SuperGLUE benchmark (Wang et al., ), and the SQuAD (Rajpurkar et al., ) and DROP (Dua et al., ) datasets.
By sparsifying 75% of the layers and fine-tuning full-parameters, LeZO outperforms MeZO on most datasets across three model scales.
For instance, on the OPT-13B model, LeZO surpasses MeZO by an average of 1% in accuracy or F1 score across seven datasets.
When integrating the ZO optimizer with Parameter Efficient Fine Tuning (PEFT), LeZO exceeds MeZO on five datasets, highlighting the versatility and effectiveness of our sparsity scheme.
Additionally, LeZO achieves over $2\times$ computational acceleration across some tasks, with speedups increasing as layer sparsity exceeds 75%.
Finally, LeZO achieves over $3\times$ training acceleration for the OPT-13B model fine-tuning on the SST-2, BoolQ, and Copa datasets.

In summary, the contributions of this paper are as follows:

- •
We analyze the computational costs of MeZO during LLM fine-tuning and find that the perturbation and updating processes account for over 50% of the fine-tuning time cost.
- •
We propose a dynamic layer-wise sparse and efficient zeroth-order optimizer that effectively reduces computational cost in fine-tuning LLMs, and achieve faster convergence than MeZO.
- •
We evaluate LeZO on SuperGLUE and two generative tasks. This demonstrates its acceleration capability across different sparsity rates and showcases its performance improvement.

## 2 Related Work

Forward-Backward Fine-Tuning Optimziers
rely on the FO optimizer and compute gradients through derivation (Robbins & Monro, ; Kingma & Ba, ), which results in high memory usage.
One approach to handle this problem is Parameter-Efficient Fine-Tuning (PEFT) (Xu et al., ).
Relevant strategies involve adding trainable modules (Li & Liang, ; Hambardzumyan et al., ) or learnable input embeddings (Houlsby et al., ) to the model.
Moreover, the LoRA series (Hu et al., ; Dettmers et al., ) adopt low-rank decomposition to reduce the size of trainable modules.
However, recent studies show that partial fine-tuning cannot match the performance of full-parameter fine-tuning (Ding et al., ; Pu et al., ).
To handle this problem, some methods enable full-parameter fine-tuning by adjusting parameters in an interleaved fashion.
For example, LISA (Pan et al., ) updates parameters of different layers in different iterations based on layer importance.
Galore (Zhao et al., ) switches low-rank subspaces using the rank information while simultaneously modifying the learnable parameters.
These techniques still require storing the intermediate states of FO optimizers, resulting in significant memory overhead.

Forward-Only Fine-tuning Optimziers do not require back-propagation for gradient computation (Malladi et al., ; Zhang et al., ).
Malladi et al. () firstly introduce the ZO optimizer for LLMs fine-tuning, known as MeZO, which
significantly reduces memory costs.
Because MeZO employs SPSA to estimate gradients, it exhibits greater randomness compared to FO optimizers. Consequently, it requires more computational cost to converge.
To accelerate the convergence of MeZO, Sparse-MeZO (Liu et al., ) only updates model parameters with small values to enhance the effectiveness of ZO optimizer.
Nevertheless, this approach necessitates ranking parameter values and introduces a mask matrix;
therefore, it results in additional memory and computational overhead.
Guo et al. () reduced the number of learnable parameters to one-thousandth.
However, it requires cloud computation to provide first-order gradient of the objective function, which is unsuitable for more general scenarios.
In summary, how to effectively accelerate the convergence speed of ZO optimizers without incurring additional memory overhead still remains a challenge.

Our proposed LeZO adopts ZO optimization to update model parameters, reducing memory usage compared to forward-backward fine-tuning.
By employing a dynamic layer-wise sparsity strategy, LeZO significantly reduces the number of trainable parameters and minimizes the computational costs during the forward-only fine-tuning.
Thus, LeZO achieves high efficiency in both memory usage and computational cost.

## 3 Efficiency Analysis of MeZO

In this section, we first revisit the classical ZO gradient estimator SPSA (Spall, ) and the ZO optimizer ZO-SGD (Malladi et al., ).
Subsequently, we analyze the computational redundancy of MeZO (Malladi et al., ).

### 3.1 Preliminaries

SPSA approximates gradients for multi-parameter systems by applying random perturbations,
which eliminates the need of gradient back-propagation.
It iteratively optimizes parameters by estimating gradients based on differences in function values around a given point. SPSA does not require the function to be smooth or convex, but it generally converges slowly.

###### Definition 1 (Simultaneous Perturbation Stochastic Approximation, SPSA (Spall, 1992 ) ) .

Given a group of parameters ${\bm{\theta}}\in{\mathbb{R}}^{d}$ from a model and a loss function $\mathcal{L}$ used for optimization, SPSA estimates the gradient on a mini-batch of data ${\mathcal{B}}$ as follows:

$$ $\widehat{\nabla}{\mathcal{L}}({\bm{\theta}};{\mathcal{B}})=\frac{{\mathcal{L}} ({\bm{\theta}}+\epsilon{\bm{z}};{\mathcal{B}})-{\mathcal{L}}({\bm{\theta}}- \epsilon{\bm{z}};{\mathcal{B}})}{2\epsilon}{\bm{z}}\approx{\bm{z}}{\bm{z}}^{ \top}\nabla{\mathcal{L}}({\bm{\theta}};{\mathcal{B}}),$ (1) $$

where ${\bm{z}}\in{\mathbb{R}}^{d}$ with ${\bm{z}}\sim{\mathcal{N}}(0,{\bm{I}}_{d})$ and $\epsilon$ is a *perturbation scale*.

Malladi et al. () applied SPSA (Definition 1) to optimize LLMs, using it to obtain approximate gradients of parameters.
They modified the SGD algorithm (Robbins & Monro, ), creating ZO-SGD (Definition 2), which incorporates ZO differential gradients to update model parameters.
MeZO employs both SPSA and ZO-SGD, and performs two forward passes in a single optimization step without caching the activation information of the parameters. Therefore, it reduces memory usage to the size occupied by the model parameters alone.

###### Definition 2 (Zeroth-Order Stochastic Gradient Descent, ZO-SGD (Malladi et al., 2023 ) ) .

Given a learning rate $\eta$ and a group of parameters ${\bm{\theta}}\in{\mathbb{R}}^{d}$, the parameters at time $t$ can be updated using the SPSA gradient estimate as follows:

$$ ${\bm{\theta}}_{t+1}={\bm{\theta}}_{t}-\eta\widehat{\nabla}{\mathcal{L}}({\bm{ \theta}};{\mathcal{B}}_{t}),$ (2) $$

where ${\mathcal{B}}_{t}$ is the mini-batch of data used at time $t$.

###### Definition 1 (Simultaneous Perturbation Stochastic Approximation, SPSA (Spall, 1992 ) ) .

###### Definition 2 (Zeroth-Order Stochastic Gradient Descent, ZO-SGD (Malladi et al., 2023 ) ) .

### 3.2 Efficiency dilemma of MeZO

Figure: Figure 2: Proportion of computational time cost for each operation in a single step when fine-tuning the OPT-13b model on the SST-2 dataset using MeZO.
Refer to caption: x2.png

Fine-tuning LLMs with MeZO is extremely time-consuming.
It often takes hundreds or even thousands of times longer than using FO optimizers like SGD (Robbins & Monro, ) and Adam (Kingma & Ba, ).
We break down the MeZO computation process into three stages: forward pass, perturbation, and updating.
Algorithm 1 explains the computational operations for each of these stages.
Figure 2 illustrates their relative time cost in an optimization step.

Surprisingly, in classification tasks, the parameter perturbation and updating stages account for more than one half of the overall time.
A common method to reduce the computational burden during optimization is to skip the calculations of certain modules (Fan et al., ).
However, this approach typically introduces an inherent error during the forward pass (Evans & Aamodt, ).
This phenomenon is challenging to mitigate and usually slows down the convergence rate.
An alternative strategy is to selectively optimize the parameters of specific modules during the updating stage. Many studies have substantiated the efficacy of this strategy in FO optimization (Liu et al., ; Mi et al., ; Pan et al., ; Zhao et al., ).
The above observations motivate us to implement sparse perturbation and updating for MeZO.

## 4 Methodology

In this section, we present the implementation details of LeZO.
We explain how it achieves convergence and computation acceleration without additional memory consumption by updating only a subset of structured parameters during each optimization step.

### 4.1 Dynamic Layer-wise Sparse Zeroth-Order Optimization

Building upon Equation 1, we apply structured pruning to the model parameter vector ${\bm{\theta}}$.
In each iteration, we partition this vector into two distinct parts.
We introduce a sparse function $\mathcal{R}$ to extract sub-vectors from the input vector and stipulate this partitioning is structured by layer.
Given a sparse rate $\rho$ ($0\leq\rho\leq 1$), a parameter vector ${\bm{\theta}}$, and a random number $s$,
we obtain a new parameter vector ${\bm{\theta}}^{\prime}\in\mathbb{R}^{\rho d}$, which is mathematically represented as:

$$ ${\bm{\theta}}^{{}^{\prime}}={\mathcal{R}}({\bm{\theta}},\rho,s_{t}).$ (3) $$

In each step, we maintain the number of elements in ${\bm{\theta}}^{\prime}$. The random seed $s_{t}$ is used to determine which layers’ parameters are selected to form ${\bm{\theta}}^{\prime}$.

###### Definition 3 (Layer-wise Sparse SPSA) .

During each step, the sparse parameter set is used as a condition for differential calculation in SPSA, which is defined as follows:

$$ $\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}};{\mathcal{B}})= \frac{{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}};{\mathcal{B}} )-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^{{}^{\prime}};{\mathcal{B}})}{2 \epsilon}{\bm{z}}^{{}^{\prime}},$ (4) $$

where ${\bm{z}}^{{}^{\prime}}=\mathcal{R}({\bm{z}},\rho,s_{t})$.

Furthermore, incorporating layer-wise sparsity into ZO-SGD results in:

###### Definition 4 (LeZO-SGD) .

At time $t$, ${\bm{\theta}}$ can be updated using the layer-wise sparse SPSA gradient estimation as:

$$ ${\bm{\theta}}^{{}^{\prime}}_{t+1}={\bm{\theta}}^{{}^{\prime}}_{t}-\eta\widehat {\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}};{\mathcal{B}}_{t}).$ (5) $$

Algorithm 1 presents the pseudocode for LeZO, employing a straightforward approach to implement the sparse function $\mathcal{R}$.
We use layers as the fundamental unit for sparsity (Fan et al., ).
By maintaining a subset $a$ to store pruned layers, these layers are skipped during perturbation and parameter updating processes.

Figure: Algorithm 1 LeZO (Layer-wise Sparse and Efficient Zeroth-Order Optimization)

###### Remark 1 .

As illustrated in Algorithm 1, it is evident that LeZO introduces a layer-wise selection operation $\mathcal{R}$ compared to MeZO.
Given the scale of parameters in the billions, this addition has a negligible computational impact.
We have the following remarks.
(1) During the Forward pass, LeZO’s computation aligns with MeZO, incurring no additional memory or computational overhead.
(2) During the perturbation process, we skip the parameter perturbation in the sparsified layers, thereby reducing the computational load.
Both LeZO and MeZO utilize a random seed for fixed perturbation $z$.
This approach eliminates the need for additional cache storage for perturbation information, thereby not increasing memory overhead. The same principle applies to the updating process.
Therefore, it is evident that LeZO reduces computational overhead through the introduction of layer-wise parameter sparsification during the perturbation and updating processes and incurs no additional memory overhead.

###### Definition 3 (Layer-wise Sparse SPSA) .

###### Definition 4 (LeZO-SGD) .

###### Remark 1 .

### 4.2 Convergence Analysis of LeZO

When examining the individual optimization steps, LeZO effectively updates a sub-network, similar to Sparse-MeZO (Liu et al., ).
We aim to demonstrate that as model parameters converge towards local optimal values,
there exists a value $\sigma^{2}$ such that the speed at which the loss approaches a local optimum is directly proportional to the number of parameters. This implies that the parameter convergence rate is related to $\rho$.

###### Lemma 1 (Unbiased Estimation of Sparse Gradient) .

Let ${\mathcal{L}}_{{\mathcal{R}}}=\mathbb{E}_{{\mathcal{R}}}[{\mathcal{L}}({\bm{
\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})]$.
The relationship between the model’s sparse gradient $\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}({
\bm{\theta}})$ and the estimated ZO sparse gradient $\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})$ can be expressed as:

$$ $\displaystyle\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})$ $\displaystyle={\mathcal{R}}(\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}) )=\nabla_{{\bm{\theta}}^{{}^{\prime}}}\mathbb{E}_{{\mathcal{R}}}[{\mathcal{L}} ({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})]$ (6) $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^{ {}^{\prime}})}{2\epsilon}{\bm{z}}^{{}^{\prime}}]=\mathbb{E}_{{\mathcal{R}}}[ \widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})].$ $$

From Lemma 1, we can see that the estimated gradient by sparse ZO is an unbiased estimation of the model’s sparse parameter gradient.

###### Assumption 1 (Lipschitz Continuous) .

Let $\nabla{\mathcal{L}}({\bm{\theta}};{\bm{x}})$ denotes the first-order gradient of ${\mathcal{L}}$ with respect to ${\bm{\theta}}$ at $x$. ${\mathcal{L}}$ satisfies Lipschitz continuity, then

$$ $\|\nabla{\mathcal{L}}({\bm{\theta}};{\bm{x}})-\nabla{\mathcal{L}}({\bm{\theta} }_{t};{\bm{x}})\|\leq\frac{L(l)}{2}\|{\bm{\theta}}-{\bm{\theta}}_{t}\|^{2},$ (7) $$

where $L(l)$ is a constant ensuring ${\mathcal{L}}$ satisfies Lipschitz continuity.

Assuming that the loss function ${\mathcal{L}}({\bm{\theta}};{\bm{x}})$ is Lipschitz continuous (1), we can calculate the norm distance between the sparse ZO estimated gradient and the true sparse gradient $\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})$.
This distance, denoted as $\|\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}(
{\bm{\theta}})-\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|$, helps establish their relationship using Lemma 1.

###### Lemma 2 (Relationship between Sparse Gradient and Estimate Value) .

Let the loss function ${\mathcal{L}}({\bm{\theta}};{\bm{x}})$ to be Lipschitz continuous. According to Minkowski inequality, we have

$$ $\|\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}\leq 2\|\widehat{ \nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta }})\|^{2}+\frac{\epsilon^{2}L^{2}(l)}{2}(\rho d+4)^{3},$ (8) $$

where $\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})={\mathcal{R}}(\nabla{
\mathcal{L}}({\bm{\theta}}))$.

Finally, we can obtain the convergence rate of LeZO.

###### Lemma 3 (Convergence of LeZO) .

Assuming a sequence of generated parameters $\{{\bm{\theta}}_{t}\}_{t\geq 0}$ in LeZO. We have

$$ $\mathbb{E}_{{\mathcal{R}},x}[\|\nabla_{{\bm{\theta}}}{\mathcal{L}}_{{\mathcal{ R}}}({\bm{\theta}}_{T})\|^{2}]\leq\sigma^{2}$ (9) $$

for any $T={\mathcal{O}}(\frac{\rho dL}{\sigma^{2}})$. $t$ represents the step of fine-tuning and $L(l)\leq L$ for all ${\mathcal{L}}({\bm{\theta}}_{t})$.

From Lemma 3, it is apparent that as the sparsity ratio $\rho$ decreases, the upper bound on the time required to converge to the expected value also decreases.
Hence, parameter sparsity and the smoothness of the objective function can enhance the convergence speed.

**Table 1: Experiments on the OPT-13b model. SSZO sparsifies 75% of the layers (30 layers out of 40). Two A100-40G GPUs are used for BoolQ and SQuAD tasks.**
| Task | SST-2 | RTE | CB | BoolQ | WSC | WIC | Copa | SQuAD | AVG. |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Task type | ———————- classification ———————- | multiple choice | generation |  |  |  |  |  |  |
| Zero-Shot | 58.8 | 59.6 | 46.4 | 59.0 | 38.5 | 55.0 | 80.0 | 46.2 | 55.4 |
| ICL | 87.0 | 62.1 | 57.1 | 66.9 | 39.4 | 50.5 | 87.0 | 75.9 | 65.7 |
| FT (12$\times$ memory) | 92.0 | 70.8 | 83.9 | 77.1 | 63.5 | 70.1 | 79.0 | 84.9 | 77.7 |
| MeZO (Malladi et al., ) | 91.4 | 66.1 | 67.9 | 67.6 | 63.5 | 61.1 | 88.0 | 84.7 | 73.8 |
| MeZO (Reproduce) | 91.1±0.1 | 70.8±1.4 | 68.8±1.8 | 69.1±0.6 | 63.5±1.2 | 58.7±0.9 | 87.0±1.6 | 84.2±1.0 | 74.2±1.1 |
| SSZO | 93.0±0.3 | 71.4±2.1 | 69.2±1.7 | 74.3±0.8 | 62.7±0.4 | 60.7±1.5 | 87.2±0.8 | 84.3±0.7 | 75.4±1.1 |

###### Lemma 1 (Unbiased Estimation of Sparse Gradient) .

###### Assumption 1 (Lipschitz Continuous) .

###### Lemma 2 (Relationship between Sparse Gradient and Estimate Value) .

###### Lemma 3 (Convergence of LeZO) .

## 5 Experiments

In this section, we present extensive experiments to validate the effectiveness of the LeZO algorithm.

### 5.1 Experimental Setting

Models and Datasets.
To evaluate the efficacy of LeZO, we follow the validation methodology by Malladi et al. ().
We conduct experiments on the OPT model family (Zhang et al., ) at various scales: 1.3 billion, 13 billion, and 30 billion parameters, with 32, 40, and 48 Transformer blocks, respectively.
These models utilize the core components of the Transformer architecture (Vaswani et al., ), including self-attention mechanisms, feed-forward neural networks, residual connections, and layer normalization within each block.
For downstream tasks, we use the SuperGLUE benchmark (Wang et al., ), which includes classification tasks, multiple-choice tasks, and two question-answering tasks.

**Table 3: Experiments on the OPT-30b model. LeZO sparsifies 75% of the layers (36 layers out of 48). We report the best results of MeZO and MeZO with prefix from the paper of Malladi et al. (). Two A100-40G GPUs are used for SST2, and four for BoolQ.**
| Task | SST-2 | BoolQ |
| --- | --- | --- |
| zero-shot | 56.7 | 39.1 |
| ICL | 81.9 | 66.2 |
| MeZO/MeZO (prefix) | 90.6 | 73.5 |
| MeZO (reproduce) | 90.3±0.5 | 69.5±0.4 |
| LeZO | 92.8±0.6 | 73.7±0.9 |

Methods.
We utilize zero-shot and 32-shot In-Content Learning (ICL) (Brown et al., ) alongside fine-tuning with Adamw (FT) as comparison.
To demonstrate LeZO’s ability to accelerate model convergence and reduce time cost per training step without additional memory costs, we compared it with MeZO (Malladi et al., ).
In addition to full-parameter fine-tuning, we integrate LeZO with two PEFT methods: LoRA (Hu et al., ) and prefix tuning (Li & Liang, ), to further enhance fine-tuning efficiency.

Hyper-parameters.
We follow most of the experimental settings used in MeZO, including configurations for LoRA and prefix tuning, and methods for selecting training and testing data.
We conduct a grid search for the learning rate and perturbation scale to identify the optimal parameters for each experimental group.
We use the experimental code for ZO optimization provided by Zhang et al. () and set the validation steps to 2000.
Experiments are conducted on an A100-40G GPU.
However, due to its memory limitations compare to the A100-80G GPU used by Malladi et al. (), we employ a multi-card parallel strategy for fine-tuning the OPT-13b and 30b model on certain downstream tasks to ensure parameter consistency.
We select the final model based on the checkpoint with the lowest validation loss.
All numerical results report in the experiments are reproduced.
We conduct parameter fine-tuning experiments using five different random seeds, reporting the average and standard deviation of these results.
Detailed settings are provided in Appendix A.
Unless otherwise specified, all baseline experiments are conducted using the OPT-13b model with 75% sparsity (30 out of 40 layers).

**Table 4: Fine-tuning performance of the ZO optimizer with PEFT. †indicates the results reported in the paper of Malladi et al. (). LeZO (LoRA/prefix) outperforms MeZO (LoRA/prefix) on 4 out of 5 tasks. LeZO (LoRA) sparsifies 50% of layers, while LeZO (prefix) sparsifies 75%.**
| Task | SST-2 | CB | BoolQ | Copa | SQuAD |
| --- | --- | --- | --- | --- | --- |
| MeZO (LoRA)† | 89.6 | 66.1 | 73.8 | 84.0 | 83.8 |
| MeZO (LoRA) | 90.6±1.6 | 70.4±1.6 | 71.8±1.2 | 86.0±1.2 | 81.1±0.8 |
| MeZO (prefix)† | 90.7 | 69.6 | 73.1 | 87.0 | 84.2 |
| MeZO (prefix) | 90.7±0.9 | 67.9±2.5 | 73.2±0.4 | 87.4±1.7 | 83.3±1.0 |
| LeZO (LoRA) | 92.3±0.5 | 71.1±0.8 | 73.7±0.8 | 86.4±1.5 | 81.5±1.1 |
| LeZO (prefix) | 92.1±0.7 | 69.7±2.5 | 74.5±0.6 | 87.6±1.1 | 83.1±0.4 |

Figure: Figure 3: Impact of learning rate and sparsity ratio on fine-tuning models using LeZO on the SST-2 task. Results with accuracy exceeding 90% are displayed. Experiments were conducted with a single random seed. “Dropout Number” indicates the number of sparse layers in the OPT 13B model. To enhance clarity, the learning rates are logarithmically scaled. The curves mapping onto the straight lines in the lower plane are used to illustrate the range of learning rates that lead to improved performance after sparsifying different numbers of layers in the model. The performance of MeZO performance is the red line.
Refer to caption: x3.png

### 5.2 Main Result

Comparison between LeZO and Other Methods.
LeZO outperforms both non-training methods and MeZO, and surpasses the FO optimizer on some tasks.
Table 2 presents a comparison between LeZO and the baseline methods such as zero-shot, the training-free method (ICL), Fine-Tuning (FT) with AdamW for FO optimization, and MeZO across various downstream tasks. We obtain the following observations.
1) LeZO significantly outperforms non-training methods such as zero-shot and ICL on all tasks.
This demonstrates LeZO’s superior convergence capabilities during training.
2) LeZO surpasses MeZO in 7 out of 8 tasks, with an average improvement exceeding 1% across all tasks.
Notable enhancements are observed on the SST-2, BoolQ, and WIC datasets, with average accuracy increases over 2% across five experiments.
This indicates that layer-wise sparsity schemes can effectively accelerate convergence.
However, there is a slight performance degradation on the WSC task compared to MeZO, likely due to the inherent instability of ZO optimization methods and MeZO’s sensitivity to prompts.
It is speculated that LeZO may inherit these drawbacks, as the fundamental differential gradient computation process in SPSA remains unchanged.
3) LeZO marginally outperforms FT on the SST-2, RTE, and Copa datasets, while demonstrating comparable performance on the other datasets.
Notably, LeZO and MeZO have the same memory consumption, and FT incurs a memory cost twelve times higher than LeZO.

Performance on Multi-Size Models.
LeZO achieves a notable performance improvement over MeZO across models of varying scales.
Tables 2 and 3 display the performance of LeZO and other methods on the OPT-1.3b and OPT-30b models, respectively.
When fine-tuning OPT-1.3b on downstream tasks, LeZO achieves superior results in 9 out of 11 tasks.
It achieves comparable results on the WSC task and its performance drop is less than 1% on RTE.
When fine-tuning OPT-30b on the SST-2 and BoolQ datasets, LeZO demonstrates significant improvements compared to MeZO.
The experiments across Tables 2, 2, and 3 reveal that LeZO achieves more pronounced performance gains on larger LLMs.
This phenomenon may relate to the stability of model convergence, with larger models being more stable. Additionally, LeZO demonstrates greater stability compared to MeZO.

Figure: Figure 5: Comparison in computation efficiency between LeZO and MeZO on various tasks.
Refer to caption: x5.png

Performance of Combining ZO optimizer and PEFT.
LeZO can be effectively integrated with PEFT methods.
We combine ZO optimizers with PEFT by updating the trainable parameters introduced by PEFT across different methods.
Table 4 showcases the fine-tuning results of LeZO and MeZO combined with the PEFT across different datasets.
LeZO (LoRA) outperforms MeZO (LoRA) on all five datasets, while LeZO (prefix) outperforms MeZO (LoRA) on 4 out of 5 datasets.
Additionally, the combination of LeZO with PEFT results in performance improvements exceeding 1% on the SST-2, CB, and BoolQ tasks compared to MeZO.
This indicates that LeZO enhances fine-tuning effectiveness even when combined with PEFT.

Convergence and Computation Speedup by LeZO.
LeZO is more efficient than MeZO.
Figure 1 illustrates the variation in accuracy on the test set when fine-tuning OPT-13b using LeZO on the SST-2 datasets.
LeZO achieves $2\times$ computation speedup and $1.7\times$ convergence speedup.
In Figure 5, we present the convergence and computation speedups obtained when using LeZO to fine-tune OPT-13b on eight downstream tasks.
The experimental results show that with the layer-wise sparsity policy, LeZO achieves effective convergence and computation speedups.
In conclusion, LeZO achieves more efficient LLM fine-tuning than MeZO.

### 5.3 Hyperparameter Analysis

Influence of Learning Rate and Sparsity Rate.
The layer-wise sparsity scheme we use shows how the number of sparse layers affects LeZO’s performance.
Our experiments show that with an increase in sparsity rate (more layers being sparsified), the ZO optimization process needs a higher learning rate.
Figure 4 illustrates the relationship between the sparsity rate (Dropout Number), learning rate, and model accuracy on downstream tasks. From the figure, we obtain several key observations:
1) LeZO demonstrates significantly superior optimization effectiveness compared to MeZO (Dropout Number=0).
Under full-parameter fine-tuning, LeZO consistently outperforms MeZO regardless of the number of sparsified layers.
2) LeZO enhances the robustness of the ZO optimization process.
Comparing the lengths of the dashed lines, it can be observed that as the sparsity ratio increases, the range of learning rates that achieve over 90% accuracy on the SST-2 task expands.
This indicates that the robustness of LeZO improves with an increased sparsity ratio.
3) The behavior of LeZO markedly differs from fine-tuning only a subset of parameters.
Performance experiences a substantial decline when the sparsity rate reaches $\rho=1$ (sparse 40 layers in OPT-13b, while fine-tuning solely the embedding and linear layers).

Figure: Figure 6: The relationship between the length of input tokens and the computational speedup achieved by LeZO.
Refer to caption: x6.png

Impact of Downstream Tasks on Computational Speedup.
LeZO achieves varying speedup ratios across different tasks, as shown in Figure 5, which depicts the computation and convergence speedup ratios obtained by LeZO across all tasks.
The differences in computational speedup ratios come from the varying proportions of the forward propagation process within the total computation.
The speed of forward propagation depends on the average token length of different tasks within the same model framework.
Figure 6 illustrates the relationship between the average input token length of different datasets and the computational speedup achieved by LeZO.
When input token length increases, computation speedup decreases.
With a constant sparsity ratio, LeZO’s floating-point computational savings per downstream task remain fixed.
Consequently, LeZO’s computation acceleration is more suited for relatively straightforward training samples.
However, a similar trend is not observed in the convergence acceleration of LeZO across different tasks.
This disparity may be attributed to the varying difficulty levels of tasks, their convergence characteristics, and the distributions of training and extracted testing sets.

## 6 Conclusion

In this study, we introduce LeZO, a layer-wise sparse and efficient ZO optimizer for fine-tuning LLMs.
We integrate the layer-wise pruning scheme into the ZO optimization process,
which achieves both computation and convergence speedups in LLMs training without additional memory costs.
Moreover, LeZO combines effectively with existing PEFT methods to further enhance acceleration.
We conduct fine-tuning experiments on models from the OPT family using the SuperGLUE benchmark and two question-answering datasets.
Empirical results show that LeZO significantly reduces training time and improves performance.
Overall, LeZO provides an efficient and effective approach to ZO fine-tuning.
It reduces the computational load caused by full-parameter perturbations in zeroth-order optimization without introducing additional memory overhead.

## Appendix A Detailed Experimental Settings

We aligned the hyperparameter configurations for our primary experiments with the standards set by MeZO, as described by Malladi et al. ().
Our experimental framework is based on the work of Zhang et al. ().
Our approach incorporates a sparsity rate in LeZO.
Our experiments indicate that this requires larger learning rates to enhance model convergence.
Consequently, the grid search ranges for learning rates differ between LeZO and MeZO in the experiments presented in Table 2, 2, 3, and 4.
We strictly adhered to the settings outlined by Malladi et al. () when replicating MeZO experiments.
The hyperparameter search ranges for grid search are detailed in Table 5.
We conducted five trials with fixed random seeds for each set of experiments to compute average results and standard deviations.
This facilitated a robust comparison of the efficiency of different methods. In the experiments depicted in Figure 4, due to the extensive number of trials, we conducted a single experiment with one random seed to obtain results under various hyperparameter settings.
To streamline the evaluation process without compromising the representation of convergence across diverse models and datasets, we set the testing interval at 2000 steps.
The convergence behavior of LeZO is contingent upon that of MeZO and is influenced by prompts; therefore, we did not conduct prompt removal experiments similar to those in MeZO.
The prompts used in the experiments are identical to those in MeZO.

**Table 5: The hyperparameter grids used for the experiments. Weight decay is set to 0 0. FT uses 5 epochs and linear scheduled learning rates. ZO optimizers use $20$K steps and constant learning rates. We check validation performance and save the best checkpoint every 1/10 total training steps (2K).**
| Experiment | Hyperparameters | Values |
| --- | --- | --- |
| LeZO | Batch size | $16$ |
|  | Learning rate | $\{1\mathrm{e}{-6},7\mathrm{e}{-7}\}$ for OPT-13b/30b, $\{3\mathrm{e}{-6},1\mathrm{e}{-6}\}$ for OPT-1.3b |
|  | $\epsilon$ | $1\mathrm{e}{-3}$ |
|  | Sparse Rate | 0.75 |
| MeZO | Batch size | $16$ |
|  | Learning rate | $\{1\mathrm{e}{-6},1\mathrm{e}{-7}\}$ or $\{1\mathrm{e}{-6},5\mathrm{e}{-7},1\mathrm{e}{-7}\}$ for RTE and SQuAD |
|  | $\epsilon$ | $1\mathrm{e}{-3}$ |
| LeZO (prefix) | Batch size | $16$ |
|  | Learning rate | $\{3\mathrm{e}{-2},1\mathrm{e}{-2}\}$ |
|  | $\epsilon$ | $1\mathrm{e}{-1}$ |
|  | Sparse Rate | 0.75 |
|  | # prefix tokens | $5$ |
| MeZO (prefix) | Batch size | $16$ |
|  | Learning rate | $\{1\mathrm{e}{-2},1\mathrm{e}{-3}\}$ or $\{5\mathrm{e}{-2},1\mathrm{e}{-2},5\mathrm{e}{-3}\}$ for SQuAD |
|  | $\epsilon$ | $1\mathrm{e}{-1}$ |
|  | # prefix tokens | $5$ |
| LeZO (LoRA) | Batch size | $16$ |
|  | Learning rate | $\{3\mathrm{e}{-5},5\mathrm{e}{-5},7\mathrm{e}{-5}\}$ |
|  | $\epsilon$ | $1\mathrm{e}{-2}$ |
|  | Sparse Rate | 0.50 |
|  | $(r,\alpha)$ | $(8,16)$ |
| MeZO (LoRA) | Batch size | $16$ |
|  | Learning rate | $\{1\mathrm{e}{-4},5\mathrm{e}{-5}\}$ or $\{1\mathrm{e}{-4},5\mathrm{e}{-5},1\mathrm{e}{-5}\}$ for SQuAD |
|  | $\epsilon$ | $1\mathrm{e}{-2}$ |
|  | $(r,\alpha)$ | $(8,16)$ |
| FT with Adam | Batch size | $8$ |
|  | Learning Rate | $\{1\mathrm{e}{-5},5\mathrm{e}{-5},8\mathrm{e}{-5}\}$ |

## Appendix B Proof

From a single-step perspective, LeZO also involves updating a sub-network, which aligns with the theory of Sparse-MeZO (Liu et al., ). Therefore, the following proof draws inspiration from it.

###### Proof of Lemma 1 .

Let ${\mathcal{L}}_{{\bm{z}}}({\bm{\theta}})$ be the expectation of ${\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}})$:

$$ $\displaystyle{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}):$ $\displaystyle=\mathbb{E}_{z}[{\mathcal{L}}({\bm{\theta}}+\epsilon{\mathcal{R}} ({\bm{z}}))]$ (10) $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[{\mathcal{L}}({\bm{\theta}}+\epsilon{ \bm{z}}^{{}^{\prime}})].$ $$

Then,

$$ $\displaystyle\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})$ $\displaystyle=\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}\mathbb{E}_{{ \mathcal{R}}}[{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})]$ (11) $\displaystyle=\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}\int_{{\bm{z}}^{{} ^{\prime}}}\text{pdf}_{{\bm{z}}^{{}^{\prime}}}({\bm{z}}){\mathcal{L}}({\bm{ \theta}}+\epsilon{\bm{z}})d{\bm{z}}$ $\displaystyle={\mathcal{R}}(\nabla\int_{{\bm{z}}^{{}^{\prime}}}\text{pdf}_{{ \bm{z}}^{{}^{\prime}}}(z){\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}})d{\bm{z}})$ $\displaystyle={\mathcal{R}}(\int_{{\bm{z}}^{{}^{\prime}}}\nabla\text{pdf}_{{ \bm{z}}^{{}^{\prime}}}({\bm{z}}){\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}})d {\bm{z}})$ $\displaystyle=\frac{1}{k}{\mathcal{R}}(\int_{{\bm{z}}^{{}^{\prime}}}\nabla e^{ -\frac{1}{2}\|{\bm{z}}\|^{2}}{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}})d{ \bm{z}})$ $\displaystyle=\frac{1}{k}{\mathcal{R}}(\int_{{\bm{y}}^{{}^{\prime}}}\nabla e^{ -\frac{1}{2}\|\frac{{\bm{y}}-{\bm{\theta}}}{\epsilon}\|^{2}}{\mathcal{L}}({\bm {y}})\frac{1}{\epsilon^{n}}d{\bm{y}})$ $\displaystyle=\frac{1}{k}{\mathcal{R}}(\int_{{\bm{y}}^{{}^{\prime}}}\frac{y-{ \bm{\theta}}}{\epsilon^{2}}e^{-\frac{1}{2\epsilon^{2}}\|{\bm{y}}-{\bm{\theta}} \|^{2}}{\mathcal{L}}({\bm{y}})\frac{1}{\epsilon^{n}}d{\bm{y}})$ $\displaystyle=\frac{1}{k}{\mathcal{R}}(\int_{{\bm{z}}^{{}^{\prime}}}\frac{{\bm {z}}}{\epsilon}e^{-\frac{1}{2}\|{\bm{z}}\|^{2}}{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}})d{\bm{z}})$ $\displaystyle={\mathcal{R}}(\int_{{\bm{z}}^{{}^{\prime}}}\text{pdf}_{{\bm{z}}^ {{}^{\prime}}}({\bm{z}}){\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}})\frac{{ \bm{z}}}{\epsilon}d{\bm{z}})$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[{\mathcal{R}}(\frac{{\mathcal{L}}({ \bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}})]$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}],$ $$

where $y={\bm{\theta}}+\epsilon{\bm{z}}$, ${\bm{y}}^{{}^{\prime}}={\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}}$, and $k=\sqrt{(2\pi)^{\rho d}}$.

Next,

$$ $\displaystyle\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}- \epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}]$ $\displaystyle=\frac{1}{k}\int_{-{\bm{z}}^{{}^{\prime}}}\frac{{\mathcal{L}}({ \bm{\theta}}+\epsilon(-{\bm{z}}))}{\epsilon}-{\bm{z}}e^{-\frac{1}{2}\|-{\bm{z} }\|^{2}}d(-{\bm{z}})$ (12) $\displaystyle=\frac{1}{k}\int_{\hat{{\bm{z}}}}\frac{{\mathcal{L}}({\bm{\theta} }+\epsilon{\bm{z}})}{\epsilon}{\bm{z}}e^{-\frac{1}{2}\|z\|^{2}}dz$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}].$ $$

Therefore,

$$ $\displaystyle\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}]$ (13) $\displaystyle=\frac{1}{2}(\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{ \theta}}+\epsilon{\bm{z}}^{{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}]- \mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^ {{}^{\prime}})}{\epsilon}{\bm{z}}^{{}^{\prime}}])$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^{ {}^{\prime}})}{2\epsilon}{\bm{z}}^{{}^{\prime}}]$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\widehat{\nabla}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})].$ $$

Q.E.D.
∎

###### Proof of Lemma 2 .

Firstly, compute the norm distance between the sparse ZO estimated gradient $\nabla_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})$ and the sparse FO gradient $\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})$:

$$ $\displaystyle\|\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})-\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|$ $\displaystyle=\|\frac{1}{k}\int_{{\bm{z}}}(\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}})-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}})}{2\epsilon}- \langle\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}),{\bm{z}}\rangle){\bm {z}}e^{-\frac{1}{2}\|{\bm{z}}\|^{2}}d{\bm{z}}^{{}^{\prime}}\|$ (14) $\displaystyle=\|\frac{1}{k}\int_{{\bm{z}}}(\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}})-{\mathcal{L}}({\bm{\theta}})}{\epsilon}-\langle{\mathcal{R}} (\nabla{\mathcal{L}}({\bm{\theta}})),{\bm{z}}\rangle){\bm{z}}e^{-\frac{1}{2}\| {\bm{z}}\|^{2}}d{\bm{z}}^{{}^{\prime}}\|$ $\displaystyle\leq\frac{1}{k\epsilon}\int_{{\bm{z}}}|{\mathcal{L}}({\bm{\theta} }+\epsilon{\bm{z}})-{\mathcal{L}}({\bm{\theta}})-\epsilon\langle\nabla{ \mathcal{L}}({\bm{\theta}}),\epsilon\rangle|\|{\mathcal{R}}({\bm{z}})\|e^{- \frac{1}{2}\|{\bm{z}}\|^{2}}d{\bm{z}}^{{}^{\prime}}$ $\displaystyle\leq\frac{\epsilon L(l)}{2k}\int_{\epsilon}\|{\bm{z}}\|^{2}\|{ \mathcal{R}}({\bm{z}})\|e^{-\frac{1}{2}\|{\bm{z}}\|^{2}}d{\bm{z}}^{{}^{\prime}}$ $\displaystyle=\frac{\epsilon L(l)}{2}\mathbb{E}_{{\mathcal{R}}}[\|{\bm{z}}^{{} ^{\prime}}\|^{3}]$ $\displaystyle\leq\frac{\epsilon L(l)}{2}(\rho d+3)^{\frac{3}{2}}.$ $$

Subsequently, employing the Minkowski inequality for norms, which can be further generalized to $\|{\bm{a}}+{\bm{b}}\|^{2}\leq 2\|{\bm{a}}\|^{2}+2\|{\bm{b}}\|^{2}$, by letting ${\bm{a}}=\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-\widehat{\nabla}_{
{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})$ and ${\bm{b}}=\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{
\mathcal{R}}}({\bm{\theta}})$, we obtain:

$$ $\displaystyle\|\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}$ $\displaystyle\leq 2\|\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})- \widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{\mathcal{R}}}({ \bm{\theta}})\|^{2}+2\|\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal {L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}$ (15) $\displaystyle=2\|\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{ {\mathcal{R}}}({\bm{\theta}})-\nabla{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta} })\|^{2}+2\|\widehat{\nabla}_{{\bm{\theta}}^{{}^{\prime}}}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})\|^{2}$ $\displaystyle\leq\frac{\epsilon^{2}L^{2}(l)}{2}(\rho d+3)^{3}+2\|\widehat{ \nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}$ $\displaystyle\leq\frac{\epsilon^{2}L^{2}(l)}{2}(\rho d+4)^{3}+2\|\widehat{ \nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}.$ $$

Q.E.D.
∎

###### Proof of Lemma 3 .

$$ $\displaystyle{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-{\mathcal{L}}({\bm{ \theta}})$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[{\mathcal{L}}({\bm{\theta}}+\epsilon{ \bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}})]$ (16) $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[{\mathcal{L}}({\bm{\theta}}+\epsilon{ \bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}})-\epsilon\langle\nabla{ \mathcal{L}}({\bm{\theta}}),{\bm{z}}^{{}^{\prime}}\rangle]$ $\displaystyle=\frac{1}{k}\int_{{\bm{z}}^{{}^{\prime}}}[{\mathcal{L}}({\bm{ \theta}}+\epsilon{\bm{z}})-{\mathcal{L}}({\bm{\theta}})-\epsilon\langle\nabla{ \mathcal{L}}({\bm{\theta}}),{\bm{z}}\rangle]e^{-\frac{1}{2}\|{\bm{z}}\|^{2}}dz$ $\displaystyle\leq\frac{1}{k}\int_{{\bm{z}}^{{}^{\prime}}}\frac{\epsilon^{2}L(l )}{2}\|{\bm{z}}\|^{2}e^{-\frac{1}{2}\|{\bm{z}}\|^{2}}d{\bm{z}}$ $\displaystyle=\frac{\epsilon^{2}L(l)}{2}\mathbb{E}_{{\mathcal{R}}}[\|{\bm{z}}^ {{}^{\prime}}\|^{2}]$ $\displaystyle\leq\frac{\epsilon^{2}L(l)}{2}\rho d,$ $$

where ${\bm{\theta}}_{t}={\bm{\theta}}+\epsilon{\bm{z}}$. Given that ${\mathcal{L}}$ satisfies Lipschitz continuity, we can derive $|{\mathcal{L}}({\bm{\theta}}^{\prime})-{\mathcal{L}}({\bm{\theta}})-\langle
\nabla{\mathcal{L}}({\bm{\theta}}),{\bm{\theta}}_{t}-{\bm{\theta}}\rangle|\leq
\frac{L(l)}{2}\|{\bm{\theta}}_{t}-{\bm{\theta}}\|^{2}$, establishing the validity of the first inequality.

$$ $\displaystyle[({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-{\mathcal{L}}({\bm {\theta}}))-({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^ {\prime}})-{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}}))]^{2}$ (17) $\displaystyle\leq 2[{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-{\mathcal{L}} ({\bm{\theta}})]^{2}+2[{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{ \bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{ \prime}})]^{2}$ $\displaystyle\leq\frac{\epsilon^{4}L^{2}(l)}{2}\rho^{2}d^{2}+\frac{\epsilon^{4 }L^{2}(l)}{2}\rho^{2}d^{2}$ $\displaystyle=\epsilon^{4}L^{2}(l)\rho^{2}d^{2}.$ $$

$$ $\displaystyle({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{\bm{z}}^{{} ^{\prime}})-{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}))^{2}$ $\displaystyle\leq 2({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{\bm{z }}^{{}^{\prime}})-{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-\epsilon\langle \widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}),{\bm{z}}^{{}^{ \prime}}\rangle)^{2}$ (18) $\displaystyle\quad+2(\epsilon\langle\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R }}}({\bm{\theta}}),{\bm{z}}^{{}^{\prime}}\rangle)^{2}$ $\displaystyle\leq\frac{\epsilon^{4}L^{2}(l)}{2}\|{\bm{z}}^{{}^{\prime}}\|^{4}+ 2\epsilon^{2}\langle\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta} }),{\bm{z}}^{{}^{\prime}}\rangle^{2}$ $\displaystyle\leq\frac{\epsilon^{4}L^{2}(l)}{2}\|{\bm{z}}^{{}^{\prime}}\|^{4}+ 2\epsilon^{2}\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^ {2}\|{\bm{z}}^{{}^{\prime}}\|^{2}.$ $$

$$ $\displaystyle({\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})-{ \mathcal{L}}({\bm{\theta}}))^{2}$ (19) $\displaystyle\leq 2(({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})-{\mathcal{L} }({\bm{\theta}}))-({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{\bm{z} }^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}}))) ^{2}$ $\displaystyle\quad+2({\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}+\epsilon{\bm{ z}}^{{}^{\prime}})-{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}))^{2}$ $\displaystyle\leq 2\epsilon^{4}L^{2}(l)\rho^{2}d^{2}+\epsilon^{4}L^{2}(l)\|{ \bm{z}}^{{}^{\prime}}\|^{4}+4\epsilon^{2}\|\widehat{\nabla}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})\|^{2}\|{\bm{z}}^{{}^{\prime}}\|^{2}$ $$

$$ $\displaystyle\mathbb{E}_{{\bm{z}},{\bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}})\|^{2}]$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\|\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^{ {}^{\prime}})}{2\epsilon}{\bm{z}}^{{}^{\prime}}\|^{2}]$ (20) $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\|\frac{{\mathcal{L}}({\bm{\theta}}+ \epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}})}{2\epsilon}{\bm{z }}^{{}^{\prime}}+\frac{{\mathcal{L}}({\bm{\theta}})-{\mathcal{L}}({\bm{\theta} }-\epsilon{\bm{z}}^{{}^{\prime}})}{2\epsilon}{\bm{z}}^{{}^{\prime}}\|^{2}]$ $\displaystyle\leq\mathbb{E}_{{\mathcal{R}}}[2\|\frac{{\mathcal{L}}({\bm{\theta }}+\epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}})}{2\epsilon}{ \bm{z}}^{{}^{\prime}}\|^{2}+2\|\frac{{\mathcal{L}}({\bm{\theta}})-{\mathcal{L} }({\bm{\theta}}-\epsilon{\bm{z}}^{{}^{\prime}})}{2\epsilon}{\bm{z}}^{{}^{ \prime}}\|^{2}]$ $\displaystyle=\mathbb{E}_{{\mathcal{R}}}[\frac{1}{2\epsilon^{2}}[{\mathcal{L}} ({\bm{\theta}}+\epsilon{\bm{z}}^{{}^{\prime}})-{\mathcal{L}}({\bm{\theta}})]^{ 2}\cdot\|{\bm{z}}^{{}^{\prime}}\|^{2}+\frac{1}{2\epsilon^{2}}[{\mathcal{L}}({ \bm{\theta}})-{\mathcal{L}}({\bm{\theta}}-\epsilon{\bm{z}}^{{}^{\prime}})]^{2} \cdot\|{\bm{z}}^{{}^{\prime}}\|^{2}]$ $\displaystyle\leq\mathbb{E}_{{\mathcal{R}}}[2\epsilon^{2}L^{2}(l)\rho^{2}d^{2} \|{\bm{z}}^{{}^{\prime}}\|^{2}+\epsilon^{2}L^{2}(l)\|{\bm{z}}^{{}^{\prime}}\|^ {6}+4\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}\|{ \bm{z}}^{{}^{\prime}}\|^{4}]$ $\displaystyle\leq 2\epsilon^{2}L^{2}(l)\rho^{3}d^{3}+\epsilon^{2}L^{2}(l)(\rho d +6)^{3}+4(\rho d+4)^{2}\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{ \theta}})\|^{2}$ $\displaystyle\leq 3\epsilon^{2}L^{2}(l)(\rho d+4)^{3}+4(\rho d+4)^{2}\| \widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}})\|^{2}.$ $$

As $\mathbb{E}_{{\mathcal{R}}}[\|{\bm{z}}^{{}^{\prime}}\|^{p}]\leq(\rho d+p)^{
\frac{p}{2}}$ for $p\geq 2$, the third inequality holds. Additionally, since $2\rho^{3}d^{3}+(\rho d+6)^{3}\leq 3(\rho d+4)^{3}$, the fourth inequality is valid.

Again, given that ${\mathcal{L}}$ is Lipschitz continuous, we have $|{\mathcal{L}}({\bm{\theta}}_{t+1})-{\mathcal{L}}({\bm{\theta}}_{t})-\langle
\nabla{\mathcal{L}}({\bm{\theta}}_{t}),{\bm{\theta}}_{t+1}-{\bm{\theta}}_{t}
\rangle|\leq\frac{L(l)}{2}\|{\bm{\theta}}_{t+1}-{\bm{\theta}}_{t}\|^{2}$. Therefore, we can derive:

$$ $\displaystyle{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t+1})-{\mathcal{L}}_ {{\mathcal{R}}}({\bm{\theta}}_{t})$ $\displaystyle-\langle\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta }}_{t}),{\bm{\theta}}_{t+1}-{\bm{\theta}}_{t}\rangle$ (21) $\displaystyle\leq|{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t+1})-{\mathcal {L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})-\langle\widehat{\nabla}{\mathcal{L}}_{ {\mathcal{R}}}({\bm{\theta}}_{t}),{\bm{\theta}}_{t+1}-{\bm{\theta}}_{t}\rangle|$ $\displaystyle\leq\frac{L(l)}{2}\|{\bm{\theta}}_{t+1}-{\bm{\theta}}_{t}\|^{2}.$ $$

By further examining the iterative process of Structured Sparse ZO-SGD as outlined in Equation 5, we can obtain:

$$ $\displaystyle{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t+1})$ $\displaystyle\leq{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})+\langle \widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t}),{\bm{\theta}} _{t+1}-{\bm{\theta}}_{t}\rangle+\frac{L(l)}{2}\|{\bm{\theta}}_{t}-{\bm{\theta} }_{t+1}\|^{2}$ (22) $\displaystyle={\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})-\eta_{t}\langle \widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t}),\widehat{ \nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})\rangle+\frac{(\eta_{t} )^{2}L(l)}{2}\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t} )\|^{2},$ $$

where $\eta_{t}$ represents the learning rate at step $t$.

Subsequently, we can derive the expected loss function of the structured sparse model at step $t+1$ as:

$$ $\displaystyle\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}}_{t+1})]$ $\displaystyle\leq\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}}_{t})]-\eta_{t}\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{ \bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})\|^ {2}]$ (23) $\displaystyle\quad+\frac{(\eta_{t})^{2}L(l_{{\bm{z}}})}{2}\mathbb{E}_{{\bm{z}} ^{{}^{\prime}},{\bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}({\bm{\theta}}_{t})\|^ {2}]$ $\displaystyle\leq\mathbb{E}_{{\bm{z}}^{{}^{\prime}},x}[{\mathcal{L}}_{{ \mathcal{R}}}({\bm{\theta}}_{t})]-\eta_{t}\mathbb{E}_{{\bm{z}}^{{}^{\prime}},x }[\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})\|^{2}]$ $\displaystyle\quad+\frac{(\eta_{t})^{2}L(l)}{2}(4(\rho d+4)\mathbb{E}_{{\bm{z} }^{{}^{\prime}},x}[\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta }}_{t})\|^{2}]+3\epsilon^{2}L^{2}(l)(\rho d+4)^{3}).$ $$

Then, let learning rate be $\eta_{t}=\frac{1}{4(\rho d+4)L(l)}$ and obtain:

$$ $\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[{\mathcal{L}}_{{\mathcal{R}}}({ \bm{\theta}}_{t+1})]\leq\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[{\mathcal {L}}_{{\mathcal{R}}}({\bm{\theta}}_{t})]-\frac{1}{8(\rho d+4)L(l)}\mathbb{E}_{ {\bm{z}}^{{}^{\prime}},{\bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R} }}({\bm{\theta}}_{t})\|^{2}]+\frac{3\epsilon^{2}}{32}L(l)(\rho d+4).$ (24) $$

Summing Equation 24 from 0 0 to $T+1$, where $T$ denotes a sufficiently large number of training steps, yields:

$$ $\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}_{ {\mathcal{R}}}({\bm{\theta}}_{T})\|^{2}]\leq 8(\rho d+4)L[\frac{{\mathcal{L}}_ {{\mathcal{R}}}({\bm{\theta}}_{0})-{\mathcal{L}}_{{\mathcal{R}}}^{*}}{T+1}+ \frac{3\epsilon^{2}}{32}L(\rho d+4)],$ (25) $$

where $L(l)\leq L$ for all ${\mathcal{L}}(\bm{{\bm{\theta}}_{t}})$. Thus, based on Lemma 2, we can have:

$$ $\displaystyle\mathbb{E}_{{\bm{z}}^{{}^{\prime}},{\bm{x}}}[\|\nabla{\mathcal{L} }_{m}({\bm{\theta}}_{T})\|^{2}]$ $\displaystyle\leq\frac{\epsilon^{2}L^{2}}{2}(\rho d+4)^{3}+2\mathbb{E}_{{\bm{z }}^{{}^{\prime}},{\bm{x}}}[\|\widehat{\nabla}{\mathcal{L}}_{{\mathcal{R}}}({ \bm{\theta}}_{T})\|^{2}]$ (26) $\displaystyle\leq 16(\rho d+4)L\frac{{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta }}_{0})-{\mathcal{L}}_{{\mathcal{R}}}^{*}}{T+1}+\frac{\epsilon^{2}L^{2}}{2}( \rho d+4)^{2}(\rho d+\frac{11}{2}).$ $$

To obtain $\sigma$-accurate solution $\mathbb{E}_{{\bm{z}}^{{}^{\prime}},x}[\|\nabla{\mathcal{L}}_{m}({\bm{\theta}}_
{T})\|^{2}]\leq\sigma^{2}$, we can define $\epsilon=\Omega(\frac{\sigma}{\rho^{\frac{3}{2}}d^{\frac{3}{2}}L})$.

$$ $\displaystyle 16(\rho d+4)$ $\displaystyle L\frac{{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{0})-{ \mathcal{L}}_{{\mathcal{R}}}^{*}}{T+1}+{\mathcal{O}}(\epsilon^{2}L^{2}\rho^{3} d^{3})$ (27) $\displaystyle=16(\rho d+4)L\frac{{\mathcal{L}}_{{\mathcal{R}}}({\bm{\theta}}_{ 0}-{\mathcal{L}}_{{\mathcal{R}}}^{*})}{T+1}+{\mathcal{O}}(\sigma^{2}).$ $$

From the above, we can get:

$$ $\displaystyle T$ $\displaystyle={\mathcal{O}}(\frac{\rho dL}{\sigma^{2}}).$ (28) $$

Q.E.D.
∎

###### Proof of Lemma 1 .

###### Proof of Lemma 2 .

###### Proof of Lemma 3 .

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: See the above weaknesses for questions.
soundness: 3
strengths: 1. The algorithm is straightforward and easy to understand, combining BCD with MeZO.
2. The authors provide a theoretical analysis of the convergence rate.
3. They empirically demonstrate that their method achieves a speed-up in fine-tuning experiments on the OPT model family.
summary: The authors propose LeZO, a method that integrates the ideas of BCD and ZO-SGD to accelerate training time in comparison to MeZO by Malladi et al. (2023).
weaknesses: 1. The method consistently improves the convergence rate compared to MeZO; however, the rate still scales with d without further assumptions.
2. Building on point 1, the improvement in convergence rate is clear both theoretically and empirically. However, the corresponding impact on model performance remains unclear and unexplained.
3. There is a lack of empirical results on larger models, such as 30B. Additionally, testing on model types other than OPT should be considered.
4. Is the random selection of parameters optimal? Alternative selection methods, such as using importance sampling and weight norms, remain unexplored.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. In Line 310, it is stated that as the sparsity ratio $\rho$ decreases, the upper bound on the convergence time to the expected value also decreases. If $\rho$ here is defined as on Line 194, then when $\rho = 0$, meaning no parameters are perturbed, why would the upper bound on the required convergence time be minimized in this case?
2. Your method appears quite similar to sparse MeZO, with convergence analysis and proofs that are almost identical. Sparse MeZO selects parameters for updates based on their magnitudes, while your approach randomly selects layers for updates. Why didn’t you include a comparison with sparse MeZO? Does your method offer any performance advantages, or is the primary benefit a reduction in memory overhead? Additionally, is there any theoretical insight for choosing layers as the basic unit for sparsification?
3. In Figure 3, there are notable performance drops between dropout numbers of 5 and 0 (MeZO), suggesting a significant performance gain by excluding updates for just 5 layers. There are also marked drops between dropout numbers 35 and 40. How do you explain these observations?
soundness: 2
strengths: 1. The proposed method is straightforward and practical, making it easy to integrate into existing training frameworks with minimal engineering effort. By sparsifying updates at the layer level, it achieves efficiency without complex changes, making it highly usable.
2. Although writing clarity could be improved, the paper is organized logically, which helps convey the main ideas and findings in a generally understandable way.
3. Experimental results show clear benefits: the approach reduces computational overhead in perturbation and updating, achieving up to 3.4× faster wall-clock training times, highlighting its effectiveness in accelerating convergence.
summary: This paper proposes a novel zeroth-order optimizer, named LeZO, which enhances the efficiency of the Memory-efficient Zeroth-Order (MeZO) optimizer by introducing sparsity in the parameter updates. The key innovation of LeZO is that it applies sparsification at the layer level, treating each layer as a unit of sparse updating. Through analysis, the authors observe that more than half of MeZO’s computational cost is spent on perturbation and updating stages. By selectively updating only a subset of layers in each iteration, LeZO significantly reduces this overhead, while still ensuring that all parameters are eventually updated. This strategy avoids additional memory costs, such as those incurred by masking. Experimental results demonstrate that LeZO achieves up to a 3.4× speedup in training wall-clock time compared to the original MeZO, without compromising optimization performance.
weaknesses: 1. Inconsistent Terminology and Notation: The paper suffers from inconsistent use of terms and symbols. For instance, the term "sparse rate $\rho$" on Line 194 and "sparsity rate reaches $\rho = 1$" on Line 451 seem to refer to entirely different concepts, which may confuse readers.
2. Errors and Ambiguities in Mathematical Notation: The mathematical expressions and symbols lack rigor and contain errors. According to Line 195, $\theta' \in \mathbb{R}^{\rho d}$ while $\theta \in \mathbb{R}^{d}$, making the addition of $\theta$ and $z'$ in Equation (4) undefined, as these vectors lie in different spaces. Additionally, cases where $\rho d$ is not an integer are not addressed. Notation in Lemma 1 is also quite unclear, making it difficult to interpret.
3. Errors in Tables: Table 1 contains unexplained elements, such as the appearance of "SSZO," which is not introduced or defined, potentially causing confusion.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: - how much /where Lezo saved memories on? any detailed profiling?
soundness: 2
strengths: - The authors conduct extensive experiments on the OPT model family using the SuperGLUE benchmark and two generative tasks. The reported 3× speedup over MeZO on tasks like SST-2, BoolQ, and Copa provides strong empirical evidence for the effectiveness of LeZO.

- LeZO effectively integrates layer-wise sparsity into the simultaneous perturbation stochastic approximation (SPSA) and zeroth-order stochastic gradient descent (ZO-SGD), maintaining the theoretical foundations of ZO optimization.
summary: The paper addresses the challenge of high memory usage during the fine-tuning of large language models (LLMs). It revisits the Memory-efficient Zeroth-Order (MeZO) optimizer and identifies that the perturbation and updating processes consume over 50% of the fine-tuning time. 
To mitigate this, the authors propose LeZO, a layer-wise sparse computation and memory-efficient zeroth-order optimizer. LeZO introduces dynamic layer-wise sparsification, treating layers as fundamental units and perturbing different parameter subsets in each step to achieve full-parameter fine-tuning. 
The proposed method aims to reduce computational costs without additional memory overhead and demonstrates faster convergence than MeZO on the SuperGLUE benchmark and two generative tasks.
weaknesses: - The theory is based on the assumption of Lipchitz continuity. In the context of deep learning and LLMs, this assumption can be overly simplistic or unrealistic. Loss landscapes in deep neural networks are often non-convex and may not satisfy Lipschitz continuity, not to say the billion params LLMs.

- The paper primarily compares LeZO with MeZO. Including comparisons with other state-of-the-art optimization techniques for fine-tuning LLMs, such as first-order methods (e.g., Adam, AdamW) or other memory-efficient optimizers, would provide a more comprehensive evaluation. (the LLM community are still generally using AdamW, I am not convinced if this appeals to adam users)

- The claim that LeZO achieves accelerated computation without additional memory overhead could be elaborated upon. 

- The setting of LoRA could sway the performances by a lot with different rank and alpha, the paper only tested using r=8, and alpha=16, I would suggest try different LoRA set ups and offer evidence that it could work in the higher rank setting. Along the same vain, as the eval is done mainly by evaluating downstream performance, then adding more models into comparison would be more convincing.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: Q1: There seems to be a typo in Table 1. The approach "SSZO" is used but not referenced or explained in any other part of the paper. If this is a typo meant to refer to LeZO, then the authors should double-check for consistency in naming.

Q2: In Figure 4, the drop in accuracy between dropout number 0 and 40 is only less than 0.5%, which does not seem significant considering all the layers have been frozen in fine-tuning. Can this be attributed to the fact that you are still fine-tuning the embedding and linear layers as mentioned in section 5.3? How much of an impact are the results obtained impacted by this?
soundness: 2
strengths: S1: Paper is overall well written and organized, providing some nice background and discussion of related works.

S2: Extensive experiments on different model size scales, discussion on evaluating LeZO on orthogonal PEFT methods, and analysis of the impacts of hyperparameters.
summary: The paper aims to reduce the computational cost of zeroth-order (ZO) optimization, specifically building upon the memory-efficient ZO (MeZO) optimizer. The main idea of the paper involves incorporating a layer-wise sparsity by randomly selecting a subset of layers to be tuned at each fine-tuning step. Experiments show that the proposed method, LeZO, achieves a noticeable speedup in fine-tuning LLMs while retaining comparable performance.
weaknesses: W1: Contribution lacks some novelty as components are borrowed from closely related work. For instance, LISA proposed by Pan et. al. 2024, uses a similar layer-wise sampling that is applied to first order optimizers like AdamW. The convergence analysis presented in the paper is also based on Sparse-MeZO by Liu et al. 2024, with minor changes.

W2: Although Sparse-MeZO was mentioned as a related work, it was not used as a baseline to evaluate against. Including this can be important to observe performance gaps between the two approaches, which both apply a form of parameter selection to improve MeZO.