On the Convergence and Calibration of Deep Learning with Differential Privacy

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.

heading: 1 Introduction
text: Deep learning has achieved tremendous success in many applications that involve crowdsourced 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-Harrison, 2018; Rocher et al., 2019; Ohm, 2009; De Montjoye et al., 2013; 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 (Shokri et al., 2017; Carlini et al., 2019). In another example, the attackers can extract a person’s name, email address, phone number, and physical address from the billion-parameter 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), a mathematically rigorous approach, to protect against leakage of private information (Abadi et al., 2016; McSherry & Talwar, 2007; McMahan et al., 2017; 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 et al., 2014), DP-Adam (Bu et al., 2019), DP-SGLD (Wang et al., 2015; Li et al., 2019), DP-FTRL (Kairouz et al., 2021), DP-FedSGD and DP-FedAvg (McMahan et al., 2017).
Algorithmically speaking, DP optimizers generally have two extra steps in comparison to non-DP standard optimizers: the per-sample clipping and the random noise addition, so that DP optimizers descend in the direction of the averaged, clipped, noisy gradient (see Figure 1). 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-art CIFAR10 accuracy with DP is ≈ 70% without pre-training (Papernot et al., 2020) (while the same non-DP networks can
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-accuracy 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 theoretical viewpoint, which is necessary to understand and 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 to real datasets.
Our Contributions
• We explicitly characterize the general training dynamics of deep learning with DP gradient 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 a 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 same privacy guarantee and computational efficiency as the local clipping, which leads to a mix-up training strategy where local and global clippings are applied interchangeably.
• Our global clipping is easy-to-code (see Appendix D) and generalizable to arbitrary optimizers, network architectures, loss functions, and tasks including federated learning.
A quick preview of the comparison among the DP optimizers with the local and the global clipping is as follows:

heading: 2 Warmup: Convergence of Non-Private Gradient Descent
text: 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 particular, we analyze the training dynamics using the neural tangent kernel (NTK) matrix1.
Suppose a neural network f is governed by weights w, with samples xi and labels yi (i = 1, ..., n). Denote the prediction by fi = f(xi,w), and the per-sample loss by `i = `(f(xi,w), yi) for some loss function `. We define the objective function L to be the average of per-sample losses L(w) = 1n ∑n i=1 `(f(xi,w), yi). The discrete gradient descent with a step size η, and the corresponding gradient flow2 are:
w(k + 1) = w(k)− η ∂L ∂w
> , and ẇ(t) = − ∂L
∂w
> = − 1
n ∑ i ∇w`i(t).
1We emphasize that our analysis works on any neural networks, not limited to the infinitely wide or over-parameterized ones. Put differently, we don’t assume the NTK matrix H to be deterministic nor nearly time-independent, as was the case in (Arora et al., 2019a; Lee et al., 2019; Du et al., 2018; Allen-Zhu et al., 2019; Zou et al., 2020; Fort et al., 2020; Arora et al., 2019b).
2I.e., the ordinary differential equation (ODE) describing the weight updates with infinitely small step size η → 0 in the continuous time.
Applying the chain rules, we obtain the following general dynamics of the loss L,
L̇ = ∂L ∂w ẇ = − ∂L ∂w ∂L ∂w
> = −∂L
∂f
∂f
∂w
∂f
∂w
> ∂L
∂f
> = −∂L
∂f H(t)
∂L
∂f
> , (2.1)
where ∂L∂f = 1 n ( ∂`1 ∂f1 , ..., ∂`n∂fn ) ∈ R 1×n, and the Gram matrix H(t) := ∂f∂w ∂f ∂w
> ∈ Rn×n is known
as the NTK matrix, which is positive semi-definite and crucial to analyzing the convergence behavior. To give a concrete example, let ` be the MSE loss `i(w) = (f(xi,w) − yi)2 and LMSE = 1 n ∑ i(fi − yi)2, then L̇MSE = −4(f − y)>H(t)(f − y)/n2. Furthermore, if H(t) is positive definite, the MSE loss LMSE → 0 exponentially fast (Du et al., 2018; Allen-Zhu et al., 2019; Zou et al., 2020) , the cross-entropy loss LCE → 0 at rate O(1/t) and any loss convex in the prediction L = ∑ i `i/n converges to 0 (Allen-Zhu et al., 2019).

heading: 3 Differentially Private Gradient Methods and Global Clipping
text: 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 1 and more optimizers such as DP-Adam and DP-FedAvg (McMahan 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.1.
Algorithm 1 DP-SGD (with local or global flat per-sample clipping)
Parameters: initial weights w0, learning rate ηt, subsampling probability p, number of iterations T , noise scale σ, gradient norm bound R, maximum norm bound Z ≥ R.
for t = 0, . . . , T − 1 do Subsample a batch It ⊆ {1, . . . , n} from training set with probability p for i ∈ It do
v (i) t ← ∇w`(f(xi,wt), yi) Option 1: Clocal,i = min { 1, R/‖v(i)t ‖2 }
. Local clipping factor (existing)
Option 2: Cglobal,i ≡ { R/Z if ‖v(i)t ‖2 ≤ Z 0 if ‖v(i)t ‖2 > Z
. Global clipping factor (ours)
v̄ (i) t ← Ci · v (i) t . Clip the gradient V̄t ← ∑ i∈It v̄ (i) t . Sum over batch
wt+1 ← wt − ηt|It| ( V̄t + σR · N (0, I) ) . Apply Gaussian mechanism and descend
Although the per-sample clipping is widely applied in DP deep learning, its effect on convergence remains a mystery. Empirical observations have found that optimizers with the per-sample clipping (even when no noise is present) have much worse convergence and accuracy (Abadi et al., 2016; Bagdasaryan et 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 Clocal or Cglobal when it is clear from the context.
We propose and analyze a new clipping, namely the global clipping (see Option 2 in Algorithm 1), 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 ∇w`i compare its length to R and multiplied with a sample-specific clipping factor 0 < Ci ≤ 1. In global clipping, only ∇w`i with norm smaller than Z is used (otherwise Ci = 0) and multiplied with a 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-definiteness of the NTK matrix via Theorem 2.

heading: 4 Convergence Analysis of DP Optimizers
text: In this section, we analyze the weight and loss dynamics of DP optimizers with the local or global per-sample clipping, denoted in the subscript, e.g., DP-SGDlocal and DP-SGDglobal. Our narrative here focuses on the widely used DP-GD for the sake of simplicity, yet and our analysis generalizes to other full-batch DP optimizers such as DP-HeavyBall, DP-RMSprop, and DP-Adam as well (see Theorem 4 and Appendix F).

heading: 4.1 Effect of Noise Addition on Convergence
text: Our first result is easy yet surprising: the gradient flow of a stochastic noisy GD with nonzero noise (4.1) is the same as that of a deterministic dynamics without the noise (4.2). Put differently, the noise addition has no effect on the convergence of DP optimizers in the continuous time gradient flow. This is a 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 1,
w(k + 1) = w(k)− η n (∑ i ∇w`iCi + σR · N (0, 1) ) . (4.1)
Notice that this general dynamics covers both the non-DP GD (σ = 0 and Ci ≡ 1) and DP-GD with local or global clipping. Through Fact 4.1, we claim that the gradient flow of (4.1) is the same ODE regardless of the value of σ, whose proof is delayed to Appendix B.
Fact 4.1. For all σ ≥ 0, the gradient descent in (4.1) has the continuous gradient flow
dw(t) = − 1 n ∑ i ∇w`i(t)Ci(t)dt. (4.2)
This result shares the spirit of the conventional wisdom3 that tune the clipping norm C first (e.g. setting σ = 0 or 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: as η → 0, different σ result in the same gradient flow.

heading: 4.2 Effect of Per-Sample Clipping on NTK Matrix
text: We move on to analyze the effect of the per-sample clipping on the DP training (4.2). It 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 linear algebra properties, especially the positive semi-definiteness, which we define below in two notions for a general matrix.
Definition 4.3. For a (not necessarily symmetric) matrix A, it is
1. positive in quadratic form if and only if x>Ax ≥ 0 for every non-zero x; 2. positive in eigenvalues if and only if all eigenvalues of A are non-negative.
3See https://github.com/pytorch/opacus/blob/master/tutorials/building_image_classifier.ipynb
These two positivity definitions are equivalent for a symmetric or Hermitian matrix, but not so for non-symmetric matrices. We illustrate this difference in Appendix A with some concrete examples. Next, we introduce two styles of per-sample clippings. Both can be implemented locally or globally.
Flat Clipping The DP-GD described in Algorithm 1 and (4.1), with the gradient flow (4.2), is equipped with the flat clipping (McMahan et al., 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 ẇ = − 1 n2 ∑ j ∇w`j ∑ i ∇w`iCi = − ∂L ∂f HC ∂L ∂f > , (4.3)
where C(t) = diag(C1, · · · , Cn) is the clipping matrix, with Ci defined in Algorithm 1.
Layerwise Clipping. We additionally analyze another widely used clipping – the layerwise 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 Rr, as demonstrated in Algorithm 2. Hence L̇ = − ∑ r ∂L ∂f HrCr ∂L ∂f > , where the layerwise NTK matrix Hr = ∂f ∂wr ∂f ∂wr > , and Cr(t) = diag(C1,r, · · · , Cn,r).

heading: 4.3 Local Per-Sample Clipping Breaks NTK Positivity
text: 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-definiteness of the NTK matrix4.
Theorem 1. For an arbitrary neural network and a loss convex in f , suppose we clip the per-sample gradients locally, and assume H(t) 0, then in the gradient flow of DP-GD: 1. The local flat clipping has the loss dynamics in (4.3), with NTK matrix H(t)Clocal(t),
which may not be symmetric nor positive in quadratic form, but is positive in eigenvalues. 2. The local layerwise clipping has the loss dynamics with NTK matrix ∑ r Hr(t)Clocal,r(t),
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.
4. If the loss L(t) converges, for the flat clipping, it converges to 0; for the layerwise clipping, it may converge to a 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 7.

heading: 4.4 Global Per-Sample Clipping Preserves NTK Positivity with Large Z
text: Now we switch gears to our global clipping. At each iteration when Z is sufficiently large so that no per-sample gradient is screened out, the global clipping clearly corresponds to a symmetric and positive semi-definite NTK matrix H(t)C(t) in flat clipping and ∑ r Hr(t)Cr(t) in layerwise clipping, since all per-sample gradients share the same clipping factor. As a result, the clipping matrices are indeed scalar in that C = CI in (4.3) and Cr = CrI in (B.1). Hence we obtain the following result for the global clipping.
Theorem 2. For an arbitrary neural network and a loss convex in f , suppose we clip the per-sample gradients globally, assuming H(t) 0 and ‖v(i)t ‖2 ≤ Z,5 then in the gradient flow of DP-GD:
1. The global flat (resp. layerwise) clipping has loss dynamics in (4.3), with NTK matrix H(t)Cglobal(t) (resp. ∑ r Hr(t)Cglobal,r(t)), which is symmetric and positive definite. 2. For both global flat and layerwise clipping, the loss L(t) decreases monotonically to 0.
4It is a fact that the product of a symmetric positive definite matrices and a positive diagonal matrix may not be symmetric nor positive in quadratic form. This is shown in Appendix A.
5If 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.
We prove Theorem 2 in Appendix B and the benefits of the global clipping are assessed in Section 6. Our findings from Theorem 1 and Theorem 2 are visualized in the left plot of Figure 9 and summarized in Table 2, which further leads to Table 1.

heading: 5 Privacy Analysis of DP Optimizers
text: In this section we define DP and prove that DP optimizers using the global clipping have the same privacy guarantee as 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. A randomized algorithm M is (ε, δ)-differentially private (DP) if for any neighboring datasets S, S′ differ by an arbitrary sample, and for any event E,
P[M(S) ∈ E] 6 eεP [M (S′) ∈ E] + δ.
A common approach to guarantee DP when approximating a 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 in DP deep learning, see more details in Lemma B.1.
For the same differentially private mechanism, different privacy accountants (e.g., Moments accountant (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 (σ, n, p, δ, T ) 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 3. DP optimizers with the local or global clipping are equally ( , δ)-DP.
0.0 0.2 0.4 0.6 0.8 1.0 FPR
0.0
0.2
0.4
0.6
0.8
1.0
TP R
non-DP no clipping DP local clipping DP global clipping

heading: 6 Numerical Results
text: We highlight that the global clipping works with any DP optimizers (e.g., DP-Adam, DPRMSprop, DP-FTRL(Kairouz et al., 2021), DP-SGD-JL(Bu et al., 2021a), etc.) that employ the local clipping, with almost identical computational complexity (discussed in Appendix D). Empirically, DP optimizers with global clipping improve over existing DP optimizers 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 reliable models. For all experiments, we use the GDP privacy accountant, with Pytorch Opacus library and on a Google Colab P100 GPU. More details are available in Appendix E.
InM -class classification problems, we denote the probability prediction for the i-th sample as πi ∈ RM so that f(xi) = argmax(πi), then the accuracy is 1{f(xi) = yi}. The confidence, i.e., the probability associated with the predicted class or maximum softmax probability, is P̂i := max M k=1[πi]k and a good calibration means the confidence is close to the accuracy
6. Formally, we employ two popular calibration metrics from (Naeini et al., 2015) in Table 3: the Expected Calibration Error (ECE) and the Maximum Calibration Error (MCE)
ECE: EP̂i [∣∣∣P(f(xi) = yi|P̂i = p)− p∣∣∣] , MCE: max
p∈[0,1] ∣∣∣P(f(xi) = yi|P̂i = p)− p∣∣∣. ECE % MCE %
non-DP DP local DP global non-DP DP local DP global CIFAR10 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.

heading: 6.1 MNIST image data with CNN model
text: 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 libraries7(Google; Facebook) (see Appendix E.1 for architecture) and train with DP-SGD. In Figure 3, both clippings result in (2.32, 10−5)-DP, similar test accuracy (96% for local and 95% for global), though the global clipping leads to smaller loss. In right sub-plot of Figure 3, we demonstrate how Z affects the performance of global clipping, ceteris paribus.
In Figure 4, the reliability diagram (DeGroot & Fienberg, 1983; Niculescu-Mizil & Caruana, 2005) displays the accuracy as a function of confidence. Graphically speaking, a calibrated classifier is expected to have blue bins close to the diagonal black dotted line. While the nonDP model is generally over-confident and thus not calibrated, the global clipping effectively achieves nearly perfect calibration. In contrast, the classifier with local clipping is not only mis-calibrated, but is ‘bipolar disordered’: it is either over-confident and inaccurate, or under-confident but highly accurate. This is observed in all classification experiments.
6Over-confident classifiers, with wrong prediction at one data point, reduce accuracy a little but increase loss significantly due to large log(πyi), since small probability is assigned to true class.
7See https://github.com/tensorflow/privacy/tree/master/tutorials in Tensorflow and https://github.com/pytorch/opacus/blob/master/examples/mnist.py in Pytorch Opacus.

heading: 6.2 CIFAR10 image data with CNN model
text: CIFAR10 is a more challenging image dataset, which contains 50000 training samples and 10000 test samples of 32×32 color images in 10 classes. We use the standard CNN on Pytorch CIFAR10 tutorial8 (see Appendix E.2 for architecture) and train with DP-SGD without pretraining (unlike (Abadi et al., 2016; Xu et al., 2020), which pretrain on CIFAR100). Both clippings result in (1.96, 10−5)-DP and the test accuracy (local: 47.6%; global: 43.5%; nonDP: 61.3%) is comparable with state-of-the-art in (Papernot 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 1. From Figure 6, we can clearly see that DP-SGDlocal results in poorly calibrated classifiers on CIFAR10 but DP-SGDglobal is well-calibrated.

heading: 6.3 SNLI text data with BERT and mix-up training
text: Stanford Natural Language Inference (SNLI) 9 is a collection of human-written English sentence 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 (Bidirectional Encoder Representations from Transformers) on Opacus tutorial10, 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
8See https://pytorch.org/tutorials/beginner/blitz/cifar10_tutorial.html. 9We use SNLI 1.0 from https://nlp.stanford.edu/projects/snli/
10See github pytorch/opacus/blob/master/tutorials/building_text_classifier.ipynb.
particular, we use a mix-up training: for global clipping, we in fact train BERT with DPSGDlocal for 3 epochs (51.5 × 103 iterations) and then use DP-SGDglobal 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-SGDlocal is used for the entire training process of 54076 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 ( = 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.

heading: 6.4 Regression Tasks
text: On regression tasks, the performance measure and the loss function are unified as MSE. Figure 9 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.

heading: 2 × 100

heading: 7 Discussion
text: 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.

heading: 8 Ethics Statement
text: The experiments in this work is conducted on publically available datasets. The methods in this paper should not raise ethical concerns.

heading: 9 Reproducibility Statement
text: 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 a large portion of our experiments. For the details of our our datasets, we describe in details in section 6 and Appendix E. We state our assumptions clearly in all our theoretical results, especially in the theorem statements.

Review summaries:
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.

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.    Gradient 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.  Difference 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.    Convergence 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.   Experiments: The paper empirically evaluates global clipping on the MNIST and CIFAR10 dataset. They  

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.  1. 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.  2. 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).  

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.