Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity
Authors: Andrew Craig Cullen
Paul Montague
Shijie Liu
Sarah Monazam Erfani
Benjamin I. P. Rubinstein
Venue: NeurIPS 2022 Accept (2022)
Keywords: certified robustness
adversarial
guarantees
adversarial defence
adversarial attack

Abstract: In response to subtle adversarial examples flipping classifications of neural network models, recent research has promoted certified robustness as a solution. There, invariance of predictions to all norm-bounded attacks is achieved through randomised smoothing of network inputs. Today's state-of-the-art certifications make optimal use of the class output scores at the input instance under test: no better radius of certification (under the $L_2$ norm) is possible given only these score. However, it is an open question as to whether such lower bounds can be improved using local information around the instance under test.  In this work, we demonstrate how today's ``optimal'' certificates can be improved by exploiting both the transitivity of certifications, and the geometry of the input space, giving rise to what we term Geometrically-Informed Certified Robustness. By considering the smallest distance to points on the boundary of a set of certifications this approach improves certifications for more than $80 \%$ of Tiny-Imagenet instances, yielding an on average $5\%$ increase in the associated certification. When incorporating training time processes that enhance the certified radius, our technique shows even more promising results, with a uniform $4$ percentage point increase in the achieved certified radius.

Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity
Andrew C. Cullen Paul Montague² Shijie Liu'
Sarah M. Erfani' Benjamin LP. Rubinstein' Schooo of Computing and Information Systems, University of Melbourne, Parkville, Australia 2 Defence Science and Technology Group, Adelaide, Australia andrew.. cuw..enunimemlll edu. au
Abstract
In response to subtle adversarial examples flipping classifications of neural network models, recent research has promoted certified robustness a solution. There, in- variance of predictions to all norm- bounded attacks is achieved through randomised smoothing of network inputs. Today's 's state-of-the-art certifications make optimal use of the class output scores at the input instance under test: no better radius of certification (under the L2 norm) is possible given only these score. However, it is an open question as to whether such lower bounds can be improved using local information around the instance under test. this work, we demonstrate how today's 's "optimal" certificates can be improved by exploiting both the transitivity of certifications, and the geometry of the input space, giving rise what we term Geooeerricall-IInfone Informed Certified Robustness. By considering the smallest distance to points on the boundary of set of certifications this approach improves certifica- tions for more than 80% of Tiny-Imagent instances. yielding an on average 5% increase in the associated certification. When incorporating training time processes that enhance the certified radius, our technique shows even more promising results, with a uniform percentage point increase in the achieved certified radius.
Introduction
Learned models, including neural networks, well known to be susceptible having the output changed by crafted perturbations to an input, that preserve the inputs semantic properties (2). Neural knoww
networks not only misclassify these perturbations- known as adversarial examples- but they also assign high confidence to these incorrect predictions. These behaviours have been observed across wide range of models and datasets, and appear to be a product piecewise- interactions [13]
Crafting these adversarial examples typically involves gradient-based optimisation to construct small perturbations. These attacks have been applied to both black- and white-box models [31] and can be used to target class changes, to attack all classes [10]. or even introduce backdoors into model behaviour (5). To mitigate the influence of these attacks, defences have typically been designed to minimise the effect of specific attack (or attacks). Such defences are known as best response strategies in a Stackelberg security game where the defender leads the attacker. Best response defences inherently favour the attacker, as deployed mitigations can be defeated by identifying undefended attack frameworks. Moreover, the defender typically has incorporate the defence training time, and as such cannot response reactively to newly developed attacks.
To circumvent these limitations, certified guarantees of adversarial robustness be constructed to identify class-constant regions around an input instance, that guarantee that all instances within a norm- bounded distance (typically L2) are not adversarial examples. Certifications based randomised smoothing of classifiers around an input point are in sense optimal { based only on the prediction
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

class scores at the input point, no better radius is in general possible. Despite this, such certifications fail to use readily available-yet still locallinfortt inal--iformation: the certifiabilitty of points nearby to the input of interest. The key insight of this work is that these neighbourhood points may generate certified radius large enough to completely enclose that of a sample point, improving the radius of certification. This process can be extended to use the intersection of the regions of certification of multiple points, and the nature of the input domain itself to generate larger certifications. This leads to our main Geommttrinni Infoormedd Certified Robustness- that produces certifications exceeding those of the hitherto best-case guaranteed approach Cohen et al. (2019) [8.
Background and literature review
Bounding mechanisms Conservative bounds upon the impact of norm-bounded perturbations can be constructed by way of either Interval Bound Propagation (IBP) which propagates interval bounds through the model; Convex Relaxation, which utilise linear relaxation to construct bounding output a manner that generally provides tighter bounds than IBP [25]. In contrast to Randomised Smoothing, bounding mechanisms employ augmented loss functions during training, which promote tight output bounds 42 at the cost of decreased applicability. Moreover they both exhibit time and memory complexity that makes them infeasible for complex model architectures or high-dimensional data 40 21
polytopes over input bounded perturbations [34 26 41 45 46 37 28
Randomised smoothing Outside of bounding mechanisms, another common framework for de- veloping certifications leverages randomised smoothing (20). in which noise is applied to input instances to smooth model predictions, subject to sampling distribution that is tied the Lp-norm of adversarial perturbations being certified against. In contrast to other robustness mechanisms, this application of the noise is the only architectural change that is required to achieve certification. In the case of Iz-norm bounded attacks, Gaussian sampling of the form
x y:
where y, i.i.d. NN(0, Vi E [I....,N}
(1)
employed for all test-time instances. These N samples are then used estimate the expected output of the predicted class of x by way of the Monte-Carlo estimator
Fy larg max fa(x + Y) = =]]
Σ 1 farg max fa(x,) =
While this Monte Carlo estimation of output expectations under randomised smoothing is test-time process, model sensitivity to random perturbations may be decreased by performing adversarial training on such random perturbations. To mitigate the computational expense of large N sample sizes during each training update, training typically employs single draws from the noise distribution.
Smoothing-based certifications Based randomised smoothing, certified robustness can guaran- tee classification invariance for additive perturbations up to some Lp-norm r, with recent work also considering rotational and/or translational semantic attacks [2 7). Lp-norm certifications were first demonstrated by way of differential privacy (20) [1. with more recent approaches employing Rényi divergence 22), and parametrising worst-case behaviours g 33 By considering the worst-case Le Lg-perturbations, Cohen et al. (2019) purports that the largest achievable pointwise certification is
p (Eo(x)) क (Eiix))
(3)
Here (Ea, } are the two largest class expectations (as per Equation (p). is the noise, and $ is the inverse normal CDF, or Gaussian quantile function.
3 Geometrically-nfoommeee certified robustness
While the work contained within this paper can be applied generally, for this work we will focus upon certifications of robustness about L2-norm bounded adversarial perturbations, for which we assume that the difficulty of attacking a model is proportional to the size of the certification, based upon the need evade both human and machine scrutiny [12 Thus, constructing larger certifications such context is inherently valuable.

---

Xi
Transitivity
(h) Multiple Transitivity
Boundary Treatment
Transitive certification exemplars. The Green, Red, and Black circles represent hyper- spheres of radius ri (by Equation 3) about points x; E (1,2,3), The resulting certifications r', r", and are described within Equations 12 and T6
Figure I:
The Black line represents the domain boundary.
This specific Lp space is of interest due to both its viability defence model, and the provable guarantee that Cohen et al. produces the largest possible certification for any instance [8]. Over the remainder of this section will document how it is possible improve upon this provably best-case guarantee by exploiting several properties of certified robustness.
3.1 Exploiting transitivity
While it is provably true that Equation (3) is the largest achievable certification for any point x, is possible to exploit the behaviour of points in the neighbourhood of x in order to enhance certifiable radius. To achieve this, consider the case of second point x', that exists within the certifiable radius of x. As both points must correspond to the same class, it then follows that the union of their regions of certification can be also be considered as a region of certification, leading Definition 3.1
Definition 3.1 (Overlap Properties of Certification). A radius of certification r; about x; can be calculated by evaluating Equation 3 at x,, This certification guarantees that no point x ||x - -x S r. can induce a chance in the predicted class. That this shape d-dimensional hypersphere for input data x E Rd allows us to introduce the notational shorthand
Bp(x,,r) (x E R* x:llr rr) S, (x E R*|[I x; ri)
(4)
represent the region covered by the hypersphere and its surface. It follows from this definition that that if (x(x1, r1) n (x(x2, r2) # 6, which ensures that the class predictions at x2 and x2 match, then the region of certification about x; be expressed as (p(x), ri) U (x2,
However typically we are concerned not with the size of the region of classification invariance, but rather the distance the nearest adversarial example. If it possible find some x' such that its region of certification completely encircles that of the certification at the following definition demonstrates that the certification radius about x can be increased.
Lemma 3.2 (Set Unions Certified Radius). If x1 and x2 have the same class associated with them and Bp (P(xI,T1) C. Bp(x2,T2) T2). then the nearest possible adversarial example- and thus, the certifiable
distance r' 2 r from X1, where
/' 12
X22
xillp
(5)
Proof. The closest point on the surface of ( 12) to x1 must exist on the vector between X; and X2. Thus r' min (r2 + [x-- x)]lp), which takes the form of Equation (5)
As such, we can recast the task of constructing a certification from being strictly analytic function to the nonlinear optimisation problem terms second ball with certified radius r2 centred at x
max 12 - |x2 x1l1p E
with Figure Ta providing two-dimensional exemplar. Crucially, the above formalism does not require obtaining a global optima, any r' ri yields improved certification at X1.

---

3.2 Multiple transitivity
To further enhance our ability to certify, let us consider the set of points and their associated certifica- tions (x1, r1, X2, r2.... .2,...xx; Fn). If the union of Bp [Iegt.......) Br (x, ri) simply-connected, then the certification across this set can be expressed as r(m) = min xcaB ||x xillp- where OBp the boundary of Bp. This can be further simplified by imposing that x, E (2 r2) > 2 and that (r(x).r,) & (p rk) V(j 2, k 2) to ensure that hyperspheres exist near the boundary of S2 and yielding a certification of
(n))
min xES
x - x where S, = S2 n (U for n 2 2
(7)
Here Sn is a (d -iddimnsio manifold embedded in Rdd
Lemma 3.3 (Optimal positioning of X3 in the case of = 3 ). Consider the addition of new hypersphere at some point X3 with associated radius vas, which has an associated boundary S3. If it true that
By(xs, 13) & Bp(X2, and (x(xs, O (x r2) +0
(8)
Bp(xs,Ts) of (p( Vf E [0, / with F 2
( (Eo - + -- (E)
(9)
then the largest possible certification r" by Equation 7 is achieved at
x3(s) X1 + Sr
X1 X2
for some E [0,
(10)
X1 X2 ll
Proof. The closest point to x1 upon S2 is located at
X1 X2
x
(11)
X X2 ll
where r' is defined by Equation 6 Thus any improved radius of certification x" >> r is only achievable if (x(x3, r3) satisfies E (xx, r3) and Equation 8 Then by symmetry, y" is the maximally
achievable radius of certification if Equation 9 hold and if x3 is defined by Equation 10
While finding some X3 satisfying Equations 8 and 10 trivial, proving Equation 9 would require an exhaustive search of the input space [0, I However, even in the absence of such a search, Equation rtsilill provides the framework for a simple search for x3. which follows Figure Ib
Lemma 3.4 (Certification from two eccentric hyperspheres). Xss is defined by Equation 70 in fashion that satisfies Equation 8 then an updated certification can be achieved in terms of some Xs((s)
defined by Equation 70 by way of
dz(r3
d3)
+ d3 dr
d3)
nd max
where
sE[0.1]
d2 + d3
d2 = ||x X1
d3 = [xx - x1|l
f3 = 0 (b
(Fo(xa()))) - -- (-\(([(xsss)))
2
(12)
Equation Gholds, then this is the largest achievable certification for 3.
Proof. By symmetry we can define the arbitrary rotational mapping f Rd - Rd from x; + y: by
way of y, f(x x)), subject to the condition
Vi + 0 for i E (1,2) and Vj + k. for some l such that j. k E (1,,,.... dd
(13)
then the intersection of the hyperspheres centred about X2 and X3 occurs at
33 - ||y y3l | 2
=2yj2,4(22 + ds) + d3 d3
(14)
13 - r3 + d2 d2
2y2,k
d2 + dg

---

This is consequence of our mapping y = f(x-(xxx x1) preserving distances under rotation, giving that
$2, = ||x² x || = d2, and with the equivalent also holding for V3,k-
As consequence of our choice of coordinate system, it follows that = |lyl| and
(r")² = lly - y2l1* 21/2,x dz
d2r3 d2r + d2dg d2dp
(15)
=r2 -2 +
d2 + d3
which is an equivalence to Equation (12p
While Equation 7 holds for any 2, the certification radius beyond cannot be enhanced by adding any one single additional hypersphere without contradicting Lemma [3.4 This a result of S3 being (d 1)-dimensional manifold in Rd, the entirety of which must be enclosed to improve the certification. An example of this can be seen with the two equidistant intersections between S2 (in Red) and S3 (in Black) in Figure lb While multiple spheres could be constructed to completely enclose $3, the number required grows exponentially with d due to the sphere packing kissing number problem ( This growth complexity makes adding additional spheres beyond n 3 infeasible. Further details of this are contained within Appendix A.2
3.3 Boundary treatments
Without loss of performance or accuracy, we can freely scale the inputs of neural networks such that X1 [0. 1] However in the majority of cases subset of (x L1) will exist outside [o, 1]d While this observation is trivially true, it has influence on the radius of certification achieved by Equation 3 due to the symmetry of (x(x1,7) r). However, the asymmetric nature of (x r2) about x1 guarantees that if Bp (X2, r2) exceeds [0, 1] then the closest point to x1 within the feasible domain must have an associated distance f > r', as is demonstrated within Figure Ic This allows us to make the following observation about improving the feasible radius of certification.
Lemma 3.5 (Boundary Certifications by way of Eccentric Circles). The eccentricity of Bp L2) bounding region about X1, and the potential for subset of Bp(x2, Lg) to exist outside the feasible space for instances allows us to construct an updated region of certification where
f max kE(1.....d)
[r2 (I22 2² 2 0]
(16)
(*t mI,K)² + ( (Vr3 (Ek x2x)2 1|xx2 x1122 (x2, -1 x111))
{i
if < 0.5
where 2
if > 0.5
where 1 is an indicator function acting upon its operator.
Proof. In contrast to the prior proof, for this problem we retain the coordinate system of the input space. To support this, we introduce the notation that Xa [n, 2..,,,,..,TT,.l.. Tn,d). If we let Ih E {0, 1), then the intersection between (x L2) and the bounding surface in dimension creates a bounding hypersphere of the form
Σ (x. 22,)) = ==
(#x x22
(17)
1=
which yields an effective radius F. = / (2k x22x
By denoting the projection of x and x2 onto the bounding hyperplane in the k-th dimension as Xi and X2, then the distance from x, to Equation (17) must take the form
F6 v | 11 + (Fz - X 1)
2
(18)
-V(2x - x² + 12 (zx- - x2 v ||x - x11² (x2 - x x1,,)²
By imposing that 2 = 1 when the k-th component of x, is greater than 0.5, and 0 otherwise, follows that max4s (0.1...... 2& must be improved radius of certification.
5

---

Algorithm Single Bubble Loop.
1: Input: data x, samples N, iterations M, true-label
2: for to MM do
3: Eo. E,, L2, j = Algorithm 2 x +W
4: if itee
5:
r'= L2 -1|x' -x x
6:
r' > ro then
7:
8:
end if
9:
x'
x + Vor'
Mrr (7 calculated by Barzilai-Borwein [. Positive branch is selected if
j = i, otherwise the negative branch brings x' towards the region which j = i.}
10: end if
end for
3.4 Algorithms
To demonstrate how the above certification approaches can be applied in practice, Algorithm demonstrates the application of Equation (5) through a simple, gradient based solver. Such a solver is highly applicable for solving such problems, due to the inherent smoothing nature of randomised smoothing being applicable both to the function space and its derivatives. To implement the multiple transitivity based approach of Section 3.2 Algorithm|] I can trivially be adapted to evaluate derivatives with respect to Equation (12). The boundary treatment of Section 3.3 does not require any additional calculations, but instead is simply the result of applying Equation (16) to the output of Algorithm
4 Extracting gradient information from non-differentiable functions
Implementing the aformentioned process requires the ability to evaluate the gradient of the class expectations. This is problematic, as each class expectation is described terms of finite sum of non-diffee non-differentiable indicator functions, as is seen in Equation 2 Within this work we have implemented two mechanisms to circumvent these conditions. The first substitutes the arg max operation with a Gumbel--Sotmax [15]. In doing so, the class expectations are rendered differentiable.
The second approach involves recasting the Monte-Carlo estimators as integrals of the form
E Jarg max fo = k] - / larg max fy) =
(19)
where w(y, x) is the multivariate- and the symmetry of the underlying space allows for the construction of undifferentiable gradients by
probability distribution centred around x. This formalism,
V fe(x) = k] Vx
Jarg max fely) = k]l(y,
(arg max foly) k) x x)dy
Jarg max foly) = k6] (y x)w(y. x)dy
(20)
aarg max fo(x;) = ki[(;; - xx)
No
where X; = x x (0,
While this derivation novel, the resultant gradient operator reflects those seen in prior works 33 important to note that such sampling process is inherently noisy, and it has previously suggested that the underlying uncertainty scales with the input dimensionality [27].
The relative performance of these two for the above approach and the Gumbel-Sofine approaches- will be tested the following section. For the case of the double transitivity of Section 3.2 our experiments suggest that uncertainty in the
labelled 'Approximate' and 'Full"

---

MNIST
by CIFAR-10
Tin--Tmmaaen Imagmeet
0.40
Calen o -
Appnee
0.35
Bet Tull
188-
0.5
Oslen = 1.
Cortifei Accurieg
Appros
0.6
0.4
0.25
Bat Full
0.5
0.4
0.15
0.2
0.1
0.05
0.0
0.5
1.0
1.5
0.0
0.3 1.0
1.3
0.0
0.5
1.0
1.5
R
R
Figure 2: The Certified Aceuracy: the proportion of samples correctly predicted and with certified radius greater than R. Blue represents Cohen, while Green and Red respectively represent the best sub-variant utilising either the Approximate or Full derivative approaches. Dashed lines for a = 0.5, solid lines for 1.0.
analytic derivatives produces deleterious results. As such derivatives for the multiple transitivity approach are exclusively considered through autograd for both the Full and Approximate methods.
Experiments
Configuration To evaluate the performance of our proposed certification improvements, con- sidered the certified radius produced for MNIST 19), CIFAR-10 18] and Tiny-Imagenet [16], the
latter of these is a 200-class variant of Imagenet 4 which downsamples images to 3 60 60. All datasets were modelled using the Resnet18 architecture in PyTorch (32, with Tiny- Lin-Immaenet also utilising 2D adaptive average pooling.
For both MNIST and CIFAR-10, our experimentation utilised a single NVIDIA P100 GPU core with 12 GB of GPU RAM, with expectations estimated over 1500 samples. Training employed Cross Entropy loss with a batch size of 128 over 50 epochs. Each epoch involved every training example was perturbed with single perturbation drawn from NN00, a²), which was added prior to normalisation. Parameter optimisation was performed with Adam [17]. with the learning rate set as 0.001. Timy-Imagenet training and evaluation utilised P100 GPU's and utilised 1000 samples. Training occurred using SGD over 80 epochs, with a starting learning rate of 0.1, decreasing by factor of 10 after 30 and 60 epochs, and momentum set 0.9.
The full code to implement our
experiments can
be
found at
https://g/t thub.
Certified accuracy To explore the performance advantage provided by our technique, we begin by considering the performance of Cohen et al. against the best of our approaches using both the approximate and full derivatives, as seen in Figure 2 While there are only minor differences between the two derivative approaches, there are clear regions of out performance relative Cohen across all tested datasets. The proportion of this increase appears be tied the semantic complexity of underlying dataset, with decreases in predictive accuracy (visible at R = 0) appearing to elicit greater percentage changes in the achieved certified radius, as evidenced by the results for Imagenet.
Semantic complexity drives decrease in the overall confidence of models, inducing a decrease in the separation between the highest class expectations Eg and E, While this process shrinks the achievable certified radius, a higher E₁ provides more information to inform our gradient based search process, allowing for the identification of larger certifications. This property would suggest that samples with larger R would exhibit decreased difference between our techniques and that of Cohen al. would decrease, as smaller values of E, provide less search information. However, it appears that singularities in the derivatives of $- as E + {0, 1} counteract the decreased information provided by the second highest class, leading to the contradictory performance best observed in the MNIST experiments of Figure 2 at 0.5.
7

---

8)
0.5
b) = 1.0
Perventage Improvenent
Single (Appos)
25-
Domble (Appux)
Bousdery (Appos]
20
Stugle (Fall)
Domble (Full)
Boundary (Pull)
10-
5-
0.4
Figure 3: Percentage improvement in the Certified Radius of Cohen et al. for varying r. This measure presents the median improvement over [r- 0.075, Equivalent figures for MNIST and CIFAR-10 are found in Appendix A.3
instances relative to
Approssimate
1.0
Propat
0.6
0.4
0.0
Figure 4: Proportion of correctly predicted instances for which each approach yields the highest certification for Tiny-Imagenet. Red, Green, and Orange represent the boundary treatment, Double transitivity, and Single transitivity, with both ties Cohen et al. in Blue. MNIST and CIFAR-10 results can be seen in Appendix A.3
Rather than strictly considering the best performing of the Approximate and Full solvers, we can also delve into the relative performance of the underlying solvers. Notably there is moderate increase in the average percentage improvement of Figure the = 0.5 and o = 1.0 cases. This would appear to belie our previous statement regarding larger certifications yielding smaller improvements, due to the asymmetry class information. However, an equivalent certification for 1.0 has significantly more information about the second class (due to the multiplicative influence of o). allowing for greater improvements from our gradient based search. That there is clear demarcation between the Full and Approximate solver variants reflects the uncertainties introduced by Equation (20). That the approximate technique is still applicable verifies the utility of approach even when the final layer is strict arg function, rather than Gumbel-Softmax,
The trends in performance across a are further explored in Figures 4 and 6 the latter of which demonstrates that the median performance improvement increases quasi-linearly with This is driven by both an increase in the performance the certifications themselves, and in the number of instances able to be certified in improved fashion. This later property stems from the smoothing influence of o, with larger levels of added noise inducing decreases in the difference between the highest class expectations, improving the ability for our search based mechanisms to identify performance improvements. Here increases in the performance of the boundary treatment are correlated with larger radii of certification, due the multiplicative influence of upon Equation (
Numerical performance inherently induces increases the computational cost of finding these improved certifications, as shown in Table [ While analytically approximating the derivatives for the first eccentric hypersphere yields lower certified accuracy, the fact that the corresponding computational cost decreases by factor of more than 4 emphasises the value of this approach. Interestingly, while the Approximate
The numerical optimisation process at the core of our certification process

---

Table Average wall clock time (in seconds) for each computational technique, for single sample evaluated over 1000 draws under noise.
Dataset
Approx.
Full
Cohen
Single
Boundary
Double
Single
Boundary
Double
M
0.08
0.66
0.66
2.94
2.17
2.17
3.97
C-10
0.08
0.76
0.76
3.83
2.08
2.08
4.62
T-1
0.12
1.13
1.13
5.61
2.87
2.86
7.95
Cobon MACER 0.5
Approx
Certified Proportion
0.5
Best Full 0.5
Cobon MACER o 1.0
0.4
Best Approx
0.3
0.2
0.1
0.0
0.50
0.76
1.00
1.50
1.75
R
Figure Certified Accuracy comparing the Cohen certification (when trained incorporating MACER) for CIFAR-10, as well as the best sub-variant utilising either the Approximate or Full derivative approaches. Dashed lines for 0.5, solid lines for a 1.0.
method does also utilise auto-differentiation for the Double variant, the increase computational cost from the Single to Double variants is significantly higher than for the Actual approach. This is surprising, as the Approx variant derives smaller values of r', which should in turn lead to a smaller, easier to navigate search space for r". Instead it counter-intuitively appears that smaller r' induces a search space for r" which is less convex, and more difficult to converge upon.
Alternative training routines Recent work has considered the potential for enhancing certified robustness by modifying the underlying training regime to incentivise maximising the expectation gap between classes [33. One such approach MACER 44) which augments the training time behaviour by considering not just the classification loss, but also the c-robustness loss, which reflects proportion of training samples with robustness above a threshold level. Such a training time modification can increase the average certified radius by 10 20%, however doing does increase the overall training cost by more than an order of magnitude.
When applying Geometrically-Iniee Informedd Certified Robustness to models trained with MACER, Figure demonstrates that our modifications yield an even more significant improvement than those observed in Figure 2 Under training with MACER, the best performing of our techniques yielded an approximately percentage point increase in the average certification. From this it is clear that while MACER does enhance the certified radii at sample point, it also induces enough smoothing in the neighbourhood of the sample point to allow transitivity to yield even more significant improvements than are present without MACER.
However, we must emphasise that while such training time modifications do producer consistently larger certifications, doing so requires significantly more computational resources, both in terms of training time and GPU memory, as compared to the more traditional certification training regime. We also emphasise that training with MACER requires degree of re-engineering. In contrast the training mechanism used for the remainder of this work only requires the addition of noise to samples prior to being passed through the model, and thus imposes significantly fewer engineering considerations.
Limitations While the principles of our Geometrically Informed Certified Robustness are extensible to I. spaces, our experimental work has so far only considered I-2-norm bounded perturbations due to the guarantee of best possible certification in this space provided by Cohen et al.. Further

---

Median Paronteg hage Improvenent
20
15
10-
Appnox
Double
5-
Approx Mod
Artual
Actual Undble
Actual Mud
1.5
2.3
3.5
Figure Median percentage improvement the Certified Radius achieved by each our approaches relative Cohen al. for Tiny-Imagenet across the level of additive noise The median was chosen to provide a fair and representative comparison to Cohen et al., that filters out outliers the percentage improvement when <
experimentation could also consider both these general spaces and broader range of training methods, which have been shown be able to tighten the achievable radius of certification (24).
We note that enhanced robustness certification have the potential to counter beneficial applications of adversarial attacks, such as those used promote stylometric privacy [3. However, we believe this bawkacks is significantly outweighed by the potential for enhanced confidence about models for which adversarial incentives exist.
Finally, we also emphasise that our approach requires M evaluations of the certified robustness, which each require N Monte-Carlo draws. resulting in time- and memory-complexin of O(MN) and O(NS) respectively, where the size of the output logit vector. With respect to the memory- complexity, this shared by any randomised smoothing based approach, and could be improved by implementing batching across the Monte-Carlo process. While the time cost can be problematic in some contexts, we emphasise that this framework is both requires both fewer adaptations the training loop and significantly less training time relative to bound propagation approaches [21 36). We believe these costs can be reduced by performing the optimisation stages with N' N model draws, and by potentially reusing model draws across the iterative process to approach the O(N) time-complexity prior randomised smoothing based certifications. Even present, we believe that the increased computational cost is not intractable, especially for human ieman-in--hhe in-the-loop certifications.
6
Acknowledgements
This research was undertaken using the LIEF HPC-GPGPU Facility hosted at the University of Mel- bourne. This Facility was established with the assistance of LIEF Grant LEI 701002000 This work was also supported in part by the Australian Department Defence Next Generation Technologies Fund, part of the CSIRO/Data61 CRP AMLC project. Sarah Erfani is in part supported by Australian Research Council (ARC) Discovery Early Career Researcher Award (DECRA) DE220100680.
Conclusions
This work has presented mechanisms that can be exploited to improve achievable levels of certified robustness, based upon exploiting underlying geometric properties of robust neural networks. In doing so our Geometrically Informed Certified Robustness approach has been able generate certifications that exceed prior guarantees by average more than 5% at a 0.5, with the percentage increase improving luasi-linearly with a. Incorporating training time modifications likes MACER yields more promising results, with the best performing of our approaches yielding a 4 percentage point increase the certified proportion at a given radius. Being able to improve upon the size of these guarantees inherently increases the cost of constructing adversarial attacks against systems leveraging machine learning, especially in the case where the attacker has no ability to observe the size of the robustness certificate.
10

---

References
[1] Jonathan Barzilai and Jonathan M Borwein. Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8(1):141-148, 1988.
[2] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmniić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion Attacks Against Machine Learning Test Time. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 387-402. Springer, 2013.
[3] Michael Brennan, Sadia Afroz, and Rachel Greenstadt. Adversarial Stylometry: Circumventing Authorship Recognition to Preserve Privacy and Anonymity. ACM Transactions on Information and System Security (TISSEC), 15(3):1 2012.
[4] Fabrício Caluza Machado and Fernando Mário de Oliveira Filho. Improving the Semidefinite Programming Bound for the Kissing Number by exploiting Polynomial Symmetry. Experimental Mathematics, 27(3):662-366 369, 2018.
[5] Nicholas Carlini and David Wagner. Towards Evaluating the Robustness of Neural Networks. In 2017 IEEE Symposium on Security and Privacy (SP). pages 39-57. IEEE, 2017.
[6] Ping-yeh Chiang, Renkun Ni, Ahmed Abdelkader, Chen Zhu, Christoph Studer, and Tom Goldstein. Certified Defenses for Adversarial Patches. arXiv preprint arXiv:2003.06693 2020.
[7] Wenda Chu, Linyi Li, and Bo Li. TPC: Transpormation-Specific Smoothing for Point Cloud Models. arXiv preprint arXiv:2201. 2022.
[8] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified Adversarial Robustness via Random- ized Smoothing. In International Conference on Machine Learning, pages 1310-1320, PMLR, 2019.
[9] HSM Coxeter. An Upper Bound for the Number of Equal Nve-Ovelgg Spheres that can Touch Another. In Convexity: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society, volume 7, page 53. American Mathematical Soc., 1963.
[10] Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting Adversarial Attacks with Momentum. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9185 9193, 2018
[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography Conference, pages 265-284. Springer, 2006.
[12] Justin Gilmer, Ryan P Adams, Ian Goodfellow, David Andersen, and George E Dahl. Motivating the Rules Of The Game for Adversarial Example Research. arXiv preprint arXiv:1807.061: 06732, 2018.
[13] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Hareessing Adver- sarial Examples. arXiv preprint arXiv:1412.6572. 2014.
[14] Leo A Goodman. On Simultaneous Confidence Intervals for Multinomial Proportions. Techno- metrics, 7(2):247-254, 1965.
[15] Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gunbel-Softmax. arXiv preprint 161iv:1611.000 144, 2016.
[16] Justin Johnson, Fei-Fei Li, and Andrej Karpathy, Tiny ImageNet Visual Recognition Challenge, Accessed 2022-01-10.
[17] Diederik P Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv preprint arXiv: 1412.690,, 2014.
[18] Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto, 2009.

---

[19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE. 86(11):2278-25 -3224, 1998.
[20] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified Robustness to Adversarial Examples with Differential Privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[21] Alexander Levine and Soheil Feizi. Randomiddd Smoothing for Certifiable Defense against Patch Attacks, Advances in Neural Information Processing Systems, 33:6465-6475, 2020.
[22] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified Adversarial Robustness with Additive Noise. In Advances in Neural Information Processing Systems, pages 9459-9469, 2019.
[23] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. TSS: Transformation-Speeiiee Smoothing for Robustness Certification. In Proceed- ings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 535-557, 2021.
[24] Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double Sampling Randomized Smoothing. arXiv preprint arXiv:2206.077 12 2022.
[25] Zhaoyang Lyu, Minghao Guo, Tong Wu, Guodong Xu, Kehuan Zhang, and Dahua Lin. Towards Evaluating and Training Rerifiably Robust Neural Networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 4308 4318, 2021.
[26] Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable Abstract Interpretation for Provably Robust Neural Networks. In International Conference on Machine Learning, pages 3578 -578.. PMLR, 2018
[27] Jeet Mohapatra, Ching- Yun Ko. Tsui-Wet Wei Weng, Pin- Yu Chen, Sijia Liu, and Luca Danicl. Higher-Order Certification for Randomized Smoothing. Advances in Neural Information Processing Systems, 33:4501-4511 2020.
[28] Jeet Mohapatra, Tei Weng, Pin-Ye Chen, Sijia Liu, and Luca Daniel. Towards Verifying Robustness of Neural Networks against a family of Semantic Perturbations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 244 252, 2020.
[29] Oleg R Musin. The Kissing Number in Four Dimensions. Annals of Mathematics, pages 1-32, 2008.
[30] Andrew M Odlyzko and Neil JA Sloane. New Bounds on the number of Unit Spheres that Can Touch a Unit Sphere in n Dimensions. Journal of Combinatorial Theory, Series A, 26(2):210- 214, 1979.
[31] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, 7. Berkay Celik, and Anan- thram Swami. Practical Black-Bor Attacks against Machine Learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506-519, 2017.
[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An Imperative Style, High-Performance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8035. Curran Associates, Inc 2019.
[33] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. In Advances in Neural Information Processing Systems, 2019.
12

---

[34] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang, A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks. Advances in Neural Information Processing Systems, 2019.
[35] Kurt Schüitee and Bartel Leendert van der Waerden. Das Problem der Dreizehn Kugeln. Mathe- matische Annalen, 125(1):325-35) 334, 1952.
[36] Zhouxing Shi, Yihan Wang, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Fast Certified Robust Training with Short Warmup. Advances in Neural Information Processing Systems, 34:18335-18349, 2021.
[37] Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev, An Abstract Domain for Certifying Neural Networks. Proceedings of the ACM Programming Languages, 3(POPL): 30, 2019.
[38] Cristina P Sison and Joseph Glaz. Simultaneous Confidence Intervals and Sample Size De- termination for Multinomial Proportions. Journal of the American Statistical Association, 90(429):366-36, 1995.
[39] David J Smith and Mavina K Vamanamurthy, How Small is a Unit Ball? Mathematics Magazine, 1212):101-107, 1989.
[40] Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-CROWN: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. Advances in Neural Information Processing Systems, 34, 2021.
[41] 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 International Conference on Machine Learning, pages 5276-5285 PMLR, 2018
[42] Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh. Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond. Advances in Neural Information Processing Systems, 33, 2020.
[43] Kaiyu Yang, Jacqueline Yau, Li Fei-Fei, Jia Deng, and Olga Russakovsky. A Study of Face Obfuscation in Imagenet. arXiv preprint arXiv:2103.08 0619, 2021.
[44] Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsich, and Liwei Wang. MACER; Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2020.
[45] Huan Zhang, Tei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 4939-4948. Curran Associates, Inc., 2018.
[46] Huan Zhang, Tei Weng, Pin-Yt Chen, Cho-Jui Hsich, and Luca Daniel. Efficient Neural Network Robustness Certification with General Activation Functions. In Neural Information Processing Systems (NeurIPS), 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the Limitations section of Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In the Limitations section of Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] This has been included in the supplementary materials, with license details included therein.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] In Section
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [No] As all experimental results are based upon metrics calculated over more than 1000 samples, the size of the underlying error bars are small enough to be negligible.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] In Section [
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] In Appendix A.I
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "n9GLIZGYWyF", "reviewer": "Reviewer_diuY", "summary": "This paper proposes to exploit the certified robustness of samples in the neighbourhood of a given data in order to enhance the certifiable radius of the given data. To be specific, the authors leverage the intersection of the certified regions of multiple neighbourhoods. Compared to the previous state-of-the-art method, the experimental results validate the effectiveness of the proposed method in enhancing certified robustness.", "questions": "- Could the authors provide any insights on how to accelerate the proposed method?\n- I am a bit confused about the meaning of some part of the title — ‘Double Bubble, Toil and Trouble’. Could the authors provide some explanations about this part?\n", "limitations": "The authors have pointed out the limitations in details in the main paper.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The proposed method is interesting and novel. The method is (arguably) supported by theoretical analyses.\n+ The authors conduct comprehensive experiments. The results on various datasets, different hyperparameters, and different transitivity approaches all support the claim that the proposed method can improve certified robustness.\n\nWeaknesses\n- It seems that the proposed method could be somewhat more time-consuming compared to previous state-of-theart method.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jN2L82rH3dI", "reviewer": "Reviewer_R63M", "summary": "The paper presents geometrically-informed certified robustness to improve the certified radii computed by randomized smoothing techniques. The paper presents three approaches for geometrically-informed certified robustness: transitivity, multiple (double) transitivity, and boundary treatment. The evaluation shows that the proposed approaches equipped with two optimization algorithms can outperform the baseline.", "questions": "1. The paper mentions \"exponential growth in the number of hyperspheres that need to be solved\" on lines 146-147. Then how about the results with small n like $n=4,5,6$?\n2. Do the three approaches subsume Cohen et al.? If they do, please state the claim in the main paper and why Figure 4. has some cases won by Cohen et al.? If they do not, please discuss the reason or provide the counterexample.  \n3. What is $r_1$ in Figure 3. \n4. What are the \"Approx\", \"Approx Mod\", \"Actual\", and \"Actual Mod\" in Figure 5?\n5. What is the choice of the iteration $M$ across all experiments?", "limitations": "The paper only presents the geometrically informed certified robustness on the l_2 norm as stated in section 5. However, it is encouraged for authors to discuss other useful norms such as the l_1 and l_inf norms. Specifically, it is not easy to extend the multiple transitivities to other norms. \nAlgorithm 1 needs M iterations, each requiring thousands of Monte-Carlo sampling. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, it is a paper with a novel and effective idea but needs improvement in writing. \n\nStrength:\nThe paper presents geometrically-informed certified robustness to improve the certified radii computed by randomized smoothing techniques. The paper identifies a hard problem and proposes simple yet effective approaches to tackle the problem. I like the idea of geometrically-informed certified robustness because the bound computed by randomized smoothing techniques is tight under assumptions that they over-approximated the worst-case behavior of the machine learning classifier **only** with respect to the constraints of E0[x] and E1[x]. In other words, other approaches ignore the underlying classifier's complex behavior (geometry). However, this paper uses additional information by choosing $x'$ with $E0[x']$ and $E1[x']$, i.e., the geometry around $x'$ to improve the certification. Ideally, if we choose a finite set of $x'$, we could approximate the geometry around $x$, yet this approximation is expensive and requires exponential computation.  \n\nWeakness:\n- The writing in sections 3 and 4 should be greatly improved:\n  1. I appreciate that the paper provides three figures for illustration. However, it is important to clarify these circles, i.e., mark out x1, x2, x3. It would be better to show the computation of these 2D examples.\n  2. Define notation before usage and the inconsistency in notations:\n    * $r_2(x_2)$ in Eq 5; \n    * $x_3(s)$, $s$, and $r'$ in Eq 6; \n    * $j$ and $k$ in Eq 8 (Here, $j$ should be $\\forall j$ and $k$ is a special dimension); \n    * $\\hat{r_k}$ in Eq 13. What are $x_3', r_3'$ in definition 3.3? \n    * The notation of $y_{2,k}$ appears in the proof of Lemma 3.4, yet the definition appears later in the proof of Lemma 3.5. Moreover, the definition later of $x_n$ is wrong, should be $\\{x_{n,1}, \\ldots, x_{n,d}\\}$. \n    * At the beginning of the proof of Lemma 3.5 until Eq 12, $x_i$ should be $z_i$.\n    * $c$, $\\lambda$, $\\Gamma$ are not used in Algorithm 1.\n    * $i$ should be $k$ in the second line of Eq 15.\n  3. State the intuition of Eq 6. Maybe say x_1, x_2, x_3 should be in the same $R^{d-1}$ hyperplane? \n  4. In the proof of Lemma 3.4, mention that $\\mathbf{y}_1$ is at the origin after translation and rotation. \n- The paper only presents the l_2 norm case as stated in section 5. However, it seems not easy to extend the multiple transitivities to other norms, e.g., l_1 and l_inf.  \n\nOther comments:\n1. Missing related works: \n  * The paper states, \"Certified robustness has not, however, extended to rotational or translational modifications\" on lines 68-69. However, there are already works [1,2] that handle the 2D and 3D image transformations.\n  * Another recent paper [3] presents a different idea to improve the certified radius of randomized smoothing by incorporating another distribution.\n2. It is interesting to explore the combination of the geometrically-informed certified robustness with other training methods [4,5] like [3] does.\n\n[1] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, Bo Li, TSS: Transformation-Specific Smoothing for Robustness Certification\n\n[2] Wenda Chu, Linyi Li, Bo Li. TPC: Transformation-Specific Smoothing for Point Cloud Models\n\n[3] Linyi Li, Jiawei Zhang, Tao Xie, Bo Li, Double Sampling Randomized Smoothing\n\n[4] Jeong, J. and Shin, J. Consistency regularization for certified robustness of smoothed classifiers\n\n[5] Jeong, J., Park, S., Kim, M., Lee, H., Kim, D., and Shin, J. Smoothmix: Training confidence-calibrated smoothed classifiers for certified robustness.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aGO2Qr0A3vU", "reviewer": "Reviewer_JQxG", "summary": "This paper addresses the problem of designing local robustness certification procedures for neural classifiers. The primary insight of the paper is that given an input x, instead of simply calculating the radius of the robust ball B centered at x, one should also consider calculating robustness radii at other points in the ball B. It is easy to see that the network is robust in the entire region defined by the union of B and the robust balls centered at these additional points. Moreover, if such additional points are suitably chosen, one can achieve a larger robustness radius at x.\nThe paper, in particular, focuses on local robustness certification via Randomized Smoothing. In order to choose suitable additional points for robustness certification, the authors formulate optimization problems for choosing up to two additional points to certify. These optimization problems are solved at inference time to choose the additional points to certify. Since the robustness radius calculation used by Randomized Smoothing requires computing expectations, special care is needed when solving these optimization problems via gradient descent. The paper presents two different approaches for solving the optimization problem so that the required gradients can be calculated.\nEmpirical evaluation is performed using MNIST, CIFAR-10, and Tiny-Imagenet datasets. The evaluation suggests that the proposed technique is indeed able to produce larger certifiable balls and improve upon the certified accuracy of randomized smoothing.", "questions": "Apart from the questions above, below are some more questions and comments:\n(1) Line 72,73 says that the certified radius formula (Equation 3) of Cohen at al. gives a lower bound on the certified radius. On the other hand, lines 36, 91, 95 etc state that this is the largest certifiable radius. Is it a lower bound or a tight bound? I believe its the latter but please provide clarification\n\n(2) Line 75: runner -> runner-up\n\n(3) Line 79: binomial -> binary?\n\n(4) Defn 3.1 seems incomplete. First, what is the definition of B_P(x1,r1), B_P(x2,r2)? Second, is it not the case that x1 and x2 have to be in each other's certifiable regions for the definition to make sense? To me, it seems like Defn 3.1 is not really a definition, but it needs to be a theorem with a proof.\n\n(5) Line 114: recast the certification problem -> recast the certification radius\n\n(6) Line 123: r_n seems overloaded since its already used to denote the certified radius for point x_n. Should r_n instead be r''' or something?\n\n(7) Line 122 and Defn 3.3: Questions about the meaning of S_n, s, and various questions about Defn 3.3 are mentioned above under \"weaknesses of the paper\".\n\n(8) Proof of Lemma 3.4: Questions about the proof are mentioned under \"weaknesses of the paper\".\n\n(9) Line 151: Why was the notation switched from r1 to L1?\n\n(10) Line 164: x_n is defined as {x_1,n, x_2,n, ...}. On the other hand, in Equation (8), in y_2,j y_3,j, the j'th coordinate of points y2 and y3 are being referred. Please make the subscript order consistent.\n\n(11) Questions about Algorithm 1 have already been mentioned earlier\n\n(12) Equation 14: i should be replaced by k\n\n(13) Equation 15: All the i's need to be replaced by k\n\n(14) Line 225: How does increase in R affect the value of E1? Isn't E1 independent of R?\n\n(15) Questions about Figure 2, 3, and 5 have already been mentioned earlier.\n\n(16) In Table 1 reporting the average amount of time required for certifying a single input? How many samples are drawn while reporting the results for Cohen et al.? Is it the same number of samples as for the other approaches, i.e., 1000 samples?\n\n(17) Cohen at al. already introduces significant overheads (due to sampling and evaluating the model on thousands of inputs). Would it not be a problem to add their overheads by one to two orders of magnitude as shown in Table 1?", "limitations": "The authors describe some limitations of their approach in Section 5 under the para labeled \"Limitations\". It would be nice to have some more discussion about the overheads introduced by the approach.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths of the paper:\n(1) The proposed idea to increase the size of the certified balls is original yet intuitive. Its a broadly applicable idea that can be applied to other local robustness certification procedures, apart from Randomized Smoothing.\n\n(2) The empirical results provide compelling evidence that the idea could lead to certification gains in practice.\n\nWeaknesses of the paper:\nThough I really like the idea presented in the paper, the presentation and quality of writing in the paper needs significant improvement before the paper can be published. I list my main concerns below:\n\n(1) The mathematical writing in the paper is very hard to follow. Often, the symbols are either not defined or not used in a careful manner. I could barely follow Sections 3.2 and 3.3. Though I believe I have a sense of what the authors are trying to say, the actual technical definitions and proofs were not helpful in understanding the material. For instance, consider Defn 3.3. I have no idea what its trying to say. What are s and r' there? Is s a vector quantity? If yes, then the rightmost term in Equation 6 involves a multiplication of two vector quantities. Is it supposed to be a dot product of two vectors? What is s anyway? Why is it of dimension R^(d-1) when the inputs are of dimension d? Line 128 says, \"assuming the above definition is true\". What does this mean? How can a definition be false? Does Defn 3.3 need to be a theorem instead? Similarly, consider the proof of Lemma 3.4. What are y_2 and y_3? What is k in equation (8)? I couldn't follow the proof at all and have no idea if Lemma 3.4 is indeed true or not.\n\n(2) Related to the above point, even the descriptions of the mathematical statements are hard to follow. For instance, consider the first two paras of Section 3.3. Even after reading them multiple times, I was not able to figure what the authors were trying to say. My understanding is that the boundary treatments can sometimes allow larger robustness radius because the closest point on the red circle (referring to Figure 1) is outside the feasible bounded region, so one can consider points on the red circle that are farther away as being closest to the test input. However, the text in Section 3.3 did not help me in figuring this out. It would be very helpful, for instance, to explain the situation using the already existing Figure 1.\n\n(4) Algorithm 1 needs to be more carefully written. Where are the input parameters c, \\lambda, \\Gamma used? Is Algorithm 2 called on line 3? Why not write it as Algorithm2(x',N,\\sigma) instead of Model(x + ....)? In fact, writing it as Model(x + ....) is incorrect since line 3 is not executing the model at a particular input but instead executing Algorithm 2. There is no description of how step size \\gamma is calculated on line 9 even though a paper is cited. And what is the justification for line 11? It would help to have a more detailed description of Algorithm 1 in Section 3.4.\n\n(5) The presentation of the empirical results is also quite confusing. Although a lot of detail is provided, important high-level details are missing. For instance, I was not able to figure out how to interpret Figure 3. What does the x-axis show? What does Figure 5 report? Percentage Improvement in what quantity? Is it reporting percentage improvement in \"certified proportion\"? Also, why is y-axis of Figure 2 labeled \"certified proportion\"? Cohen et al. call it \"certified accuracy\" which is a much more informative name. If Figure 5 is indeed reporting median percentage improvement in certified accuracy, at what radius is the certified accuracy being calculated?\n\n===============================  \nPost one round of rebuttal:  \nChanged *Contribution* from 3 to 4  \nChanged *Rating* from 3 to 4 \n  \nPost second round of rebuttal:  \nChanged *Presentation* from 1 to 2  \nChanged *Rating* from 4 to 6 ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LJ-krRdJsX", "reviewer": "Reviewer_7Pxn", "summary": "The authors provide a method to enlarge the certification radii given by randomised smoothing based approaches. They use gradient based methods to find a points (and calculate their certification radii) in the proximity of the original input point, such that the combined information yields a larger certificate for the original input point. Two tricks are employed to be able to calculate the gradients yielding two methods: The ‘Full’ method, where the Gumble-Softmax is used to replace the argmax and the ‘Approximate’ method, which is based on reformulations and approximations.  The approaches are evaluate on MNIST, CIFAR-10, Tiny-Imagenet - the networks are based on Resnet18. ", "questions": "- How would the improvements look like where more recent state of the art methods (as above) where to be used to train the network?\n- What is the standard deviation between different training runs?  \n- Eq. 6: what does $r’$ refer to? The same as in Eq. 5?\n- Lemma 3.4: Is Lemma 3.4 optimal? Is $x_3$ here now fixed or variable? In Eq. 7, it seems as if $d_3$ and $r_3$ depend on $x_3$, whereas in Eq. 9 and Eq. 10 there seems to be a (further?) dependence of $y$ on $x$. \n- 152: To what does “feasible domain” refer to? \n- Did the authors consider to evaluate on ImageNet? \n", "limitations": "The authors have mostly covered the limitations well. However, it remains unclear how scalable the method is to ImageNet. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors tackle an important problem, as certified robustness is an important research field. The ideas are interesting and the contributions are to the best of my knowledge novel. In the evaluation section, the authors give good intuition when explaining their results. The ideas are general and seem (at least partially) applicable to approaches certifying the robustness of geometric perturbations.\n\nThe experimental evaluation seems weak in the sense that the authors compare to [5], but not showcase how much their method would improve the results on some of the more recent papers published in this direction including MACER (https://arxiv.org/pdf/2001.02378.pdf), SmoothAdv (https://arxiv.org/pdf/1906.04584.pdf) or Consistency Smoothing (https://arxiv.org/pdf/2006.04062.pdf). Further, Section 3.2 and 3.3 are difficult to follow. The proof of Lemma 3.4 is not well explained and could hence not be checked for correctness. This is likely due to some minor confusion that can be easily clarified by the authors. More in the questions. Formalisation and maybe some pictorial illustrations might improve this section. Similarly for Lemma 3.5. Also, it remained unclear how the method would perform on challenging datasets including ImageNet. \n\nRegarding the related work: In line 52 and following, there is a misleading claim. The time and memory complexity are not the problem. For example interval bound propagation can be applied to analyse high dimensional inputs on large networks. The practical problem is the loss of precision linear relaxations suffer from. Further, the authors mention multiple times in the paper that “Certified robustness has not, however, extended to rotational or translational modifications …”. I encourage the authors to take a look at the following papers, the last 2 are randomised smoothing based: \n\nhttps://arxiv.org/pdf/1712.01785.pdf\n\nhttps://dl.acm.org/doi/10.1145/3290354\n\nhttps://papers.nips.cc/paper/2019/file/f7fa6aca028e7ff4ef62d75ed025fe76-Paper.pdf\n\nhttps://arxiv.org/pdf/1912.09533.pdf\n\nhttps://arxiv.org/abs/2002.12463\n\nhttps://arxiv.org/pdf/2002.12398.pdf\n\nMinor: In line 121, “the” appears twice in a row and $x_j$ is typed differently. \n\n*** \nAfter the authors response, i have increased the score. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept