Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger
Authors: Zhiqi Bu
Yu-Xiang Wang
Sheng Zha
George Karypis
Venue: NeurIPS 2023 poster (2023)
Keywords: deep learning
differential privacy
optimization
hyper-parameter tuning
TL;DR: We propose a per-sample gradient clipping that removes the need to tune the clipping threshold while achieving SOTA accuracy.

Abstract: Per-example gradient clipping is a key algorithmic step that enables practical differential private (DP) training for deep learning models. The choice of clipping threshold $R$, however, is vital for achieving high accuracy under DP. We propose an easy-to-use replacement, called automatic clipping, that eliminates the need to tune $R$ for any DP optimizers, including DP-SGD, DP-Adam, DP-LAMB and many others.
The automatic variants are as private and computationally efficient as existing DP optimizers, but require no DP-specific hyperparameters and thus make DP training as amenable as the standard non-private training. We give a rigorous convergence analysis of automatic DP-SGD in the non-convex setting, showing that it can enjoy an asymptotic convergence rate that matches the standard SGD, under a symmetric gradient noise assumption of the per-sample gradients (commonly used in the non-DP literature). We demonstrate on various language and vision tasks that automatic clipping outperforms or matches the state-of-the-art, and can be easily employed with minimal changes to existing codebases.

Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger
Zhiqi Bu AWS AI
Yu-Xiang Wang AWS AI, UC Santa Barbara
Sheng Zha AWS AI
zhi 2hiqibu@amazon.com com
yuxiangwecs aesb.edu
zhasheng@amazon.coom com
George Karypis
AWS AI
gkarypis@amazon.comm com
Abstract
Per-example gradient clipping is key algorithmic step that enables practical differential private (DP) training for deep learning models. The choice of clipping threshold R, however, is vital for achieving high accuracy under DP. We propose an easy-to-use replacement, called automatic clipping, that eliminates the need tune R for any DP optimizers, including DP-SGD, DP-Adam, DP-LAMB and many others. The automatic variants are as private and computationally efficient existing DP optimizers, but require no DP-specific hyperparameters and thus make DP training as amenable as the standard non-private training. We give a rigorous convergence analysis of automatic DP-SGD in the non-convex setting, showing that it can enjoy an asymptotic convergence rate that matches the standard SGD, under symmetric gradient noise assumption of the per-sample gradients (commonly used in the non-DP literature). We demonstrate on various language and vision tasks that automatic clipping outperforms or matches the tfae-off-the-ar, and can be easily employed with minimal changes to existing codebases
Introduction
Deep learning has achieved impressive progress in a wide range of tasks. These successes are made available, in part, by the collection of large datasets, sometimes containing sensitive private information of individual data points. Prior works have illustrated that deep learning models pose severe privacy risks individual subjects in the training data and are susceptible various practical attacks. For example, machine learning services such as Google Prediction API and Amazon Machine Learning can leak membership information from the purchase records [65]; the GPT2 language models auto-complete texts that contain someone's 's full name, phone number, email address, etc., from the training data that it memorizes, if invoked by specific prefixes [11].
Differential privacy (DP) [24, 26, 25] is a formal definition of privacy that has been shown to prevent the aforementioned privacy risks in deep learning [1]. At a high level, the key difference between the DP deep learning and the standard one is whether the gradient is privately released. In other words, while the standard optimizers update on Σ, gt, the DP optimizers update on the private gradient:
CCode for our experiments is available at FastDP library http:///hhiaaoooossssss////sciit
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

private gradient
DP Optimizer( (g:: [=)) Optimizer(
9. Clip +oR (1.1)
Standard Optimizer( ) } = Optimizer( Σ, gi)
(1.2)
Here 9, E Rd is the per-sample gradient of loss 4 .V is the standard normal, o is the noise multiplier,
and R is the clipping threshold. The clipping function Clip Id + is defined such that l1g: - Clip(ge; Rill S R. For instance, the DP-SGD in [1]
(1.3) and a need to be determined in DP learning (1.1). On the one hand, setting the noise multiplier o is easy and can be derived analytically prior to the training. Whenever the privacy budget (c, 6) is determined, one apply off-the-shelf privacy accounting tools in Section 2.1 to determine o, based on the subsampling probability p and the number of iterations T:
DP-SGD Abadi
w1+1 = wi n Σ;
04, min
R//
dwr, 11 + oR -.....
04.
Ow.
In comparison to the regular training (1.2), two additional DP-specific hyperparameters
privacy_accouninee accountant 0. 6) =
On the other hand, the choice of clipping threshold R is crucial to the performance of DP models, yet the hyperparameter tuning is much iabon-intensive. Recent advances of DP deep learning on ImageNet [38] and on E2E datasets [41], using ResNet18 and GPT2 respectively. illustrate that the performance is very sensitive to R. We have reproduced their results Figure Observe that on ImageNet, ResNet18 8 can drop from the highest 45% accuracy to 31 1 if R is chosen 2 times larger, and to 0.1 % if R is chosen 4 times larger. Similar drastic drop can also be observed in [38, Figure 3] even if the noise multiplier = O. Unlike the noise multiplier a, the clipping threshold R cannot be inferred from the privacy budget (e, and have to be tuned. Consequently, DP training necessarily requires expensive 2D grid search for (R, v). like Figure 1, whereas the regular training only requires an easy ID grid search for v,. Even worse, the difficulty of tuning a per-layer clipping threshold vector [49], i.e. one clipping threshold for one layer, may increase exponentially as the number of layers increases.
To save the effort of tuning R. previous researches have proposed different approaches. In [3, 58, 28, 31], researchers advocate to use uuta-adaptive information select R. such as a specified quantile of the gradient norm distribution. These adaptive clipping methods can be little ad-hoc: they often replace the need to tune by the need to tune one or more new hyperparameters, e-g. the quantile to use and the ratio split the privacy budget between the quantile decision and the gradient perturbation. Another approach used by the practitioners is to replace the single 2D grid search by multiple cheaper 1D grid searches. For example, the researchers propose, in [38, Section 3.3] to fine-tune 1) with non-DP SGD, fix v) and sweep over various values of the clipping threshold R with DP-SGD, then further fix R and do one more grid search 17. However, tuning R formally in data-dependent way (e.g. through cross-validatie volssvvalittion) introduces additional privacy loss [55], and most existing empirical work does not privately conduct hyperparameter tuning.
We take a completely different route by proposing a new clipping principle that removes R, instead of coming up with methods to find the appropriate R. We term our method as automatic clipping and the DP optimizers using it as automatic DP optimizers. Our contributions are:
1. We propose the automatic clipping in (4.1) that expunges the clipping threshold from general DP optimizers, making DP training as amenable as regular training. In large-scale tasks (GPT-level) like Figure 1, our automatic clipping can reduce the cost of ablation study by 5x?.
2. We show that automatic DP optimizers are as private and efficient as existing DP optimizers.
3. We show in Theorem 4 that automatic DP-SGD converges in the non-convex setting, at the same asymptotic convergence rate the standard SGD. Our theoretical analysis successfully explains the training behaviors of deep learning in previous empirical works.
4. We demonstrate the superiority of automatic clipping on a variety of vision and language tasks, especially with large models including ResNet, RoBERTa and GPT2.
5. In Appendix K, we include simple code snippets that demonstrate how easy it to switch from Abadi's clipping to our automatic clipping in popular codebases, c.g. Opacus and ObJAX.
'The hyperparameter tuning of (R, 1) takes days (e.g. GPT2 [41]) to months (e.g. GPT3-175B) on large foundation models, highlighting the significance of our method expunge the additional Rt

---

2 Preliminaries
2.1 Differential Privacy
We consider the (c, 5)-DP in Definition 2.1, where smaller (c. 6) means stronger privacy guarantee.
Definition 2.1 ([25]). randomized algorithm M is (e, -differrential private (DP) if for any two neighboring datasets S, (i.e. if one can obtain S' by adding or removing one data point from S), and for any event E,
PIM(S) F.J & PP E +
(2.1)
In words, DP restricts the influence of an arbitrary sample, so that the information contributed by such sample is limited and less vulnerable to privacy attacks. In deep learning, DP is achieved by applying the subsampled Gaussian mechanism to privatize the minibatch gradients during training.
As illustrated in Equation (1.1), the subsampled Gaussian mechanism involves (I) sampling mini- batch by including each data point iid with probability (II) per-sample gradient clipping to bound the l2 norm sensitivity at R and (III) adding independent Gaussian noise proportional to R and where a is derived from the privacy budget (c, 5). This can be realized by leveraging a variety of modern privacy accounting tools, such Renyi DP (or moments accountant) [1, 51, 71], Privacy Loss distribution (Fourier accountants) [37, 30, 82], or Gaussian DP [19, 7].
2.2 Differentially Private optimizers with general clipping operations
Privately released stochastic gradients (through the Gaussian mechanism) can be used by various off-the-shelf optimizers, including DP-SGD (1.3), DP-HeavyBall, DP-AdaGrad, DP-Adam, DP- FedAvg/FedSGI [49], etc. To improve the performance of DP optimizers, previous researches the per-sample clipping can be classified into two categories.
The first category, where the majority of researches lie in, works with Abadi's clipping and focuses on better design of R. To name few examples, one can adaptively design Rg for each iteration [3, 58, 28], or design the per-layer clipping threshold vector R E R_ for L. layers [1, 49] so to apply a different clipping threshold for each layer.
Fewer works fall into the second category that proposes new clipping methods. In fact, any function Clip Fd + ER satisfying [[lip(g) gl R can serve valid clipping function besides Abadi's For example, the global clipping [9] proposes Clip (g:) := I(Ilg:ll || < R) to mitigate the bias of the private gradient and alleviate the mis-calibration issue of DP classifiers. Another example is the re-parameterized clipping [17], pr
param (9:) min(1, (1/11g II, 1/R), which is equivalent Abadi's s clipping under re-scaled learning rate. Our automatic clipping belongs this category. We note that different clipping methods work orthogonally to optimizers, network architectures and gradient norm computation (see Section 8).
3 Motivation
3.1 Small clipping threshold often works best
15-1.6033
60.66626
59.58
60.01
57.87
35.44
3-
43.0
2.0
0.1
0.1
0.1
50
Learning rale
10"124 50.48 50.31
50.48
49.25
34.47
Leaming rate
8*30*
22.0
45.0
0.1
0.1
30
s0r1ga 33.17 38.18
33.13
32.96
29.50
B.13
2.1
22.0
to 29.74
29.55
27.07
0.29
10
B+15->
0.1
0.25
2.1
13.0
0.44
0.
011-2
30
Clipping norm
Clipping norm
Figure 1: Ablation study of clipping threshold and learning rate. Left: BLEU score GPT2 on E2E
dataset [41], with OP-AAdaWW, W. Right: Test accuracy of ResNet18 8 on ImageNet [38], with DP-SGD.

---

One intriguing observation that we can make about the recent studies on DP learning with large models is that the state-of-the-ae (SOTA) results are often achieved with very small clipping threshold R. This observation is consistent in both vision and language tasks. In [41], GPT2 (about 800 million parameters) and RoBERTa models (over 300 millions parameters) achieve the best results under DP on QNLI, MNLI, SST-2, QQP, E2E, and DART datasets, with each per-sample gradient clipped to length At = 0.1. In [38, 17, 50], ResNets and Vision Transformers achieve the best DP results on ImageNet with R = 1; in [68], the best DP results CIFARIO use R = 0.1 with ResNeXt-29 and SimCLRv2 [13]. The effectiveness of small clipping threshold together with proper learning rate is depicted in Figure 1.
Intuitively, smaller R implies that the Abadi's clipping (3.1) is effective, which means min [R/ll:/ll = R/ ||g:1l- Given that the clipping threshold R is so small compared to the number of parameters in large models, and that strong DP is guaranteed when the number of training iterations is small (i.e. ||g: || has not converged to small values yet), we expect and empirically observe that the clipping happens on a large proportion of per-sample gradients at all iterations. For instance, we find in the GPT2 generation experiments in [41] that 100% of per-sample gradients are clipped at all iterations; in classification tasks such as QQP, QNLI, and MNLI, the percentage of clipping is about 20 ~ 60% on average (more details in Appendix H.I).
3.2 Per-sample gradient normalization as new clipping
In the small clipping threshold regime, we can approximately view
Clip (g:: R) min R/ = R/ 1l C1iPAUTO-V R)
(3.1)
and thus derive novel private gradient Σ, R 8: + oo- .N(O, I). Here AUTO-V stands for the vanilla automatic clipping, which essentially performs the normalization on each per-sample gradient. As a specific example, we can write the R-dependent automatic DP-SGD as
R-dependent DP-SGDAUTO-V W = w. nl (I
/1 A
R
04 ow. /lo, ow.
Ø4
||
+ oR aR. N(..1)
(3.2)
We may view our AUTO-V clipping as to maximize the dot-product similarity commonly used similarity measure, e.g. in the attention block in transformers [69]) between the clipped gradient and the regular gradient. Suppose we want to
max
C. E C2
s.t. 0 O, R/
(3.3)
Note that the constraint is a sufficient condition for clipping, as discussed in Section 2.2. It is not hard to see that the optimal clipping factor (though violating DP guarantee") regarding (3.3) is
C R/llg,1 I((g.. E, g,) 0)
(3.4)
If the per-sample gradients are indeed concentrated in the sense Vi, (g., E, 9j) 2 0, then AUTO-V is the optimal per-sample gradient clipping. We compare with Abadi's clipping in Figure 2, where this similarity is significantly magnified by our AUTO-V V clipping. In fact, the dot dro-puoduct similarity in (3.3) closely resembles the convergence of DP optimization for Theorem 4 in (C.2).
35000 s00000
AUTO-N clipping
AUTO-V clipping
dipping
Abadi clipping
Dot product
250000 b000s
10x
46
16
s5ice sades roice Laloa 120000198000 173000200000
Beration
Dot product
Figure 2: RoBERTa-base with AP-Adam (c 3) on SST2 dataset, as in Section 6.2.
IIn DP literature, per-sample clipping depend only on individual gradient g, separately, hence does not allow the use of E, gj. which changes the sensitivity when adding or removing one data point from the mini-bane batch.

---

3.3 Stability constant breaks scale-invariance and remains stationary
One potential drawback AUTO-V clipping is that all gradients lose their magnitudes information completely, since lig: CliPAUTOn v R)]l = R, Vi. This scale- invariance in AUTO-V and partially in Abadi's clipping (when gill > R) leads to the "lazy region" issue: the parameters will not be updated by DP-GD even if the true gradients are non-zero. In Figure 3, we illustrate such issue in a logistic regression' for AUTO-V V and Abadi's clipping, when the trainable parameter E [-2, 2]. as the gradients from two classes cancel each other.
0.044
0.822
-0.92
staddd grad
(iored and (Atadi
cloped grai (AUTO cloped gral (AUTO-3)
-0.24
Figure 3: Gradient (scalar) at each O.
To preserve the magnitude information and thus escape the lazy region, we propose the AUTO-S clipping, with a positive stability constant
C1 PAAPPUOOSSS (9: Rt) R/ + 7)
(3.5)
We visualize in Figure 5 that AUTO-S allows larger per-sample gradients have larger magnitudes after the clipping. while still allowing smaller gradients to vanish after "clipping". That is, as gi - 0. the existence of y allows the clipped gradient Cıg: 9:/7 rather than having magnitude R as in AUTO-V, V. We elaborate this point in Section 4.3. This is critical in our convergence analysis and allows UP-SGGAUTOS (but not DP-SGDAUTO-V converge to zero gradient norms in Section 5.
Automatic DP Training
One may wonder why our clipping (3.1)(355) automatic at all, if the hyperparameter R is still present and there additional parameter y choose. It turns that any constant choice of R 0 equivalent to choosing R = 1, and common deep learning optimizers are insensitive to the choice o (e.g. for any y 0, show that the gradient norm converges to zero the same asymptotic
rate in Theorem 4; see also the ablation study in Figure 15). Consequently, we set 7 0.01 as the default. Specifically, let us redefine the R-independent clipping function:
CliPAUTO-S (g:) == 1/(1g: +7).
(4.1)
With this clipping, we can design automatic DP optimizers similar to (1.1):
Automatic DP Optimizer(1g:)) )
Optimizer
Σ g + + (OO
Jt.i
(4.2)
denoted as 9+
Clearly, the new private gradient 9r from our automatic clipping is R-independent, in contrast to the one used in (1.1). A concrete example (in the case of 7 0) that is comparable to (3.2) will be
0l
Øl.
R-independent DP-SGDAUTO.v: W = w. n Σ
+ t -VO,)) (4.3)
Ow.
Ows
I Leveraging the private gradient å: in (4.2), we can train DP neural networks without tuning DP- specific hyperparamters R and o, as demonstrated in Algorithm
Algorithm Automatic Deep Learning with DP
Parameters: initial weights Wo, learning rate T) sampling probability p. number of iterations T.
1: Compute such that CAccountant (5, o. T) from any privacy accountant.
2: for iteration t = 1,... do
3: Sample a batch B, by including each data point i.i.d. with probability p
4: Apply automatic clipping to per-sample gradients ie 9: = gi/ (11gg111122 0.01).
5: Add Gaussian noise the sum of clipped gradients: 9 Σ, 9, + (O.
6: Update wn by any optimizer on the private gradient ğ with learning rate п)-
'The settings are in Appendix F, where the lazy region issues also emerge in the mean estimation problem. We note that the lazy region also discussed [14, Example 2].
5

---

We will elaborate two distinct reasons in the next sub-section for the following statement:
DP Optimizer Abadi
Abadi R R-dependent DP OptimizerAurI AUTO = R-independent DP Optimizer AUTO
which expunges the DP hyperparameters, only leaving the regular hyperparameters such as learning rate, weight decay, etc. The significant save in the tuning effort is illustrated in Figure 4.
85.0 64.7
67.0
75.8
47.8 47.8 47.8
Learning rate
c.m 90.6 90.8 90.6 90.8 91.3
90.7
[4.3 84.9 85.2 84.0 80.0 85.1
Learning rafe
557.0
67.0
47.8
47.8 47.8
R.om 99.0 02.00.0 92.3 92.3
92.7
14..3
84.6
84.2
04.4
17.0
18.4
78.2
78.0
1000--91.3 91.4 91.9
92.3
91.4
82.3 62.5
02.2
17.2
77.2
77.2
4000 90.9 9 90.9 91.2 91.6 92.1
93.2
soou 79.2
79.4 79.4 79.3 79.2
79.5
4000
74.1
74.5 74.7
74,9
75.0
16.6
Clipping Test accuracy of RoBERTa-base by different clipping thresholds R and learning rates This is trained with DP-Adam (Abadi and AUTO-S) on SST2 (left, 3 epochs), QNLI (middle, epoch), and MNLI (right, I epoch), under e = 3. Notice by only searching along 1), instead of over (R, n),, we can save the cost of hyperparameter tuning by 5x.
Cipping
Clipping
Figure 4:
4.1 Non-adaptive optimizer couples clipping threshold with learning rate
With R-dependent automatic clipping, DP-SGD becomes
R
Wi+1 = wi 17 Σ 9t.
I + + oR (R..NO = w. - -Rgg.
We can view Neffeetive = n. as whole: increasing R has the same effect as increasing 7) which explains the diagonal pattern in Figure 1(owwer plot) where DP-SGD Abadi clipping threshold. We extend to general non-adaptive optimizers in Theorem 1s.
Abadi is applied with small
Theorem 1. Non-adaptive R-dependent automatic DP optimizers (including SGD, Heavyball[59] and NAG[54]), with learning rate di and weight decay X, is equivalent to R-independent automatic DP optimizers, with learning rate R and weight decay X/ R.R.
4.2 Adaptive optimizer can be insensitive to clipping threshold
Adaptive automatic DP optimizers are different than the non-adaptive ones, as the clipping threshold cancels out instead of being coupled with learning rate. To see this, we scrutinize DP-Adam, Abadi (which is similar to Ad-AoomAUTO-V in Figure 1(upper plot). where columns to the left are almost identical. Further evidence observed in [50, Table that shrinking R has zero effect on LAMB. We now give simple explanation using AdaGrad [22]:
9t
Wi+1 ut: 7)
VErce 9
where Dt -, It.s is the gradient sum. In R-dependent DP-AdaGrad the private gradient is Rg: in place of the standard gradient sum gr:
Rg.
gt
1 = w:
Wt
RC E
Eres (g-)
We generalize to other adaptive optimizers in Theorem 2 and to the per-layer clipping style in Appendix B.3.
Theorem 2. Adaptive R-dependent automatic DP optimizers (e.g. AdaGrad[22),, AdaDelta[79) AdaMaz/AAdm{{55] NAdam/20) RAdam[43), LARS[75), LAMB[76]), with learning rate and weight decay is equivalent to R-independent automatic DP optimizers with learning rate n and weight decay X/ With decoupled weight decay[46), R-dependent automatic DP-AdamW is equivalent to R-independent automatic DP-AdamW with the same 17 and X.
'This coupling of rj and R is also partially observed in [17, Appendix B. through a re- parameterization trick of Abadi's clipping. Unlike AUTO-SP S/V, the coupling is not strict (e.g. doubling R is not equivalent to doubling y7 thus still necessitating tuning both (n, Ht).. and the relationship to weight decay not discussed.

---

4.3 Automatic clipping is equally private and maximizes utility
In Theorem (proved in Appendix A), we show that the new private gradient 9: in (4.2) has the same level of privacy guarantee as the existing one in (1.1), since the global sensitivity remains the same (see Figure 5).
Norm clipped gradient
0.0
3.6
AUTO-S, 0
0.4
We note that as long as 7 > O, the mag- nitude information of per-sample gradients is preserved by AUTO-S, in the sense that Ig > |لاو|| - |[ag::ll > |[, ll. whereas this can be violated in both the AUTO-V and Abadi's 's clipping (as depicted by the flat curve Figure when g > 1).
AUTO:S, y
AUTO Y=
82
AUTO-S, Y=1
80
0.0
025
0.50
0.75
100
125
150
175
200
||9il
Figure Per-sample gradient norms before and after different clippings at 1
Additionally, note that when & is small, almost all data points "max out" the signal relative to the amount of noise we add. To say it differently, for the same amount of noise, AUTO-S with small y allows more signal to be pushed through differentially private channel. Towards the end of the training, i.e., at the limit when || + 0 for all i, then we have 2; Tell
9: + + >. Di- In words. the clipped gradients become closer to the standard SGD, thus do not suffer from the instability of AUTO-V.
Theorem 3. Under the noise multiplier a. number of iterations T. subsampling probability B/n, DP optimizers using AUTO-V or AUTO-S clipping satisfy (Caccomnont (Ō, a, B)n,T)) where Accommtant is any valid privacy accountant for DP-SGD under Abadi's s clipping.
5
Convergence analysis of DP-SGD with automatic clipping
5.1 Convergence theory of DP-SGD stationary points
We highlight that automatic clipping can be more amenable to analysis than Abadi's clipping in [14], since longer need decide whether each per-sample gradient is clipped.
To analyze the convergence of automatic DP-SGD (4.2) in the non-convex setting, we follow the
standard assumptions in the SGD literature [27, 2, 6], including a symmetry assumption the gradient noise, which empirically verified [14, Figure 3] and commonly used in the standard non-DP literature [48, 66, 12, 73J. We refer the curious readers Appendix E.5 for details.
Assumption 5.1 (Lower bound of loss). For all w and some constant L., we have L(w) 2 L.. Assumption 5.2 (Smoothness). Let g denote the gradient of the objective L(w). Then Vw, v. there is an non-negative constant L such that
L
((v) [[(w) (
T (v- w)] w
w112.
(5.1)
Assumption 5.3 (Gradient noise). The per-sample gradient noise Zr.i 9r is i.id. from some ditribution such that
E 9t) = 0, Elg., - 9e < E
and g is centrally symmetric about g: distribution: G..; g: gt
gt.i-
We show in Theorem 4 that DP-SGD with AUTO-S clipping allows the true gradient norm to converge to zero, though the clipped gradient may still be biased, but not so with AUTO-V clipping.
Theorem 4. Under Assumption 5.1, 5.2, 5.3, running DP-SGD with automatic clipping for T
iterations and setting the learning rate n) 1/VT give
L.)L (1+ (Co-
o²d :E,7 B )=:))
5 F (.....r,E,,)) (r, (5.2) r00
min B(Ilgal)) S oSiST
min
'The upper bound takes an implicit form of G(:E. because it is a lower envelope of functions < F(rr, &, over all possible r > 0, whose forms are detailed in Theorem 6, Notice that & results only from the clipping operation, not from the noise addition.
7

---

Here ... represents the first argument of G. and G is increasing and positive. T + oo, we have min, E(Ilg.l)) O(T 1/4 ) for AUTO-S, the same rate as the standard SGD given Theorem 9.
Upper toound oppelliii
Upp Bosane of mino manat00li0 (10il0
Lpgee ROSSTIRR of PepellllnDD 3
0P-50 AUTO-6
of Beret
Beratore
Figure 6: Left: DP-SGD with AUTO-V clipping. Middle: DP-SGD with AUTO-S clipping. Right: Log-log plot of convergence rate in comparison to standard SGD. Here ç = 25, 7 = 0.01, and the O(1/VT) term is set to 10 for DP-SGD and to for standard SGD,
Remark 5.4. We show in Theorem 6 and in Figure that the upper bound (5.2) has 9 2 & for AUTO-V (y = 0), and g only reduces to zero for AUTO-S (? 0). We provide real data evidence in Figure 14 that strictly positive y reduces the gradient norm significantly.
5.2 Analysis faccorr affecting the convergence
We now analyze the many factors that affect the convergence Theorem 4, from a unified viewpoint of both the convergence and the privacy.
We start with the stability constant 7 and the learning rate Tts both only affect the convergence the privacy. We empirically observe in Figure 8 that small benefits the convergence at initial iterations (when the privacy guarantee is strong) but larger y converges faster asymptotically. For me- the optimal is in fact the miminizer of the hyperbola in (C.5), that is unique and tunable.
Next, focus the hyperparameters that affect both convergence and privacy: the batch size B, the noise multiplier a, and the number iterations T. These hyperparameters have to be considered along the privacy-accuracy tradeoff, not just from convergence perspective.
Recall that given fixed privacy budget (e, 8), we rely on modern privacy accountant for computing the appropriate combinations of parameter T, B. The exact expression of the bound function of (e, 8) somewhat messy. For this reason, we illustrate our analysis in terms of the surrogate parameter for μ-GDP [19], which implies (c, 5DDP with c = +y 2ott////og///////////////
log(1/))). [7] showed that DP-SGD's privacy guarantee asymptotically converges μ-GDP (as T oc) with μ VT(el/a* -1). We alternatively leverage p-CCDP [10] for similar conclusions, using p in place of 1²² in (5.3).
Theorem 5. Under Assumption 5.1, 5.2, 5.3, fixing the asymptotic p(c, 8)-G parameter, running DP-SGD with automatic clipping for T iterations and setting the learning rate n x 1/VT give
( / (c/cco- C.)L (+
1 + +0 (((TTT) :5.77
min B(1lg: S & 0S1ST
(5.3)
12
To show that our analysis matches the training behaviors observed SOTA empirical work [41, 38, 17, 68, 50, 78], minimize the first argument of G in (5.3), denoted X X(B, T, T, μ, d, L, Co).
1. [Train longer with larger noise] Fixing the expected batch size we that X is decreasing in T. Hence larger T and consequently larger are preferred.
2. [Larger batch size helps] Fixing number of iterations T or epochs E BT/n, we see that X is decreasing in B. Hence larger B and consequently larger
preferred.
3. [Pretraining is critical] Pretraining boost the DP accuracy through much smaller initial loss Lo and from a smooth (small L) and flat (small ç, c.f. Figure 8(left)) initialization.
4. [Learning rate needs tuning] The optimal learning rate by minimizing (C.5) is V Lla"n"+dT) This indicates that one should use larger learning rate for smaller model d, weaker privacy (larger y small e), smaller iteration budget T.

---

Experiments
We evaluate our automatic DP training on image classification, sentence classification, and table-to- text generation tasks. Detailed settings including hyperparameters can be found in Appendix G.
6.1 Image classification
use the same setup in [56, 68, 64] with simple CNN. For CIFARIO, we use the same setup as in [68] with pretrained SimCLRv2 [13]. For ImageNette, a the same setup in [36] without the learning rate decay. For CelebA [45], the real human face dataset, we train ResNet9 [32] with group normalization to replace the batch normalization. Notice that CelebA contains high-resolution (178x218) images, each with 40 labels. We consider CelebA for either multi-class classification on one label, e.g. 'Smiling' and 'Male', for multi-label/multi--e problem to learn all labels simultaneously.
For MNIST/FashionMNISTT,
10-class sub-task of ImageNet [18],
Table 1: Average test accuracy and 95% confidence interval on image tasks over 5 runs.
Accuracy
Task
Model
(c,5)
non-DP
Abadi's clipping
AUTO-S clipping
(c (==3) 00)
MNIST
layer CNN
[3. le-5)
98.04 = 0.09
98.15 + 0.07
99.11 0.07
FashionMNIST
layer CNN
[3, 1e-5)
86.04 = 0.26
86.36 0.18
89.57 + 0.13
0.113
CIFARTO pretrained
SimCIRv2
2, le-5)
92.44 + 0.13
92.70 0.02
94.42 + 0.01
ImageNette
ResNet9
[8, le-4
60.29 + 0.53
60.71 + 0..48
71.11 + 0.37
CelebA [Smiling]
ResNer9
18, 5e-6)
90.75 + 0.11
91.08 + 0.08
92.61 + 0.20
CelebA [
ResNet9
88 5)-66
95.54 + 0.14
95.70 0.07
97.90
0.04
CelebA Multi-labo
ResNet9
3. 56-6)
86.81 + 0.03
87.05 0.01
90.30
+ 0.02
CelebA Multi-label
ResNer9
(8, 5e-6]
87.52 + 0.15
87.58 + 0.04
90.30 + 0.02
In Table 1, we observe that AUTO-S clipping outperforms existing clipping in all datasets with statis- tical significance. Interestingly, the standard deviation from different runs smaller for automatic DP optimizers, indicating better reproducibility and stability. We additionally experiment 40 binary classification problems on CelebA with respect to each label, and observe that the mean accuracy further improves to 91.63% at 8 for AUTO-S (see Appendix J).
6.2 Sentence classification
On five benchmark language datasets (MNL((m/mm))72), QQP[34], QNLI[62), SST2[67D, we compare our automatic DP training with re-parameterized gradient perturbation (RGP, [78]) and full-parameter finetuning (full, [41]) using RoBERTa models [44]. These methods use the same experimental setup. For language models, our automatic training based on the codebase [41].
Table 2: Test accuracy on language tasks with RoBERTa-bant (12 blocks, 125 million parameters).
Method
3=3
=
do (non-DP)
MNLI
QQP QNLI SST2
MNLI
QQP
QNLI
SS12
MNLI
QQP QNLI SST2
RGP[78]
80.5779.6
85.5 87.2
91.6
83.6/83.2
89.3 91.3 92.9
[41]
82.45/82.99
85.56 87.42 91.86 83.20/83.44
86.08
87.94 92.09
full AUTO-V
81.21/82.03
84.72 86.56 91.86 82.18/82.64 86.23
87.24
92.09
85.91/86.14 87.34 91.40 94.49
full AUTO-S
83.22/83.21 85.76 86.91 92.32 83.82/83.55
86.58
87,85
92.43
Table 3: Test accuracy on language tasks with largRTa-large (24 blocks, 355 million parameters).
Method
3
E E=
8
co (non-DP)
MNLI
QQP ONLI SST2
MNLI
QQP QNLI SST2
MNLI
QQP QNLI SST2
RGP [78]
1/86/0
86.7 90.0 93.0
full [41]
86.43/86.46 46 86.43 90.76 93.04 87.02/87.26
87.47 91.10 93.81
full AUTO-V
85.33/85.61 86.61 89.99 93.12 10 86.86 90.55 93.35
90.33/90.03 87.90 93.61 96.21
full AUTO--S
86.27/86.67 86.76 91.01 93.92 87.07/87.16 87.47 91.45 94.61
In Table and Table 3, we note that full parameter finetuning with AUTO-S outperforms or least matches SOTA on all tasks. We use exactly the same hyperparameters in [41].

---

6.3 Table-to-text generation
We compare our automatic DP training with variety of fine-tuning methods, for table-to-texx generation task on E2E dataset [23], where the goal is to generate texts about different aspects of a restaurant's data. We measure the success on this task by BLEU, ROUGE-L (in Table 4), METEOR, NIST, CIDEr (extended in Table 8), with higher value meaning better model quality.
Table 4: Test performance E2E dataset with GPT2. Additional performance measures are included in Table 8. The best two GPT2 models for each row are marked in bold.
DP
GPT2
GPT2
GPT2
Metric
guarantee
large
medium
full
full
full
full LORA RGP
prehx top2
retrain
AUTO-S
AUTO-S
AUTO-S
AUTO-V
[41]
[33]
[78]
[40]
== 3
64,180
63,850
61.340
61.519
61.519
58.153 58.482
47.772 25.920 15.457
BLEU
= 8
64.640
64,220
63.600
63.189
63.189
63.389 58.455 49.263 26.885 24.247
non-DP
66.840
68.500
69.463
69.463
69.463
69.682 68.328 68.845 65.752
65.731
<= 3
67.857
67.071
65.872
65.670
65.670
65.773 65,560
88,964 44,536 35,240
ROGUE-L
68.968
67.533
67.073
66.429
66.429
67.525 65.030 60.730 46,421 39.951
non-DP
70.384
71.458
71.359
71.359
71.359
71.709 68.844 70.805 78. 68.751
Competitive methods include low-rank udaption (LoRA), prefix-tuming (prefix), RGP, only fine-tuning the top Transformer blocks (top2), and training from scratch (retrain), as were recorded [41]. Again, we use the exactly the same hyperparameters as in [41]. For GPT2 (124 million parameters), GPT2 medium (355 million), and GPT2 large (774 million), Table 4 shows that AUTO-S is scalable with stronger performance on larger models. Our automatic full-parameter finetuning has the best overall performance. Additionally, we highlight that AUTO-S and methods like LoRA are not mutually exclusive and can be combined to yield strong performance, since AUTO-S modifies the optimizers and LoRA modifies the architecture.
Related works
While other DP works also normalize the per-sample gradients (instead of clipping them) use small clipping threshold (making the clipping similar to normalization), our work is very different in terms of theoretical analysis, algorithm design and experiments. In fact, the concurrent work [74] gives the
same algorithm as AUTO-S, although its theoretical analysis and experiment design is fundamentally different from ours. [16] proposes to normalize the per-user (not per-sample) gradient in the federated learning setting, and analyzes the convergence in a convex, non-deep-leaming setting.
On the other hand, many works apply the per-sample gradient clipping with small R for good utility [1, 41, 50, 38, 17]. These works have led to valuable insights, but also some false or incomplete conclusions, due the lack of rigorous theoretical analysis. For instance, since I is present in the (re-pan (re-parameterized) per-sample clipping, it cannot avoid the hyperparameter tuning as the choice of R robust; even if a sufficiently small R is used, the clipping does not reveal the stability constant in AUTO-S, which enjoys theoretical and empirical advantages in Remark 5.4 and Section 6. We devote Appendix L to more instances (c.g. Footnote 5) and a thorough comparison.
8 Discussion
In this work, we propose the automatic clipping as drop-in replacement to the standard per-example clipping for differentially private training. This is the first technique that eliminates the need to tune the clipping threshold R, thus making DP deep learning casy as regular learning. Our AUTO-S method enjoys both theoretical guarantee of convergence in non-convex problems (under various conditions), and strong empirical performance that advances DP learning on computer vision and language tasks.
We are excited about the future of automatic DP training, especially along with other working techniques, such as general optimizers (e.g- [8, 21)), clipping styles (all-layer or per-layer or adaptive clipping), architecture modifications (e.g. LoRA, RGP, prefix), and data augmentation (e.g. adversarial training [29] and multiple augmentation [17]). Thus, we expect to achieve comparable results to all SOTA in a lightweight fashion.
10

---

Acknowledgement
We would like to thank Xuechen Li for updating his codebase and for his quick response in technical details to reproduce the results, which was crucial for benchmarking experiments.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
[2] Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. Advances in neural information processing systems, 31, 2018.
[3] Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems, 34, 2021.
[4] Satanjeev Banerjee and Alon Lavie. METEOR: An automatic metric for MT evaluation with improved correlation with human judgments. In Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, pages 65-72, Ann Arbor, Michigan, June 2005. Association for Computational Linguistics.
[5] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[6] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 20,3)11 2018.
[7] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
[8] Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Hanwen Shen, and Uthaipon Tantipongpipat. Fast and memory efficient differentially private-sgd via projections. Advances in Neural Information Processing Systems, 34, 2021.
[9] Zhiqi Bu, Hua Wang, and Qi Long. On the convergence and calibration of deep learning with differential privacy. arXiv preprint arXiv:2106.0785 106.07830, 2021.
[10] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. Proceedings of the 50th Annual ACM SIGACT Symposium on Thheory of Computing, pages 74 14-86,772 2018
[11] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagiclski, Ariel Herbert- Vearbert-Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633-26501 2021.
[12] Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-10. IEEE, 2018.
[13] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607. PMLR, 2020.
[14] Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 13:13773-13782. 2020.
[15] Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference machine learning, pages 2260-2268. PMLR, 2020.

---

[16] Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, and Inderjit S Dhillon. On the convergence of differentially private federated learning on non-lipschitz objectives, and with normalized client updates. arXiv preprint arXiv: 100.02006677994 2021.
[17] Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
[18] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255 255. Icee, 2009.
[19] Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B, 84(1):3-37, 2022.
[20] Timothy Dozat. Incorporating nesterov momentum into adam. 2016.
[21] Jian Du and Haitao Mi. Dp-fp: Differentially private forward propagation for large models. arXiv preprint arXiv:21 /2. /4430, 2021.
[22] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[23] Ondrej Dusek, Jekaterina Novikova, and Verena Rieser. Evaluating the State-of-the-Art of End-to-End Natural Language Generation: The E2E NLG Challenge. Computer Speech & Language, 59: 123-156, January 2020.
[24] Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and upplications of models of computation, pages 1-19. Springer, 2008
[25] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[26] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)2211-00) 2014.
[27] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4): 2013.
[28] Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang. Aaron Roth, Michael Kearns, and Stefano Soatto. Mixed differential privacy in computer vision. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 8376-8386, 2022.
[29] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
[30] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34, 2021.
[31] Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. arXiv preprint arXiv: 12.::2132 2022.
[32] Kaiming Hc, 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.
[33] Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, Weizhu Chen, et al. Lora: Low-rank adaptation of large language models, In International Conference on Learning Representations, 2021.
[34] Shankar Iyer, Nikhil Dandekar, and Kornel Csernai. First quora dataset release: Question pairs, 2017.
12

---

[35] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
[36] Helena Klause, Alexander Ziller, Daniel Rueckert, Kerstin Hammernik, and Georgios Kaissis. Differentially private training of residual networks with scale normalisation. arXiv preprint arXiv:2203.00322 2022.
[37] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pages 2560-2569. PMLR, 2020.
[38] Alexey Kurakin, Steve Chien, Shuang Song, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward training imagenet scale with differential privacy. arXiv preprini 22ti::220..13228, 2022.
[39] Quentin Lhoest, Albert Villanova del Moral, Yacine Jernite, Abhishek Thakur, Patrick von Platen, Suraj Patil, Julien Chaumond, Mariama Drame, Julien Plu, Lewis Tunstall, Joe Davison, Mario Sasko, Gunjan Chhablani, Bhavitvya Malik, Simon Brandeis, Teven Le Scao, Victor Sanh, Canwen Xu, Nicolas Patry, Angelina McMillan-Major, Philipp Schmid, Sylvain Gugger, Clément Delangue. Théo Matussière, Lysandre Debut, Stas Bekman, Pierric Cistac, Thibault Goehringer, Victor Mustar, François Lagunas, Alexander Rush, and Thomas Wolf. Datasets: A community library for natural language processing. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 175-184, 184, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[40] Xiang Lisa Li and Percy Liang. trefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume Long Papers), pages 4582-4597 2021.
[41] Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language mod- els can be strong differentially private learners. In International Conference on Learning Representations, 2021.
[42] Chin-Yevr Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summariza- tion Branches Out, pages 74-81, Barcelona, Spain, July 2004. Association for Computational Linguistics.
[43] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference on Learning Representations, 2019.
[44] 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: 1662,, 2019.
[45] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[46] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018
[47] Danilo P Mandic. A generalized normalized gradient descent algorithm. IEEE signal processing letters, 11(2):15--11,, 2004.
[48] Stephan Mandt, Mathew D Hoffman, and David M Blei. Stochastic gradient descent as approximate baycsian inference. Journal of Machine Learning Research, 18:1-35, 2017.
[49] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
13

---

[50] Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky. Large scale transfer learning for differentially private image classification, arXiv preprint arXiv:2205.0297. 0222735, 2022.
[51] Iya Mironov. Rényi differential privacy. In 2017 JEEE 30th computer security foundttions symposium (CSF), pages 263-275. IEEÉ, 2017.
[52] Diganta Misra. Mish: A self regularized non non-monotonic activation function. BMVC 2020, 2019.
[53] Ryan Murray, Brian Swenson, and Soummya Kar. Revisiting normalized gradient descent: Fast evasion of saddle points. IEEE Transactions on Automatic Control, 64(1 (4(11):4818-8 2019.
[54] Yurii E Nesterov. A method for solving the convex programming problem with convergence rate o (1/k" 2). Dokl. akad. nauk Sssr, volume 269, pages 543-547, 1983.
[55] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2021.
[56] Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9312-9321. 2021.
[57] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: A method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguisties, ACL '02, page 111-118, USA, 2002. Association for Computational Linguistics.
[58] Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X Yu, Sashank J Reddi, and Sanjiv Kumar. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv: 07643, 2019.
[59] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[60] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimizaaion, 30(4):838 855, 1992.
[61] Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with batch-channel normalization and weight standardization. arXiv preprint arXiv:1903.10520 2019.
[62] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100, 000+ questions for machine comprehension text. In EMNLP, 2016
[63] Seyed Omid Sadjadi, Timothee Kheyrkhah, Audrey Tong, Craig S Greenberg, Douglas A Reynolds, Elliot Singer, Lisa P Mason, Jaime Sermandez-Cordena et al. The 2017 nist language recognition evaluation. In Odyssey, pages 82-89, 2018.
[64] Ali Shahin Shamsabadi and Nicolas Papernot. Losing less: A loss for differentially private deep learning. 2021.
[65] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3-18. IEEE, 2017.
[66] Samuel I. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V Le. Don't 't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018.
[67] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pages 1631-1642 2013.
[68] Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference Learning Representations, 2020.
14

---

[69] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[70] Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh, Cider: Consensus- image description evaluation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4566-4575 2015.
[71] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differ- ential privacy and analytical moments accountant. In International Conference on Artificial Intelligence and Statistics, pages 1226-1235. PMLR, 2019.
[72] Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 1112-1122. Association for Computational Linguistics, 2018.
[73] Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference Learning Representattinss 2020.
[74] Xiaodong Yang, Huishuai Zhang, Wei Chen, and Tie- Yan Liu. Normalizeddilippedd sgd with per- turbation for differentially private non-convex optimization. arXiv preprint arXiv:2206. 13033, 2022.
[75] Yang You, Igor Gitman, and Boris Ginsburg, Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 1708.000000 03888, 6(12):6, 2017.
[76] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations, 2020.
[77] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. /2298, 2021.
[78] 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, pages 12208-12188, PMLR. 2021.
[79] Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprini arXiv:1212.5777 1212.5701, 2012.
[80] Shen-Y Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. Stochastic normalized gradient descent with momentum for large batch training. arXiv preprint arXhv:2007.13985, 2020.
[81] Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1-13, 2021.
[82] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In International Conference on Artificial Intelligence and Statistics, pages 4782-4817. PMLR, 2022.
15

---

A Proof of differential privacy
Proof of Theorem 3. Define the & sensitivity of any function g be Ag sups,s' (lg(S) -0(5')) where the supreme is over all neighboring ("). Then the Gaussian mechanism g(S) g(5) Ag Bag.Non (0,
denotes the "Noise multiplier", which corresponds to the noise-level when a Gaussian mechanism applied to query with sensitivity 1.
Observe that automatic clipping (AUTO-V and AUTO-S (4.1)) ensures the bounded global-sensitiitty of the stochastic gradient noise-level itself) ensures that the the noise-to-sensitiviy ratio eAg is fixed regardless of Ag. Ag
Abadi's clipping. Aligning the noise-multiplic (rather than the
The Gaussian mechanism's 's privacy guarantees equivalent. Thus from the privacy accountant perspective, DP-SGD with both Abadi's 's clipping and our autoclipping method can be equivalently represented the adaptive composition of I Poisson sampled Gaussian Mechanism with sampling probability B n and noise multiplier o.
B Proof of automaticity
B.1 Non-adaptive DP optimizers
Proof of Theorrm I. We prove Theorem by showing that, DP-SGD using R-dependent AUTO-S with learning rate y) and weight decay À is equivalent to R-independent AUTO-S with learning rate R and weight decay A/ R. We claim other non-adaptive optimizers such as HeavyBall and NAG can be easily shown in similar manner.
Recall standard SGD with weight decay
Öl
W ut: 7)
Σ
Aune
VEB.
Replacing the standard gradient
8L. Owa.
with the private gradient, we write the R-dependent case as
Ol,
O4,
Σ
R/ll ow,
1la + oR xR-N(0,1) Xw
Wi+1 W. 17
dw
Vi
0l,
04
= W: - nR
/
|l t -V(0.I))
-n/ww
ow.
ow:
BEB
which is clearly equivalent to the Rt-independent case:
wi+1 = -w:- -
Σ
ØL.
Ö4 Owr
112 + a -V 1) + N'w,
Iwe
1E Br
we use v/' n and X' A/R.
B.2 Adaptive DP optimizers
Proof of Theorem 2. We prove Theorem 2 by showing that, AP-AdamW using R-dependent AUTO- with learning rate y and weight decay is equivalent to R-independent AUTO-S with the same learning rate and weight decay A/R. R. This is the most complicated case. We claim other adaptive optimizers such AdaDelta, Adam with weight decay (not AdamW), and NAdam can be easily shown in similar manner.
Recall the standard AdamW is
m1/(1 -B1)
Wi+1 = w. -
+ Awa,
Vvrl(1 (z2
16

---

where 31, are constants, : Ei
04. Ow:
is the standard gradient,
m: = - + +(1 - -1)g: - m, = Σ ( -1- -1)g..
Vi 1300-1 (1 --22g v Σ 82 1 (1 32)99.
Replacing the standard gradient with the private gradient Rğ: := RiE: we write the Rt-dependent DP-AdamW as
o1. Bree
/1l
OL Bure
lla -N(0,
(1 - B1)
11+1 w. 17
Vor/(1 - -32)
where
m -,m Ri) - m Σ -1
B20,-1 (1 (1-B22) R2 8r Σ 81 R2)
Clearly, the factor in the numerator and denominator of m./(1-8.) cancel each other. Therefore we claim that the R-dependent DP-Adam is in fact completely independent R.
(1,((1-3)
B.3 Automatic per-layer clipping
In some cases, the per-layer clipping is desired, where we use clipping threshold vector R [Ri,... Rr. and each layer uses different clipping threshold. We claim that DP optimizers under automatic clipping works with the per-layer clipping when R tuned proportionally, e.g. R= R [a..... azl, but not entry-wist (see counter-example in Fact B.1). One special case is the uniform per-layer clipping when R1
R2 R// LT. This is widely applied as only norm R requires tuning, instead L norms in R. particularly the case of deep models with hundreds of layers. The corresponding DP-SGD with AUTO-S in (3.5) gives
( w 2+1 w.
9
+ tOR COR.N(O,TT)
VEB
VL
+7
Here the superscript (1) is the layer index. Clearly R couples with the learning rate r) and the same analysis in Theorem follows. The adaptive optimizers can be similarly analyzed from Theorem 2. Fact B.I. Changing one clipping threshold in the clipping threshold vector R (i.e. not proportionally) can break the coupling with learning rate.
Proof of Fact B.I. We prove by counter-example of R in I?, Consider DP-SGD with per-layer clipping thresholds (R1, R2) = (9, 12):
( w wi
Riga,
a R2 RG N(O.T)
iEB
Increasing R3 from to 16 changes the update for the first layer
"
9gt,i.1 + 15a .V(O. -17 gr,iall
Σ NEB
16g Ig...all
20
-N(0,))
FEB
The noise-to-signal ratio decreases from 5/3 to 5/4 for this layer, and increases from 5/4 to 5/3 for the second layer. This breaks the coupling with learning rate, since the coupling does not change noise-to-signal ratio.
D
17

---

C Main results of convergence for DP-SGD with automatic clipping
C.1 Main proof of convergence for DP-SGD (the envelope version)
Proof of Theorem 4. In this section, we prove two parts of Theorem 4.
The first part Theorem 4 is the upper bound on min, E(Igg: Il), which is a direct result following from Theorem 6, and prove it in Appendix C.2.
Theorem 6. Under Assumption 5.1, 5.2, 5.3, running DP-SGD with automatic clipping for T iterations gives
min B(lgel - 6 F
4 VT ((oo-L.) L.)L. (1+ o²d
B² :r,6.7
(C.1)
where
for r < 1,7 and n & 1/VT, F(s)
minocect farr and [(rr)
(1+re)
V+*+2re41
--3-2 for r 2 1, = 0 and y x 1/ F(x)
(1-re)
for r 2 1,, > and x 1/VT, F the convex envelope of (C.9), and is strictly increasing.
10
Upper bound (1ne
Upper bound mine: ((o)))
35
20-
-00
15-
-0 0
1-0.99ym00
111,1,
113,y
r=1011y-01
r-5.y=01
10
O11
0:11-
Figure 7: Visualization of upper bound & + (O(L/VT):r...)) for gradient norm, with O(1/vT) in (C.1). Here & = 1. The right plot is a zoom-in (with additional lines) of the left one.
Notice that, (C.1) holds for any > However, we have consider an envelope curve over in (C.1) to reduce the upper bound: with AUTO-V clipping (7 = 0), the upper bound in (C.1) is always larger than & as 1; we must use AUTO-S clipping (? > 0) to reduce the upper bound zero, as can be seen from Figure 7. In fact, larger T needs larger r to reduce the upper bound.
All in all, specifically focus converge to zero. This scenario also where we prove the second part of Theorem 4.
2 and 7 0, which is the only scenario that (C.1) can
The second part of Theorem 4 is the asymptotic convergence rate O(T-1/4) of DP-SGD, only possible under 2 and >> 0.
By (C.1) in Theorem 6, upper bound from Theorem 4 can be simplified
{ (M-))ee r>0 r
( 4 ( (+Viee (Co (Co-
C.)L (.))
o2d (1+
min
B ..
where the function M- is explicitly defined in (C.9) and the subscript cov means the upper concave envelope. Clearly, as T + co, ( O. We will next show that the convergence rate of
M is indeed O 1) and the minimization over r makes the overall convergence rate 1/44) }
18

---

Starting from (C.9), we denote r r= == -
L.) (1 ( and write
- 4 + (1² - 1) x + 1yx + V ($)2 25x 22xx + x²
M- (x;,,,,7))
27 - (r² 16.-11 1)2
25 + (r² 1) rya +7 1 /63+
E)²+2Ex 25xx 24 + x²2
+ 1--1
27 x: + +x²²)
24
75
+ (r² 1) 1) + ry + 75
2( + 7)r2x
+ 0xx2)
27
r
5²
7 1
(1 +
x + +0(x²))
27
2
+ (1² - - + m + 26 (1+ (5 (5+ 7)02x 7)
+ 0((3))
27
1
(1+
x + 0(1²))
27
(r2 1) - + rya + 7 + +0(22) (1+
x2
x + 0(O9))
2y
27
1
(+² (+2- 1) E
7/5 + ((5t))r) . 0(2))
2y
1
(5+7)²
p - 5 x x
((²2) (
2y
{
Since M 1 is asymptotically linear as x + O, we instead study
< + + (x; min e + (E + 7)2 r 5)) 5) x .
min r>0 r
+ O(x3).
r>0 r 2x
{
That is, ignoring the higher order term for the asymptotic analysis, the M-1 -1 part converges as O(x) O1/vTT), and we visualize this Figure 9.
Although DP-SGD converges faster than SGD, the former converges to e/r and the latter converges 0. Thus, taking &/r into consideration, the objective reduces hyperbola
{(1 2))
x(E 7)2
27
whose minimum over r is obviously 2
2/ E(1
0(V))=
24
To give more details about the upper bound in (5.2), demonstrate its dependence on & and 7 in Figure 8.
C.2 Main proof of convergence for DP-SGD (the non-envelope version)
Proof of Theorem 6. Consider DP-SGD with AUTO-S clipping
Σ
gt,i + o
W1+1 w.
o.. +7
where 9r,; is i.i.d. samples of gr, an unbiased estimate of gt. with a bounded variance as described in Assumption 5.3.
19

---

Upper bound minetlloull
Upper mimatillol
121
129
37-500 AUtO 6-1
39-500 Aitovv [-3
3F-500 AiMO- 5-10
37-500 AIROV, y--3
32-550 AUTOVV 5-10
37-520 AURO-, 3.01
500 AUTO d-
32.520 AUTO- 531
20
500 Auro- 10000
500 AUtO
Stantard sea
Soniam 560
10
107
10n
16
1641
lberatiions
Number iberat
Figure 8: Dependence of the upper bound g on & (left) and y (right). Here the O(1/VT) term is set to 10 and either 7 0.01 (left) (right).
,r!,r= 1.1
101
SGD grad norm
10-1
10-2
10
10a
10
10'
104
Number of iterations
Figure Convergence with respect to T. Same setting as Figure
By Lipschitz smoothness in Assumption 5.2, and denoting Z =0, I), we have
L wel?
C++1 Le S g. (Wi+1 - -w,) + |10+11
Ln
= = Σ Cig.. +0
Cight oZ
2
(1I Cggc
(C.2)
<n1..
Σ
C.gr, +02
+ Ln²
+0211Z113
n- T
Cig.
+ L (B² + t 1211
where the second last inequality follows from Cauchy Schwartz, and the last inequality follows from the re-parameterized clipping [17].
the fact that ||C. < 1, e.g. C2 is |lğr../ (I..)l + +
Notice that in the last equality, the first term (ignoring g. for its zero expectation) can be written in the same form as (3.3), which supports our motivation in Section 3.2; the second term is independent of clipping functions. Note that the last inequality is tight if and only if C; This empirically holds in Appendix H.1, especially for GPT2.
Given the fact that |l9..: + + 1, the expected improvement at iteration is
B(L++1 L.(we) <-19,, TE Σ
Jt.i
+ Ly² (B² d
@ +
(C.3)
= B.
+ Lni² (B² + +zdd
|g. ll +
Now we want to lower bound g,
| in (C.3).
20

---

Write 9: 9: + As where the gradient noise A, follows EA, 0, El|ll < & by Assumption 5,3. Then
9t 2 + 9: De
9:
E
EE
|grr|
|
+
19: A. +7
1
99 12 + g. A
1
9 22 + g. A
B
D HH+
D H- 19 gi D
2
g + Arl +7
9r + Drl +
9+ 2 9t A
2
g + A.ll +7
A. H4
+
9r Aell +7
A E 11+
where we use the hyperplane perpendicular to gr to divide the support of A, into two half-spaces:
H+ == (v 9: 0 0), =
= {v g < 0}.
We use the symmetry assumption Assumption 5.3 to get
P(A, E H+) = P(A. H.)
and notice that A, 2 - i... if A. H4, then - H_ with the same distribution.
The next result further gives a lower bound for g. 11..1 using glgel.
Lemma C.1.
[ell" 2 + gr A
1 g. A.
E
+
D H+
2
min f(c,
(119el - E/r)
[gg A, +7
19 A.ll +
ocesi
[gill
for any r > 0 and f(c,r;)))= V+*+2r++++
(1-re)
(1-re) V1=-2rot+tT"
For the simplicity of notation, denote the distance measure
M(llgul - E/r:n,En)) min f (c.r: (0m))))) (119:) EE/r)
(C.4)
o<egi
and leave the fine-grained analysis (e.g. its explicit form in some scenarios) at the end of this section. Using the lower bound from Lemma C.I, the expected improvement (C.3) becomes
nB B(C.+1 - L, (..) s - - MM - g/rr Lxp B²
a²d
1+
B
Now extend the expectation over randomness in the trajectory, and perform telescoping sum the iterations
Co - L. 2 Lo ELT
B(c. - L(+1)
BB 2
Σ Millall s/m) -E/r) TL B² (1+
o²d B
>
Substituting nBB //// V where yh is a base learning rate, we have
2(Co L.) VI
T Σ
M(llgall - -E/r) 2LT
1+ o²d
132
and finally
E
M(llg:11 -E/r)
<
2(Lo L.)
+ 2Lmp
1+
o²d
(C.5)
T
VT
110
Ba
21

---

With To chosen properly at 70 = /
Lo-L, (+
the hyperbola on the right hand side in (C.5) is
[1(1+ 1x
minimized to 4v (Lo - L.)L. (1 3 and we obtain
vT (Co L.) (1+ o²d
Σ Mileall - -
E
B²
Since the minimum of sequence is smaller than the average, we have
1 - -/-r) S T Σ ((M(alllEEE)))) =
4 VT
(Cu ((CC-C))) L.)L (1+ o2d
min -
(+ B²
(C.6)
We claim that MM may not be concave or convex. Therefore we use Meuz denote its lower convex envelope, i.e. the largest convex function that is smaller than M. Then by Jensen's inequality (C.6) becomes
o²d
min (B(lelll E//r) S min M(Mez (1led - E/r)) < /T
(Co (C)-
L.)L (1
B
(C.7)
is obvious that Move is increasing as M is increasing by Theorem 8. Hence, (Move) -1 is also increasing, as the inverse of Mezz- We write (C.7) as
o²d B
min E(1g: - E/rr (Meux) -1
/T V (Co L.)L (1+
and equivalently
min E(Ilg)l)) S E (Mazz)
(VTV (Co L.) (1+
o2d
(C.8)
B²
Finally, we derive the explicit properties of M(Ig -E/r) in Theorem 8. These properties allow us to further analyze on the convergence of M(llgil - E/r), based on AUTO-V and AUTO-S, respectively.
1. DP-SGD with AUTO-V clipping. By Theorem 8, we write
M(x
min f(c, 0) cE(0,1
This is a linear function and thus Mana M = 1/M cor
As a result, we have
1
(Co ( (.)-..... (.)
o2d B
min B B(1gg:
min (c,r;;))
VT
We note here r plays an important role under AUTO-V clippnni: when r < we spend more iterations to converge to better and smaller gradient norm &/r: when 2 1, mine f'c, r) f(1,;;)) 0 and it takes forever to converge. This is demonstrated in the left plot of Figure 6.
2. DP-SGD with AUTO-S clipping.
By Theorem 8 and for > 1, we write
M(I;n.E.n) = (r- ()(x (Tr +/rr (r 1)(x + +
Notice that the inverse of lower convex envelope is equivalent to the upper concave envelope (denoted by the subscript ccv) of an inverse. Therefore we can derive (Mavs) (M- )oor with explicit form
M (xsr,)))) -5r + (r2 1) + ryy + +7v (5)2 + 2 - 2 + x²
(C.9)
27 (r² 1)x
22

---

we can derive it based on & T and substitute back to (C.8).
Note that the domain of M 11 (or the image of M) is [0; 1 -
In comparison to the AUTO-V clipping, M takes much more complicated form, as depicted in the middle plot of Figure 6, where > 1 plays an important role for the gradient norm to converge to zero.
C.3 Proof of Lemma C.1
Proof of Lemma C.I. We want to lower bound
|g 2| g. A.
|1g:11 g. A
A H+
(C.10)
[g. + Arl +
19. - A. +
To simplify the notation, we denote noise-to-signal ratio 5 = ||+|| 0 be the random angle between g: and A, Note that 0 < S when A, E H
and c == cos A
g. A.
with
|1g-1l
1 |Il
The term inside the conditional expectation in (C) be written
(1 9t
(1 - Sc)
VSa + 2Sc
11 +7
VS2 - 2Sc + 1 +7
(1+ Sc)
(1- (C)
=166||
VS2 2Sc 7/ 9ill
V52 -Sc-2Sc 7/ gel
Defining l' >>/ll: and
(1 (1)
(1-
f(c, ST
(C.11)
V +
VSa - 2Sc + 1+r
the conditional expectation in (C.10) into
9: 2 + gi
Ar +
12 9:
A
+
A
E H+
I9:: E H4)
(C.12)
gg + A.ll
9g:
A.l
for which we want to lower bound fc. S) over 0 < c 1,5 0,1 We use the next theorem prepare some helpful properties. The proof can be found in Appendix E.1.
Theorem 7. For f defined in (C.11), we have
1. ((c,S:D) is strictly decreasing in S for all 0 < c < and I >> 0.
2. Consequently, min.e1o.1) f(c, S:T) is strictly decreasing in S.
3. STT, is strictly decreasing in for all S >>> and r >> 0.
We consider thresholding ratio > 0 and we will focus on the regime that S < This will turn out to measure the minimum gradient norm at convergence: informally speaking, |[gi]] converges to e/r.
23

---

By the law of total expectation, (C.12) can be relaxed as follows.
l1
(t) A A H+)
= -Ilgi | (f(c, A H. <r) P(rllg.)l ||ا|||||||| E H4)
+ +11..
(f(c, A -,, P(rllg.1l
||||||||||| A E H+)
2 2lg. [B
H. 5kr P(rllg:1l ||ه||| E H+)
(C.13)
2 ll |E (f(er)I))
A H <
P(rlggd |||| A H+)
= 11 | (f(e,1;))
E H+, S <r)
P(rllgell > ||]]
2 min [(,r;
g (r 9 ||ll)
cE(0.1]
where in the first inequality, the ignoring of last term is justified by ((c,S:D) > min.gro.1] f(c, S:D) 2 min.sto.1) f(c, oo; D) = 0, from the monotonicity (second statement) in Theorem 7.
first lower bound + by applying the Markov's inequality:
P(rllgell > || 2
9:
and hence by Assumption 5.3,
19. |Prllll) > ||xl]) || /// 2 1gell E/r.
Finally, the conditional expectation of interest in (C.10) gives
E
gell + g: A.
| 1 - 9. A
A E H+]
min o<eg1
Y f(e, r;
(llgel - E/r)
19 + A
9 Ael
[gg
C.4 Proof of Theorem
To derive some properties of mine f(c, D), we need to compute separately for AUTO-V (without stability constant, r 0) and for AUTO-S (with the stability constant, P 0), as shown in Theorem 8. As we will show, the number of training iterations T - xc, DP-SGD with AUTO-V clipping can only compress ||g:]| to e/r for r However, DP-SGD with AUTO-S clipping can compress ||ge| ε/r to any 1. Theorem 8.
1. For <r< < 1 and bounded by
have minceto.1) (c; 0. Then Equation (C.12) is lower
min f(c,r;)) (llgel) g/r) cE(0.1]
which increasing in ||g|| g/r.
2. For and I 0, have min 1) fc,,r; I) f(1rr;0) 0. In words, (C.10) has trivial lower bound and Theorem 6 cannot compress [|g: č/r.
3. For 2 and r Equation (C.12) is lower bounded by
have min H(rr; f(1,r; (1 ,4f+1)
Then
7 (x- ( 1)llgel1 (r-1)] +y (r 1)llgil ) (119.1) g/r)
which increasing in ||g:1| - g/r.
Proof. To prove statement we use the second statement from Theorem 7 and show that min, [(, r; 0) min, (c, oo; 0) = 0. To prove statement 2 and 3, we use the third statement from Theorem and see that min. flc f(L,r; with an explicit formula.
24

---

D Convergence rate of standard SGD
Theorem 9. Under Assumption 5.1, 5.2, 5.3 (without the symmetry assumption), running the standard non-DP SGD for T iterations gives, for 1j x 1/VT,
5²
min E (1l - / 2(o - L.)L+
B
Proof of Theurrm 9, Consider the standard SGD
E, 9t.
W[+1 = we 1)
B
where Hr,i is ii.d. unbiased estimate of gt. with a bounded variance as described in Assumption 5,3. By Lipschitz smoothness assumption in Assumption 5.2,
L++1 - Lu S g: (we+1 - -w:) + _ w++1 wt, 1|2 ~19
Σ
1
Tap
Σ
gr.
+
gt,
B
The expected improvement at one iteration is
Lnj² B1 Σ
E(C++1 L((we) s -ng, Bgi,; +
B
(D.1)
Lip [1g.1]
52
S -nllgell? 2
2
Now extend the expectation randomness in the trajectory, and perform telescoping over the iterations
Σ E(GG- ( (1
Ln²²
TL
Lo ECT
E
llg 11
2B
Notice that we do need the symmetry assumption Assumption 5.3 in the non-DP SGD analysis. We apply the same learning rate as in [5], IVT
TE²
VT
E²
2(Cu - 2.)
Σ
Igill??
E
Σ
LVT
LT
BLT
L
T
BL
and finally
2²7
min E (1l9:1' 11
< E
Igill
2(Co L.)L
T
VT
B
Using the Jensen's inequality, can have
1
min E (llg)l)
<
2(Lo - -C.)L+
T1/4
B
E Auxiliary proofs
E.1 Proof of Theorem 7
Proof. We first show dfcc.S:) 0 for all 0 < c < 1, > 0 and S 0, as visualized in the left plot of Figure 10. We can explicitly write down the derivative, by WolframAlpha
(c, S:
2 + +
dS
- 2cS + 1V5 2c5 1(T V5a 2cS 1) V
2cS 1)2
(E.1)
25

---

with
Alc,
+ -65 +1 (3e S + 2c(8 +1)+
B(c,5) 48 -| -
C(c,S) (1 (1- -S2 2c8 + 2c8 +
is obvious that, since 1,
5 + 2cS +1> 8 = 2cS + c² o) 20
(E.2)
From (E.2), the denominator in (E.1) is positive and it suffices to show A + BT + C' 0 for all
0 < < 1 and S > 0, in order to show
4f as < O.
Also from (E.2), we can easily see Bec, S) Lemma E. 1. after very heavy algebraic computation.
and C(e, S) 0. We will show that A(c, 8) > in
Now claim that AT BT C > by Fact E.3, and complete the proof of the first statement.
To further see that min, f(c, S: is decreasing in S, let us denote c=(x; min mem. I). Then considering S < S", we prove the second statement by observing
min f(e, S;T) (); > f(c"(S:
2 min flc,
This statement is also visualized in the right plot of Figure 10.
We next show (fc,,S 0 for all 0 < < 1.1 > 0 and 1. We can explicitly write down the derivative, by WolframAlpha
de
ScT, de
5(AT BT
VS² - 2c5 2 1(T
VSa 2cS 2c5+1122 1)2(+ VS2 2c8 1)2 (E.3)
with
+2 S)(c,S) (S + - (82 3c8 + 2)V 52 2c8 +258+1
B'(c, 4Sc V 2.5 $ 208
(5 -11) 1)] +1 205
C) = (c+ (S 2c5 1)3/2 + +cc (c- SS2 + 2cS + 1)3/2
Clearly (c,, 5) and (c, 0. since 52 2c5 + 52 2cS è (S c) 0. And
we will show ('cc, 5) > 0 in Lemma E.2, after some algebra.
We again claim that AT + BT + by Fact E.3, which guarantees that the numerator in (E.3) is negative and that of 0. This is visualized in Figure 11.
2.-
r
0.1
0-1.1
R,
1.58
144
[=1
1.22
[=1
1.2
1.02
min
0.5
0.6
0.2
84-
0.33
1.3
S
Figure 10: Visualization f(0.5, S, (left) and minosesi (c, over S >
26

---

2.
(c,
1.3
0.1
0.1
0.2
[=1
Figure 11: Visualization of f(c, 0.8, (left) and f(c,2,T) over 0 scs 1.
E.2 Proof of Lemma E.1
Lemma E.1. For all 0 < c and 5 >
A 52 + 2c8 + (3c2 20( +1 +) 2c8 2 + S) >
Proof.
We prove by contradiction. Suppose
v 5 2cB (3c2s 20 + -
<0.
Then
<< -
2c8 205 2c - +1) +1)+
where the first inequality comes from f c)2 20.
Squaring everything gives
(S² 2cS 1) (3c25 + 2c(S² +1) S)² (52 2cS + +1) (3e25 - 2c(S2 + 1) + S)²
Taking the difference gives
4cS(2 + 35 - 52 + 25 26 + +5)) <0
Given that > 0, 0, we have
2 + 352 5² + 25 + 2c - - + S < 0
Denoting X S2 and viewing the above as quadratic polynomial of X, we have
2)x²2 (3 20 9c (2c² + 2) <
Using the frosed-form minimizer of quadratic polynomial (,, after some heavy algebra, one can check the minimum of ! is
(1+ 3c2)211 - -1) 9c²)
8(1+
which is clearly positive. Contradiction!
E.3
Proof of Lemma E.2
Lemma E.2. For all 0 < c < and S > 1,
(52 +c5 + 2) / 52 2cS + (S2 3cS + 2) 2 2cS +1>0 0.
Proof. Notice that (S2 + 3cS +2) > 82 + > 0 and S 225 > 0. Therefore if S2 - 3cS
2 < are done.
Otherwise, we prove by contradiction and suppose
(S2 + 3cS 2) 2c5 + 1 < (52 - + 2) 52 + 2c5 +
27

---

under the condition that S² 3cS +2> 0.
Squaring everything gives
(5 3cS + (5² -c5 + 1) < (5 3cS + 2)² + 2c5 +).
Taking the difference gives
cS(8 - 20. - 36 + 85") <0
Given that 0,S 0, we have
+ 5.5 96 + 25 <
Denoting X = 52 and viewing the above quadratic polynomial of X, have, for X >
2x + (5 96 ) + <0
The closed-form minimizer of quadratic polynomial 2 (9c2-5) Given that c < must
have - 95 < 1. Hence the minimizer is not within the feasible domain (1) of X. Thus
the minimum of ② is achieved with X = at 9(1 e²). This is positive. Contradiction!
E.4 Proof of Fact E.3
Fact E.3. For a quadratic polynomial Ax + Bx + with A, B, > 0, the minimum value on the 0. Therefore Az + Br C 0.
domain 2 0 is C, at
Proof. Since 0, the quadratic polynomial convex and increasing on the domain x > 24' и 24 < and hence the quadratic polynomial is strictly increasing on
Since B > 0 as well, we know
> 0. Therefore the minimum value is achieved when x = 0, and we obtain Ax + Bx+C C'> 0 for all x 2 0.
E.5
Assumption of symmetric gradient noise
We show that Assumption 5.3 is actually relaxed from and less strict than the assumptions used the non-DP literature. In words, Assumption 5.3 allows our DP convergence to be comparable to the standard convergence (as in Thcorem 9), because our assumption does not enforce extra constraint.
In standard non-DP analysis [48, 66, 12, 73], the mini-batch gradient is assumed to be an unbiased estimate of the oracle gradient Ow
ac
B
Σ
9: + E(w)
B
and & is the random gradient noise with E ~ N(O, (ww)/B) Since this assumption holds for any batch size B, we can set B to recover the per-sample gradient noise: -r, - gr is i.idd. and symmetric because zero-mean Gaussian is symmetric.
In fact, proof of convergence will follow we instead assume the mirror symmetry about the hyperplane normal gr, that is {u g. v 0}.
further relax Assumption 5.3: besides assuming the central symmetry, the same
F Examples of lazy regions
F1 Balanced binary classification
We describe the data generation in Section 3.3. The label is uniformly +1, that is P(y: +1)
P(y: -1) 0.5. We have 10000 positive and negative samples .i ~ (v,, 1). We consider
logistic regression model TP(Y = y/a) = T(y = 1) Sigmoid(s: + 0) + T = 11) -
Sigmoid(x: +
0)) I+e अलक.क.. where R is the intercept. The gradient with respect to this only trainable
parameter is
dc. 30
- Ite I+e-woo+a) - ). We set the clipping threshold R 0.01 and the stability
constant 7 0.01.
28

---

F.2 Mean estimation on Gaussian mixture data
rzll?. Here P(z; ~ (44, 1)) = P(æ, ~ (44, 1)) = 0.5. We have 10000 samples from each Gaussian distribution. The regular minimum is clearly E, 24 O, where the regular gradient and AUTO-S clipped gradient vanish. Yet both AUTO-V V and Abadi's clipping lose motivation to update the mean estimator on the interval (-1,1), We set the clipping threshold R 0.01 and the stability constant - 0.1.
We also observe the lazy region issue in the mean estimation problem ming 2110
10
-10
10a
-00
standard rd grad
clipped (Abadi)
-10
clipped (AUTO-V)
10-
clipped grad (AUTO-S)
10a
-1.5
0.5
1.5
2.0
Figure 12: Scalar gradient ac
as at each A.
G Experiments settings
G.1 Image classification settings
We give the experiments settings for computer vision tasks in Table
MNIST:
We the network architecture from [56, 68, 64], with 40 epochs, 512 batch size, 0.5 learning rate (or 0.005 non-DP learning rate), 0.1 clipping threshold, DP-SGD with 0.9 momentum, and without pretraining. This setting is the same [68].
FashionMNIST: We use the same network architecture as MNIST, with 40 epochs, 2048 batch size, 4 learning rate (or 0.04 non-DP learning rate), DP-SGD with 0.9 momentum, and without pretraining. This setting is the same as [68].
CIFAR10 pretrained: We use the SimCLR model from [13]?, with 50 epochs, 1024 batch size, 4 learning rate (or 0.04 non-DP learning rate), 0.1 clipping threshold, and DP-SGD with 0.9 momentum. The SimCLR model is pretrained on unlabelled ImageNet dataset. After pretraining, we obtain feature of dimension 4096 which linear classifier trained privately. This setting is the same as [68].
ImageNette:
We use the ResNet9 (2.5 million parameters) with Mish activation function [52].
We set 50 epochs, 1000 batch size, 0.0005 learning rate (or 0.000005 non-DP learning rate), 1.5 clipping threshold, and use DP-NAdam, without pretraining. This setting is the same as [36] except we did not apply the learning rate decaying scheduler.
CelebA (Smiling and Male and Multi-label) We use the same ResNer9 as above, with 10 epochs, 500 batch size, 0.001 DP learning rate (or 0.00001 non-DP learning rate), 0.1 clipping threshold, and use Ad-Adam, without pretraining. We use the labels 'Smiling' and 'Male' for two binary classification tasks, with cross-entropy loss. For the multi-label task uses scalar loss by summing up the 40 binary cross-entropy losses from each label.
We refer the code for MNIST, FashionMNIST., CIFARIO, CIFARIO pretrained to https:// gi github. com/ftrament Serramer/Handcrffteeee. htmm/cbbnite221/Reeeee
by [68]. ResNe19 can be found in https: //ithub.
"See implementation in https: ptttp://giiee //gtthub//bbbt.ee////
29

---

Throughout all experiments, we do not apply tricks such as random data augmentation (single or multiple times [17]), weight standardization [61], or parameter averaging [60].
G.2 Sentence classification settings
experiment on five datasets in Table 2 and Table 3.
MNLI(m) MNLI-matched, the matched validation and test splits from Multi-Genre Natural Language Inference Corpus.
MNL[(mm) MNLI-mismatched, the matched validation and test splits from Multi-Genre Natural Language Inference Corpus.
QQP The Quora Question Pairs2 dataset.
QNLI The Stanford Question Answering dataset.
SST2 The Stanford Sentiment Treebank dataset.
The datasets are processed and loaded from Huggingface [39], as described in https:// huggingface co/ dataastts/ We follow the same setup as [78] and [41]. We refer the interested readers to Appendix G.H.I.KNN [41] for more details.
We emphasize that our automatic clipping uses exactly the same hyperparameters as the Abadi's clipping in [41], which is released in their Transforrrss library
Dataset Epoch
MNLI((/mm)
QQP
QNLI
SST2
18
18
6
3
Batch size
6000
6000
2000
1000
clipping threshold R
0.1
0.1
0.1
0.1
DP learning rate
5e-4
5e-4
5e-4
5e-4
non-DP learning rate
5e-5
5e-5
5e-5
5e-5
learning rate decay
Yes
Yes
Yes
Yes
AdamW weight decay
0
Max sequence length
256
256
256
256
Table Hyperparameters of automatic clipping and Abadi's 's clipping, for sentence classification in Table 2 and Table 3, using either RoBERTa base or large.
Notice that DP learning rate 5e-4 across tasks for the R-dependent automatic DP-Adam, which equivalent to R-independent automatic DP-Adam with the same learning rate. We demonstrate that the results not sensitive learning rates around the optimal choice. That is, the automatic clipping does not eliminate R at the cost of more difficult tuning of learning rate.
leamiing rate CoBERTa-basse
le-4
3e-4
5e-4
8e-4
1e-3
93.92
94.38
94.49
94.72
93.35
RoBgRTa-large
95.76
96.21
96.21
96.33
95.99
Table 6: SST2 accuracy with respect to learning rate.
G.3 Table-to-text generation settings
We experiment multiple GPT2 models on E2E dataset from Huggingface [39] in Table 4. We follow the same setup as [41], and our automatic clipping uses exactly the same hyperparameters as Abadi's clipping in [41], which is released in their Private-Transformee library "
*See http://uruuurrrppppppppppp
classificationn/uu.rrraaa 'See table2text/run.th http:://hhhhoooacccccccccccttttr
30

---

Model
GPT2
GPT2 medium
GPT2 large
Epoch
10
10
10
Batch size
1024
1024
1024
clipping threshold I
0.1
0.1
0.1
DP learning rate
2e-3
2e-3
2e-3
non-DP learning rate
2e-4
le-4
le-4
learning rate decay
No
No
No
AdamW W weight decay
0.01
0.01
0.01
Max sequence length
100
100
100
Table 7: Hyperparameters of automatic clipping and Abadi's clipping, for the E2E generation task in Table
H
Figure zoo
H.1 Frequency of clipping
We show that in all sentence classification tasks, Abadi's clipping happens on a large proportion of per-sample gradients. This supports the similarity between Abadi's clipping and AUTO-V (3.1).
1.0
1.0
Percentage of ge. clipped
Percentage of gt: clipped
Myyla Ma
0.8
0.7
0.6
M ha in 11/l
MT Hw Ir M WwMM hw
0.4
0.-
100 Iteration
150
Iteration
1.0
clipped
Percentage of Q::1 ciloped
0.8
0.7
M mw wwm.mmmmm you
0.5
WW
0.2
0.2
0.0
20
60
80
100
50
73
100
125
150
Iteration
Iteration
1.0
Percentage of St.1 clipped
Percentage Ge. clipped
0.8
MMw M
0.-
Oar A
wmp w
0.
02
200
Iteration
Iberatton
Figure 13: Percentage of clipped per-sample gradients when training with AP-A (c = 3).
as in Section 6.2. Left panel RoBERTa-baan base and right panel is RoBERTa-large. Top row: MNLI. Middle row: QNLI. Bottom row: QQP.
31

---

We note that for GPT2, GPT2 medium and GPT2 large, empirically in all iterations 100% of the per-sample gradients are clipped by the Abadi's ss clipping, making the performance of Abadi's clipping equivalent to AUTO-V clipping, as shown in Table 4.
H.2 Stability constant helps AUTO clipping reduce gradient norm
To corroborate our claim in Theorem 6, that the stability Y reduces the gradient norm, we plot the actual gradient norm by iteration.
A AUTO $
AUTOVN
333832
50XC
AUTO
50XCE
133892
200
100 Iteration
Deeraion
Figure 14: Gradient norm by different automatic clipping methods, on SST2 (left) and MNLI (right), trained with RoBERTa-base.
H.3 Choice of stability constant is robust
We claim in Theorem that, as long as y >> O in our automatic clipping, the asymptotic convergence rate of gradient norm is the same as that by standard non-private SGD. We plot the ablation study of learning rate and the stability constant y to show that is easy to set yy in Table 2 and Table we adopt learning rate 0.0005, under which wide range of 0.0001 < y < 1 gives similar accuracy. Note that the largest good r is 1000 times bigger than the smallest good 7.
Learning rate
0001
60.5
10.3
60.7
91.0 91.4 92.4 0LG 06
0.001
90.0
92.3
92.3 62 023
92. 61.7 06
1.92
1.0003
9.1
12.1
52.3 92.4 92.4 92.7 03. 92.
0.0005
91.
915
53. 655 916 11.4 51. 01.
2.003
51.3
31.4
91.4 920 222 528 231
92.4
5.84
0.002--22
-237
24.
24.5 565 945 75.0 15.1
5.000
96.7
20.3
01.
DLA
21.4
52.3
922
91.
a.cent
-930
94.5 15.1 95
50001
3,09
0%
10
100
10:00
5.92
0000
500
5000
Stability constant
Stability constant
2.02
0.50
1.83
0.85
Learning rate
6:01-
65.9
15.2
052
25.3
86.7
72.0
0.000
85.7
15.1 803
5,000
66.0
16.3
661 812 26.3 862 040 78.
0.0005
09.7
90.3
10.5 602
5.73
2,0002
64.5
24.3
03. 25.1 85.2 040
77.4
2.5
0.0002
00
03.2 29.3 803
2,001
63.8
12.4
035 23.7 62.5 602
71.
0.0001
-7.
03.0
16.1 60
260m
693
:09
10.09
2.53
0.30th
0gth
1999
035
Stability constant
0.52
Stability constant
0.50
Learning rate
6001
14.3
14.3
001
045
02.7
01.
50.4
1.83
rate
00.0
92A
26.1
005
015
0 800
64.5
44.3
664
815 24. 623
78.0
65.0
5.79
94.0
2611
60
02.0
700
0.75
3.63
1.8
0.00
2.003
60l
0.
50
100
50000
Stability constant
2.52
Stability constant
030
Figure 15: Test accuracy by different stability constant and learning rate 17 in automatic clipping = 3). Upper row: SST2 for full 3 epochs. Middle row: QNLI for full 6 epochs. Lower row: QNLI for one epoch. Trained with RoBERTa-base (left) and RoBERTa-large (right).
32

---

I Full table of GPT2 generation task on E2E dataset
This is the extended version of Table 4 on E2E dataset. The performance measures are BLEU [57],
ROGUE-L [42], NIST [63]. METEOR [4], and CIDEr [70] scores. Here is accounted by RDP [51]. where e = 3 corresponds to 2.68 if accounted by Gaussian DP [19, 7] or to 2.75 if accounted by numerical composition [30], and 8 corresponds 6.77 if accounted by Gaussian DP or to 7.27
accounted by numerical composition.
DP
GPT2
GPT2
GPT2
Metric
guarantee
large
medium
Tull
full
full
full
full
LoRA
RGP
prelix
top2
retrain
AUTO-S
AUTO-S
AUTO-S
AUTO-V
[41]
[33]
[78]
[40]
[41]
[41]
c 3
64.180
63.850
61.340
61.519
61.519
58.153
58.482
47.772 25.920
15.457
BLEU
E - 8
64.640
64.220
63.600
63.189
63.189
63.389
58.455 49.263
26.885 24.247
non-
66.840
68,500
69.463
69.463
69.463
69.682 68.328 68.845 65.752
65.731
c 3
67.857
67.071
65.872
65.670
65.670
65.773 65.560 58.964
44.536 35.240
ROGUE-L.
E 8
68.968
67.533
67.073
66,429
66.429
67.525 65.030
60.730
46.421
39.951
non-DP
70.384
71.458
71.359
71.359
71.359
71.709
68.844
70.805
68.704
68.751
E 7.937
7.106
7.071
6.697
6.697
5.463
5.775
5.249
1,510
0.376
NIST
c 8
8.301
8.172
7.714
7.444
7.444
7.449
6.276
5.525
1.547
1.01
non-DP
8.730
8.628
8,780
8.780
8.780
8.822
8.722
8.722
8.418
8.286
E 3
0.403
0.387
0.387
0.384
0.384
0.370
0.331
0.363
0.197
0.113
METEOR
c 8
0.420
0.418
0.404
0,400
0.400
0.407
0.349
0,364
0.207
0.145
non-DP
0.460
0.449
0.461
0.461
0.461
0.463
0.456
0.445
0.443
0.429
c 3
2.008
1.754
1.801
1.761
1.761
1.581
1.300
1.507
0.452
0.116
CIDEr
E 8
2.163
2.081
1,938
1.919
1.919
1.948
1.496
1.569
0.499
0.281
non DP
2.356
2.137
2,422
2,422
2,422
2,491
2.418
2.345
2.180
2.004
Table Test performance on E2E dataset with GPT2. The best GPT2 models for each row marked in bold.
We observe that GPT2 (163 million parameters), GPT2-medium (406 million), and GPT2-large (838 million), Table trained with our automatic clipping consistently perform better in comparison to other methods. In some cases, LoRA trained with Abadi's 's clipping also demonstrates strong performance and it would be interesting see how LoRA trained with the automatic clipping will behave.
J Further experiments on CelebA dataset
In this section, we present a complete summary of accuracy results, with DP constraint or not, for the CelebA dataset. We do not apply any pattoprrpro..sssnn... In the first experiment, we apply a single ResNet on the 40 labels as the multi-task/multi-laby learning. In the second experiment, we apply one ResNet on one label. As expected, our automatic DP optimizers have comparable test accuracy to the Abadi's 's DP optimizers, but do not need to tune the clipping threshold for each individual task/label. We also notice that, learning different labels separately gives better accuracy than learning all labels together, though at the cost of heavier computational burden.
33

---

J.1 Multi-label classification
We apply ResNet9 as Appendix G.I on the multi-label classification task. Lee the output layer has 40 neurons, each corresponding to one sigmoid cross-entropy loss, that are summed to single loss and all labels are learnt jointly.
Abadi's s
AUTO-S
Abadi's 8
AUTO-S
non-DP
Index
Attributes
6 3
= 3
6
0
o Clock Shadow
90.64
90.997
90.81
91.28
93.33
Arched Eyebrows
75.15
76.311
76.84
77.111
81.52
2
Attractive
75.85
76.101
77.50
77.74
81.15
3
Bags Under Eyes
80.75
81.121
82.15
82.13
84.81
4
Bald
97.84
97.871
98.04
97.98
98.58
5
Bangs
92.71
92.684
93.46
93.551
95.50
6
Big Lips
67.51
67.781
68.34
68.44
71.33
Big Nose
78.01
80.231
76.69
80.59
83.54
8
Black Hair
81.92
80.95
83.33
83.28
88.55
Blond Hair
92.25
92.381
93.52
93.09
95.49
10
Blurry
94.91
94.82
95.08
94.90
95.78
11
Brown Hair
80.13
82.501
83.74
83.89
87.79
12
Bushy Eyebrows
88.06
88.231
89.72
88.80
92.19
Chubby
94.72
94.54
94.54
94.50
95.56
14
Double Chin
95.19
95.491
95.50
95.51
96.09
15
Eyeglasses
97.06
97.641
98.32
98.06
99.39
16
Goatee
95.68
95.45
95.84
95.871
97.06
17
Gray Hair
96.77
96.791
97.02
97.031
98.06
18
Heavy Makeup
84.96
85.701
87.58
87.291
90.76
19
High Cheekbones
81.46
81.42
82.62
82.72
86.62
20
Male
92.05
92.171
93.32
93.17
97.46
21
Mouth Slightly Open
86.20
86.321
87.84
88.48
93.07
22
Mustache
96.05
95.96
96.08
95.99
96.74
23
Narrow Eyes
84.90
84.78
85.14
85.18
86.98
24
No Beard
91.55
91.671
92.29
92.45
95.18
25
Oval Face
71.26
71.421
71.98
71.25
74.62
26
Pale Skin
96.09
96.04
96.15
96.171
96.93
27
Pointy Nose
70.34
72.11
72.23
73.01
75.68
28
Receding Hairline
91.53
91.374
91.75
91.74J
92.87
29
Rosy Cheeks
93.26
93.02
93.56
93.35
94.86
30
Sideburns
96.16
96.094
96.27
96.46
97.44
31
Smiling
86.39
87.081
88.87
88.63
92.25
32
Straight Hair
76.20
77.951
78.78
78.52
80.66
33
Wavy Hair
70.30
71.791
73.58
73.194
79.15
34
Wearing Earrings
80.53
81.521
82.29
82.20
87.56
35
Wearing Hat
96.99
96.83
97.46
97.31
98.68
36
Wearing Lipstick
88.95
88.04|
89.87
90.72
93.49
37
Wearing Necklace
84.59
85.831
85.93
85.42
86.61
38
Wearing Necktie
93.91
93.91
94.43
94.08
96.30
39
Young
81.35
81.21]
82.18
82.52
87.18
Table 9: Accuracy on CelebA dataset with settings in Appendix G.1 from one run. The green arrow indicates AUTO-S better than Abadi's clipping under the same e; the red arrow indicates otherwise; the black bar indicates the same accuracy.
34

---

J.2 Multiple binary classification
For the second experiment, apply ResNet9 on each label binary classification task. Le.. the output layer has neuron and we run 40 different models for all labels separately.
Abadi's s Single
AUTO-S Single
Abadi's Multi
AUTO-S Multi
non-DP
Index
Attributes
Multi
8
0o
0
5 Clock Shadow
92.15
92.291
90.81
91.28
93.33
Arched Eyebrows
81.18
80.19
76.84
77.11
81.52
2
Attractive
79.31
79.791
77.50
77.74
81.15
3
Bags Under Eyes
83.52
83.48
82.15
82.13
84.81
4
Bald
97.89
97.88.
98.04
97.98
98.58
5
Bangs
94.52
94.831
93,46
93.551
95.50
6
Big Lips
67.32
67.531
68.34
68.441
71.33
7
Big Nose
82.31
82.361
76.69
80.59
83.54
8
Black Hair
87.08
86.934
83.33
83.28
88.55
9
Blond Hair
94.29
94.731
93.52
93.09
95.49
10
Blurry
94.95
95.201
95.08
94.90
95.78
11
Brown Hair
87.41
87.194
83.74
83.891
87.79
12
Bushy Eyebrows
91.23
91.431
89.72
88.80
92.19
13
Chubby
94.70
94.70-
94.54
94.50
95.56
Double Chin
95.43
95.43-
95.50
95.51
96.09
15
Eyeglasses
98.88
99.141
98.32
98.06
99.39
Goatee
96.12
96.07
95.84
95.871
97.06
17
Gray Hair
97.48
97.34
97.02
97.03
98.06
18
Heavy Makeup
88.85
88.72
87.58
87.29
90.76
19
High Checkbones
85,66
85.45
82.62
82.72
86.62
20
Male
95.42
95.701
95.53
93.17
97.46
21
Mouth Slightly Open
92.67
92.741
87.84
88.48
93.07
22
Mustache
96.13
96.13-
96.08
95.99
96.74
23
Narrow Eyes
85.13
85.13
85.14
85.18
86.98
24
No Beard
94.26
94.581
92.29
92.45
95.18
25
Oval Face
70.77
73.051
71.98
71.25
74.62
26
Pale Skin
96.38
96.34
96.15
96.171
96.93
27
Pointy Nose
71.48
73.371
72.23
73.01
75.68
28
Receding Hairline
91.51
91.51-
91.75
91.74
92.87
29
Rosy Cheeks
93.26
93.351
93.56
93.35
94.86
30
Sideburns
96.46
96.34J
96.27
96.46
97.44
31
Smiling
90.82
90.871
88.87
88.63L
92.25
32
Straight Hair
79.01
79,01
78.78
78.52
80.66
33
Wavy Hair
77.55
78.831
73.58
73.19
79.15
34
Wearing Earrings
87.33
87.501
82.29
82.20
87.56
35
Wearing Hat
98.04
98.111
97.46
97.31
98.68
36
Wearing Lipstick
92.05
90.46|
89.87
90.72
93.49
37
Wearing Necklace
86.21
86.21-
85.93
85.42
86.61
38
Wearing Necktie
95.85
95.941
94.43
94.08
96.30
39
Young
85.19
84.121
82.18
82.52
87.18
Table 10: Accuracy on CelebA dataset with settings in Appendix G.I from one run. 'Single" means each attribute is learned separately as a binary classification task. 'Multi means all attributes are learned jointly multi-label classification task. The green arrow indicates AUTO-S is better than Abadi's clipping under the same and the same task; the red arrow indicates otherwise; the black bar indicates the same accuracy.
35

---

K
Code implementation of automatic clipping
Changing Abadi's clipping to automatic clipping is easy in available codebases. One can set the clipping R= or any other constant, as explained Theorem and Theorem
K.1
Opacus
For Opacus [77] version 1.1.2 (latest), we can implement the all-layer automatic clipping by changing Line 399-401 in https://github. ctt pttp:cytttccctttoct hwtphh/opcacccaaaaaaa http//llbb///maae httpaaaa///pccsppppiamm..aaaa optimizer.py to
per_eample_clip_cee factor self. self.max_get max_ggadd_oon /per__samle__non
0.01)
The per-layer automatic clipping requires changing changing Line 61-63 in https: //t:: cttptutr.coooytttcchu.cc
.yy to
per pet_eample_ciip_facoo =max_graa_noom [per_sample_norms 0.01)
For older version (< 1.0, e.g. 0.15) of Opacus, we can implement the all-layer automatic clipping by changing Line 223-225 in httts:://gtthiiie com httpooocccoppccc//llobbbbb 15. 0/opacus/
utils/clipping, py to
per_sample_clip_factoe self. flau_value (norms [0] 0.01)
or implement the per-layer automatic clipping by changing Line 301-302 https: /tte::///httttt com/
pytorch/ hittorchoppcus////e/e
http:///ww/ptt...oeooo////rrrrpp py to
per wtt_sampe__clip_faee
threshold (norm + 0.01)
clipping factor append (per_sample__..ppe wtlpe__llpppp__o_o
K.2 ObJAX
For ObJAX version 1.6.0 (latest), we can implement the automatic clipping in https://githut: com/ htt//ooogle//bjja/lllbbb
/ http:////w...ttattot///at/////// wraddidnnddgrdinnn.....r py by changing Line 92
idivisor self 12__nomm_m_mppp / (total_grrd_normoo..or
and changing Line 145 to
idivisor self 12_ (ltpp//gadppggadd///ea Soeradd_ormm+O.o00
K.3 Private-transformers
To reproduce experiments for sentence classification and table-to-text generation, we modify the "private-transformers' (version 0.1.0) codebase of [41]. The modifica-
tion is in https://github.. wttp://cccoooocccoeeeeeeeeae http:///.o..omeeeeee/ee///rtttte hrwpr//eeeeeetattteeaaaaattrenne wwt.eoorrrrr/ooooaain//eeeeaeeee tramsfoommerr//ppirroruuttiiipip
py, by changing Line 349 to
return self wtt.mmaaaddadoooe
saor__sample 0.01)
and Line 510-512
coef sample self max_maaad_nooraeee norm scale (horm_sample + 0.01)
L More on related works of per-sample clipping
We discuss the difference between work and the related (see the table below).
36

---

C
reference
clipping not
convergence amalysis
experiments
min 1,
[1. 41]
clipping
None
CV and NLP
min
TI=iT
[17]
clipping
None
CV only
It lig
[16]
normalization
convex and federated setting (not per-sample)
CV only
[74]
normalization
non-convex, relaxed Lipschitz smoothness
CV and NLP
this work
normalization non-convex, same smoothness as non-DP CV and NLP
le Table 11: Comparison between clipping functions. CV means computer vision and NLP means natural language processing. Notice that any clipping function with R is not automatic and requires tuning, and that the stability constant enjoys theoretical and empirical benefits.
Our work is very different to most works which do not analyze the convergence of DP deep learning non-convex setting, but is very similar to [74]"0. However, [74] assumes relaxed Lipschitz smootheness in place of our Assumption 5.3, where we instead assume the symmetric gradient noise. In addition, our experiments are more comprehensive, covering over 10 tasks including DP-GPT2, while [74] only experimented with smaller models ResNet20 and Roberta-base.
L.1 Clarifications
We now clarify some false incomplete conclusion in previous literatures that apply the per-sample gradient clipping tre-parameterized or not).
1. Per-sample clipping is not robust to R, even with re- ee-paameterrzationn
In [17, Figure 8] and our Figure 4, the accuracy of DP optimizer with Abadi's clipping is insensitive to R only if one has found small enough region (e.g. R S 1), which takes effort to find or the accuracy will be unacceptably low out of the region. In particular, choosing R in [17] is universally proper, e.g. [41] uses R = 0.1 for language models. This dependence on tasks, datasets and optimizers means per-sample clipping still requires the expensive hyperparameter tuning.
In other words, per-sample gradient clipping is at best an approximation of per-sample gradient normalization (i.e. our AUTO-V) and should be considered as semi-automatic. whereas AUTO- V/S fully automatic in terms tuning R. Although technically we introduce a new hyperparameter "y in the place of R, we claim that automatic clipping not sensitive to 7 (our only hyperparameter) for a large range, e.g. one can multiply 7 by 10000 times, going from 7 =0.001 to 10 with learning rate 0.0005 in Figure 15, and the accuracy is similar.
Per-sample clipping does not decouple R, especially for DP-Adam.
In general, is not completely decoupled from the re-parameterized per-sample clipping in [17]:
R gi
1) R Cre-param = R. min( 1
Abbudi
min(
gg R
Given that R appears in both terms on the right hand side, one can at most say "... when the clipping norm is decreased times, the learning rate should be increased k times to maintain similar accuracy." by [38] and "... Using this update, performance becomes less sensitive to the choice of clipping norm." by [17]. In contrast, maintains exactly the same accuracy and completely insensitive to the choice of R.
state that adjusting the learning rate proportionally, our AUTO-V/S
Additionally and importantly, the understanding in [38, 17] is limited to DP-SGD (as they only experiment with the computer vision tasks), where "... the learning rate absorbs a factor of by [17]. As rigorously proved in Theorem and Theorem 2, adaptive optimizers like Adam and AdaGrad do not absorb but rather cancel it. This visualized Figure 1, where the performance landscape is row-wise for DP-Adam and diagonal for DP-SGD.
Re-parameterized per-sample clipping unintentionally changes the weight decay.
WeWe emphasize that [74] is a concurrent work with no known dependency either way. which goes public (to arXiv, 27 Jun 2022) after ours (on 14 Jun 2022).
37

---

Weight decay is a common technique used in any work that uses AdamW and in the re- pe-aamettriieed trick by [17]. We can see that
1
R
oR
NN.0
Before re-parameterization: W++11 We 7)
min(1,
9:
Auy
B
After e--aarameterization: w/+1 = W/
1
min
1 R
1
)9:
X
+ N(O.T)
B
|9::1
R
B
Therefore, when move along R. like in [17, Figure 8), from R = 1 to 2 6, the weight decay increases from À to 26 by 64 times, which may worsen the accuracy as seen the blue curve of [17, Figure 8]! Again, this is due to the incomplete decoupling by per-sample clipping, which is only avoided AUTO-V/S thanks to theoretical analysis Theorem and Theorem
AUTO-V/S with weight decay: w++1 Wi
71
Σ B
Ie + 9b + Aw + 0 N(.
L.2 Connections to normalized optimisation
Variants of normalized gradient have been used optimization [47, 53, 81, 80, 15]. These normalized optimizers are fundamentally different to our automatic optimizers, because the normalization is on mini-batch not each sample and noise is not involved:
B Σ 96
NSGD: w1+1 = 1t 17
11 Σ, 9b1l
AUTO-V: V: w++1 wt -1 17
1 B
Σ
Si
+ x..o.))
Mell
The main difference lies in the challenge of analyzing per-sample normalization (which is biased) and the aatch-gradient normalization (which is unbiased in the direction). That is, 1. A. g: is parallel to
E.
the mini-batch gradient E.9 but + E:
Ø1 is generally not parallel to it (this conclusion also |[ holds if the normalizaiton is replaced by the clipping). On side note, is interesting that Theorem indeed shows although bias is introduced by the per-sample clipping, it is not fatal to the asymptotic convergence and hence may not be concerning matter.
38


Reviews:
[{"review_id": "XfJGNqbm8J", "reviewer": "Reviewer_Cysx", "summary": "The script proposed an automatic clipping methods for various DP algorithms. The problem is important because the performance of DP models are sensitive to the choice clipping threshold, yet there is no theorical guidance for tuning it. \n\n", "questions": "**Only one question:**\n\nAccording to to line 140, Auto-V maximizes the dot product similartiy **only when** <g_i, \\sum_j g_j> >0 for any i.  However, in practice, <g_i, \\sum_j g_j>  could be negative, but Auto-V still perform gradient normalization on these samples. I wonder: what if we only normalize g_i with <g_i, \\sum_j g_j> >0 and ignore the rest, (i.e., do exactly the optimal normlization in line 140). Will it bring better performance? Similar question also goes to Auto-S.\n\n\n\n**Suggestions:**\n\nI suggest add index to the equations in line 138 and 140. ", "limitations": "See above", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The writing is clear and the paper is easy to follow. The idea is simple and effective.  Theory and experiments are provided to show the efficacy of the proposed automatic clipping method. I think this result is worth sharing with the DP community. \n\n\n\n", "weaknesses": "See below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our work! We will add index to equations as suggested.\n\nWe expect the optimal clipping, as we already stated in line 140, to have a better performance BUT it will not lead to DP guarantee. The reason is due to the term $\\sum_j g_j$, which changes when adding or removing one sample from the batch. To give more details, the bounded sensitivity in DP requires that the sum of clipped gradients changes by at most $R$, when adding or removing one sample. Suppose in one dataset we have only one datapoint (j=1,2) and in its neighboring dataset we have two datapoints (j=1,2,3). We will use AUTO-V clipping as an example, and Abadi's clipping can be analyzed similarly. Then for AUTO-V clipping, we have $|| C_1g_1+C_2g_2+C_3g_3||-||C_1g_1+C_2g_2||\\leq ||C_3g_3||\\leq 1$ by the triangular inequality (where $C_i=1/||g_i||$). But the clipping in line 140 gives $||C_1'g_1+C_2'g_2+C_3'g_3||-||C_1g_1+C_2g_2||$ (where $C_i=\\mathbb{I}(\\langle g_i, g_1+g_2\\rangle>0)$ and $C_i'=\\mathbb{I}(\\langle g_i, g_1+g_2+g_3\\rangle>0)$), hence the triangular inequality does not apply due to $C_1'\\neq C_1$. This is the reason that per-sample clipping has to look at individual gradient separately in most DP literature (unless $\\sum_j g_j$ is privatized at additional privacy budget), i.e. $C_i$ only depends on $g_i$ and nothing else. We will add this explanation in the camera ready version."}, {"review_id": "E6cynfOICH", "reviewer": "Reviewer_V9NQ", "summary": "This paper introduces 'automatic clipping' to replace the usual clipping operation in DP-SGD. The challenge of usual clipping is to choose a good threshold 'R' especially for deep learning models. The authors claim that automatic clipping maintains the same level of privacy and computational efficiency as existing DP optimizers such as DP-SGD, DP-Adam, and DP-LAMB, but without the need for any DP-specific hyperparameters. In fact, automatic clipping uses a kind of normalization to bound the sensitivity of individual gradient. Additionally, they provide a thorough convergence analysis for DP-SGD with automatic clipping in the non-convex setting, demonstrating that it can match the convergence rate of standard SGD under certain conditions. The authors validate their proposal by showing that automatic clipping either matches or surpasses the state-of-the-art performance on a variety of language and vision tasks.\n", "questions": "See weakness.", "limitations": "See weakness", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. **Simplicity**: The proposed method of automatic clipping significantly simplifies the process of DP training by eliminating the need for tuning DP-specific hyperparameters, thereby making DP as user-friendly as standard non-private training.\n\n2. **Performance**: The paper demonstrates that the automatic clipping method is either on par with, or better than, existing state-of-the-art techniques in a variety of tasks. This suggests that the method does not compromise performance for ease-of-use.\n\n3. **Rigorous Analysis**: The authors provide a detailed convergence analysis of automatic DP-SGD in a non-convex setting, showing that it can match the convergence rate of standard SGD under the symmetric gradient noise assumption of per-sample gradients.", "weaknesses": "**Misleading justification**: In figure 2, the paper present the dot products of $\\langle g_i, \\sum_i g_i \\rangle$. First it does not make sense if the dot product is properly normalized.  Moreover, the distribution of  $\\langle g_i, \\sum_i g_i \\rangle$ does not necessarily align with good performance. The illustration in Figure 2 is rather misleading.\n\n**Too strong Assumptions**: The proposed automatic clipping method's performance is based on a symmetric gradient noise assumption of the per-sample gradients. This assumption is too constrained and does not satisfy in practice.\n\n**Overclaim**: Section title 4.3 \"Automatic clipping is equally private and maximizes utility\" is somewhat overclaiming. It is not carefully argued why automatic clipping can \"maximize utility given a privacy budget.\n\n**Missing reference**: The paper missed a very related reference Yang et al. \"Normalized/clipped sgd with perturbation for differentially private non-convex optimization\" which also studied the DP-SGD with normalization. The paper should have a careful comparison with it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We will address the your comments point-by-point.\n\nMisleading justification & Overclaim: the dot product is not normalized and it is indeed aligned with good convergence in the following sense. Under our non-convex but Lipchitz smooth setting (see Appendix C.2), $L_{t+1} − L_t \\leq g_t^\\top(w_{t+1} − w_t) + \\frac{L}{2}||w_{t+1} − w_t||^2$, where $L_t=\\sum_i L_i(w_t), g_t=\\sum_j g_j(w_t)$. According to DP-SGD, we have $w_{t+1} − w_t=-\\sum_i C_i g_i-\\sigma N(0,I)$, and the loss decrease (as stated above equation C.2) is upper bounded by $-\\eta (\\sum_j g_j)(\\sum_i C_i g_i+\\sigma N(0,I))+L\\eta^2(B^2+\\sigma^2 d)$. Notice that the second term is independent of clipping and the first term (ignoring $\\sum_j g_j\\cdot \\sigma N(0,I)$ for its zero expectation) can be written as $-\\eta \\langle \\sum_i C_i g_i, \\sum_j g_j\\rangle$, which is exactly the dot product in Section 3.2 that we want to maximize. We thank the reviewer for bringing this up and will surely add this explanation in the camera ready version.\n\nToo strong Assumptions: We emphasize that the symmetric noise is actually relaxed from the common non-DP deep learning literature (see references in Footnote 6, also the \"Noise structures\" section in [1*] for a literature survey about the symmetry of gradient noise), and has been empirically verified in DP deep learning by [14]. We agree that the assumption can be strong and not satisfied in practice, but it is necessary and insightful, shedding light on the training behaviors below Theorem 5 for practitioners.\n\n[1*] Wu, Lei, Mingze Wang, and Weijie Su. \"The alignment property of SGD noise and how it helps select flat minima: A stability analysis.\" Advances in Neural Information Processing Systems 35 (2022): 4680-4693.\n\nMissing reference: We thank the reviewer for mentioning this paper. It is a concurrent work that goes public (to arxiv) after ours. To comply with NeurIPS anonymous submission policy, we cannot provide the timestamp. We will add the comparison in the camera ready version by claiming that (1) Our algorithms are the same. (2) The analysis is based on different assumptions. Yang et al. uses a relaxed Lipchitz smoothness, instead,  we use the symmetric gradient noise assumption. (3) Our experiments is more comprehensive, covering over 10 tasks including the scalability of DP GPT, while they only cover 2 smaller models.\n\nWe are happy to extend the discussion and hope the reviewer can raise the score if satisfied!"}, {"review_id": "XfOKyRrrog", "reviewer": "Reviewer_FQ5E", "summary": "The paper discusses a way to control the sensitivity of DP-SGD by a method that does not require clipping.\n", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The motivation for the paper is clear\n- The authors make a compeling argument that suggest why their method should work\n- They have sound theoretical guarantees and experiments\n- The idea is simple yet fully developed\n- The impact this could have on private learning is huge\n- Experimental results are compeling\n", "weaknesses": "N/A", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you! Happy to extend the discussion any time."}, {"review_id": "cVPFsUuu8C", "reviewer": "Reviewer_jhaz", "summary": "The author(s) proposed a new gradient clipping technique for differential private training algorithms. It was shown that the new clipping technique is more robust to hyper-parameters and can save the time for hyper-parameter tunning. Convergence of the proposed method under a gradient symmetric assumption is developed and experiments on both vision and language tasks are conducted to evaluate the proposed method.", "questions": "- Consider the example with 3 data points, $f(x) = f_1(x) + f_2 (x) + f_3(x)$, where $f_1( x ) = 2 x^2, f_2(x) = (x-1)^2, f_3( x ) = f_2(x) = (x-1)^2$. Then the solution is at $x^* = 0.5$, but this point is not stationary for Algorithm 1, because $g_1( x^* ) = 2, g_2(x^*)=g_3(x^*)=-1$, which implies $g_1( x^* ) / \\| g_1( x^* ) \\| = 1, g_2(x^*) / g_2( x^* )=g_3(x^*)/g_3( x^* )=1$. Algorithm 1 willi fail on this example, does the author(s) agree?", "limitations": "I do not find any negative societal impact of this paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow in general.\n- The experiments are thorough and the algorithm seems to be useful on the practical side.", "weaknesses": "- The convergence analysis is based on a gradient symmetric assumption, therefore the utility bound in Theorem 4 is not really comparable to prior works. Please also see my quetions below. Overall, the theoretical contribution seems limited. However, given the strong empirical performance of the proposed method, this might be acceptable.\n- Some related work should be added [1,2,3].\n\n[1] Clip21: Error Feedback for Gradient Clipping, https://arxiv.org/abs/2305.18929\n\n[2] Improved Convergence of Differential Private SGD with Gradient Clipping, https://openreview.net/forum?id=FRLswckPXQ5\n\n[3] Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization, https://arxiv.org/pdf/2206.13033.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your enlightening review. We agree that Theorem 4 is not directly comparable to prior DP works, because our proof techniques are novel and settings are different. We hope the reviewer would agree that our setting (including the symmetric gradient noise, not symmetric gradient) is more realistic as noted in Footnote 6, consistent to most non-DP deep learning literature. We would also like to point the reviewer to the \"Noise structures\" section in [1*] for a literature survey about the symmetry of gradient noise, where the gradient noise is proportional to the oracle Hessian matrix, which by definition is symmetric.\n\n[1*] Wu, Lei, Mingze Wang, and Weijie Su. \"The alignment property of SGD noise and how it helps select flat minima: A stability analysis.\" Advances in Neural Information Processing Systems 35 (2022): 4680-4693.\n\nTo provide a comparison to the standard non-DP SGD, we devote Appendix D to study the convergence under the same setting as our DP-SGD analysis. We will add the suggested reference in the camera ready version, especially we would add a short paragraph comparing your 3rd reference to ours: (1) The analysis is based on different assumptions. Yang et al. uses a relaxed Lipchitz smoothness, instead, we use the symmetric gradient noise assumption. (2) Our experiments is more comprehensive, covering over 10 tasks including the scalability of DP GPT, while they only cover 2 smaller models.\n\nLastly, to address your example question, we agree that AUTO clipping does not find this minimum. However, this example should not belittle AUTO clipping for several reasons. (1) Per-sample clipping is known to introduce some bias, e.g. Abadi's clipping will also not find this minimum for R=1, because $C_1g_1(x^*)=1, C_2g_2(x^*)=C_3g_3(x^*)=-1$. It will find the minimum when R is large and not do the clipping, but then the noise $\\sigma R\\mathcal{N}(0,I)$ is also large, rendering much worse performance. Hence the issue is not unique to AUTO clipping. (2) This example seems to not follow the i.i.d. data assumption, a common one in deep learning literature, in that $f_1,f_2,f_3$ should take the same form, like $f_i=L(x_i;w)$. In our Section 3.3, we also provide an example by specifying the data distribution and draw large number of datapoints. We would love to extend the discussion if the reviewer is interested in such examples.\n\nWe hope the reviewer can raise the score if satisfied!"}, {"review_id": "lsgx1FfydP", "reviewer": "Reviewer_2WqJ", "summary": "The paper proposes a new alternative version of the DP-SGD algorithm where the gradients are normalized. This new method allows for a proof of convergence of the gradient when we add a small stability constant to the rescaling factor. This work eliminates the need for a costly 2D gridsearch between learning rate and clipping constant when training DP models. The authors then proceed to run experiments on to show their method equals or outperforms Abadi’s DP-SGD algorithm.", "questions": "### Can you provide tangible proof that your method is significantly less expensive to tune than the rescaled DP-SGD algorithm ?\n\nThe figure you cite in the concurrent work of De et al. in section 4.4 does not seem complete enough and gives no indication of the strain in ressources the rescaled DP-SGD might still induce.\n", "limitations": "The method is original. However some similarities can be drawn with existing concurrent approaches like Yang et al. 2022 [2206.13033]  that did not go through peer-reviewing to the best of my knowledge, however this work might be worth citing.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The article eliminates a costly operation in DP training and provides strong evidence regarding the convergence of their method. The exhaustive list of datasets on which the method was tested testifies as to how only minimal changes to existing implementations are needed to apply this method.\n\n### Originality\n\nThe method is original.\n\n### Quality\n\nThe experiments presented are very complete and yield high quality results. Also, various supporting githubs and ressources are mentionned, making these results reproducible.\n\n### Clarity\n\nThe article is clear and well written.\n\n### Significance\n\nThe original motivation of the article is clear. ", "weaknesses": "## Sensitivity of the hyperparameter optimization\n\nThe results are not clear enough to indicate whether the proposed DP training method is superior to the rescaled DP-SGD method which impedes the significance of the article. If the authors of the paper manage to prove that their method is less expensive than the rescaled DP-SGD trick then the contribution is significant. The article lacks a conclusive experiment or statement proving that the sensitivity of the hyperparameter optimization process is easier with this method than with the re-scaled version of Abadi’s DP-SGD. \n\nThe paper shows in its appendix H. that the training process of the AUTO-S method is relatively robust to the choice of $\\gamma$ on NLP tasks. However the paper doesn’t compare the sensitivity of the **AUTO-S method** to the $\\gamma$ factor to the sensitivity of the **rescaled Abadi clipping** to the $R$ factor. In my opinion this is an important experiment to run, since it would justify using this method instead of the widely known rescaled DP-SGD version introduced in De et al. [15]. This could improve the impact and the significance of the contribution.\n\n### Actionable feedback\n\n> However, R remains and is expensive to tune (l223)\n\nThis sentence in particular is a bit of an overclaim in my opinion, see my comments below.\n\n**In your experiments you specifiy regarding the range of $\\gamma$**\n> ”under which a wide range of 0.0001 < < 1 gives similar accuracy”\n\nand\n>“Note that the largest good is 1000 times bigger than the smallest good ”\n\n\n**In the comparison to related works on clipping**\nYou state “Similarly (De et al.) re-parametrizes the per-sample gradient clipping to mimic normalization. However R remains and is expensive to tune (see figure 8 of De et al.)”. However this fig 8. shows that the re-parametrized per-sample gradient clipping seems to stay stable by a similar factor of approximately 1024 on the clipping norm, on a even harder dataset. Even though their experiment are not extensive enough to prove a superior efficiency of the rescaled DP-SGD method to yours, it is not conclusive enough for you to assume that your method is easier to tune.\n\nIf you add this missing experiment, or if you modify this claim, I would consider improving my rating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments! We will address the comparison to re-scaled DP-SGD in (De et al.) from the aspects of (1) convergence and hence performance, (2) better understanding of general DP optimizer, (3) saving the hyperparameter tuning efforts, (4) extensive experiments.\n\n1. Convergence\n\nBecause re-scaled DP-SGD simply absorbs the clipping threshold into the learning rate, there is a one-to-one mapping between original DP-SGD and re-scaled DP-SGD. Hence the convergence is exactly the same if both DP-SGD are tuned optimally. In contrast, our AUTO clipping has better convergence, as illustrated in Section 3.2, 3.3 with clear motivation, Section 5 with theoretical proof (which is absent in De et al.) and Section 6 with empirical evidence. Our improvement is particularly attributed to the stability $\\gamma$ not found in re-scaled DP-SGD.\n\n2. Understanding of general DP optimizer\n\nDe et al.'s re-scaling does not consider weight decay, which would lead to\n$$\\text{Before re-scale: }w_{t+1}=w_t-\\eta\\left(\\frac{1}{B}\\sum_i\\min(1,\\frac{R}{||g_i||})g_i+\\lambda w_t+\\frac{\\sigma R}{B}N(0,I)\\right)$$\n$$\\text{After re-scale: }w_{t+1}=w_t-\\eta\\left(\\frac{1}{B}\\sum_i\\min(\\frac{1}{R},\\frac{1}{||g_i||})g_i+\\frac{\\lambda}{R} w_t+\\frac{\\sigma}{B}N(0,I)\\right)$$\nThis is proved in Theorem 1. In words, although re-scaled DP-SGD seems robust to $R$ by a factor of approximately 1024, it also secretly weakens the weight decay when using smaller $R$, as shown in their Fig 8. Also, it is unclear how re-scaling would work with adaptive optimizers like Adam, because Adam does not absorb the clipping factor but rather cancels it with the adaptive denominator. This difference is visualized in our Figure 1 and proved in Theorem 2.\n\nIn words, the understanding from re-scaling omits some important aspects when advanced techniques, like adaptivity and weight decay, are introduced to DP-SGD, which is formalized by our work.\n\n3. Saving the hyperparameter tuning\n\nWe argue that the sensitivity experiments are already done by noticing the fact that re-scaled DP-SGD only modifies the learning rate (by absorbing the clipping norm; in De et al.'s own word, \"This is a re-parameterization of Equation (2) in which the learning rate absorbs a factor of C\"). Therefore, the optimal choice of re-scaled DP-SGD is the same as the optimal choice of original DP-SGD, just that the learning rate is re-scaled. \n\nHence our Figure 14&15 (appendix H4) demonstrate that (re-scaled) DP-SGD can be sensitive to R but AUTO DP-SGD is not sensitive to $\\gamma$. We also would like to point out that De et al. explicitly claimed that they use optimal $R=1$ for their vision models. However, we found that DP-Adam requires an optimal clipping norm $R=0.1$ on language models, i.e. RoBERTa and GPT2. This is also confirmed in \"LARGE LANGUAGE MODELS CAN BE STRONG DIFFERENTIALLY PRIVATE LEARNERS\". Hence, the performance of different tasks seems not robust to choice of $R$.\n\n4. Extensive experiments\n\nWe experimented on large models and language tasks, while De et al. only experimented with computer vision datasets. Note that many techniques like linear probing only works for vision but not language, or vice versa. We show this is not the case for AUTO-S. Specially, we extend to large models with over 700 param (GPT2-large), for which the normalization is much favorable because the tuning efforts are huge.\n\nWe will add an appendix to include this discussion. We sincerely hope the reviewer would appreciate our contribution besides the hyperparameter tuning and consider raising the score if satisfied."}]

Author rebuttal:

Meta-review: The paper got positive scores from the reviewers. The crux of the idea is elegant. However, I read the paper, and I had a concern about the applicability the results in a setting where clipping of the gradients do not correspond to scaling, meaning when we are operating in a non-spherical geometry. Some experiments, or theoretical analysis for that setting would be great.
Decision: Accept (poster)