Adversarially Robust Generalization Requires More Data

Introduction

Modern machine learning models achieve high accuracy on a broad range of datasets, yet can easily be misled by small perturbations of their input. While such perturbations are often simple noise to a human or even imperceptible, they cause state-of-the-art models to misclassify their input with high confidence. This phenomenon has first been studied in the context of secure machine learning for spam filters and malware classification . More recently, researchers have demonstrated the phenomenon under the name of adversarial examples in image classification , question answering , voice recognition , and other domains (for instance, see ). Overall, the existence of such adversarial examples raises concerns about the robustness of trained classifiers. As we increasingly deploy machine learning systems in safety- and security-critical environments, it is crucial to understand the robustness properties of our models in more detail.

A growing body of work is exploring this robustness question from the security perspective by proposing attacks (methods for crafting adversarial examples) and defenses (methods for making classifiers robust to such perturbations). Often, the focus is on deep neural networks, e.g., see . While there has been success with robust classifiers on simple datasets , more complicated datasets still exhibit a large gap between “standard” and robust accuracy . An implicit assumption underlying most of this work is that the same training dataset that enables good standard accuracy also suffices to train a robust model. However, it is unclear if this assumption is valid.

So far, the generalization aspects of adversarially robust classification have not been thoroughly investigated. Since adversarial robustness is a learning problem, the statistical perspective is of integral importance. A key observation is that adversarial examples are not at odds with the standard notion of generalization as long as they occupy only a small total measure under the data distribution. So to achieve adversarial robustness, a classifier must generalize in a stronger sense. We currently do not have a good understanding of how such a stronger notion of generalization compares to standard “benign” generalization, i.e., without an adversary.

In this work, we address this gap and explore the statistical foundations of adversarially robust generalization. We focus on sample complexity as a natural starting point since it underlies the core question of when it is possible to learn an adversarially robust classifier. Concretely, we pose the following question:

How does the sample complexity of standard generalization compare to that of adversarially robust generalization?

To study this question, we analyze robust generalization in two distributional models. By focusing on specific distributions, we can establish information-theoretic lower bounds and describe the exact sample complexity requirements for generalization. We find that even for a simple data distribution such as a mixture of two class-conditional Gaussians, the sample complexity of robust generalization is significantly larger than that of standard generalization. Our lower bound holds for any model and learning algorithm. Hence no amount of algorithmic ingenuity is able to overcome this limitation.

To complement our theoretical results, we conduct a range of experiments on MNIST, CIFAR10, and SVHN. By subsampling the datasets at various rates, we study the impact of sample size on adversarial robustness. When plotted as a function of training set size, our results show that the standard accuracy on SVHN indeed plateaus well before the adversarial accuracy reaches its maximum. On MNIST, explicitly adding thresholding to the model during training significantly reduces the sample complexity, similar to our upper bound in the binary data model. On CIFAR10, the situation is more nuanced because there are no known approaches that achieve more than 50% accuracy even against a mild adversary. But as we show in the next subsection, there is clear evidence for overfitting in the current state-of-the-art methods.

via stochastic gradient descent over the model parameters $\theta$. We utilize projected gradient descent for the inner maximization problem over allowed perturbations of magnitude $\varepsilon$ (see for details). Figure 1 displays the training curves for three quantities: (i) adversarial training error, (ii) adversarial test error, and (iii) standard test error.

The results show that on MNIST, robust optimization is able to learn a model with around 90% adversarial accuracy and a relatively small gap between training and test error. However, CIFAR10 offers a different picture. Here, the model (a wide residual network ) is still able to fully fit the training set even against an adversary, but the generalization gap is significantly larger. The model only achieves 47% adversarial test accuracy, which is about 50% lower than its training accuracy.We remark that this accuracy is still currently the best published robust accuracy on CIFAR10 . For instance, contemporary approaches to architecture tuning do not yield better robust accuracies . Moreover, the standard test error is about 87%, so the failure of generalization indeed primarily occurs in the context of adversarial robustness. This failure might be surprising particularly since properly tuned convolutional networks rarely overfit much on standard vision datasets.

2 Outline of the paper

Theoretical Results

Also, our main contribution is a lower bound. So establishing a hardness result for a simple problem means that more complicated distributional setups that can “simulate” the Gaussian model directly inherit the same hardness.

Our first data model is a mixture of two spherical Gaussians with one component per class.

While not explicitly specified in the definition, we will use the Gaussian model in the regime where the norm of the vector $\theta^{\star}$ is approximately $\sqrt{d}$. Hence the main free parameter for controlling the difficulty of the classification task is the variance $\sigma^{2}$, which controls the amount of overlap between the two classes.

To contrast the notions of “standard” and “robust” generalization, we briefly recap a standard definition of classification error.

Next, we define our main quantity of interest, which is an adversarially robust counterpart of the above classification error. Instead of counting misclassifications under the data distribution, we allow a bounded worst-case perturbation before passing the perturbed sample to the classifier.

The Gaussian model has one parameter for controlling the difficulty of learning a good classifier. In order to simplify the following bounds, we study a regime where it is possible to achieve good standard classification error from a single sample.We remark that it is also possible to study a more general setting where standard generalization requires a larger number of samples. As we will see later, this also allows us to calibrate our two data models to have comparable standard sample complexity.

To minimize the number of parameters in our bounds, we have set the error probability to 1%. By tuning the model parameters appropriately, it is possible to achieve a vanishingly small error probability from a single sample (see Corollary 19 in Appendix A.1).

Robust generalization.

Next, we show that this significantly increased sample complexity is necessary. Our main theorem establishes a lower bound for all learning algorithms, which we formalize as functions from data samples to binary classifiers. In particular, the lower bound applies not only to learning linear classifiers.

The proof of the theorem can be found in Corollary 23 (Appendix A.2) and we provide a brief sketch in Section 3. It is worth noting that the classification error $\nicefrac{{1}}{{2}}$ in the lower bound is tight. A classifier that always outputs a fixed prediction trivially achieves perfect robustness on one of the two classes and hence robust accuracy $\nicefrac{{1}}{{2}}$.

Comparing Theorems 5 and 6, we see that the sample complexity $n$ required for robust generalization is bounded as

Finally, we remark that our lower bound applies also to a more restricted adversary. As we outline in Sections 3, the proof uses only a single adversarial perturbation per class. As a result, the lower bound provides transferable adversarial examples and applies to worst-case distribution shifts without a classifier-adaptive adversary. We refer the reader to Section 7 for a more detailed discussion.

2 The Bernoulli model

Let $\theta^{\star}\in\{\pm 1\}^{d}$ be the per-class mean vector and let $\tau>0$ be the class bias parameter. Then the $(\theta^{\star},\tau)$-Bernoulli model is defined by the following distribution over $(x,y)\in\{\pm 1\}^{d}\times\{\pm 1\}$: First, draw a label $y\in\{\pm 1\}$ uniformly at random from its domain. Then sample the data point $x\in\{\pm 1\}^{d}$ by sampling each coordinate $x_{i}$ from the distribution

As in the previous subsection, the model has one parameter for controlling the difficulty of learning. A small value of $\tau$ makes the samples less correlated with their respective class vectors and hence leads to a harder classification problem. Note that both the Gaussian and the Bernoulli model are defined by simple sub-Gaussian distributions. Nevertheless, we will see that they differ significantly in terms of robust sample complexity.

As in the Gaussian model, we first calibrate the distribution so that we can learn a classifier with good standard accuracy from a single sample.To be precise, the two distributions have comparable sample complexity for standard generalization in the regime where $\sigma\approx\tau^{-1}$. The following theorem is a direct consequence of the fact that bounded random variables exhibit sub-Gaussian concentration.

To simplify the bound, we have set the error probability to be 1% as in the Gaussian model. We refer the reader to Corollary 28 in Appendix B.1 for the proof.

Robust generalization.

Next, we investigate the sample complexity of robust generalization in our Bernoulli model. For linear classifiers, a small robust classification error again requires a large number of samples:

In isolation, the thresholding step might seem specific to the Bernoulli model studied here. However, our experiments in Section 5 show that an explicit thresholding layer also significantly improves the sample complexity of training a robust neural network on MNIST. We conjecture that the effectiveness of thresholding is behind many of the successful defenses against adversarial examples on MNIST (for instance, see Appendix C in ).

Lower Bounds for the Gaussian Model

Several remarks are in order. Since we lower bound the expected robust classification error for a distribution over the model parameters $\theta^{\star}$, our result implies a lower bound on the minimax robust classification error (i.e., minimum over learning algorithms, maximum over unknown parameters $\theta^{\star}$). Second, while we refer to the learning procedure as an algorithm, our lower bounds are information theoretic and hold irrespective of the computational power of this procedure.

Moreover, our proof shows that given the $n$ samples, there is a single adversarial perturbation that (a) applies to all learning algorithms, and (b) leads to at least a constant fraction of fresh samples being misclassified. In other words, the same perturbation is transferable across examples as well as across architectures and learning procedures. Hence our simple Gaussian data model already exhibits the transferability phenomenon, which has recently received significant attention in the deep learning literature (e.g., ).

We defer a full proof of the theorem to Section A.2 of the supplementary material. Here, we sketch the main ideas of the proof.

We fix an algorithm $g_{n}$ and let $S_{n}$ denote the set of $n$ samples given to the algorithm. We are interested in the expected robust classification error, which can be formalized as

We swap the two outer expectations so the quantity of interest becomes

Given the samples $S_{n}$, the posterior on $\theta^{*}$ is a Gaussian distribution with parameters defined by simple statistics of $S_{n}$ (the sample mean and the number of samples). Since the new data point $x$ (to be classified) is itself drawn from a Gaussian distribution with mean $\theta^{*}$, the posterior distribution $\mu_{+}$ on the positive examples $x\sim\mathcal{N}(\theta^{*},\sigma^{2})$ is another Gaussian with a certain mean $\bar{z}$ and standard deviation $\sigma^{\prime}$. Similarly, the posterior distribution $\mu_{-}$ on the negative examples is a Gaussian with mean $-\bar{z}$ and the same standard deviation $\sigma^{\prime}$. At a high level, we will now argue that the adversary can make the two posterior distributions $\mu_{-}$ and $\mu_{+}$ similar enough so that the problem becomes inherently noisy, preventing any classifier from achieving a high accuracy.

We now lower bound the inner probabilities by considering the fixed perturbation $\Delta=\overline{z}$. Note that a point $x\sim\mu_{+}$ is certainly misclassified if we have $\lVert\Delta\rVert_{\infty}\leq\varepsilon$ and $x-\Delta\in A_{-}$. Thus the expected misclassification rate is at least $\mu_{+}(\{x\,|\,x-\Delta\in A_{-}\})=\mu_{+}(A_{-}+\Delta)$.For a set $A$ and a vector $v$, we use the notation $A+v$ to denote the set $\{x+v:x\in A\}$. But since $\mu_{+}$ is simply a translated version of $N(0,{\sigma^{\prime}}^{2})$, this implies that

where the distribution $\mu_{0}$ is the centered Gaussian $\mu_{0}=\mathcal{N}(0,{\sigma^{\prime}}^{2})$. Similarly,

Since $\mu_{0}(A_{-})+\mu_{0}(A_{+})=1$, this implies that the adversarial perturbation $-\bar{z}$ misclassifies in expectation half of the positively labeled examples, which completes the proof. As mentioned above, the crucial step is that the posteriors $\mu_{+}$ and $\mu_{-}$ are similar enough so that we can shift both to the origin while still controlling the measure of the sets $A_{-}$ and $A_{+}$.

Lower Bounds for the Bernoulli Model

For the Bernoulli model, our lower bound applies only to linear classifiers. As pointed out in Section 2.2, non-linear classifiers do not suffer an increase in sample complexity in this data model. We now give a high-level overview of our proof that the sample complexity for learning a linear classifier must increase as

The point of start of our proof of the lower bound for linear classifiers is the following observation. For an example $(x,y)$, a linear classifier with parameter vector $w$ robustly classifies the point $x$ if and only if

By the definition of dual norms, the supremum on the right hand size is thus equal to $\varepsilon\lVert yw\rVert_{1}=\varepsilon\lVert w\rVert_{1}$.

The learning algorithm infers the parameter vector $w$ from a limited number of samples. Since these samples are noisy copies of the unknown parameters $\theta^{\star}$, the algorithm cannot be too certain of any single bit in $\theta^{*}$ (recall that we draw $\theta^{*}$ uniformly from the hypercube). We formalize this intuition in Lemma 29 (Appendix B.2) as a bound on the log odds given a sample $S$:

Experiments

We complement our theoretical results by performing experiments on multiple common datasets.

We consider standard convolutional neural networks and train models on datasets of varying complexity. Specifically, we study the MNIST , CIFAR-10 , and SVHN datasets. The latter is particularly well-suited for our analysis since it contains a large number of training images (more than 600,000), allowing us to study adversarially robust generalization in the large dataset regime.

For MNIST, we use the simple convolution architecture obtained from the TensorFlow tutorial . In order to prevent the model from overfitting when trained on small data samples, we regularize the model by adding weight decay with parameter $0.5$ to the training loss. For CIFAR-10, we consider a standard ResNet model . It has 4 groups of residual layers with filter sizes (16, 16, 32, 64) and 5 residual units each. On SVHN, we also trained a network of larger capacity (filter sizes of $(16,64,128,256)$ instead of $(16,16,32,64)$) in order to perform well on the harder problems with larger adversarial perturbations. All of our models achieve close to state-of-the-art performance on the respective benchmark.

Robust optimization.

2 Empirical sample complexity evaluation

We then evaluate the robustness of each trained network to perturbations of varying magnitude ($\varepsilon_{test}$). For each choice of training set size $N$ and fixed attack $\varepsilon_{test}$, we select the best performance achieved across all hyperparameters settings (training perturbations $\varepsilon_{train}$ and model size). On all three datasets, we observed that the best natural accuracy is usually achieved for the naturally trained network, while the best adversarial accuracy for almost all values of $\varepsilon_{test}$ was achieved when training with the largest $\varepsilon_{train}$. We maximize over the hyperparameter settings since we are not interested in the performance of a specific model, but rather in the inherent generalization properties of the dataset independently of the classifier used. The results of these experiments are shown in Figure 2 for each dataset.

The plots clearly demonstrate the need for more data to achieve adversarially robust generalization. For any fixed test set accuracy, the number of samples needed is significantly higher for robust generalization. In the SVHN experiments (where we have sufficient training samples to observe plateauing behavior), the natural accuracy reaches its maximum with significantly fewer samples than the adversarial accuracy. We report more details of our experiments in Section C of the supplementary material.

3 Thresholding experiments

We repeat the sample complexity experiments performed in Section 5.2 with networks where thresholding filters are explicitly encoded in the model. Here, we replace the first convolutional layer with a fixed thresholding layer consisting of two channels, $ReLU(x-\varepsilon_{train})$ and $ReLU(x-(1-\varepsilon_{train}))$, where $x$ is the input image. Results from networks trained with this thresholding layer are shown in Figure 3. For naturally trained networks, we use a value of $\varepsilon=0.1$ for the thresholding filters, whereas for adversarially trained networks we set $\varepsilon=\varepsilon_{train}$. For each data subset size and test perturbation $\varepsilon_{test}$, we plot the best test accuracy achieved over networks trained with different thresholding filters, i.e., different values of $\varepsilon$. We separately show the effect of explicit thresholding in such networks when they are trained naturally or adversarially using PGD. As predicted by our theory, the networks achieve good adversarially robust generalization with significantly fewer samples when thresholding filters are added. Further, note that adding a simple thresholding layer directly yields nearly state-of-the-art robustness against moderately strong adversaries ($\varepsilon=0.1$), without any other modifications to the model architecture or training algorithm. It is also worth noting that the thresholding filters could have been learned by the original network architecture, and that this modification only decreases the capacity of the model. Our findings emphasize network architecture as a crucial factor for learning adversarially robust networks from a limited number of samples.

We also experimented with thresholding filters on the CIFAR10 dataset, but did not observe any significant difference from the standard architecture. This agrees with our theoretical understanding that thresholding helps primarily in the case of (approximately) binary datasets.

Related Work

Due to the large body of work on adversarial robustness, we focus on related papers that also provide theoretical explanations for adversarial examples. Compared to prior work, the main difference of our approach is the focus on generalization. Most related papers study robustness either without the learning context, or in the limit as the number of samples approaches infinity. As a result, finite sample phenomena do not arise in these theoretical approaches. As we have seen in Figure 1, adversarial examples are currently a failure of generalization from a limited training set. Hence we believe that studying robust generalization is an insightful avenue for understanding adversarial examples.

study the adversarial robustness of nearest neighbor classifiers. In contrast to our work, the authors give theoretical guarantees for a specific classification algorithm. We focus on the inherent sample complexity of adversarially robust generalization independently of the learning method. Moreover, our results hold for finite sample sizes while the results in are only asymptotic.

Recent work by explores a specific distribution where robust learning is empirically difficult with overparametrized neural networks.It is worth noting that the distribution in has only one degree of freedom. Hence we conjecture that the observed difficulty of robust learning in their setup is due to the chosen model class and not due to an information-theoretic limit as in our work. The main phenomenon is that even a small natural error rate on their dataset translates to a large adversarial error rate. Our results give a more nuanced picture that involves the sample complexity required for generalization. In our data models, it is possible to achieve an error rate that is essentially zero by using a very small number of samples, whereas the adversarial error rate is still large unless we have seen a lot of samples.

relate the robustness of linear and non-linear classifiers to adversarial and (semi-)random perturbations. Their work studies the setting where the classifier is fixed and does not encompass the learning task. We focus on generalization aspects of adversarial robustness and provide upper and lower bounds on the sample complexity. Overall, we argue that adversarial examples are inherent to the statistical setup and not necessarily a consequence of a concrete classifier model.

The work of establishes a connection between robust optimization and regularization for linear classification. In particular, they show that robustness to a specific perturbation set is exactly equivalent to the standard support vector machine. The authors give asymptotic consistency results under a robustness condition, but do not provide any finite sample guarantees. In contrast, our work considers specific distributional models where we can demonstrate a clear gap between robust and standard generalization.

discuss adversarial robustness at the population level. They assume the existence of an adversary that can significantly increase the loss for any hypothesis in the hypothesis class. By definition, robustness against adversarial perturbations is impossible in this regime. As demonstrated in Figure 1, we instead conjecture that current classification models are not robust to adversarial examples because they fail to generalize. Hence our results concern generalization from a finite number of samples. We show that even when the hypothesis class is large enough to achieve good robust classification error, the sample complexity of robust generalization can still be significantly bigger than that of standard generalization.

In a recent paper, also give provable lower bounds for adversarial robustness. There are several important differences between their work and ours. At a high level, the results in state that there are fundamental limits for adversarial robustness that apply to any classifier. As pointed out by the authors, their bounds also apply to the human visual system. However, an important aspect of adversarial examples is that they often fool current classifiers, yet are still easy to recognize for humans. Hence we believe that the approach in does not capture the underlying phenomenon since it does not distinguish between the robustness of current artificial classifiers and the human visual system.

Moreover, the lower bounds in do not involve the training data and consequently apply in the limit where an infinite number of samples is available. In contrast, our work investigates how the amount of available training data affects adversarial robustness. As we have seen in Figure 1, adversarial robustness is currently an issue of generalization. In particular, we can train classifiers that achieve a high level of robustness on the CIFAR10 training set, but this robustness does not transfer to the test set. Therefore, our perspective based on adversarially robust generalization more accurately reflects the current challenges in training robust classifiers.

Finally, utilize the notion of a latent space for the data distribution in order to establish lower bounds that apply to any classifier. While the existence of generative models such as GANs provides empirical evidence for this assumption, we note that it does not suffice to accurately describe the robustness phenomenon. For instance, there are multiple generative models that produce high-quality samples for the MNIST dataset, yet there are now also several successful defenses against adversarial examples on MNIST. As we have shown in our work, the fine-grained properties of the data distribution can have significant impact on how hard it is to learn a robust classifier.

where $n$ is the number of samples. To illustrate this bound, consider the Gaussian model in the regime $\sigma=\Theta(d^{\nicefrac{{1}}{{4}}})$ where a single sample suffices to learn a classifier with low error (see Theorem 4). The standard bound on the norm of an i.i.d. Gaussian vector shows that we have a data norm bound $\rho=\Theta(d^{\nicefrac{{3}}{{4}}})$ with high probability. While the Gaussian model is not strictly separable in any regime, we can still consider the probability that a sample achieves at least a certain margin:

A simple calculation shows that for $\lVert\theta^{\star}\rVert_{2}=\sqrt{d}$ (as in our earlier bounds), the Gaussian model does not achieve margin $\gamma\geq\sqrt{d}$ even at the quantile $\delta=\nicefrac{{1}}{{2}}$. Hence the margin-based bound would indicate a sample complexity of $\Omega(d^{\nicefrac{{1}}{{4}}})$ already for standard generalization, which obscures the dichotomy between standard and robust sample complexity.

Robust statistics.

An orthogonal line of work in robust statistics studies robustness of estimators to corruption of training data . This notion of robustness, while also important, is not directly relevant to the questions addressed in our work.

Discussion and Future Directions

The vulnerability of neural networks to adversarial perturbations has recently been a source of much discussion and is still poorly understood. Different works have argued that this vulnerability stems from their discontinuous nature , their linear nature , or is a result of high-dimensional geometry and independent of the model class . Our work gives a more nuanced picture. We show that for a natural data distribution (the Gaussian model), the model class we train does not matter and a standard linear classifier achieves optimal robustness. However, robustness also strongly depends on properties of the underlying data distribution. For other data models (such as MNIST or the Bernoulli model), our results demonstrate that non-linearities are indispensable to learn from few samples. This dichotomy provides evidence that defenses against adversarial examples need to be tailored to the specific dataset and hence may be more complicated than a single, broad approach. Understanding the interactions between robustness, classifier model, and data distribution from the perspective of generalization is an important direction for future work.

The focus of our paper is on adversarial perturbations in a setting where the test distribution (before the adversary’s action) is the same as the training distribution. While this is a natural scenario from a security point of view, other setups can be more relevant in different robustness contexts. For instance, we may want a classifier that is robust to small changes between the training and test distribution. This can be formalized as the classification accuracy on unperturbed examples coming from an adversarially modified distribution. Here, the power of the adversary is limited by how much the test distribution can be modified, and the adversary is not allowed to perturb individual samples coming from the modified test distribution. Interestingly, our lower bound for the Gaussian model also applies to such worst-case distributional shifts. In particular, if the adversary is allowed to shift the mean $\theta^{\star}$ by a vector in $\mathcal{B}_{\infty}^{\varepsilon}$, our proof sketched in Section 3 transfers to the distribution shift setting. Since the lower bound relies only on a single universal perturbation, this perturbation can also be applied directly to the mean vector.

Several questions remain. We now provide a list of concrete directions for future work on robust generalization.

An interesting aspect of adversarial examples is that the adversary can often fool the classifier on most inputs . While our results show a lower bound for classification error $\nicefrac{{1}}{{2}}$, it is conceivable that misclassification rates much closer to 1 are unavoidable for at least one of the two classes (or equivalently, when the adversary is allowed to pick the class label). In order to avoid degenerate cases such as achieving robustness by being the constant classifier, it would be interesting to study regimes where the classifier has high standard accuracy but does not achieve robustness yet. In such a regime, does good standard accuracy imply that the classifier is vulnerable to adversarial perturbations on almost all inputs?

As mentioned above, less adversarial forms of robustness may be better suited to model challenges arising outside security. How much easier is it to learn a robust classifier in more benign settings? This question is naturally related to problems such as transfer learning and domain adaptation.

Our results directly apply to two concrete distributional models. While the results already show interesting phenomena and are predictive of behavior on real data, understanding the robustness properties for a broader class of distributions is an important direction for future work. Moreover, it would be useful to understand what general properties of distributions make robust generalization hard or easy.

In our work, we show a separation of $\sqrt{d}$ between the standard and robust sample complexity for the Gaussian model. It is open whether larger gaps are possible. Note that for large adversarial perturbations, the data may no longer be robustly separable which leads to trivial gaps in sample complexity, simply because the harder robust generalization problem is impossible to solve. Hence this question is mainly interesting in the regime where a robust classifier exists in the model class of interest.

Our focus has been on robust learning for specific distributions without any limitations on the hypothesis class. A natural dual perspective is to investigate robust learning for specific hypothesis classes, as in the probably approximately correct (PAC) framework. For instance, it is well known that the sample complexity of learning a half space in $d$ dimensions is $O(d)$. Does this sample complexity also suffice to learn in the presence of an adversary at test time? While robustness to adversarial training noise has been studied in the PAC setting (e.g., see ), we are not aware of similar work on test time robustness.

Acknowledgements

Ludwig Schmidt is supported by a Google PhD Fellowship. During this research project, Ludwig was also a research fellow at the Simons Institute for the Theory of Computing, an intern in the Google Brain team, and a visitor at UC Berkeley. Shibani Santurkar is supported by the National Science Foundation (NSF) under grants IIS-1447786, IIS-1607189, and CCF-1563880, and the Intel Corporation. Dimitris Tsipras was supported in part by the NSF grant CCF-1553428. Aleksander Mądry was supported in part by an Alfred P. Sloan Research Fellowship, a Google Research Award, and the NSF grant CCF-1553428.

References

Appendix A Omitted proofs for the Gaussian model

We begin with standard results about (sub)-Gaussian concentration in Fact 12 and Lemmas 13 to 16. These results show that a class-weighted average of sufficiently many samples from the Gaussian model achieves a large inner product with the unknown mean vector. Lemma 17 then relates the inner product between a linear classifier and the mean vector to the classification accuracy. Theorem 18 uses the lemmas to establish our main theorem for standard generalization. Corollary 19 instantiates the bound for learning from one sample. After further simplification, this yields Theorem 4 from the main text.

For robust generalization, we first relate the inner product between a linear classifier and the unknown mean vector to the robust classification accuracy in Lemma 20. Similar to the standard classification error, Theorem 21 and Corollary 22 then yield our upper bounds for robust generalization. Simplifying Corollary 22 further gives Theorem 5 from the main text.

Since each $z_{i}$ has the same distribution as $\mu+g_{i}$ for $g_{i}\sim\mathcal{N}_{d}(0,\sigma^{2}I)$, we can bound the desired tail probability for

Morever, the average of the $g_{i}$ has the same distribution as $\overline{g}\sim\mathcal{N}_{d}(0,\frac{\sigma^{2}}{n}I)$. Hence it suffices to bound the tail of $\lVert\mu+\overline{g}\rVert_{2}$. For any $c\geq 0$, applying the triangle inequality then gives

Setting $c=\sigma\sqrt{\nicefrac{{d}}{{n}}}+t$ with

and substituting into Fact 12 then gives the desired result. ∎

For convenient use in our later theorems, we instantiate Lemma 13 with the parameters most relevant for our Gaussian model. In particular, the norm of the mean vector $\mu$ is $\sqrt{d}$ and we are interested in up to exponentially small failure probability $\delta$ (but not necessarily smaller).

We substitute into Lemma 13 with $\lVert\mu\rVert_{2}=\sqrt{d}$ and $\sqrt{2\log\nicefrac{{1}}{{\delta}}}=\sqrt{d}$. ∎

As in Lemma 13, we use the fact that $\overline{z}$ has the same distribution as $\mu+\overline{g}$ where $\overline{g}\sim\mathcal{N}_{d}(0,\frac{\sigma^{2}}{n}I)$. For any $t\geq 0$, this allows us to simplify the tail event to

and substituting $t\;=\;\sigma\lVert\mu\rVert_{2}\sqrt{\frac{2\log\nicefrac{{1}}{{\delta}}}{n}}$ then gives the desired result. ∎

with probability $1-e^{\nicefrac{{-d}}{{2}}}$. Moreover, we invoke Lemma 15 with $\delta=e^{\nicefrac{{-d}}{{8\sigma^{2}}}}$ and $\lVert\mu\rVert_{2}=\sqrt{d}$ to get

with probability $1-e^{\nicefrac{{-d}}{{8\sigma^{2}}}}$. We continue under both events, which yields the desired overall failure probability $2e^{\nicefrac{{-d}}{{2}}}$.

Since $z$ has the same distribution as $\mu+g$ where $g\sim\mathcal{N}_{d}(0,\sigma^{2}I)$, we can bound the tail event as

The inner product $\langle w,g\rangle$ is distributed as a univariate normal $\mathcal{N}(0,\sigma^{2})$ because the vector $w$ has unit norm. Hence we can invoke the standard sub-Gaussian tail bound to get the desired tail probability. ∎

Let $z_{i}=y_{i}\cdot x_{i}$ and note that each $z_{i}$ is independent and has distribution $\mathcal{N}_{d}(\theta^{\star},\sigma^{2}I)$. Hence we can invoke Lemma 16 and get

with probability at least $1-2\exp(-\frac{d}{8(\sigma^{2}+1)})$ as stated in the theorem.

Next, unwrapping the definition of $f_{\widehat{w}}$ allows us to write the classification error of $f_{\widehat{w}}$ as

Invoking Lemma 17 with $\rho=0$ then gives the desired bound. ∎

Let $(x,y)$ be drawn from a $(\theta^{\star},\sigma)$-Gaussian model with

Invoking Theorem 18 with $n=1$ gives a classification error bound of

It remains to show that $\beta^{\prime}\leq\beta$.

We now bound the denominator in $\beta^{\prime}$. First, we have

which yields the desired classification error when substituted back into $\beta^{\prime}$. ∎

Per Definition 3, we have to upper bound the quantity

For linear classifiers, we can rewrite this event as follows:

We now use the definition of the dual norm. Note that for any $\Delta\in\mathcal{B}_{p}^{\varepsilon}$, we also have $-\Delta\in\mathcal{B}_{p}^{\varepsilon}$. Since $y\in\{\pm 1\}$, we can drop the $y$ factor. Overall, we get

By assumption in the lemma, we have $\langle\widehat{w},\theta^{\star}\rangle\geq\varepsilon\lVert\widehat{w}\rVert_{p}^{*}$. Hence we can invoke Lemma 17 with $\mu=\theta^{\star}$ and $\rho=\varepsilon\lVert\widehat{w}\rVert_{p}^{*}$ to get the desired bound on the robust classification error. ∎

Let $z_{i}=y_{i}\cdot x_{i}$ and note that each $z_{i}$ is independent and has distribution $\mathcal{N}_{d}(\theta^{\star},\sigma^{2}I)$. Hence we can invoke Lemma 16 and get

with probability at least $1-2\exp(-\frac{d}{8(\sigma^{2}+1)})$ as stated in the theorem.

this simplifies to the robust classification error stated in the theorem. ∎

First, we consider the case where $\varepsilon\leq\frac{1}{4}d^{-\nicefrac{{1}}{{4}}}$. Using $n=1$, the resulting robustness is

Next, we consider the case $\frac{1}{4}d^{-\nicefrac{{1}}{{4}}}\,\leq\,\varepsilon\,\leq\,\frac{1}{4}$. Substituting $n=64\varepsilon^{2}\sqrt{d}$, we get

A.2 Lower bound

The following theorem is our main lower bound for the Gaussian model. To make the lower bound easily comparable to Corollary 22 on the upper bound side, we simplify the lower bound in Corollary 23 and bring it into a similar form.

where it is important to note that $f_{n}=g_{n}((x_{1},y_{1}),\ldots,(x_{n},y_{n}))$ depends on the samples $(x_{i},y_{i})$ but not on $\theta$. This will allow us to re-arrange the above expectations in a crucial way.

We first rewrite the expectations by noting that we can sample $z_{i}\sim\mathcal{N}(\theta,\sigma^{2}I)$ without conditioning on the class $y_{i}$ by then setting $f_{n}=g_{n}((y_{1}z_{1},y_{1}),\ldots,(y_{n}z_{n},y_{n}))$. This yields

where in the second line we moved the expectation over the class labels to the outside.

Next, we will swap the order of the expectations over the mean parameter $\theta$ and the conditional samples $x_{i}$. Since the posterior distribution for a Gaussian prior and likelihood is also Gaussian, the conditional distribution of $\theta$ given the $z_{i}$ is a multivariate Gaussian with parameters

where $\overline{z}=\sum_{i=1}^{n}z_{i}$. Moreover, let $\mathcal{M}$ be the marginal distribution over $(z_{i},\ldots,z_{n})$ after integrating over $\theta$ (which we will analyze later). Then we get

We now bound the term $\Psi$. Since the inner events only depends on $\theta$ through $x$, we can combine the Gaussian expectation with the Gaussian probability after moving the expectation over the label $y$ to the outside. This gives

where $\Sigma^{\prime\prime}=\Sigma^{\prime}+\sigma^{2}I$.

Now, note that as long as $\lVert\mu^{\prime}\rVert_{\infty}\leq\varepsilon$, the set $\mathcal{B}_{\infty}^{\varepsilon}(A_{-})$ contains a copy of $A_{-}$ shifted by $\pm\mu^{\prime}$. Hence we have

Repeating the same argument for the $y=-1$ case and substituting back into Equation (3) yields

In the last line, we used that the sets two sets $A_{-}$ and $A_{+}$ are complements of each other and hence their total mass under the measure $\mathcal{N}(0,\Sigma^{\prime\prime})$ is 1.

Substituting back into Equation (2) yields

where we dropped the expectation over the labels $y_{i}$ since the inner expression is now independent of the labels.

It remains to analyze the distribution of the vector $\overline{z}$. Note that conditioned on a vector $\theta_{2}\sim\mathcal{N}_{d}(0,I)$, the distribution of each $z_{i}$ is $\mathcal{N}(\theta_{2},\sigma^{2}I)$. Hence the conditional distribution of $\overline{z}$ given $\theta_{2}$ is $\mathcal{N}(\theta_{2},\frac{\sigma^{2}}{n}I)$ and integrating over $\theta_{2}$ yields a marginal distribution of $\mathcal{N}(0,(1+\frac{\sigma^{2}}{n})I)$. Overall, this gives

Rearranging this inequality yields the statement of the theorem. ∎

Standard concentration results for the maximum of $d$ i.i.d. Gaussians (e.g., see Theorem 5.8 in ) now imply that the above probability is at least $(1-\nicefrac{{1}}{{d}})$. Invoking into Theorem 11 then completes the proof of this corollary. ∎

Appendix B Omitted proofs for the Bernoulli model

As in the Gaussian case, our upper bounds rely on standard sub-Gaussian concentration. Lemmas 24 and 25 provide lower bounds on the inner product between a single sample from the Bernoulli model and the unknown parameter vectors. Lemma 26 then relates the inner product between a linear classifier and the unknown mean vector to the classification accuracy. Combining these results yields Theorem 27 for generalization from a single sample. Simplifying this theorem yields Corollary 28, which directly implies Theorem 8 from the main text.

Note that $g=(g_{1},g_{2},...,g_{d})$ is a vector of sub-Gaussian random variables since each entry is bounded, i.e., each $g_{j}$ (like $z_{j}$) lies in an interval of length $2$. Hence, the sub-Gaussian parameter of each $g_{j}$ is 1. Invoking Corollary 1.7 from for the weighted combination of independent sub-Gaussian random variables, we get that

Since $\lVert\theta^{\star}\rVert_{2}^{2}=d$, we can simplify the tail event

Moreover, we invoke Lemma 24 with $\delta=\exp\lparen-\frac{\tau^{2}d}{2}\rparen$ to get

with probability $\delta$ as stated in the lemma. ∎

As in Lemma 24, we center $z=2\tau\theta^{\star}+g$, where $g$ is a vector of zero-mean sub-Gaussian random variables. We can bound the tail event as

We know that the sub-Gaussian parameter of each $g_{j}$ is 1 as discussed in Lemma 24. Hence, invoking Corollary 1.7 from for the weighted combination of independent sub-gaussian random variables, we get that

with probability at least $1-\exp(-\frac{\tau^{2}d}{2})$ as stated in the theorem. Next, unwrapping the definition of $f_{\widehat{w}}$ allows us to write the classification error of $f_{\widehat{w}}$ as

Invoking Lemma 26 then gives the desired bound. ∎

Invoking Theorem 27 gives a classification error bound of

It remains to show that $\beta^{\prime}\leq\beta$. Now,

B.2 Lower bounds

In this section, we show that any linear classifier for the $(\theta^{*},\tau)$-Bernoulli model requires many samples to be robust. The main result is formalized in Theorem 31, which can be simplified to yield Theorem 9 from the main text. Before we proceed to the main theorem, we first prove a simple but useful lemma.

Let $\theta$ be drawn uniformly at random from $\{-1,1\}$ and let $(x_{1},y_{1}),\ldots,(x_{n},y_{n})$ be drawn independently from the $(\theta,\tau)$-Bernoulli model. Then for $\tau\leq\nicefrac{{1}}{{4}}$ and $n\leq\frac{1}{\tau^{2}}$, we have with probability $1-\delta$ over the samples that

For any sequence $(x_{1},y_{1})\ldots,(x_{n},y_{n})$, we can write

because $\Pr[\theta=+1]=\Pr[\theta=-1]$. We now simplify the right hand side to

where the second line follows from a simple calculation of the conditional probabilities.

Writing $z_{i}=y_{i}x_{i}$, we next combine Equations (4) and (5) to

where $\hat{\tau}$ is such that $\exp(\hat{\tau})=\frac{1+2\tau}{1-2\tau}$. For $\tau\leq\frac{1}{4}$, a simple calculation shows that $\hat{\tau}\leq 5\tau$.

Conditioned on $\theta$, the sum $\overline{z}=\sum_{i=1}^{n}z_{i}$ has expectation $2\tau n\theta\leq 2\tau n$. Hoeffing’s Inequality (e.g., see Theorem 2.8 in ) then yields that with probability $1-\nicefrac{{\delta}}{{2}}$

It follows that with probability $1-\nicefrac{{\delta}}{{2}}$ (taken over the samples $z_{1},\ldots,z_{n}$), the likelihood ratio above is bounded by

Under the assumptions that $n\leq\frac{1}{\tau^{2}}$, we have

and the upper bound follows because the first term in the $\exp$ is at most twice the second term. The lower bound is symmetric. ∎

Let $\theta^{\star}\in\{-1,+1\}^{d}$ and consider the linear classifier $f_{\theta^{\star}}$ for the $(\theta^{\star},\tau)$-Bernoulli model. Then,

Let $(x,y)$ be drawn from the $(\theta^{\star},\tau)$-Bernoulli model. Then for the linear classifier $w=\theta^{\star}$, we have

Hoeffing’s Inequality (e.g., see Theorem 2.8 in ) then gives

On the other hand, for a parameter $\varepsilon$,

Thus if $\varepsilon<\tau$, then for any $(x,y)\in S$,

Finally, let $w^{\prime}$ be any other linear classifier. Then we have

Let $E_{i}$ be a $\pm 1$ random variable with expectation $2\tau$. We observe that the random variable $yx_{i}w^{\prime}_{i}$ is stochastically dominated by $E_{i}\cdot\lvert w^{\prime}_{i}\rvert$ (note that $yx_{i}$ is itself a $\pm 1$ random variable with expectation $2\tau$). We can now write $E_{i}$ as

where the random variable $A_{i}$ is in $\{0,1\}$ and has expectation $2\tau$. The random variable $B_{i}$ is in $\{-1,0,1\}$ and has a symmetric distribution that depends on $A$. In particular, $B_{i}=0$ iff $A_{i}=1$ and $B_{i}$ is a Rademacher random variable otherwise. Since $A_{i}$ is non-negative, we can use Markov’s inequality on $\sum_{i}\lvert w_{i}\rvert A_{i}$. The $B_{i}$’s have a symmetric distribution even conditioned on $A_{i}$ so that $\sum_{i}\lvert w^{\prime}_{i}\rvert B_{i}\leq 0$ with probability at least $\nicefrac{{1}}{{2}}$. Thus with probability at least $\nicefrac{{1}}{{6}}$, we have

Lemma 30 implies that the most interesting robustness regime for linear classifiers is $\varepsilon=O(\tau)$. For larger values of $\varepsilon$, it is impossible to learn a linear classifier with small robust classification error regardless of the number of samples used.

Next, we bound the ratio of probabilities by invoking Lemma 29 (note that we have $\tau\leq\nicefrac{{1}}{{4}}$ and $n\leq\nicefrac{{1}}{{\tau^{2}}}$ as required). With probability $(1-\frac{\gamma}{2})$, $S$ is such that for all $i\in[d]$ we have

Substituting this into Equation (6) then yields

where we used the inequality $e^{x}-1\leq 2x$ for $0\leq x\leq 1$ (note that the upper bound on $n$ in the theorem implies that the argument to the exponential function is in this range).

Combining the bound above with the analogous lower bound gives

We condition on such an $S$ for the rest of this proof.

The second part of the proof will bound the classification margin the linear classifier $w$ achieves on a fresh sample $x$. Incorporating the class label $y$, this margin is the quantity $y\langle w,x\rangle$. From the first part of the proof, it follows that

To simplify the following calculation, we introduce the shorthand $a_{n}=30\tau^{2}\sqrt{2n\log(4d/\gamma)}$. Next, we provide a tail bound on $\langle w,yx\rangle$. Similar to Lemma 30, we observe that the random variable $yx_{i}w_{i}$ is stochastically dominated by $E_{i}\cdot\lvert w_{i}\rvert$ where $E_{i}$ is a $\pm 1$ random variable with expectation $a_{n}$. We can again write $E_{i}$ as

where the random variable $A_{i}$ is in $\{0,1\}$ and has expectation $a_{n}$. The random variable $B_{i}$ is in $\{-1,0,1\}$ and has a symmetric distribution that depends on $A$. In particular, $B_{i}=0$ iff $A_{i}=1$ and $B_{i}$ is a Rademacher random variable otherwise. Since $A_{i}$ is non-negative, we can use Markov’s inequality on $\sum_{i}\lvert w_{i}\rvert A_{i}$. The $B_{i}$’s have a symmetric distribution even conditioned on $A_{i}$ so that $\sum_{i}\lvert w_{i}\rvert B_{i}\leq 0$ with probability at least $\nicefrac{{1}}{{2}}$. Thus with probability at least $\frac{1-\gamma}{2}$, we have

Using the upper bound on $n$ from the theorem statement, we have

By duality, the minimum value is exactly $\varepsilon\lVert w\rVert_{1}$. Hence conditioned on the samples $S$ and the bound on $\langle w,yx\rangle$, the adversarially perturbed point $x+e$ is mis-classified because

The overall probability of this event occuring is at least $1-\frac{\gamma}{2}$ (conditioning on $S$) times $\frac{1-\gamma}{2}$ (bound on $\langle w,x\rangle$). Since

Appendix C Omitted Figures