Understanding Noise-Augmented Training for Randomized Smoothing
Authors: Ambar Pal
Jeremias Sulam
Venue: Accepted by TMLR ()

Abstract: Randomized smoothing is a technique for providing provable robustness guarantees against adversarial attacks while making minimal assumptions about a classifier. This method relies on taking a majority vote of any base classifier over multiple noise-perturbed inputs to obtain a smoothed classifier, and it remains the tool of choice to certify deep and complex neural network models. Nonetheless, non-trivial performance of such smoothed classifier crucially depends on the base model being trained on noise-augmented data, i.e., on a smoothed input distribution. While widely adopted in practice, it is still unclear how this noisy training of the base classifier precisely affects the risk of the robust smoothed classifier, leading to heuristics and tricks that are poorly understood. In this work we analyze these trade-offs theoretically in a binary classification setting, proving that these common observations are not universal. We show that, without making stronger distributional assumptions, no benefit can be expected from predictors trained with noise-augmentation, and we further characterize distributions where such benefit is obtained. Our analysis has direct implications to the practical deployment of randomized smoothing, and we illustrate some of these via experiments on CIFAR-10 and MNIST, as well as on synthetic datasets.

Published in Transactions on Machine Learning Research (04/2023)
Understanding Noise-Augmented Training for Randomized Smoothing
Ambar Pal
AMBARQ.JU.EI
Deportment of Computer Science & Mathematical Instûtute of Data Science Johns Hopkins University Baltimore, MD 21218, USA
Jeremias Sulam
JSULAMI @JH..EDU
Department of Biomedical Engineering Mathematical Institule of Dala Science
Johns Hopkins University Baltimore, MD 21218, USA
Reviewed on OpenReview: https: // openreview. net/ forum? id= fuyhEmDüFFr
Abstract
Randomized smoothing is technique for providing provable robustness guarantees against adversarial attacks while making minimal assumptions about a classifier. This method relies on taking a majority vote any base classifier over multiple noise-perturbed inputs to obtain a smoothed classifier, and it remains the tool of choice certify deep and complex neural network models. Nonetheless, non-trivial performance of such smoothed classifier crucially depends on the base model being trained noise-augmented data, i.e., smoothed input distribution. While widely adopted in practice, it is still unclear how this noisy training of the base classifier precisely affects the risk of the robust smoothed classifier, leading to heuristics and tricks that are poorly understood. In this work we analyze these trade-offs theoretically in binary classification setting, proving that these common observations are not universal. We show that, without making stronger distributional assumptions, no benefit can be expected from predictors trained with noise-augmentation, and we further characterize distributions where such benefit is obtained. Our analysis has direct implications to the practical deployment of randomized smoothing, and we illustrate some of these via. experiments on CIFAR-10 and MNIST, as well as on synthetic datasets.
1 Introduction
Machine learning classifiers are known to be vulnerable to adversarial attacks, wherein a small, human- imperceptible additive perturbation to the imput is able to produce a change the predicted class (Szegedy et al., 2013). Because of clear security implications (Kurakin al., 2016), this phenomenon has sparked increasing amounts of work dedicated to devising defense strategies (Metzen al., 2017; Gu and Rigazio, 2014; Madry et al., 2017) and correspondingly more sophisticated attacks (Carlini and Wagner, 2017; Athalye et al., 2018; Tramer et al., 2020), with each group trying to triumph over the other in arms-race of sorts. As a result, an increasing number of works have begun providing theoretical guarantces and understanding of adversarial attacks and defenses, studying learning theoretic questions (Shafahi et al., 2018; Cullina et al., 2018; Bubeck et al., 2018; Tsipras et al., 2018), understanding the sample complexity of robust learning (Schmidt al., 2018; Yin et al., 2018; Tu et al., 2019; Awasthi al., 2019), characterizing the optimality of attacks and defenses (Pal and Vidal, 2020), analyzing the implications of robust representations (Awasthi al., 2020; Sulam et al., 2020; Muthukumar and Sulam, 2022), and more.

---

Published in Transactions on Machine Learning Research (04/2023)
One of the central objects of study in this setting are robustness certificates, which provide provable guarantees on the prediction of models as long as the input is not perturbed beyond a specific contamination level Raghunathan et al., 2018; Yang et al., 2020). In this vein, randomized smoothing (Lecuyer et al., 2019; Cohen et al., 2019) employs a base classifier, typically vulnerable to adversarial attacks, and derives from it a smoolhed version by taking a majority vote of the base classifier's oulputs on several (stochastic) noise-perturber versions of the input. While making minimal assumptions about the base model, the resulting smoothed predictor is provably robust to input perturbations of bounded Ep norm (Yang et al., 2020). Because this is applicable to any given predictor, randomized smoothing has arguably become the most practical certified defense technique against ad adversarial examples for deep learning models, which are often too complex be analyzed and certify otherwise.
(Cohen et al., 2019;
Nonetheless, the accuracy of the resulting smoothed model differs from that of its base classifier. It has been empirically observed that smoothing a base classifier out of the box; i.e., without any modifications to the network weights or structure, docs not provide good performance, for example in terms of certified accuracy (Cohen et al., 2019; Gao al., 2019). Tricks like noise-augmentte training for the base classifier need to be employed in order to obtain meaningful results and defense certificates. This phenomenon, while pervasive in practice, does not have a good theoretical understanding. There are several open questions surrounding the relationship between the base classifier and its smoothed version: Why is andmeenngeeneed training useful when training the base classifier? How does the performance of the smoothed classifier depend on the distribution of the training noise? Is noise perturbed training always needed for all data-distributions, and if not, could we determine this before modifying the training procedure? In this paper, we take a step towards answering some of these questions for general binary classification task in Rd.
In summary, our contributions are as follows:
1. For a general bounded data-distribution, we derive an upper bound on the benign risk obtained from smoothing a classifier that has been trained with noise augmentation. Surprisingly, this bound suggests that noise-angmented training can in fact be harmful to the benign risk of the final smoothod classifier, which is contrary to the observed phenomenon in practical applications.
2. We then characterize a family of data distributions for which the above bound is tight, and for which training on noise-augmented data is only detrimental. These distributions are characterized by notion of large interference distance, which we formalize.
3. We show that this notion of interference distance captures some of the trade-offs in randomized smoothing, and we prove that there exist a family of distributions where benefits can be obtained from noise-augmented training as observed in practice.
4. Our empirical experiments suggest, firstly, that real data distributions lie in the low-interference distance regime, and hence noise-augmented training is beneficial to randomized smoothing. Secondly, contrary to practice, our proofs suggest that the parameters of the noise-distribution for noise- augmented training and that of randomized smoothing need not be the same, and that allowing for different values of these parameters lead to improved results. Our experiments on MNIST and CIFAR-10 confirm this theoretical intuition.
The rest of the paper is organized as follows. In Section 2 we describe preliminaries and set up our notation and framowork. In Section 3 we introduce our main results informally, obtaining conditions that characterize data distributions where noise-augmented training provides an advantage, and those where it does not. Section presents our main results greater technical detail. Lastly, we conduct our synthetic and real data experiments in Section 5, and conclude in Section 7 highlighting our answers to the questions posed above.
2 Preliminaries and Setup
y We consider a binary classification task on data X X C Rd with labels Y E y² - 10, The random variable X follows a data distribution over the space X' with PDF px. In turn, the label or response variable
We comment on extensions multiple classes later Section 4.
2

---

Published in Transactions on Machine Learning Research (04/2023)
Y follows distribution py over its corresponding space. We assume that X' is bounded (we take diameter for simplicity). A supervised learning task is defined by the joint distribution px,,; and the goal is to obtain a predictor h: X' + [0, 1] so that h is a good approximation for the conditional expectation E[Y]X = x|. These distributions are unknown, however, so the learning problem consists of finding such a predictor from a set of samples, lypically identically and independently distributed from Px,Y-
In this work we will not dwell much on the learning problem, and instead we will assume we are given access to function h: X' + [0, 1] which is good approximation ? for the conditional prjx. The base classifier is given by the composition of h with discretizing decision mapping, Φ:: [0, 1] >. In our setting, (2) = 1 2 0.5], where [[-] denotes the indicator function. Note that if h is the real conditional distribution of the label for a given input, this coincides with the Bayes classifier for this problem.
Adversarial examples are "small" additive perturbations designed for an input sample such that the predicted label at the perturbed input incorrect. Typically these perturbations are constrained to be in some lg norm ball, i.e,, ||ô]1, S e, so as to be imperceptible achieve excellent accuracy in normal settings can misclassify samples perturbed even with very small values of e (Goodfellow et al., 2014). The goal of certified robustness methods is to guarantee that the output of a certain model at a given input", (x)) will not change when contaminated by perturbations in a ba-ball with radius of at most e*. That is, certifying that (x))(2)) = (b)((zz + 6) for every 8: 1001g S
humans. It has been extensively shown that models that
Randomized smoothing (Cohen et al., 2019) achieves this by "smoothing" the classifier (h) with an isotropic distribution. More precisely, the smoothed classifier (mo)th(<(h)) is constructed from (h) by
Smoothpy (1)h))
def arg max P))())(++ eEY
(1)
where V pv. The choice of the distribution pv centrally depends on the norm constraint of the adversarial perturbation. Randomized smoothing was first introduced as a certification method against Ey-bounded perturbations, for which pv = (0,8 [a)- However, this has been extended to other norms in a series of recent works (Lecuyer et al., 2019; Li et al., 2019; Yang et al., 2020), yiclding correspondingly different distributions pv. In particular, for the binary case with bz-bounded perturbations, randomized smoothing measures the probability of the predicted class (say 1) after smoothing as s = Pfh(z V) = 1). Then, it provides certified radius e" = (s) that depends on this probability E (0.5, 1] as well the variance of the smoothing distribution B², where --1 is the inverse of the standard Gaussian CDF. Before continuing, it will be useful for our discussions to employ the following equivalent form of randomized smoothing.
When pv is symmetric, and for the binary classification lask defoned above, the smoothed classifier is given by Smoothp (+()))(z))= = (((((h) (zz), where * denotes the convolution operation.
Proposition 2.1.
Proof. Consider the random variable V pv and simplify Smoothpv (1((h)((z) as,
Smoothp (v)h))(z)) = arg max (l)())(x + V) cc] cE(0,1)
<(Pisch) 1])= = (/ (Ile((t)(+ 11pv (v)dv)
( (()))a +) ((((h)))v))) (x)
L
In this manuseript, we will work with single-paramete smoothing distributions pg- Accordingly, we will simplify our notation to denote the smoothed classifier as ((t)t))(((h))(()))
We consider the setting where certain minimum level of robustness is required at deployment, say c² In other words, we want our certified radius to be at least e From the previous discussion, this implies that
2Our results developed for h E[)]X), but show that most of them be extended the approximate case in Appendix G.
SUp the deterministic nature of (2) whenever 0.5.
For simplicity of notation our analysis, we use (x))(x)) denote the composition &h h at.
3

---

Published in Transactions on Machine Learning Research (04/2023)
B ( 2 e", implying that we need a minimum strength for randomized smoothing, say & def Then, given that one will be required to employ (v)))))))((())aa)) how should be obtained?
= (L/0-1(s))
To make the above question precise, we recall the definition of the risk of a classifier under the data- distribution px, R(f) (X)()) YY). When f Smooths. (1i(h)), this becomes
R(Smootha- (v(h)) =
(x())) Y)..
As mentioned in the introduction, obtaining h via natural training typically leads to a certifiable predictor with higher error than that of the base classifier, i.e., R(Smooth3- ((nnmotthhh(((())))))))))))()))) > R(v(h)). This expected, as the classifier (hh) was precisely trained to minimize the risk [())))), whereas its smoothed counterpart Smooth3 (v))), was not. Such phenomenon can also be regarded as an out-of-distribbution (OOD) problem, albeit in very specific setting where the distribution shift is produced by certification method. Indeed, it has been widely demonstrated in practice that naïvely smoothing any basc classifier leads to significant degradation in benign accuracy, i.e., accuracy on aarraddvrsarriallyyooouueee samples, and hence to a lower certified- accuurac. Besides the well established empirical evidence reported in the literature (Gao et al., 2020; Cohen et al., 2019), we will also showcase this phenomenon in our experiments.
To alleviate the discrepancy, practitioners have resorted to retraining the base classifier (hh) with a noise- augmented data distribution instead, denoted here by px- This is achieved by adding noise V ~ pv to the data variable X px to obtain the noise-augmented data X, = X + V ~ px Following general intuition, in practice one employs the same smoothing distribution for noise-angmentation certification stage. If we let p& be the PDF of Xs, it is well known that px is the convolution of px and pv, i.c. p = px pv-
as that employed for the
Throughout this work, we will make minimal assumptions about the underlying data distribution, the parameterization of the predictor, and the (finite) dimension of the data. However, we will assume that the hypothesis class is rich enough, and the learning algorithm good enough, such that the true conditional expectations are learnt successfully. As we show in Appendix B, this implies that the Bayes classifiers (h) and (hh )v) are learnt successfully under data distributions Px and Px respectively. Therefore, a classifier learnt on the noise-augmented data results in Smooth (1>(h pv)), which will be the central object of our study.
While the assumption of learning the Bayes classifiers exactly might seem stringent, much of our results can be adapted to relax this assumption while maintaining our general proof technique, assuming a controlled difference between the Bayes and the obtained classifier. In Section 4 and Appendix G, we discuss this further and extend our results to handle errors in learning. On the one hand, our analyses of the Bayes classifiers are informative because they reflect the best possible predictors that can be learned from data. On the other hand, and importantly, we will illustrate how these assumptions are reasonable and sufficient to depict what is observed in relevant scenarios. Indeed, our theoretical results and simulations on synthetic experiments will resemble the observations in natural image data, presented in Section 5.
As earlier, we will employ noise-augmenntttion distributions parameterized by a single parameter. Accordingly, we will denote our noise-augmentation distribution as Pa to highlight the only parameter, a. For instance, when augmenting data with a Gaussian we have that pv = Pa = a2) and in the case of a uniform distribution supported over a & ball of radius a, one has pv Pa- = Unif( a)). In this way, the final hed classifier is given by Smooth * P.)). A key goal of our work is to understand the interplay between these two parameters: B (controlling the certified radius) and a (controlling the aiise-augmentation of the data distribution).
3 Main Results
Our central aim in this section is to theoretically characterize the empirically observed difference between the benign risks of the original classifier (hh),, and that of the smoothed classifier trained noise-augmented data, Smooth (v Pa)). In other words, we want to obtain an estimate of the excess risk
(h)) R(Smooths * pp))) R()(h),
(2)
4

---

Published in Transactions on Machine Learning Research (04/2023)
Large Sa
Smoothing
Small Ca
(h)
6h p.)
Smooths(w(( * p.)) [e(h) Smooths<yy(h p.))
Figure 1: Theorem 3.1 and Theorem 3.3 deal with the cases of large (top row) and small (bottom row) interference distance Çh. respectively, where CA is the average of the pairwise distances between the orange regions, denoted by the black arrows. The text after Theorem 3.3 provides a detailed description of the different regions in the figure.
where the risk measures the probability of error over Рx, (see Section 1). We will present our result conceptually and slightly informally here, and we will provide a more detailed version of these later Section 4.
In our first result, we demonstrate that the behaviour observed in practice (namely, that performing noise- augmented training is beneficial is not universal. We do this by showing that there exists a. class of distributions Hi with a certain minimal interference distance property where training the classifier on a noisc-augmented distribution before performing the smoothing for certification is in fact detrimental. The interference distance Sn. for a classifier (hh) can be informally thought as the average & distance between any two disjoint input regions classified as by (bh) (normalized by the size of the domain). Figure provides simple illustration, where Ça is the average length of all the black arrows. We defer the formal definition of this property to Section 4, where we will use tighter characterizations by using the minimum and maximum of such lengths.
Theorem 3.1 (No need for aoise-augmentation).. There exists class of distributions Hi with large in- terference distance, such that, for all h H1, training smoothed distribution has benefit; that is (h) < (h) for all a. B 0.
This result is of importance because it sheds light the kind of behaviour that can be expected while making minimal assumptions of the (conditional) distribution h. Indeed, we now present result that upper bounds (h) as a function of the smoothing parameters, a, B.
Thcorem 3.2 (Simplified (pper-Bound) For any h with bounded support, (h) I Ga,s, where Ga is monotonically increasing function of both a and 3.
We pause to make a few remarks about Theorem 3.2. First, we see that Ga increases with the certification parameter 8, suggesting that the excess risk A,,3 may increase as we increase B. This behavior expected and reflects what is seen in practice. Recall that the inverse the smoothness parameter of the classifier the randomized smoothing strength, 3. Hence as 3 increases, the classifier changes more slowly, and more error is incurred the spiky regions of the domain where the true class fluctuates rapidly. This demonstrates the well known accuracy-robustness trade-off: larger & leads to better robustness certificates but worse benign performance (Gao et al., 2020; Cohen et al., 2019).
S (vh Po)) proportional
studying the robust risk the smoothed classifier. Nevertheless, understanding properties of the benign risk is an essential step towards understanding the robust risk, as the former lower bound the latter.
Note that
5

---

Published in Transactions on Machine Learning Research (04/2023)
Secondly, we see that Ga.9 increases monotonically with This suggests that, for any fixed value of B, the excess risk A,,3 is minimized at a O; ie,, it is better not to perform noise-augmentationn during training. This is contrary to the behavior of randomized smoothing in practice: to obtain a smoothed classifier Smooths(y/( Pa)) with a good benign risk a practitioner typically sets a = B > 0. One might be tempted to conclude that this seeming contradiction stems from the fact that the bound in Theorem 3.2 is Loo loose to be informative. Yet, we find that this not the case. In fact, Theorem 3.2 reflects the behaviour of (h.)(h) for a general h with bounded support, and this upper bound is tight for functions h E Hi, i.e,, the family of distributions from Theorem 3.1.
If retraining on noise-augmented data is not universally needed, then for what family of distributions is it. beneficial? It turns out that our notion of interference distance ÇA. controls this trade-off, as we now show.
Theorem 3.3 (Noise- Angieetnngtonntioonn helps for distributions with small interference distance). There exists class of distributions H2 with small interference distance, such that, for all h E H2, training on noise- augmented dala is favorable; i.e., there erisls a, 3,33 > 0 such that g < (h,
Before delving into our detailed results in Section 4, summarize few key implications of Theorem 3.1 and Theorem 3.3 for randomized smoothing, as illustrated in the example in Figure 1. There, a classifier (bh) predicts the class in the orange regions of the input space X, and class 0 otherwise. In the large separation regime that is captured by the family of distributions in Hi, the orange regions are far apart and have a very small effect on each other (this is seen pictorially as each positive regions shrinks uniformly upon smoothing as if there were no other positive regions). In these cases, training on noisy data leads to each of the orange regions to shrink in the final smoothed classifier Smooth (v' Pa)) for any O, and the smoothed classifier with noisy training has larger benign risk than training with no noise (Figure top row). On the other hand, as the separation parameter decreases the orange regions get closer to each other eventually having a significant effect on their neighbors after smoothing (Figure bottom row). In this regime, it becomes possible to set a > 0 to achieve better benign risk after smoothing compared to smoothing a classifier not trained with noisy data (i.e. with a = 0). Such distributions are captured in H2. For these distributions, the result in Theorem 3.2 is in fact not tight, and thus benefit can be derived from setting a >>0 O.
With these informal results in mind, we now present them with greater rigour in the next section, before moving to the numerical experiments later in Section 5.
4 Detailed Results
In this section we will expand and make our results from Section 3 more precisc. We will firstly prove in Section 4.1 the phenomenon observed in the large separation regime illustrated in the top panel of Figure 1, and demonstrated in our experiments (Figure 3). Next, in Section 4.2, we will construct data distributions that have a specific structure, following the phenomenon observed in the small separation regime, illustrated in the bottom panel of Figure 1.
Given a conditional distribution h, we define a partition of the input space X' as X = -- where I+ contains all the points where the classifier outputs 1, i.e., I+ {z E X: (h)(z)) = 1}. Further, we think of I as being composed of disjoint positive partitions I, I2, In such that each partition is simply connected 6. I- is the rest of the space, i.e., X') It, and is partitioned analogously. In oth words,
I+ = I1 UZ JM and I- = X' It,
where LJ denotes the disjoint union. Note that how to exactly obtain a valid partition above is unspecified - we construct the partitions explicitly for Theorems 4.1 and 4.3, and Theorem 4.2 holds for any valid partitioning. In Figure 1, these regions are colored orange. When a classifier is trained on data perturbed by noise Pa: and then smoothed by noise p3, cach of these positive partitions change in some way. Denote these latter partitions I (a, (a, ,).... I (a, 3). In the following two subsections, we will show how the difference wetw
6 A subset of the space X' defined in the standard topological sense be simply connected, if it is a connected region containing no holes, iee, every curve can be contimously contracted paint.
6

---

Published in Transactions on Machine Learning Research (04/2023)
Ig and [a 9) changes under different separation regimes, and how this in turn determines the behavior of Aa,3.
4.1 Large Separation Regime
We will first formalize and prove version of Theorem 3.1 by constructing suitable distributions Hi with large interference distance. We will then generalize the proof strategy to arbitrary distributions to obtain Theorem 3.2.
Unless specified otherwise, we assume that the noise distributions (i.e., those for smoothing) pa(2) we are working with are nice, in the following specific sense. Nice probability distributions are decrcasing in their argument x; and are spherically symmetric. Formally, a probability distribution p over Rd parameterized by scalar IR is defined to be nice, if for all 21, IRd p satísfies the properties
(Decreasing in argument norm) (Spherically symmetric)
Pa (x1) 2 Pa (x2);
if | S |2al|2, and,
Pa (x1) = Pa (x2);
if | = |
Nice distributions comprise Uniform and Gaussian as special cases. Throughout the paper, we consider the family of Po and py to be the same (e.g., both Uniform or both Gaussian). This is not required for our analyses, and simple extensions of our results could generalize further to these having different forms.
The lower interference distance for a given h is now defined as the minimum distance between any two positive partitions, i.e., S, mingze dist 4z) 1j). The lower interference distance over a family H is defined as Sx = min, S,, We can now state the detailed version of Theorem 3.1. The full proof, along with further properties these nice distributions, can be found in Appendix D)
Theorem 4.1. For nice noise distributions Pa Uni (0, a)) and ps Uni (0, there exists Hi with interference distance Su, max(aa, B), such that for all h E Hi we have (h, < (h) for all 0<a < Sz. and all 0 < B SHz"
While we tightly bound aa.g from above and below in Theorem 4.1, we are able to do so by assuming that the positive partitions I+ are perfectly spherical. In the following result, we show that we can in fact generalize our proof technique to obtain an upper-bound for Ax,s in Theorem 4.2 that only assumes that h is supported on the (bounded) data domain X, with partitions of arbitrary shape. In doing so, we obtain an upper-bound that might be loose in general. However, note that there exist simple distributions (Hz) where the upper-bound in Theorem 4.2 is tight, implying that it is the best one could hope for without assuming anything else about h. The full proof can be found in Appendix E.
Thcorom 4.2. For nice noise distributions Po: P3, for any h supported on a bounded domain X,
A (h) S Σ px (Be (8 (wiir - rd.))+)),
where p/ = -=
Val 0.5+7)
if Is a positive partition, i.c., Is E I+ and r = Va
0.5 0.5-T
otherwise,,
i.e., I& EI. Further, rh. = r + v W (0.5), and aa, V are the CDFs of the distribution of [|21[ when Pa and 2 ~ ps, respectively. px(S) denotes the measure of the set S under px. The upper bound (3) holds for any choice of (wwi {.)}]} such that at is the center of a ball of radius wh completely contained in In.r defined as Ix,- = fx E Ix: [h(x)- 0.5) 2T. We can choose the sequence ((w) (*))) such that the upper bound (3) minimized.
This results upper bounds the excess risk by one minus the sum of the mcasures of balls under the data distribution. Each partition It contributes to the upper bound in (3) via the difference (w* - r²)). The first term wht, denotes the inradius of subset of Ix, defined as the portion of Ij classified with a confidence margin t, i.c., In,- = (ar I&: [h(z) 0.5| 2 r}. The second term net captures the shrinkage produced by smoothing. Specifically, r denotes the shrinkage caused in Ig while moving from the original classifier to the
7

---

Published in Transactions on Machine Learning Research (04/2023)
Noise-Augment Augmented Training
(h)
4h * Pa)
61
C2
C3
C1
Randomized Smoothing
SaaddonizedSSmooihon
(+)( p2,)
v(v(h * Pa) * p&u)
An example h E H2 where noiso-augmented training is beneficial for randomized smoothing. The orange and blue shaded bars denote the regions where the smoothed classifiers make errors, ie., (h) A Smooth (w(h)) and (h) * Smooth (vi(hxpa))) respectively. Assuming suitable data-distribution px, the orange region can have a higher px-mass than the blue region, iee, Aoo.8o (h) A0,0 (h). See the text below for details of the four sub-figures.
Figure 2:
classifier, i.e., (hh + (/ Po). Similarly, ri.s denotes the shrinkage caused while moving from the noise-trained classifier to the randomized smoothed classifier, iee, v/ * pa) + (b * Pa) ps). For any fixed B, as we increase the noise-augmennationn strength a, the shrinkage ra,s also increases, leading an increase in the upper bound in Eq. (3).
4.2 Small Separation Regime
We will show that, unlike what is reflected by Theorem 4.1, there exists a family of distributions H2 characterized by a small separation distance where A,, indeed minimized at some a > 0, which is the behavior observed practice common image datasets.
We will begin with an illustrative one-dimensional example of a data distribution supported on X' where will show that the interference distance Ç explicitly controls whether any benefit can be obtained by noise-augmentation. We will observe the basic structure required in h for this to occur, and then generalize this structure to construct examples supported on X' C Rd forming the family H2 required for Theorem 4.3.
dimensional example We will now walk through the four panels Figure 2. First, we let defined as
h(x) = h(x)= ={0
x (-0.5)))) (02, 03) (c,, otherwise,
(4)
where the specific values of CI....Ca are not important for the example but can be found in Appendix F. Additionally, let px be uniform in [ei, ca] this assumption is needed, but simplifies the following discussion. The resulting (h) is plotted in the top-left panel of Figure 2.
For smoothing, we use the nice distribution Ps. = Unif([-Au/2, where 3o is just large enough, so that (vhh) * (x) = 0 for all x E (c), In other words, randomized smoothing ensures that the seoothed classifier Smootha, (v)) outputs a consistent label across the input, hence ensuring robust classification (and in particular, that label 0). However, observe that the benign risk of the smoothed classifier RSmoooth,, (v())) very high, as makes an error whenever z in the bottom left. panel of Figure? 2.
[c1, 02] U ca). This situation is shown
8

---

Exactly Learning Bayes Classifiers We pause here comment on the assumptions we made in analyzing randomized smoothing on a noisc-smoothed distribution, Smooth * pa)). As we mentioned above and as we prove in Appendix B our analysis assumed that one has access to the true conditional distribution of Published in Transactions on Machine Learning Research (04/2023)
We now consider the nice noise distribution for noise-augmented training, defined as Pao = Unif(I-cu/2 ax/ /2)). For a suitable value of a, we can ensure that 1b(h= ( PPa)))))))))))))) = 1 for all 2 E [[I,ca] ca] This is shown in the top right panel of Figure 2. But now, since Po was just enough to obtain Smooths, (w)(h) = 0, the additional positive mass in [c2, e3] causes the classification to flip, and now Smooth,, (1+ Pa. (z) = for all x E [c1, cal- The benign risk of the smoothed classifier now is much lower than earlier, as only makes an error on the small crevice [c2, es]. This situation is shown in the bottom right panel of Figure 2. Thus, one can choose h p, ao: 9o such that
R(Smoothg, (1b(h) * Poo)) < R
demonstrating that training with noise augmentation is indeed beneficial when h has a low interference distance. The specific values of oo So can be found in Appendix F.
Fixing the woise-angmentation distribution Poo and the smoothing distribution Pa+, we now modify h to h by increasing the interference distance |c2 - ca while maintaining the same structure, i.e. h(x) = when x < 6 U (z), U (2a, 0.5), and h(x) = otherwisc. When (02 - ماع > ao/2, noise-angmentation with Pro is no longer effective, i.e., (v) Poo) = (b(((h) poo)) Intuitively, this is caused by insufficient positive mass near any class-0 point for the prediction to flip after noise- augeentatmtniiinnn and this can be verified using the values of ao, 8o provided in Appendix F). Applying randomized smoothing (v((h) * pao) now simply leads to Smooth (1x(h) * (z) = =0 everywhere, implying that the risk after smoothing is high, i.c.
R(Smootha, (vh(h) * Poo)) 2 R(Smooths, (+hh)).
(6)
Thus, we have shown via this example that the interference distance directly controls whether we get any benefit out of training with aoise-augmentation (5) or not (6).
The distance Ic2 - csl above corresponds to a small upper interference distance 2, which we define now as the maximum distance between any two positive partitions, i.e., Ç maxizy dist 1z). With this definition, we can now extend the ideas in the simple example above to general constructions in d dimeension
Theorem 4.3. There exist nice distributions Pa: Pa, family H2 with low interference distance SH and data-distributions px, such that for all h E H2 we have Au, (h) > (a,s( for some > 0, > 0.
We pause again to understand some implications of Theorem 4.3. From the one-dimensional example and the proof of Theorem 4.3, we see that training with noisy data, ie., a > 0, is better for distributions with low interference distance. We conjecture that natural distributions follow this structure as well, containing regions corresponding to one class that are packed closely in the domain. Interestingly, we find evidence in the favor of this conjecture in our experiments in Section 5. Moreover, this result also shows that there is no reason for the noise level a to be the same as the smoothing level 3 for final smoothed classifier to obtain its lowest risk. This suggests that the common practice of using = 3 for randomized smoothing (e.g,, see (Cohen et al., 2019)) might not. be optimal. Indeed, we will shortly demonstrate in our experimental section that better choices for smoothing can be found by relaxing the constraint that the training noise level a should be equal to B. Additionally, our findings might provide a theoretical foundation for recent works (Alfarra et al., 2020; Anderson and Sojoudi, 2022; Súkeník et al., 2021) on obtaining an adaptive /3 for smoothing at each input point.
E[Y]X,]. However, in more realistic settings, the learned predictor might deviate from this optimal value. We now argue that our analysis is still relevant in these cases, too.
On the one hand, in Theorem G.I, we provide an extension of our result in Theorem 4.1 by considering a predictor that is an inexact approximation to the conditional expectation. In other words, we assume that training with nois--augmentation results in a function g(x) that is not too far from the true smoothed conditional distribution, 19(x)- * (x() S n for all x E X. As we show in Appendix G, our same proof technique allows us to show that indeed, there exist. distributions where no benefit, can be expected from
9

---

Published in Transactions on Machine Learning Research (04/2023)
randomized smoothing, even in this more general case where the assumption of learning the true conditional
distribution is relaxed.
On the other hand, it is also not hard to see that our results that provide an upper bound to the excess risk based on Bayes classifier, (h,, are also useful in characterizing upper bounds to more realistic predictors that might deviate from the true conditional distribution. Indeed, given access to g that only an approximation h Pas one can show (see our derivation in Appendix G) that the excess risk of smoothing g can be upper bounded by
Da (k, + px ((h * Pa) Px) + g()))
As a result, our upper bound in Theorem 4.2 also provides an upper bound to the excess risk of more general predictors g and the tightness of this bound is naturally controlled by the mass under px of the errors between g and h Pa-
Extension to Multiple Classes Although our theory was developed for binary classification, a standard extension to K-way classification is possible, using the technique followed while certifying multi-class Randomized Smoothing based classifiers Cohen et al. (2019), Yang al. (2020). In this context, the class Y now represents one of the K-classes, and Y = represents all the remaining classes. All our theorems would then extend, having additional parameter for the class viewed as 0.
Having established our thcoretical results, we now turn to an empirical verification of some of them on synthetic datasets, well as MNIST and CIFAR-10.
5 Experiments
Synthetic Experiments. We begin by conducting synthetic experiments" with distributions resembling those used in the proofs of our existence results Theorems 3.1 and 3.3. We take X' = [0, 100] x [0, 100] the data domain, and sample the positive partitions of h as spheres at random locations in the domain (see Appendix A for more details about the construction) to obtain the data-distribution hs, where the superscript C denoles the interference distance. Figure 3 shows a few examples of AS for different values of Ç.
<= 0
Ç t 10
Ç = 20
= 30
Examples of *H()) for different values of Ç. The blue regions denote (x)))(r)) 0 and the orange regions denote (x)))(z)= 1.
Figure 3:
In Figure 4, we report quantitative results using our synthetic distributions as described above. Over several choices of interference distance Ç. we first sample several synthetic data distributions h$, We then plot the quantity Ax,9 Ao,s, which is the difference between the benign risks of smoothing a noiso-angmented classifier, i.c., R(Smooths
P&)), and smoothing a classifier not trained with noise-augmennation, i..,, R(Smooth a (()on))),(((())))) We increase the smoothing strength B moving from left to right in Figure 4, and plot the difference in the risks function of a for each 8. Recall that noise aoise-augmentttion is useful only when can
We provide code for all of our experiments at htt.:tt....//aaaaapaaaaaaaaaaaao htwpa///annnddddeeaaa smoothing.
10

---

Published in Transactions on Machine Learning Research (04/2023)
find ao. So such that A D O. Accordingly, plot dashed line whenever noiso-angmentation is useful, Le., 3oo, 90 Aao.Po 40.% and solid otherwise, i.e., Va, / Aa.3 2 An.3-
At high Ç. we are operating in the large interference distance regime and the results from Section 4.1 apply. Those results dictate that Aa.9; should be minimized at a = 0 for any fixed 3o 0. Indeed, this phenomenon can be seen Figure for Ç = 3, where we see that the line remains solid for all /.
On the other hand, at lower (, we go into the small interference distance regime and the results from Section 4.2 apply. Those results dictate that A..A, should be minimized at some 0 given large enough, but fixed Bg > 0. Indeed this phenomenon is seen in Figure 4, where the lines tend to become dashed as increases. Thus, our synthetic experiments confirm the predictions from our theory.
8.0
B 11.0
B 14.0
0..00
[
0.008
[
(
0.080
0.12
2
[
0.006
[=3 3
0.025
[ -
{
Ao.
0.10
0.004
0.08
0.002
0.005
0.06
0.000
-0002
0.02
0.005
0.00
α
Figure 4: Synthetic Experiments showing the variation in Aa.o. The line dashed if there exists a > 0 such that A Au,s, and solid otherwisc.
MNIST, CIFAR-10 Experiments. We now procoed conduct experiments with real data distributions. For a range of finely spaced in [0, 1], we train standard CNN ho with isotropic Gaussian noise-augmentation with variance a² i.e., Pa =0 22 For each of these trained models, use the isotropic Gaussian with variance 322 with B E 10, as the smoothing distribution, i.e., Pş (O, 8 I), to obtain the smoothed classifier Smooths(H{h pa)). We then plot the standard empirical estimate of the risk, Å., (ss.g)ES [SSmooth
v] over the test set Sust, for different a,3 in Figure 5.
The first observation that we make from the MNIST and CIFAR-10 plots in Figure 5 is that non-zero lata-augmentttion is always beneficial, i.e., a > O. While not an implication arising from our theory, this behavior is reminiscent of our results in Theorem 4.3, suggesting that real data distributions lie in the small interference distance regime. Additionally, we note the similarity the synthetic experiment plots at low Ç in Figure and the real-data curves Figure (upto scaling of the a-axis, and the fact that we subtract. o for normalization in Figure 4), providing empirical validation for our theoretical assumptions.
The second observation make from Figure 5 is that, suggested by Theorem 4.3, the smoothing parameter need not be the same the data augmentation parameter for the best performance of the smoothed classifier. This phenomenon has also been observed empirically in prior work Alfarra et al. (2020), Salman et al. (2019), Zhai et al. (2020), and our results provide a theoretical foundation for such obscrvations.
6 Related Work
In this work, we study randomized smoothing, which is currently the method of choice for obtaining robustness guarantees for deep, complex neural network classifiers. Since the early proposals of stochastic smoothing (Liu et al., 2018), many works have derived robustness certificates against adversarial attacks for smoothed classifiers (Lecuyer al., 2019; Li et al., 2018: Cohen al., 2019). These certificates obtain radius r around input such that the network prediction is robust in Ep ball of radius around x. Studied
11

---

Published in Transactions on Machine Learning Research (04/2023)
--000 0.25 3
0-02 of 0.26
10"
0.000
0.4.4,
10
0.6.0 o 0.42
8- 0.1, o' 0.08
0.7.7 0.02
==00,
A 0.S, of 11.29
038
2x MP
8 0., o² 0.50
- 0.5, of 0.37
10-2
0.6, of 0.39
0.0
0.2
0.1
0.4
0.5
0.6
at
(4) MNIST
(b) CIFAR-10
Figure Plot of A,,9 for MNIST (5a) and CIFAR-10 (5b). For each fixed value of B 3o, the legend a* (and the corrosponding shaded disk the plot) shows the minimizer of the A,, curve.
balls include p 0 (Levine and Feizi, 2020a; Lee et al., 2019), p= = (Teng al., 2019), (Cohen et al., (Zhang, 2002). Certificates have also been extended to non-e,
2019; Salman et al., 2020; 2019) and smoothing distributions (Levine and Feizi, 2020b). For different notions of optimality, the optimal certificates have also been characterized (Yang et al., 2020; Kumar et al., 2020)
However, there has been lesser attention given to the impact that randomized smoothing has on the benign accuracy of the smoothed classifier, and a theoretical understanding for the need-or or lack thereof for noise-augmented training of the classifier in order to produce accurate smoothed classifier. Recent work in Gao et al. (2020), which is closest to ours in spirit, takes first step towards this goal by analyzing the class of hypotheses that are realizable when training strictly reduces the hypothesis class whenever the smoothing strength is above a threshold. In this way, Gao et al. (2020) provide some thcoretical basis for the reduction of accuracy of the so smoothod-trained classifier. Elsewhere, Mohapatra et al. (2021) theoretically demonstrate that randomized smoothing leads to shrinkage of class boundaries for simple data distribuutons. Importantly, their definition of "shrinkage" is that the bounding sphere (or cone, for "semi-bounded" regions) of the decision boundary becomes smaller. This is different from our analysis, as a shrunk decision region R& might not be subset of the original region R under this definition. In comparison, our universal result in Theorem 4.2 holds in much more generality for arbitrary (bounded) data-distributionss, and our existence results Theorems 4.1 and 4.3 construct specific synthetic datasets. While Mohapatra et al. (2021) only analyse the distance ||ʃ Smoohh, (f) given a trained classifier f, we directly bound the risk R ((Smooths and shrinkage does show up in some parts of our analysis. Our proof techniques are able handle both noise-angmentation of strength a and randomized smoothing of strength B simultaneously, allowing smoothing (in other words, showing cases where the combined effect might not be shrinkage of the decision boundaries). Some recent works have tried to move away from having the same smoothing and noisy-training distribution, by studying input-dependent smoothing (Alfarra et al., 2020; Anderson and Sojoudi, 2022; Súkeník el al., 2021). Lastly, and in a very different context of graph convolutions ional networks (GCNs), recent results in Keriven (2022) show that a positive level smoothing (defined as the number of GCN layers) can be beneficial for supervised learning task, before becoming detrimental once smoothing is too large. Studying further connections between our analysis and smoothing for GCNNs constitutes an interesting direction of research.
hed data. Their result shows that this re- trainingg
discover cases where roise-augmentation helps randomized
12

---

Published in Transactions on Machine Learning Research (04/2023)
7 Conclusion, Limitations and Future Work
In this work, we provided a theoretical understanding of how noise-augmented training affects classifiers defended using randomized smoothing. We identified a parameter of the data distribution, which we dubbed interference distance, that, for certain families of data-distributions, determines whether noise-angmented training could be beneficial for randomized smoothing. Using this parameter, we showed there exist data distributions where noiso-augmented training reduces the accuracy of the final smoothed classifier, contrary to common observation. Our upper bound to the benign risk in Theorem 4.2 for very general conditional distributions and which is tight for distributions presented in Theorem 4.1- demonstrates that no benefit. of randomized smotthing is possible without further structural distributional assumptions. In turn, we showed the existence of distributions with small interference distance in Theorem 4.3, where improvements by noise-angmented training is possible. We complemented our theoretical results with empirical validation, suggesting that real-world distributions lie in regimes where the parameter ( is small, and so noise-augmented training can indeed help randomized smoothing if the smoothing strength chosen properly. Contrary to intuition, the proof of our theoretical result in Theorem 4.3, and our experiments, suggest that this smoothing strength need not be the same as the noise-augmentation strength for best performance of the final predictor.
We now revisit the open questions that we posed in Section 1. Firstly, why is noise-augmental ion helpful while training the base classifier? We saw in the bottom row of Figure 1 that noise augmented training helps the smoothed classifier have good benign accuracy when we are in the low-interference distance regime, as it alleviates the degradation of the risk incurred by randomized smoothing at deployment time. Secondly, how does the performance of the smoothed classifier depend on the training noise distribution? We saw Theorems 4.1 and 4.3 that in the high interference regime, training with low to zero noise leads good performance of the smoothed classifier. On the other hand, in the oow-ineerferenc regime, the training noise can be tuned to extract good performance of the smoothed classifier. These conclusions are derived for the cases when the same family of distribution is used for augmentation during training and for smoothing at deployment time. Future work could consider exlending these to different classes of distribution. Thirdly, is srise-auumenned training needed for all always effective in reducing the risk of the classifier after randomized smoothing, and the interfrenco-ddistance parameter can distinguish between families of data-distributions where noise-augmentation helps randomized smoothing. It remains unclear how to efficiently determine this parameter for real data-distribution which would allow us to determine whether noise-augmented training is needed at all, or what the optimal parameters of the augmentation distribution should be. This remains matter of future rescarch.
The answer is no, noise- aabis--ugmmetattion is not
We note that our results are independent of the learning aspect of the problem, i.e., we assume that the learning algorithm is good enough to obtain the predictor with the lowest possible risk. These assumptions, while simplistic, nonetheless allowed us to characterize observations that have practical relevance. Though we provide some results on how to relax such assumptions in Appendix G, we see this as starting point. for future work that should explore these trade-offs in more generality. Additionally, our experiments and theory suggest that the best data-auggentattonn strength is not the same as the smoothing strength in general, and we hope that future work can theoretically quantify and provide precise estimates for this quantity. Finally, in this paper, we studied the benign risk of classifiers after smoothing. Future work could extend these results to the study of the robust risk (which is lower bounded by the benign risk), and extend our techniques to quantify how the former depends on the noise-augmentation distribution.
Acknowledgements
The authors thank René Vidal for insightful comments, as well as the anonymous reviewers for their valuable suggestions, which helped improve this manuscript. AP acknowledges the support of DARPA (via GARD HIR00112200100 and NSF (via Grant 1934979). JS acknowledges support from DARPA GARD HR001 12020004.
13

---

Published in Transactions on Machine Learning Research (04/2023)
References
Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem. Data dependent randomized smoothing. arXiv preprint arXi::201..04: 04351, 2020.
Brendon G Anderson and Somayeh Sojoudi. Certified robustness via locally biased randomized smoothing. Proceedings of Machine Learning Research vol, 144:1-14, 2022.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. orXiv preprint arXiv:1802.0044 0040 2018.
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, and Aravindan Vijayaraghavan, Adversarially robust low dimensional representations. arXiv preprint arXix:1911.13221 2019.
Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, and Aravindan Vijayaraghavan. Adversarial robustness via robust low rank representations. arXiv preprint arXin:2007.06555, 2020.
Sébastion Bubock, Eric Price, and Ilya Razenshtoyn. Adversarial examples from computational constraints. arXiv preprint Xix: 10204 2018
Nicholas Carlini and David Wagner. Adversarial examples are not easily delected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3 14, 2017.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint 1tt.:199000291.. 2019.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In Advances in Newral Information Processing Systems, pages 230-241, 2018.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Tee. Convergence of adversarial training in overparametrized neural networks. In Advonces in Neural Information Processing Systems, pages 13009-13020, 2019.
Yue Gao, Harrison Rosenberg, Kassem Fawaz, Somesh Jha, and Justin Hsu. Analyzing accuracy loss in randomized smoothing defenses. arXiv preprint arXiv:2003.01599 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arxio:1412.60 6572, 2014.
Shixiang Gu and Luca Rigazio. Towards deep neural network architectures robust to adversarial examples. arXiv preprint 14 12055688, 2014.
Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over) smoothing. arXiv preprint arXiv:2205.129 12156, 2022.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomizod smoothing for certifiable robustness. In International Conference on Machine Learning, pages 5458 5467.
PMLR, 2020.
Alexey Kurakin, lan Goodfellow, Samy Bengio, et al. Adversarial examples in the physical world, 2016.
Richard J Larsen and Morris Marx. An introduction to mathematical statistics. Prentice Hall, 2005.
Mathias Lecuyer, 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),
pages 656 672. IEEE, 2019.
Guang-He He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advances in Newral Information Processing Systems, 32, 2019.
14

---

Published in Transactions on Machine Learning Research (04/2023)
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, pages 4585-4444 4593,, 2020a.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 1988-3947. PMLR, 2020b.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. Xivi preprint Xrx: 1809.80000000 0009031133. 13, 2018.
Bai Li, Changyou Chon, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. Advances in newral information processing systems, 32, 2019.
Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensent celf-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pages 369-385, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint orXiv:1706. 706.06066, 2017.
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. Xix preprind ar Sd::77220420 2017.
Jeet Mohapatra, Ching- Yun Ko, Lily Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Hidden cost of randomized smoothing. In International Conference on Artificial Intelligence and Stalistics, pages 4033 4041. PMLR, 2021.
Ramchandran Muthukumar and Jeremias Sulam. Adversarial robustness of sparse local lipschitz predictors. arXiv preprint arXiv:2202.12216 2022.
Ambar Pal and René Vidal. A game theoretic analysis of additive adversarial attacks and defenses. arXiv preprinl ar Xix:2009.005530 2020.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. Xrxiv preprint arXiv:1801 001.09944, 2018.
Hadi Salman, Jerry Li, Tlya Razenshteyn, Pengchuan Zhang, Huan Zhang, Scbastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J Zico Kolter. Black-box smoothing: A provable defense for pretrained classifiers. arXiv preprint arXiu:2003.01900 2020.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. In Advances in Neural Information Processing Systems, pages 5014-5026, 2018.
Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint arXiv:1809.022. 02100, 2018
Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input-dependent randomized smoothing. arXiu preprint arxix:2110. 05365, 2021.
Jeremias Sulam, Ramchandran Muthukumar, and Raman Arora. Adversarial robustness of supervised sparse coding. Advances in neural information processing systems, 13:2110-2121, 2020.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprinl Xrv::133 61999, 2013.
15

---

Published in Transactions on Machine Learning Research (04/2023)
Jiaye Teng, Guang- He Lee, and Yang Yuan. & adversarial robustness certificates: randomized smoothing approach. 2019.
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks adversarial example defenses. arXiv preprint or ar:i:2002 08347, 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy, arXiv preprint arXi:: 12152, 2018.
Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis of adversarial learning: A minimax approach. In Advances in Neural Information Processing Systems, pages 12259 12269, 2019.
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, llya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning, pages 10693-10705. PMLR, 2020.
Dong Yin, Kannan Ramchandran, and Peter Bartlett. Rademacher complexity for adversarially robust. generalization. arXiv preprint arXiv:1810. 11914, 2018
Fisher Yu, Dequan Wang, Evan Shelhamer, and Trevor Darrell. Deep layer aggregation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2403 2412, 2018.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-frce and scalable robust training via maximizing certified radius. arXiv preprint arXiv:2001.02377 2020.
Tong Zhang. Covering number bounds of certain regularized lincar function classes. Journal of Machine Learning Research, 2(Mar):527-55) 2002.
16

---

Published in Transactions on Machine Learning Research (04/2023)
A Experimental Details
Synthetic Experiments To construct our synthetic distributions, we take X' = [0, 100 x [0, 100] as the data domain. We start with an empty set I = {} and radius r y= 10. We repeat the following steps 500 times: (1) Sample a center e in X' uniformly at. random. (2) Test whether ||e- 2' > < 2r for all spheres (e,(dr,) E I. If true, add rr, to I, otherwise reject this sample. At the end of this process, we obtain set of spheres I satisfying the property ||c d 5 ++22 2r for all c d', where Ç is the interference distance.
MNIST Experiments We take 100 samples from each of Pa. Pa per image x in the MNIST test set to compute a single point Aa,s. The figures are quite stable against random initialization due to the MNIST test set size of 10000 samples. We use the following archilecture for the neural network classifier ha;
12put(28,28) 28) - (1,,3) + Conv 1 + Lincar(9216, 128) - Linear(128, 2)
In the above, the input image has dimension 28 x 28, and convolution layers with filter size of 3 and stride of 1 are applied. The notation (a, denotes that the input. depth is and the number of filters is b for the convolution. Finally, the notation Linear(a, b) denotes affine transformation with input dimension and output dimension b.
CIFAR-10 Experiments We use the DLA Architecture (Yu et al., 2018) for the neural network classifier. For obtaining has we use standard noise augmentation on the CIFAR-10 dataset, i.c., we augment every training sample with noise sampled from Pa- For obtaining the smoothed classifier Smoothg(ha)) we use 200 noise samples from Pg for every image. We report results aggregated over 4000 images from the CIFAR-10 test
B Derivation of Bayes Classifiers
Recall that X and Y denote the data and label random variables, respectively, such that (X,Y) ~ px,y. In this binary setting, the Bayes classifier, i.e. the classifier that minimizes the probability of misclassification, can be obtained by thresholding the conditional expectation E[Y]X = x] at 0.5. We assume that the learning algorithm results in a predicted score hxx)= = E| = x]. The prediction of this model is given by (h)).
Now, we instead train on noisy data, X, ~ px, where X, = X + such that V ~ pp.. It well known that p'x = px= * pv, where denotes the convolution operator (Larsen and Marx, 2005). Further, we can show that the conditional expectation is X x] = h pv:
E[y X, x] p(Y 1|X, z) p(Y = +V x)
PY = 1|8 + +V x, V = =u)p (v)dv
p(Y = x|1 = x -, v, V = v)py(vi)) (v)dv
p(Y 1|8 = x = (o)dv
(8)
M(x - ())v = (h * xv)
where (8) uses the fact that the noise variable V is independent the data variable X. As carlier, the Bayes classifier is now given by thresholding of the conditional expectation, i.e., (hh pv).
17

---

Published in Transactions on Machine Learning Research (04/2023)
C Nice Distributions and their Properties
Nice Distributions. A probability distribution p over R parameterized by a scalar E R is defined to be nice, if p satisfies the properties (9) and (10):
(Decreasing argument norm) (Spherically symmetric)
Pa(xi) 2 (x(2)), Pa(x1) (x
if || S |
(9)
if || = |
(10)
For case of understanding of the rest of the section, a ball of radius 0, i.e., Po Unif( Br, (0, 0)), which is nice distribution.
think of p to be the uniform distribution supported
Shifted CDE. We define the multivariate cunulative distribution function (CDF) w.r.t. E X C R as
T (r,
Palx t)dt
(11)
For nice distributions p, can show the following properties for the CDF:
(Decreasing in argument Norm)
Pa(r, < (r(
if || ll 2 1 l2
(12)
(Spherically symmetric) (Increasing radius)
(a(r, = (r,
if || ll = ||22|
(13)
(r(ri,)) 2 &. (r2, x); if 2 12
(14)
To (13), we choose any 21, 22 with ||x,|| | Now, note that the integral in (11) can be rewritten @ (r,x)) (I.B,, Pa (t)dt, which in other words computes the mass of the Pa contained in an lz ball of radius around x. Since ||<| || = || we can find a rolation matrix Q that maps 21 to #2 as Qui = d2- Observe that the same rotation matrix Q also maps the entire ball B(x1,7) to the ball B(x2, r). Finally, (13) follows from by observing that Pa = Pa for any rotation matrix Q as || ||0=122-
Now that know that (r, is spherically symmetric in the second argument, we can focus our attention to the restriction of & along the standard basis vector E₁ for showing (12). For any > 0, consider the
function Φ: R + R defined as d(c)= = ((r, ce,) for scalar c. Points 22 with || || 2 ||zll correspond to ||жد|| in the sense that 4(r, 21) = Φ(c1) and 4(r, = o(c2). and ei 2 2 0. Define
C1 = ||>م|| and D1 = Beg (c161, r) and D2 = Big (C2e1, We have,
[ (t(t)dt
p(c))
JIED
I JECDDNDD Pa(l)dt+ +
/ SEE(DIND)) pa(l)
/
(LE(DiNDA) Pa(t)dt+ = ((02).
JEE(DAND)) (((d)
(15)
To obtain the inequality in (15), observe that D1, D2 are spheres of the same radius with their centers Cye1, 0262 such that 0 S 02 S ct. This ensures that any point in D2 \ Dj has a lower le norm than any point in Dj D2 which in turn means that the every term in the integral SIE(DAAD.) Pa (f)dt is lower bounded by every term in the integral SIE(D, Pa (t)dt, using Property (9) of pa-
Due to properties (12) and (13), that 2)) is non-increasing as ||ا|| increases. As result, define the function Aar IR - R as
Aar(C)=
max (r.z)2c)
||0||2.
(16)
{z:
which computes the maximum & norm that ||æl| can take before the CDF falls below c. This function will be useful us later when we reason about how much does smoothing a classifier contract or ezpand its positive regions.
18

---

Published in Transactions on Machine Learning Research (04/2023)
We finstly note that Aarr is decreasing in This can be seen increasing makes the constraint tighter in (16), and hence the optimal objective value can only decrease when we increase
Secondly, we note that ( (T, zo)) = | for any To E X, a 2 0 and r 2 0. This can be seen by observing that for x = 20. we have cu = (r, 2o), and thus zu is a feasible point for the optimization problem max(u: t. (n.a))cc)) ||a]|22 Hence (ca) || Then, by property (12), we know that (r x²) - (r, mo) whenever ||> || implying that any such x' will not be feasible. This shows that (c,r | completing the argument.
D Proof of Theorem 4.1
Theorem 4.1. For nice noise distributions Pa = Unif(Be, (0, a)) and ps = Unif( (), there ewists Hi with interference distance S4y > max(a, B), such that for all h E Hi we have ( < ah, for all 0ca < Sm. and all O < B EN.
Proof. Recall that h(z) p(Y = 1|X = x). Let 11, I2...., In be spheres such that 1 = Bea(cg,r)). Define h(x)) = 0.5 + whenever x E 1 U U Je, and O otherwise.
Large Interference Distance Recall that S, = mingy dist (4: 4,), and assume that S, max B).
Recall the CDF (I( = - Siillss Pala - t)dt, which is function decreasing monotonically in || Also recall the function Aar with the property ( |2ll2 for all æ. For any æ E Ij, we obtain h Pa
((t)pa(x-t)dt / h(t)pa(I - t)dt + // h(t)p.(z - -tldt
h* h* px()) =
/ (0.5 + (xpa - t)dt + Sry,, h(t) 0 dt
J
= (0.5 T) (x - -cg,r))-
a-Shrinkage The regions where the classifier p..) predicts are given by 4io for I,: h*p. 2 0.5). This region Lja is an a-shrinkage of Iy and can be obtained as
(0.5 + () 2 0.5 = || 1| 11l2 S Aar,
0.5
def
(17)
0.5
where we have used the definition of the function Aa,
Now, the regions where the classifier Smooths(h Pa) predicts 1 are similarly given by Ia,, = for e Ii @h e Pa)) 2 0.5). We can follow the same steps as earlier on the a-shrunk balls Ii = Bi, Big(ei r,)) This time, for x E I we have
/ ((h * (a)*pa)(0ps( t)dt + Sxrtsn w(h * pa)(1pp(p t)dt
Smooths(1b() (x)
15.0
= f 1,,
1.ps(1 - t)dt = $3 - Cj, r,a))
B S-Shrinkage Again, we can find the 3-shrinkage in Ij,a as
6 - cj,Taa) 2 0.5 = || c;112 1l2 Aarry. (0.5) T2a
19

---

Published in Transactions on Machine Learning Research (04/2023)
We have thus obtained f, the a, 3-shrunk balls, i.., I,, Beg(eg,T3,aa)) We compute the risk of the smoothed classifier as
R(Smooth (1/() Pa)))
J S pa)) Yl ddddy
/ Smoothhs (v/h (r) (px())))x((x)ll + (whh (olp:///ooooollllllolooooooaadd
Let I U2... & be the posilive regions, and Ia, 1 U 2208 ... U Iaa be the shrunk positive regions. For the first term above, we note that
0,
E Ia,
( px))) 1/p(1/x) =
0.5
x E I Ia.0
0,
# E I
Similarly, for the second term, we see that
0.5 -
I In,8
Smooth (=))()))() (a)
0,
I Ia.ß
0,
E X I I
Substituting into the integrals, we obtain the risk of the smoothed classifier
R(Smooth Pa))) = (0.5 + (Z Ta,z) + (0.5 - T)Px (Ta
= (0.5 + (T) 2Tpx (In.t))
Recalling that (x( is positive everywhere in the domain, and using Io,g 3 Ia, for < a, < <S, in the above, we obtain
px( > pI = -TTpx (Ia.)) > -2Tpx(Io.))
In other words, we have
R(Smooth (1) pa))) R(Smooth, = Da.9 > Do,3- E
E Proof of Theorem 4.2
Theorem 4.2. For nice noise distribulions Pos Ps, for any h supported a bounded domain X,
A (h))(h) S Σ px (Be (wtt r(.g)))))
(3)
where pk a V=² 0.5+7
if Is a posilive partition, i.e,, Is E I+ and rh V
otherwise,
0.5-7
i.c., Is EI Further, ra. = r + v (0.5), and Va, V are the CDFs of the distribution of ||=|| when Do and z ~ pa, respectively. PS(S) denoles the mensure of the set. S under px- The upper bound (3) holds for any choice of (wwh, )*)} such that at is the center of a ball of radius wh completely contained in Ix.r defined as Ix,- = fa E Ix: [1(x)) 0.5) T). We can choose the sequence ((wt,,, such that the upper bound (3) minimized.
Definition E.1 (Inradius). The inradius of a set S is defined the largest radius such that an &g ball of radius p is completely contained in S. In other words, there exists S such that Be, (2,r*) S.
20

---

Published in Transactions on Machine Learning Research (04/2023)
In order to bound (h,)(h), will follow strategy which generalizes the arguments in Theorem 4.1 to any arbitrary conditional distribution h(z) p(Y = 1|x = z). Our first step would be to upper-bound the positive partitions of (h Pa), i.e, the regions where the classifier trained with noise-augmentation predicts 1. This will be then be used along with properties of randomized smoothing to apper-bound the positive partitions Smooth (vb( * Po)), i.e., the regions where the final smoothed classifier predicts 1. These regions would finally be used to upper bound the risk of the smoothed classifier a function of a and B.
Proof. Let I+ denote the set of maximal, non-empty simply connected subsets I S X of the input space such that h()) 2 0.5 for each x E I. Pick any / E It and let I, C be such that h(x) 2 0.5 + + for each x EEE T, and 0 S r < 0.5.
Bounding region where (h Pa)(x) 1. Let J1 1, be the maximal subset of 4 such that the noise- trained classifier ob * pa) predicts 1 in JI, i.e. J1 = {ir I; C (i is satisfied }, where Ci is the condition (h Pa) (z) > 0.5. We will firstly lower bound the area in J1 by using stronger condition (2 = f1,-z(7 + 0.5)pa. (6) X 2 0.5. To show that C2 is stronger condition than C₁, we will show that C2(x) = 1 implics (2)
follows:
(h * px)p) = J Mx (6)p
J ,, 1(6)pa 5)dō
(8)) / (r (T 0.5)p5pp. - 8)dō / 1.-2
Defining J2 (x I, C2(z) 1}, that J2 J1. We will further lower bound J2 by considering the largest d-dimensional ball centered at 0 that can be inscribed in I, for each æ. Define the condition Cz(2,r) as the following:
Ca(o,r) (C2(x) = and B(r,r) S I+)
=
(T + 0.5)pm (0) 2 0.5 and B(a,r) I
(18)
The set Js(r) for E I, Cz(2,r) 1} is subset of Ju for all 0. In words, Ja(r) denotes the set of points in J2 which are at least distance away from the boundary of Ir. Finally, combine the two conditions I and Il in Cz( to obtain our final condition C1(x,r).
S (T ( (.5) 2 0.5 and B(x,r) I,
Ca(z,r)
(19)
Note that B(x,r) r) C T, is the same as B(,,r) S I, I,-2a x. Hence, the integral (19) over a smaller set than (18), from where follows that C₃ stronger condition than C3 and the set J4(r) tsr e 4; C4(2,)) 1} is subset of (r( for all 0.
We now simplify Ca(r) by using the distribution of ||=1 where z ~ Pa. as follows.
J Pa (5)dō = Pr |||=1|2 S
Srupo
= =V.(2
21

---

Published in Transactions on Machine Learning Research (04/2023)
In the above, a is the CDF of the distribution of | when Pa- Setting (r + 2 0.5 gives the following condition
0.5
Cs(x)= = B(r, r) S I such that r 2
Val
0.5
0.5
B Iy Va
C 4
0.5 +
Our final subset Jz(a) {- E L: Cs(x) = } denotes the set of points in I which are at least Ta
Vo
0.5
away from the boundary of I.. In other words, Js(a) S Lr is To conttraactoon of Lr.
0.5+7
Bound region where Smooth3 (1 Pa)) =. We will now follow the same general strategy the previous part of the proof. Let K1 Js(a) be the maximal subset of Js (a) such that the smoothed classifier Smooths(H)(h Pa) predicts 1 in K1, Le., K1 fa Js(a): D₁ (xx)) is satisfied }, where Di is the condition (Smootha(V(h (a)) 2 0.5. We will firstly lower bound the area in Ki by using stronger condition D2 = [ Ps po(0)dō 2 0.5. To show that D2 is a stronger condition than D1, we will show that D2(x)) implies (x) 1, as follows:
3Smooths($(() pa)) = / (v(h+p)))= (0o0))((=00p00000 8)po())dō
I (w(h pa))(())pp( 5)d8
(s())
= S po(a -0)66 [s(a)
= [
Jo(a)-o Po(8)d8
Defining K2 = fx E Js(:): D2(x)= 1), we see that K₂ S Kg. We will further lower bound K₂ by considering the largest d-dimensional ball centered at 0 that can be inscribed in Js(a) - for each æ. Define the condition Dz(2, r) as the following:
D2(x,r) (D2(x) and B(x,r) Jo(a))
=( [6(()) Po(o)dō 2 0.5 and B(I, r) S Jo(())
(20)
The set Ka(r) = {x Jo(a): Dz(a, 1} is subset of K2 for all r > 0. In words, Ka(r) denotes the set of points in K2 which are atleast r distance away from the boundary of Js(a). Finally, we combine the two conditions in D) to obtain our final condition (I,
Sf P=())d8 2 0.5 and B(a,r) Ja(a)
Da(x,))= JB(o.r)
(21)
Note that rz S J5(a) is the same B(O,r) S. Jı(a) z. Hence, the integral in (21) is over a smaller than in (20), from where follows that D4 is stronger condition than D3 and the set Ki(r) fa Js(a): Da(z,r) 1} is subset of Ks(r) for all O.
We now simplify Ka(r) by using the distribution of | where pa, follows.
f J pr(ō)dō -rr[|=1|0 S 19] where ~ pa
= v)
22

---

Published in Transactions on Machine Learning Research (04/2023)
In the above, 3 is the CDF of the distribution of | when pg. Setting v)(r2) 2 0.5 gives the following condition
Dz(x)= B(x,r) E Js(a) such that 2 (0.5
2. V V (0.5) e Jo(a)
Our final subset Ks 3) for E L; Ds(x) 1} denotes the set of points in I which are at least Ta, Ta + V (0.5) away from the boundary of I, In other words, Ks B) S I, is conttccnno of I,.
We recall that is such that the subset 1, has inradius wh,r- By the definition inradius, this means that there exists ball B wh,7) for some & E I, such that ( wh,z) S I,. Hence, the contraction of I, by Ta,8, i.e., Ks( B), is a superset of the contraction of B(ã, wh,r) by Ta,8s
Biē, Wh.t Ta.8) S ()(
Risk Upper Bound Recall that ~ px, Y ~ py are the data and the response variables respectively. Let be the random variable obtained from the smoothed, noise-angmented classifier as Smooth (+ Pa))()) Let T be the random variable obtained from the original classificr (X)) We know that the risk of the original classifier is given by
R(v(h)) (r))) # + p(T=TTTTT---- 1,Y 0) + P(T 0, Y 1).
Define I+ = (z: (z) 1} and I- = fx: (h)(() = 0} as the regions of the input space classified as and 0 respectively by the basc classifier. With this definition, we can rewrite the base risk as
R(v(h)) p(X e e P
Let KC C I+ be any subset classified as 1 by the smoothed classifier, i.e.,
(z)) K C fx: Smooths(b(h pp)))))))))))))))))))))))))))))) = n
Similarly,
K- C (x: Smooth pa)) 03 nz
We will think of the sets KC as shrunk versions of I, and where the smoothed classifier predicts the correct label. Specifically, we will let KC be the union of all the contractions Ks(a, 3) of the positive partitions of (h), where K5 B) was obtained carlier. Similarly, we will let XC be the union of the contractions of all the negative partitions of (h). This ensures that
K. d x X' x Ks, X
where we define IC as the rest of the space.
The risk of the smoothed classifier
where the first term decomposes into
= 0,
23

---

Published in Transactions on Machine Learning Research (04/2023)
noting that p(S 1,Y = - X X
implics S = 0. Similarly, the second term decomposes
-
Combining, we have
{(Smooths(*(h pp))) = p(Y = 0, - p 1, = 0, 0,
p(v = 0, + =1, +
The above expression says that the errors made by the smoothed classifier can be decomposed into the errors made in the regions K, and the error everywhere else K. Now, since K SI+,K K CI, we have
R(Smooths(V(h pa))) S p(Y 0, + 1, X +
- +(s+)
R(Smooths(W((h Pa))) & ((v(h)) E K) = (h) S Spee
As 8) (0 for any a, B 2 have p(X RR,g) 2 p(X Ro,o), showing that the upper-bound (*) decreases as increases any fixed B.
Finally, notice that the upper-bound (*) becomes tight at a =3- = K = It, =I I K, f, as then R(Smootho (v<(h * Po)) = R()(h)) and p(X e K) =
Finally, we can use in (*) to obtain
Aa,8 S 1- Px w - rr.
for any choice of the points {Øx} such that ah is such that Be, (tt wh S IK.T.
Fhe quantities V/51 (
0.5 and V (0.5) must be non-ncgative for the above balls to be well defined. 0.52r
This in turn implies that w - - 2 0 for all k. i.., the inradius of each partition is at least large the amount of shrinkage that partition goes through. These requirements are not additional constraints on h, but rather a property of the proof technique: whenever the inradius is too small, the partition vanishes from the upper bound. To capture this subtlcty, we can write the upper bound as
D 1 px (Be, (whir rr,,)+)),
where (c)+ denotes the positive part of c.
F Proof of Theorem 4.3
Theorem 4.3. There exist nice distributions Pa: Pa, family H2 with low interference distance ÇH2 and dota-distributions px, such that for all h E H2 we have A0,30 (h) >> An, (h) for some >> 0, 30 > 0.
Proof. We will firstly derive general conditions on E H2 and ag, Bu > 0 such that Aap. (h) < Ao, (h). We will then show that the H2 as restricted by these conditions not empty, by providing a particular h that satisfies these conditions. We will assume that the domain is bounded.
Lower-Bound on 3. We first of all require 3 to be large enough such that (b((()) Pa, pa.) (z) 0 for all x X. This is to ensure that without noise-aggmentation. the smoothed classifier predicts 0 everywhere. In other words, Vx E X' we require
[e v()((x (t)dt 0.5.
(22)
Condition (22) implies Bo 2 B for some 3, will become clear later in (26).
24

---

Published in Transactions on Machine Learning Research (04/2023)
Acceptable Range of a. Secondly, require wh Pao (x) over set X, where think of the size of X' as being close to the size of X' in the sense px (z E X X) S for small 6. This subset X denotes the part of the input where the noise-trained classifier predicts 1. In other words, for all æ E X, we require
JeN h1x - P) (t)dt 2 0.5.
(23)
Condition (23) implies lower and upper bounds a 2 ag 2 at as will become clear later in (27), (28).
Upper-Bound on B. Thirdly, we require (/ Pao) p.o (2)) = 1 for all x E &, where we again think of the size of & being close to the size of X, i.e, px (x) S e. This ensures that the smoothed classifier predicts 1 in almost all of the region where the noise-trained classifier predicts 1. In other words, for all x E X, we require
JIe shh * poo)(E t)ps. (f)dt 2 0.5.
(24)
Condition (24) implies an upper bound 3 2 So, as will become clear in (29).
Small Interference-Distanee. Finally, we require that the data-distiibution places more mass on the label 1, Le.
1 +e. + P\Y >
(25)
Condition (25) ensures that h has small upper-interference distance. Informally, this is expected: (25) says that the positive partitions of v(h) need to have certain mass under p, and the domain is bounded, so the partitions cannot be far apart. Formally, this will become clear in (30) when we demonstrate a particular example h where the above constraints are satisfied. Before that, we will prove that the above conditions are sufficient to guarantce Aa.. (h) < 40,5, (h).
Let Sa.8 be the random variable Smooth (+<( * (X)) X ~ px; and simplify 40,% as
Ao, (h) = p(Y # S0,50)
Using (22)
= p(Y + #0)
> P( = =0)+ +
Using (25)
2 p(Y = =0, ExER +
2 p(Y 11,X E 8) + +x (X 8) + xx
p(Y + Sao X E 8) + p(X E X 18)
Using (24)
p(Y # San X E x) + p(Y + Sao. X X 2)
Amo.8o (h).
We will consider the one- dinensiooinll example h described in Section 4.2, and show that it satisfies the above constraints. The domain can be taken to be = [-0.25, 0.25). h is defined by specifying c, C2 C3 C4. We can take C1 = -0.25, 02 = -0.25 + w, c4 = 0.25, C3 = 0.25 - w, for some w I 0.25. Here w is the inradius of the positive partitions of h, similar to what we saw in Theorem 4.2. Additionally, the upper interference distance { is the distance between the positive partitions, i.e., (0.25 w) - (-0.25 + w) 0.5 2w. The smoothing distribution p is uniform in ball, po Unif([ 0/2, 0/2)), and the marginal distribution px is uniform over [-0.25, 0.25].
The lower bound on (22) then requires for all x E X, we have S (z)(xx)) (1/3)dt 0.5. stronger condition is (1/8) ( (t)(tt)t s 0.5 which implics lower bound on B as
(2w) 0.5 = B2 4ws
(26)
25

---

Published in Transactions on Machine Learning Research (04/2023)
The acceptable range of a is defined by (23). We take X' X (hence 0). For [-0.25 + w.2.5 w], (23) gives
2- -0.25 - (1/a) & 0.5 = 2 4(0.25 w).
(27)
For 1.0.25.-0.25 + w| U [0.25 w. 0.255) a stronger condition to (23) gives
w(1/a) 0.5 a 2w.
(28)
The upper bound on 8 is given by (24). As = 0, we have & = X, which gives
(0.5) (1/B) 2 0.5 = 3 1..
(29)
Finally, Eq. (25) gives condition
(ww)
0.5 >
= <> 0.125.
(30)
The proof is now complete with the observation that = 0.23, a 0.1, 0.93 satisfies these constraints, showing that h E H2 as (h) > (0.1.0.33hh).
Note that the condition (30) on w implied an upper-bound on the interference distance 5. as [ = 0.5 2w. This shows that when satisfies the condition (25), has a low interference distance.
G Accommodating Errors in Learning Bayes Classifiers.
While obtaining a pandomized-smootine classifier in a real learning scenario, we might deviate from the Bayes classifier in any stage of the process. Specifically, we have stages: (1) Learn a classifier on the noisy data (X,, Y) and (2) Smooth the resultant classifier using randomized smoothing.
In Theorem 4.1, assumed that i.c. s0hh+ Pa). This assumption can be relaxed while maintaining the same general proof technique, albeit by paying with further slack in the obtained bounds due to the inexactness of the learned classifier. We now sketch a modification of the argument in Appendix D that allows a bounded deviation from the Bayes classifier.
able to exactly learn the Bayes Classifier for (X,, Y) in stage (1),
We start with the first column of Figure 1, i.e. (h), and train the classifier data perturbed by noise Pa- In the idcal case sketched above, this leads precisely to the second column, i.c., 1/hh * Pa). In the non-ideal scenario, assume that we obtain classifier in stage (1) after training on (Xa, Y), such that for all æ, have 19(z) h * Pa (z) S 77. In other words, the maximun eтror in the trained classifier compared to the actual conditional no larger than n. For clarity, we still maintain that stage (2) is done exactly, i.e. that classifier.
given (g)) we are able to obtain Smooth (vb())))((())) exactly as our final randomized-smmode
As result, we are interested in analysing the modified excess risk
Lg. h) (SSSmotths R())h))
(31)
for all (g. h) such that l Polloo < Eq. (31) captures the increase in the benign risk due to randomized smoothing an imperfectly learned classifier on the noise-augmented data. Additionally, we define
A A
max
a h),
(32)
(a: ||s
Sn)
to be the maximum excess risk when using an imperfectly learned g. Similarly, we define
A A7 (h) (a: hepa
min
A h),
(33)
Sn)
be the minimum excess risk when using an imperfectly learned g. We now have the following modified version of Theorem 4.1.
26

---

Published in Transactions on Machine Learning Research (04/2023)
Theorem G.1. For nice noise distributions Pa Uni a)) and р3 (0, there crists H1 with interference distance Sn.' such that for all h E Hi we have 0, (h) - (h), and 0,g A, for all smoothing parameters a. 3 such that Srz > 2 max(a, 3), and n < 0.5.
Proof. Similar to Theorem 4.1, let I ....... Is be spheres such that I, Bžg (cg, r) for some positive radius >> 0. Define h(2) = 0.5 + whenever x E I U 12 ....UU Tb and 0 otherwise, for some 0 I 0.5.
Large Interference Distance We assume that CA >> 2 max(a, 8), where note the additional factor 2 in the required lower bound as compared to Theorem 4.1. This stricter condition will become useful when we deal with errors in learning the bayes classifier.
a Shrinkage Recall that we earlier analyzed the region 1j.- = fi E 1y: * pa(x) 2 0.53. In this new non-ideal setting, it now useful to consider the regions 1, defined as
J = (sr E Jaa: h (a(x) 2 0.5 + 7)-
(34)
The inaccurate classifier y would have (1)(2)) for all U as g(x) (a()) 2 0.5.
Similarly, the sets {1j_"} can be defined as the set of maximal simply connected regions forming a partition of {ar: h * Pa()) 2 0.5 - n). There a natural correspondence between 1 J and Ija. which will become clear once obtain the explicit forms of these sets. Note that (x) = 0 for all U,dra' g(r) S h (x())) ( - 0.5.
We can characterize r explicitly as the set of all x satisfying
(0.5 (0.5+))0a (x - cc,) 2 0.5 n -1--- S Aa.r
0.5 (0.5+1 1]
def
rra
(35)
0.5 0.5
obtaining the shrunk ball rta = B(c,,r+*)) Similarly, we see that I J is the ball J,a = B(cj,r=") with radius
def Aa.r 0.5 0.5
0.5 0.5-7
Handling Inaccuracy in 9 We now perform randomized smoothing on this classifier 9, and obtain ((((g)) * ps)).
For 1y we have that
Smooths = =/ v(o)(t)ps(> - t)dt + J 1,22
(())(t)p(( t)dt f JNNT2 *())(t)pa(r t)dt.
(36)
We will now split the domain of the last integral (36) as
x X 5.2 = (U:+s u (X(
where note that the integral over the second set in the union, i.e, Securr ((g)(t)ss( t)dt is zero, by the observation above that (t) = for all t & Uy This leaves us with the integral over the first set, which we will now show to be as well.
For the first set, we want to see whether there is any point 17 + j such that (t) and pa(x t) 0. This can happen only when g(t) 2 0.5 and ||x +ll2 S 3. Now consider the triangle formed by the points {2,4, C, and apply the reverse triangle inequality to gel
||| c:ll2 2 ||e. xlla
||x 2||2 2 2 max 8)+ +r B ar
27

---

Published in Transactions on Machine Learning Research (04/2023)
where the interference distance condition was used for ||e; - z|| > 2 max B). But now we know that ((1) - (t) I 1 <, 0.5, and that h (t) = 0 for any /. at distance more than a + distance away from all the centers This implies that g(t) < 0.5, which further implies that (t) = 0. Hence, the integral over the first set (Ue4s- is O.
The first term in (36) simply
f 1
(()(())s( - t)dt = J,-.. 1 ps(# t)dt = Φ2 - cj. rTa)).
2,n
For the second term in (36), can only produce upper and lower bounds, as
5
((9)(t)ps( t)dt - ppssx t)dt
172
Combining, we have
Φ rg, < Smooth)({(0))(e) Fz(# r..r"")
(37)
where the lower-bound occurs when g(x) takes the lowest possible value for all 1,00 V45.0 Similarly, the upper-bound occurs when g(x) takes the highest possible value in the same region.
3 Shrinkkaee Compared Theorem 4.1, we now only have an inequality (37) for the smoothed classifier any point x. As a result, we cannot determine the positive regions IJ.0,8 = (x E Iy: (m))th)(((g))())) 2 0.5} exactly. Instead, the following set inclusions follow from (37):
Be, (c, Aa.tt (0.5)) S IJ S (e.lc,Aar.=
Bounding Risk Similar Theorem 4.1, we can now compute the risk of the smoothed classifier as
R(Smooth pa)))
(38)
(Wooths(@(( pz) (xx())))x(())de / Smooth * px) (x)dz.
(39)
Let = 11 Us are the positive regions for the base classifier (hh), and let It.,% = Uy (cj, Aa.r!") and I Be Aa.rg (0.5)) be the upper and lower bounds the positive regions of the smoothed classifier Smooth (V:()) Le., Ia,g U, U,
A A Aa.r (0.5) denote the largest possible radius of the positive partitions after smoothing. We now have two cases, To,B.n S r (Case A), or r < <T.a,. (Case B). When 0, the positive partitions always shrink (as we saw in Thcorem 3.1), and we are in Case A. As we increase beyond a certain 7 2 7oo we go into Case B, where the positive partitions have potentially dilated after smoothing. We handle both cases separately.
Let To.3.n
Case A Define S II \ Ity to be the subset of I="l \ It where (v(g))() = 1. For the first integral in (39), we obtain
0,
x E Itz x E S # (I Itt) S
0,
(Smooths(((())ee) 1/p(1/=)
0.5 0.5+0
0.5 +T,
x Z I x E X'
0,
28

---

Published in Transactions on Machine Learning Research (04/2023)
For the second integral in (39), obtain
0.5 T
I
0.5 T
EEZ S
0,
(I a.
Ta.g)
0,
I
0,
E X I
Substituting into the integrals, we obtain
((Smooths(((g)) = (0.5 - -)xx US) +0.5 r)px (1ET.3 \ (5) 2,3))
which is minimized when 5 is as large possible, and viro-versa. This gives the risk bounds
(0.5 - (0xx))xx(__331 (0.5 (0.5+) (05+))) I. & R (0.5 7)px (T..)) + (0.5 + 7) (I Ix.3)
(0.5 - 2Tpx -Tppxx R(((h)) S ha - + 2Tpx 2 -R((() (40)
(h) (b)
(h)
As a increases for a fixed B,n.T, T, both the upper and lower bounds in (40) increase, following the same argument as Theorem 4.1.
Case B Define Ti S I I to be the subset of T to be the subset of I I where
I where ( 1. Define T- CIVI 1. For the first integral in (39), we obtain
0,
x I
0,
T2
-mmooth(((())(=)>1pp))p
0.5 0.5
E (I \ I2t77) T2
0,
X I
For the second integral in (39), we obtain
0.5 T
x E It1
a.
0.5 T,
T2
0,
I I (I I \ \T
(M0) =
1,
TET;
0,
E (I \ Z) Ti
0,
x x X' I
Again substituting into the integrals, we obtain ((Smooth)((())) (0.5 + T)px((I \T2 + -0.5 (4.5-))px(2) (Tz) + Px + (0.5 - -)p (I
which is minimized when T, is emply and T2 is as large as possible, and maximized when Tj is as large as possible and T3 is empty. This gives the risk bounds
(0.5 - (T) & (())) S +T5++)xx(0 2Txx (I 2. + px \2)
(0.5- T)Px (I) - R(v(h)) & Aa.o(g, h) s (0.5 ()p 2Tpx (It.) + Px (I II) - R((((h)) (41)
A7 (k)) (h)
(h,)(h)
Note that the lower bound for the risk in (41) is equal to the Bayes Error this is expected as in the best scenario, the classifier after smoothing can be idential to the original classifier in Case B. For the upper bound, we observe that as we increase a at a fixed B, 8,n,7 t, the set I shrinks, which causes the upper bound to increase.
We have hence shown that in both Case A and Case B, the risk of the smoothed classifier increases as is increased from O, modulo approximations due to errors in learning the bayes classifier.
29

---

Published in Transactions on Machine Learning Research (04/2023)
Upper Bound for General g We show here that via simple application of Theorem 4.2, we upper bound (g, h) for general g, h:
Aa.(g, (a, + px ((h pa))+)))(X)..))) + g(X)
(42)
To show (42), we let Sg denote the random variable ( and S.. denote the random variable Smootha (v) (X). We use the following simple sequence of upper-bounds:
h) = H(Smooths(((())) R(v(h))
= =p(S, # Y) - R(vi(h))
= p(S0 & SY = =5g) - R((b())) + r(5 # SY + Sg)
Sp(Sn +Y) - [(v(h)) + p( (Sh+5p, +5))
(h) pSS + S.g)
S ( p((h pa) + 9(X))
30


Reviews:
[{"review_id": "6peDfiYuZD", "reviewer": "Reviewer_9yXc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The manuscript is overall well-organized and clearly written - for example, I appreciate Section 3 of the manuscript that effectively summarizes the main results of the paper.\n- The focus of the study, i.e., the effect of noise-augmented training in randomized smoothing, has been sparse in the literature, and the manuscript presents a meaningful theory on this.\n- The manuscript also contains empirical supports besides of its interesting theory.\n\nWeaknesses\n\n- To my knowledge, the “shrinking” effect of randomized smoothing (in its decision boundary) was previously explored theoretically by Mohapatra et al. (2021), which is not mentioned in the manuscript. I think the manuscript should include a discussion comparing its theoretical novelty upon the work.\n- Although I feel the theory presented in the paper is quite clear, but its practical implication seems relatively weak given the lack of discussion about when the theory holds in the real-world. For example, as empirically shown in the paper, it seems the “no-need-noise-augmentation” theorem does not actually hold in practical scenarios such as MNIST and CIFAR-10. The theory may provide useful insight on the properties of smoothed classifiers, but the week connection to practice can decrease its significance.\n- (minor) Some lines are somewhat unclear to me:\n    - p.3: “this implies a minimal strength for the randomized smoothing parameter, say $\\beta^*$” - why one requires a minimal parameter given $\\epsilon^*$? How does $\\beta^*$ actually defined?\n    - Theorem 3.3: What denotes $H$ in $\\zeta_{H}$, perhaps a typo?\n    - Figure 4: “The line is dashed if … for any $\\alpha > 0$, …” - shouldn’t be that “there exist $\\alpha$ …” instead?\n\n[Mohapatra et al., 2021] Hidden Cost of Randomized Smoothing, AISTATS 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper theoretically investigates the effect of noise-augmented training in randomized smoothing, which has been a practice to obtain a good smoothed classifier. In particular, it focuses on the change in the optimal benign risk of smoothed classifiers given a (training) noise strength $\\alpha$. It proves that noise-augmented training with strength $\\alpha$ can be harmful in the benign risk of smoothed classifier for certain data distributions. The paper further characterizes such distributions in terms of “interference distance”, and shows that the favorability of noise-augmented training is partially corresponded to the small interference distance of data distribution. Experimental results demonstrate that one can indeed construct a dataset that noise-augmented training harms the accuracy of smoothed classifiers, while it is also remarked that more realistic data such as MNIST and CIFAR-10 does not suffer from this phenomenon perhaps due to their small enough interference distance. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- A more discussion or (either theoretical or empirical) justification on why real-world data (such as MNIST and CIFAR-10 tested in the paper) tends to get small enough interference distance would help reader to better understand the practical aspects of the theory.\n- A discussion compared to [Mohapatra et al., 2021] especially in terms of theoretical novelties would improve clarity.", "broader_impact_concerns": "None that I am aware of. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Af9XFMTeRg", "reviewer": "Reviewer_YbSr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n -  The paper makes a thorough theoretical treatment of a question (whether noise augmented training is necessary for RS) that has not received theoretical attention in the literature.  \n - Interestingly, the authors construct situations where noise-augmented training is harmful to the natural accuracy of the smoothed classifier, which is an unintuitive finding.\n\n\nWeaknesses: \n - As I understand them, Theorems 3.1 and Theorem 3.3 show that _there exist_ distributions with large / small interference distances, such that training on them is not beneficial / beneficial for the natural accuracy of the smoothed classifier.  But this is weaker than showing that interference distance is a complete characterization of when noise-augmented training helps or hurts.\n\n- The specific high-dimensional structure of image data seems different than the synthetic distributions studied in the paper.  In particular, the necessity of Gaussian data augmentation for CIFAR RS strikes me as an OOD accuracy problem - if the base classifier has never seen a noisy image, it won't know how to deal with it at smoothing time.  Could the authors comment? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In randomized smoothing, the base classifier is usually trained on images augmented with Gaussian noise of the same magnitude as is applied later during smoothing.  This manuscript aims to understand the purpose of this \"noise-augmented training.\"  The authors introduce a concept called \"interference distance\" which is intended to capture whether noise-augmented training is helpful or not for the natural accuracy of the smoothed classifier.  On datasets with \"low interference distance,\" like natural image data, noise-augmented training is helpful.  But there do exist datasets with \"high interference distance\" where noise-augmented training has no benefit and can be harmful.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- randomized smoothing was proposed as a certified defense by Lecuyer et al (2019), not Cohen et al (2019) - this paper should be cited on page 1\n\n - typo in first paragraph of section 4 - you mean the bottom panel", "broader_impact_concerns": "no concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ytRyNbSZeW", "reviewer": "Reviewer_UVsX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**Novel problem.**  I am not aware of another paper that looks at the role of NA in RS.  Indeed, NA is widely used for RS, but it isn't clear how one should use NA and why it results in stronger randomized classifiers.  The authors attempt to demystify this phenomenon from a theoretical perspective.  And their theory does lead to (albeit somewhat limited) insights on the practice of NA for RS.\n\n### Weaknesses\n\n**Informal presentation.**  I think that an informal statement of theoretical results can be a useful way of presenting results like this.  However, I don't believe that the presentation is effective here.  To improve this, I would start Section 3 by telling the reader that the results are going to be informally stated.  Then, I would try to make the statements of the results informal.  Right now, they read as half-way between formal and informal.  It's challenging to interpret the theorems in Section 3 without knowing what the ID is.  In Theorem 3.2, at this level of detail, is this not trivial, in the sense that $G_{\\alpha,\\beta}$ could simply be taken to be $\\Delta_{\\alpha,\\beta}(h)$?  $\\Delta$ seems to be monotonic in both of these parameters, right?\n\n**The \"simple\" example.**  I didn't understand the 1-D example.  It is relatively complicated.  It might help to pick arbitrary constants for $c_1$-$c_4$, hence sacrificing generality for intuitiveness.  Figure 2 needs to be explained in more detail.  You may want to walk the reader through this diagram panel by panel, because as written, it was rather confusing.  \n\n**Experiments.**  There is a strange argument at the end of the experiments.  The authors say that \n\n> \"The first observation that we make from the MNIST and CIFAR-10 plots in Figure 5 is that a non-zero data-augmentation is always beneficial, i.e., $\\alpha^\\star > 0$. This suggests that real data distributions lie in the small interference distance regime.\"\n\nThe argument seems to be that since NA is useful, the distribution of data must be in the small ID regime.  However, the results in the paper (i.e., Theorems 3.3 and 4.3) seem to say that small ID implies that NA is useful.  If we let A denote \"the distribution has small ID\" and we let B denote \"NA is useful\", this can be simplified as follows: The theory says that $A \\implies B$, whereas the experiments say that $B\\implies A$.  Clearly, these two are not equivalent.  Perhaps the authors can clarify, because this conflict undermines the main results of the paper.\n\n**Grammatical problems.**  Here's a summary of some of the grammatical issues I found in this paper:\n* Page 1: \"One of the central questions...\" -- the authors do not state an actual question here.\n* Page 2: What is meant by \"out of the box?\"\n* Page 3: \"...for a pair of input sample and its label\" -- this is awkwardly worded\n* Page 3: \"rendered astray\" -- this wording doesn't make sense.  It would improve readability to use more precise language\n* Page 4: \"relaxed the relax this assumption\" -- this seems wrong, consider revising\n* Page 4: \"Our first result consists in demonstrating...\" -- this is not correct grammar\n \n**Notational problems.**\n* The symbol $h$ is used in different ways, and they seem to contradict one another.  On page 2, the authors say that $h:\\mathcal{X}\\to[0,1]$, meaning that $h(x)$ is a number between 0 and 1.  On page 5, $\\mathcal{H}_1$ is defined to be a set of distributions, and the authors say that $h\\in\\mathcal{H}_1$.  So is $h$ a distribution now?  Then, in Section 4, the authors say \"the conditional distribution $h(x)$.  $h(x)$ is a number -- how can it be a conditional distribution?\n\nAlso, in (2), $\\Delta_{\\alpha,\\beta}$ doesn't have an argument.  In Theorem 3.1, it takes $h$ as an argument.  Which one is correct?\n\n**Miscellaneous.**\n* Page 2: \"Why is noise-augmented training necessary...\" Is it **necessary** for good performance?  It seems to be sufficient, but it's not clear that it is necessary.\n* Page 2: \"We show that this notion of interference distance captures the trade-offs in randomized smoothing\" -- are you asserting that it captures **every possible** trade-off?  Might consider rephrasing.\n* Page 2: \"...set of samples, typically identically and independently distributed...\" -- what is meant by \"typically?\"  In practice, this does not always hold.  Take MNIST for example.  Is it even possible to determine whether the MNIST digits are IID?  \n* Page 3: \"...as well as the variance of the smoothing distribution $\\beta$...\" -- $\\beta$ is the standard deviation, not the variance.\n* Page 5: \"...have a very small effect on each other.\" -- I'm not sure how we can see this from the figure.\n* Page 6: The authors should define \"simply connected.\"  Also, the intervals $I$ should be formally defined (with equations).  The definitions of **nice** noise distributions should be moved into the main text.\n* Page \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the role of noise augmentation (NA) when training classifiers that are later smoothed during randomized smoothing (RS).  The main idea is to characterize regimes in which NA help/hurt the benign and smoothed performance of a given classifier.  The authors find that the degree to which NA helps depends on a particular metric on the Bayes optimal classifier, which they refer to as the interference distance (ID).  Several experiments are performed to demonstrate the interplay between the ID and the parameters of the distributions used for NA and RS.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Fixing the grammatical and notational problems outlined above.\n2. Having a clearer take home message that is supported **clearly** by the experiments (see the \"Weaknesses\" section)\n3. Resolving the \"Miscellaneous\" comments above.\n4. Defining the ID more clearly.\n5. If you're going to use the informal presentation style, make sure the results are stated so that a reader can understand them informally.  I.e., don't include constants or quantities that are completely undefined or under-defined.\n6. Move most of the conclusion to the appendix to make room for additional definitions.\n7. Add more details to Figures 1 and 2, both of which look great, but are not explained clearly enough.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper theoretically investigates the effect of noise-augmented training in randomized smoothing, which has been a practice to obtain a good smoothed classifier. The authors introduce a concept called "interference distance" which is intended to capture whether noise-augmented training is helpful or not for the natural accuracy of the smoothed classifier. Experimental results demonstrate that one can indeed construct a dataset that noise-augmented training harms the accuracy of smoothed classifiers, while it is also remarked that more realistic data such as MNIST and CIFAR-10 does not suffer from this phenomenon.

All reviewers suggests "Accept" or "Leaning Accept" as the authors' claims are technically correct and would be of interest for some TMLR audience. AC agrees with this and also recommend acceptance. However, AE and some reviewers think that the paper would be much stronger if the experimental evidence was more compelling to practitioners.
Decision: Accept (poster)