Randomized Smoothing of All Shapes and Sizes

Introduction

We propose two new methods to compute robust certificates for additive randomized smoothing against different norms.

Related Works

Defences against adversarial examples are mainly divided into empirical defenses and certified defenses.

Empirical defenses are heuristics designed to make learned models empirically robust. An example of these are adversarial training based defenses (Kurakin et al. 2016; Madry et al. 2017) which optimize the parameters of a model by minimizing the worst-case loss over a neighborhood around the input to these models (Carlini & Wagner 2017; Laidlaw & Feizi 2019; Wong et al. 2019; Hu et al. 2020). Such defenses may seem powerful, but have no guarantees that they are not “breakable”. In fact, the majority of the empirical defenses proposed in the literature were later “broken” by stronger attacks (Carlini & Wagner 2017; Athalye et al. 2018; Uesato et al. 2018; Athalye & Carlini 2018).

Certified defenses guarantee that for any input $x$, the classifier’s output is constant within a small neighborhood of $x$. Such defenses are typically based on certification methods that are either exact or conservative. Exact methods include those based on Satisfiability Modulo Theories solvers (Katz et al. 2017; Ehlers 2017) or mixed integer linear programming (Tjeng et al. 2019; Lomuscio & Maganti 2017; Fischetti & Jo 2017), which, although guaranteed to find adversarial examples if they exist, are unfortunately computationally inefficient. On the other hand, conservative methods are more computationally efficient, but might mistakenly flag a “safe” data point as vulnerable to adversarial examples (Wong & Kolter 2018; Wang et al. 2018a; Wang et al. 2018b; Raghunathan et al. 2018a; Raghunathan et al. 2018b; Wong et al. 2018; Dvijotham et al. 2018b; Dvijotham et al. 2018a; Croce et al. 2018; Salman et al. 2019b; Gehr et al. 2018; Mirman et al. 2018; Singh et al. 2018; Gowal et al. 2018; Weng et al. 2018; Zhang et al. 2018). However, none of these defenses scale to practical networks. Recently, a new method called randomized smoothing has been proposed as a probabilistically certified defense, whose architecture-independence makes it scalable.

We are the first to relate to adversarial robustness the theory of Wulff Crystals. Just as the round soap bubble minimizes surface tension for a given volume, the Wulff Crystal minimizes certain similar surface energy that arises when the crystal interfaces with another material. The Russian physicist George Wulff first proposed this shape via physical arguments in 1901 (Wulff 1901), but its energy minimization property was not proven in full generality until relatively recently, building on a century worth of work (Gibbs 1875; Wulff 1901; Hilton 1903; Liebmann 1914; von Laue; Dinghas 1944; Burton et al. 1951; Herring; Constable 1968; Taylor 1975; Taylor 1978; Fonseca & Müller 1991; Brothers & Morgan 1994; Cerf 2006).

Randomized Smoothing

One can think of $U$ has the decision region of some base classifier. Thus $\mathcal{G}_{q}(p,v)$ gives the maximal growth of measure of a set (i.e. decision region) when $q$ is shifted by the vector $v$, if we only know the initial measure $p$ of the set.

Methods for Deriving Robust Radii

Then the Neyman-Pearson lemma tells us that (Neyman & Pearson 1933; Cohen et al. 2019)

While this gives way to a simple expression for the growth function when $q$ is Gaussian (Cohen et al. 2019), it is difficult for more general distributions as the geometry of $\mathcal{NP}_{\kappa}$ becomes hard to grasp. To overcome this difficulty, we propose the level set method that decomposes this geometry so as to compute the growth function exactly, and the differential method that upper bounds the growth function derivative, loosely speaking.

For each $t>0$, let $U_{t}$ be the superlevel set

Then its boundary $\partial U_{t}$ is the level set with $q(x)=t$ under regularity assumptions. The integral of $q$’s density is of course 1, but this integral can be expressed as the integral of the volumes of its superlevel sets:

If $q$ has a differentiable density, then we may rewrite this as an integral of level sets (E.3):

The graphics above illustrate the two integral expressions (best viewed on screen). In this level set perspective, the Neyman-Pearson set $\mathcal{NP}_{\kappa}$ (Eq. 4) can be written as

Then naturally, its measure is calculated by

Similarly, the Neyman-Pearson set can also be written from the perspective of $q(\cdot-v)$,

where $\mathring{U}$ is the interior of the closed set $U$. So its measure under $q(\cdot-v)$ is

The graphics above illustrate the integration domains of $x$ in Eqs. ∨ and ∧ ‣ 4.1. In general, the geometry of $\partial U_{t}\cap(U_{t/\kappa}+v)$ or $\partial U_{t}\setminus(\mathring{U}_{t\kappa}-v)$ is still difficult to handle, but in highly symmetric cases when $U_{t}$ are concentric balls or cubes, Eqs. ∨ and ∧ ‣ 4.1 can be calculated efficiently.

Eqs. ∨ and ∧ ‣ 4.1 allow us to compute the growth function by Eq. NP. In general, this yields an upper bound of the robust radius

2 The Differential Method

To derive certification (robust radius lower bounds) for more general distributions, we propose a differential method, which can be thought of as a vast generalization of the proof in Salman et al. 2019a of the Gaussian robust radius. The idea is to compute the largest possible infinitesimal increase in $q$-measure due to an infinitesimal adversarial perturbation. More precisely, given a norm $\|\cdot\|$, and a smoothing measure $q$, we define

Intuitively, one can then think of $1/\Phi(p)$ as the smallest possible perturbation in $\|\cdot\|$ needed to effect a unit of infinitesimal increase in $p$. Therefore,

The robust radius in $\|\cdot\|$ is at least

where $\rho$ is the probability that the base classifier predicts the right label under random perturbation by $q$.

By exchanging differentiation and integration and applying a similar greedy reasoning as in the Neyman-Pearson lemma, $\Phi(p)$ can be derived for many distributions $q$ and integrated symbolically to obtain expressions for $R$. We demonstrate the technique with a simple example below, but much of it can be automated; see F.6.

when $\rho$ is the probability of the correct class as in 4.1.

By linearity in $\lambda$, we WLOG assume $\lambda=1$. By 4.1 and the monotonicity of $\Phi$, it suffices to show that $\Phi(p)=1/2d$ for $p\geq 1/2d.$ For any fixed $U$ with $q(U)=p$,

where $U$ ranges over all $q(U)=p$. Note $\langle e_{1},e_{x}\rangle=0$ if $i^{*}\neq 1$, and $\operatorname{sgn}(x_{i^{*}})$ otherwise. Thus, to maximize $\lim_{r\searrow 0}\frac{q(U-re_{1})-p}{r}$ subject to the constraint that $q(U)=p$, we should put as much $q$-mass on those $x$ with large $\langle e_{1},e_{x}\rangle$. For $p\geq 1/2d$, we thus should occupy the entire region $\{x:\langle e_{1},e_{x}\rangle=1\}$, which has $q$-mass $1/2d$, and then assign the rest of the $q$-mass (amounting to $p-1/2d$) to the region $\{x:\langle e_{1},e_{x}\rangle=0\}$, which has $q$-mass $1-1/d$. This shows that

3 Comparison of the Two Methods and Prior Works

We summarize the distributions our methods cover in Fig. 1 and the bounds we derive in Table A.1. We highlight a few broadly applicable robustness guarantees:

for some constant $c$ depending on the distribution.

In general, the level set method always gives certificate as tight as Neyman-Pearson, while the differential method is tight only for infinitesimal perturbations, but can be shown to be tight for certain families, like in 4.3 above. On the other hand, the latter will often give efficiently evaluable symbolic expressions and apply to more general distributions, while the former in general will only yield a table of robust radii, and only for distributions whose level sets are sufficiently symmetric (such as a sphere or cube).

For distributions that are covered by both methods, we compare the bounds obtained and note that the differential and level set methods yield almost identical robustness certificates in high dimensions (e.g. number of pixels in CIFAR-10 or ImageNet images). See Section B.1.

Many earlier works used differential privacy or $f$-divergence methods to compute robust radii of smoothed models (Lecuyer et al. 2018; Li et al. 2019; Dvijotham et al. 2019). In particular, Dvijotham et al. 2019 proposed a general $f$-divergence framework that subsumed all such works. Our robust radii are computed only from $\rho$; Dvijotham et al. 2019 called this the “information-limited” setting, and we shall compare with their robustness guarantees of this type. While their algorithm in a certain limit becomes as good as Neyman-Pearson, in practice outside the Gaussian distribution, their robust radii are too loose. This is evident by comparing our baseline Laplace results in Footnote 2 with theirs, which are trained the same way. Additionally, our differential method often yields symbolic expressions for robust radii, making the certification algorithm easy to implement, verify, and run. Moreover, we derive robustness guarantees for many more (distributions, adversary) pairs (Figs. 1 and A.1). See Section B.2 for a more detailed comparison.

Wulff Crystals

A priori, it is a daunting task to understand the relationship between the adversary $\mathcal{B}$ and the smoothing distribution $q$. In this section, we shall begin our investigation by looking at uniform distributions, and then end with an optimality theorem for all “reasonable” distributions.

If $S$ is convex, and we take $v$ to be an infinitesimal translation, then the RHS above is infinitesimally larger than $p$, as follows:

In fact, Wulff Crystals solve the more general problem without convexity constraint.

The Wulff Crystal w.r.t. $\mathcal{B}$ minimizes

In fact, distributions with Wulff Crystal level sets more generally maximizes the robust radii for “hard” inputs.

Let $\mathcal{B}$ be sufficiently symmetric. Let $q_{0}$ be any distribution with a ‘‘reasonable’’ Reasonable here roughly means Sobolev, i.e. has weak derivative that is integrable, and this can be further relaxed to bounded variations; for details see G.20 and H.15. and even density function. Among all “reasonable” and even density functions $q$ whose superlevel sets $\{x:q(x)\geq t\}$ have the same volumes as those of $q_{0}$, the quantity

is minimized by the unique distribution $q^{*}$ whose superlevel sets are proportional to the Wulff Crystal w.r.t. $\mathcal{B}$.

This theorem implies that distributions with Wulff Crystal level sets give the best robust radii for those hard inputs $x$ that a smooth classifier classifies correctly but only barely, in that the probability of the correct class $\rho=1/2+\epsilon$ for some small $\epsilon$. The constraint on the volumes of superlevel sets indirectly controls the variance of the distribution. While this theorem says nothing about the robust radii for $\rho$ away from $1/2$, we find the Wulff Crystal distributions empirically to be highly effective, as we describe next in Section 6.

Experiments

We empirically study the performance of different smoothing distributions on image classification datasets, using the bounds derived via the level set or the differential method, and verify predictions made by the Wulff Crystal theory. We follow the experimental procedure in Cohen et al. 2019 and further works on randomized smoothing (Salman et al. 2019a; Li et al. 2019; Zhai et al. 2020) using ImageNet (Deng et al. 2009) and CIFAR-10 (Krizhevsky 2009).

We focus on the effect of the noise distribution in this section and only train models with noise augmentation. In Appendix D we also study (1) stability training, and (2) the use of more data through (a) pre-training on downsampled ImageNet (Hendrycks et al. 2019) and (b) semi-supervised self-training with data from 80 Million Tiny Images (Carmon et al. 2019). As shown in Table 2, these techniques further improve upon our results in this section.

Exponential, $\propto\|x\|_{\infty}^{-j}e^{-\|x/\lambda\|^{k}_{\infty}}$

Power law, $\propto(1+\|x/\lambda\|_{\infty})^{-a}$

We compare to previous state-of-the-art approaches using the Gaussian and Laplace distributions, as well as new non-cubical distributions.

Pareto i.i.d. (non-cubical), $\propto\prod_{i}(1+|x_{i}|/\lambda)^{-a}.$

The relevant certified bounds are given in Table A.1.

Exponential, $\propto\|x\|_{2}^{-j}e^{-\|x/\lambda\|_{2}^{k}}$

Power law, $\propto(1+\|x/\lambda\|_{2})^{-a}$

We find these distributions perform similarly to, though do not surpass the Gaussian (Fig. 3, left).

No-Go Results for Randomized Smoothing

A normed space $T=(X,\|\cdot\|)$ is said to have cotype $p$ for $2\leq p\leq\infty$ if there exists $C$ such that for all finite sequences $x_{1},\ldots,x_{n}\in X$, we have

where the $\sigma_{j}$ are independent Rademacher random variables. The smallest such $C$ is denoted $C_{p}(T)$.

It is easy to see that, up to constants, the Gaussian smoothing scheme achieves equality, and thus is optimal (in terms of dimension dependence), for all $p\in[1,\infty]$.

Another route is to directly look for better randomized smoothing schemes for multi-class classification. We formulated our no-go result in the setting of binary classification, and it is not clear whether a similarly strong barrier applies for multi-class classification. However, current techniques for certification only look at the two most likely classes, and separately reason about how much each one can change by perturbing the input. Our no-go result then straightforwardly applies to this case as well.

Conclusion

More broadly, randomized smoothing is a method for inducing stability in a mechanism while maintaining utility — precisely the bread and butter of differential privacy. We suspect our methods for deriving robustness guarantees here and for optimizing the noise distribution can be useful in that setting as well, where Laplace and Gaussian noise dominate the discussion. Whereas previous work Lecuyer et al. 2018 has applied differential privacy tools to randomized smoothing, we hope to go the other way around in the future.

We thank Huan Zhang for brainstorming of ideas and performing a few experiments that unfortunately did not work out. We also thank Aleksandar Nikolov, Sebastien Bubeck, Aleksander Madry, Zico Kolter, Nicholas Carlini, Judy Shen, Pengchuan Zhang, and Maksim Andriushchenko for discussions and feedback.

References

Appendix A Table of Robust Radii

Appendix B Analysis of Robust Radii

Here we make a few observations about the robust radii of the distributions studied in this paper.

We can understand this phenomenon intuitively via the level set method: Two distributions concentrating around the same level set will have Eq. ∨ and Eq. ∧ evaluate to similar quantities.

This is evident in the top left, middle right, and bottom right subplots of Fig. A.1.

This is evident, for example, in the top middle subplot of Fig. A.1, where the distribution $\propto\|x\|_{\infty}^{-j}e^{-\|x/\lambda\|_{\infty}}$ with “large” $j=3070$ has robust radii much smaller than those of $\propto e^{-\|x/\lambda\|_{\infty}}$. Same thing can be observed in the top right, center, middle right, bottom left, bottom middle subplots of Fig. A.1.

The top middle and bottom left subplots of Fig. A.1 illustrate this point. Thus, we see no evidence for the “soap-bubble hypothesis” put forth by Zhang* et al. 2020; see also Fig. C.8.

The middle left and bottom left subplots of Fig. A.1 demonstrate this behavior. The robust radii formulas for $\exp(-\|x\|_{\infty})$ (I.6) and for the uniform distribution (I.8) also reflect this, as the former has robust radius $\to\infty$ as $\rho\to 1$, but the latter has a finite maximal robust radius.

B.1 Level Set Method vs Differential Method

Here we concretely compare the robust radii obtained from the level set method and those obtained from the differential method for the distribution $\exp(-\|x\|_{2}\sqrt{d})$, for various input dimensions $d$ (we scale the distributions this way so each coordinate has size $\Theta(1)$). For convenience, here’s the robust radius from the differential method (I.18):

The robust radii from level set method are computed as in I.20, and they are tight. As we see in Fig. B.1, the differential method is very slightly loose in low dimensions $d=2$ and 4, but in high dimensions $d=32$ or $1024$, the robust radii obtained from both methods are indistinguishable.

B.2 In-Depth Comparison with Dvijotham et al. 2019

The information-limited certification algorithm in Dvijotham et al. 2019 relaxes the optimization problem

It turns out that the Renyi and KL divergences are computationally attractive for a broad class of smoothing measures, while the Hockey-Stick divergences are theoretically attractive as they lead to optimal certificates in the information-limited setting. However, Hockey-Stick divergences are harder to estimate in general, so we only use them for Gaussian smoothing measures.

Concretely, the looseness of their relaxation can be observed when comparing our baseline Laplace results (Footnote 2) with theirs.

Operationally, their algorithm proceeds as follows

For each distribution $q$ and function $f$, manually find the $f$-divergence “ball” that contains $\{q(\cdot-v):v\in\mathcal{B}\}$, i.e. compute $\{\epsilon_{f}\}_{f\in F}$ such that

Then they relax the original certification problem to the certification of all $q^{\prime}$ close to $q$ in $f$-divergence, i.e. they solve Eq. 7 for the $\epsilon_{f}$ found in the previous step.

Appendix C Additional Experimental Results

All results in this section are described for CIFAR-10.

Results for these experiments are shown in Fig. C.2. The suffix of the noises in the legend denotes the value of the shape parameter $k$ or $a$ that was chosen (whereas we fixed shape parameter $j=0$). We note that results for distributions with cubical level sets match but do not exceed that of the Uniform distribution. Meanwhile distributions without cubical level sets do not match performance of the Uniform distribution. This suggests that the tail behavior of the noise does not matter as much as the shape of level sets.

As an additional visualization, when we plot the certified accuracy at fixed $\epsilon$s versus the training accuracy of a Wide ResNet on noise-augmented CIFAR-10, the Uniform distribution can be seen to significantly outperform the Gaussian and Laplace distributions at all training accuracies except those very close to 1 (Fig. C.6).

So while some of the improvement in certified accuracy in Fig. 2(b) is due to improved certified radius per $\rho$, it seems much more of it is due to the difference in how well a classifier trains when smoothed by noise.

Smoothing with unmodified noise, rotated images:

Smoothing with rotated noise, unmodified images:

Note that certification bounds are no longer necessarily applicable, so we only compare clean training accuracy i.e. whether $\arg\max_{\mathcal{Y}}g(x)=y$. Results for Wide ResNet are shown in Fig. C.7. We find that the difference in training performance still exists (but to a lesser degree) under alternative (1), smoothing with unmodified noise but rotated images. On the other hand, we find this difference vanishes under alternative (2), smoothing with rotated noise and unmodified images.

This suggests that the improvement of training accuracy under Uniform noise is due to some synergy of the model architecture with the data distribution and the smoothing noise. The choice of Uniform distribution induces some improvement in training accuracy but this is greatly amplified by the interaction between convolution layers and the image dataset. Thus, a good noise for randomized smoothing seems to be one that balances its robustness properties with its compatibility with the architecture and the data.

In addition to the Gaussian distribution, we considered an Exponential distribution with spherical level sets and a power law distribution with spherical level sets.

Results for these experiments are shown in Fig. C.8. After appropriate hyperparameter search (of $j$ and $a$), performance for both distributions with spherical level sets matches that of the Gaussian.

Appendix D Experimental Details

There are several methods of training a smoothed classifier. Let $f$ denote the base classifier (up to the logit layer), $q$ denote the smoothing distribution, and consider an observation $(x,y)$.

Noise augmentation as in Cohen et al. 2019,

Directly training the smoothed classifier as described in Salman et al. 2019a (without adversarial attacks),

Adversarial training as in Salman et al. 2019a,

where $\delta\sim q$, $\sigma$ here denotes the softmax function, and $\gamma$ is a hyper-parameter.

Unless otherwise noted, in all experiments we trained with the first option, appropriate noise augmentation. We found that direct training was slower and did not yield superior performance in practice. Of these four options we found that stability training with $\gamma=6$ tended to produce the best results (our choice of $\gamma$ follows Carmon et al. 2019). Therefore, we re-trained our SOTA models with stability training and list results in Table 2 and Figure D.1.

For distributions with cubic level sets, we needed to sweep over larger $\sigma$s as well to estimate the large-radius portion of the upper envelope better:

In Fig. C.1 we show the certified accuracies of Gaussian, Laplace and Uniform distributions, for each $\sigma$, for both ImageNet and CIFAR-10. The upper envelopes reported in the main text are defined as the maximum certified accuracies over $\sigma$.

For all experiments we trained with a cosine-annealed learning rate of 0.1, optimized by stochastic gradient descent with momentum of 0.9 and weight decay of 0.0001.

For ImageNet experiments we used a ResNet-50 model and trained with a batch size of 64 for 30 epochs.

For CIFAR-10 experiments we used a Wide ResNet 40-2 model and trained with a batch size of 128 for 120 epochs.

Ablation studies with a fully connected neural network employed two hidden layers of 2048 and 512 nodes followed by ReLU activations, trained with a learning rate of 0.01.

To compute the top categories for certification (which used $N=100,000$ samples), we used 64 samples.

Our code is publicly available at: github.com/tonyduan/rs4a

We explore using more data to improve the robustness of our SOTA smoothed classifiers for CIFAR-10 in two ways: using pre-training as in Hendrycks et al. 2019, and semi-supervised learning as in Carmon et al. 2019. Results are listed in Table 2 and Figure D.1.

Semi-supervised learning is inspired by Carmon et al. 2019, who showed that self-training on the unlabeled 80 Million Tiny Images dataset can improve robustness of CIFAR-10 classifiers. We use their publicly released dataset of 500k images equipped with pseudo-labels generated by a network trained by CIFAR-10, and train on mini-batches from this dataset and CIFAR-10.

Appendix E Mathematical Preliminaries

In this section, we rigorously define several mathematical notions and their properties that will recurrent throughout what follows. We will be brief here, but readers can skip this on first reading and refer back when necessary.

While many distributions like Gaussian have continuously differentiable densities, many others, like Laplace, only have “weak” derivatives. Thus, to cover all such distributions, we need to pin down a notion of “weakly differentiable.”

This means that $f$ has a weak derivative $\nabla f$ such that both $f$ and $\nabla f$ are integrable. For example, ReLU is not a continuously differentiable function, but it is regular since it has the Heavyside step function as its weak derivative.

Here the integral in $x$ in the RHS is over the $(d-1)$-dimensional Hausdorff measure of the reduced boundary of $U_{t}$, which we abuse notation and denote as $\partial U_{t}$.

The regularity of $f$ can be replaced by weaker conditions (see Evans & Gariepy 2015), but the statement here suffices for our purposes.

By setting $g$ in E.3 to be the indicator function over the set where the gradient of $f$ vanishes, we get

Recall the standard definition of absolute continuity, which can be thought of as a more general notion of differentiability.

Such an $f$ has derivative $f^{\prime}$ almost everywhere, and $f^{\prime}$ coincides with $g$ almost everywhere.

Sobolev functions are known to be absolutely continuous on every line, and this property roughly captures all Sobolev functions.

The ACL property of Sobolev functions yields the differentiability of the convolution of a $L^{\infty}$ and a $W^{1,1}$ function.

A function is differentiable if all of 1) its partial derivatives exist and 2) are continuous. First we show that, for any vector $u$, $F*(D_{u}q)=D_{u}(F*q)$. We can compute as follows.

Note additionally that, since $D_{u}q\in L^{1}$ (by assumption) and $F\in L^{\infty}$, their convolution $F*(D_{u}q)$ is bounded and continuous.

Then, taking $u$ to be the coordinate vectors, we see the partial derivatives of $F*q$ all exist and are continuous, proving our lemma. ∎

Appendix F The Differential Method

We summarize the setup of this section in the following assumption. Here we use a notion called regularity introduced in E.2 that roughly says that a function needs to continuous almost everywhere and be “weakly” differentiable, and it and its gradient are both absolutely integrable. All concrete density functions we work with in this paper will be regular, with the exception of the uniform distribution.

If $\psi(x)=\|x\|^{2}_{2}$, then $q$ is the standard Gaussian distribution. If $\psi(x)=\|x\|_{1}$, then $q$ is the Laplace distribution.

The following definition of $\Phi$ turns out to be equivalent to Eq. 5, which will be apparent in the proof of F.6. It gives a systematic way of computing $\Phi$.

and define the inverse complementary CDF ${\varphi}^{-1}_{u}(p)$ of $\gamma_{u}$ to be

For any $p\in$, define a new random variable $\gamma_{u}^{(p)}$ by

The following theorem is the master theorem for applying the differential method. We illustrate its usage to recover the known Gaussian (Cohen et al. 2019) and Laplace (Teng et al. 2019) bounds as warmups in Sections F.1 and F.2 before applying the technique at scale.

Then for any $x$, if $G(x)<1/2$, then $G(x+\delta)<1/2$ for any

In F.6, one should think of $G(x)$ as the probability that the smoothed classifier assigns to any class other than the correct one. So F.6 says that, if the smoothed classifier predicts the correct class ($G(x)<1/2$), then it continues to do so even when the input is perturbed by a noise with magnitude bounded by Eq. ⋆ .

Sometimes, when $\varphi_{u}$ is continuous for all $u$, for $p\in[0,1/2]$, we can factor

Suppose $\Phi(p)=\bar{\varphi}({\varphi}^{-1}(p))$ on $p\in[0,1/2]$, where $\varphi(p)$ is differentiable and both $\varphi$ and $\bar{\varphi}$ are nonincreasing. Then for any $0\leq p_{0}\leq 1/2$,

Finally, as mentioned before, the proof of F.6 will show that

and apply Lemma F.9 to yield the desired result.

where $\mathcal{B}$ is the unit ball of the norm $\|\cdot\|$, and the equality is because $u\cdot\nabla G(x)$ is linear in $u$, so optima are achieved on vertices. Therefore, it suffices to show that,

where we used Lemma E.7 and the assumption that $q$ is regular. Then

In other words, the maximizing $\hat{F}$, which we denote as $\hat{F}^{*}$, is

where $\gamma_{u}^{(p)}$ is the random variable defined in F.4. Finally, putting everything together,

by the definition of $\Phi$ in F.4. This shows Eq. 12 and consequently the theorem as well. ∎

Consider a function $p_{t}$ differentiable in $t\in[0,\infty)$. Suppose $0<p_{0}\leq 1/2$, and

WLOG, we can assume that $dp_{t}/dt>0$ for all $t\in[0,\infty)$. Thus, $p_{t}$ is increasing in $t$, and there exists a differentiable inverse function $t(p)$ that expresses the time $t$ that $p_{t}=p$. We then have $dt(p)/dp=\frac{1}{dp_{t}/dt}=\frac{1}{\Phi(p)}$, and for any $\epsilon\geq 0$,

Since this integral is continuous in $\epsilon$, there is an $\epsilon^{*}>0$ such that

Therefore $p_{T}=1/2-\epsilon^{*}<1/2$, as desired. ∎

We give a quick example of recovering the tight Gaussian bound of Cohen et al. 2019 using the differential method.

Suppose $H$ is a smoothed classifier smoothed by the Gaussian distribution

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Let us give another quick example of recovering the tight Laplace bound of Teng et al. 2019 using the differential method.

with $\nabla\psi(x)$ defined whenever all $x_{i}$s are nonzero.

Suppose $H$ is a smoothed classifier smoothed by the Laplace distribution

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Appendix G Wulff Crystal

The following is an intuitive statement of the main isoperimetric property of Wulff Crystals.

with equality holding if and only if $\Omega$ differs from a translate of $Z$ by a set of volume zero.

This statement carries across the core essence of the isoperimetry, and is a rigorous statement if $\Omega$ is restricted to have smooth boundary, but care needs to be taken to explain the concept of “finite perimeter,” “normal vector,” the “boundary $\partial\Omega$,” and the boundary measure on $\partial\Omega$, in the context of general, measurable $\Omega$. These quantities are defined in Appendix H, but we also refer the interested reader to (Brothers & Morgan 1994) for more mathematical details.

The zonotope can be viewed as a linear projection of the cube $^{\mathcal{S}}$ sending each unit vector to a vector of $\mathcal{S}$.

The volume of a zonotope, and thus of Wulff Crystals, can be computed easily using the following formula.

where $\det\mathcal{T}$ is the determinant of the square matrix with vectors of $\mathcal{T}$ as columns.

G.2 Wulff Crystals Yield Optimal Uniform Distributions for Randomized Smoothing

In this section, we will formulate 5.2 rigorously and prove it.

For example, the boolean cube $\{\pm 1\}^{d}$ is symmetric, and so is the set of coordinate vectors and their negations. The following is the main theorme of this section, stating the optimality of uniform distributions suppoorted Wulff Crystals.

The condition “finite perimeter” can be interpreted intuitvely here, but a formal definition is given in H.4. This condition is necessary because otherwise the limit in question does not exist.

where $\mathbf{n}(x)$ is the normal at $x$ w.r.t. $S$, and $\Theta(x)=\max(0,x)$. Note this quantity is convex in $v$ because $\Theta$ is convex. Then

Using the fact that the volume of the $d$-dimensional unit ball is $\pi^{d/2}\Gamma(d/2+1)^{-1}$, and the volume of the standard $d$-dimensional cross polytope is $2^{d}/d!$, as well as the identity

if $S$ is convex, we can derive the following facts easily.

and confirm it equals $e\sqrt{2/\pi}$. Note that the unit surface normals of $S$ are $\{\pm 1\}^{d}/\sqrt{d}$, occurring with equal probability over the surface measure of $S$. Using Eq. 13, we then see that

where $W=\frac{\sqrt{d}}{(d-1)!}$ is the volume of the simplex $\{x:\sum_{i}x_{i}=1,x\geq 0\}$. This evaluates to

Finally, since the volume of $S$ is $2^{d}/d!$, we can calculate Eq. 15 directly and obtain the desired result. ∎

We verify this approximation to be correct numerically for moderately large $d$. Similarly, the uniform distribution over $\{\pm 1\}^{d}$ is close to a standard Gaussian when $d\gg 1$, so that $\Pi_{v}\{\pm 1\}^{d}$ is close to a $(d-1)$-dimensional standard Gaussian. Therefore, we should expect that

where $Y$ is a $(d-1)\times(d-1)$ Gaussian matrix, and where in Eq. 18, we used the heuristic that for large $d$, $|\det Y|$ is lognormal (G.17). Again, we verify these approximations numerically. Plugging in Eqs. 17 and 18 into Eq. 16 and taking the $d\to\infty$ limit yields the desired result.

Since the sphere has the same large $d$ limit (G.9), we can say that

where $X\in\{\pm 1\}^{d\times d}$ is a random $d\times d$ matrix whose coordinates are iid Rademacher variables (i.e. 1 or $-1$ with equal probability).

Because $\det X=0$ if any two columns are equal, so this is equivalent to summing over all $X$ with distinct columns.

Finally, any given set of $d$ distinct column vectors is represented $d!$ times in the sum through its $d!$ permutations, so this is equal to

which by G.5 is the volume of the zonotope in question. ∎

Let $A_{n}$ be an $n\times n$ random matrix whose entries are independent real random variables with mean zero, variance one and with subexponential tail. Then with $\mu_{n}=\frac{1}{2}\log(n-1)!$ and $\sigma_{n}=\sqrt{\frac{1}{2}\log n}$,

In other words, $\det A_{n}\approx\sqrt{(n-1)!}e^{z\sqrt{\frac{1}{2}\log n}}$ where $z\sim\mathcal{N}(0,1)$.

G.2.3 Growth Formula of a Set

where $\mathbf{n}(x)$ is the normal at $x$ w.r.t. $S$, and $\Theta(x)=\max(0,x)$.

Now, taking the supremum of the RHS over all compactly supported $C^{1}$ function $|f|\leq 1$, we get

G.3 Optimal Smoothing Distributions Have Wulff Crystal Level Sets

Call two distribution $q_{1}$ and $q_{2}$ level-equivalent if their superlevel sets have the same volumes:

where $\|\cdot\|$ is the norm defined by $\mathcal{B}$.

Note that this theorem does not imply G.7 since uniform distributions do not have regular densities. However, this can be generalized to bounded-variation densities (H.15) which subsume both G.7 and G.20.

Consider any distribution $q$ level-equivalent to $q_{0}$. Let $U_{t}$ be its superlevel sets.

Expanding the definition of $\Phi$ in terms of $\gamma_{u}^{(p)}$ (see F.4), and exchanging maximization and expectation, we get

By the Weak Sard’s theorem (E.4), we may ignore the places where $\nabla q(x)=0$, and this integral is the same as

and the inner integral here is invariant in $u$ when $q=q^{*}$ by the symmetry of the Wulff Crystal, as in the proof of G.7, Eq. 19 in fact holds with equality for $q^{*}$, so that $q^{*}$ minimizes $\Phi(1/2)$ as well. ∎

G.4 Optimality among Wulff Crystal Distributions

Given the optimality of Wulff Crystal distributions among level-equivalent distributions, one may wonder, among Wulff Crystal distributions themselves, which one minimizes $\Phi(1/2)$? Because no two such distributions are level-equivalent, we need to fix another notion of the spread of the distribution. The below theorem answers this question, controlling for the expected Wulff Crystal norm.

Note that for any $p>0,k>0$, there is a constant $T_{p,k}$ depending only on $Z$ such that

for any $q$ of the form in G.21. So this theorem applies when we want to fix most measures of spread.

Then, by Holder’s inequality, for any $k>0$,

Concretely, when $d=3\times 1024$ as in the case of CIFAR10, this quantity is 1.00016, so Eq. 22 is quite close to being tight here.

Appendix H Generalization of Differential Method and Wulff Crystal Optimality Results to Bounded Variation Densities

While the regularity condition E.2 covers most distributions we care about, we still have to reason separately about, e.g. uniform distributions on sets, or mixture of such distributions and regular distribution. However, regularity can be weakened to the notion of bounded variation to cover all such cases. Bounded variation (BV) is “essentially the weakest measure theoretic sense in which a function can be differentiable” (Evans & Gariepy 2015). BV functions include the usual continuously differentiable functions as well as indicator functions of “finite perimeter” sets. More generally, the notion of BV allows a “controlled” amount of jump-type discontinuities. Our differential method and our Wulff Crystal optimality results can be generalized to distributions with BV densities.

Readers exposed to the notion of bounded variation for the first time might find it helpful to mentally substitute “BV” in our results below with “differentiable” or with “indicator function” on the first read through. All probability distribution densities we work with concretely in this paper have bounded variation.

We denote by $Df$ the vector measure $\mathbf{n}|Df|$.

If $u$ is the indicator function of, for example, a ball, then $|Du|$ is the $(d-1)$-dimensional Hausdorff measure supported on its boundary (a sphere), and $\mathbf{n}(x)$ is the unit normal at $x$ pointing inward. More generally, this characterization of $Du$ as the boundary measure with unit normals holds when $u$ is the indicator function of a set of finite perimeter.

A set $U$ has finite perimeter if its indicator function $\chi$ is a BV function. In this case, we write

For sufficently smooth sets $U$ (like a sphere), the LHS of Eq. 24 can be interpreted as an integral over the Hausdorff measure of the topological boundary $\partial U$, and Eq. 24 still holds. More generally, there is a subset of the topological boundary, called the reduced boundary of $U$, containing “almost every point” of $\partial U$, such that the LHS of Eq. 24 can be interpreted as an integral over the Hausdorff measure of the reduced boundary. See (Evans & Gariepy 2015) for more details.

Coarea formula also holds for BV functions.

If $f$ is differentiable, then Eq. 25 reduces to

We also have a converse that tells us a function is BV if almost all of its superlevel sets have finite perimeter.

By setting $g$ in H.5 to be the indicator function over the complement of the support of $|Df|$, we get

This allows to show convolution with BV functions yields a.e. differentiability.

where $D_{u}$ on the LHS denotes ordinary directional derivative, and $D_{u}q$ on the RHS denotes the measure $\langle\mathbf{n},u\rangle|Dq|$, with $\mathbf{n}$ as in H.1.

Note that $F*q$ is already bounded and continuous as the convolution of a $L^{\infty}$ and a $L^{1}$ function.

In Eq. 27, we applied Fubini’s theorem after noting that

H.1 Differential Method for BV Densities

To generalize the differential method to distribution with BV densities, we need to to define $\Phi$ differently.

Let $q(x)$ be a distribution with BV density, which we also denote as $q$. Then $|Dq|$ is a finite Radon measure. By Lebesgue Decomposition Theorem, $|Dq|$ is the sum of two measures $|Dq|_{ac}$ and $|Dq|_{s}$ which are resp. absolutely continuous and singular w.r.t. $q$. Thus, there is some set of $q$-measure 0 that has full measure under $|Dq|_{s}$.

and define the inverse complementary CDF ${\varphi}^{-1}_{u}(p)$ of $\gamma_{u}$ to be

For any $p\in$, define a new random variable $\gamma_{u}^{(p)}$ by

Here, $\vartheta_{u}$ represents the instantaneous growth in measure when the set has maximal allocation toward the support of $|Dq|_{s}$.

Let $q$ be the uniform distribution on $^{d}$. Then $|Dq|$ is the Hausdorff measure on the surface of the cube, which is purely singular w.r.t. $q$. Thus, $|Dq|=|Dq|_{s}$, $|Dq|_{ac}=0$, and $\gamma_{u}=0$. On the other hand, for $x$ on the boundary of the cube, $\mathbf{n}(x)$ is the unit normal pointing into the cube, and

This example generalizes to any uniform distribution on any set $S$ of finite perimeter, except that the last equality needs not hold if $S$ is not convex.

With this definition of $\Phi$, the proof of the differential method goes through if we swap usage of Lemma E.7 with Lemma H.11.

Then for any $x$, if $G(x)<1/2$, then $G(x+\delta)<1/2$ for any

H.2 Wulff Crystal Optimality for BV Densities

Similarly, if we swap out usage of E.3 with H.5 and the usage of E.4 with H.9, then we generalize G.20 to distributions with BV densities.

where $\|\cdot\|$ is the norm defined by $\mathcal{B}$.

Likewise, G.21 generalizes similarly to BV densities.

Appendix I Robust Radii Derivations

In this section, we study smoothing distributions that have i.i.d. coordinates.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then with $p_{0}=1-\rho$, and by reparametrization the integral (Lemma F.7), the certified radius is

Simplifying this in terms of the CDF, and noting that $\varphi^{-1}(1/2)=0$ because $\phi$ is even, yields the expression in the theorem statement.

This robust radius is tight, as can be seen from the case when a half-plane $\{x:x_{1}\geq s\}$ is the set of inputs that the base classifier assigns the label $y$.

where $\varphi^{-1}$ is the inverse function of

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then by change of variables $c=\varphi^{-1}(p)$ and with $p_{0}=1-\rho$, the certified radius is

Since $\phi$ is even, $\varphi^{-1}(1/2)=\infty$, yielding the desired result.

Suppose $H$ is a smoothed classifier smoothed by

When $p<1$, it satisfies I.3, so we obtain

Suppose $H$ is a smoothed classifier smoothed by

The integral above can be evaluated explicitly for inverse integer $p=1/k$. We show a few examples below:

In this section, we derive robustness guarantees for distributions of the form $q(x)\propto\|x\|_{\infty}^{-j}\exp(-\|x\|_{\infty}^{k})$.

We first demonstrate the differential method on $q(x)\propto\exp(-\|x\|_{\infty})$ as a warmup before stating the more general result.

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$. Here, we have $q(x)\propto\exp(\psi(x))$ with

where $i^{*}=\argmax_{i}|x_{i}|$, and $e_{i^{*}}$ is the $i^{*}$th coordinate vector, with $\nabla\psi(x)$ defined whenever $i^{*}$ is the unique argmax.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Therefore, for $p\in[0,1/2]$, the random variable $\gamma_{u}^{(p)}$ defined in F.4 is

Simplifying the arithmetics yields the desired claim. ∎

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$. Here, we have

where $i^{*}=\argmax_{i}|x_{i}|$, and $e_{i^{*}}$ is the $i^{*}$th coordinate vector, with $\nabla\psi(x)$ defined whenever $i^{*}$ is the unique argmax.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Therefore, for $p\in[\frac{1}{2d},\frac{1}{2}]$, the random variable $\gamma_{u}^{(p)}$ defined in F.4 is

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

As $j=0$ and $k\to\infty$, the distribution above converges to the uniform distribution, and the robust certificate converges likewise to the one computed previous for uniform distribution.

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Suppose $H$ is a smoothed classifier smoothed by

More generally, if the smoothing distribution is

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Note that $\bar{\varphi}(c)=\frac{1}{2}\bar{\phi}(c)$. Plugging into F.6 yields Eq. 34.

where $C=\frac{k}{2}\frac{\Gamma\left(\frac{d+k-1}{k}\right)}{\Gamma\left(\frac{d}{k}\right)}$. Plugging into F.6 yields Eq. 33. ∎

Compare this with the uniform case below.

When $d\to\infty$, this robust radius is roughly

On the other hand, when $k\to\infty$ in Eq. 33, we see that

by simple calculation $k\frac{\Gamma(\frac{d+k-1}{k})}{\Gamma(\frac{d}{k})}\to d$

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

where $r$ is a random variable with CDF Eq. 35.

Therefore, for $p\in[\frac{1}{2d},\frac{1}{2}]$, the random variable $\gamma_{u}^{(p)}$ defined in F.4 is

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Since $r\mapsto(1+r)^{-1}$ is a decreasing function on $r\in[0,\infty)$, we have, for $p<1/2$,

Plugging into F.6 yields the desired result. ∎

Consider the following generalization of the Laplace distribution

with $\nabla\psi(x)$ defined whenever all $x_{i}$s are nonzero.

Suppose $H$ is a smoothed classifier smoothed by

Here $R=\frac{2\Gamma\left(\frac{d}{k}\right)}{k\Gamma\left(\frac{d+k-1}{k}\right)}$, and

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Therefore, for $p\in[0,1/2]$, the random variable $\gamma_{u}^{(p)}$ defined in F.4 is

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Suppose $H$ is a smoothed classifier smoothed by the Laplace distribution

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the desired robust radius. ∎

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

I.5 Pareto Distribution

Consider smoothing distributions of the form

with $\nabla\psi(x)$ defined when all coordinates $x_{i}$s are nonzero.

Suppose $H$ is a smoothed classifier smoothed by

where $\,{}_{2}F_{1}$ is the hypergeometric function.

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Suppose $H$ is a smoothed classifier smoothed by

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

We seek to apply F.6 to $G(x)=1-H(x)_{y}$, for which we need to derive random variables $\gamma_{u}$ and $\gamma_{u}^{(p)}$, and most importantly, the function $\Phi$.

Then, by setting $G(x)$ in F.6 to be $1-H(x)_{y}=1-\rho$, we get the provably robust radius of

Unpacking the definition of $\varphi$ yields the result. ∎

I.7 Uniform Distribution over a Sphere

By linearity in $\lambda$, it suffices to show this for $\lambda=1$.

By assumption, there is a region of probability $\rho$ under the uniform distribution $q(x+\cdot)$ centered at $x$ that the base classifier classifies as $y$. The intersection between the support of $q(x+\cdot)$ and $q(x+\delta+\cdot)$ for any $\|\delta\|_{2}\leq\epsilon$ contains a region of probability at least

that the base classifier classifies as $y$. For this probability to be at least $1/2$, we require

Define $W_{d}(r,s,\epsilon)$ to be the probability a point sampled from the surface of a ball of radius $r$ centered at the origin is outside a ball of radius $s$ with center $\epsilon$ away from the origin. By Lemma I.23, we have

Note that $W_{d}$ can be evaluated quickly using standard scipy functions.

For most $\bar{q}$, $p_{0}$ and $p_{1}$ can be evaluated numerically and quickly for each $\kappa$ and $\|v\|_{2}$ using 1-dimensional integrals.

If we change coordinates from $t$ to $r$, then

Since $\bar{q}(r)r^{d-1}$ is proportional to the density of $\|x\|_{2},x\sim q$, we can also write this as

The distribution of $r$ here has density $\propto r^{d-1}\bar{q}(r)$. Then setting $p_{0}=q(\mathcal{NP}_{\kappa}),p_{1}=q(\mathcal{NP}_{\kappa}-v)$ yields the desired result by Eq. NP. ∎

I.9 Basic Facts about Probability Distributions

Sample a point $v$ from the unit sphere of $\|\cdot\|$

Appendix J Proof of 7.3

In this section we prove our main impossibility result, 7.3. We will assume throughout this proof that the reader is familiar with standard notions in functional analysis. Our proof will proceed in two steps.

Formally, let $(X,d_{X})$ and $(Y,d_{Y})$ be two metric spaces. We say an embedding $f:X\to Y$ has distortion $D$ if there exist positive constants $\alpha<1<\beta$ so that

for all $x_{1},x_{2}\in X$, where $\beta/\alpha\leq D$. We will first show:

This result is essentially folklore in the metric embedding community, but we include a proof for completeness.

These two lemmas together immediately imply 7.3. The rest of this section is dedicated to proofs of these two lemmas. To do so, it will first be useful to establish some regularity conditions on a variant of the growth function considered previously in this paper.

We will assume throughout this proof that $q_{2}$ is absolutely continuous with respect to $q_{1}$. The more general case can be easily handled by the theory of Radon-Nikodym derivatives and Lebesgue’s decomposition theorem. This growth function satisfies the following, basic properties, whose proofs are easy and are omitted.

Let $q_{1},q_{2},\mathcal{G}_{q_{1},q_{2}}$ be above. Then:

$\mathcal{G}_{q_{1},q_{2}}(p)$ is monotonically increasing.

$\mathcal{G}_{q_{1},q_{2}}(1)=1$, and $\mathcal{G}_{q_{1},q_{2}}(0)\geq 0$.

For any $q_{1},q_{2}\in\Delta_{d}$, the function $\mathcal{G}_{q_{1},q_{2}}$ is concave.

which we can think of as a generalized Neyman-Pearson set, for the two distributions $q_{1},q_{2}$.

Then, by classical arguments, for every $p$, the set which obtains the supremum in the definition of the growth function for that value of $p$ is given by

where $K(p)$ is defined so that $q_{1}(S_{K(p)})=p$. Therefore, for all $p$, we have that $\mathcal{G}(p)=q_{2}(S_{K(p)})$.

We will show that for all $p<p^{\prime}<p^{\prime\prime}$, the growth function satisfies

Note that for any $0\leq r\leq r^{\prime}$, we have that $\mathcal{G}(r^{\prime})-\mathcal{G}(r)=q_{2}(\Delta_{r^{\prime},r})$, where $\Delta_{r^{\prime},r}=S_{K(r^{\prime})}\setminus S_{K(r)}$. However, observe that for $p<p^{\prime}<p^{\prime\prime}$, we have that $\tfrac{dq_{2}}{dq_{1}}(x)\geq\tfrac{dq_{2}}{dq_{1}}(x^{\prime})$ for all $x\in\Delta_{p^{\prime},p}$ and $x^{\prime}\in\Delta_{p^{\prime\prime},p^{\prime}}$. But we also have

J.2 Proof of Lemma J.1

We now need another notion, introduced in Andoni et al. 2018.

A map $f:X\to Y$ between two metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ is an $(s_{1},s_{2},\tau_{1},\tau_{2})$-threshold map if it satisfies:

If $d_{X}(x_{1},x_{2})\leq s_{1},$ then $d_{Y}(f(x_{1}),f(x_{2}))\leq\tau_{1}$.

If $d_{X}(x_{1},x_{2})\geq s_{2}$, then $d_{Y}(f(x_{1}),f(x_{2}))\geq\tau_{2}$.

Our first observation is that Lemma J.4 allows us to relate the usefulness of the smoothing scheme to total variation distance:

First, consider the case where $p\geq 1/2$. Then, by concavity of $\mathcal{G}(p)$, we have that

since $\mathcal{G}(0)\geq 0$ by J.3. Therefore, we have that

The case where $p<1/2$ follows symmetrically by considering the line segment between $p$ and $1$. ∎

From this, the proof of Lemma J.7 is simple.

We first prove that it satisfies the first condition. Let $x,y$ be so that $\|x-y\|\leq\varepsilon$. Then, the robustness condition implies that

With Lemma J.7 in hand, we can now invoke a number of classical results from the theory of metric embeddings to obtain our desired result. We first use the following fact, which follows since $L_{1}$ embeds isometrically into squared-$L_{2}$.

We now require the following theorem, first proven in Andoni et al. 2018, which we reproduce below in a slightly simplified form:

Finally, we require the following theorem from Andoni et al. 2018, which we reproduce for completeness:

Let $X$ be a finite-dimensional normed space with norm $\|\cdot\|$, and let $\Delta>0$. Let $H$ be a Hilbert space with associated norm $\|\cdot\|_{H}$. Assume we have a map $f:X\to H$, such that, for some absolute constant $K>0$, and for all $x,y\in X$, we have:

$\|f(x_{1})-f(x_{2})\|_{H}\leq K\cdot\sqrt{\|x_{1}-x_{2}\|}$, and

if $\|x-y\|\geq\Delta$, then $\|f(x_{1})-f(x_{2})\|_{H}\geq 1$.

Combining J.12 and J.13 immediately yields Lemma J.1.

J.3 Proof of Lemma J.2

Here $\sigma_{1},\ldots,\sigma_{n}$ are independent Rademacher random variables. In particular, for $0<p\leq p_{0}\approx 1.8$, $A_{p}=2^{1/2-1/p}$.

where $\sigma_{1},\ldots,\sigma_{n}$ are independent Rademacher random variables.

Let $x_{ij}$ denote coordinate $j$ of $x_{i}$, i.e., $X$ is the $n\times d$ matrix whose rows are $x_{1},\ldots,x_{n}$. By Khintchine’s inequality,

Let us now consider the case $p\leq 2$. By the triangle inequality for $\|\cdot\|_{q}$, where $q=2/p\geq 1$, applied to the vectors $(|x_{1j}|^{p},|x_{2j}|^{p},\ldots,|x_{nj}|^{p})$, $j\in[d]$,

Finally, by the concavity of the function $x\mapsto x^{p}$ for $p\in(0,1]$, we have

We now have all the tools we need to prove Lemma J.2:

Combining these facts and Lemma J.15, we obtain that $\beta/\alpha\geq A_{p}C_{2}=\Omega(C_{2})$, as claimed, where $A_{p}$ is as in Lemma J.15 and J.14. ∎