Adversarial vulnerability for any classifier

Introduction

Deep neural networks are powerful models that achieve state-of-the-art performance across several domains, such as bioinformatics bio2; bio1, speech sp2, and computer vision he2015deep; cv2. Though deep networks have exhibited very good performance in classification tasks, they have recently been shown to be unstable to adversarial perturbations of the data szegedy2013intriguing; biggio2013evasion. In fact, very small and often imperceptible perturbations of the data samples are sufficient to fool state-of-the-art classifiers and result in incorrect classification. This discovery of the surprising vulnerability of classifiers to perturbations has led to a large body of work that attempts to design robust classifiers goodfellow2014; shaham2015understanding; madry2017towards; cisse2017parseval; papernot2015distillation; alemi2016deep. However, advances in designing robust classifiers have been accompanied with stronger perturbation schemes that defeat such defenses carlini2017adversarial; uesato2018adversarial; robust_vision.

In this paper, we assume that the data distribution is defined by a smooth generative model (mapping latent representations to images), and study theoretically the existence of small adversarial perturbations for arbitrary classifiers. We summarize our main contributions as follows:

We show fundamental upper bounds on the robustness of any classifier to perturbations, which provides a baseline to the maximal achievable robustness. When the latent space of the data distribution is high dimensional, our analysis shows that any classifier is vulnerable to very small perturbations. Our results further suggest the existence of a tight relation between robustness and linearity of the classifier in the latent space.

We prove the existence of adversarial perturbations that transfer across different classifiers. This provides theoretical justification to previous empirical findings that highlighted the existence of such transferable perturbations.

We evaluate our bounds in several experimental setups (CIFAR-10 and SVHN), and show that they yield informative baselines to the maximal achievable robustness.

Related work

It was proven in fawzi2015a; nips2016_ours that for certain families of classifiers, there exist adversarial perturbations that cause misclassification of magnitude $O(1/\sqrt{d})$, where $d$ is the data dimension, provided the robustness to random noise is fixed (which is typically the case if e.g., the data is normalized). In addition, fundamental limits on the robustness of classifiers were derived in fawzi2015a for some simple classification families. Other works have instead studied the existence of adversarial perturbations, under strong assumptions on the data distribution gilmer2018adversarial; tanay2016boundary. In this work, motivated by the success of generative models mapping latent representations with a normal prior, we instead study the existence of robust classifiers under this general data-generating procedure and derive bounds on the robustness that hold for any classification function. A large number of techniques have recently been proposed to improve the robustness of classifiers to perturbations, such as adversarial training goodfellow2014, robust optimization shaham2015understanding; madry2017towards, regularization cisse2017parseval, distillation papernot2015distillation, stochastic networks alemi2016deep, etc… Unfortunately, such techniques have been shown to fail whenever a more complex attack strategy is used carlini2017adversarial; uesato2018adversarial, or when it is evaluated on a more complex dataset. Other works have recently studied procedures and algorithms to provably guarantee a certain level of robustness hein2017formal; peck2017lower; sinha2017certifiable; raghunathan2018certified; dvijotham2018dual, and have been applied to small datasets (e.g., MNIST). For large scale, high dimensional datasets, the problem of designing robust classifiers is entirely open. We finally note that adversarial examples for generative models have recently been considered in kos2017adversarial; our aim here is however different as our goal is to bound the robustness of classifiers when data comes from a generative model.

Definitions and notations

The goal of this paper is to study the robustness of $f$ to additive perturbations under the assumption that the data is generated according to $g$. We define two notions of robustness. These effectively measure the minimum distance one has to travel in image space to change the classification decision.

In-distribution robustness: For $x=g(z)$, we define the in-distribution robustness $r_{\text{in}}(x)$ as follows:

where $\|\cdot\|$ denotes an arbitrary norm on $\mathcal{X}$. Note that the perturbed image, $g(z+r)$ is constrained to lie in the image of $g$, and hence belongs to the support of the distribution $\mu$.

Unconstrained robustness: Unlike the in-distribution setting, we measure here the robustness to arbitrary perturbations in the image space; that is, the perturbed image is not constrained anymore to belong to the data distribution $\mu$.

This notion of robustness corresponds to the widely used definition of adversarial perturbations. It is easy to see that this robustness definition is smaller than the in-distribution robustness; i.e., $r_{\text{unc}}(x)\leq r_{\text{in}}(x)$.

In this paper, we assume that the generative model is smooth, in the sense that it satisfies a modulus of continuity property, defined as follows:

We assume that $g$ admits a monotone invertible modulus of continuity $\omega$; i.e., This assumption can be extended to random $z$ (see C.2 in the appendix). For ease of exposition however, we use here the deterministic assumption.

Note that the above assumption is milder than assuming Lipschitz continuity. In fact, the Lipschitz property corresponds to choosing $\omega(t)$ to be a linear function of $t$. In particular, the above assumption does not require that $\omega(0)=0$, which potentially allows us to model distributions with disconnected support. In this paper, we use the term smooth generative models to denote that the function $\omega(\delta)$ takes small values for small $\delta$.

It should be noted that generator smoothness is a desirable property of generative models. This property is often illustrated empirically by generating images along a straight path in the latent space radford2015unsupervised, and verifying that the images undergo gradual semantic changes between the two endpoints. In fact, smooth transitions is often used as a qualitative evidence that the generator has learned relevant factors of variation.

Fig. 1 summarizes the problem setting and notations. Assuming that the data is generated according to $g$, we analyze in the remainder of the paper the robustness of arbitrary classifiers to perturbations.

Analysis of the robustness to perturbations

We state a general bound on the robustness to perturbations and derive two special cases to make more explicit the dependence on the distribution and number of classes.

This theorem is a consequence of the Gaussian isoperimetric inequality first proved in borell1975brunn and sudakov1978extremal. The proofs can be found in the appendix.

Remark 2. Dependence on $K$. Theorem 1 shows an increasing probability of misclassification with the number of classes $K$. In other words, it is easier to find adversarial perturbations in the setting where the number of classes is large, than for a binary classification task. We assume here equiprobable classes. This dependence confirms empirical results whereby the robustness is observed to decrease with the number of classes. The dependence on $K$ captured in our bounds is in contrast to previous bounds that showed decreasing probability of fooling the classifier, for larger number of classes nips2016_ours.

Remark 3. Classification-agnostic bound. Our bounds hold for any classification function $f$, and are not specific to a family of classifiers. This is unlike the work of fawzi2015a that establishes bounds on the robustness for specific classes of functions (e.g., linear or quadratic classifiers).

Remark 4. How tight is the upper bound on robustness in Theorem 1? Assuming that the smoothness assumption in Eq. 1 is an equality, let the classifier $f$ be such that $f\circ g$ separates the latent space into $B_{1}=g^{-1}(C_{1})=\{z:z_{1}\geq 0\}$ and $B_{2}=g^{-1}(C_{2})=\{z:z_{1}<0\}$. Then, it follows that

which precisely corresponds to Eq. (2). In this case, the bound in Eq. (2) is therefore an equality. More generally, this bound is an equality if the classifier induces linearly separable regions in the latent space. In the case where Eq. (1) is an inequality, we will not exactly achieve the bound, but get closer to it when $f\circ g$ is linear. This suggests that classifiers are maximally robust when the induced classification boundaries in the latent space are linear. We stress on the fact that boundaries in the $\mathcal{Z}$-space can be very different from the boundaries in the image space. In particular, as $g$ is in general non-linear, $f$ might be a highly non-linear function of the input space, while $z\mapsto(f\circ g)(z)$ is a linear function in $z$. We provide an explicit example in the appendix illustrating this remark.

Remark 5. Adversarial perturbations in the latent space While the quantities introduced in Section 3 measure the robustness in the image space, an alternative is to measure the robustness in the latent space, defined as $r_{Z}=\min_{r}\|r\|_{2}\text{ s.t. }f(g(z+r))\neq f(g(z))$. For natural images, latent vectors provide a decomposition of images into meaningful factors of variation, such as features of objects in the image, illumination, etc… Hence, perturbations of vectors in the latent space measure the amount of change one needs to apply to such meaningful latent features to cause data misclassification. A bound on the magnitude of the minimal perturbation in the latent space (i.e., $r_{Z}$) can be directly obtained from Theorem 1 by setting $\omega$ to identity (i.e., $\omega(t)=t$). Importantly, note that no assumptions on the smoothness of the generator $g$ are required for our bounds to hold when considering this notion of robustness.

Relation between in-distribution robustness and unconstrained robustness.

While the previous bound is specifically looking at the in-distribution robustness, in many cases, we are interested in achieving unconstrained robustness; that is, the perturbed image is not constrained to belong to the data distribution (or equivalently to the range of $g$). It is easy to see that any bound derived for the in-distribution robustness $r_{\text{in}}(x)$ also holds for the unconstrained robustness $r_{\text{unc}}(x)$ since it clearly holds that $r_{\text{unc}}(x)\leq r_{\text{in}}(x)$. One may wonder whether it is possible to get a better upper bound on $r_{\text{unc}}(x)$ directly. We show here that this is not possible if we require our bound to hold for any general classifier. Specifically, we construct a family of classifiers for which $r_{\text{unc}}(x)\geq\frac{1}{2}r_{\text{in}}(x)$, which we now present:

This result shows that if a classifier has in-distribution robustness $r$, then we can construct a classifier with unconstrained robustness $r/2$, through a simple modification of the original classifier $f$. Hence, classification-agnostic limits derived for both notions of robustness are essentially the same. It should further be noted that the procedure in Eq. (5) provides a constructive method to increase the robustness of any classifier to unconstrained perturbations. Such a nearest neighbour strategy is useful when the in-distribution robustness is much larger than the unconstrained robustness, and permits the latter to match the former. This approach has recently been found to be successful in increasing the robustness of classifiers when accurate generative models can be learned in defensegan. Other techniques ilyas2017robust build on this approach, and further use methods to increase the in-distribution robustness.

2 Transferability of perturbations

One of the most intriguing properties about adversarial perturbations is their transferability szegedy2013intriguing; liu2016delving across different models. Under our data model distribution, we study the existence of transferable adversarial perturbations, and show that two models with approximately zero risk will have shared adversarial perturbations.

Compared to Theorem 1 which bounds the robustness to adversarial perturbations, the extra price to pay here to find transferable adversarial perturbations is the $2\delta$ term, which is small if the risk of both classifiers is small. Hence, our bounds provide a theoretical explanation for the existence of transferable adversarial perturbations, which were previously shown to exist in szegedy2013intriguing; liu2016delving. The existence of transferable adversarial perturbations across several models with small risk has important security implications, as adversaries can, in principle, fool different classifiers with a single, classifier-agnostic, perturbation. The existence of such perturbations significantly reduces the difficulty of attacking (potentially black box) machine learning models.

3 Approximate generative model

In the previous results, we have assumed that the data distribution is exactly described by the generative model $g$ (i.e., $\mu=g_{*}(\nu)$ where $g_{*}(\nu)$ is the pushforward of $\nu$ via $g$). However, in many cases, such generative models only provide an approximation to the true data distribution $\mu$. In this section, we specifically assume that the generated distribution $g_{*}(\nu)$ provides an approximation to the true underlying distribution in the 1-Wasserstein sense on the metric space $(\mathcal{X},\|\cdot\|)$; i.e., $W(g_{*}(\nu),\mu)\leq\delta$, and derive upper bounds on the robustness. This assumption is in line with recent advances in generative models, whereby the generator provides a good approximation (in the Wasserstein sense) to the true distribution, but does not exactly fit it arjovsky2017wasserstein. We show here that similar upper bounds on the robustness (in expectation) hold, as long as $g_{*}(\nu)$ provides an accurate approximation of the true distribution $\mu$.

We use the same notations as in Theorem 1. Assume that the generator $g$ provides a $\delta$ approximation of the true distribution $\mu$ in the 1-Wasserstein sense on the metric space $(\mathcal{X},\|\cdot\|)$; that is, $W(g_{*}(\nu),\mu)\leq\delta$ (where $g_{*}(\nu)$ is the pushforward of $\nu$ via $g$), the following inequality holds provided $\omega$ is concave

where $r_{\text{unc}}(x)$ is the unconstrained robustness in the image space. In particular, for $K\geq 5$ equiprobable classes, we have

In words, when the data is defined according to a distribution which can be approximated by a smooth, high-dimensional generative model, our results show that arbitrary classifiers will have small adversarial examples in expectation. We also note that as $K$ grows, this bound decreases and even goes to zero under the sole condition that $\omega$ is continuous at $0$. Note however that the decrease is slow as it is only logarithmic.

Experimental evaluation

We now evaluate our bounds on the SVHN dataset netzer2011reading which contains color images of house numbers, and the task is to classify the digit at the center of the image. In all this section, computations of perturbations are done using the algorithm in moosavi2015deepfool. Note that in order to estimate robustness quantities (e.g., $r_{\text{in}}$), we do not need the ground truth label, as the definition only involves the change of the estimated label. Estimation of the robustness can therefore be readily done for automatically generated images. The dataset contains $73,257$ training images, and $26,032$ test images (we do not use the images in the ’extra’ set). We train a DCGAN radford2015unsupervised generative model on this dataset, with a latent vector dimension $d=100$, and further consider several neural networks architectures for classification. For the SVHN and CIFAR-10 experiments, we show examples of generated images and perturbed images in the appendix (Section C.3). Moreover, we provide in C.1 details on the architectures of the used models. For each classifier, the empirical robustness is compared to our upper bound. To evaluate numerically the upper bound, we have used a probabilistic version of the modulus of continuity, where the property is not required to be satisfied for all $z,z^{\prime}$, but rather with high probability, and accounted for the error probability in the bound. We refer to the appendix for the detailed optimization used to estimate the smoothness parameters. In addition to reporting the in-distribution and unconstrained robustness, we also report the robustness in the latent space: $r_{Z}=\min_{r}\|r\|_{2}\text{ s.t. }f(g(z+r))\neq f(g(z))$. For this robustness setting, note that the upper bound exactly corresponds to Theorem 1 with $\omega$ set to the identity map. Results are reported in Table 1.

Observe first that the upper bound on the robustness in the latent space is of the same order of magnitude as the empirical robustness computed in the $\mathcal{Z}$-space, for the different tested classifiers. This suggests that the isoperimetric inequality (which is the only source of inequality in our bound, when factoring out smoothness) provides a reasonable baseline that is on par with the robustness of best classifiers. In the image space, the theoretical prediction from our classifier-agnostic bounds is one order of magnitude larger than the empirical estimates. Note however that our bound is still non-vacuous, as it predicts the norm of the required perturbation to be approximately $1/3$ of the norm of images (i.e., normalized robustness of $0.36$). This potentially leaves room for improving the robustness in the image space. Moreover, we believe that the bound on the robustness in the image space is not tight (unlike the bound in the $\mathcal{Z}$ space) as the smoothness assumption on $g$ can be conservative.

Further comparisons of the figures between in-distribution and unconstrained robustness in the image space interestingly show that for the simple LeNet architecture, a large gap exists between these two quantities. However, by using more complex classifiers (ResNet-18 and ResNet-101), the gap between in-distribution and unconstrained robustness gets smaller. Recall that Theorem 2 says that any classifier can be modified in a way that the in-distribution robustness and unconstrained robustness only differ by a factor $2$, while preserving the accuracy. But this modification may result in a more complicated classifier compared to the original one; for example starting with a linear classifier, the modified classifier will in general not be linear. This interestingly matches with our numerical values for this experiment, as the multiplicative gap between in-distribution and unconstrained robustness approaches $2$ as we make the classification function more complex (e.g., in-distribution robustness of $3.1\times 10^{-2}$ and out-distribution $1.4\times 10^{-2}$ for ResNet-101).

We now consider the more complex CIFAR-10 dataset krizhevsky2009learning. The CIFAR-10 dataset consists of 10 classes of $32\times 32$ color natural images. Similarly to the previous experiment, we used a DCGAN generative model with $d=100$, and tested the robustness of state-of-the-art deep neural network classifiers. Quantitative results are reported in Table 2. Our bounds notably predict that any classifier defined on this task will have perturbations not exceeding $1/10$ of the norm of the image, for $25\%$ of the datapoints in the distribution. Note that using the PGD adversarial training strategy of madry2017towards (which constitutes one of the most robust models to date uesato2018adversarial), the robustness is significantly improved, despite still being $\sim 1$ order of magnitude smaller than the baseline of $0.1$ for the in-distribution robustness. The construction of more robust classifiers, alongside better empirical estimates of the quantities involved in the bound/improved bounds will hopefully lead to a convergence of these two quantities, hence guaranteeing optimality of the robustness of our classifiers.

Discussion

We have shown the existence of a baseline robustness that no classifier can surpass, whenever the distribution is approximable by a generative model mapping latent representations to images. The bounds lead to informative numerical results: for example, on the CIFAR-10 task (with a DCGAN approximator), our upper bound shows that a significant portion of datapoints can be fooled with a perturbation of magnitude $10\%$ that of an image. Existing classifiers however do not match the derived upper bound. Moving forward, we expect the design of more robust classifiers to get closer to this upper bound. The existence of a baseline robustness is fundamental in that context in order to measure the progress made and compare to the optimal robustness we can hope to achieve.

In addition to providing a baseline, this work has several practical implications on the robustness front. To construct classifiers with better robustness, our analysis suggests that these should have linear decision boundaries in the latent space; in particular, classifiers with multiple disconnected classification regions will be more prone to small perturbations. We further provided a constructive way to provably close the gap between unconstrained robustness and in-distribution robustness.

Our analysis at the intersection of classifiers’ robustness and generative modeling has further led to insights onto generative models, due to its intriguing generality. If we take as a premise that human visual system classifiers require large-norm perturbations to be fooled (which is implicitly assumed in many works on adversarial robustness, though see elsayed2018adversarial), our work shows that natural image distributions cannot be modeled as very high dimensional and smooth mappings. While current dimensions used for the latent space (e.g., $d=100$) do not lead to any contradiction with this assumption (as upper bounds are sufficiently large), moving to higher dimensions for more complex datasets might lead to very small bounds. To model such datasets, the prior distribution, smoothness and dimension properties should therefore be carefully set to avoid contradictions with the premise. For example, conditional generative models can be seen as non-smooth generative models, as different generating functions are used for each class. We finally note that the derived results do bound the norm of the perturbation, and not the human perceptibility, which is much harder to quantify. We leave it as an open question to derive bounds on more perceptual metrics.

A.F. would like thank Seyed Moosavi, Wojtek Czarnecki, Neil Rabinowitz, Bernardino Romera-Paredes and the DeepMind team for useful feedbacks and discussions.

Appendix A Proofs

Recall that we write the cumulative distribution function for the standard Gaussian distribution $\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-u^{2}/2}du$. We state the Gaussian isoperimetric inequality borell1975brunn; sudakov1978extremal, the main technical tool used in to prove the results in this paper.

We then state some useful bounds on the cumulative distribution function for the Gaussian distribution $\Phi$.

Let $p\in[1/2,1]$, we have for all $\eta>0$,

If $p=1-\frac{1}{K}$ for $K\geq 5$ and $\eta\geq 1$, we have

As $p\geq 1/2$, we have $\Phi^{-1}(p)\geq 0$. Thus,

In the case $p=1-\frac{1}{K}$, it suffices to show that that for $K\geq 5$, we have

Using the upper bound in (7), and the fact that $x+\sqrt{x^{2}+2}\leq 2\sqrt{x^{2}+1}$, it suffices to show that $\frac{1}{2}\frac{e^{-x^{2}}}{\sqrt{\pi}\sqrt{x^{2}+1}}\geq\frac{1}{K}$ where $x=\sqrt{\frac{1}{2}\log\left(\frac{K^{2}}{4\pi\log(K)}\right)}$. This inequality is equivalent to showing that $\sqrt{\log(K)}\geq\sqrt{x^{2}+1}$ for the same value of $x$. If we let $u=\log(K)$ this amounts to showing that $\sqrt{u}\geq\sqrt{u-\frac{1}{2}\log(4\pi u)+1}$ for all $u\geq\log(5)$. For such $u$ one can verify that $-\frac{1}{2}\log(4\pi u)+1\leq 0$ and so clearly the inequality is satisfied.

A.2 Proof of Theorem 1

To prove the general bound in Eq. (2), we define

For the bound (4) that makes explicit the dependence on the number of classes, we simply use the more explicit bound in (9). ∎

A.3 Proof of Theorem 2

A.4 Proof of Theorem 3

We use the same notations as in the proof of Theorem 1: let $B_{i}(f)=g^{-1}(C_{i}(f))$ and $B_{i}(h)=g^{-1}(C_{i}(h))$, and let

where the notation $\overline{B}$ stands for the complement of $B$.

Note that $B_{i}(f)\cup B_{i}(h)=\overline{\overline{B_{i}(f)}\cap\overline{B_{i}(h)}}$. We have $\nu(\overline{B_{i}(f)}\cap\overline{B_{i}(h)})\geq\nu(\overline{B_{i}(f)})-\delta=1-\nu(B_{i}(f))-\delta\geq\frac{1}{2}$. Thus, using the Gaussian isoperimetric inequality with $A=\overline{B_{i}(f)}\cap\overline{B_{i}(h)}$, we obtain

where we also used inequality (8). As a result,

Now assume that $z\in B_{i\rightarrow}$ but also $z\in B_{i}(f)\cap B_{i}(h)$. Then it is classified as $i$ for both $f$ and $h$. In addition, the condition $z\in B_{i\rightarrow}$ ensures that there exists $z^{\prime}\in\overline{B_{i}(f)}\cap\overline{B_{i}(h)}$ such that $\|z-z^{\prime}\|_{2}\leq\omega^{-1}(\eta)$. Setting $v=g(z^{\prime})-g(z)$, we have that $f(g(z)+v)\neq f(g(z))$ and $h(g(z)+v)\neq h(g(z))$ and $\|v\|\leq\omega(\|z-z^{\prime}\|)\leq\eta$. As such it suffices to show that the set $B_{i\rightarrow}\cap(B_{i}(f)\cap B_{i}(h))$ has sufficiently large measure. Indeed, we have

because $\sum_{i=1}^{K}\nu(B_{i}(f)\cap\overline{B_{i}(h)})+\nu(\overline{B_{i}(f)}\cap B_{i}(h))=2\cdot\nu\left\{f\circ g(z)\neq h\circ g(z)\right\}\leq 2\delta$.

A.5 Proof of Theorem 4

Using a bound similar to Theorem 1 applied to $r_{\mathcal{Z}}$ we get

Assuming now that the classes are equiprobable, i.e., $a_{\neq i}=\Phi^{-1}(1-1/K)=:a(K)$ for all $i$ we get that

We assume now that $g$ is such that $W(g_{*}(\nu),\mu)\leq\delta$, where $W$ denotes the Wasserstein distance in $(\mathcal{X},\|\cdot\|)$. Let $(X,X^{\prime})$ be a coupling with $X\sim\mu$ and $X^{\prime}\sim g_{*}(\nu)$. We will construct a random variable $X^{\prime\prime}$ such that almost surely $X^{\prime\prime}$ and $X$ are classified differently. We define $X^{\prime\prime}=X^{\prime}$ if $X$ and $X^{\prime}$ are classified differently and otherwise $X^{\prime\prime}=X^{\prime}+\vec{r}^{*}(X^{\prime})$ where $\vec{r}^{*}(X^{\prime})$ is defined to be a vector of minimum norm such that $X^{\prime}+\vec{r}^{*}(X^{\prime})$ and $X^{\prime}$ are classified differently. Then we have

Appendix B Toy example: tightness of Theorem 1

As an illustration to Remark 4, we explicitly show through a toy example that a classifier which is not linear in the $\mathcal{Z}$-space can be significantly less robust than a linear one.

Assume that $B_{1}=g^{-1}(C_{1})$ and $B_{2}=g^{-1}(C_{2})$ are given by:

$B_{1}=\{(z_{1},\dots,z_{d}):\sum_{i=1}^{d}\left\lfloor z_{i}\right\rfloor\mod 2=0\}$,

See Fig. 3(a) for an illustration. Then, we have

Fig 3(b) compares the general bound in Theorem 1 to Eq. (11). As can be seen, in the checkerboard partition example, the probability of fooling converges much quicker to $1$ (wrt $\eta$) than the general result in Theorem 1. Hence, a classifier that creates many disconnected classification regions can be much more vulnerable to perturbations than a linear classifier in the latent space.

Appendix C Experimental results

For the SVHN dataset, we resize the images to $64\times 64$. For the generative model, we use the PyTorch implementation of DCGAN available on https://github.com/pytorch/examples/blob/master/dcgan/main.py using the default parameters for architecture and optimization. The $2$-layer LeNet classifier has the following architecture:

where the parameters of Conv are kernel size, padding and number of filters, respectively. We used the ResNet18 and ResNet101 architectures available on https://github.com/kuangliu/pytorch-cifar/blob/master/models/resnet.py, with a kernel size of $5$ for Conv1 and a stride of $2$. For all $3$ architectures, we used SGD with a learning rate of $0.01$, momentum of $0.9$, batch size of $100$. To solve the problem in Eq. 12, we use gradient descent (for the maximization of $\|g(z)-g(z^{\prime})\|_{2}$) with learning rate $0.1$ for $1,000$ steps. The upper bound was computed based on $100$ samples of $z$.

For the CIFAR-10 experiment, we use a similar DCGAN generative model. The VGG-type architecture has 11 conv layers, each of kernel size $3$, with number of output channels $(64,64,128,128,128,256,256,256,512,512,512)$ and stride $(1,1,2,1,1,2,1,1,2,1,1)$. Each conv layer is followed by BatchNorm and a ReLU function. For the WideResNet architecture, we use the WRN-28-10 model available on https://github.com/szagoruyko/wide-residual-networks. SGD is used with learning rate $0.1$, momentum $0.9$, and batchsize $100$. For the adversarially trained Wide ResNet with PGD training, we have used the model of madry2017towards.

C.2 Numerical evaluation of the upper bound

To evaluate numerically the upper bound, we have used a probabilistic version of the modulus of continuity, where the property is not required to be satisfied for all $z,z^{\prime}$, but rather with high probability, and accounted for the error probability in the bound. Specifically, while the modulus of continuity function is given by $\omega(\delta)=\max_{z}\max_{z^{\prime}:\|z-z^{\prime}\|_{2}\leq\delta}\|g(z)-g(z^{\prime})\|_{2}$, we use in the experiments a probabilistic version of the modulus of continuity, given by:

Then, the following bound holds for any $\delta,\kappa$:

For example, when $\kappa$ is set to $0$, we recover the exact bounds in Theorem 1. When $\kappa>0$, we have to account for the use of a probabilistic definition of the modulus of continuity in the bound; this exactly corresponds to the additive $\kappa$ term in the probability in Eq. (13).

In practice, for a fixed target probability (set to $0.25$ in the experiments of the main paper), it is possible to choose the value of $\delta$ that yields the best bound, since Eq. (13) is valid for any $\delta$. For a fixed value of $\delta$, we used gradient descent (until the loss function stabilizes) in order to solve the optimization problem $\sup_{z:\|z^{\prime}-z\|_{2}\leq\delta}\|g(z)-g(z^{\prime})\|$. For a fixed value of $\delta$, we hence summarize the procedure used to evaluate the upper bound in Algorithm 1. We have used in practice $100$ samples to estimate the upper bound, for each value of $\delta$. For any value of $\delta$, Algorithm 1 provides an estimate of the upper bound; such an estimate can be improved by using many different values of $\delta$.

C.3 Illustration of generated images

Fig. 4 illustrates generated images for SVHN, as well as corresponding perturbed images that fool a ResNet-18 classifier (in-distribution robustness). Similarly, Fig. 5 illustrates examples of generated images for CIFAR-10, as well as perturbed samples required to fool the VGG classifier, where perturbed images are constrained to belong to the data distribution (i.e., in-distribution setting).

References