When Does Differentially Private Learning Not Suffer in High Dimensions?
Authors: Xuechen Li
Daogao Liu
Tatsunori Hashimoto
Huseyin A Inan
Janardhan Kulkarni
YinTat Lee
Abhradeep Guha Thakurta
Venue: NeurIPS 2022 Accept (2022)
Keywords: Differential Privacy
fine-tuning
DP convex optimization
pretrained models

Abstract: Large pretrained models can be fine-tuned with differential privacy to achieve performance approaching that of non-private models. A common theme in these results is the surprising observation that high-dimensional models can achieve favorable privacy-utility trade-offs. This seemingly contradicts known results on the model-size dependence of differentially private convex learning and raises the following research question: When does the performance of differentially private learning not degrade with increasing model size? We identify that the magnitudes of gradients projected onto subspaces is a key factor that determines performance. To precisely characterize this for private convex learning, we introduce a condition on the objective that we term restricted Lipschitz continuity and derive improved bounds for the excess empirical and population risks that are dimension- independent under additional conditions. We empirically show that in private fine-tuning of large language models, gradients obtained during fine-tuning are mostly controlled by a few principal components. This behavior is similar to conditions under which we obtain dimension-independent bounds in convex settings. Our theoretical and empirical results together provide a possible explanation for the recent success of large-scale private fine-tuning. Code to reproduce our results can be found at https://github.com/lxuechen/private-transformers/tree/main/examples/classification/spectral_analysis. 

When Does Differentially Private Learning Not Suffer in High Dimensions?
Xuechen Li*
Daogao Liu" University of Washington dgliuOuw.edi
Stanford University lxuechen@cs. stanford.
Tatsunori Hashimoto
Huseyin A. Inan
Janardhan Kulkarni
Stanford University thashim@stanford edu
Microsoft Research
Microsoft Research jakul @mi comoortoot.. com
huseyin. www.nmicoooooeeeieo.ooiooooooooe com
Yin Tat Lee
Abhradeep Guha Thakurta
University of Washington
Google Research athakurta@googlee com
Microsoft Research yintat@uw. edu
Abstract
Large pretrained models can be fine-tuned with differential privacy to achieve performance approaching that of non-private models. A common theme in these results is the surprising observation that sigh-dimensional models can achieve favorable privacy-utility trade-offs. This seemingly contradicts known results the model-size dependence of differentially private convex learning and raises the following research question: When does the performance of differentially private learning not degrade with increasing model size? We identify that the magnitudes of gradients projected onto subspaces is key factor that determines performance. To precisely characterize this for private convex learning, we introduce con- dition the objective that term restricted Lipschitz continuity and derive improved bounds for the excess empirical and population risks that are dimension- independent under additional conditions. We empirically show that private fine-tuning of large language models, gradients obtained during fine-tuning are mostly controlled by few principal components. This behavior similar con- ditions under which we obtain -anpniiionn-deeeeeeenn bounds in convex settings. Our theoretical and empirical results together provide a possible explanation for the recent success of large-scale private fine-tuning, Code to reproduce results can be found at http:s///github..cmm/xxeeeeeee http:////aaaaaaeeaaaaaaaatttttte analyssss....
wwt.://ec///eecee/eeeeeeeeeeeeee http:/priiiieeeeeeeeeeeeeeeaeeee trans
Introduction
Recent works have shown that large publicly pretrained models can be differentially privately fine- tuned small downstream datasets with performance approaching those attained by non non-private models. In particular, past works showed that pretrained BERT [DCLT18] and GPT-2 IRNSS18. 18, RWC+ 19] models can be fine-tuned to perform well for text classification and generation under a privacy budget of e E [2, 6) [LTLH21, YNB+21]. More recently, it was shown that pretrained
"Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ResNets [HZRS16] and vision- Transformers [DBK't 20] can be fine-tuned to perform well for ImageNet classification under single digit privacy budgets [DBH* 22, MTKC22).
One key ingredient in these successes has been the use of large pretrained models with millions to billions of parameters. These works generally highlighted the importance of two phenomena: (i) large pretrained models tend to experience good privacy-utility trade-off's when fine-tuned, and (ii) the trade-off improves with the improvement of the quality of the pretrained model (correlated with increase in size). While the power of scale and pretraining have been demonstrated numerous times in non-private deep learning [KMH+ 20], one common wisdom in private learning had been that large models tend to perform worse. This intuition was based on (a) results in differentially private convex optimization, most of which predicted that errors would scale proportionally with the dimension of the learning problem in the worst case, and (b) empirical observations that the noise injected to ensure privacy tends to greatly exceed the gradient in magnitude for large models [YZCI,2la, Kam20J.
For instance, consider the problem of differentially private convex empirical risk minimization (ERM). Here, we are given dataset examples D {s,}ā=1 E S", convex set K. C E2d (not necessarily bounded), and the goal is to perform the optimization
n (1)ss) minimize,ex D) = n j=1
subject to differential privacy, where f(; 8) convex over K. for all s S. For bounded K., past works presented matching upper and lower bounds that are dimension-dependent under the usual Lipschitz assumption on the objective [BST14, CMS11J. These results seem suggest that the performance of differentially private ERM algorithms inevitably degrades with increasing problem size in the worst case, and present seeming discrepancy between recent empirical results on large-scale fine-tuning."
To better understand the relation between problem size and the performance of differentially private learning, we study the following question both theoretically and empirically:
When does the performance of differentially private stochastic gradient descent (DP-SGD) not degrade with increasing problem dimension?
On the theoretical front, we show that DP-SGD can result in dimension dimension-inddeeenden error bounds even when gradients span the entire ambient space for unconstrained optimization problems. We identify that the standard dependence on the dimension of the ambient space can be replaced by the magnitudes of gradients projected onto subspaces of varying dimensions. We formalize this in condition that we call restricted Lipschitz continuity and derive refined bounds for the excess empirical and population risks for DP-SGD when loss functions obey this condition. We show that when the restricted L Lipschitz coefficients decay rapidly, both the excess empirical and population risks become commensioo-iddeeedden. This extends a previous work which derived rank-dependent bounds for learning generalized linear models an unconstrained space [SSTT21].
Our theoretical results shed light on the recent success of large-scale differentially private fine-tuning. We empirically show that gradients of language models during fine-tuning are mostly controlled by a few principal components - a behavior that is similar to conditions under which we obtain cameeniion-nndpendden bounds for private convex ERM. This provides possible explanation for the observation that densely fine-tuning with DP-SGD need not necessarily experience much worse performance than sparsely fine-tuning [LTLH21]. Moreover, it suggests that DP-SGD can be adaptive to problems that are effectively low-dimensional (as characterized by restricted Lipschitz. continuity) without further algorithmic intervention.
We summarize our contributions below.
(1) We introduce condition the objective function that term restricted I. Lipschitz continuity. This condition generalizes the usual Lipschitz continuity notion and gives rise to refined analyses when magnitudes of gradients projected onto diminishing subspaces decay rapidly.
(2) Under restricted Lipschitz continuity, we present refined bounds on the excess empirical and population risks for DP-SGD when optimizing convex objectives. These bounds generalize
"We judiciously choose to describe the discrepancy seeming, since the refined analysis presented in the current work suggests that the discrepancy is likely non-existent.

---

previous dimension dimension-independeer independent results [SSTT21] and are broadly applicable to cases where gradients are full rank but most coordinates only marginally influence the objective.
(3) Our theory sheds light on recent successes of large-scale differentially private fine-tuning of language models. We show that gradients obtained through fine-tuning mostly lie in subspace spanned by a few principal components -a a behavior similar to when optimizing restricted Lipschitz continuous loss with decaying coefficients. These empirical results provide possible explanation for the recent success of large-scale private fine-tuning.
2
Preliminaries
We define the notation used throughout this work and state the problems of differentially private empirical risk minimization and differentially private stochastic convex optimization. Finally, give a brief recap of differentially private stochastic gradient descent, and existing dimension-dependen and dimension-inndeeeddenl results in the literature.
Notation & Terminology. For positive integer n E N+, define the shorthand [xx] = ........... For a vector E TRdd denote its no-m by ||æ||]- Given symmetric M E Rdxdd let Y (M) 2 (MM 2 ... 2 (M) denote its eigenvalues. Given positive semidefinite matrix A, let ||a:]|a (x Ar) denote the induced Mahalanobis norm. For scalar functions f and we write S if there exists a positive constant C' such that (xx S Cg(z) for all input æ in the domain.
2.1 Differentially Private Empirical Risk Minimization and Stochastic Convex Optimization
Before stating the theoretical problem of interest, we recall the basic concepts of Lipschitz continuity, convexity, and approximate differential privacy.
Definition 2.1 (Lipschitz Continuity). The loss function h KC + R is G-Lipschitz with respect to the l2 norm for all x, x' E XC, (f() - f(x') S Gllæ 2'|12.
Definition 2.2 (Convexity). The loss function h K + R is convex if h(ar + (1 a)y) s
ah(x) + (1 ay), for all a E [0, 1), and æ, in a convex domain JC.
Definition 2.3 (Approximate Differential Privacy [DR* + 14]). A randomized algorithm M is (c, 6)- differentially private if for all neighboring datasets D and D' that differ by single record and all sets O C ran, the following expression holds
Pr(M(D) O) S exp(E) Pr[M(D') E +
In this work, we study both differentially private empirical risk minimization (DP-ERM) for convex objectives and differentially private stochastic convex optimization (DP-SCO).
In DP-ERM for convex objectives, we are given a dataset = {sy]se(w) E S of examples. Each per-example loss f(; ) is convex over the convex body K. C Rd and G-Lipschitz. We aim to design an (s, DD algorithm that returns a solution zrivv which approximately minimizes the empirical risk F(x; D) == E.JeDD f(;; s,). The term Eggm [F D) minzex F(x; D) is referred to as the excess empirical risk.
In DP-SCO, we assume the per-example loss f(=s) is convex and G-Lipschitz for all s S, and we are given n examples drawn i.i.d. from some (unknown) distribution P. The goal is to design an (s, 0DD algorithm which approximately minimizes the population risk F(æ; P) := Es- [f (x; s)].
The term Ege
[x P) - minzex Fz; P)] is referred to as the excess population risk.
2.2 Differentially Private Stochastic Gradient Descent
Differentially Private Stochastic Gradient Descent (DP-SGD) [ACG+ 16, SCS13) is a popular algo- rithm for DP convex optimization. For the theoretical analysis, we study DP-SGD for unconstrained optimization. To facilitate analysis, we work with the &a regularized objective expressed as
1 n
Fa (z; D)
Σ
f(x; 85)
a | x 101
n 1=1
2
3

---

To optimize this objective, DP-SGD independently samples an example in each iteration and updates the solution by combining the gradient with an isotropic Gaussian whose scale proportional G, the Lipschitz constant of f. Algorithm 1 presents the pseudocode.
Algorithm 1: DP-SGD for optimizing regularized finite-sum objectives
Input: Initial iterate 07(0), dataset D {8y) Je() per-step noise magnitude a, number of updates T. learning rate 17. Lipschitz constant G of f.
for / ...., do
jt ~ Uniform([zz) [rz])
(()) (((-1)
V (f(x((11); + a((x(t11)) =z!0)) + GG- Se (e~N(0,021a)
5 &end
Return: F def 1 I
7 ΣT= 1(0)
It is straightforward to show that Algorithm I satisfies differential privacy. The following lemma quantifies the overall privacy spending and builds on long line of work on accounting the privacy loss of compositions [ACG+ 16, BBGI8J.
Lemma 2.4 ([KLL21). There exists constants e and c2 such that 2 10. e/T/n? and 02 e2 Tlog 1/5)
E (0, 3. DP-SGD (Algorithm 1) is (s, 6D whenever a 2
2.3 On the Dimension Dependence of Private Learning
Early works on bounding the excess empirical and population risks for privately optimizing convex objectives focused on constrained optimization setup where algorithms typically project iterates back onto fixed bounded domain after each noisy gradient update. Results in this setting suggested that risks are inevitably dimension-depennt
in the worst case. For instance, it was shown that the excess empirical risk bound ( [K]ll, v log (1/8)n-1g-l) -1= and excess population risk bound @ [|l]2 (n-1/2 + /1log(1/5)n__--- objectives convex domain of diameter [|/]]], [BST14). Moreover, the lower bound instances in these works imply that such dimension-dependene lower bounds also apply when one considers the class of loss functions whose gradients are low-rank.
are tight when privately optimizing convex G-Lipschitz
The body of work on unconstrained convex optimization is arguably less abundant, with the notable result that differentially private gradient descent need not suffer from dimension-dependee penalty when learning generalized linear models with low-rank data (equivalently stated, when gradients are low-rank) [SSTT21]. Our main theoretical results (Theorems 3.3 and 3.5) extend this line of work and show that comeenion-innependeene is achievable under weaker conditions.
Refined Dimension-Deppeneene via Restricted Lipschitz Continuity
In this section, we formally introduce the restricted Lipschitz continuity condition and derive improved bounds for the excess empirical and population risks for DP-SGD when optimizing convex objectives. Definition 3.1 (Restricted Lipschitz Continuity). We say that the loss function h : K. + R is restricted Lipschitz continuous with coefficients Go...., if for all k [d]. there exists an orthogonal projection matrix P% with rank & such that
[| Pt) S Gg. for all x E K and all subgradients Vh(rr) @h(xr).
Note that any G-Lipschitz function is also trivially restricted Lipschitz continuous with coefficients Ga, since orthogonal projections never increase the mn-m of a vector (generally, it is easy to that G Go 2 G1 2 G2 2 G. 0). On the other hand, expect that a function which exhibits little growth in subspaces of dimension & to have a restricted Lipschitz coefficient Ga-s of almost O.
G= Go = G1 =
Our bounds on DP convex optimization will characterize errors through the use of restricted Lipschitz coefficients. We now summarize the main assumptions before presenting the core theoretical results.

---

Assumption 3.2. The per-example loss function s) is convex and G-Lipschitz continuous for all 8 E S. The average loss ((:;") D) is restricted Lipschitz continuous with coefficients {G+)
3.1 Bounds for Excess Empirical Loss
We present the main theoretical result on DP-ERM for convex objectives. The result consists two pieces: Equation (1) is general bound that is applicable to any sequence of restricted Lipschitz coefficients; Equation (2) specializes the previous bound when the sequence of coefficients decays rapidly and demonstrates dimension-inndeeedden error scaling.
Theorem 3.3 (Excess Empirical Loss). Let å (0, z.- and (0, 10). Under Assumption for
any positive integer k E [d], setting T ((n² + d d), θ
/Tooil//8
D
RE
11
ko
and a 2V Ex 2220 20 where S = [logd//}]] + 1, DP-SGD (Algorithm 1) is (5, 0)-P) and
GoDv (1/0 + D
E F(z; min F(z; D)
22nnG 1k
(I)
en
where [zx10) argming F(;; D)ll2 S D. D. is the (random) output of DP-SGD (Algorithm 1), and the expectation is over the randomness of x. Moreover, for some > 1/2, we have G2 S Gok for all k [d], and in addition n 2 --1 Vlo((1/5) minimizing the right hand side of (1) with respect
to yields
(Vlog(1/8) (
20/(1+26)
F(;:D) - min min F(; $ GoD.
(2)
En
We include sketch of the proof techniques in Section 3.3 and defer the full proof to Appendix A. Remark 3.4. Consider DP-ERM for learning generalized linear models with convex and Lips- chitz. losses. When the (empirical) data covariance is of rank
d. the span of gradients span (()))) is also of rank r. Thus, the average loss is restricted Lipschitz continuous with coefficients where Gp-- for all r' > r. Setting k (I) yields the excess empirical risk bound of order O Gr log(1 1//j0=-n"" This recovers the previous dimension-indeeeeddett result [SSTT21].
The restricted Lipschitz continuity condition can be viewed as generalized notion of rank. The result captured in (2) suggests that the empirical loss achieved by DP-SGD does not depend on the problem dimension the sequence of restricted Lipschitz coefficients decays rapidly. We leverage these insights to build intuition for understanding private fine-tuning of language model in Section 4.
3.2 Bounds for Excess Population Loss
For DP-SCO, make use of the stability of DP-SGD to bound its generalization error [BE02], following previous works [BFTT19, BFGT20, SSTT21]. The bound on the excess population loss follows from combining the bounds on the excess empirical risk and the generalization error.
}. and (0, 10). Under Assumption 3.2, for any positive integer k E [d]. by setting T = On + dlog² d). e TTgg(118)
Theorem 3.5 (Excess Population Loss). Let 8 E (0,
D = T-CTT/attko) and a = PVES S2 where = [log(d/k)] + 1, DP-SGD (Algorithm 1) is (E, DP. and
GoD Vn
GoD log((11
E F(x; min F(x:P))
+
222 G2 24-1k
EN
5

---

where ||x argmin, F(z; P)12 S D, F is the (random) outpur of DP-SGD (Algorithm 1), and the expectation is over the randomness of
Moreover, for some e. > 1/2, we have Gk S Gok for all k. E [d]. and in addition n > e-1 (log(1/)), minimizing the above bound with respect to k yields
20/(1+20)
GoD Vn
[Vlog(100)
E min
min F(;;
2
+ GoD.
EN
Remark 3.6. Our result on DP-SCO also recovers the DP-SCO rank sank-dependent result for learning generalized linear models with convex and Lipschitz losses [SSTT21].
Remark 3.7. When > 1/2, (1) and ē = 1/poly(n). the population loss matches the (non-private) informatiional-thorrtiiio lower bound ( Vn) [AWBR09].
Remark 3.8. Our results on DP-ERM and DP-SCO naturally generalize to (full-batch) DP-GD,
3.3 Overview of Proof Techniques
The privacy guarantees in Theorems 3.3 and 3.5 follow from Lemma 2.4. suffices to prove the utility guarantees. We give an outline of the main proof technique and defer full proofs to the supplementary. The following is a sketch of the core technique for deriving (2) in Theorem 3.3.
By convexity, the error term of SGD is upper bounded as follows
(-(()) fz (f)(x(()) T
where j E [n] is the random index sampled at iteration t. By definition of Gk. we know that there is k dimensional subspace U such that the gradient component orthogonal to U is small when G3 is small. Naïvely, decomposes the gradient (x)()(()) 91 + 92. where 91 E U and 92 U and separately bounds the terms 91 (a:(*) x²) and 92
(zx(1) x²). Since Ii lies in k dimensional subspace, can follow existing arguments DP-SGD to bound 9, (ax(t) -xr). Unfortunately, this argument does not lead to dimension- piieension-indeeedddnnee Although |192 l2 I G5 (which can be small
for large k), the term [|x(()) x=" lle can be as large as I( with high probability due to the isotropic
Gaussian noise injected in DP-SGD. Therefore, the naive upper bound on [g] (Ix(t) - x) can be as large O( O(v)).).
Our key idea is to partition the whole space Rd into [log(d/k) + 2 orthogonal subspaces, expressing - x²) as the sum of individual terms each of which corresponds to particular subspace. Fix the positive integer & I d, and consider the following subspaces: Let Uo = range(Ps) U, be the subspace orthogonal to all previous subspaces such that Di_ U, 2 sunge(P2-a. for 1,2, (lo(d/k)]] and Us be the subspace such that the orthogonal direct sum of all subspaces {U.) Rd where S [log(d/k)) + Here, P; is the orthogonal projection matrix with rank é promised by G; in Assumption 3.2. Let Q2 be the orthogonal projection the subspace U.. Observe that rank(Q.) < 2 and [Q))F( I G2e-14 k for all x and all s 2 1. Rewriting the right hand side of (3) with this decomposition yields
the error term V F (z(())) (x)
projection
-
(OVI)((()) Σ )
(x -x)))-)) x*).
On the hand, if G decays rapidly, |[E QQ. V fylllz will be small for large On the other hand, expect (z =l)ll2 be small for small where Qs is orthogonal projection onto small subspace. Thus, for each 8, (T, (small Vf, in expectation over the random index) or small noise (small Q, (z(1) x )), since noise injected in DPDSGD is isotropic. More formally, in Lemma I. we show that for any projection matrix Q with rank r, (x(())()) o(10) can be upper bounded by a term that depends only on (rather than d).
x²) is small either due small gradient
4 Numerical Experiments
The aim of this section is twofold. In Section 4.1, we study synthetic example that matches our theoretical assumptions and show that DP-SGD attains dimenssoon-indeeendeer empirical and

---

population loss when the sequence of restricted Lipschitz coefficients decays rapidly- even when gradients span the entire ambient space. In Section 4.2, we study stylized example of privately fine-tuning large language models. Building on the previous theory, we provide insights as to why dense fine-tuning can yield good performance.
4.1 Synthetic Example: Estimating the Generalized Geometric Median
We privately estimate the geometric median which minimizes the average Mahalanobis distance. Specifically, let x E Rd for i [x]] be feature vectors drawn i.i.d. from some distribution Pa each of which is treated as an individual record. Denote the entire dataset as D = {ar)-=-- Subject to differential privacy, we perform the following optimization
min (a( = EEE sER4
+ f(xx)
a 2
(0)
r lilla
+
a
x (0))
1
2
where we adopt the shorthand f((z) = f f(; 2;) = | z
Il When A= ba and a (without the regularization term), the problem reduces to estimating the usual geometrie median (commonly known as center mass).
For this example, individual gradients are bounded since Vi) = ||A(( - x.)//l> z3llااla - A (A4/2) = Go. More generally, the restricted Lipschitz coefficients of F(x) are the eigenvalues of A/22, since
a (QvVF())l2 QuAIR?
1 xz) n 1 xz ll
- 1|Q A Gkz
where Qx - P& chosen to be the rank (d k) orthogonal projection matrix that projects onto the subspace spanned by the bottom (d- k) eigenvectors of 1/1/2
To verify our theory, we study the optimization and generalization performance of DP-SGD for minimizing (4) under Mahalanobis distances induced by different A as the problem dimension grows. The optimization performance is measured by the final training error, and the generalization performance is measured by the population quantity P..=P..=lle -x AA], where denotes the random output of DP-SGD. We study the dimension scaling behavior for A being one of
Aconst diag( .1....,,) 1), Asqu diag(1
1/Va), Annerr = diag 1, 1/. 1/d),
where diag: dR gdxd maps vectors onto square matrices with inputs the diagonal. In all cases, the span of gradients span((VF(x))) is the ambient space Rd, since is of full rank. To ensure the distance from the initial iterate ((0) = to the optimum the same for problem instances of different dimensions, we let feature vectors {z, }/= take zero values in any dimension k > dmin- where dmin is the dimension of the smallest problem in our experiments. Our theoretical bounds suggest that when the sequence of restricted Lipschitz coefficients is constant (when A Aconst). the excess empirical loss grows with the problem dimension, whereas when the sequence of kth-Lipschitz constants rapidly decays with A: (when A Asgn A Atimar),, the excess empirical loss does not grow beyond a certain problem dimension. Figure empirically captures this phenomenon. We include additional experimental setup details in Appendix C.
4.2
Why Does Dense Fine- Fine-Tuning Work Well for Pretrained Language Models?
Stated informally, our bounds in Theorem 3.5 imply that DP-SGD obtains Aimension-indepenen errors if gradients approximately reside in subspace much smaller than the ambient space. Inspired by these results for the convex case, we now turn to study dense language model fine-tuning [LTLH21] and provide possible explanation for their recent intriguing success fine-tuning gigantic parameter vectors frequently results in moderate performance drops compared to non-priver non-private learning.
In the following, we present evidence that gradients obtained through fine-tuning mostly lie in a small subspace. We design subsequent experiments to work under simplified setup. Specifically, we fine- tune DistilRoBERTa [SDCW19, LOG 19] under = 8 and 5 = ..1 for sentiment classification on the SST-2 dataset [SPW+13] 13]. We reformulate the label prediction problem as templated text prediction [LTLH21], and fine-tune only the query and value matrices in attention layers.
7

---

120
120
const
100
100
train loss
test loss
20
20
d
(a) empirical loss
(b) (estimated) population loss
The empirical and population losses grow with increasing problem dimension when the sequence of restricted Lipschitz coefficients remain constant. On the other hand, these losses remain almost constant when the sequence of restricted Lipschitz coefficients decays rapidly. Error bars represent one standard deviation over five runs of DP-SGD with the same hyperparameters which were tuned on separate validation data. For the same A, the optimal training error mingeR* F(x) is the same for problem instances with different dimensions (thus errors do not scale if learning was non-private). Each training run was performed with 2, 10-6, and n 10000.
Figure 1:
We focus on fine-tuning these specific parameter matrices due to the success of LoRA for non-private learning [HSW+21] which focuses on adapting the attention layers. Unlike LoRA, we fine-tune all parameters in these matrices rather than focusing on low-rank updates. This gives a setup that is lightweight enough to spectral analyses computationally tractably but retains enough parameters (< million) such that a problem of similar scale outside of fine-tuning results in substantial losses in utility. 2 For setup, DP-SGD obtains dey set accuracy approximately of 90% and 92%, privately and non-privately, respectively. These numbers are similar to previous results obtained with the same pretrained model (YNB- 21, LTLH21). We include the full experimental protocol and additional results in Appendix D.
To provide evidence for the small subspace hypothesis, sample gradients during fine-tuning and study their principal components. Specifically, we "over-train' by privately fine-tuning for 2 10a updates and collect all the non-privatized average clipped gradients along the optimization trajectory. While fine-tunigg for 200 and 2k updates have similar final dev set performance under our hyperparameters, the increased number of steps allows us to collect more gradients around the converged solution. This yields a gradient matrix H E TR"x,, where p R 7 x 10 is the size of the parameter vector. We perform PCA for H with the orthogonal iteration algorithm [Dem97] and visualize the set of estimated singular values o, (H) Xx(II' H) in terms of both (i) the density estimate, and (ii) their relation with the rank. Figure 2 (a) shows the top 1000 singular values sorted and plotted against their rank i and the least squares fit on log- transforrmred inputs and outputs. The plot displays few large singular values which suggests that gradients are controlled through only few principal directions. The linear fit suggests that singular values decay rapidly (at a rate of approximately -0.6).
To study the effects that different principal components have on fine-tuning performance, we further perform the following re-training experiment. Given the principal components, we privately re-fine- tune with gradients projected onto the top A E {10, 20, 100} components. Note that this projection applies only to the (non-privation privaaizit average clipped gradients and the isotropic DP noise is still applied all dimensions. Figure (b) shows that the original performance can be attained by optimizing within a subspace of only dimension = 100, suggesting that most of the dimensions of the 7 million parameter vector encode limited learning signal.
While these empirical results present encouraging insights for the commension-indpeeddeen performance of fine-tuning, we acknowledge that this is not a complete validation of the restricted L Lipschitz
For instance, an off thelshelf ResNet image classifier has 10 to 20+ million parameters. A plethora of works report large performance drops when training these models from scratch (YZCL2Ib, LWAFF21, DBH 22).
8

---

continuity condition and fast decay of coefficients (even locally near the optimum). We leave more thorough analysis with additional model classes and fine-tuning tasks future work.
SST-2 classification cassiiicaaioon accuracy (dev)
eddimnttdd values
Inwer fit: logy 61logx 0.18 (R
0.987)
0.88
A(H H2)22
0.86
10"
Subspace rark=10
0.02
subsspcce rankm20
original
10
10
10
10'
10*
50
100
150
200
250
iteration
(a) singular values decay with rank
(b) retrain in fixed subspace
Figure 2: Gradients obtained through fin-tuning are controlled by few principal components. Left: Singular values decay rapidly with their rank. Right: Retraining with gradients projected onto subspace (but noise not projected!) sufficient recover original performance.
5
Related Work
DP-ERM and DP-SCO are arguably the most well-studied areas of differential privacy [CMS1L, 1, KST12, BST14, SCS13, WYX17, FTS17, BFTT19, MRTZ17, ZZMW17, WLK+ FKT20, 19,+19, BFGT20, STT20, LL21, AFKT21, BGN21, GTU22, GLL22]. Tight dependence on the number of model parameters and the number of samples is known for both DP-ERM (BST14) and DP-SCO [BFTT19]. In particular, for the eгror general convex losses, an explicit polynomial dependence on the number of optimization variables is necessary. However, gradients lie in a fixed low-rank subspace M, the dependence on dimension d can be replaced by rank(M) which can be significantly smaller [JT14, STT20J. We extend this line of work show that under a weaker assumption (restricted Lipschitz continuity with decaying coefficients) one can obtain analogous error guarantees that are independent of d, but do not require the gradients of the loss to strictly lie in any fixed low-rank subspace M. As a consequence, our results provide a plausible explanation for the empirical observation that dense fine-tuning can be effective and that fine-tuning larger model under DP can generally be more advantageous in terms of utility than fine-tuning a smaller model [LTL221, YNB+21]. ]. concurrent work shows that the standard dimension dependence of DP-SGD can be replaced by dependence the trace of the Hessian assuming the latter quantity is uniformly bounded [MMZ22].
shown that if
A complementary line of work designed variants of DP-SGD that either explicitly or implicitly control the subspace in which gradients are allowed to reside [AGM+21, LVS+ ADF+21, KDRT21, YZCL21b). They demonstrated improved dependence of the етrоr on the dimension if the true gradients lie in "near" low-rank subspace. Our results are incomparable to this line of work because of two reasons: (i) Our algorithm is vanilla DP-SGD and does not track the gradient subspace either explicitly or implicitly, and hence does not change the optimization landscape. Our improved dependence on dimensions is an artifact of the analysis. (ii) Our analytical results do not need the existence of any public data to obtain tighter dependence on dimensions. All prior works mentioned above need the existence of public data to demonstrate any improvement.
On the empirical front, past works have observed that for image classification tasks, gradients of ConvNets converge to a small subspace spanned by the top directions of the Hessian. In addition, this span remains stable for long periods of time during training [GARD18]. While insightful, this line of work does not look at language model fine-tuning Another line of work measures for language model fine-tuning the intrinsic dimension- the minimum dimension such that optimizing a randomly sampled subspace of such dimension approximately recovers the original performance [LFLY18 88, AZG20J. We note that a small intrinsic dimension likely suggests that gradients are approximately low rank. Yet, this statement should not be interpreted as a strict implication, since the notion of

---

intrinsic dimension is at best vaguely defined (e.g.. there's no explicit failure probability threshold over the randomly sampled subspace in the original statement), and the definition involves not fixed subspace but rather randomly sampled one.
6 Conclusion
We made an attempt to reconcile two seemingly conflicting results: (i) in private convex optimization, emrors predicted to scale proportionally with the dimension of the learning problem; while (ii) in empirical works on large-scale private fine-tuning through DP-SGD, privacy-utility trade- offs become better with increasing model size. We introduced the notion of restricted Lipschitz continuity, with which we gave refined analyses of DP-SGD for DP-ERM and DP-SCO. When the magnitudes of gradients projected onto diminishing subspaces decay rapidly, our analysis showed that excess empirical and population losses of DP-SGD are independent of the model dimension. Through preliminary experiments, we gave empirical evidence that gradients of large pretrained language models obtained through fine-tuning mostly lie in the subspace spanned by a few principal components. Our theoretical and empirical results together give a possible explanation for recent successes in large-scale differentially private fine-tuning.
Given improved upper bounds the excess empirical and population risks for differentially private convex learning, it instructive to ask such bounds are tight the mini-max sense. We leave answering this inquiry future work. In addition, while have presented encouraging empirical evidence that fine-tuning gradients mostly lie in a small subspace, more work is required to study the robustness of this phenomenon with respect to the model class and fine-tuning problem. Overall, we hope that our work leads to more research on understanding conditions under which DP learning does degrade with increasing problem size, and more generally, how theory inform and explain the practical successes of differentially private deep learning.
Acknowledgements
XL. supported by Stanford Graduate Fellowship.
10

---

References
[ACG+16 16] Martin Abadi, Andy Chu, Ian 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 security, pages 308-3 318, 2016.
[ADF+21] Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pages 383-392. PMLR, 2021.
[AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in & geometry. arXiv preprint arXiv:2103.01516 2021.
[AGM+21] Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M. Suriyakumar, Om Thakkar, and Abhradeep Thakurta. Public data-assisted mirror descent for private model training. CoRR, abs/21 12.00193, 2021.
[AWBR09] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information-theore lower bounds on the oracle complexity convex optimization. Advances in Neural Information Processing Systems, 22, 2009.
[AZG20] Armen Aghajanyan, Luke Zettlemoyer, and Sonal Gupta. Intrinsic dimensionality ex- plains the effectiveness of language model fine-tuning, arXiv preprint 35x 2020.
[BBG18] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsam- pling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
[BE02] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[BFGT20] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochas- tic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381 4391, 2020.
[BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11279-11 1888 2019.
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pages 474-499, PMLR, 2021.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimiza- tion: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
[CMS11] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[DBH+22] Soham De, Leonard Berrada, Jamie Hayes, Samuel I. Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
[DBK 20] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold. Syl- vain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv: 1929, 2020.
[DCLT18] Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 04805, 2018

---

[Dem97] James W Demmel. Applied numerical linear algebra. SIAM, 1997.
[DR+ 14] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-40)) 2014.
[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439 439-449, 2020.
[FTS17] Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk minimization with input perturbation. In International Conference on Discovery Science, pages 82-90. Springer, 2017.
[GARD18] Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in tiny subspace. arXiv preprint arXiv: 18/2.04754, 2018.
[GKX19] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference Machine Learning, pages 2232-222222222222222222222- 2241. PMLR, 2019.
[GLL22] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via expo- nential mechanism. arXiv preprini arXiv:2203.mm 00260003, 2022.
[GTU22] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Langevin diffusion: almost universal algorithm for private euclidean (convex) optimization. arXiv preprint 0585 2022.
[GWG19] Diego Granziol, Xingchen Wan, and Timur Garipov. Deep curvature suite. arXiv preprint arXiv:1912.09656. 2019.
(HSW+21) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:
2021.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[INS+19] Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), 2019.
[JT14] Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differentially private learning. In International Conference Machine Learning, pages 476-484, 2014.
[Kam20] Gautam Kamath. Lecture 14 - Private ML and Stats: Modern ML. http://www. 2020.
gautamkamath. http:/aaaaaaaccccccecmcooaao comm///860nntteeee114,,
[KDRT21] Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta. (nearly) dimension independent private erm with adagrad rates
via publicly estimated subspaces. In COLT, 2021.
[KIL21] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. arXiv preprint arXiv:2103.15352 2021.
[KMH+ 20) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
[KST12] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1, 2012.
12

---

[LFLY18] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint 1r04 2018.
[LL21] Daogao Liu and Zhou Lu. Curse of dimensionality in unconstrained private convex emm. arXiv preprint arXiv:2105. 13637, 2021.
[LOG 19] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint arXiv: 190::::977.1199000 2019.
[LTLH21] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. arXiv preprint 2r 10.05679, 2021.
[LVS+21] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and Zhiwei Steven Wu. Leveraging public data for practical private query release. arXiv preprint arXiv:2102.08598, 2021.
[LWAFF21] Zelun Luo, Damiel J Wu, Ehsan Adeli, and Fei-Fee. Scalable differential privacy with sparse network finetuning. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5059-5068, 2021.
[MMZ22] Yi-An Ma, Teodor Vanislavov Marinov, and Tong Zhang. Dimension independent generalization of dp-sgd for overparameterized smooth convex optimization. arXiv preprint arXiv:2206.01835 2022.
[MRTZ17] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differen- tially private recurrent language models. arXiv preprint arXiv:/710.06963, 2017.
[MTKC22] Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Large scale transfer learning for differentially private image classification. arXiv preprint arXiv:2205.02973. 2022.
[NDR17] Jekaterina Novikova, Ondřej Dušek, and Verena Rieser. The e2e dataset: New chal- lenges for end-to-end generation. arXiv preprint UrXiv:1706.09254 2017.
[RNSS18] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018.
[RWC+19] 19] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[SCS13] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248. IEEE, 2013.
[SDCW19] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint 1rXiv:1910.000 108, 2019.
[SPW+11 13] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning. Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic composition- ality over a sentiment treebank. Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642, 2013.
[SSTT21] 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, pages 2638-2646. PMLR, 2021.
[STT20] Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gra- dient descent on convex generalized linear problems. arXiv preprint urXiv:2006.0678: 2020.
13

---

[WLK*17] 17] Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey F. Naughton. oolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD, 2017.
[WYX17] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[YNB+21] Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, al. Differentially private fine-tuning of language models. arXiv preprint arXiv:2110.06500, 2021.
[YZCL21a] Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. arXiv preprint 1rXiv:2102.12677 2021.
[YZCL21b] Da Yu, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[ZZMW17] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. In IJCAI, 2017.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work presents theory which characterizes the performance of existing algorithms. This work would not lead to any direct societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "O7gUCpAGalZ", "reviewer": "Reviewer_vt7U", "summary": "\nThe paper considers differential privacy convex optimization in high-dimensional settings. Early theoretical results on private convex optimization say that empirical and population risk depends on the model size. However, empirical observations showed that the error could be much smaller in practice. Further theoretical work showed that if the gradients of the underlying loss function lie in a fixed low-rank space, then the risk can be bounded by its rank. \n \nThis paper is motivated by the empirical observation that given a pre-trained model, then using private gradient descent to fine-tune the model has good performance independent of model size. In a sense, this empirical observation contradicts theoretical results that state that differentially private convex learning degrades with model size. \n \nThe paper provides bounds independent of the model size on the empirical and population risk of private convex optimization. This result extends from prior work [JT14, STT20] that assumes that gradients belong to a fixed low-rank space. Furthermore, other results require learning the gradients subspace to get improved results or using public data to approximate the gradient subspace. Finally, the paper analyzes DP stochastic gradient descent without modification and only requires a condition called restricted Lipschitz continuity. \n \nThe analysis follows by partitioning the solution space into different orthogonal sub-spaces and then decomposing the gradient into a sum such that each term falls into a subspace. By the restricted Lipschitz continuity condition, each gradient term can be bounded by a constant.\n", "questions": "Could more intuition be provided about the is the effect of regularization in the analysis?\n", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe paper analyzes a practical algorithm (DP-SGD) for convex optimization and provides improved risk bounds under certain conditions that are more general than prior work. In addition, the bounds provided recover bounds from prior work that requires a low gradient subspace.\nThe idea of using restricted Lipschitz continuity conditions is new to my knowledge, and the analysis that follows is novel. Furthermore, experiments validate the theoretical claims. \n\nThe paper also motivates the theory in the convex setting to justify the high performance of pre-trained models in a non-convex setting. The paper claims and provides evidence that since pre-trained models are already close to a local optimum, they could lie in a small subspace. This argument gives some optimism about the future of private training large models. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FClQd0arrpK", "reviewer": "Reviewer_tNQa", "summary": "This paper proposes an analysis that captures the behavior that DP-SGD’s utility performance does not deteriorate with the increasing dimension under a specific assumption. Such assumption generally states that if the gradient lies in a limited subspace of the ambient space, then the excess risk is then dimension-independent.\nThis paper gives some evidence for the fact that when fine-tuning a DL model, such an assumption holds. By such observation, the theoretical result explains some phenomena.\n\n", "questions": "See the limitations for details ", "limitations": "This paper assumes that it is in the convex setting, however, even in the fine-turning stage, it is not guaranteed in the convex setting as is the case for deep learning model. Hence, such result has a limited implication.\nAnother important point is that, when doing fine-tuning, it is still not guaranteed to be near the local optimal point (we still don’t how to quantify “near” either). The experiment gives positive evidence, however, I think more experiment should be done to validate the hypothesis that fine-tuning starts from a near-optimal point.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The error analysis technique is not new, and the key assumption proposed in this paper is a variant of the assumption that gradient lies in a limited subspace (which is not new either), however, from such an assumption to deriving the error bound seems like non-trivial. And such result has an implication.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7g5oIjyt09e", "reviewer": "Reviewer_VSjU", "summary": "Recent advances in natural language processing have witnessed the advantage of a large language model in private fine-tuning, which can achieve state-of-the-art performance even compared to non-private algorithms. Since the theoretical understanding of success is still lacking so far, this paper fills the gap to understand why the curse of dimension does not happen in the large-model fine-tuning. By using the novel notion of restricted Lipschitz-continuity, the authors proved a refined dimension-independent bound on the excess empirical error and excess population error by differentially-private stochastic gradient descent. Empirically, the authors show that the near-optimal models (e.g., pre-trained models) tend to produce gradients concentrated in a few principal components of the gradient subspace, which confirm the assumption of the restricted Lipschitz-continuity.", "questions": "1. The definition of the convex domain diameter D is not clearly stated. It was first used in Line 129 to state the prior bounds. In Theorem 3.3, D is defined to be the upper bound of the difference between x and x^*. It is confusing if the two D's denotes the same or related things. In the final excess error bounds, the D is used intensively both in prior arts and the paper's results. The authors may clarify the notation here.\n2. In Line 267 of the Experiment section, why the DistillRoBERTa is selected? Do the results generalize to other large models? In the [LTLH21] which is the major empirical motivation for the work, the large RoBERTa was used. Some clarification may help the readers to understand the generality of the empirical studies. Since the restricted Lipschitz continuity is the major assumption of the paper, stronger empirical evidence is essential here.\n3. How does the private fine-tuning of all attention parameters compared to more parameter-efficient fine-tuning? Since the dimension is a major concern for private learning in the scope of the paper, some advanced parameter-efficient fine-tuning should gain some advantage in the privacy-accuracy trade-off. By parameter-efficient fine-tuning, e.g., Prompt, the dimension of parameters to be privately trained could be effectively reduced. As a result, I believe that the authors may provide some empirical or theoretical results discussing the connection between the studied (almost) full fine-tuning and the parameter-efficient fine-tuning.", "limitations": "I did not find obvious negative social impacts of the work. The authors bring up the limitation of their work on the bound tightness. I believe the limitation is beyond the scope of the paper, which is reasonable to be left there.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. The paper asked an important and novel question: why the curse of dimension does not happen with private fine-tuning of pre-trained models? Prior empirical results have demonstrated the phenomenon, yet a theoretical understanding was not available. The paper fill the gap and clearly give an explanation of the source of the success.\n2. Both the theoretical studies and empirical evaluations are insightful and sound and could inspire future works in the community of private learning.\n3. The paper is well written and the experiments are well designed to support the theoretic results.\n\nWeakness\n1. My major concern is the experiment part. More large models should be evaluated to demonstrate the rationality of the restricted Lipschitz continuity assumption.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept