Center Smoothing: Certified Robustness for Networks with Structured Outputs
Authors: Aounon Kumar
Tom Goldstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial Robustness
Certified Robustness
Randomized Smoothing
Structured Outputs

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.

Center Smoothing: Certified Robustness for Networks with Structured Outputs
Aounon Kumar University of Maryland aounon@und. edu
Tom Goldstein University of Maryland tomg@cs umd. edu
Abstract
The study of provable adversarial robustness has mostly been limited to classi- fication tasks and models with one-dimensional real-valued outputs. We extend the scope certifiable robustmess to problems with more general and structured outputs like sets, images, language, etc. We model the output space metric space under distancc/Similarity function, such as dntersection-ovee-uniooo per- ceptual 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 robustmess technique called randomized smoothing, our center smoothing procedure can produce models with the guarantee that the change in the output, 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.
Introduction
The study of adversarial robustness in machine learning (ML) has gained 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 model's predictions [56] 46 23 35). They can significantly degrade the performance of model, like an image classifier, and make it output almost any class
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 100. Similar attacks can cause neural image captioning systems to produce specific target captions with high success-rate ΠЛ 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 tumors in MRI scans, through adversarial inputs [ Super-resolution systems can be made to generate distorted images that can in turn deteriorate the performance of subsequent tasks that rely the high-resolution outputs [4
50 g 12].
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 48 Such widespread presence of adversarial attacks is concerning as it threatens the use of deep neural networks in critical systems, such facial recognition, self-driving vehicles, medical diagnosis, etc., where safety, security and reliability are of utmost importance.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Adversarial defenses have mostly focused on classification tasks [34 6 26 17
25 22 Certified
defenses based on convex-relaxation 61
49
53
13
54 interval-bound propagation 24
28
1 47
that guarantee that the predicted class will remain the same certified region around the input point have also been studied. Compared to empirical 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 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.
and randomized smoothing [5
36
42
51
robustness methods that are often shown to be broken by stronger attacks p 3 58
Unlike classification problems, where certificates guarantee that the predicted class remains un- changed 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 met- rics 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: I + (M, d) which map a k dimensional real-valued space into a metric space . with distance function d M x M R>o. In this work, we design randomized smoothing based technique to obtain provable robustness for functions of this type with minimal assumptions on the distance metric d. We generate robust version f such that the change in its output, measured by d, is small for small change in its input. More formally, given an input x and an l fe-perturbation size 61, we produce value 62 with the guarantee that, with high probability,
Va s.t. || - 1l2 S e d(((),,(<')) s2..
Our contributions: We develop center smoothing, procedure to make functions like / provably ro- bust against adversarial attacks. For a given input r, center smoothing samples collection of points in the neighborhood of x using a Gaussian smooth- ing distribution, computes the function f on cach of these points and returns the center of the smallest ball enclosing at least half the points in the output space (see figure D. Computing the minimum enclosing ball in the output space is equivalent to solving the I I-cette problem with outliers (hence the name of our procedure), which is NP-complete problem for a general metric (52). We approximate it by comput- ing the point that has the smallest median distance all the other points in the sample. We show that the output of the smoothed function robust to input per- turbations of bounded lz-size. We restrict the input perturbations to inside an balball as the main focus of this work is on the output space of f. However, our method does not critically rely on the &g threat model or Gaussian smoothing noise, and can be adapted to other perturbations types and smoothing distributions. Although we define the output space as metric, our proofs only require the symmetry property and triangle inequality to hold. Thus, center smoothing can also 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 ép metrics, and certifies robustness in metrics like IoU/Jaccard distance for object localization, and total voral-varattion, which is a good measure of perceptual similarity for images. In our experiments, we show that this method can produce meaningful certificates for wide variety of output metrics without significantly compromising the quality of the base model.
f F(x)
Input Space
Output Space
Figure 1: Center smoothing.
Related Work: Randomized smoothing has been extensively used for provable adversarial robustness the classification setting to defend against different é, [5 36 51 57
37 40 and non-Ep
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 [3). Smoothing a
bounded valued function by taking the mean of the output vectors has been shown to have

---

bounded Lipschitz constant when both imput and output spaces are f2-metrics [60]. Center smoothing does not require the base function to be bounded because the minimum enclosing ball 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 [1] 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 clean segmentation output and an adversarial one under a metric such as intersection over union.
2 Preliminaries and Notations
Given a function f IR - (M, d) and distribution over the input space R let (D) denote the probability distribution of the output of f in M when the input is drawn from D. For a point R let + P denote the probability distribution of the points x + 8 where is a smoothing noise drawn from a distribution P over R$ and let X be the random variable for x P. For elements in M, define r)) version of f under 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 + i.....
{=' d(z, z') I r) as a ball of radius r centered at z. Define a smoothed
(x) argmin s.t. P(f(X) B(z,r)) 22.r) B
there are multiple balls with the smallest radius satisfying the above condition, return one of the centers arbitrarily. Let (a:) be the value of the minimum radius. Hereafter, we ignore the subscripts and superseripts in the above definitions whenever they are obvious from context. In this work, we sample the noise vector from an i.i.d Gaussian distribution of variance o² in each dimension, i.e., 6 ~ o2)
2.1 Gaussian Smoothing
Cohen et al. in 2019 showed that classifier h R$ + smoothed with Gaussian noise o(0,021) as,
h(x)= argmax P [h(x + + = c], <Ey
where }' is 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 æ under the smoothing distribution is p, then for & perturbation of size most e, the probability of the top class is guaranteed to be at least
== (p)
where & is the CDF of the standard normal distribution NN 1). This bound applies to any {0, 1ffunntinn over the input space R² i.e., if P(h(x) 1] p, then for any e-size perturba- tion x,, P(((2') = =] 2 Pc-
We use this bound to generate robustness certificates for center smoothing. We identify a ball Bx)x), R) of radius R enclosing a very high probability mass of the output distribution. One can define a function that outputs one if ff maps point to inside B(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, least half of the mass of the output distribution is enclosed in B(f(x), R). We show in section 3 that the output of the smoothed function for a perturbed input 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 J is the center the smallest ball the output space that encloses at least half the probability mass of the f(x + P). Thus, in order to significantly change the output, an adversary has find perturbation such that a majority of the neighboring points map far away from f(r). However, for function that is roughly accurate most points around
3

---

small perturbation in the input cannot change the output of the smoothed function by much, thereby making it robust.
For an fe perturbation size of 61 of an input point x. let R be the radius of a ball around f(x) that encloses more than half the probability mass of f(a'' + +P) for all x' satisfying || rl112 61, i.e.
1 Ya' s.t. | 2'11 S 61, PP(((X))) E B(((), 2
where X' ~ x' + P. Basically, probability mass of f(x' + P) for any (, sissiee perturbation x' of æ. Then, we have the following robustness guarantee on ʃ:
the radius of ball around f(x) that contains at least half the
Theorem 1. For all such that || - x'112 S1.
d(f(z), f(z')) 2R.
Proof. Consider the balls (af(²), (x')) and B (z))), R) (see figure From the definition of (=²") and R, we know that the sum of the probability masses of f( + P) enclosed by the balls must be strictly greater than one. Thus, they must have an element in common. Since d satisfies the triangle inequality, we have:
a(F(z),{(<))) S d(f(x),)) d(y, ((x')
<R+r"(
Since, the ball (x) R) encloses more than half of the probability mass of fx++P) P), the minimum ball with least half the probability mass cannot have a radius greater than R, i.e, r" (=() < R. Therefore, (z). f(x')) < 2R.
The above result, in theory, gives us a smoothed ver- sion of f with provable guarantee of robustness. However, in practice, it may not be feasible to obtain just from samples of f(z P). Instead, we will use some procedure that approximates the smoothed output with high probability. For some [0. 1/2]. let f(x; A) be the radius of the smallest ball that en- closes at least 1/2 + A probability mass of f(x + P), i.e.
(z')
f f(x²)
R
f(x, A) = min r s.t. Pif(X) e B(2',
+
2
Now define probabilistic approximation f(z) of the smoothed function f to be point = .M, which with probability at least 01 (for @1 E [0. 1)). encloses least 1/2- probability mass of f(x PP) within a ball of radius f(x, A). Formally, f(x) is a point E M, such that, with at least 01 probability,
f(x)
Figure 2: Robustness guarantee.
IP [f(()) E B(z f(z, A)]]
1 A.
Defining Rt to be the radius of ball centered at f(x)) that satisfies:
Va' s.t. || - 2'112 S E1, P[f(X') e B(f(2), 1o)) >
2 + A,
(3)
we can write probabilistic version of theorem [
Theorem 2. With probability at least - 0A,,
Yx s.t. || x' ei, d(f(s), f(z)) < 22h,
The proof of this theorem is in the appendix, and logically parallels the proof of theorem |

---

Algorithm Smooth
Algorithm 2 Certify
Input: R a, A, 01-
Input: RR. <,,0, G, A 01,02
Output: 2 E M.
Output: <g E R.
Set Z = {zi Miz s.t. 2 ~ f(x+
Compute (ax using algorithm
Set A v (2/a1) /2n.
Set 2 {2 s.t. 24 ~ f(x o(),
Compute 2 = 3-MEB Z, 1/2).
Compute R {d) f(x)) 2 2)
Re-sample Z.
Set p (1/0-111200 A) /
Compute PA..
Set q = p + /In(1//2) 12mm
Set 2 = 1/2 - PA11
Set gth-quantile of R.
If A < max( 11, A2), discard and abstain.
Set = (1 + 3)
3.1
Computing /
For an input x and a given value of A, sample n points independently from a Gaussian distribution W0, 1) around the point x and compute the function on each of these points. Let Z = (2,,,,, žn} be the set of n samples of
o)))) produced in the output space. Compute
the minimum enclosing ball (22, r) that contains at least half of the points Z. The following lemma bounds the radius r of this ball by the radius of the smallest ball enclosing at least 1/2 + A probability mass of the output distribution (proof in appendix).
Lemma 1.
With probability at least 22n
rs ((r
Now, sample fresh batch of random points. Let PA, = = - A1, where p is the fraction of points that fall inside B(,,r). Then, by Hoeffding's inequality, with probability at least e 2nd
PP (f(() B(2,r)] 2 PA.
Let A2 = 112-14, - If max(A1, A2) I A, the point satisfies the conditions the definition of f. with at least 1 - 2e 2n probability. If max(A1, A2) A, discard the computed center and abstain. our experiments, we select A,, n and (r appropriately so that the above process succeeds easily.
Computing the minimum enclosing ball B(2, r) exactly can be computationally challenging, for certain metrics, it is known to be NP-complete [52]. Instead, we approximate it by computing a ball 3-MEB(Z, 1/2) that contains at least half the points Z, but has radius that is within / factor of the optimal radius We modify theorem T account for this approximation (see appendix for proof).
Theorem 3. With probability at least - a1.
Yx s.t. | d212250 c1, ((()). < (1 B)
where in = 2e -2n
We use simple approximation that works for all metrics and achieves an approximation factor of two, producing a certified radius of 3R. It computes point from the set Z, instead of 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²) pair- wise distance computations. To see how the factor 2-approximation is achieved, consider the optimal ball with radius r. By triangle inequality d, each pair 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 obtained for specific norms, e.g., there exists (1 + <>aappoxinnttion algorithm for the & 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
3.2 Certifying f
Given an input x, compute f(x) as described above. Now, we need to compute a radius î that satisfies condition] 3 As per bound [ in order to maintain probability mass of at least 1/2 A for
5

---

any 61-size perturbation of x, the ball [ (z)( R) must enclose at least
p= ②
Φ 11
2 +
+ 1
(4)
probability mass of f(x + P). Again, just in the case of estimating f. we may only compute R from a finite number of samples m of the distribution f(r + P). For each sample z; ~ I + P, we compute the distance d( d(f(xx), f(())) and set Rt to be the gth-quantile Ry of these distances for that is slightly greater than p (see equation 5 below). The gth-quantile R2 is value larger than at least y fraction of the samples. We set q as,
In (1/02) q q=p+y
(5)
2m
for some small 02 [0, 1]. This guarantees that, with high probability, the ball ((f()), R₂)
encloses at least fraction of the probability mass of f(x + P). We prove the following lemma by bounding the cumulative distribution function of the distances of (=))s from fxx) using the - inequality. With probability - 022,
Lemma 2.
P [F(X) B(f(2), > p.
Combining with theorem 3 we have the final certificate:
Var s.t. || x'1la S C,, (()() S (1+
with probability at least 1 - a, for = + 02. In our experiments, we set 0 02 = 0.005 to achieve an overall success probability of 1 a 0.99, and calculate the required 41, A2 and g values accordingly. We set A to be as small as possible without violating max(A, (1, A2) S A too often. We use a 2-approximation for computing the minimum enclosing ball in the smoothing step. Algorithm provides the pseudocode for the certification procedure.
4 Relaxing Metric Requirements
Although 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(21, 22) to be strictly greater than zero for 21 # 22- 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 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 incquality as it 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) I r(((a, b) + d(b, c)). for some constant y. The theorems and lemmas can be adjusted to account for this approximation, e.g., the bound in theorem [ will become RyR. commonly used distance measure for comparing images and documents is the cosine distance defined as the inner 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 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 and Iz, let ((I1) and ((I2) 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 (I, I2) = d(o(I,), ((12) in the image space, which also satisfies the relaxed triangle inequality. For any image Ta,
(L, I2) d(o(I)),
S (d((((()), - d(o(la)) ((2))) (do(11, 12) + (2),

---

5 Experiments
We apply center smoothing to certify a wide range of output metries: 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 6 = 0.2, the Jaccard distance (I-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 generative model (trained on ImageNet) that produces 128 x 128 RGB images using a high-dimensional version of the smoothing procedure Smooth- HD described in the appendix. For total variation distance, 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, 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 train = 0.1, 0.2...., ...5 to make them more robust to input perturbations. We keep the smoothing noise a of the robust model same as the training noise Ttrain of the base model. We use 10 samples to estimate the smoothed function and m = 10t samples to generate certificates, unless stated otherwise. We set = 0.05, a = 0.005 and 0₂2 0.005 as discussed in previous sections. We grow the smoothing noise linearly with the input perturbation 61- Specifically, we maintain 61 = -ho for different values of h- = 2, 1 and 1.5 in our experiments. We plot the median certified output radius 62 and the median smoothing error, defined as the distance between the outputs of the base model and the smoothed model f()) of fifty random test examples for different values of E1. In all our experiments, we observe that both these quantities increase as the input radius é 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 62). This could be due the fact that for a higher h, the smoothing noise is lower (keeping constant), which means that the radius of the minimum enclosing ball in the output space smaller leading to a tighter certificate. However, setting h too high can cause the value of q in equation 5 to exceed one (g depends on p, which in turn depends on h in eq. 4. Icading the certification procedure (algorithm{) 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
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, c.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 the size of their union (IoU). Thus, to certify the robustness of the output of 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 ToU which defines a metric over the universe of sets.
IAn B A A
AAn B AAUB
LoU (A, B)=
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 the certified output radius 62 and the smoothing error for h e1/a = 1 and 2 for E 0.11 0.2, .2, 0.5. Certifying the Jaccard distance allows us to certify
7

---

Eas lon out (hn2)
N AIDS OUN
Smoothin ereer (h=2)
Eps lon out (h=1)
Smoothing erer (h-1)
Jacoard Distance (1 (o0))
Epsion
(a) Certifying Jaccard Distance (1 IoU).
(b) Smoothed Output.
Face Detection on CelebA using MTCNN detector: Part (a) plots the certified output radius C2 and the smoothing error for h 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.
Figure 3:
IoU as well, e.g., for h = 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 3b 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 [II. One attack model to produce an adversarial example that is close the original input in the latent space, measured using fz-norm. The goal is to make the model generate different looking image using a latent representation that is close to that of the original image. We apply center smoothing to generative adversarial network BigGAN pre-trained on ImageNet images [5]. We use the version of the GAN that generates 128 x 128 resolution ImageNet images from a set of 128 latent variables. Since 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 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 of as generating two feature vectors Φ1 and de for the two input images J and 12 respectively, then computing a weighted sum of the element-wise square of the differences between the two feature vectors, i.c.,
be thought
d(I1. 12)= we(cn: -z
The square of differences metric can be shown to follow the relaxed triangle inequality for y = Therefore, the the final bound on the certified output radius will be 71 + 2 27) ft = 10f. Figure 4a plots the median smoothing error and certified output radius e2 for fifty randomly picked latent vectors for 6 = 0.01, 0.02, 0.05 and h = 1, 1.5. For these experiments, we set n 2000, m = 10 and = 0.8. We use the modified smoothing procedure Smooth-Hi (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 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 c1, but the smoothing error remains low showing that, in practice, the method does not significantly degrade the performance of the base model. Figure 4b 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 compared to the input (image) spaces in our other experiments.
8

---

*pation out (1#1 8)
Smrepching emor the
Epstion (h-1)
Smeathhng (h=1)
Perceptus Destance
506
137
(3)
Epslon n
(b) Model Output vs Smoothed Output.
(a) Certifying perceptual distance.
Figure 4: Generative model for ImageNet: Part (a) plots the certified output radius e2 and the smoothing error for and 1.5. Part (b) compares the output the base model to that of the smoothed model.
5.3 Total Variation Distance
The total variation norm of vector a is defined as the sum of the magnitude of the difference between pairs of coordinates defined by neighhorhood set N. For a 1-dimensional array x with & elements, one can define the neighborhood the set of consecutive elements.
A-1 TV(x)= = Σ bx 1a--ryh syys TVi((=) Σ 1r - x441l.
(GEE
Similarly, for grayscale image represented by h w 2-dimensional array æ, 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 -ormm.. For, our experiments we use the -nomm.
h-1 1
TVRGB(#)
| 2.41,5l1 + || - æ1s+1ll1
1=1 1=1
The total variation distance between images I, and I2 be defined the total variation
norm of the difference J, - J2, i.e., TVD(1, I2) = TV(h - I2). The above distance defines 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 distance of zero from the original image. However, noted in section 4 our certificates hold even for this setting.
We certify total variation distance for the problems of dimensionality reduction and image recon- struction on MNIST [6] and CIFAR-10 [2]. The base-model for dimensionality reduction is an autoencoder that convolutional layers in its encoder module map image down to small number of latent variables. The decoder applies a set of de-convolutional operations to reconstruct the 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 on each image to obtain the measurements. The base model tries to reconstruct the original image from the measurements. The attacker, in this case, assumed add perturbation the measurement space instead of the image space (as in dimensionality reduction). The model first reverts the measurement vector to vector in the image space by simply applying the pseudo-inverse A and then passes through a similar autoencoder model as for dimensionality reduction. We present results for = 0.2, 0.4...... 1.0 and h = 2, 1.5 and use 256 latent dimensions and measurements for these experiments in figure To put these plots in perspective, the maximum TVD between two CIFAR-10 images could be x 31 x 5766 and between MNIST images could be x 27 1458 (pixel values between 0 and 1).

---

Dimensionality Reduction MNIST
(b) Dimensionality Reduction on CIFAR-10
ty 3o
ty end Br
Deaohiig wex (e))
Deaohing are (we)
Tysice ou (o13))
Cysliee (w1l))
peraohing entrr (we
Sir Sirashing entr (1e1
Dalvvca
Spuioe
Spuise in
(c) Image Reconstruction on MNIST
(d) Image Reconstruction on CIFAR-10
Figure 5: Certifying Total Variation Distance
6 Conclusion
Provable adversarial robustness can be extended beyond classification tasks to problems with struc- tured outputs. We design a smoothing procedure that can make model of this kind provably robust against norm bounded adversarial perturbations of the input. In our experiments, we demon- strate that this method can generate meaningful certificates under a wide variety 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 & 2o-m bounded adversaries and the Gaussian smoothing distribution. An important direction for future investigation could be whether this method can be generalised beyond ép- adversaries 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.
10

---

References
[1] Vegard Antun, Francesco Renna, Clarice Poon, Ben Adcock, and Anders C. Hansen. On instabilities of deep learning in image reconstruction does AI come cost? CoRR, abs/1902.05300, 2019. URL //ttp://arxii. http//orwvvvooo/////////
[2] Amurag Arnab, Ondrej Miksik, and Philip H. S. Torr. On the robustness of semantic segmentation models to adversarial attacks. CoRR,
2017. URL http::/aaxiiy org/ /bs/
09856
[3] 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, Stt.-22llmtcooooomsssse Stockholmsmässann Stockholm Sweden, 10-15 Jul 2018. PMLR.
[4] 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. 116-3-319-62416-777
62119--226-6622- 19. URL https:://ai..rgg// 1007
[5] 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
7/openreview aipparrvies..net/fouurr222 www.eeeee//otmmee n
[6] 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
[7] Mihai Bundefineddoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings of the Thiry-Fourth Annual ACM Symposium Theory of Computing, STOC '02, page 250-257, New York, NY, USA, 2002. Association for Computing Machinery. ISBN doi: 10. 10.1145/509907.509944
1581134959,
URL hhttps://dol orwpoi..rg111... 1145/509901
509947
[8] Francesco Calivá, Kaiyang Cheng, Rutwik Shah, and Valentina Pedoia. Adversarial robust training in mri reconstruction. arXiv preprint S.kiv:2011.000111 2020.
[9] Nicholas Carlini and David A. Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec@ CCS 2017, Dallas, TX, USA, November 3, 20/7, pages 3-14, 2017.
[10] Nicholas Carlini and David A. Wagner. Audio adversarial examples: Targeted attacks on speech-to-text. CRRR, abs//801.00 00944,, 2018 URL http:p//:///iiiii org/ ht/////s//18// www.///1.....00 01944
[11] Hongge Chen, Huan Zhang, Pin-Yo 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. http://axxvvvog/eee//// btrrg/bbs/7111 02051
[12] 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 httttt:::/pprrcedinggaatt mlr www.spreessseeeeeee vv21s///v1111/// http///hhegaaa.a//// html
[13] 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.
[14] 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 IEEF/CVF International Conference Computer Vision, ICCV 2019, Seoul, Korea (South), October
11

---

27 - November 2, 2019, pages :ttps://doi.org/ 11190.....000000 ICCV 221. 00039
IEEE, 2019. doi: 10.1 10.11099//CC2221990000099 URL
[15] 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.
[16] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 29(6): 142-142, 2012. doi: 10.1 109/MMP22221 221 1477.
[17] 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.
[18] Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' O'Dongguue Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers, 2018
[19] Marc Fischer, Maximilian Baader, and Martin T. Vechev. Scalable certified segmentttionnn via randomized smoothing. CoRR, abs/2107.0022 002288, 2021. http:/ttsss//aaxx..orr///////// 00228
[20] Morgan Frearson and Kien Nguyen. Adversarial attack on facial recognition using visible light. arXiv preprint arXiv:2011. 12680, 2020.
[21] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforeement learning. In 8th International Confer- ence on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httpss///pppeereviirr http://pennoiii....eeettttrrrr// heot/forumnid-HJgERRe
[22] Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku. Adversarial and clean data are not twins. CoRR, abs/ Abs/1704, 2017.
[23] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[24] 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.
[25]
Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick D. Mc- Daniel. On the (statistical) detection of adversarial examples. CoRR, abs/1702.062888 2017.
[26] 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
[27] 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, 12111, 2019. Utt. htt//arivvvorrr/ee/// abs/abbs//// 12181
(28) Po-Sen Huang, Robert Stanforth, Johannes Welbi, 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. EMNNL-IJCNLP 2019, Hong Kong. China, November 3-7, 2019, pages 4081 1 1091, 2019. doi: 10. 11865//11DD1-1444 1419. URL https: org/10 18653/v1/D19-144 1419
[29] Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, wtwp:eewweeeooooeeeeeeeeeeeeeeoe 2017. URL htt.ppanwrrrrio.eeeeeoooorrrraaa
12

---

[30] Xu Kang, Bin Song, Xiaojiang Du, and Mohsen Guizani. Adversarial attacks for image segmentation on multiple lightweight models. IEEE Access, 8:31359-11370, 2020. doi: 10.1 10/1109/ACESS 2WW.:/CCESSS222.29....0 2020.297306..
[31] 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: D0.1109/PPW22118.0000 URL
https: org 1109/SPW 2018.01180000 00014
[32] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research). http:ttt:/were wttp://.oww.t.oooooooooo www.oonto.edo////... www/ekrii///oooeeee catii////aaa..// .ttll
[33]
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: https::/ neurips. cc/
Aounon Kumar, Alexander Levine, Soheil Feizi, and Tom Goldstein.
[34] 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. [ttLattts///ppereriiee wwtpriiwwwwwee.fro...o net/forum?
id= 1d=JJm4T4Kgx
[35] Cassidy Laidlaw and Soheil Feizi Functional adversarial attacks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'Alhh-BBu, Emily B. Fox, and Roman Gar- nett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Van- couver, BC, Canada, pages 10408-10418, 2019. URL battp://paper pwtppprrs.iiss...m cc/paper/ 9228-functional.
[36] 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.
[37] 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: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 4911-4922. 2019.
[38] Alexander Levine and Soheil Feizi. Wasserstein smoothing: wasserstein adversarial attacks, 2019.
Certified robustness against
[39] Alexander Levine and Soheil Feizi. Sobrrddd for certifiable defense against patch attacks. CORR, abs/2002. 10733, 2020. URI. httpp:httt:///arii..oo abrp:/abb//2002// 10733
[40] Alexander Levine and Soheil Feizi. Robustmess certificates for sparse adversarial attacks by randomized ablation. In The Fhirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The "hirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAA/
2020, New York, NY, USA, February 7-12, 2020, pages 4585 4593. AAAI Press, 2020. URL
[41] Alexander Levine, Aounon Kumar, Thomas Goldstein, and Soheil Feizi. Tight second-order
certificates for randomized smoothing, 2020.
[42] 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
2019.
[43] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversaiial attack and certifiable robustness, 2019. URL http://///ppppeeeeeeeeeeot//rttr
[44] Xin Li and Fuxin Li. Adversarial examples detection in deep networks with convolutional filter statistics. IEFE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 5775-5783, 2017.
13

---

[45] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep leamnigg face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[46] 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.
[47] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. 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 httL//ttt///rocceddngg
mlr. wwwppreeseve..
htt///80//mm// ww188//miii/ mirn1188 html
[48] 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 (040-2042. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA/ ACM, 2018. URL pattpp//áii acm. org/ citation..... ieeiatidoncfmmidd cfm?id= 3238064
[49] 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.
[50] Ankit Raj. Yoram Bresler, and Bo Li. Improving robustness of deep-learning bbaed 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 raj20a.html
PMLR, 2020. URL
mlr .pr.ss/veii
[51] 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-113000 1300. 2019.
[52] 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.or/// URL htt:::tt: http:::/www..ccceceeeeeeee.eeeee wwwencedirectt.c..c..... http://deeeeetto//ccc////errrraa
$0195669981500888)
[53] Sahil Singla and Soheil Feizi. Robustness certificates against adversarial examples for relu networks. CoRR, abs/1902.00125,, 2019.
[54] Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks, 2020.
[55] Qing Song, Yingqi Wu, and Lu Yang. Attacks on state-of-the-art face recognition using attentional adversarial attack generative network. CoRR, abs/181 2018. http?
//arxiv.org abs// 1811. 12026
[56] Christian Szegedy, Wojeiech 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.
[57] Jiaye Teng, Guang-He Lee, and Yang Yuan, l adversarial htw.:esssaaaaarrrttteceeeenee robustness certificates: a randomized smoothing approach, 2020. htLpstts::/// http://pwwooooooeoeee/o//oeottaa
[58] Jonathan Uesato, Brendan O' D'Dongguee, 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 Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 5032-5041, 2018
[59] Fatemeh Vakhshiteh, Raghavendra Ramachandra, and Ahmad Nickabadi. Threat of adversarial attacks on face recognition: A comprehensive survey. arXiv preprint 2XXY::2007.11709, 2020.
14

---

[60] Adva Wolf. Making medical image reconstruction adversarially robust. 2019. URL http: 7/cs229. stanf ord. edu ctt/ppr9/220118p//rppr/////// pdf
[61] 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, ICMI. 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pages 5283- 5292, 2018.
[62] Ping ych Chiang, Michael J. Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein. Detection regression: Certified object detection by median smoothing, 2020.
[63] Minghao Yin, Yonghing 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 978 9781450356657.
doi: 0..144573240550.22440063 URL
https://doi.org//11 /ttp////....11//11111
3240603
[64] 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. URLhttpp
7/arxiv. org/ hts///b///000 1604. 02878
[65] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman, and Oliver Wang. The un- reasonable 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/CVPR220 00068. URL http::ttp///ooecceesss thecvf com/ wontent_cvprreeeeeee cotp__208/html// Ltt///haanggaaa paper html
Carraaonbble_ifffeciieeeeesss
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] In the conclusion (section 6 we
discuss that more work is needed to generalize our method threat models other than
lz.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work aims to help make machine learning models more robust and reliable for real-world applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs all theoretical results? [Yes] Complete proofs of all theorems and lemmas can be found in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] Code is included in the supplemental.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the experiments section.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the experiments section.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license the assets? [N/A] We are using datasets that are available in the public domain with custom license terms that allow non-commercial use, like MNIST, CIFAR-10 10 and CelebA.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Our code is included in the supplemental.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We are using datasets that are available in the public domain with custom license terms that allow non-commercial use, like MNIST, CIFAR-10 and CelebA.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "VWJN-V0GNKJ", "reviewer": "Reviewer_t5kY", "summary": "This paper aims to extend certifiable robustness methods based on randomized smoothing into the situation when the output space is a general metric space. The basic idea is to output the center of the smallest ball in the output space that can enclose half the probability mass of the output distribution with Gaussian input.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The paper is based on randomized smoothing methods but focuses on a new setting where the output space is a general metric space. \n\nQuality: The proposed method is interesting and suitable for many situations. It will be better if the authors can explain why the proposed method will work without requiring the output of the base classifier to be bounded, because most of the previous randomized smoothing approaches usually rely on the assumption that the output is bounded (in [0, 1]). \n\nClarity: This paper is well written.\n\nSignificance: The setting considered in this paper is potential, however, the experiments results in the paper is limited. The reviewer would like to encourage the authors to add more examples (maybe as future work) to showcase the usage of certifying in a metric space.\n\n---\nUpdate after rebuttal:\nThe rebuttal provides more detailed explanations of the paper which the reviewer suggests should be added to the paper. And I'll keep my score as weak accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "U0YRKX_jU2l", "reviewer": "Reviewer_aHRy", "summary": "The paper proposes an extension to randomized smoothing to certify robustness of functions over more general metric spaces by finding the center of the smallest ball which contains at least half of the output of a set of points. They approximate this center by finding the point with the smallest median distance to the other points.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper feels a bit like a solution in search of a problem.\n\nI've seen a lot of work take randomized smoothing and do some small change to apply it to a slightly different setting, without presenting much work that seems truly novel. These sorts of works are worth sharing, but I don't personally feel they're worth publishing individually at a top conference. I don't believe that smoothing over general metric spaces is useless, and of course I know that the authors had to do some work to bridge the gap from A to B---hence I feel the contribution does have merit. But ultimately this paper presents a very minor development necessary to apply randomized smoothing to [slightly new setting X that no one has yet staked a claim on].\n\nThe presentation is decent. The experiments are decent. The math is trivial, but fine. This is the only meaningful summary I feel I can give on this work: it is technically correct, but not insightful and the math is trivial. So I guess the question is, what is the expectation for an accepted publication? This is a subjective question. I think it should be more than just a stamp of approval that the math is technically correct, so while I don't think this work is bad, I would not recommend publication.\n\nAdditional notes:\n\n* Line 39 is not correct, randomized smoothing was not first studied by Cohen et al. The idea of injecting noise a la differential privacy is due to [1], and the formulation in its current form was first suggested in [2].\n\n* Are the authors aware that smoothing a bounded function with Gaussian noise already naturally induces certified robustness in the form of Lipschitzness? This is known as the Weierstrass transform, see Appendix A of [3]. I'm not 100% sure but I think this could serve as a (much faster, simple) baseline to compare when evaluating bounded functions such as IOU?\n\n[1] Certified Robustness to Adversarial Examples with Differential Privacy. Lecuyer et al. 2018\n\n[2] Certified Adversarial Robustness with Additive Noise. Li et al. 2019 (this paper was originally called \"Second-Order Adversarial Attack and Certifiable Robustness\" and was first posted to arXiv in 2018).\n\n[3] Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. Salman et al. 2019\n\n\n---------------------\n**Update post rebuttal**\n\nThe authors and I had some fruitful discussion. However, my feeling that the novelty and significance of the submission are below the bar for publication remains. I think this is an ok idea, but the work itself just isn't a paper's worth of material. I encourage the authors to further explore this idea; fleshed out with additional experiments, more finetuned theoretical analyses, or other improvements I expect this could be a reasonable publication.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "OO6xwax9lCF", "reviewer": "Reviewer_mjCZ", "summary": "This paper proposed a smoothing technique to perform adversarial training, such that the trained model is robust to small $l_2$ perturbations in the input. The major contribution is that the proposed method is applicable to a wide range of distance metrics. The idea of computing the minimum enclosing ball is also a very interesting idea, and I believe similar idea can be used to smoothing based optimization. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n1. This paper provides not only a theoretical justification of the proposed method but also an algorithm that can be implemented and used in practice. \n\nCons: \n1. There is no description on the distribution of the input perturbation $x-x'$. It only says $||x-x'||_2 \\le \\epsilon_1$. Is the noise uniformly distributed into all the pixels or concentrated in a local region. Since the Guassian smoothing is used, it is natural to assume that the proposed method only works when the input image is perturbed by a white noise, unless additional experiments show that the proposed method also works for concentrated perturbations. In recent years, there are new adversarial attack methods, e.g., square attack,  that generate concentrated perturbations to fool an image classifier. Thus, it is important to understand what kind of perturbations the proposed method can handle. \n\n2. In the examples using pre-trained models, they authors trained the base models on data with added noises to make them more robust to input perturbations. My understanding is that this is not part of the proposed smoothing technique. For those examples, it is not clear which part (noise injection or smoothing) plays a more important role in making a robust model. An ablation study on this would be helpful. \n\n3. It's not clear how to choose the value $h$ in $\\epsilon_1 = h \\sigma$ on Line 241. The authors claim, in Line 246, that the increasing of $h$ improves the quality of the certificates. Does it mean that I should use a very large $h$? In practice, we usually assume we know $\\epsilon_1$ and question is how to find an appropriate $\\sigma$ so that we can get the best certificates (smallest $\\epsilon_2$). I don't know whether this is the setting considered in this paper. \n\n4. There is a little abuse of notation that cause some confusion. For example, is $\\sigma$ in Line 237 the same as $\\sigma$ in Line 241? Is the constant $h$ in Line 241 the same as the $h$ in Line 96? I think they are all different. If so, it would be better to use different notations. \n\nIn summary, even though the authors proposed a promising idea, there is a lack of ablation study to demonstrate the effectiveness of the method. I would be happy to increase my rating if the above concerns are addressed. \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Iaax878RZmE", "reviewer": "Reviewer_ujD6", "summary": "The authors extends randomized smoothing, originally developed for classifiers, to functions which map inputs to a general metric space. The extension seems intuitive but is technically challenging. The authors develop tractable, statistical methods both for finding the smooth prediction as well as computing the certificates. Various experiments are conducted to highlight its flexibility in different metrics and scenarios, such as Jaccard distance w.r.t. face detection, total variation distance w.r.t. dimension reduction, and angular distance for image reconstruction. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Well-executed statistical methods for deriving and computing the certificates of robustness. It is not clear how tight the certificate is, though. \n\n2. It is not clear to me how to choose $\\Delta$. How exactly to select $\\Delta_1$ appropriately so the process succeeds easily (as written in line 161)? Can the user optimize $\\Delta$ to improve the certificate (given the same smoothed model)?\n\n3. I think line 107 and the first part of Section 3.2 can be written in a much more clear way by writing the \"classifier\" down explicitly. For example, you can write it as something like $P(\\mathbb{I}(f(x + \\delta) \\in B))$ and it will be clear that $\\mathbb{I}(f(x + \\delta) \\in B)$ is a classifier so you can apply the result from (Cohen et al. 2019). \n\n4. Theorem 1 is very clean, highlighting how the certificate is derived in a high-level, ideal scenario, but since it is very similar to Theorem 2 and Theorem 1 is not really used, I wonder whether it is possible to simplify this part. \n\n5. The derivation of the certificate is not very clean, with some details missing / hiding in the Appendix. In the Appendix, since there is no page limitation, I suggest the authors to write every step in detail so as to make this paper self-contained. For example, first writing Hoeffding's inequality and DKW inequality down and then showing how the inequalities are applied can help the readers understand the proof. \n\n6. The problem is not strongly motivated. It is not clear how severe current systems would fail and what the consequences would be in the context considered in this paper. For example, how non-robust can a model without smoothing behaves for dimension reduction? Even if it is indeed not very robust, what would be the real world consequence? Based on the writing, the authors only indicate the existence of adversarial examples and motivate robustness for face recognition, but it is not really clear how bad existing methods are. \n\nIn contrast, it is very clear how bad and imperceptible adversarial example can be in image classifiers, and the consequence is trivial since many mission-critical problem (e.g., face identification) are formulated as classification problems. The contribution of this paper is currently very limited to its technical discovery due to this reason. \n\n7. In addition, there is no empirical comparison to existing models. Even though this work might be the first work for certified robustness w.r.t. metric space outputs, the authors can still compare it with vanilla models without smoothing, and show that the vanilla model would fail (i.e. finding an adversarial example) under the certified region given by the smoothed model. Clearly the authors can run simple gradient methods to find adversarial examples for total variation distance and angular distance. \n\n8. Lots of space are wasted for large figures in experiment sections and simple concepts (e.g., how cosine is computed). I suggest the authors to shrink figure sizes and replace trivial concepts with technical details in the proofs to make the method more understandable. \n\n9. Nevertheless, the paper still seems technically solid (if the proof are indeed correct), and the problem seems new and interesting (although the significance is questionable), I will recommend this paper for marginally above the acceptance threshold. \n\nMinor:\nIn line 103 and 104, I think it should be $h(x + \\delta)$ and $h(x' + \\delta)$. \n\nDisclaimer:\nI did not read all the proofs in the Appendix. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There seems no immediate negative societal impacts. The authors could also discuss potential methods that would improve the tightness of their method. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission to NeurIPS.  The reviewers and I are all in agreement that the proposed work presents a nice (if incremental, at least from a technical perspective), extension to randomize smoothing, to apply to more general output spaces than previous approaches.  The results are technically sound, even if by no means represent a foundational breakthrough, and the experiments illustrate the potential usefulness of the approach.  And the authors did a great job during the response period discussing the issues raised by the reviewers and offering further potential benefits of the approach.

The majority of the discussion centered around the question of whether such a result is substantial enough (from a philosophical standpoint) to warrant publication at NeurIPS.  And in this setting, I want to make two points.  First, I think it's entirely appropriate for the reviewer to bring up the point in this manner.  Paper selection for NeurIPS _is_ ultimately about making subjective (rather than just factual) evaluations of papers, and it's entirely appropriate for the reviewer to highlight their concerns about the fundamental novelty and perceived impact of the work.  Indeed, it's far preferable to bring it up in an honest and frank manner (and engage fully with the reviewers afterward in discussion), than to try to couch this fundamental concern in the veil of minor technical issues with the paper (which is too often the standard in reviews).  If there are questions about a paper's significance, it can and should be brought up in the manner.  And second, I must say that I agree to some extent with what this reviewer is saying: there _is_ an extent to which the paper seems to be extending randomized smoothing to "one more domain".  And the other three reviewers, while being positive, are only minorly so, and weren't substantially swayed by the author response.

Despite this, however, I am going to recommend the paper be accepted.  While I'm sympathetic to the points that the negative reviewer makes, ultimately I think that rejecting an otherwise-universally-recommended-to-be-accepted paper on the grounds of perceived significance be an incorrect decision, given that it's such a subjective quality.  My own reading of the paper is that it presents a practically-valuable extension to randomized smoothing for problems beyond classification, using technically sound approaches.  Although the methodology may not be the most fundamentally groundbreaking, it covers a topic of likely interest to a wide variety of practitioners who may be considering using randomized smoothing, and hence has a notable value for the field.  Given all this, I believe the paper does meet the bar for NeurIPS despite the ultimate persisting disagreement between reviewers.
Decision: Accept (Poster)