Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger

Introduction

Deep learning has achieved impressive progress in a wide range of tasks. These successes are made available, in part, by the collection of large datasets, sometimes containing sensitive private information of individual data points. Prior works have illustrated that deep learning models pose severe privacy risks to individual subjects in the training data and are susceptible to various practical attacks. For example, machine learning services such as Google Prediction API and Amazon Machine Learning can leak membership information from the purchase records ; the GPT2 language models auto-complete texts that contain someone’s full name, phone number, email address, etc., from the training data that it memorizes, if invoked by specific prefixes .

Differential privacy (DP) is a formal definition of privacy that has been shown to prevent the aforementioned privacy risks in deep learning . At a high level, the key difference between the DP deep learning and the standard one is whether the gradient is privately released. In other words, while the standard optimizers update on $\sum_{i}\bm{g}_{i}$, the DP optimizers update on the private gradient:

In comparison to the regular training (1.2), two additional DP-specific hyperparameters $R$ and $\sigma$ need to be determined in DP learning (1.1). On the one hand, setting the noise multiplier $\sigma$ is easy and can be derived analytically prior to the training. Whenever the privacy budget $(\epsilon,\delta)$ is determined, one can apply off-the-shelf privacy accounting tools in Section 2.1 to determine $\sigma$, based on the subsampling probability $p$ and the number of iterations $T$:

On the other hand, the choice of clipping threshold $R$ is crucial to the performance of DP models, yet the hyperparameter tuning is much labor-intensive. Recent advances of DP deep learning on ImageNet and on E2E datasets , using ResNet18 and GPT2 respectively, illustrate that the performance is very sensitive to $R$. We have reproduced their results in Figure 1. Observe that on ImageNet, ResNet18 can drop from the highest 45% accuracy to 31% if $R$ is chosen 2 times larger, and to 0.1% if $R$ is chosen 4 times larger. Similar drastic drop can also be observed in [38, Figure 3] even if the noise multiplier $\sigma=0$. Unlike the noise multiplier $\sigma$, the clipping threshold $R$ cannot be inferred from the privacy budget $(\epsilon,\delta)$ and have to be tuned. Consequently, DP training necessarily requires an expensive 2D grid search for $(R,\eta)$, like Figure 1, whereas the regular training only requires an easy 1D grid search for $\eta$. Even worse, the difficulty of tuning a per-layer clipping threshold vector , i.e. one clipping threshold for one layer, may increase exponentially as the number of layers increases.

To save the effort of tuning $R$, previous researches have proposed different approaches. In , researchers advocate to use data-adaptive information to select $R$, such as a specified quantile of the gradient norm distribution. These adaptive clipping methods can be a little ad-hoc: they often replace the need to tune $R$ by the need to tune one or more new hyperparameters, e.g. the quantile to use and the ratio to split the privacy budget between the quantile decision and the gradient perturbation. Another approach used by the practitioners is to replace the single 2D grid search by multiple cheaper 1D grid searches. For example, the researchers propose, in [38, Section 3.3] to fine-tune $\eta$ with non-DP SGD, fix $\eta$ and sweep over various values of the clipping threshold $R$ with DP-SGD, then further fix $R$ and do one more grid search on $\eta$. However, tuning $R$ formally in a data-dependent way (e.g. through cross-validation) introduces additional privacy loss , and most existing empirical work does not privately conduct hyperparameter tuning.

We take a completely different route by proposing a new clipping principle that removes $R$, instead of coming up with methods to find the appropriate $R$. We term our method as automatic clipping and the DP optimizers using it as automatic DP optimizers. Our contributions are:

We propose the automatic clipping in (4.1) that expunges the clipping threshold from general DP optimizers, making DP training as amenable as regular training. In large-scale tasks (GPT-level) like Figure 1, our automatic clipping can reduce the cost of ablation study by $5\times$The hyperparameter tuning of $(R,\eta)$ takes days (e.g. GPT2 ) to months (e.g. GPT3-175B) on large foundation models, highlighting the significance of our method to expunge the additional $R$..

We show that automatic DP optimizers are as private and efficient as existing DP optimizers.

We show in Theorem 4 that automatic DP-SGD converges in the non-convex setting, at the same asymptotic convergence rate as the standard SGD. Our theoretical analysis successfully explains the training behaviors of deep learning in previous empirical works.

We demonstrate the superiority of automatic clipping on a variety of vision and language tasks, especially with large models including ResNet, RoBERTa and GPT2.

In Appendix K, we include simple code snippets that demonstrate how easy it is to switch from Abadi’s clipping to our automatic clipping in popular codebases, e.g. Opacus and ObJAX.

Preliminaries

We consider the $(\epsilon,\delta)$-DP in Definition 2.1, where smaller $(\epsilon,\delta)$ means stronger privacy guarantee.

A randomized algorithm $M$ is $(\varepsilon,\delta)$-differentially private (DP) if for any two neighboring datasets $S,S^{\prime}$ (i.e. if one can obtain $S^{\prime}$ by adding or removing one data point from $S$), and for any event $E$,

In words, DP restricts the influence of an arbitrary sample, so that the information contributed by such sample is limited and less vulnerable to privacy attacks. In deep learning, DP is achieved by applying the subsampled Gaussian mechanism to privatize the minibatch gradients during training.

As illustrated in Equation 1.1, the subsampled Gaussian mechanism involves (I) sampling a minibatch by including each data point iid with probability $p$ (II) per-sample gradient clipping to bound the $l_{2}$ norm sensitivity at $R$ and (III) adding independent Gaussian noise proportional to $R$ and $\sigma$, where $\sigma$ is derived from the privacy budget $(\epsilon,\delta)$. This can be realized by leveraging a variety of modern privacy accounting tools, such as Renyi DP (or moments accountant) , Privacy Loss distribution (Fourier accountants) , or Gaussian DP .

2 Differentially Private optimizers with general clipping operations

Privately released stochastic gradients (through the Gaussian mechanism) can be used by various off-the-shelf optimizers, including DP-SGD in (1.3), DP-HeavyBall, DP-AdaGrad, DP-Adam, DP-FedAvg/FedSGD , etc. To improve the performance of DP optimizers, previous researches on the per-sample clipping can be classified into two categories.

Motivation

One intriguing observation that we can make about the recent studies on DP learning with large models is that the state-of-the-art (SOTA) results are often achieved with very small clipping threshold $R$. This observation is consistent in both vision and language tasks. In , GPT2 (about 800 million parameters) and RoBERTa models (over 300 millions parameters) achieve the best results under DP on QNLI, MNLI, SST-2, QQP, E2E, and DART datasets, with each per-sample gradient clipped to length $R=0.1$. In , ResNets and Vision Transformers achieve the best DP results on ImageNet with $R=1$; in , the best DP results on CIFAR10 use $R=0.1$ with ResNeXt-29 and SimCLRv2 . The effectiveness of small clipping threshold together with proper learning rate is depicted in Figure 1.

Intuitively, smaller $R$ implies that the Abadi’s clipping (3.1) is effective, which means \min\big{(}R/\|\bm{g}_{i}\|,1\big{)}=R/\|\bm{g}_{i}\|. Given that the clipping threshold $R$ is so small compared to the number of parameters in large models, and that strong DP is guaranteed when the number of training iterations is small (i.e. $\|\bm{g}_{i}\|$ has not converged to small values yet), we expect and empirically observe that the clipping happens on a large proportion of per-sample gradients at all iterations. For instance, we find in the GPT2 generation experiments in that 100% of per-sample gradients are clipped at all iterations; in classification tasks such as QQP, QNLI, and MNLI, the percentage of clipping is about $20\sim 60\%$ on average (more details in Section H.1).

2 Per-sample gradient normalization as new clipping

In the small clipping threshold regime, we can approximately view

and thus derive a novel private gradient $\sum_{i}R\frac{\bm{g}_{i}}{\|\bm{g}_{i}\|}+\sigma R\cdot\mathcal{N}(0,\mathbf{I})$. Here AUTO-V stands for the vanilla automatic clipping, which essentially performs the normalization on each per-sample gradient. As a specific example, we can write the $R$-dependent automatic DP-SGD as

We may view our AUTO-V clipping as to maximize the dot-product similarity (a commonly used similarity measure, e.g. in the attention block in transformers ) between the clipped gradient and the regular gradient. Suppose we want to

Note that the constraint is a sufficient condition for clipping, as discussed in Section 2.2. It is not hard to see that the optimal clipping factor (though violating DP guaranteeIn DP literature, per-sample clipping depend only on individual gradient $\bm{g}_{i}$ separately, hence does not allow the use of $\sum_{j}\bm{g}_{j}$, which changes the sensitivity when adding or removing one data point from the mini-batch.) regarding (3.3) is

If the per-sample gradients are indeed concentrated in the sense $\forall i,\langle\bm{g}_{i},\sum_{j}\bm{g}_{j}\rangle\geq 0$, then AUTO-V is the optimal per-sample gradient clipping. We compare with Abadi’s clipping in Figure 2, where this similarity is significantly magnified by our AUTO-V clipping. In fact, the dot-product similarity in (3.3) closely resembles the convergence of DP optimization for Theorem 4 in (C.2).

3 Stability constant breaks scale-invariance and remains stationary

One potential drawback of AUTO-V clipping is that all gradients lose their magnitudes information completely, since $\|\bm{g}_{i}\cdot\texttt{Clip}_{\text{AUTO-V}}(\bm{g}_{i};R)\|=R,\forall i$. This scale-invariance in AUTO-V and partially in Abadi’s clipping (when $\|\bm{g}_{i}\|>R$) leads to the "lazy region" issue: the parameters will not be updated by DP-GD even if the true gradients are non-zero. In Figure 3, we illustrate such issue in a logistic regressionThe settings are in Appendix F, where the lazy region issues also emerge in the mean estimation problem. We note that the lazy region is also discussed in [14, Example 2]. for AUTO-V and Abadi’s clipping, when the trainable parameter $\theta\in$, as the gradients from two classes cancel each other.

To preserve the magnitude information and thus escape the lazy region, we propose the AUTO-S clipping, with a positive stability constant $\gamma$:

We visualize in Figure 5 that AUTO-S allows larger per-sample gradients to have larger magnitudes after the clipping, while still allowing smaller gradients to vanish after “clipping”. That is, as $\bm{g}_{i}\to 0$, the existence of $\gamma$ allows the clipped gradient $C_{i}\bm{g}_{i}\to\bm{g}_{i}/\gamma$ rather than having a magnitude $R$ as in AUTO-V. We elaborate this point in Section 4.3. This is critical in our convergence analysis and allows DP-SGD${}_{\text{AUTO-S}}$ (but not DP-SGD${}_{\text{AUTO-V}}$) to converge to zero gradient norms in Section 5.

Automatic DP Training

One may wonder why our clipping (3.1)(3.5) is automatic at all, if the hyperparameter $R$ is still present and there is an additional parameter $\gamma$ to choose. It turns out that any constant choice of $R>0$ is equivalent to choosing $R=1$, and common deep learning optimizers are insensitive to the choice of $\gamma$ (e.g. for any $\gamma>0$, we show that the gradient norm converges to zero at the same asymptotic rate in Theorem 4; see also the ablation study in Figure 15). Consequently, we set $\gamma=0.01$ as the default. Specifically, let us redefine the $R$-independent clipping function:

With this clipping, we can design automatic DP optimizers similar to (1.1):

Clearly, the new private gradient $\hat{\bm{g}}_{t}$ from our automatic clipping is $R$-independent, in contrast to the one used in (1.1). A concrete example (in the case of $\gamma=0$) that is comparable to (3.2) will be

Leveraging the private gradient $\hat{\bm{g}}_{t}$ in (4.2), we can train DP neural networks without tuning DP-specific hyperparamters $R$ and $\sigma$, as demonstrated in Algorithm 1.

We will elaborate two distinct reasons in the next sub-sections for the following statement:

which expunges the DP hyperparameters, only leaving us the regular hyperparameters such as learning rate, weight decay, etc. The significant save in the tuning effort is illustrated in Figure 4.

With $R$-dependent automatic clipping, DP-SGD becomes

We can view $\eta_{\text{effective}}\equiv\eta R$ as a whole: increasing $R$ has the same effect as increasing $\eta$, which explains the diagonal pattern in Figure 1(lower plot) where $\text{DP-SGD}_{\text{Abadi}}$ is applied with small clipping threshold. We extend to general non-adaptive optimizers in Theorem 1This coupling of $\eta$ and $R$ is also partially observed in [17, Appendix B.1] through a re-parameterization trick of Abadi’s clipping. Unlike AUTO-S/V, the coupling is not strict (e.g. doubling $R$ is not equivalent to doubling $\eta$, thus still necessitating tuning both $(\eta,R)$), and the relationship to weight decay was not discussed..

Non-adaptive $R$-dependent automatic DP optimizers (including SGD, Heavyball and NAG), with learning rate $\eta$ and weight decay $\lambda$, is equivalent to $R$-independent automatic DP optimizers, with learning rate $\eta R$ and weight decay $\lambda/R$.

2 Adaptive optimizer can be insensitive to clipping threshold

Adaptive automatic DP optimizers are different than the non-adaptive ones, as the clipping threshold cancels out instead of being coupled with learning rate. To see this, we scrutinize $\text{DP-Adam}_{\text{Abadi}}$ (which is similar to $\text{DP-Adam}_{\text{AUTO-V}}$) in Figure 1(upper plot), where columns to the left are almost identical. Further evidence is observed in [50, Table 5] that shrinking $R$ has zero effect on LAMB. We now give a simple explanation using AdaGrad :

where $\bm{g}_{t}=\sum_{i}\bm{g}_{t,i}$ is the gradient sum. In $R$-dependent DP-AdaGrad${}_{\text{AUTO-V}}$, the private gradient is $R\hat{\bm{g}}_{t}$ in place of the standard gradient sum $\bm{g}_{t}$:

We generalize to other adaptive optimizers in Theorem 2 and to the per-layer clipping style in Section B.3.

Adaptive $R$-dependent automatic DP optimizers (e.g. AdaGrad, AdaDelta, AdaMax/Adam, NAdam, RAdam, LARS, LAMB), with learning rate $\eta$ and weight decay $\lambda$ is equivalent to $R$-independent automatic DP optimizers with learning rate $\eta$ and weight decay $\lambda/R$. With decoupled weight decay, $R$-dependent automatic DP-AdamW is equivalent to $R$-independent automatic DP-AdamW with the same $\eta$ and $\lambda$.

3 Automatic clipping is equally private and maximizes utility

In Theorem 3 (proved in Appendix A), we show that the new private gradient $\hat{\bm{g}}_{t}$ in (4.2) has the same level of privacy guarantee as the existing one in (1.1), since the global sensitivity remains the same (see Figure 5). We note that as long as $\gamma>0$, the magnitude information of per-sample gradients is preserved by AUTO-S, in the sense that $\|\bm{g}_{i}\|>\|\bm{g}_{j}\|\Longleftrightarrow\|C_{i}\bm{g}_{i}\|>\|C_{j}\bm{g}_{j}\|$, whereas this can be violated in both the AUTO-V and Abadi’s clipping (as depicted by the flat curve in Figure 5 when $\|\bm{g}_{i}\|>1$). Additionally, note that when $\gamma$ is small, almost all data points “max out” the signal relative to the amount of noise we add. To say it differently, for the same amount of noise, AUTO-S with small $\gamma$ allows more signal to be pushed through a differentially private channel. Towards the end of the training, i.e., at the limit when $\|\bm{g}_{i}\|\rightarrow 0$ for all $i$, then we have $\sum_{i}\frac{\bm{g}_{i}}{\|\bm{g}_{i}\|+\gamma}\rightarrow\frac{1}{\gamma}\sum_{i}\bm{g}_{i}$. In words, the clipped gradients become closer to the standard SGD, thus do not suffer from the instability of AUTO-V.

Under the noise multiplier $\sigma$, number of iterations $T$, subsampling probability $B/n$, DP optimizers using AUTO-V or AUTO-S clipping satisfy $(\epsilon_{\text{Accountant}}(\delta,\sigma,B/n,T),\delta)$-DP, where $\epsilon_{\text{Accountant}}$ is any valid privacy accountant for DP-SGD under Abadi’s clipping.

Convergence analysis of DP-SGD with automatic clipping

We highlight that automatic clipping can be more amenable to analysis than Abadi’s clipping in , since we no longer need to decide whether each per-sample gradient is clipped.

To analyze the convergence of automatic DP-SGD (4.2) in the non-convex setting, we follow the standard assumptions in the SGD literature , including a symmetry assumption on the gradient noise, which is empirically verified in [14, Figure 3] and commonly used in the standard non-DP literature . We refer the curious readers to Section E.5 for details.

For all $\bm{w}$ and some constant $\mathcal{L}_{*}$, we have $\mathcal{L}(\bm{w})\geq\mathcal{L}_{*}$.

Let $\bm{g}(\bm{w})$ denote the gradient of the objective $\mathcal{L}(\bm{w})$. Then $\forall\bm{w},\bm{v}$, there is an non-negative constant $L$ such that

We show in Theorem 4 that DP-SGD with AUTO-S clipping allows the true gradient norm to converge to zero, though the clipped gradient may still be biased, but not so with AUTO-V clipping.

Under 5.1, 5.2, 5.3, running DP-SGD with automatic clipping for $T$ iterations and setting the learning rate $\eta\propto 1/\sqrt{T}$ giveThe upper bound takes an implicit form of $\mathcal{G}(\cdot;\xi,\gamma)$ because it is a lower envelope of functions $\frac{\xi}{r}+\mathcal{F}(\cdot;r,\xi,\gamma)$ over all possible $r>0$, whose forms are detailed in Theorem 6. Notice that $\mathcal{G}$ results only from the clipping operation, not from the noise addition.

We show in Theorem 6 and in Figure 6 that the upper bound (5.2) has $\mathcal{G}\geq\xi$ for AUTO-V ($\gamma=0$), and $\mathcal{G}$ only reduces to zero for AUTO-S ($\gamma>0$). We provide real data evidence in Figure 14 that strictly positive $\gamma$ reduces the gradient norm significantly.

2 Analysis of factors affecting the convergence

We now analyze the many factors that affect the convergence in Theorem 4, from a unified viewpoint of both the convergence and the privacy.

We start with the stability constant $\gamma$ and the learning rate $\eta_{t}$, both only affect the convergence not the privacy. We empirically observe in Figure 8 that small $\gamma$ benefits the convergence at initial iterations (when the privacy guarantee is strong) but larger $\gamma$ converges faster asymptotically. For $\eta_{t}$, the optimal is in fact the miminizer of the hyperbola in (C.5), that is unique and tunable.

Next, we focus on the hyperparameters that affect both convergence and privacy: the batch size $B$, the noise multiplier $\sigma$, and the number of iterations $T$. These hyperparameters have to be considered along the privacy-accuracy tradeoff, not just from a convergence perspective.

Recall that given a fixed privacy budget $(\epsilon,\delta)$, we rely on modern privacy accountant for computing the appropriate combinations of parameter $\sigma,T,B$. The exact expression of the bound as a function of $(\epsilon,\delta)$ is somewhat messy. For this reason, we illustrate our analysis in terms of the surrogate parameter $\mu$ for $\mu$-GDP , which implies $(\epsilon,\delta)$-DP with $\epsilon=\mu^{2}+\mu\sqrt{2\log(1/\delta)})$. showed that DP-SGD’s privacy guarantee asymptotically converges to $\mu$-GDP (as $T\rightarrow\infty$) with $\mu=\frac{B}{n}\sqrt{T(e^{1/\sigma^{2}}-1)}$. We can alternatively leverage $\rho$-tCDP for similar conclusions, using $\rho$ in place of $\mu^{2}$ in (5.3).

Under 5.1, 5.2, 5.3, fixing the asymptotic $\mu(\epsilon,\delta)$-GDP parameter, running DP-SGD with automatic clipping for $T$ iterations and setting the learning rate $\eta\propto 1/\sqrt{T}$ give

To show that our analysis matches the training behaviors observed in SOTA empirical work , we minimize the first argument of $\mathcal{G}$ in (5.3), denoted as $X(B,T,\mu,d,L,\mathcal{L}_{0})$.

[Train longer with larger noise] Fixing the expected batch size $B$, we see that $X$ is decreasing in $T$. Hence larger $T$ and consequently larger $\sigma$ are preferred.

[Larger batch size helps] Fixing number of iterations $T$ or epochs $E=BT/n$, we see that $X$ is decreasing in $B$. Hence larger $B$ and consequently larger $\sigma$ are preferred.

[Pretraining is critical] Pretraining can boost the DP accuracy through a much smaller initial loss $\mathcal{L}_{0}$ and from a smooth (small $L$) and flat (small $\xi$, c.f. Figure 8(left)) initialization.

[Learning rate needs tuning] The optimal learning rate by minimizing (C.5) is $\sqrt{\frac{(\mathcal{L}_{0}-\mathcal{L}_{*})\mu^{2}n^{2}}{L(\mu^{2}n^{2}+dT)}}$. This indicates that one should use larger learning rate for smaller model $d$, weaker privacy (larger $\mu$ or small $\epsilon$), or smaller iteration budget $T$.

Experiments

We evaluate our automatic DP training on image classification, sentence classification, and table-to-text generation tasks. Detailed settings including hyperparameters can be found in Appendix G.

For MNIST/FashionMNIST, we use the same setup as in with a simple CNN. For CIFAR10, we use the same setup as in with pretrained SimCLRv2 . For ImageNette, a 10-class sub-task of ImageNet , we use the same setup as in without the learning rate decay. For CelebA , the real human face dataset, we train ResNet9 with group normalization to replace the batch normalization. Notice that CelebA contains high-resolution (178x218) images, each with 40 labels. We consider CelebA for either multi-class classification on one label, e.g. ‘Smiling’ and ‘Male’, or for multi-label/multi-task problem to learn all labels simultaneously.

In Table 1, we observe that AUTO-S clipping outperforms existing clipping in all datasets with statistical significance. Interestingly, the standard deviation from different runs is smaller for automatic DP optimizers, indicating better reproducibility and stability. We additionally experiment 40 binary classification problems on CelebA with respect to each label, and observe that the mean accuracy further improves to 91.63% at $\epsilon=8$ for AUTO-S (see Appendix J).

2 Sentence classification

On five benchmark language datasets (MNLI(m/mm), QQP, QNLI, SST2), we compare our automatic DP training with re-parameterized gradient perturbation (RGP, ) and full-parameter finetuning (full, ) using RoBERTa models . These methods use the same experimental setup. For language models, our automatic training is based on the codebase of .

In Table 3 and Table 3, we note that full parameter finetuning with AUTO-S outperforms or at least matches SOTA on all tasks. We use exactly the same hyperparameters as in .

3 Table-to-text generation

We compare our automatic DP training with a variety of fine-tuning methods, for table-to-text generation task on E2E dataset , where the goal is to generate texts about different aspects of a restaurant’s data. We measure the success on this task by BLEU, ROUGE-L (in Table 4), METEOR, NIST, CIDEr (extended in Table 8), with higher value meaning better model quality.

Competitive methods include low-rank adaption (LoRA), prefix-tuning (prefix), RGP, only fine-tuning the top 2 Transformer blocks (top2), and training from scratch (retrain), as were recorded in . Again, we use the exactly the same hyperparameters as in . For GPT2 (124 million parameters), GPT2 medium (355 million), and GPT2 large (774 million), Table 4 shows that AUTO-S is scalable with stronger performance on larger models. Our automatic full-parameter finetuning has the best overall performance. Additionally, we highlight that AUTO-S and methods like LoRA are not mutually exclusive and can be combined to yield strong performance, since AUTO-S modifies the optimizers and LoRA modifies the architecture.

Related works

While other DP works also normalize the per-sample gradients (instead of clipping them) or use small clipping threshold (making the clipping similar to normalization), our work is very different in terms of theoretical analysis, algorithm design and experiments. In fact, the concurrent work gives the same algorithm as AUTO-S, although its theoretical analysis and experiment design is fundamentally different from ours. proposes to normalize the per-user (not per-sample) gradient in the federated learning setting, and analyzes the convergence in a convex, non-deep-learning setting.

On the other hand, many works apply the per-sample gradient clipping with small $R$ for good utility . These works have led to valuable insights, but also some false or incomplete conclusions, due to the lack of rigorous theoretical analysis. For instance, since $R$ is present in the (re-parameterized) per-sample clipping, it cannot avoid the hyperparameter tuning as the choice of $R$ is not robust; even if a sufficiently small $R$ is used, the clipping does not reveal the stability constant in AUTO-S, which enjoys theoretical and empirical advantages in Remark 5.4 and Section 6. We devote Appendix L to more instances (e.g. Footnote 5) and a thorough comparison.

Discussion

In this work, we propose the automatic clipping as a drop-in replacement to the standard per-example clipping for differentially private training. This is the first technique that eliminates the need to tune the clipping threshold $R$, thus making DP deep learning as easy as regular learning. Our AUTO-S method enjoys both theoretical guarantee of convergence in non-convex problems (under various conditions), and strong empirical performance that advances DP learning on computer vision and language tasks.

We are excited about the future of automatic DP training, especially along with other working techniques, such as general optimizers (e.g. ), clipping styles (all-layer or per-layer or adaptive clipping), architecture modifications (e.g. LoRA, RGP, prefix), and data augmentation (e.g. adversarial training and multiple augmentation ). Thus, we expect to achieve comparable results to all SOTA in a lightweight fashion.

Acknowledgement

We would like to thank Xuechen Li for updating his codebase and for his quick response in technical details to reproduce the results, which was crucial for benchmarking our experiments.

References

Appendix A Proof of differential privacy

$\sigma$ denotes the “Noise multiplier”, which corresponds to the noise-level when a Gaussian mechanism is applied to a query with sensitivity $1$.

Observe that automatic clipping (AUTO-V and AUTO-S (4.1)) ensures the bounded global-sensitivity of the stochastic gradient as in Abadi’s clipping. Aligning the noise-multiplier (rather than the noise-level itself) ensures that the the noise-to-sensitivity ratio $\frac{\sigma\Delta g}{\Delta g}=\sigma$ is fixed regardless of $\Delta g$. The Gaussian mechanism’s privacy guarantees are equivalent. Thus from the privacy accountant perspective, DP-SGD with both Abadi’s clipping and our autoclipping method can be equivalently represented as the adaptive composition of $T$ Poisson sampled Gaussian Mechanism with sampling probability $B/n$ and noise multiplier $\sigma$. ∎

Appendix B Proof of automaticity

We prove Theorem 1 by showing that, DP-SGD using $R$-dependent AUTO-S with learning rate $\eta$ and weight decay $\lambda$ is equivalent to $R$-independent AUTO-S with learning rate $\eta R$ and weight decay $\lambda/R$. We claim other non-adaptive optimizers such as HeavyBall and NAG can be easily shown in a similar manner.

Recall the standard SGD with weight decay is

Replacing the standard gradient $\sum_{i}\frac{\partial l_{i}}{\partial\bm{w}_{t}}$ with the private gradient, we write the $R$-dependent case as

which is clearly equivalent to the $R$-independent case:

if we use $\eta^{\prime}=\eta R$ and $\lambda^{\prime}=\lambda/R$. ∎

B.2 Adaptive DP optimizers

We prove Theorem 2 by showing that, DP-AdamW using $R$-dependent AUTO-S with learning rate $\eta$ and weight decay $\lambda$ is equivalent to $R$-independent AUTO-S with the same learning rate $\eta$ and weight decay $\lambda/R$. This is the most complicated case. We claim other adaptive optimizers such as AdaDelta, Adam with weight decay (not AdamW), and NAdam can be easily shown in a similar manner.

where $\beta_{1},\beta_{2}$ are constants, $\bm{g}_{t}:=\sum_{i}\frac{\partial l_{i}}{\partial\bm{w}_{t}}$ is the standard gradient,

B.3 Automatic per-layer clipping

In some cases, the per-layer clipping is desired, where we use a clipping threshold vector $\bm{R}=[R_{1},\cdots,R_{L}]$ and each layer uses a different clipping threshold. We claim that DP optimizers under automatic clipping works with the per-layer clipping when $\bm{R}$ is tuned proportionally, e.g. $\bm{R}=R\cdot[a_{1},\cdots,a_{L}]$, but not entry-wise (see counter-example in B.1). One special case is the uniform per-layer clipping when $R_{1}=\cdots=R_{L}=R/\sqrt{L}$. This is widely applied as only one norm $R$ requires tuning, instead of $L$ norms in $\bm{R}$, particularly in the case of deep models with hundreds of layers. The corresponding DP-SGD with AUTO-S in (3.5) gives

Changing one clipping threshold in the clipping threshold vector $\bm{R}$ (i.e. not proportionally) can break the coupling with learning rate.

Increasing $R_{1}$ from 9 to 16 changes the update for the first layer

The noise-to-signal ratio decreases from 5/3 to 5/4 for this layer, and increases from 5/4 to 5/3 for the second layer. This breaks the coupling with learning rate, since the coupling does not change the noise-to-signal ratio. ∎

Appendix C Main results of convergence for DP-SGD with automatic clipping

In this section, we prove two parts of Theorem 4.

Under 5.1, 5.2, 5.3, running DP-SGD with automatic clipping for $T$ iterations gives

for $r<1,\gamma=0$ and $\eta\propto 1/\sqrt{T}$, $\mathcal{F}(x)=\frac{x}{\min_{0<c<1}f(c,r)}$ and $f(c,r):=\frac{(1+rc)}{\sqrt{r^{2}+2rc+1}}+\frac{(1-rc)}{\sqrt{r^{2}-2rc+1}}$; for $r\geq 1,\gamma=0$ and $\eta\propto 1/\sqrt{T}$, $\mathcal{F}(x)=\infty$;

for $r\geq 1,\gamma>0$ and $\eta\propto 1/\sqrt{T}$, $\mathcal{F}$ is the convex envelope of (C.9), and is strictly increasing.

Notice that, (C.1) holds for any $r>0$. However, we have to consider an envelope curve over $r$ in (C.1) to reduce the upper bound: with AUTO-V clipping ($\gamma=0$), the upper bound in (C.1) is always larger than $\xi$ as $r<1$; we must use AUTO-S clipping ($\gamma>0$) to reduce the upper bound to zero, as can be seen from Figure 7. In fact, larger $T$ needs larger $r$ to reduce the upper bound.

All in all, we specifically focus on $r\geq 1$ and $\gamma>0$, which is the only scenario that (C.1) can converge to zero. This scenario is also where we prove the second part of Theorem 4.

The second part of Theorem 4 is the asymptotic convergence rate $O(T^{-1/4})$ of DP-SGD, only possible under $r\geq 1$ and $\gamma>0$.

By (C.1) in Theorem 6, our upper bound $\mathcal{G}$ from Theorem 4 can be simplified to

Starting from (C.9), we denote $x=\frac{4}{\sqrt{T}}\sqrt{(\mathcal{L}_{0}-\mathcal{L}_{*})L\left(1+\frac{\sigma^{2}d}{B^{2}}\right)}$ and write

Since $\mathcal{M}^{-1}$ is asymptotically linear as $x\to 0$, we instead study

That is, ignoring the higher order term for the asymptotic analysis, the $\mathcal{M}^{-1}$ part converges as $O(x)=O(1/\sqrt{T})$, and we visualize this in Figure 9.

Although DP-SGD converges faster than SGD, the former converges to $\xi/r$ and the latter converges to 0. Thus, taking $\xi/r$ into consideration, the objective reduces to a hyperbola

whose minimum over $r$ is obviously $2\sqrt{\xi(1-\frac{x}{2\gamma})\frac{x(\xi+\gamma)^{2}}{2\gamma\xi}}=O(\sqrt{x})=O(T^{-1/4})$. ∎

To give more details about the upper bound in (5.2), we demonstrate its dependence on $\xi$ and $\gamma$ in Figure 8.

C.2 Main proof of convergence for DP-SGD (the non-envelope version)

By Lipschitz smoothness in 5.2, and denoting $Z=\mathcal{N}(0,\mathbf{I})$, we have

Notice that in the last equality, the first term (ignoring $\bm{g}_{t}^{\top}Z$ for its zero expectation) can be written in the same form as (3.3), which supports our motivation in Section 3.2; the second term is independent of clipping functions. Note that the last inequality is tight if and only if $C_{i}=1$. This empirically holds in Section H.1, especially for GPT2.

where we use the hyperplane perpendicular to $\bm{g}_{t}$ to divide the support of $\Delta_{t}$ into two half-spaces:

We use the symmetry assumption in 5.3 to get

and notice that $\Delta_{t}\overset{D}{=}-\Delta_{t},$ i.e., if $\Delta_{t}\in H_{+}$, then $-\Delta_{t}\in H_{-}$ with the same distribution.

for any $r>0$ and $f(c,r;\Gamma)=\frac{(1+rc)}{\sqrt{r^{2}+2rc+1}+\Gamma}+\frac{(1-rc)}{\sqrt{r^{2}-2rc+1}+\Gamma}$.

For the simplicity of notation, we denote the distance measure

and leave the fine-grained analysis (e.g. its explicit form in some scenarios) at the end of this section.

Using the lower bound from Lemma C.1, the expected improvement (C.3) becomes

Now extend the expectation over randomness in the trajectory, and perform a telescoping sum over the iterations

Substituting $\eta B=\eta_{\text{0}}/\sqrt{T}$ where $\eta_{\text{0}}$ is a base learning rate, we have

With $\eta_{\text{0}}$ chosen properly at $\eta_{0}=\sqrt{\frac{\mathcal{L}_{0}-\mathcal{L}_{*}}{L\left(1+\frac{\sigma^{2}d}{B^{2}}\right)}}$, the hyperbola on the right hand side in (C.5) is minimized to $4\sqrt{(\mathcal{L}_{0}-\mathcal{L}_{*})L\left(1+\frac{\sigma^{2}d}{B^{2}}\right)}$, and we obtain

Since the minimum of a sequence is smaller than the average, we have

We claim that $\mathcal{M}$ may not be concave or convex. Therefore we use $\mathcal{M}_{cvx}$ to denote its lower convex envelope, i.e. the largest convex function that is smaller than $\mathcal{M}$. Then by Jensen’s inequality (C.6) becomes

It is obvious that $\mathcal{M}_{cvx}$ is increasing as $\mathcal{M}$ is increasing by Theorem 8. Hence, $(\mathcal{M}_{cvx})^{-1}$ is also increasing, as the inverse of $\mathcal{M}_{cvx}$. We write (C.7) as

Finally, we derive the explicit properties of $\mathcal{M}(\|\bm{g}_{t}\|-\xi/r)$ in Theorem 8. These properties allow us to further analyze on the convergence of $\mathcal{M}(\|\bm{g}_{t}\|-\xi/r)$, based on AUTO-V and AUTO-S, respectively.

This is a linear function and thus $\mathcal{M}_{cvx}=\mathcal{M}=1/\mathcal{M}_{cvx}^{-1}$. As a result, we have

We note here $r$ plays an important role under AUTO-V clipping: when $r<1$, we spend more iterations to converge to better and smaller gradient norm $\xi/r$; when $r\geq 1$, $\min_{c}f(c,r;0)=f(1,r;0)=0$ and it takes forever to converge. This is demonstrated in the left plot of Figure 6.

DP-SGD with AUTO-S clipping.

we can derive it based on $r,\xi,\gamma$ and substitute back to (C.8).

Note that the domain of $\mathcal{M}^{-1}$ (or the image of $\mathcal{M}$) is $[0,\frac{\gamma}{r-1}-\frac{\gamma}{r+1})$.

In comparison to the AUTO-V clipping, $\mathcal{M}^{-1}$ takes a much more complicated form, as depicted in the middle plot of Figure 6, where $r>1$ plays an important role for the gradient norm to converge to zero. ∎

C.3 Proof of Lemma C.1

To simplify the notation, we denote noise-to-signal ratio $S:=\frac{\|\Delta_{t}\|}{\|\bm{g}_{t}\|}$ and $c:=\cos\theta=\frac{\bm{g}_{t}^{\top}\Delta_{t}}{\|\bm{g}_{t}\|\|\Delta_{t}\|}$, with $\theta$ be the random angle between $\bm{g}_{t}$ and $\Delta_{t}$. Note that $0<c\leq 1$ when $\Delta_{t}\in H_{+}$.

The term inside the conditional expectation in (C.10) can be written as

Defining $\Gamma=\gamma/\|\bm{g}_{t}\|$ and

we turn the conditional expectation in (C.10) into

for which we want to lower bound $f(c,S;\Gamma)$ over $0<c\leq 1,S>0,\Gamma>0$. We use the next theorem to prepare some helpful properties. The proof can be found in Section E.1.

$f(c,S;\Gamma)$ is strictly decreasing in $S$ for all $0<c<1$ and $\Gamma>0$.

Consequently, $\min_{c\in(0,1)}f(c,S;\Gamma)$ is strictly decreasing in $S$.

$f(c,S;\Gamma)$ is strictly decreasing in $c$ for all $S>1$ and $\Gamma>0$.

We consider a thresholding ratio $r>0$ and we will focus on the regime that $S<r$. This $r$ will turn out to measure the minimum gradient norm at convergence: informally speaking, $\|\bm{g}_{t}\|$ converges to $\xi/r$.

By the law of total expectation, (C.12) can be relaxed as follows.

where in the first inequality, the ignoring of last term is justified by $f(c,S;\Gamma)\geq\min_{c\in(0,1]}f(c,S;\Gamma)\geq\min_{c\in(0,1]}f(c,\infty;\Gamma)=0$, from the monotonicity (second statement) in Theorem 7.

We first lower bound $\star$⃝ by applying the Markov’s inequality:

Finally, the conditional expectation of interest in (C.10) gives

C.4 Proof of Theorem 8

To derive some properties of $\min_{c}f(c,r;\Gamma)$, we need to compute separately for AUTO-V (without the stability constant, $\Gamma=0$) and for AUTO-S (with the stability constant, $\Gamma>0$), as shown in Theorem 8. As we will show, as the number of training iterations $T\to\infty$, DP-SGD with AUTO-V clipping can only compress $\|\bm{g}_{t}\|$ to $\xi/r$ for $r<1$. However, DP-SGD with AUTO-S clipping can compress $\|\bm{g}_{t}\|$ to $\xi/r$ to any $r>1$.

For $0<r<1$ and $\Gamma=0$, we have $\min_{c\in(0,1]}f(c,r;0)>0$. Then Equation C.12 is lower bounded by

For $r\geq 1$ and $\Gamma=0$, we have $\min_{c\in(0,1]}f(c,r;\Gamma)=f(1,r;0)=0$. In words, (C.10) has a trivial lower bound and Theorem 6 cannot compress $\|\bm{g}_{t}\|$ to $\xi/r$.

For $r\geq 1$ and $\Gamma>0$, we have $\min_{c\in(0,1]}f(c,r;\Gamma)=f(1,r;\Gamma)=\left(\frac{\Gamma}{r+\Gamma-1}-\frac{\Gamma}{r+\Gamma+1}\right)$. Then Equation C.12 is lower bounded by

which is increasing in $\|\bm{g}_{t}\|-\xi/r$.

To prove statement 1, we use the second statement from Theorem 7 and show that $\min_{c}f(c,r;0)>\min_{c}f(c,\infty;0)=0$. To prove statement 2 and 3, we use the third statement from Theorem 7 and see that $\min_{c}f(c,r;\Gamma)=f(1,r;\Gamma)$ with an explicit formula. ∎

Appendix D Convergence rate of standard SGD

Under 5.1, 5.2, 5.3 (without the symmetry assumption), running the standard non-DP SGD for $T$ iterations gives, for $\eta\propto 1/\sqrt{T}$,

By Lipschitz smoothness assumption in 5.2,

The expected improvement at one iteration is

Now we extend the expectation over randomness in the trajectory, and perform a telescoping sum over the iterations

Notice that we do not need the symmetry assumption in 5.3 in the non-DP SGD analysis.

We apply the same learning rate as in , $\eta=\frac{1}{L\sqrt{T}}$,

Using the Jensen’s inequality, we can have

Appendix E Auxiliary proofs

We first show $\frac{df(c,S;\Gamma)}{dS}<0$ for all $0<c<1,\Gamma>0$ and $S>0$, as visualized in the left plot of Figure 10. We can explicitly write down the derivative, by WolframAlpha

From (E.2), the denominator in (E.1) is positive and it suffices to show $A\Gamma^{2}+B\Gamma+C>0$ for all $0<c<1$ and $S>0$, in order to show $\frac{df}{dS}<0$.

Also from (E.2), we can easily see $B(c,S)>0$ and $C(c,S)>0$. We will show that $A(c,S)>0$ in Lemma E.1, after very heavy algebraic computation.

Now we can claim that $A\Gamma^{2}+B\Gamma+C>0$ by E.3, and complete the proof of the first statement.

To further see that $\min_{c}f(c,S;\Gamma)$ is decreasing in $S$, let us denote $c^{*}(x;\Gamma):=\text{arg min}_{c\in}f(c,x;\Gamma)$. Then considering $S<S^{\prime}$, we prove the second statement by observing

This statement is also visualized in the right plot of Figure 10.

We next show $\frac{df(c,S;\Gamma)}{dc}<0$ for all $0<c<1,\Gamma>0$ and $S>1$. We can explicitly write down the derivative, by WolframAlpha

Clearly $B^{\prime}(c,S)>0$ and $C^{\prime}(c,S)>0$, since $S^{2}+2cS+1>S^{2}-2cS+c^{2}=(S-c)^{2}\geq 0$. And we will show $A^{\prime}(c,S)>0$ in Lemma E.2, after some algebra.

We again claim that $A^{\prime}\Gamma^{2}+B^{\prime}\Gamma+C^{\prime}>0$ by E.3, which guarantees that the numerator in (E.3) is negative and that $\frac{df}{dc}<0$. This is visualized in Figure 11. ∎

E.2 Proof of Lemma E.1

where the first inequality comes from $S^{2}-2cS+1>S^{2}-2cS+c^{2}=(S-c)^{2}\geq 0$.

Denoting $X:=S^{2}$ and viewing the above as a quadratic polynomial of $X$, we have

Using the closed-form minimizer of quadratic polynomial $①$, after some heavy algebra, one can check the minimum of $①$ is

which is clearly positive. Contradiction! ∎

E.3 Proof of Lemma E.2

Notice that $(S^{2}+3cS+2)>S^{2}+2>0$ and $\sqrt{S^{2}\pm 2cS+1}>0$. Therefore if $S^{2}-3cS+2\leq 0$, we are done.

Otherwise, we prove by contradiction and suppose

under the condition that $S^{2}-3cS+2>0$.

Denoting $X:=S^{2}$ and viewing the above as a quadratic polynomial of $X$, we have, for $X>1$,

The closed-form minimizer of quadratic polynomial $②$ is $\frac{(9c^{2}-5)}{4}$. Given that $0<c<1$, we must have $-\frac{5}{4}<\frac{9c^{2}-5}{4}<1$. Hence the minimizer is not within the feasible domain $(1,\infty)$ of $X$. Thus the minimum of ② is achieved with $X=1$ at $9(1-c^{2})$. This is positive. Contradiction! ∎

E.4 Proof of E.3

For a quadratic polynomial $Ax^{2}+Bx+C$ with $A,B,C>0$, the minimum value on the domain $x\geq 0$ is $C$, at $x=0$. Therefore $Ax^{2}+Bx+C>0$.

Since $A>0$, the quadratic polynomial is convex and increasing on the domain $x>-\frac{B}{2A}$. Since $B>0$ as well, we know $-\frac{B}{2A}<0$ and hence the quadratic polynomial is strictly increasing on $x>0$. Therefore the minimum value is achieved when $x=0$, and we obtain $Ax^{2}+Bx+C\geq C>0$ for all $x\geq 0$. ∎

E.5 Assumption of symmetric gradient noise

We show that 5.3 is actually relaxed from and less strict than the assumptions used in the non-DP literature. In words, 5.3 allows our DP convergence to be comparable to the standard convergence (as in Theorem 9), because our assumption does not enforce extra constraint.

In standard non-DP analysis , the mini-batch gradient is assumed to be an unbiased estimate of the oracle gradient $\bm{g}_{t}=\frac{\partial\mathcal{L}}{\partial\bm{w}}$:

In fact, we can further relax our 5.3: besides assuming the central symmetry, the same proof of convergence will follow if we instead assume the mirror symmetry about the hyperplane normal to $\bm{g}_{t}$, that is $\{\bm{v}:\bm{g}_{t}^{\top}\bm{v}=0\}$.

Appendix F Examples of lazy regions

F.2 Mean estimation on Gaussian mixture data

Appendix G Experiments settings

We give the experiments settings for computer vision tasks in Table 1.

MNIST: We use the network architecture from , with 40 epochs, 512 batch size, 0.5 learning rate (or 0.005 non-DP learning rate), 0.1 clipping threshold, DP-SGD with 0.9 momentum, and without pretraining. This setting is the same as .

FashionMNIST: We use the same network architecture as MNIST, with 40 epochs, 2048 batch size, 4 learning rate (or 0.04 non-DP learning rate), DP-SGD with 0.9 momentum, and without pretraining. This setting is the same as .

CIFAR10 pretrained: We use the SimCLR model from See implementation in https://github.com/google-research/simclr., with 50 epochs, 1024 batch size, 4 learning rate (or 0.04 non-DP learning rate), 0.1 clipping threshold, and DP-SGD with 0.9 momentum. The SimCLR model is pretrained on unlabelled ImageNet dataset. After pretraining, we obtain a feature of dimension 4096 on which a linear classifier is trained privately. This setting is the same as .

ImageNette: We use the ResNet9 (2.5 million parameters) with Mish activation function . We set 50 epochs, 1000 batch size, 0.0005 learning rate (or 0.000005 non-DP learning rate), 1.5 clipping threshold, and use DP-NAdam, without pretraining. This setting is the same as except we did not apply the learning rate decaying scheduler.

CelebA (Smiling and Male and Multi-label) We use the same ResNet9 as above, with 10 epochs, 500 batch size, 0.001 DP learning rate (or 0.00001 non-DP learning rate), 0.1 clipping threshold, and use DP-Adam, without pretraining. We use the labels ‘Smiling’ and ‘Male’ for two binary classification tasks, with cross-entropy loss. For the multi-label task uses a scalar loss by summing up the 40 binary cross-entropy losses from each label.

We refer the code for MNIST, FashionMNIST, CIFAR10, CIFAR10 pretrained to https://github.com/ftramer/Handcrafted-DP by . ResNet9 can be found in https://github.com/cbenitez81/Resnet9.

Throughout all experiments, we do not apply tricks such as random data augmentation (single or multiple times ), weight standardization , or parameter averaging .

G.2 Sentence classification settings

We experiment on five datasets in Table 3 and Table 3.

MNLI(m) MNLI-matched, the matched validation and test splits from Multi-Genre Natural Language Inference Corpus.

MNLI(mm) MNLI-mismatched, the matched validation and test splits from Multi-Genre Natural Language Inference Corpus.

QNLI The Stanford Question Answering dataset.

SST2 The Stanford Sentiment Treebank dataset.

The datasets are processed and loaded from Huggingface , as described in https://huggingface.co/datasets/glue. We follow the same setup as and . We refer the interested readers to Appendix G,H,I,K,N of for more details.

We emphasize that our automatic clipping uses exactly the same hyperparameters as the Abadi’s clipping in , which is released in their Private-Transformers library See https://github.com/lxuechen/private-transformers/blob/main/examples/classification/run_wrapper.py.

Notice that we use DP learning rate 5e-4 across tasks for the $R$-dependent automatic DP-Adam, which is equivalent to $R$-independent automatic DP-Adam with the same learning rate. We demonstrate that the results are not sensitive to learning rates around the optimal choice. That is, the automatic clipping does not eliminate $R$ at the cost of more difficult tuning of learning rate.

G.3 Table-to-text generation settings

We experiment multiple GPT2 models on E2E dataset from Huggingface in Table 4. We follow the same setup as , and our automatic clipping uses exactly the same hyperparameters as the Abadi’s clipping in , which is released in their Private-Transformer library See https://github.com/lxuechen/private-transformers/blob/main/examples/table2text/run.sh.

Appendix H Figure zoo

We show that in all sentence classification tasks, Abadi’s clipping happens on a large proportion of per-sample gradients. This supports the similarity between Abadi’s clipping and AUTO-V in (3.1).

We note that for GPT2, GPT2 medium and GPT2 large, empirically in all iterations 100% of the per-sample gradients are clipped by the Abadi’s clipping, making the performance of Abadi’s clipping equivalent to AUTO-V clipping, as shown in Table 4.

H.2 Stability constant helps AUTO clipping reduce gradient norm

To corroborate our claim in Theorem 6, that the stability $\gamma$ reduces the gradient norm, we plot the actual gradient norm by iteration.

H.3 Choice of stability constant is robust

We claim in Theorem 6 that, as long as $\gamma>0$ in our automatic clipping, the asymptotic convergence rate of gradient norm is the same as that by standard non-private SGD. We plot the ablation study of learning rate and the stability constant $\gamma$ to show that it is easy to set $\gamma$: in Table 3 and Table 3, we adopt learning rate 0.0005, under which a wide range of $0.0001<\gamma<1$ gives similar accuracy. Note that the largest good $\gamma$ is 1000 times bigger than the smallest good $\gamma$.

Appendix I Full table of GPT2 generation task on E2E dataset

This is the extended version of Table 4 on E2E dataset. The performance measures are BLEU , ROGUE-L , NIST , METEOR , and CIDEr scores. Here $\epsilon$ is accounted by RDP , where $\epsilon=3$ corresponds to 2.68 if accounted by Gaussian DP or to 2.75 if accounted by numerical composition , and $\epsilon=8$ corresponds to 6.77 if accounted by Gaussian DP or to 7.27 if accounted by numerical composition.

We observe that GPT2 (163 million parameters), GPT2-medium (406 million), and GPT2-large (838 million), Table 4 trained with our automatic clipping consistently perform better in comparison to other methods. In some cases, LoRA trained with Abadi’s clipping also demonstrates strong performance and it would be interesting to see how LoRA trained with the automatic clipping will behave.

Appendix J Further experiments on CelebA dataset

In this section, we present a complete summary of accuracy results, with DP constraint or not, for the CelebA dataset. We do not apply any data-preprocessing. In the first experiment, we apply a single ResNet on the 40 labels as the multi-task/multi-label learning. In the second experiment, we apply one ResNet on one label. As expected, our automatic DP optimizers have comparable test accuracy to the Abadi’s DP optimizers, but we do not need to tune the clipping threshold for each individual task/label. We also notice that, learning different labels separately gives better accuracy than learning all labels together, though at the cost of heavier computational burden.

We apply ResNet9 as in Section G.1 on the multi-label classification task. I.e. the output layer has 40 neurons, each corresponding to one sigmoid cross-entropy loss, that are summed to a single loss and all labels are learnt jointly.

J.2 Multiple binary classification

For the second experiment, we apply ResNet9 on each label as a binary classification task. I.e. the output layer has 1 neuron and we run 40 different models for all labels separately.

Appendix K Code implementation of automatic clipping

Changing Abadi’s clipping to automatic clipping is easy in available codebases. One can set the clipping $R=1$ or any other constant, as explained in Theorem 1 and Theorem 2.

For Opacus version 1.1.2 (latest), we can implement the all-layer automatic clipping by changing Line 399-401 in https://github.com/pytorch/opacus/blob/main/opacus/optimizers/optimizer.py to

The per-layer automatic clipping requires changing Line 61-63 in https://github.com/pytorch/opacus/blob/main/opacus/optimizers/perlayeroptimizer.py to

For older version ($<1.0$, e.g. 0.15) of Opacus, we can implement the all-layer automatic clipping by changing Line 223-225 in https://github.com/pytorch/opacus/blob/v0.15.0/opacus/utils/clipping.py to

or implement the per-layer automatic clipping by changing Line 301-302 in https://github.com/pytorch/opacus/blob/main/opacus/optimizers/perlayeroptimizer.py to

K.2 ObJAX

For ObJAX version 1.6.0 (latest), we can implement the automatic clipping in https://github.com/google/objax/blob/master/objax/privacy/dpsgd/gradient.py by changing Line 92 to

K.3 Private-transformers

To reproduce our experiments for sentence classification and table-to-text generation, we modify the ‘private-transformers’ (version 0.1.0) codebase of . The modification is in https://github.com/lxuechen/private-transformers/blob/main/private_transformers/privacy_utils/privacy_engine.py, by changing Line 349 to

Appendix L More on related works of per-sample clipping

We discuss the difference between our work and the related (see the table below).

Our work is very different to most works which do not analyze the convergence of DP deep learning in a non-convex setting, but it is very similar to We emphasize that is a concurrent work with no known dependency either way, which goes public (to arXiv, on 27 Jun 2022) after ours (on 14 Jun 2022).. However, assumes a relaxed Lipschitz smootheness in place of our 5.3, where we instead assume the symmetric gradient noise. In addition, our experiments are more comprehensive, covering over 10 tasks including DP-GPT2, while only experimented with 2 smaller models — ResNet20 and Roberta-base.

We now clarify some false or incomplete conclusion in previous literatures that apply the per-sample gradient clipping (re-parameterized or not).

1. Per-sample clipping is not robust to $R$, even with re-parameterization.

In [17, Figure 8] and our Figure 4, the accuracy of DP optimizer with Abadi’s clipping is insensitive to $R$ only if one has found a small enough region (e.g. $R\leq 1$), which takes effort to find or the accuracy will be unacceptably low out of the region. In particular, choosing $R=1$ as in is not universally proper, e.g. uses $R=0.1$ for language models. This dependence on tasks, datasets and optimizers means per-sample clipping still requires the expensive hyperparameter tuning.

In other words, per-sample gradient clipping is at best an approximation of per-sample gradient normalization (i.e. our AUTO-V) and should be considered as semi-automatic, whereas AUTO-V/S is fully automatic in terms of tuning $R$. Although technically we introduce a new hyperparameter $\gamma$ in the place of $R$, we claim that automatic clipping is not sensitive to $\gamma$ (our only hyperparameter) for a large range, e.g. one can multiply $\gamma$ by 10000 times, going from $\gamma=$0.001 to 10 with learning rate 0.0005 in Figure 15, and the accuracy is similar.

2. Per-sample clipping does not decouple $R$, especially for DP-Adam.

In general, $R$ is not completely decoupled from the re-parameterized per-sample clipping in :

Given that $R$ appears in both terms on the right hand side, one can at most say "… when the clipping norm is decreased k times, the learning rate should be increased k times to maintain similar accuracy." by and "… Using this update, performance becomes less sensitive to the choice of clipping norm." by . In contrast, we can state that adjusting the learning rate proportionally, our AUTO-V/S maintains exactly the same accuracy and is completely insensitive to the choice of $R$.

Additionally and importantly, the understanding in is limited to DP-SGD (as they only experiment with the computer vision tasks), where "… the learning rate $\eta$ absorbs a factor of $R$." by . As rigorously proved in Theorem 1 and Theorem 2, adaptive optimizers like Adam and AdaGrad do not absorb $R$ but rather cancel it. This is visualized in Figure 1, where the performance landscape is row-wise for DP-Adam and diagonal for DP-SGD.

3. Re-parameterized per-sample clipping unintentionally changes the weight decay.

Weight decay is a common technique used in any work that uses AdamW and in the re-parameterized trick by . We can see that

Therefore, when we move along $R$ like in [17, Figure 8], from $R=1$ to $2^{-6}$, the weight decay increases from $\lambda$ to $2^{6}\cdot\lambda$ by 64 times, which may worsen the accuracy as seen in the blue curve of [17, Figure 8]! Again, this is due to the incomplete decoupling by per-sample clipping, which is only avoided in AUTO-V/S thanks to theoretical analysis in Theorem 1 and Theorem 2.

L.2 Connections to normalized optimisation

Variants of normalized gradient have been used in optimization . These normalized optimizers are fundamentally different to our automatic optimizers, because the normalization is on mini-batch not on each sample and noise is not involved:

The main difference lies in the challenge of analyzing per-sample normalization (which is biased) and the batch-gradient normalization (which is unbiased in the direction). That is, $\frac{\frac{1}{B}\sum_{i}g_{i}}{\|\frac{1}{B}\sum_{i}g_{i}\|}$ is parallel to the mini-batch gradient $\frac{1}{B}\sum_{i}g_{i}$ but $\frac{1}{B}\sum_{i}\frac{g_{i}}{\|g_{i}\|}$ is generally not parallel to it (this conclusion also holds if the normalizaiton is replaced by the clipping). On a side note, it is interesting that Theorem 4 indeed shows although a bias is introduced by the per-sample clipping, it is not fatal to the asymptotic convergence and hence may not be a concerning matter.