On the Convergence and Calibration of Deep Learning with Differential Privacy
Authors: Zhiqi Bu
Hua Wang
Qi Long
Weijie J Su
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Learning
Differential Privacy
Optimization Algorithms
Convergence Theory
Calibration

Abstract: In deep learning with differential privacy (DP), the neural network achieves the privacy usually at the cost of slower convergence (and thus lower performance) than its non-private counterpart. This work gives the first convergence analysis of the DP deep learning, through the lens of training dynamics and the neural tangent kernel (NTK) matrix. Our convergence theory successfully characterizes the effects of two key components in the DP training: the per-sample clipping and the noise addition. We initiate a general principled framework to understand the DP deep learning with any network architecture, loss function and various optimizers including DP-Adam. Our analysis also motivates a new clipping method, the 'global clipping', that significantly improves the convergence, as well as preserves the same DP guarantee and computational efficiency as the existing method, which we term as 'local clipping'. In addition, our global clipping is surprisingly effective at learning calibrated classifiers, in contrast to the existing DP classifiers which are oftentimes over-confident and unreliable. Implementation-wise, the new clipping can be realized by inserting one line of code into the Pytorch Opacus library.

Under review as a conference paper at ICLR 2022
ON THE CONVERGENCE AND CALIBRATION OF DEEP LEARNING WITH DIFFERENTIAL PRIVACY
A Anonymous authors
Paper under double-blind review
ABSTRACT
In deep learning with differential privacy (DP), the neural network achieves the privacy usually at the cost of slower convergence (and thus lower per- formance) than its non-private counterpart. This work gives the first con- vergence analysis of the DP deep learning, through the lens of training dynamics and the neural tangent kernel (NTK) matrix. Our convergence theory successfully characterizes the effects of two key components in the DP training: the per-sample clipping and the noise addition. We initi- ate general principled framework to understand the DP deep learning with any network architecture, loss function and various optimizers includ- ing Ad-Adam. Our analysis also motivates new clipping method, the global clipping, that significantly improves the convergence, as well as pre- serves the same DP guarantee and computational efficiency as the existing method, which we term as local clipping. In addition, our global clipping is surprisingly effective at learning colibrated classifiers, in contrast to the existing DP classifiers which are oftentimes over-confident and unreliable. Implementation-viin the new clipping can be realized by inserting one line of code into the Pytorch Opacus library.
INTRODUCTION
Deep learning has achieved Iremendous success in many applications that involve crowd- sourced information, e.g., face image, emails, financial status, and medical records. However, using such sensitive data raises severe privacy concerns on a range of image recognition, natural language processing and other tasks (Cadwalladr & Graham- Hariissnn 2018 Rocher jet al., 2019 Ohm 2009 De Montjoye et al., [013) 2015). For concrete examples, there are multiple successful privacy attacks on deep learning models, in which members in the dataset can be re-identified using the location or the purchase record, via the membership inference attack QShokri et al., [0117] Carlini et al.) 2019). In another example, the attackers can extract a person's 8 name, email address, phone number, and physical address from the bilion--arameter GPT-2 (Radford et al. 2019) via the extraction attack (Carlini et al. 2020 Therefore, many studies have applied differential privacy (DP) (Dwork et al.) 2006
Dwork 2008 Dwork et al. 2014 Mironov 2017 Duchi et al. 2013 Dong et al.] 2019).
mat mathenatically rigorous approach, to protect against leakage of private information (A Aadi
et al. 2016 McSherry & Talwar 2007 McMahan et al. 22017 Geyer et al.) 2017 To
achieve this gold standard of privacy guarantee, since the seminal work (Abadi et al. 2016).
DP optimizers are applied to train the neural networks while preserving the accuracy of
prediction. To name a few, researchers have proposed DP-SGD (Abadi et al. 2016 Bassily
2014 DP-Adam (Bu al. 2019), DP-SGLD (Wang et al. 2015: Li al. ct al.
2019)
FTRL Kairoux el al. 2021], FedSGD and DP-FedAvg (McMahan et al. 2017).
Algorithmically speaking, DP optimizers generally have two extra steps comparison to
non-DP standard optimizers: the per-sample clipping and the random noise addition, so that DP optimizers descend in the direction the averaged, clipped, noisy gradient (see Figure D. These extra steps protect the resulting models against privacy attacks via the Gaussian mechanism (Dwork et al.) 2014, Theorem A.1), at the expense of an empirical performance degradation compared to the non-DP deep learning, in terms of much slower convergence and lower utility. For example, state-of-the-ae CIFAR10 accuracy with DP is 70% without pre-training (Papernot al. 2020 (while the same DP networks can

---

Under review as a conference paper at ICLR 2022
achieve 90% accuracy) and similar performance drops have been observed on facial images, tweets, and many other datasets (Bagdasaryan et al. 2019
Empirically, many works have evaluated the effects of noise scale, batch size, clipping norm. learning rate, and network architecture on the privacy-acuuracy trade-off (Abadi et al, 2016 Papernot et al. 2020 However, despite the prevalent usage of DP optimizers, little is known about its convergence behavior from a thcoretical viewpoint, which is necessary to understand and im improve the deep learning with differential privacy. We notice one previous attempt by (Chen et al. 2020), ; analyzing the DP-SGD convergence with an assumption of symmetric gradient distribution, which can be unrealistic and inapplicable real datasets.
Our Contributions
We explicitly characterize the general training dynamics deep learning with DP gra- dient methods (e.g., DP-GD and DP-Adam). We show a fundamental influence of the DP training on the NTK matrix, which causes the convergence to worsen. This analysis leads to convergence theory for the DP deep learning.
We propose a novel principle for designing the DP optimizers and thus develop a new global clipping method that provably enjoys desirable convergence behaviors.
We demonstrate via numerous experiments that DP optimizers with global clipping significantly improve the loss convergence. Interestingly, our clipping further effectively mitigates the calibration issue of existing DP classifiers, which usually exacebates the "over-confidence" in non-DP models.
Our global clipping has the some privacy guarantee and computational efficiency the local clipping, which leads to a miz-up training strategy where local and global clippings are applied interchangeably.
Our global clipping is easy-to-cods (see Appendix D and generulizable to arbitrary optimizers, network architoctures, loss functions, and tasks including foderated learning.
quick preview of the comparison among the DP optimizers with the local and the global
clipping is as follows:
Clipping type
Positive NTK
Loss convergence
Monotone loss decay
No To zero loss
No clipping
Yes
Yes
Yes
Yes
Local & Flat
No
No
Yes
Local & Layerwise
No
No
No
No
Global & Flat
Yes
Yes
Yes
Global & Layerwise
Yes
Yes
Yes
Yes
Table 1: Effects different per-sample clippings on deep learning with DP-GD, assuming
no screening happens in global clipping. Here "Yes/No" means guaranteed or not and the loss refers to the training set.
"Loss convergence" is conditioned on H(1) > 0 (see (2.1
WARMUP: CONVERGENCE OF NON-PRIVATE GRADIENT DESCENT
We start by reviewing the standard, non-DP Gradient Descent (GD) for arbitrary neural network and arbitrary loss, before we dive into the analysis of DP optimizers. In partic- ular, we analyze the training dynamics using the neural tangent kernel (NTK) matrix]]
Suppose neural network f is governed by weights w, with samples 2, and labels y: I...., n). Denote the prediction by f: f(x,, w), and the per-sample loss by 4 = E(f(z, w). vi) for some loss function f. We define the objective function L to be the average of per-sample losses L(w) n En E(f(a,, w) v.). The discrete gradient descent with a step size y7, and the corresponding gradient flou are:
w(k + w aw
ØL
and w() = Ow
OL
T1 -.
We emphasize that our analysis works any neural networks, not limited to the infinitely wide
over- over-parameterized ones. Put differently, we don't assume the NTK matrix H to be deterministic
nor nearly indee-ddddeendnnt. as was the case (Arora et al. 2019a Lee et al. 2019: Du et al.
2018 Allen-Zhu et al. 2019 Zou et al. 2020 Fort et al.] 2000
Arora ét al. 2019b).
Tee. the ordinary differential equation (ODE) describing the weight updates with infinitely
small step size 7 + in the continuous time.
2

---

Under review as a conference paper at ICLR 2022
Applying the chain rules, we obtain the following general dynamics of the loss L,
ÖL ØL
0f of T OL of dw dw of
AL 0f
OL Df
i. Ow Ow dw
H(t)
(2.1)
where AL 1. 88 Den E IR xx and the Gram matrix H(t) == of os T
[ ... af. as the NTK malrix, which is positive semi-definite and crucial to analyzing the convergence
Sw 8w E R is known
behavior. To give concrete example, let & be the MSE loss ((()) (f(æ,, w) - y:) and
LASE = (, -y:² then EMSE = -4 y) (ftt(ff y)/n² Furthermore, if H(t) is positive definite, the MSE loss LMSE - 0 exponentially fast (Du et al. 2018 Allen- Zhu
et al.j [219 Zou et al.) 2020 the cross-entropy loss LCE - 0 at rate 1(1)) and any loss
convex in the prediction L Σ, L//n converges to 0 (Allen-Zhu et al. 2019).
DIFFERENTIALLY PRIVATE GRADIENT METHODS AND GLOBAL CLIPPING
We now introduce the DP optimizers Google Facebook) to train the DP neural networks. One popular optimizer is the DP-SGD (Song et al. 2013 Chaudhuri et al. 2011 Abadi et al. 2016 Bu et al., 2019) in Algorithm ] and more optimizers such as DP-Adam and DF-FedAvg IMMMahal et al. 2017) for federated learning can be found in Appendix F In contrast to
the standard SGD, the DP-SGD has two unique steps: the per-sample clipping (to bound the sensitivity of per-sample gradients) and the random noise addition (to guarantee the privacy of models), both are discussed in details via the Gaussian mechanism in Lemma B.
Algorithm 1 DP-SGD (with local or global flat per-sample clipping)
Parameters: initial weights Wo, learning rate St, subsampling probability p, number of iterations T, noise scale a, gradient norm bound R maximum norm bound 2 2 R.
for O,..., T do Subsample a batch 4.S (I,.....,,)) from training set with probability p
for E I do 1/ Vwl(f(ar; we), v4)
Option 1: Clocat, min {1, R/ ||
[b]
b Local clipping factor (existing)
Option 2: Cgiobat, = R/Z if ooz
S Z
b Global clipping factor (ours)
if 10
Z
0 C.-v(( (1)
Clip the gradient Sum over batch
VA - Eier, Vi
(8)
W41 t Wt II
De
(Ve (V+OR--NO.N
> Apply Gaussian mechanism and descend
Although the per-sample clipping is widely applied in DP deep learning, its effect on con- vergence remains mystery. Fapirical observations have found that optimizers with the per-sample clipping (even when no noise is present) have much worse convergence and accu- racy (Abadi et al.) 2016 Bagdasaryan al. 2019). In fact, the current form of clipping is heuristic and lacks theoretical understanding, especially when the noise addition is present. In what follows, we use C to denote Clocat Cylobal when it is clear from the context.
We propose and analyze a new clipping, namely the global clipping (see Option 2 in Algorithm D]. where the clipping operation takes place on all per-sample gradients that pass the screening procedure. From this viewpoint, the global clipping is a batch clipping instead of an individual clipping (see Appendix F.6 for comparison with local clipping). More precisely, in local clipping, each per-sample gradient Vwe; compare its length to R and multiplied with a sample-specific clipping factor 0 C, S 1. In global clipping, only Vwl; with norm smaller than 2 is used (otherwise C, ===00 =) 0) and multiplied with common clipping factor R/Z, which guarantees the sensitivity to be R as in local clipping. At a high level, the idea of global clipping is to preserve the gradient direction (i.e. to remove the gradient bias) while bounding the sensitivity during the clipping, which will guarantee the positive semi-definitenes of the NTK matrix via Theorem
3

---

Under review as a conference paper at ICLR 2022
(Zoom In).
Clip-
Sum
Add Noise
Figure 1: Illustration of global (upper) and local per-sample clipping (lower) in Algorithm Black arrowed lines are per-sample gradients. The circles have radius I (red) and Z (grey). )
4 CONVERGENCE ANALYSIS OF DP OPTIMIZERS
In this section, analyze the weight and loss dynamics of DP optimizers with the local or global per-sample clipping, denoted in the subscript, e.g., DP-SGDrood and DP-SGD gtoooDat Our narrative here focuses the widely used DP-GD for the sake of simplicity, yet and our analysis generalizes to other full-batch DP optimizers such as DP-leavyBall, DP-RMSprop, and DP-Adam well (see Theorem and Appendix F
globol-
4.1 EFFECT OF NOISE ADDITION ON CONVERGENCE
Our first result is easy yet surprising: the gradient flow of a stochastic noisy GD with non- zero noise (4.1) is the same that of a deterministic dynamics without the noise (.2) Put differently, the noise addition has no effect on the convergence of DP optimizers the continuous time gradient flow. This is common phenomenon called certainty equivalence in the stochastic control community with the name of [Chow et al. 1975).
To elaborate this point, we consider the DP-GD with Gaussian noise, as in Algorithm
+k+1))= = w(k) !
Σ Twl.C oR +.RCC++RR-NO..)) NR.,)
(4.1)
Notice that this general dynamics covers both the non-DP GD (a 0 and C. 1) and DP-GD with local or global clipping. Through Fact 4.1 we claim that the gradient flow of (11 is the same ODE regardless of the value of a, whose proof is delayed to Appendix B
Fact 4.1. For all 2 0, the gradient descent in 4.1 has the continuous gradient flow
dw(() -w) v &
(4.2)
This result shares the spirit of the conventional wisdom that tune the clipping norm first (e.g. setting
small), and tune the noise level afterwards, since the convergence is more sensitive to the clipping factor. We visualize this point via experiment in Appendix G
Remark 4.2. Our proof of Fact 4.1 generally holds true for any DP optimizer besides DP-GD: 1) 0, different a result in the same gradient flow.
4.2
EFFECT OF PER-SAMPLE CLIPPING ON NTK MATRIX
We move to analyze the effect of the per-sample clipping on the DP training (42 Tt has been empirically observed that the per-sample clipping results in a worse convergence and accuracy even without the noise (Bagdasaryan et al. 2019). We highlight that the NTK matrix is the key to understand the convergence behavior, and that the clipping affects NTK through its lincar algebra propertics, especially the positive semi-definiteness, which we define below in two notions for general matrix.
Definition 4.3. For a (not necessarily symmetric) matrix A, it is
1. positive in quadratic form if and only if T AA TA 2 0 for every non-zero ;;
2. posilive in eigenwalues if and only if all eigenvalues of A are non-negative.
"See http:p/ssgggtaa...oooopr///ee//a orgee

---

Under review as a conference paper at ICLR 2022
These two positivity definitions are equivalent for symmetric Hermitian matrix, but not so for non-symmetric matrices. We illustrate this difference in Appendix A with some concrete examples. Next, introduce two styles of per-sample clippings. Both can be implemented locally or globally.
Flat Clipping The DP-GD described in Algorithm and 4.11 with the gradient flow 4.2). is equipped with the flat clipping (McMahan et a.. 2018 In words, the flat clipping upper bounds the entire gradient vector by a single R. Using the chain rules, we get
L ÔL w -
VwC.C -,
ÖL
OL
HC
(4.3)
Ow
of
of
where C(t) = .i,ig(C,....... C.) is the clipping matrix, with C, defined in Algorithm
Layerwise Clipping, We additionally analyze another widely used clipping - the lay- erwise clipping (Abadi et al.) 2016 McMahan et al.) 2017 Phan et al. 2017). Unlike the flat clipping, the layerwise clipping upper bounds the r-th layer's gradient vector by a layer- dependent norm R,, as demonstrated in Algorithm 2 Hence i. Σr
8L H,
H, Cr,rr at wheree
87
the layerwise NTK matrix H,
af af ow, Ow,
and C,(t) = diag(C2,r)".. Cr.)).
4.3 LOCAL PER-SAMPLE CLIPPING BREAKS NTK POSITIVITY
We start with the analysis of local clipping, which is the prevailing clipping technique prior to our work. We show that the DP-GD with local clipping breaks the traditional positive semi-defiitteness of the NTK matri
Thcorem 1. For arbitrary neural network and loss conver in f, suppose we clip the per-sample gradients locally, and assume H(t) > 0, then in the gradient flow of DP-GD:
The local flat clipping has the loss dynamics in (4.3) with NTK matrix H(t) Clocet(t). (t); which may not be symmetric nor positive in quadratic form, but is positive in eigenvalues.
The local layerwise clipping has the loss dynamics with NTK matrie Σ, (1) which may not be symmetric nor positive in quadratic form or in eigenvalues.
3. For both local flat and layerwise clipping, the loss L(t) may not decrease monotonically.
If the loss L(t) converges, for the flat clipping, it converges to 0; for the layerwise clipping, it may converge to non-zero value.
We prove Theorem 1 in Appendix B The theorem states that the symmetry of NTK is almost surely broken by the local clipping. In that case, severe issues arise in the loss convergence, which are depicted in Figure 5 and Figure
4.4 GLOBAL
CLIPPING PRESERVES NTK POSITIVITY WITH LARGE Z
Now we switch gears to our global clipping. At each iteration when is sufficiently large so that no per-sample gradient is screened out, the global clipping clearly corresponds to a sym- metric and positive semi-definite NTK matrix H(t)C(t) in flat clipping and Σ, (t, in layerwise clipping, since all per-sample gradients share the same clipping factor. As result, the clipping matrices are indeed scalar in that C = CI in (4.3 and C, = C, in B.I.. Hence obtain the following result for the global clipping.
Theorem 2. For an arbitrary neural network and loss conver in f. suppose we clip the per-sample gradients globally, assuming H(t) > O and (0,(0)1 < 7 then in the gradient flow of DP-GD:
1. The global flat (resp. layerwise) clipping has loss dynamics in 4.3 with NTK matrix ((())attbai(t) (resp. Σ, (,,(gt)g which symmettrc and positive definite. For both global flat and layerwise clipping, the loss L(t) decreases monotonically to
"It is fact that the product of symmetric positive definite matrices and positive diagonal matrix may not symmetric nor positive in quadratic form. This shown in Appendix
'If Z is not large and the screening is effective, then the global clipping (flat or layerwise) may break its symmetry and positivity both in quadratic form and in eigenvalues. Consequently, the training loss may not decrease monotonically nor to zero.
5

---

Under review as a conference paper at ICLR 2022
We prove Theorem 2 in Appendix B and the benefits of the global clipping are assessed in Section
Our findings from Theorem and Theorem 2 are visualized in the left plot of
Figure 9 and summarized in Table which further leads to Table [
Clipping
NTK
Symmetric matrix
Positive in quadratic form
Positive in eigenvalues
method
matrix
No clipping
H E, H,
Yes
Yes
Yes
Local & Flat
HC
No
No
Yes
Local & Layerwise
Σ, Cr
No
No
No
Global & Flat
HC
Yes
Yes
Yes
Global & Layerwise
Σ, H.
Yes
Yes
Yes
Table 2: Linear algebra properties of NTK by different clipping methods, assuming no
screening happens in global clipping. Here 'Yes/No' means guaranteed not.
PRIVACY ANALYSIS OF DP OPTIMIZERS
In this section we define DP and prove that DP optimizers using the global clipping have the same privacy guarantee those using the local clipping. Notice that for the privacy analysis, we work with the general DP optimizers, including those with mini-batches.
Definition 5.1. randomized algorithm M is (c. d)-iifcrrettial private (DP) if for any neighboring datasets S' differ by arbitrary sample, and for any event E,
P[M(S) E E) & P (S") E E +
A common approach guarantee DP when approximating function g is via additive noise calibrated to g's sensitivity (Dwork et al. 2006). This is known as the Gaussian mechanism and widely used
DP deep learning, see more details in Lemma B.1
For the same differentially private mechanism, different privacy accountants (e.g.. Moments actountant (Abadi et al. 2016 Canonne et al., 2020), Gaussian differential privacy (GDP) (Dong et al. 2019 Bu et al. 2019 Fourier accountant (Koskela et al. 2020), each based on a different composition theory) accumulate the privacy risk E(a, n. p. ö, differently over T iterations. The next result shows that DP optimizers with global clipping is as private as those with local clipping, independent of the choice of the privacy accountant.
Theorem DP oplimizers with the local or global clipping are equally (e, 8),
While a DP model by definition is resilient to all types of privacy attacks, we illus- trate that DP-SGD, global offers similar pri- vacy protection to DP-SGD against the membership inference attacks (MIA) in Fig- ure 2 MIA is a common privacy attack by which the attacker aims determine whether a given dala point belongs to the sensitive training set [26, 38, 41, 48). In our setting, the black-box attacker uses a logis- tic regression that only has access to the prediction logits and labels. The privacy vulncrability is characterized as the attack model's AUC, while lower AUC is preferred.
yP-SGDDioohe!
0.6
TPR
non-DP no clipping
DP local clipping
global clipping
6.0
0.0
6.2
2.4
6.6
1.0
FPR
Figure Attack model's ROC-AUC on entire CTFAR10 in Scction
6.2
non-DP AUC, 0.717;
DP-SGDiocat, 0.644; DP-SGDDtota global, 0.648.
NUMERICAL RESULTS
We highlight that the global clipping works with any DP optimizers (e.g.. DP-Adam, DP- RMSprop, OP-FTRI et al. 2021), DP-SGD-JL(Bu et al. 2021a). etc.) that em- ploy the local clipping, with almost identical computational complexity (discussed in Ap- pendix D Empirically, DP optimizers with global clipping improve over existing DP op- timizers on the convergence of training and generalization losses. We thus reveal a novel phenomenon that DP optimizers play important roles in producing well-calibrated and reli- able models. For all experiments, we use the GDP privacy accountant, with Pytorch Opacus library and Google Colab P100 GPU. More details available in Appendix

---

Under review as a conference paper at ICLR 2022
In M-class classification problems, we denote the probability prediction for the i-th sample as Ty E RM so that f(x,) = argmax(T;;; then the accuracy is 1{f(z;; = yı). The confidence, Le., the probability associated with the predicted class maximum softmax probability, P; max [Ts]& and good calibration means the confidence is close to the accuracy Formally, we employ two popular calibration metries from (Nacini et al. 2015) Table the Expected Calibration Error (ECE) and the Maximum Calibration Error (MCB)
PP(( vil p) o||
ECE: P.,
MCE:
max pe[o.1]
(()())) vil p) p
ECE %
MCE %
non-DP
DP local
DP global
non-DP
DP local
DP global
CIFARIO
13.9
20.0
3.3
20.9
32.0
9.9
SNLI
13.0
22.0
17.6
34.7
62.5
28.9
MNIST
0.8
2.5
0.5
21.1
50.2
22.8
Table 3: Calibration metrics ECE and MCE by non-DP (no clipping) and DP optimizers.
Note that the SNLI's DP global stands for mix-up training described in Section 6.3
6.1 MNIST IMAGE DATA WITH CNN MODEL
On the MNIST dataset, which contains 60000 training samples and 10000 test samples of
28 28 grayscale images in 10 classes, we use the standard CNN in the DP libraries Google Facebook) (see Appendix E.1 for architecture) and train with DP-SGD. In Figure g both clippings result in (2.32, 10 -D, similar test accuracy (96% for local and 95% for global).
though the global clipping leads smaller loss. In right sub-plot of Figure X how Z affects the performance of global clipping, ceteris paribus.
we demonstrate
DP SED train DP-SGDuc list DP-S lest
3.34
Text Accuuracy
Test Accuracy
DP-StD DP 550
Epoch
100
Figure 3: Loss (left) and accuracy (right) on MNIST with 4-layer CNN under different clipping methods, batch size 256, learning rate 0.15, noise scale 1.1, clipping norm 1.0; for global clipping, we choose Z 210 as the maximum gradient bound, (c, (2.32, 10 10-5).
Porfect cal bration
Accuracy
Over-confidence
Acourccy
Under confidence
Acounary
84
Confidence
Confidence
Confidence
Figure 4: Reliability diagrams (left for non-DP; middle for global clipping: right for local clipping) on MNIST with 4-layer CNN.
In Figure 4 the reliability diagram (DeGroot & Fienberg 1983 Niculescu- Caruana 2005 displays the accuracy as a function of confidence. Graphically speaking, calibrated classifier is expected have blue bins close to the diagonal black dotted line. While the non- DP model is generally over-confident and thus not calibrated, the global clipping elfectively achieves nearly perfect calibration. In contrast, the classifier with local clipping not only mis mis-calibrated, but is 'bipolar disordered': ; it is either ovef-confident and inaccurate, or under-confident but highly accurate. This observed in all classification experiments.
6 Over-confident classifiers, with wrong prediction at one data point, reduce accuracy little but increase loss significantly due to large log ). since small probability is assigned to true class. in Tensorflow and Pytorch Opacus.
SSe httpp://ggh..accccceeeeeoee//t/s

---

Under review as a conference paper at ICLR 2022
6.2
CIFAR10 IMAGE DATA WITH CNN MODEL
DP layer
DP-SGD
645
DF SGDpsest flat
pGD fott
Text Acturacy E3
PP
Toct Loos
DP-SGD
24
0.0
DP- DP-50Dua: fat 500 poea
DP 500 layer
Epech Figure 5: Loss (left and middle) and accuracy (right) CIFARIO with 5-layer CNN under different clipping methods, batch size 250, learing rate 0.05, noise scale 1.3, Z = 75, clipping norm 1.5 (flat). For layerwise clipping, global: [1.5, 0.3] per layer (1.5 for weights, 0.3 for biases); local: [1.5, 1.5), (c = (1.96, 10-
Epoch
Epoch
CIFAR10 is a more challenging image datasct, which contains 50000 training samples and 10000 test samples of x2 color images in 10 classes. We use the standard CNN on Pytorch CIFARIO tutoria, (see Appendix E.2 for archilecture) and train with DP-SGD without pre- training (unlike (Abadi et al. 2016 Xu et al. 2020). which pretrain on CIFAR100). Both clippings result in (1.96, 10 DPP and the test accuracy (local: 47.6%; global: 43.5%: non- DP: 61.3%) is comparable with state-of-the-art in Paaperot et al. 2020), which is around 47% at this privacy budget. Clearly from Figure 5 global clipping has better convergence and similar accuracy than local clipping. Especially, local layerwise clipping can be unstable, as indicated by Theorem I From Figure G we can clearly see that DP-SGDtocal results in poorly calibrated classifiers on CIFAR10 but DP-SGD global is well-calibrated.
3.0
sration
Arcuracy
Ovenccmnideece Under confidence
Accuracy
Accuracy
85
1.0
33
4.2
0.2
Confidence
Confidence
Confidence
Figure 6: Reliability diagrams (left for non- DP; middle for global clipping; right for local clipping) on CIFARIO with 5-layer CNN.
6.3 SNLI TEXT DATA WITH BERT AND MIX-UP TRAINING
Morry My
8.m0
032
10-
635
1.5.
0.00
DP-Ads mWnco train
13.
AddamW..... best
DP-AdsmWyendd train
OP-AdamWWuur Adam
DP-AdamtNoca
test
315
DP AcamcM
26 teration=1000
Ierationxx000 42
200atioxx000
Figure 7: Loss (left), accuracy (middle) and calibration after switching clipping (right) SNLI with pre-trained BERT, batch size 32, learning rate 0.0005, noise scale 0.4, = 1000, clipping norm 0.1, (e, 8) (1.25, 1/550152).
Stanford Natural Language Inference (SNLI) collection of human-written English sen- tence paired with one of three classes: entailment, contradiction, or neutral. The dataset has 550152 training samples and 10000 test samples. We use the pre-trained BERT (Bidi- rectional Encoder Representations from Transformers) on Opacus tutoria("" TM which gives a state-of-the-art. privacy-accuracy result. Our BERT contains 108M parameters and we only train the last Transformer encoder, which has 7M parameters, using DP-AdamW. In
WW use SNLI 1.0 from Stt.i//Uiiiiirrrp///aaaaaaatttdd 10eee githuh httph//cwggggggaaaaaaaaaaaaaaaaa htw.ll/nnnneetttccaaiiiieeee
classifier ipymb

---

Under review as a conference paper at ICLR 2022
particular, we use mix-up training: for global clipping, we in fact train BERT with DP- SoDa for 3 epochs (51.5 x 10 iterations) and then use DP-SGD for an additional 2500 iterations. In other words, 95% of the training is done with local clipping but the last 5% is done with global clipping- For local clipping, DP-SGD is used for the entire training process of 54076 iterations.
Porfect calioration
62-
Oven-conideene Under-orniience
Accuracy
Acturaccy
02
Confidence
Confidence
Confidence
Figure 8: Reliability diagrams (left for non-DP; middle for global clipping; right for local clipping) on SNLI with BERT. Note that global clipping is only used for the last 2500 iterations out of the entire 54000 iterations.
Surprisingly, the existing DP optimizer does not minimize the loss at all, yet the accuracy still improves along the training. We again observe that global clipping has significantly better convergence than the local clipping (observe that when turned to global clipping in the last 2500 steps, the test loss decreases significantly from 1.79 to 1.08, and the training loss decreases from 1.81 to 1.47; while keeping local clipping has no effect on reducing the losses). The resulting global model also has similar accuracy (local: 74.1%; global: 73.1%; as a benchmark, non-DP: 85.4%), same privacy (e = 1.25, -1/550152) and much better calibration in comparison to the local clipping (see Table 3 We remark that all hyperparameters are the same as in the Opacus tutorial.
6.4 REGRESSION TASKS
On regression tasks, the performance measure and the loss function are unified as MSE Figure shows that global clipping is comparable if not better than local clipping. We experiment on the California Housing data (20640 samples, 8 features) and Wine Quality (1599 samples, 11 features, run with full-batch DP-GD). Additional experimental details are available in Appendix E.4
DP-GD
2>10
DD.
GD
Test Lozs
15
DP Adamyuea'
DP Adamyull
Ron-DP Adam
Epoch
Figure 9: Performance of DP optimizers under different clipping methods on the Wine Quality with Z = 400 (left) and the California Housing datascts with Z = 2000 (right).
DISCUSSION
In this paper, we establish a framework of the convergence analysis for DP deep learning, via the NTK matrix, that applies to general neural network architecture, loss function, and optimization algorithm. We show that in the continuous time analysis, the noise addition does not affect the convergence but the per-sample clipping does. We then propose the global clipping method, which has provable advantages in convergence with the same privacy guarantee and efficiency as the existing local clipping. Hence, one may apply two clippings interchangeably during the mix-up training. Our global clipping significantly outperform the local clipping in terms of loss and better calibration. Future directions include the discrete time analysis as well as mini-batches. This means that the added noise and the sub-sampling noise will come into effect, and requires analysis of stochastic differential equation.

---

Under review as a conference paper at ICLR 2022
8 ETHICS STATEMENT
The experiments in this work is conducted on publically available datasets. The methods in this paper should not raise ethical concerns.
REPRODUCIBILITY STATEMENT
Our code is easily reproducible, since we have already provide the full implementation in the Appendix [D] For the script that reproduces our experiments, we have submitted a set of template code that covers large portion of our experiments, For the details of our our datasets, we describe in details in section 0 and Appendix E We state our assumptions clearly in all our theoretical results, especially the theorem statements.
REFERENCES
Martin Abadi, Andy Chu, Tan Goodfellow, H Brendan McMahan, Tlya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308 318, 2016.
Zeyuan Allen Ahu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via peeepaarametiiiition. In International Conference on Machine Learning, pp. 242 252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 1rXii 2019a.
Sanjeov Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fino-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint Xiv: 08584, 2019b.
Eugene Bagdasaryan, Omid Poursaced, and Vitaly Shmatikov. Differential privacy has dis- parate impact on model accuracy. In Advances in Neural Information Processing Systems, pp. 15453 15462, 2019.
Racf Bassily, Adam Smith, and Abhradoep Thakurta. Private empirical risk minimization: Elficient algorithms and tight error bounds. In 2014 IEEE 55th Anneal Symposium on Foundations of Computer Science, pp. 464 473. IEEE, 2014.
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie Su. Deep learning with gaussian differential privacy. arXiv preprint 1rxiv:1911.11600 2019.
Zhiqi Bu, Sivakanth Gopi, Janardhan Kulkarni, Yin Tat Lee, Judy Hanwen Shen, and Uthaipon Tantipongpipat. Fast and memory efficient differentially privato-sgd via pro- jections. arXiv preprint arXiv:2102 03013, 2021a.
Zhiqi Bu, Shiyun Xu, and Kan Chen. A dynamical view on optimization algorithms of overparameterized neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 3187-3195. PMLR, 2021b.
Carole Cadwalladr and Emma Grahan-Harrison. Revealed: 50 million facebook profiles harvested for cambridge analytica in major data breach. The guardiin, 17:22, 2018.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differ- ential privacy. arXiv preprinl arXiv:2004.0001 2020.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th (USENIX) Security Symposium (( ((USENIX) Security 19), pp. 2019.
10

---

Under review as a conference paper at ICLR 2022
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Ex- tracting training data from large language models. arXiv preprint arXiv:2012.07880 2020.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private em- pirical risk minimization. Journal of Machine Learning Research, 12(3). 2011.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances in Neural Information Processing Systems, 33, 2020.
Gregory C Chow al. Analysis and control of dynamic economic systems. Wiley, 1975.
André Belotto da Silva and Maxime Gazeau. A general system of differential equations to model first-order adaptive algorithms. Journal of Machine Learning Research, 21(199) 1-42, 2020.
Alexande De Montjoye, Cósar A Hidalgo, Michel Verleysen, and Vincent D Blondel. Unique in the crowd: The privacy bounds human mobility. Scientific reports, 3(1):1-5, 2013.
Yees-Alex De Montjoye, Laura Radaelli, Vivek Kumar Singh, et al. Unique in the shopping mall: On the reidentifiability of credit card metadata. Science, (42()12)):536 539, 2015.
Morris H DeGroot and Stephen E. Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series D (The Statistician), (2(12))112 1222:2222,, 22, 1983.
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert Skeel, and Hartmut Neven. Bayesian sampling using stochastic gradient thermostats. 2014.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint arXim: 02388, 2019.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arxiv preprint arXim:1810.0000 2018.
John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 239-438. TEFE, 2013.
Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pp. 1-19. Springer, 2008.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-40) 407,, 2014.
Facebook. Pytorch Privacy library -bpruuy-ppauus..
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. arXiv preprint urXiv:2010.155 101.11110, 2020.
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint 172 2017.
Google. Tensorflow Privacy library.
11

---

Under review as a conference paper at ICLR 2022
Peter Kairouz, Brendan McMahan, Shuang Song. Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling arXiv preprint arXiv:2103.0000 2021.
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guar- antees using fft. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569. PMLR, 2020.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint Xrv: 06720, 2019.
Bai Li, Changyou Chen, Hao Liu, and Lawrence Carin. On connecting stochastic gradi- ent meme and differential privacy. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 557-566. PML.R, 2019.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang, Learning differentially private recurrent language models. arXiv preprint arXiv: 11100 06963, 2017.
H Brendan McMahan, Galen Andrew, Ulfar Erlingsson, Steve Chien, Nya Mironov, Nicolas Papernot, and Peter Kairouz. A general approach to adding differential privacy to iterative training procedures. Xrviv preprint arXic:1812.066 06210, 2018.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEFE Symposium on Foundations of Computer Science (FOCS 07), pp. 94-103. IEFE, 2007.
llya Mironov. Rényi differential privacy. In 2017 IEEE 30th Compuler Securily Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Mahdi Pakdaman Nacini, Gregory Cooper, and Milos Hauskrocht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI Conference Artificial Intelligence, volune 29, 2015.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o (1/k" 2). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
A Alexandru Nieulescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pp. 625- 632, 2005.
Paul Ohm. Broken promises of privacy: Responding to the surprising failure of anonymiza- tion. UCLA L. Rev., 57:1701, 2009.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. arXiv preprint 0rXim:2007.14190 2020.
Nait Phan, Xintao Wu, Han Hu, and Dejing Dou. Adaptive laplace mechanism: Differ- ential privacy preservation in deep learning. In 2017 IEEE International Conference on Data Mining (ICDM), pp. 385 394. IEEE, 2017.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compulational mathemalics and mathemalical physics, 4(5):1-17, 1964.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Lue Rocher, Julien M Hendrickx, and Yves-Alexandre De Montjoye. Estimating the success of re-identifiattins in incomplete datasets using generative models. Nature communica- tions, 10(1):1 9, 2019.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership infer- ence attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP); pp. 18... IEFF, 2017.
12

---

Under review as a conference paper at ICLR 2022
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 248-248. IEEE, 2013.
Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Mochine Learning, pp. 2493-2502. PMLR, 2015.
Zhiying Xu, Shuyu Shi, Alex X Liu, Jun Zhao, and Lin Chen. An adaptive and fast convergent approach to differentially private deep learning. In IEEE INFOCOM 2020- IEEE Conference on Computer Communications, pp. 1867 1876. IEEE, 2020.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- paramcterized deep relu networks. Machine Learning, 10943):467-492, 2020.
13


Reviews:
[{"review_id": "vpyJco7ImB0", "reviewer": "Reviewer_Yf7v", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Simple and elegant clipping\n- Nice theoretical analysis \n- Nice empirical showing", "summary_of_the_paper": "The paper proposes a new clipping method for DP-SGD. It is shown that this new clipping method performs favorably empirically. Furthermore, the paper analyzes the clipping method using NTK.", "summary_of_the_review": "I am in favor of this work. The global clipping is simple but elegant. Furthermore, the NTK analysis is nice and helps support the intuition behind the method. I think that using NTK to analyze differential privacy is actually a method with potentially widespread applicability. Furthermore, the empirical analysis of the method seems sound. The issue of calibration with DP-SGD is also interesting and understudied. I find few faults in this work, and the brevity of this review is a consequence of having little to critique. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "mVhmHVSAOBb", "reviewer": "Reviewer_b1Rw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### ***Overall merit of the paper.***\n\nThe problem of better understanding the properties of differentially private optimizers is an important topic within the ML community, as it would allow building more robust techniques with provable convergence guarantees. Moreover, the possibility of analyzing the dynamics using the continuous gradient flow seems to be an interesting idea, especially if it allows the introduction of new clipping methods improving the convergence of the algorithms. \n\n### ***Concerns and remarks to authors.***\n\nMy main concerns with this work are the technical quality and relevance of the contributions. I detail below the most important ones I have. \n\n**Relevance of studying GD instead of SGD.** At first glance, it seems that the authors are studying the well-known DP-SGD procedures and trying to improve the existing knowledge of this widely used algorithm. In fact, this is the method that is presented in Algorithm 1 and that is being used in most of the experiments (Sections 6.1, 6.2, 6.3). However, the theoretical contribution only studies full gradient descent, which is much less relevant in the context of deep learning because it is never used in practice due to its computational complexity. As a result, I think the authors overstate their contribution by stating that they provide a \"convergence theory for deep learning DP\". I think their analysis is more applicable to simple classification or regression tasks with small datasets. \n\n**Regarding the NTK framework.** The idea of studying the convergence dynamics of differentially private deep learning through the lens of gradient flow seems like a good idea, but I am not sure the authors properly used and analyzed existing tools from control theory. Here are some of my comments below. \n\n1. To build their whole theoretical framework, the authors explain that the derivative of the loss function is characterized by $\\dot{L} = \\frac{\\partial L}{\\partial f} HC \\frac{\\partial L}{\\partial f}^{T}$. Then, they introduce a set of new concepts extending the notion of matrix positivity to non-symmetric matrices (Definition 4.3), to analyze HC (because it might not be symmetric). However, from my understanding of the literature, it is not relevant to study HC directly. In fact, we can always rewrite the derivative of the loss function as $\\dot{L} = 1/2 \\frac{\\partial L}{\\partial f} (HC + (HC)^T) \\frac{\\partial L}{\\partial f}^{T}$. Therefore, the analysis of $(HC + (HC)^T)$ is sufficient to characterize $\\dot{L}$ and does not require the introduction of new concepts since $(HC + (HC)^T)$ is indeed symmetric. \n2. It is unclear to me how certainty equivalence can be applied to provide a proof for Fact 4.1. I think that certainty equivalence is related to the fact that the optimal control is the same; that is, the system with zero-mean additive noise has the same optimal control law as the system without noise. But, as I understand it, equivalence of optimal control laws does not mean equivalence of dynamics. Moreover, certainty equivalence does not hold true when the dynamical system is nonlinear, which is indeed the case here.\n\n**Unfair comparison between global and local clipping.** The paper presents a new method of clipping called global clipping and compares it to local clipping (previous method) both theoretically and empirically.  I have some concerns on both sides, explained below.\n\n1. From a theoretical point of view, the authors claim that global clipping offers better convergence guarantees than local clipping. To justify this claim, they present two theorems stating that local clipping can have a bad impact on convergence (Theorem 1) while global clipping does not (Theorem 2). However, the comparison does not seem fair to me. Indeed, in order to show that global clipping does not have a bad impact on convergence, the authors make the additional assumption that $Z$ (one of the clipping parameters) is large enough so that no vector is dropped during the procedure.  In fact, this assumption is equivalent to saying that there exists a real number $M < \\infty$ such that for all $i$ and $t$, $\\Vert v_t^{(i)} \\Vert \\leq M$. In this particular case, taking $Z \\geq M$, the global clipping amounts to rescaling each gradient with a fixed constant; therefore, it does not hinder the convergence (it is actually equivalent to changing the learning rate). As the authors point out in Footnote 5, this assumption is central to the proof of Theorem 2 and cannot be relaxed. But if we were to assume the existence of such an upper bound $M$ on the gradients in Theorem 1 as well, then we could also show that local clipping does not impede the learning procedure simply by taking $R \\geq M$. As a result, the paper does not present a fair comparison of the two clipping methods, and as I understand the results at this point, there is no way to argue that global clipping is better than local clipping from a theoretical viewpoint.\n2. From an empirical standpoint, while I agree that global clipping seems to help in classifier calibration, I do not think it can be considered to have similar performance as local clipping. Looking at the experimental results (e.g., Figures 3 and 5), it appears that DP-SGD with global clipping generally takes longer to converge than DP-SGD with local clipping. While this may not be very important in standard deep learning, it is critical when considering privacy because each learning step increases the final privacy budget. Therefore, DP-SGD with global clipping will use a larger privacy budget to achieve the same level of accuracy as DP-SGD with local clipping.\n\n\n", "summary_of_the_paper": "This paper studies the problem of understanding the convergence of differentially private deep learning models. The most common technique to ensure differential privacy (DP) in deep learning is to adapt the SGD algorithm by clipping the gradient at each learning step before perturbing it with Gaussian noise. The present work proposes to study the impact the clipping step and the noise injection can have on the convergence of the algorithm. In doing so, the authors claim to make several contributions summarized below.\n\n1. Provide a characterization of the training dynamics of differentially private gradient descent methods through the lens of gradient flow theory, using neural tangent matrices (NTK).  The authors claim that this framework enables a fine-grained analysis of the impact of clipping and noise injection on the convergence of deep learning algorithms. \n2. Develop a new clipping method called \"global clipping\" that improves convergence and mitigates the lack of calibration of differential private gradient descent methods. Moreover, this new approach does not change the DP guarantees of the gradient descent algorithm, is easy to implement and is as computationally efficient as the previous clipping methods (called \"local clipping\" in the paper). \n", "summary_of_the_review": "\nOverall, while I think this paper explores an interesting question, I also think it overstates its contributions and impact. In particular, I think that the utility of global clipping is not sufficiently well supported by theory or experiments. In addition, I think that the use of gradient flow to analyze the dynamics of DP-SGD is interesting but lacks clarity at this time. For the above reasons, I will argue for rejection.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bzHtcciY_lD", "reviewer": "Reviewer_Aa4t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n  - The proposed global clipping is very simple and intuitive to implement.\n  - The (lack-of) effects of Gaussian noise on the gradient flow is a very neat fact.\n  - The analysis of the proposed global clipping is analysed in various settings (with even more details in the appendix).\n  - Experiments are very promising.\n\nWeaknesses:\n  - Claims on convergence rely heavily on the NTK matrix being positive-definite. However, is this the case in practice? I know that the Fisher information matrix has mostly close to zero eigenvalues (e.g. \"Universal Statistics of Fisher Information in\nDeep Neural Networks: Mean Field Approach 2019\"), but are there similar characterizations of the spectrum for NTK?\n  - Similarly to the above, does the positive-definiteness hold in practice?\n  - Theorem 2 relies on the global maximum norm bound $ Z $ for the batch gradients. How often does this happen in practice?\n  - The claim of Theorem 3 seems to be worded quite strongly. My initial interpretation of it was that local clipping is $(\\varepsilon, \\delta)$-DP iff global clipping is $(\\varepsilon, \\delta)$-DP. However, I don't believe this is the case given the proof.\n\nOther / Minor:\n  - Inconsistent use of oxford comma (abstract + intro versus rest of paper).\n  - For Figure 1, it would help to emphasis the global clipping by making the grey circle smaller.\n  - Algorithm 2 mentioned in main text needs a pointer to appendix.\n  - It would be worth stating that you are looking at fair loss function where no loss is incurred for perfect prediction (e.g. \"Information, Divergence and Risk for Binary Experiments 2011\"). Especially so since this is key to the proof of Theorem 1 statement 4.\n  - A few typos in the appendix:\n       - Proof of Theorem 2 statement 1: at $ x^{T} x \\mathbf{H} x $;\n       - \"citep\" above Lemma B.1;\n       - Lemma B.1 \"supreme\" -> \"supremum\".\n  - Top of Section 4 \"yet and our\" -> \"yet our\".", "summary_of_the_paper": "The paper analysis differentially private (DP) optimization convergence in neural networks by examining the neural tangent kernel (NTK). In particular, the papers analysis focuses on DP optimization which utilize gradient clipping and the Gaussian mechanism for gradient updates. Through the analysis of the NTK, an alternative clipping operation is proposed which has guarantees for convergence of the loss function. In addition, this alternative clipping operation provides a DP guarantee. Experiments in the paper then verify that the proposed clipping performs well in practice.", "summary_of_the_review": "Overall I would recommend an accept. The simplicity of the approach and the improvements shown in the experiments show that the global clipping has promise. However, there are a couple of aspects in the paper which need to be addressed. In particular, I believe that the text of Theorem 3 is worded too strongly.\n\n---\n\nEdit: I have changed my score from 6 -> 5 as a result of reviewer discussion. In particular, due to how the assumptions of Theorems 1 & 2 are not the same due to the assumption on the gradient norm bounds. Further discussion / analysis is needed for the violation or removal of this particular assumption (following the critics presented in LL2P and b1Rw's reviews).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0n_EIDxJXPh", "reviewer": "Reviewer_LL2P", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think that using the NTK framework to analyze the converge of DP-SGD is a very interesting direction. However, the theoretical claims seem not surprising and I question how useful the global clipping strategy is for practical purposes. First, according to theorem 2, the convergence of SGD with global clipping is only guaranteed when we can find a parameter Z big enough such that all sample gradients have norm less than Z. However, it is not possible to choose such a Z in advance before running the algorithm, therefore theorem 2 it’s not very informative for the practical algorithm (i.e., what should we set Z too?). In practice, Z is a hyperparamter that needs to be tune before running the algorithm since, according to figure 3 (rightmost plot), the choice of Z has a big influence in the final model accuracy. By using the original local clipping strategy, one does not need to worry about finding an optimal Z, thus one could claim local clipping is more practical. \n\nOn the empirical evaluation results are also unsatisfactory in my view. Somehow, using global clipping results in lower test loss that using local clipping but local clipping seems to give better accuracy, this phenomenon is not explained in the paper. Specially in the hard CIFAR10 setting, using global clipping does not seem to make a big difference. Furthermore, running global clipping requires knowledge of the Z parameter but that’s not required for local clipping. Therefore, I’m not convince that I should use global clipping vs local clipping for practical applications. \n\n\n\nQuestions:\n- The paper makes then case that global clipping reduces the clipping bias that occurs with local clipping. However when Z is small, removing samples from the batch can also creating a bias. How can we compare then bias of both methods and can one create an example where global clipping would change the gradient direction more than (or add more bias) local clipping would?\n\n- I don’t understand what figure 1 is trying to convey. My understanding is that the figure is comparing the average clipped gradient with global and local clipping. However it would be good to compare against some baseline. For example, we could compare against  the gradient of the average gradient without clipping. \n\n\n\n\n\nOther comments: \nI was confused by definition 4.3. Is the definition 4.3 equivalent to positive-semi-definite matrix?", "summary_of_the_paper": "The paper analyzes convergence of DP-SGD using the NTK framework. The general idea is that the learning dynamics of SGD converge when the NTK matrix is positive-semi-definite.  They  characterize the effect of clipping and noise and Propose global clipping strategy. The global clipping idea consists of eliminating samples that have gradient norm bigger than some threshold and then applies a common clipping multiplier for each sample gradient. The authors claim that global clipping reduces gradient bias. \n\n\nGradient Clipping Summary: DP-SGD consist of the following steps: Over T rounds: 1) the algorithm samples a batch of samples from a dataset I_t. 2) it computes the gradient of each individual samples. 3) Each gradient sample is multiplied by a number such that the final gradient has norm bounded by R. 4) Finally, all clipped gradients are aggregated, noise is added to the average clipped gradient and the result is applied to update the model.\n\nDifference between local and global clipping:  In local clipping, the gradient of each sample is multiplied by a factor specific to that sample such that the gradient  norm  of each sample is bounded by R. In global clipping, there is an additional parameter Z, each sample in a batch with gradient norm smaller than Z are multiplied by a constant factor R/Z and samples with gradient norm bigger than Z are not used. Therefore in global clipping each sample in a batch has gradient norm bounded by R. The intuition behind global clipping is that each gradient in a batch gets multiplied by a constant factor, this means that the direction of the aggregated gradient should be preserve. \n\n\nConvergence Analysis: The convergence analysis uses the Neural Tangent Kernel (NTK) framework. The premise is that, the convergence of SGD is controlled by the NTK matrix in that the condition for convergence is that the NTK matrix is positive-semi-definite. The paper provides two main theorems: The first one claims that local clipping cannot guarantee convergence because local clipping can break the conditions for convergence under the NTK framework. The second theorem says that when the parameter Z is large then global clipping can guarantee convergence because each gradient is multiplied by a constant factor and does not affect the positive-semi-definitess of the NTK matrix. \n\nExperiments: The paper empirically evaluates global clipping on the MNIST and CIFAR10 dataset. They \n", "summary_of_the_review": "The paper has a very interesting theme but I find the analysis and conclusion unsatisfactory. Furthermore, the empirical evaluation is not more convincing. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The major concern with this paper is the unfair comparison between global and local clipping (at least from the theoretical point of view). The assumption that the norms of the gradients are bounded in Theorem 2 is too strict for the following reasons. Clipping has been introduced exactly because we cannot assume the norm of the gradient to be bounded by a fixed constant  in the first place. Accordingly, comparing two clipping methods under the bounded gradient assumption does not seem relevant. Further, the two methods are not studied under the same set of assumptions (In Theorem 1, the norm of the gradient is not assumed to be bounded, but in Theorem 2 it is). 
A fair comparison needs to be presented to make the case for the proposed method.
Decision: Reject