# Augment then Smooth: Reconciling
Differential Privacy with Certified Robustness

Jiapeng Wu
Layer 6 AI
<EMAIL_ADDRESS>
&Atiyeh Ashari Ghomi
Layer 6 AI
<EMAIL_ADDRESS>
&David Glukhov
University of Toronto &
Vector Institute
<EMAIL_ADDRESS>
Jesse C. Cresswell
Layer 6 AI
<EMAIL_ADDRESS>
&Franziska Boenisch
University of Toronto &
Vector Institute
<EMAIL_ADDRESS>&Nicolas Papernot
University of Toronto &
Vector Institute
<EMAIL_ADDRESS>
###### Abstract

Machine learning models are susceptible to a variety of attacks that can erode
trust in their deployment. These threats include attacks against the privacy
of training data and adversarial examples that jeopardize model accuracy.
_Differential privacy_ and _randomized smoothing_ are effective defenses that
provide certifiable guarantees for each of these threats, however, it is not
well understood how implementing either defense impacts the other. In this
work, we argue that it is possible to achieve both privacy guarantees and
certified robustness simultaneously. We provide a framework called DP-CERT for
integrating certified robustness through randomized smoothing into
differentially private model training. For instance, compared to
differentially private stochastic gradient descent on CIFAR10, DP-CERT leads
to a 12-fold increase in certified accuracy and a 10-fold increase in the
average certified radius at the expense of a drop in accuracy of 1.2%. Through
in-depth per-sample metric analysis, we show that the certified radius
correlates with the local Lipschitz constant and smoothness of the loss
surface. This provides a new way to diagnose when private models will fail to
be robust.

##  1 Introduction

Machine learning (ML) models are becoming increasingly trusted in critical
settings despite an incomplete understanding of their properties. This raises
questions about the _trustworthiness_ of those models, encompassing aspects
such as privacy, robustness, and more. Society at large might expect _all_ of
these properties to hold simultaneously as ML’s influence on everyday life
expands, but each aspect is challenging enough that scientists and
practitioners still mostly grapple with them individually. Relatively little
research has been done on the intersectionality of trustworthy ML
requirements, since each aspect seems to push us in orthogonal research
directions.

We aim to reconcile two key objectives of trustworthy ML, namely privacy and
robustness. Privacy in the context of ML manifests as the requirement that a
model does not leak information about the data it was trained on [34], such as
revealing whether or not certain data points were included in the training
dataset [43] or what characteristics they exhibit [17]. In our study,
robustness refers to the requirement that a model’s prediction should not
change when its test inputs are perturbed, even in the worst case when
perturbations are chosen adversarially [2, 45, 19].

The current gold standard for providing privacy guarantees is differential
privacy (DP) [13]. In ML, DP produces mathematically rigorous privacy
guarantees by limiting the impact of each individual training data point on
the final model. This is achieved by clipping per-sample gradients, and adding
a well-calibrated amount of noise to all model updates. Clipping serves to
bound the sensitivity of the training algorithm, while the addition of noise
ensures that training will be more likely to output similar models whether any
of the individual data points are added to or removed from the training
dataset. However, clipping and adding noise can impede the convergence of
models [47] and yield decision boundaries that are less smooth [20],
negatively impacting robustness [16].

These findings call for integrating robustness measures into private training,
yet this remains challenging because most methods to increase robustness use
random or adversarial augmentations of training data points, which both
conceptually and practically do not align well with DP training. Conceptually,
augmenting an input increases the sensitivity of private training to it, and
thereby provides additional avenues for information leakage. From a practical
viewpoint, since gradients are computed on a per-example basis for DP,
augmentations drastically increase the time and memory costs of training.

To bridge the gap between robust and private ML model training, we evaluate
the certified robustness of private models and improve it by integrating
state-of-the-art techniques [51, 38] with DP training. CR provides
probabilistic guarantees that perturbations of a certain magnitude will not
change a model’s prediction, regardless of what attack strategy (known or yet
unknown) is used to modify the test inputs, and thereby provides future-proof
robustness guarantees. A common approach for certifying robustness is
_randomized smoothing_ , where a classifier’s outputs are averaged over a
distribution surrounding the test point [28, 29, 10].

While DP and CR are the most promising standards for providing future-proof
privacy and robustness guarantees respectively, their intersection has seen
little attention. Recent works [37, 36, 46] propose adding noise or
adversarial examples while training to improve CR guarantees, but lack the
flexibility to incorporate state-of-the-art methods for non-private training
[51, 38], and usually rely on training additional network components. We aim
to provide CR guarantees within the standard DP training framework, overcoming
several challenges in doing so.

##### Present Work.

We study the possible pitfalls of combining DP and CR in a systematic manner.
Through our analysis and ablation studies combining randomized smoothing
techniques with DP training, we show that standard DP training of ML models is
insufficient to provide strong CR results. We propose DP-CERT, an adaptable
framework for integrating CR into standard DP training which effectively
incorporates augmentations while managing the additional privacy risks.
Compared to private training without augmentations, DP-CERT achieves better
robustness on MNIST, Fashion-MNIST, and CIFAR10, and even surpasses the state-
of-the-art for robustness on the latter dataset under the same privacy
guarantee. Finally, we analyze CR on a per data point basis rather than
averaged across test datasets. Using the gradient norm, Hessian spectral norm,
and local Lipschitz constant, we find that the certifiable radius has a
negative log-linear correlation with these quantities, and compare their
distributions across training methods. We conclude with concrete
recommendations of best practices for the community to achieve CR and DP
simultaneously.

##  2 Preliminaries

##### Problem Setup.

Consider a classification task with $Y$ classes from a dataset
$D=\\{(x_{i},y_{i})\\}_{i=1}^{n}$, where $x_{i}\in\mathbb{R}^{d}$ and
$y_{i}\in\\{1,{...},Y\\}$ denote the $i$-th input and label. Let
$f_{\theta}:\mathbb{R}^{d}\xrightarrow{}\\{1,{...},Y\\}$ be a neural network
with parameters $\theta$, and $F_{\theta}$ denote the soft classifier which
outputs the probability distribution, such that
$f_{\theta}(x)=\operatorname*{arg\,max}_{y\in\\{1,{...},Y\\}}F_{\theta}(x)_{y}$,
where $F_{\theta}(x)_{y}$ denotes the model probability of $x$ being a member
of class $y$.

##### Differential Privacy and DPSGD.

We rely on the rigorous framework of differential privacy (DP) [14] to obtain
models with privacy guarantees. DP ensures that a model’s weights at the end
of training will be similar in distribution whether or not a particular data
point was included in the training set. More formally, let $D$ and
$D^{\prime}$ be two potential training datasets for a model $f_{\theta}$ that
differ in only one data point. The training mechanism $M$ guarantees
$(\varepsilon,\delta)$-DP if for all possible sets of outcomes $S$ of the
training process, it holds that $\mathrm{Pr}\left[M(D)\in S\right]\leq
e^{\varepsilon}\mathrm{Pr}\left[M(D^{\prime})\in S\right]+\delta$. The
parameter $\varepsilon$ specifies the privacy level, with smaller
$\varepsilon$ yielding higher privacy, while $\delta$ quantifies the
probability of the algorithm violating the $\varepsilon$ privacy guarantee.

To obtain a differentially private variant of stochastic gradient descent
(SGD), two modifications need to be made [1]. First, the individual gradients
of each data point are clipped to a norm $C$ to limit the sensitivity of the
model update caused by each data point. Second, choosing a noise level $\rho$,
noise from $\mathcal{N}(0,\rho^{2}C^{2}\mathbf{I})$ is added to the aggregated
gradients to prevent the changes to the model from revealing too much
information about individual data points. We detail the resulting algorithm
DPSGD (1) and a more thorough introduction to DP in Appendix A.1.

##### Certified Robustness.

Adversarial examples are a well-studied phenomenon in ML, in which an input to
a model is perturbed in ways that do not alter its semantics yet cause the
model to misclassify the perturbed input [2, 45, 19]. Formally, for a given
labeled datapoint $(x,y)$ and classifier $f$, an $(\ell_{p},\zeta)$-adversary
aims to create an adversarial example $x^{\prime}$ such that
$\|x^{\prime}-x\|_{p}<\zeta$ and $f(x^{\prime})\neq y$. Despite much research,
the most common defense against adversarial examples remains adversarial
training [19, 58, 39]. While adversarial training improves robustness to known
algorithms for finding adversarial examples, it does not guarantee that a
model will be robust to all adversarial examples (e.g., those crafted with
other attack algorithms). This motivates the development of techniques that
can provide certifiable guarantees of robustness to adversarial examples by
providing a lower bound $r$ on the distance between a correctly classified
input and any adversarial example that may be misclassified [51, 38]. This
lower bound is also known as the certification radius.

##### Randomized Smoothing.

One popular approach for establishing certified robustness (CR) guarantees is
through probabilistic robustness verification which, with high probability,
verifies that no adversarial examples exist within a certain radius of the
original input [30]. The most commonly studied method for providing a
probabilistic robustness verification is through smoothing a classifier [28,
29, 10] by averaging the class predictions of $f$ using a smoothing
distribution $\mu$,

$\displaystyle\hat{g}(x)=\operatorname*{arg\,max}_{c\in[Y]}\int_{\zeta\in\text{supp}(\mu)}\mathbb{I}[f(x+\zeta),c]\mu(\zeta)d\zeta,$
(1)

where $\mathbb{I}[a,b]=1\iff a=b$ and $0$ otherwise [30]. As computing the
integral in Equation (1) is intractable, Monte Carlo sampling is used. We
denote the approximation of $\hat{g}$ given by Monte Carlo sampling as $g$.
One can certify at different radii through the choice of smoothing
distribution $\mu$. Smoothed classifiers are evaluated in terms of their
certified accuracy—the fraction of samples correctly classified when
certifying robustness at a given radius $r$.

A tight $\ell_{2}$ radius was obtained by Cohen et al. [10] when using
isotropic Gaussian noise $\mu=\mathcal{N}(x,\sigma^{2}\mathbf{I})$, where
$\sigma$ is a hyperparameter that controls a robustness/accuracy tradeoff. In
particular, Cohen et al. [10] proved that for any base classifier $f$, the
Gaussian smoothed classifier $g$ is robust around an input $x$ with radius
$r=\frac{\sigma}{2}(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B}))$ where $p_{A}$ and
$p_{B}$ denote the probabilities of $c_{A}$ and $c_{B}$, the most and second-
most probable classes returned by $g(x)$, and $\Phi^{-1}$ is the inverse of
the standard Gaussian CDF. In fact the exact probabilities $p_{A}$ and $p_{B}$
are not needed and one can use lower $\underline{p_{A}}\leq p_{A}$ and upper
$\overline{p_{B}}\geq p_{B}$ bounds instead, approximated by Monte Carlo
sampling.

The output of the smoothed classifier $g(x)$ is approximated by aggregating
the predictions of a base classifier $f(x+\eta)$ for
$\eta\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$. As a high dimensional standard
Gaussian assigns almost no mass near its mean $0$, ensuring that $g(x)$ is
accurate at large certification radii requires the base classifier $f$ to be
accurate on Gaussian perturbed data [18].

##  3 Method

Training machine learning models to be both differentially private and
certifiably robust poses several challenges. The gradient clipping and noise
addition used in DPSGD harms the convergence rate of training [9, 47, 4],
while restrictive privacy budgets may further require stopping training prior
to convergence. Robustness on the other hand suffers for models that are not
converged, as having large gradients at test points makes finding adversarial
examples easier [16].

Another challenge surfaces around the use of adversarial training [19] or
augmentations of datapoints [10] along with DPSGD. As shown by Cohen et al.
[10], data augmentations used for training can enhance a model’s CR, however,
it is crucial to ensure that augmented data points do not leak private
information about the original. Previous works on the combination of DP and CR
have proposed adding noise or adversarial examples during training, but
deviate from the standard DPSGD template to address the privacy risks [37, 36,
46]. These approaches add trainable model components increasing the overall
complexity [37, 46], or lack the flexibility to incorporate the latest
advancements in adversarial training methods [36]. For a more detailed
description of these related works and comparison to our method, please see
Appendix B.

We aim to make CR feasible within the standard training procedure of DPSGD,
with state-of-the-art convergence and proper accounting for additional privacy
risks by introducing the DP-CERT framework. In this section, we describe DP-
CERT, how it effectively manages training with augmented samples while
preserving privacy, and how it enables the integration of recent advancements
in adversarial training and regularizers to enhance certifiable robustness
[40, 29, 56]. Our training framework consists of three stages, summarized in
Figure 1: augmentation multiplicity as the foundational stage, plus
regularization and adversarial training as two optional stages. After the
model is trained, randomized smoothing is used at inference time. We present
four instantiations of the framework: DP-Gaussian, DP-SmoothAdv, DP-Stability,
and DP-MACER, employing different techniques at each stage.

Figure 1: The DP-CERT training framework for providing strong CR guarantees
within DPSGD.

##### Augmentation Multiplicity.

For each data point $(x_{i},y_{i})$, we obtain $K$ augmented data points
$(x_{i}^{j},y_{i})$, where $j\in\\{1,...,K\\}$ and $x_{i}^{j}$ is the $j$-th
augmented data point. For notational convenience, we use $x_{i}^{0}$ to denote
the original data point $x_{i}$. As shown by Cohen et al. [10], training with
Gaussian data augmentation can enhance a model’s certified robustness. When
not using adversarial training, we define $x_{i}^{j}=x_{i}+\eta_{j}$,
$\eta_{j}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$ for $j\neq 0$.

An important component of our DP-CERT is how we handle training with augmented
data points. We adopt augmentation multiplicity, introduced in [11] and
previously unused in studies of CR for DP, which involves averaging the
gradients of multiple augmentations of the same training sample before
clipping. Since all downstream impact to the model weights from sample $x_{i}$
is contained in this averaged gradient, clipping it provides a finite
sensitivity as required for the Sampled Gaussian Mechanism used in DPSGD [32],
and no additional privacy cost is incurred. The model updates can be expressed
as follows

$\theta^{t+1}=\theta^{t}-\lambda_{t}\Biggl{[}\frac{1}{B}\sum_{i\in
B_{t}}\textrm{clip}_{C}\Biggl{(}\frac{1}{K+1}\sum_{j=0}^{K}\nabla_{\theta^{t}}L_{\text{CE}}(x_{i}^{j},y_{i})\Biggr{)}+\frac{\rho
C}{B}\xi\Biggr{]}\text{.}$ (2)

$\theta^{t}$ denotes the model parameters at iteration $t$, $\lambda_{t}$ is
the learning rate, $B$ is the batch size, $C$ is the clipping bound, $K$ is
the number of augmentations, $\rho$ is the noise multiplier,
$\xi\sim\mathcal{N}(0,\textbf{I})$, and
$\nabla_{\theta^{t}}L_{\text{CE}}(x_{i}^{j},y_{i})$ is the gradient with
respect to data point $(x_{i}^{j},y_{i})$. Note that $j$ starts from 0, which
means we include the _original samples_ along with the augmented ones in model
training.

##### Regularization.

We propose adapting stability and consistency regularization to private
training in order to minimize the distance between the output probability of
the original and augmented examples, hereby improving the robustness to input
noise. Stability training [29] adds a smoothed cross-entropy loss as
regularization. Inspired by TRADES [57], we instead use the Kullback–Leibler
(KL) divergence with a hyperparameter $\gamma$ controlling the strength of the
regularization as:

$\displaystyle
L_{\text{stability}}(x_{i},y_{i})=\sum_{j}L_{\textrm{CE}}(x_{i}^{j},y_{i})+\gamma
D_{\text{KL}}\big{(}F_{\theta}(x_{i})||F_{\theta}(x_{i}^{j})\big{)}\text{.}$
(3)

Consistency regularization [25] is a similar technique that instead minimizes
the KL divergence between $\hat{F}_{\theta}(x_{i})$ and $F_{\theta}(x_{i})$,
where $\hat{F}_{\theta}(x)=\frac{1}{K}\sum_{j}F_{\theta}(x_{i}^{j})$ is the
average output probability of all smoothed samples. The loss can be expressed
as

$\displaystyle
L_{\text{consistency}}(x_{i},y_{i})=\sum_{j}L_{\textrm{CE}}(x_{i}^{j},y_{i})+\gamma
D_{\text{KL}}\big{(}\hat{F}_{\theta}(x_{i})||F_{\theta}(x_{i}^{j})\big{)}\text{.}$
(4)

Additionally, we propose integrating MACER [56], an alternative training
modification to directly optimize the certified accuracy at larger robustness
radii without requiring the costly process of adversarial training. MACER
achieves this by decomposing the error of a smoothed classifier into a
classification error term and a robustness error term, the latter reflecting
whether or not the smoothed classifier was able to certify robustness for a
given radius.

##### Adversarial Training.

To achieve better certified accuracy, we incorporate adversarial training by
deploying existing attacks to create adversarial examples. Specifically, we
integrate SmoothAdv [40] into private training, which, given original data
$(x,y)$, optimizes

$\displaystyle\operatorname*{arg\,max}_{\|x^{\prime}-x\|_{2}\leq\epsilon}\Big{(}-\log\underset{\eta\sim
N(0,\sigma^{2}I)}{\mathbb{E}}[F_{\theta}(x^{\prime}+\eta)_{y}]\Big{)},$ (5)

to find an $x^{\prime}$ $\epsilon$-close to $x$ that maximizes the cross
entropy between $g_{\theta}(x^{\prime})$ and label $y$. Using Monte Carlo
sampling, Objective (5) can be optimized by iteratively computing the
approximate gradient

$\displaystyle\nabla_{x^{\prime}}\Big{(}-\log\Big{(}\frac{1}{K}\sum_{j=1}^{K}F_{\theta}(x^{\prime}+\eta_{j})_{y}\Big{)}\Big{)}.$
(6)

where $\eta_{1},...,\eta_{K}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$. The
approximate gradient is then used to update $x^{\prime}$, with the final
$x^{\prime}$ used as examples within augmentation multiplicity.

###  3.1 Metrics for Interpreting Robustness

To elicit some insights into why certain training methods may produce better-
performing models than others, we investigate several per-data point metrics
associated with robustness, the _input gradient norm_ , _input Hessian
spectral norm_ , and _local-Lipschitz constant_ , and study their
relationships with CR. The first two metrics measure the local smoothness of
the loss landscape with respect to the input space. Taylor’s approximation can
be used to show a direct link between these two metrics and the worst-case
change in loss from small input perturbations. Due to this connection, prior
works directly regularized them in order to train more robust models [22, 24,
33].

Gradients and Hessians are highly local quantities that are only connected to
robustness through Taylor’s approximation at small radii around the input data
point. Consequently, they may not be informative at larger radii used to
certify robustness. Thus, we also compare models using an empirical estimate
of the average local Lipschitz constant of the model’s penultimate layer. By
viewing the network as a feature extractor composed with a linear classifier,
using the penultimate layer captures the worst-case sensitivity of the feature
extractor to perturbations of the data. This metric was initially proposed by
Yang et al. [54] to investigate adversarial robustness and is given by

$\frac{1}{n}\sum_{i=1}^{n}\max_{x_{i}^{\prime}\in
B_{\infty}(x,\zeta)}\frac{\|f(x_{i})-f(x_{i}^{\prime})\|_{1}}{\|x_{i}-x_{i}^{\prime}\|_{\infty}},$
(7)

where the maximum is approximated in the same manner as is used for
adversarial example generation, typically projected gradient descent (PGD)
[31].

##  4 Conclusion

We achieve better certified robustness with DPSGD training through
augmentations and randomized smoothing, reconciling two crucial objectives for
trustworthy ML, namely privacy and robustness. To overcome the theoretical and
practical challenges that arise from the combination of both approaches, we
rely on state-of-the-art DP training with augmentations that does not incur
additional privacy costs. We employ various regularizations, and adversarial
training methods to enhance robustness. Our resulting DP-CERT framework is
modular and supports multiple combinations of these methods. Through our
extensive experimental study, we confirm that DPSGD training alone, even with
state-of-the-art convergence, does not provide satisfactory certified
robustness. However, introducing a small number of computationally inexpensive
augmentations into training, such as adding Gaussian noise, suffices to yield
strong privacy protection and certified robustness. By thoroughly analyzing
per-sample metrics, we show that the certified radius correlates with the
local Lipschitz constant and smoothness of the loss surface; this opens a new
path to diagnosing when private models will fail to be robust. To conclude,
our findings yield concrete recommendations for the community to
simultaneously achieve CR and DP, providing a valuable contribution towards
more trustworthy ML. When training from scratch, Gaussian augmentations (not
adversarial) should be used with DPSGD, and randomized smoothing applied at
inference time. For fine-tuning pretrained models, adding stability
regularization also helps accuracy, and leads to much lower local Lipschitz
constants.

##### Acknowledgments.

DG, FB, and NP would like to acknowledge sponsors who support their research
with financial and in-kind contributions: CIFAR through the Canada CIFAR AI
Chair, NSERC through a Discovery Grant, the Ontario Early Researcher Award,
and the Sloan Foundation. Resources used in preparing this research were
provided, in part, by the Province of Ontario, the Government of Canada
through CIFAR, and companies sponsoring the Vector Institute.

## References

  * Abadi et al. [2016] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2016.  doi: 10.1145/2976749.2978318.
  * Biggio et al. [2013] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šrndić, P. Laskov, G. Giacinto, and F. Roli.  Evasion attacks against machine learning at test time.  In _Machine Learning and Knowledge Discovery in Databases: European Conference_ , pages 387–402, 2013.
  * Boenisch et al. [2021] F. Boenisch, P. Sperl, and K. Böttinger.  Gradient masking and the underestimated robustness threats of differential privacy in deep learning.  _arXiv:2105.07985_ , 2021.
  * Bu et al. [2021] Z. Bu, H. Wang, and Q. Long.  On the convergence and calibration of deep learning with differential privacy.  _arXiv:2106.07830_ , 2021.
  * Bu et al. [2022a] Z. Bu, P. Li, and W. Zhao.  Practical adversarial training with differential privacy for deep learning.  _OpenReview Preprint_ , 2022a.  URL https://openreview.net/forum?id=1hw-h1C8bch.
  * Bu et al. [2022b] Z. Bu, J. Mao, and S. Xu.  Scalable and efficient training of large convolutional neural networks with differential privacy.  In _Advances in Neural Information Processing Systems_ , 2022b.
  * Bu et al. [2022c] Z. Bu, Y.-X. Wang, S. Zha, and G. Karypis.  Automatic clipping: Differentially private deep learning made easier and stronger.  _arXiv:2206.07136_ , 2022c.
  * Chen et al. [2021] C.-F. R. Chen, Q. Fan, and R. Panda.  CrossViT: Cross-Attention Multi-Scale Vision Transformer for Image Classification.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 357–366, October 2021.
  * Chen et al. [2020] X. Chen, S. Z. Wu, and M. Hong.  Understanding Gradient Clipping in Private SGD: A Geometric Perspective.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Cohen et al. [2019] J. Cohen, E. Rosenfeld, and Z. Kolter.  Certified adversarial robustness via randomized smoothing.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pages 1310–1320, 2019.
  * De et al. [2022] S. De, L. Berrada, J. Hayes, S. L. Smith, and B. Balle.  Unlocking high-accuracy differentially private image classification through scale.  _arXiv:2204.13650_ , 2022.
  * Deng et al. [2009] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 248–255, 2009.  doi: 10.1109/CVPR.2009.5206848.
  * Dwork and Roth [2014] C. Dwork and A. Roth.  The Algorithmic Foundations of Differential Privacy.  _Found. Trends Theor. Comput. Sci._ , 9(3–4):211–407, Aug. 2014.  ISSN 1551-305X.  doi: 10.1561/0400000042.
  * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating Noise to Sensitivity in Private Data Analysis.  In _Theory of Cryptography_ , pages 265–284. Springer Berlin Heidelberg, 2006.  ISBN 978-3-540-32732-5.
  * Esipova et al. [2023] M. S. Esipova, A. A. Ghomi, Y. Luo, and J. C. Cresswell.  Disparate impact in differential privacy from gradient misalignment.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Fawzi et al. [2018] A. Fawzi, S.-M. Moosavi-Dezfooli, P. Frossard, and S. Soatto.  Empirical study of the topology and geometry of deep networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , June 2018.
  * Fredrikson et al. [2015] M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security_ , page 1322–1333, 2015.  doi: 10.1145/2810103.2813677.
  * Gao et al. [2022] Y. Gao, I. Shumailov, K. Fawaz, and N. Papernot.  On the limitations of stochastic pre-processing defenses.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Goodfellow et al. [2014] I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  _arXiv:1412.6572_ , 2014.
  * Hayes et al. [2022] J. Hayes, B. Balle, and M. P. Kumar.  Learning to be adversarially robust and differentially private.  _arXiv:2201.02265_ , 2022.
  * Hinton and Zemel [1993] G. E. Hinton and R. Zemel.  Autoencoders, Minimum Description Length and Helmholtz Free Energy.  In _Advances in Neural Information Processing Systems_ , 1993.
  * Hoffman et al. [2019] J. Hoffman, D. A. Roberts, and S. Yaida.  Robust Learning with Jacobian Regularization, 2019.
  * Horváth et al. [2021] M. Z. Horváth, M. N. Müller, M. Fischer, and M. Vechev.  Boosting randomized smoothing with variance reduced classifiers.  _arXiv preprint arXiv:2106.06946_ , 2021.
  * Jakubovitz and Giryes [2018] D. Jakubovitz and R. Giryes.  Improving DNN Robustness to Adversarial Attacks using Jacobian Regularization.  In _Proceedings of the European Conference on Computer Vision_ , 2018\.
  * Jeong and Shin [2020] J. Jeong and J. Shin.  Consistency regularization for certified robustness of smoothed classifiers.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Krizhevsky and Hinton [2009] A. Krizhevsky and G. Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. [2010] Y. LeCun, C. Cortes, and C. Burges.  MNIST handwritten digit database.  _Available at http://yann.lecun.com/exdb/mnist_ , 2, 2010.
  * Lecuyer et al. [2019] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana.  Certified robustness to adversarial examples with differential privacy.  In _2019 IEEE Symposium on Security and Privacy_ , pages 656–672, 2019.  doi: 10.1109/SP.2019.00044.
  * Li et al. [2019] B. Li, C. Chen, W. Wang, and L. Carin.  Certified adversarial robustness with additive noise.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Li et al. [2023] L. Li, T. Xie, and B. Li.  SoK: Certified Robustness for Deep Neural Networks.  In _2023 IEEE Symposium on Security and Privacy_ , pages 94–115, 2023\.  doi: 10.1109/SP46215.2023.00006.
  * Madry et al. [2018] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , 2018.
  * Mironov et al. [2019] I. Mironov, K. Talwar, and L. Zhang.  Rényi Differential Privacy of the Sampled Gaussian Mechanism.  _arXiv:1908.10530_ , 2019.
  * Moosavi-Dezfooli et al. [2019] S.-M. Moosavi-Dezfooli, A. Fawzi, J. Uesato, and P. Frossard.  Robustness via curvature regularization, and vice versa.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , June 2019.
  * Papernot et al. [2018] N. Papernot, P. McDaniel, A. Sinha, and M. P. Wellman.  SoK: Security and Privacy in Machine Learning.  In _2018 IEEE European Symposium on Security and Privacy_ , pages 399–414, 2018.  doi: 10.1109/EuroSP.2018.00035.
  * Paszke et al. [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Phan et al. [2020] H. Phan, M. T. Thai, H. Hu, R. Jin, T. Sun, and D. Dou.  Scalable differential privacy with certified robustness in adversarial learning.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119, pages 7683–7694, 2020.
  * Phan et al. [2019] N. Phan, M. N. Vu, Y. Liu, R. Jin, D. Dou, X. Wu, and M. T. Thai.  Heterogeneous gaussian mechanism: Preserving differential privacy in deep learning with provable robustness.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , 2019.  doi: 10.24963/ijcai.2019/660.
  * Raghunathan et al. [2018] A. Raghunathan, J. Steinhardt, and P. Liang.  Certified defenses against adversarial examples.  In _International Conference on Learning Representations_ , 2018.
  * Rebuffi et al. [2021] S.-A. Rebuffi, S. Gowal, D. A. Calian, F. Stimberg, O. Wiles, and T. A. Mann.  Data augmentation can improve robustness.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Salman et al. [2019] H. Salman, J. Li, I. Razenshteyn, P. Zhang, H. Zhang, S. Bubeck, and G. Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Salman et al. [2020] H. Salman, M. Sun, G. Yang, A. Kapoor, and J. Z. Kolter.  Denoised smoothing: A provable defense for pretrained classifiers.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Shamsabadi and Papernot [2022] A. S. Shamsabadi and N. Papernot.  Losing less: A loss for differentially private deep learning.  _OpenReview Preprint_ , 2022.  URL https://openreview.net/forum?id=u7PVCewFya.
  * Shokri et al. [2017] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  In _2017 IEEE Symposium on Security and Privacy_ , pages 3–18, 2017\.  doi: 10.1109/SP.2017.41.
  * Simonyan and Zisserman [2014] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv:1409.1556_ , 2014.
  * Szegedy et al. [2013] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  _arXiv:1312.6199_ , 2013.
  * Tang et al. [2022] P. Tang, W. Wang, X. Gu, J. Lou, L. Xiong, and M. Li.  Two Birds, One Stone: Achieving both Differential Privacy and Certified Robustness for Pre-trained Classifiers via Input Perturbation.  _OpenReview preprint_ , 2022.  URL https://openreview.net/forum?id=keQjAwuC7j-.
  * Tramèr and Boneh [2021] F. Tramèr and D. Boneh.  Differentially private learning needs better features (or much more data).  In _International Conference on Learning Representations_ , 2021.
  * Tramèr et al. [2017] F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel.  Ensemble adversarial training: Attacks and defenses.  _arXiv:1705.07204_ , 2017.
  * Tsipras et al. [2019] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry.  Robustness may be at odds with accuracy.  In _International Conference on Learning Representations_ , 2019.
  * Tursynbek et al. [2021] N. Tursynbek, A. Petiushko, and I. Oseledets.  Robustness threats of differential privacy.  _arXiv:2012.07828_ , 2021.
  * Wong and Kolter [2018] E. Wong and Z. Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _Proceedings of the 35th International Conference on Machine Learning_ , 2018.
  * Xia et al. [2022] T. Xia, S. Shen, S. Yao, X. Fu, K. Xu, X. Xu, X. Fu, and W. Wang.  Differentially private learning with per-sample adaptive clipping.  _arXiv:2212.00328_ , 2022.
  * Xiao et al. [2017] H. Xiao, K. Rasul, and R. Vollgraf.  Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms.  _arXiv:1708.07747_ , 2017.
  * Yang et al. [2020] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. R. Salakhutdinov, and K. Chaudhuri.  A closer look at accuracy vs. robustness.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Yousefpour et al. [2021] A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov.  Opacus: User-friendly differential privacy library in PyTorch.  _arXiv:2109.12298_ , 2021.
  * Zhai et al. [2020] R. Zhai, C. Dan, D. He, H. Zhang, B. Gong, P. Ravikumar, C.-J. Hsieh, and L. Wang.  MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius.  In _International Conference on Learning Representations_ , 2020.
  * Zhang et al. [2019a] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan.  Theoretically principled trade-off between robustness and accuracy.  In _International conference on machine learning_ , pages 7472–7482. PMLR, 2019a.
  * Zhang et al. [2019b] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. E. Ghaoui, and M. Jordan.  Theoretically principled trade-off between robustness and accuracy.  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 7472–7482, 2019b.
  * Zhang et al. [2012] J. Zhang, Z. Zhang, X. Xiao, Y. Yang, and M. Winslett.  Functional mechanism: regression analysis under differential privacy.  _arXiv preprint arXiv:1208.0219_ , 2012.
  * Zhang and Bu [2022] Y. Zhang and Z. Bu.  Differentially private optimizers can learn adversarially robust models.  _arXiv:2211.08942_ , 2022.

##  Appendix A Differential Privacy Background

###  A.1 Differential Privacy and DPSGD

Differential Privacy (DP) [14] is a formal framework that aims to provide
mathematical guarantees on the privacy of individual data points in a dataset,
while allowing one to learn properties over the entire dataset. More formally
a randomized mechanism $M$ fulfills $(\varepsilon,\delta)$-DP if

$\displaystyle\mathrm{Pr}\left[M(D)\in S\right]\leq
e^{\varepsilon}\mathrm{Pr}\left[M(D^{\prime})\in S\right]+\delta,$ (8)

where $D$ and $D^{\prime}$ are neighboring datasets (i.e. datasets differing
in only one data point), $S$ is the set of output values of $M$, and
$\epsilon$ and $\delta$ are privacy parameters.

$\varepsilon$ indicates the level of obtained privacy, with a smaller value of
$\varepsilon$ indicating a stronger privacy guarantee. $\delta$ accounts for
the probability that the algorithm can violate the privacy guarantee, i.e.,
not stay within the specified $\varepsilon$. A larger value of $\delta$
increases the chance of privacy leakage.

The most popular algorithm for implementing DP guarantees in ML is
differentially private stochastic gradient descent (DPSGD) [1]. It extends the
standard SGD algorithm with two additional steps, namely gradient clipping and
noise addition. While the former bounds the sensitivity of the model update,
the latter implements the privacy guarantee by preventing the gradients from
revealing too much information about individual data points. More formally,
let $\theta_{t}$ denote the model parameters at training iteration $t$. At
each iteration $t$, DPSGD computes the gradient of the loss function with
respect to $\theta_{t}$ at an individual data point $x$ as
$\nabla_{\theta}L(\theta_{t},x)$. The data point’s gradient is then clipped to
a maximum norm $C$ using the operation
$\text{clip}\left(\nabla_{\theta}L(\theta_{t},x),C\right)$, which replaces the
gradient with a vector of the same direction but smaller magnitude if its norm
exceeds $C$. The clipped gradient from all datapoints in a batch are
aggregated, then perturbed by adding random noise from
$\mathcal{N}(0,\rho^{2}C^{2}\mathbf{I})$, where $\rho$ is the noise scale
parameter. We detail DPSGD in Algorithm 1.

Algorithm 1 Standard DPSGD, adapted from [1].

0: Private training set $D=\\{(x_{i},y_{i})\mid i\in[N_{\text{prv}}]\\}$, loss
function $L(\theta_{t},x)$, Parameters: learning rate $\eta_{t}$, noise scale
$\rho$, group size $B$, gradient norm bound $C$.

1: Initialize ${\theta}_{0}$ randomly

2: for $t\in[T]$ do

3: Sample mini-batch $B_{t}$ with sampling probability $B/N_{\text{prv}}$
{Poisson sampling}

4: For each $i\in B_{t}$, compute
${\mathbf{g}}_{t}(x_{i})\leftarrow\nabla_{\theta}L({\theta}_{t},x_{i})$
{Compute per-sample gradients}

5:
$\bar{{\mathbf{g}}}_{t}(x_{i})\leftarrow{\mathbf{g}}_{t}(x_{i})/\max\left(1,\frac{\|{\mathbf{g}}_{t}(x_{i})\|_{2}}{C}\right)$
{Clip gradients}

6:
$\tilde{{\mathbf{g}}}_{t}\leftarrow\frac{1}{|B_{t}|}\left(\sum_{i}\bar{{\mathbf{g}}}_{t}(x_{i})+\mathcal{N}\left(0,\rho^{2}C^{2}{\mathbf{I}}\right)\right)$
{Add noise to aggregated gradient}

7: ${\theta}_{t+1}\leftarrow{\theta}_{t}-\eta_{t}\tilde{{\mathbf{g}}}_{t}$
{Gradient Descent}

8: end for

9: Output ${\theta}_{T}$ and compute the overall privacy cost
$(\varepsilon,\delta)$ using a privacy accounting method.

###  A.2 DP-PSAC

We used DP-PSAC [52] in addition to DPSGD to ensure differential privacy while
training. Per-sample adaptive clipping (PSAC) is one of a number of approaches
that tries to reduce the bias from per-example clipping [4, 7, 15], and was
motivated for maximizing the signal to noise ratio of gradient updates. It has
shown the best performance on several datasets including MNIST, FashionMNIST
and CIFAR10. To compare with DPSGD, we incorporated DP-PSAC into our
experiments.

DP-PSAC is similar to DPSGD, with the exception that it employs a different
clipping method,

$\textrm{clip}_{C,r}(g_{i,t})=C\cdot
g_{i,t}\bigg{/}\biggl{(}\|g_{i,t}\|+\frac{r}{\|g_{i,t}\|+r}\biggr{)}.$ (9)

Where $g_{i,t}$ denotes the loss gradient for the $i$th sample at iteration
$t$. The motivation of this clipping method is that per-example gradients with
small norms come from data points on which the model has already converged,
and these gradients are often orthogonal to mini-batch gradients. Hence, small
norm gradients should not have disproportionally large contributions to the
batch gradient as when using per-sample normalization methods [7]. Compared to
such approaches, PSAC reduces the influence of small norm gradients.

##  Appendix B Additional Background and Related Work

###  B.1 Randomized Smoothing

Previous works have tackled improving the certified robustness of randomized
smoothing methods in a variety of ways. The dominant approach for doing so
involves modifications to training the base classifier so as to increase
robustness and accuracy under Gaussian perturbations. The simplest approach
involves adding noise to inputs during training [10], while other works
utilize regularization [56, 29, 25], ensembling [23], and adversarial training
[40]. While these modifications have been independently studied in the context
of improving the certified accuracy of randomized smoothing classifiers, we
are the first work integrating these methods with private training through
augmentation multiplicity. We provide additional information on two of these
training modification methods mentioned in Section 3.

####  B.1.1 SmoothAdv

One of the most effective methods for improving the performance of randomized
smoothing classifiers utilizes adversarial training of the classifier. The
method, SmoothAdv proposed in [40], was motivated by the idea that to improve
certified accuracy at a larger certification radius one needs a classifier
that is more robust to local perturbations, and the best known method of
achieving that is through adversarial training.

Given a soft classifier $F:\mathbb{R}^{d}\rightarrow P(Y)$ where $P(Y)$ is the
set of probability distributions over $Y$, its smoothed soft classifier $G$ is
defined as:

$G(x)=(F*\mathcal{N}(0,\sigma^{2}I))(x)=\mathbb{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}[F(x+\delta)].$
(10)

The goal of SmoothAdv is to find a point $\hat{x}$ that maximizes the loss of
$G$ in an $l_{2}$ ball around $x$ for the cross entropy loss. They use a
projected gradient descent variant to approximately find $\hat{x}$, and define
$J(x^{\prime})=l_{\textrm{CE}}(G(x^{\prime}),y)$ to compute

$\Delta_{x^{\prime}}J(x^{\prime})=\Delta_{x^{\prime}}\biggl{(}-\log\mathbb{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}[F(x^{\prime}+\delta)_{y}]\biggr{)}.$
(11)

Since the expectation in Equation 11 is difficult to compute exactly, a Monte
Carlo approximation is used by sampling noise
$\delta_{1},...,\delta_{m}\sim\mathcal{N}(0,\sigma^{2}I)$ to approximately
compute $\Delta_{x^{\prime}}J(x^{\prime})$,

$\Delta_{x^{\prime}}J(x^{\prime})\approx\Delta_{x^{\prime}}\biggl{(}-\log\biggl{(}\frac{1}{m}\sum\limits_{i=1}\limits^{m}[F(x^{\prime}+\delta_{i})_{y}]\biggr{)}\biggr{)}.$
(12)

Finally, $x^{\prime}$ is updated by taking a step in the direction of
$\Delta_{x^{\prime}}J(x^{\prime})$, and the final $x^{\prime}$ is used to
train the classifier.

####  B.1.2 MACER

Similar to the Stability training method from Equation 3, MACER [56] also
modifies the loss for optimization so that the final model has higher
certified accuracy at a larger certified radius. In contrast to SmoothAdv,
regularizing the model to be more robust in this sense does not require
generation of adversarial examples and instead can be optimized directly. The
method achieves this by decomposing the error of the smoothed classifier into
a classification error term and a robustness error term. The former captures
the error from the smoothed classifier misclassifying a given datapoint and
the latter captures the error of a certified radius being too small.

Robustness error, much like hard label classification error, cannot be
optimized directly. To address this, MACER proposes a surrogate loss to
minimize the robustness error term—a hinge loss on the data $(x,y)$ for which
$g_{\theta}(x)=y$,

$\displaystyle\max\\{0,\gamma-(\Phi^{-1}(\hat{f}_{\theta}(x)_{y})-\Phi^{-1}(\hat{f}_{\theta}(x)_{\hat{y}\neq
y}))\\},$ (13)

where $\hat{f}_{\theta}(x)$ denotes the average of softmax probabilties on
Gaussian perturbations of $x$, $\hat{f}_{\theta}(x)_{y}$ denotes the softmax
probability $\hat{f}_{\theta}(x)$ assigned to the true class $y$, and
$\hat{f}_{\theta}(x)_{\hat{y}\neq y}$ denotes the maximum softmax probability
for a class that isn’t the true class. This loss term is added to cross
entropy of loss from the soft smoothed classifier as a regularization term.

###  B.2 DPSGD and Robustness

The adversarial robustness of differentially private models has been studied
in several prior works. Tursynbek et al. [50] demonstrated that models trained
with DPSGD are sometimes more vulnerable to input perturbations. Boenisch et
al. [3] further consolidate this claim with more experiments, and showed that
improper choices of hyperparameters can lead to gradient masking. Zhang and Bu
[60] find that the success of adversarially training robust models with DPSGD
depends greatly on choices of hyperparameters, namely smaller clipping
thresholds and learning rates, differing from those that produce the most
accurate models. Furthermore, they found that pretraining models helps further
mitigate the privacy-robustness-accuracy tradeoff. These works reveal
interesting adversarial robustness characteristics of DP models, however, they
do not endeavor to _improve_ the robustness of DP models.

DP-ADV [5] proposes combining adversarial training with DPSGD. They achieve
this by replacing the original example with an adversarially crafted example,
obtained with a FGSM or PGD attack. Their work is orthogonal to ours in that
they focus on the robustness to adversarial attacks, whereas we focus on
certified robustness. Additionally, they do not perform any data augmentation,
which has been shown to be effective against adversarial attacks [39].

There are a few prior works that have studied certified robustness with
differential privacy guarantees. Phan et al. [37] first introduced a framework
called Secure-SGD, which aims to achieve both certified robustness and
differential privacy simultaneously. They use a PixelDP approach, proposed by
Lecuyer et al. [28], to attain certified robustness and introduced the
Heterogeneous Gaussian Mechanism, which involves adding heterogeneous Gaussian
noise instead of element-wise Gaussian noise to the gradient. Another work
[36] introduced the StoBatch algorithm to guarantee DP and certified
robustness. First, it employs an Autoencoder (AE) [21] and a functional
mechanism (objective perturbation [59]) to reconstruct input examples while
preserving DP. Subsequently, this reconstructed data is use to train a deep
neural network. They implement adversarial training [48] to achieve both
robustness and DP for the neural network. Tang et al. [46] propose
transforming input gradients with perturbation during training, and introduced
the Multivariate Gaussian Mechanism. This mechanism allows them to achieve the
same DP guarantee with less noise added to the gradient. They follow the
architecture of denoised smoothing, adding differentially private noise to a
pre-trained classifier.

Compared with the existing work, DP-CERT 1) presents a simple and effective
augmented training scheme, allowing practitioners to introduce different
adversarial training techniques through noising, regularization, and
adversarially crafted examples, 2) doesn’t rely on a denoiser at the inference
time, reducing inference latency, and 3) can be used for training both
randomly initialized or pre-trained networks.

##  Appendix C Experimental Details

###  C.1 Dataset Statistics

We conduct experiments on MNIST, Fashion-MNIST and CIFAR10. The MNIST database
of handwritten digits has a training set of 60,000 examples, and a test set of
10,000 examples, as does Fashion-MNIST. Each example in MNIST and Fashion-
MNIST is a 28$\times$28 grayscale image, associated with one label from 10
classes.

The CIFAR-10 dataset consists of 60,000 RGB images from 10 classes, with 6,000
images per class. There are 50,000 training images and 10,000 test images of
size 32$\times$32$\times$3.

###  C.2 Code and Implementation

Our code will be released upon publication. We give credit to the original
repository for the implementation of SmoothAdv, MACER, stability, and
consistency regularization.111https://github.com/jh-jeong/smoothing-
consistency For CERTIFY222https://github.com/locuslab/smoothing and local
Lipschitz constant333https://github.com/yangarbiter/robust-local-lipschitz
evaluations, we use the code provided by the original authors.

##  Appendix D Additional Results

###  D.1 Additional Comparative Study

Figure 2: Approximate certified accuracy comparison on MNIST (top), and
Fashion-MNIST (bottom). Figure 3: Approximate certified accuracy comparison on
CIFAR10. Baseline results are from [46].

Figure 2 shows the approximate certified accuracy as the certified radius is
increased on MNIST and Fashion-MNIST, corresponding to Table
LABEL:tab:certified_accuracy_main in the main text, for different values of
the noise $\sigma$ used during training. All variants of DP-CERT greatly
outperform the baseline methods which do not specifically encourage
robustness. Similar plots for CIFAR10 were shown in Figure
LABEL:fig:certified_accuracy_main in the main text. We also compare
implementations of DP-CERT to the prior approaches TransDenoiser, SecureSGD,
and StoBatch on CIFAR10 in Figure 3. All variants of DP-CERT achieve state-of-
the-art certified accuracy on CIFAR10 for differentially private models, with
a much smaller pre-trained model compared to [46].

###  D.2 Additional Ablation Study

To extend Figure LABEL:fig:ablation from the main text, we show the complete
ablation study results in Figures 4 and 5 on MNIST and Fashion-MNIST under
$\sigma\in\\{0.25,0.5,1.0\\}$. Figure 4 shows the effects of adding
consistency regularization, or changing the DP clipping method to PSAC.
Neither approach makes significant changes to the certified accuracy. Figure 5
shows the effects of changing the multiplicity of augmentations. Again, there
is little difference in certified accuracy when using more than two
augmentations, so we advocate using the smallest amount which is least
expensive computationally. We emphasize that using _no_ augmentations is
significantly worse than using two or more – the case without augmentations is
simply DPSGD which was compared in Table LABEL:tab:certified_accuracy_main and
Figures LABEL:fig:certified_accuracy_main and 2. One of our main conclusions
is that adding a small number of Gaussian augmentations to DPSGD is sufficient
to greatly improve certified robustness.

Figure 4: Certified accuracy of DP-Gaussian and DP-SmoothAdv combined with
consistency regularization and PSAC on MNIST (top) and Fashion-MNIST (bottom).

Figure 5: Certified accuracy comparison under different numbers of
augmentations (2, 4, 6 and 8) on MNIST (top) and Fashion-MNIST (bottom)

###  D.3 Additional Per-sample Metric Analysis

Figures 6 through 10 show the distributions of our three proposed metrics for
interpreting robustness, the input gradient norms, input Hessian spectral
norms, and local Lipschitz constants. We use various training methods on MNIST
and Fashion-MNIST under $\sigma\in\\{0.25,0.5,1.0\\}$. Echoing the analysis of
RQ1 in Section LABEL:sec:fine_grained_analysis, DPSGD produces a bimodal
distribution for the Hessian and gradient norms, while Regular training
exhibits a log-normal distribution and smaller tails for large metric values.
PSAC shifts the distributions to be closer to those of Regular training by
reducing clipping bias. DP-CERT methods, on the other hand, shift the
distribution towards smaller metric values, resulting in higher certified
accuracy. An exception is DP-Stability, which has significantly higher average
gradient and Hessian norms, but without the mode at very high values, and with
lower local Lipschitz constants than the other three variants.

(a) Comparison among Regular, DPSGD, PSAC, and DP-Gaussian training.

(b) Comparison among DP-Gaussian, DP-SmoothAdv, DP-Stability, and DP-MACER.

Figure 6: Per-sample metric comparisons on MNIST with $\sigma=0.25$

(a) Comparison among Regular, DPSGD, PSAC, and DP-Gaussian training.

(b) Comparison among DP-Gaussian, DP-SmoothAdv, DP-Stability, and DP-MACER.

Figure 7: Per-sample metric comparisons on MNIST with $\sigma=1.0$

(a) Comparison among Regular, DPSGD, PSAC, and DP-Gaussian training.

(b) Comparison among DP-Gaussian, DP-SmoothAdv, DP-Stability, and DP-MACER.

Figure 8: Per-sample metric comparisons on Fashion-MNIST with $\sigma=0.25$

(a) Comparison among Regular, DPSGD, PSAC, and DP-Gaussian training.

(b) Comparison among DP-Gaussian, DP-SmoothAdv, DP-Stability, and DP-MACER.

Figure 9: Per-sample metric comparisons on Fashion-MNIST with $\sigma=0.5$

(a) Comparison among Regular, DPSGD, PSAC, and DP-Gaussian training.

(b) Comparison among DP-Gaussian, DP-SmoothAdv, DP-Stability, and DP-MACER.

Figure 10: Per-sample metric comparisons on Fashion-MNIST with $\sigma=1.0$

Figure 11 shows the distribution of certified radii for baseline training
methods and an instance of DP-CERT for the same settings as Figure
LABEL:fig:analysis-mnist-0.5. Whereas Regular, DPSGD, and PSAC training all
have a large spike of samples that cannot be certified at any level, DP-
Gaussian achieves certified radii above 1.0 for most samples, with the mode
even higher at 1.6.

Figure 11: Distributions of certified radii for Regular, DPSGD, PSAC, and DP-
Gaussian training on MNIST with $\sigma=0.5$.

While our main focus has been on certified robustness, we briefly compare to
adversarial robustness against common attacks. Figure 12 shows the adversarial
accuracy under a $l_{\infty}$-FGSM attack, with the attack strength in
$\\{0.0005,0.01,0.1,0.5,1\\}$. Consistent with the ranking of the average
local Lipschitz constant from Figures 6 through 10, DP-Stability consistently
outperforms other approaches, while DP-Gaussian, DP-SmoothAdv, and DP-MACER
all achieve similar adversarial accuracy above that of the unprotected
baselines.

Figure 12: Adversarial accuracy against a $L_{\infty}$-FGSM attack under
various attack strengths on MNIST (top) and Fashion-MNIST (bottom).

Finally, we study the metric distributions for individual samples that can or
cannot be certified above a threshold $\tau$, similar to Figure
LABEL:fig:analysis-mnist-0.5-local-lipschitz in the main text. Figures 13 and
14 respectively show the input gradient norm and input Hessian spectral norm
distributions for the baselines and proposed methods, with different threshold
values $\tau\in\\{0.25,0.5,1.0\\}$. In each subfigure the top row shows
samples that can be certified at radius larger than $\tau$, and the bottom row
shows samples that cannot. We only show the plots for MNIST under $\sigma=0.5$
for brevity. We note that the shapes of the distributions between gradients
and Hessians resemble each other closely. The analysis of RQ2 in Section
LABEL:sec:fine_grained_analysis also applies here; for example, in Figure 13,
the samples with certified radii below the threshold have slightly higher
average input gradient norm. As the threshold $\tau$ increases, more examples
with _higher_ input gradient norm end up below the certified radius threshold.
We find that the samples on which the models are least robust tend to be
samples where the gradient and Hessian norms are largest. From this
observation we expect that training methods that reduce the prevalence of
large gradient and Hessian norms should be the most robust, which is indeed
confirmed by DP-Stability which does not have the mode at very large values in
Figures 6 through 10, and the best adversarial robustness in Figure 12.

(a) Per-sample metric comparison among Regular, DPSGD, PSAC, and DP-Gaussian
training.

(b) Per-sample metric comparison among DP-Gaussian, DP-SmoothAdv, DP-
Stability, and DP-MACER.

Figure 13: Comparing the distribution of input gradient norm of baselines and
proposed methods on MNIST. All DP-CERT methods are trained with $\sigma=0.5$.
We show the logarithmic metric values for all methods for better
visualization.

(a) Per-sample metric comparison among Regular, DPSGD, PSAC, and DP-Gaussian
training.

(b) Per-sample metric comparison among DP-Gaussian, DP-SmoothAdv, DP-
Stability, and DP-MACER.

Figure 14: Comparing the distribution of input Hessian spectral norm of
baselines and proposed methods on MNIST. All DP-CERT methods are trained with
$\sigma=0.5$. We show the logarithmic metric values for all methods for better
visualization.