Private Fine-tuning of Large Language Models with Zeroth-order Optimization
Authors: Xinyu Tang
Ashwinee Panda
Milad Nasr
Saeed Mahloujifar
Prateek Mittal
Venue: Accepted by TMLR ()

Abstract: Differentially private stochastic gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner, but has proven difficult to scale to the era of foundation models. We introduce DP-ZO, a private fine-tuning method for large language models by privatizing zeroth order optimization methods. A key insight into the design of our method is that the direction of the gradient in the zeroth-order optimization we use is random and the only information from training data is the step size, i.e., a scalar. Therefore, we only need to privatize the scalar step size, which is memory-efficient. DP-ZO provides a strong privacy-utility trade-off across different tasks, and model sizes that are comparable to DP-SGD in $(\varepsilon,\delta)$-DP. Notably, DP-ZO possesses significant advantages over DP-SGD in memory efficiency, and obtains higher utility in $\varepsilon$-DP when using the Laplace mechanism.

Published in Transactions on Machine Learning Research (01/2025)
Private Fine-tuning of Large Language Models with Zeroth- order Optimization
Xinyu Tang")
Ashwinee Panda"
Milad Nasr*
Saeed Mahloujifar
Prateek Mittal'
'Princeton Universily GGoogle DeepMind
$FAIR, Meta
Reviewed OpenReview:
Abstract
Differentially private stochastic gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner, but has proven difficult to scale to the era of foundation models. We introduce DP-ZO, a private fine-tuning method for large language models by privatizing zeroth order optimization methods. A key insight into the design of our method is that the direction of the gradient in the zeroth-order optimization we use is random and the only information from the training data is the step size, i.e., scalar. Therefore, we only need to privatize the scalar step size, which is memory-eficient, DP-ZO provides strong privacy-utility trade-off across different tasks, and model sizes that are comparable to DP- SGD in (c, 6)-DP. Notably, DP-70 possesses significant advantages over DP-SGD in memory efficiency, and obtains higher utility in pure s-DP when using the Laplace mechanism.
1 INTRODUCTION
DP-ZO
The proliferation open-source models pretrained on web-scale datasets (Brown et al., 2020; Zhang al., 2022; Touvron et al., 2023) has created paradigm shift in privacy preserving machine Iearn- ing. Differential Privacy (DP) (Dwork et al., 2006) is the gold standard for preserving privacy while train- ing models on private data, but it requires additional data (Tramèr & Boneh, 2021) to prevent a drop in utility (Yu al., 2021a). Pretrained model check- points have emerged as compelling "free" source of prior information to boost the performance of DP training (Ganesh et al., 2023; Tang al., 2023; Panda et al., 2024a). By only requiring DP during the fine-tunig phase, recent line of work (Li et al., 2022b;a; Yu et al., 2022; He et al., 2023; Bu et al., 2023d) is able to obtain impressive performance with DP-SGD (Abadi et al., 2016). Despite these advanccments, DP-SGD causes additional memory cost and needs additional engineering effort, especially for large models across devices. We propose a new direction for DP fine-tuning of large pretrained models that achieves strong privacy-utility trade-off and is more resourco-cficieent, casy to implement, and portable.
Two random direction
Gradient sca estimate
d-dim noise range, e.g. laplace gaussian
Noise added to scalar estimate
Figure 1: Visualization of DP-ZO. The only informa- tion from private data is a scalar step size for direction with lower target function value and we only nood add noise this scalar. This scalar privalization enjoys the benefits of flexibility with DP mechanisms, ease of implementation, and reduced computation.
In this work, we study DP fine-tuning of large pretrained models with zeroth-order optimization and introduce DP-ZO. Our method uses zeroth-order optimization (2O) (Spall, 1992). Our key insight is the synergy between differentially private fine-tuning and zeroth-order optimization. ZO provides the gradient estimates
"Euual Contribution.

---

Published in Transactions on Machine Learning Research (01/202))
50
Accuracy F150
F119%
60-
20-
5040
6003
DAGP
Dataset
1.30
2.75
8.70
356
300
600
DP-SGD
09-20
Model size
Figure 2: DP-ZO provides a strong privacy-utility trade-off across dif- ferent tasks under conservative pri- vacy budgets. Fl is for SQuAD and DROP and accuracy is for SST2.
Figure 3: DP-ZO achieves compa- rable performance DP-SGD with same model size and scales seam- lessly to large models like 30B/ /66B, that are challenging for DP-SGD.
Figure 4: DP-ZO achieves non- trivial performance for e-DP. Tn contrast, DP-SGD (laplace) suffers to improve upon & = 0 (zero-shot) due to high variance.
and the only information from private data in ZO is a scalar. We only need privatize the scalar update by adding noise it. Specifically, the scalar the differences between losses from models with the same random perturbation but flipped signs. DP-ZO privatizes the zeroth-order update, by adding noise to the difference between the losses (visualized in Figure 1). This noise is proportional to the scnsitivity of this loss difference with respect to changing single example in the training set, which controlled by clipping. We limit the Ep sensitivity by clipping the norm of the difference scalar losses, between the two random perturbations. Therefore, DP-ZO is flexible for both e-DP and (s, d)-D. By removing the need for per-example gradient clipping (Abadi et al., 2016), DP-ZO enables DP training of language models with just few lines of code without, backpropagation.
DP-ZO provides strong privacy-utilitty trade-off across different tasks, model sizes, dataset sizes, and DP mechanisms under conservative privacy budgets. DP-ZO only slightly degrades the performance compared to the non-private baseline (Figure 2). DP-70 achieves comparable performance as DP-SGD within the same model size from 1.3B to 13B (Figure 3). DP-ZO scales scamlessly to large modcls without additional engineering, while DP-SGD requires much more memory and effort to implement per-example gradient. clipping across GPUs (within reasonable research computation limit, DP-SGD results on OPT-30B /66B /6666 not available and omitted in Figure 3). As the model size increases to OPT-66B, the performance of DP-20 increases and the utility gap between DP-ZO and the non-private baseline also decreases (Figure 3). Because our hothod only privatizes scalar, it is compatible with multiple DP mechanisms. Specifically, DP-ZO is the first method to provide pure e-DP with nontrivial utility (73.52 for SQuAD at = 4) for large models by using the Laplace mechanism (Figure 4).
Besides, we provide the empirical privacy analysis of (DP-)70. While 70 itself incurs less empirical privacy loss than SGD, such empirical privacy leakage estimated by membership inference attacks (Shokri al., 2017; Panda et al., 2024b) is still much higher than random guess. Compared to ZO, DP-ZO reduce this membership inference attack close to random guess. We also show the computation efficiency of DP-ZO over DP-SGD, even when applying gradient checkpointing and half-precision to both methods.
Independently and concurrently, Zhang et al. (2024a) also studied privatizing the scalar loss in Zeroee- optimization with Gaussian noise and proposed DPZero. Our DP-ZO shares some similar motivation and design as DPZcro, and there are scveral differences between our work and theirs. We provide a detailed discussion DP-ZO and Zhang et al. (2024a) in Section 5.
2
BACKGROUND
2.1
Differential Privacy
Differential privacy (DP) is the gold standard method for providing algorithmic privacy (Dwork et al., 2006).
2

---

Published in Transactions on Machine Learning Research (01/2025)
Definition 2.1 ((E,8)- Differential Privacy (DP)). We call D' are neighboring datasets if they differ in exactly one record by adding or removing one record. 1 An algorithm M is said to be (e,8)-DP if for all sets of events S S Range(MM) and neighboring datasets D ~ D' we have the guarantee:
Pr(M(D) $s < Pr(M(D)) E
(1)
When d = 0, we term it pure OP or sDDP for simplicity.
For a vector x = (I1, F2 .., En), we use 1p to denote the p-norm of x, 12(x) = (|21 P + |222 + ... + | l)) We now introduce a set of existing DP mechanisus that we will use in our work.
Proposition 2.2 (Gaussian mechanism (Dwork & Roth, 2014; Balle & Wang, 2018)). For any function f x - R with lg sensitivity A, the mechanism defined as
M(X) - ((X)+
where 2 ~~~ N (0, provides (D where $1 - -2 - 2g )))
S 6. Φ(1) is the cumulatiive
distribution function (CDF) of the univariate Gaussion distribution N (N, 1).
Proposition 2.3 (Laplace mechanism (Dwork & Roth, 2014)). For any function f X" R with l
sensitivity A the mechanism defined as
f(X)+++
where Laplace (0, A), provides (E.
2.2 Zeroth-order Optimization
Zeroth-order optimization methods (Kiefer & Wolfowitz, 1952; Spall, 1992; Shamir, 2013; Ghadimi & Lan, 2013; Nesterov & Spokoiny, 2017) use finite difference of function values to estimate gradicnts, instead of computing gradients in first-order methods like SGD. By evaluating the objective function values around the points I, ZO provides the step size towards the direction where the point has a lower function value; See Liu et al. (2020); Zhang et al. (2024c) for more detailed review of Zeroth-order optimization methods. Particularly, we use the difference in losses between two random perturbations SPSA (Spall, 1992; Duchi et al., 2015) with opposite signs to determine the magnitude of gradient update in the direction of the random perturbations, Following (Spall, 1992; Malladi et al., 2023), define SPSA in Definition 2.4.
Definition 2.4 (Simultancous Perturbation Stochastic Approximation (SPSA) (Spall, 1992)). Given a model with parameters 0 E Rd and loss function L, the gradient estimate D is computed by projecting the loss on the minibatch L(0; B) onto random perturbation E Rd that is a standard Gaussian random variable (i.c., 2 ~ (NO, scaled by perturbation scale Ø:
minibatch B drawn from dataset.
(B: C(0 + o2; B) L(O 62;; B)
(2)
2Φ
As noted in the Malladi et al. (2023), when & 0, the SPSA estimate could be considered as a rank-1 reconstruction of the gradient. While SPSA only provides scalar information from the data, interestingly, Malladi et al. (2023) show this method converges at rate that is not catastrophically slower than SGD in fine-tuning large language models in downstream tasks. Malladi et al. (2023) reason this phenomena as a result of the Hossian of the loss exhibiting small local effective rank.
Zeroth-order optimization (ZO) serves as high-variance estimates of the actual gradient (Liu et al., 2018), enabling optimization without the need for explicit gradient computations. While the update of model is from the random perturbation scaled by the step size and the only information from dała is the step size, ZO still carries privacy risk, leaking information about the data (as show later in Section 4.3). Therefore, incorporating differential privacy into ZO is essential to safeguard against these vulnerabilities.
This neighhoring definition is for add/removal DP and the most common one. There are other neighboring definitions in the literature (Desfontaines & Pejó, 2020; Ponomareva al., 2023).
3

---

Published in Transactions on Machine Learning Research (01/2025)
3 OUR METHOD: DP-ZO
We introduce our method for differentially private zeroth order optimization (DP-20) by integrating DP into Definition 2.4. In DP-ZO, the information obtained from training data can be represented scalar. This scalar has bounded sensitivity (when applying clipping) and can be privatized by adding noise. If we compare the noise added in DP-ZO to single dimension to the noise added in DP-SGD to the entire gradient, we expect the univariate noise to be less detrimental to the utility (due to the curse dimensionality in differential privacy (Dwork & Roth, 2014)). In other words, we would expect the gap between non- non-private and private utility to be smaller than that of DP-SGD. However, it is possible that for some tasks the non-private performance of zeroth-order optimization is poor (see Section 4.3).
Algorithm Differentially Trivate-ZO)
1: Model paramcters 0, dataset D, learning rate 7) perturbation scale Φ, privacy paramcter a, noising mechanism 2 (Gaussian or Laplace), clipping threshold C, expected batch size B, sub-sampling rate
p p= =B/IDI).
2: for E I....T do
Poisson sample B from D with sub-sampling rate p
E~ /~~N(i NN(0 [(000111101111
@+ + 0 0z
6:
0- + 0 - oz
7:
for [I V1) E B do
8:
If + L(++, (z;; vi))
9:
L. + [(0 (zi, Vi)
10:
4 = clipllt .T.)) C)
11:
end for
12:
if Z is Gaussian then
Lies (+..00,C9
13:
B:2g else if 2 is Laplace then
14:
Eeen 4 Lappalacc
15:
B.26
16: end if
17:
0 = 0 nsE
18: end for
DP-ZO. We explain the steps of our algorithm while emphasizing the key differences from Definition 2.4 required to provide DP guarantce. We first sample a batch from the datasct with Poisson sampling (Balle et al., 2018) which allows us to use privacy amplification by subsampling. For each model parameter 0g we want to update, we independently sample a perturbation 2; from a standard Gaussian distribution and scale it by a predetermined constant o; we denote the full perturbation vector as Φž. Now we compute an approximation of the gradient by projecting it onto the random perturbation E. That is, for a training sample di we compute the difference in scalar losses between 0 + ož, 0 - dž. Intuitively, this scalar tells us how much better one random step is than the other. We clip this scalar to limit the sensitivity We add noise to the aggregation over samples in our training batch (described in detail in the subsequent paragraph). Finally, we take a step in the direction Z by scaling our private step size by the expected batch size, perturbation constant Φ, and the learning rate n).
DP-ZO enables new mechanisms by privatizing the difference in losses between perturbations. DP-ZO proposes update direction determined by d-dimensional random vector (sampled from standard Gaussian distribution) independent of the private training data. The only private information is the step size, that is influenced by the difference in losses between perturbations with opposite signs. To privatize this step size, we add noise proportional to the sensitivity of the step size. We bound the sensitivity of the step size by clipping the per-example step sizes to a specific range [-C, C), so the sensitivity under add-remove DP is C.
Given a private scalar with bounded sensitivity, we can apply the classical Gaussian mechanism release a privatized scalar with (c, J)-P. The Gaussian mechanism is widely studied in privacy-preserving machine
4

---

Published in Transactions on Machine Learning Research (01/2025)
learning techniques like DP-SGD. However, the Gaussian mechanism can only provide (c, ()DP) and rescarchers often recommend using crypiographically small values of á (Vadhan, 2017). The stronger privacy notion, i.e., s-DP, comes with guarantee that the mechanism will never fail catastrophically. For example, we can use the Laplace mochanism to achieve the pure E-DP guarantoe. However, due to large tails of the Laplace mechanism, it has never been a contender for high dimensional optimization.
Although it is possible to obtain pure DP with DP-SGD by adding Laplace noise scaled to the & sensitivity of the gradient, this is challenging for large models because the l sensitivity can be vd times larger than the Eg sensitivity (and often is; see Section 4.3), especially for billion-parameen parameter LLMs. In contrast, DP-ZO only requires privatizing the loss. The one-dimensional private estimation of the step size is amenable to the Laplace mechanism, because the Ep norms are equivalent for the scalar. Specifically, DP-20 with the Laplace mechanism is the first method to achieve a reasonable cervacy-utility trade-off off under pure e-DP for private fine-tuning of LLMss. While this work primarily explores these two mechanisms, DP-70 is flexible enough to be extended to other differential privacy mechanisms, broadening its applicability.
Privacy analysis. As we consider multiple accounting methods with multiple previously proposed mecha- nisms, we give the overview of the analysis below and defer the full privacy analysis to Appendix A.
Theorem 3.1. Algorithm 1 is (f, DD.. Particularly, for Laplace mechanism Laplace o)), Algorithm 1 is ED with E = T- loog11 +p. (c!/a - 1)).
Proof Overview. We first provide the privacy analysis for each step. At cach step, line 10 upper bounds the l (and therefore by 21 for the scalar value) sensitivily of the difference in losses 1, by C. Lines 13 and 15 add noise based DP mechanisms such that each step in Algorithm satísfies (e, 6)PD) with some privacy parameters. For Laplace mechanism, each step satisfies s-DP where log + (e2/0 - -1)). For Gaussian mechanism, each step satisfies (E. (PP where max(Ha (N of) p).,), + +NN(1, Hee p),(1, + pW(0, (2), 0²))) & 8 and (-ll-) is Hockey-stick divergence (see Definition A.3 in Ap- pendix A). Therefore Algorithm is (s, 6)-DP with some privacy parameters that are calculated via some mechanissm-deependent composition theorem. Most of the privacy analyses in Appendix A are similar to the privacy analysis of DP-SGD and are based on the numerical composition of privacy loss random vari- able (sce Definition A.7 in Appendix A) for the corresponding privacy curve (Gopi et al., 2021) except for the pure s-DP analysis. The analysis for pure e-DP by the Laplace mechanism is based on the basic composition (Dwork & Roth, 2014). Given a number of iterations T and the use of the Laplace mechanism Laplace(O, Co), Algorithm 1 is s-DP with E = T' log(1 + p- (c2/a-1))
Remark. We can get a tighter composition of e by relaxing Laplace mechanism's e-DP to (c, 6).D). Note that since we are dealing with scalar values, our mechanism in each iteration will be a one dimensional Laplace mechanism. Therefore we can compute the dominating pair for a single dimensional Laplace mechanism based on Zhu et al. (2022); Wang et al. (2023), that is tighter than directly using the private random variable for privacy curve of a sDDP algorithm in Gopi et al. (2021). We detail the full privacy analysis in Appendix A.
Prior works (Song et al., 2021; Li et al., 2022a) have analyzed when the convergence rate of DP-SGD is dependent on the effective rank r of the problem rather than the model dimension size d. A concurrent and independent work (Zhang et al., 2024a) propose DPZero by privatizing the loss difference scalar in ZO with Gaussian noise, that shares some similar design as our DP-ZO. They provide the convergence guarantee for DPZero that is independent of the model dimension in private training. Here we briefly discuss the algorithm design difference between DPZero in Zhang et al. (2024a) and our DP-ZO. DPZero is Algorithm 2 in Zhang et al. (2024a), and the random perturbation is by sampling E' from a unit Sphere gd-1 = {x E Rd = =1] In our Algorithm 1, Z is sampled from Gaussian distribution. We reimplemented our perturbation method based on the algorithms in Zhang et al. (2024a), and we obtain 82.32o.s2 for LoRA fine-tuning OPT-13B on SQuAD with (1, 1 DDD, that is comparable as the perturbation method in our Algorithm 1, that achieves 82.28p.84 under the same sctting. We also note that Zhang et al. (2024a) also share same observation on this by experiments on Roberta-large models (Liu el al., 2019) in their Table 7. Algorithm 2 in Zhang et al. (2024a) for DPZero is under full batch setting. 2 As we show in Appendix D.2, in the evaluated number of iteration range, given the same amount of computation time on single GPU, by training more steps with small batch size, DP-ZO achieves better performance than by accumulating steps for large batch size. This result is
TThe experiment section Zhang al. (2024a) also uses small batch size and perturbation from random Gaussian distribution.
5

---

Published in Transactions on Machine Learning Research (01/2025)
consistent with the observation in the non-private zeroth-order optimization results in McZO (Malladi et al., 2023). Besides, Algorithm 2 in DPZero considers the sensitivity as 2C with clipping threshold C, this leads to adding twice necessary noise under add/remove DP. Our Algorithm 1 analyzes the sensitivity C' with clipping threshold C, and we share this add/remove DP choice and sensitivity C' with popular DP-SGD library like Opacus (Yousefpour et al., 2021). We further discuss our work and Zhang et al. (2024a) Section
4 EVALUATION
We first overview our experimental setup in Section 4.1 and then evaluate the performance of DP-70 in Section 4.2. We find that DP-ZO provides a competitive privacy-utility trade-off for conservative privacy budgets across multiple datasets, model architectures and can scale to large models under conservative privacy budgets. We also compare DP-ZO to DP-SGD in Section 4.2 and show that DP-ZO achieves comparable performance to DP-SGD for the same model size. Furthermore, we show that DP-ZO achieves non-trivial privacy-utility trade-off under pure e-DP under a conservative privacy budget like e = 4 on large language models. In Section 4.3 we first provides results of DP-ZO across different model architectures. We then measure the empirical privacy loss and computation efficiency of DP-ZO, We also characterize DP-Z0 under different few-shot scttings and different noise mechanisms for (D....
4.1 Experimental Setup
We report the metric of interest (F'l score or accuracy) and standard deviation averaged across independent runs with different random sceds. We detail the full hyper-parameter searches and computation cost. in Appendix D.2.
Datasets. Following Malladi et al. (2023), we mainly consider three different benchmark NLP tasks: SQuAD (Rajpurkar et al., 2016) and DROP (Dua et al., 2019) for text generation, and SST2 (Socher et al., 2013) for text classification. We use F1 for text generation and accuracy for text classification as evaluation metric (we include a detailed description of the metric in Appendix D.1). Although all these datasets have very different dataset sizes, we consider the few-shot setting for all these datasets where we sample 1000 points for each dataset. Fine-tuning LLMs with O(n 1000) samples a standard setting in the NLP community (Gao et al., 2021; Malladi et al., 2023) because we are generally interested in the few-shot abilities of LLMs (Brown et al., 2020). This represents a departure from prior works that privately finctune LLMs; Yu el al. (2022); Li et al. (2022b); Yu et al. (2021b) use the entire training dataset of SST2 that has about 65,000 examples. It is well known that the privacy-utility trade-off improves greatly with more data (Tramèr & Bonch, 2021). It is straightforward to see that our sctting with datasets of the size n = 1000 with = 10-6 is simultaneously more challenging and more aligned with real-world usecases than previous works in DP finetuning of LLMs. Despite the increased difficully of our few-shot setting as compored to prior work, our results volidate that DP-20 realizes a strong privacy-utility trade-off. We also varies the training sample size from the few-shot to the full training set by conducting experiments the QNLI (Wang et al., 2019) dataset to be consistent with previous works (Li et al., 2022b; Yu et al., 2022) for fair comparison.
Models. We present our main results (Table 1) using a pretrained OPT-13B (Zhang et al., 2022) model that is finetuned with LoRA (Hu et al., 2022); that is, we update- < 1% of the total parameters. We include a range of analysis, including varying the model size among the OPT series, model architectures including Mistral-7B-vi (Jiang ct al., 2023) and amount of parameters to be updated, after we present the main results. We also include one experiments for QNLI on RoBERTa-base (Liu et al., 2019) to be consistent with previous works (Li et al., 2022b; Yu et al., 2022) for a fair comparison.
Privacy budgets. We consider various privacy levels with = = (0.5, 1,44 and fix 5 = 10-5 for (c, We include the zero-shot e = 0 that does not incur any privacy loss because we evaluate the pretrained model directly without finetuning on private data. We also include the non con-private E = oo baseline that is trained without any DP guarantce. That is, we itcrate over the shuffled datasct instead of doing Poisson sampling (replacing line 3), do not clip the step size (skipping line 10) and set o (in line 13). We make these modifications because Poisson sampling and small threshold like C 0.1 for per-example clipping makes
6

---

Published in Transactions on Machine Learning Research (01/2025)
gradient estimator biased and loss convergence issues in a = 0 for DP-SGD (Andrew et al., 2021; Chen et al., 2020; De et al., 2022; Bu et al., 2023b), and we want to compare to the strongest possible nonprivate baseline.
4.2 Main Results
DP-ZO provides a strong privacy-utility trade-off for conservative privacy budgets. As shown Table 1, across all three tasks and all ES, DP-ZO significantly improves upon the baseline, and only slightly degrades the performance compared to the non-private baseline. For SQuAD, even at E = 0.5, DP-ZO can still achieve 80.10%, that significantly outperforms & = 0 baseline (46.23%). The gap between & = 0.5 and & 0o is about 6.75%. By increasing & from 0.5 to 4, this gap can be further reduced to 3%. For DROP and SST2, DP-Z0 (Gaussian) achieves comparable performance as the non-private baseline at E == 4.
Table 1: Main results with 1000 training samples for each dataset. OPT-13B model with LoRA fine-tuning. DP-ZO (G) is DP-ZO instantiated with the Gaussian mechanism. 8 = 10-5. The E = oo by 'o is 86.85 for SQuAD, 33.22 for DROP, and 93.69 for SST2. The s = 0 baseline, i.e., directly doing model evaluation without training, is 46.23 for SQuAD, 14.64 for DROP, and 58.83 for SST2. The results of DP-SGD on DROP are omitted because fino-tuning OPT-13B on the DROP dataset by LoRA will cause the out of memory issue on a single A100 GPU even in the non-private setting.
Task
SQuAD
DROP
SST2
Task type
generation (metric: F1)
classification (metric: accuracy)
Method
= 0.5
8 =
8 == 4
= 0.5
6=1
6 == 4
= 0.5
6 6= 1
6 6 4
DP-ZO(G)
80. 00.e0..
82.28n.se
83.87
28.39o.s2
30.30p.51
31.99o.s1
85.412.91
91.19p.90
92.59p.30
DP-SGD
79.85..90
82.1
83.05g.51
64.33
90.25p.78
92.06g.52
DP-ZO scales to large models. In Table we show that DP-ZO continues improving as the model size increases from 1.3B to 66B. Due to space constraints, we provide the non-private (e oo) performance of all models and methods in Appendix E. Table 2 shows promising insight: the model size and non-private performance increase, the gap in performance belween privale and non-prieale models shrinks. Specifically, the gap for OPT-1.3B is 5.68% (80.97% at = oo reduced to 75.29% under E = 1). But this gap shrinks to just 3.37% for OPT-66B, where the private performance at c = 1 is 84.12% compared to 87 87.49% non-privately. Our findings suggest that DP-ZO scales to large models not only because is compatible with existing pipeline without much additional engineering effort but also because the utility drop due to privacy is smaller as the model size increases.
Table 2: DP-ZO (Gaussian) and DP-SGD with full parameter and LoRA fine-tuning on SQuAD with 1000 training samples across different model sizes. (1, (0,-DD-) means the approach did not scale with forward implementation; Section 5 details the additional engineering required to scale DP-SGD to larger models. ._ for DP-ZO means the results are omitted due to limited computational resources. Due to limited computing resources, this table does not include the standard deviation for OPT-66B model.
Method
OPT-L33
OPT-2.7B
OPT-6.7B
OРT-13B
OPT-30B
OPT-66B
DP-ZO-LoRA (Gaussian)
75.29p.90
80.341.14
81.341.04
82.28
82.48o.83
84.121.01
DP-SGD-LORA
75.39p.a3
79.42p.57
79.53o.52
82.14
DP-ZO-Full (Gaussian) 72.841.03
77.250.27
79.06g.67
82.16p.41
DP-SGD-Full
75.50p.89
79.81o.64
Comparison with DP-SGD. We compare DP-ZO to differentially private stochastic gradient descent (DP- SGD) (Abadi et al., 2016) which has been applied to fine-tune LLMs with full parameter fine-tuning (Li et al., 2022b) and with LoRA (Yu al., 2022; He et al., 2023). Recall that DP-ZO compatible out-of-thoobox with mixed precision training and GPU parallelism, enabling us to fino-tune OPT-66B. As we discuss in Section 5, it is significantly more challenging to integrate DP-SGD with these techniques, and furthermore, DP-SGD
7

---

Published in Transactions on Machine Learning Research (01/2025)
requires more memory than DP-ZO to store activations and compute per-sample gradients (sce Section 4.3). As a direct result, DP-SGD cannot directly scale past 2.7B with full fine-tuning 13B with ToRA without additional implementation effort for multi-GPU training, while DP-ZO can scale seamlessly to larger models. In Table we present comparisons between DP-ZO and DP-SGD with full paramcter finctuning and LoRA. With the same model size, DP-Z0 achieves comparable performance as DP-SGD as by LoRA finetuning, ie., both DP-ZO and DP-SGD achieves 82% on OPT-13B models. The best performance by DP-ZO is 84.12% by OPT-66B finetuned with LoRA. This is 2% better than the best performance of DP-SGD in Table that is 82.14% by OPT-13B with LoRA.
DP-ZO with pure c-DP. To the best of our knowledge, DP-ZO (Laplace) is the first method that achieves non-trivial privacy-utility trade-off under pure s-DP under a conservative privacy budget like = 4 on large language models.
In Table 3, DP-ZO (Laplace) can significantly improve upon & = =0. Given a budget 4, which some prior work has considered reasonable (Ponomareva al., 2023), DP-ZO (Laplace) can obtain 73.52% on SQuAD. When increasing = 4 to E = 15, DP-ZO (Laplace) can obtain 78.82% on SQuAD. Note that the 4 sensitivity required for Laplace mechanism makes it hard for DP-SGD to achieve comparable performance as DP-ZO because the gradients in DP-SGD have high dimension. Table 3 shows that DP-SGD with I norm clipping and Laplace noise only achieves 47. 47.25% for reasonable privacy budgets with & ranging from 4 to 15, that is only marginal improvement upon the zero-shot performance. Even when relaxing the privacy budget to near-vacuous guarantees such as 6 = 10450, DP-SGD (Laplace) still achieves worse performance compared to DP-ZO due the Laplace noise added in digh-dimension gradients.
Table 3: Pure e-DP by DP-70 (Taplace), SQUAD with 1000 training samples. OPT-13B with LoRA finetunnngg The e = baseline is 46.23%. 8
E 10
15
10450
DP-ZO (Laplace)
73.521.04
76.751.39
78.821.s7
81.021.24
DP-SGD (Laplace) 47.250.79
47.27g.95
47.361.02
76.50p.s9
4.3 Analysis
In this section, we provide experiments for DP-ZO across different model architectures, empirical privacy analysis to measure how private is DP-2O, memory efficiency of DP-ZO, the amount of training data that we sample in DP-ZO, and the choice of DP mechanism in DP-ZO.
DP-ZO provides a strong privacy-utility tradc-off across different model architoctures. Table and Table 2 show that DP-ZO achieves the comparable performance DP-SGD on various OPT models sizes. We now rum experiments include the results of OPT-6.77 7B and OPT-13B for the case of comparison. On Mistral-7B-vi DP-ZO and DP-SGD both achieve comparable performance at E = 1, that are around 89%. Moreover, even Mistral-7B-vi has similar model parameters as OPT-6.7F and much fewer parameters than OPT-13B, DP-ZO achieves better performance by Mistral-7B- than OPT-13B. This indicates that with the development of more advanced models, the power of DP-ZO will be further unlockod.
SQuAD with Mistral-7B-vi model (Jiang et al., 2023) in Table 4 and
Table The results of DP-ZO on different model architectures. The = 0 baseline for Mistral-7B-vl 68.37. Mistral-7B-vl
Models
OPT-6.7B
OPT-13B
DP-20
81.34..04
82.28p.84
89.79..41
DP-SGD
79.53u.s2
82.14p.1s
89.44g.11
DP-ZO memory efficient. We omitted several results of DP-SGD in Scction 4.2 due excessive memory consumption of DP-SGD that leads to out-of-memory (OOM) issue on single A100 80G GPU. We now provide more fine-grained memory analysis for better understanding of DP-ZO and DP-SGD.
8

---

Published in Transactions on Machine Learning Research (01/2025)
The naive implementation of DP-SGD causes additional memory consumption due to the per-example gradient computation. An ongoing line of work (Li et al., 2022b; Yu et al., 2022; He et al., 2023; Bu et al., 2024) has continued improving the scalability of DP-SGD over the past few years. For memory cost comparison, we consider several variants of DP-SGD including DP-SGD-full (Abadi et al., 2016; Li et al., 2022b), DP-SGD-ful(ghoot) (Li et al., 2022b), DP-SGD-LORA (Yu el. al., 2022), DP-SGD-BiLFiT (Bu el al., 2024) and DP-ZO (including full and LoRA) for fair comparison.
As discussed in Li et al. (2022b); De al. (2022), small batch size will incur sub-optimal performance of DP-SGD and therefore large batch size is preferred, we consider gradient accumulation in memory analysis to enable large batch size. We consider full precision both for DP-SGD and DP-ZO for fair comparison. We present the results of such memory consumption for different sequence lengths on OPT-2.7B in Table 5.
Table 5: Comparison of memory consumption (GB) of DP-ZO and DP-SGD varying different sequence length L on OPT-2.7B. Full-precision, no gradient check-pointing, Batch size=2, gradient accumulation steps-2. OOM indicates out-of-memory on a single A100 80G GPU.
Methods
DP-SCD-full DP-SGD-fullghoot)) DP-SCD-LORA DP-SGD-BiFRt DP-ZO-full DP-ZO-LoRA
L 128
51.3
32.9
11.4
12.2
11.6
10.3
L= 512
51.4
39.6
18.1
21.3
11.7
11.1
L = 2048
OOM
OOM
OOM
OOM
15.6
15.6
Table shows that the naive implementation of DP-SGD incurs around 50GB for sequence length L 128 and incurs out-of-memory (OOM) issue when increasing sequence length to L = 2048. Ghost clipping can help reduce the memory consumption by removing per-sample gradient computation, but still needs to accumulate gradients and consumes memory more than 30GB. Parameter efficient fnn-tuning methods including DP-SGD-LORA, DP-SGD-BitFiT can largely reduce the memory cost for gradient accumulation with fewer parameters in gradients. However, as the imput sequence length L increases, the activation saved in forward-pass for gradients computation significantly increases and inputs with sequence length 2048 still cause OOM error for parameter efficient fine-tuning methods. Note that such long sequence input exists in practical scenarios such digesting from long documents and recent foundation models put efforts to support longer context (Gemini-Tees et al., 2023). In contrast, DP-ZO does not need to store gradients nor store additional activation for gradients, therefore can reduce the memory consumption to be less than 16GB even when sequence length is 2048. In fact, DP-70 only incurs a negligible additional memory cost than Zo (Malladi et al., 2023) for the per-sample loss clipping and noise addition.
We now consider a more restrictive memory setting such as on- device mobile setting, i.c., 8GB as memory limit (Gim & Ko, 2022; Guo et al., 2024). As discussed in Malladi et al. (2023), gradient checkpointing can help reduce the ivaitation memory consumption. We use gradient checkpointing to reduce the memory consumption of activation and half-precision to reduce the memory consumption of weights and gradients. We measure the memory cost with the default implementation of activation checkpointing where we checkpoint every block of the model. We consider batch size=1 and accumulate gradients in 2 steps to enable training in large batch size. We present the results of the memory consumption for different sequence lengths on OPT-2.7B model in Figure 5. While gradient checkpointing significantly reduces the memory consumption in DP-SGD, DP- SGD-full is still beyond the SGB memory limit due gradient accumulation. Similarly, with gradient checkpointing, DP-SGD-
17.7
impu_lee==12 Input Ion-204B
15.0-
Memory Contoo
12.5
20.0
limit
7.5
5.4
5.7
6.2
5.2
5.0
0.0
DP-7G-ull Methoes
DP-70-0ra
Figure 5: Memory comparison of DP-ZO and DP-SGD with half-precision and gradi- ent checkpointing. Batch size=1, gradient. accumulation steps=2.
$DP-SCD-full DP-SGD-fullghhett) DP-SCD-LoRA based https:/ http:/gtthbbbbob//ueeeeeeee http:///ucceee//paaatttaaatarrre pravattt-trassssrmesss For DP-SGD-BitFi, we use fastDP https//github.comm htg.huub.co//wwllaaae...s wwwlawswwassaaaoaaaaaaa /wwss//s//fstttllffeeeeee liffeeeleeeeettiall palllpprriiaeeeeeeeeee /tree/mainn /m//////aa//aDPP and follow the guideline by using one line of code [param.requires grad grad__aaaaale (False) for name, param in madel.named parameters() if "bias' not in name).
9

---

Published in Transactions on Machine Learning Research (01/2025)
LoRA still exceeds the 8GB limit when increasing sequence length to 2048. In contrast, DP-ZO incurs just 6.2GB even when input sequence length is 2048.
How private is DP-ZO and ZO: an empirical privacy analysis. We discussed earlier in Section 2.2 that the single scalar information from Zeroth-order Optimization will leak private information and therefore motivate our design of DP-70. We now validate our design by conducting empirical privacy evaluation through membership inference attacks (MIA) (Shokri al., 2017) understand the privacy implication of DP-ZO. We use the state-of-the-art privacy auditing method in Panda et al. (2024b) for empirical privacy evaluation. Similar to Panda et al. (2024b), we construct synthetic canaries by creating one new token for each canary to the vocabulary to increase the information from canaries for better auditing. Following Panda et al. (2024b); Mireshghallah et al. (2022), we use MIA Area under the ROC Curve (AUC-ROC) for empirical privacy evaluation. We report the results for DP-ZO and DP-SGD in Table for different es including [0.5, 1,4, 10, oo].
As observed in Panda et al. (2024b), this privacy attack method is very successful for DP-SGD when no noise added, and DP-SGD can effectively reduce the attack AUC to 54.8 that is closed to random guess at 0.5. For DP-ZO, when noise added, the MIA AUC is 71.4 that is lower than DP DP-SGD(E oo), however much higher than the random guess bascline 50. Interestingly, in this empirical privacy case study, the privacy leakage of 70 is similar to the privacy leakage of DP-SGD at e = 10. DP-70 is motivated to get a formal privacy guarantee by differential privacy. DP-ZO can reduce the attack AUC to around random guess at s = [0.5, 4] To the best of our knowledge, this is the first experimental result that measures the privacy leakage in ZO and DP-ZO. This result shows the necessity of DP-ZO reduce MIA close to random guess, and also raises an open problem about the inherent privacy property of zeroth-order optimization.
Table 6: Membership Inference Attack AUC-ROC for DP-70 and DP-SGD.
8 0.5
8
8 = 4
==
10
8 = 00
DP-Z0
53.2
54.5
55.6
58.8
71.4 100.0
DP-SGD
54.8
55.0
61.5
71.9
Characterizing the effect of data size. Although it known that private learning requires more data than non- non-private learn- ing (Bassily et al., 2014), prior work has not characterized this improvement for fine-tuning language models. In Table 7 and Figure 6 we first vary the number of training samples around the n = 1000 setting in the main results while keeping = 10-5 fixed for all choices of n. Table 7 shows that DP-ZO can achieve nontrivial performance in few-shot settings under conservative privacy guarantees. Furthermore, we find that while increasing the amount of training data by 10x barely increases pon-private performance, it increases private perfor- mance by R 6% (n = 500 vs. n = 5000). Similarly, for e-DP; acquiring more data enhances privacy amplification and reduces the amount of noise we need to add to achieve a target DP guarantee. In Table 8 we find that increasing the number of training examples from 1000 to 5000 improves performance at == 4 from 73.52% to 79.89%, although the improvement of by increasing training samples from 1000 to 5000 is insignificant.
250-shot
Training Loss (ar = 0.01)
1.75
500-shot
1.50
1000-shat
5000-shot
1.25
1.00
0.75
0.50
0
20000
40000
60000
Iterations
Figure 6: (Smoothed) training loss. n = 5000 has better convergence rate compared to n 250.
non-private performance at
While non-private few-shot learning can succeed by just memorizing the training data, Figure 6 indicates that the convergence rate for different shots for private few-shot learning is different. With the proliferation of pretrained models, we anticipate that pricalely fine-tmiig downstream lasks in the few-shot selting will be more aligned with real-wor world use cases (Gao et al., 2021).
Besides the shot setting, we now scale the size of training data size up to more than 100k samples and compare the performance of DP-SGD and DP-70. For the ease of comparison, we follow Li et al. (2022b); Yu
10

---

Published in Transactions on Machine Learning Research (01/2025)
Table 7:
The effect of different n training samples for DP-ZO (Gaussian) fon SQuAD dataset. (1,I0-9)-DP.
Table 8: E-DP (s = 4) by DP-ZO (Laplace) on different n in SQuAD on OPT-13B (LoRA). & = x by 70 is $6.85% for n = 1000 and 86.92%
OPT-13B with LoRA finetuning.
n-shot
nt = 250
πt 500
n= 1000
π = 5000
for 5000. & = 0 is 46.2%.
n-shot
n= 1000 " 5000
1
74.86p.74 86.40
78. 78.252.38
82. 82.280.84
84.29
00
86.53
86.85
86.92
DP-70 (Taplace) 73.521.04
79.89b.49
Table Comparison of DP-ZO and DP-SGD on different
Table 10: DP-ZO with different DP mechanism.
n in QNLI on RoBERTa-base model. (3, 4.7 x 10-P)-D
SQuAD with 1000 training samples. 5 = 10-5
n-shot
1000
5000
10000
50000
104743
8
= 0.5
==1
5 4
DP-SGD
73.27
79.44
80.54
84.81
87.40
DP-ZO (G)
80.10
82.28u.84
83.87
DP-ZO
76.19
78.66
79.28
79.70
79.85
DP-ZO (L)
77.580.s1
80.490.63
82.944.69
et al. (2022) and conduct experiments for DP-ZO and DP-SGD on QNLI with RoBERTa-basc with a range of examples at (3, 4.7 x 10-53-DP and report result in Table 9. Similar to previous observation, Table 9 shows that at a small data regime, i.e. number of samples n = 1000, DP-ZO achieves comparable performance as DP-SGD. DP-70 can also improve its performance within more samples. Compared to DP-SGD, we notice that when inercasing the data size n, there is a utility gap between DP-ZO and DP-SGD, In addition, we compare the utility of DP-ZO, ZO, DP-SGD, SGD under different n in Table 11 to further understand the utility gap between DP-ZO and DP-SGD. Due to the limited computation resources, for RoBERTa-basc on QNLI and OPT-13B (LoRA finc-tuning) on SST2 in Table 11 for n 1000 and full training set. We observe a similar utility gap between DP-ZO and DP-SGD as QNLI in Table 9 for SST2 in Table 11 when increasing n to the full training set. The utility gap of SGD and 70 on QNLI and SST2 in Table 11 indicate that the challenge of utility for ZO when the number of training samples n increases. Therefore there is also the utility gap between DP-ZO and DP-SGD when n increases. This limitation shows open problem on how to improve data efficiency in zeroth-order optimization (Zhang al., 2024c; Zhao et al., 2024) and DP-2O, and we leave this data efficiency improvement in ZO as future work.
provide results
Different noise mechanisms for (c, D)D.. We now relax the privacy guarantee provided by the Laplace mechanism to approximate (e, 8)-DP. Tn Table 10, we compare DP-70 instantiated with the Laplace and Gaussian mechanisms. DP-ZO (Gaussian) outperforms DP-ZO (Laplace) for strict privacy budgets such as ş = 0.5 because it enjoys lighter accounting (Gopi et al., 2021) and lower variance (Dwork Roth, 2014). These advantages are less significant for larger privacy budgets; for 4, the gap between DP-ZO (Gaussian) and DP-ZO (Laplace) is within 1%.
Our experiments the DP-ZO with laplace for s-DP and the comparisons of Laplace and Gaussian mechanisms for (e, DD shows that DP-ZO provides a strong utivicy-utility trade-off under different DP mechanisms while DP-SGD suffers from Laplace mechanisms for (c, which opens the new opportunity for the synergy between DP mechanisms and large language models.
Table 11: (DP-)ZO and RoBERTa-baas 10 (1,10-5)
across different number of training samples (3, 4.7 x 10-9) for QNLI
5) for SST2 OPT-13B. For full set, 104743 for QNLI and 66849 for SST2.
QNLI
SST2
DP-ZO
Z0
DP-SGD
SGD
DP-ZO
ZO
DP-SGD
SGD
n 1000
76.19
79.85
73.27
84.40
91.19
93.69
90.25
95.64
full set.
79.85
79.99
87.40
89.49
93.00
94.84
95.07
96.33
11

---

Published in Transactions on Machine Learning Research (01/2025)
5 DISCUSSION
Discussion of our work and DPZero (Zhang et al., 2024a). Most recently, a concurrent work (Zhang et al., 2024a) also privatizes the SPSA algorithm in zeroth-order optimization method. Zhang et al. (2024a) propose DPZero and provide the convergence guarantee for DPZero that is independent of the model dimension in private training. Zhang et al. (2024a) presented experimental results for DP7ero/DP-SCC on Roberta-large model and DPZero on OPT 1.3B-6.7B models. Our work focus on understanding the privacy-utility trade-off for DP-ZO as well as the privacy implication and the practical implication of DP-ZO. We provide a comprehensive understanding of the privacy-utilityy trade-off for DP-ZO and DP-SGD for OPT-1.3B to 66B models. We consider DP-ZO as a general framework for private machine learning. We found that DP-ZO is compatible with Laplace mechanism and enabling e-DP with reasonable privacy-utility trade-off while DP-SGD with Laplace mechanism suffers to optimize. The result indicates that DP-ZO can open the new opportunity for the synergy between DP mechanisms and large language models. To the best of our knowledge, we provide the first experimental result that measures the privacy leakage in (DP-)ZO. We also conduct experiments for analyzing the effect of data size and the memory consumption for limited resource scenarios. Our findings could provide insights on future directions for improving the analysis and implementation of DP-ZO methods.
Discussion DP-SGD and DP-ZO. In Section 4.2 we showed that DP-70 obtains competitive privacy- utility tradcoff. Now examine the amount of engineering effort necessary to scale DP-SGD to larger models, a topic on which many papers have been written (Bu et al., 2023b;c; Youselpour et al., 2021; Li et al., 2022b; He et al., 2023; Bu et al., 2023a). We find that DP-ZO seamlessly scales to larger models and believe its simplicity presents a compelling alternative to DP-SGD for practitioners.
DP-SGD. Differentially Private Stochastic Gradient Descent (DP-SGD) (Song et al., 2013; Abadi el al., 2016) is the standard given by w(++1) (t() | dclip w(t)) + where the two changes to SGD are the ex eXVe(a,,(())
algorithm to train models on private data, with an update rule
per-sample gradient clipping (Vi(,, w())) max(c]]VV and addition of noise sampled from a d-dimensional Gaussian distribution & ~ (O,, 1) with standard deviation a. DP-SGD is the marquee algorithm for seeracc-rreeeving machine learning, but it requires implementing per-example gradient clipping. This creates slew of challenges for deploying DP-SGD.
Computational and memory challenges in DP-SGD. DP-SGD requires the computation of per-example gradients, which can be naively implemented by storing each gradient in the batch separately. This approach inflates the memory overhead by factor of B, where B is the batch size. TensorFlow Privacy avoids this issue by clipping microbatches rather minibatches, which does not slow down training but increases the noise added and therefore hurts utility. Jax can automatically vectorize the per-sample gradient computation, but. training is still slowed down. Recently, specialized libraries have been developed that instead analytically compute the norm of the gradients for different layers (Li et al., 2022b; Bu ct al., 2023d; Ding et al., 2024). This requires actually implementing the computation, which is challenging for new layers. Parameter efficient fine-tuning methods (Yu et al., 2022; Bu et al., 2024) can help reduce the computation cost by reducing the number of trainable parameters. However, as discussed in Section 4.3, those methods still incur much more memory cost than DP-ZO for long sequences. Besides, when model cannot be loaded into a single GPU, model parallelism needed to load large models across several GPUs and per-example gradient norm clipping requires additional implementation, both for gradient clipping and communication across device. He et al. (2023) investigate how to make group-wise gradient clipping efficient and achieve good performance in DP-SGD and fine-tunes 175B GPT3 model with 16 V100 GPUs each with 32 gigabytes of VRAM. Bu et al. (2023a) implements DP-SGD based on Zero Redundancy Optimizer (Rajbhandari et al., 2020) to scale model size up to GPT-100B and maintain efficiency. It currently also only supports layer-wise or block-wise clipping.
We now discuss the advantage of DP-Z0 that can scale to large language models seamlessly. Note that DP-Z0 inherits the scamless scalability from 70 as a result of only additional computation cost on loss. DP-ZO achieves comparable performance as DP-SGD. In contrast, DP-SGD incurs more computational and memory challenges than SGD due to per-example gradient clipping.
12

---

Published in Transactions on Machine Learning Research (01/2025)
Model parallelism and data parallelism in DP-ZO. To train large models like OPT-66B, whose parameters cannot be loaded into memory on single A100 GPU, we need to implement some form of parallelism across GPUs. It is easy for such parallelism in DP-ZO (in the simplest form, just running DP-ZO on a machine with 2 GPUs will prompt HuggingFace to implement naive model parallclism), while much more effort DP-SGD. To synchronize model stale between GPUs in pall--prallee-D--200 we just transfer the random seed and its corresponding half-precision float16 scalar step size; this is just a few bytes. However, first-order approaches such as DP-SGD require the transfer of gradients across devices to update all the models, necessitating expensive allgather and reduce operations. This communication overhead is 1.5d in PyTorch FSDP, where d is the size of the model.
DP-ZO is storage and communication-efieee significant advantages in terms of storage and communccatin efficiency, especially beneficial for bandwidth- constrained environments like edge devices (Li et al., 2024). Unlike traditional methods where the difference in model parameters 6u- - 0 shared which could amount to multiple gigabytes for large models, DP-ZO allows for the storage and transmission of sequence of updates. This sequence is represented as an array of tuples [(SEEDo, 0.54). (SEEDy, -0.14)], where each tuple contains a seed and step size, taking up only 4 bytes. Even for 1 x 10t fine-tuning iterations, this array would require less than 1MB of storage, representing substantial reduction in both storage and communication overhead. We can apply these weight differences to a model by simply iterating over the array, sampling from the PRNG using the given seed, scaling that random vector, and applying it to the current model parameters. This procedure highly efficient, as it involves only sequential memory accesses and scalar floating- point operations.
even after training has completed. DP-ZO offers
DP-SGD vs. DP-ZO. We have discussed the memory efficiency of DP-70 over DP-SGD in details. This is helpful in limited memory scenarios as show in Figure 5. While being much more memory efficient, DP-ZO achieves comparable performance as DP-ZO on several tasks including OPT-13B models on 1000 SQuAD examples with Gaussian mechanism (Table 1) and provides reasonable privacy-utility trade-off for c-DP (Table 3), which is promising. We also note that the utility challenge of DP-ZO when scaling with more samples (Table 7), mostly due to the gap of ZO and SGD (Table 11). This indicates the future improvement for data efficiency in zeroth-order optimization, that will benefit DP-ZO with Gaussian and Laplace mechanism.
6 CONCLUSION
DP-SGD has been the de-facto private training method of the last decade. In this work we propose DP-ZO, a novel method for private fine-tuning that privatizes the zeroth-order update by adding noise to the difference in loss between two perturbations. DP-ZO's unique univariate privatization unlocks training larger models with better parallelism than DP-SGD. DP-ZO provides strong privacy-utility tradc-off across different tasks, model sizes, dataset sizes, and DP mechanisms. We anticipate that future work can further study these design choices, integrate more DP mechanisms into DP-ZO, and apply it to the vision domain.
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Securily, pp. 308 318, 2016.
Wael Alghandi, Juan Felipe Gomez, Shahab Asoodeh, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. The saddle-point method in differential privacy. In International Conference on Machine Learning, pp. 108-528.7 PMLR, 2023.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34:17455 17466, 2021.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for diffcrential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pp. 394-403. PMLR, 2018.
13

---

Published in Transactions on Machine Learning Research (01/2025)
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, 2018.
Gilles Barthe, Marco Gaboardi, Benjamin Grégoire, Justin Hsu, and Pierre-Yver Strub. Proving differential privacy via probabilistic couplings. In 2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-10. IEEE, 2016.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, 2014.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D) Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Nya Sutskever, and Dario Amodei. Language models are few-shot. learners. In Advances in Neural Information Processing Systems, pp. 1877 1901, 2020.
Zhiqi Bu, Justin Chiu, Ruixuan Liu, Sheng Zha, and George Karypis. Zero redundancy distributed learning with differential privacy. arXiv preprinl arXiv:2311 11822 2023a.
Zhiqi Bu, Hua Wang, Zongyu Dai, and Qi Long. On the convergence and calibration of deep learning with differential privacy. Transactions on Machine Learning Research, 2023b. ISSN 2835-8856. URL
https:// //ppr///////ee//eee/e wtw.:rrrwwweeeeeoouuuuummmaa net/forummId-xOCAGG (ackkccGgKKKSSSS
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. In Advances in Newral Information Processing Systems, 2023c.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private optimization on large model at small cost. In Proceedings of the 40th International Conference on Machine Learning, pp. 3192 3218. PMLR, 2023d.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Differentially private bias-term fine-tuiig of foundation models. In Forty-first International Conference on Machine Learning, 2024.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release statistics. ACM Transactions on Information and System Security (TISSEC), (3):1-24, 2011.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Nearal Information Processing Systems, 33:13773 13782, 2020.
Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How private are DP-SGD implementations? Tn Ruslan Salakhuudinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 8904 8918. PMLR, 2024.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
Damien Desfontaines and Balézs Pejó. Sok: differential privacies. Proceedings on Privacy Enhancing Technologies, 2020(2):288 313, 2020.
Youlong Ding, Xueyang Wu, Yining Meng, Yonggang Luo, Hao Wang, and Weike Pan. Delving into differentially private transformer. In Proceedings of the 41st International Conference on Machine Learning, pp. 11049-11071. PMLR, 2024.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint Xix:v:1905. 1905.0238,, 2019.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings on Privacy Enhancing Technologies, 2022.
Minxin Du, Xiang Yue, Sherman M. Chow, Tianhao Wang, Chenyu Huang, and Huan Sun. Dp-forward: Fini-g and inference on language models with differential privacy forward pass. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 2665 1065-2679, 2023.
Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 2368 2378,, 2019.
Haonan Duan, Adam Dziedzic, Nicolas Papernot, and Franziska Boenisch, Flocks of stochastic parrots: Differentially private prompt learning for large language models. In Advances in Neural Information Processing Systems, 2023.
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. IEEE Transactions on Information Theory, (1)5)22788 2806, 2015. doi: (0.1109/TIT.20
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-407 2014.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint (XX3:160300188 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp. 265-284, 2006.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the Corty-Second ACM Symposium on Theory of Computing, pp. 715-724, 2010.
Arun Ganesh, Mahdi Haghifam, Milad Nasr, Sewoong Oh, Thomas Steinke, Om Thakkar, Abhradeep Guha Thakurta, and Lun Wang. Why is public pretraining necessary for private model training? In Proceedings of the 40th International Conference on Machine Learning, pp. 10611-10622 PMLR, 2023.
Tianyu Gao, Adam Fisch, and Danqi Chen. Making pre-trained language models better sew-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), pp. 3816 3830, 2021.
Gemini-Tenn Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean- Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja. Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312. 11805, 2023.
Saced Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. Xie preprint arXis:1309.5549, 2013.
In Gim and JeongGil Ko. Memory-efficient dnn training mobile devices. In Proceedings of the 20th Annual International Conference on Mobile Systems, Applications and Services, pp. 464-476, 2022.
Gooble's-D--Libraar. Dp accounting library, 2020. URL https://githe: com/ com/google/
differential httpa//iaaaaiiiteeeeeeeeeraaaaaa hwtpdpppcccooinn...m
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, pp. 11631-11642, 2021.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Cristiano Gratton, Naveen K. D. Venkategowda, Reza Arablouci, and Stefan Werner. Privacy-preserve distributed learning with zeroth-order optimization. TEEE Transactions on Information Forensics ond Security, 17:265 279, 2022. doi: 10.1109/T1FSS 2021.31997...
Wentao Guo, Jikai Long, Yimeng Zeng, Zirui Liu, Xinyu Yang, Yide Ran, Jacob R Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, et al. Zeroth-order fine-tuning of llms with extreme sparsity. arXiv preprint arXie:2406. 02913, 2024.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarmi, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. In International Conference on Learning Representations, 2023.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Zonghao Huang, Rui Hu, Yuanxiong Guo, Eric Chan-Tin, and Yanmin Gong. Dp-admm: Admm-based distributed learning with differential privacy. IEEE Transactions on Information Forensics and Securily, 15:1002-100 -012,, 2020. doi: 10.1109/TIFS. 201.2231068.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. Xrviv preprint arXiv:2310.0682 2023.
J. Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of a regression function. Annals of Math- 16662-46,, ematical Statistics, 23:462 466, 1952. URL https://api. semanticscholar wwg. htt//CoppuI:::2220700100
Antti Koskela and Antti Honkela. Computing differential privacy guarantees for heterogeneous compositions using fft. arXiv preprint arXiv:2102. 12412, 2021.
Antti Koskela, Joonas Jälkö, and Autti Honkela. Computing tight differential privacy guarantees using fft. International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020.
Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pp. 3358-3366. PMLR, 2021.
Christian Janos Lebeda, Matthew Regehr, Gautam Kamath, and Thomas Steinke. Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition, In IEEE Conference on Secure and Trustworthy Machine Learning, 2025.
Brian Lester, Rami Al-Rfou, and Noah Constant. The power of scale for parameter-effcieet prompt tuning. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 3045 3059, 2021.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. 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), pp. 4582-4597, 2021.
Xuechen Li, Daogao Liu, Tatsunori Hashimoto, Huscyin A Inan, Janardhan Kulkarni, YinTat Lee, and Abhradeep Guha Thakurta. When does differentially private learning not suffer in high dimensions? In Advances in Newral Information Processing Systems, pp. 28616-28630, 2022a.
Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations, 2022b.
Zhe Li, Bicheng Yang, Zidong Liu, Chaosheng Dong, and Haibo Yang. Achieving dimension-fre. communication in federated learning via zeroth-order optimization. arXiv preprint arxiv:2405. 15861, 2024.
16

---

Published in Transactions on Machine Learning Research (01/2025)
Sijia Liu, Bhavya Kailkhura, Pin-Ye Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, 2018.
Sijia Liu, Pin-Yu Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod K Varshney. A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43 54, 2020.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zeulemoyer, and Veselin Stoyanov. Roberla: A robustly optimized bert pretraining approach. arXiv preprint arXie:1907. 16692, 2019.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Advances in Neural Information Processing Systems, 2023.
Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 247 264, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450336930. doi: 10.1145/3222 /33433333333347366633 URL
http://d....rr/00..111////444442 3243765.
Microsoft. Prv accountant, 2021. URL http:://gggtubb...o///crroo/t//
Fatemehsadat Mireshghallah, Kartik Goyal, Archit Uniyal, Taylor Berg- King-KKrkpatrickk, and Reza Shokri. Quantifying privacy risks of masked language models using membership inference attacks. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. for Computational Linguistics, 2022.
Association
Iyy Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security foundations Symposium (CSF), pp. 263-275, 2017.
Yurii Nesterov and Vladimir G. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
Ashwinee Panda, Xinyu Tang, Saeed Mahloujifar, Vikash Sehwag, and Prateek Mittal. A new linear scaling rule lor privale adaptive hyperparameter optimization. In Forty-forst International Conference on Machine Learning, 2024a.
Ashwinee Panda, Xinyu Tang, Milad Nasr, Christopher A. Choquette- Choo,, and Prateek Mittal. Privacy auditing of large language models. In TCML 2024 Workshop on Foundation Models in the Wild, 2024b. URL https: /tttpe://ppenreviex http://wwww.....oo..//m////aaaaa
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113-1200 jul 2023. doi: 221613/jair.1.. 1.1649.
Samyam Rajbhandari, Jelf Rasley, Olatunji Ruwase, and Yuxiong He. Zero: memory optimizations toward training trillion parameter models. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Press, 2020.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2383 2392, 2016.
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Proceedings of the 26th Annual Conference on Learning Theory, pp. 3 24. PMLR, 2013.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEFF Symposium on Security and Privacy (SP), pp. 3- 18. IFFE, 2017.
17

---

Published in Transactions on Machine Learning Research (01/2025)
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, pp. 1631-111100 1642, 2013.
David M Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proceedings on Privacy Enhancing Technologies, 2019(2):245-2g)) 269,, 2019.
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pp. 248, 2013.
Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pp- 2638 2646. PMLR, 2021.
James C. Spall. Multivariate stochastic approximation using a simultancous perturbation gradicnt approxi- mation. IEEE Transactions on Aulomatic Control, 37:332 341, 1992.
Xinyu Tang, Ashwince Panda, Vikash Schwag, and Pratock Mittal. Diffcrentially private image classification by learning priors from random processes. In Advances in Newrul Information Processing Systems, 2023.
Xinyu Tang, Richard Shin, Huseyin A Inan, Andre Manoel, Fatemchsadat Mireshghallah, Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, and Robert Sim. Privacy-preserving in-context learning with differentially private few-shot generation. In International Conference on Learning Representations, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Tzacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and elficient foundation language models. arXiv preprinl XrXiv:230..13971 2023.
Florian Tramèr and Dan Boneh. Differentially privale learning needs better features (or much more data). In International Conference on Learning Representations, 2021.
Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pp. 047-450,44 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R. Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations, 2019.
Jiachen T Wang, Saeed Mahloujifar, Tong Wu, Ruoxi Jia, and Prateek Mittal. A randomized approach for tight privacy accounting. In Advances in Neural Information Processing Systems, 2023.
Tong Wu, Ashwinee Panda, Jiachen T. Wang, and Prateek Mittal. Privacy-preserving in-context learning for large language models. In International Conference on Learning Representations, 2024.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and llya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiu:2209.1199 12298, 2021.
Da Yu, Huishuai Zhang, Wei Chen, and Tie Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Representations, 2021a.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Yan Liu. Large scale private learning via low-rank reparametrization. In International Conference on Machine Learning, pp. 12208-12218. PMLR, 2021b.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In International Conference on Learning Represendations, 2022.
18

---

Published in Transactions on Machine Learning Research (01/2025)
Liang Zhang, Bingcong Li, Kiran Koshy Thekumparampil, Sewoong Oh, and Niao He. DPZero: Private fine-tuning of language models without backpropagation. In Forty-first International Conference on Machine Learning, 2024a.
Qinzi Zhang, Hoang Tran, and Ashok Cutkosky. Private zeroth-order nonsmooth nonconvex optimization. In International Conference Learning Representations, 2024b.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pro-trained transformer language models. arXiv preprinl or Xiv:2200. 01068, 2022.
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin- Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-cfficient LLM fino-tuning: A benchmark. In Forty-first International Conference on Machine Learning, 2024c.
Yanjun Zhao, Sizhe Dang, Haishan Ye, Guang Dai, Yi Qian, and Ivor W Tsang, Second-order fine-tuning without pain for llms: A hessian informed zeroth-order optimizer. arXiv preprint arXiv:2408.1517% 2024.
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of disferential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics,
PMLR, 2022.
19

---

Published in Transactions on Machine Learning Research (01/2025)
A Privacy Analysis
DP-ZO can be instantiated with different noise mechanisms. In this subsection provide privacy analysis for the Gaussian mechanism and Laplace mechanism.
We first introduce two propositions for DP analysis.
Proposition A.1 (Basic Composition theorem (Dwork & Roth, 2014)). If M1 is (=1,61)-DP and M2 is (E2, 62), then the adaptive composition of M1 and M2 is (#1 + E2, 81 + +
Proposition A.2 (Privacy Amplification via Subsampling (Balle al., 2018)). If M is (e.6)-DP, then the subsampled mechanism with sampling rate p obeys (E', -'DP with privacy parameters e' = =log(1 + +((e - 1)) and 8' = po.
Analyzing the privacy guarantees of specific mechanism can be done via worst-case inputs to a mechanism M leading to pair of worst-case distributions (Dwork & Roth, 2014), Meiser & Mohammadi (2018) introduce a novel method to approximately compose the privacy curves based on the discretized version of privacy loss random variables (Dwork & Rothblum, 2016), whose distribution is called privacy loss distribution (PLD). Meiser & Mohammadi (2018) provide the worst-case pair of distributions for basic mechanisms such as Gaussian mechanism and Laplace mechanism. Sommer al. (2019) derive the exact analytical and closed formula for the Gaussian mechanism. Zhu et al. (2022) formalize rigorous notion of the "worst-case" PLD for DP mechanism under the name dominating PL.Ds. Therefore, following Zhu el al. (2022), we introduce the following definitions.
Definition A.3 (Hockcy-stick Divergence). For a > 0, the Hockey-stick divergence is defined as Ha (PII))
P(o) Eo Q(o) -a)+], where (x)) == x1 (x: (x200 0).
Lemma A.4. (Barthe et al., 2016) For a randomized algorithm M, sup He (M(D)) 8 is equivalent to Desinilion 2.1.
We follow Zhu et al. (2022) and formalize 8 a function of E.
Definition A.5 (Optimal Privacy Curve). The optimal privacy curve a mechanism M the function 8m R+ + [0, 1] s.t. 6m(s) == supp-ry Hes (M(D)))M(D').
Definition A.6 (Dominating Pair of Distributions (Zhu et al., 2022)). (P,Q) is a dominating pair of distributions for M (under neighboring relation >) if for all a 20
sup H Ha(M(D))M(('))) & Ha(Pl)) DzD
(3)
When P. P,Q is chosen such that equation 3 takes "_" for all (P,Q) is light dominating pair of distributions or simply, tightly dominating.
Based on Sommer et al. (2019); Koskela et al. (2020); Gopi et al. (2021), we follow Zhu et al. (2022) and define the privacy loss random variable as follows.
P(o) Definition A.7 (Privacy Loss Random Variable). We call := log Qío) o ~ P the privacy loss random variable (PRV) for mechanism M associated with dominating pair (P.
Zhu et al. (2022) prove that any privacy mechanism has tightly dominating pair of distributions and provide the dominating pairs for basic privacy mechanisms such as Gaussian mechanism and Laplace mechanism.
Further, based on Definitions A.3 and A.7, (PII)) can be written as an expectation: H.s (PlQ)) =
Ey [1 (1-e-M),] M,]- 8M(() can be bounded by first identifying M's dominating pair distributions as well
as the associated PRV Y, and then computing this expectation, denoted as (x) = Ey [11 (1-ce-X) (M(() < (E), where 5x)(E) = (E) for tight dominating pair (P,Q).
As we sample a batch of samples from the training data via poisson subsampling in each iteration for experiments, we introduce the subsampling amplification for dominating pair following Zhu et al. (2022).
20

---

Published in Transactions on Machine Learning Research (01/2025)
Proposition A.8. (Zhu et al., 2022) Let M be randomized algorithm. If (P.Q) dominates M then (P. (p(1-))p+p)) dominates Me Poisson for add neighbors and - + pp, pP,p))+pp,@) Q) dominates M o Sp for remove neighbors, where S Poisson is poisson sampling with subsampling rate
Poisson
Given dominating pair, Zhu et al. (2022) show that if the characteristic function of the PLDs has analytical expression, for example, Gaussian mechanism, the tight DP composition bounds can be computed in O(1) times. However, without the closed form, such as the sub-sampled Gaussian and sub-sampled Laplace, numerical accounting methods for T steps are proposed to approximate the integral composition formula and compute upper bounds on the privacy budget parameters (e. () in DP (Koskela et al., 2020; Koskela & Honkela, 2021; Koskela al., 2021; Gopi et al., 2021; Doroshenko al., 2022; Alghamdi et al., 2023; Wang et al., 2023). There are multiple open-souree implementations for numerically accurate composition including Microsoft (2021) and Google's-DP-Iane D-DessD-PParry (2020) that are used by DP-SGD experiments (Yu el al., 2022; Chua et al., 2024)
We now provide the privacy analysis for DP-ZO.
Gaussian Mechanism. As outlined in Line 10, the l2 scnsitivity of Algorithm is C' and we are adding [(0, C²o²) noise to the estimated loss. From Zhu et al. (2022), we know that the tight dominating pair for Gaussian mechanisms is P -0 and Q =2(,o0²). By Proposition A.8, each step therefore satisfies (e, ()-P) where
(N(,,
+ H. (L + s (4)
For step, we analyze the compositions of subsampled Gaussian for T steps with the PRV accountant of Gopi et al. (2021). We provide the privacy parameters we use for Gaussian mechanism in Table 16 and Table 17. We also provide the example code for using Microsoft PRV Accountant library (Microsoft, 2021) below.
from prv_accountant import Prisosssbaanppedddsssssaaaaaaaae from arv_accountant import PRVAccountant sample_rate = 16/1000
signa 16.4
step = 75000
delta 1/(1e5)
mech DssisosSuaaanlluuussssaallaaaaaa
noise_ hasse__ultipllierrsiin,,,
saap:ing__robbbliitssaaap.____
10
accountant PRVAccountant
11
prve=[mech],
12
13
ops_error=0.001,
14
delta_error=le-10
15
ape_low, eps_est, up accountant
(delta-deta. num_self,__ sus_eels_coopeeiioon=
step])
10 print (eps_loc eps_est, epa_up)
Listing 1: DP accounting using Microsoft PRV Accountant (Microsoft, 2021). We ensure the upper bound upSup does not exceed the desired e at the specified 8.
Laplace Mechanism. Laplace mechanism can give pure DP guarantee of 0 which can be interest. in some socnarios. Here we first analyze the pure s-DP guarantce provided by Laplace mochanism and then provide the analysis for approximate 8)-DP analysis.
Pure E-DP by Laplace mechanism. We data in single batch instead of all training data to compute the gradients in each updates. For the privacy analysis for Laplace mechanism in Algorithm 1, when we sample each batch in the poisson manner, we could leverage Proposition A.2 to compute the privale amplification by subsampling. We first analyze the privacy cost for one step by the Laplace mechanism. At each step, we sample new batch of data with the sample rate of p B/D As outlined in Line 10, the e sensitivity of Algorithm 1 is C. By Proposition 2.3, the privacy cost at one step would cost (1/a, O)-DP on this batch.
By Proposition A.2, the privacy cost at one step would cost (log(1 + p (c O)DP the full dataset.
21

---

Published in Transactions on Machine Learning Research (01/2025)
D. By Proposition A.1, the privacy cost of Algorithm 1 instantiated with Laplace mechanism satisfies (Poog(( + p. (el/o 1)), D)-DP
We provide the privacy parameters we used for pure s-DP by the Laplace mechanism in Table 12.
Table 12: Privacy parameters for Table 3 and Ta-
Table 13: Privacy parameters for Table 10. (e. 8)DD guarantee for Laplace. 8 = 10-5, |D] 1000. BSZ-16, Steps=75000.
ble 8, e-DP by Laplace. BSZ=20, Steps=2000.
D]
10.5
1000
4
(by Monte-Carlo)
(by pure-DP PRV)
4.5
1000
10
30.8
0.5
0.51
3.2
1000
15
16.3
1.04
2.5
5000
4
4.6
4.70
Approximate e-DP by Laplace mechanism. We can also get tighter composition of s with relaxation to 8 >> O. The most straight forward way is to instantiate the privacy loss random variable of random response with (log(1 + +p- +p- (e2/o - 1)) 0) because the dominating pair for random response is a dominating pair for the pure DP mechanism. Then, we can use the numerical composition of Pure DP PRV accountant by Gopi et al. (2021). Note that this method is agnostic to the DP mechanisms used for pure e-DP. We now provide more fine-grained privacy analysis for the Laplace mechanism. Specifically, composition for the Laplace mechanism by Monte Carlo based DP accountant (Wang et al., 2023). Note that since we are dealing with scalar values, our mechanism in each iteration will be one dimensional Laplace mechanism. Let b be the scale of Laplace noise, p the sub-sampling rate, and assume the sensitivity is 1, and assume we are doing composition for T iterations, each iteration with sampling rate p. By Zhu et al. (2022) we know that the pair of distribution (P, Q) dominating pair for a single dimensional Laplace mechanism, where P and Q are distributed according to the following probability density functions,
could compute the privacy cost of
1 exp(-1x 11/b). fp exp(-1xz1/b) and fo = 2b
1
Therefore, (P Q) is the dominating pair for the sub-sampled Laplace. We plug this into the standard Monto-Carlo accountant of Wang et al. (2023) (without importance sampling, see Algorithm 2 and Theorem 10 in Wang et al. (2023)) while using 102H samples to calculate the 5 at a given value of c. Also, using the analytical accountant explained above, we always make sure that E[Sacc is bounded by 10-8 (we use the fact that E[ is bounded by B[Y²] and the fact the PRV Y is always bounded for Laplace mechanism). This ensures that the error of our estimation of 8 is at most 10 8 with probability at least 1 1- 1-10-5 Putting all together, for all reported values of E, our 5 is bounded by 10-5, with probability at least 0.99999. This privacy analysis is tighter with E is high compared to the former analysis which uses the pure DP PRV accountant. This is consistent with the intuition. As we increase the distance between the Laplace dominating pairs, the probability of sampling points from the area between the centers increases. And that is where the Laplace Mechanism different from the Randomized Response. We present the accounting results for the Laplace method to achieve (c, 5)-D) by these two accounting methods in Table 13. Table 13 shows that the Monte Carlo based DP accountant can give tighter analysis for the Laplace mechanism for (c, ()DP) than the pure &DD PRV method.
Remark A.9. We want to note a minor technicality in our privacy analysis with poisson subsampling. Zhu et al. (2022) treat the add neighboring relation and remove neighboring relation separately, because this is crucial in retaining tight dominating pair with a fosed-form expression. As shown in Zhu et al. (2022) and Lebeda et al. (2025), neither one of the add/remove neighboring relation can dominates the other one. To get the results for the standard add/ren ded/remove neighboring relation for T-fold composition of subsampled mechanism, we need to do the pointwise maximum of the add-only and remove-only relation. The Microsoft (2021) library only implements one of the add/remove and our randomized accounting method for subsampled Laplace (2020) implements DP
mochanism only considers the add-only relation. We note that Google's-DP--Lirre accounting by taking maximum of the two neighboring relations under T folds and provides the accounting code for both sub-sampled Gaussian and sub-sampled Laplace mechanisms. We verify that our privacy
22

---

Published in Transactions on Machine Learning Research (01/2025)
parameters in Tables 13 and 16 to 18 do not exceed the desired e using the method of Doroshenko et al. (2022) in Google's-DP-Iibrra (2020) with the pessimistic estimate (i.e., the upper bound).
Implementation Details
We follow Malladi et al. (2023) and provide the memory-efiicient version of DP-ZO in Algorithm 2. Algorithm 2 enjoys the benefit that it does not incur additional GPU memory cost compared to inference.
A Algorithm 2 Differentially Private-70 (GPU memory efficient. version. Adapted from Malladi et al. (2023) Model parameters dataset D, learning rate a, perturbation scale ø, random seed s, weight decay X, noise scale 0, noising mechanism 2, clipping threshold C, expected batch size B and sampling rate p B/ Lines with are DP modifications.
procedure DP-ZO((0, D, o, T, 6, C, a))
3:
for t E T do
4:
Poisson samples B from dataset D with sampling rate + PerturbParameters// 0,5)
5:
Compule per-sample loss (1 B)*
t PerturbParameterss 220 s)
Compute per-sample loss C2 B3)*
O +
6)
10:
Compute difference in loss L = L1 L2
11:
Clamp L between -C' and C
Σ L+2(C,o)
12:
B+2g
13:
Reset random number generator with seed
14:
for 0: E 0 do
15:
2 ~~~ ~0011
16:
0: < 02 0
17:
end for 18: end for
19: end procedure
20: procedure PERTURBPARAMETEESS(
21:
Reset random number generator with seed
22:
for 0, E 0 do
23:
2 ~~ (0,11
24:
0, 0z
25:
end for
26: end procedure
C Design Choices
Algorithm outlines our DP-70 that estimates the gradients via privatized loss value without backpropagation. In this subsection, we provide several design choices for Algorithm 1.
Definition 2 (n-SPSA Gradient Estimator) The n-SPSA gradient estimate averages Vo, over n randomly sampled 2. We can write this vector notation, dropping the normalizing constants for succinctness.
gi L(O ez;; B) L(0 - ez;; e2;; (projecced gradient for each i)
Z [21, .... 2n (matrix whose columns are the 2 vectors)
g = [g1. 02. Inl ] of projected gradients)
Then the n-SPSA gradient estimate be written
23

---

Published in Transactions on Machine Learning Research (01/2025)
VI, B) g Z (2)
How Many Gradients to be Estimated in Model Update. Algorithm 1 estimates the gradients once. As outlined above, SPSA can be extended to n-SPSA gradient estimator and n-SPSA can improve the performance in the non-private setting (Malladi et al., 2023). Here we discuss our design choice of why we choose n = 1 in Algorithm 1.
Estimate the average. Previous work (Malladi et al., 2023) shows that averaged estimation helps the non-private setting. In a private setting, we have to privatize the gradient estimation. Here we discuss our initial design of the privatized n-SPSA gradient estimation. For the sampled batch, assuming we are adding the Gaussian noise (00 C²a²) for 1-SPSA. Then for n-SPSA, to ensure we have the same privacy cost as 1-SPSA, we need add WNO, C²a²) cach gradient estimation and finally average the n gradients. Our privacy analysis follows the n-fold composition of Gaussian mechanism (Corollary 3.3 in Gaussian differential privacy (Dong et al., 2019)). Our imitial experiment result shows that our current analysis for n-SPSA noise addition does not make n-SPSA improve in the private set ting compared to 1-SPSA. We leave the improvement in tighter analysis for private n-SPSA as future work and use 1-SPSA to conduct experiments.
The Type of Noise for DP. As discussed in Section 3, Algorithm 1 can be incorporated in different noise mechanisms. We focus on the Gaussian noise mechanism and the Laplace mechanism in this work. The Gaussian noise mechanism has been widely studied in previous literature both for privacy analysis and empirical performance in DP-SGD (Abadi et al., 2016; Mironov, 2017; Dong et al., 2019). The Laplace mechanism, though less studied for privacy-preserving machine learning, can provide pure DP while the Gaussian mechanism can only provide approximate DP. We have provided the privacy analysis in Section A.
D Experimental Details
D.1 Datasets and Metrics
Datascts. Following Malladi et al. (2023), we use SST2 (Socher et al., 2013) for text classification and SQuAD (Rajpurkar et al., 2016) and DROP (Dua et al., 2019) for text generation. SST2 is a binary classification for sentiment classification based on text from movie reviews. SQuAD and DROP are question answering tasks, that given the context and question, the language model should output needed answers. Such answers are generated tokens one by one and therefore considered as generation task. In Section 4.3, follow prior works (Yu et al., 2022; Li et al., 2022b) and experiments on QNLI (Wang et al., 2019). QNLI is a binary classification task to determine whether the two sentences in pair are entailment not.
Metrics. Following Rajpurkar et al. (2016), we use the Fl score for text generation task. For ground truth and generation, we count the number for each different tokens (therefore ignoring the ordering of the tokens) and calculate the number of same tokens Nsame between the ground truth and the predictions. Precision is Precision N Nsame/Ngt where Ngt is the total number of tokens of ground truth. Recall is Recall = Nsame/Naaann Npred, where Npred the total number of tokens of ground truth. F1 is the harmonic mean of precision and recall F1 2/( 2pprccisooo + " We use classification accuracy for text classification evaluation metric.
D.2 Hyper-parameter Search
Our experiments are based on the open-source code of Malladi et al. (2023). We provide the prompts we use in Table 14. In this section, we first provide several initial results for hyperparameter search on clipping threshold and finally present the hyperparameter tables. We also provide an initial study to systematically evaluate the interplay between batch size and training ilerations for DP-ZO
24

---

We present the hyper-parameter for Published in Transactions on Machine Learning Research (01/2025)
Table 14: The prompts of the datasets we used for DP-ZO.
Dataset
Type
Prompt
SQuAD
QA
Title: <title>
Context: <context>
Question: <question>
Answer:
DROP
QA
Passage: <context>
Question: <question>
Answer:
SST-2
classification
<text>
was
terri-
ble/great
Different Clipping Threshold. Li et al. (2022b); De et al. (2022) recommend small clipping C threshold for DP-SGD training. For example, al. (2022b) use C = 0.1 for training language models. We therefore study the effect of different clipping threshold and present the results in Table 15. We find that while C' = performs significantly worse, setting C as 0.1, 0.05, 0.01 within the 2% performance gap. We therefore choose C = 0.05.
Table 15: Different clipping C. 15.9. batch size=16, 10,000 steps. 0.35.
Clip=1
Clip=0.1
Clip=0005
Clip=0.01
F1
66.04
74.26
76.81
75.39
Hyper-parameter for DP-ZO (Gaussian) in Main Results. DP-ZO (Gaussian) in Table 16 and Table 17.
Table 16: Hyper-parameter search for DP-ZO in main results Table 1.
|D]
1000
Steps T
75000
Clipping C Batch size
0.05
16
30.9 for 0.5, 16.4 for 1, 4.8 for
learning rate
[5c-6, 1c-5, 2c-5, 5e-5, 1c-4] 8
LoRA rank
0.01
Table 17: Hyperparameter search for DP-70 with full parameter fine-tuning in Table 2.
D
1000
Steps T'
10000
Clipping C Batch size
0.05
16
11.47 for = 0.5, 6.08 for = 1, 1.88 for =
learning rate
[2e-7, 5e-7, 1e-6, 2e-6, 5e-6]
0.001
Hyper-parameter for DP-SGD.
We present the hyper-parameter search for DP-SGD in Table 18.
25

---

Published in Transactions on Machine Learning Research (01/2025)
Table 18: Serer--arameter search for DP-SGD in Table
D
1000
Steps T
200
Clipping C
0.1
Batch size
64
6.60 for == 0.5, 3.59 for = 1, 1.28 for = = [1o44 20-4, 5c-4, 1o-3, 20-3] for LoRA fine-tuning.
learning rate
[le-5, 2e-5, 5e-5, le4, 2e-4, 5e-4] for Full fine-tuning. 8
LoRA rank
Hyper-parameter for DP-ZO (Laplace). The paprmmter search for DP-ZO (Laplace) similar to DP-ZO (Gaussian).
Effects of Batch Size and Steps. In Table 19 and Table 20, we did an initial study systematically evaluate the interplay between batch size and training iterations by varying batch size in [16,32,64,125 and steps in [10000, 2000, 40000, 80000]. Similar to main results, run 5 independent runs for each setting and compute the average of 5 runs. This set of experiments is done on OPT-13B on SQuAD dataset with LoRA fine-tuning. Table 19 and Table 20 show that increasing steps T improves the performance more than increasing the batch size. We also run experiments of T' in [200, 400, 800, 1600] for DP-SGD (and did not observe significant improvements in DP-SGD) to ensure the fair comparison of DP-SGD and DP-ZO. Taking the computation limitation into consideration, we set = 75000 and batch size BSZ=16 for main results in Table 1. We leave more investigation on the batch size and steps for DP-ZO, such variance reduction method, future work.
Table 19: T 10000, Varying batch size BSZ.
Table 20: Batch size=16.
Varying steps T'
BSZ=16
BSZ=32
BSZ=64
BSZ=128
T
10000
20000
40000
80000
81.35
81.63
81.47
81.72
F1
81.35
81.65
81.42
82.52
Computation Cost. DP-ZO for OPT-13B models SQuAD datasets takes around 4hrs for 10000 steps. DP-SGD for OPT-13B models on SQuAD datasets takes around 4hrs for 200 steps. When increasing T or B in DP-70, the training time scales proportionally to the scaling factor. Future work includes how to reduce the computation time of DP-ZO, c.g., by variance reduction method to improve the convergence rate.
E Effect of Model Size
Section 4.2 shows that DP-ZO scales to larger models and provides the results of DP-ZO for model size varying from 1.3B to 66B parameters in Table 2. Here provide the full results of DP-ZO finetuned with baseline
LoRA at 1, with model size ranging from 1.3B to 66B. We also include the = 0 and reference in Table 21.
Table 21 shows the full trend of DP-2O with model size scaling from 1.3B to 66B, that is DP-20 scales to larger models.
For OPT-1.3B, the gap between private and non con-private baseline is 5.67. For OPT-66B, the non-private baseline is 87.49 and the gap between the private and non-private results is 3.37.
26

---

Published in Transactions on Machine Learning Research (01/2025)
Table 21:
The experiment results of DP-ZO across different model sizes. (1,10-9)-DP.
Model
OPT-133
OPT-2.7B
OPT-6.7B
OPT-13B
OPT-30B
OPT-66B
0
27.20
29.89
36.48
46.23
46.53
48.13
8 1
75. 75.29n.90
10.341.14
81.341.04
82.28p.84
82.48p.88
84.121.01
0C
80.97
84.14
86.44
86.85
86.98
87.49
F RELATED WORK
In this section we give an overview of the broader body of work privacy preserving large language models and private zeroth-order optimization method.
Privacy preserving large language models. Recent studies have leveraged DP-SGD to fine-tune large language models. Li et al. (2022b) provide methods for fine-tuning large language models with DP-SGD by ghost clipping to mitigate the memory burden of per-sample gradient clipping. Yu et al. (2022) report compelling results by only updating sparse subset. of the LLMs with parameter efficient fine-tuning (PEFT) methods such as LoRA (Hu et al., 2022). He et al. (2023) leverage group-wise clipping with adaptive clipping threshold and privately fine-tune the 175 billion-parameter GPT-3. Duan et al. (2023); Li et al. (2022b) also consider private prompt tuning by adding noise to the soft prompt (Li & Liang, 2021; Lester et al., 2021). Du et al. (2023) add non-i.idd noise from a matrix Gaussian distribution to directly perturb embedding in the forward pass of language models. With the emergence in-context learning of large language models (Brown et al., 2020), recent works (Duan al., 2023; Wu al., 2024; Tang el al., 2024) study privale in-context. learning of large language models without fine-tuning.
Private zeroth-order optimization. Most recently, a concurrent work (Zhang al., 2024a) also considers the same DP-SPSA algorithm for veroth-order optimization. We have discussed our work and DPZero (Zhang et al., 2024a) in Section 5.
Zhang et al. (2024b) study private zeroth-order nonsmooth nonconvex optimization. Their work incorporates two zeroth-order estimators to reduce variance and samples (model dimension) i.i.d. estimators for each data point to achieve optimal dimension dependence. Zhang al. (2024b) leverage the tree mechanism (Dwork et al., 2010; Chan et al., 2011) on disjoint data to ensure the privacy cost of the algorithm. The main focus of our work is private fine-tuning of large language models and one estimator for each batch could successfully converge in this set-up. Therefore, we only need to privatize such scalar. We leave the investigation on the private zeroth-order for more than one estimators such as the variance reduction method proposed in Zhang et al. (2024b) as future work.
Gratton al. (2022) analyze the intrinsic privacy of the zeroth-order optimization for DP-ADMM (Huang et al., 2020) in distributed learning. Their work states that if the output of the zeroth-order method itself follows Gaussian distribution, the noise be analyzed the Gaussian mechanism and provide intrinsic privacy. However, this is merely stated
assumption for lemma 1. To the best of our knowledge there is no work that proves that the zeroth-order gradient estimator can actually be analyzed as the sum of an unbiased gradient estimator and some Gaussian error lerm.
27


Reviews:
[{"review_id": "V5Ad48TaXz", "reviewer": "Reviewer_7MQH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Extensive experimental results testing various hypotheses in different settings (models, datasets, privacy levels, dataset size, etc.), including experiments showing the competitiveness of DP-ZO and its memory efficiency. \n\n    a. Papers also show that gap between DP-ZO and DP-SGD reduces as the model size increases\n\n    b. I also very much appreciate that the authors include a very useful negative results (Table 9) which shows that the gap between DP-ZO and DP-SGD increase with number of samples.\n\n2. Paper identifies that “exact” epsilon-DP which incurs additional dimension dependent terms in DP-SGD (and hence impractical) is practical in DP-ZO (also see weakness).\n3. Authors also use Membership Inference Attacks (MIA) to analyze the privacy leakage of DP-ZO and conclude that inherent noise in sampling the direction for the derivative boosts the empirical privacy of DP-ZO over DP-SGD.\n4. Authors also argue in detail that scaling DP-ZO to larger models though sophisticated model training paradigms (e.g. model/data parallelism) is easier to implement than DP-SGD which requires per-sample gradient clipping instead of per-sample directional derivative clipping.\n\nWeaknesses:\n\n1. Theory is wrong and incomplete: Although authors claim to provide privacy analysis and convergence rate of their method but it seems incomplete and wrong. Some issues are noted below\n\n    a. Theorem 3.1 statement appears incomplete as algorithm hyper parameters values are not defined.\n\n    b. Number of iterations T does not appear in the privacy analysis of Gaussian mechanism?\n\n    c. Clipping factor C does not appear in the analysis of Laplace mechanism\n\n    d. Proof contains too much hand-waving. Proof by words (jargon) instead of more precise mathematical statements. What are PRV and “dominating pair”?\n\n    e. It is also quite peculiar that proof (Appendix A) computes precise values for \\delta which never appeared in the theorem statement.\n\n    f. There are additional dimension factors appearing in zeroth order optimization. So it is not clear whether Laplace mechanism would be practical in all use cases of DP-ZO such as full finetuning or training from scratch. Making theory more precise would help with this confusion.\n\n    g. Proposition 3.2 is given without any proof. Authors allude that this follows from Malladi et al. (2023). However, this prior work precisely proves it for non-DP ZO algorithm under certain conditions including taking limit of \\phi. However, it is not at all clear how the same applies to DP-ZO (with non-zero \\phi) which adds clipping and noise perturbation. One concern is that clipping factor or noise may be dimension dependent and lead to worse convergence rate for DP-ZO.\n\n    h. “In the non-private setting where the adaptation between the pretrained model and the fine-tuning dataset has low rank (Hu et al., 2022), as in fine-tuning large language models, Malladi et al. (2023) show this method converges at a rate that is not catastrophically slower than SGD fine-tuning.” This is incorrect reading of (Malladi et al., 2023) which assumes low rank Hessian of the objective. This is clearly different from assuming low rank in LoRA finetuning where of Hessian could still have large rank.\n\n2. Prior work not properly attributed. Authors’ claim that (Zhang et al., 2024a) is a concurrent and independent work is hard to justify as this paper appeared in October 2023. (Zhang et al., 2024a) seems to have already made the observation that adding DP to ZO is computationally cheap and proved it theoretically. It is also worrisome that authors do not mention this paper till page 5 and only discuss their contribution in page 12. According to standard academic conventions, it is more appropriate to discuss very relevant prior work in the introduction and only claim the novel contributions (see strengths) as original as opposed to “new methodology DP-ZO” (on page 1).\n\n3. Why are different settings (models, datasets, etc) chosen for different experiments. E.g. Table 7 vs 9, Table 1 vs 2. Usually arbitrary experimental choices like these increases the chances of wrong conclusion by sheer randomness.\n\n   a. How does DP-ZO compare with MeZO and DP-SGD when doing full fine tuning on these 3 datasets instead of QNLI?\n\n4. Paper is not well written mainly due to many undefined jargon and terminology. Sometimes sentences are hard to parse.\n\n    a. “empirical privacy analysis is still much higher than random guess” What does this mean?\n\n    b. “Random perturbations in zeroth-order optimization (ZO) serve as high-variance estimates of the actual gradient, enabling optimization without the need for explicit gradient computations. However, these perturbations themselves carry a privacy risk” What does this mean?\n\n    c. l_p sensitivity is never defined even though used in words in the proof of Theorem 3.1\n\n    d. “add-remove DP” in page 4 is never defined or referenced\n\n    e. “privately fine-tuning downstream tasks in the few-shot setting will be more aligned with real-world use cases.”: It is not clear what authors meant by this line and paragraph.\n\n   f. “clipping are known to degrade performance,”: Please add a reference for this claim? Can it be proved empirically?\n\n5. Although authors provide extensive results for the memory usage, paper is missing comparison overall run time and number of iterations used by various methods.\n\nThese suggest that the manuscript is not yet ready for publication.\n\nMinor comments:\n1. Table 9: do you have similar gap between ZO and SGD for non-private eps=\\infty?\n2. Table 2: Why does gap between DP-ZO and DP-SGD have opposite trends across LoRA and full finetuning?\n3. Figure 1 is confusing. Also there seems to be some violation of format spacing between caption and main text.\n5. Sec 5.1: [1] suggested similar idea of communicating only seeds and direction derivatives to save computation in federated learning\n6. Typo: “activatiosn”\n\n[1] Li, Z., Ying, B., Liu, Z., & Yang, H. (2024). Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization. arXiv preprint arXiv:2405.15861.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies differentially private (DP) zeroth order (ZO) optimization in the context of fewshot finetuning of Large Language Models (LLMs). It is noted that adding DP to ZO optimization has minimal computational overhead as one only needs to privatize the directional derivative along some randomly chosen direction. Note that DP-SGD requires privatizing the full gradient and it involves per-sample gradient clipping. Although the paper is claiming to have identified this idea, it is already known (see weakness). Inspired by this method authors propose an algorithm, DP-ZO, and attempts (see weakness) to provide privacy and convergence rate analysis for it. Rest (most) of the paper provides extensive experimental evidence to argue that DP-ZO has several advantages over the standard DP-SGD, including (1) comparable performance in fewshot finetuning, (2) considerably smaller memory consumption, and (3) practicality of exact epsilon-DP through DP-ZO which is impractical to achieve through DP-SGD due to additional dimension factors (see weakness). Although a few of these results are already known in some settings, I consider the comprehensive empirical results as useful and major contribution of this paper.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address my concerns in weaknesses and minor comments.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "O3ckR3aJzl", "reviewer": "Reviewer_he8N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. Integrating DP with ZO looks promising, as only a scalar needs to be privatized, which enjoys better scalability than DP-SGD on large models.\n2. This work includes an extensive empirical study on language tasks. Evaluating privacy protection via MIA is also useful in practice.\n\n\n## Weakness\n1. I feel the background part about zero-th order optimization is not adequate. Readers like me who do not have knowledge in ZO may find it confusing. It seems that this algorithm still uses gradient descent, but it does not explicitly calculate the gradient, instead, the gradient is estimated by a scaled difference between function values and a random direction. For example, in Figure 1, in each iteration $\\theta$  moves along one of the two random directions. If z is random, I am not clear how it is guaranteed to move towards the optimal solution.\n3. I personally think the discussion of clipping threshold is important and should be included in the main body. But this is a minor point and is up to your consideration.\n4. Theorem 3.1 is meaningless. I guess what you are trying to say here is that Alg 1 satisfies DP guarantee, but $\\epsilon$ is not just a symbolic name, instead, it is a function of many training parameters and $\\delta$. I know it might be hard to write down the explicit calculation. One alternative way is to analyze the DP guarantee of just one iteration. \n6. In Table 1, DP-ZO has incremental improvements against DP-SGD, except on SST2 when $\\epsilon=0.5$. The performance of DP-SGD drops a lot when $\\epsilon=0.5$, but this doesn't happen on SQuAD. Can you double check this result? If nothing is wrong, can you please explain why?\n7. Figure captions need to be more self-contained. For example, for Fig 2, 3, 4, the task is not even specified, readers will have no idea what the accuracy/F1 is for.\n8. Found one typo (not sure if there is more): caption of Table 6\n\n## Questions\n1. it also looks to me that both $\\phi$ and $\\eta$ need to be very small numbers to make it work properly (is this true?) If so, does it mean that you will need more training iterations compared to DP-SGD? This might be a concern because training iterations will affect the total privacy accumulation.\n5. How do you calculate the total $\\epsilon$? If you are using existing libraries for DP-SGD, you need to make sure in each iteration the calculation of $\\epsilon $is consistent with DP-SGD, because the rest part, e.g. subsampling and composition should be the same as DP-SGD.\n3. Page 3, \"...Intuitively, this scalar tells us how much better one random step is than the other...\" Can you please elaborate more?\n4. Page 4, \"...Unfortunately, due to limitations of accounting methods, we currently cannot calculate...\" What is the limitation?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "While DP-SGD is the current dominant algorithm for private training and fine-tuning, it suffers from notable training time and memory overhead. This paper proposes an alternative to DP-SGD by utilizing zero-th order optimation, namely, DP-ZO. Since in ZO the gradient is estimated by the difference between two loss values, which is a scalar, it does not suffer from the curse of dimensionality thus is supposed to scale well on large models and datasets. The authors conducted extensive experiments on language tasks to demonstrate the effectiveness of DP-ZO.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "To me there are two necessary changes: (1) Theorem 3.1 (2) Expanding introduction on zero-th order optimization. Probably also need to discuss more on the comparison with DP-SGD. The benefit of DP-ZO is that you only need to add noise to a scalar, which may help improve the model utility, but the downside is you are using a less accurate gradient (an estimate) to optimize, so there is a trade-off. It is not very straightforward to me which one is clearly better than the other, which I guess depends on the application scenario.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vKZbT2xQmd", "reviewer": "Reviewer_3HQN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper proposes a practical method for an important problem in private machine learning. It will definitely interest TMLR's audience. As with non-private zeroth order optimization, this approach presents an interesting set of tradeoffs. The empirical evaluation of utility is sufficient to convince me that the approach might be the best choice for real tasks. \n\nThere are a few serious issues with the formal statements. \n1) Theorem 3.1 is not well-formed, since Algorithm 1 does not reference the parameters $\\epsilon$ and $\\delta$. Indeed, Algorithm 1 is not even fully specified, since it requires a \"noise mechanism\" as input. The privacy analyses in the appendix are completely standard, but this theorem is false.\n2) Proposition 3.2 is not well-formed. As with the previous point, Algorithm 1 does not depend on any parameters $\\epsilon$. Furthermore, what is the \"effective rank\"? What do you mean by convergence rate? How could such a convergence rate not depend on $\\delta$? And, most importantly: where is the proof? Does this claim come from Zhang et al. 2024a? If so, the paper should be extremely explicit about this. Furthermore, if so the claim appears to be false because Zhang et al. 2024a analyze a different form of random perturbation.\n3) Finally, a common error: Prop 2.2 is false as the conclusion does not hold for all $\\epsilon \\ge 0$. See [1].\n\nIf Proposition 3.2 comes from Zhang et al. 2024a, then I am deeply confused. This means the submission calls the work concurrent but uses their theoretical results? I seem to be missing something. I am also a little surprised to see Zhang et al. 2024a cited for the first time only on page 5: if their algorithm is indeed functionally the same, then it seems anyone interested in your paper would also be interested in theirs. \n\nI did not fully understand the datasets used and experimental evaluation. What are these tasks? How do we measure accuracy? And, pardon my ignorance, how do we apply F1 scores for a generation task?  \n\nAt times, I suspect the text would be difficult for an inexperienced researcher to follow. Particular examples include the introduction's Figure 1 and discussion of the algorithm and the discussion after Definition 2.4. (the definition says that $z$ is the \"random perturbation.\" But then in this paragraph you say that \"Random perturbations in zeroth-order optimization (ZO) serve as high-variance estimates of the actual gradient\", which doesn't make sense since $z$ is drawn from a Gaussian. The same issue later: \"... these perturbations themselves carry a privacy risk.\" What does that mean?)\n\nThere are a number of places where I feel the writing could be slightly improved. Examples include:\n1) I feel the framing of the work as a \"new methodology\" and a \"framework\" is not quite accurate, since the algorithms seem like straightforward ways to privatize existing approaches. \n2) In Section 3 paragraph \"DP-ZO\" we have a lot of words in italics that don't make sense to me, aside from \"Poisson sampling,\" but even that doesn't need to be italicized. \n3) The paper says that current accountants can't deal with small values of $\\delta$ for subsampled Gaussian mechanism. Is this well-known? Is there a citation?\n4) In Definition 2.4: what is b, what is $\\phi$?\n5) \"Ablation\" refers to the removal of something, so uses like \"Ablation of DP-ZO (Gaussian) for different $n$ training samples\" are not correct. \n\n[1] Balle, Borja, and Yu-Xiang Wang. \"Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.\" International Conference on Machine Learning. PMLR, 2018.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies differentially private zeroth order optimization and its application to the task of fine-tuning a pretrained LLM on a small dataset. From the current iterate $\\theta$, the algorithm picks a random vector $z$ evaluates the loss on a minibatch at $\\theta + \\phi z$ and $\\theta - \\phi z$. It uses this as an estimate of the gradient at that point. This is a classic optimization procedure. Each point contributes a single scalar value to the estimate, so the paper privatizes the procedure by clipping and adding Gaussian or Laplace noise.\n\nCompared to standard gradient methods, this estimator is simple and has lower memory overhead, as there is no backprop. Under privacy, it avoids the cost and complexity of per-gradient clipping that come with DP-SGD. Although the zeroth order estimator has high variance (that may grow with the dimension), the privacy noise under DP-SGD also grows with the dimension. So the univariate noise for privacy considered here seems very promising.\n\nThe paper evaluates the method on three NLP datasets and a variety of model sizes. Broadly, it seems to perform about as well as DP-SGD or slightly better.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following changes will be critical to securing my recommendation:\n1) All mathematical claims should be well-formed and true. Each should be accompanied by a proof or explicit reference to existing results.\n2) The relationship between the submission and Zhang et al. 2024a (regarding the algorithm, publication timeline, and theoretical analysis) needs to be absolutely clear to the reader.\n3) The discussion of datasets and evaluation metrics needs to provide more detail, such that a researcher from outside NLP can understand the results.\n\nIn addition, I suggest improving the presentation throughout. I feel small changes would result in a much better paper.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have taken into account reviewers' comments during the review process and as a result the paper has improved. I think it is almost ready to be accepted as is, however, I think still a minor revision is required to address some remaining reviewers' comments.

Please still carefully go over the statement of Theorem 3.1, the "proof outline" and the related material in the appendix (also requested by reviewer 7MQH). I think that in Proposition A.7, the dominating pair of distributions you state is the dominating pair only in the "add" case. Rigorously speaking, you should consider both add and remove cases, see Theorem 11 by [Zhu et al., 2022](https://proceedings.mlr.press/v151/zhu22c/zhu22c.pdf). I believe the $\varepsilon$-values you report are correct: as far as I know PRV accountant implements only one of the cases, however it seems to always give the upper bound though it hasn't been rigorously shown that it gives the upper bounds for add/remove (see conjecture in [Lebeda et al., 20249(https://arxiv.org/pdf/2405.20769)). So, given the experimental nature of this paper, I think its ok to rely on the $\varepsilon$-values given by the PRV accountant and simply fix the theoretical part (e.g., mention both cases, and that you need to take the maximum of the two resulting $\delta$-values). Also, you could add to the discussion of Appendix A that the privacy loss random variables add up in case of compositions.

Also, I would request to still carefully go through the writing. Please go carefully through examples in reviewers comments. Few examples of strang sentences I found:
- "still causes OOM error for sequence length equals to 2048"
- "In fact, DP-ZO incurs nearly no additional memory cost than ZO"
- "DP-ZO ss flexible enough to be extended..."

In Definition 2.1 you write $D,D' \in \mathcal{D}^n$ however you use add/remove neighbourhood relation. Perhaps consider changing the notation or further clarifying the explanation "...if they differ in exactly one record by adding or removing one record".

Other remarks:

- you mention "Unfortunately, due to limitations of accounting methods, there are challenges for calculating the tight privacy of composition of sub-sampled Gaussian mechanism for values of $\delta$ smaller than $10^{-10}$ (Wang et al., 2023)." Notice that there are method for particularly addressing small $\delta$-values, see e.g. [Alghamdi et al., 2022](https://arxiv.org/pdf/2208.09595).

- You are using randomized privacy accounting for $(\varepsilon,\delta)$-DP analysis of the Laplace mechanism. Notice that you could also use FFT-based accounting. For example, the PLD for one of the cases (add / remove) is given in Appendix A.3 of [Sommer et al., 2020](https://eprint.iacr.org/2018/820.pdf).
Decision: Accept (poster)