Intriguing Properties of Input-dependent Randomized Smoothing
Authors: Peter Súkeník
Aleksei Kuvshinov
Stephan Günnemann
Venue: ICLR 2022 Submitted (2022)
Keywords: randomized smoothing
certifiable robustness
deep learning
machine learning

Abstract: Randomized smoothing is currently considered the state-of-the-art method to obtain certifiably robust classifiers. Despite its remarkable performance, the method is associated with various serious problems such as ``certified accuracy waterfalls'', certification vs.\ accuracy trade-off, or even fairness issues. Input-dependent smoothing approaches have been proposed to overcome these flaws. However, we demonstrate that these methods lack formal guarantees and so the resulting certificates are not justified. We show that the input-dependent smoothing, in general, suffers from the curse of dimensionality, forcing the variance function to have low semi-elasticity. On the other hand, we provide a theoretical and practical framework that enables the usage of input-dependent smoothing even in the presence of the curse of dimensionality, under strict restrictions. We present one concrete design of the smoothing variance and test it on CIFAR10 and MNIST. Our design solves some of the problems of classical smoothing and is formally underlined, yet further improvement of the design is still necessary.

Under review as a conference paper at ICLR 2022
INTRIGUING PROPERTIES OF
RANDOMIZED SMOOTHING
Anonymous authors Paper under double-blind review
ABSTRACT
Randomized smoothing is currently considered the state-of-the-art method to ob- tain certifiably robust classifiers. Despite its remarkable performance, the method is associated with various serious problems such as "certified accuracy water- falls", certification vs. accuracy trade-off, or even fairness issues. Input-dependent smoothing approaches have been proposed with intention of overcoming these flaws. However, we demonstrate that these methods lack formal guarantees and so the resulting certificates are not justified. We show that the imput-depende smoothing, in general, suffers from the curse of dimensionality, foreing the vari- ance function to have low semi-elasticity. On the other hand, we provide theoret- ical and practical framework that enables the usage of input-dependent smoothing even in the presence of the curse of dimensionality, under strict restrictions. We present one concrete design the smoothing variance and test on CIFAR 10 and MNIST. Our design solves some of the problems of classical smoothing and is formally underlined, yet further improvement of the design is still necessary.
INTRODUCTION
Deep neural networks one of the dominating recently used machine learning methods. They achieve state-of-the-ar performance in variety of applications like computer vision, natural lan- guage processing, and many others. The key property that makes neural networks so powerful is their expressivity (Gühring et al., 2020). However, as prize, they possess weakness a vulnera- bility against adversarial attacks (Szegedy et al. 2013 Biggio et al. 2013). The adversarial attack on sample is a point x' such that the distance d( is small, yet the model f's predictions on x and x' differ. Such examples are often easy to construct, for example by optimizing for a change in prediction fz) (Biggio et al. 2013). Even worse, these attacks are present even if the model's prediction on & is unequivocal.
This property is highly undesirable because in several sensitive applications, misclassifying sam- ple just because it does not follow the natural distribution might lead to serious and harmful conse- quences. A well-known example would be sticker placed on traffic sign, which could possibly confuse the self-driving car and cause an accident (Eykholt et al., 2018). To prevent this behaviour, the robustness of classifiers against adversarial examples has begun be strongly discussed topic. Though many methods claim to provide robust classifiers, just some of them are certifiably robust, i.e. the robustness is mathematically guaranteed. The certifiability turns out to be essential since more sophisticated attacks can break empirical defenses (Carlini & Wagner 2017
Currently, the dominating method to achieve the certifiable robustness is randomized smoothing (RS). This clever idea to get rid of adversarial examples using randomization of input was introduced by [Lecuyer et al. (2019) and Li et al. (2019) and fully formalized and improved in Cohen et al. (2019). Let f be classifier classifying inputs
R as one of the classes C' E C. Assume now a random deviation E o2 The smoothed classifier g. made of f. is defined as: g(x) arg max; (Pf(( + C), for C C. In other words, the smoothed classifier classifies class that has the highest probability under the sampling of f(x c). Consequently, an adversarial attack x' on ff is less dangerous for g. because g does not look directly at z' but rather at its whole neighborhood, in a weighted manner. This way, we can get rid of local artifacts that f possesses thus the name "smoothing". It turns out, that g enjoys strong robustness properties against attacks

---

Under review as a conference paper at ICLR 2022
bounded by specifically computed lg-norm threshold, especially if f is trained under a Gaussian noise augmentation (Cohen et al. 2019).
Unfortunately, since the introduction of the RS, several serious problems were reported to be con- nected to the technique. [Cohen et al. (2019) mention two of them. First is the usage of lower confidence bounds to estimate the leading class's probability. With a high probability, this leads to smaller reported certified radiuses in comparison with the true ones. Moreover, it yields a theoret- ical threshold, which upper-bounds the maximal possible certified radius and causes the "certified accuracy waterfalls", significantly decreasing the certified accuracy. This problem is particularly pronounced for small levels of the used smoothing variance o², which motivates to use larger vari- ance. Second, RS possesses robustness vs. accuracy trade-off problem. The bigger a we use as the smoothing variance, the smaller clean accuracy will the smoothed classifier have. This motivates to use rather smaller levels of a. Third, as pointed out by Mohapatra et al. (020aa), RS smoothens the decision boundary of f in such way, that bounded or convex regions begin to shrink as a increases, while the unbounded and anti-convex regions expand. This, as the authors empirically demonstrate, creates a disbalance in class-wise accuracies of g and causes serious fairness issues. Therefore, again, the smaller values of are more preferable. See Appendix A for detailed discussion.
Clearly, the usage of a global, constant a is suboptimal. For the samples close to the decision bound- ary, we want to use small o, so that f and g have similar decision boundaries and the expressivity of f is not lost (where not necessary). On the other hand, far from the decision boundary of f. where the probability of the dominant class is close to 1, need bigger a avoid the severe under-certification (see Appendix (A). Together, using a non-constant ar (zx) rather than constant o, a suitable smoothing variance could be used to achieve optimal robustness. Yet there are some works introducing this concept (see Appendix C. most of them lack mathematical reasoning about the correctness of their method, which, as we show, turns out to be critical.
To support this argumentation, we present a toy example. We train a network on a 2D dataset of a circular shape with the classes being two complementary sectors, where one is of a very small angle. In Figure D we show the difference between constant and input-dependent σ. Using non-constant (1) defined in Equation I we obtain an improvement both in terms of the certified radiuses as well as clean accuracy. For more details see Appendix A
Visuelization of function
Decision boundary of smoothed classeler or
Toy dataseet comparieoo
5.0
soand dlsa
clas
1.0
0.8
constant
iosl-dupender1
0.5
03.9
0.0
-2.
0.0
0.44
-5.0
-0.5
-7.5
-1.0
00
3.0 15
1.5
Figure 1: Motivating toy experiment. The constant a 0.6 and the input-dependent (x) equal in average to the constant a are used. Left: Dataset and the variance function depicted as circles with the radius equal (xx and centers the data points. Middle: Zoomed in part of the dataset and decision boundaries of the smoothed classifiers with constant a (red) and input-dependent a (x) (green). Note that we recover part of the misclassified data points by using more appropriate smoothing strength close to the decision boundary. Right: Certified accuracy plot. The waterfall effect vanishes since the points far from the decision boundary are certified with a correspondingly large a (zz)
The main contributions of this work are fourfold. First, we generalize the methodology of Cohen et al. (2019)'s work for the case of input-dependent RS (IDRS), obtaining useful and important insights about how to use the Neyman-Pearson lemma in this, general, case. Second and most importantly, we show that the IDRS suffers from the curse of dimensionality in the sense that the semi semi-elastichn elasticct coefficient r of (z) (that is (za)) (o (x1)) S ri|zu- ll Vig, 21 E I R in nigh-dimensional setting is restricted to be very small. This means, that even if we wanted to vary the a (αx) significantly with varying ø, we can't. The maximal reasonable speed of change of (x) turns out to be almost too small to handle, especially in high dimensions. Third, in contrast,
2

---

Under review as a conference paper at ICLR 2022
also study the conditions on (²x) under which it is applicable in high-dimensional regime and prepare a theoretical framework necessary to build an efficient certification algorithm. We are the first to do so for (z)) functions, which are not locally constant (as in Wang et al. (2021)). Finally, provide a concrete design of the a (x) function and test it extensively and compare it to the classical RS on the CIFAR10 and MNIST datasets. We discuss to what extent the method treats the issues mentioned above.
2 INPUT-DEPENDENT RS AND THE CURSE OF DIMENSIONALITY
Let C be the set of classes, f IRN - C a classifier (reffered to as the base classifier), o R - R non-negative function and P(C) set of distributions over C. Then call G RN - P(C) the smoothed class probability predictor, if ()(4)c
C) where and gf TN C is called smoothed classifier if (x) arg maxc (z()) for C' C. We will omit the subscript f in 9j often, since it is usually clear from the context, to which base classifier the 9 corresponds. Furthermore, let A := g(x) refer to the most likely class under the random variable [x, o²1)), while B denote the second most likely class. Define Pa = and PB Gf(z), as the respective probabilities. It important to note that in practice, it impossible to estimate PA and pa precisely. Instead, PA is estimated as a lower confidence bound (LCB) of the relative occurence of class A in f's predictions given certain number of Monte- Carlo samples n and a confidence level a and the estimate is denoted as PA- We use the exact Clopper-Peane Pearson interval for estimation of the LCB. Similarly for PB. We work with In-nosms denoted as ||-]|-
P( +
(
Gy(z)
First of all, we summarize the main steps the derivation of certified radius using any method that relies on a use of Neyman-Pearson lemma.
1. For a potential adversary x' specify the worst-case classifier f³ such that IP (f (VV("V o A) PA, while (N(z', B) is maximized.
2. Express the probability Gy-(z') as function depending on x'.
3. Determine the conditions on x' (possibly related to || - x'I)) for which this probability is
< 0.5. From these condtions, derive the certified radius.
Cohen et al. (2019) proceeded in this way to obtain tight certified radius R / ( (pa)(pp)) 4 (P()) Unfortunately, their result is not directly applicable to the input-dependent case. The constant a simplifies the derivation of f that turns out to be a linear classifier. This is not the case for non-constant (x) anymore. Therefore,
need to generalize the methodology of Cohen et al. (019). put Py = 1- 1-pA for simplicity (yet it is not necessary to assume this, see Appendix[B... B.55) Let be the point to certify, 11 the potential adversary point, 5 -11-1 -20 the noise and on o (rr) σ = (xx) the standard deviations used in vi and 21 respectively. Furthermore, let Si be a density and P, probability measure corresponding to (z (=,,,a?))) i {0.1). 1].
Lemma 1. Out of all possible classifiers ʃ such that Gf(z) S pn 1 Pa, the one, for which
Gz(z + 5)B is maximized is the one, which predicts class B in a region determined by the likelihood ratio:
f((z)
B R.
2
fo(x))
where r is fixed, such that Po (B) = Pp- Note, that we use B to denote both the class and the region of that class.
We use this lemma to compute the decision boundary of the worst-case classifier f Theorem 2. of > 01, then B is N -ddimensional ball with the center at Sy and radius Rs:
of R
og of (a
1811 + 2N oz of of
8o
20j07
S, = + 00 of
log
+ of
log(r).
of)²
of
01
If 0o0 oi then B is the complement of N -idiennsion ball with the center at Se and radius Rzi
20 - (of - -
oā log
20
Sz
0
8. R
|
|8||2 + 2N
of
ob
0o
of
o
log(r).
3

---

Under review as a conference paper at ICLR 2022
CLASS
CLASS
Figure 2: Decision regions of the worst-case classifier ʃ" Left: do > σi Right: on < 01
As we depict on Figure both resulting balls are centered on the line connecting To, 31. Moreover, the centers of the balls are always further from 2o, than I is from zo (even in the case do < a1). both cases, it depends on Pa (since r fixed such that (B( = pn) and the ball can, but might not cover zo and/or 21. Note that if σ1. what can happen even in input-dependent regime, the worst-case classifier is the half-space described by [Cohen et al. (2019).
To compute the probability of ball under probability measure with an isotropic Gaussian density far more challenging than to compute the probability half-space. In fact, there is no closed- form formula for such probability. However, this probability is connected the non-central chi- square distribution (NCCHSQ). More precisely, the probability of an N-dimensional ball centered with radius under (00 /) can be expressed as cumulative distribution fucntion (edf) of NCCHSQ with N degrees of freedom, non-centrality parameter || and argument r². With this knowledge, we can express Po(B) and PP (B) terms of the edf of NCCHSQ follows. Theorem 3.
of (o) - o
R PB( X2
(G33 of
R |1011
Pb( = x
(o8 - o?
of
where the sign or >> is chosen according the inequality between dy and 01
Note, that both Theorem 2 and Theorem 3 work well also for 5 = 0. In this case, we encounter ball centered at Zo I1 and all the edf functions become edf functions of central chi-squared.
We expressed probabilities of the worst-case class B's decision region using the cdf of NCCHCSQ. Now, how do do the certification? We start with the certification just for two points, 2g and Z1- We question, under which circumstances can be certified from the point of view of rp. Having To.
PA and 0g > di, we can obtain such R, that (B)( x2y [166||00/( (o oi)², It)) 1- PA pn simply by putting it into the quantile function: R² = x2vat /101//8//(0 - of) (-11-pa) PA). Then,
substitute into Pı PIB x²v (110]]0a/((3) 3 of)? RRoo/of) This way, obtain Pi PI
and can judge, whether (B) < 1/2 or not. Similar computation can be done if oo 01- Denote
= || We can express the IP, (B) more simply for og 01 as
of
of (of
{a) := PB() = x
(of ofp
of
XN.af
o
off
a² - PA
and for 0g <
o
2
o; [o
d PA ))
== P(())=;;(BB=111 =1
2
o
32
o
XNal
2y
With this in mind, if we have Zo, 21, PA, Go. d1, then the correct sign (<,>) and computing & (l]mg- - xz II) or & ([|.,
certify 21 w.r.t zo simply by choosing
Iz l]), comparing them with 0.5.
The sample plots of these & functions be found in Appendix B
Now, we are ready to discuss the curse dimensionality. The problem that arises that having a high dimension N and 0 differing lot from each other, & functions already big at 0, even
4

---

Under review as a conference paper at ICLR 2022
Tightness of the results, Pa = 0.9
Tightness of the results, PA 0.999
threshold
threshold
0.6
0.-
0.4
theoretical threshold
cheoretical threshold
practical threshold
oractical threshold
AM00
1MM0
dimension
dimension
Figure 3: Plots depicting tightness of results of Theorem On both figures, the biggest possible threshold of a 01/00 for which the condition in Theorem is satisfied (theoretical threshold) and the numerically computed threshold for which &> (0) passes the threshold 0.5 (practical threshold) are depicted. Left: Plot for a 0.9, Right: Plot for p.a 0.999.
for considerably small PB. For fixed ratio 0 0 and probability PB. with increasing dimension, the <(O) increases and soon becomes bigger than 0.5. This, together with monotonicity of & function yields that any cannot be certified w.r.t. Zg, if op are used. The more dissimilar the og and are, the smaller the dimension N needs be for this situation to occur. we want to certify 2ı in a reasonable distance from To. we need to use similar 01. This restricts the variability of (xx function. We will formalize the curse of dimensionality in the following theorems. More on why the curse of dimensionality is present is in Appendix B.2
Theorem (curse of dimensionality). Let Zo. 31, PA oo. T1. N be as usual. Then, the following two implications hold:
1. If oo 01 and
0
21og PA)
log
+ 1
<
00
N
then is not certified w.r.t. 27.
2. If 0 and
of - log
0
-1
2og (1 - -PA)
+
N
of
N
N
then 21 not certified w.r.t. Fp-
Corollary 5 (one-sided simpler bound). Let F1, PA 01, N be as usual and assume now dp > 01. Then, if
log(1 1 PA)
2/
On
N
then øj is not certified w.r.t Zo.
Note, that both Theorem and Corrolary 5 can be adjusted to the case where we have a separate estimate Pæ and do not put PB = 1 - Pa (see Appendix B.5). We must emphasize, that the bounds obtained in Theorem 4 are very tight. In other words, if the ratio @ is just slightly bigger than the minimal possible threshold determined in Theorem 4 ε (0) becomes smaller than 0.5 and similarly for E> (0). The reason for this is, that the only two estimates used in the proof of Theorem are the estimates the median, which are very tight and constant with respect to N and the Chernoff bound, which is generally considered to be tight too and improves for larger N. The tightness is depicted on Figure where we plot the minimal possible threshold 0 given by Theorem 4 and minimal threshold for which & (0) < 0.5 as a function N.
To get better feeling about the concrete numbers, provide simple table, which shows the theoretical threshold values provided by Theorem If //o smaller than the threshold, we are not able to certify any pair of zp, Ti using do. 01
5

---

Under review as a conference paper at ICLR 2022
PA
0.9
0.99
0.999
0.99993
MNIST
0.946
0.924
0.908
0.892
CIFARIO
0.973
0.961
0.953
0.945
ImageNet
0.997
0.995
0.994
0,993
Table 1: Theoretical threshlhessoods for / for different data dimensions and class A probabil- ities. The ImageNet spatial size is assumed to be 3x256x256.
Results from Table 1 are very restrictive. Assume we have CIFARIO sample with PA 0.999. For such a probability, constant o = 0.5 is more than sufficient to guarantee the certified radius of more than 1. However, in the non-constant regime, to certify R > no sample within the distance of from zo uses 0j < 0.953mp- To even strengthen this statement, note that one needs guarantee d1 be even much closer do in practice. Why? The results of Theorem 4 lower- lower-bound the & functions at 0. However, since & functions are strictly increasing (as shown in Appendix FD. one usually needs dg and 01 to be much closer to each other to guarantee being smaller than 0.5 at > O. This not only forces the a (x) function to have really small semi- elasticity but also makes problematic to define a stochastic (x). For more, see Appendix B.2
first need to guarantee that
To fully understand, how the curse of dimensionality affects the usage of IDRS, we mention two more significant effects. First, with increasing dimension, the average distance between samples tends to grow as /N. This enables bigger distance to change a (x). On the other hand, the average level of a (x) used (like ~ 0.12, 0.25....) needs to be adjusted also as VN with increasing dimen- sion. The bigger average level of (zx) we use, the more is the semi-clasticity of (zz) restricted by Theorem 4 and Theorem 7 All together, these two effects combine in a final trend that for On and σ1 being variances used two random test samples, 100/01 1| is restricted to go to as 1/VN. For detailed explanation, see Appendix B.4
3 HOW TO USE INPUT-DEPENDENT SMOOTHING PROPERLY
As we discuss above, usage of IDRS is challenging. How can we use a (xx) and obtain valid, math- ematically justified certified radiuses? Fix some design (z)) If o(x) is not trivial, to obtain a certified radius at Fu, need go over all the possible adversaries 2ı in the neighborhood of zo, compute oi and Ex.> (a). Then, the certified radius is the infimum over |x0 - x1 for all uncertified In points. Of course, this is priori infeasible. Fortunately, the & functions possess a property that helps to simplify this procedure. For convenience, we extend the notation of & functions such that ((a,a)) additionally denotes the dependance on the 01 value.
Theorem 6. Let 20,41,PA;00 To be as usual and let ||00 - æ1ll = R. Then, the following two statements hold:
1. Le 0g. Then, for all 02 01 I 02 oo if (R, 02) 0.5, then (R, > 0.5.
2. Le og. Then, for all 0g o 8a oo. if & (R, 02) 0.5, then (R, 0.5. I
Theorem 6 serves as a kind of monotonicity property. The main gain is that now, for each distance R from Zg. we need to pick just two adversaries the one with biggest 01 (if bigger than og) and the one with the smallest 01 (if smaller than do). If we cannot certify some point 21 at the distance R from Zo. then we will for sure not be able to certify at least one of the two adversaries with the most extreme 0i values.
This does, however, not suffice for most of the reasonable (xx designs, since it might be still too hard to determine the two most extreme o 's at some distance from Zg. Therefore, we need to assume that our a (xr) has a bounded semi-elasticity coefficient r. Then we have a guarantee that a ((ro)exp(rra)) < (xx) S (xx)) exp(ra). Thus, we can assume the worst-case extreme 0 's for every distance a from Zg. Using this, we guarantee the following certified radius.
Theorem 7. Let (x) be r-semi-elastic function and zo, PA, N, do as usual. Then, the certified radius at Ty guaranteed by our method is
CR(xp) max s0,sup (R 0: E> E> a exp((rRR)) 0.5 and &x og exxp(rR) < 0.5)).

---

Under review as a conference paper at ICLR 2022
Note that Theorem can be adjusted to the case where we have separate estimate Pg and do not put PB = 1 1 PA (see Appendix B.5). Since the bigger the semi eaiieciaticity constant of ( is, the worse certifications
obtain, it is important to estimate the constant tightly. Even with a good
estimate of r, we still get smaller certified radiuses in comparison with using the (x) exactly, but that is prize that is inevitable for the feasibility of the method.
The practical algorithm is then very easy we just need to pick sufficiently dense space of possible radiuses and determine the smallest, for which either (R, oo exp(-rft) or & (R, oo (x)(rRt) becomes bigger than a half. The only non-trivial part is, how to evaluate the E functions. For small values of R. the exp(-r is very close that this results in extremely big imputs to the edf and quantile function of NCCHSQ. To avoid numerical problems, we employ a simple hack where we assume thresholds for σi such that for R small enough, these thresholds are used instead of exp(+r R)). Unfortunately. the numerical stability still disables the usage of this method on really high-dimensional datasets like ImageNet. For more details on implementation, see Appendix D
and from the definition of ç functions it is obvious
4 THE DESIGN OF (z)) AND EXPERIMENTS
The only missing ingredient to finally being able to use IDRS is the (z)) function. As we have seen, this function has to be r-semi-elastic for rather small r and ideally deterministic. Yet should at least roughly fulfill the requirements imposed by the motivation it should possess big values for points far from the decision boundary of f and rather small for points close to it. Adhering to these restrictions, we use the following function:
(1(1
(xx) a exp r
1 xzll (x))
Σ
for being base standard deviation, r being the required semi semi-elasticity, {x;} the training set, (x) the nearest neighbors of z and m the normalization constant. Intuitively, if sample is far from all other samples, it will be far from the decision boundary, unless the network overfits to this sample. On the other hand, the dense clusters of samples are more likely to be positioned near the decision boundary, since such clusters have a high leverage on the network's weights, forcing the decision boundary to adapt well to the geometry of the cluster. To use such function, however, we first prove that it is indeed r-semi-elastic.
Theorem 8. The (x) defined in equation I is r-semi-elastic.
We test our IDRS and our (2) functions extensively. For both CIFARIO Krizhevsky 2009 and MNIST (Leuun et al. 1999) datasets, we analyze series of different experimental setups, including experiments with an mput-dependent train-time Gaussian data augmentation. We present a direct comparison of our method with the constant method using evaluation strategy from Cohen et al.) 2019) (all other experiments, including ablation studies, and the discussion on the hyperparameter selection are presented in Appendix [E). Here, compare Cohen al. (2019)'s evaluations for = 0.12, 0.25, 0.50 with our evaluations, setting σ, = a. = 0.01, h = 20. m 5, 1.5 (for CIFARIO 10 and MNIST, respectively), applied on models trained with Gaussian data augmentation, using constant standard deviation roughly equal to the average test-time o (Ir) or test-time a. For CIFAR1O, these levels of train-time standard deviation are Otr 0. 0.. 0.263, 0.53 and for MNIST Orr = 0.124, 0.258, 0.517. In this way, the levels of a (xx we use in the direct comparison are spread from the values roughly equal Cohen et al. (2019)'s 's constant o to higher values. The results are depicted in Figure
From Figure 4 we see that we outperform the constant a for small levels of a, such as 0.12 or 0.25. On higher levels of a. we are, in general, worse (see explanation in (..3. The most visible improvement in mitigation of the truncation of certified accuracy (certified accuracy waterfall). To comment on the other two issues, we provide Tables [ and with the clean accuracies and class- wise accuracy standard deviations. These results are averages of 8 independent runs and in Table the displayed error values equal to empirical standard deviations.
From Tables accuracy trade-off, because the differences in clean accuracies are not statistically significant in
2 and 3 we draw two conclusions first, it is not easy to judge about the robustness

---

Under review as a conference paper at ICLR 2022
CIFAR-10 companizon. 0:12
main comperison, 0.25
CIFAR--10 comparieon, 0.50
0.32,
0.25, mb
Dinifed MOSUNNe
0.6
68
08
0.4
8.
04
0.0
6.1
0.2
0.4
0.5
0.0
02
0.5
0.8
100
0.5
1.0
1.5
2.0
MNIST, comparison,
comparison,
MNIST, main comparison,
cent feet excuricyy
0.8
0.8
0.8
0.4
0.4
022
Cohen
Cohon
0.125
r-002,
0.50,
0..53
00
0.1
0.2
0.3
0.5
0.6
60
0.2
0.4
0.6 rodius
088
1.0
00
0.5
1.0
1.5
2.0
1adlus
Figure 4: Comparison of certified accuracy plots for Cohen et al. (2199) and our work.
dataset
0.12
0 0.25
0.50
T 0.01, Otr increased
0.852
0.002
0.780 +: 0.013
0.673 1 0.008
r' 0.00
C
0.851 + 0.006
0.792 + 0.004
0.674 = 0.018
0.01, Frr increased
M
0.9912 0.0003
0.9910 + 0.0006
0.9881 + 0.0003
r 0.00
M
0.9914 + 0.0004
0.9907 + 0.0004
0.9886 + 0.0005
Table 2: Clean accuracies for both input-dependent and constant a evaluation strategies on CIFARIO (C) and MNIST (M).
dataset
o
0.12
0.25
a = 0.50
0.01, Der increased
C
0.076
0.099
0.120
r= 0.00
C
0.076
0.097
0.122
0.01, oer increased
M
0.00775
0.00777
0.00930
r= 0.00
M
0.00751
0.00778
0.00934
Table 3: Class-wise accuracy standard deviations for both input-dependent and constant evaluation strategies on CIFARIO (C) and MNIST (M).
any of the experiments (not even for CIFARIO and 0.25, where the difference is at least pro- nounced). However, the general trend Table indicates that the clean accuracies tend to slightly decrease with increasing rate. Nevertheless, the differences are not large enough to compensate negatively the fact that we outperform constant a in terms of the certified accuracies. Second, the standard deviations of the class-wise accuracies, which serve as good measure of the impact of the shrinking phenomenon and subsequent fairness, don't 't significantly change after applying the non-constant RS.
RELATED WORK
Since the vulnerability of deep neural networks against adversarial attacks has been noticed by Szegedy et al. (2013); Biggio et al. (2013) a lot of effort has been put into making neural nets more robust. There two types of solutions empirical and certified defenses. While empirical defenses suggest heuristics to make models robust, certified approaches additionally provide way to compute mathematically valid robust radius.
8

---

Under review as a conference paper at ICLR 2022
One of the most effective empirical defenses, adversarial training (Goodfellow et al. 2014 Kurakin ct al. 2016 Madry et al.) 2017), is based on a very intuitive idea to use adversarial examples for traiiig. Unfortunately, together with adversarial training. other promising empirical defenses were subsequently broken by more sophisticated adversarial methods (for instance Carlini & Wagner (2018), among many others).
(2017)
Athalye & Carlini (2018); Athalye et al.
2018: Anil et al.) [019 Hein & Andriushchenko 2017 Wong & Kolter, 2018 Raghunathan et al. [2018] Mirman et al. 2018; Weng et al. (0118).
Among many certified defenses (Tsuzuku et al.
one of the most successful yet is RS. While Lecuyer et al. (2019) introduced the method within
the context of differential privacy, Li et al. (2019) proceeded via the knowledge of Rényi diver-
gences. Possibly the most prominent work on RS is that of Cohen et al. (2019), where authors fully
established RS and proved tight certification guarantees.
Later, lot of authors further worked with RS. The work of Yang et al. (2020) generalizes the cer- tification provided by [Cohen et al.) 2 to certifications with respect to the general Ip norms and provide the optimal smoothing distributions for each of the norms. Other works point out differ- ent problems or weaknesses of RS like the curse dimensionality (Kumar et al., 2020 Hayes) 2020 Wu et al.] (2021), robustness vs. accuracy trade-off (Gao et al.) (0200) or shrinking phe- nomenon Mohapatra et al. 2020a), which yields serious fairness issues (Mohapatra et al., (220a)).
The work of Mohapatra al. (2020b) improves RS further by introducing the first-order information about g. In this work, authors not only estimate g(z). but also Vg(x), making more restrictions on the possible base models f that might have created g. /Zhai al. (2020) and Salman al. (2019)
improve the training procedure of f to yield better robustness guarantees of g. Salman et al. (019))
directly use adversarial training of the base classifier f. Finally, Zhai et al. (2020) introduce so- called soft smoothing, which enables to compute gradients directly for and construct a training method, which optimizes directly for the robustness of g via the gradient descent.
To address several issues connected to randomized smoothing, there have been already four works that introduce the usage of IDRS. Wang et al. (2021) divide R- into several regions R., e {I...., K} and optimize for o;, E {I,.... ..... K} locally, such that is a most suitable choice for the region RG Yet this work partially solves some problems of randomized smoothing, also possesses some practical and philosophical issues (see Appendix C [Alfarra et al. (2020): [Eiaa et al.) Chen et al.) (202T), suggest to optimize for locally optimal as for each sample x; from the test set. A similar strategy is proposed by these works in the training phase, with the intention of obtaining the base model f that is most suitable for the construction of the smoothed classifier g. They demonstrate, that by using this deput-den approach, one can overcome some of the main problems of randomized smoothing. However, as we demonstrate in Appendix C their methodology is not valid and therefore their results are not trustworthy.
[0ee))[Chen
CONCLUSIONS
We show in this work that input-dependent randomized smoothing suffers from the curse of dimen- sionality. In the high-dimensional regime, the usage of input-dependent (zx) is being put under strict constraints. The azx) function is forced to have very small semi-clasticity. This is in con- flict with some recent works, which have used the input-dependent randomized smoothing without mathematical justification and therefore claim invalid results. It seems that input-dependent random- ized smoothing has limited potential of improvement over the classical, constant-o RS. Moreover, due to numerical instability, the computation of certified radiuses on high-dimensional datasets like ImageNet remains to be an open challenge.
On the other hand, we prepare a ready-to-use mathematically underlined framework for the usage of the input-dependent RS and show, that it works well for small to medium-sized problems. We also show via extensive experiments, that our concrete design of the azx) function reasonably treats the truncation issue connected to constant-o RS and is partially capable of mitigating the robust- ness vs. accuracy one. The most intriguing and promising direction for the future work lies in the development of new (Ix) functions, which are capable of even better treatment of the mentioned issues.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
Both our theoretical and practical results and experiments are reproducible. In the theoretical part, we provide all the relevant proofs, insights and all the important reasoning. We use public datasets for our experiments and our code contains just public, well-known libraries. The code will be publicly available after the review process. We not use seeds for stochastic algorithms, but the level of variance is not large enough to obtain qualitatively different results. Upon request, we are willing to provide models trained by us to obtain exactly the same results.
REFERENCES
Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem. Data dependent randomized smoothing. arXiv preprint arXiv:2012.04357, 2020.
Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. Kama- lika Chaudhuri and Ruslan Salakhutdinoy (eds.), Proceedings of the 36th International Confer- ence on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 291-
301. PMLR, 09-15 Jun 2019. URL httLttt://prrceednnng. mmr wwwppprsssss/eeeee http://1///nnn1.... html
Anish Athalye and Nicholas Carlini. On the robustness of the evpr 2018 white-box adversarial example defenses. arXiv preprint 1oXiv:1804.0333 2018.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of curity: Circumventing defenses to adversarial examples. In International conference on machine learning, pp. 274 PMLR, 2018.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 387-402, Berlin, Heidelberg, 2013. Springer Berlin Hei- delberg. ISBN 978-3-642-40999--3
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten de- tection methods. In Proceedings the 10th ACM workshop on artificial intelligence and security, pp. 3-14, 2017.
Chen Chen, Kezhi Kong, Peihong Yu, Juan Luque, Tom Goldstein, and Furong Huang. Insta- rs: Instance-wise randomized smoothing for improved robustness and accuracy. arXiv preprint arXiv:2103.04436, 2021.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320 1320. PMLR, 2019.
Francisco Eiras, Motasem Alfarra, M Pawan Kumar, Philip HS Torr, Puneet K Dokania, Bernard Ghanem, and Adel Bibi. Ancer: Anisotropic certification via sample-wise volume maximization. arXiv preprint arXiv:2107.04570, 2021.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1625-1634, 2018.
Yue Gao, Harrison Rosenberg, Kassem Fawaz, Somesh Jha, and Justin Hsu. Analyzing accuracy loss in randomized smoothing defenses. arXiv preprint trXiv:2003.0/500 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Ingo Gühring, Mones Raslan, and Gitta Kutyniok. Expressivity of deep neural networks. arXiv preprint arXiv:2007.04759 2020.
10

---

Under review as a conference paper at ICLR 2022
Jamie Hayes. Extensions and limitations of randomized smoothing for robustness guarantees. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Work- shops, pp. 786-787, 2020.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of classifier against adversarial manipulation. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http:: / /ttptpppps//prrceeednlgg... neurips cc/ Papper pdf
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. URL http://
Www. toronto........oooooooooo....... edu/ ttt........t....oiii////// wea.ii/leeriinggge featunnss-eueeseeeeeeeee 2009- pdf
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learn- ing. pp- 5458 5468, PMLR, 2020.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint arXiv:161 2016.
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. The mnist database of handwritten digits, 1999. URL http:: lecun. www.uu.c.o/exx////////oooee htnm/exxbmmmiss.//
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy (SP), pp. 656-672 IEEE, 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 32:9464-9474, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. arXiv preprint 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 3578-3586. PMLR, 10-15 Jul 2018. URL httt:://proceeeeee press/ fress/v80/ne mi rman www.maannn.......m htm.
mir.
Jeet Mohapatra, Ching-Yun Yun Ko, Sijia Liu, Pin-Yu Chen, Luca Daniel, et al. Rethinking randomized smoothing for adversarial robustness. arXiv preprint arXiv:2003.012 012499 2020a.
Jeet Mohapatra, Ching- Yun Ko, Tsui- Sei-WWii Weng, Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing. Advances Neural Information Processing Sys- tems, 33, 2020b.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference on Learning Representations, 2018.
Christian Robert. On some accurate bounds for the quantiles of a non-central chi squared distribu- tion. Statistics & probability letters, 10(2):101-106, 1990.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In NeurIPS, 2019.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312,6 / 2013.

---

Under review as a conference paper at ICLR 2022
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-margeh margin training: Scal- able certification of perturbation invariance for deep neural networks. In S. Ben-
gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL
Paper. Paper..d pdf
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 6777):377--3820, 2014.
Lei Wang, Runtian Zhai, Di He, Liwei Wang. and Li Jian. Pretrain-to-finetune, adversarial training via sample-wise randomized smoothing. 2021. /tLpttts://ppeeeeviii net formm?? Ti--Tlaa22mg In
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song. Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5276-5285, PMLR, 10-15 Jul 2018. URL
mlr wtt.ssswm.ppppp..pe.eeeeeeeeeeee wwtpss/vwt/wweeeeeeeepeeeeeeeeee
html
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295, PMLL, 2018.
Yihan Wu, Aleksandar Bojehevski, Aleksei Kuvshinov, and Stephan Günnemann. Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions. In International Conference on Artificial Intelligence and Statistics, pp- 3763-3777.
PMLR, 2021.
Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference Machine Learning, pp. 10693- 10705. PMLR, 2020.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. arXiv preprint arXiv:2001.02378, 2020.
A THE ISSUES OF CONSTANT a SMOOTHING
A. TOY EXAMPLE
To better demonstrate our ideas, we prepared a two-dimensional simple toy dataset. This dataset can be seen in F 5 The dataset is generated in polar coordinates, having uniform angle and the distance distributed as a square root suitable chi-square distribution. The classes are positioned in circle sectors, one in sector with very sharp angle. The number of training samples is 500 for each class, number of test samples is 100 for each class (except demonstrative figures, where increased it to 300). The model that was trained on this dataset three-layer neural network with ReL.U activations and a maximal width of 20.
simple fully connected
A.2 UNDERCERTIHCATION CAUSED BY THE USE OF LOWER CONFIDENCE BOUNDS
As we mention in Section 0 one can not usually obtain exact values of PA and pB- However, obvious, that for vast majority of evaluated samples, PA < PA and pg PB. Given the nature of our certified radius, it follows that < R. where I denotes the certified radius coming from the certification procedure with PA and pg, while R here stands for the certified radius corresponding to true values PA.PB.
It is. therefore, clear, that face certain level of under-certiffcation. But how serious under- certification it is? Assume the case with a linear base classifier. Imagine, that we move the point further and further away from the decision boundary. Therefore, PA 1. At some point, the
12

---

Under review as a conference paper at ICLR 2022
probability will be so large, that with high probability, all samplings in our evaluation of PA will be classified as A, obtaining PA = 1 the empirical probability. The lower confidence bound PA is therefore bounded by having PA 1. Thus. from some point, the certification will yield the same PA regardless of the true value of p.A. So in practice, we have an upper bound on the certified radius R in the case of the linear boundary. In Figure (lefft, we from a distance of roughly 4, we can no longer achieve a better certified radius, despite its theoretical value equals the distance. Similarly, if we fix distance of a from decision boundary and vary o, for very small values of a, the value of Φ (pa) will no longer increase, but the values of a will pull R towards zero. This behaviour is depicted in Figure [ (right).
the truncation effect. Using a 1,
We can also look at it differently what is the ratio between & (PA) and 4 (''(pA) for different values of PA? Since R σ (PA)
x and R o (pa), the ratio represents the "undercertifi- (Pa)
cation rate". In Figure 6 we plot (p4) as a function of pa for two different ranges of values. The situation is worst for very small and very big values of PA- In the case of very big values, this can be explained due to extreme nature of 6- For small values of PA. it can be explained as a consequence of fact, that even small difference between PA and PA will yield big ratio between Φ (pA) and क Φ- (pA) due to the fact, that these values are close to O.
If we look at the left plot on Figure g we see, that the certified accuracy plots also possess the truncations. Above some radius, no sample is certified anymore. The problem is obviously more serious for small values of a. On the right plot of Ti we see, that samples far from the decision boundary are obviously under-certified. We can also see, that certified radiuses remain constant, even though in reality they would increase with increasing distance from the decision boundary.
All the observations so far motivate us use rather large values of a in order to avoid the truncation problem. However, as we will see in the next sections, using a large carries a different, yet equally serious burden.
A.3 ROBUSTNESS VS. ACCURACY TRADE-OFF
As we demonstrate in the previous subsection, it is be useful to use large values of a to prevent the cettficertiiic.ioon. But does it come without prize? If we have closer look at Figure 8 (right), might notice, that the accuracy on the threshold 0, i.e. "clean accuracy", decreases as a increases.
This effect has been noticed in the literature (Cohen al. 2019: Gao al. 2020 Mohapatra al., 2020a) and is called robustness vs. accuracy tradeoff.
There are several reasons, why this problem occurs. Generally, changing a changes the decision boundary of and we might assume, that due to the high complexity of the boundary of f. the decision boundary of g becomes smoother. If is too large, however, the decision boundary will be so smooth, that it might lose some amount of the base classifier's expressivity. Another reason for the accuracy drop is also the increase in the number of samples, for which the evaluation abstained. This is because using big values of a makes more classes "within the reach of our distribution". making the Pa and PA small. PA < 0.5 and we do not estimate pn but set Fg = PA. then
Train dataset
Test dataset
75-
first class
second class
-3-
-73
first class
-180-
second class
3.
7.5
10.0
Figure 5: The toy dataset.
13

---

Under review as a conference paper at ICLR 2022
Uncercertificazion rate, linear boudnary
Uncercertification rate, linear boudnary
030
(p.1rr (kbbppp ()
0.84
0.97
0.88
699 00 07
64
0.
10
9993
0.82
0034
0.000
0356
1002
Pa
Figure 6: The ratio between certified radius if using lower confidence bounds and using exact values for the case linear boundary.
Certified radius distance (linear boundary)
Certified radius of sigma (linear boundary)
15-
10
255
madius
2.4
redius
1.5
14-
03
60
0.0
distance
sgma
Figure 7: Left: Certified radius as function of distance linear boundary case. The truncation 100000, a 0.001, a 1. Right: Certified radius for point x at fixed distance from linear boundary as a function of used σ.. The undercertification follows from usage lower confidence bounds.
due the of lower confidence bounds. The parameters
Toy dataset comparison
Cohen = 0.12
Cohen a 0.25
0.8
cortified accuraby
Cohen - 0.50
Cohen a 1.00
Cohen 2.00
2.0 radius
Certified accuracy for different levels of a. Right: Certified radiuses and decision boundary of g visualized directly on test set.
Figure 8: Results certification on toy dataset. Left:
not able to classify the sample class A, yet cannot classify it different class either, which forces us to abstain. To demonstrate these results, we computed not only the clean accuracies of Cohen et al. (2019) evaluations but also the abstention rates. Results depicted in the Table 4
From the table, it is obvious, that the abstention rate possibly even bigger cause of accuracy drop than the "clean misclassification" This problem can be partially solved if one estimated pæ together
14

---

Under review as a conference paper at ICLR 2022
Accuracy
Abstention rate
Misclassification rate
0 0.12
0.814
0.038
0.148
0.25
0.748
0.086
0.166
0 0.50
0.652
0.166
0.182
0 1.00
0.472
0.29
0.238
Table 4: Accuracies, rates of abstentions and misclassification rates of Cohen et al. (0019) evaluation for different levels of a.
Hearmap smrotted constant
Hearmap sed clsatier constant
|eetmmp base clessiler
-60
120
-38
with conslant signe
with conslant sigma
with constant sigma
04
40
30
10
Figure 9: Heatmaps and decision boudnary of base classifier (top left) and the smoothed classifier for increasing levels of a. As a increases, the classifier more smooth and the decision boundary recedes.
with PA too. In this way, using big yields generally small estimated class probabilities, but since pa 2 pn. the problematic pn 2 Pa occur just very rarely. Another option increase the number of Carle samplings for the classification decision, what is almost for free.
Yet another reason for the decrease in the accuracy is the so-called shrinking phenomenon, which will discuss in the next subsection.
contrast with the truncation effect, the robustness vs. accuracy trade-off motivates the usage of smaller values of a in order to prevent the accuracy loss, which is definitely very serious issue.
A.4 SHRINKING PHENOMENON
How exactly does the decision boundary of g change, as we change the a? For instance, if f is linear classifier, then the boundary does not change at all. To answer this question, we employ the following experiment: For our toy base classifier on our toy dataset, we increase a and plot the heatmap of f.g. together with its decision boundary. This experiment is depicted on Figure 9 As we see from plots, increasing a causes several effects. First of all, the heatmap becomes more and more blurred, what proves, that stronger smoothing implics stronger smoothness.
Second, crucial, effect is that the bigger the a, the smaller the decision boundary class is. The shrinkage becomes pronounced from any decision boundary anymore. Generally, as o - oc, g will predict the class with the biggest volume in the input space (in the case of bounded input space, like in image domain, this is very well defined). For extreme values of sigma, the PA will practically just be the ratio between the volume of A and the actual volume of the input space (for bounded input spaces).
submissive 4, there is hardly
1. Already for
15

---

Under review as a conference paper at ICLR 2022
Following from these results, but also from basic intuition, seems, that an undesired effect becomes present as o increases - the bounded/convex regions become to shrink, like in Figure while the umbounded/big/aniiccomm
regions expand. This is called shrinking phenomenon. Mohapatra et al. (2020a) investigate this effect rather closely. They define the shrinkage and vanishing of regions formally and prove rigorously, that if a - oc, bounded regions, semi-bounded regions (see Mohapatra et al. (2020a)) will eventually vanish. We formulate the main result in this direction.
Theorem 9. Let us have K the number of classes and the dimension N. Assume, that we have some bounded decision region D for a specific class roughly centered around O. Further assume, that this is the only region where the class is classified. Let R be smallest radius such that DD C (B(()).
Then, this decision region will vanish at most for a z RyK
Proof. The idea of the proof is not very hard. First, the authors prove, that the smoothed region will be a subset of the smoothed (0). Then, they upper-bound the vanishing threshold of such a ball in two steps. First, they show, that O is not classified as the class, then no other point will be (this is quite an intuitive geometrical statement. The (0) has the biggest probability under (z o I) if x = 0). Second, they upper-bound the threshold for a, under which (R) will have probability below K (since they use slightly different setting as Cohen et al. (2019) for the N(x, ()), Using some insights about incomplete gamma function, which Is known to be also the cdf of central chi- square distribution, and some other integration tricks, they obtain the resulting bound.
Besides Theorem | authors also claim many other statements abound shrinking, including shrinking of semi-bounded regions. Moreover, they also conduct experiments on CIFARIO and ImageNet to support their theoretical findings. They also point out serious fairness issue that comes out as a consequence of the shrinkage phenomenon. For increasing levels of a, they measure the class- wisee clean accuracy of the smoothed classifier. If f is trained with gaussian data augmentation (what is known to be a good practice in randomized smoothing), using a = 0.12, the worst class cat has test accuracy of 67%, while the best class automobile attains the accuracy of 92%. The figures, however, change drastically, if we use a = instead. In this case, the worst predicted class cat has accuracy of poor 22%, while ship has reasonable accuracy 68%. As authors claim, this is consequence of the fact that samples of cat are situated more in bounded, convex regions, that suffer from shrinking, while samples of ship mostly placed in expanded regions of anti-convex shape that will expand as the a grows. In addition, the authors also show, that the gaussian data augmentation or adversarial training will reduce the shrinking phenomenon just partially and for moderate and high values of a, this effect will be present anyway.
We must emphasize, that this is a serious faimess issue, that has to be treated before randomized smoothing can be fully used in practice. For instance, if we trained a neural network to classify humans into several categories, fairness of classification is inevitable and the neural network cannot be used until this issue is solved.
Similarly as the robustness vs. accuracy tradeoff, this issue also motivates to use rather smaller values of a. We see, that it is not possible to address all three problems consistently because they disagree on whether to use smaller, or bigger values of
A.5 EXPERIMENTS ON WIGII-DIMENSIONAL TOY DATASET
In this subsection, we present the results of our motivational experiment on a synthetic dataset. Before reading this section, please read our main text, because we will use the necessary notation of the paper.
The dataset we evaluated our method on is generalization of the dataset visualized on Figure I The data points from one class lie in cone of small angle and the points are generated such that the density is higher near the vertex of the cone (which is put in origin). Points from other class are generated from a spherically symmetrical distribution (where points sampled into the cone are excluded) with density again highest in the center (note, that the density peak is more pronounced than in the case of normal distribution, where the density around the center resembles uniform dis- tribution). This dataset is chosen so that the (2) function designed in Equation I well corresponds to the geometry of the decision boundary. Moreover it is chosen that the conic decision region
16

---

Under review as a conference paper at ICLR 2022
Dimension
(0r)
Accuracy
2
0.5
0.943
2
0,4
0.2
0.96
2
0.5
0.2
0.943
6
0.5
0,946
6
0.4
0.1
0.963
18
1.0
0.86
18
0.8
0.05
0.886
60
1.0
0.83
60
0.8
0.03
0.85
60
1.0
0.03
0.83
180
2.0
0.713
180
1.9
0.01
0.726
400
2.0
0.623
400
1.95
0.005
0.623
Table Clean accuracies different evaluations of our toy experiment.
will shrink rather fast with increasing a. The motivation of this example is to show that if the (xx) function is well-designed, our IDRS can outperform the constant RS considerably.
The setup of our experiment is follows: We evaluate dimensions N 2, 6, 18, 60, 180, 400. The used for constant smoothing is a = 0.5, 0.5, 1.0, 1.0, 2.0, 2.0 respectively. The used is 0.4, 0.5 for N 2, 0.4 for N 6, 0.8 for N 18, 0.8, 1.0 for N 60, 1.9 for N 180 and 1.95 for N = 400. The rates are r 0.2, 0.1, 0.05, 0.03, 0.01, 0.005 respectively. The training was executed without data augmentation (because samples from different classes are very close to each other). Moreover, we have set maximal ar (Ix) threshold for numerical purposes, because some samples were outliers and were way too far from other samples (and if the (xx) way too big, the method encounteres numerical problems). In this case set (zz) I 5 but we are aware that also much bigger thresholds would have been possible. We present our comparisons Figure I0 and Table
From both the Figure 10aa an Table 5 it is clear that the IDRS can outperform the constant a RS con- siderably, if
really suitable (x) function. We manage improve significantly the certified radiuses without losing single correct classification. On the other hand, in cases where a < a, outperform constant both in clean accuracy and in certified radiuses. This example is synthetic and designed in our favour. The main message is not how perfect our design of (xx) is, but the fact, that if or (2) is designed well, the IDRS can bring real advantages, even moderate dimensions.
B MORE ON THEORY
B.
GENERALIZATION OF RESULTS FROM LI
ET AL. 2019
In our main text, we mostly focus on the generalization of the methods from Cohen et al. (2019). This is because these methods yield tight radiuses and because the application of Neyman- Pearson lemma is beautiful. However, the methodology from Li et al. (2019) can also be generalized for the input-dependent RS. To be able do it, we need some auxiliary statements about the Rényi divergence.
Lemma 10. The Rényi divergence between two one-dimensional normal distributions is as follows:
Da(N(Hn, (olV(nn,o)) of))
amm 222)
1
log Oa
20
1
provided, that oz aaoo aot 2 0.
Proof. See Van Erven & Harremos (2014).
17

---

Under review as a conference paper at ICLR 2022
Multdimenniooall toy dataset, N 2
Multidimensional toy dataset, N 2
Cohen
Cohen
Us = 0.40, = 0.2
Us = 0.50, = 0.2
0.8
0.8
certifed socuracy
certilled socuraoy
0.8
0.8
0.4
0.4
0.2
0.2
0.0
0.0
0
5
0
5
radius
radius
Multidimensional toy dataset,
Multidimensional toy dataset,
1.0
1.0
Cohen = 0.50
Cohen 1.00
0.8
Up 0
0.40, 0.1
0.8
Us 0 0.80, = 0.05
certifee soouracy
certifed soouracy
0.8
0.8
0.4
0.4
0.2
0.2
0.0
0.0
radius
radius
Multidimensional toy dataset, N 60
Multidimensional toy dataset, N 60
Cohen a 1.00
Cohen o 1.00
Us 0.60,
Us 1.00,
certifed acouraoy
certifed acouracy
4
6
10
0
2
10
12
radius
radius
Multidimensional toy dataset, N 180
Multidimensional toy dataset. N = 180
2.00
2.00
Us a 1. 1.90, - 0.01
Us a 1.90, r 0.01
comtife acquracy
0.8
0.8
0.6
0.6
corfified
0.4
0.4
0.2
0.2
0.0
0.0
10 radius
20
10 radius
20
Figure 10: Certified accuracy plots of our multidimensional toy experiments.
Note, that this proposition induces some assumptions on how o d1, a should be related. If > 0 then the required inequality holds for any & a > 0. If og < 0j, then a is restricted and we need to keep that in mind.
Lemma 11. Assume, we have some one-dimensional distributions PI........ Pi and Q1, Q2...., QN defined on common space for pairs with the same index. Then, assuming product space with product -allgerra, we have the following identity:
N
Da x P...... x PN x 22 x ...... x xN)= = Σ D. (P.ll..)
18

---

Under review as a conference paper at ICLR 2022
Proof. See Van Erven & Harremos (2014).
Using these two propositions, we are now able to derive formula for Rényi divergence between two multivariate isotropic normal distributions:
Lemma 12.
20 12 of og 207 + 20 o
log
La
T
N
N
log
01
Proof. Imporant property that is needed here is, that isotropic gaussian distributions factorize to one-dimensinal independent marignals. In other words:
N11,, of = NN(11, x (V of) x (N(IN,
and analogically for zp. Therefore, using Lemma we see:
N =
Σ D of)).
=11
Now, it suffices to plug in the formula from Proposition 10 to obtain the required result:
Da(N(en. (g = a(01; - x22)²
log
20
1
-1-00
0
%
20 a x21))
log
01
log
00
+ 2a(0) - -of)
a
1
a
Now suffices to sum up over i and the result follows.
To obtain the certified radius, we also need result from Li et al. (201)) which gives a guarantee that two measures on the set of classes will share the modus if the Rnyi divergence between them is small enough.
Lemma 13. Let F (P1, Pa..... PK) and (g1 92...., 9k) two discrete measures on C. Let PA PB correspond to two biggest probabilities in distribution Let (ı a+b and M1 Mı-o(a, b) 21-=+b'- - If
D. < - log(1 - (M4.P4 + (MM
then the distributions and Q agree on the class with maximal assigned probability.
Proof. This lemma can be proved by directly computing the minimal required D,, to be able to disagree the maximal class probabilities via constrained optimization problem (with variables Pt, qi i E {1,..., KY), solving KKT conditions. For details, consult Li et al. (2019).
Having explicit formula for the Rnyi divergence, we can mimic the methodology of et al. (019 obtain the certified radius:
Theorem 14. Given To, PA PB. do. N, the certified radius squared for all æ1 such that fixed is used is:
20 + 20(o) ot)
log
Ra
sup
N a log
aa
N
a
σ1
a
log(1 2M (PA, pB) 2M 1M ( (PA,PB))
(0,
where Sog.o. = R4, ao > and Sno.
ア if 0o <a.
19

---

Under review as a conference paper at ICLR 2022
Proof. Let fix 21 and assume, that So Then, due to post post-processing inequality for Renyi
divergence, it follows that
Da(S(z1 + N(O0 of + +N(00, & Da(21 + +N(00, -N0.00))))
log In 1-a
a 20 - xi
00
+N
log
2 + 2a( - o
01
Due to Lemma
13 it suffices that the following inequality holds for some E So0.o1
al120 21
log
da
+ N
N 1
log
_ + 20 o1)
1-
01
-log(1 2 (PA,PB) +
This can be rewritten w.r.t. | x 11
|| =1|1²> 20 + 2a(o ot)
N a
00
log
ga
log
N
log(1 - 2MA + 2Maaa(PA. PB))
The resulting certified radius squared is now simply obtained by taking maximum over ||z0 - x || s.t. 3a E Smo.ag such that the preceding inequality holds.
Note, that this theorem is formulated assuming, that except in To. we use σı everywhere. would require some further work to generalize this for general (0x) functions, but demonstrate the next point, it is not even necessary. Looking at the expression, we can observe that
log
de
00
N
log
N
depends highly N and even for ratio of do close 1, we already obtain very strong negative ai 2 (PA.PB) + 2MI-a(PA,PB) is far less values for high dimensions. The expression log(1 2M, sensitive w.r.t PA and for large dimensions of N is easily "beaten" by the first expression. There- fore, the higher the dimension N is, the bigger pa or the closer to the Zn has to be order to obtain even valid certified radius (not to speak about big). This points out that also the method of et al. (2019) suffers from the curse of dimensionality. as we know it must have done. This method is not useful for big N, because the conditions on PA do, Ji are so extreme, that barely any inputs would yield positive certified radius. This fact is depicted in the Figure
The key reason why this happens if done via Rényi divergences is that while divergence (a(N(21, [| I) grows independently of dimension as || |00 Iz grows, it drastically increases for big N even if æ Io! This reflects the effect, that if do * σ1. then the more dimensions we have, the more dissimilar are M(11, I) and M(ro, T))- We can think of it consequence of standard fact from statistics that the more data we have, the more confident statistics against the null hypothesis dp oi will we get if the null hypothesis is false. Since isotropic normal distributions can be actually treated as a sample of one-dimensional normal distributions, this is in accordance with our multivariate distributions setting.
B.2 THE EXPLANATION THE CURSE OF DIMENSIONALITY
In the Section 2 we show that input-dependent RS suffers from the curse of dimenisonality. Now we will elaborate a bit more on this phenomenon and try to explain why it occurs. First, it is obvious from the Subsection B.I that also the generalized method of Li et al. (2019) suffers from the curse of dimensionality, because the Rényi divergence between two isotropic Gaussians with different variances grows considerably with respect to dimension. This suggests that the input-dependent RS might suffer from the curse dimensionality in general. To motivate this idea even further, we present this easy observation:
20

---

Under review as a conference paper at ICLR 2022
Certified radius as a function dimension. Params: p P_A90 sig sig_0=1, 0=1, sig 1-0.8
1.75
certified radius
1.25
1.00
0.75
0.50
0.25
0
10
40
50
dimension
Figure 11: The certified radius function of dimension. Paremeters PA 0.99, 00 1,01 0.8
Theorem 15. Denote Re to be a certified radius given for and op at To assuming the constant Tn and following the certification Cohen al. 2019 Assume, that we do the certification for each by assuming the worst classslasi as in Theorem 2 Then, for any Tu, any function (xx) and any PA. the following inequality holds:
R R
Proof. Fix γ2 and 01. From Theorem 2 we know that the worst-case classifier f defines ball B such that (B) space B; that assume constant do also for æ1 and the worst-case for do such that TP Bi) = PA not worst-case for the case of using 01 instead. Therefore, (B; (B).
PA- From this it obviously follows, that the linear classifier fi and the linear
Moreover, let IPC be probability measure corresponding to (Z T)), i.e. the probability mea- P (Bt) 0.5 because the probability of a linear half-space under isotropic normal distribution is bigger than half if and only the mean is contained in the half-space.
sure assuming constant og- It is easy to that (Bt) 0.5 >
Assume, for contradiction that R > Rg. From that, it exists particular æı such that IP (B:) > 0.5 (BB.). because otherwise there would be no such point, which would cause R > Rc. However, PP (B,) > 0.3 = Pi (B, > 0.5, thus Pi (Bi) > (B and that is contradiction.
This theorem shows, that we can never achieve a better certified radius at zo using and having probability a than that, which we would get by Cohen al. (219)'s certification. Of course, this does not mean, that using non-constant is useless, since og can vary. The question is, how much do we lose using non-constant a. To get a better intuition, we plot the functions & and & under different setups in Figure [2] together with P, (B:) from the proof of Thcorem 15 From the top row we can deduce that dimension N has a very significant impact on the probabilities and therefore also on the certified radius. We particularly point out the fact, that even & ( can have significant margin w.r.t to the probability coming out of linear classifier Already for = 90, we are not able certify PA 0.99 for rather conservative value of Za From middle row see, that decreasing 51
do can mitigate this effect strongly. For instance, for do L, 0.95 the difference between di (B) and P; (B₃) almost negotiated. Bottom row compares & (a), & (a) and the respective linear classifier probabilities. We can see, that the case op σ might cause stronger restrictions on our certification (yet we deduce it just form the picture).
TThe "C" the subscript certified radius might come both from "constant" "Cohen et. al." Notice the similarity with Rényi divergence, which also has positive value even for if * and then grows rather reasonably with distance.
21

---

Under review as a conference paper at ICLR 2022
Real protability of hall as fcn of distance,
Real probability at hall as fon of distance,
[1. 0.8, 10, 0.01]
1.25, 10. 0.01]
10
10
04-
prebabiitt
66-
Me-35
the leas Ne-15
the Iuao No
traa MI-33
traa M1-333
the innert bourdrry
the inter boundaryy
60
distace
distance
Roal prabability of a ball as fon of distance,
Roal probability of hall as fon of distance. 0.8, 100, 0.1]
[1. 0.6, 100, 0.01]
0.-
probabiity
probebiity
the tean sn Iw0.6 tras eg 1-0.0
2.5-322
tra 2.0-
04-
distacce
distance
Real probability ball distance. [1, 0.85, 100, 0.001]
pribabiity
32-
sayras
boundaryy cart Brrshhes
Figure 12: Plots of E3 (a), (a) for different setups. Coding for parameters is: (oo, Ø1, PB] Top: <> (a) left, (a) right, varying values of N. Center: On the left, (a) for varying 01, on the right E (a) for varying Pg- Bottom: {>(()) (a) and (a) compared.
What the reason for &> (a). {x being so big even at 0? The problem is following: Assume To 01- If xo FT the worst-case classifier coming from Lemma@ will be ball B centered right at Zo, such that PB( = PA- If we look at (B)), we see, that we have the same ball centered directly at the mean, but the variance of the distribution smaller. Using spherical symmetry of the isotropic gaussian distribution, this is equivalent to evaluating the probability of bigger ball. If we fix 0i comes into the game. For
Fo(B) with increasing N, the curse of dimensionality 2, the ratio is not too big. However, if N 3072, like in CIFAR 10, this ratio is far bigger. This can be intuitively seen from a property of chi-square distribution (which is present in the case øo = TT), that while expectation is N, the standard deviation is "just" v2N,
and look at the ratio of probabilities P. (B)
/Var(x3) 0 as N Do. B(ck))
i.c.
B.3 WHY DOES THE INPUT-DEPENDENS SMOOTHING WORK BETTER FOR SMALL VALUES?
As can be observed in Section and Appendix the bigger the σ use, the harder it is to keep up to standards of constant smoothing. An interesting question is, why the usage of small 0₁ helpful for the input- deputddependent smoothing?
Assume fixed o, say Ø = a = 0.12. The theoretical bound on the certified radius given 100000 Monte-Carlo samplings and 0.001 confidence level using constant smoothing is about 0.48. Having
22

---

Under review as a conference paper at ICLR 2022
Certified distance (9.12, 0.01, 30121
Cartitte radius distance (USI, 19.5, 0,03,
0.5
2.00
375
0.4
222
0.3
100
0.75
050
0.1
025
ConStORE F012
constartsimma
constanc Sgma
constan 5ggn
Figure 13: Comparison of certified radius as a function of distance for constant and input-dependent smoothing. Left: σg 0.12, right: db 0.50.
(xx) 0.12, we cannot expect much bigger certified radius. Therefore, if we follow Theorem 7 the values of cxp(-rR) and exp(r R) in the critical distance ~ 0.5 will be much closer to 1, than = 0.50 instead, where the critical values the values of exp(-rR3 and exp(r (R) if we used db of R could be much bigger than 0.5. Therefore, the "gain" in (B) imposed by the curse of dimensionality, compared to IP (B) assuming constant a will not be that severe yet. This means, that the loss in certified radius caused by the curse of dimensionality will be much less pronounced on the "active" range of certified radiuses (those for which the constant smoothing still works), compared to using big σb = a. To support this idea, we demonstrate it on Figure 13 where we depict the certified radius as a function of distance from decision boundary, assuming f to be a linear classifier, using db = 0.12 and σg = 0.50 for comparison.
B.4 How DOES THE CURSE OF DIMENSIONALITY AFFECT THE TOTAL POSSIBLE VARIABILITY OF (x))
Fix certain type of task, say RGB image classification with images of similar object, but consider many possible resolutions (dimensions N). Given two random images from the test set (Io. X1), what is the biggest reasonable value of (2z))/0(2)) ( 1/? Theoretically, the expression is bounded by exp(=r||20 - 21 II) 1/. given that r is the semi- semi-elasticity constant of o(x). However, the average distance between scales vN. Therefore, with constant r, this upper-bound increases.
samples from test set of constant size, but increasing dimension
The increasing distance between samples is, therefore, a countereffect to the curse of dimensionality. In simple words, we have "more distance change a (370) to (x1)". Even if the decreased just as 1/VN, the increasing distances would cancel the effect of the curse of dimensionaity and result, the maximal reasonable value of (xzo)/o(zz) However, we need to take into account another effect. As the dimension increases, also the average distance of samples from the decision boundary increases. This is because the distances in general grow with dimension and we assume that the number of intersections of a line segment between To and 2 with the decision boundary of the network remains roughly constant then the average distance from the decision boundary grows v/N too. In order to compensate for this, need to adjust the basic level of (zz) (which we later call σn and can be understood as the general offset of our (z)) as VN too. This is because the maximal attainable certified radius given fixed confidence level and the number of Monte-Carlo samples is a constant multiple of (x:).
1 would remain roughly constant w.r.t. N.
However, with increased a, we need to decrease the semi-elasticity rate r in order to obtain full certifications (see also Appendix [B.3 for intuition behind this).
As a sketch of proof, we provide a simple computation, which tells us the approximate asymptotic behavior of (0)))//((z1 1|. By Theorem S holds:
(p
exp exp(-reVN) 2 V 1-
N
23

---

Under review as a conference paper at ICLR 2022
if we want to be able predict a certified radius of evN (though this is just necessary condition. For sufficiency, the LHS must be much closer to 1). After simple manipulation, we obtain:
1 log
11
log(pB) N
1 (-1)2)
log(PB)
lpg(PB)
2cv N
2cv N
N
cN
So the rate scales as 1/N. Now we have:
|a()))) 0 (z1) 1| - exp(+r|l - xz (I) - exp(r|/=0 - 21ll) - -
log(pB) CVN) VCClog(PB)
exp(
cN
cVN
B.5 DOES THE CURSE OF DIMENSIONALITY APPLY IN MULTI-CLASS REGIME?
In the main text, we presented a setup, where pn is set to be - PA- This is equivalent to pretending that we have just 2 classes. By not estimating the proper value of рæ lose some amount of power and the resulting certified radius is smaller than it could have been, did we have the PB as well. This is most pronounced for datasets with many classes. The natural question, therefore, is, whether we could avoid the curse of dimensionality by properly estimating the pæ together with PA- The answer no. The problem is that the the theory Section Soctionnalreado aaready implicitly works with the estimate of pn in a form of PA. The theory would work also with any other estimate of pn- Assuming constant pn, instead of constant pa, as we did in Section will, therefore, yield the same conclusions. Moreover, there is neither theoretical, nor practical reason, why should pg decrease with increasing dimension.
This insight even applies to the question of the usage of input-dependent RS in practice. The sumption PB = 1 PA is no more important in Section3thha Section Therefore, we can apply method also for the PB obtained directly by Monte-Carlo sampling for the class B (or by any other estimation method).
C CONCURRENT WORK
As we mention in Section the idea to use input-dependent RS is not new. It has popped out in years 2020 and 2021 in at least four works from three completely distinct groups of authors, even though none of these works has been successfully published yet. We find it necessary to comment on all of these works because of two orthogonal reasons. First, it is good practice to compare work with the concurrent work to see what are pros and cons of these similar approaches and to what extend the approaches differ. Second, which are not mathematically valid. We find this to be a particularly critical problem in a domain such certifiable robustness, which is by definition based on rigorous, mathematical certifications.
are convinced, that three of these four works claim results,
C.1 THE WORK OF WANG ET AL. 2021
This work, submitted for the ICLR conference 2021 is the only work that seems to be mathematically functional. In this work, authors have two main contributions first, they propose two-phase training. where in the second phase, for each sample z;, roughly the optimal d; is being found and then this sample 2; is being augmented with this d; as an augmentation standard deviation. Authors call this method pretrain to finetune. Second, they provide specific version of input-dependent RS. Essentially, they try to overcome the mathematical problems connected to the usage of non- constant a (zx) by splitting the input space in so called robust regions R,, where the constant Ø, is guaranteed to be used. All the certified balls are guaranteed to lie within just one these robust regions, making sure that within one certified region, constant level of is used. Authors test this method on CIFAR10 and MNIST and show, that the method can outperform existing state-of-the-an approaches, mainly the more complex CIFAR10 dataset.
However, we make several points, which make the results of this work, as well as the proposed method less impressive:
24

---

Under review as a conference paper at ICLR 2022
The computational complexity of both their train-time and test-time algorithms seems to be quite high.
The final smoothed classifier depends on the order of the incoming samples. As a conse- quence, it is not clear, whether the method works well for any permutation of the would- tested samples. This creates another adversarial attack possibility to attack the final smoothed classifier by manipulating the test set that the order of samples is inappropriate for the good functionality of the final smoothed classifier.
Even more, the fact, that the smoothed classifier depends on the order of the would-be tested samples makes it necessary. that the same smoothed classifier is used all the time for some test session approve entry real-world applications. For instance, a camera recognizing faces high-security building would need keep the same model for its whole functional life, because restarting the model would enable attackers to create attacks the predictions from the previous session. This might lead to significant restrictions the practical usability of this method.
C.2 THE WORKS OF ALFARRA ET AL. (2200) AND EIRAS ET AL. 2021
In these works, similarly as the work of Chen et al. (2021), authors suggest to optimize in each test point v for such a (x:), that maximizes the certified radius given by Zhai et al. 2020), which is an extension of Cohen et al. (2019)'s 's certified radius for soft smoothing. The optimization for (xx) differs but is similar some respect (as will be discussed).
Besides, all three works further propose -nput-dependent training procedure, for which o(x) the standard deviation of gaussian data augmentation is also optimized. Altogether, both authors claim strong improvements over all the previous impactful works like Cohen et al. (2019); Zhai et al. 2020 [Salman et al. (2019). The only significant difference between the works of farra et al. 2020) and Eiras et al. (2021) I (which have strong author intersections) is that in [Eiaa et al. (2021), authors build upon [lfarra al. (2020)ss work and move from the isotropic smoothing to the smoothing with some specific anisotropic distributions.
As mentioned, authors first deviate from the setup Cohen et al. (2019) and turn to the setup introduced by Zhai et al. (2020), i.c. they use soft smoothed classifier G defined as
Gr(z)c = 1A + +8cc.
The key property of soft smoothed classifiers is that the Cohen et (2019)'s result on certified radius holds for them too.
Theorem 16 (certified radius for soft smoothed classifiers). Let G' be the soft smoothed probability predictor. Let be s.t.
G(x)a 2 EA EB 2 G(z)
Then, the smoothed classifier is robust at x with radius
R = ( ( ( --- -- (EA) + 1 EB))
where 4- denotes the quantile function of standard normal distribution.
Proof. Is provided Zhai al. 2020
Note, that it is, similarly in the hard randomized smoothing version of this theorem, essential to provide lower and upper confidence bounds for G(xz) and G(z) otherwise we cannot use this theorem with the required probability that the certified radius valid. Denote G(x, a) to be the soft smoothed classifier using in z. Authors propose to use the following theoretical (zz) function:
(x) = arg max ( (GG(I, (())))) - -- 7>0 2
(2)
is course not possible to optimize for this particular function since it not known. It also not feasible run the Monte-Carlo sampling for each Ø, because that is too costly and moreover due
25

---

Under review as a conference paper at ICLR 2022
Algorithm Data dependent certification (Alfarra et al. 2020) 80 M, K):
function OPTIMIZESIGMACE for k = O..... K do sample 81..... 8as -N(0,1) I)
((ax) M Σ F(x + oō,)
(a((K) = maxe @00R)c
Eg(Ok) = maxc4A @(Tx)c
R((x)) = 3t ( -- (f-((())))))
0k+1 + -V., R(ak)
o² = OK return o"
stochasticity, it would lead discontinuous function. Treatment of this problem is probably the most pronounced difference between the works Alfarra et al. (2020) and[Cen et al. (202T)
Alfarra et al. (2020) the following easy observation: (N(0, x r) (0 T). Assume have
,, (1, ... 3) be i.i.d. sample from (0, I). Obviously, (x)) ~ + P(x F(x+
E
since this is just the empirical mean of the theoretical expectation. Then, Expression can be approximated as:
M F(x F(x+oo;)))
M Σ F(x + +
σ (xx) arg max e>0
Φ-1
-
Φ-1
(3)
2
M
M
Here, M is the number of Monte-Carte samplings used to approximate this function. Note, that this function is random realization of stochastic process which is driven by the stochasticity in the sample d;, i E . MY To find the maximum of this function, authors furhter propose to use simple gradient ascent, which is possible due to the simple differentiable form of Expression 3 This differentiability is one of the main motivations to switch from hard to soft randomized smoothing. Now, we are able to state the exact optimization algorithm Alfarra et al.) (2020):
Note, that being done in this way, this algorithm can be viewed as stochastic gradient ascent. After obtaining a² = a<x), authors further run the Monte-Carla sampling to estimate the certified radius exactly as in Cohen et al. (2019), but with or (zx) instead of some global Using this algorithm, authors achieve significant improvement over the Cohen et al. (2019)'s ss results, particularly getting rid of the first problem mentioned in Appendix A the truncation issue. For the results, we refer to Alfarra et al. (020)) We will now give several comments on this algorithm and this method.
To begin with, in this optimization, authors do not adjust the estimated expectations and therefore don't use lower confidence bounds, but rather raw estimates. This not incorrect, since these estimates
used directly for the estimation of certified radius, but it is inconsistent with the resulting estimation. In other words, authors optimize for a slightly different function than they then use. The difference is, however, not very big apart from extreme values of EA, where the difference might be really significant.
To overcome slightly this inconsistence, authors further (without comment) use clamping of the (a())) and (B( on the interval [0.02, 0.98]. Le. if (A( > 0.98, it will be set 0.98 and this is also taken into account in the computation of gradients. This way, authors get rid of the inconvenient issue, that if G(z) 1, then (x(Ox) ~ 1 for big value of t (ÉA(())))) yielding strong inconsistency with what would be obtained, if lower confidence bound was used instead.
O, what might cause very
However, the clamping causes even stronger inconsistence in the end. Note, that if G(z) 1, then the true value of (ox) would be really close to 1, yielding high values of & (o))), This value would be far better approximated by the lower confidence bound than with the clamping, since
26

---

As we have seen in previous paragraphs, the resulting (x) yielded in Algorithm Dis very instable and stochastic- it depends heavily on F, do. K, B, M and of course 5;, E {1...., M} for each iteration of the for cycle. Now, for instance for CIFARIU 10 and PA = 0.99, we have the minimal Under review as a conference paper at ICLR 2022
the lower confidence bound of 1 for M 100000 and a 0.001 is more than 0.9999, while the clamped value is just 0.98. This makes small values of a highly disadvantageous, since - 0 as + 0. yet Φ (E)(())) is being stuck on $ = In other words, this way authors artificially force the resulting (x) to be big enough, s.t. (x)())) & 0.98. This assumption is not commented in the article and might result in intransparent behaviour.
Second of all, authors use M = 1 for their experiments. This can be interpreted as using batch size 1 in classical SGD. We suppose that this small batch size is suboptimal since it yields an insanely high variance of the gradient.
Third of all, during the search for (x), it is not taken into account, whether the prediction is correct or not. This is, of course, a scientifically correct approach, since we cannot look at the label of the test sample before the very final evaluation. However, it is also problematic, since the function in Expression 2 might attain its optimum in such a (I)), which leads to misclassification. This could have been avoided if constant a was used instead.
To further illustrate this issue, assume F(x) (0)), i.e. F(x) predicts class 1 if and only if |a||| < 1. otherwise predicts class O. Assume we are certifying x = and assume that do in Algorithm M is initialized such that class 0 is already dominating. Then, we will have positive gradient Vo R(ax) in all steps, because F(aō;) is obviously non-increasing, so the number of points classified as class 1 for fixed sample 6,, é E 1,..., M is decreasing, yielding (x(()) non- decreasing in oh, while de strictly increasing in Øg- This way, the a% will diverge to for k - 2 However, point r = 0 is classified as class 1, yielding misclassification which is, moreover, assigned very high certified radius.
This issue is actually even more general - the function in Expression 2 does in most cases (assuming infinite region RR-N) not possess global maximum, because usually
lim ( (G(z, - (G(zz, (x)) = oc. 70c 2
This can be seen, for instance, easily for the F(x) B (0)), but it is the case for any hard classifier, for which one region becomes to have dominating area as the radius around some To goes to infinity. This is because, some region becomes be dominating (for instance if all other regions are bounded), then & grows, while Φ- (G(x, (x))a) t (G(r, (x)))) B) either grows too, or stagnates, making the whole function strictly increasing with sufficiently high slope.
This issue also throws the hyperparameter K under closer inspection. What is the effect of this hy- perparameter on the performance of the algorithm? From the previous paragraph, it seems, that this parameter serves not only as the scaled number of epochs", but also some stability parameter, which, however, does not have theoretical, but rather practical justification.
Another issue is, that the function in Expression 2 might be non-convex and might possess many different local minima, from which not all (or rather just a few) are actually reasonable. Therefore, the Algorithm is very sensitive initialization do-
However, probably the biggest issue of all is connected to the impossibility result showed in Sec- tion 2 which shows, that the Algorithm [ actuully yields invalid certified radiuses. Why it is so?
First of all, we must justify, that our impossibility result is applicable also for the soft randomized smoothing. This is because elassifiers of type F(x)c 1(x E Rc) for Re being decision region for class C' are among applicable classifiers s.t. G(r,a)A = E With such classifiers, however, there is no difference between soft and hard smoothing and moreover F = PA from our setup. This way we can construct the worst-case classifiers F* exactly as in our setup and therefore the same worst- case classifiers and subsequent adversarial examples are applicable here as well. In other words, for fixed value of soft smoothed G(z, d) = EA we can denote PA EA and find the worst-case hard classifier F defined as indicator of the worst-case ball, which will yield Eg = (B) from Theorem 3 in some queried point .11-
possible ratio equal to more than 0.96. It is hard to believe, that such instable, highly stochastic and nogulaguld (except for K, () method will yield (xr) sufficiently slowly varying such that
27

---

Under review as a conference paper at ICLR 2022
Certified radius according to Alfarra et. al.'s optimization
400
350
certified radius
300
250
20
60
100
0
The theoretical certified radius in Expression The function is monotonically in- creasing on interval [0, 100) and will further be increasing too.
Figure 14:
within the certified radius around zo. there will be no Ii for which on deviates more than by this strict threshold from do- This is even more pronounced on ImageNet, where the minimal possible ratio @a above 0.99 for any PA or Eg. do
Even without the help of curse of dimensionality, algorithm will not yield valid certified radius. Assume again F(x) = 1(B, (0) and assume modest dimension N Assume we try certify point To [50, Oj. Then, the theoretical o-dependent
construct counterexample for which the
function from Equation is depicted on Figure 14
We see, that the resulting (1)) will be as big our regularizers K and in Algorithm will allow. Therefore, if we run the algorithm for K high-enough. surely the resulting certified radius will be far bigger than 50. However, if we certify the point x = [0, 0] and we start with do 0.25, for instance, then the o-dependent certified radius in Expression [ will be decreasing in this do. yielding (xx) < 0.25, which will result in classification of class This point [0, 0) lies within the "certified" range of [50, OJ. yet it is not classified the same, because, obviously, [50. 0] is classified as class This is therefore a counterexample to the validity of Alfarra et al. (2020)'s certification method and their results.
Note that even though our counterexample a bit "extreme" and one could argue that in practice such situation would not occur, we must emphasize, that this counterexample is constructed even without the help of the curse dimensionality. In practice, fully suffices, that for zo and some certified radius R in To. there exists 21 within the range of this certified radius, s.t. di is quite dissimilar to op- such situation occurs, then R surely is not a valid certified radius.
C.3 THE WORK OF CHEN ET AL. 2021
The methodology Chen al. 2022 is rather similar to that Alfarra et al. (2020). The biggest difference consists in the optimization of Expression 2
Instead of stochastic gradient descent, they use more sophisticated version of grid search so called multiplesttart fast gradient sign search. Simply speaking, this method first generates set of pairs (0o, 8 E (1....: K) it increases o oū js to o² of + (j + 1)s and checks, whether the a o-dependent empirical certified radius in Expression 3 lincreases or not. yes, they continue until j is above some threshold T. if not, they break and report 0; the o, from the inner step where while cycle was broken. After obtaining o; for E (1...., K). they choose (x) to be the one, that maximizes Expression More concretely, their multiple start fast gradient sign search algorithm looks follows:
} and then for each of the runs, it runs j-while cycle, where each step j.
not entirely clear from the text of Chen et al. (202I), how exactly are 4e, Sy sampled, but is written there, that the interval for 1 is 16] and for it is (11,1). Moreover, the authors don't ton't
28

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Instance-wise multiple-start FGSS (Chen et al. 2021)
function OPTIMIZESIGMACE 2, do, M, K,TY
generate (4,, 2,,k E {1, [L,...,K} for l: 1,.... ... do
sample .,,.... 8M ~ ~N(0,
M
1 Σ
F(x+ +()
M
i=1
BA(vTT = maxc @5 VT
R(V(+00) = V4 -1 (EA(v(RO)))
my = R(v[400))
while 4 E [1.T] do
sample 51, 51,...,5N ~ [0, (1e + 1x)o
M
② V1 + 8000) = M
1
Σ
F(x + 6:)
==1
Ea(v + 0000) maxe Φl U + SRO0NC
R(vl, 1/2 + 8400) = VT + $0 I (Ex skoo))
if R( [n + 5400) R( (R()THoO) then
4 f 1k +
mk R(vlx 1+= SkOO)
else
break
a(x) = max m
kE(L....
return (xx
provide the code and from the text, it seems, that they don't use lower confidence bounds during the evaluation of certified radiuses, what we consider to be a serious mistake (if really the case). However, we add some comments to this method regardless of the lower confidence bounds.
Generally, this method possesses most of the disadvantages mentioned in Section C.2 They use the same function for optimization, the Expression 2 and its empirical version 3 This means, that the method suffers from having several local optima, having no global optimum in general (and in most cases with limit infinity). Similarly like before, here is also no control over the correctness of the prediction, i.e. many or all local optima might lead to misclassification.
On the other hand, in this paper authors M 500 (the effective batch size), which is definitely more reasonable than M = 1 as in Alfarra et al. (2020). Furthermore, they use multiple initializa- tions, making the optimization more robust and improving the chances obtain global, or least very good local minimum.
However, the main problem, the curse of dimensionality yielding invalid results nounced here. Unlike the "continuous approach" in Alfarra et al. (2020), here authors for each wo sample just some discrete grid (more complex, since there are more initializations) of possible val- ues of (xx). For instance, if s 1, then the smallest possible ratio between two consecutive I's in the Algorithm i 115/4- ~ 0.97, making it impossible to certify some 21 w.r.t. if for both and L + I on ImageNet and also for a of samples on CIFAR 10. Of course, the fact that is randomly sampled from (-1, 1) makes this counter-aggumentation more difficult, but it is, again, highly unlikely that this highly stochastic method without control over (zx) would yield function with sufficiently small semi-elasticity. Therefore also the impressive results of Chen et al. (2021) are, unfortunately, scientifically invalid.
more pro-
D IMPLEMENTATION DETAILS
Even though our algorithm is rather easy, there are some perks that should be discussed before one safely use it in practice. First, show the actual Algorithm
29

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Pseudocode for certification and prediction of my method based on Cohen et al. (2019)
evaluate g at zo
function PREDICT(F, Go, 2o. a)):
counts + SampleUnderNoise(, zu, n, da)
ČA,CB CB t two top indices in counts
n1,, f f counts(cx), counts(èn)
if BinomPValue(
nn, 0.5) S a then return d^
else return ABSTAIN
certify the robustness of g around To
function CERTIFY do, To, no, n. at):
counts0 - SampleUndderooise(f,
roo, σo)
č top index in counts0
counts + SampleUnderNNoise
σo)
PA LowerConiBound counts [Ca]: n, a)
PA
1/2 then return
prediction
and radius
CompueCCrtiieeRRaaluuuno N, PAP num step)
else return ABSTAIN
function COMPUTECCERTHEDDRADIUUSSTOO r, PA. PA. stepsteps)
radiuses linspace(nummspace))
for R in radiuses do
01 0o exp(-rR) T12 f do exp(rR) xi xi.lower
+ &
+ (11,
if biggger, xin loweer) > 0.5 then BREAK
return
Note that the function ComputeCert ifidrdiddiss a bit more complicated than depicted in Algorithm We don't use simple for-loop, but rather quite efficient search method.
Theoretically speaking, this algorithm works perfectly. However, in practice, it is a bit problem- atic. The issue is, that since use σ11 and 012, which are extremely close to dp for small tested radiuses R, the NCCHSQ functions will get extremely high inputs, making the results numerically instable. To prevent this, evaluation at particular distance R. the worse for us, we can prevent numerical issues simply by putting o, do and σT > do be maximal and minimal used a's in our evaluation, i.c. the true used will be min(or, ao exp(-rIt) and max(or, do exp(r Rt). This way, we avoid nu- merical issues, because we can put de, OT to be s.t. og og-o? is not too big and in the same time maintainting the correct certification thanks to the Lemma 6 The problems of this workarounds are first that it decreases the certification power, since it assumes oi ''s that are even worse than the theoretically guaranteed worst-case possibilities and second, more importantly, that it requires some engineering to design the dz, or designs.
simple trick. Since the
extreme d will assume in
submoptimal to put one constant value for these thresholds, because the numerical problems occur at different ratio thresholds of a /ao for different class probabilities pa and the dimension N. This requires to design specific (p(AA) and or (P(A)) functions for each dimension N which we want to apply. For instance, we use (p.) = 0.9993 + 0.001 (pF), and (T(PA) = 1/or(P4) for CIFARIO, while for MNIST we use o, (pa) = 0.9988 0.001 (Pg))(BB), and (T(4s) = 1/ar(pA). To design such functions, one needs to plot plot.real_probab..
wtt.ees...a...o..iaii.... fune- tion, which computes the g functions, for particular N and several values of PA and look, whether it computes correctly. As example, provide such plots for well and ill working setups Figure 13
Another performance trick is not evaluate for each R, where R, is i-th grid point of evaluation, but rather evaluate sequentially Rşa, i.e. just every -- point, until we reach value > 0.5 and then search just the interval [(i 1,,,, 12), where is the first iteration for which & (R,e, 01) 2 0.5.
30

---

Under review as a conference paper at ICLR 2022
probabbiiiy
probability 784, 0.03)
(1.
7E4, 0.0313
1.0
boundary
certificaaion threchafd
0.5
0.-
gobsbiitt
0.5
02-
the true. 0.0-0.01 Dic inter soundo
cortiication thres 4dd
Figure 13: Well and ill working function
www.reeelpobbbbliteeteeo wttpllittyoo..aaallllaaaammaaa.e www.ih.fiieed.vrianeeee.e.e of which computes the & functions. The coding is [oo, N,
E MORE TO EXPERIEMNTS AND ABLATIONS
Before we present our further results, we must emphasize that our certification procedure is barely any slower than that of Cohen et al. (001)). More specifically, given 100000 iterations of monte- carlo sampling, certification of one sample using Cohen et al.] (2019)'s algorithm CIFAR10 takes ~ 15 seconds on our machine, while certification of a sample using our Algorithm 3 takes 15- - 20 seconds depending
the σb, r setup. If least of σ and is small, then method runs practically instantly. If both parameters are small, then one evaluation can take up to 5 seconds depending on the exact value of parameters and on the PA- Note, that this part of the certification is ianeeessioondddeedeeeen and therefore can run in the same time also on much higher-dimensionn problems.
Besides the actual certification, we have to compute (r) for each of the test examples. This part of the algorithm being executed before the actual certification and usually takes around minute on our machine and on CIFAR10.
All in all, even in the really worst-case scenario, our method runs at most 1/3-times longer than the old method on CIFAR10. On MNIST, the ratio between our run and the original run is higher, since MNIST is smaller-dimensional problem. However, since our part of evaluation is practically independent of the setup (except the values of and which, however, yield just some upper- bounded amount of slow-down), our algorithm does not bring any added asymptotic time complex- ity.
E. HOW TO CHOOSE THE HYPERPARAMETERS
Our design of (x)) function defined in Equation uses several hyperparameters. These are: r for the rate, for the scaling, db for the base sigma and ls for the k-nearest neighbors. How do we choose these hyperparameters?
The m parameter depends on our goals. We can set that (ι) achieves lowest values at σ by setting it so that it is roughly equal to the minimal distance from & nearest neighbors across, for instance, training samples. Other possibility is to set so that roughly equal to the average distance from & nearest neighbors, to ensure that the average (xx) will roughly correspond to the db-
The k parameter needs to be set with two objectives in mind. Firstly, it would be unwise set it too small, because then the distance from l nearest neighbors would be too noisy. On the other hand, we don't don't want it too high, because then it will not be changing fast enough with changing the position of x. The suitable value can obtained by looking at histograms of average distances from nearest neighbors and choosing the for which the histogram is enough scattered, but it is not small.
31

---

Under review as a conference paper at ICLR 2022
CIFAR-10 Gohen
0.12
CIFAR-10, Cohan al's models, 0.25
CIFAR-10 Cohan
Loten U-1.222
(ueen 0.25
Cultaru
th, ew net-0.006
o 0.25 mard 205
Ua - mile0.005
th 0.22. 08a-0001
d maae21
rite
centfed socurny
64
04
04
60
0.1
0.
0.3
0.4
3.5
266
00
02
04
0.6
0.2
0.00
0.25
0.30
0.75
1.55
125
1.30
1.75
2.00
Figure 16: Comparison of certified accuracy plots for Cohen et al. (2019) and our work. For each plot, the same base model f is used for evaluation.
0
0.12
0.25
0.50
r
0.00
0.831
0.766
0.658
J 0.005
0.830
0.766
0.654
0.01
0.828
0.762
0.649
r 0.015
0.826
Table 6: Clean accuracies for Cohen's models and our non-constant a (z) models.
0.12
σ = 0.25
=
0.50
0.00
0.084
0.108
0.131
r 0.005
0,086
0.112
0.135
r 0.01
0.088
0.119
0.142
Table 7: Standard deviations of class-wise accuracies for different levels of a and r.
The r parameter needs be chosen so that we can have some significant advantage over constant smoothing, but it cannot be too big, because otherwise the curse of dimensionality would apply. The value can decided either by trial and error, by plotting the certified radius given linear elassifier, or from Theorem 4 setting the rate low-enough so that within the expected certified radius range, the ratio E can't 't move anywhere near the theoretical thresholds implied by Theorem 4
The dg the base and should be used according the level of smoothing variance we want to use. More discussion on this can be found in Cohen et al. (019
E.2 COMPARISON WITHI COIIEN ET AL. 2019) METHODOLOGY ON CIFARIO DATASETS
Here, we compare Cohen et al. (2019) 's evaluations for a 0.12, 0.25,..000.50 with our evaluations
directly on models trained by Cohen al. (2019), setting σ; a, 0.005, 0.01 and 0.015 for σb = σ 0.12. & = 20 and m 5. In this way. the levels of (z) used in direct comparison will rise from the values roughly equal to Cohen et al. (2019)'s constant to higher values. The results are depicted in Figure [6
Note, that this evaluation being done on the models trained directly by Cohen et al. (2019) and therefore the variance of Gaussian data augmentation is not entirely consistent with the optimal variance that should be used for non-constant a,, which should be either the same, (xx) or constant, but in average equal to (x)) The results are similar in the Section 4 Note, that for σb o = 0.50, the curse of dimensionality becomes most pronounced, as explained in Appendix Further, provide the Tables 6 7 where the clean accuracies and class-wise standard deviations are displayed.
The results are, again, similar in the section
32

---

Under review as a conference paper at ICLR 2022
comperison
MNIST. comperison,
COFT Fed SOCA
044
amib Use 8.22, mo0s, p0100
Us 0.22
0.25 amv0
0.50, -000), 3m10
Us om 0.23 (m0.00 um66
Une 2.50, m4000 31i60
Borr mons, aribid
Usrt
0.50, mout,
60
641
02
0.3
2.5 2.6
0.0 04 06
0.8
0.20
0.25
0.30
0.75
1.0
125
1:30
1.75
2000
Figure 17: Comparison of certified accuracy plots for Cohen al. (2019) and our work. MNIST. For each plot, the same base model f is used for evaluation. The term irr stands for train-time rate, will be discussed later and can be ignored now.
0.12
0.25
0.50
r
0.00
0.9913
0.9910
0.9888
F
0.005
0,9914
0.9912
0.9885
r
0.01
0.9914
0.9910
0.9887
r 0.02
0.9914
0.9912
0.9876
0.05
0.9914
0.9906
0.9836
Table 8: Clean accuracies for Cohen's 's models and our non-constant (xx)
models on MNIST.
0.12
σ = 0.25
=
0.50
0.00
0.677
0.729
0.909
r
0.005
0.659
0.735
0.905
r 0.01
0.659
0.722
0.9318
0.02
0.659
0.713
0.960
0.05
0.715
0.796
1.159
Table 9: Standard deviations of class-wise accuracies for different levels of and r. The printed values are multiples of 100 of the real standard deviations.
E.3 COMPARISON WITH COHEN ET AL.. 2019
METHODOLOGY ON MNIST DATASETS
Here, present similar comparison as in Subsection
E.2 but on MNIST and with models trained
0.12, 0.25, 0.50 with 0.005, 0.01, 0.02, 0.05 and train-time level of again equal to o O3. It is important to note, that we use different normalization constant m in the MNIST case. In CIFARIO. we set m 5, MNIST, the suitable m 1.5. This way we assure, that the smallest a (xx) values in the test set will roughly equal the ag a. The certified accuracy plots are depicted on Figure 17 We also add the clean accuracy table and class-wisc clean accuracies standard deviation table (
by us. Again, the setup is similar as in the Section 4 We compare
test-time rates
All the results are, again, very similar to those presented in Section even though the gain in certified accuracies is marginally worse, since our evaluations run on models trained with average smaller train-time time lata-augmentttion standard deviation d
E.4 INVESTIGATION OF THE EFFECT OF TRAINING WITH INPUT- INPUT-DEPENDENT GAUSSIAN AUGMENATATION
It has been shown by many works, that apart from good test-time certification method, also the appropriate training plays a very important role in the final robustness of our smoothed classifier g. Already Cohen et al. (2019) realize this and propose train with gaussian data augmentation with constant σ. They experiment with different levels with the same level of that will be later used in the test time is usually the most suitable option.
during training and conclude that training
33

---

Under review as a conference paper at ICLR 2022
CIFAR-10, my treining,
CIFAR-10. my training. 0.25
CIFAR-10. my training.
Med 0.12 mm00 3000
Ve e--025 má amd Ve on 2.25 (i) and Me ow02. 35, ow-
gig 50 aed
Med 0.12, m600 areor
Ve ciu 50 mi and be
Medd- 12, moon you7
m000 2000
ow and
oettre 9000
04
62
00
0.1
0.
0.3
0.4
3.5
26
00
02
04
06
0.2
0.30
0.25
0.50
0.75
1.5
125
1.30
1.75
2.00
Figure 18: The certified accuracies of our procedure on CIFARIO for σb 0.12, 0.50, rate r = 0.01 and training rate trr = 0.0, 0.01, 0.04, 0.1.
The question of best-possible training to boost the certified robustness didn't 't stay without the in- terest of different researchers. Both Zhai et al. (2020) and Salman et al. (2019) try to improve the way of training and propose two different, yet interesting and effective training methods. While Zhai et al.] (2020) manage to incorporate the adversarial robustness into the training loss function, therefore training directly for the robustness, (Salman al. (2019) propose use adversarial training to achieve more robust classifiers.
Both Alfarra al. (2020) and et al. (202T) already propose use training with input-dependent a as the variance of gaussian data augmentation. Both of them proceed similarly as during test time to obtain training (Ix), they optimize for such, that would maximize the certified accuracy of training samples.
In this section, we propose and test our own training method. We propose to use again gaussian data augmentation with input-dependent (x)) but we suggest to use the simple (I)) defined in Equation 1 other words, we suggest using the same (I) during training as during testing (up to parametrization, which might differ).
Note, that, unlike the certification, the training procedure does not require any mathematical analysis nor certification. It is totally up to us how we train the base classifier ff and the way of training does not influence the validity of subsequent certification guarantees during test time. However, is good to have reasonable training procedure, because otherwise, we would achieve a satisfactory model neither in terms of clean accuracy nor in terms of adversarial robustness.
In the subsequent analysis, evaluate and compare certification procedures on models trained with different training parametrizations. For this particular section, we run the comparison only on the CIFAR10 dataset. For each test-time db, r, we evaluate our method with these parameters base models f trained with the same db. but different level of training rate trr. The training rate trr plays exactly the same role as the evaluation rate r but is used exclusively during training. Note, that this makes our (I) different during training and testing since it is parametrized with different rates.
On the Figure 18 we plot evaluations on CIFARIO of our method for rate 0.01, all levels of o = 0.12, 0.25, 0.50 and each of these test-time setups is evaluated on 4 different levels of train-time rate trr = 0.0, 0.01, 0.04, 0.1.
From the results, we judge, that our training procedure works satisfactorily well. It can generally outperform the constant training, yet the standard accuracy vs. robustness trade-off is present in some cases. If we train with small train-time rate, the improvement of the certified accuracies is not pronounced (the case for a = just a result of the variance of clean accuracy w.r.t different traning runs) enough, but we also don't lose almost any clean accuracy. Increasing the rate to trr 0.04 results in much more pronounced improvements in high certified accuracies, yet also comes at a prize of clean accuracy drop, especially for large levels. Even bigger training rate, such trr = 0.1 seems be too big and does not bring almost any improvement over the rate trr = 0.04, yet loses a large amount of clean accuracy.
0.50 is slightly misleading, since such configuration
These results suggest, that the input-dependent training with a carefully chosen training rate for (x) can lead to significant improvements in certifiable robustness. However, it is important note, that
34

---

Under review as a conference paper at ICLR 2022
0.12
0.25
0.50
trr 0.00
0.084
0.107
0.153
trr 0.01
0.078
0.099
0.126
lrr 0.04
0.068
0.081
0.117
Irr 0.1
0.088
0.099
0.230
Table 10: Standard deviations of class-wise accuracies for different levels of a and trr, under con- stant rate r 0.01.
the optimal trr seems to be dependent the σs, therefore for each value of σb, some effort has to be invested to find the optimal hyperparameters.
Besides, we were also interested, whether using input-dependent (xx) during training influences the wise accuracy balance. In Table T0 we report the standard deviations of class-wise accura- cies.
We can observe, that unlike the pure input-dependent evaluation, the input-dependent training is partially capable of mitigating the effects of the shrinking. For instance, the trr 0.04 for Ø 0.12 provides obvious improvement in establishing class-wise balance. Similarly successful are trainings with Irr 0.01 for σ 0.12 and both Irr 0.01, 0.04 for o 0.25. Also for = 0.50 the mitigation is present for small-enough training rates. However, we must emphasize, that if we use big training rate, the disbalance between class accuracies will be re-established and in some cases even magnified. Therefore, we must be careful to choose the appropriate training rate for the 0b, r.
E.5 WHY DO WE NOT COMPARE WITH THE CURRENT STATE-OF-THE-A
could, but don't consider it necessary. Since we claim just one type of improvement over the Cohen et al. (2019)'s 's model (experiment-wist) and don't 't claim new state-of- the-art training method, we didn t find necessary to measure our strengths with methods of Salman et al. (2019) and Zhai et al. (2020). It is obvious that we would outperform these methods in the question of certified accuracy waterfalls anyway, since these methods focus on the training phase. Since we do not outperform Cohen et al. (2019) neither in terms of the clean accuracies nor in terms of class-wise accuracies, is not our belief that we would outperform the two modern methods in these metrics. Moreover, we find the comparison with Cohen et al. (2019) most structured, since extend the theory built by them.
Briefly speaking
E.6 ABLATIONS
Even though our results so far might look impressive, we can't claim that it is fully due our particular method until we exclude the possibility, that some different effects play an essential role the improvement over[Coher et al. (2019)'s 's work.
To investigate, whether our particular method dominates the contribution to the performance boost, we conduct several ablation studies first, we study the variance our evaluations and trainings, second, we study the effect of input-dependent test-time randomized smoothing, and third, we study the effect of input-dependent trai-time data augmentation.
E. VARIANCE THE EVALUATION
To find out, whether there a significant variance in the evaluation of certified radiuses, we conduct simple experiment- train single model on CIFARI0 and evaluate our method this model for the very same setup of parameters multiple times. This way, the only present stochasticity is in the Monte-Carke sampling, which influences the evaluation of certified radiuses. We pick the parameters as follows: d₁ = 0.50, r = 0.01, trr = 0.0, since the ag = 0.50 turns out to have biggest variance in the training. The results are depicted in Figure 19
From the results, it is obvious that the variance in the evaluation phase absolutely negotiable. Therefore, there is need to the same evaluation setup more times.
35

---

Under review as a conference paper at ICLR 2022
CIFAR-10, the same setups, 0 = 0.50
1.0
Me 0.50, r-0 01, mm-000 run,
01, mm-00. min
0.50, m0 tm00000000000000000m 2in_2
0.8
Me o 0.50 m0 01, bm=0.00
Cartified accuracy
--000-000000000000000000000 01, tm-0000000000000000000000000
Me or 0.50 m0 01. tm000.0000...000000m0000000m.000 min_
0.6
0.4
0.2
0.0
0.00
0.25
0.50
0.75
1.00
1.75
2.00
radius
Figure 19: The variance of evaluation. Parameters σ 0.50, 0.01, trr 0.0, the evaluated model is the same for runs. There are 7 runs on CIFAR1O.
CIFAR-10, same setups, 0.12
CIFAR-10, the same sotups, 0.25
CIFAR-13, same setup6, 0.50
10
0/
08
and
0.
0.
0.5
roct ania
oertee
0.29
Figure 20: The certified accuracies of our procedure CIFARIO for = 0.12, 0.25, 0.50, rate r 0.01 and training rate trr = 0.0 evaluated on 9 different trained models for each of the setups.
0.12
0.25
0.50
accuracy
0.61%
0.40%
1.86%
abstention rate
0.17%
0.34%
0.59%
misclassification rate
0.60%
0.24%
1.48%
Table 11:
Standard deviations clean accuracies, abstention rates and misclassification rates for runs of each parameter configuration on CIFAR10.
E.6.2 VARIANCE THE TRAINING
To estimate the variance of the training, we train several models for one specific training setup and evaluate them with the same evaluation setup (knowing, that there is no variance in the eval- uation phase, this is equivalent to measuring directly the training variance). We pick our classical non-constant (xx) for the evaluation, but we train with constant variance data augmentation. The concrete parameters we work with are: trainings for each of these parameter configurations. Then we run full certification to not only see the variance in clean accuracy, but also the variance in the certified radiuses. The results are depicted in Figure 20
(0.12, 0.25, 0.50), = 0.01, /rr = 0.0 and we run
From the figures we that the variance of the training is strongly on-dependent. Most volatile clean accuracy is present for the case σ, = 0.50. However, fortunately, the biggest variability is present for the clean accuracy and the curves fied radiuses. The concrete standard deviations of clean accuracies are Table [T] The standard deviations of clean accuracies for MNIST dataset and the same parameters in Table 12
to be less scattered in the areas of high certi-
36

---

Under review as a conference paper at ICLR 2022
0.12
0.25
0.50
accuracy
0.036%
0.042%
0.044%
abstention rate
0.037%
0.027%
0.058%
misclassification rate
0.043%
0.029%
0.021%
Standard deviations of clean accuracies, abstention rates and misclassification rates for 8 runs of each parameter configuration on MNIST.
Table 12:
Since the differences in accuracies of different methods very subtle, it is hard to obtain statisti- cally trustworthy results. For instance, given, that the standard deviation 0.4% is the true standard deviation of the 76 0.25 runs, would need 16 runs decrease it to standard deviation of 0.1%. which might be considered to be precise-enough. To do the same in the case of σ 0.50 on CIFARIO, we would roughly need 400 runs to decrease the standard deviation below 0.1%. There- fore, the results we provide in the subsequent subsections, being the average of "just" runs, have be taken just modulo variance in the results, which might still be considerable.
E.6.3 EFFECT
EVALUATION
In this ablation study, we compare the certification method particular db, 0.01, Irr 0.0 with the constant-o certification method with Cos, r 0.0, Irr = 0.0, where C is an appropriate constant. The motivation behind such an experiment is, that our o (xx) is generally bigger than o. but σb evaluation. Therefore, in average, samples
originally, compare this method constant in our method enjoy bigger values of (z). Natural question is, whether we cannot obtain the same performance boost using just the constant method with Co. db set to such value, which roughly corresponds to the average of (x;) for x;, f1..... .T) being the test set. The problem of using bigger Cog is, that we encounter performance drop and more severe case of shrinking. but we need to check, to what extent is the performance drop present in the input-dependent a (xr) method. Comparing the performance drops of larger constant Ca,, and input-dependent (zx). which is in average larger (but in average the same as the Co₁), we will be able to answer, to what degree the usage of input-dependent (2) really justified. If we remind ourselves, that
(-
m ))
(3) ab exp
r
Σ M
r.ll 1
(.
then we see, that the constant C' we are searching for is the average (or rather median) value of
exp r
(1(
(
Σ (.EA(())
12-2111
z:ll = -mm
Fortunately, empirically, the mean and median of the above expression are roughly equal for both CIFAR1O and MNIST, so we are not forced to choose between them. For r 0.01, m = 5. choose the rounded value of C exp(0.05) on CIFARIO. For r 0.01, m 1.5 as in MNIST, the constant is set to C = 1.035. In the end, the values of Co used in this experiment are Ca 0.126, 0.263, 0.53 for CIFARIO and Co 0.124, 0.258, 0.517 for MNIST. To obtain fair comparison. though, we evaluate the input-dependee with constant Coş standard deviation of gaussian augmentation. This is because this level of is equal to the mean value of the (z) and we believe, that such training data augmentation standard deviation more consistent with our a (x) function. We provide the plots of single-run evaluations of certified accuracies for CIFARIO in Figure 21 and for MNIST in Figure 22 The models on which we evaluate differ because for the increased constant o evaluations we needed to also use an increased level of the training data augmentation variance.
(z)) evaluation strategy
models trained
From the figures, it is obvious, that our method is not able to outperform the constant a method using the same mean in terms of certified accuracy, not even for strongest σG 0.12. This fact might not be in general bad news, if we demonstrated, that our method suffers from less pronounced accuracy drop less pronounced disbalance in class-wise accuracies. To find out, measure
37

---

Under review as a conference paper at ICLR 2022
CIFAR-10, my treining,
CIFAR-10. my treiningg 0.25
CIFAR-10. my training.
6.22 m0.2, tend 128 Me on 0.126, m330 1m12 die 12, avid
B25 m6.01 mee6.25
pw 50 ta Us on 53 m6 00 srr 0 We o 50 ria 20 wei
Ne 6-283, mo00, smob
Mild 6.25 mit wid
centeed SOCL
0.6
04
04
04
62
00
0.1
0.2
0.3
0.4 2.5 266 00 02
0.4
0.
0.2
0.30
0.25
0.30
0.75
1.55
125
1.30
1.75
200
Figure 21: The certified accuracies of our procedure on CIFARIO for σb 0.12, 0.25, 0.50, rate r = 0.01 and constant, yet increased Co, training variance. compared to certified accuracies of the constant a method for o og 0.12, 0.25, 0.50 and also Co. 0. 0.126, 0.265, 0.53. Evaluated on a single training.
MNIST, main abtation, a 0.12
MNIST, main ab abiation. or 0.25
MNIST, main ablation, a- 0.50
1.0
08
6A
0.6
06
04
Gutic w 12
Golic o 25
Golec a 50
Una (400) 124
Use (16.11 reed
5:30, -4001 29e0.117
0.1
0.20 0.29
125
Figure 22: The certified accuracies of our procedure MNIST for σы 0.12, 0.25, 0.50, rate r = 0.01 and constant, yet increased Co, training variance, compared to certified accuracies of the constant method for σb 0.12, 0.25, 0.50 and also Co. 0.124, 0.258, 0.517. Evaluated on a single training.
a = 0.12
0 0.25
0 = 0.50
0.01, frs increased
0.852
0.780
0.673
r 0.00 classical
0.851
0.792
0.674
0.00 increased
0.853
0.780
0.673
Table 13: Clean accuracies for both input-dependent and constant o evaluation strategies on CI- FAR10.
0.12
0 0.25
σ 0.50
r = 0.01, frs increased
0.076
0.099
0.120
r' 0.00 classical
0.076
0.097
0.122
0.00 increased
0.076
0.101
0.123
Table 14:
Class-wise accuracy standard deviations for both input-dependent and constant o evalua- tion strategies on CIFARIO.
average accuracies of the evaluation strategies from runs for each, as well as average class-wise accuracy standard deviations from 8 runs. The results are provided in Tables 13 and for CIFARI0 and Tables 15 and for MNIST.
As for CIFAR1O, except for a d = 0.25, the differences in accuracies between different evalua- tion strategies are so small, that we cannot consider them to be statistically significant. Even though the difference for = a = 0.25 is high, it is still not possible to draw some definite conclusions, especially for the difference between the input-dependent (I) and the increased constant Co. evaluations. In general, it is not easy to judge, whether our method possesses some advantage (or disadvantage) over the increased Co, method in terms of clean accuracy. Similar conclusions can be drawn in the context of the shrinking phenomenon. Here, the differences also very small, but
38

---

Under review as a conference paper at ICLR 2022
0.12
0.25
0.50
0.01, irs increased
0,9913
0.9905
0.9885
0.00 classical
0,9914
0,9907
0.9886
0.00 increased
0.9914
0.9904
0.9885
Table 15: Clean accuracies for both input-dependent and constant evaluation strategies MNIST.
0.12
0.25
o 0.50
0.01, frs increased
0.00757
0.00798
0.00929
r 0.00 classical
0.00751
0.00778
0.00934
0.00 increased
0.00750
0.00798
0.00925
Table 16: Class-wise accuracy standard deviations for both input-dependent and constant o evalua- tion strategies on MNIST. Printed are multiples of 100 of the real values.
my training,
my training,
training.
lma 0 no and Me u 0.22. H0.1 3nv0
mids ampup
M 6.25 mid mnt.0..mmti ambbo Mico w m6001 in8.01.ttweeatt tww
d -oot 90o00 Meo 0.50. -001, 2a4000
conteed scarthy
04
044
82
02
02
60
01
02
0.3
0.1
3.5
266
60
0.1
0.6 3.8
0.30
625
0.0
0.75
1.01
135
1.0
1.25
2000
10230
Figure 23: The certified radiuses on CIFARIO of the non-constant (xx) method with rate r = 0.01, but different training strategies. Used training strategies are input-dependent training with the same (2) function and constant-o training with either ag or Ca, variance level. Evaluations are being done from single run.
unlike in the comparison with Cohen et al. (2019) models, where we evaluate our input-dependent o (a) method on classifiers trained with inconsistent augteetgmenttiionn variance, here we observe the general trend, that our method is able to outperform the increased constant Co3 evaluation. This good news and confirms our suspicion, that the bad results from Subsection E.2 could come from the train-test inconsistency.
The results on MNIST suggest similar conclusions for accuracy vs. robustness tradeoff. Simi- larly, the σb 0. 12, 0.50 not telling much, and for db 0.25, the differences still rather small (yet the standard deviation of the results should be ~ 0.0001, so it is rather on the edge). The conclusions for the shrinking phenomenon CIFAR1O. Here we don't see any improvement over the constant a, not even the one with increased level.
bit more pesimistic than in the case of
E.6.4 EFFECT OF INPUT-DEPENDENT TRAINING
In this last ablation study, we compare our input-dependent data augmentation for particular db. and particular training rate trr with the constant Ca,, data augmentation, where the training rate trr set to The strategy for choosing the constant Particularly, we evaluate our method with same level of σ, and training rate trr 0.01 with the evaluations using r 0.01 and σ 0.12, 0.25, 0.50 during test time, while during train time using training rate irr = 0.0. but using the constant o 0.126, 0.263, 0.53 for CIFAR1O 10 and a = 0.124, 0.258, 0.517 for MNIST. This way, compensate for the "increased levels of (xx)" with respect to σb- We present comparisons in the Figure 23 for CIFAR1O and 24 for MNIST, providing the evaluations with r = 0.01, o, = 0. 0.12, 0.25, 0.50 and the same d and Irr 0.0 during train time reference.
exactly the same as in the first experiment. 0.01 and Ø 0.12, 0.25, 0.50, trained with the
39

---

Under review as a conference paper at ICLR 2022
training
MNIST. Cohen mine, 0.25
04
64
Usd 0.12 mm00), 3m10
M 0.25. m- Iv-
e--03.0 m8001
tm-00
Use 8.22, m600) p11001
Miw 0 1=225 in
Mine 2.50 m60. 1am001
Borr 6.12 montt awrt.124
blle 0..% rend 24t
0.50 (ndOs
60
641
02
0.3
2.5
26 00
22 04 06
0.20
0.25
0.00
0.75
1.5
125
1:30
1.75
200
Figure 24: The certified radiuses on MNIST of the non-constant (a) method with rate 0.01, but different training strategies. Used training strategies are input-dependent training with the same (a) function and constant-o training with either σg or Ca, variance level. Evaluations are being done from single run.
0.12
= 0.25
0.50
IrT 0.01
0.843
0.780
0.671
trr 0.00 classical
0.849
0.790
0.670
trr = 0.00 increased
0.852
0.780
0.673
Table 17: Clean accuracies for both input-dependent and constant a training strategies on CIFARIO.
a
0.12
0 0.25
0.50
Irr 0.01
0.080
0.101
0.121
Irr 0.00 classical
0.080
0.105
0.135
trr 0.00 increased
0.076
0.099
0.120
Table Class-wise accuracy standard deviations for both input-dependent and constant training strategies on CIFAR1O.
0 0.12
0.25
0.50
trr 0.01
0.9912
0.9910
0.9883
trr 0.00 classical
0.9914
0.9906
0.9884
trr = 0.00 increased
0.9913
0.9905
0.9885
Table 19: Clean accuracies for both input-dependent and constant training strategies on MNIST.
o = 0.12
o = 0.25
σ = 0.50
trr 0.01
0.00757
0.00800
0.00947
trr 0.00 classical
0.00743
0.00789
0.00929
0.00 increased
0.00757
0.00798
0.00929
Table 20: Class-wiss wise accuracy standard deviations for both input-dependent and constant a training strategies MNIST.
The certified accuracy results for the CIFARIO and the MNIST differ bit. For CIFAR10 training
with rate = 0.01 does not overperform the constant Ca, training. For T₁ = 0. 12, the constant Co, training clearly outperforms the input-dependent training. For de 0.25, these two training strategies seem to have almost identical performances. For d₁ = 0.50, the input-dependent (z) strategy outperforms the constant ones, but the training. On the other hand on MNIST, we either have very similar performance or even slightly outperform the constant training.
know, that it is purely due to the variance in
40

---

Under review as a conference paper at ICLR 2022
Looking the aceuracy and standard deviation Tables 17 ing. In terms of clean accuracy, the input-dependent training strategy performs worst in most of the cases, even though the differences in performance might not be statistically significant. We see, that we would need far more evaluations to see some clear pattern. However, these results are definitely not good news for the use of input-dependent (xx) during training.
18
19 and 20
deduce the follow-
In terms of the class-wise accuracy standard deviation, we again see countering results for CIFARIO and MNIST datasets. For CIFARIO the input-dependent (xx) clearly outperforms the smaller con- stant σ training method, particularly for o 0.50. However, the constant Co, method seem to outperform even the input-dependent (z)). For MNIST, the smaller constant σy outperforms both other methods, while they are rather similar.
Together with findings from previous sections, these results suggest, that usage of this particular design of input-dependent (xr) might not be worthy until more precise evaluation is conducted. However, the combination of input-dependent test-time evaluation with constant, yet increased train- time augmentation is possibly the strongest combination that can be achieved using input-dependent sigma at all (especially for CIFARIO).
F PROOFS
Lemma 17 Jeyman--Parsonn Let X, Y be random vectors in E with densities z. Let h RN + {0,1) 13 be random or deterministic function. Then, the following two implications hold:
1. S = {
R E
v(= S } for some t > 0 and P(M(X) = 1) 2 P(X E S), then
x[=]
P(h(Y) 1) 2 P(Y S).
2. If 5- { E RN v(z)
21} for some t 0 and P(N(X) 1) S P(X S), then
=(=)
P()(Y) = 1) < P(Y E S).
Proof. See Cohen et al. (2019).
Lemma 1 Out of all possible classifiers f such that Gz(z) S 1 the one, for which
Gz(z + 0)B is maximized is the one, which predicts class B in a region determined by the likelihood
ratio:
f((x) fo(x)
)
B x RN
where r fixed, such that (B) = pn- Note, that we use to denote both the class and the region of that class.
Proof. Let f be arbitrary classifier. To invoke the Neyman- Peaassn Lemma 17 define = f (with the only difference, that h goes to (0,1) instead of B)). Moreover, let S = B and Y ~ Ni + ö, 1)). Let also f classify S as B. Then obviously, IPX E S)
X ~ (zx FB = pg. Since Gy(x) < pB, we have P(h(X) 1) S pn. Using directly the second part of Jayman-Pearson Lemma 17 this will yield P(Y E S) 2 P(L(Y) = 1). Rewritten in the words of
our setup, Gy- 6) 2 Gy x 66)
Theorem 2 If oo 01, then B is N-dimensional ball with the center at Sy and radius Rx:
S, = = o% oi
oe
1011 + 2N oāo of
ao
20
5, R
V (o))
of
log
+ o of
log(r).
If lo < o1, then the complement of a N-ddimensional ball with the center at Se and radius Re:
20 - (of - -
oā
20
Sz
0
8. R
|8|12 + 2N
log
log(r).
0
of
ob
00
o o
41

---

Under review as a conference paper at ICLR 2022
Proof. From spherical symmetry of isotropic multivariate normal distribution, it follows, that with- out loss of generality we can take 5 = (a. O.... O.....O). With little abuse of notation, let a refer to (a, O....... 0) as well as O.... 0)|l- With this, the B is set of all x, for which:
f1(2) fo(x)
2 ; =
N
N
(2x) 0 N exp
20
2
(2
12
NV
exp
20
(0) - a)²
+
1=1
2=
N
N
(x) a1²² +
1
Σ
2
S
N
log
00 01
+ log(r) =
2
20
2
1=2
i=1
5
(oj
1 + (o
2
20 + oja²² < 22Nojo log
+ 2000 log(r)
01
Now assume dg > 01 and continue:
N
(
ot)
+
- -f - 200 + oña" < 2No
log
0
+ 20 log(r) )o(r))
01
2=2
20
a'a
oj
oo
Σ
2
aT
+
2N
log
00
+
log(r) -
of
o
of
o
of
01
of
of
2
N
o
σ 2
o
11
+
2
+ 2N
log
+
log(r)
0
2
0
o
01
o - of
Such inequality defines exactly the ball from the statement of the theorem. On the other hand, if To < G1:
N
(of - v Σ
+ (of
- -o))a + 20 - -oja² 2 2No log
- 20 log(r)
1=2
N
20
d'
o
01
20 2
>
2N
log
2 log(r)
4
0j
0
0 00
0
00
0
2
0
2=2
I1 +
20
2 2
2 +
2N
2 2
log
01
20 2
log(r)
of
(0} og
of
0
of o
1=2
This is exactly the complement of ball from the second part of the statement of the theorem.
Theorem 3-
o
R2 PB( = x²
of
Re
Pb( = x (o) of
10
10812
of
-
where the sign or >> is choosed according to the inequality between do and 01.
a + 0. Now, the
Proof. Assume first 0o σi. Let us shift the coordinates, such that
o
o 8. Assume X ~ N -
of 8, oz.). To obtain
will have coordinates
0.
|1 + 2N Rंoी
20 2
= Bb
E B) PP |1X|12 <
log
5
+ og of log(r)
[oū - otj²
oj
of
42

---

Under review as a conference paper at ICLR 2022
could almost use NCCHSQ. but don't have correct scaling of variance of X. However, for any regular square matrix Q, it follows that P E B) = P(QX E QB), where QB is interpreted set projection. Therefore, if we choose Q
L I, we will get
6a
Po(B)= =P (1xx/oo|2
of
1012 + 2N o
log
0u
20 log(r)
(o of
oj
Now, since X/00 ~ N
on
8, I), we can use the definition of NCCHSQ to obtain the final:
o of
o
of
of oj
2 log(r)
Po( = XN
011 +
2N
log
(o)
of
(o) o
o of
To obtain (B). we will do similar calculation, yet we need to compute the offset:
x + 0f 0 of
of o2 a.
Thus, after shifting coordinates in the same way, our alternative will be distributed like X ~ V~ -3 of -z 01 I). Now, the same idea as before will yield the required formula.
In the case of oo < TT. we do practically the same thing, yet now, we have keep in mind, that B will not be a ball, but its complement, therefore we will obtain "1-" in the formulas.
Lemma 18. Functions & (a). E< (a) are continuous on the whole R4. Particularly, they are contin- uous O.
Proof. Assume for simplicity do > 01 and fix To. whose position is irrelevant and fix 21 such that ||z0- - z1ll = am, where Om the point, where we prove the continuity. Note, that x2x (A, x) can be interpreted (as we have seen) as a probability of an offset ball with radius v and offset vx. Assume have sequence {a:) ag Om- Define x; to be point lying on the line defined by 20, 21 s.t. ||0p- - æi| = dg. define Ba, to be the worst-case ball corresponding to Ty. Now, without loss of generality, we can assume, that all B's are open. We have already seen from Lemma 2 that centers of B; converge to the center of Bm- Define X; = 1(B.), Xm = 1(Bm).
First we need to prove, that rú, radiuses of the balls converge. Assume for contradiction, that ra do not converge. Without loss of gererality, let r. = limsup
Tm- If r. oc, it is trivial to
see, that Po(B.) + PB for some i for which r; is too big. If < co, consider {az, JR=o to be the subsequence for which is monotonically attained. Define B, the ball with center 21 and radius r. and X, (B.). Then, Xig " X. for k + and from dominated convergence theorem, Po (B.B., + (B.). However, (B.) > (P( = pn. what is contradiction, since obviously Fo Fo(B..) # PB for some k.
Since oi is fixed, the Ii, probability measures corresponding to NN LI.) are actually the same probability measure up a shift. Therefore, II, (B.) can be treated as (B.). where IP simply measure corresponding to (00 ((0, and B, is simply B; shifted accordingly s.t. P1, (B,) = P2 (B)) (and assume, without loss of generality, that for each i, they are shifted such that their centers lie on fixed line). Now, since we know, that "position" of both the centers of the balls and the is continuous w.r.t a, as can be seen from Lemma[2 the radiuses are still r; and converge), we see, that even 1 (B,) - 1 (B.) almost surely. Now, we can simply use dominated convergence theorem using P2 to obtain (22(B,) - (2(B..) and thus PI, (B.) - Pi,. (Bm). what we wanted to prove.
Note that the proof for the case do < o is fully analogous, yet instead of class B probabilities, we work with class A probabilities to still work with balls and not with less convenient complements.
Lemma 19. If A1 > X2, then (2 x3) S (1g
Proof. Let us fix Ao, I) and respective measure and respective density f. From symmetry, the NCCHCSQ defined as distribution of 2 for an offset normal distribution can be well defined as |X - s|{ under centralized normal distribution. Define B, a ball with center at (A,, O........ 0) and radius x and B2 a ball with center (A2, O,..0...., 0) and radius x. Denote C( as the center
43

---

Under review as a conference paper at ICLR 2022
of ball B. From definition of NCCHSQ it now follows, that P(B,) x3v(2,, {1,2).
Therefore, suffices to show P(B1) & P(22).
Define D1 B1 B2 and D2 B2 11, Then we know:
P((B)) / f(z)dz= = / f(z)dz+ + / f(z)d==
/ f(z)dz+ + f(z)dz
B.
BinBa
BiiB2
B1
D1
P(B2) f(2)d== f(z)dz /
f(z)d2= f(z)dz / f(z)de.
B3
BanBI
Br
BBnB
D2
Thus,
/ f(z)d2.
P(B1) P(22) = f(z)d2
D1
D2
S C( Define central symmetry M with center S. Let 21 D1. Then can be 2
decomposed as 21 C(B)) + d, ||d|| I z. Then, 22 == ( = C(B2) from symmetry. This way, we see, that D1 = M (D2 and D2 M(D1) under bijection M which does not distort the geometry and distances of the euclidean space. Therefore, it suffices show:
2E D2 f(z) 2 f(M(=)), M(2) E DT.
From the monotonicity f()) w.r.t llyll actually suffices to show || S [IM 2 E D2. Fix some = E D2. By the fact that M is central symmetry and - M(=), it is obvious, that = = S + M(=) = p. where p is some vector. Now, using law of cosine, we can write:
|| = ||s]|2 + I|p|| ||||p| cos(a),
where a is angle between S and -p. On the other hand:
(z)]1 ||8|]| |1- 2||s|||| coS(IT a).
It is obvious from these equations, that
|| < [|M(z)]] > a S = 50.
Here, the crucial observation is, that Dj and D2 separated by hyperplane perpendicular to S (vector), such that S (point) is in this hyperplane. From this it follows:
D2 = y' |SP,, y D1 = S' |||| E
Now, since = SS and E D2. this implies |||| > ESS = -p" and thus p' < 0.
Lemma 20. Functions &> (a), (a) are non-decreasing in
Proof. First assume og > σ and analyse {> (a). From Lemma 18 we can without loss generality assume, that a > 0, since & (0) is simply the limit for 0 and cannot change the monotonicity status.
Denote B, be the worst-case ball corresponding to zo, 21 and P1 as usual. Choose e < oz o6-07 a, which is the distance between 21 and C(B.), as can be seen from Lemma
Now, fix > 0 and define 20. 21 s.t. ||z0
x1ll
Now, assume lies on line defined by zo, æn with ||:0 (lonn=z2) x22| || ate. Let Bate be the corresponding worst-case ball and P. as usual. First observe, that (P2(B.. 2 PI())), since ||x| C(B.) |22 C(B.)]l. Here use x (A), < x (12, if X > X2. what is proved in Lemma 19 Second, note, that since Bate is the worst-case ball for x2, it follows P2(Ba+)) 2 P2..)). Thus, (B,). (2(u)))), but that is exactly (a (a +).
To prove (a) < E (a + e) also for e a, starting and ending
o 0, it suffices to consider finite sequence of points that are "close enough each other" such that the respective 6 of
that codes the shift a; + aiti satisfy < of 04
44

---

Under review as a conference paper at ICLR 2022
Now, assume do di and analysie fx (a). The proof is similar, but we have to be a bit careful about some details. Again, fix a >> 0, define To, 21 accordingly and all other objects as before, except now, let denote A, Ba and Aute = Ba to be the class A balls which are complements to the since || C(Aa)l < || C(Aa) We again used the monotonicity from Lemma 19 Moreover, (2(Aa+)) S 22 (A,,, since Bute is the worst-case set for Z2. Therefore, P1 (AA)) P2(Aa+e). but after reverting to B's, it follows E> (a) S & (a + e).
anti-balls B. Again, (Aa) ) < IP since
Here, don't even need to care about ||e||, since the centers of A's on the opposite half-lines from To than # and 22
To prove the main theorem, we need simple bound on median of central chi-squared distribution, shown in Robert 1990)) in more general way.
Lemma 21. For all 2 0,
N c (x S (0.)
Proof. See Robert (1990).
Theorem (the curse of dimensionality): Let 2o, 21 PA, 0o. σ1, N be as usual. Then, the follow- ing two implications hold:
1. If 00 σn and
0 <
2og 1 PA)
log
+
N
then 2i certified w.r.t. T0-
2. If 01 and
0f N N - of --1
1
2 llg - PA)
log
+1
N <
0
N
of
N
then 1 certified w.r.t. To-
Proof. We will first prove first statement, thus let us assume do > 01. Then P, = ((
aill). From monotonicity of & showed in Lemma 20 we know { =1ll) 2 (0).. We will
show (0) > 0.5. We have, using definition of &> plugging in = 0:
o o
(0) x2v
XN (1-a((
Note, that here, we work with central chi-square edf and quantile function. In order to show & (0) > 0.5, it suffices show
XN a (1 PA) N,
because it is well-known, that median of central chi-square distribution smaller than mean, which is N, i.e. from strict monotonicity of edf, will get x (N) 0.5. To show the above inequal- ity, we will use Chernoff bound on chi-squared, which states the following: If O < 2 < 1, then
x (=N) < exexp(1 N/2, Putting z
of using chernoff bound we get: of
of
exp (1 (1-
o 1
x
< <1 11-PA- PA
The last inequality is required to hold. If holds, then necessarily X2 (1 - PA) > of N and thus
of
xx -PA) > N. Manipulating the required inequality, we will get exactly
+1 of <
2log(1 - Pa)
log
o
N
what is the assumption of 1.
45

---

Under review as a conference paper at ICLR 2022
Similarly will also prove the statement 2. Assume do 01. Like in part 1, will just prove {<( > 0.5 by using chernoff bound. This time, however, we have:
{0) 1- x2
o (
(
Xix
0i
ic. we need to prove
o 2 (op x2
1
<
The second part of Chernoff bound states: If < 2, then (=N 2 1 (zexp(1 (exxp(1=>))//2 2))
Let us
choose: 2
N-1 Then Chernoff bound yields:
0 N
o N
- N N
o N N
(1- of N -111
1)
x
21
exp
> PA
0
N
0
% N
this holds, then
(PA)(PA)
+
xx (PA) <N-NN - 1.
N
Now, using Lemma
21 for the easy case of central chi-sq -quuruu we see: x2 - 1) < 0.5 and thus
o x
< 1
of
what we wanted to prove.
Corollary 5 (one-sided simpler bound): Let Tp, PA, 0o. 01, N be as usual and assume now To > 01. Then,
log(1 PA)
2
N
then 21 is not certified w.r.t To.
Proof. We will simply prove
2/ log(1 pa) log
o
of 2 log(1 PA)
<
0 N
Assume expression log(1 (11--)+++ +y: yy 1 > y > 0. From Taylor series, it is apparent, that log(1 11-111y))) y) ty <
. Therefore, n loog(1 PA) then also log(1 y) + y < N
log PPA Solving for in the
N
first inequality, get sufficient condition y 2/
log(1 pA). Plugging of into y we get:
ab
log(1 PA)
2
N
which is very easily manipulated to the inequality from theorem statement.
Theorem 6 Let To PI be as usual and let | xill R. Then, the following two statements hold:
1. Let S og. Then, for all 02 01 S oo. if E3 (R, 02) > 0.5, then (2, 01) > 0.5.
2. Let do- Then, for all 02 an 2 aa Go. if E (R, 02) 0.5. then & (R,a)) 0.5.
46

---

Under review as a conference paper at ICLR 2022
Proof. We will first prove the first statement. Denote, usual in the proofs B, the worst-case ball for og, P, the probability associated to (f)) Since (R, Ø2) > 0.5 and since is essentially F2 (22), we see, that the probability of ball under normal distribution is bigger than half. This is obviously possible just if x1 E B2. From the fact, that B1 is the worst-case ball for oR we see
E> (x, 01) = Pi (B)) 2 PP (B2). It suffices to show Pi (B2) 2 (2().).
This follows, since d1 I 02 and 21 E B2. We know, that we can rescale the space such that
Pr (r = P2 2 (B2 (1B2-x1)+ x1)
using the fact that o just scales the normal distribution. The set Eo (B2 x1) + 21 is just an image of B2 via homothety with center 21 and rate øz, So suffices to prove
di
02 (B2 P2
11) + x1 2 (B2).
21)
01
However, obviously (B2 - 11) ) + +1 S B2 from convexity of a ball. If, namely, #1 + = E B2, then from convexity also + = E Bg and this maps back to + z, thus 21 + 2 is in an image. Applying monotonicity of P., we obtain the result.
Now will prove the second statement and as usual, let A1, A2, P1, P2 be usual (A is now the ball connected to class A), As always, Pi (AA.) < Fi (AA2), so it suffices to show (2 < 0.5 + Fi (A2) 0.5. Now, we need to distinguish two cases. If æ1
A2, the proof is completely analogical to the first part, but now reasoning on A's rather than B's. In this case, we will even get stronger Pi (A2) I P22 (A2) just like in the first part. If x1 & A2, then it is easy to see, that indeed (A2) < 0.5, yet it is also obvious to that PI (A2) < 0.5. This finishes the proof of the lemma.
Theorem 7 Let (I:) be r-semi-elastic function and Po, N, on as usual. Then, the certified radius at zo guaranteed by our method is
CR((a)) = max {0, sup (R 2 0; &> (R,, o, exp(((rR)) < 0.5 and &x exp(r < 0.5)).
Proof. This follows easily from Theorem
M Lemma 22. Let us have f(z) = Σ f(x)11(x E R2), where { is finite set of regions that t=1
divide the R and [ ft R; + R is finite set of I-Lipschitz continuous (I-LC) functions. Moreover assume, that (I) continuous. Then, fx) is 1-LC.
Proof. We do not assume any nice behaviour from decision regions, what can make the situation quite ugly. For instance, regions might not be measurable. However, it will not be a problem for us.
Fix 1 22. Consider line segment S I + a(x2 xI), a E [0, 1]. Let us instead of points in S work with numbers in [0, 1] via the a encoding. Consider the following coloring of [0. 1]: Each point E [0, 1] will be assigned one of M colors according to which region the a(x2 21) belongs. Define dj = 0 and d2 = sup(= E [0, C()) = C(d,)). Thus, de is the supremum of all numbers colored the same color 0. Then,
If(z1 d2(22 z1)) f(x1 + di (x2 x1)) (d2 - di)ll02 xill-
Why? Let (2 be a nen-deccgg sequence s.t. C(2,) C(0) and 2j - d2. Since f is continuous, obviously f(x1 + dz(22 21)) lim f(1 + 2, 2, x1)). Now, since norm and
j
absolute value are both continuous functions and since from 1-LC of fc(() on Ro(o) we have
Vj N: 1f + 2,(22 rı)) f(z d1 r1))
<
(2, - 12)1122 x1
we also necessarily have
[f + dz(x22 - x1)) - f(x1 + di di - x1))
<
(d2 d,) 222 xil
47

---

Under review as a conference paper at ICLR 2022
If d2 = 1, we finish the construction. If not, distinguish two cases. First assume C(d2) C(11). In this case, take some color s.t.
3zz1}=11 2j+1 S 2j Vj E N and 2j - d2 and 2j d2 Vj E,,
and fix one such {z Obviously, C * C(O), since d2 is upper-bound on points of color (()). Then, define da sup(z E [0, 1], (=)) C} and also define {
2 2 ēj Vj E
N and žj d3. From continuity of f, we again have f(z1 + d2 - x1)) = lim f(1 +2
7
a))) and similarly f(z + dz x 21))
lim f(x + 27(22 x1)). Again from continuity of
absolute value and norm and 1-LC of all the partial functions we have:
VjEN: [f + 2,(22 - 21)) fx1 + 22 x1))
31
(2j 2z) 822 x11
and
[f(z1 + ds(22 - x1)) fz) -2( - x1)) S
(ds 1 d2) x22 x1 |l
Now assume ((22) * C(dy). Then, we can take as C directly ('(22) and do the same as in the last paragraph (note, that this case could have implicitly come up in the previous construction too, but we would need to not take C = C(O) and we find this case distinction to be more elegant).
If d3 1, finish the construction. If not, continue in exactly the same manner as before. Since the number of colors M is finite, we will run out of colors in finite number of steps and thus, eventually there will be 1 M s.t. di 1. The final 1-LC is now trivially obtained follows:
[f(1 + 1(x2 x1)) f(x) + -(22-(11))))) z1))
f(z + di+1 x1)) f(x + di(12 xi)) Σ 1=1
f(z) + di+1 x1)) far di(x2 =21)| s Σ
-d di)ll z1
t=1
1-1
= | - ø1 Σ (d++1 - d,) = =||ا x1
Theorem 8: The (z)) defined in Equation Lis r rlasmi-elastic.
Proof. Our aim is to prove, that
(1
log(o(z)) = lo)( +r
Σ
2 - xill
m
k
(x)
is lipschitz continuous. Obviously, this does not depend neither log(os). nor -rm, will focus just on E
Σ
||. æill. Obviously, this function is r lipschitz continuous and only
(x)
Σ (x)
1
D. is 1-LC.
Let us fix y E V We will first prove || - y|l is 1-LC. Let us fix œ1, 02. From triangle inequality have
|| - yl - || - xll $ || x2ll. what exactly what we wanted to prove.
Now fix y1, 32 .... 3k and 11, 22. Then
2 yill
h:
100
yill
=
Ke
- yill
||00 - yill
1=1
i=1
1
|
well
-11002 well
|
x221 =
k
1=1
48

---

Under review as a conference paper at ICLR 2022
Finally note, that using the k nearest neighbors out of finite training dataset will divide RN in finite number of regions, where each region is defined by the set of k nearest neighbors for that region. Note, that the average distance from le nearest neighbors is obviously continuous. Then, using Lemma 22 the claim follows.
49


Reviews:
[{"review_id": "x_lh9LPychx", "reviewer": "Reviewer_UXiJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### strengths\n\n- It is important to build the input-dependent RS methods.\n- While there have been some previous works, most of them are mathematically invalid (as the authors argued).\n- It is challenging to formulate such input-dependent RS with a valid certification, and the authors successfully address the problems.\n- The paper is well written in a logical order.\n    - Lemma 1 and Theorem 2 describe the worst-case decision region for $\\sigma_0$ and $\\sigma_1$. Given $\\sigma_0$, to use the input-dependent $\\sigma(x)$, it is required to certify for all valid $\\sigma_1$ as stated in Theorem 6. If we know upper/lower bounds on the $\\sigma_1$, it is easy to obtain a certified radius. Therefore, Theorem 8 justifies the design of $\\sigma(x)$ in eqn (1) as we can easily compute the bounds of $\\sigma_1$ as in Theorem 7 because it has globally bounded variations ($r$-semi-elastic).\n- It is a general approach that can be extended and applied to other RS scenarios.\n\n### (minor) weaknesses\n\n- In Abstract, the authors (over)state that \"... to overcome these flaws (certification vs acc trade-off or fairness issues)\" which may mislead the readers to thinking that the paper solve these problems. However it is not quite true as stated in Section 4 regarding the results in Table 2 and 3 (the last paragraph in page 7).\n    - However, I still believe that the paper has enough contributions.\n- It would be nice to compare the results with ($r=0.00$ and $\\sigma_{tr}$ increased) too.\n    - concrete, actionable feedback: please show the corresponding additional results in Table 2 and 3.\n- Except for the above two comments, the paper has no significant weakness in its content, but there are some major/minor presentation issues that must be addressed before published.\n- \"Using non-constant \\sigma(x) defined in Section 2, ...\" (page 2)\n    - It is defined as eq 1. in Section 4.\n- It would be better to use the same color for each method to avoid confusion in Figure 4.\n- $\\sigma_{tr}$ and trs (and $r$ and trr) seem to indicate the same thing, but the terms trs and trr have never been defined (in Figure 4).\n- not useful [README.md](http://readme.md/) copied from the original RS repository.\n    - for example, see [https://github.com/paperswithcode/releasing-research-code](https://github.com/paperswithcode/releasing-research-code)\n- Please kindly correct me if I misunderstood anything.\n\n### Others\n\n- Compared to other parts, the curse of dimensionality part is hard to understand. Could you elaborate it more in detail (in easy words)?\n- How long does it take to compute the $\\sigma(x)$ in eqn (1), compared to the Monte-Carlo process? Is it negligible? It would be nice to provide the (additional) computation cost.\n- The authors mention that \"Here, we compare Cohen et al. (2019)’s evaluations for ... with our evaluations, setting ... (for CIFAR10 and MNIST, respectively), applied on models trained with Gaussian data augmentation, **using constant standard deviation roughly equal to the average $\\sigma(x)$ or $\\sigma$ used during evaluation**.\" How do you choose the training $\\sigma_{tr}$ **before** evaluation phase?\n- How do you choose $r, k$ and $m$?", "summary_of_the_paper": "The authors propose an input-dependent randomized smoothing method with non-constant input-dependent $\\sigma(x)$.\n\n### contributions\n\n- The authors generalize randomized smoothing with non-constant input-dependent $\\sigma(x)$.\n- The proposed method successfully addresses some intrinsic limitations/flaws in the previous (input-independent) RS.", "summary_of_the_review": "The authors tackle important problems of RS. \nThey use their original method to solve the problem in a rigorous way and the method seems to be effective. \nI thereby recommend the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "xK6Ik_XdNKg", "reviewer": "Reviewer_j688", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The main theorem looks reasonable to me. Despite all the complex equations, I think the intuition is that the worst-case classifier f* when using input dependent randomized smoothing has a spherical structure, and its volume shrinks in high dimensional space.\n\n2. The proposed input-dependent randomized smoothing standard deviation function $\\sigma(x)$ is novel and different from existing works (but unfortunately the improvements are quite small).\n\nWeaknesses:\n\n1. The theoretical study is limited to the setting where isotropic Gaussian noise is applied. However, when considering input dependent smoothing, I feel a non-isotropic Gaussian noise would be more useful - for example, on MNIST, it can be quite reasonable to apply a larger noise on the pixels that are black (background) and apply smaller noise on the white pixels. By applying this kind of input dependent smoothing, the limitation of input dependent smoothing found in this paper does not necessarily hold. I hope the authors can discuss more on this more useful setting.\n\n2. One missing factor in the analysis, is that in high dimensional datasets, the distances between the images are actually pretty large: for example, the L2 distance between two ImageNet images from different classes are actually large, grown by the factor of $\\sqrt{N}$ ($N$ is the data dimension).  In terms of smoothing, I think it totally makes sense that when we are certifying a single image, the $\\sigma(x)$ function should not change too much within a small radius $\\| \\delta \\|$. However, since different images are already very far away, we can certainly apply different smoothing $\\sigma(x)$ on different images.\n\n3. The design of $\\sigma(x)$ is pretty naive and the empirical results are very weak - compared to smoothing with uniform noise, the gain is too little.  I feel this is due to the restriction of using isotropic Gaussian noise.  Since the variance of the Gaussian noise is the only thing we can change and they cannot be changed too much, the proposed input dependent smoothing scheme in this paper is not very useful. \n\n4. No comparisons to existing baselines (such as Wang et al. 2021) using input dependent smoothing were given.", "summary_of_the_paper": "This paper studies the input-dependent randomized smoothing technique - it adds isotropic Gaussian noise with different variance on different input x to give robustness certificates.  The hope is that this can perform better than applying a uniform noise.  The main theoretical claim in this paper is that when adding input dependent isotropic Gaussian noise, the variance of the noise should not change too much among different inputs. Based on this, the authors propose an input dependent smoothing mechanism based on k-nearest neighbor and evaluate its performance on MNIST and CIFAR datasets.", "summary_of_the_review": "Overall, I do like the analysis for input dependent randomized smoothing, but I think the overall impact of this work is rather limited. I rate the paper at borderline because I feel the theoretical part of this paper has certain limitations and the proposed procedure is also not very effective in practice and has quite small improvements. To further improve the contribution of this paper, as I mentioned in the \"weaknesses\" above, the authors can study the more useful setting of applying non-isotropic input dependent noise, and develop better $\\sigma(x)$ function to improve smoothing performance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "OYUQxTHkTKW", "reviewer": "Reviewer_jyXD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- The main merit of this work is the theoretical contribution in section 2. It is quite useful deriving the conditions under which the input independent smoothing is theoretically valid.\n- The summary for the steps in deriving the radius in page 3 is neat and useful.\n\nWeaknesses: I will summarize the main points below and detail the reasons behind each of them afterwards.\n1.  The experimental evaluation presented in this work is insufficient. Moreover, the proposed methodology has no notable improvement over the considered baseline. \n2. The writing of this work along with the presented figures can be significantly improved. \n3. There are several parts that need more elaborative discussion. \n\nRegarding the first point:\n- While the motivation of this work is the \"certified accuracy waterfalls\" the proposed objective in Equation (1) does not solve the problem. The results presented in Figure 4 show that the proposed method suffer from a similar but slightly delayed issue.\n- The presented experiments considered the weakest baseline (Cohen et.al) were the effectiveness of the method should be tested with stronger baselines including MACER and SmoothADV and preferably on larger datasets such as ImageNet.\n- While the objective in (1) could arguably increase the value of $\\sigma$ for points \"far from decision boundary\", it is not clear how would it decrease it for points close to the boundary. This point is related to the results on CIFAR10: why does the proposed method perform slightly worse on small radii? Shouldn't the values of $\\sigma$ get adjusted for points nearby decision boundaries such that some improvement is got in that regime?\n\nRegarding the second point:\n- It is not clear why did you need to assume the semi-elasticity bound.\n- There are several notations introduced within text such as $a := \\|\\delta\\|$ and used later without referring to the same variable.\n- The plot in Figure 4 should have consistent colors. An envelop curve over the different values of $\\sigma$ could benefit the comparison.\n\nRegarding the third point:\n- It is not clear how in the special case for when $\\sigma_0 = \\sigma_1$ will the results be reduced to the one in Cohen et. al.\n- It is clear how the objective in (1) could be used during training, but it is not clear how is it used at test time. What is $\\mathcal N_k(x)$ in that case?\n- The discussion in the paragraph below (1) is a little vague. Instances belonging to the same class could significantly differ in the input space (e.g. instance of white dog and instance of black dog). How could these distances relate to the position to decision boundaries?\n\nOther questions:\n- Regarding the curse of dimensionality: While the variation between $\\sigma_0$ and $\\sigma_1$ is restricted by Theorem 4, is it possible to break the input space into small regions where the variation is small within the region but large enough between instances far from each other?\n- Since the proposed method requires knowing $\\mathcal N_k(x)$, How will this neighborhood be obtained in test time?\n\n\n\n", "summary_of_the_paper": "This work extends the theoretical results from Cohen et.al to the input dependent setup. In particular, the derive the theoretical conditions for the validity of data-dependent randomized smoothing through a similar procedure to the one in Cohen et.al. At last, a function that optimizes the smoothing parameters per input was proposed and validated experimentally on MNIST and CIFAR10.", "summary_of_the_review": "The theoretical analysis presented in this paper is both novel and of interest. However, there are several weaknesses of this paper that need to be addressed including the experimental setup, the effectiveness of the proposed method, and the presentation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "Jt_ZkR0dahT", "reviewer": "Reviewer_Q6Nf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe \"takeaway\" from this paper is a negative result (both theoretical and experimental), but I think it is of relevance to the community. The idea of input-varying noise $\\sigma(x)$ is attractive (as the authors note several other papers have recently touched upon this idea), and this paper makes a strong theoretical case for why it's unlikely to outperform Cohen et al's baseline.\n\nWeaknesses:\n\nThe main weakness lies in the fact that this is a negative result -- it doesn't provide any real improvement over Cohen et al. 2019, and the authors acknowledge that this method doesn't scale to modern ImageNet-scale datasets.\n\nExperimentally, the results could use some work. Writing-wise, it would be helpful to more clearly differentiate CIFAR-10 and MNIST in Tables 2 and 3. In Figure 4, the colors orange and blue are swapped between the baseline and the proposed methods when the setting changes between CIFAR-10 and MNIST (this is extremely confusing)! It would additionally be helpful to make clear that the $r=0$ case in Table 2 corresponds to clean accuracy. \n\nIt's unclear how the authors derived Equation (1) -- is it possible that there exists another choice of $\\sigma(x)$ that could yield superior empirical results? \n\nIt seems unlikely that training with a fixed noise level would be the optimal way to train input-dependent smoothing models -- have the authors tried, for example, changing the noise level of the Gaussian at training time to be input-dependent as well?\n\nIt would be helpful to evaluate the proposed Equation (1) on toy simulated datasets in low dimensions, simply to verify that we can indeed see an improvement from input-dependent smoothing. Figure 1 is helpful for building intuition, but I'd be curious in seeing how that result scales with dimensionality $N$.\n\nMiscellaneous:\n\nTypo in Figure 4, \"coparison\".\n\nI'd be willing to revisit my rating if the experiments and writing could be cleaned up substantially.", "summary_of_the_paper": "The authors study input-dependent adversarial smoothing i.e. the setting where the smoothing distribution has noise level $\\sigma$ dependent on $x$. They begin by deriving the robustness certificate in this setting, and show that it suffers from the curse of dimensionality -- in order to maintain non-vacuous certificates in high dimensions, $\\sigma(x)$ must be prohibitively smooth. They then provide empirical experiments using an example function $\\sigma(x)$ on CIFAR-10 and MNIST and show that performance is more or less the same compared to the fixed noise level baseline (Cohen et al. 2019).", "summary_of_the_review": "This paper presents theoretical and experimental negative results on input-dependent randomized smoothing. \n\nI think it's likely to be of *some* interest to those working on randomized smoothing.\n\nBut the wider community will likely be uninterested by this negative result. \n\n(Additionally the paper could use more work on the experiments and writing in particular).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers input-dependent randomized smoothing to obtain certified robust classification. The main contribution is the derivation of necessary conditions on how the variance of the smoothing distributions (assumed to be spherically symmetric Gaussian distributions) has to change to achieve certified robustness. All reviewers like this result, as it provides guidance on designing input-dependent smoothing, which is an interesting result for the community and certainly helps future research.

On the negative side, the smoothing method derived based on the theory provides little (if at all) improvement in practice, it cannot be scaled to higher dimensions, it does not address the problems it claims to address (the "waterfall" effect, as also admitted by the authors in the discussion), and the presentation should be significantly improved. 

The paper received mixed reviews. While I think that the presented theoretical results are useful and interesting, the problems mentioned above make me to side with the negative reviewers and suggest rejection of the paper at this point (although this was not an easy decision).

While this is only lightly touched in the reviews, I strongly recommend the authors to make the presentation of the theoretical results more comprehensible. It is quite hard to follow the paper as notation is introduced continuously in an ad-hoc and confusing way (e.g., in the proof of Theorem 2, $a$ denotes $\delta$ and $\|\delta\|$), and things are often not adequately defined (e.g., the certified robust radius is not defined formally; in Lemma 1, $x$ is undefined and used for $x_0$ as well as a free parameter, $\chi_N^2$ is only implicitly defined, etc.)
Decision: Reject