Certified Adversarial Robustness Under the Bounded Support Set
Authors: Yiwen Kou
Qinyuan Zheng
Yisen Wang
Venue: ICLR 2022 Submitted (2022)

Abstract: Deep neural networks (DNNs) have revealed severe vulnerability to adversarial perturbations, beside empirical adversarial training for robustness, the design of provably robust classifiers attracts more and more attention. Randomized smoothing method provides the certified robustness with agnostic architecture, which is further extended to a provable robustness framework using $f$-divergence. While these methods cannot be applied to smoothing measures with bounded support set such as uniform probability measure due to the use of likelihood ratio in their certification methods. In this paper, we introduce a framework that is able to deal with robustness properties of arbitrary smoothing measures including those with bounded support set by using Wasserstein distance as well as total variation distance. By applying our methodology to uniform probability measures with support set $B_{2}(O,r)$, we obtain certified robustness properties with respect to $l_{p}$-perturbations. And by applying to uniform probability measures with support set $B_{\infty}(O,r)$, we obtain certified robustness properties with respect to $l_{1},l_{2},l_{\infty}$-perturbations. We present experimental results on CIFAR-10 dataset with ResNet to validate our theory. It is worth mentioning that our certification procedure only costs constant computation time which is an improvement upon the state-of-the-art methods in terms of the computation time.

Under review as a conference paper at ICLR 2022
CERTIFIED ADVERSARIAL ROBUSTNESS UNDER THE BOUNDED SUPPORT SET
Anonymous authors Paper under double-blind review
ABSTRACT
Deep neural networks (DNNs) have revealed severe vulnerability to adversarial perturbations, besides empirical adversarial training for robustness, the design of provably robust classifiers attracts more and more attention. Randomized smooth- ing method provides the certified robustness with agnostic architecture, which is further extended provable robustness framework using f-divergence. While these methods cannot be applied to smoothing measures with bounded support sets such uniform probability measures due to the use of likelihood ratio in their certification methods. In this paper, we introduce framework that is able to deal with robustness properties of arbitrary smoothing measures including those with bounded support set, by using Wasserstein distance well total vari- ation distance. By applying our methodology to uniform probability measures with support set (2(O, r). we obtain certified robustness properties concerning b--petuurbation. And by applying to uniform probability measures with support set (0,r). we obtain certified robustness properties with respect to 4 12, &o-- perturbations. We present experimental results on CIFAR-10 10 dataset with ResNet validate our theory. It worth mentioning that our certification procedure only costs constant computation time, which is an improvement upon the state-of-the- art methods in terms of the computation time.
INTRODUCTION
Vulnerability adversarial samples is major obstacle that various classifiers obtained by machine learning algorithms, especially deep neural networks (DNNs), need to overcome (Szegedy et al. 2013 guyen et al. 2015)). For instance, in computer vision applications, deliberately adding some subtle perturbation that humans cannot perceive the input image æ will cause DNNs give wrong classification output with high probability. Many empirical adversarial defenses have been proposed, among which adversarial training (Madry et al. 20188) is the most effective one (Athalyc) al., 2018), however, still faces stronger or adaptive attacks to decrease its effectiveness certain degree (Croce & Hein 2020). This motivates research on certified robustness: algorithms that are provably robust to the worst-case attacks.
Some works propose algorithms to learn DNNs that are provably robust against norm- noun-bounded ad- versarial perturbations by using some convex relaxation methods (Wong & Kolter 2018 8 Weng et al.) 2018 Xiao al. 2018 Zhang al.) 2019). However, these approaches usually computationally expensive and require extensive know legge classifier architecture. Besides, randomized smooth- ing (first introduced in Cohen et al. (2019) has received significant attention in recent years for verifying the robustness classifiers. Based on this method, several papers have studied which smoothing strategies perform better for specific Ip perturbations. Cohen et al. (2019) concludes that randomized smoothing can be well understood for the l2 case by using Gaussian probability measure for smoothing. It follows that several special cases of the conjecture have been proven for p < 2. Li et al. (2018) show that 1 robustness can be achieved with the Laplacian distribution, and Lee et al. (2119) show that lo robustness can be achieved with discrete distribution. Other papers start from opposite perspective and focus on studying under specific assumptions which perturbation is provably difficult to handle and which smoothing methods are ineffective for particular disturbance. As for the existence of noise distribution that works for the case of p 2, Blum al. (2020) and Kumar et al. (2000) show hardness results for random smoothing to achieve certified adversarial robustness against attacks in the ball of radius e. Nevertheless, since these works provide hard- ness results for every possible base classifier f Id + y including those unusual and even bizarre ones, hardness results given by these papers might be attributed to taking into account classifiers that

---

Under review as a conference paper at ICLR 2022
will never appear in real-world applications. From this perspective, the order of difficulty restricted within the common classifiers subset still remains unresolved.
Notably, based on randomized smoothing strategy. Dvijotham , et al. (020)) introduce a provable ro- bustness framework using f-divergence their convex relaxation technique. However, due to the use of likelihood ratio in their certification methods, the framework cannot be applied to smoothing measures with bounded support sets such as uniform probability measures. In this paper, we intro- duce framework that is able deal with robustness properties of arbitrary smoothing measures, including those with bounded support set, by using Wasserstein distance as well as total variation distance. Our contributions are summarized as follows:
By applying our methodology to uniform probability measures with support set (2(O, we obtain certified robustness properties with respect to ly-perturbations. By applying our methodology to uniform probability measures with support set (0, we obtain certified robustness properties with respect to 42, Lo perturbations.
Furthermore, we analyze the cases when smoothing measure is taken as uniform proba- bility measure with more general support set (O, and show the unavoidable curse of dimension for the usage of bounded support set smoothing measures.
We present experimental results on CIFAR- 10 dataset with ResNet to validate our theory. It is worth mentioning that our certification procedure only costs constant computation time, which is an improvement upon the state-of-the- methods in terms of the computation time.
2 PROBLEM SETTING
Given a binary base classifier h R2 + y y= {=1} and smoothing probability measure μ., the randomly smoothed classifier (x)) is defined as follows.
Definition 1 (smoothed classifier, smoothing measure). The smoothed version of a base binary classifier h producing labels in set y = {=1} is defined as
(x) = arg max Pxartal(( = yl.
(1)
yEy
where μ E P(X) is called smoothing measure.
Another way understand this definition is to say that the smoothed classifier first scores point as (x) = IP (h(]+ = y] for each specific class y E 3 and then outputs the class y" with the highest score. We want to study the robustness of the smoothed classifier h2 against adversarial perturbations of size most e with respect to a given norm I|p. The question that whether bounded ip norm adversarial attack on a fixed input x satisfying (x) = +1 is successful or not can be formulated as solving the optimization problem below:
min ||a Sa
Px
+1].
The attack is successful if and only if the minimum value is smaller than 1. Since we know little about the information of the black-box classifier h, we follow the approach introduced in Dvvjothhm (et al. (2020): rather than studying the adversarial attack in the input space X, we study it in the space of probability measures defined on input space P(X))
min -2llse
PX + (x(X) = +1] min Ex<uth(X) = +1], vEDa.c.
(3)
where D D2... (2/+p: + || 2'114 S e} represents an l,-norm- based constraint set of radius for smoothing measure centered at a particular sample point x. Then, we follow the full-information robust certification framework established in Dvijotham et al. (2020) and analyze the generalization 
of binary classifier h, which they called specification and denote it as Φ X C Rd + Z C IR. Besides, define reference measure p + l and collection of perturbed probability measures D C P(x). Checking whether a given specification is robustly certified at p with respect to or not is equivalent to estimating the optimal value of following optimization problem is non-negative or not:
OPT( p. D) = min Ex~rlx(X))
(4)
FED
And certifying 4p robustness on input with output of smoothed classifier (z) = +1 is equivalent to verify whether OPT + n, Dr,.g) 2 0 or not.
2

---

Under review as a conference paper at ICLR 2022
3 OUR CERTIFICATION PROCEDURES
Notice that the certification Dvijotham et al. 2020) uses the likelihood ratio r(X) = v(X)
p(x) while
r(X) is well-defined only when the support set of contains the support set of v. Thus, when the support set of reference measure p is bounded, and takes even a small translation of p. the support set of y will cross over the boundary of support set of p. Their certification is invalid in this case. In this paper, by using Wasserstein distance well as total variance distance, we provide analytical techniques able analyze bounded support set which not covered by Dvijotham et al. (2020).
Since the set of measures Dz.c.g constraint in optimization problem OPT J + Dz,c.g) .) is in- tractable to deal with, consider relaxations of this by using Wasserstein distance well total variance distance constraints between and + μ., i.e. Dz.c.g S {u Wp( + (r,)) _ 6) == Dz,h.p which represents Wp-distance--ass sample point x and 'D C {v TV μr, constraint set of radius for smoothing measure μ centered at sample point x. Combining the two relaxations, we know Dr.c.a _ D2,66pp n nDz,g and therefore
constraint set of radius ò for smoothing measure centered at
{ = Dz.g which represents I'V-distance-basee
OPT(h, + (,, Da,e,)) 2 OPT(h, t, D.Do,5.p (a.e))
(5)
And we can obtain tighter relaxation by combining multiple Wasserstein distance relaxation with different ie. Dacg S (NiEz D.. nD2, where I C Rt and therefore
OhT(h, u. Da,e.)) 2 OPT h, μe, (N (a,,6)..))) DD..)) iEI
Thus, for fixed input x, suffices to consider the Wasserstein distance and total variance distance relaxed problem and verify whether OPT x p. Dz.ó.p n Dzzgg) 2 0 or not. The analysis this problem can be divided into three parts: computing the Wasserstein distance relaxation measure set, computing the total variance distance relaxation measure set, and computing the Lagrange function as well as dual problem of the relaxed optimization problem OPT x + 14, Dz,b.p n Dr,e). The details are discussed in the following three sections.
3.1 RELAXATION USING WASSERSTEIN DISTANCE
In this section, we show the following relaxation from norm- besed constraint sets into W-distance- based constraint sets for general smoothing measures as well as Gaussian smoothing measure.
Da.e.g (a' + pc: || x' 2'114 S { S (v: Wp(1 + v.v) s 83 D..6.pp'
3.1.1 GENERAL PROBABILITY MEASURE
Here, we want to find (e() such that
Dr... (x' u= 2'lla s <e) S (v: Wp(x u.v) S 5g(()) = DD, for all P(X).
(8)
Theorem 3.1. For all x Rd 0.g norm-based constraint set Dze. can be relaxed into W-distance constraint set D2,5,(6).v with radius 8g(c) = maxfc, ed+ {) which can be formulated as
Da.s, S W +1,)) maxfe, ed +b =
a. a.max (c,ed 3
3,3
And this relaxation radius max (c, cdt- } works for any Wasserstein distance parameter p >> 0 as well as any smoothing measure μ.
Note that for (g < 2) adversarial perturbations, the relaxed radius avoids the influence of dimen- sion d, whereas for (q > 2) adversarial perturbations, as y increases, 1/2 increases from to }
correspondingly. The fact that the radius of Wi-distance constraint set grows with order @(d2- provides us with intuition that it is increasingly harder to bound Dz.c.g with larger q. therefore, W-distance-relaxxaton works better for lg S 2) norm perturbation. And this relaxation radius tight for W2 distance and Gaussian smoothing measures which is proved in the appendix D and therefore shows that V works well for Gaussian smoothing measure.
3

---

Under review as a conference paper at ICLR 2022
3.2 RELAXATION USING TOTAL VARIANCE DISTANCE
In this section, we show the following relaxation from norm-based constraint sets into TV-distance- based constraint sets for Gaussian and uniform smoothing measures.
Dr,c,g- {x' + μ ||2 z'114 < S {v: TV ( p, S <E) -z,,E
(10)
3.2.1 GAUSSIAN PROBABILITY MEASURE
Here, we want to find E(t) for Gaussian measure μ = -0 1² such that
Dz.e.g {2' + p || - z' I'lly S c S {v: TV( xr v.,) - E(c)) = Dr,ete
(11)
The magnitude of É(c) is given by the following theorem.
Theorem 3.2. For Gaussian probability measure μr = (0 I² on Euclidean space IR and all E R, > 0, q > O, based constraint set Dz,e.q can be relaxed into TV-distance-based con-
straint set D Da.g(e) with radius E(E) 2G( max(e,ed ( "b)
where G is the cumulative distribution function standard normal distribution (N00,) which can be formulated as
2a
Dz,.. E E(V: v: (V VV + p,v) s 2G max { 20 20
{-_ ed cdd- 1))
(12)
This theorem theoretically shows that TV distance relaxation works effectively for 1g S 2) per- turbation due to the irrelevance of the radius to dimension d and increasingly bad for 14(9 > 2) perturbation because of the dependence of the radius to dimension order Odd
3.2.2 UNIFORM PROBABILITY MEASURE
Here, we want to find (c) for uniform measure ja = (K),, where K is a specific convex compact set, with density function fx (x) = Vol, Vol TrEK such that
Dz,e.g fa' + p
2'11, S e) S (v: TV(x p.v) S E(c)) Dr,gto)
(13)
In this paper, we mainly focus the when K is l,-morm ball centered at original point O with radius r, ie., K = (r,.,r). We give following theorems about special cases when = 1, co.
Theorem 3.3. When K is an l norm ball centered at O with radius for uniform probability measure (K) on Euclidean space Rd, we huve
Dr.c. \ {v: TV::V + n, v) 11-60 - 8} + for all > and arbitrurily small 0,
(14)
whene e 2rd Note that e 2 2r. which decays with order O(d ) q = 2 and e Z 2 which Va
decays with order ford=))oogg xo.
This theorem theoretically shows that for uniform smoothing measures with 1 ball support set, and total variance distance failed to relax measure set Da,,. effectively when = 2, xo. And this will consequently lead to bad performance for l2 and l. robustmess certification task, which can be from the following section discussing the importance of TV-distance-baa based relaxation radius.
Theorem 3.4. When K is an l2 (Euclidean) ball centered at O with radius r, for uniform probability measure U(K) on Euclidean space IR. and for all x E R.C > 0, q.q > 0. when e > min 2rdh-3 -b,, norm-based constraint set Dr,c.g failed to be relaxed into TV-distance- based constraint which can be formulated as
Di.e.g \ {v: TV(x 11,)) 5) + 0 for all q and arbitrarily small 5 0.
(15)
And when S min 2 - 3), norm-based constraint set Dz.e.g be relaxed into valid TV- amoont mas fe
sin" " (t)dt which can
listance-based constraint set Da.e(e) with radius E(e) be formulated
S sin" (t)dt
parcart maas ad 27
Jo
sin" sin" (1)dt
Dz,eg S UV
$1
(16)
J0 sin si)n"())
4

---

Under review as a conference paper at ICLR 2022
This theorem shows that for uniform smoothing measures with l2 ball support set, when q S 2, relaxation radius is independent of dimension d, whereas when 9 > 2 relaxation radius starts to be bound up with dimension d and the impact of d grows as increases. To put it another way. total variance distance relaxation performs well for uniform smoothing measures with l2 ball support set when Q S 2 and increasingly poor when q > 2.
Theorem 3.5. When K is an loe cube centered O with radius r. for uniform probability measure ( Euclidean space R and for all x E R, >> 0,q > O. when >> 2r, norm permmbased constraint set D Da.s. failed to relaxed into Wi-distance-bused constraint set which can formulated as
De,eg \. (v:TV(z (,)) - 11 * 0 for all q 0 and arbitrarity small 6 0.
(17)
And when 2r, norm-based constraint Da.e.q can be relaxed into valid TV-distance-based constraint set Dz.((e). When = 1, E(E) can be taken as 2 which can be formulated as
De,,11 S { (V:TV(E p. S e } 2r
(18)
When q = 2, E(e) can taken as 1 11-11111 (1- when < S 2ln where in approaches an exponential rate, which can be formulated as
D-1 S ln < 1 and
Dz,,22 S { f::: VV: H, <
Re (v TV:TV(++up0 S $1- =1- (19) 2d2r - )0)
V
1- when 21 < < 2r, which
E(c) can be taken as can be formulated as
Da..22 S { J: (u: TV(
(d ( V /dl 12
2
d +11 c+1 d-1
(20)
When g = 00, E(t) can be taken as 1(1 (1- 4),², which can be formulated as
D2,6,00 E (u:TV(E p, p
(1 (1-)))
(21)
As for uniform smoothing measures with Loo cube support set, this theorem shows that the perfor- mance towards L perturbation turns out to be fine since TV distance relaxation radius žy has nothing to do with dimension d and the dimensional curse is avoided. However, in this case, TV distance relaxation shows incapability to cope with le and loo perturbation some extent due to the rate of
increasing radius tending to as ((edd) and O(e").
After discussing the special cases when K is an too cube or an la Euclidean ball, we then consider the general case when K is Ip ball centered the original point with radius r and give lower bound for TV distance relaxation radius in the following theorem.
Theorem 3.6. When K an lp ball centered at O with radius r, for uniform probability measure u(K) on Euclidean space Idd and assume norm-based constraint set Dz,e.q can be relaxed into TV-distance-baser constraint set De.t(e) then
E(E) 2 2 (r(po))Po ra 2) 11-e(2x1(1 + + dx
exp
p
for all perturbation norm parameter q > O with high probability when d is sufficiently large, which can be formulated as
Da,cg ff:
X TV TV +1,)) 2 (( exp ( e(2aT(1 + )1)) do - 8 # 0 (22)
for arbitrarily small 8 6>0 0.
5

---

Under review as a conference paper at ICLR 2022
y
1.2
1.0
1.0
0.8
1,0
0.6
0.6
0.5
0.4
0.2
02
-0.6 -04 -0.2
0.2
0.4
0.6
-0.6 -0.4 -0.2
0.2
0.2
Figure 1: Graph of density function f(x) exp ( (T ( (²)"))) when p 2,4, 6 from left to right
A way to interpret this theorem is that as p increases and K correspondingly translates from 4 norm cross-polytope into Lx norm cube, the dependence of integral upper limit cd#
4r(pe)
dimension d is gradually reduced, which theoretically shows by taking all kinds of lg perturbations into consideration, in average scale 21 [Bp (O)r)) tends to perform better than 24 (B,(( (O,) where > Nevertheless, note that the curse dimension is unavoidable when we use uniform smooth- ing measure ((K) with bounded support set. Note the graphs of density function shown in Figure when p 2, 4, 6, we know that as p increases, the density curve is increasingly short, fat, and light-tailed. From another perspective, we consider a ball with fixed radius r. As the dimension d of the base Euclidean space increases, fixed proportion of mass concentrates within slab of width (d) Thus, intuitively, it is increasingly difficult to bound the perturbed measure set Dz,e.q by using TV distance and certify as dimension d enlarge due to the existence of TV-relaxation upper bound in the dual optimization problem.
3.3 VERIFYING FULL- ROBUST CERTIFICATION
Based on the above analysis, in this section, we are now prepared to compute the Lagrange function and dual problem of the relaxed optimization problem OPT(ó, + μ,, D.... 7 Dz.e). Here we mainly focus the case when reference measure / x=ト and perturbed probability measure absolutely continuous w.r.t. Lebesgue measure À on Rd i.e., p. & À and discard uncommon cases assume the density function of p
when p, V are discrete, single or mixed w.r.t. A. Since p, and w.r.t. Lebesgue measure À are f f(x) and g(x), E I respectively. Instead of using likelihood ratio r(x), we consider the difference between g(x) and f(x) and define it as g(z) == g(z) fx)) The objective function [xx=(((() of optimization problem OPT( p, D) can be rewritten in terms of difference function q(z). And we give the theorems below.
Theorem 3.7 (W, distance relaxation with
p S 1). The relaxed optimization problem (P, x + Dz,5.p n Da.e) is equivalent to the convex optimization problem with only one func- tional variable below
[ (lz))(())d)))))))) + Exxxttlo(X)) s.t. (E)
/ f(x)g(x)dd s (a(x)|dr s 2 11
inf
sup
(23)
where [|fll.,p == sup Bup aask
[(())-(())
Theorem 3.8 (Wp distance relaxation with p > 1). When smoothing measure μ possesses convex compact support set K and R == supyek l1l|22, R = | R R+ (c, (, cdt-tt) the relaxed op- timization problem (9, x p. Dz.6.p can be further relaxed into the convex optimization problem with only one functional variable below
(EC+ inf [ d(x)g(x)da + (owx+n/o(X))
(24)
f(z)g(2)dz & + 1 [a(=))dx < 25,
s.t. sup | Sp(2n))
where [lfllz == supa.yeR x#u
[(x))
Theorem 3.9. The Lagrange function of optimization problem in
23 and 24
T(A) E Ex-rtal((X)) XC,
(25)

---

Under review as a conference paper at ICLR 2022
Smoothing Measure
Perturbation
Certification Objective
Prerequisite
amooost sin (t)dt
u(B2(O,r))
1 S 2)
(x>a+vlo(X)) 2
6 S 2r
So sin (Ode
mmooss sin (t)dd
14(4 2)
Ex Ex-a+pl [o(X)]
6 S 2rd
1o² sin (O)d
(O,r)
4
E Ex [[()]
S 2r
l2
E Ex~x+H [x(X)] - 2 1 - 2d
S 2
100
E Xx [x(X]] 2 - 2F
S 2r
N(0,021)
1g(9 S 2)
E [x(x) 2(2G
20
<
-
E Ex~aty [o(X)] - 2(20( odà
1g19 2)
Table 1: Certification objectives and prerequisites.
where 2 is the dual variable w.r.t. constraint suPlliia S ((x)g(x)dd S or constraint 3uP1)//ll==002111)---1 fx))((x) (()gg))) I 8 + (p - 1)(2R*) yo and C == 8 when 0 < p S 1 whereas
C: 8 + ( when p 1.
Using the duality result, we know the optimal value in 23 can be obtained by computing
max Ex-r+ (oterr/ll(00 [x)) - XC x ( -. A20
(26)
which is only related to the radius TV distance relaxation set. We can see from this formula the significance of TV distance relaxation radius. By plugging the TV distance relaxation radius given in theorem 3.4 3.5 and 3.22 in dual optimization problem, obtain the certification objective in Table and we return certified for lp norm perturbation with magnitude e the objective function has non-negative value.
3.4 RELATIONSHIP WITH PREVIOUS WORK
By applying our methodology to Gaussian probability measure, we miraculously obtain the same certified robustmess properties provided in Dvijotham al. (2020) using Hockey-stick divergence with 3 =
Theorem 3.10. When smoothing measure is taken as Gaussian probability measure, the certificate Ex-atu [x(X] 2(2G -11-1) given in our paper is equivalent to the certificate c 0. given paper Dvijotham al. 12000
Therefore, when applying both methodologies to Gaussian measure, the formulas obtained are the- oretically equivalent. Despite the similarity in analyzing Gaussian measure, our work covers cases with bounded support sets, which our main contribution.
EXPERIMENTS
For adversarial robustness certification, we choose the test set certified accaracy our metric of interest, which is defined as the percentage of data points in the test set that can be correctly classified and can also pass the robustness certification within an l2 ball of an assigned radius r. To pass the robustness certification at data point x, the classification results of all points within an distance to original point must be consistent. For a model using the smoothing method, the classification result of a data point is the class with the highest score in the smoothed data distribution, not to be confused with the direct output of the base classifier that data point.
In all experiments, the certification process on the test set with assigned perturbation la radius shown in the following Algorithm Note that the cert(score,, 1 - score,, r) function returns true if the certification objective is neg-tiga,ive, otherwise it returns false. Such objective is calculated

---

Under review as a conference paper at ICLR 2022
using formulas in [ with l2 perturbation and corresponding smoothing distribution. Since method using Wasserstein distance does not involve iterations, our certification procedure only costs constant computation time, which is much faster than Dvijotham et al. (2020).
Algorithm 1 Certification process
Input: T: test set, gf(): true class of image x; fa)):: base classifier, D(x): smoothing distribution, n: sample amount, r: perturbation radius
Output: acc: test set certified accuracy
certCount <- 0, allCount <-
2: for all x E ' do
3: S (n samples from [)x)
4: counte f- for every class c
5: for all x E S do
6: count f count f(x))
7:
end for
8:
score, f counta for every class
card[S]
9:
+- arg maxe (saore))
10: if a = gt(x) A cert(score,, 1 scorea, r)
then
11:
certCound certCount
12: end if
13:
aliCount + allCount +
14:
end for
15:
return acc f cerlCount alCCount
We achieve identical results when comparing our W-distance method with the F-divergence method in Dvijotham et al.) (2020) using Gaussian distribution and with specific metric parameter settings, which is proved possible in Section 3.4 However, there is no previous work done yet to examine the usage of uniform distribution when smoothing, we mainly focus comparing Gaussian, l2 and lox uniform distribution all using our W-distance method.
4.1 SETUPS
We choose CIFAR-I0 as our dataset and ResNet-110 as our base classifier. We firstly train the base classifier on the 50000 image training set without smoothing and achieve 89.6% prediction accuracy on the 10000 image perturbation radius r. We test out different smoothing distributions as mentioned above, and we change the parameters of such distributions to illustrate the effect of different distributions further. We also try increasing the smoothing sample amount examine the trade-off between performance and accuracy improvement. All training, testing, and certification are run on an NVIDIA RTX 3090.
set. Then we run the certification process the test set with incremental
4.2 W-DISTANCE METHOD WITH DIFFERENT SMOOTHING DISTRIBUTIONS
We firstly implement our W-distance method with N(x, 0.05) as smoothing distribution and sample amount n=100, and then we change the variance of the Gaussian distribution to 0.025 and 0. As shown in Figure 2 there a neat cut-off for each setting where the perturbation gets too big, and no data point can pass the certification at this point. By changing the variance of the smoothing distri- bution, observe clear trend that the increase of variance leads to drop of initial certification
Gaussian
1 Uniform
L. Unifarm
Saman5.00 05
0.4
3.2
0.54
2.00
0.00
0.1
0.22
0.14
0.15
00005
0.001
0.0015
0
0.005
0.033
0.01
0.0035
1.00
Radius
Radius
Figure 2: Results of different smoothing distributions using our W-distance method. Sigma stands for variance for Gaussian distribution and the norm range for uniform distribution.
8

---

Under review as a conference paper at ICLR 2022
accuracy but also stronger robustness that endure more significant perturbation, and the decrease of the variance leads to the opposite change accordingly.
Next, for smoothing process, we substitute Gaussian distribution with /2 or l. uniform distribution, with the norm range set to 0.025, 0.05 and 0.1. In Figure 2 both experiment results show identical characteristics as with Gaussian distribution, but they bring along a critical issue, the mismatch the perturbation radius's 's magnitude. Comparing the perturbation radius at the cut-off point, we find that the radius of Gaussian distribution is about 50 times larger than that of two uniform distributions.
We assume that this phenomenon is caused by the lack of intersection of the smoothing distributions before and after perturbation. For Gaussian distribution, there is always an intersection no matter how big the perturbation radius gets, but two uniform distributions will separate quickly and become disjoint under perturbation. Furthermore, the dimension of 32 x 32 x 3 image is 3072, the square root of which is around 55.4, very close to the cut-off radius's s 50 times ratio difference. Such correlation may trace the involvement of dimension when calculating the finite support set volume of la and loc uniform distribution, while the support set volume of Gaussian distribution is infinitely large. We conjecture that such deficiency is inherent when using the uniform distribution, which can hardly be further improved.
4.3 W-DISTANCE METHOD WITH DIFFERENT SAMPLING AMOUNTS
When caleulating scores for each class in the smoothing process, we cannot classify all possible data points, we shall only acquire approximate scores by sampling from the smoothed data distri- bution. Thus such scores may differ in multiple runs due to the randomness of sampling. However, through our experiments, we find that with a certain amount of samples, we can already obtain suf- ficiently accurate scores, which cannot be significantly improved by increasing the sample amount.
Gaussian
Uniform
L_ Uniform
60.6
gos
0.7
n0-1000
n0-100
n0-100000
0.9
0.8
--- m0w100
m0000000000
n0-10000
Cortification rate
1000
n0-10000
R0+100
2 30.4
8.3
0.1
0.1
0.02
0.06
0.0005
0.001
0.0015
0.0005
0.001
0.0015
Radius
Radius
Radius
Figure 3: Results on sample amounts with different smoothing distributions using W-distance.
We the sample amount 100, 1000, and 10000 with three different smoothing distributions, and they all obtain similar results: it takes only 10 minutes to run through the 10000 images test set with 100 samples for each image, 30 minutes with 1000 samples and 3 hours with excessive 10000 samples. It is ten times faster than the 2 hours running time with the iteration-based method in Dvijotham et al. (2020) using just 100 samples. It is also worth noting in Figure by increasing the sample amount, no significant improvement is observed with Gaussian distribution. However, there is minor progress made with both uniform distributions when the samples are getting overly abundant. We assume that the extra samples make up for the lack of intersections of smoothing uniform distributions before and after the perturbation, while Gaussian distribution has such issues.
5 CONCLUSION
We have introduced a framework based on Wasserstein distance and total variance distance relax- ation as well Lagrange duality. This methodology is able to deal with the analysis of bounded support set smoothing measures, which is not covered by previous work. Moreover, we have ana- lyzed the performance of specific smoothing measures, including Gaussian probability measure and uniform probability measures with support set (2, B (0,r) theoretically and experimen- tally, which shows the relative incapability of bounded support set smoothing measures compared with Gaussian smoothing measure.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In ICMI, 2018.
Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang. Random smoothing might be unable to certify Lo robustness for high-dimensional images. Journal Of Machine Learning Research, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In ICMI, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustmess with an ensemble of diverse parameter-free attacks. In ICML, 2020.
D.C Dowson and B.V Landau. The fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis, 1982.
Krishnamurthy Dj Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gy- orgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In ICLR, 2020.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality randomized smoothing for certifiable robustness. In ICML, 2020.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. arXiv preprint arXiv:1906.049: 2019.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. arXiv preprint
2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. ICI.R, 2018.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confi- dence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2015.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint ar 2013.
Matthew Thorpe. Introduction to optimal transport, 2018.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In ICML, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In ICML, 2018.
Kai Y Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. arXiv preprint arXiv: 180.:0000,00008, 2018.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li. Duane Boning, and Cho-Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint 19Xiv:1906.06311 2019.
10

---

Under review as a conference paper at ICLR 2022
A OPTIMAL TRANSPORT THEORY
Assume J. V E P(Rd). Besides, assume p. v are absolutely continuous w.r.t. Lebesgue measure and let density functions be f and g-
Definition 2 (Push Forward). IfT TRd - TR., then the distribution of T(X) is called the push- forward of P, denoted by + P. In other words,
P(A) P(T(x) E A) (AT-
Definition 3 (Optimal Distance, Optimal Transport Map). The Monge version of the optimal trans- port distance is
I [1=-T())]PPPG)
inf T: TTTT== P= A minimizer T", if one exists, is called the optimal transport map.
(27)
Definition 4 (Wasserstein Distance, Earth Mover Distance, Optimal Transport Plan). Let I(u, v) denote all joint distributions ? for (X,Y) that have marginals μ and v. Then the Wasserstein distance is
(P(,vv) (0 inf (EIT(p.))
1 ( /1l=-ulBdd(e..))
7 where p 2!
(28)
When p = 1, this is also called the Farth Mover distance. The minimizer 7 (which does exist) is called the optimal transport plan.
Lemma A.1 (Dual Formulation of Wasserstein Distance When p S 1), It can be shown that
WF(,,)) = =sup (())dv(V) - ((z)dp(x))
(29)
where ( (b()) S || ull.. In the special case when p = 1, we have the very simple represen- tation Wi(H,2)=
PEF, / p(z)dp(=)) ((x))u(x))=
PEF, /
/
((z)d(a-v\(() = sup PEF,
=sup
(f))(f-))(z)))
(30)
where Fi denotes all maps from B.d to TR such that (f(x) - f(v)) || ull for all x, y. In the when 0 < p < L, we have similar simple representation
f ((x)du(())) (0())du())=
sup / (())( PEF,
Wo(u,v) sup seF,
sup *ET,
((z)d(p-v)(()-
(31)
where Fp denotes all maps from IRd to IR such that [f(x) f(v) S 1| ull for all x, y.
Lemma A.2 (Dual Formulation of Wasserstein Distance When < p oo). In the case when < p < oc and the support sets of measure y and v are included in a convex compact set K.
Define R = supaek ||~||2, then we have slightly different dual formulation
sup @Elip(e(2mppp1) / (aodd(u-)((u) (0-())((011(22)))))) (00-))22)-11
wn(nn))
/ ((u) f)()dd - (p 1)(2R)p-1)
sup (EIip)((2R))
(32)
where Lip(p(2R)p-)) denotes all maps from R.d. R such that (f(x) f(y)] S ((2R) ( i vl for all x, V E K.
Definition 5 (Total Variation Distance). The total variation distance between two probability distri- bution and v on Rd is defined by
|| pllzv max (la)) ((l(AA--(AA)) -v())) AC
(33)
where Rd is the set of all Borel subsets.
Lemma A.3. Let and v be two probability distributions Rd and absolutely continuous w.nt. Lebesgue measure X. Assume the density function of measure μ and v w.r.t are f(x) and g(x:). Then,
|| v/|rv =
f [f(x) g(x)) dx
(34)
11

---

Under review as a conference paper at ICLR 2022
B PROOF OF LEMMA A.2
Recall the dual form of Wasserstein distance
I (Vv)du(s) - ((z)du(2)
sup v.DEC(B))
(35)
where *v()) Φ(x) - | ylp..
For simplicity of the proof, consider equivalent form
/ (W))de(s + ((())d(()))
WF(,, v) sup V.DEC(RO)
(36)
where (b(1) (xx) 1 | yll. First, we introduce a theorem in Thorpe 2018
Theorem B.1 (Existence of a Maximiser to the Dual Problem). Let E P(X), P(Y), where
X and Y are polish, and c: X x Y [0, +oc). Assume that there exists ex (p), ey (v) such that cx, y) S. ex cx(x) + ey (v) for p-almost every x E X and v-almost every y E Y. In addition, assume that
M = / (x(x)dp(() /, cr(y)du(u) <
(37)
Then there exists (g,, vb) E 4 = ((p,)) E (2) x L-(v): ((x) + +(y) S c(x,y)) where the inequality is understood hold for y-almost every x E X and v-almost every y Y such that
sup = I(p,,)))
(38)
4.
where I is defined by J: ('))) x L (v)v) - R, 1) Sx sdp + Jy dddv. Futhermore we can choose (sp, 1b) (118, v7)) for some 7 E I (n). For X - IR, the c-transforms of, 11 are defined by
rfth Y + R, (z) inf (c(I, 3) n1xx)
(39)
sEX
gf + R, (8) inf (o(x, 8) - 17
(40)
TeX
Lemma B.1. For a, b IR and 1 S p < x0,
la + 1/p & 28 (lal2 + [bjp)
(41)
Proof. First, it's easy to verify the cases when either of a = 0, = 0.p 1 holds. Then, Wlog,
assume a, E R-
la + 6/" < 2n 1 + (b(²)
- (a D)P < 2-
1 (a" + bP)
a + b) )
p
20-1
a la+b)
- 2- '12" (1 x> 2 1, Vr (0.1)
where the last inequality is easy verify.
In our case, c(x, || y 1" M is exactly the condition that μ and have finite nt moments which is easy to verify by noting that suрр(μ) = supp(z) = K is compact set in Rd. Then, according to the theorem, there exists 17 E (p) such that
(||=)] + ||>l])
+ [|r|P) 2|==1
and the requirement that
/ (()dduu))) + f (F(())duo)) nEL'(u)
WF(n, u) sup
(42)
Note that of possesses Lipschitz continuous property stated below
12

---

Under review as a conference paper at ICLR 2022
Lemma B.2. For n, E (K) where K C R is convex compact set, then of is p(2R)=-1.
Lipschitt,function where R == su ||x|| and cp(x, = | ylP. i.e.
(1)7((()) 1 (v)ll - p(2R) - ull, z
(43)
Proof.
11/ (x) - (1)
inf (1|= 2 =1EK
inf (Ily z211? ((22))
(44)
#2EK
inf sup ( (l1xr - =11l- - lly 22|1²) - (11(1) -
[111-
# 22EK
S sup K
(|| - =|10 -)())) (Ily =1| -n()))
(45)
sup =ek
||| - =1| 11y - =||||
where i4 due to the definition of c-transform:
45 is obtained by taking a specific value of 21 as 22- 2 =||0| is a continuous function w.r.t. 2, then there
Note that is compact set and ||| 1 =1|"
exists a point =" such that ||| - 2" 1| - 11y 2- supzek ||| - ==||- - 11 - =||%/_ According
to the first order condition, 2" satisfies the equation below
V [1 - =||2 - 11 - =Ip² VzI1= =1|² Vz lly - =1| = Vz || + - V - =/|
pl|z x|| $ - (2 x) -pl1z v / y) T
(46)
=||=
x 2 (2 - x) T ||= - - -1 v) T
[I|= x|| | - ||z - yll -1|)) 22 T = || x|| $ + 1| - y11 -
||2 21 | -1
||2 3||35-
||2
1
|| y|| - x ||
x |||
|| -1
where 46 is due |=||=||0 V T x) p(x (x)
-| And this equation
shows that x* lic on the line determined by x and y but does not lies on the part between x and y, which can be formulated as 2" = Ax + (1 \)y, X E IR \\ (0, 1). Note that
||æ (Az + (1 - ))y) 1|I 11 (Ax + (1 A)v)
sup (011
[1(1 - (z - 811l - -11A(y - 2)|pp/
sup (011
[] - A|p - |xp| || - u1|²= = ( sup
|1 A1I2 - -1x1)) .1z -yl
sup (01)
(E
Then, we just need to optimize
11 A1p 12Kk
sup (031
s.t. Xx + (1 A)y E K
Note that we can relax the constraint as below
A + (1 - X)y K
X(x y) --)+y=(0 =
A) x)
||(x - y) + +|| = [11 A) 2) x) < R
(47)
||[( - b)ll < R + MM
||(1 - A)(y - x)| - R + |||||
(48)
|X| -||=-
(1r-w/] =/l
2R,
1 1-=--=11 vll s 2R
(49)
2R
2R
<A <
- vll
where 47 and 49 is due the definition of R supzek
||]||
48 is due triangular inequality.
13

---

Under review as a conference paper at ICLR 2022
Using the relaxed constraint, we can show that when À 2 1, increasing function w.r.t. À as p then
[1 - Alp - = - (A 1)p an
- App - | = AP (A
2R
)" )
(
2R
(50)
| vll
|
vll
And when A S 0, [1| 11- - (1- (-A)e P is decreasing function w.r.t p 2 1, then
11
A|-
1210 (1 2) (-X)
|| (1re-v]]
2R
yll )
P
2R
1
(51)
||
vl1
Note that
2R
P
2R
- )
P
k- (
| y|1 ) + (1 k)
2R
2R
p-1
(52)
| - w/1
w/1
| y
2R
+ (k- 1) (11-1 p-l
2R p-1
P
||
vll
S p
||x v11
where 52 is due to the Differential Mean Value Theorem where A: E (0, 1).
Thus, we have
2R
P-1
17 (v) $ (f)
.11 - u/1 ((2R)) yl1
(53)
|| mee-yll v/l
Lee 1)8(()) is p(22)) function.
Using Lipschitz continuous property of ry,, we get
/ ((())du()) + f / ())())))()) mEL
/ ((u)du()) + / (x))))(())
(z(+2)) = sup
sup (ELIp(p((2)))11
/ (()))u(()) / (1))d((())
sup (
(54)
where Lip(p(2R)p-)) denotes the set of 1122))21---iieeeee that
1 Lipschiiz functions. On the other hand, recall
/ (())de()) ff ((())du()))
WP(ms u)= sup
(55)
v.dECTR))
where (v)) + d(x) S || - yIl. Keeping (x) fixed and optimizing w.r.t. d(y), then we just
need to optimize f dd))dp(y) under constraint Φdv) I || wll (xx) Then obviously have o² (y()) infaek (Ile- y/l2 vx)) (x) where cp(z, y) || yll. The map
(o, 1b) C(K)² (v (+)) C(K) replaces dual potentials by "better" ones improving the dual
objective (p,
Using c-transform, we can reformulate constrained problem into unconstrained convex problem over a single potential
/ (on)du(s) + (z))))(())== sup
/ ((u)du())) + / (5)()))((v))
WP (1, v) = sup (EC(RA)
WEC(R))
(56)
Combining 54 56, we know that when the support set of measure μ and v supp(n) supp(u)= K where K is a convex compact set, we have
/ ((s)du())+ / wer (v)dd())) WB(m))
/ (())du())+ / / (z)dd(()))
sup (EC(K)
sup PELip(r(2N))
(57)
Note that Lipschitz function must be continuous and therefore Lip(r(2R)p-)) S C(K). Then, we have
sup (EL -1 / ((())du()) + ((())d(())) < sup ((w)du(w) + (>>()) (58) &EC(K)
14

---

Under review as a conference paper at ICLR 2022
Combining 57 and 58
we know the inequality in 57 changes into equality
pELip(p(2R)) 2) ʃ ((v)du(v) + f ( u)(
sup
(59)
Note that for f(x) xd --(22) 2, R+ achieves its minimum when f' pxt-1 p(2R)=- 0, i.. = 2R. and the minimum is f(2R) = (p 1)(22)))) Then,
(v)
inf (1n-yy1l==((xx)) p())) 2 øek
inf =E
(1I- (|=-y]l-<(w0-<<220) 11x- = -p
(60)
Thus, we attain a lower bound of (H,
/ p(v)du(v)+ (elf////ada ( vELip(P(2R))-)
W WP4,
sup
(61)
((y)du(v) (v(x) (p- ( ())1))2)) dd((v)
sup pETip(p(2R))
(62)
((v)du(y) / p(v)du(y) (p 1))(2))
sup (ELip(p(22))-1)
p(u)d(v (m( - -Op - (o)1)22R)
sup (ELip(p(2R))
where 61 is due to and 62 is due to 60
C PROOF OF THEOREM 3.1
Proof.
Da fs' + || x'llg S e)
(63)
Note that
(1, sup pED
sup
Wp( nl x' + + sup W 2 pd)
(64)
1|2-2'11,Se
|=
where the first equality is due to the definition of Pz,.,q and the second equality due to the trans- lation invariance property of Wasserstein distance.
Then recall the Monge version of Wasserstein distance
Wolu, S
inf (T:TFHv
[[=-T(x)]Pdp(e))
(65)
Noticing the inf operator in the Monge version definition of W,, we can get an upper bound for Wp(,, v) by specializing a transport map Î satisfying Tp = u. In our case, we take Í. Idd Rdd T: xr + and it's easy to verify that T# + Then we get the upper bound below
$ < <
1
/ ||0 ((x) [(=))())Pdddo)))
inf T-T#
||||||
(66)
where the last equality is due to μ is probability measure. This provides us with intuition that the upper bound of Wp(u, + (1) is determined by the Euclidean norm displacement z. Using this upper bound,
Wplu, = 11) S sup ||=||2 1|
sup
(67)
1|=1l.Sc
When 0 < q S 2, using the lemma that when 0 < p < q xo, ||I||, < || pr Vz E Rd holds, we
have sup se ||2||2 I sup sup]|=ll, || = c. On the other hand, note that [|e1l|2 = ||ceally = c,
we have sup s ||=||| = e. And when q > 2, recall Holder's Inequality below
Lemma C.1 (Holder's Inequality for R"), For (ai (bi C R. > 1, we have
1
aa Lailbbel E
[lail")
Jail")
Σ a |a/==)
(68)
im
15

---

Under review as a conference paper at ICLR 2022
Apply it to the case
lail
|2;1² [bol -1 and = 1.
2
Σ m
1orl 2 1
Σ
R)
Σ
17
2 10
d'
(69)
Y=1
i=1
1=1
d
|| =
Σ
xij 11
d
:
||01|1
(70)
ed-- On the other hand, note that 4 واl, e, 111 Σ eill ed ,, we have sup suppl=ll || ed - Combin-
Thus, su ||:||2 v |1p[1 Se || d
n2
n2
ing the case when 0 < < and q 2, we have
c when 0 < <a52 = max edt
sup 11o-ee
Wp( + 1,, +)) sup W 11) v
cdt when q >
S|
(71)
D W2 DISTANCE RELAXATION IS TIGHT FOR GAUSSIAN PROBABILITY MEASURE
Here, show that W2 distance relaxation for Gaussian probability measure is tight. Theorem D.I. When μ = o(0,021) and p = 2, the relaxation in 9 is tight. In other words,
Da... S D a, J.2
but Dz,e.9 \ \D a.max(read 8.2 * 0 for any sufficiently small 6 >>> 0.
(72)
Proof. Note that Dowson & Landau (1822) established the formula Wasserstein distance between two Gaussian measures.
Theorem D.2. For Gaussian probability measures = N(un, and v NN2,, E2), W2- distance between p and have closed form form formula
W2(u, v)² 11m 12ll2 +r E., 2(E E2)
(73)
Using above theorem, yield following tight relaxation between norm-based constraint set Dr... and W2-distance based constraint sets 22,5,2 for Gaussian smoothing measures centered at origin, i.e. f NO0 r2)
sup W2(,vV)= sup vEDz...
W2(1 + 2, +1) = sup W2(n, 2 + +1) ||--z'|1,
||=||,5c
sup S
|||||| = max edl -d)
(74)
where 74 due theorem D.2 and equality 71 And generalization of above theorem when Jr (0, E) can be proved in the same way.
PROOF OF THEOREM 3.2
Proof.
First, introduce the lemma below.
Lemma E.1. Let X be a random variable that follows d-dimensional Gaussian distribution with density function
1
(,:;,,))
(75)
(2T)
where I, u E d and E Sh... Let H. I w + b 0 be a hyperplane in the d-dimensional
Euclidean space Rd, where w E ERd and b E RR The hyperplane H defines two half-spaces:
2= RR bbb 0), Ω for E Rd bbb)) <0}
(76)
16

---

Under review as a conference paper at ICLR 2022
Define the integral over half-space Q+
P= [ Jat
E)de= J., Ja, (2
2 20-22)1-16 (x-
Since E is positive definite symmetric, there exist an orthogonal matrix U and diagonal matrix D with positive diagonal elements such that Σ = U DU. Let To - lIVDUw
1. w4b and hence =
Jao V2n
e- 1a² dx.
(The proof of this lemma is credit to over -aapaaaaeeessppsceeaaaa-- space))
Recall the definition of 4p nnorm constraint set of probability measures
Dacc. = fa' + :e: || x'1l4 {}
(77)
Note that
sup TV v) vEDx...
sup
TV(x + u1, + sup TV + μ))
(78)
1
|
where the first equality is due to the definition of Dz,c.q and the second equality due to the trans- lation invariance property of total variance distance.
Define hyperplane H' xTx ||l 0 and H : xxx= + 11=12 0. The hyperplane H' defines
2
2
two half-spaces: 04 = {xr E Rd) 2
2 2 0} and Ω = (xr E
m ||:11
2 < 0]. And
the hyperplane H² defines two half-spaces: ? = {x E Rd 2 +
-e=l 2 2 0} and Ω = {o e
1= + ||=1 < 0}. Applying lemma E.1 and lemma A.3 we know that
2
sup Se
(V, 2 + 14)
1 2 /
1
1
(a 2 x)
sup [e
(2T) (2m) od
20
(2T)
20
dz
(79)
(
(n-
( (m-s)
2 ||=llu SelloSr.aa n1. (2T)
sup
20
c
20
dx +
Sa (2d))adl
c 20 -
20
dr
2 ||alloSe at (2x)zod
1 sup
(I=e)
20
IT 20 dr /
22 (27)
(
(e
20
(=-2)
20
(x-=)
dr
(80)
1 sup
/
d(=+1) { du { du { d(z + 1))
Jaz
Jn
2 ||=1l, 44
14
1
/
sup
duc
du
+
du
dp
(81)
2
||
52
Hellz 20
ll la
1 sup
1
f0²
dr
1
t=²
dx
1
2
dx
2m
dx
2
-11l112
v 2T
lllll2
22T
2T
< 2T
000
(82)
1 sup
GG [|=112]
- -G(
|1:112
+
G
||:112
G
||2112
))
(83)
2
||=
20
20
2a
20
1 sup
||:1|2
2G
(84)
2 ||=lleSc
20
=2G( max ma, ed -
(85)
2a
where 79 is due to lemma A.3 80 80 is due to the consistency of sign of integrand function on ? and
Q1 is due to the transformation formula of space coordinates; 82 due to lemma E. 83
and
85 is due to the definition and central symmetry property of G as the cumulative density function of standard normal distribution: is due to 71
17

---

Under review as a conference paper at ICLR 2022
F
PROOF OF THEOREM 3.3
Proof. Recall the definition of nnnorm constraint set of probability measures
Dz,e.g = {a' + p ||
11, S c)
(86)
Note that
sup (V, MEDe.c.v
= sup ||2-z|11,c
TV + u. + 11) sup TV (1) 1,5c
(87)
where the first equality is due to the definition of Dz.e,q and the second equality is due to the trans-
lation invariance property of total variance distance. Next, compute the value of TV (t, 2 + p.)
Lemma F.1. K is a 4 norm ball centered at original point of radius then K n (z + K) = 0 if and only 1=1|1| 2r.
Proof. First, we prove the if part and assume ||=||2 > 2r. Consider arbitrarily taken æ E (a + K), i.e. 1 - =|11 S r. According to the triangular inequality with respect to li norm, we have
|| = || - (x - =)I1ı 2 ||*||| - || - =|I1 2r -
(88)
which shows that & K and therefore K n (2 + K) 0.
Then we prove the only if part by using reduction to absurdity and assume ||=|| - 2r. Take f2,
then ||v/|1 1 |||||1 < and l1y 2|I1 2 ||=|||
which shows that y E K n (a + K) and
therefore K" n (= K) + @ which leads to contradiction.
L
According to lemma
F.1 we know that when {=|1|=11a e, 1111=111 2 2r} * 0, we have
sup vEDr...
(V
sup (V + (4) =
(89)
||:1,
Define 3 2r Eiz1 Co and it's easy to verify that ||ž|| = 2r and || = 2rd -1 for g > 1. Thus,
when 6 2rd we have
sup DEDa,c,
TV(uD))
sup TV(44 + n)) = ||
(90)
G PROOF OF THEOREM 3.4
Proof. First, we introduce the lemmas below for the convenience of later proof.
Lemma G.1 (Volume Formula of d-dimensional spherical cap). The volume of a d-dimensional hyperspherical cap of height h and radius r is given by:
paccost
V
sin (t)dtt
(91)
2
where we define h as the value shown in figure 4 and I (the gamma function) is given by I(2) Jo ii
=
Lemma G.2 (Volume formula of d-dimensional Euclidean ball). The volume of d-dimensional Eu- clidean ball of radius is given by
(92)
r 1)
Recall the definition of 4p norm constraint set of probability measures
Da,iy fa + :: || I'114 {)
(93)
Note that
sup (V, = sup DED...M
TV + u, + +
sup TV (1)
(94)
||z-z'
|| 15
where the first equality is due to the definition of Dz,e.q and the second equality is due to the trans- lation invariance property of total variance distance.
18

---

Under review as a conference paper at ICLR 2022
Figure 4: An example of a spherical cap in blue
Lemma G.3. K is a l2 norm ball centered at original point of radius r, then K n (2 K) = 0 if and only | 2r.
According to this lemma, we know that when and c> > 2r, we have
12 sup TV 2 + n) (M, c01 + p) Vol(KS(ee) + K)) 2Vol(K)
(95)
where the last equality is due to ||ce|l12 = > 2r and applying lemma G.3
And when g > 2 and
2rd have
VoI(KA 5
Ei 4 + K))
1 12 sup 2
Σ
Gi + +)
(96)
S|
di
2Vo((
where the last equality is due to 1 Dd cill2 = ed > 2r and applying lemma G.3.
Combin-
19
ing the results for S and > 2, we have
TV 2 + p)) when > m2n 2nd #/
sup 1e
(97)
Next, consider the case when S min 2nd -b3. Applying G.1 lemma G.2 and lemma we have
A.3
sup TV(,, 2 + ||
1 || 2
sup
/ Vol(K)
IDEK 1
Vol(K) Ineztx|do
(98)
1 || 2Vol(K)
/ IxcKA(=+kjd=== sup 1|=1,sSc
Vol(K + K)) 2Vol(K)
sup
Vol(K)
2n - a parccus(" (illla) (t)dt
r( (()))) Jo
r at1) Ju
a aancou
[1ll|
sin (t)
sup
sup 11
1
Vol(K)
Vol(K)
(99)
2x 1
arecns
sin (t)dt
2T + T d+1 T
arccos Halll
sup S|
sup 11=1|SSc
1
sin a (t)dt
p
I +1)
(100)
arccos max Rxeed
2 +1)
2r
sin (t)
(101)
T オ 4+1
where 114 is due to lemmal A.3
99
is due to lemma G.
100 is due to lemma G.2
101
is due to
71
Because of the computation difficulty (overflow), we have to simplify the term
19

---

Under review as a conference paper at ICLR 2022
When d is even, assume d = 2k, & N and note that r(1) =,, . then
r +1 r(k + 1) T( 2 [[k
(1
k!
(2k)!!
(102)
5)
II _ (i (
क II (1 - 2/)
x (2k: - 1)!!
Recall the Wallis integral lemma that when d is even
1-² cos (t) (d
1)!!
sin sin (t)dt
d 24 EN
(103)
d!!
Thus,
TG +1)
(2k)!!
1
1
I( TE (2k 1)!!
2n 1 (3
(2k 11!!
2x
S0² sin
(t)dt
2x - So² sin (t)
(2x)1!
(104)
When d odd, assume d 2k + 1, 1: E N and note that [(1) = =1, = tž, then
T +1)
I( d+11 = [( 2))
()T(E)
T ==
+ 2
. + 1)!!
(105)
r(k: + 1)
(1)
k!
2 (2k)!!
Recall the Wallis integral lemma that when d is odd
Ld sin s (t)dt = S/² cos (t)dt (d - 1)!!
d d= 2k +1EN
(106)
d!!
Thus,
r 1)
<2k + 1)!! 2 (2k)!!
1
1
1
((
2T $
(2 (2k+1)11
2n Jo sin
sin 2k+1 (1)dl
2x Jo² sin sin (t)dt
(107)
To sum up, for all d E N, we have
r 1)
(108)
r( I(
2T 2 1/2 f sin (t)dt
Then we avoid the computation of l + 1),1( and transfer it into the computation of an integral. Applying formula 108, have
Anccoss
sup = =1== ||
sin a (t)
(109)
So* sin (I)dl
H PROOF OF THEOREM 3.5
Proof. Recall the definition of -norm constraint set of probability measures
Da... = fa' + fi: || - x x'lla S c}
(110)
Note that
sup (v, = sup VED
TV u. + + sup TV 1|z-r'1,,e
(111)
where the first equality is due to the definition of Dz,e.o and the second equality is due to the trans- lation invariance property of total variance distance.
When 2r.
12 sup TV(u, +)) TV + + =1 S|
(112)
20

---

Under review as a conference paper at ICLR 2022
where the first inequality is due to the fact that μ and + probability measures; the second inequality is due to supp(μ) n supp(ce) 14) 0. Thus, this case,
sup (V + S|
(113)
When < 2r,
sup Sc
(H, 2 14)
/ sup ||=
1
1
1
IPEK
2Vol(K) I IxE+tK
(114)
2.
Vol(K)
2Vo((K) / KIEKA(++)dd==== sup |1
1
Vol(K + K))
Vol(K n (2 + K))
sup
sup Se
1|=1b5
2Vo((K)
Vol(K)
1 11
1 (2r - 1zil)
1 - 11: (1
[
sup ||=1,
(2r)d
$|=1|
sup
2r
(115)
First, we study typical cases when 9 1,2, c0. optimization problem
When g
we need solve the following
inf Se
(2r
(116)
Here we use mathematical induction to prove that
inf 11
[2a)) (2r)a-1(21
(117)
||l|is
When d 2,
1 (12)) Se
inf
inf (2r (2rl) ((22) inf (2r + (22l) [22)) 1sa
inf (2r - e + 22r -22) = inf 22(E - 22) + 2r(2r c) = 2r(2r - E) 0$=25e
Thus, induction hypothesis holds for d = 2. Then, assume induction hypothesis holds for d = n.
When d = n + 1,
inf m -1z1)) = inf Se
Σx IaiSe m (2r - (2,)) = Ei le (2:)) (zn-1)
inf
inf (2r) (2r (2r- t + | [) |2x41l)
(118)
|s.11/se
-2r) -) = (2r) E)
(119)
where 118 is due to the induction hypothesis when d = n: 119 due to the induction hypothesis
when d = 2. Therefore, we have already proved that
inf II. 1 (2r -12/1) d22r)d1((0 c), Vd E
(120)
||
Plugging in this result, it follows that
11 (2r (2r (2r)
|2+))
(2r) (2r)d
(2r -c)
sup TV (v, + p) = sup ||=||
(121)
|=]liS
2r
When q 2, 2, we need to solve the following optimization problem
inf IT 12 (2:1)
(122)
||=||SSc
When d 2,
inf 11dL (2r 12() ||
| 2 S5. (2r- (2r ((2--2111))))))1 inf (2r (62 -23)² (2r 1122)
inf
inf (2r (62 22) (2r 22)
05
21

---

Under review as a conference paper at ICLR 2022
Define f(22) = In (2r - -(e2
- -22) + In (2r - -22), then
f((22) = 22(c² - -22)-
(e² - =2)) 2 - 22)(2-22))
- 22) - - 2r + (c2 - =23)²
2r - -E²² - -2ÿ) 3/2 2r 22
2r (e² (2-22) -=ž)² (2r - 22)
(123)
Define g(22) = 2r - x22) - =2](e² - 2/2
- 2r- - (c² - 2)) then
(2222) = (223 - 3222 22 + 2rc (²² - -22)=
(124)
Define h(22) = 2 1 32222 + 2re², then (22(2) -62 3e² 6(22 v2
(x + (2) Thus,
when 0 22 S 7/2 11(x) < 0: when v2 < S h((x)= > O. Thus, the minimum value of h(x))
on interval [0,e] is h( (/) = v222 - c). Therefore, function f(2) behaves differently when
0 <<< S /2r and when /2r <E< < 2r.
When 0- < E S 22r, h(22) 2 (122))= = v22(V2r -)) 2 0 on interval [0, e] and therefore
0'(=2) = (=22 2- 23)) 4/2
- 2 0. Note that g(0) c 2r < (g) 00g(c=) ) 0o and
therefore (=2) S 0 when 0- S 22 S fo while (22) > 0 when
v < 22 S c. Thus, f(22) takes
its minimum when 22- v2 In this case.
inf 05
(2r (2r- - (62 - =3)3) (2r - -2) = (2r E )²
v22 )²
(125)
When 22r e < 2r, we have h(0) 2re² > 0.h(
5,) = v2e
c) < 0, Q(c)
v2
(2r - c) > 0. Assume h(t1) h(t2) 0,0 < < v2
<t2 < c, then when 0 S 22 S t1
or 12 S 22 S c. h(22) 2 0 and when t < 22 < 12 h(22)
< 0. Therefore, g((22) 2 when
0 0. 22 2 or
tr S 22 S c, (22) < 0 when 1 < 22 < tz. Note that g(22) = 0 4 (2:)
8) ()(((22-))+222-- )²) = 0, therefore when 0 S 2 2 rr-v I -2 or 5/ S 22 Sr rr v 1 - 12,
((22) S 0; when r- V
2 r2 <<<<<>0 V2 or r + V 7 12 < 22 < e, (22)) > 0. Thus, when
2
122 -12 or 5/ 2 S rr v //2 12, -2, f'(x) < 0: when r / / - < 22 < V2
05 22 S r
V
or V 2
,2 < < e, (x) > 0. Thus, ((2) takes its minimum when 22 / 1タ4 ,2
or 22 = r + / //2 - p2 In this case,
inf 05255e
2r - (62 - (23))))) (2r - 22) = =-(--/ (1-1)
2 -r2)
rr + ( V
2
-2 12
= =2
2²
(126)
2
2
2
inf II (z:l) = inf E 255
I (2r (2|l =
inf - 1
(2r-
||
Σ
(127)
By then, we have understand clearly the optimization problem when d =2 2. Then, consider the case when d = 3. When d = 3, inf II _ (2r - 12=1)) = +
inf (2r - 1=:11)1)22 (1o - 12al)
(128)
||=||eS<
When 0 << e < /2r, assume the optimal point is x², We will prove that each coordinate of =' has the same value. Here use reduction to absurdity, and wlog assume 2 # 23. By fixing the value of zz. the optimization problem 122 is equivalent to
inf
(2r - (2r - -22z)
(129)
# (=g)²
And (zi, x5) should be an optimal point of above problem. Note that e² (2-(2))² < e² < 2n and
applying 125 we know that 2 = 2 which is a contradiction. Thus, 2 = 22 =
2/ = c. And
inf II (2r |2 ||=
inf (2r c)3 2r
c
(130)
v3
22

---

then Under review as a conference paper at ICLR 2022
128 must lie on the boundary of feasible region, i.c. (z1)² + (=1)² + (zg)² = e². Wlog, assume (23
When /2r < <<< v3r, it's obvious that the optimal point 2² of optimization problem
2²
3 and
(2i)² + (zz)² < 2 < 2r By fixing the value of 23 and following similar deduction procedure as above we know that 21 = 2 c², where c* is the optimal point of following optimization problem.
inf (2r - c) - v² - -2c) 0505
(131)
Define f(x) = -2 (2r - x) + In (2r - -xx²) where S x S V3
f((x) = 2(3.²2 -2rx 2² 2r 2 2x
(132)
(sr 22r Ve 2x 2 2x
It's obvious that the denominator of f'(x) is negative, As for the numerator, define g(x) = 3xx²
2r e² where ك x S v3.
Note that
g S max {a(0)
E (52) max { ( e, 2re
-max
S 0
(133)
v3
/3
Thus, we have the following equivalent relationship
3=²- 2rz 6² + 2r 22 2x 50
- 3x² 2rx 2 < -2r 22
c - 2x 0
(3x² 2rx- - 2)2 2 ( -2r
2 - 2xx) 2 0
(3x² 2 (3x² 2 - 4r + 41² e²) 2 0
3x- 4rx + 47 - 20
2
0
when V2r <E S 2x552/5 //3""
2r
332²
8 2r + v322 8
when 2 2 < < v3r
3
3
3
where the last equivalent relationship is due to the discriminant of the quadratic equation 3z.² 4r + 4r2 22 is A 4(3,2 2r Therefore, when /2r c 2 2 (rr.r f'(x) S 0, S x S v3
and hence the optimal point c* in the optimization problem 131 takes value V3* whereas when
2/ frr <<< V3r, f'xx < 0 for 0 < 2r-vart- 2r /3.2
8p
< x
v3 and f'(x) > 0
3
for 2r 87 S x -- and note that f( 22 8r
3
3
f(
v
hence the optimal
point c* in the optimization problem takes value 2r- 3e2
8y
To sum up, when v2r c S 2 fr.
3
the optimal point =* of optimization problem 128 satisfies
27
=7=0
23 = 5/3 And when 2
3
c S /3r, the optimal point 2" of optimization problem 128 -8--" one of its permutations.
satisfies 2j 25 2r-
/ 3
8p .28
When v3r <E < 2r, similarly we have (27)3 + (20)3 + (2z)3 = 22, If there exists S i < 3 such
that (2 2 2 - 2r², wlog assume (2g)² 2 ² 2r By substituting the value range of from
[0, Jel into [0. r). following similar deduction procedure and noticing that f( (2r v3c" 8r
fr)).
know that the optimal point 2n in this case satisfies 21 25 2 2, for all 1 < I 3, then
2r V3e² Sp
23 4r+/3"" 33 8F
3
or one of its permutations. On the other hand, if (2 )
(2T)² + (2g)² = é - (zz)² ? > 2r2. Applying 126 and taking of = (=
72, 2
T + 2 (21)² r2, we know the optimization problem is equivalent to
inf
2x
2 (2r 23)
23
(134)
05 <VE=<Ve-2F
2
23

---

Under review as a conference paper at ICLR 2022
According monotonicity analysis of the cubic function above, the optimal point 23 is either 2r-
2r And it's easy to verify that f( f( f(ve- 2r and or Ve² 3e" However, (zz)² E² 2r² which leads to contradiction.
therefore 2/
In summary, considering the case d = 3, when < c S 2/3r. the optimal point 2" of original optimization problem satisfies zj = 22 = 23 v3 and the optimal value is (2r -3 and when
v3r E < 2r, the optimal point x" the optimal point x" of original optimization problem satisfies 2î = 2/2 2r-v3. 8r 23 4rt vrt/ 8r or one of its permutations.
Next, consider the general case when useful properties of the optimal point z" which help simplify our later discussion a lot.
2 4. In the first place, we point out and prove two
All coordinates of optimal point 2n takes most two different values.
If the coordinates of optimal point =" takes exactly two different values e₁ and c2, then the number of coordinates equal to ci must be n 1 or 1.
Proof. On one hand, by using reduction to absurdity, wlog assume 21, 22, 23 take three different values. Fixing the value of the other n coordinates, know that (2i: 20, 2z) the optimal point of a special case original problem when d = 3. And note that for all the optimal points of d = 3. there must exist two coordinates taking the same value, which leads to contradiction. Thus, the first property is satisfied.
On the other hand, similarly, by applying reduction to absurdity, wlog assume z 25 C₁ and 23 21 02 where 01 + c2. Fixing 2i, 2 and the value of the other 4 coordinates and aware of the fact that (=7)² (=))² S 2 < 2r we know that (2f; 23) the optimal point of special case of original problem when d = 2, c < V2r and therefore 27 25. which leads to a contradiction. Thus, the second property is satisfied.
Using the two properties above, we know that the optimal point 2 has only two possible forms: x" v
and x* (c. ,, v (n - I)c²) or one its permutations where O V V v which can be unified into one form: 2" (c.... ... or one of its permutations where 0 S c < - Thus, the original problem can be simplified into following optimization problem with one degree of freedom:
/ - (n - 1)c²)
inf (2r c)n Ve - (n -)o2
(135)
05e5 vm-I
Define f(x) = (n 10-1)m 1n (2r x) In (2r - Ve - (n 1)x²)
where 0 5 x I -ύ- then
(n - (nxx 2r - 2 2r 2 (n 1)1
(x)
where 0 S x <
(136)
(x - 2r) (2 - Ve² (n 1)x²
(n 1)x²
vn
It's obvious that the denominator of f'(x) is negative. As for the numerator, define g(x) nx² 2r 2 where
-パー Note that
g(x) & min (00))0 /n e
} max {0, ele - 2yn Ir) $
(137)
n -
24

---

Under review as a conference paper at ICLR 2022
where the last inequality is due to < 2r -r. Thus, when 0 z I - Vn-I
nx" 2rz - 2 + 2r - ( - 0
nx² 2r - è S -2 22 (1 - 1)x² <0 0
(nx² 2rx- 213 2 ( - 2r 2 - (n - 1)x?) 2
(nx² ( (nx - Arx + 4r² - -2)) 2
(nx² - -Axx + 4,2 - 2*) 2 0
2
Vn
1 2 V1
when < <<<<< <
11
2r
NE² - 4(n 1)r²
2r + Vne² 4(n 1)r
n 1 when 2V
S E < 2r
n
n
where the last equivalence relationship is due to the discriminant of the quadratic equation no² 4rx + 2r
2 = 0
A = 4 {nEe² - 4(n 1(n) < = 0<E<2 n 1
(138)
Thus, if 0 < < 2/ ,r,, then (x)x) 2 0 when
S S -ズー and f'(x) < 0 when
vn
05 x < c. Thus, f(r) takes its minimum when x and therefore e² vn
Vn'
If 2 n-1 S < 2r, then (x) 2 0 when
v / l)r²
S
V ne
Or
Vn < x < and (z) 0 when S x 2r V ne² - A(n 1 1)r
2r ned 4(n 1)r
or
ne² 1(n-))2
In this case, f(x) takes its minimum when x
or vn
For the
convenience of analysis, assume कΦ < t < and it follows that
( = (2r)" (1
(139)
Vnl
20 Vnce 2 4in--1i
(n 1) (n (n- + v nl2
n-1 (1
/l/2 - (n - 1)
(2r)m
n
n
(140)
We can prove that there exists tn E (V n-1
such that c* when 2 n-1 r S c < 2
and c² 2r- /on-/nee= - 1(m=1)+ when 2r, < c < 2r while f, converge at an exponential rate as
shown in figure 5
In conclusion, for the case d = n 2 4. when 0 < c 2t,r, e² in and therefore
inf (2r- 121) = (2r (2r- (2r- v2 - (n - 1)((+)3) = (2r [|
6 n
)
-T]
= 2r
d
n2
(141)
Plugging in this result, it follows that
(2r d
sup (V(,,++p) sup 1 IT (2r - 121
d2
1- (1-
d
(142)
||
||=||aSc
(2r)d
(2r)
2d
25

---

Under review as a conference paper at ICLR 2022
15+
1
15
26
025
Figure
5:
Graphs of functions Ji(()
(1
S2(1)
(n- (o--1)4// nt? (n-1) n-1 n when 4, 16, 64 from left right. Accord-
n
ing to the figure, on interval V n-1 11 f2(t) is greater than fi (t( at first and then f2(t) exceeds (t). Furthermore, as n increases, the horizontal coordinate the intersection point converge to 1, which can be seen intuitively from the figure above.
and when 2 < 2r, C* V nee i(n 1)r
and therefore
inf [2r - |2+1) = (2r ct)n-1
12r - v - (n - ())))
|| la
n-1 /2r n 4(n 1),² 22(n 1)r + Vnez 4(n - 1)n2
n
n
2(d 1)r + v de 4(d - 1)r2 1)p2
2r v de - 4 1)r²
Plugging in this result, it follows that
I|d (2r (z+l)
sup ||=||ae
(V p)
sup ||=||aSc
(2r)d
2(d-1))r+ v de d 1(d-1)m2
22 de-vd22-1(d11)
(2r)d
d + v
c 2
d+1
d-1
/
d+1
2r
d
d
When y = oc, it's easy to verify that
inf
I II (2r - |2 = (2r +)a
(143)
||
Plugging in the formula above, it follows
II 1-1 (2r 1x()
(2r - c)a
(V /)) = sup 1
(2r) - -1- (144)
sup 11=
[1= Se
(2r)
2r
I PROOF OF THEOREM 3.6
Proof. Recall the definition of fn-morm constraint set of probability measures
Da,e. = {a' + pi : ||æ - x x'lla S c)
(145)
Assume Dr.e.q C DDr.e(e) then
E(c) 2 sup TV(,,))
sup (2 = sup TV 2 TV(,
vEDr.ng
|| 112-5011,5e
11
(146)
26

---

Under review as a conference paper at ICLR 2022
which indicates that (1s,,, ce2 + (u) provides lower bound for E(e). Thus, we only need to estimate the value of TV(,, ce, + p). According to lemma A.33 we have
(V + (t) Vol( (M(KA(ce)+ + K)) =1 ( + +K)
2Vol(K)
Vol(K)
Note that
K Kn (c61 + K)
{IE Rd
[ 12 +... | S.,, |-| E|p + |22| + + | 8 S rp)
x E Rdd
- (r" - (1221 + ................................ |xal" }) S क1 S (r" - (|22 12 + 11)
{ x E Rd (r" (122| +... + |mal))) S s } U { 2 S (r" (|02|" +... + | PD)
:- 12, Ul2 where 92 0s0 = 0
It's easy to verify that Vol( - (92 according to integration by substitution and therefore Vol(K n (ce1 + K)) 2Vol( To estimate the volume of f2g, we first introduce several lemmas below for the convenience of later discussion.
Lemma I.1 (Volume formula of d-dimensional lp norm ball), The volume of d-dimensional Ip ball of radius is given by
Vi P = (2r) r(1 + 2)²
(147)
r(1 + $)
Lemma 1.2. The d-dimensional 1n ball of volume 1 has radius about
dP
2(p)) P((++))))))) ;)
Proof. When dimension is big enough, we can obtain an asymptotic volume estimation of Ip norm ball with radius r.
[(1 1 2 (2r) 2nT
1 T(1 + p
(r(pe)=T(1 ) d
2r(pe)
v(() (2r)
P
(148)
T( T( + 9)
2nd
d=
where the first equality is due to lemma and the approximate equality is due to Stirling's formula about the estimation of gamma function that I(2 1) ss /2Tz ( = Thus, when Vidd) we have
dt
(149)
(ip))T(C) +
Then we estimate the volume of Ip norm ball cap by studying the asymptotic property of the mass
distribution of lp norm ball. To begin with, let's estimate the (d - didieensiol volume of a slice through the center of the Ip ball of volume 1. Note that the ball has radius r = (V: ( 1. The slice is an (d- - -iddmennioonal ball of this radius, so its volume is
= 2d-1 r(1 p) 2)d-1
r(1 1) r(1 #)
2d
(150)
r(1 d=1ه
Using Stirling's 's formula again, when d is sufficiently large, we have v(d-1), d-
22 2d-1 I(1 + p
1jd-1 T(1 +
1)d p
1yd-1 T(1
M(1 +
1
2d
2d-1
p
2d
p
I(1+ + p
I(1 + ②)
z
2T
d-1 p
d-1
2n
d
pe
pe
d-1
1
(1 + -
2n d-1
d=1
2 (v
(
#
+
22
2b4 (d - 1) 1
1-1 +
2nd
za
p
pe
pc
27

---

Under review as a conference paper at ICLR 2022
Figure 6: Comparing the volume of a ball with that of its central slice
where the second equality is due to Stirling's formula for r(1+ ا and [ + f); the third equality just eliminate the exponential and ['(1 + })) Thus, we conclude that the slice has volume about eP when is large.
Then, consider the (d - 1 dimensioonl volumes of parallel slices. The slice at distance from the center is (d -)ddieensin ball whose radius is (r² z²)² so the volume the smaller slice about
e (r - r²)
(1 1 2 ())
d=1
er
Since r is roughly
dF
this is about
2(pe) p r((--)) })
e² (1- 2x(pe) (T ( 1
(1- (e(22 + 4))
~ exp (1
db
Thus, if we project the mass distribution of the Ip ball of volume onto single coordinate direction, we get a distribution with density function f(x) = exp(; - e(2rT(1 + })))) = exp - e( (
Thus, for an lp ball centered at original point O with volume 1 and approximate radius 2(p)) P r(1+
then we can use the integral J exp (2 e0--e(22r(1 })))) dz to estimate the volume between two parallel slices at the same distance from the center. Then the volume of lp ball cap corresponding to
the slice at distance s from the center can be approximated by 1 - So" exp - <2x1l (1+ })) dr.
oF
Note that the ratio of slice's distance d from center to radius about
2(me) 2(1e)r((1+))
Fe(pe)FI(1+ i.. kd
Thus, the volume of cap can be represented as
dF
2(pe) ((1++))
25pe) Fra+ exp (-- e(2rT(1 + b)) dx
p
which is only related the ratio k. Then, we can conclude that for lp ball with radius r, when dimension d is large enough and its cap corresponding to the slice at distance h form the center, then the volume ratio of cap to ball is approximately
1
2n(pe) rat exp (= e(2xT(1 ) do p
(151)
2
Thus,
Vol(S2)
anire) ra
exp
L
e(2x1(1 (1+ + }
(152)
Vol(K)
2
oo
p
28

---

Under review as a conference paper at ICLR 2022
and therefore
(V, E01 + +1) =1 Vol(K (Ee) + K))
2Vol(
Vol(K)
Vol(K)
+f (n(pe) e ro+ ;
exp (= e(2x1(1 + b
2
PROOF OF THEOREM 3.7
Proof. Note that (x) and g(r) are respectively density functions of reference measure p= + and perturbed measure and ((x) defined as g(x) f(z). Therefore
Exarlo(X)] / ((z)g(<)
(())f())d== f())) /
olo))(o)drr olz)f(z)dd
= f (()) + Exxxttl (((())
where the first term contains all the uncertainty in one functional variable g(x) and the second term is constant when sample point smoothing measure μ and specification are fixed. And when E org or equivalently W Wp(u, x + p)) S 6, applying the dual form of Wp distance given in formula 30 and 31 we have
/ p())(S - (x)d = sup per,
/ ((())(g- (x))d===
/ (())g(o)dd PEA,
W1 Wi(u, x +)) = sup sEF
sup
/ [())g())d 8
sup 11
(153)
And when v Da, or equivalently (V, x +1) S E, applying lemma A.3 for absolutely contin- uous measure, we have
TV(n, x + p) / | g(x))dx = / la(x))do S
(154)
follows that (P x μ4 Da.6,p n Dz,c) is equivalent to min ApDDa. E(o(X) according to the definition and therefore equivalent to optimization problem 23 which is obviously convex according to 153 and 154
K
PROOF OF THEOREM 3.8
Recall the following result proved in the section before
Exxulo(X]) = / (z))((x)dr +Ex Ex~etvlo(X)
(155)
When v E Da,., equivalently Wp(u, + a) 6, applying the dual form of W, distance given
in formula 32 and noticing that suppesp(o) l|ul|2 = || R + max(e, cd {} = R"
we have
/ p(v)(g f( -p- 1121)))0111 1 4) (156)
sup (p
equivalently
sup 50(2e y / (())g(2)da S S + (p 1)(2R*)p-1
p(u) My)dy
sup PELip(p(2nt (--1)
(157)
5 where Lip Lip(p(2R*)r=) denotes all maps f from Rdd to RR such that (() vll for all x, y E K. Note OP, according to the definition and therefore can be relaxed into optimization problem which is obviously convex according to 1.77 and 154
(0. x + μ, Dr,6,p (Dzzg) equivalent to min D..... El X))
29

---

Under review as a conference paper at ICLR 2022
L PROOF OF THEOREM 3.9
Proof. For 0 < < 1, the optimization over y can be solved using Lagrangian duality as follows: we dualize the constraints on and obtain
( ((x))(())d + Exxxtulo(X)] + X
/ (()))())d
L(A) = inf
sup
llelh s2g
11
(f [ X sup
/ [(x)g(x)dx -))
Ex~ztall [[([]]]] + inf sup 1lalli 11 / (0(x) + +()))((a))r A6 inf sup llllli |1
1111
Exxxtx(o(X))
S1 22 / (o(z) + f(x)) 28
Exxztulo(X)) +
sup
inf
/((0()) f(x)) A6
[x>z+nlo(X)]
sup
inf
(158)
|I 11all / [0(z)) + f(x)){(x) dx A8
(X>etnld(X)
inf sup
|1 |[ll)
Ex~ztp [xx]) 25 inf s1
||((z) + f(x) A6
(159)
Ex (xxx+v(((X))
A5
(160)
where 158 is due to the choice of q(x) such that sgn(q(=)) = sgn()(x) + f())); 159 is due to
Holder incquality when 1, p oc: 160 due to the fact that |ffll ((x) + f(=) = since the range of Φ(x) is } in applications and f cannot change suddenly when crossing the decision region boundary of due to the Lipschitz constant constraint.
Similarly, for p > we have
L(A)
(/oc))loodd + Ex Exxx++ + 22
11/1 S0(2 / [()))(a)dx - (50 (p (0)-)(22))P-1)
in 11lli (xnaatll((X))
sup
((o=))(o))d
/ f(z)g(x)dr= (5P + (p 1)(2R* -
+ inf
sup
sup (0/
|1all [Illl p--1
+ |1al) [is] Sp((2 /
-Exwatul00)
inf
sup
+ ((o))) + (p (p-1))2R))0-1
Ex [o()]
1 inf
sup
(olz)+ 1(8" + (p 1)(2H))P-1
Ex (xxat)l((X))
sup
inf
+
1(80 + ap- 1)(2
||lll Sp(an)p 1 11
/ [(((z) (()(r))+()))))))))
Exxrtul0(X) 1p |/ 1 158
inf
sup
1 + +(p 1)(2R*)
Exxrtul0f (x)) 2
inf 11)(z))))))))) + f(x)|l - 2(00 + (p 10)2)))))
inf
1 1
Exart (o(x))lo(())) 2 1(87 + (p - 1)(2222))))))
30

---

Under review as a conference paper at ICLR 2022
M PROOF OF THEOREM 3.10
Recall the certificate by using Hockey-stick divergence provided in table 4 Dvijotthh et al. (2020) as below
:(00 0c)
3
e S
2
When 8 = it follows that
00
0,
EHS, I
Besides, recall the relaxation radius using Hockey-stick divergence as below
E = G 20
G(-
2G
1
20
20
And plug it in above inequality, we have
CHS,1 2G 20
15
2
And recall the definition of 0, and 0s we have
Ex~atH 1o [x(X] = 02 - 0,
Thus, our certificate X [x(X) - 2(2G(
20 - -1) 2 0 is equivalent to
0₂ 0g
2G(
1 <
20
2
Thus, the equivalence relation holds.
31


Reviews:
[{"review_id": "jp6sPWIK9n5", "reviewer": "Reviewer_55UR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nThe theoretical analysis is comprehensive and sound.\n\n**Weakness**\n1. There is a huge gap between the theoretical analysis and experimental results. Around 10 Theorems proposed in the paper but I'm not sure whether all of them are necessary yet increase the reading difficulty.\n\n2. Algorithm 1 is unnecessary since it's almost the same as existing randomized smoothing based algorithms.\n\n3. The certified bounds in experimental parts like in Figure 2 and 3 are very trivial. I understand that the results are given by a natural trained ResNet-110, but the certified accuracy on robust trained models is also significant but missing at all in the paper. Moreover, it looks like the proposed method does support robust training but there are no experimental results shown here.\n\n4. The paper claimed multiple times on the efficiency of the proposed compared with Dvijotham et al. (2020) but considering Dvijotham et al. (2020) has experimental results on the ImageNet dataset, it would be more convincing to add experiments on such large-scale datasets. Also, consider most conventional randomized smoothing based methods have constant computation time, so I think the author should turn down the statement \"an improvement upon the state-of-the-art methods in terms of the computation time\" since actually there is only one other method (Dvijotham et al. (2020)) you mentioned here.\n\n5. No comparison experiment with conventional randomized smoothing based methods and a very related work is missing:\n Yang, Greg, et al. \"Randomized smoothing of all shapes and sizes.\" International Conference on Machine Learning. PMLR, 2020.\n", "summary_of_the_paper": "The paper proposed a framework based on Wasserstein distance and total variance distance relaxation as well as Lagrange duality to deal with the analysis of bounded support set smoothing measures. The experimental results show the relative incapability of bounded support set smoothing measures compared with Gaussian smoothing measures.", "summary_of_the_review": "I think the current version of the paper is not well-ready to ICLR quality, there are multiple missing parts in related work and experiments sections. ", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H7VcitC-Jrp", "reviewer": "Reviewer_neZn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths:** \nThe paper is well organized and clearly explains the approach considered. The work is technically impressive and involves some fairly complicated derivations. The proposed approach is significantly more efficient that Dvijotham's approach. There are several results here, though sadly, many of them are negative in nature.\n\n**Weaknesses:**\nA primary downfall of this work is the motivation. It is unclear under what circumstances the designer of a robustness certificate does not have control of the smoothing distribution. The standard and accepted setting is that we desire a classifier that is robust to a specified threat model, and we are allowed to choose whichever smoothing distribution we like to achieve this goal. It is not well motivated why the opposite question should be asked: \"how can one apply the full-information robust certification approach of Dvijotham when the smoothing distribution is fixed a priori?\". Without such a motivation, the theorems read like a laundry list of smoothing distributions for which we can prove properties, instead of a series of hard-fought and significant contributions.\n\nAdditionally, the experiments section is unsatisfying. While it is true that no other works consider uniform distributions when smoothing, no mention is paid to the comparison of Lp-robustness certificates against competing approaches that use the same base classifier (but possibly different smoothing distributions). Is this because the uniform smoothing distribution vastly underperforms when compared to these settings?\n\n**Other notes:**\n- I've never seen \"total variation distance\" referred to as \"total variance distance.\" Maybe this is valid, but it is certainly nonstandard\n- The authors should probably cite Yang et al which describes optimal smoothing distributions to attain Lp robustness.\n", "summary_of_the_paper": "The authors provide robustness certification results for smoothed classifiers. Specifically, the considered setting follows that of Dvijotham (2020) except the base smoothing distribution is specified to have bounded support, and the relaxation follows from an intersection of Wasserstein and TV balls. Under this setting, much of the technical machinery describes which Wasserstein and TV balls are needed to cover these bounded-support smoothing distributions.", "summary_of_the_review": "While technically very sound, this work faces serious problems regarding motivation and provides several negative-seeming results regarding smoothing using uniform distributions. I do not recommend for acceptance, but could raise my score to borderline if a convincing argument of motivation is provided.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7BSe7WxCP3R", "reviewer": "Reviewer_hLLe", "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": "The idea of this paper is to use analytic tools to enable randomized smoothing with bounded smoothing distributions, mainly uniform distribution within a symmetric Lp ball, similar to Gaussian and Laplacian distribution in previous works.\n\nWhile the motivation is good, the empirical performance of the uniformly smoothed classifiers s are much worse than the Gaussian smoothed classifier. It’s worth mentioning that this should be expected as previous work has drawn conclusions that most i.i.d smoothing distributions suffer from the curse of dimensionality [1]. More importantly, in Section 5 of [1], it has been shown that uniform distributions suffer from the curse of dimensionality, in the sense that the certifiable radius is upper bounded by a factor of $(1/d^{1-1/p}$, where $d$ Is the dimensions and $p$ Is for the corresponding $L_p$ measure.\n\nIn some sense, [1] has shown that uniform distributions can be used for randomized smoothing, and the fact that it’s not a good choice.\n\n[1] Kumar, Aounon, et al. \"Curse of dimensionality on randomized smoothing for certifiable robustness.\" International Conference on Machine Learning. PMLR, 2020.", "summary_of_the_paper": "In this paper, the authors aim to improve previous works on randomized smoothing by extending the analysis to allow smoothing measures with bounded support.", "summary_of_the_review": "While the analytic efforts in this paper are both deep and comprehensive, the problem the authors try to solve has been studied with a quite decisive and general conclusion. Considering the overlaps, I cannot recommend accepting this 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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Authors study robustness properties of arbitrary smoothing measures with bounded support using Wasserstein distance and total variation distance. Reviewers pointed out several weaknesses about this work. In particular, they mentioned the paper is not well-organized, comparison with prior work is lacking, the conclusion of the theoretical analysis is not novel and the experiments are not comprehensive. I suggest authors to take these comments into account in improving their work.
Decision: Reject