# Center Smoothing: Certified Robustness for Networks with Structured Outputs

Aounon Kumar
University of Maryland
<EMAIL_ADDRESS>
&Tom Goldstein
University of Maryland
<EMAIL_ADDRESS>

###### Abstract

The study of provable adversarial robustness has mostly been limited to
classification tasks and models with one-dimensional real-valued outputs. We
extend the scope of certifiable robustness to problems with more general and
structured outputs like sets, images, language, etc. We model the output space
as a metric space under a distance/similarity function, such as intersection-
over-union, perceptual similarity, total variation distance, etc. Such models
are used in many machine learning problems like image segmentation, object
detection, generative models, image/audio-to-text systems, etc. Based on a
robustness technique called randomized smoothing, our center smoothing
procedure can produce models with the guarantee that the change in the output,
as measured by the distance metric, remains small for any norm-bounded
adversarial perturbation of the input. We apply our method to create
certifiably robust models with disparate output spaces – from sets to images –
and show that it yields meaningful certificates without significantly
degrading the performance of the base model. Code for our experiments is
available at: https://github.com/aounon/center-smoothing.

##  1 Introduction

The study of adversarial robustness in machine learning (ML) has gained a lot
of attention ever since deep neural networks (DNNs) have been demonstrated to
be vulnerable to adversarial attacks. These attacks are generated by making
tiny perturbations of the input that can completely alter a model’s
predictions [56, 46, 23, 35]. They can significantly degrade the performance
of a model, like an image classifier, and make it output almost any class of
the attacker’s choice. However, these attacks are not limited just to
classification problems. They have also been shown to exist for DNNs with
structured outputs like text, images, probability distributions, sets, etc.
For instance, automatic speech recognition systems can be attacked with 100%
success rate to output any phrase of the attackers choice [10]. Similar
attacks can cause neural image captioning systems to produce specific target
captions with high success-rate [11]. Quality of image segmentation models
have been shown to degrade severely under adversarial attacks [2, 27, 30].
Facial recognition systems can be deceived to evade detection, impersonate
authorized individuals and even render them completely ineffective [59, 55,
20]. Image reconstruction models have been targeted to introduce unwanted
artefacts or miss important details, such as tumors in MRI scans, through
adversarial inputs [1, 50, 8, 12]. Super-resolution systems can be made to
generate distorted images that can in turn deteriorate the performance of
subsequent tasks that rely on the high-resolution outputs [14, 63]. Deep
neural network based policies in reinforcement learning problems also have
been shown to succumb to imperceptible perturbations in the state observations
[21, 29, 4, 48]. Such widespread presence of adversarial attacks is concerning
as it threatens the use of deep neural networks in critical systems, such as
facial recognition, self-driving vehicles, medical diagnosis, etc., where
safety, security and reliability are of utmost importance.

Adversarial defenses have mostly focused on classification tasks [34, 6, 26,
17, 44, 25, 22]. Certified defenses based on convex-relaxation [61, 49, 53,
13, 54], interval-bound propagation [24, 28, 18, 47] and randomized smoothing
[15, 36, 42, 51] that guarantee that the predicted class will remain the same
in a certified region around the input point have also been studied. Compared
to empirical robustness methods that are often shown to be broken by stronger
attacks [9, 3, 58], procedures with provable robustness guarantees are of
special importance to the study of robustness in ML as their guarantees hold
regardless of improvements in attack strategies. Among these approaches,
certified defenses based on randomized smoothing have been show to scale up to
high-dimensional inputs, such as images, and does not need to make assumptions
about the underlying model. The robustness certificates produced by these
defenses are probabilistic, meaning that they hold with high probability and
not absolute certainty.

Unlike classification problems, where certificates guarantee that the
predicted class remains unchanged under bounded-size perturbations, it is not
immediately obvious what the goal of robustness should be for problems with
structured outputs like images, text, sets, etc. While accuracy is the
standard quality measure for classification, more complex tasks may require
other quality metrics like total variation for images, intersection over union
for object localization, earth-mover distance for distributions, etc. In
general, neural networks can be cast as functions of the type
$f:\mathbb{R}^{k}\rightarrow(M,d)$ which map a $k$ dimensional real-valued
space into a metric space $M$ with distance function $d:M\times
M\rightarrow\mathbb{R}_{\geq 0}$. In this work, we design a randomized
smoothing based technique to obtain provable robustness for functions of this
type with minimal assumptions on the distance metric $d$. We generate a robust
version $\bar{f}$ such that the change in its output, as measured by $d$, is
small for a small change in its input. More formally, given an input $x$ and
an $\ell_{2}$-perturbation size $\epsilon_{1}$, we produce a value
$\epsilon_{2}$ with the guarantee that, with high probability,

$\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;d(\bar{f}(x),\bar{f}(x^{\prime}))\leq\epsilon_{2}.$

Figure 1: Center smoothing.

Our contributions: We develop center smoothing, a procedure to make functions
like $f$ provably robust against adversarial attacks. For a given input $x$,
center smoothing samples a collection of points in the neighborhood of $x$
using a Gaussian smoothing distribution, computes the function $f$ on each of
these points and returns the center of the smallest ball enclosing at least
half the points in the output space (see figure 1). Computing the minimum
enclosing ball in the output space is equivalent to solving the 1-center
problem with outliers (hence the name of our procedure), which is an NP-
complete problem for a general metric [52]. We approximate it by computing the
point that has the smallest median distance to all the other points in the
sample. We show that the output of the smoothed function is robust to input
perturbations of bounded $\ell_{2}$-size. We restrict the input perturbations
to be inside an $\ell_{2}$-ball as the main focus of this work is on the
output space of $f$. However, our method does not critically rely on the
$\ell_{2}$ threat model or Gaussian smoothing noise, and can be adapted to
other perturbations types and smoothing distributions. Although we define the
output space as a metric, our proofs only require the symmetry property and
triangle inequality to hold. Thus, center smoothing can also be applied to
pseudometric distances that need not satisfy the identity of indiscernibles.
Many distances defined for images, such as total variation, cosine distance,
perceptual distances, etc., fall under this category. Center smoothing steps
outside the world of $\ell_{p}$ metrics, and certifies robustness in metrics
like IoU/Jaccard distance for object localization, and total-variation, which
is a good measure of perceptual similarity for images. In our experiments, we
show that this method can produce meaningful certificates for a wide variety
of output metrics without significantly compromising the quality of the base
model.

Related Work: Randomized smoothing has been extensively used for provable
adversarial robustness in the classification setting to defend against
different $\ell_{p}$ [15, 36, 51, 57, 43, 41, 37, 40] and non-$\ell_{p}$ [38,
39] threat models. Beyond classification, it has also been used for certifying
the median output of regression models [62] and the expected softmax scores of
neural networks [33]. Smoothing a bounded vector-valued function by taking the
mean of the output vectors has been shown to have a bounded Lipschitz constant
when both input and output spaces are $\ell_{2}$-metrics [60]. Center
smoothing does not require the base function to be bounded because the minimum
enclosing ball is resistant to outliers. Moving an outlier point away from
this ball does not affect the output of the smoothed function. On the other
hand, smoothing techniques that compute the mean of the output samples are
more susceptible to outliers as changing any of the samples can alter the
mean. Recently, a provable defense for segmentation tasks was developed by
certifying each individual pixel of the output using randomized smoothing
[19]. Due to the accumulating uncertainty over individual certifications, it
is difficult to produce guarantees for large images, often leading to
certified outputs with ambiguous pixels. Center smoothing bypasses this
challenge by directly certifying the similarity between a clean segmentation
output and an adversarial one under a metric such as intersection over union.

##  2 Preliminaries and Notations

Given a function $f:\mathbb{R}^{k}\rightarrow(M,d)$ and a distribution
$\mathcal{D}$ over the input space $\mathbb{R}^{k}$, let $f(\mathcal{D})$
denote the probability distribution of the output of $f$ in $M$ when the input
is drawn from $\mathcal{D}$. For a point $x\in\mathbb{R}^{k}$, let
$x+\mathcal{P}$ denote the probability distribution of the points $x+\delta$
where $\delta$ is a smoothing noise drawn from a distribution $\mathcal{P}$
over $\mathbb{R}^{k}$ and let $X$ be the random variable for $x+\mathcal{P}$.
For elements in $M$, define $\mathcal{B}(z,r)=\\{z^{\prime}\mid
d(z,z^{\prime})\leq r\\}$ as a ball of radius $r$ centered at $z$. Define a
smoothed version of $f$ under $\mathcal{P}$ as the center of the ball with the
smallest radius in $M$ that encloses at least half of the probability mass of
$f(x+\mathcal{P})$, i.e.,

$\bar{f}_{\mathcal{P}}(x)=\underset{z}{\arg\\!\min}\;r\;\text{s.t.}\;\mathbb{P}[f(X)\in\mathcal{B}(z,r)]\geq\frac{1}{2}.$

If there are multiple balls with the smallest radius satisfying the above
condition, return one of the centers arbitrarily. Let $r^{*}_{\mathcal{P}}(x)$
be the value of the minimum radius. Hereafter, we ignore the subscripts and
superscripts in the above definitions whenever they are obvious from context.
In this work, we sample the noise vector $\delta$ from an i.i.d Gaussian
distribution of variance $\sigma^{2}$ in each dimension, i.e.,
$\delta\sim\mathcal{N}(0,\sigma^{2}I)$.

###  2.1 Gaussian Smoothing

Cohen et al. in 2019 showed that a classifier
$h:\mathbb{R}^{k}\rightarrow\mathcal{Y}$ smoothed with a Gaussian noise
$\mathcal{N}(0,\sigma^{2}I)$ as,

$\bar{h}(x)=\underset{c\in\mathcal{Y}}{\text{argmax}}\;\mathbb{P}\left[h(x+\delta)=c\right],$

where $\mathcal{Y}$ is a set of classes, is certifiably robust to small
perturbations in the input. Their certificate relied on the fact that, if the
probability of sampling from the top class at $x$ under the smoothing
distribution is $p$, then for an $\ell_{2}$ perturbation of size at most
$\epsilon$, the probability of the top class is guaranteed to be at least

$\displaystyle p_{\epsilon}=\Phi(\Phi^{-1}(p)-\epsilon/\sigma),$ (1)

where $\Phi$ is the CDF of the standard normal distribution
$\mathcal{N}(0,1)$. This bound applies to any $\\{0,1\\}$-function over the
input space $\mathbb{R}^{k}$, i.e., if $\mathbb{P}[h(x)=1]=p$, then for any
$\epsilon$-size perturbation $x^{\prime},\mathbb{P}[h(x^{\prime})=1]\geq
p_{\epsilon}$.

We use this bound to generate robustness certificates for center smoothing. We
identify a ball $\mathcal{B}(\bar{f}(x),R)$ of radius $R$ enclosing a very
high probability mass of the output distribution. One can define a function
that outputs one if $f$ maps a point to inside $\mathcal{B}(\bar{f}(x),R)$ and
zero otherwise. The bound in (1) gives us a region in the input space such
that for any point inside it, at least half of the mass of the output
distribution is enclosed in $\mathcal{B}(\bar{f}(x),R)$. We show in section 3
that the output of the smoothed function for a perturbed input is guaranteed
to be within a constant factor of $R$ from the output of the original input.

##  3 Center Smoothing

As defined in section 2, the output of $\bar{f}$ is the center of the smallest
ball in the output space that encloses at least half the probability mass of
the $f(x+\mathcal{P})$. Thus, in order to significantly change the output, an
adversary has to find a perturbation such that a majority of the neighboring
points map far away from $\bar{f}(x)$. However, for a function that is roughly
accurate on most points around $x$, a small perturbation in the input cannot
change the output of the smoothed function by much, thereby making it robust.

For an $\ell_{2}$ perturbation size of $\epsilon_{1}$ of an input point $x$,
let $R$ be the radius of a ball around $\bar{f}(x)$ that encloses more than
half the probability mass of $f(x^{\prime}+\mathcal{P})$ for all $x^{\prime}$
satisfying $\|x-x^{\prime}\|_{2}\leq\epsilon_{1}$, i.e.,

$\displaystyle\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;\mathbb{P}[f(X^{\prime})\in\mathcal{B}(\bar{f}(x),R)]>\frac{1}{2},$
(2)

where $X^{\prime}\sim x^{\prime}+\mathcal{P}$. Basically, $R$ is the radius of
a ball around $\bar{f}(x)$ that contains at least half the probability mass of
$f(x^{\prime}+\mathcal{P})$ for any $\epsilon_{1}$-size perturbation
$x^{\prime}$ of $x$. Then, we have the following robustness guarantee on
$\bar{f}$:

######  Theorem 1.

For all $x^{\prime}$ such that $\|x-x^{\prime}\|_{2}\leq\epsilon_{1}$,

$d(\bar{f}(x),\bar{f}(x^{\prime}))\leq 2R.$

###### Proof.

Consider the balls $\mathcal{B}(\bar{f}(x^{\prime}),r^{*}(x^{\prime}))$ and
$\mathcal{B}(\bar{f}(x),R)$ (see figure 2). From the definition of
$r^{*}(x^{\prime})$ and $R$, we know that the sum of the probability masses of
$f(x^{\prime}+\mathcal{P})$ enclosed by the two balls must be strictly greater
than one. Thus, they must have an element $y$ in common. Since $d$ satisfies
the triangle inequality, we have:

$\displaystyle d(\bar{f}(x),\bar{f}(x^{\prime}))$ $\displaystyle\leq
d(\bar{f}(x),y)+d(y,\bar{f}(x^{\prime}))$ $\displaystyle\leq
R+r^{*}(x^{\prime}).$

Since, the ball $\mathcal{B}(\bar{f}(x),R)$ encloses more than half of the
probability mass of $f(x+\mathcal{P})$, the minimum ball with at least half
the probability mass cannot have a radius greater than $R$, i.e.,
$r^{*}(x^{\prime})\leq R$. Therefore, $d(\bar{f}(x),\bar{f}(x^{\prime}))\leq
2R$. ∎

Figure 2: Robustness guarantee.

The above result, in theory, gives us a smoothed version of $f$ with a
provable guarantee of robustness. However, in practice, it may not be feasible
to obtain $\bar{f}$ just from samples of $f(x+\mathcal{P})$. Instead, we will
use some procedure that approximates the smoothed output with high
probability. For some $\Delta\in[0,1/2]$, let $\hat{r}(x,\Delta)$ be the
radius of the smallest ball that encloses at least $1/2+\Delta$ probability
mass of $f(x+\mathcal{P})$, i.e.,

$\hat{r}(x,\Delta)=\underset{z^{\prime}}{\min}\;r\;\text{s.t.}\;\mathbb{P}[f(X)\in\mathcal{B}(z^{\prime},r)]\geq\frac{1}{2}+\Delta.$

Now define a probabilistic approximation $\hat{f}(x)$ of the smoothed function
$\bar{f}$ to be a point $z\in M$, which with probability at least
$1-\alpha_{1}$ (for $\alpha_{1}\in[0,1]$), encloses at least $1/2-\Delta$
probability mass of $f(x+\mathcal{P})$ within a ball of radius
$\hat{r}(x,\Delta)$. Formally, $\hat{f}(x)$ is a point $z\in M$, such that,
with at least $1-\alpha_{1}$ probability,

$\mathbb{P}\left[f(X)\in\mathcal{B}(z,\hat{r}(x,\Delta))\right]\geq\frac{1}{2}-\Delta.$

Defining $\hat{R}$ to be the radius of a ball centered at $\hat{f}(x)$ that
satisfies:

$\displaystyle\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;\mathbb{P}[f(X^{\prime})\in\mathcal{B}(\hat{f}(x),\hat{R})]>\frac{1}{2}+\Delta,$
(3)

we can write a probabilistic version of theorem 1,

######  Theorem 2.

With probability at least $1-\alpha_{1}$,

$\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;d(\hat{f}(x),\hat{f}(x^{\prime}))\leq
2\hat{R},$

The proof of this theorem is in the appendix, and logically parallels the
proof of theorem 1.

###  3.1 Computing $\hat{f}$

For an input $x$ and a given value of $\Delta$, sample $n$ points
independently from a Gaussian distribution $x+\mathcal{N}(0,\sigma^{2}I)$
around the point $x$ and compute the function $f$ on each of these points. Let
$Z=\\{z_{1},z_{2},\ldots,z_{n}\\}$ be the set of $n$ samples of
$f(x+\mathcal{N}(0,\sigma^{2}I))$ produced in the output space. Compute the
minimum enclosing ball $\mathcal{B}(z,r)$ that contains at least half of the
points in $Z$. The following lemma bounds the radius $r$ of this ball by the
radius of the smallest ball enclosing at least $1/2+\Delta_{1}$ probability
mass of the output distribution (proof in appendix).

######  Lemma 1.

With probability at least $1-e^{-2n\Delta_{1}^{2}}$,

$r\leq\hat{r}(x,\Delta_{1}).$

Now, sample a fresh batch of $n$ random points. Let
$p_{\Delta_{1}}=\rho-\Delta_{1}$, where $\rho$ is the fraction of points that
fall inside $\mathcal{B}(z,r)$. Then, by Hoeffding’s inequality, with
probability at least $1-e^{-2n\Delta_{1}^{2}}$,

$\mathbb{P}\left[f(X)\in\mathcal{B}(z,r)\right]\geq p_{\Delta_{1}}.$

Let $\Delta_{2}=1/2-p_{\Delta_{1}}$. If
$\max(\Delta_{1},\Delta_{2})\leq\Delta$, the point $z$ satisfies the
conditions in the definition of $\hat{f}$, with at least
$1-2e^{-2n\Delta_{1}^{2}}$ probability. If
$\max(\Delta_{1},\Delta_{2})>\Delta$, discard the computed center $z$ and
abstain. In our experiments, we select $\Delta_{1},n$ and $\alpha_{1}$
appropriately so that the above process succeeds easily.

Computing the minimum enclosing ball $\mathcal{B}(z,r)$ exactly can be
computationally challenging, as for certain metrics, it is known to be NP-
complete [52]. Instead, we approximate it by computing a ball
$\beta\text{-MEB}(Z,1/2)$ that contains at least half the points in $Z$, but
has a radius that is within a $\beta$ factor of the optimal radius $r$. We
modify theorem 1 to account for this approximation (see appendix for proof).

Algorithm 1 Smooth

Input: $x\in\mathbb{R}^{k},\sigma,\Delta,\alpha_{1}$.

Output: $z\in M$.

Set $Z=\\{z_{i}\\}_{i=1}^{n}\text{ s.t. }z_{i}\sim
f(x+\mathcal{N}(0,\sigma^{2}I))$.

Set $\Delta_{1}=\sqrt{\ln\left(2/\alpha_{1}\right)/2n}$.

Compute $z=\beta$-MEB$(Z,1/2)$.

Re-sample $Z$.

Compute $p_{\Delta_{1}}$.

Set $\Delta_{2}=1/2-p_{\Delta_{1}}$.

If $\Delta<\max(\Delta_{1},\Delta_{2})$, discard $z$ and abstain.

Algorithm 2 Certify

Input: $x\in\mathbb{R}^{k},\epsilon_{1},\sigma,\Delta,\alpha_{1},\alpha_{2}$.

Output: $\epsilon_{2}\in\mathbb{R}$.

Compute $\hat{f}(x)$ using algorithm 1.

Set $Z=\\{z_{i}\\}_{i=1}^{m}\text{ s.t. }z_{i}\sim
f(x+\mathcal{N}(0,\sigma^{2}I))$.

Compute $\tilde{\mathcal{R}}=\\{d(\hat{f}(x),f(z_{i}))\mid z_{i}\in Z\\}$.

Set $p=\Phi(\Phi^{-1}(1/2+\Delta)+\epsilon_{1}/\sigma)$.

Set $q=p+\sqrt{\ln(1/\alpha_{2})/2m}$.

Set $\hat{R}=q$th-quantile of $\tilde{\mathcal{R}}$.

Set $\epsilon_{2}=(1+\beta)\hat{R}$.

######  Theorem 3.

With probability at least $1-\alpha_{1}$,

$\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;d(\hat{f}(x),\hat{f}(x^{\prime}))\leq(1+\beta)\hat{R}$

where $\alpha_{1}=2e^{-2n\Delta_{1}^{2}}$.

We use a simple approximation that works for all metrics and achieves an
approximation factor of two, producing a certified radius of $3\hat{R}$. It
computes a point from the set $Z$, instead of a general point in $M$, that has
the minimum median distance from all the points in the set (including itself).
This can be achieved using $O(n^{2})$ pair-wise distance computations. To see
how the factor 2-approximation is achieved, consider the optimal ball with
radius $r$. By triangle inequality of $d$, each pair of points is at most $2r$
distance from each other. Thus, a ball with radius $2r$, centered at any one
of these points will cover every other point in the optimal ball. Better
approximations can be obtained for specific norms, e.g., there exists a
$(1+\epsilon)$-approximation algorithm for the $\ell_{2}$ norm [7]. For graph
distances or when the support of the output distribution is a small discrete
set of points, the optimal radius can be computed exactly using the above
algorithm. The smoothing procedure is outlined in algorithm 1.

###  3.2 Certifying $\hat{f}$

Given an input $x$, compute $\hat{f}(x)$ as described above. Now, we need to
compute a radius $\hat{R}$ that satisfies condition 3. As per bound 1, in
order to maintain a probability mass of at least $1/2+\Delta$ for any
$\epsilon_{1}$-size perturbation of $x$, the ball
$\mathcal{B}(\hat{f}(x),\hat{R})$ must enclose at least

$\displaystyle
p=\Phi\left(\Phi^{-1}\left(\frac{1}{2}+\Delta\right)+\frac{\epsilon_{1}}{\sigma}\right)$
(4)

probability mass of $f(x+\mathcal{P})$. Again, just as in the case of
estimating $\bar{f}$, we may only compute $\hat{R}$ from a finite number of
samples $m$ of the distribution $f(x+\mathcal{P})$. For each sample $z_{i}\sim
x+\mathcal{P}$, we compute the distance $d(\hat{f}(x),f(z_{i}))$ and set
$\hat{R}$ to be the $q$th-quantile $\tilde{R}_{q}$ of these distances for a
$q$ that is slightly greater than $p$ (see equation 5 below). The $q$th-
quantile $\tilde{R}_{q}$ is a value larger than at least $q$ fraction of the
samples. We set $q$ as,

$\displaystyle q=p+\sqrt{\frac{\ln\left(1/\alpha_{2}\right)}{2m}},$ (5)

for some small $\alpha_{2}\in[0,1]$. This guarantees that, with high
probability, the ball $\mathcal{B}(\hat{f}(x),\tilde{R}_{q})$ encloses at
least $p$ fraction of the probability mass of $f(x+\mathcal{P})$. We prove the
following lemma by bounding the cumulative distribution function of the
distances of $f(z_{i})$s from $\hat{f}(x)$ using the
Dvoretzky–Kiefer–Wolfowitz inequality.

######  Lemma 2.

With probability $1-\alpha_{2}$,

$\mathbb{P}\left[f(X)\in\mathcal{B}(\hat{f}(x),\tilde{R}_{q})\right]>p.$

Combining with theorem 3, we have the final certificate:

$\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;d(\hat{f}(x),\hat{f}(x^{\prime}))\leq(1+\beta)\hat{R},$

with probability at least $1-\alpha$, for $\alpha=\alpha_{1}+\alpha_{2}$. In
our experiments, we set $\alpha_{1}=\alpha_{2}=0.005$ to achieve an overall
success probability of $1-\alpha=0.99$, and calculate the required
$\Delta_{1},\Delta_{2}$ and $q$ values accordingly. We set $\Delta$ to be as
small as possible without violating $\max(\Delta_{1},\Delta_{2})\leq\Delta$
too often. We use a $\beta=2$-approximation for computing the minimum
enclosing ball in the smoothing step. Algorithm 2 provides the pseudocode for
the certification procedure.

##  4 Relaxing Metric Requirements

Although we defined our procedure for metric outputs, our analysis does not
critically use all the properties of a metric. For instance, we do not require
$d(z_{1},z_{2})$ to be strictly greater than zero for $z_{1}\neq z_{2}$. An
example of such a distance measure is the total variation distance that
returns zero for two vectors that differ by a constant amount on each
coordinate. Our proofs do implicitly use the symmetry property, but asymmetric
distances can be converted to symmetric ones by taking the sum or the max of
the distances in either directions. Perhaps the most important property of
metrics that we use is the triangle inequality as it is critical for the
robustness guarantee of the smoothed function. However, even this constraint
may be partially relaxed. It is sufficient for the distance function $d$ to
satisfy the triangle inequality approximately, i.e.,
$d(a,c)\leq\gamma(d(a,b)+d(b,c))$, for some constant $\gamma$. The theorems
and lemmas can be adjusted to account for this approximation, e.g., the bound
in theorem 1 will become $2\gamma R$. A commonly used distance measure for
comparing images and documents is the cosine distance defined as the inner-
product of two vectors after normalization. This distance can be show to be
proportional to the squared Euclidean distance between the normalized vectors
which satisfies the relaxed version of triangle inequality for $\gamma=2$.

These relaxations extend the scope of center smoothing to many commonly used
distance measures that need not necessarily satisfy all the metric properties.
For instance, perceptual distance metrics measure the distance between two
images in some feature space rather than image space. Such distances align
well with human judgements when the features are extracted from a deep neural
network [65] and are considered more natural measures for image similarity.
For two images $I_{1}$ and $I_{2}$, let $\phi(I_{1})$ and $\phi(I_{2})$ be
their feature representations. Then, for a distance function $d$ in the
feature space that satisfies the relaxed triangle inequality, we can define a
distance function $d_{\phi}(I_{1},I_{2})=d(\phi(I_{1}),\phi(I_{2}))$ in the
image space, which also satisfies the relaxed triangle inequality. For any
image $I_{3}$,

$\displaystyle d_{\phi}(I_{1},I_{2})$
$\displaystyle=d(\phi(I_{1}),\phi(I_{2}))$
$\displaystyle\leq\gamma\left(d(\phi(I_{1}),\phi(I_{3}))+d(\phi(I_{3}),\phi(I_{2}))\right)$
$\displaystyle=\gamma\left(d_{\phi}(I_{1},I_{3})+d_{\phi}(I_{3},I_{2})\right).$

##  5 Experiments

We apply center smoothing to certify a wide range of output metrics: Jaccard
distance based on intersection over union (IoU) of sets, total variation
distances for images, and perceptual distance. We certify the bounding box
generated by a face detector – a key component of most facial recognition
systems – by guaranteeing the minimum overlap (measured using IoU) it must
have with the output under an adversarial perturbation of the input. For
instance, if $\epsilon_{1}=0.2$, the Jaccard distance (1-IoU) is guaranteed to
be bounded by 0.2, which implies that the bounding box of a perturbed image
must have at least 80% overlap with that of the clean image. We use a pre-
trained face detection model for this experiment. We certify the perceptual
distance of the output of a generative model (trained on ImageNet) that
produces $128\times 128$ RGB images using a high-dimensional version of the
smoothing procedure Smooth-HD described in the appendix. For total variation
distance, we use simple, easy-to-train convolutional neural network based
dimensionality reduction (autoencoder) and image reconstruction models. Our
goal is to demonstrate the effectiveness of our method for a wide range of
applications and so, we place less emphasis on the performance of the
underlying models being smoothed. In each case, we show that our method is
capable of generating certified guarantees without significantly degrading the
performance of the underlying model. We provide additional experiments for
other metrics and parameter settings in the appendix.

As is common in the randomized smoothing literature, we train our base models
(except for the pre-trained ones) on noisy data with different noise levels
$\sigma_{train}=0.1,0.2,\ldots,0.5$ to make them more robust to input
perturbations. We keep the smoothing noise $\sigma$ of the robust model same
as the training noise $\sigma_{train}$ of the base model. We use $n=10^{4}$
samples to estimate the smoothed function and $m=10^{6}$ samples to generate
certificates, unless stated otherwise. We set $\Delta=0.05,\alpha_{1}=0.005$
and $\alpha_{2}=0.005$ as discussed in previous sections. We grow the
smoothing noise $\sigma$ linearly with the input perturbation $\epsilon_{1}$.
Specifically, we maintain $\epsilon_{1}=h\sigma$ for different values of
$h=2,1$ and 1.5 in our experiments. We plot the median certified output radius
$\epsilon_{2}$ and the median smoothing error, defined as the distance between
the outputs of the base model and the smoothed model $d(f(x),\hat{f}(x))$, of
fifty random test examples for different values of $\epsilon_{1}$. In all our
experiments, we observe that both these quantities increase as the input
radius $\epsilon_{1}$ increases, but the smoothing error remains significantly
below the certified output radius. Also, increasing the value of $h$ improves
the quality of the certificates (lower $\epsilon_{2}$). This could be due to
the fact that for a higher $h$, the smoothing noise $\sigma$ is lower (keeping
$\epsilon_{1}$ constant), which means that the radius of the minimum enclosing
ball in the output space is smaller leading to a tighter certificate. However,
setting $h$ too high can cause the value of $q$ in equation 5 to exceed one
($q$ depends on $p$, which in turn depends on $h$ in eq. 4), leading the
certification procedure (algorithm 2) to fail. We ran all our experiments on a
single NVIDIA GeForce RTX 2080 Ti GPU in an internal cluster. Each of the
fifty examples we certify took somewhere between 1-3 minutes depending on the
underlying model.

###  5.1 Jaccard distance

(a) Certifying Jaccard Distance (1 - IoU).

(b) Smoothed Output.

Figure 3: Face Detection on CelebA using MTCNN detector: Part (a) plots the
certified output radius $\epsilon_{2}$ and the smoothing error for $h=1$ and
2. Part (b) compares the smoothed output (blue box) to the output of the base
model (green box, mostly hidden behind the blue box) showing a significant
overlap.

It is known that facial recognition systems can be deceived to evade
detection, impersonate authorized individuals and even render completely
ineffective [59, 55, 20]. Most facial recognition systems first detect a
region that contains a persons face, e.g. a bounding box, and then uses facial
features to identify the individual in the image. To evade detection, an
attacker may seek to degrade the quality of the bounding boxes produced by the
detector and can even cause it to detect no box at all. Bounding boxes are
often interpreted as sets and the their quality is measured as the amount of
overlap with the desired output. When no box is output, we say the overlap is
zero. The overlap between two sets is defined as the ratio of the size of the
intersection between them to the size of their union (IoU). Thus, to certify
the robustness of the output of a face detector, it makes sense to bound the
worst-case IoU of the output of an adversarial input to that of a clean input.
The corresponding distance function, known as Jaccard distance, is defined as
$1-IoU$ which defines a metric over the universe of sets.

$IoU(A,B)=\frac{|A\cap B|}{|A\cup B|},\quad
d_{J}(A,B)=1-IoU(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$

In this experiment, we certify the output of a pre-trained face detection
model MTCNN [64] on the CelebA face dataset [45]. We set $n=5000$ and
$m=10000$, and use default values for other parameters discussed above. Figure
3(a) plots the certified output radius $\epsilon_{2}$ and the smoothing error
for $h=\epsilon_{1}/\sigma=1$ and 2 for $\epsilon_{1}=0.1,0.2,\ldots,0.5$.
Certifying the Jaccard distance allows us to certify IoU as well, e.g., for
$h=2$, $\epsilon_{2}$ is consistently below 0.2 which means that even the
worst bounding box under adversarial perturbation of the input has an overlap
of at least 80% with the box for the clean input. The low smoothing error
shows that the performance of the base model does not drop significantly as
the actual output of the smoothed model has a large overlap with that of the
base model. Figure 3(b) compares the outputs of the smoothed model (blue box)
and the base model (green box). For most of the images, the blue box overlaps
with the green one almost perfectly.

###  5.2 Perceptual Distance

Deep generative models like GANs and VAEs have been shown to be vulnerable to
adversarial attacks [31]. One attack model is to produce an adversarial
example that is close to the original input in the latent space, measured
using $\ell_{2}$-norm. The goal is to make the model generate a different
looking image using a latent representation that is close to that of the
original image. We apply center smoothing to a generative adversarial network
BigGAN pre-trained on ImageNet images [5]. We use the version of the GAN that
generates $128\times 128$ resolution ImageNet images from a set of 128 latent
variables. Since we are interested in producing similar looking images for
similar latent representations, a good output metric would be the perceptual
distance between two images measured by LPIPS metric [65]. This distance
function takes in two images, passes them through a deep neural network, such
as VGG, and computes a weighted sum of the square of the differences of the
activations (after some normalization) produced by the two images. The process
can be thought of as generating two feature vectors $\phi_{1}$ and $\phi_{2}$
for the two input images $I_{1}$ and $I_{2}$ respectively, then computing a
weighted sum of the element-wise square of the differences between the two
feature vectors, i.e.,

$d(I_{1},I_{2})=\sum_{i}w_{i}(\phi_{1i}-\phi_{2i})^{2}$

The square of differences metric can be shown to follow the relaxed triangle
inequality for $\gamma=2$. Therefore, the the final bound on the certified
output radius will be $\gamma(1+2\gamma)\hat{R}=10\hat{R}$. Figure 4(a) plots
the median smoothing error and certified output radius $\epsilon_{2}$ for
fifty randomly picked latent vectors for $\epsilon_{1}=0.01,0.02,\ldots,0.05$
and $h=1,1.5$. For these experiments, we set $n=2000,m=10^{4}$ and
$\Delta=0.8$. We use the modified smoothing procedure Smooth-HD (see appendix)
for high-dimensional outputs with a small batch size of 150 to accommodate the
samples in memory. It takes about three minutes to smooth and certify each
input on a single NVIDIA GeForce RTX 2080 Ti GPU in an internal cluster. Due
to the higher factor of ten in the certified output radius in this case
compared to our other experiments where the factor is three, the certified
output radius increases faster with the input radius $\epsilon_{1}$, but the
smoothing error remains low showing that, in practice, the method does not
significantly degrade the performance of the base model. Figure 4(b) shows
that, visually, the smoothed output is not very different from the output of
the base model. The input radii we certify for are lower in this case than our
other experiments due to the low dimensionality (only 128 dimensions) of the
input (latent) space as compared to the input (image) spaces in our other
experiments.

(a) Certifying perceptual distance.

(b) Model Output vs Smoothed Output.

Figure 4: Generative model for ImageNet: Part (a) plots the certified output
radius $\epsilon_{2}$ and the smoothing error for $h=1$ and 1.5. Part (b)
compares the output of the base model to that of the smoothed model.

###  5.3 Total Variation Distance

The total variation norm of a vector $x$ is defined as the sum of the
magnitude of the difference between pairs of coordinates defined by a
neighborhood set $N$. For a 1-dimensional array $x$ with $k$ elements, one can
define the neighborhood as the set of consecutive elements.

$TV(x)=\sum_{(i,j)\in N}|x_{i}-x_{j}|,\quad
TV_{1D}(x)=\sum_{i=1}^{k-1}|x_{i}-x_{i+1}|.$

Similarly, for a grayscale image represented by a $h\times w$ 2-dimensional
array $x$, the neighborhood can be defined as the next element (pixel) in the
row/column. In case of an RGB image, the difference between the neighboring
pixels is a vector, whose magnitude can be computed using an $\ell_{p}$-norm.
For, our experiments we use the $\ell_{1}$-norm.

$TV_{RGB}(x)=\sum_{i=1}^{h-1}\sum_{j=1}^{w-1}\|x_{i,j}-x_{i+1,j}\|_{1}+\|x_{i,j}-x_{i,j+1}\|_{1}$

The total variation distance between two images $I_{1}$ and $I_{2}$ can be
defined as the total variation norm of the difference $I_{1}-I_{2}$, i.e.,
$TVD(I_{1},I_{2})=TV(I_{1}-I_{2})$. The above distance defines a pseudometric
over the space of images as it satisfies the symmetry property and the
triangle inequality, but may violate the identity of indiscernibles as an
image obtained by adding the same value to all the pixel intensities has a
distance of zero from the original image. However, as noted in section 4, our
certificates hold even for this setting.

(a) Dimensionality Reduction on MNIST

(b) Dimensionality Reduction on CIFAR-10

(c) Image Reconstruction on MNIST

(d) Image Reconstruction on CIFAR-10

Figure 5: Certifying Total Variation Distance

We certify total variation distance for the problems of dimensionality
reduction and image reconstruction on MNIST [16] and CIFAR-10 [32]. The base-
model for dimensionality reduction is an autoencoder that uses convolutional
layers in its encoder module to map an image down to a small number of latent
variables. The decoder applies a set of de-convolutional operations to
reconstruct the same image. We insert batch-norm layers in between these
operations to improve performance. For image reconstruction, the goal is to
recover an image from small number of measurements of the original image. We
apply a transformation defined by Gaussian matrix $A$ on each image to obtain
the measurements. The base model tries to reconstruct the original image from
the measurements. The attacker, in this case, is assumed to add a perturbation
in the measurement space instead of the image space (as in dimensionality
reduction). The model first reverts the measurement vector to a vector in the
image space by simply applying the pseudo-inverse of $A$ and then passes it
through a similar autoencoder model as for dimensionality reduction. We
present results for $\epsilon_{1}=0.2,0.4,\ldots,1.0$ and $h=2,1.5$ and use
256 latent dimensions and measurements for these experiments in figure 5. To
put these plots in perspective, the maximum TVD between two CIFAR-10 images
could be $6\times 31\times 31=5766$ and between MNIST images could be $2\times
27\times 27=1458$ (pixel values between 0 and 1).

##  6 Conclusion

Provable adversarial robustness can be extended beyond classification tasks to
problems with structured outputs. We design a smoothing-based procedure that
can make a model of this kind provably robust against norm bounded adversarial
perturbations of the input. In our experiments, we demonstrate that this
method can generate meaningful certificates under a wide variety of distance
metrics in the output space without significantly compromising the quality of
the base model. We also note that the metric requirements on the distance
measure can be partially relaxed in exchange for weaker certificates.

We focus on $\ell_{2}$-norm bounded adversaries and the Gaussian smoothing
distribution. An important direction for future investigation could be whether
this method can be generalised beyond $\ell_{p}$-adversaries to more natural
threat models, e.g., adversaries bounded by total variation distance,
perceptual distance, cosine distance, etc. Center smoothing does not
critically rely on the shape of the smoothing distribution or the threat
model. Thus, improvements in these directions could potentially be coupled
with our method to further broaden the scope of provable robustness in machine
learning.

##  7 Acknowledgements

This work was supported by the AFOSR MURI program, DARPA GARD, the Office of
Naval Research, and the National Science Foundation Division of Mathematical
Sciences.

## References

  * Antun et al. [2019] Vegard Antun, Francesco Renna, Clarice Poon, Ben Adcock, and Anders C. Hansen.  On instabilities of deep learning in image reconstruction - does AI come at a cost?  _CoRR_ , abs/1902.05300, 2019.  URL http://arxiv.org/abs/1902.05300.
  * Arnab et al. [2017] Anurag Arnab, Ondrej Miksik, and Philip H. S. Torr.  On the robustness of semantic segmentation models to adversarial attacks.  _CoRR_ , abs/1711.09856, 2017.  URL http://arxiv.org/abs/1711.09856.
  * 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.
  * Behzadan and Munir [2017] Vahid Behzadan and Arslan Munir.  Vulnerability of deep reinforcement learning to policy induction attacks.  In Petra Perner, editor, _Machine Learning and Data Mining in Pattern Recognition - 13th International Conference, MLDM 2017, New York, NY, USA, July 15-20, 2017, Proceedings_ , volume 10358 of _Lecture Notes in Computer Science_ , pages 262–275. Springer, 2017.  doi: 10.1007/978-3-319-62416-7\\_19.  URL https://doi.org/10.1007/978-3-319-62416-7_19.
  * Brock et al. [2019] Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale GAN training for high fidelity natural image synthesis.  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=B1xsqj09Fm.
  * Buckman et al. [2018] Jacob Buckman, Aurko Roy, Colin Raffel, and Ian J. Goodfellow.  Thermometer encoding: One hot way to resist adversarial examples.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * Bundefineddoiu et al. [2002] Mihai Bundefineddoiu, Sariel Har-Peled, and Piotr Indyk.  Approximate clustering via core-sets.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing_ , STOC ’02, page 250–257, New York, NY, USA, 2002. Association for Computing Machinery.  ISBN 1581134959.  doi: 10.1145/509907.509947.  URL https://doi.org/10.1145/509907.509947.
  * Calivá et al. [2020] Francesco Calivá, Kaiyang Cheng, Rutwik Shah, and Valentina Pedoia.  Adversarial robust training in mri reconstruction.  _arXiv preprint arXiv:2011.00070_ , 2020.
  * 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.
  * Carlini and Wagner [2018] Nicholas Carlini and David A. Wagner.  Audio adversarial examples: Targeted attacks on speech-to-text.  _CoRR_ , abs/1801.01944, 2018.  URL http://arxiv.org/abs/1801.01944.
  * Chen et al. [2017] Hongge Chen, Huan Zhang, Pin-Yu Chen, Jinfeng Yi, and Cho-Jui Hsieh.  Show-and-fool: Crafting adversarial examples for neural image captioning.  _CoRR_ , abs/1712.02051, 2017.  URL http://arxiv.org/abs/1712.02051.
  * Cheng et al. [2020] Kaiyang Cheng, Francesco Calivá, Rutwik Shah, Misung Han, Sharmila Majumdar, and Valentina Pedoia.  Addressing the false negative problem of deep learning mri reconstruction models by adversarial attacks and robust training.  In Tal Arbel, Ismail Ben Ayed, Marleen de Bruijne, Maxime Descoteaux, Herve Lombaert, and Christopher Pal, editors, _Proceedings of the Third Conference on Medical Imaging with Deep Learning_ , volume 121 of _Proceedings of Machine Learning Research_ , pages 121–135, Montreal, QC, Canada, 06–08 Jul 2020. PMLR.  URL http://proceedings.mlr.press/v121/cheng20a.html.
  * Chiang et al. [2020] Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein.  Certified defenses for adversarial patches.  In _8th International Conference on Learning Representations_ , 2020\.
  * Choi et al. [2019] Jun-Ho Choi, Huan Zhang, Jun-Hyuk Kim, Cho-Jui Hsieh, and Jong-Seok Lee.  Evaluating robustness of deep image super-resolution against adversarial attacks.  In _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019_ , pages 303–311. IEEE, 2019.  doi: 10.1109/ICCV.2019.00039.  URL https://doi.org/10.1109/ICCV.2019.00039.
  * 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.
  * Deng [2012] Li Deng.  The mnist database of handwritten digit images for machine learning research [best of the web].  _IEEE Signal Processing Magazine_ , 29(6):141–142, 2012.  doi: 10.1109/MSP.2012.2211477.
  * Dhillon et al. [2018] Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Animashree Anandkumar.  Stochastic activation pruning for robust adversarial defense.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * Dvijotham et al. [2018] Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O’Donoghue, Jonathan Uesato, and Pushmeet Kohli.  Training verified learners with learned verifiers, 2018.
  * Fischer et al. [2021] Marc Fischer, Maximilian Baader, and Martin T. Vechev.  Scalable certified segmentation via randomized smoothing.  _CoRR_ , abs/2107.00228, 2021.  URL https://arxiv.org/abs/2107.00228.
  * Frearson and Nguyen [2020] Morgan Frearson and Kien Nguyen.  Adversarial attack on facial recognition using visible light.  _arXiv preprint arXiv:2011.12680_ , 2020.
  * Gleave et al. [2020] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell.  Adversarial policies: Attacking deep reinforcement learning.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=HJgEMpVFwB.
  * Gong et al. [2017] Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku.  Adversarial and clean data are not twins.  _CoRR_ , abs/1704.04960, 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.
  * 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.
  * Grosse et al. [2017] Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. McDaniel.  On the (statistical) detection of adversarial examples.  _CoRR_ , abs/1702.06280, 2017.
  * Guo et al. [2018] Chuan Guo, Mayank Rana, Moustapha Cissé, and Laurens van der Maaten.  Countering adversarial images using input transformations.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * He et al. [2019] Xiang He, Sibei Yang, Guanbin Li, Haofeng Li, Huiyou Chang, and Yizhou Yu.  Non-local context encoder: Robust biomedical image segmentation against adversarial attacks.  _CoRR_ , abs/1904.12181, 2019.  URL http://arxiv.org/abs/1904.12181.
  * 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.
  * Huang et al. [2017] Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel.  Adversarial attacks on neural network policies.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings_. OpenReview.net, 2017.  URL https://openreview.net/forum?id=ryvlRyBKl.
  * Kang et al. [2020] Xu Kang, Bin Song, Xiaojiang Du, and Mohsen Guizani.  Adversarial attacks for image segmentation on multiple lightweight models.  _IEEE Access_ , 8:31359–31370, 2020.  doi: 10.1109/ACCESS.2020.2973069.
  * Kos et al. [2018] Jernej Kos, Ian Fischer, and Dawn Song.  Adversarial examples for generative models.  In _2018 IEEE Security and Privacy Workshops, SP Workshops 2018, San Francisco, CA, USA, May 24, 2018_ , pages 36–42. IEEE Computer Society, 2018.  doi: 10.1109/SPW.2018.00014.  URL https://doi.org/10.1109/SPW.2018.00014.
  * [32] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton.  Cifar-10 (canadian institute for advanced research).  URL http://www.cs.toronto.edu/~kriz/cifar.html.
  * Kumar et al. [2020] Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein.  Certifying confidence 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.  URL https://proceedings.neurips.cc/paper/2020/hash/37aa5dfc44dddd0d19d4311e2c7a0240-Abstract.html.
  * Kurakin et al. [2017] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017.  URL https://openreview.net/forum?id=BJm4T4Kgx.
  * 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.
  * 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.
  * Lee et al. [2019] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S. Jaakkola.  Tight certificates of adversarial robustness for randomly 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 4911–4922, 2019.
  * Levine and Feizi [2019] Alexander Levine and Soheil Feizi.  Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks, 2019.
  * Levine and Feizi [2020a] Alexander Levine and Soheil Feizi.  (de)randomized smoothing for certifiable defense against patch attacks.  _CoRR_ , abs/2002.10733, 2020a.  URL https://arxiv.org/abs/2002.10733.
  * 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.
  * Levine et al. [2020] Alexander Levine, Aounon Kumar, Thomas Goldstein, and Soheil Feizi.  Tight second-order certificates for randomized smoothing, 2020.
  * Li et al. [2019a] 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, 2019a.
  * Li et al. [2019b] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin.  Second-order adversarial attack and certifiable robustness, 2019b.  URL https://openreview.net/forum?id=SyxaYsAqY7.
  * Li and Li [2017] Xin Li and Fuxin Li.  Adversarial examples detection in deep networks with convolutional filter statistics.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pages 5775–5783, 2017.
  * Liu et al. [2015] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision (ICCV)_ , December 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.
  * Mirman et al. [2018] Matthew Mirman, Timon Gehr, and Martin Vechev.  Differentiable abstract interpretation for provably robust neural networks.  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 3578–3586. PMLR, 10–15 Jul 2018.  URL http://proceedings.mlr.press/v80/mirman18b.html.
  * Pattanaik et al. [2018] Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary.  Robust deep reinforcement learning with adversarial attacks.  In Elisabeth André, Sven Koenig, Mehdi Dastani, and Gita Sukthankar, editors, _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018_ , pages 2040–2042. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018.  URL http://dl.acm.org/citation.cfm?id=3238064.
  * 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.
  * Raj et al. [2020] Ankit Raj, Yoram Bresler, and Bo Li.  Improving robustness of deep-learning-based image reconstruction.  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 7932–7942. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/raj20a.html.
  * 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.
  * Shenmaier [2015] Vladimir Shenmaier.  Complexity and approximation of the smallest k-enclosing ball problem.  _European Journal of Combinatorics_ , 48:81 – 87, 2015\.  ISSN 0195-6698.  doi: https://doi.org/10.1016/j.ejc.2015.02.011.  URL http://www.sciencedirect.com/science/article/pii/S0195669815000335.
  * 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, 2020.
  * Song et al. [2018] Qing Song, Yingqi Wu, and Lu Yang.  Attacks on state-of-the-art face recognition using attentional adversarial attack generative network.  _CoRR_ , abs/1811.12026, 2018.  URL http://arxiv.org/abs/1811.12026.
  * 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.
  * Teng et al. [2020] Jiaye Teng, Guang-He Lee, and Yang Yuan.  $\ell_{1}$ adversarial robustness certificates: a randomized smoothing approach, 2020.  URL https://openreview.net/forum?id=H1lQIgrFDS.
  * 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.
  * Vakhshiteh et al. [2020] Fatemeh Vakhshiteh, Raghavendra Ramachandra, and Ahmad Nickabadi.  Threat of adversarial attacks on face recognition: A comprehensive survey.  _arXiv preprint arXiv:2007.11709_ , 2020.
  * Wolf [2019] Adva Wolf.  Making medical image reconstruction adversarially robust.  2019\.  URL http://cs229.stanford.edu/proj2019spr/report/97.pdf.
  * 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.
  * yeh Chiang et al. [2020] Ping yeh Chiang, Michael J. Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein.  Detection as regression: Certified object detection by median smoothing, 2020.
  * Yin et al. [2018] Minghao Yin, Yongbing Zhang, Xiu Li, and Shiqi Wang.  When deep fool meets deep prior: Adversarial attack on super-resolution network.  In _Proceedings of the 26th ACM International Conference on Multimedia_ , MM ’18, page 1930–1938, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450356657.  doi: 10.1145/3240508.3240603.  URL https://doi.org/10.1145/3240508.3240603.
  * Zhang et al. [2016] Kaipeng Zhang, Zhanpeng Zhang, Zhifeng Li, and Yu Qiao.  Joint face detection and alignment using multi-task cascaded convolutional networks.  _CoRR_ , abs/1604.02878, 2016.  URL http://arxiv.org/abs/1604.02878.
  * Zhang et al. [2018] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018_ , pages 586–595. IEEE Computer Society, 2018.  doi: 10.1109/CVPR.2018.00068.  URL http://openaccess.thecvf.com/content_cvpr_2018/html/Zhang_The_Unreasonable_Effectiveness_CVPR_2018_paper.html.

##  Appendix A Proof of Theorem 2

Let $z^{\prime}=\hat{f}(x^{\prime})$. Then, by definition of $\hat{f}$,

$\displaystyle\mathbb{P}\left[f(X^{\prime})\in\mathcal{B}(z^{\prime},\hat{r}(x^{\prime},\Delta))\right]\geq\frac{1}{2}-\Delta,$
(6)

where $X^{\prime}\sim x^{\prime}+\mathcal{P}$ and

$\hat{r}(x^{\prime},\Delta)=\underset{z^{\prime\prime}}{\min}\;r\;\text{s.t.}\;\mathbb{P}[f(X^{\prime})\in\mathcal{B}(z^{\prime\prime},r)]\geq\frac{1}{2}+\Delta.$

And, by definition of $\hat{R}$,

$\displaystyle\mathbb{P}[f(X^{\prime})\in\mathcal{B}(\hat{f}(x),\hat{R})]>\frac{1}{2}+\Delta.$
(7)

Therefore, from (6) and (7),
$\mathcal{B}(z^{\prime},\hat{r}(x^{\prime},\Delta))$ and
$\mathcal{B}(\hat{f}(x),\hat{R})$ must have a non-empty intersection. Let, $y$
be a point in that intersection. Then,

$\displaystyle d(\hat{f}(x),\hat{f}(x^{\prime}))$ $\displaystyle\leq
d(\hat{f}(x),y)+d(y,z^{\prime})$
$\displaystyle\leq\hat{r}(x^{\prime},\Delta)+\hat{R}.$

Since, by definition, $\hat{r}(x^{\prime},\Delta)$ is the radius of the
smallest ball with $1/2+\Delta$ probability mass of
$f(x^{\prime}+\mathcal{P})$ over all possible centers in $\mathbb{R}^{k}$ and
$\hat{R}$ is the radius of the smallest such ball centered at $\hat{f}(x)$, we
must have $\hat{r}(x^{\prime},\Delta)\leq\hat{R}$. Therefore,

$d(\hat{f}(x),\hat{f}(x^{\prime}))\leq 2\hat{R}.$

##  Appendix B Proof of Lemma 1

Consider the smallest ball $\mathcal{B}(z^{\prime},\hat{r}(x,\Delta_{1}))$
that encloses at least $1/2+\Delta_{1}$ probability mass of
$f(x+\mathcal{P})$. By Hoeffding’s inequality, with at least
$1-e^{-2n\Delta_{1}^{2}}$ probability, at least half the points in $Z$ must be
in this ball. Since, $r$ is the radius of the minimum enclosing ball that
contains at least half of the points in $Z$, we have
$r\leq\hat{r}(x,\Delta_{1})$.

##  Appendix C Proof of Theorem 3

$\beta$-MEB$(Z,1/2)$ computes a $\beta$-approximation of the minimum enclosing
ball that contains at least half of the points of $Z$. Therefore, by lemma 1,
with probability at least $1-e^{-2n\Delta_{1}^{2}}$,

$\beta\text{-MEB}(Z,1/2)\leq\beta\hat{r}(x,\Delta_{1})\leq\beta\hat{r}(x,\Delta),$

since $\Delta\geq\Delta_{1}$. Thus, the procedure to compute $\hat{f}$, if
succeeds, will output a point $z\in\mathbb{R}^{k}$ which, with probability at
least $1-2e^{-2n\Delta_{1}^{2}}$, will satisfy,

$\mathbb{P}\left[f(X)\in\mathcal{B}(z,\beta\hat{r}(x,\Delta))\right]\geq\frac{1}{2}-\Delta.$

Now, using the definition of $\hat{R}$ and following the same reasoning as
theorem 2, we can say that,

$\displaystyle d(\hat{f}(x),\hat{f}(x^{\prime}))$
$\displaystyle\leq\beta\hat{r}(x^{\prime},\Delta)+\hat{R}$
$\displaystyle\leq(1+\beta)\hat{R}.$

##  Appendix D Proof of Lemma 2

Given $z=\hat{f}(x)$, define a random variable $Q=d(z,f(X))$, where is $X\sim
x+\mathcal{P}$. For $m$ i.i.d. samples of $X$, the values of $Q$ are
independently and identically distributed. Let $F(r)$ denote the true
cumulative distribution function of $Q$ and define the empirical cdf
$F_{m}(r)$ to be the fraction of the $m$ samples of $Q$ that are less than or
equal to $r$, i.e.,

$F_{m}(r)=\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}_{\\{Q_{i}\leq r\\}}$

Using the Dvoretzky–Kiefer–Wolfowitz inequality, we have,

$\mathbb{P}\left[\sup_{r\in\mathbb{R}}\left(F_{m}(r)-F(r)\right)>\epsilon\right]\leq
e^{-2m\epsilon^{2}}$

for $\epsilon\geq\sqrt{\frac{1}{2m}\ln 2}$. Setting,
$e^{-2m\epsilon^{2}}=\alpha_{2}$ for some $\alpha_{2}\leq 1/2$, we have,

$\sup_{r\in\mathbb{R}}\left(F_{m}(r)-F(r)\right)<\sqrt{\frac{\ln\left(1/\alpha_{2}\right)}{2m}}$

with probability at least $1-\alpha_{2}$. Set $r=\tilde{R}_{q}$, the $q$th
quantile of of the $m$ samples. Then,

$\displaystyle F(\tilde{R}_{q})$
$\displaystyle>F_{m}(\tilde{R}_{q})-\sqrt{\frac{\ln\left(1/\alpha_{2}\right)}{2m}}$
$\displaystyle\text{or,}\quad\mathbb{P}\left[Q\leq\tilde{R}_{q}\right]$
$\displaystyle>q-\sqrt{\frac{\ln\left(1/\alpha_{2}\right)}{2m}}=p.$

With probability $1-\alpha_{2}$,

$\mathbb{P}\left[f(X)\in\mathcal{B}(\hat{f}(x),\tilde{R}_{q})\right]>p.$

##  Appendix E High-dimensional Outputs

For functions with high-dimensional outputs, like high-resolution images, it
might be difficult to compute the minimum enclosing ball (MEB) for a large
number of points. The smoothing procedure needs us to store all the $n\sim
10^{3}-10^{4}$ sampled points until the MEB computation is complete, requiring
$O(nk^{\prime})$ space, where $k^{\prime}$ is the dimensionality of the output
space. It does not allow us to sample the $n$ points in batches as is possible
for the certification step. Also, computing the MEB by considering the pair-
wise distances between all the sampled points is time-consuming and requires
$O(n^{2})$ pair-wise distance computations. To bring down the space and time
requirements, we design another version (Smooth-HD, algorithm 3) of the
smoothing procedure where we compute the MEB by first sampling a small number
$n_{0}\sim 30$ of candidate centers and then returning one of these candidate
centers that has the smallest median distance to a separate sample of $n\;(\gg
n_{0})$ points. We sample the $n$ points in batches and compute the distance
$d(c_{i},z_{j})$ for each pair of candidate center $c_{i}$ and point $z_{j}$
in a batch. The rest of the procedure remains the same as algorithm 1. It only
requires us to store batch-size number of output points and the $n_{0}$
candidate centers at any given time, significantly reducing the space
complexity. Also, this procedure only requires $O(n_{0}n)$ pair-wise distance
computations. The key idea here is that, with very high probability
($>1-10^{-9}$), at least one of the $n_{0}$ candidate centers will lie in the
smallest ball that encloses at least $1/2+\Delta_{1}$ probability mass of
$f(x+\mathcal{P})$. Also, with high probability, at least half of the $n$
samples will lie in this ball too. Thus, the median distance of this candidate
center to the $n$ samples is at most $2\gamma\hat{r}(x,\Delta_{1})$, after
accounting for the factor of $\gamma$ in the relaxed version of the triangle
inequality as discussed in section 4. Ignoring the probability that none of
the $n_{0}$ points lie inside the ball, we can derive the following version of
theorem 3:

######  Theorem 4.

With probability at least $1-\alpha_{1}$,

$\forall x^{\prime}\text{ s.t.
}\|x-x^{\prime}\|_{2}\leq\epsilon_{1},\;d(\hat{f}(x),\hat{f}(x^{\prime}))\leq\gamma(1+2\gamma)\hat{R}$

where $\alpha_{1}=2e^{-2n\Delta_{1}^{2}}$.

Algorithm 3 Smooth-HD

Input: $x\in\mathbb{R}^{k},\sigma,\Delta,\alpha_{1}$.

Output: $z\in M$.

Set $C=\\{c_{i}\\}_{i=1}^{n_{0}}\text{ s.t. }c_{i}\sim
f(x+\mathcal{N}(0,\sigma^{2}I))$.

Set $\Delta_{1}=\sqrt{\ln\left(2/\alpha_{1}\right)/2n}$.

Sample $Z=\\{z_{j}\\}_{j=1}^{n}\text{ s.t. }z_{j}\sim
f(x+\mathcal{N}(0,\sigma^{2}I))$ in batches.

For each batch, compute pair-wise distances $d(c_{i},z_{j})$ for $c_{i}\in C$
and $z_{j}$ in the batch.

Compute the center $c\in C$ with the minimum median distance to the points in
$Z$.

Re-sample $Z$ in batches.

Compute $p_{\Delta_{1}}$.

Set $\Delta_{2}=1/2-p_{\Delta_{1}}$.

If $\Delta<\max(\Delta_{1},\Delta_{2})$, discard $c$ and abstain.

##  Appendix F Baseline for $\ell_{2}$-Metric

In this section, we compare the certificates from center smoothing against a
bound derived in [60] for functions like $f$ smoothed by taking the
expectation of $f$ under a Gaussian noise. This bound only applies when the
output metric is $\ell_{2}$. For a vector-valued function $f$, the change in
the function defined as $\mathbb{E}_{\delta}[f(x+\delta)]$ where
$\delta\sim\mathcal{N}(0,\sigma^{2}I)$, under an $\ell_{2}$-perturbation of
the input of size $\epsilon_{1}$, can be bounded by
$(\max\|f\|_{2}+\min\|f\|_{2})\text{erf\\!}\left(\epsilon_{1}/2\sqrt{2}\sigma\right)$.
We apply our center smoothing procedure on the autoencoder and image
reconstruction models used in section 5.3 with $\ell_{2}$ as the output metric
and compare its certificates to the above bound. Since the minimum
$\ell_{2}$-norm of the output of these models can be zero and we keep
$h=\epsilon_{1}/\sigma=2$ for these experiments, the change in the output of
$\mathbb{E}_{\delta}[f(x+\delta)]$ can be bounded by
$\max\|f\|_{2}\text{erf\\!}\left(1/\sqrt{2}\right)\leq 0.68\sqrt{d}$, where
$d$ is the number of dimensions of the output space. For $28\times 28$ gray-
scale MNIST images and $32\times 32$ RGB CIFAR-10 images, the corresponding
bounds are 19.04 and 37.69 respectively. Figure 6 shows that the certificates
obtained for center smoothing remain below the baseline for all the values of
$\epsilon_{1}$ used. Thus, by observing the neighborhood of an input point,
center smoothing can yield better certificates for individual points in the
input space than the baseline bound which is a global guarantee.

(a) Dimensionality Reduction on MNIST

(b) Dimensionality Reduction on CIFAR-10

(c) Image Reconstruction on MNIST

(d) Image Reconstruction on CIFAR-10

Figure 6: Comparison with baseline ($h=2$).

##  Appendix G Angular Distance

A common measure for similarity of two vectors $A$ and $B$ is the cosine
similarity between them, defined as below:

$\text{cos}(A,B)=\frac{A\cdot
B}{\|A\|_{2}\|B\|_{2}}=\frac{\sum_{i}A_{i}B_{i}}{\sqrt{\sum_{j}A_{j}^{2}}\sqrt{\sum_{k}B_{k}^{2}}}.$

In order to convert it into a distance, we can compute the angle between the
two vectors by taking the cosine inverse of the above similarity measure,
which is known as angular distance:

$AD(A,B)=\text{cos}^{-1}(\text{cos}(A,B))/\pi.$

Angular distance always remains between 0 and 1, and similar to the total
variation distance, angular distance also defines a pseudometric on the output
space. We repeat the same experiments with the same models and hyper-parameter
settings as for total variation distance (figure 7). The results are similar
in trend in all the experiments conducted, showing that center smoothing can
be reliably applied to a vast range of output metrics to obtain similar
robustness guarantees.

(a) Dimensionality Reduction on MNIST

(b) Dimensionality Reduction on CIFAR-10

(c) Image Reconstruction on MNIST

(d) Image Reconstruction on CIFAR-10

Figure 7: Certifying Angular Distance

##  Appendix H Effect of Training with Noise

A common practice in the randomized smoothing literature is to train the base
model with noise added to the training examples [15]. This helps the model to
learn to ignore the smoothing noise and leads to better robustness
certificates for classification tasks. For the total variation certificates in
section 5.3, we train the autoencoders and the reconstruction models using a
Gaussian noise with the same variance as the one used for prediction and
certification. In this section, we perform an ablation experiment to study the
effect of the training noise in the certified output radius of the base model
(figure 8). We observe that both the smoothing error and the certified output
radius deteriorate in the absence of training noise. However, models trained
without noise also produce non-trivial certificates. This shows that both
center smoothing and training with noise contribute towards the robustness and
performance of the smoothed models.

(a) Dimensionality Reduction on MNIST

(b) Dimensionality Reduction on CIFAR-10

(c) Image Reconstruction on MNIST

(d) Image Reconstruction on CIFAR-10

Figure 8: Impact of training noise on the performance of the robust model and
its certificates.