# Certifying Model Accuracy under Distribution Shifts

Aounon Kumar
University of Maryland
<EMAIL_ADDRESS>
Alexander Levine
University of Maryland
<EMAIL_ADDRESS>
Tom Goldstein
University of Maryland
<EMAIL_ADDRESS>
Soheil Feizi
University of Maryland
<EMAIL_ADDRESS>

###### Abstract

Certified robustness in machine learning has primarily focused on adversarial
perturbations of the input with a fixed attack budget for each point in the
data distribution. In this work, we present provable robustness guarantees on
the accuracy of a model under bounded Wasserstein shifts of the data
distribution. We show that a simple procedure that randomizes the input of the
model within a transformation space is provably robust to distributional
shifts under the transformation. Our framework allows the datum-specific
perturbation size to vary across different points in the input distribution
and is general enough to include fixed-sized perturbations as well. Our
certificates produce guaranteed lower bounds on the performance of the model
for any (natural or adversarial) shift of the input distribution within a
Wasserstein ball around the original distribution. We apply our technique to:
(i) certify robustness against natural (non-adversarial) transformations of
images such as color shifts, hue shifts and changes in brightness and
saturation, (ii) certify robustness against adversarial shifts of the input
distribution, and (iii) show provable lower bounds (hardness results) on the
performance of models trained on so-called “unlearnable” datasets that have
been poisoned to interfere with model training.

##  1 Introduction

Machine learning models often suffer significant performance loss under minor
shifts in the data distribution that do not affect a human’s ability to
perform the same task– e.g., input noise [1, 2], image scaling, shifting and
translation [3], spatial [4] and geometric transformations [5, 6], blurring
[7, 8], acoustic corruptions [9] and adversarial perturbations [10, 11, 12,
13, 14]. Overcoming such robustness challenges is a major hurdle for deploying
these models in safety-critical applications where reliability is paramount.
Several training techniques have been developed to improve the empirical
robustness of a model to data shifts, e.g., diversifying datasets [15],
training with natural corruptions [16], data augmentations [17], contrastive
learning [18, 19, 20] and adversarial training [12, 13, 21, 22, 23]. These
methods are designed to withstand specific ways of introducing changes in
inputs (e.g., a particular adversarial attack procedure) and may break down
under a different method for generating perturbations, e.g., adversarial
defenses becoming ineffective under newer attacks [11, 24, 25, 26, 27].

Certifiable robustness, on the other hand, seeks to produce provable
guarantees on the adversarial robustness of a model which hold regardless of
the attack strategy. However, the study of provable robustness has mostly
focused on perturbations with a fixed size budget (e.g., an $\ell_{p}$-ball of
same size) for all input points [28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39, 40]. Among provable robustness methods, randomized smoothing based
procedures have been able to successfully scale up to high-dimensional
problems [28, 29, 30, 31] and adapted effectively to other domains such as
reinforcement learning [41, 42] and models with structured outputs [43].
Existing techniques do not extend to the aforementioned data shifts as the
perturbations for each input point in the distribution need not have a fixed
bound on their size. For example, stochastic changes in the input images of a
vision model caused by lighting and weather conditions may vary across time
and location. Even adversarial attacks may adjust the perturbation size
depending on the input instance.

Robustness against natural as well as adversarial shifts in the distribution
is a major challenge for deploying machine learning algorithms in safety-
critical applications such as self-driving, medical diagnosis and critical
infrastructure. Verifiable robustness to both these shifts is an important
goal in designing reliable real-world systems. A standard way to describe such
data shifts is to constrain the Wasserstein distance between the original
distribution $\mathcal{D}$ and the shifted distribution $\mathcal{\tilde{D}}$,
i.e., $W_{1}^{d}(\mathcal{D},\mathcal{\tilde{D}})\leq\epsilon$, for an
appropriate distance function $d$ and a real number $\epsilon$. It essentially
bounds the average perturbation size across the entire distribution instead of
putting a hard budget constraint for each input point. Wasserstein distance is
a standard similarity measure for probability distributions and has been
extensively used to study distribution shifts [44, 45, 46, 47]. Certifiable
robustness against Wasserstein shifts is an interesting problem to study in
its own right and a useful tool to have in the arsenal of provable robustness
techniques in machine learning.

In this work, we present an efficient procedure to make any model robust to
distributional shifts with verifiable guarantees on performance. We consider
families of parameterized distribution shifts which may include shifts in the
RBG color balance of an image, the hue/saturation balance, the
brightness/contrast, and more. To achieve distributional robustness, we
randomize the input to our model by replacing each input image with a shifted
image randomly sampled from a “smoothing” distribution. By randomizing in this
way, a given model can be made provably robust to any shifted distribution
(natural or adversarial) within a Wasserstein radius $\epsilon$ from the
original distribution.

We design robustness certificates that bound the difference between the
accuracy of the robust model under the distributions $\mathcal{D}$ and
$\mathcal{\tilde{D}}$ as a function of $\epsilon$. For a function $\bar{h}$
representing the performance of the robust model on an input-output pair
$(x,y)$, our main theoretical result in Theorem 1 shows that

$\left|\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\right|\leq\psi(\epsilon),$

where $\psi$ is a concave function that bounds the total variation between the
smoothing distributions at two input points as a function of the distance
between them (condition (3) in Section 3). Such an upper bound always exists
for any smoothing distribution because the total variation remains between
zero and one as the distance between the two input points increases. We
discuss how to find the appropriate $\psi$ for different smoothing
distributions in appendix C. The above result places a Lipschitz-like bound on
the change in performance with respect to the Wasserstein distance of the
shifted distribution.

Figure 1: Certified accuracies obtained for different natural transformations
of CIFAR-10 images such as color shifts, hue shifts and changes in brightness
and saturation. The Wasserstein distance of each distribution shift from the
original distribution is defined with respect to the corresponding distance
function.

Robustness under distribution shifts is a fundamental problem in several areas
of machine learning and our certificates could be applicable to a multitude of
learning tasks. Our method does not make any assumptions on the model or
significantly increase its computational requirements as it only needs one
sample per input to make robust predictions, making it viable for real-world
applications that use conventional neural network architectures. The sample
complexity for generating Wasserstein certificates over the entire
distribution is roughly the same as obtaining adversarial certificates for a
single input instance using existing randomized smoothing based techniques
[28, 31]. We demonstrate the usefulness of our main theoretical result
(Theorem 1) in three domains:

(i) Certifying model accuracy under natural shifts of the data distribution
(Section 5): We consider three image transformations: color shift, hue shift
and changes in brightness and saturation (SV shift). We define a parameter
space for each of these transformations in such a way that the transformations
satisfy properties, such as additive composability (equation (5)), required
for the certificates. We show that by randomizing the input of a model in the
parameter space of the transformation, we can derive distribution level
robustness certificates which guarantee that the accuracy of the model will
remain above a threshold for any shifted distribution within an
$\epsilon$-sized Wasserstein ball around the original input distribution.
Figure (1) visualizes CIFAR-10 [48] images under each of these transformations
and reports the corresponding certified accuracies obtained by our method.
Figure (2) plots the accuracy of two base models (trained on CIFAR-10 images
with and without noise in the transformation space) under a shifted
distribution and compares it with the certified accuracy of a robust model
(noise-trained model smoothed using input randomization). Note that we
commpute the empirical accuracies of the base model (dashed lines) under
random, non-adversarial perturbations in the parameter space because naturally
occurring image transformations are not adversarial in nature. An adversarial
attack that seeks to find the worst-case case perturbation could further lower
the base models’ accuracies. These results demonstrate that our certificates
are significant and non-vacuous (see appendix E for more details).

(ii) Certifying population level robustness against adversarial attacks
(Section 6): The distribution of instances generated by an adversarial attack
can also be viewed as a shift in the input distribution within a Wasserstein
bound. The Wasserstein distance of such a shift is given by the average size
of the perturbation ($\ell_{2}$-norm) added per input instance in the data
distribution. Since our certificates work for any distribution shift (natural
or adversarial) satisfying the Wasserstein bound, we can certify the accuracy
of models against adversarial attacks as well. Unlike existing certification
techniques which assume a fixed perturbation budget across all inputs [28, 29,
30, 31], our guarantees work for a more general threat model where the
adversary is allowed to choose the perturbation size for each input instance
as long as it respects the constraint on the average perturbation size over
the entire data distribution. Also, our procedure only requires one sample
from the smoothing distribution per input instance which makes computing
population level certificates significantly more efficient than existing
techniques. The certified accuracy we obtain significantly outperforms the
base model under attack (figure 5(a)).

Figure 2: Comparison between the empirical performance (dashed lines) of two
base models (trained on CIFAR-10 images with and without noise in
transformation space) and the certified accuracy (solid line) of a robust
model (noise-trained model smoothed using input randomization) under
distribution shifts. The certified accuracy often outperforms the undefended
model and remains reasonably close (almost overlaps for hue shift) to the
model trained under noise for small shifts in the distribution.

(iii) Hardness results for generating “unlearnable” datasets (Section 7): [49]
proposed a method to make regular datasets unusable for modern deep learning
models by poisoning them with adversarial perturbations to interfere with the
training of the model. The intended purpose is to increase privacy for
sensitive data such as personal images uploaded to social media sites. The
dataset is poisoned in such a way that a model that minimizes the loss on this
data distribution will have low accuracy on clean test samples. We show that
our framework can obtain verifiable lower bounds on the performance of a model
trained on such unlearnable datasets. Our certificates guarantee that the
performance of the robust model (using input randomization) will remain above
a certain threshold on the test distribution even when the base model is
trained on the poisoned dataset with a smoothing noise of suitable magnitude.
This demonstrates a fundamental limitation in producing unlearnable datasets.

##  2 Related Work

Augmenting training data with corruptions has been shown to improve empirical
robustness of machine learning models [16, 17, 12, 13]. Training a model with
randomly transformed inputs, such as blurring, cropping and rotating images,
can improve its test performance against such perturbations. However, these
methods do not seek to produce guarantees on the performance of the model with
respect to the extent of the shift in the data distribution. Our method
applies transformations during inference to produce verifiable performance
guarantees against any shift in the data distribution within the certified
Wasserstein radius. It does not depend on the underlying model’s architecture
or the training procedure and may be coupled with robust training techniques
to improve the certified guarantees.

Smoothing based approaches that aggregate the predictions on a large number of
noisy samples of the input [28, 29, 30, 31] and that use input randomization
[50] have been studied in the context of certified adversarial robustness.
Certified robustness for parameterized transformations on images also exist
[51]. These techniques produce instance-wise certificates and do not generate
guarantees on shifts in the data distribution with varying perturbation budget
across different points in the distribution. Our work also differs from
instance-wise adversarial attacks and defenses [52, 53] that use the
Wasserstein distance (instead of conventional $\ell_{p}$ distances) to measure
difference between an image and its perturbed version. In contrast, our
certificates consider the Wasserstein distance between data distributions from
which images themselves are sampled.

Robustness bounds on the population loss against Wasserstein shifts under the
$\ell_{2}$-distance [54, 55] have been derived assuming Lipschitz-continuity
of the base model. These bounds require the Lipschitz constant for the neural
network model, which becomes extremely large for deep networks. Our
certificates produce guarantees on the accuracy of an arbitrary neural model
without requiring any restrictive assumptions or a global Lipschitz bound.
Additionally, our approach can certify robustness under non-$\ell_{p}$ changes
to the input images, such as visible color shifts, for which the
$\ell_{2}$-norm of the perturbation in the image space will be very large.
Another line of work seeks to prove generalization bounds with respect to
divergence-based measures of distribution shift [56, 57, 58]. Divergence
measures become arbitrarily large (e.g. KL-divergence becomes infinity) or
attain their maximal value (e.g. total variation becomes one) when the
supports of probability distributions do not coincide. Thus, these measures
are not suitable for measuring out-of-distribution data shifts which by
definition have non-overlapping support. Wasserstein distance, on the other
hand, uses the spatial separation between two distributions to meaningfully
measure their distance even when their supports are disjoint.

##  3 Preliminaries and Notations

Let $\mathcal{D}$ be the data distribution representing a machine learning
task over an input space $\mathcal{X}$ and an output space $\mathcal{Y}$. We
define a distribution shift as a covariate shift that only changes the
distribution of the input element in samples
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ drawn from $\mathcal{D}$ and leaves the
output element unchanged, i.e., $(x,y)$ changes to $(\tilde{x},y)$ under the
shift. Given a distance function
$d_{\mathcal{X}}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0}$
over the input space, we define the following distance function between two
tuples $\tau_{1}=(x_{1},y_{1})$ and $\tau_{2}=(x_{2},y_{2})$ to capture the
above shift:

$d(\tau_{1},\tau_{2})=\begin{cases}d_{\mathcal{X}}(x_{1},x_{2})&\text{if
}y_{1}=y_{2}\\\ \infty&\text{otherwise.}\end{cases}$ (1)

Let $\mathcal{\tilde{D}}$ denote a shift in the original data distribution
$\mathcal{D}$ such that the Wasserstein distance under $d$ between
$\mathcal{D}$ and $\mathcal{\tilde{D}}$ is bounded by $\epsilon$ (i.e.,
$W_{1}^{d}(\mathcal{D},\mathcal{\tilde{D}})\leq\epsilon$). Define the set of
all joint probability distributions with marginals $\mu_{\mathcal{D}}$ and
$\mu_{\tilde{\mathcal{D}}}$ as follows:

$\displaystyle\Gamma(\mathcal{D},\mathcal{\tilde{D}})=\bigg{\\{}\gamma\;\text{
s.t.
}\int_{\mathcal{X}\times\mathcal{Y}}\gamma(\tau_{1},\tau_{2})d\tau_{2}=\mu_{\mathcal{D}}(\tau_{1})\text{
and
}\int_{\mathcal{X}\times\mathcal{Y}}\gamma(\tau_{1},\tau_{2})d\tau_{1}=\mu_{\mathcal{\tilde{D}}}(\tau_{2})\bigg{\\}}.$

The Wasserstein bound implies that there exists an element
$\gamma^{*}\in\Gamma(\mathcal{D},\mathcal{\tilde{D}})$ such that

$\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[d(\tau_{1},\tau_{2})]\leq\epsilon.$
(2)

Let $\mathcal{S}:\mathcal{X}\rightarrow\Delta(\mathcal{X})$ be a function
mapping each element $x\in\mathcal{X}$ to a smoothing distribution
$\mathcal{S}(x)$, where $\Delta(\mathcal{X})$ is the set of all probability
distributions over $\mathcal{X}$. For example, smoothing with an isometric
Gaussian noise distribution with variance $\sigma^{2}$ can be denoted as
$\mathcal{S}(x)=\mathcal{N}(x,\sigma^{2}I)$. Let the total variation between
the smoothing distributions at two points $x_{1}$ and $x_{2}$ be bounded by a
concave increasing function $\psi$ of the distance between them, i.e.,

$\operatorname{\mathsf{TV}}(\mathcal{S}(x_{1}),\mathcal{S}(x_{2}))\leq\psi(d_{\mathcal{X}}(x_{1},x_{2})).$
(3)

For example, when the distance function $d$ is the $\ell_{2}$-norm of the
difference of $x_{1}$ and $x_{2}$, and the smoothing distribution is an
isometric Gaussian $\mathcal{N}(0,\sigma^{2}I)$ with variance $\sigma^{2}$,
$\psi(\cdot)=\operatorname{erf}(\cdot/2\sqrt{2}\sigma)$ is a valid upper bound
on the above total variation that is concave in the positive domain (see
appendix C for more examples).

Consider a function $h:\mathcal{X}\times\mathcal{Y}\rightarrow[0,1]$ that
represents the accuracy of a model. For example, in the case of a classifier
$\mu:\mathcal{X}\rightarrow\mathcal{Y}$ that maps inputs from space
$\mathcal{X}$ to a class label in $\mathcal{Y}$,
$h(x,y)\coloneqq\mathbf{1}\\{\mu(x)=y\\}$ could indicate whether the
prediction of $\mu$ on $x$ matches the desired output label $y$ or not.
Another example could be that of segmentation/detection tasks, where $y$
represents a region on an input image $x$. Then,
$h(x,y)\coloneqq\text{IoU}(\mu(x),y)$111IoU stands for Intersection over
Union. could represent the overlap between the predicted regions $\mu(x)$ and
the ground truth $y$. The overall accuracy of the model $\mu$ under
$\mathcal{D}$ is then given by $\mathbb{E}_{(x,y)\in\mathcal{D}}[h(x,y)]$. We
define a robust model $\bar{\mu}(x)=\mu(x^{\prime})$ where
$x\sim\mathcal{S}(x)$. Our goal is to bound the difference in the expected
performance of the robust model between the original distribution
$\mathcal{D}$ and the shifted distribution $\mathcal{\tilde{D}}$. We define a
smoothed version of the function $h$ to represent the performance of
$\bar{\mu}$ on a given input-output pair $(x,y)$:

$\bar{h}(x,y)=\mathbb{E}_{x^{\prime}\sim\mathcal{S}(x)}[h(x^{\prime},y)].$ (4)

Our main theoretical result (Theorem 1) bounds the difference between the
expected value of $\bar{h}$ under $\mathcal{D}$ and $\mathcal{\tilde{D}}$
using the function $\psi$ and the Wasserstein bound $\epsilon$.

###  3.1 Parameterized Transformations

We apply our distributional robustness certificates to certify the accuracy of
an image classifier under natural transformations of the images such as color
shifts, hue shifts and changes in brightness and saturation. We model each of
them as a parameterized transformation $\mathcal{T}:\mathcal{X}\times
P\rightarrow\mathcal{X}$ which is a function over the input/image space
$\mathcal{X}$ and a parameter space $P$ which takes an image $x\in\mathcal{X}$
and a parameter vector $\theta\in P$ and outputs a transformed image
$x^{\prime}=\mathcal{T}(x,\theta)\in\mathcal{X}$. An example of such a
transformation could be a color shift in an RGB image produced by scaling the
intensities in the red, green and blue channels
$x=(\\{x_{ij}^{R}\\},\\{x_{ij}^{G}\\},\\{x_{ij}^{B}\\})$ defined as
$\mathsf{CS}(x,\theta)=(2^{\theta_{R}}\\{x_{ij}^{R}\\},2^{\theta_{G}}\\{x_{ij}^{G}\\},2^{\theta_{B}}\\{x_{ij}^{B}\\})/\mathsf{MAX}$
for a tuple $\theta=(\theta_{R},\theta_{G},\theta_{B})$, where $\mathsf{MAX}$
is the maximum of all the RGB values after scaling. Another example could be
vector translations $\mathsf{VT}(x,\theta)=x+\theta$. In order to apply
randomized smoothing, we assume that the transformation returns $x$ if the
parameters are all zero, i.e., $\mathcal{T}(x,0)=x$ and that the composition
of two transformations with parameters $\theta_{1}$ and $\theta_{2}$ is a
transformation with parameters $\theta_{1}+\theta_{2}$ (additive
composability), i.e.,

$\mathcal{T}(\mathcal{T}(x,\theta_{1}),\theta_{2})=\mathcal{T}(x,\theta_{1}+\theta_{2}).$
(5)

Given a norm $\|\cdot\|$ in the parameter space $P$, we define a distance
function in the input space $\mathcal{X}$ as follows:

$d_{\mathcal{T}}(x_{1},x_{2})=\begin{cases}\min\\{\|\theta\|\mid\mathcal{T}(x_{1},\theta)=x_{2}\\}&\text{if
}\exists\theta\text{ s.t. }\mathcal{T}(x_{1},\theta)=x_{2}\\\
\infty&\text{otherwise.}\end{cases}$ (6)

Now, define a smoothing distribution
$\mathcal{S}(x)=\mathcal{T}(x,\mathcal{Q}(0))$ for some distribution
$\mathcal{Q}$ in the parameter space of $\mathcal{T}$ such that
$\forall\theta\in P,\mathcal{Q}(\theta)=\theta+\mathcal{Q}(0)$ is the
distribution of $\theta+\delta$ where $\delta\sim\mathcal{Q}(0)$, and
$\operatorname{\mathsf{TV}}(\mathcal{Q}(0),\mathcal{Q}(\theta))\leq\psi(\|\theta\|)$
for a concave function $\psi$. For example,
$\mathcal{Q}(\cdot)=\mathcal{N}(\cdot,\sigma^{2}I)$ satisfies these properties
for $\psi(\cdot)=\operatorname{erf}(\cdot/2\sqrt{2}\sigma)$. Then, the
following lemma holds (proof in appendix B):

######  Lemma 1.

For two points $x_{1},x_{2}\in\mathcal{X}$ such that
$d_{\mathcal{T}}(x_{1},x_{2})$ is finite,

$\operatorname{\mathsf{TV}}(\mathcal{S}(x_{1}),\mathcal{S}(x_{2}))\leq\psi(d_{\mathcal{T}}(x_{1},x_{2})).$

##  4 Certified Distributional Robustness

In this section, we state our main theoretical result showing that the
difference in the expectation of the smoothed performance function $\bar{h}$
defined in equation (4) under the original distribution $\mathcal{D}$ and the
shifted distribution $\mathcal{\tilde{D}}$ can be bounded by the Wasserstein
distance between $\mathcal{D}$ and $\mathcal{\tilde{D}}$. Given a concave
upper bound $\psi$ on the total variation between the smoothing distributions
at two points $x_{1}$ and $x_{2}$ (condition (3)), the following theorem
holds.

######  Theorem 1.

Given a function $h:\mathcal{X}\times\mathcal{Y}\rightarrow[0,1]$, define its
smoothed version as
$\bar{h}(x,y)=\mathbb{E}_{x^{\prime}\sim\mathcal{S}(x)}[h(x^{\prime},y)]$.
Then,

$\left|\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\right|\leq\psi(\epsilon).$

We defer the proof to the appendix. The intuition behind the above guarantee
is that if the overlap between the smoothing distributions between two
individual points does not decrease rapidly with the distance between them,
then the overlap between $\mathcal{D}$ and $\mathcal{\tilde{D}}$ augmented
with the smoothing distribution remains high when the Wasserstein distance
between them is small. Thus, for a Wasserstein shift of $\epsilon$, the
accuracy of the model can be bounded as
$\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\geq\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\psi(\epsilon)$.
But, in practice, we may only estimate
$\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]$ using a
finite number of samples. In our experiments, we compute a confidence lower
bound using the Clopper-Pearson method that holds with $1-\alpha$ probability
(for some $\alpha>0$, usually 0.001) on the robust model’s accuracy on the
original distribution [59]. In the following sections, we will demonstrate the
usefulness of this fundamental result in several applications.

##  5 Certified Accuracy against Natural Transformations

We certify the accuracy of a ResNet-110 model trained on CIFAR-10 images under
three types of image transformations: color shifts, hue shifts and variation
in brightness and saturation (SV shift). We train our models with varying
levels of noise in the transformation space and evaluate their certified
performance using smoothing distributions of different noise levels. For color
and SV shifts, we show how the certified accuracy varies as a function of the
Wasserstein distance as we change the training and smoothing noise. For hue
shift, we use a smoothing distribution (with fixed noise level) that is
invariant to rotations in hue space and the certified accuracy remains
constant with respect to the corresponding Wasserstein distance. Training each
model for 90 epochs takes a few hours on a single NVIDIA GeForce RTX 2080 Ti
GPU and computing the distribution level Wasserstein certificates using
$10^{5}$ samples with 99.9% confidence takes about 25 seconds.

Figure 3: Certified accuracy under color shifts. Each plot corresponds to a
particular training noise and each curve corresponds to a particular smoothing
noise.

###  5.1 Color Shifts

Denote an RGB image $x$ as an $H\times W$ array of pixels where the red, green
and blue components of the pixel in the $i$th row and $j$th column are given
by the tuple $x_{ij}=(r,g,b)_{ij}$. Let $r_{\max},g_{\max}$ and $b_{\max}$ be
the maximum values of the red, green and blue channels, respectively. Assume
that the RGB values are in the interval $[0,1]$ normalized such that the
maximum over all intensity values is one, i.e.,
$\max(r_{\max},g_{\max},b_{\max})=1$. Define a color shift of the image $x$
for a parameter vector $\theta\in\mathbb{R}^{3}$ as

$\mathsf{CS}(x,\theta)=\left\\{\frac{(2^{\theta_{R}}r,2^{\theta_{G}}g,2^{\theta_{B}}b)_{ij}}{\max(2^{\theta_{R}}r_{\max},2^{\theta_{G}}g_{\max},2^{\theta_{B}}b_{\max})}\right\\}^{H\times
W}$

which scales the intensities of each channel by the corresponding component of
$\theta$ raised to the power of two and then normalizes the scaled image so
that the maximum intensity is one. For example, $\theta=(1,-1,0)$ would first
double all the red intensities, halve the green intensities and leave the blue
intensities unchanged, and then, normalize the image so that the maximum
intensity value over all the channels is equal to one. The above
transformation can be shown to satisfy the additive composability property in
condition (5). See appendix D for a proof.

Given an image $x$, we define a smoothing distribution around $x$ in the
parameter space as $\mathsf{CS}(x,\delta)$ where
$\delta\sim\mathcal{N}(0,\sigma^{2}I_{3\times 3})$. Define the distance
function $d_{\mathsf{CS}}$ as described in (6) using the $\ell_{2}$-norm in
the parameter space. For a distribution $\mathcal{\tilde{D}}$ within a
Wasserstein distance of $\epsilon$ from the original distribution
$\mathcal{D}$, the performance of the smoothed model on $\mathcal{\tilde{D}}$
can be bounded as
$\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\geq\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\operatorname{erf}(\epsilon/2\sqrt{2}\sigma)$.
Figure 3 plots the certified accuracy under color shift with respect to the
Wasserstein bound $\epsilon$ for different values of training and smoothing
noise. In appendix G, we consider a smoothing distribution that randomly picks
one color channel achieving a constant certified accuracy of 87.1% with
respect to the Wasserstein bound $\epsilon$.

###  5.2 Hue Shift

Any RGB image can be alternatively represented in the HSV image format by
mapping the $(r,g,b)$ tuple for each pixel to a point $(h,s,v)$ in a
cylindrical coordinate system where the values $h,s$ and $v$ represent the
hue, saturation and brightness (value) of the pixel. The mapping from the RGB
coordinate to the HSV coordinate takes the $[0,1]^{3}$ color cube and
transforms it into a cylinder of unit radius and height. The hue values are
represented as angles in $[0,2\pi)$ and the saturation and brightness values
are in $[0,1]$. Define a hue shift of an $H\times W$ sized image $x$ by an
angle $\theta\in[-\pi,\pi]$ in the HSV space that rotates each hue value by an
angle $\theta$ and wraps it around to the $[0,2\pi)$ range. In appendix F, we
show that the certified accuracy under hue shifts does not depend on the
Wasserstein distance of the shifted distribution and report the certified
accuracies obtained by various base models trained under different noise
levels

Figure 4: Certified accuracy under brightness and saturation changes. Each
plot corresponds to a particular training noise and each curve corresponds to
a particular smoothing noise.

###  5.3 Brightness and Saturation Changes

Define the following transformation in the HSV space of an image that shifts
the mean of the saturation (S) and brightness (V) values for each pixel by a
certain amount:

$\displaystyle\mathsf{SV}(x,\theta)=\Bigg{\\{}\bigg{(}h,$
$\displaystyle\frac{s+(2^{\theta_{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}},\frac{v+(2^{\theta_{V}}-1)v_{\operatorname{mean}}}{\mathsf{MAX}}\bigg{)}_{ij}\Bigg{\\}}^{H\times
W}$

where $s_{\operatorname{mean}},s_{\max},v_{\operatorname{mean}}$ and
$v_{\max}$ are the means and maximums of the saturation and brightness values
respectively before the shift is applied and
$\mathsf{MAX}=\max(s_{\max}+(2^{\theta_{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{V}}-1)v_{\operatorname{mean}})$
is the maximum of the brightness and saturation values after the shift.
Similar to color shift , the $\mathsf{SV}$ transformation can also be shown to
satisfy additive composability (appendix D).

Figure 4 plots the certified accuracy under saturation and brightness changes
with respect to the Wasserstein bound $\epsilon$ for different values of
training and smoothing noise. The smoothing distribution for this
transformation is a uniform in the range $[0,a]^{2}$ in the parameter space,
the distance function is the $\ell_{1}$-norm and
$\psi(\epsilon)=\min(\epsilon/a,1)$.

##  6 Population-Level Certificates against Adversarial Attacks

In this section, we consider the $\ell_{2}$-distance in the image space to
measure the Wasserstein distance instead of a parameterized transformation. We
use a pixel-space Gaussian smoothing distribution
$\mathcal{S}(x)=\mathcal{N}(x,\sigma^{2}I)$ to obtain robustness guarantees
under this metric. To motivate this, consider an adversarial attacker
$\text{Adv}:\mathcal{X}\to\mathcal{X}$, which takes an image $x$ and computes
perturbation $\text{Adv}(x)$ to try and fool a model into misclassifying the
input. If $(x,y)\sim\mathcal{D}$, define $\mathcal{\tilde{D}}$ to be the
distribution of the tuples $(\text{Adv}(x),y)$. Defining $d$ in 1 using
$d_{\mathcal{X}}=\ell_{2}$, it is easy to show that:

$W_{1}^{d}(\mathcal{D},\mathcal{\tilde{D}})\leq\mathbb{E}_{x\sim\mathcal{D}}[\|\text{Adv}(x)-x\|_{2}]$
(7)

So, if the average magnitude of perturbations induced by Adv is less than
$\epsilon$ (i.e., $[\|\text{Adv}(x)-x\|_{2}]<\epsilon$), then
$W_{1}^{d}(\mathcal{D},\mathcal{\tilde{D}})<\epsilon$ which means that we can
apply Theorem 1: the gap in the expected accuracy between $x\sim\mathcal{D}$
and $\text{Adv}(x)\sim\mathcal{\tilde{D}}$ will be at most $\psi(\epsilon)$.
Note that, under this threat model, Adv can be strategic in its use of the
average perturbation “budget”: if a certain point $x$ would require a very
large perturbation to be misclassified, or is already misclassified, then
$\text{Adv}(x)$ can save the budget by simply returning $x$ and use it to
attack a greater number of more vulnerable samples.

Note that our method differs from sample-wise certificates against $\ell_{2}$
adversarial attacks which use randomized smoothing, such as [28].
Specifically, we use only one smoothing perturbation (and therefore only one
forward pass) per sample. Our guarantees are on the overall accuracy of the
classifier, not on the stability of any particular prediction. Finally, as
discussed, our threat model is different, because we allow the adversary to
strategically choose which samples to attack, with the certificate dependent
on the Wasserstein magnitude of the distributional attack.

(a) $\ell_{2}$ adversarial attacks.

(b) Unlearnability.

Figure 5: Distributional certificates against (a) adversarial attacks and (b)
unlearnable datasets. The smoothing noise used in part (b) is $0.4$. Results
for other values are reported in the appendix.

Results on CIFAR-10 are presented in Figure 5(a). We use ResNet-110 models
trained under noise from [28]. For the undefended baseline, (on an undefended
classifier $g$), we first apply a Carlini and Wagner $\ell_{2}$ attack to each
sample $x$ [11], generating adversarial examples $x^{\prime}$. Define this
attack as the function $CW(\cdot)$, such that $x^{\prime}=CW(x,y;g)$, where
$y$ is the ground-truth label. (If the attack fails, $CW(x,y;g)=x$). We then
define a strategic adversary $\text{Adv}_{\gamma}$ that returns $CW(x,y;g)$ if
$\|CW(x,y;g)-x\|_{2}<\gamma$, otherwise it returns $x$. By not attacking
samples which would require the largest $\ell_{2}$ perturbations to cause
misclassification, this attack efficiently balances maximizing
misclassification rate with minimizing the Wasserstein distance between
$\mathcal{D}$ and $\mathcal{\tilde{D}}$. The threshold parameter $\gamma$
controls the tradeoff between misclassifcation rate and the Wasserstein
perturbation magnitude. The ‘Undefended’ baseline in Figure 5(a) plots the
accuracy on attacked test samples under adversary $\text{Adv}_{\gamma}$, for a
sweep of values of $\gamma$, against an upper bound on the Wasserstein
distance, given by
$\mathbb{E}_{x\sim\mathcal{D}_{test}}[\|\text{Adv}_{\gamma}(x)-x\|_{2}]$.
(Note that here we are using the finite test distribution
$\mathcal{D}_{test}$, so this is technically an upper bound on
$W_{1}^{d}(\mathcal{D}_{test},\mathcal{\tilde{D}}_{test})$). We can observe a
large gap between this undefended model performance under attack, and the
certified robustness of our model, showing that our certificate is highly
nonvacuous. In the supplemental material, we include results to show the
empirical robustness of the smoothed classifiers under an “adaptive” attack,
based on the attack on sample-wise $\ell_{2}$ smoothing proposed by [31].

##  7 Hardness Results on Unlearnability

In this section, we show that the pixel-space $\ell_{2}$-Wasserstein
distributional robustness certificate shown above can also be applied to
establish a hardness result in creating provably “unlearnable” datasets [49].
In these datasets, every sample of the released data is “poisoned” so that the
accuracy of a classifier trained on this data is high on both the training set
and any other (i.e., validation) set split from the released dataset, while
the test accuracy on non-poisoned samples drawn from the same distribution is
low. This technique has legitimate applications, such as protecting privacy by
preventing one’s personal data from being learned, but may also have malicious
uses (e.g., a malicious actor could sell a useless classifier that
nevertheless has good performance on a provided validation set.) We can view
the “clean” data distribution as $\mathcal{D}$, and the distribution of the
poisoned samples (i.e., the unlearnable distribution) as
$\mathcal{\tilde{D}}$. If the magnitude of the perturbations is limited,
Theorem 1 implies that the accuracy on $\mathcal{D}$ and $\mathcal{\tilde{D}}$
must be similar, implying that our algorithm is provably resistant to
unlearnablility attacks, effectively establishing provable hardness results to
create unlearnable datasets.

In order to apply our guarantees, we must make a few modifications to the
attack proposed in [49]. First, we bound each poisoning perturbation on the
released dataset to within an $\epsilon$-radius $\ell_{2}$ ball, rather than
an $\ell_{\infty}$ ball. From Equation 7, this ensures that
$W_{1}^{d}(\mathcal{D},\mathcal{\tilde{D}})\leq\epsilon.$

Second, we consider an “offline” version of the attack. In the original attack
[49], perturbations for the entire dataset are optimized simultaneously with a
proxy classifier model in an iterative manner. This makes the perturbations
applied to each sample non-I.I.D., (because they may depend on each other
through proxy-model parameters) which makes deriving generalizable guarantees
for it difficult. However, this simultaneous proxy-model training and
poisoning may not always represent a realistic threat model. In particular, an
actor releasing “unlearnable” data at scale may not be able to constantly
update the proxy model being used. For example, consider an “unlearnability”
module in a camera, which would make photos unusable as training data. Because
the camera itself has access to only a small number of photographs, such a
module would likely rely on a fixed, pre-trained proxy classifier model to
create the poisoning perturbations. To model this, we consider a threat model
where the proxy classifier is first optimized using an unreleased dataset: the
released “unlearnable” samples are then perturbed independently using this
fixed proxy model. We see in Figure 5(b) that our modified attack is still
highly effective at making data unlearnable, as shown by the high validation
and low test accuracy of the undefended baseline.

In Figure 5(b), we also show the performance of our algorithm on CIFAR-10
under unlearnability attack. We use an “adaptive” attack against the smoothed
classifier, inspired by [31]: details are presented in the appendix. The
defense is empirically effective at thwarting unlearnability: the poisoned
validation and clean test sets have similar accuracies, even at large
perturbation size. However, overall accuracy is reduced substantially.
Certified lower bounds on the clean accuracy, computed from the poisoned
validation accuracy using Theorem 1, are also given.

##  8 Conclusion

In this work, we show that it is possible to certify distributional robustness
under natural as well as adversarial shifts in the data distribution. Our
method can make any model provably robust without increasing its sample
complexity. We certify accuracy with respect to the Wasserstein distance of
the distribution shift which is a more suitable metric for out-of-distribution
shifts than previously considered divergence measures such as KL-divergence
and total variation. The robustness guarantees we derive do not make any
assumptions on the base model such as Lipschitz-continuity, making our method
suitable for most real-world applications using deep neural network
architectures.

We show that by appropriately parameterizing the transformation space, one can
obtain meaningful certificates for natural shifts that have a high
perturbation size in image space. However, the distance functions we consider,
such as $\ell_{2}$ and parameterized transformations, are predefined non-
learnable functions which may not be suitable for modelling more sophisticated
data shifts such as perceptual changes. A future direction of research could
be to adapt our distributional certificates for more difficult domains such as
weather patterns, user preferences, facial expressions, etc. We do not foresee
any immediate negative impact of our work on society. It seeks to make machine
learning models more robust and reliable against unexpected data shifts in the
real world.

##  9 Acknowledgements

This project was supported in part by NSF CAREER AWARD 1942230, a grant from
NIST 60NANB20D134, HR001119S0026 (GARD), ONR YIP award N00014-22-1-2271, and
Army Grant No. W911NF2120076.

## References

  * Dodge and Karam [2016] Samuel F. Dodge and Lina J. Karam.  Understanding how image quality affects deep neural networks.  _CoRR_ , abs/1604.04004, 2016.  URL http://arxiv.org/abs/1604.04004.
  * Geirhos et al. [2018] Robert Geirhos, Carlos R. Medina Temme, Jonas Rauber, Heiko H. Schütt, Matthias Bethge, and Felix A. Wichmann.  Generalisation in humans and deep neural networks.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 7549–7561, 2018.
  * Azulay and Weiss [2019] Aharon Azulay and Yair Weiss.  Why do deep convolutional networks generalize so poorly to small image transformations?  _Journal of Machine Learning Research_ , 20(184):1–25, 2019.  URL http://jmlr.org/papers/v20/19-519.html.
  * Engstrom et al. [2019] Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry.  Exploring the landscape of spatial robustness.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1802–1811. PMLR, 2019\.  URL http://proceedings.mlr.press/v97/engstrom19a.html.
  * Fawzi and Frossard [2015] Alhussein Fawzi and Pascal Frossard.  Manitest: Are classifiers really invariant?  _CoRR_ , abs/1507.06535, 2015.  URL http://arxiv.org/abs/1507.06535.
  * Alcorn et al. [2019] Michael A. Alcorn, Qi Li, Zhitao Gong, Chengfei Wang, Long Mai, Wei-Shinn Ku, and Anh Nguyen.  Strike (with) a pose: Neural networks are easily fooled by strange poses of familiar objects.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pages 4845–4854. Computer Vision Foundation / IEEE, 2019.  doi: 10.1109/CVPR.2019.00498.
  * Vasiljevic et al. [2016] Igor Vasiljevic, Ayan Chakrabarti, and Gregory Shakhnarovich.  Examining the impact of blur on recognition by convolutional networks.  _CoRR_ , abs/1611.05760, 2016.  URL http://arxiv.org/abs/1611.05760.
  * Zhou et al. [2017] Yiren Zhou, Sibo Song, and Ngai-Man Cheung.  On classification of distorted images with deep convolutional neural networks.  _CoRR_ , abs/1701.01924, 2017.  URL http://arxiv.org/abs/1701.01924.
  * Pearce and Hirsch [2000] David J. B. Pearce and Hans-Günter Hirsch.  The aurora experimental framework for the performance evaluation of speech recognition systems under noisy conditions.  In _INTERSPEECH_ , 2000.
  * Szegedy et al. [2014] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014.
  * Carlini and Wagner [2017] Nicholas Carlini and David A. Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In _Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec@CCS 2017, Dallas, TX, USA, November 3, 2017_ , pages 3–14, 2017.
  * Goodfellow et al. [2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.
  * Madry et al. [2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * Biggio et al. [2013] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli.  Evasion attacks against machine learning at test time.  In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný, editors, _Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III_ , volume 8190 of _Lecture Notes in Computer Science_ , pages 387–402. Springer, 2013.  doi: 10.1007/978-3-642-40994-3\\_25.  URL https://doi.org/10.1007/978-3-642-40994-3_25.
  * Taori et al. [2020] Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt.  Measuring robustness to natural distribution shifts in image classification.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Hendrycks and Dietterich [2019] Dan Hendrycks and Thomas G. Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=HJz6tiCqYm.
  * Yang et al. [2019] Fanny Yang, Zuowen Wang, and Christina Heinze-Deml.  Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 14757–14768, 2019.
  * Kim et al. [2020] Minseon Kim, Jihoon Tack, and Sung Ju Hwang.  Adversarial self-supervised contrastive learning.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Radford et al. [2021] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning transferable visual models from natural language supervision.  In Marina Meila and Tong Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 8748–8763. PMLR, 2021.  URL http://proceedings.mlr.press/v139/radford21a.html.
  * Ge et al. [2021] Songwei Ge, Shlok Mishra, Haohan Wang, Chun-Liang Li, and David W. Jacobs.  Robust contrastive learning using negative samples with diminished semantics.  _CoRR_ , abs/2110.14189, 2021.  URL https://arxiv.org/abs/2110.14189.
  * Tramèr and Boneh [2019] Florian Tramèr and Dan Boneh.  Adversarial training and robustness for multiple perturbations.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 5858–5868, 2019.
  * Shafahi et al. [2019] Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein.  Adversarial training for free!  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pages 3353–3364, 2019.
  * Maini et al. [2020] Pratyush Maini, Eric Wong, and J. Zico Kolter.  Adversarial robustness against the union of multiple perturbation models.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 6640–6650. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/maini20a.html.
  * Athalye et al. [2018] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 274–283, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Uesato et al. [2018] Jonathan Uesato, Brendan O’Donoghue, Pushmeet Kohli, and Aäron van den Oord.  Adversarial risk and the dangers of evaluating against weak attacks.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 5032–5041, 2018.
  * Laidlaw and Feizi [2019] Cassidy Laidlaw and Soheil Feizi.  Functional adversarial attacks.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pages 10408–10418, 2019.  URL http://papers.nips.cc/paper/9228-functional-adversarial-attacks.
  * Laidlaw et al. [2021] Cassidy Laidlaw, Sahil Singla, and Soheil Feizi.  Perceptual adversarial robustness: Defense against unseen threat models.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net, 2021.  URL https://openreview.net/forum?id=dFwBosAcJkN.
  * Cohen et al. [2019] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1310–1320, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * Lécuyer et al. [2019] Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana.  Certified robustness to adversarial examples with differential privacy.  In _2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019_ , pages 656–672, 2019.
  * Li et al. [2019] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin.  Certified adversarial robustness with additive noise.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pages 9459–9469, 2019.
  * Salman et al. [2019] Hadi Salman, Jerry Li, Ilya P. Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pages 11289–11300, 2019.
  * Gowal et al. [2018] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models, 2018.
  * Huang et al. [2019] Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krishnamurthy Dvijotham, and Pushmeet Kohli.  Achieving verified robustness to symbol substitutions via interval bound propagation.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pages 4081–4091, 2019.  doi: 10.18653/v1/D19-1419.  URL https://doi.org/10.18653/v1/D19-1419.
  * Wong and Kolter [2018] Eric Wong and J. Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pages 5283–5292, 2018.
  * Raghunathan et al. [2018] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang.  Semidefinite relaxations for certifying robustness to adversarial examples.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 10900–10910, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Singla and Feizi [2019] Sahil Singla and Soheil Feizi.  Robustness certificates against adversarial examples for relu networks.  _CoRR_ , abs/1902.01235, 2019.
  * Singla and Feizi [2020] Sahil Singla and Soheil Feizi.  Second-order provable defenses against adversarial attacks.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 8981–8991. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/singla20a.html.
  * Levine and Feizi [2021] Alexander Levine and Soheil Feizi.  Improved, deterministic smoothing for L1 certified robustness.  _CoRR_ , abs/2103.10834, 2021.  URL https://arxiv.org/abs/2103.10834.
  * Levine and Feizi [2020a] Alexander Levine and Soheil Feizi.  (de)randomized smoothing for certifiable defense against patch attacks.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020a.
  * Levine and Feizi [2020b] Alexander Levine and Soheil Feizi.  Robustness certificates for sparse adversarial attacks by randomized ablation.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 4585–4593. AAAI Press, 2020b.  URL https://aaai.org/ojs/index.php/AAAI/article/view/5888.
  * Kumar et al. [2021] Aounon Kumar, Alexander Levine, and Soheil Feizi.  Policy smoothing for provably robust reinforcement learning.  _CoRR_ , abs/2106.11420, 2021.  URL https://arxiv.org/abs/2106.11420.
  * Wu et al. [2021] Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li.  CROP: certifying robust policies for reinforcement learning through functional smoothing.  _CoRR_ , abs/2106.09292, 2021.  URL https://arxiv.org/abs/2106.09292.
  * Kumar and Goldstein [2021] Aounon Kumar and Tom Goldstein.  Center smoothing: Certified robustness for networks with structured outputs.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Courty et al. [2017] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy.  Joint distribution optimal transportation for domain adaptation.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 3730–3739, 2017.
  * Damodaran et al. [2018] Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty.  Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation.  In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, _Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part IV_ , volume 11208 of _Lecture Notes in Computer Science_ , pages 467–483. Springer, 2018.  doi: 10.1007/978-3-030-01225-0\\_28.  URL https://doi.org/10.1007/978-3-030-01225-0_28.
  * Lee and Raginsky [2018] Jaeho Lee and Maxim Raginsky.  Minimax statistical learning with wasserstein distances.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 2692–2701, 2018.
  * Wu et al. [2019] Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary C. Lipton.  Domain adaptation with asymmetrically-relaxed distribution alignment.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6872–6881. PMLR, 2019\.  URL http://proceedings.mlr.press/v97/wu19f.html.
  * [48] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research).  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Huang et al. [2021] Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani, James Bailey, and Yisen Wang.  Unlearnable examples: Making personal data unexploitable.  In _ICLR_ , 2021.
  * Pinot et al. [2021] Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Gouy-Pailler, Yann Chevaleyre, and Jamal Atif.  On the robustness of randomized classifiers to adversarial examples.  _CoRR_ , abs/2102.10875, 2021.  URL https://arxiv.org/abs/2102.10875.
  * Fischer et al. [2020] Marc Fischer, Maximilian Baader, and Martin T. Vechev.  Certified defense to image transformations via randomized smoothing.  In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Wong et al. [2019] Eric Wong, Frank R. Schmidt, and J. Zico Kolter.  Wasserstein adversarial examples via projected sinkhorn iterations.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6808–6817. PMLR, 2019\.  URL http://proceedings.mlr.press/v97/wong19a.html.
  * Levine and Feizi [2019] Alexander Levine and Soheil Feizi.  Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks, 2019.
  * Shen et al. [2018] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu.  Wasserstein distance guided representation learning for domain adaptation.  In Sheila A. McIlraith and Kilian Q. Weinberger, editors, _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018_ , pages 4058–4065. AAAI Press, 2018.  URL https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17155.
  * Sinha et al. [2018] Aman Sinha, Hongseok Namkoong, and John C. Duchi.  Certifying some distributional robustness with principled adversarial training.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.  URL https://openreview.net/forum?id=Hk6kPgZA-.
  * Ben-David et al. [2006] Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira.  Analysis of representations for domain adaptation.  In Bernhard Schölkopf, John C. Platt, and Thomas Hofmann, editors, _Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006_ , pages 137–144. MIT Press, 2006.  URL https://proceedings.neurips.cc/paper/2006/hash/b1b0432ceafb0ce714426e9114852ac7-Abstract.html.
  * Zhao et al. [2019] Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon.  On learning invariant representations for domain adaptation.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 7523–7532. PMLR, 2019\.  URL http://proceedings.mlr.press/v97/zhao19a.html.
  * Mehra et al. [2021] Akshay Mehra, Bhavya Kailkhura, Pin-Yu Chen, and Jihun Hamm.  Understanding the limits of unsupervised domain adaptation via data poisoning.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 17347–17359, 2021.  URL https://proceedings.neurips.cc/paper/2021/hash/90cc440b1b8caa520c562ac4e4bbcb51-Abstract.html.
  * Clopper and Pearson [1934] C. J. Clopper and E. S. Pearson.  The use of confidence or fiducial limits illustrated in the case of the binomial.  _Biometrika_ , 26(4):404–413, 1934.  ISSN 00063444.  URL http://www.jstor.org/stable/2331986.
  * Nicolae et al. [2018] Maria-Irina Nicolae, Mathieu Sinn, Minh Ngoc Tran, Beat Buesser, Ambrish Rawat, Martin Wistuba, Valentina Zantedeschi, Nathalie Baracaldo, Bryant Chen, Heiko Ludwig, Ian Molloy, and Ben Edwards.  Adversarial robustness toolbox v1.2.0.  _CoRR_ , 1807.01069, 2018.  URL https://arxiv.org/pdf/1807.01069.

##  Appendix A Proof of Theorem 1

######  Statement.

Given a function $h:\mathcal{X}\times\mathcal{Y}\rightarrow[0,1]$, define its
smoothed version as
$\bar{h}(x,y)=\mathbb{E}_{x^{\prime}\sim\mathcal{S}(x)}[h(x^{\prime},y)]$.
Then,

$\left|\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\right|\leq\psi(\epsilon).$

###### Proof.

Let $\tau_{1}=(x_{1},y_{1})$ and $\tau_{2}=(x_{2},y_{2})$ denote the input-
output tuples sampled from $\mathcal{D}$ and $\mathcal{\tilde{D}}$
respectively. Then, for the joint distribution
$\gamma^{*}\in\Gamma(\mathcal{D},\mathcal{\tilde{D}})$ in (2), we have

$\mathbb{E}_{\tau_{1}\sim\mathcal{D}}[\bar{h}(\tau_{1})]=\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[\bar{h}(\tau_{1})]\quad\text{and}\quad\mathbb{E}_{\tau_{2}\sim\mathcal{\tilde{D}}}[\bar{h}(\tau_{2})]=\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[\bar{h}(\tau_{2})].$

This is because when $(\tau_{1},\tau_{2})$ is sampled from the joint
distribution $\gamma^{*}$, $\tau_{1}$ and $\tau_{2}$ individually have
distributions $\mathcal{D}$ and $\mathcal{\tilde{D}}$ respectively. Also,
since the expected distance between $\tau_{1}=(x_{1},y_{1})$ and
$\tau_{2}=(x_{2},y_{2})$ is finite, the output elements of the sampled tuples
must be the same, i.e. $y_{1}=y_{2}=y$ (say). See lemma 2 below. Then,

$\displaystyle\big{|}\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]$
$\displaystyle-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\big{|}$
$\displaystyle=\left|\mathbb{E}_{\tau_{1}\sim\mathcal{D}}[\bar{h}(\tau_{1})]-\mathbb{E}_{\tau_{2}\sim\mathcal{\tilde{D}}}[\bar{h}(\tau_{2})]\right|$
$\displaystyle=\left|\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[\bar{h}(\tau_{1})-\bar{h}(\tau_{2})]\right|$
$\displaystyle\leq\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[|\bar{h}(\tau_{1})-\bar{h}(\tau_{2})|].$

Now, from definition (4) and for $i=1$ and $2$,

$\bar{h}(\tau_{i})=\bar{h}(x_{i},y)=\mathbb{E}_{x_{i}^{\prime}\sim\mathcal{S}(x_{i})}[h(x_{i}^{\prime},y)]=\mathbb{E}_{x_{i}^{\prime}\sim\mathcal{S}(x_{i})}[g(x_{i}^{\prime})]$

can be expressed as the expected value of a function
$g:\mathcal{X}\rightarrow[0,1]$ under distribution $\mathcal{S}(x_{i})$.
Without loss of generality, assume
$\mathbb{E}_{x_{1}^{\prime}\sim\mathcal{S}(x_{1})}[g(x_{1}^{\prime})]\geq\mathbb{E}_{x_{2}^{\prime}\sim\mathcal{S}(x_{2})}[g(x_{2}^{\prime})]$.
Then,

$\displaystyle\big{|}\mathbb{E}_{x_{1}^{\prime}\sim\mathcal{S}(x_{1})}[g(x_{1}^{\prime})]$
$\displaystyle-\mathbb{E}_{x_{2}^{\prime}\sim\mathcal{S}(x_{2})}[g(x_{2}^{\prime})]\big{|}$
$\displaystyle=\int_{\mathcal{X}}g(x)\mu_{1}(x)dx-\int_{\mathcal{X}}g(x)\mu_{2}(x)dx$
($\mu_{1}$ and $\mu_{2}$ are the PDFs of $\mathcal{S}(x_{1})$ and
$\mathcal{S}(x_{1})$)
$\displaystyle=\int_{\mathcal{X}}g(x)(\mu_{1}(x)-\mu_{2}(x))dx$
$\displaystyle=\int_{\mu_{1}>\mu_{2}}g(x)(\mu_{1}(x)-\mu_{2}(x))dx-\int_{\mu_{2}>\mu_{1}}g(x)(\mu_{2}(x)-\mu_{1}(x))dx$
$\displaystyle\leq\int_{\mu_{1}>\mu_{2}}\max_{x^{\prime}\in\mathcal{X}}g(x^{\prime})(\mu_{1}(x)-\mu_{2}(x))dx-\int_{\mu_{2}>\mu_{1}}\min_{x^{\prime}\in\mathcal{X}}g(x^{\prime})(\mu_{2}(x)-\mu_{1}(x))dx$
$\displaystyle\leq\int_{\mu_{1}>\mu_{2}}(\mu_{1}(x)-\mu_{2}(x))dz$ (since
$\max_{x^{\prime}\in\mathcal{X}}g(x^{\prime})\leq 1$ and
$\min_{x^{\prime}\in\mathcal{X}}g(x^{\prime})\geq 0$)
$\displaystyle=\frac{1}{2}\int_{\mathcal{X}}|\mu_{1}(x)-\mu_{2}(x)|dx=\operatorname{\mathsf{TV}}(\mathcal{S}(x_{1}),\mathcal{S}(x_{2})).$
(since
$\int_{\mu_{1}>\mu_{2}}(\mu_{1}(x)-\mu_{2}(x))dx=\int_{\mu_{2}>\mu_{1}}(\mu_{2}(x)-\mu_{1}(x))dx=\frac{1}{2}\int_{\mathcal{X}}|\mu_{1}(x)-\mu_{2}(x)|dx$)

Thus, from (1) and (3), we have
$|\bar{h}(\tau_{1})-\bar{h}(\tau_{2})|\leq\psi(d_{\mathcal{X}}(x_{1},x_{2}))=\psi(d(\tau_{1},\tau_{2}))$,
and therefore,

$\displaystyle\big{|}\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]$
$\displaystyle-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\big{|}$
$\displaystyle\leq\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[\psi(d(\tau_{1},\tau_{2}))]$
$\displaystyle\leq\psi\left(\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[d(\tau_{1},\tau_{2})]\right).$
($\psi$ is concave, Jensen’s inequality)

Hence, from (2) and since $\psi$ is non-decreasing, we have

$\left|\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]-\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\right|\leq\psi(\epsilon).$

∎

######  Lemma 2.

Let $\Omega=\\{(\tau_{1},\tau_{2})\text{ s.t. }y_{1}\neq y_{2}\text{ where
}\tau_{1}=(x_{1},y_{1})\text{ and }\tau_{2}=(x_{2},y_{2})\\}$. Then

$\mathbb{P}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]=0.$

###### Proof.

Assume, for the sake of contradiction, that

$\mathbb{P}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]\geq
p$

for some $p>0$. From condition (2), we have

$\mathbb{E}_{(\tau_{1},\tau_{2})\sim\gamma^{*}}[d(\tau_{1},\tau_{2})]\leq\epsilon.$

By the law of total expectation

$\displaystyle\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})]=$
$\displaystyle\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})\mid(\tau_{1},\tau_{2})\in\Omega]\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]$
$\displaystyle+$
$\displaystyle\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})\mid(\tau_{1},\tau_{2})\notin\Omega]\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\notin\Omega].$

We replace $(\tau_{1},\tau_{2})\sim\gamma^{*}$ with just $\gamma^{*}$ in the
subscripts for brevity. Since both summands are non-negative,

$\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})\mid(\tau_{1},\tau_{2})\in\Omega]\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]\leq\epsilon.$

Consider a real number $l>\epsilon/p$. Then, for any
$(\tau_{1},\tau_{2})\in\Omega$, from definition (1) and because $y_{1}\neq
y_{2}$, $d(\tau_{1},\tau_{2})\geq l$. Therefore,
$\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})\mid(\tau_{1},\tau_{2})\in\Omega]\geq
l$ and

$\displaystyle l\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]$
$\displaystyle\leq\mathbb{E}_{\gamma^{*}}[d(\tau_{1},\tau_{2})\mid(\tau_{1},\tau_{2})\in\Omega]\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]$
$\displaystyle l\;\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]$
$\displaystyle\leq\epsilon$
$\displaystyle\mathbb{P}_{\gamma^{*}}[(\tau_{1},\tau_{2})\in\Omega]$
$\displaystyle\leq\epsilon/l<p,$

which contradicts our initial assumption. ∎

##  Appendix B Proof of Lemma 1

######  Statement.

For two points $x_{1},x_{2}\in\mathcal{X}$ such that
$d_{\mathcal{T}}(x_{1},x_{2})$ is finite,

$\operatorname{\mathsf{TV}}(\mathcal{S}(x_{1}),\mathcal{S}(x_{2}))\leq\psi(d_{\mathcal{T}}(x_{1},x_{2})).$

###### Proof.

Consider the $\theta$ for which $d_{\mathcal{T}}(x_{1},x_{2})=\|\theta\|$.
Then, $\mathcal{T}(x_{1},\theta)=x_{2}$.

$\displaystyle\operatorname{\mathsf{TV}}(\mathcal{S}(x),\mathcal{S}(x_{2}))$
$\displaystyle=\operatorname{\mathsf{TV}}(\mathcal{T}(x,\mathcal{Q}(0)),\mathcal{T}(z,\mathcal{Q}(0)))$
$\displaystyle=\operatorname{\mathsf{TV}}(\mathcal{T}(x,\mathcal{Q}(0)),\mathcal{T}(\mathcal{T}(x,\theta),\mathcal{Q}(0)))$
$\displaystyle=\operatorname{\mathsf{TV}}(\mathcal{T}(x,\mathcal{Q}(0)),\mathcal{T}(x,\theta+\mathcal{Q}(0)))$
(additive composability, equation (5))
$\displaystyle=\operatorname{\mathsf{TV}}(\mathcal{T}(x,\mathcal{Q}(0)),\mathcal{T}(x,\mathcal{Q}(\theta))).$
(definition of $\mathcal{Q}$)

Let $A$ be the event in the space $M$ that maximizes the difference in the
probabilities assigned to $A$ by $\mathcal{T}(x,\mathcal{Q}(0))$ and
$\mathcal{T}(x,\mathcal{Q}(\theta))$. Let $u:P\rightarrow[0,1]$ be a function
that returns the probability (over the randomness of $\mathcal{T}$) of any
parameter $\eta\in P$ being mapped to a point in $A$, i.e.,
$u(\eta)=\mathbb{P}\\{\mathcal{T}(x,\eta)\in A\\}$. For a deterministic
transformation $\mathcal{T}$, $u$ is a 0/1 function. Then, the probabilities
assigned by $\mathcal{T}(x,\mathcal{Q}(0))$ and
$\mathcal{T}(x,\mathcal{Q}(\theta))$ to $A$ is equal to
$\mathbb{E}_{\eta\sim\mathcal{Q}(0)}[u(\eta)]$ and
$\mathbb{E}_{\eta\sim\mathcal{Q}(\theta)}[u(\eta)]$. Therefore,

$\displaystyle\operatorname{\mathsf{TV}}(\mathcal{S}(x),\mathcal{S}(x_{2}))$
$\displaystyle=|\mathbb{E}_{\eta\sim\mathcal{Q}(0)}[u(\eta)]-\mathbb{E}_{\eta\sim\mathcal{Q}(\theta)}[u(\eta)]|$
$\displaystyle\leq\operatorname{\mathsf{TV}}(\mathcal{Q}(0),\mathcal{Q}(\theta))$
$\displaystyle\leq\psi(\|\theta\|)=\psi(d_{\mathcal{T}}(x_{1},x_{2})).$
(definition of $\mathcal{Q}$ and $d_{\mathcal{T}}$)

∎

##  Appendix C Function $\psi$ for Different Distributions

For an isometric Gaussian distribution $\mathcal{N}(0,\sigma^{2}I)$,

$\operatorname{\mathsf{TV}}(\mathcal{N}(0,\sigma^{2}I),\mathcal{N}(\theta,\sigma^{2}I))=\operatorname{erf}(\|\theta\|_{2}/2\sqrt{2}\sigma).$

###### Proof.

Due to the isometric symmetry of the Gaussian distribution and the
$\ell_{2}$-norm, we may assume, without loss of generality, that
$\mathcal{N}(\theta,\sigma^{2}I)$ is obtained by shifting
$\mathcal{N}(0,\sigma^{2}I)$ only along the first dimension. Therefore, the
total variation of the two distributions is equal to the difference in the
probability of a normal random variable with variance $\sigma^{2}$ being less
than $\|\theta\|_{2}/2$ and $-\|\theta\|_{2}/2$, i.e.,
$\Phi(\|\theta\|_{2}/2\sigma)-\Phi(-\|\theta\|_{2}/2\sigma)$ where $\Phi$ is
the standard normal CDF.

$\displaystyle\operatorname{\mathsf{TV}}(\mathcal{N}(0,\sigma^{2}I),\mathcal{N}(\theta,\sigma^{2}I))$
$\displaystyle=\Phi(\|\theta\|_{2}/2\sigma)-\Phi(-\|\theta\|_{2}/2\sigma)$
$\displaystyle=2\Phi(\|\theta\|_{2}/2\sigma)-1$
$\displaystyle=2\left(\frac{1+\operatorname{erf}(\|\theta\|_{2}/2\sqrt{2}\sigma)}{2}\right)-1$
$\displaystyle=\operatorname{erf}(\|\theta\|_{2}/2\sqrt{2}\sigma).$

∎

For a uniform distribution $\mathcal{U}(\theta,b)$ between $\theta_{i}$ and
$\theta_{i}+b$ in each dimension for $b\geq 0$ (as used for the SV shift
transformations),
$\operatorname{\mathsf{TV}}(\mathcal{U}(0,b),\mathcal{U}(\theta,b))\leq\|\theta\|_{1}/b$.
When $\|\theta\|_{1}$ is constrained, the volume of the overlap between
$\mathcal{U}(0,b)$ and $\mathcal{U}(\theta,b)$ is minimized when the shift is
only along one dimension.

##  Appendix D Additive Composability of Natural Transformations

In this section, we prove that the natural transformation
$\mathsf{CS},\mathsf{HS}$ and $\mathsf{SV}$ defined in the paper all satisfy
the additive composability property in condition (5).

######  Lemma 3.

The transformation $\mathsf{CS}$ satisfies the additive composability
property, i.e., $\forall x\in M,\theta_{1},\theta_{2}\in\mathbb{R}^{3}$,

$\mathsf{CS}(\mathsf{CS}(x,\theta_{1}),\theta_{2})=\mathsf{CS}(x,\theta_{1}+\theta_{2}).$

###### Proof.

Let $x=\\{(r,g,b)_{ij}\\}^{H\times
W},x^{\prime}=\\{(r^{\prime},g^{\prime},b^{\prime})_{ij}\\}^{H\times
W}=\mathsf{CS}(x,\theta_{1})$ and
$x^{\prime\prime}=\\{(r^{\prime\prime},g^{\prime\prime},b^{\prime\prime})_{ij}\\}^{H\times
W}=\mathsf{CS}(x^{\prime},\theta_{2})$. We need to show that
$x^{\prime\prime}=\mathsf{CS}(x,\theta_{1}+\theta_{2})$. Let
$r_{\max},g_{\max}$ and $b_{\max}$ be the maximum values of the red, green and
blue channels respectively of $x$ and $r^{\prime}_{\max},g^{\prime}_{\max}$
and $b^{\prime}_{\max}$ be the same for $x^{\prime}$. From the definition of
$\mathsf{CS}$ in section 5.1, we have:

$\displaystyle r^{\prime}_{ij}$
$\displaystyle=\frac{2^{\theta_{1}^{R}}r_{ij}}{\mathsf{MAX}},\quad
g^{\prime}_{ij}=\frac{2^{\theta_{1}^{G}}g_{ij}}{\mathsf{MAX}},\quad
b^{\prime}_{ij}=\frac{2^{\theta_{1}^{B}}b_{ij}}{\mathsf{MAX}}$
$\displaystyle\text{and}\quad r^{\prime\prime}_{ij}$
$\displaystyle=\frac{2^{\theta_{2}^{R}}r^{\prime}_{ij}}{\mathsf{MAX^{\prime}}},\quad
g^{\prime\prime}_{ij}=\frac{2^{\theta_{2}^{G}}g^{\prime}_{ij}}{\mathsf{MAX^{\prime}}},\quad
b^{\prime\prime}_{ij}=\frac{2^{\theta_{2}^{B}}b^{\prime}_{ij}}{\mathsf{MAX^{\prime}}}$

where
$\mathsf{MAX}=\max(2^{\theta_{1}^{R}}r_{\max},2^{\theta_{1}^{G}}g_{\max},2^{\theta_{1}^{B}}b_{\max})$
and
$\mathsf{MAX^{\prime}}=\max(2^{\theta_{2}^{R}}r^{\prime}_{\max},2^{\theta_{2}^{G}}g^{\prime}_{\max},2^{\theta_{2}^{B}}b^{\prime}_{\max})$.
From the definition of $r^{\prime}_{\max}$, we have:

$r^{\prime}_{\max}=\max{r^{\prime}_{ij}}=\max{\frac{2^{\theta_{1}^{R}}r_{ij}}{\mathsf{MAX}}}=\frac{2^{\theta_{1}^{R}}\max{r_{ij}}}{\mathsf{MAX}}=\frac{2^{\theta_{1}^{R}}r_{\max}}{\mathsf{MAX}}.$

Similarly,

$g^{\prime}_{\max}=\frac{2^{\theta_{1}^{G}}g_{\max}}{\mathsf{MAX}}\quad\text{and}\quad
b^{\prime}_{\max}=\frac{2^{\theta_{1}^{B}}b_{\max}}{\mathsf{MAX}}.$

Therefore,

$\mathsf{MAX^{\prime}}=\frac{\max(2^{\theta_{1}^{R}+\theta_{2}^{R}}r_{\max},2^{\theta_{1}^{G}+\theta_{2}^{G}}g_{\max},2^{\theta_{1}^{B}+\theta_{2}^{B}}b_{\max})}{\textsf{MAX}}.$

Substituting $r^{\prime}_{ij}$ and MAX’ in the expression for
$r^{\prime\prime}_{ij}$, we get:

$r^{\prime\prime}_{ij}=\frac{2^{\theta_{2}^{R}}2^{\theta_{1}^{R}}r_{ij}}{\mathsf{MAX^{\prime}}\mathsf{MAX}}=\frac{2^{\theta_{1}^{R}+\theta_{2}^{R}}r_{ij}}{\max(2^{\theta_{1}^{R}+\theta_{2}^{R}}r_{\max},2^{\theta_{1}^{G}+\theta_{2}^{G}}g_{\max},2^{\theta_{1}^{B}+\theta_{2}^{B}}b_{\max})}.$

Similarly,

$g^{\prime\prime}_{ij}=\frac{2^{\theta_{1}^{G}+\theta_{2}^{G}}g_{ij}}{\max(2^{\theta_{1}^{R}+\theta_{2}^{R}}r_{\max},2^{\theta_{1}^{G}+\theta_{2}^{G}}g_{\max},2^{\theta_{1}^{B}+\theta_{2}^{B}}b_{\max})}\quad\text{and}\quad
b^{\prime\prime}_{ij}=\frac{2^{\theta_{1}^{B}+\theta_{2}^{B}}b_{ij}}{\max(2^{\theta_{1}^{R}+\theta_{2}^{R}}r_{\max},2^{\theta_{1}^{G}+\theta_{2}^{G}}g_{\max},2^{\theta_{1}^{B}+\theta_{2}^{B}}b_{\max})}.$

Hence, $x^{\prime\prime}=\mathsf{CS}(x,\theta_{1}+\theta_{2})$. ∎

######  Lemma 4.

The transformation $\mathsf{SV}$ satisfies the additive composability
property, i.e., $\forall x\in M,\theta_{1},\theta_{2}\in\mathbb{R}_{\geq
0}^{2}$,

$\mathsf{SV}(\mathsf{SV}(x,\theta_{1}),\theta_{2})=\mathsf{SV}(x,\theta_{1}+\theta_{2}).$

###### Proof.

Let $x=\\{(h,s,v)_{ij}\\}^{H\times
W},x^{\prime}=\\{(h,s^{\prime},v^{\prime})_{ij}\\}^{H\times
W}=\mathsf{SV}(x,\theta_{1})$ and
$x^{\prime\prime}=\\{(h,s^{\prime\prime},v^{\prime\prime})_{ij}\\}^{H\times
W}=\mathsf{SV}(x^{\prime},\theta_{2})$ in HSV format. We need to show that
$x^{\prime\prime}=\mathsf{SV}(x,\theta_{1}+\theta_{2})$. Let
$s_{\operatorname{mean}},s_{\max},v_{\operatorname{mean}}$ and $v_{\max}$ be
the means and maximums of the saturation and brightness values of $x$ and
$s^{\prime}_{\operatorname{mean}},s^{\prime}_{\max},v^{\prime}_{\operatorname{mean}}$
and $v^{\prime}_{\max}$ be the same for $x^{\prime}$. From the definition of
$\mathsf{SV}$ in section 5.3, we have:

$\displaystyle
s^{\prime}_{ij}=\frac{s_{ij}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}},\quad
v^{\prime}_{ij}=\frac{v_{ij}+(2^{\theta_{1}^{V}}-1)v_{\operatorname{mean}}}{\mathsf{MAX}}$
$\displaystyle\text{and}\quad
s^{\prime\prime}_{ij}=\frac{s^{\prime}_{ij}+(2^{\theta_{2}^{S}}-1)s^{\prime}_{\operatorname{mean}}}{\mathsf{MAX^{\prime}}},\quad
v^{\prime\prime}_{ij}=\frac{v^{\prime}_{ij}+(2^{\theta_{2}^{V}}-1)v^{\prime}_{\operatorname{mean}}}{\mathsf{MAX^{\prime}}}$

where
$\mathsf{MAX}=\max(s_{\max}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{1}^{V}}-1)v_{\operatorname{mean}})$
and
$\mathsf{MAX^{\prime}}=\max(s^{\prime}_{\max}+(2^{\theta_{2}^{S}}-1)s^{\prime}_{\operatorname{mean}},v^{\prime}_{\max}+(2^{\theta_{2}^{V}}-1)v^{\prime}_{\operatorname{mean}})$.
From the definitions of $s^{\prime}_{\operatorname{mean}}$ and
$s^{\prime}_{\max}$, we have:

$\displaystyle s^{\prime}_{\operatorname{mean}}$
$\displaystyle=\operatorname{mean}{s^{\prime}_{ij}}=\operatorname{mean}{\frac{s_{ij}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}}}=\frac{\operatorname{mean}{s_{ij}}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}}=\frac{2^{\theta_{1}^{S}}s_{\operatorname{mean}}}{\mathsf{MAX}}$
$\displaystyle s^{\prime}_{\max}$
$\displaystyle=\max{s^{\prime}_{ij}}=\max{\frac{s_{ij}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}}}=\frac{\max{s_{ij}}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}}=\frac{s_{\max}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}}.$

Similarly,

$v^{\prime}_{\operatorname{mean}}=\frac{2^{\theta_{1}^{V}}v_{\operatorname{mean}}}{\mathsf{MAX}}\quad\text{and}\quad
v^{\prime}_{\max}=\frac{v_{\max}+(2^{\theta_{1}^{V}}-1)v_{\operatorname{mean}}}{\mathsf{MAX}}.$

Therefore,

$\displaystyle\mathsf{MAX^{\prime}}$
$\displaystyle=\max(s^{\prime}_{\max}+(2^{\theta_{2}^{S}}-1)s^{\prime}_{\operatorname{mean}},v^{\prime}_{\max}+(2^{\theta_{2}^{V}}-1)v^{\prime}_{\operatorname{mean}})$
$\displaystyle=\max(\frac{s_{\max}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}+(2^{\theta_{2}^{S}}-1)2^{\theta_{1}^{S}}s_{\operatorname{mean}}}{\mathsf{MAX}},v^{\prime}_{\max}+(2^{\theta_{2}^{V}}-1)v^{\prime}_{\operatorname{mean}})$
$\displaystyle=\max(\frac{s_{\max}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}}}{\mathsf{MAX}},v^{\prime}_{\max}+(2^{\theta_{2}^{V}}-1)v^{\prime}_{\operatorname{mean}})$
$\displaystyle=\max(s_{\max}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{1}^{V}}-1)v_{\operatorname{mean}}+(2^{\theta_{2}^{V}}-1)2^{\theta_{1}^{V}}v_{\operatorname{mean}})/\mathsf{MAX}$
$\displaystyle=\max(s_{\max}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{1}^{V}+\theta_{2}^{V}}-1)v_{\operatorname{mean}})/\mathsf{MAX}.$

Substituting $s^{\prime}_{ij},s^{\prime}_{\operatorname{mean}}$ and
$\mathsf{MAX^{\prime}}$ in the expression for $s^{\prime\prime}_{ij}$, we get:

$\displaystyle s^{\prime\prime}_{ij}$
$\displaystyle=\frac{s_{ij}+(2^{\theta_{1}^{S}}-1)s_{\operatorname{mean}}+(2^{\theta_{2}^{S}}-1)2^{\theta_{1}^{S}}s_{\operatorname{mean}}}{\mathsf{MAX^{\prime}}\mathsf{MAX}}$
$\displaystyle=\frac{s_{ij}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}}}{\max(s_{\max}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{1}^{V}+\theta_{2}^{V}}-1)v_{\operatorname{mean}})}.$

Similarly,

$v^{\prime\prime}_{ij}=\frac{v_{ij}+(2^{\theta_{1}^{V}+\theta_{2}^{V}}-1)v_{\operatorname{mean}}}{\max(s_{\max}+(2^{\theta_{1}^{S}+\theta_{2}^{S}}-1)s_{\operatorname{mean}},v_{\max}+(2^{\theta_{1}^{V}+\theta_{2}^{V}}-1)v_{\operatorname{mean}})}.$

Hence, $x^{\prime\prime}=\mathsf{SV}(x,\theta_{1}+\theta_{2})$. ∎

##  Appendix E Details for Plots in Figure 2

The distribution shifts used to evaluate the empirical performance of the base
models in figure 2 have been generated by first sampling an image $x$ from the
original distribution $\mathcal{D}$ and then randomly transforming it images
from the original distribution by adding a noise in the corresponding
transformation space. The Wasserstein bound of these shifts can be calculated
by computing the expected perturbation size of the smoothing distribution. For
example, the expected $\ell_{2}$-norm of a 3-dimensional Gaussian vector is
given by $2\sqrt{2}\sigma/\sqrt{\pi}$ and expected $\ell_{1}$-norm a
2-dimensional vector sampled uniformly from $[0,b]^{2}$ is $b$.

The training and smoothing noise levels used for color shift, hue shift and SV
shift are (0.8, 10.0), ($180\degree$, $180\degree$) and (8.0, 12.0)
respectively.

##  Appendix F Hue Shift

Define a hue shift of an $H\times W$ sized image $x$ by an angle
$\theta\in[-\pi,\pi]$ in the HSV space as:

$\displaystyle\mathsf{HS}(x,\theta)$
$\displaystyle=\left\\{\left(w(h+\theta),s,v\right)_{ij}\right\\}^{H\times W}$
$\displaystyle\text{where}\quad w(x)$
$\displaystyle=x-2\pi\left\lfloor\frac{x}{2\pi}\right\rfloor$

which rotates each hue value by an angle $\theta$ and wraps it around to the
$[0,2\pi)$ range. It is easy to show that this transformation satisfies
additive composability in condition (5). The Wasserstein distance is defined
using the corresponding distance function $d_{\mathsf{HS}}$ by taking the
absolute value of the hue shift $|\theta|$.

######  Lemma 5.

The transformation $\mathsf{HS}$ satisfies the additive composability
property, i.e., $\forall x\in M,\theta_{1},\theta_{2}\in[-\pi,\pi]$,

$\mathsf{HS}(\mathsf{HS}(x,\theta_{1}),\theta_{2})=\mathsf{HS}(x,\theta_{1}+\theta_{2}).$

###### Proof.

Let $h$ be the hue value of the $(i,j)$th pixel of the image $x$. Since the
transformation only affects the hue values, we ignore the other coordinates.
The hue value after the transformation
$\mathsf{HS}(\mathsf{HS}(x,\theta_{1}),\theta_{2})$ is given by

$\displaystyle w(w(h+\theta_{1})+\theta_{2})$
$\displaystyle=w\left(h+\theta_{1}-2\pi\left\lfloor\frac{h+\theta_{1}}{2\pi}\right\rfloor+\theta_{2}\right)$

∎

Define a smoothing distribution that applies a random hue rotation $\delta$
sampled uniformly from the range $[-\pi,\pi]$. Since $\mathsf{HS}$ wraps the
hue values around in the interval, the distributions of $h+\delta$ and
$(h+\theta)+\delta$ for two hue values shifted by an angle $\theta$ are both
uniform in $[0,2\pi]$. Thus, the smoothing distribution for two hue shifted
images is the same which implies that $\psi(d(x_{1},x_{2}))=0$ whenever
$d(x_{1},x_{2})$ is finite. Hence, from Theorem 1, we have
$\mathbb{E}_{(x_{2},y_{2})\sim\mathcal{\tilde{D}}}[\bar{h}(x_{2},y_{2})]\geq\mathbb{E}_{(x_{1},y_{1})\sim\mathcal{D}}[\bar{h}(x_{1},y_{1})]$
for hue shifts. Since, the certified accuracy remains constant with respect to
the Wasserstein distance of the shift, we just plot the certified accuracies
obtained by various base models trained under different noise levels in figure
6. We plot the certified accuracies obtained by various models trained using
random hue rotations picked uniformly from the range $[-\beta,\beta]$ for
different values of the maximum angle $\beta$ in the range. The certified
accuracy roughly increases with the training noise achieving a maximum of
87.9% for a max angle $\beta=180\degree$ for the training noise level.

Figure 6: Certified accuracy under hue shift for different levels of training
noise. Since, the certified accuracy remains constant with respect to the
Wasserstein distance ($\epsilon$) of the shifted distribution, we plot the
certified accuracy of models trained with different noise levels $\beta$.

##  Appendix G Random Channel Selection

Consider a smoothing distribution that randomly picks one of the RGB channels
with equal probability, scales it so that the maximum pixel value in that
channel is one and sets all the other channels to zero. This smoothing
distribution is invariant to the color shift transformation $\mathsf{CS}$ and
thus, satisfies $\psi(d_{\mathcal{T}}(x_{1},x_{2}))=0$ whenever
$d_{\mathcal{T}}(x_{1},x_{2})$ is finite. Therefore, from theorem 1, we have
$\mathbb{E}_{z\sim\mathcal{\tilde{D}}}[\bar{h}(z)]\geq\mathbb{E}_{x\sim\mathcal{D}}[\bar{h}(x)]$
under this smoothing distribution for all Wasserstein bounds $\epsilon$ with
respect to $d_{\mathsf{CS}}$. Figure 7 plots the certified accuracies, using
random channel selection for smoothing, achieved by models trained using
Gaussian distributions of varying noise levels in the transformation space.
The certified accuracy roughly increases with the training noise achieving a
maximum of 87.1% for a training noise of 0.8.

##  Appendix H Experiment Details for Section 6

As mentioned, for the certified models, we use the released pre-trained
ResNet110 models from [28], using the same level of Gaussian Noise for
training and testing. For empirical results, we use the implementation of the
$\ell_{2}$ Carlini and Wagner [11] attack provided by the IBM ART package [60]
with default parameters (except for batch size which we set at 256 to increase
processing speed.)

Figure 7: Certified robustness against color shift using random channel
selection as the smoothing distribution. Since, the certified accuracy remains
constant with respect to the Wasserstein distance ($\epsilon$) of the shifted
distribution, we plot the certified accuracy of models trained with various
levels of Gaussian noise in the transformation space.

##  Appendix I Experiment details for Section 7

Our experimental setting is adapted from the “sample-wise perturbation”
CIFAR-10 experiments in [49]: hyperparameters are the same as in that work
unless otherwise stated. For background, [49] creates an unlearnable dataset
by performing the following “bi-level” minimization, to simultaneously train a
proxy classifier model and create unlearnable examples:

$\min_{\theta}\min_{(\epsilon_{1},...,\epsilon_{n})}\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}(f_{\theta}(x_{i}+\epsilon_{i}),y_{i})$
(8)

In other words, in contrast with standard training, both the samples and the
proxy classifier are optimized to decrease the loss. New classifiers trained
on the resulting samples fail to generalize to unperturbed samples. In the
experiments, as in [49], the inner minimization over perturbations is
performed for 20 steps over the entire dataset, for every one batch update
step of the outer minimization. Training stops when training accuracy reaches
a threshold value of 99%.

We now detail differences in experimental setup from [49]:

###  I.1 Adaptation to $\ell_{2}$ attack setting

After each optimization step, we project $\epsilon_{i}$’s into an $\ell_{2}$
ball (of radius given by the Wasserstein bound $\epsilon$) rather than an
$\ell_{\infty}$ ball. We also use an $\ell_{2}$ PGD step:

$\epsilon_{i}^{\prime}=\epsilon_{i}+\tau\frac{{\nabla}_{\epsilon_{i}}\mathcal{L}(\cdot)}{\|{\nabla}_{\epsilon_{i}}\mathcal{L}(\cdot)\|_{2}}$
(9)

Step size $\tau$ was set as 0.1 times the total $\ell_{2}$ $\epsilon$ bound.

###  I.2 Adaptation to offline setting

As discussed in the test, we modify the algorithm such that the simultaneous
training of the proxy model and generation of perturbations does not introduce
statistical dependencies between perturbed training samples. This is
especially important because, if the victim later makes a train-validation
split, this would introduce statistical dependencies between training and
validation samples, making it hard to generalize certificates to a test set.

To avoid this, we construct four data splits:

  * •

Test set (10000 samples): The original CIFAR-10 test set. Never perturbed,
only used in final model evaluation.

  * •

Proxy training set (20000 samples): Used for the optimization of the proxy
classifier model parameters $\theta$ in Equation 8 and discarded afterward.

  * •

Training set (20000 samples): Perturbed using one round of the the standard 20
steps of the inner optimization of Equation 8, while keeping $\theta$ fixed.

  * •

Validation set (10000 samples): Perturbed using the same method as the
“Training set.”

The victim model is trained on the “Training Set” and evaluated on the
“Validation set” and “Test set”. We also tested on the clean (unperturbed)
version of the validation set.

###  I.3 Adaptive attack setting

When testing our smoothing algorithm, we tested two types of attacks:

  * •

Non-adaptive attack: the proxy model is trained and perturbations are
generated using undefended models without smoothing: only the victim policy
applies smoothing noise during training and evaluation.

  * •

Adaptive attack: In the minimization of Equation 8, the loss term
$\mathcal{L}(f_{\theta}(x_{i}+\epsilon_{i}),y_{i})$ is replaced by the
expectation:

$\mathop{\mathbb{missing}}{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}\mathcal{L}(f_{\theta}(x_{i}+\epsilon_{i}+\delta),y_{i})$
(10)

In other words, this models the expectation of a smoothed model, like the
victim classifier. This smoothed optimization is used in both the proxy model
training, as well as the generation of the training and validation sets.
Following [31], which proposed a similar adaptive attack for sample-wise
smoothed classifiers we approximate the expectation using a small number of
random perturbations, which are held fixed for the 20 steps of the inner
optimization. In our experiments, we use 8 samples for approximation. Because,
at large smoothing noises, this makes the attack much less effective, we cut
off training after 20 steps of the outer maximization, rather than relying on
the accuracy to reach 99%. (the maximum number of steps required to converge
we observed for the non-adaptive attack was 15).

###  I.4 Results

Complete experimental results are presented in Figure 8. All results are means
of 5 independent runs, and error bars represent standard errors of the means.

Figure 8: Complete Experimental results for unlearnability experiments.

##  Appendix J Empirical Attacks on $\ell_{2}$-distributional robustness.

In this section, we describe an empirical attack on $\ell_{2}$-distributional
smoothing. Our attack is based on the attack from [31], and we use the code
for PGD attack against smoothed classifiers from that work as a base, but
there are a few considerations we must make.

Figure 9: Adversarial attack on distributionally-smoothed classifiers, for
CIFAR-10. For smoothed classifiers, we us the PGD attack described in this
section; see main text for details on the baseline. The dashed lines represent
an upper bound on the empirical Wasserstein distances. In plot (a), we use the
loss function in Equation 11, while in (b) we use Equation 12.

First, while the goal of the attacker in [31] is to change the output of a
classifier that uses the expected logits, the goal in our case is to instead
reduce the average classification accuracy of each noise instance. Concretely,
[31] uses an attacker loss function for each sample $x,y$ of the following
form:

$\max_{\epsilon}\mathcal{L}_{\text{Cross
Ent.}}\left(\mathop{\mathbb{missing}}{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}[\tilde{f}_{\theta}(x+\epsilon+\delta)],y\right)$
(11)

Where we use $\tilde{f}$ to represent the SoftMax-ed logit function. However,
because in our case, the classifier under attack is not
$\mathbb{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}[\tilde{f}_{\theta}(x+\epsilon+\delta)]$,
but rather $\tilde{f}_{\theta}(x+\epsilon+\delta)$ itself, we instead
considered the loss function:

$\max_{\epsilon}\mathop{\mathbb{missing}}{E}_{\delta\sim\mathcal{N}(0,\sigma^{2}I)}\left[\mathcal{L}_{\text{Cross
Ent.}}\left(\tilde{f}_{\theta}(x+\epsilon+\delta),y\right)\right]$ (12)

Empirically, we find the choice of loss function to make very little
difference: see Figure 9.

We also must consider how to correctly make the attacker “strategic”: that is,
how to allocate attack magnitude so as to attack most effectively while
minimizing Wasserstein distance. This is more difficult than in the undefended
case, because it is no longer true that for each sample $x$, we can identify
the magnitude $\|CW(x,y;g)-x\|_{2}$ such that an attack of this magnitude is
guaranteed to be successful, while a smaller attack is unsuccessful and hence
is not attempted. Rather, for a given attack magnitude, there is instead a
probability of success, over the distribution of $\delta$.

In order to deal with this, we perform PGD at a range of attack magnitudes,
specifically $E=\\{i/8|i\in\\{1,...,16\\}\\}$. Let $PGD_{e}(x,y;g)$ be the
result of the attack at magnitude $e\in E$. We then define the adaptive
attacker as:

$\text{Adv}_{\gamma}(x):=PGD_{e*}(x,y;g)$ (13)

Where:

$\begin{split}&e*:=\max e\in E\text{ such that }\\\
&\frac{\mathop{\mathbb{missing}}{E}_{\delta}\left[\mathcal{L}_{0/1}\left(\tilde{f}_{\theta}(PGD_{e}(x,y;g)+\delta),y\right)\right]-\mathop{\mathbb{missing}}{E}_{\delta}\left[\mathcal{L}_{0/1}\left(\tilde{f}_{\theta}(x+\delta),y\right)\right]}{e}>\gamma\end{split}$
(14)

In other words, we use the largest attack such that the increase in
misclassification rate per unit attack magnitude is above the threshold
$\gamma$. If this is not the case for any $e\in E$, we elect not to attack,
and set $\text{Adv}_{\gamma}(x):=x$. As was described in the main text for the
baseline case, we sweep over a range of threshold values $\gamma$ when
reporting results. When evaluating the expectations in Equation 14, we use a
sample of 100 noise instances. However, once $e*$ is identified, we then use a
different sample of 100 noise instances per training sample $x$ when reporting
the final accuracy: this is to de-correlate the attack generation of
$\text{Adv}_{\gamma}(x)$ with the evaluation of the attack. (However, noise
instances are kept constant over the sweep of $\gamma$). When reporting
results (the upper bounds of empirical Wasserstein distances), we use $e*$ as
an upper bound on $\|PGD_{e*}(x,y;g)-x\|_{2}$, rather than using
$\|PGD_{e*}(x,y;g)-x\|_{2}$ directly.

Attack hyperparameters are taken from [31]: We use 20 attack steps, a step
size of $e/10$, and use 128 noise instances when computing gradients. We
evaluate using 10% of the CIFAR-10 test set.