Fine-Tuning Language Models with Just Forward Passes

Sadhika Malladi * 1 Tianyu Gao * 1 Eshaan Nichani 1 Alex Damian 1
Jason D. Lee 1 Danqi Chen 1 Sanjeev Arora 1

1. Introduction

Abstract

Fine-tuning pre-trained language models (LMs) has been
the dominant methodology for solving many languagetasks (Devlin et al., 2019), adapting to specialized domains (Gururangan et al., 2020), or incorporating human
instructions and preferences (Ouyang et al., 2022). However, as LMs are scaled up (Brown et al., 2020; OpenAI,2023), computing gradients for backpropagation requires aprohibitive amounts of memory – in our test, up to 12× thememory required for inference – because it needs to cache
activations during the forward pass, gradients during the
backward pass, and, in the case of Adam (Kingma and Ba,2015), also store gradient history (Section 3.1).

Fine-tuning language models (LMs) has yielded
success on diverse downstream tasks, but as LMs
grow in size, backpropagation requires a prohibitively large amount of memory. Zeroth-order(ZO) methods can in principle estimate gradientsusing only two forward passes but are theorized tobe catastrophically slow for optimizing large models. In this work, we propose a memory-efficient
zeroth-order optimizer (MeZO), adapting theclassical ZO-SGD method to operate in-place,thereby fine-tuning LMs with the same memory
footprint as inference. For example, with a single
A100 80GB GPU, MeZO can train a 30-billion
parameter model, whereas fine-tuning withbackpropagation can train only a 2.7B LM withthe same budget. We conduct comprehensive
experiments across model types (masked and autoregressive LMs), model scales (up to 66B), anddownstream tasks (classification, multiple-choice,and generation). Our results demonstrate that
(1) MeZO significantly outperforms in-context
learning and linear probing; (2) MeZO achieves
comparable performance to fine-tuning withbackpropagation across multiple tasks, with up to
12× memory reduction; (3) MeZO is compatible
with both full-parameter and parameter-efficienttuning techniques such as LoRA and prefixtuning; (4) MeZO can effectively optimize
non-differentiable objectives (e.g., maximizing
accuracy or F1). We support our empiricalfindings with theoretical insights, highlighting
how adequate pre-training and task prompts
enable MeZO to fine-tune huge models, despiteclassical ZO analyses suggesting otherwise.

As a result, while it is possible to run inference with a 30billion (30B) parameter LM on 1 Nvidia A100 GPU (with80GB memory), backpropagation with Adam is feasible
only for a 2.7B LM. Parameter-efficient fine-tuning methods(PEFT (Hu et al., 2022; Li and Liang, 2021; Lester et al.,2021)) update a fraction of the network parameters, but needto cache many activations, because tuned parameters arescattered throughout the model. In our tests, fine-tuning an
OPT-13B model with full parameter or PEFT requires 12×
and 6× more memory than inference respectively.
In-context learning (ICL (Brown et al., 2020)) has allowed
solving many tasks with a single inference pass, during
which the model processes labeled examples (demonstrations) in its context and then outputs a prediction on a test
example. While this allows for quick adaptation of themodel to specific use cases, current models allow a limited
context size (and thus, limited demonstrations) and theperformance is sensitive to the formatting and choice of
demonstrations (Liu et al., 2022; Lu et al., 2022). ICL also
often performs worse than fine-tuning of medium-sizedmodels (Brown et al., 2020). Besides, inference with ICL
is more expensive, as it always requires demonstrations incontext and thus increases the input length.
A classical zeroth-order optimization method (ZOSGD (Spall, 1992)) uses only differences of loss values
to estimate the gradients. Thus in principle, the method can
update neural networks with just forward passes, thoughnaive implementation still doubles the memory overhead
and classical lower bounds (Nemirovskij and Yudin, 1983;*

Equal contribution 1 Princeton University, Princeton, NJ, USA.
Correspondence to: Sadhika Malladi <smalladi@princeton.edu>,
Tianyu Gao <tianyug@princeton.edu>.
Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1Fine-Tuning Language Models with Just Forward Passes

Accuracy/F1 (%)

90
70
50
30
10

SST-2

RTE

CB

BoolQ
Zero-shot

WSC

WIC

ICL

MultiRC
MeZO

Copa

ReCoRD

SQuAD

DROP

FT (12x memory)

Figure 1: OPT-13B results with zero-shot, in-context learning (ICL), MeZO (we report the best among MeZO/MeZO(LoRA)/MeZO (prefix)), and fine-tuning with Adam (FT). MeZO demonstrates superior results over zero-shot and ICL
and performs on par with FT (within 1%) on 7 out of 11 tasks, despite using only 1/12 memory. See Table 2 for detailed
numbers and Figure 2 for memory profiling.
Duchi et al., 2015) suggest that convergence slows linearlywith model size. As such, ZO methods have been applied indeep learning settings to find adversarial examples or tune
input embeddings (Sun et al., 2022b;a) but not to directly
optimize large-scale models (see Liu et al. (2020a)).

the per-step optimization rate (Theorem 1) and global
convergence rate (Lemma 3) of MeZO depend on acertain condition number of the landscape (i.e., thelocal effective rank, Assumption 1) instead of numbersof parameters. This result is in sharp contrast to existing ZO lower bounds (Nemirovskij and Yudin, 1983;
Duchi et al., 2015) suggesting that the convergence rate
can slow proportionally to the number of parameters(Section 4).

We propose a memory-efficient zeroth-order optimizer(MeZO), which adapts the classical ZO-SGD algorithm
and reduces its memory consumption to the same as inference. We apply MeZO to fine-tune large LMs and show that,both empirically and theoretically, MeZO can successfully
optimize LMs with billions of parameters. Specifically, ourcontributions are:

2. Zeroth-order optimization
Zeroth-order (ZO) optimizers have long been studied in thecontext of convex and strongly convex objectives. Consider
a labelled dataset D = {(xi , yi )}i∈[|D|] and a minibatch
B ⊂ D of size B, we let L(θ; B) denote the loss on theminibatch. We introduce a classical ZO gradient estimate inthis setting.

1. In MeZO, we adapt the ZO-SGD algorithm (Spall,1992) and a number of variants to operate in-place
on arbitrarily large models with almost no memory
overhead (see Algorithm 1 and Section 2).
2. We conduct comprehensive experiments across modeltypes (masked LM and autoregressive LM), model
scales (from 350M to 66B), and downstreamtasks (classification, multiple-choice, and generation).
MeZO consistently demonstrates superiority overzero-shot, ICL, and linear probing. Moreover, with
RoBERTa-large, MeZO achieves performance close
to standard fine-tuning within 5% gap; with OPT-13B,
MeZO outperforms or performs comparably to finetuning on 7 out of 11 tasks, despite requiring roughly
12× less memory (Figure 1.

Definition 1 (Simultaneous Perturbation Stochastic Approximation or SPSA (Spall, 1992)). Given a model with parameters θ ∈ Rd and a loss function L, SPSA estimates thegradient on a minibatch B as
L(θ + z; B) − L(θ − z; B)
b
∇L(θ;
B) =
z
2
≈ zz > ∇L(θ; B)
where z ∈ Rd with z ∼ N (0, Id ) and  is the perturbationb
B)
scale. The n-SPSA gradient estimate averages ∇L(θ;over n randomly sampled z.

3. We demonstrate MeZO’s compatibility with fullparameter tuning and PEFT (e.g., LoRA (Hu et al.,2022) and prefix-tuning (Li and Liang, 2021)) in Section 3. Further exploration showcases that MeZO can
optimize non-differentiable objectives such as accuracy or F1 score, while still requiring only the same
memory as inference (Appendix A.2).

SPSA requires only two forward passes through the model
to compute the gradient estimate (for n-SPSA, each estimate
requires 2n forward passes). It is widely known that theestimate can be used to replace the backpropagation gradientin any optimizer such as SGD.

4. Our theory suggests that adequate pre-training ensures2

Fine-Tuning Language Models with Just Forward Passes

Algorithm 1: MeZO#

Require: parameters θ ∈ Rd , loss L : Rd → R, step
budget T , perturbation scale , batch size B, learning
rate schedule {ηt }for t = 1, ..., T do
Sample batch B ⊂ D and random seed sθ ← PerturbParameters(θ, , s)`+ ← L(θ; B)θ ← PerturbParameters(θ, −2, s)`− ← L(θ; B)θ ← PerturbParameters(θ, , s)

11x
12x
11x

#

##
8x
7x

#

#

Figure 2: GPU memory consumption with different OPT
models and tuning methods on MultiRC (400 tokens per
example on average).

projected_grad ← (`+ − `− )/(2)Reset random number generator with seed sfor θi ∈ θ doz ∼ N (0, 1)
θi ← θi − ηt ∗ projected_grad ∗ z
endend
Subroutine PerturbParameters(θ, , s)
Reset random number generator with seed sfor θi ∈ θ doz ∼ N (0, 1)
θi ← θi + z
end
return θ

Hardware
1×A100 (80GB)
2×A100 (160GB)
4×A100 (320GB)
8×A100 (640GB)

Largest OPT that can fit
FT

FT-prefix

MeZO

2.7B
6.7B
13B
30B

6.7B
13B
30B
66B

30B
66B
66B
175B†

Figure 3: Largest OPT models that one can tune
with specific hardwares and algorithms. † : projected results without actual testing.
tings with prompts. We also explore both full-parametertuning and PEFT including LoRA (Hu et al., 2022) andprefix-tuning (Li and Liang, 2021) (Appendix F.5). We
compare MeZO with zero-shot, in-context learning (ICL),
linear-probing (LP), and fine-tuning with Adam (FT).

2.1. Memory-efficient ZO-SGD (MeZO)
The vanilla ZO-SGD algorithm costs twice the memoryof inference, as it needs to store z ∈ Rd . We propose amemory-efficient implementation of ZO-SGD called MeZO
(Algorithm 1). At each step, we sample a random seed s,
and then for each of z’s four uses in Algorithm 1, we reset
the random number generator by s and resample the relevant
entry of z. Using this in-place implementation, MeZO has amemory footprint equivalent to the inference memory cost.

MeZO improves substantially over zero-shot, ICL, and LP
across model types, sizes, and task types, and it performs
comparably to FT over a number of tasks, while drastically reducing the memory cost by, e.g., 12× on OPT-13B.
Appendix G.6 finds that MeZO saves more GPU-hours as
the model scale increases. MeZO can also optimize nondifferentiable objectives, such as accuracy and F1 score(Appendix A.2). We compare the memory consumption of
ICL, FT, LP, and MeZO in Figures 2 and 3.

MeZO can also be combined with other gradient-based
optimizers (e.g., Adam). Though naive implementation
would require storing gradient history, MeZO-momentum
and MeZO-Adam alleviate such overhead by recomputing
past gradients using saved losses and seeds (Appendix D).

3.1. Memory usage

3. Experiments

In this section we profile the memory usage of zero-shot,
ICL, FT, FT (prefix), and MeZO. We test OPT models of
various sizes with Nvidia A100 GPUs (80GB memory) on
MultiRC (average #tokens=400), and report the peak GPU
memory consumption (Appendix F.7). As shown in Figure 2 and Appendix G.5, MeZO exhibits the same memory
consumption as zero-shot while offering memory savingsof up to 12× compared to standard FT and 6× compared to
FT (prefix). This advantage enables training larger models
within a fixed hardware budget (Figure 3) Using a single

Preliminary experiments (Appendix C) show that MeZO
only works when using prompts (Brown et al., 2020; Schickand Schütze, 2021; Gao et al., 2021) (see Appendix F.2) andis generally insensitive to increasing n, so we use n = 1.
We conduct comprehensive experiments on both mediumsized masked LMs (RoBERTa-large, 350M (Liu et al.,2019b)) and large autoregressive LMs (OPT-13B, 30B,
66B (Zhang et al., 2022)) in few-shot and many-shot set3

Fine-Tuning Language Models with Just Forward Passes

A100 GPU, MeZO tunes a model that is 11× larger thanwhat is feasible with FT. Appendix E studies the theoreticalmemory-time tradeoffs of backpropagation and MeZO.

Agarwal et al., 2012; Raginsky and Rakhlin, 2011; Duchi
et al., 2015; Shamir, 2017; Nemirovskij and Yudin, 1983;
Wang et al., 2020). (Wang et al., 2018; Balasubramanian andGhadimi, 2018; Cai et al., 2022) showed that leveraged lowdimensional gradient structure to improve efficiency, though
the estimation has at least Ω(sd log d) memory cost. Salient
applications of ZO to deep learning are distributed methods (Tang and Li, 2019; Hajinezhad and Zavlanos, 2018)
and black-box adversarial example generation (Cai et al.,2021; Liu et al., 2019a; Chen et al., 2017; Liu et al., 2020b).
Some ZO methods do not estimate the gradient (Golovin
et al., 2020; Mania et al., 2018; Hinton, 2022).

4. Theory
Our theoretical analysis (Appendix B) highlights why
MeZO can optimize large LMs, although a number of classical results (Nemirovskij and Yudin, 1983; Jamieson et al.,2012; Raginsky and Rakhlin, 2011; Agarwal et al., 2012)suggest that optimization should be catastrophically slow
when training so many parameters. We show that when
the loss landscape exhibits favorable conditions (Assumption 1), we can derive a convergence rate independent of
the number of parameters: the loss decreases per step at a
rate independent of the parameter dimension d (Theorem 1),
and, under stronger conditions, the algorithm converges intime independent of d (Lemma 3). Together, these results
imply that MeZO is not catastrophically slower than SGD
when fine-tuning.1 Our main assumption is that the Hessianof the loss exhibits small local effective rank.2
Assumption 1 (Local r-effective rank). Let G(θt ) =max(x,y)∈D k∇L(θt ; {(x, y)})k. There exists a matrix
H(θt ) such that:
1. For all θ such that kθ − θt k ≤ ηdG(θt ), we have
∇2 L(θ)  H(θt ).
2. TheeffectiverankofH(θt ),i.etr(H(θt ))/ kH(θt )kop , is at most r.
This assumption allows us to show that the loss decreases at
a rate independent of d.
Theorem 1 (Dimension-Free Rate). Assume the loss exhibits local r-effective rank (Assumption 1). If θt+1 =bθt − ηZO ∇L(θt ; B) is a single step of ZO-SGD using the nSPSA estimate with a minibatch of size B, then there exists
a γ = Θ(r/n) such that the expected loss decrease can bebounded as

Memory-efficient backpropagation Backpropagation
can be made more efficient by sparsifying gradients (Sunet al., 2017; Wei et al., 2017), approximating Jacobians (Abdel-Khalik et al., 2008; Choromanski and
Sindhwani, 2017), and subsampling the computationalgraph (Oktay et al., 2020; Adelman et al., 2021), thoughthese methods may accrue large approximation errors
for deep networks. Gradient checkpointing (Chen et al.,2016), FlashAttention (Dao et al., 2022), and quantization
works (Dettmers et al., 2022a;b) all present other ways toreduce the memory overhead of handling large models.
Gradient-free adaptation of large language models
BBT and BBTv2 (Sun et al., 2022b;a) use evolutionary
algorithms to achieve gradient-free optimization but is limited to low-dimension projection of prefixes and smaller
models in few-shot settings. Other works focus on optimizing discrete prompts without updating the model (Chai et al.,2022; Deng et al., 2022; Diao et al., 2022; Hou et al., 2022;
Prasad et al., 2022).

6. Conclusion
MeZO may be applicable to pruning, distillation, saliency,
interpretability, and dataset selection for fine-tuning. Nondifferentiable objectives are a particularly exciting area,
given recent advances in tuning large LMs to adapt to human
feedback. Theoretical analyses of these gradient estimatesin new applications are of interest.

2

E[L(θt+1 ) | θt ] − L(θt ) ≤ − ηZO k∇L(θt )k1 2
2` · γ · E[k∇L(θ; B)k ]+ ηZO
2

5. Related work
Zeroth-order optimization Classical lower bounds depend on the number of parameters d (Jamieson et al., 2012;

Acknowledgements
We thank Kaifeng Lyu, Abhishek Panigrahi, Nikunj Saunshi, and Mengzhou Xia for their helpful feedback. SA andSM are funded by NSR, ONR, SRC, and Simons Foundation. JDL, AD, and EN acknowledge the support of the
ARO under MURI Award W911NF-11-1-0304, the Sloan
Research Fellowship, NSF CCF 2002272, NSF IIS 2107304,
NSF CIF 2212262, ONR Young Investigator Award, andNSF CAREER Award 2144994. This work is also partially
funded by the National Science Foundation (IIS-2211779).

1

Section 3 uses the standard choice of Adam for FT; we provide
SGD experiments in Appendix G.1.
2
It is prohibitively expensive to directly measure the effective
rank of the Hessian of a large LM on a reasonably sized dataset.
However, many previous works have shown that the Hessian of
the loss for deep neural networks trained by SGD has remarkably
low effective rank (Papyan, 2018; 2020; Ghorbani et al., 2019; Yao
et al., 2020; Wu et al., 2020; Sagun et al., 2017), and Aghajanyan
et al. (2021); Li et al. (2018) demonstrated that LM fine-tuning canoccur in a very low dimensional subspace (< 200 parameters).

4Fine-Tuning Language Models with Just Forward Passes

References

Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah,
Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.
Language models are few-shot learners. In Advances inneural information processing systems, volume 33, pages
1877–1901, 2020.

Hany S Abdel-Khalik, Paul D Hovland, Andrew Lyons,Tracy E Stover, and Jean Utke. A low rank approach
to automatic differentiation. In Advances in Automatic
Differentiation, pages 55–65, 2008.
Menachem Adelman, Kfir Levy, Ido Hakimi, and Mark
Silberstein. Faster neural network training with approximate tensor operations. Advances in Neural Information
Processing Systems, 34:27877–27889, 2021.

HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin.
A zeroth-order block coordinate descent algorithm forhuge-scale black-box optimization. In International Conference on Machine Learning, pages 1193–1203, 2021.

Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar,and Martin J. Wainwright. Information-theoretic lower
bounds on the oracle complexity of stochastic convex
optimization. IEEE Transactions on Information Theory,
58(5):3235–3249, May 2012.

HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang
Zhang. Zeroth-order regularized optimization (zoro):
Approximately sparse gradients and adaptive sampling.
SIAM Journal on Optimization, 32(2):687–714, 2022.

Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer.
Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Proceedings of the 59th
Annual Meeting of the Association for Computational
Linguistics and the 11th International Joint Conference
on Natural Language Processing (Volume 1: Long Papers), pages 7319–7328, 2021.

Yekun Chai, Shuohuan Wang, Yu Sun, Hao Tian, Hua Wu,
and Haifeng Wang. Clip-tuning: Towards derivative-free
prompt learning with a mixture of rewards. arXiv preprint
arXiv:2210.12050, 2022.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and
Cho-Jui Hsieh. Zoo: Zeroth order optimization based
black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM
workshop on artificial intelligence and security, pages
15–26, 2017.

Stephen H Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Fevry, et al. Promptsource: An integrated development environment andrepository for natural language prompts. arXiv preprint
arXiv:2202.01279, 2022.

Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin.
Training deep nets with sublinear memory cost. arXiv
preprint arXiv:1604.06174, 2016.

Krishnakumar Balasubramanian and Saeed Ghadimi.
Zeroth-order (non)-convex stochastic optimization via
conditional gradient and gradient updates. In Advancesin Neural Information Processing Systems, volume 31,
2018.

Krzysztof M Choromanski and Vikas Sindhwani. On blackbox backpropagation and jacobian sensing. In Advancesin Neural Information Processing Systems, volume 30,
2017.

Roy Bar Haim, Ido Dagan, Bill Dolan, Lisa Ferro, Danilo
Giampiccolo, Bernardo Magnini, and Idan Szpektor. The
second PASCAL recognising textual entailment challenge. In Proceedings of the Second PASCAL Challenges
Workshop on Recognising Textual Entailment, 2006.

Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom
Kwiatkowski, Michael Collins, and Kristina Toutanova.
BoolQ: Exploring the surprising difficulty of natural
yes/no questions. In Proceedings of the 2019 Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 2924–
2936, 2019.

Luisa Bentivogli, Peter Clark, Ido Dagan, and Danilo Giampiccolo. The fifth PASCAL recognizing textual entailment challenge. In TAC, 2009.

Ido Dagan, Oren Glickman, and Bernardo Magnini. The
PASCAL recognising textual entailment challenge. In
the First International Conference on Machine Learning
Challenges: Evaluating Predictive Uncertainty VisualObject Classification, and Recognizing Textual Entailment, 2005.

Raghu Bollapragada, Richard Byrd, and Jorge Nocedal.
Adaptive sampling strategies for stochastic optimization.
SIAM Journal on Optimization, 28(4):3312–3343, 2018.
Samuel R. Bowman, Gabor Angeli, Christopher Potts, andChristopher D. Manning. A large annotated corpus forlearning natural language inference. In Proceedings ofthe 2015 Conference on Empirical Methods in Natural
Language Processing, pages 632–642, 2015.

Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact
5Fine-Tuning Language Models with Just Forward Passes

attention with io-awareness. In Advances in Neural Information Processing Systems, volume 35, pages 16344–
16359, 2022.

IEEE Transactions on Information Theory, 61(5):2788–
2806, 2015.
FairScale authors. Fairscale: A general purpose modular
pytorch library for high performance and large scale training, 2021.

Marie-Catherine De Marneffe, Mandy Simons, and Judith
Tonhauser. The commitmentbank: Investigating projection in naturally occurring discourse. In Sinn und Bedeutung, volume 23, pages 107–124, 2019.

Tianyu Gao, Adam Fisch, and Danqi Chen. Making pretrained language models better few-shot learners. In Proceedings of the 59th Annual Meeting of the Association
for Computational Linguistics and the 11th International
Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 3816–3830, 2021.

Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan
Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing,
and Zhiting Hu. RLPrompt: Optimizing discrete text
prompts with reinforcement learning. In Proceedings ofthe 2022 Conference on Empirical Methods in Natural
Language Processing, pages 3369–3391, 2022.

Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An
investigation into neural net optimization via hessian
eigenvalue density. In International Conference on Machine Learning, pages 2232–2241, 2019.

Tim Dettmers, Mike Lewis, Younes Belkada, and Luke
Zettlemoyer. GPT3.int8(): 8-bit matrix multiplication fortransformers at scale. In Advances in Neural Information
Processing Systems, 2022a.

Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, andBill Dolan. The third PASCAL recognizing textual entailment challenge. In the ACL-PASCAL Workshop on
Textual Entailment and Paraphrasing, 2007.

Tim Dettmers, Mike Lewis, Sam Shleifer, and Luke Zettlemoyer. 8-bit optimizers via block-wise quantization. In
International Conference on Learning Representations,2022b.

Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee,
Xingyou Song, and Qiuyi Zhang. Gradientless descent:High-dimensional zeroth-order optimization. In International Conference on Learning Representations, 2020.

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina
Toutanova. BERT: Pre-training of deep bidirectionaltransformers for language understanding. In Proceedingsof the 2019 Conference of the North American Chapterof the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short
Papers), pages 4171–4186, 2019.

Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch,
Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint
arXiv:1706.02677, 2017.
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algorithmic differentiation. SIAM, 2008.

Shizhe Diao, Xuechun Li, Yong Lin, Zhichao Huang, andTong Zhang. Black-box prompt learning for pre-trained
language models. arXiv preprint arXiv:2201.08531,
2022.

José Grimm, Loı̄c Pottier, and Nicole Rostaing-Schmidt.
Optimal time and minimum space-time product for reversing a certain class of programs. PhD thesis, INRIA,
1996.

Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan
Yang, Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min
Chan, Weize Chen, et al. Delta tuning: A comprehensive
study of parameter efficient methods for pre-trained language models. arXiv preprint arXiv:2203.06904, 2022.

Suchin Gururangan, Ana Marasović, Swabha Swayamdipta,
Kyle Lo, Iz Beltagy, Doug Downey, and Noah A. Smith.
Don’t stop pretraining: Adapt language models to domains and tasks. In Proceedings of the 58th Annual
Meeting of the Association for Computational Linguistics,
pages 8342–8360, 2020.

Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel
Stanovsky, Sameer Singh, and Matt Gardner. DROP:
A reading comprehension benchmark requiring discretereasoning over paragraphs. In Proceedings of the 2019
Conference of the North American Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long and Short Papers), pages
2368–2378, 2019.

Davood Hajinezhad and Michael M Zavlanos. Gradient-free
multi-agent nonconvex nonsmooth optimization. In 2018
IEEE Conference on Decision and Control (CDC), pages
4939–4944, 2018.

John C. Duchi, Michael I. Jordan, Martin J. Wainwright,
and Andre Wibisono. Optimal rates for zero-order convex
optimization: The power of two function evaluations.

Geoffrey Hinton.
The forward-forward algorithm:
Some preliminary investigations.
arXiv preprint
arXiv:2212.13345, 2022.
6Fine-Tuning Language Models with Just Forward Passes

Bairu Hou, Joe O’Connor, Jacob Andreas, Shiyu Chang,and Yang Zhang. Promptboosting: Black-box textclassification with ten forward passes. arXiv preprint
arXiv:2212.09257, 2022.

Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedingsof the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint
Conference on Natural Language Processing (Volume 1:
Long Papers), pages 4582–4597, 2021.

Edward J Hu, yelong shen, Phillip Wallis, Zeyuan AllenZhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu
Chen. LoRA: Low-rank adaptation of large language
models. In International Conference on Learning Representations, 2022.

Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora. On the validity of modeling SGD with stochastic differential equations (SDEs). In A. Beygelzimer, Y. Dauphin, P. Liang,
and J. Wortman Vaughan, editors, Advances in Neural
Information Processing Systems, 2021.

Kevin G Jamieson, Robert Nowak, and Ben Recht. Querycomplexity of derivative-free optimization. In Advancesin Neural Information Processing Systems, volume 25,
2012.

Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan,
Lawrence Carin, and Weizhu Chen. What makes goodin-context examples for GPT-3? In Proceedings of Deep
Learning Inside Out (DeeLIO 2022): The 3rd Workshop
on Knowledge Extraction and Integration for Deep Learning Architectures, pages 100–114, 2022.

Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C.J.
Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q.
Weinberger, editors, Advances in Neural Information Processing Systems, volume 26, 2013.

Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen,
and Jiawei Han. Understanding the difficulty of training
transformers. In Proceedings of the 2020 Conferenceon Empirical Methods in Natural Language Processing(EMNLP), pages 5747–5763, 2020a.

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear
convergence of gradient and proximal-gradient methods
under the polyak-łojasiewicz condition, 2020.
Daniel Khashabi, Snigdha Chaturvedi, Michael Roth,Shyam Upadhyay, and Dan Roth. Looking beyond thesurface: A challenge set for reading comprehension overmultiple sentences. In Proceedings of the 2018 Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 252–262, 2018.

Sijia Liu, Bhavya Kailkhura, Pin-Yu Chen, Paishun Ting,
Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In
Advances in Neural Information Processing Systems, volume 31, 2018.

Diederik P Kingma and Jimmy Ba. Adam: A method forstochastic optimization. In International Conference on
Learning Representations, 2015.

Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong.
signSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019a.

Ananya Kumar, Aditi Raghunathan, Robbie Matthew Jones,
Tengyu Ma, and Percy Liang. Fine-tuning can distort
pretrained features and underperform out-of-distribution.
In International Conference on Learning Representations,
2022.

Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang,
Alfred O Hero III, and Pramod K Varshney. A primer
on zeroth-order optimization in signal processing andmachine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43–54,
2020b.

Brian Lester, Rami Al-Rfou, and Noah Constant. The powerof scale for parameter-efficient prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in
Natural Language Processing, pages 3045–3059, 2021.

Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke
Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly
optimized bert pretraining approach. arXiv preprint
arXiv:1907.11692, 2019b.

Hector Levesque, Ernest Davis, and Leora Morgenstern.
The winograd schema challenge. In Thirteenth international conference on the principles of knowledge representation and reasoning, 2012.

Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel,and Pontus Stenetorp. Fantastically ordered prompts andwhere to find them: Overcoming few-shot prompt ordersensitivity. In Proceedings of the 60th Annual Meeting of
the Association for Computational Linguistics (Volume 1:
Long Papers), pages 8086–8098, 2022.

Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason
Yosinski. Measuring the intrinsic dimension of objective
landscapes. In International Conference on Learning
Representations, 2018.
7

Fine-Tuning Language Models with Just Forward Passes

Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen,
and Sanjeev Arora. A kernel-based view of language
model fine-tuning. arXiv preprint arXiv:2210.05643,
2022.

Maxim Raginsky and Alexander Rakhlin. Informationbased complexity, feedback and dynamics in convex programming. IEEE Transactions on Information Theory,57(10):7036–7056, 2011.

Horia Mania, Aurelia Guy, and Benjamin Recht. Simple
random search of static linear policies is competitive forreinforcement learning. In Advances in Neural Information Processing Systems, volume 31, 2018.

Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, andPercy Liang. SQuAD: 100,000+ questions for machinecomprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383–2392, 2016.

Arkadij Semenovič Nemirovskij and David Borisovich
Yudin. Problem complexity and method efficiency inoptimization. 1983.

Melissa Roemmele, Cosmin Adrian Bejan, and Andrew S
Gordon. Choice of plausible alternatives: An evaluationof commonsense causal reasoning. 2011.

Deniz Oktay, Nick McGreivy, Joshua Aduol, Alex Beatson,
and Ryan P Adams. Randomized automatic differentiation. arXiv preprint arXiv:2007.10412, 2020.
OpenAI.
Gpt-4 technical report.
arXiv:2303.08774, 2023.

Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin,and Leon Bottou. Empirical analysis of the hessianof over-parametrized neural networks. arXiv preprint
arXiv:1706.04454, 2017.

arXiv preprint

Timo Schick and Hinrich Schütze. Exploiting clozequestions for few-shot text classification and natural language inference. In Proceedings of the 16th Conferenceof the European Chapter of the Association for Computational Linguistics: Main Volume, pages 255–269, 2021.

Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human
feedback. Advances in Neural Information Processing
Systems, 35:27730–27744, 2022.

Ohad Shamir. An optimal algorithm for bandit and zeroorder convex optimization with two-point feedback. The
Journal of Machine Learning Research, 18(1):1703–1713,
2017.

Vardan Papyan. The full spectrum of deepnet hessians at
scale: Dynamics with sgd training and sample size. arXiv
preprint arXiv:1811.07062, 2018.

Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang,
Christopher D. Manning, Andrew 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
Processing, 2013.

Vardan Papyan. Traces of class/cross-class structure pervade
deep learning spectra. Journal of Machine Learning
Research, 21(252):1–64, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer,
James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito,
Martin Raison, Alykhan Tejani, Sasank Chilamkurthy,
Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance
deep learning library. In Advances in Neural Information
Processing Systems 32, pages 8024–8035. 2019.

J.C. Spall. Multivariate stochastic approximation using asimultaneous perturbation gradient approximation. IEEE
Transactions on Automatic Control, 37(3):332–341, 1992.
Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou,
Xuanjing Huang, and Xipeng Qiu. BBTv2: Towards a
gradient-free future with large language models. In Proceedings of the 2022 Conference on Empirical Methods in
Natural Language Processing, pages 3916–3930, 2022a.

Mohammad Taher Pilehvar and Jose Camacho-Collados.
WiC: the word-in-context dataset for evaluating contextsensitive meaning representations. In Proceedings of the2019 Conference of the North American Chapter of the
Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers),
pages 1267–1273, 2019.

Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang,and Xipeng Qiu. Black-box tuning for language-modelas-a-service. In International Conference on Machine
Learning, pages 20841–20855, 2022b.
Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang.
meProp: Sparsified back propagation for accelerated deeplearning with reduced overfitting. In Proceedings of the34th International Conference on Machine Learning, volume 70, pages 3299–3308, 2017.

Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit
Bansal. Grips: Gradient-free, edit-based instruction
search for prompting large language models. arXiv
preprint arXiv:2203.07281, 2022.
8Fine-Tuning Language Models with Just Forward Passes

Yujie Tang and Na Li. Distributed zero-order algorithms
for nonconvex multi-agent optimization. In 2019 57th
Annual Allerton Conference on Communication, Control,and Computing (Allerton), pages 781–786, 2019.

Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain
Gugger, Mariama Drame, Quentin Lhoest, and Alexander
Rush. Transformers: State-of-the-art natural language
processing. In Proceedings of the 2020 Conference on
Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, 2020.

Zhiwei Tang, Dmitry Rybin, and Tsung-Hui Chang. Zerothorder optimization meets human feedback: Provablelearning via ranking oracles, 2023.

Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, andRong Ge. Dissecting hessian: Understanding common
structure of hessian in neural networks. arXiv preprint
arXiv:2010.04261, 2020.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, andIllia Polosukhin. Attention is all you need. In Advances inneural information processing systems, volume 30, 2017.

Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W
Mahoney. Pyhessian: Neural networks through the lensof the hessian. In 2020 IEEE international conference on
big data (Big data), pages 581–590, 2020.

Ellen M Voorhees and Dawn M Tice. Building a question answering test collection. In the 23rd annual international
ACM SIGIR conference on Research and development in
information retrieval, 2000.

Sheng Zhang, Xiaodong Liu, Jingjing Liu, Jianfeng Gao,
Kevin Duh, and Benjamin Van Durme. Record: Bridging
the gap between human and machine commonsense reading comprehension. arXiv preprint arXiv:1810.12885,
2018.

Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet
Singh, Julian Michael, Felix Hill, Omer Levy, and SamuelBowman. Superglue: A stickier benchmark for generalpurpose language understanding systems. In Advances inneural information processing systems, volume 32, 2019.

Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe,
Moya Chen, Shuohui Chen, Christopher Dewan, MonaDiab, Xian Li, Xi Victoria Lin, et al. Opt: Open pretrained transformer language models. arXiv preprint
arXiv:2205.01068, 2022.

Chong Wang, Xi Chen, Alexander J Smola, and Eric P Xing.
Variance reduction for stochastic gradient optimization.
In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani,
and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Yining Wang, Simon Du, Sivaraman Balakrishnan, andAarti Singh. Stochastic zeroth-order optimization in highdimensions. In Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics,
volume 84, pages 1356–1365, 2018.
Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian
Ma, and Meisam Razaviyayn. Zeroth-order algorithms
for nonconvex minimax problems with improved complexities. arXiv preprint arXiv:2001.07819, 2020.
Bingzhen Wei, Xu Sun, Xuancheng Ren, and Jingjing Xu.
Minimal effort back propagation for convolutional neuralnetworks. arXiv preprint arXiv:1709.05804, 2017.
Adina Williams, Nikita Nangia, and Samuel Bowman. A
broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), 2018.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac,
Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison,9Fine-Tuning Language Models with Just Forward Passes

A. Additional Results
A.1. Medium-sized masked language models
We conduct experiments with RoBERTa-large on sentiment classification, natural language inference, and topic classification
tasks. We follow (Gao et al., 2021; Malladi et al., 2022) to study the few-shot and many-shot settings, sampling k examples
per class for k = 16 and k = 512 (details in Appendix F). We summarize the results from Figure 4 and Table 17 below.
k=16 RoBERTa-large

Accuracy (%)

100
90

90

80

80

70

70

60

60

50

50

40

40

30

SST-2

SST-5

SNLI

MNLI

k=512 RoBERTa-large

100

RTE

Zero-shot
MeZO (prefix)

TREC

LP
FT

30

SST-2

SST-5

MeZO
FT (LoRA)

SNLI

MNLI

MeZO (LoRA)
FT (prefix)

RTE

TREC

Figure 4: Experiments on RoBERTa-large. We report zero-shot, linear probing (LP), and MeZO and fine-tuning (FT) withfull parameter, LoRA, and prefix-tuning. MeZO outperforms zero-shot and LP and approaches FT (within 5% for k = 512)with much less memory. Detailed numbers in Table 17.

MeZO works significantly better than zero-shot, linear probing, and other memory-equivalent methods. On all six
diverse tasks, MeZO can optimize the pre-trained model and consistently perform better than zero-shot and linear probing.
We also show for several tasks that MeZO can outperform another ZO algorithm, BBTv2 (Sun et al., 2022a), by up to 11%
absolute (Appendix G.4).3
With enough data, MeZO achieves comparable performance (up to 5% gap) to FT. MeZO achieves close-to-finetuning performance on k = 16, with some tasks only having 2% gaps. When using k = 512 data, the gap between MeZO
and FT further reduced to within 5% across all tasks.
MeZO works well on both full-parameter tuning and PEFT. Full-parameter tuning (MeZO) and PEFT (MeZO with
LoRA and prefix-tuning) achieve comparable performance, while MeZO (prefix) sometimes outperforms MeZO. We also
show in Appendix G.3 that the three variants converge at similar rates, agreeing with our theory in Section 4, which showsthat MeZO converges at a rate independent of the number of parameters being optimized.
We show additional results with more FT (FT with SGD) and MeZO variants in Appendix G.1. We see that (1) ZOAdam sometimes outperforms ZO-SGD but is not consistent across tasks; (2) LP and then MeZO, as suggested forfine-tuning (Kumar et al., 2022), can sometimes improve the performance.
A.2. Training with non-differentiable objectives
We demonstrate the efficacy of MeZO for optimizing non-differentiable objectives through initial experiments. Accuracy andF1 are used as the respective objectives (details in Appendix F.6). Table 3 reveals that MeZO with accuracy/F1 successfully
optimizes LMs with superior performance to zero-shot. Although minimizing cross entropy results in stronger performance,these preliminary findings highlight the promising potential of applying MeZO to optimize non-differentiable objectives
without clear differentiable surrogates, such as human preferences (Ouyang et al., 2022).
3

BBTv2 is sensitive to #parameters and can only train down-projected prefixes instead of the full model.

10Fine-Tuning Language Models with Just Forward Passes

Task

SST-2

RTE

BoolQ

WSC

WIC

SQuAD

30B zero-shot
30B ICL30B MeZO/MeZO (prefix)

56.7
81.9
90.6

52.0
66.8
72.6

39.1
66.2
73.5

38.5
56.7
63.5

50.2
51.3
59.1

46.5
78.0
85.2

66B zero-shot
66B ICL66B MeZO/MeZO (prefix)

57.5
89.3
93.6

67.2
65.3
66.4

66.8
62.8
73.7

43.3
52.9
63.5

50.6
54.9
58.9

48.1
81.3
85.0

Table 1: Experiments on OPT-30B and OPT-66B (with 1,000 examples). We report the best of MeZO and MeZO (prefix).
See Appendix G.2 for more results. We see that on most tasks MeZO effectively optimizes up to 66B models and outperforms
zero-shot and ICL.

Task
Task type

SST-2 RTE CB BoolQ WSC WIC MultiRC COPA ReCoRD SQuAD DROP———————— classification ———————— – multiple choice – — generation —Zero-shot
ICL
LP

58.8
87.0
93.4

59.6 46.4
62.1 57.1
68.6 67.9

59.0
66.9
59.3

38.5
39.4
63.5

55.0
50.5
60.2

46.9
53.1
63.5

80.0
87.0
55.0

81.2
82.5
27.1

46.2
75.9
3.7

14.6
29.6
11.1

MeZO
MeZO (LoRA)MeZO (prefix)

91.4
89.6
90.7

66.1 67.9
67.9 66.1
70.8 69.6

67.6
73.8
73.1

63.5
64.4
57.7

61.1
59.7
59.9

60.1
61.5
63.7

88.0
87.0
84.0

81.7
81.4
81.2

84.7
83.8
84.2

30.9
31.4
28.9

FT (12x memory)

92.0

70.8 83.9

77.1

63.5

70.1

71.1

79.0

74.1

84.9

31.3

Table 2: Experiments on OPT-13B (with 1,000 examples). ICL: in-context learning; LP: linear probing; FT: full fine-tuningwith Adam. MeZO outperforms zero-shot, ICL, and LP across the board, and achieves comparable (within 1%) or better
performance than FT on 7 out of 11 tasks.

Model
Task

RoBERTa-large (350M)
SST-2 SST-5 SNLI TREC

Zero-shot
Cross entropy (FT)
Cross entropy (MeZO)
Accuracy/F1 (MeZO)

79.0
93.9
93.3
92.7

35.5
55.9
53.2
48.9

50.2
88.7
83.0
82.7

32.0
97.3
94.3
68.6

OPT-13B
SQuAD
46.2
84.2
84.7
78.5

Table 3: MeZO with non-differentiable objectives. For classification (k = 512), we use MeZO with full-parameter andoptimize accuracy; for SQuAD (1,000 examples), we use MeZO (prefix) and F1.

A.3. Wall Clock TimeIn this section, we measure the wallclock time efficiency of MeZO compared to full-parameter FT, with respect to different
model sizes. We conduct our experiments with 80GB A100s connected by NVLink and InfiniteBand, which are stateof-the-art solutions for distributed training. As shown in Table 22, on the MultiRC datasets, training with MeZO brings
7.74× speedup per step compared to full-parameter FT on a 30B model. This is due to (1) MeZO does not require costly
backpropagation and (2) MeZO requires fewer GPUs and reduces the multi-GPU communication overhead.
Note that even though MeZO has better per-step wallclock efficiency, it requires significantly more steps than standard FT.
Taking our OPT-30B experiments as an example: MeZO takes 32× more steps than standard FT, while FT takes 8× more
GPUs and 7.74× more time per step. Overall, MeZO requires only half as many GPU-hours as FT.
11

Fine-Tuning Language Models with Just Forward Passes
Method
13B
30B

MeZO

Full-parameter FT

1× (2.72s)
1× (5.90s)

2.52×
7.74×

Table 4: Wallclock time per step of different training methods. It is measured on 80GB A100s with NVLink and InfiniteBandconnections. The wallclock time is averaged over 100 steps. It is measured on the MultiRC task with the OPT family. 13B
and 30B OPT require 1 A100 with MeZO and 4 and 8 A100s with FT respectively.

B. Theory
We follow classical analyses of SGD and replace the mini-batch gradient estimate with SPSA. Consider the minibatch
SGD update θt+1 ← θt − η∇L(θ; Bt ) where Bt is a minibatch drawn uniformly from DB . Crucially, the SGD minibatch
gradient estimate is unbiased.
Definition 2 (Unbiased Gradient Estimate). Any minibatch gradient estimate g(θ, B) is said to be unbiased if E[g(θ, B)] =∇L(θ).
B.1. Per-step analysis
The classical descent lemma uses a Taylor expansion to study how SGD reduces the loss at each optimization step. It
highlights that when the gradient covariance is large, the maximum possible decrease in loss at each optimization step issmall, thereby resulting in slower optimization.
Lemma 1 (Descent Lemma). Let L(θ) be `-smooth.4 For any unbiased gradient estimate g(θ, B),
1
2
2
E[L(θt+1 ) | θt ] − L(θt ) ≤ −η k∇L(θt )k + η 2 ` · E[kg(θ, Bt )k ].
2(1)

The descent lemma highlights the importance of the gradient norm, which we derive for MeZO below.
Lemma 2. Let B be a random minibatch of size B. Then, the gradient norm of MeZO isi2
d+n−1 h2b=
E k∇L(θ; B)k .
Ex ∇L(θ; B)nwhere n is the number of z sampled in n-SPSA (Definition 1) and d is the number of parameters.

Thus, in the usual case where n  d, MeZO has a much larger gradient norm than SGD.5 The descent lemma also showsthat to guarantee loss decrease, one needs to choose the learning rate as2η≤

2 k∇L(θt )k2` · E[kg(θ, B)k ]Lemma 2======⇒

ηZO =

n
ηSGD
d+n−1

(2)

where ηZO and ηSGD are the maximum permissible learning rates for MeZO and SGD respectively. Thus we see that without
any further assumptions, MeZO can slow optimization by decreasing the largest permissible learning rate by a factor of d.
Moreover, MeZO reduces the loss decrease that can be obtained at each step and, as a consequence, slows convergence by afactor of d as well.
Surprisingly, our experiments show that MeZO can quickly optimize pre-trained models with billions of parameters, andreducing the number of tuned parameters via PEFT techniques does not substantially accelerate optimization (Appendix G.3).
We attribute these phenomena to the Hessian of the loss exhibiting small local effective rank. It is prohibitively expensive todirectly measure the effective rank of the Hessian of a large LM on a reasonably sized dataset. However, many previous
works have shown that the Hessian of the loss for deep neural networks trained by SGD has remarkably low effective rank
(Papyan, 2018; 2020; Ghorbani et al., 2019; Yao et al., 2020; Wu et al., 2020; Sagun et al., 2017). In particular, the bulkof the spectrum concentrates around 0 with only a small number of outliers, and the number of these outliers is an upper
45This is satisfied for the standard cross-entropy objective.
All of our experiments use n = 1.

12

Fine-Tuning Language Models with Just Forward Passes

bound on the effective rank. In addition, prior works (Aghajanyan et al., 2021; Li et al., 2018) have demonstrated that LM
fine-tuning can occur in a very low dimensional subspace (< 200 parameters), which further supports the below assumption.
We formalize the assumption on the effective rank below. In particular, we require an upper bound on the Hessian in aneighborhood around the current iterate to have effective rank at most r.
Assumption 2 (Local r-effective rank, reproduction of Assumption 1). Let G(θt ) = max(x,y)∈D k∇L(θt ; {(x, y)})k.
There exists a matrix H(θt ) such that:
1. For all θ such that kθ − θt k ≤ ηdG(θt ), we have ∇2 L(θ)  H(θt ).
2. The effective rank of H(θt ), i.e tr(H(θt ))/ kH(θt )kop , is at most r.
Under this assumption, we show that the convergence rate of ZO-SGD does not depend on the number of parameters.
Instead, the slowdown factor only depends on the effective rank of the Hessian.
Theorem 2 (Dimension-Free Rate, reproduction of Theorem 1). Assume the loss exhibits local r-effective rank (Assumpb
tion 1). If θt+1 = θt − ηZO ∇L(θt ; B) is a single step of ZO-SGD using the n-SPSA estimate with a minibatch of size B,
then there exists a γ = Θ(r/n) such that the expected loss decrease can be bounded as
1 2
2
2
E[L(θt+1 ) | θt ] − L(θt ) ≤ −ηZO k∇L(θt )k + ηZO` · γ · E[k∇L(θ; B)k ]2

By applying Equation (2), we can directly compare to the SGD descent lemma.
Corollary 1. Choosing the learning rate ηZO = γ −1 · ηSGD , ZO-SGD obtains a loss decrease of


1
1 2
2
2
` · E[k∇L(θ; B)k ] .
E[L(θt+1 ) | θt ] − L(θt ) ≤ · −ηSGD k∇L(θt )k + ηSGD
γ
2

(3)

(4)

Here we see that comparing to SGD, the slowdown factor of ZO-SGD scales with the local effective rank r, which we argue
is much smaller than the number of parameters d. The above analysis focuses on how much ZO-SGD and SGD decrease theloss at each step. Below, we show that under stronger assumptions about the loss landscape, we can obtain rates for how
quickly the ZO-SGD algorithm converges to an optimal value.
B.2. Global convergence analysis
We show that the global convergence rate also slows by a factor proportional to the local effective rank under stronger
assumptions about the loss landscape. We assume that the landscape obeys the classical PL inequality: the gradient norm
grows quadratically with the suboptimality of the iterate.
2
Definition 3 (PL Inequality). Let L∗ = minθ L(θ). The loss L is µ-PL if, for all θ, 21 k∇L(θ)k ≥ µ(L(θ) − L∗ ).
The PL inequality is not as strong as assuming that optimization exhibits kernel-like dynamics, but it ensures that thelandscape is amenable to analysis (Karimi et al., 2020). In addition to the PL inequality, we assume the trace of the gradientcovariance is bounded, so noise does not disrupt the trajectory too drastically.
Definition
4 (Gradient Covariance).
The SGD gradient estimate on a minibatch of size B has covariance Σ(θ) =B(E ∇L(θ; B)∇L(θ; B)> − ∇L(θ)∇L(θ)> ).

As we show in Appendix H.1, this assumption holds for common loss functions such as square loss or binary cross entropy
for several settings (e.g., kernel behavior (Malladi et al., 2022)). With these two assumptions, we show that ZO-SGD has aslowdown proportional to the effective rank r, not the parameter dimension.
Lemma 3 (Global Convergence of ZO-SGD). Let L(θ) be µ-PL and let there exist α such that tr(Σ(θ)) ≤ α(L(θ) − L∗ )for all θ. Then after





 `
 r
L(θ0 ) − L∗ `αt = O
log+1 ·+
µ µ2 B

 n
|
{z
}
SGD rate (Lemma 4)

iterations of ZO-SGD we have E[L(θt )] ≤ L∗ + .

13

Fine-Tuning Language Models with Just Forward Passes

C. Algorithmic Ablations
We perform a number of ablations to select the best algorithm. As is standard in ZO literature, we consider the main
computational cost to be the number of forward passes. In our case, the number of forward passes can be affected by the
number of gradient steps taken, any usage of gradient accumulation, and using more noise samples to reduce the variance ofthe gradient estimate.
We observed that the performance of MeZO improves monotonically with the number of steps, and there does not appear tobe any overfitting. Hence, when performing algorithmic ablations, we can focus on the efficiency of different algorithms
without considering implicit bias. This is also reflected in our theoretical analysis. To ease the computational load, we fix
the number of forward passes to 10, 000 and compare many different algorithms for RoBERTa-large on a smaller set oftasks that span sentiment analysis, entailment, and topic classification: SST-2, SNLI, and TREC. We emphasize that 10, 000
is a small budget and is only used as a setting to compare these ZO algorithms to each other. We find that using a linearlydecreasing learning rate schedule during training, as was done for fine-tuning with backpropagation in (Liu et al., 2019b),
does not help or hurt MeZO. Similarly, using a learning rate warmup leads to identical results on these three tasks. For
simplicity, we use a constant learning rate schedule with no warmup for all of the below experiments. We perform few-shot
experiments with k = 16 and average the results across 5 seeds.

Experiment
MeZO

Hyperparameters

ValuesBatch size
Learning rate
Weight Decay{16, 64} ×{1e−5, 1e−6, 1e−7} ×{1e−3, 1e−5} ×{0, 0.1}

Table 5: The hyperparameter grid used in our ablation experiments. For simplicity, we use a constant learning rate schedule.
C.1. Prompting
We study if adding a prompt is crucial to the ability of MeZO to optimize the network. We use prompts from Gao et al. (2021).
Malladi et al. (2022) claimed the prompt makes the optimization trajectory well-behaved, though we note that the current
paper considers RoBERTa-large and large autoregressive models while the previous work only studied RoBERTa-base.
We note the similarity between kernel behavior and our theoretical setting in Section 4. MeZO succeeds on tasks that arereported to not exhibit kernel behavior in Malladi et al. (2022), so we investigate whether or not the prompt is necessary.

PromptNo Prompt

SST-2

SNLI

TREC

89.6 (1.2)
51.9 (2.9)

65.1 (6.2)
34.8 (2.1)

66.7 (6.2)
19.5 (9.0)

Table 6: Experiments using MeZO to fine-tune models with and without a prompt.
Both experiments followed the grid in Table 5, but we also expanded the grid to include a learning rate of 1e − 4 for the no
prompt case. As a result of these experiments, we fix the setting to prompt-based fine-tuning for all of the below experiments.
C.2. Sample Schedules
One can sample nt noise vectors at the tth step and use nt -SPSA to compute the gradient estimate. Similar ideas were
proposed in Bollapragada et al. (2018); Cai et al. (2022). We study the effect of linearly increasing and constant sampling
schedules in the ablation setting. The intuition for the linearly increasing schedule is that the optimizer may need a higher
fidelity gradient as it approaches the minimum. Increasing the number of zs can speed up optimization by reducing thegradient variance, but doing so also increases the number of forward passes required for each optimization step, so there
is a trade-off to study. We note that increasing the number of zs should be accompanied by a proportional scaling of thelearning rate, analogous to the linear scaling rule proposed in (Goyal et al., 2017) (theoretical justification can follow the14

Fine-Tuning Language Models with Just Forward Passes

SDE technique (Li et al., 2021)). Table 7 shows no consistent benefit in one schedule over the other, and it demonstrates that
increasing the n in n-SPSA while fixing the number of forward passes allowed results in only marginal gains at best.
n

Schedule

SST-2

SNLI

TREC

n=1
n=4
n=4
n = 16n = 16

Constant
Constant
LinearConstant
Linear

89.6 (1.2)
89.5 (1.1)
89.6 (1.4)
90.4 (0.7)
88.9 (1.2)

65.1 (6.2)
68.6 (3.2)
65.3 (6.4)
67.0 (3.4)
62.8 (5.9)

66.7 (6.2)
62.3 (5.6)
66.1 (5.5)
62.8 (6.3)
64.2 (5.3)

Table 7: Experiments using MeZO with different schedules for n. We scale the learning rate proportionally to the number ofz’s sampled.

D. MeZO Variants
There is a rich history of transferring ideas from first order optimization to enhance ZO algorithms. Below, we highlightseveral variants of MeZO that did not achieve as high performance as the algorithm presented in Algorithm 1.
D.1. Memory-efficient n-SPSA
We highlight how MeZO can perform n-SPSA (Definition 1) efficiently for n > 1 in Algorithm 2. In particular, if samplingn z vectors and averaging the projected gradients, we require storing 2n additional scalars: the random seeds and the
projected gradients. The same caveat about perturbing individual weights versus entire weight matrices still applies here
(see Section 2).
D.2. Augmenting MeZO with Gradient History
The n-SPSA algorithm merely provides a gradient estimate that can subsequently be used in place of the gradient in any
gradient-based optimizer. Many popular optimizers, such as Adam and SGD with momentum, require storing some historicalinformation about gradients (e.g., a moving average). This requirement causes such algorithms to require 2× or 3× thememory that is needed for SGD.
However, one advantage of MeZO is that the gradient history can be recomputed at each step without requiring muchadditional memory. In reference to Algorithm 1, note that the gradient only needs projected_grad and the random
seed s used to compute the perturbation z. projected_grad can be recomputed from the two perturbed losses `1 and`2 , so we need to only store 3 scalars per step to reproduce the gradient history (i.e., up to 3T scalars during training). Thisis a substantial reduction in added memory overhead that is usually needed for using Adam or momentum instead of vanilla
SGD.
Table 17 illustrates that MeZO-Adam can sometimes improve the performance of MeZO, though each gradient step requires
additional computation (but no additional forward passes). We leave it to future work to investigate when MeZO-Adam may
be more useful than MeZO.

ExperimentHyperparameters

Values

MeZO-Adam

Batch size
Learning rate
Weight Decay64{1e−6, 1e−5, 1e−4, 5e−4, 1e−3}
1e−30Table 8: The hyperparameter grid used for MeZO-Adam. For simplicity, we use a constant learning rate schedule.

15Fine-Tuning Language Models with Just Forward Passes

Algorithm 2: MeZO with n > 1
Require: parameters θ ∈ Rd , loss L : Rd → R, step budget T , perturbation scale , batch size B learning rate schedule{ηt }, n for n-SPSA estimate (Definition 1)
for t = 1, ..., T do
seeds, projected_grads ← []for j = 1, ..., n do
Sample batch B ⊂ DB and random seed sθ ← PerturbParameters(θ, , s)`+ ← L(θ; B)θ ← PerturbParameters(θ, −2, s)`− ← L(θ; B)θ ← PerturbParameters(θ, , s)projected_grad ← (`+ − `− )/(2)projected_grads[j] ← projected_grad
seeds[j] ← send. Will each contain n scalars. Reset parameters

for j = 1, ..., n do
Reset random number generator with seed seeds[j]for θi ∈ θ doz ∼ N (0, 1)
θi ← θi − (ηt /n) ∗ projected_grads[j] ∗ z
end
end
end
Subroutine PerturbParameters(θ, , s)
Reset random number generator with seed sfor θi ∈ θ doz ∼ N (0, 1)
θi ← θi + z
end
return θ. Avg grad for z1 , ..., zn. For sampling z. Modify parameters in place

16Fine-Tuning Language Models with Just Forward Passes

D.3. Modifying the Variance of MeZO
Our theory in Section 4 sketches the well-known fact that the variance of the stochastic gradient estimate can impact
the rate of optimization. ZO methods can be combined with standard variance reduction techniques to possibly improve
optimization speed. For example, Liu et al. (2018) designed a variance reduced ZO algorithm, analogous to SVRG (Johnson
and Zhang, 2013), to improve the speed of convergence. Below, we show that several variance reduction methods (e.g.,using the gradient norm) can be implemented in a memory-efficient manner. However, when controlling for the total budgetof forward passes (i.e., function queries), these methods are not as performant as MeZO. We nevertheless present them todemonstrate the ease with which MeZO can be adapted, and we suggest these methods may be useful for optimizing more
complex objectives.
First, we define a general SPSA estimate that has the same expectation (i.e., the true gradient) but has a scaled variance.
Definition 5 (Variance-Modified SPSA). Given a matrix D = diag(d), the variance modified SPSA computes
L(θ + (d
e
∇L(θ;
B) =

−1

z); B) − L(θ − (d−12z); B)(dz)

where d ∈ Rd has nonzero entries and d−1 denotes the coordinatewise reciprocal.
e
The above SPSA variant is an unbiased estimator of the gradient, because E[∇L(θ;B)] = E[D−1 zz > D∇L(θ; B)] =E[∇L(θ; B)]. We will draw inspiration from classical methods (i.e., “control variates”) and choose d to be a block vector
with gradient norms or parameter norms (Wang et al., 2013). To select the parameter groups, we split the model by layer,
keeping the embedding and the head separate (i.e., RoBERTa-large has 24 + 2 = 26 parameter groups). It is straightforward
to measure the parameter norms without consuming additional memory. We can measure the gradient norms without
performing backpropagation, as shown below.
Proposition 1 (ZO Estimate of Gradient Norm of `th Layer). Define z` to have z ∼ N (0, 1) in each coordinate corresponding to parameters in the `th layer and 0 everywhere else. Then, we can estimate the norm of the gradient of the loss
w.r.t. the `th layer ∇θ` ask∇θ` L(θ; B)k2 ≈L(θ + z` ; B) − L(θ − z` ; B)2

As is true for SPSA, increasing the number of z` ’s sampled for each value of ` and averaging the result reduces the varianceof the estimate. The rationale for this estimate is that for any vector v, Ez [(hv, zi)2 ] = kvk22 for Gaussian z. It is clear that
this estimate can be computed in a memory efficient way, although it requires 2L forward passes to compute gradient norms
for L parameter groups.
We show the experimental results for modifying the variance below. We follow the ablation setting and use a fixed budgetof 10, 000 steps (Appendix C). Generally, using the gradient norm to reduce the variance substantially hurts performance(Table 9). If we “cheat” and allow one backpropagation through the network to estimate the gradient norm, then we see that
reducing the variance using the gradient norm does not substantially hurt or help performance. Modifying the variance using
the parameter norm, analogous to layerwise adaptive rate methods, does not substantially impact the performance of MeZO
(Table 10).
Our observation is that decreasing the variance by setting d as the gradient norm does not improve optimization. Thisempirical result agrees with the exposition in Section 4 that the straightforward variance analysis (which yields a dependence
on the number of parameters d) is not the best lens to study the rate of optimization when fine-tuning with MeZO. Our
effective rank view in Theorem 1 and Lemma 3 is likely a better characterization of fine-tuning dynamics. We leave it to
future work to explore if these methods can be useful for other more complex objectives.
D.4. Modifying the Expectation of MeZOThe above experiments show that modifying the variance of MeZO cannot consistently accelerate its convergence. However,a simple modification of Definition 5 allows us to change the expectation of MeZO as well. This can be used to efficiently
estimate coordinate-wise normalized gradient-based optimizer updates (e.g., Adam).
17

Fine-Tuning Language Models with Just Forward Passes

Recompute d

ZO estimate of dBaseline MeZO (Algorithm 1)

SST-2

SNLI

TREC

89.6 (1.2)
89.7 (0.8)
87.0 (2.5)
79.0 (10.3)

65.1 (6.2)
65.2 (5.2)
49.6 (9.2)
48.9 (2.2)

66.7 (6.2)
64.3 (6.4)
32.6 (7.7)
38.7 (7.5)

Table 9: Experiments modifying the variance of MeZO using d as the gradient norm (see Definition 5). We sometimes
recompute d at the start of each epoch or use Proposition 1 to estimate d without requiring backpropagation.
Recompute d

SST-2

SNLI

TREC

Baseline MeZO (Algorithm 1)

89.6 (1.2)
89.2 (2.1)
88.2 (4.7)

65.1 (6.2)
65.4 (4.2)
65.2 (4.0)

66.7 (6.2)
64.8 (5.6)
64.7 (5.5)

Table 10: Experiments modifying the variance of MeZO using d as the parameter norm (see Definition 5). We sometimes
recompute d at the start of each epoch.
Definition 6 (Expectation-Modified SPSA). Given a matrix D = diag(d), the variance modified SPSA computes
L(θ + (d
e
∇L(θ;
B) =

where d ∈ Rd .

−1z); B) − L(θ − (d−12z); B)zeB) = E[D−1 zz > ∇L(θ; B)] so the SPSA estimate is no longer an unbiased estimator for ∇L(θ).
Now, we see that ∇L(θ;If we choose d to be the gradient norm, for example, then SPSA can estimate the normalized gradient. Concurrent workin Tang et al. (2023) gives another ZO estimate of the normalized gradient while assuming access to only rankings of inputs(instead of the noisy function evaluations available in our setting). We find that estimating the normalized gradient does not
perform as well as directly estimating the gradient (Table 11). Regardless, we present this algorithm as a way to highlightthat any coordinate-wise operation to the gradient can be applied in a memory-efficient manner.
Method

SST-2

SNLI

TREC

Baseline MeZO (Algorithm 1)
Estimate of normalized gradient (Definition 6)

89.6 (1.2)
88.0 (1.2)

65.1 (6.2)
60.0 (2.4)

66.7 (6.2)
44.0 (14.0)

Table 11: Experiments modifying the expectation of MeZO using d as the gradient norm (see Definition 6). We use the ZO
estimate of the gradient norm (Proposition 1).

E. Memory Analysis
The compute-memory tradeoff of backpropagation is complex to analyze. Griewank and Walther (2008) provides a rigorous
theoretical treatment of the problem. We empirically measure the memory consumption of different methods for commonlyused large language models, but here we hope to provide a more rigorous comparison of different gradient estimation
algorithms, independent of the software used to implement them. Below, we summarize some key points that may help
readers to understand how the MeZO compute-memory tradeoff compares to backpropagation.
Given a network, the first step to perform backpropagation is to decompose the model into easily differentiable blocks. We
note that this decomposition is not unique. For each block, one can choose to cache the resulting output during the forward
pass (thereby consuming memory) or instead recompute the output when it is needed (thereby consuming compute). The
below proposition, adapted from Rule 21 in Griewank and Walther (2008), captures this tradeoff.
Proposition 2 (Time-Memory Tradeoff for Backpropagation, Griewank and Walther (2008)). Consider a network containing
N bits. For any time-memory tradeoff hyperparameter c = O(1), there exists a backpropagation algorithm that runs in timeO(cN ) and consumes memory proportional to O(N 1/c ).
18

Fine-Tuning Language Models with Just Forward Passes

Grimm et al. (1996) also gave sharp bounds for the memory-time product. Note that the popular gradient checkpointing (Chenet al., 2016) method allows one to tune c with limited precision (i.e., one cannot always further
split a differentiable block√and observe savings). Experiments in Chen et al. (2016) choose c = 2 to achieve O( N ) memory while consuming
O(2N ) computation. In the extreme case, gradient checkpointing allows one to use O(N log N ) computation and O(log N )memory.
MeZO always consumes 2N compute and O(1) memory, so it is more compute-efficient at at the same memory cost as
gradient checkpointing. Our exposition in Section 2 discusses that we can perturb groups of parameters together to savetime while consuming additional memory. However, we do not consider that variant here because it is somewhere in the
middle of the compute-memory pareto curve, where we cannot reason about what backpropagation will do. In particular,
MeZO can split groups differently than backpropagation can, since MeZO does not require that each parameter group iseasily differentiable, so it is hard to compare the two algorithms along the entire pareto curve.
We also compare backpropagation for the c = 1 case (i.e., storing everything during the forward pass). When storing
everything, backpropagation consumes O(N ) time and O(N ) memory. Hence, SPSA consumes slightly more time andsubstantially less memory than backpropagation at this end of the tradeoff.
Unlike gradient checkpointing, MeZO computes only an approximation of the gradient. This approximation is only usefulfor fine-tuning with a prompt, making it less broadly useful than gradient checkpointing. There are other methods thatapproximate the gradient with less memory consumption than gradient checkpointing (see the Related Work section), though
it is unclear how the memory consumption of those algorithms compare to MeZO.

F. Experiment setup
F.1. Datasets
For RoBERTa-large, we consider classification datasets: SST-2 (Socher et al., 2013), SST-5 (Socher et al., 2013),
TREC (Voorhees and Tice, 2000), MNLI (Williams et al., 2018), SNLI (Bowman et al., 2015), and RTE (Dagan et al., 2005;
Bar Haim et al., 2006; Giampiccolo et al., 2007; Bentivogli et al., 2009). We follow Malladi et al. (2022) in limiting thetest set to 1, 000 examples for fast iteration. For training and validation, we have two settings: k = 16 and k = 512, whichmean that we have 16 or 512 examples per class for both training and validation.
For OPT experiments, we consider the SuperGLUE dataset collection (Wang et al., 2019), including: BoolQ (Clark et al.,2019), CB (De Marneffe et al., 2019), COPA (Roemmele et al., 2011), MultiRC (Khashabi et al., 2018), ReCoRD (Zhang
et al., 2018), RTE (Dagan et al., 2005; Bar Haim et al., 2006; Giampiccolo et al., 2007; Bentivogli et al., 2009), WiC (Pilehvarand Camacho-Collados, 2019), and WSC (Levesque et al., 2012). We also include SST-2 (Socher et al., 2013) and twoquestion answering (QA) datasets, SQuAD (Rajpurkar et al., 2016) and DROP (Dua et al., 2019). We randomly sample
1,000 examples for training, 500 examples for validation, and 1,000 examples for testing.
F.2. Prompts
Table 12 shows the set of downstream tasks and prompts with which we fine-tune RoBERTa-large, which are adapted from
(Gao et al., 2021).
DatasetC

Type

PromptLabel words

SST-2
SST-5
TREC

2
5
6

sentiment cls.
sentiment cls.
topic cls.

<S1 > It was [MASK] .
<S1 > It was [MASK] .
[MASK] : <S1 >

MNLI
SNLI
RTE

3
3
2

NLI
NLI
NLI

<S1 > ? [MASK] , <S2 ><S1 > ? [MASK] , <S2 ><S1 > ? [MASK] , <S2 >{great, terrible}{great, good, okay, bad, terrible}{Description, Expression, Entity,
Human, Location, Number}{Yes, Maybe, No}{Yes, Maybe, No}{Yes, No}

Table 12: The prompts of the datasets we used in our RoBERTa-large experiments (Table 17 and Figure 4). The prompts are
adapted from (Gao et al., 2021) and include a template and a set of label words that can fill in the [MASK]token. <S1 > and<S2 > refer to the first and the second (if any) input sentence.
Table 13 demonstrates the prompts we use for OPT. Note that in OPT experiments we have three types of tasks: classification,
19

Fine-Tuning Language Models with Just Forward Passes

multiple-choice, and question answering. Prompts are adopted from GPT-3 (Brown et al., 2020) and PromptSource withminor changes (Bach et al., 2022).

DatasetType

Prompt

SST-2
RTE

cls.
cls.

CB

cls.

BoolQ

cls.

WSC

cls.

WIC

cls.

MultiRC

cls.

COPA
ReCoRD

mch.
mch.

SQuAD

QA

DROP

QA

<text> It was terrible/great<premise>
Does this mean that "<hypothesis>" is true? Yes or No?
Yes/NoSuppose <premise> Can we infer that "<hypothesis>"? Yes, No, or Maybe?
Yes/No/Maybe<passage> <question>?
Yes/No<text>In the previous sentence, does the pronoun "<span2>" refer to <span1>? Yes or No?
Yes/NoDoes the word "<word>" have the same meaning in these two sentences? Yes, No?
<sent1><sent2>
Yes/No<paragraph>
Question: <question>
I found this answer "<answer". Is that correct? Yes or No?
Yes/No<premise> so/because <candidate><passage><query>.replace("@placeholder", <candidate>)
Title: <title>
Context: <context>
Question: <question>
Answer:Passage: <context>
Question: <question>
Answer:Table 13: The prompts of the datasets we used in our OPT experiments. There are three types of tasks: classification(cls.), multiple-choice (mch.), and question answering (QA). Prompts are adopted from GPT-3 (Brown et al., 2020) and
PromptSource (Bach et al., 2022) with minor changes. <text> represents input from the dataset and Yes represents labelwords. For inference on multiple choice tasks, we put in different candidates in the prompt and calculate the average
log-likelihood for each candidate, and choose the candidate with the highest score. For inference on QA tasks, we use
greedy decoding to generate the answer.

F.3. Hyperparameters
We use the hyperparameters in Table 14 for MeZO experiments on RoBERTa-large (Table 17 and Figure 4). Experiments inAppendix C informed the grid; in particular, the choice of  seemed to not significantly impact performance, and using alarger batch size consistently yielded faster optimization. We use the hyperparameters in Table 15 for MeZO experiments on
OPT.
Regarding learning rate scheduling and early stopping, we use linear learning scheduling for all fine-tuning with backpropagation experiments and constant learning rate for all MeZO experiments. For RoBERTa experiments, we evaluate the model
on validation sets every 1/10 of total training steps and save the best validation checkpoint. All FT experiments use 1K steps
and MeZO experiments use 100K steps. For OPT experiments, we evaluate the model on validation sets every 1/5 of thetotal training steps and save the best validation checkpoint. All FT experiments train for 5 epochs and all MeZO experiments
use 20K steps. Note that FT experiments mostly converge within 5 epochs but we observe that MeZO performance can still
improve with more training steps.
20

Fine-Tuning Language Models with Just Forward Passes
ExperimentHyperparameters

ValuesMeZO

Batch size
Learning rate
Weight Decay64{1e−7, 1e−6, 1e−5}
1e−30

MeZO (prefix)

Batch size
Learning rate
Weight Decay# prefix tokens

64{1e−2, 5e−3, 1e−3}
1e−1
0
5

MeZO (LoRA)

Batch size
Learning rate
Weight Decay(r, α)

64{1e−5, 5e−5, 1e−4}
1e−3
0.1(8, 16)

FT with Adam

Batch size (k = 16)
Batch size (k = 512)
Learning Rates
Weight Decay{2, 4, 8}{8, 16, 32}{1e−5, 3e−5, 5e−5}0

FT with SGD

Batch size (k = 16)
Batch size (k = 512)
Learning Rates
Weight Decay{2, 4, 8}{8, 16, 32}{1e−4, 5e−4, 1e−3, 5e−3, 1e−2}0

FT (prefix)

Batch size
Learning Rates
Weight Decay# prefix tokens{8, 16, 32}{1e−2, 3e−2, 5e−2}05FT (LoRA)

Batch size
Learning Rates(r, α){4, 8, 16}{1e−4, 3e−4, 5e−4}(8, 16)

Table 14: The hyperparameter grids used for RoBERTa-large experiments. MeZO uses a constant learning rate schedule, andFT uses linear scheduling. All FT experiments use 1K steps and MeZO experiments use 100K steps. We check validation
performance every 1/10 total training steps.

F.4. Modeling and implementation
For RoBERTa experiments, we follow (Gao et al., 2021) for the prompt-based fine-tuning paradigm for masked language
models. Please refer to the original paper for more details.
In OPT experiments, for classification tasks, we train the model similar to (Gao et al., 2021), i.e., we take the logits
corresponding to the label words and apply cross entropy loss on them; for multiple choice tasks and generation tasks (QA),
we only keep the correct candidate and use teacher forcing to train on the correct examples. We only keep the loss on tokens
in the candidate part and exclude the prompt part.
For OPT inference on classification and multiple-choice tasks, we use the model to get the average log-likelihood (by tokens)of all the candidates/label words, and predict the one with the highest average log-likelihood. For generation tasks, we use
greedy decoding to generate the answer.
For in-context learning, we use 32 examples in the context. We also try filling in as many examples as possible in the context
but does not improve performance and sometimes lead to unstable results. Thus we keep the 32-example results.
For linear probing of classification tasks, we take the output feature and use scipy package to train a linear classifier.
For multiple-choice tasks and generation tasks, we found that this leads to poor results since the output space is the whole
vocabulary; instead, we do head-tuning, where the whole model is fixed except for the LM projection head. We use a batch
size of 8 and a learning rate of {1e−4 5e−4}, and train the head for 5 epochs.
For experiments on 30B and 66B OPT models, we largely follow the OPT hyperparameters except that we do not evaluate21Fine-Tuning Language Models with Just Forward Passes
ExperimentHyperparameters

ValuesMeZO

Batch size
Learning rate16
{1e−6, 1e−7}
1e−3

MeZO (prefix)

Batch size
Learning rate# prefix tokens

16{1e−2, 1e−3}
1e−15

MeZO (LoRA)

Batch size
Learning rate(r, α)

16{1e−4, 5e−5}
1e−2(8, 16)

FT with Adam

Batch size
Learning Rates8{1e−5, 5e−5, 8e−5}

Table 15: The hyperparameter grids used for OPT experiments. All weight decay is set to 0. FT uses 5 epochs and linear
scheduled learning rates and MeZO uses 20K steps and constant learning rates. We check validation performance and savethe best checkpoint every 1/5 total training steps.

the intermediate validation performance and directly use the last checkpoint for evaluation, due to the high storage cost ofintermediate checkpoints of large models.
F.5. Parameter-efficient fine-tuning
Fine-tuning and storing a copy of the large language model for each downstream task is expensive. Parameter-efficientfine-tuning (PEFT) techniques alleviate this problem: instead of tuning all model parameters, PEFT only tunes a small
number of additional parameters (usually less than 1%) and can often achieve comparable or better performance (Li andLiang, 2021; Lester et al., 2021; Ding et al., 2022). The ZO optimizer is compatible with PEFT methods, since ZO can
operate on any subset of the model parameters. We are interested in the following two common PEFT methods, designed fortransformers (Vaswani et al., 2017).
LoRA (Hu et al., 2022) adds a tunable low-rank delta to a linear layer during fine-tuning. Suppose a linear layer performed
W x + b during pre-training with W ∈ Rm×n . When fine-tuning, LoRA introduces two smaller matrices A ∈ Rm×r andB ∈ Rr×n such that r  min(m, n). The linear layer is then computed as


W+


α
AB x + br(5)where r and α are hyperparameters. A and B are trained on the downstream task while W is frozen at its pre-trained value.
In transformers, this modification to the linear layer is applied to the query and value operations of each attention layer.
Empirically, r can be very small, so the number of trainable parameters during fine-tuning is small. We choose r = 8 and
α = 16.
Prefix-tuning (Li and Liang, 2021) adds a prefix of m tunable representations at each layer and freezes the rest of the model.
The representations are added as new keys and values and treated as additional context during the attention operation. We
initialize these tunable representations by randomly sampling tokens from the vocabulary and passing them through the
LLM to get their keys and values at different attention layers. We found this crucial to make prefix tuning stable with MeZO,
and this trick additionally boosts the performance of prefix tuning with backpropagation, as shown in Table 16. We also
tried the reparameterization trick in (Li and Liang, 2021), which does not help MeZO training. In our experiments, we findm = 5 to be sufficient to achieve good performance on most tasks.
We also show that MeZO is compatible with parameter-efficient fine-tuning methods, such as prefix tuning and LoRA.
Surprisingly, the performance of MeZO does not improve substantially when tuning much fewer parameters, as one
might expect from classical analyses (see Section 4). Accordingly, our theoretical analysis in Section 4 suggests that theconvergence rate of ZO-SGD does not depend on the parameter dimension during fine-tuning.
22Fine-Tuning Language Models with Just Forward Passes

Task
Type

SST-2
SST-5
—— sentiment ——

SNLI
MNLI
RTE
—— natural language inference ——TREC— topic —FT (prefix, random init)
FT (prefix, real act init)

90.7 (1.7)
91.9 (1.0)

70.7 (2.8)
77.2 (1.3)

83.4 (4.7)
85.7 (1.3)

47.2 (2.0)
47.7 (1.1)

62.6 (3.3)
66.5 (2.5)

63.5 (4.4)
66.6 (2.0)

Table 16: Prefix-tuning ablations. We compare randomly-initialized prefixes and real word activation prefixes. Using real
word activations significantly outperforms random initialization.

F.6. Training with non-differentiable objectives
The experiments maximizing the accuracy of a RoBERTa-large model were all conducted using the same grid as MeZO in
Table 14.
For OPT experiments on SQuAD with F1 as objective, we use a batch size of 16. For MeZO, we use a learning rate of{1e−6, 5e−6, 1e−5} and  = 1e−3. For MeZO (prefix), we use a learning rate of {1e−1, 5e−2, 1e−2} and  = 1e−1.
F.7. Memory profiling
In memory profiling, we use standard implementation with Huggingface’s transformers (Wolf et al., 2020) package.
We did not turn on any advance memory-saving options, e.g., gradient checkpointing. We set the per-device batch sizeas 1 to test the minimum hardware requirement to run the model with specific optimization algorithms. For multi-GPU
backpropagation, we use fully sharded data parallel (FSDP) (FairScale authors, 2021) provided by PyTorch (Paszke
et al., 2019). For multi-GPU MeZO, we use transformers multi-GPU inference of large models. We use Nvidia’s
nvidia-smi command to monitor the GPU memory usage. We call a run “successful” if there is no out of memory error
from GPUs for at least 100 steps.

G. More experiment results
G.1. RoBERTa-large experiments
Table 17 contains the detailed numbers corresponding to Figure 4 and also reports the performance of MeZO-Adam.
LP-MeZO We also compare MeZO to performing linear probing and then subsequently performing fine-tuning via MeZO,
following the analogous suggestion for fine-tuning in Kumar et al. (2022). We use the MeZO grid described in Table 14.
Note that the linear probing checkpoints used here have early stopping, unlike the ones reported in Table 17. We heuristically
implement early stopping by limiting the number of iterations (from 5000 to 1000) and increasing the convergence tolerance(from 1e−4 to 0.01) in the scipy solver. Experiments on a few settings show that LP-MeZO can sometimes improve
performance without increasing the memory consumption (see Table 18). However, sometimes, linear probing first canseverely hurt performance.
G.2. OPT experiments
Table 19 present the full results of OPT-30B and OPT-66B, with detailed MeZO numbers.
G.3. Convergence of MeZO with full-parameter and PEFT
We demonstrate the convergence rate of MeZO, MeZO (LoRA) and MeZO (prefix) on SST-2 and SNLI for the first 5,000
steps in Figures 5. We see that despite the different number of parameters they optimize, MeZO demonstrates similar
training speed on full parameter and PEFT. This agrees with our theory in Section 4, which shows that MeZO’s optimization
speed is independent of the number of parameters.
G.4. ZO vs BBTv2
We compare ZO with BBTv2 (Sun et al., 2022a) on mutually assessed tasks in Table 20. ZO significantly outperform BBTv2.
Furthermore, BBTv2 is limited to optimize in low-dimensional space and requires prefix-tuning and a down-projection
23

Fine-Tuning Language Models with Just Forward Passes

Task
Type

SST-2
SST-5
—— sentiment ——

SNLI
MNLI
RTE
—— natural language inference ——Zero-shot

79.0

50.2

35.5

48.8

TREC
— topic —

51.4

32.0

59.4 (5.3)
64.0 (3.3)
64.9 (3.6)
65.4 (3.9)
59.2 (11.1)†

51.3 (5.5)
76.9 (2.7)
73.1 (6.5)
80.3 (3.6)
78.3 (1.4)

66.4 (7.2)
66.1 (3.5)
66.6 (2.0)

85.0 (2.5)
82.7 (4.1)
85.7 (1.3)

73.1 (1.5)
78.6 (2.0)
77.6 (1.3)
77.2 (0.8)
79.2 (1.2)

89.4 (0.5)
94.3 (1.3)
95.0 (0.7)
94.4 (0.7)
95.1 (0.3)

82.7 (1.4)
83.2 (1.3)
82.5 (0.8)

97.3 (0.2)
97.0 (0.3)
97.4 (0.2)

Gradient-free methods: k = 16LP
MeZO
MeZO (LoRA)MeZO (prefix)
MeZO-Adam

76.0 (2.8)
90.5 (1.2)
91.4 (0.9)
90.8 (1.7)
90.4 (1.4)

40.3 (1.9)
45.5 (2.0)
43.0 (1.6)
45.8 (2.0)
45.4 (1.5)

66.0 (2.7)
68.5 (3.9)
69.7 (6.0)
71.6 (2.5)
74.1 (2.7)

56.5 (2.5)
58.7 (2.5)
64.0 (2.5)
63.4 (1.8)
64.3 (0.8)†

Gradient-based methods: k = 16
FT
FT (LoRA)
FT (prefix)

91.9 (1.8)
91.4 (1.7)
91.9 (1.0)

47.5 (1.9)
46.7 (1.1)
47.7 (1.1)

77.5 (2.6)
74.9 (4.3)
77.2 (1.3)

70.0 (2.3)
67.7 (1.4)
66.5 (2.5)

Gradient-free methods: k = 512
LP
MeZO
MeZO (LoRA)MeZO (prefix)
MeZO-Adam

91.3 (0.5)
93.3 (0.7)
93.4 (0.4)
93.3 (0.1)
93.3 (0.6)

51.7 (0.5)
53.2 (1.4)
52.4 (0.8)
53.6 (0.5)
53.9 (0.8)

80.9 (1.0)
83.0 (1.0)
84.0 (0.8)
84.8 (1.1)
85.3 (0.8)

71.5 (1.1)
78.3 (0.5)
77.9 (0.6)
79.8 (1.2)
79.6 (0.4)

Gradient-based methods: k = 512
FT
FT (LoRA)
FT (prefix)

93.9 (0.7)
94.2 (0.2)
93.7 (0.3)

55.9 (0.9)
55.3 (0.7)
54.6 (0.7)

88.7 (0.8)
88.3 (0.5)
88.3 (0.7)

84.4 (0.8)
83.9 (0.6)
83.3 (0.5)

Table 17: Experiments on RoBERTa-large (350M parameters). LP: Linear probing; ZO, ZO (LoRA), and ZO (prefix): ourmemory-efficient ZO-SGD (Section 2.1) with full-parameter tuning, LoRA, and prefix-tuning respectively; FT: fine-tuningwith Adam. All reported numbers are averaged accuracy (standard deviation). All experiments use prompts (Appendix F.2).
ZO outperforms zero-shot and LP by a large margin and approaches FT performance with much less memory cost.

24Fine-Tuning Language Models with Just Forward Passes
Task

SST-2

SST-5

SNLI

TREC

Zero-shot
FT

79.0
91.9 (1.8)

35.5
47.5 (1.9)

50.2
77.5 (2.6)

32.0
85.0 (2.5)

MeZO
LP-MeZO

90.5 (1.2)
91.4 (1.4)

45.5 (2.0)
41.9 (3.3)

68.5 (3.9)
70.7 (3.4)

76.9 (2.7)
54.0 (4.5)

Table 18: Performing linear probing before fine-tuning with MeZO, as suggested previously (Kumar et al., 2022), cansometimes improve performance without increasing the memory overhead. We use k = 16 for these experiments.

Task

SST-2

RTE

BoolQ

WSC

WIC

SQuAD

30B zero-shot
30B ICL30B MeZO
30B MeZO (prefix)

56.7
81.9
90.6
87.5

52.0
66.8
66.4
72.6

39.1
66.2
67.2
73.5

38.5
56.7
63.5
55.8

50.2
51.3
56.3
59.1

46.5
78.0
85.2
83.9

66B zero-shot
66B ICL66B MeZO
66B MeZO (prefix)

57.5
89.3
91.2
93.6

67.2
65.3
65.7
66.4

66.8
62.8
72.7
73.7

43.3
52.9
63.5
57.7

50.6
54.9
58.9
58.6

48.1
81.3
*
85.0

Table 19: Experiments on OPT-30B and OPT-66B (with 1,000 examples). *: MeZO requires further tuning to successfully
optimize.

to reduce the number of optimized parameters. BBTv2 also employs an iterative scheme which only optimizes one layer
at a time. In contrast, ZO works with both full-parameter tuning and PEFT, as shown in our experiments (Section 3) andtheory (Section 4).

Task
Task type

SST-2—— sentiment ——Zero-shot

79.0

50.2

51.4

90.3 (1.7)
90.5 (1.2)
91.4 (0.9)
90.8 (1.7)

57.3 (2.3)
68.5 (3.9)
69.7 (6.0)
71.6 (2.5)

56.7 (3.3)
64.0 (3.3)
64.9 (3.6)
65.4 (3.9)

BBTv2
MeZO
MeZO (LoRA)MeZO (prefix)

SNLI
RTE
– natural language inference –Table 20: ZO vs BBTv2 with RoBERTa-large. BBTv2 performance is from Sun et al. (2022a).

G.5. Memory profiling
We show the detailed numbers of memory profiling results Table 21, which also corresponds to Figure 2. For how we profile
the memory usage, please refer to Appendix F.7.
G.6. Wallclock time efficiency
In this section, we measure the wallclock time efficiency of MeZO compared to full-parameter FT, with respect to different
model sizes. We conduct our experiments with 80GB A100s connected by NVLink and InfiniteBand, which are stateof-the-art solutions for distributed training. As shown in Table 22, on the MultiRC datasets, training with MeZO brings
7.74× speedup per step compared to full-parameter FT on a 30B model. This is due to (1) MeZO does not require costly
backpropagation and (2) MeZO requires fewer GPUs and reduces the multi-GPU communication overhead.
25

Fine-Tuning Language Models with Just Forward Passes

SNLI

SST-2
0.55

2.0

MeZO Train
MeZO (LoRA) Train
MeZO (prefix) Train

0.50

1.8
1.6

0.45
0.40

Loss

Loss

MeZO Train
MeZO (LoRA) Train
MeZO (prefix) Train

0.35

1.4
1.2
1.0

0.30

0.8

0.25
0

500

0.6

1000 1500 2000 2500 3000
Steps

0

500

1000 1500 2000 2500 3000
Steps

Figure 5: MeZO does not optimize significantly faster when tuning fewer parameters, agreeing with our theory in Section 4.
MethodZero-shot / MeZO

ICL

Prefix FT

Full-parameter FT

1.3B
2.7B
6.7B
13B
30B
66B

1xA100 (4GB)
1xA100 (7GB)
1xA100 (14GB)
1xA100 (26GB)
1xA100 (58GB)
2xA100 (128GB)

1xA100 (6GB)
1xA100 (8GB)
1xA100 (16GB)
1xA100 (29GB)
1xA100 (62GB)
2xA100 (134GB)

1xA100 (19GB)
1xA100 (29GB)
1xA100 (46GB)
2xA100 (158GB)
4xA100 (315GB)
8xA100

1xA100 (27GB)
1xA100 (55GB)
2xA100 (156GB)
4xA100 (316GB)
8xA100 (633GB)
16xA100

Table 21: Memory usage on the MultiRC (avg #tokens=400) dataset.
Note that even though MeZO has better per-step wallclock efficiency, it requires significantly more steps than standard FT.
Taking our OPT-30B experiments as an example: MeZO takes 32× more steps than standard FT, while FT takes 8× more
GPUs and 7.74× more time per step. Overall, MeZO requires only half as many GPU-hours as FT for a 30B model.
Method
13B
30B

MeZO

Full-parameter FT

1× (2.72s)
1× (5.90s)

2.52×
7.74×

Table 22: Wallclock time per step of different training methods. It is measured on 80GB A100s with NVLink andInfiniteBand connections. The wallclock time is averaged over 100 steps. It is measured on the MultiRC task with the OPT
family. 13B and 30B OPT require 1 A100 with MeZO and 4 and 8 A100s with FT respectively.

26

Fine-Tuning Language Models with Just Forward Passes

H. Proofs
Proof of Lemma 2. We first note that in the  → 0 limit, we have
1
b
∇L(θ;
B) =
Bn

X

X

(x,y)∈B i∈[n]zi ziT ∇L(θ; {(x, y)}).

bbB) is an unbiased estimator of
Taking expectation over the batch B and the zi , we have E[∇L(θ;B)] = ∇L(θ), so ∇L(θ;the gradient.
Computing the second moment, we gethibb
E ∇L(θ;B)∇L(θ;
B)T
X
1
= 2 2
B n

X

(x1 ,y1 ),(x2 ,y2 )∈B i,j∈[n]
E (zi ziT ∇L(θ; {(x1 , y1 )}))(zj zjT ∇L(θ; {(x2 , y2 )}))TLet u, v be two arbitrary vectors. We have that
Ezi ,zj [zi ziT uv T zj zjT ] = uv T
when i 6= j, andEzi [zi ziT uv T zi ziT ] = Ez [z ⊗4 ](u, v)
3d=
Sym(I ⊗2 )(u, v)
d+2
d
2d
=
· uT v · I +· uv T .
d+2
d+2
ThereforehibbE ∇L(θ;B)∇L(θ;
B)T


X


2d
n−1
1
E L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T
+
= 2
B
n
n(d + 2)
(x1 ,y1 ),(x2 ,y2 )∈B

+



d
· E L(θ; {(x1 , y1 )})T L(θ; {(x2 , y2 )}) I.
n(d + 2)

Next, note that when (x1 , y1 ) 6= (x2 , y2 ), we haveE L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T = ∇L(θ)∇L(θ)T ,and when (x1 , y1 ) = (x2 , y2 ) we haveE L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T = ∇L(θ)∇L(θ)T + ΣM B (θ).

Therefore

1B2

X(x1 ,y1 ),(x2 ,y2 )∈B
1E L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T = ∇L(θ)∇L(θ)T + Σ(θ),
B

and plugging this yields
 

1
d−2
T
· ∇L(θ)∇L(θ) + Σ(θ)
n(d + 2)
B


d
1
2
+
I · k∇L(θ)k + tr(Σ(θ)) .
n(d + 2)
B

i 
T
b
b
E ∇L(θ; B)∇L(θ; B) = 1 +
h

27

(6)

Fine-Tuning Language Models with Just Forward Passes

Finally, we have
E



b
∇L(θ;
B)

2



 

1
d2 + d − 22· k∇L(θ)k + tr(Σ(θ))= 1+n(d + 2)
B
h
i
d+n−1
2
=
· E k∇L(θ; B)k .
n

Proof of Theorem 1. By Taylor’s theorem with remainder, we have thatL(θt+1 ) = L(θt ) + ∇L(θt )T (θt+1 − θt )Z 1
λ(θt+1 − θt )T ∇2 L(λθt+1 + (1 − λ)θt )(θt+1 − θt )T dλ+0

Next, note that
√
1 X T
b
zi ∇L(θ; {(x, y)}) ≤ ηdG(θt ).
kθt+1 − θt k = η ∇L(θ;B) ≤ η d ·Bn
Therefore kλθt+1 + (1 − λ)θt − θt k ≤ ηdG(θt ). By the assumption we have the upper bound ∇2 L(λθt+1 + (1 − λ)θt ) H(θt ), and thus
L(θt+1 ) ≤ L(θt ) + ∇L(θt )T (θt+1 − θt ) + (θt+1 − θt )T H(θt )(θt+1 − θt )
1 2b
T
b
b
= L(θt ) − η∇L(θt )T ∇L(θt ; B) + η ∇L(θt ; B) H(θt )∇L(θt ; B).
2
Taking the conditional expectation with respect to θt and plugging in (8), the formula for the covariance of our ZO estimateb∇L(θt ; B), yields
h
iE
η2 D
b
b
B)∇L(θ;B)T
H(θt ), E ∇L(θ;
2


2
1
η
d
2
2
k∇L(θt )k + tr(Σ(θt )) tr(H(θt ))= L(θt ) − η k∇L(θt )k +·2 n(d + 2)
B




η2
d−2
1
T
+
1+
∇L(θt ) H(θt )∇L(θt ) + hΣ(θt ), H(θt )i2n(d + 2)B
2

E[L(θt+1 ) | θt ] ≤ L(θt ) − η k∇L(θt )k +By assumption, the Hessian upper bound H(θt ) satisfies kH(θt )kop ≤ ` and tr(H(θt )) ≤ `r. Thus 
dr + d − 2
1
η2 `
2
·
+ 1 · k∇L(θt )k + tr(Σ(θt ))E[L(θt+1 ) | θt ] ≤ L(θt ) − η k∇L(θt )k +2n(d + 2)
B


i
h
2
η `
dr + d − 222= L(θt ) − η k∇L(θt )k +·+ 1 · E k∇L(θt ; B)k ,2n(d + 2)2

as desired.
H.1. Proofs of Global Convergence
Lemma 4. Let L(θ) be µ-PL and let there exist α such that tr(Σ(θ)) ≤ α(L(θ) − L∗ ) for all θ. Then after
L(θ0 ) − L∗
`α
`
log
+ 2
t=O
µ µ B

iterations of SGD we have E[L(θt )] ≤ L∗ + .
28

Fine-Tuning Language Models with Just Forward Passes

Proof of Lemma 4. The descent lemma for SGD yields
1
2
2
E[L(θt+1 ) | θt ] − L(θt ) ≤ −η k∇L(θt )k + η 2 ` · E[k∇L(θt ; B)k ].
2
2

2

Plugging in E[k∇L(θt ; B)k ] = k∇L(θt )k + B1 tr(Σ(θt )) and selecting a learning rate η ≤ 1` yields
E[L(θt+1 ) | θt ] ≤ L(θt ) −

η2 `
η
2
k∇L(θt )k +tr(Σ(θt ))2
2B

Since L is µ-PL, we get
E[L(θt+1 ) | θt ] ≤ L(θt ) − ηµ(L(θt ) − L∗ ) +Since tr(Σ(θt )) ≤ α(L(θt ) − L∗ ), we have
E[L(θt+1 ) | θt ] ≤ L(θt ) − ηµ(L(θt ) − L∗ ) +η2 `tr(Σ(θt )).
2Bη 2 `α(L(θt ) − L∗ ).
2B

Altogether,
E[L(θt+1 )] − L∗ ≤Choosing η = min( 1` , µB`α ), we obtain
E[L(θt+1 )] − L∗ ≤

1 − ηµ +1 − min(η 2 `α2B

(E[L(θt )] − L∗ )

µ µ2 B,) (E[L(θt )] − L∗ ).
2` 2`αTherefore we reach a solution with E[L(θt )] − L∗ ≤  after







L(θ0 ) − L∗`2` 2`αL(θ0 ) − L∗
`α
log
=O
log
t = max,+µ µ2 Bµ µ2 B
iterations.
Proof of Lemma 3. By Corollary 1, ZO-SGD with ηZO = γ −1 ηSGD yields


1
1 2
2
2
E[L(θt+1 ) | θt ] − L(θt ) ≤ · −ηSGD k∇L(θt )k + ηSGD ` · E[k∇L(θ; B)k ] .
γ
2As in the proof for SGD, choosing ηSGD ≤ 1` yields
E[L(θt+1 ) | θt ] − L(θt ) ≤ γ

−1




2
ηSGD
ηSGD
`
2
· −
k∇L(θt )k +tr(Σ(θt )) .
2
2B

Therefore under µ-PL and the tr(Σ(θt )) ≤ α(L(θt ) − L∗ ) assumption we obtain


2
ηSGD
`α
−1
E[L(θt+1 )] − E[L(θt )] ≤ γ · −ηSGD µ +· (E[L(θt )] − L∗ )
2B



η 2 `α(E[L(θt )] − L∗ ).
=⇒ E[L(θt+1 )] − L∗ ≤ 1 − γ −1 ηSGD µ − SGD
2B
Choosing ηSGD = min( 1` , µB`α ) yields
E[L(θt+1 )] − L∗ ≤

1 − γ −1 · min(µ µ2 B,) (E[L(θt )] − L∗ ).
2` 2`αTherefore we reach a solution with E[L(θt )] − L∗ ≤  after







 `
2` 2`αL(θ0 ) − L∗`α
L(θ0 ) − L∗rt = γ · max
log
=O
log
, 2
+1 ·
+ 2
µ µ B

n
µ µ B

iterations.
29Fine-Tuning Language Models with Just Forward Passes

H.1.1. V ERIFICATION OF ASSUMPTIONS
We show that the tr(Σ(θt )) ≤ α(L(θt ) − L∗ ) assumption holds for certain losses.
First, consider optimizing the model f (x; θ) with square loss, so that
1 X
(f (xi ; θ) − yi )2 .
N

L(θ) =i∈[N ]

One then has that
Σ(θ) =2 X(f (xi ; θ) − yi )2 ∇f (xi ; θ)∇f (xi ; θ)T − ∇L(θ)∇L(θ)T .
Ni∈[N ]

Therefore2 X
2(f (xi ; θ) − yi )2 k∇f (xi ; θ)kNi∈[N ]
X
2≤ 2L(θ)k∇f (xi ; θ)k .

tr(Σ(θ)) ≤i∈[N ]

Assume that the data can be interpolated, i.e L∗ = 0. If the function is L-Lipschitz, i.e k∇f (x; θ)k ≤ L, then the condition
holds with α = 2N L2 . If we are in the kernel regime, i.e f (xi ; θ) = φ(xi )T θ for some feature map φ, then2 X
f (xi ; θ)∇f (xi ; θ)T .
N∇2 L(θ) =i∈[N ]Thus
tr(Σ(θ)) ≤ N tr(∇2 L(θ)) · L(θ) ≤ N `r · L(θ).
So the condition holds for α = N `r.
Next, consider the cross entropy loss function, i.eL(θ) =1 X
exp(−yi f (xi ; θ)).
N
i∈[N ]

One then has that
Σ(θ) =1 X
exp(−2yi f (xi ; θ))yi2 ∇f (xi ; θ)∇f (xi ; θ)T − L(θ)L(θ)T ,Ni∈[N ]

Assume that the targets yi are bounded in [−1, 1] (which is true for binary classification tasks), and that L∗ = 0 (which canbe achieved if |f (x; θ)| can be sent to ∞) we have thattr(Σ(θ)) ≤1 X
2
exp(−2yi f (xi ; θ)) k∇f (xi ; θ)k .
Ni∈[N ]In the kernel regime, f (xi ; θ) = φ(xi )T θ, and thus
∇2 L(θ) =1 X
exp(−yi f (xi ; θ))∇f (xi ; θ)∇f (xi ; θ)T .
Ni∈[N ]

Thereforetr(Σ(θ)) ≤ N tr(∇2 L(θ)) · L(θ) ≤ N `r · L(θ).
Therefore the condition holds with α = N `r as well.
30

Fine-Tuning Language Models with Just Forward Passes

H.2. Proofs for Gaussian perturbationsb
The first lemma computes the second moment of the covariance estimate ∇L(θ;B) when z is drawn N (0, I).
Lemma 5. Let zi ∼ N (0, I) i.i.d. Then

 

h
i 
1
1
b
b
E ∇L(θ;B)∇L(θ;B)T = 1 +· ∇L(θ)∇L(θ)T + ΣM B (θ)
n
B


1
1
2
+ I · k∇L(θ)k + tr(ΣM B (θ)) .
n
B

(7)

Proof. As in the proof of Lemma 2, we have that in the  → 0 limithibbB)∇L(θ;B)T
E ∇L(θ;
X
X 

1
= 2 2
E (zi ziT ∇L(θ; {(x1 , y1 )}))(zj zjT ∇L(θ; {(x2 , y2 )}))TB n(x1 ,y1 ),(x2 ,y2 )∈B i,j∈[n]

For vectors u, v, we have that
Ezi ,zj [zi ziT uv T zj zjT ] = uv T
when i 6= j, andEzi [zi ziT uv T zi ziT ] = Ez [z ⊗4 ](u, v) = 3Sym(I ⊗2 )(u, v) = uT v · I + 2uv T .
ThereforehibbB)∇L(θ;B)T
E ∇L(θ;


X


2
n−1
1
E L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T
+
= 2
B
n
n
(x1 ,y1 ),(x2 ,y2 )∈B

+



1
· E L(θ; {(x1 , y1 )})T L(θ; {(x2 , y2 )}) I.
n

In the proof of Lemma 2 we showed that
1
B2

X

(x1 ,y1 ),(x2 ,y2 )∈B
1E L(θ; {(x1 , y1 )})L(θ; {(x2 , y2 )})T = ∇L(θ)∇L(θ)T + Σ(θ).
B

Plugging this yields
hi n + 1 
1bb
B)∇L(θ;B)T =E ∇L(θ;· ∇L(θ)∇L(θ)T + Σ(θ)
n
B


1
1
2
+ I · k∇L(θ)k + tr(Σ(θ)) .
n
B

(8)

We can prove an analog to Theorem 1 in the case where the zi are Gaussian. One challenge is that kθt+1 − θt k is no longer
bounded; instead we the r-local effective rank assumption only holds with high probability, and thus to bound the expected
loss decrease we must control the probability of the kθt+1 − θt k being large.
Consider the following modified version of the local r-effective rank assumption, where the upper bound on the Hessian ismeasured over a ball of radius twice as large as the one in Assumption 1.
Assumption 3 (Local r-effective rank, Gaussian). Let G(θt ) = max(x,y)∈D k∇L(θt ; {(x, y)})k. There exists a matrix
H(θt ) such that:31

Fine-Tuning Language Models with Just Forward Passes

1. For all θ such that kθ − θt k ≤ 2ηdG(θt ), we have ∇2 L(θ)  H(θt ).
2. The effective rank of H(θt ), i.e tr(H(θt ))/ kH(θt )kop , is at most r.
Theorem 3 (Dimension-Free Rate, Gaussian z). Assume the loss exhibits local r-effective rank (Assumption 3). Ifbθt+1 = θt − ηZO ∇L(θt ; B) is a single step of ZO-SGD using the n-SPSA estimate with a minibatch of size B, then there
exists a γ = Θ(r/n) such that the expected loss decrease can be bounded as
E[L(θt+1 ) | θt ] − L(θt )

1 2
2
2
2
` · γ · E[k∇L(θt ; B)k ] + ηZO`G(θt )2 exp(−Ω(nd)).
≤ −ηZO k∇L(θt )k + ηZO
2

Proof of Theorem 3. Let A be the event that kθt+1 − θt k ≤ 2ηdG(θt ). On A, we have that
1 b
T
b
b
L(θt+1 ) ≤ L(θt ) − η∇L(θt )T ∇L(θ;B) + η 2 ∇L(θt ; B) H(θ)∇L(θt ; B).
2

Likewise, since L is `-smooth, we have that

Therefore1bb
L(θt+1 ) ≤ L(θt ) − η∇L(θt )T ∇L(θ;B) + η 2 ` ∇L(θt ; B)
2

2.

i
E
1 D hb2bB)∇L(θ;B)T · 1(A) , H(θt )E[L(θt+1 ) | θt ] ≤ L(θt+1 ) − η k∇L(θt )k + η 2 E ∇L(θ;
2


2
1 2
b
+ η `E ∇L(θt ; B) · 1(¬A)
2iE
1 D hb2bB)∇L(θ;B)T , H(θt )= L(θt+1 ) − η k∇L(θt )k + η 2 E ∇L(θ;2iE
1 2 D hbbB)T · 1(¬A) , `I − H(θt ) .
η E ∇L(θ; B)∇L(θ;2

The latter term can be bounded as follows


i
E
2
1 2 D hbT2bb
η E ∇L(θ; B)∇L(θ; B) · 1(¬A) , `I − H(θt ) ≤ η `E ∇L(θ; B) · 1(¬A)
2

1
4 2
2
b
≤ η `E ∇L(θ; B)
Pr[¬A]1/2 .

b
The gradient estimate ∇L(θ;B) satisfies

1
b
∇L(θ;
B) ≤
n

X

i∈[n]

ziT ∇L(θ; B) · kzi k

The expectation term is upper bounded asi4
1 X h T
44b
E ∇L(θ; B)≤
E z ∇L(θ; B) · kzk
n
i∈[n]

h
i
i1/2
8 1/2
8
E kzk
≤ E z T ∇L(θ; B)√≤ 105(d + 6)2 G(θt )4 ,hwhere we have plugged in explicit formulas for moments of Gaussian and χ2 random variables.
Next, note that on the event ¬A, we have1b2ηdG(θt ) ≤ kθt+1 − θt k = η ∇L(θt ; B) ≤ η ·
n
32

X

i∈[n]

2

kzi k G(θt ).

Fine-Tuning Language Models with Just Forward Passes

ThereforePr[¬A] ≤ Pr 

X

i∈[n]



2

kzi k ≥ 2ndLemma 6 (Standard χ2 -tail bound). Let Z be a χ2 random variable with k degrees of freedom. Then


 2
u
u
Pr[Z ≥ k + u] ≤ exp − min,
16k 16
Since

P

2
2
i∈[n] kzi k is a χ random variable with nd degrees of freedom, we thus have that

ndPr[¬A] ≤ exp −
16



.

Altogether,iE
1 2 D hbndb
η E ∇L(θ; B)∇L(θ;B)T · 1(¬A) , `I − H(θt ) ≤ η 2 `1051/4 (d + 6)G(θt )2 exp(− )232= η 2 `G(θt )2 exp(−Ω(nd)).
Finally, plugging in (7), along with the fact that kH(θt )kop ≤ ` and tr(H(θt )) ≤ `r,


i
E r+n+1 
D h
1
2
b
b
E ∇L(θ;B)∇L(θ;B)T , H(θt ) =· ` k∇L(θt )k + tr(Σ(θt ))
n
B
h
i
r+n+1
2
· E k∇L(θt ; B)k=n

Thus letting γ = r+n+1
yieldsn
E[L(θt+1 ) | θt ] − L(θt )122≤ −η k∇L(θt )k + η 2 ` · γ · E[k∇L(θt ; B)k ] + η 2 `G(θt )2 exp(−Ω(nd)),2
as desired.

33