Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers

Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, Sebastien Bubeck

Introduction

Neural networks have been very successful in tasks such as image classification and speech recognition, but have been shown to be extremely brittle to small, adversarially-chosen perturbations of their inputs . A classifier (e.g., a neural network), which correctly classifies an image $x$ , can be fooled by an adversary to misclassify $x+\delta$ where $\delta$ is an adversarial perturbation so small that $x$ and $x+\delta$ are indistinguishable for the human eye. Recently, many works have proposed heuristic defenses intended to train models robust to such adversarial perturbations. However, most of these defenses were broken using more powerful adversaries . This encouraged researchers to develop defenses that lead to certifiably robust classifiers, i.e., whose predictions for most of the test examples $x$ can be verified to be constant within a neighborhood of $x$ . Unfortunately, these techniques do not immediately scale to large neural networks that are used in practice.

In this paper, we employ adversarial training to substantially improve on the previous certified robustness resultsNote that we do not provide a new certification method incorporating adversarial training; the improvements that we get are due to the higher quality of our base classifiers as a result of adversarial training. of randomized smoothing . We present, for the first time, a direct attack for smoothed classifiers. We then demonstrate how to use this attack to adversarially train smoothed models with not only boosted empirical robustness but also substantially improved certifiable robustness using the certification method of Cohen et al. .

Finally, we provide an alternative, but more concise, proof of the tight robustness guarantee of Cohen et al. by casting this as a nonlinear Lipschitz property of the smoothed classifier. See appendix A for the complete proof.

Our techniques

Here we describe our techniques for adversarial attacks and training on smoothed classifiers. We first require some background on randomized smoothing classifiers. For a more detailed description of randomized smoothing, see Cohen et al. .

where $\Phi^{-1}$ is the inverse of the standard Gaussian CDF. It is not clear how to compute $p_{A}$ and $p_{B}$ exactly (if $f$ is given by a deep neural network for example). Monte Carlo sampling is used to estimate some $\underline{p_{A}}$ and $\overline{p_{B}}$ for which $\underline{p_{A}}\leq p_{A}$ and $\overline{p_{B}}\geq p_{B}$ with arbitrarily high probability over the samples. The result of (2) still holds if we replace $p_{A}$ with $\underline{p_{A}}$ and $p_{B}$ with $\overline{p_{B}}$ .

This guarantee can in fact be obtained alternatively by explicitly computing the Lipschitz constant of the smoothed classifier, as we do in Appendix A.

2 SmoothAdv: Attacking smoothed classifiers

We will refer to ( $\mathcal{S}$ ) as the SmoothAdv objective. The SmoothAdv objective is highly non-convex, so as is common in the literature, we will optimize it via projected gradient descent (PGD), and variants thereof. It is hard to find exact gradients for ( $\mathcal{S}$ ), so in practice we must use some estimator based on random Gaussian samples. There are a number of different natural estimators for the derivative of the objective function in ( $\mathcal{S}$ ), and the choice of estimator can dramatically change the performance of the attack. For more details, see Section 3.

We note that ( $\mathcal{S}$ ) should not be confused with the similar-looking objective

as suggested in section G.3 of . There is a subtle, but very important, distinction between ( $\mathcal{S}$ ) and (4). Conceptually, solving (4) corresponds to finding an adversarial example of $F$ that is robust to Gaussian noise. In contrast, ( $\mathcal{S}$ ) is directly attacking the smoothed model i.e. trying to find adversarial examples that decrease the probability of correct classification of the smoothed soft classifier $G$ . From this point of view, ( $\mathcal{S}$ ) is the right optimization problem that should be used to find adversarial examples of $G$ . This distinction turns out to be crucial in practice: empirically, Cohen et al. found attacks based on (4) not to be effective.

Interestingly, for a large class of classifiers, including neural networks, one can alternatively derive the objective ( $\mathcal{S}$ ) from an optimization perspective, by attempting to directly find adversarial examples to the smoothed hard classifier that the neural network provides. While they ultimately yield the same objective, this perspective may also be enlightening, and so we include it in Appendix B.

3 Adversarial training using SmoothAdv

We now wish to use our new attack to boost the adversarial robustness of smoothed classifiers. We do so using the well-studied adversarial training framework . In adversarial training, given a current set of model weights $w_{t}$ and a labeled data point $(x_{t},y_{t})$ , one finds an adversarial perturbation $\hat{x}_{t}$ of $x_{t}$ for the current model $w_{t}$ , and then takes a gradient step for the model parameters, evaluated at the point $(\hat{x}_{t},y_{t})$ . Intuitively, this encourages the network to learn to minimize the worst-case loss over a neighborhood around the input.

At a high level, we propose to instead do adversarial training using an adversarial example for the smoothed classifier. We combine this with the approach suggested in Cohen et al. , and train at Gaussian perturbations of this adversarial example. That is, given current set of weights $w_{t}$ and a labeled data point $(x_{t},y_{t})$ , we find $\hat{x}_{t}$ as a solution to ( $\mathcal{S}$ ), and then take a gradient step for $w_{t}$ based at gaussian perturbations of $\hat{x}_{t}$ . In contrast to standard adversarial training, we are training the base classifier so that its associated smoothed classifier minimizes worst-case loss in a neighborhood around the current point. For more details of our implementation, see Section 3.2. We emphasize that although we are training using adversarial examples for the smoothed soft classifier, in the end we certify the robustness of the smoothed hard classifier we obtain after training.

We make two important observations about our method. First, adversarial training is an empirical defense, and typically offers no provable guarantees. However, we demonstrate that by combining our formulation of adversarial training with randomized smoothing, we are able to substantially boost the certifiable robust accuracy of our smoothed classifiers. Thus, while adversarial training using SmoothAdv is still ultimately a heuristic, and offers no provable robustness by itself, the smoothed classifier that we obtain using this heuristic has strong certifiable guarantees.

Second, we found empirically that to obtain strong certifiable numbers using randomized smoothing, it is insufficient to use standard adversarial training on the base classifier. While such adversarial training does indeed offer good empirical robust accuracy, the resulting classifier is not optimized for randomized smoothing. In contrast, our method specifically finds base classifiers whose smoothed counterparts are robust. As a result, the certifiable numbers for standard adversarial training are noticeably worse than those obtained using our method. See Appendix C.1 for an in-depth comparison.

Implementing SmoothAdv via first order methods

However, it is not clear how to evaluate (5) exactly, as it takes the form of a complicated high dimensional integral. Therefore, we will use Monte Carlo approximations. We sample i.i.d. Gaussians $\delta_{1},\ldots,\delta_{m}\sim\mathcal{N}(0,\sigma^{2}I)$ , and use the plug-in estimator for the expectation:

The equality (a) is known as Stein’s lemma , although we note that something similar can be derived for more general distributions. There is a natural unbiased estimator for (7): sample i.i.d. gaussians $\delta_{1},\ldots,\delta_{m}\sim\mathcal{N}(0,\sigma^{2}I)$ , and form the estimator $\nabla_{x^{\prime}}(G(x^{\prime})_{y})\approx\frac{1}{m}\sum_{i=1}^{m}\frac{\delta_{i}}{\sigma^{2}}\cdot F(x^{\prime}+\delta_{i})_{y}\;.$ This estimator has a number of nice properties. As mentioned previously, it is an unbiased estimator for (7), in contrast to (6). It also requires no computations of the gradient of $F$ ; if $F$ is a neural network, this saves both time and memory by not storing preactivations during the forward pass. Finally, it is very general: the derivation of (7) actually holds even if $F$ is a hard classifier (or more precisely, the one-hot embedding of a hard classifier). In particular, this implies that this technique can even be used to directly find adversarial examples of the smoothed hard classifier.

Despite these appealing features, in practice we find that this attack is quite weak. We speculate that this is because the variance of the gradient estimator is too high. For this reason, in the empirical evaluation we focus on attacks using (6), but we believe that investigating this attack in practice is an interesting direction for future work. See Appendix C.6 for more details.

2 Implementing adversarial training for smoothed classifiers

We incorporate adversarial training into the approach of Cohen et al. changing as few moving parts as possible in order to enable a direct comparison. In particular, we use the same network architectures, batch size, and learning rate schedule. For CIFAR-10, we change the number of epochs, but for ImageNet, we leave it the same. We discuss more of these specifics in Appendix D, and here we describe how to perform adversarial training on a single mini-batch. The algorithm is shown in Pseudocode 1, with the following parameters: $B$ is the mini-batch size, $m$ is the number of noise samples used for gradient estimation in (6) as well as for Gaussian noise data augmentation, and $T$ is the number of steps of an attackNote that we are reusing the same noise samples during every step of our attack as well as during augmentation. Intuitively, this helps to stabilize the attack process..

Experiments

Given a smoothed classifier $g$ , we use the same prediction and certification algorithms, Predict and Certify, as . Both algorithms sample base classifier predictions under Gaussian noise. Predict outputs the majority vote if the vote count passes a binomial hypothesis test, and abstains otherwise. Certify certifies the majority vote is robust if the fraction of such votes is higher by a calculated margin than the fraction of the next most popular votes, and abstains otherwise. For details of these algorithms, we refer the reader to .

Fig. 1(middle) plots our vs ’s best models for varying noise level $\sigma$ . Fig. 1(right) plots a representative model for each $\sigma$ from our adversarially trained models. Observe that we outperform in all three plots.

For ImageNet

We point out, as mentioned by Cohen et al. , that $\sigma$ controls a robustness/accuracy trade-off. When $\sigma$ is low, small radii can be certified with high accuracy, but large radii cannot be certified at all. When $\sigma$ is high, larger radii can be certified, but smaller radii are certified at a lower accuracy. This can be observed in the middle and the right plots of Fig. 1 and 2.

Effect on clean accuracy

Training smoothed classifers using SmoothAdv as shown improves upon the certified accuracy of Cohen et al. for each $\sigma$ , although this comes with the well-known effect of adversarial training in decreasing the standard accuracy, so we sometimes see small drops in the accuracy at $r=0$ , as observed in Fig. 1(right) and 2(right).

Additional experiments and observations

We compare the effectiveness of smoothed classifiers when they are trained SmoothAdv-versarially vs. when their base classifier is trained via standard adversarial training (we will refer to the latter as vanilla adversarial training). As expected, because the training objective of SmoothAdv-models aligns with the actual certification objective, those models achieve noticeably more certified robustness over all radii compared to smoothed classifiers resulting from vanilla adversarial training. We defer the results and details to Appendix C.1.

2 More Data for Better Provable Robustness

We explore using more data to improve the robustness of smoothed classifiers. Specifically, we pursue two ideas: 1) pre-training similar to , and 2) semi-supervised learning as in .

Hendrycks et al. recently showed that using pre-training can improve the adversarial robustness of classifiers, and achieved state-of-the-art results for empirical $l_{\infty}$ defenses on CIFAR-10 and CIFAR-100. We employ this within our framework; we pretrain smoothed classifiers on ImageNet, then fine-tune them on CIFAR-10. Details can be found in Appendix E.1.

Semi-supervised learning

Carmon et al. recently showed that using unlabelled data can improve the adversarial robustness as well. They employ a simple, yet effective, semi-supervised learning technique called self-training to improve the robustness of CIFAR-10 classifiers. We employ this idea in our framework and we train our CIFAR-10 smoothed classifiers via self-training using the unlabelled dataset used in Carmon et al. . Details can be found in Appendix E.2.

We further experiment with combining semi-supervised learning and pre-training, and the details are in Appendix E.3. We observe consistent improvement in the certified robustness of our smoothed models when we employ pre-training or semi-supervision. The results are summarized in Table 2.

3 Attacking trained models with SmoothAdv

Related Work

Recently, many approaches (defenses) have been proposed to build adversarially robust classifiers, and these approaches can be broadly divided into empirical defenses and certified defenses.

Empirical defenses are empirically robust to existing adversarial attacks, and the best empirical defense so far is adversarial training . In this kind of defense, a neural network is trained to minimize the worst-case loss over a neighborhood around the input. Although such defenses seem powerful, nothing guarantees that a more powerful, not yet known, attack would not break them; the most that can be said is that known attacks are unable to find adversarial examples around the data points. In fact, most empirical defenses proposed in the literature were later “broken” by stronger adversaries . To stop this arms race between defenders and attackers, a number of work tried to focus on building certified defenses which enjoy formal robustness guarantees.

Certified defenses are provably robust to a specific class of adversarial perturbation, and can guarantee that for any input $x$ , the classifier’s prediction is constant within a neighborhood of $x$ . These are typically based on certification methods which are either exact (a.k.a “complete”) or conservative (a.k.a “sound but incomplete”). Exact methods, usually based on Satisfiability Modulo Theories solvers or mixed integer linear programming , are guaranteed to find an adversarial example around a datapoint if it exists. Unfortunately, they are computationally inefficient and difficult to scale up to large neural networks. Conservative methods are also guaranteed to detect an adversarial example if exists, but they might mistakenly flag a safe data point as vulnerable to adversarial examples. On the bright side, these methods are more scalable and efficient which makes some of them useful for building certified defenses . However, none of them have yet been shown to scale to practical networks that are large and expressive enough to perform well on ImageNet, for example. To scale up to practical networks, randomized smoothing has been proposed as a probabilistically certified defense.

Conclusions

Acknowledgements

We would like to thank Zico Kolter, Jeremy Cohen, Elan Rosenfeld, Aleksander Madry, Andrew Ilyas, Dimitris Tsipras, Shibani Santurkar, and Jacob Steinhardt for comments and discussions.

References

The smoothed function $\hat{f}$ is known as the Weierstrass transform of $f$ , and a classical property of the Weierstrass transform is its induced smoothness, as demonstrated by the following.

The function $\hat{f}$ is $\sqrt{\frac{2}{\pi}}$ -Lipschitz.

It suffices to prove that for any unit direction $u$ one has $u\cdot\nabla\hat{f}(x)\leq\sqrt{\frac{2}{\pi}}$ . Note that:

and thus (using $|f(t)|\leq 1$ , and classical integration of the Gaussian density)

However, $\hat{f}$ in fact satisfies an even stronger nonlinear smoothness property as shown in the following lemma.

and thus we need to prove that for any unit direction $u$ , denoting $p=\hat{f}(x)$ ,

Note that the left-hand side can be written as follows (recall (8))

For an adversarial $\delta$ , $\hat{f}_{A}(x+\delta)\leq\hat{f}_{B}(x+\delta)$ for some class $c_{B}$ , leading to

By lemma 2 applied to $\hat{f}_{B}$ , and noting that $\hat{f}_{B}(x+\delta)\geq\hat{f}_{B}(x)$ , we know that,

Combining (11) and (12), it is straightforward to see that

Note that both lemmas presented in this appendix give the same robustness guarantee for small gaps ( $p_{A}-p_{B}$ ), but the second lemma is much better for large gaps (in fact, in the limit of a gap going to $1$ , the second lemma gives an infinite radius while the first lemma only gives a radius of $\frac{1}{2}\sqrt{\frac{\pi}{2}}$ ).

Appendix B Another perspective for deriving SmoothAdv

To find an adversarial perturbation of $g$ at data point $(x,y)$ , it is sufficient to find a perturbation $\hat{x}$ so that $g(x)_{y}$ is minimized. Combining this with the approximation (15), we find that a heuristic to find an adversarial example for the smoothed classifier at $(x,y)$ is to solve the following optimization problem:

and as we let $\beta\to\infty$ , this converges to finding an adversarial example for the true smoothed classifier.

To conclude, we simply observe that for neural networks, $\zeta_{\beta}(L(x+\delta))_{y}$ is exactly the soft classifier that is thresholded to form the hard classifier, if $\beta$ is taken to be $1$ . Therefore the solution to ( $\mathcal{S}$ ) and (16) with $\beta=1$ are the same, since $\log$ is a monotonic function.

An interesting direction is to investigate whether varying $\beta$ in (16) allows us to improve our adversarial attacks, and if they do, whether this gives us stronger adversarial training as well. Intuitively, as we take $\beta\to\infty$ , the quality of the optimal solution should increase, but the optimization problem becomes increasingly ill-behaved, and so it is not clear if the actual solution we obtain to this problem via first order methods becomes better or not.

Appendix C Additional Experiments

We compare SmoothAdv-ersarial training (training the smoothed classifier $g$ ) to:

using vanilla adversarial training (PGD) to find adversarial examples of the base classifier $f$ and train on them. We refer to this as Vanilla PGD training.

using vanilla adversarial training (PGD) to find adversarial examples of the base classifier $f$ , add Gaussian noise to them, then train on the resulting inputs. We refer to this as Vanilla PGD+noise training.

For our method and the above two methods, we use $T=2$ steps of attack, $m_{train}=1$ , and we train for $\epsilon\in\{0.25,0.5,1.0,2.0\}$ , and for $\sigma\in\{0.12,0.25,0.5,1.0\}$ .

C.3 Effect of ϵitalic-ϵ\epsilon during training on the certified accuracy of smoothed classifiers

C.5 Effect of the number of Monte Carlo samples n𝑛n in Predict on the empirical accuracies

C.6 Performance of the gradient-free estimator (7)

Despite the appealing features of the gradient-free estimator (7) presented in Section 3.1 as an alternative to (6), in practice we find that this attack is quite weak. This is shown in Fig. 9 for various values of $m_{test}$ .

We speculate that this is because the variance of the gradient estimator is too high. We believe that investigating this attack in practice is an interesting direction for future work.

C.7 Certification Abstention Rate

Note that Cohen et al. reported the abstention rates for prediction (but not certification), which tend to be lower than the certification abstention rates.

Appendix D Experiments Details

Here we include details of all the experiments conducted in this paper.

We emphasize that we are not using PGD and DDN to attack the base classifer $f$ of a smoothed model, instead we are using them to adversarially train smoothed classiers (see Pseudocode 1).

Training details

In order to report certified radii in the original coordinates, we first added Gaussian noise and/or do adversarial attacks, and then standardized the data (in contrast to importing a standardized dataset). Specifically, in our PyTorch implementation, the first layer of the base classifier is a normalization layer that performed a channel-wise standardization of its input.

For both ImageNet and CIFAR-10, we trained the base classifier with random horizontal flips and random crops (in addition to the Gaussian data augmentation discussed in Section 3.2).

The main training algorithm is shown in Pseudocode 1. It has the following parameters: $B$ is the mini-batch size, $m$ is the number of noise samples used for gradient estimation in (6) as well as for Gaussian noise data augmentation, and $T$ is the number of steps of an attack.

First, an important parameter is the radius of the attack $\epsilon$ . During the first epoch, it is set to zero, then we linearly increase it over the first ten epochs, then it stays constant.

Second, we are reusing the same noise samples during every step of our attack as well as augmentation. Intuitively, it helps to stabilize the attack process.

Finally, the way training is described in Pseudocode 1 is not efficient; it needs to be appropriately batched so that we compute adversarial examples for every input in a batch at the same time.

Compute details and training time

On CIFAR-10, we trained using SGD on one NVIDIA P100 GPU. We train for 150 epochs. We use a batch size of 256, and an initial learning rate of 0.1 which drops by a factor of 10 every 50 epochs. Training time varies between few hours to few days, depending on how many attack steps $T$ and noise samples $m$ are used in Pseudocode 1.

On ImageNet we trained with synchronous SGD on four NVIDIA V100 GPUs. We train for 90 epochs. We use a batch size of 400, and an initial learning rate of 0.1 which drops by a factor of 10 every 30 epochs. Training time varies between 2 to 6 days depending on whether we are doing SmoothAdv-ersarial training or just Gaussian noise training (similar to Cohen et al. ).

Models used

The models used in this paper are similar to those used in Cohen et al. : a ResNet-50 on ImageNet, and ResNet-110 on CIFAR-10. These models can be found on the github repo accompanying https://github.com/locuslab/smoothing/blob/master/code/architectures.py.

Parameters of Certify amd Predict

For details of these algorithms, please see the Pseudocode in .

For Certify, unless otherwise specified, we use $n=100,000$ , $n_{0}=100$ , $\alpha=0.001$ .

For Predict, unless otherwise specified, we use $n=100,000$ and $\alpha=0.001$ .

Source code

Our code and trained models are publicly available at http://github.com/Hadisalman/smoothing-adversarial. The repository also includes all our training/certification logs, which enables the replication of all the results of this paper by running a single piece of code. Check the repository for more details.

Appendix E Details for Pre-training and Semi-supervision to Improve the Provable Robustness

In this appendix, we describe the details of how we employ pre-training within our framework to boost the certified robustness of our models. We pretrain smoothed classifiers on a 32x32 down-sampled version of ImageNet (ImageNet32) as done by Hendrycks et al. . Then we fine-tune all the weights of these models on CIFAR-10 (with the 1000-dimensional logit layer of each model replaced by a randomly initialized 10-dimensional logit layer suitable for CIFAR-10).

Fine-tuning on CIFAR-10

E.2 Semi-supervised Learning

In this appendix, we detail how we employ semi-supervised learning within our framework to boost the certified robustness of our models.

We train our CIFAR-10 smoothed classifiers via the self-training technique of using their 500K unlabelled dataset. We equip this dataset with pseudo-labels generated by a standard neural network trained on CIFAR-10, as in ; see for more detailsThe 500K unlabelled dataset was not public at the time this paper was written. We obtained it, along with the pseudo-labels, from the authors of . We refer the reader to the authors of to obtain this dataset if interested in replicating our self-training results. .

Self-training a smoothed classifier works as follows: at every step we randomly sample either a labelled minibatch from CIFAR-10, or a pseudo-labelled minibatch from the 500K dataset:

for a labelled minibatch, we follow Pseudocode 1 as is.

for a pseudo-labelled minibatch, we scale the CE loss by a factor of $\eta\in\{0.1,0.5,1.0\}$ and we follow the rest of Pseudocode 1.