Projected Randomized Smoothing for Certified Adversarial Robustness
Authors: Samuel Pfrommer
Brendon G. Anderson
Somayeh Sojoudi
Venue: Accepted by TMLR ()

Abstract: Randomized smoothing is the current state-of-the-art method for producing provably robust classifiers. While randomized smoothing typically yields robust $\ell_2$-ball certificates, recent research has generalized provable robustness to different norm balls as well as anisotropic regions. This work considers a classifier architecture that first projects onto a low-dimensional approximation of the data manifold and then applies a standard classifier. By performing randomized smoothing in the low-dimensional projected space, we characterize the certified region of our smoothed composite classifier back in the high-dimensional input space and prove a tractable lower bound on its volume. We show experimentally on CIFAR-10 and SVHN that classifiers without the initial projection are vulnerable to perturbations that are normal to the data manifold and yet are captured by the certified regions of our method. We compare the volume of our certified regions against various baselines and show that our method improves on the state-of-the-art by many orders of magnitude.

Published in Transactions on Machine Learning Research (09/2023)
Projected Randomized Smoothing for Certified Adversarial Robustness
Samuel Pfrommer
san.gfrommerrBeekkkle.... edu
Department of Electricol Engineering and Computer Sciences University of California, Berkeley
Brendon G. Anderson
byandersonn@berreeeyy.. edu
Deportment of Mechanical Engineering University of California, Berkeley
Somayeh Sojoudi
sojoudi@berkeley.co edu
Deportment of Electricol Engineering and Computer Sciences Department of Mechanical Engineering Universily of California, Berkeley
Reviewed on OpenReview: https: // // opw.review.ee.e... net/ permno id= FObbuuLuu
Abstract
Randomized smoothing is the current state-of-the-art method for producing provably robust classifiers. While randomized smoothing typically yields robust f2-ball certificates, recent research has generalized provable robustness to different norm balls as well as anisotropic regions. This work considers a classifier architecture that first projects onto a low-dimensional approximation the data manifold and then applies a standard classifier. By performing randomized smoothing the low-dimensional projected space, we characterize the cortified region of smoothed composite classifier back in the high-dimensional input space and prove tractable lower bound its volume. We show experimentally SVHN that classifiers without the initial projection are vulnerable to perturbations that normal to the data manifold and yet are captured by the certified regions of our method. We compare the volume of our certified regions against various baselines and show that our method improves on the state-of the-trt by many orders of magnitude.
CIFAR-10 and
1 Introduction
Despite their state-of-the-art performance on a variety of machine learning tasks, neural networks are vulnerable to adversarial inputs inputs with small (often human-imperceptible)) noise that is maliciously crafted to induce failure (Biggio al. 2013 Szegedy al. 2014 Nguyen al. 2015). This sensitive behavior is unacceptable in contemporary safety-critical applications of neural networks, such autonomous driving
Bojarski et. al. 2016 Wu et. al. 2017 and the operations of power systems (Kong et al. 2017p. The works Eykholt et al. (2018) and Liu et al. (2019a) highlight the validity and eminence of these threats, wherein both physical and digital adversarial perturbations are shown to cause image classification models to misclassify vehicle traffic signs.
Heuristics have been proposed to defend against various adversarial attacks, only to be defeated by stronger attack methods, leading to "arms race" in the literature (Carlini & Wagner 2017 Kurakin et al. 2017 Athalye et al.] 2018 Uesato et al.) 2018 Madry et al. 2018). This has motivated rescarchers to consider certifiable robustness theoretical proof that models perform reliably when subject to arbitrary attacks of
Source code reproducing our results available
GitHub

---

Published in Transactions on Machine Learning Research (09/2023)
bounded norm (Wong& & Kolter 2018
Weng et al 2018 Raghunathan et al. 2018
Anderson et al. 2020
Ma & Sojoudi, 2021). Randomized smoothing, popularized in Lecuyer et al. (2019); Li et al. (2019) Cohen et al. (2019), remains one of the state-of-the-art methods for generating classifiers with certified robustness guarantecs. Instead of directly classifying a given input, randomized smoothing intentionally corrupts the input with random noise and returns the most probable class, which, intuitively, "averages out" any polential adversarial perturbations the data.
The seminal work Cohen et al. 2019) certifies that no adversarial perturbation within certain 62-bal can cause the misclassification of smoothed model using isotropic Gaussian noise of fixed variance. Recent works have attempted to certify larger regions of the input space by lurning to randomized smoothing with optimized variances (Zhai et al., 22200) input-dependent variances (Alfarra et al., 2020 Wang et al. 2021 J
anisotropic distributions (Eiras al. 2021), and semi-infinite lincar programming (Anderson et al. 2022
However, for a fixed variance, the certilied radius is upper-bounded by a constant in the dimension d of the input (Kumar et al. 2020), implying that the volume of the certified lz-ball degrades factorially fast. ((KTTT + +)) where I' is Euler's gamma function and K is some positive constant (Folland 1999 Current input-dependent and anisotropic smoothing approaches have similarly been shown to suffer from the curse of dimensionality (Súkeník et al. 2021
The small certified regions of randomized smoothing in high dimensions corroborate empirical findings that show increased robustness when precomposing classifiers with dimensionality reduction, e-g-; principal component analysis projections (Bhagoji et al., 2018) and autoencoders (Sahay et al. 2019). These findings align with the manifold hypothesis, which posits that real datasets lie on low-dimensional manifold in a
feature space (Fefferman et al. 2016), and related results showing that perturbation directions most useful to an adversary are ones normal to this manifold (Jha ct al. 2018 Zhang et al., 2020b).
Thus, projecting inputs onlo the manifold, or at least a low-dimensional subspace containing the manifold, should increase classification robustness. Methods taking this approach, such as Mustafa et al. (2019) and Alemany & Pissinoul (2022), have worked well as heuristics, but lack theoretical robustness guarantees. Motivated by these works, aim to enlarge the certifiably robust regions of randomized smoothing by performing the smoothing in low-dinensional space in which adversarial access to the data's 's statistically insignificant yet vulnerable features has been eliminated.
1.1 Contributions
We propose projected randomized smoothing, whereby inputs are projected onto a low-dimensional linear subspace in which randomized smoothing is applied before classification, Our method combines the empirical successes of dimension-reducing projection methods with the theoretical guarantees of randomized smoothing to achiove the following contributions:
1. We theoretically characterize the geometry of the certified region in the input space and prove tractable lower bound on the volume of this certified region.
2. We empirically demonstrate that classifiers can be attacked along subspaces spanned by statistically insignificant features that contribute nothing to classification accuracy, which are vulnerabilit ies that projected randomized smoothing certifiably eliminates.
3. Experiments on CIFAR-10 (Krizhevsky et al. 2009 and SVHN Netzer et al. 2011 show that our method yields certified regions with order-of of mfw.n-iude larger volumes than prior smoothing schemes.
1.2 Related works
Robustification via dimensionality reduction. The work Bhagoji et al. 2018) was the first to consider lincarly projecting inputs onto the top principal components of the training data before classification as a means improve empirical (not certified) robustness. The authors of (Sahay al. (2019) nonlinearly preprocess test data using denoising and dimensiion-rddueing autoencoders, and find substantial increase in
2

---

Published in Transactions on Machine Learning Research (09/2023)
classification accuracy when the inputs are subject to the popular fast gradient sign method attack. The work [afna et al. (2018) projects an input onto its top-k discrete cosine transform components to defend against "60 -attacks, but this empirical defense was later broken using adapative "ty"-attccss (Tramer et al. 2020), which directly motivates our approach for cortified projection-based robustness. The work Sanyal eet al. (2018) introduces a low-rank regularizer to encourage neural network feature representations to reside in a low-dimensional linear subspace, which is found to enhance empirical robustness. In Mustafa et al. (2019), the authors use super-resolution to project images onto the natural data manifold and obtain high empirical robustness for convolutional neural networks. [lemanyy & Pissinou (2022) shows that decreasing the codimension of data, i.e,, decreasing the difference between the intrinsic dimension of the data manifold and the dimension of the input space in which it is embedded, generally leads to increased robustness of models defined on that input space.
Shamir al. (021)) | posits that learned decision boundaries tend to aligu with and "dimple" around the natural data manifold, and that adversarial perturbations are normal to this manifold. This finding supports our approach for certifiably eliminating off-manifold perturbations by projecting onto a low-dimensional approximation of the data manifold. The authors of Awasthi et al. (2021) reformulate principal component analysis to find projections that are robust, with respect. to projection error-a a method that naturally complements our framework- and give robustness guarantees for the Bayes optimal projection- based classifier in the special case of binary Gaussian-distriiutee data. The work Zeng et al. (2021) precomposes classifiers with orthogonal encoders and performs randomized smoothing in the encoder's low-dimensional latent space means to speed up the sample-based smoothing procedure. To the best of our knowledge, [Zeng et al. (2021) is the only work that provides certified robustness guarantees for general models and data distributions when using dimensionality reduction at the input-al all of the other referenced works are heuristic- and their choice of orthogonal encoders ensures that the certified ba-ball in the input space has the same radius as that in the latent space. Notably, their approach is highly conservative in estimating the input-space certified set as il relies on Lipschitzness of the orthogonal encoding layers, and is thus employed primarily as means lo speed up randomized smoothing. On the other hand, the method we propose uses a connstiiiaaioonmotvviaia projection for which we prove more general (anisotropic) certicates that capture off-manifold perturbations
Certification via randomized smoothing. The work Cohen et al. (2019) develops randomized smoothing using an isotropic Gaussian distribution with unput-nneeennent variance to obtain certified lg- falbals. A subsequent line of works attempts to generalize randomized smoothing to other classes of certified regions,
e.g., Wasserstein, "Lu"-, er,, and bbllbalss (Levine & Feizi 2020; Lee et al. 2019 Teng et al. 2020; Yang
let al. 2020). Various approaches have been taken to enlarge the certified regions. For example, Salman el al. (2019) unifies adversarial training with randomized smoothing to obtain state-of-the-as certified lg-radi..
The authors of Zhai et al. (2020) incorporate the certified l--radius into the model's training objective as a means to enlarge certified regions. The method in Zhhag et al. (2020a) optimizes over base classifiers to increase the size of more general ba-balls. Li et al. (0022) employs a second smoothing distribution to tighten
robustness certificates.
Optimizing the certified region pointwise in the input space has also been considered, but generally these methods require locally constant smoothing distributions to ensure that the resulting certificates are mathe- matically valid (Alfarra et al. 2020 Wang et al.) 2021 Súkeník et al., 2021 Anderson & Sojoudi 2022). To
further strengthen the robustness guarantees of randomized smoothing, the recent works Firas et al. (2021): ) Erdemir et al. (2021); ; Tecot 2021 ) have turned to certifying anisotropic regions of the input space. For
example, Eiras et al. 2021 maximizes the volume of certified ellipsoids and generalized cross-polytopes of the form {z E _ Az p b) for p [1,2), allowing for the certification of perturbations that are potentially larger in magnitude than the minimum adversarial perturbation. We show in Scction !| that our proposed method is able to outperform these methods by leveraging dimensionallty reduction. As is standard practice in the randomized smoothing literature (Cohen et al. 2019 Yang et al., 20200 Jeong et al. 2021 Zhai et al.) 2020 Lee et al.) 2019), our emphasis is on certified robustness and not empirical robustness we refer the reader to Maho et al. (2022) for connections between certified and empirical robustness under randomized smoothing, and in particular the difficulty in constructing and evaluating suitable empirical attacks.
3

---

Published in Transactions on Machine Learning Research (09/2023)
We also emphasize that volume (Lebesgue measure) is the natural scalar measure for the size of anisotropic certified regions of the input space and is the standard notion considered by prior works (Liu et al. 2019b Eiras et al. 2021
Tecot 2021).
1.3
Notation
We denote the set of real numbers by R. The fy-norm of vector & E IK" is denoted by ||=||, whereas the general 6-norrm is given an explicit subscript ||>||>- The range and nullspace of a matrix U E IR are denoted by R(U) S R and (UU) _ IR", respectively. The n x n identity matrix is written as Ln- For a random variable X with distribution D and a mcasurable function f. the expectation of f(X) denoted by EX=D (X)). The multivariate normal distribution with mean μ R" and covariance Σ E R is given by N), The cardinality of set S is written as [S]. For Lebesgue-measuurbble set S C R contained in A-dimensional affine subspace, we write (S),,, termed the k-dimensional volume of S, to mean the Lebesgue measure of S within that affine subspace. For sets S,T C R", we denote their Minkowski sum by S + = fx + y x E S, E T}- Fuler's gamma function is denoted by r. Recall that [(n) = (n - 1)! when n is a positive integer.
2 Classifier architecture
Consider the task of classifying inputs from a zero-centered cube C²= --1 C Rd into distinct classes y 21, c) Under the randomized smoothing framework, we begin with a given classifier fe: Idd [0, 1]s, parameterized by 0, that maps into the probability simplex over e classes. The problem hand is to increase the robustness of fo with certifiable guarantees.
Vanilla randomized smoothing. We give a brief overview of how this would be accomplished using vanilla randomized smoothing (Cohen et al 2019). Randomized smoothing takes the base classifier fe and smooths with Ganssian noisc on the input to yiold the associated smoothed soft and hard classifiers
(x)
E So(x + e), g(x) = arg max ('(x)9: yEy
where (x)) denotes the yth component the vector (*xx) and a is a hyperparameter. Cohen et al. (2019 Theorem 1) then gives, under certain conditions, certified balb for a particular input x E R": namely, that g(x 5) g(x) for all ||o]| < R where R > 0 is determined by the confidence of the smoothed classifier at æ. We leverage this result for approach and refer interested readers to Cohen et al. (2019) for additional details on the computation of the smoothing expectation and precise formula for R.
Projected randomized smoothing. Motivated by the relationships between robustness and dimensionality described in Section 1 we consider p < d and let P: Rd + Rp be a projection into Rp defined by P(x) U'z where Rd & semi-orthogonal matrix satislying UTU = Ip- Similarly, we let the reconstruction P: RP Rdd be defined by P(a)= = Us. Throughout, we let U1, UI,..., ra-p E IRd be an orthonormal basis for N(UT) and let ud-ptl...., Ud E Rdd denote the orthonormal columns of U. In practice, we instantiate the columns of U as the first p principal components of a random subset of the training dataset, although our hot and theory hold for any orthonormal set of vectors. With the dimension- projection P in place, we consider the classifier architecture consisting of the composition
f == o PoP.
In particular, f first uses P project inputs into the low -ow-dimensional space Rp and then reconstructs the inputs in lossy way using P before feeding them through the classifier fo- We generally finetune fo to account for the slight image corruption associated with the projection step.
The sero-centered cube is used without loss of generality instead of [o, 1jd for notational convenience and compatibility with results from the mathematical literature.
4

---

Published in Transactions on Machine Learning Research (09/2023)
R(U)
P
P
So
f*(x)
Od C Rd
(a)
(b)
Figure (a)) Projected randomized smoothing architecture. Inputs a are projected into low-dimensional space by P, smoothed with Gaussian noise, and then reconstructed by P and classified by So. Lb) Illustration of projected randomized smoothing for a binary classification task (circles vs. squares). The base classifier decision regions are shown in green and red. The white circle represents the smoothed dccision boundary in RP, 1, with the projected subspace depicted by the dotted line and projected points depicted as solid dots. The blue area represents the certified region around æ in Rd of the projected randomized smoothing classifier g.
We now propose projected randomized smoothing, wherein randomized smoothing is performed in the compressed space R". To do so, we define fo: IP + [o, 1] by fo = fo P so that f fo P. and we smooth so by adding Gaussian noise in its low-dimensional input space to obtain a new classifier fă: R" + [0, 1J defined by
(x)
+c)
(1)
(0,,00,))1,)
The new overall smoothed soft classifier is then given by
fg P.
(2)
and its structure is illustrated in Figure la The corresponding hard classifier is then given by the arg max of the soft classifier
g(x)
arg max f (())y- vEY
3
A graphical illustration of our approach for d = 2 is shown in Figure lb To summarize, classifying input
E Rd using projected randomized smoothing amounts to applying the mapping x + g(z) defined by [
through and is for that we seek to derive certified regions of the input space.
3 Robustness certificates
In this section, we construct certified regions for g around arbitrary inputs & the high-dimensional space Rd. The key idea is that f3 is by-ball robust the low-dimensional space RP, and the preimage of this ball in the original input space is then "large" it includes the inputs in (UT)). We formalize the geometry of the certified region in Section 3.1 and introduce our metric of interest as the volume of the certified region restricted to the unit cube of feasible inputs. In Section 3.2 provide lower bound on this volume
For ease exposition, assume throughout that all arg max yield singleton and therefore equality signs may used unambiguously.
5

---

Published in Transactions on Machine Learning Research (09/2023)
in high-dimensional spaces that involves solving an -oom linear regression. Section 3.3 compares the asymptotic behavior of the volume of the certified region of 9 with the standard b2-ball certificates as the input dimension grows large. Finally, we discuss runtime and limitations in Section 3.4 For ease of exposition, all proofs are deferred to the appendices.
3.1 Characterizing the certified region geometry
In the following two propositions, we characterize the geometry of the projected randomized smoothing classifier the high-dimensional input space Rd based on the certified fz-robustness of the classifier fä the low-dimensional projected space Rº.
R - [0, 1]e is said to be certified at 5. with radius Definition 1. Let & E IR and R 2 0. The classifier fg: R
arg arg max fō + +)yy = arg max fi)), DEY
NEY
for all å Re satisfying ||ā|| < R.
Proposition Let x E RRd and R 2 0. 1f fä is certified at P(x)= = Urx with rddius R, then g(x + 5) = g(x) for all E (R) C CRd where
A) (8 E Rd | 811 S R}
Proposition 2
Let R 0. The certified region (R) can be expressed as the Minkowski sum (
B (R) + -UT),, where B S Rd is a p-dimensional ball embedded into R(U):
By = (310a-p+1+
................................ +... B, ||||| S R, e R
Propositions and characterize the geometry of the certified region of our classifier Proposition ! provides an easy-to-check condition for an input to lie in the certified region, while Proposition @ formalizes the same geometry as a hypercylinder consisting of a low-dimensional sphere that is "extruded" along the nullspace of the projection P, allowing us to certify adversarial off-manifold inputs of potentially very large magnit that are projected back onto the natural data manifold. Intuitively, the certified region A (R) is potentially much larger than fz-ball of radius R in Rd, it captures perturbations in the nullspace of UT whose dinensionality is large when < d.
We note that the above characterization of the decision region geometry holds analogously for other norm ball certificates in the projected space (i.e., the bblll certificates of Levine Feizi (2021)) While the following theory is presented for the concrete case of ba-ball certificates, it also applies this more general setting. Concrete experiments with other certificates is an exciting line of future work.
3.2
Lower-bounding the certified region volume
To compare a standard by-ball certificate with our certified region A A AR(R), which does not immediately come equipped with notion of "radius," " we adopt the perspective of recent works, e.g., Liu et al. (2019b) Firas et al. 2021 Tecot [202]), by considering our metric of interest to be the volume of the certified region. One immeddate issue is that the volume of A (R) is infinite since ((UT) is an unbounded subspace. To
enable meaningful comparisons, we restrict ourselves to measuring the volume A (R) contained in the cube Cdd [-1/2, 1/2]d of possible inputs. This amounts to computing the volume
Va (Ctd n (R))
(4)
where we recall that Va measures d-dimensional volume in Euclidean space, and A (R) (x+d: de (R)),,
with R chosen such that fg is certified at P(x) with radius R so that g(z') = g(x) for all x' E A by Proposition [ Computing the volume in 4 is highly nontrivial, especially high-dimensional input spaces. Instead, we develop tractable lower bound on Va(O" n A (R)) throughout the remainder of this section. Since A (R) contains affine subspaces, this derivation rests heavily on theory regarding cube-subspace

---

Published in Transactions on Machine Learning Research (09/2023)
intersections in high dimensions. The most important result for our purposes comes from Vaaler 1979 which showed the following.
Theorem 1. Let Sy be a k-dimennsonal linear subspace of R Then Vx n (kk 2 1.
This result proved Good's conjecture and generalized previous result for the k d - 1 case (Hensley 1979 We begin with an extension of Theorem to cubes of non-unit side length, and then to intersections with affine subspaces which do not necessarily contain the origin.
Corollary 1 Let Sk be k-dimensional linear subspace of Rd and rCat be zero-centered cube of side length 0. Then Va(rO" n Sk) r
Corollary
Let x E Rdd and let Sx(x)) C IRd be the k-dimensiioal affine subspace
k a,4 : R
Sx(x)
x
spanned by arbitrary vectors u.,.., Uk and passing through æ. Let t 2 O be the minimal -nom of a point in (x)):
inf (
1
inf ocRt
x +
0
(5)
Then, for all r> 21, holds that Ve(rCd (x)) 2 (r - 21)/
Corollary 2 generalizes Corollary | to affine subspaces. If Sx(x) contains the origin, t= 0 and the bound from Corollary is recovered. We are now ready to present the main result of this section.
Thcorem Let x E Cdd, let be defined as in 5 with k =d= p, and let R [0, t). If fa is certified at P(x) Tx with radius R, then
TP/2
ValCa n
I +) R1 2R 21)
(6)
Notice that the lower bound given in Thcorem docs not monotonically increase with the certified radius R from the randomized smoothing performed in RR. Therefore, if the certified radius R is large enough, we may able to improve our lower bound on the volume Va(O'd n (R) by using a smaller certified radius (which is course still valid), and in particular, we may choose the optimal such radius to use according to the following fored-form expression.
Proposition
Let and R be as in Theorem
The lower bound
6 is mazimized as follows:
p(1 - 2t)
7P/2
min R
E arg max rE(o,
P (1 2r - -21)
2d
[ + 1)
The overall certification procodure derived in this section is summarized Algorithm We note that our method inherits its ABSTAIN behavior from the original randonized smoothing Monte Carlo sampling scheme (Cohen et al. 2019: namely, evaluate the certification confidence using many Caussian-perturbed samples, and if the prediction or certification procedures do not resolve with uscr-specified confidence, ABSTAIN is returned.
3.3 Asymptotic behavior of the volume bound
We brielly compare the volume lower bound of the projected randomized smoothing certified region
that of standard certified fz-ball. The volume of d-dimensional ba-ball Ba(R) == {a Rd || s R) of
radius R > 0 is well-known (e.g., see Folland (1999. Theorem 2.44, Corollary 2.55)) to be
n7 dd/2
Va (B)(R))
Rd.
(8)
T( +
7

---

Published in Transactions on Machine Learning Research (09/2023)
While the numerator of (8) scales exponentially in d, the denominator I(3 + 1) scales factorially, leading to tiny l2-ball certified volumes in high-dimensional input spaces. By contrast, the denominator in our bound 6 scales factorially in the projected dimension p, where < d. This suggests dramatic improvements in
the volume of our certified regions: while the numerator in ( might be exponentially smaller than that of
the denominator is smaller by a factorial factor. We thus expect the volumes of projected randomized
smoothing to dominate at higher dimensions. We verify our analysis experimentally in Section 4.2 and
illustrate some simulated certified volume ratios over a range of values for p and d in Appendix A.1
Algorithm 1 Prediction and certification
def PREDICT, CERTIFY as in Cohen et al 2019
function PROJECTPREDICT((66 U, 0, x, n, def P(x)= = UTw P(a) Ub
return PREDICT o P. P(z) n.
function PROJECTCERTIFY( U, U, 2, nu, n, a)
def P(x) = UTæ P(ū) UZ (d.p) shape(U) (U) ABSTAIN, CA, R t CERTIFY(Fe o P.o. P(x), no, n. a)
if ABSTAIN then return ABSTAIN compute orthonormal basis U1.... Ud-p for (UT)) solve the optimization
p
t +
inf aERd
r
+
0
(Alg1)
assign R +- min RR p(1 (2d)
compute the certified volume lower bound
71/2
V
+1++1) RC 2R - 21)
return prediction é^ and volume bound V
3.4 Runtime and limitations
Our certification strategy has two additional computational steps outside of the PREDICT and CERTIFY subroutines from the conventional randomized smoothing method of Cohen et al. (2019). The first is a one-time computation of the principal components of the data that occurs at the beginning of training. The second is computing the regresssio in Algl]] which we solve as a linear program using the standard epigraph formulation. For the CIFAR-10 and SVHN datasets considered this work, the addod runtime is comparable to the certification sampling step from Cohen et al. (2019). Namely, we found that the regressssnonn averaged around 16 seconds for CIFAR-10 and 19 seconds for SVHN
The number of variables and constraints in the optimization Alg scales linearly with d Since generally p & d, this makes the volume approximation of the cortified region computationally intensive in high- dimensional spaces. We remark that is still trivial to check whether any particular perturbation lies in the certified region using Proposition ! is just that computing lower bound on the volume of this region for comparison purposes becomes more challenging. For natural image dataset such ImageNet, the analysis of Section 3.3 suggests that the certified region volume improvements would in fact be substantially larger than those for CIFAR-10. The main challenge to computationally verifying this conjecture lies in holding the optimization problem (Agg] | in memory, which is infeasible on our hardware for ImageNet-scale inputs.
AAll experiments were run Ubuntu 20.04 virtual machine with VCPUs, 56 GIB RAM, and Tesla K80 GPU. Complete reproduction takes roughly 0.06 GPU years.
8

---

Published in Transactions on Machine Learning Research (09/2023)
Further research in this vein would likely leverage techniques from the large-scale -egressin literature, e.g.: Shen et al. (2014), and is outside the scope of this work.
4
Experiments
This section reports our experiments on the CIFAR-1O and SVHN datasets. We first demonstrate Section 4.1 that networks are vulnerable to bo--dde attacks in the subspace of low-variance principal components, which architecture is provably robust. Section 4.2 then presents results comparing the volume of the projected randomized smoothing certified regions to variety of baseline certified classifiers.
4.1 Vulnerability to low-variance PCA attacks
Consider perturbations ò E (UUT) contained in the span of a dataset's low-variance principal components, where we take U to contain sufficient components to account for 99% of the datasel variance for CIFAR-10 and 95% for SVHN, which is more robust to low-variance subspace attacks due to its increased compressibility. Such a perturbation is known to be esscntially orthogonal to the truc data manifold, and therefore is reasonable to expect a truly robust classifier directly robust to such perturbations under the simple condition that we use fewer components in our initial projection step, as demonstrated in Proposition 2
invariant to small perturbations MV(T). Our method is
We now investigate whether this theoretical guarantee adds degree of robustness over a typical neural network classifier. The answer is affirmative. Namely, we show that our subspace allack can attain a comparable attack success rate to a standard bounded projected gradient descent (PGD) attack, with roughly four-fold increase in the size of the admissible -bll.
Formally, consider a particular hard classifier g, to which we assume that our adversaries have white-box access, and take specific input that g classifies correctly. We first consider the standard projected gradient descent allack strategy (G e) which seeks to construct a perturbation || I such that x + 5 E Cd and g(x + +) # g(x). As z + E Odd if and only if ||x + ōlloc I 1/2, satisfying both lx- noom constraints on å is easily accomplished using clipping. Our routine SUDSPACEPGD (x, (x, adds the additional constraint 8 e (UT). Note that finding perturbation that satisfies 8 (UT), || S c, and + Cd is nontrivial, projection onto one set generally removes input from the other set. The precise details of our attack strategy are detailed in Appendix B.2
For reference, we also consider RANDMAX and RANDUNIFORM, which generate perturbations randomly on the boundary of and uniformly in the attack ball, respectively. We instantiate g as the Wide ResNet. considered in Yang et al. (2020) with the default hyperparameters and a = 0.15 Gaussian noise augmentation during training. See Appendix B.5.1 for the attack hyperparameters.
Figure 2 demonstrates that umprotected classifiers are indeed vulnerable to adversarial perturbations in the subspace of low-variance principal components. Enlargements of the attack radius do not invalidate that these are true adversarial attacks, as the perturbed images in the third row of Figure 25 are still easily classified by human. Furthermore, SUBSPACEPGD adversarial examples are substantially less perceptible than PGD attacks of the same magnitude, which tend to produce stronger visual distortions of the image, paralleling results from Shamir et al. (2021); take as representative example the area around the frog's head in the second row of the third column in Figure 2b compared with the same image perturbed by SUBSPACEPGD in the third row. The results for the SVHN dataset in Figure 2d are even more striking. This is likely because PGD allacks have access to high-variance principal components which convey the dataset information content. Despite visually appearing random, we establish in Figures [2a] and 2c that the SUbsPACEPGD attack significantly more successful than random-noise attacks of the same magnitude. These results suggest that undefended classifiers can be attacked in the subspace of low-variance principal components, to which projected randomized smoothing is provably robust. by Proposition 2
9

---

Published in Transactions on Machine Learning Research (09/2023)
CIFAR-10 attack success rate
boat
car
frog
cat
1.00
PGD
Orig
SUBSPACEPGI
0.75
PGD
RANDMAX
RANDUNIFORM
0.50
PGD
Sub.
0.25
Rad.
Max
0.00
4/255
8/255
16/255
32/22/ 255
64/255
Rnd. Uni
fo attack radius
aa)
(b)
SVHN attack success rate
1.00
PGD
Orig
9
11
1818
SUBSPACEPGD RANDMAX RANDUNIFORM
0.75
PGD
2
07
0.50
Sub.
PGD
18183
0.25
Rnd.
Max
11
18189
0.00
4/255
8/255
16/20
32/255 64/255
Rnd.
Uni.
18189
Loo attack radius (c)
(d)
Figure 2:
(a. CIFAR-10 adversarial attack success rates for the PGD, SUDSPACEPGD. and random attack
strategies. bb Perturbation examples for CIFAR-10 with attack radius of 32/255. The top row represents the original image. (cb SVHN aversarial attack success rates for the PGD, SUbsPACEPDD, and random attack strategies.
d Perturbation examples for SVHN with an attack radius of e = 32/255.
4.2 Certified region comparison
Having established that the certified region of projected randomized smoothing provides a meaningful robustness improvement against low-variance principal component attacks, we now compare the volume of our certified region with several basclincs. Namcly, we evaluate the balballs of Cohen et al. (2019) (denoted RS), the l and balls of Yang et al. 2020) (denoted RS4A - l and RS4A fxx, respectively), and the anisotropic ellipsoids of Eiras al. [2021] (denoted ANCER), without use of the associated memory module.
Some additional remarks the inclusion of Eiras et al. 22021 are warranted. As noted in Súkeník et al. (2021 without the inclusion of the memory modulc, the local certificate optimization technique in Eiras et al. 2021 yields overly optimistic and mathematically incorrect certificates as the smoothing distribution varies between inputs. The work Eiras et al. (2021) corrects this with the use memory module that records previous inputs ensure compatibility
the smoothing cortificates. However, this results a classifier that is dependent on the input order and adds ambiguity about what classifier is actually being certified, as the smoothed classifier modified at test time after each input. We therefore discard the memory module and
10

---

Published in Transactions on Machine Learning Research (09/2023)
report the certified volume at each point if the locally optimized smoothing distribution were being used globally. This yields an upper bound on the certified volume of any data-dependent aniso ellipsoidal smoothing method and is thus very strong baseline to compare against.
Our results are summarized Figure 8 and Table T We achieve state-of-the-art median certified volumes, easily outperforming standard randomized smoothing and even the optimistic ANCER baseline by 706 and 2453 orders of magnitude is attributable to the higher compressibility of the dataset. Figure G in Appendix [B.3] suggests that our performance derives from the added robustness of our method against low-variance features, as the radii of the projected-space certified balls are similar to those of standard randomized smoothing in the inpul space. This further validates the asymptotic dimension analysis in Section 3.3 Note that although the ANCER bascline achicves higher accuracy at smaller volumes, its cortificates are mathematically invalid (Súkeník
CIFAR-10 and SVHN, respectively. The larger improvement on SVHN
et al.
2021 and our method significantly outperforms ANCER larger volumes.
Figure 3b examines the 10 certified accuracy curves over range of choices for the dimensionality of the compressed space. For large p, image reconstruction is near-perfect as 620 covers 99% of variance in the CIFAR-10 dataset. Thus, methods with 2 300 have comparable accuracy at small regions, with the certified volumes increasing as the dimensionality of the projected space decreases, corroborating the discussion in Section 3.3 We are therefore able to increase the robustness of our classifier to disturbances that are normal to the manifold with only 2% drop in accuracy (Table lak. Figure 3d presents similar results for the SVHN dataset. Note that the due to the compressibility of the dataset, fewer principal components are required to achieve high accuracy.
The hyperparameter p introduces a mild tradeoff between clean accuracy and certified volume,; if p is chosen to be very small, the projected images may be too corrupted to classify, while if p is chosen be very large, certified volume may suffer. However, as Figures 3b and 3d suggest, our method's certified volunes comfortably outperform those of standard randomized smoothing for large range of p, indicating that this choice is not particularly sensitive. A practical heuristic for choosing p involves making just large enough to reconstruct images with high fidelity roughly corresponding to PCA components that explain 95% to 99% of the dataset variance. If desired, a small, localized sweep of p around this initial choice can be used to further optimize the hyperparameter depending on the experimentalist's 's target metrics (e.g., clean accuracy, median certified volume, other metrics, or some combination). In any case, we emphasize that the parameter choice is quite robust and any additional tuning is likely result in minimal gains compared to the practical heuristic. We select p 450 for the CIFAR-10 experiment in Figure 3a and p 150 for SVHN.
Table 1: Quantitative representation of the data in Figure 3 The first column reports the smoothed classifier clean accuracy for each method and the second column reports the median certified volume for correctly classified samples. We use the median instead of the mean due to the log-scaled nature of our data.
(a) CIFAR certification performance.
(b) SVHN certification performance.
Median cert. vol. (logıo)
Median cert. vol. (log
Accuracy
Accuracy
PROJECTEDRS
85.8%
3175
PROJECTEDRS
91.4%
-1588
RS
87.8%
-4377
RS
92.6%
-4280
ANCER
87.4%
-3881
ANCER
91.2%
-4031
RS4A- L
83.8%
-9573
RS4A- E1
93.0%
-9573
RS4A Loo
85.4%
-6102
RS4A loo
92.6%
-6171
5
Conclusion
Motivated by the manifold hypothesis, we consider a classifier architecture that first projects onto a principal component approximation of the data manifold and then applies randomized smoothing in the low-dimensional projected space. This yields a precise characterization of the input-space certified region capturing
11

---

Published in Transactions on Machine Learning Research (09/2023)
CIFAR-10 certified accuracy
CIFAR-10 certified accuracy
0.8
0.8
PROJECTEDRS"
0.6
0.6
P 100
PROJECTEDRS'
p = 200
0.4
0.4
RS
P = 300
ANCER
p 450
0.2
0.2
RS4A
4
P 600
RS4A
Lo0
p = 1000
0.0
0.0
10
10
10 3a 10 2xx
10 1a
10 3a
10 10-2a Volume
10 1a
Volume
(a)
(b)
SVHN cerlified accuracy
SVHN certified accuracy
0.8
0.8
PROJECTEDRS'
0.6
0.6
p p= 60
PROJECTEDRS'
p 100
0.4
0.4
RS
p 150
ANCER
p 200
0.2
0.2
RS4A- &
300
RS4A - loo
450
0.0
0.0
10 40
10 30
10 10-1a
10 20
10 10-1o
Volume
Volume
(c)
(d)
Figure [a] Certified region volumes for CIFAR-10, with our method highlighted by an asterisk. Here a 3465 is scaling constant corresponding the d-dimensional unit ball volume; i.c. Va(Ba(1)) 10-a bb CIFAR-10 certified region volumes while varying the projected space dimension p for our method. (c) Certified region volumes for SVHN. (dl SVHN certified region volumes while varying p.
disturbances in the projection nullspace. We interpret this certifiable robustification against vulnerable features that are irrelevant to the dataset information content as they are normal to the data manifold. We show that unprotected classifiers, unlike our method, are vulnerable to such perturbations by explicitly constructing adversarial examples in the span of the low-variance principal components. We prove a volumetric lower bound on the intersection of our certified region with the unit cube of feasible inputs and derive two additional ways to tighten the bound: one which involves solving an regresssnno problem and another which is closcd-form radius adjustment.
Comparing against state-of-the-art f1-, l2z, foo-, and anisotropic baselines shows that our classifier produces certified regions with many orders of magnitude greater volume. This confirms an asymptotic analysis that shows that our method's certified volumnes decay factorially the low dimension of the projected space, while competing methods decay factorially in the high dimension of the input space. Future research directions include examining more sophisticated dimensionality reduction techniques while maintaining certified guarantees for projected points in the original input space.
12

---

Published in Transactions on Machine Learning Research (09/2023)
References
Sheila Alemany and Niki Pissinou. The dilemma between data transformations and adversarial robustness for time series application systems. In Proceedings of the AAAT Conference on Artificial Intelligence, 2022.
Motasem Alfarra, Adel Bibi, Philip H.S. Torr, and Bernard Ghanem. Data dependent randomized smoothing. arXiv preprint ar 2r1xi:201220435.. 2020.
Brendon G. Anderson and Somayeh Sojoudi. Certified robustness via locally biased randomized smoothing. Learning for Dynamics and Control. PMLR, 2022.
Brendon G. Anderson, Ziye Ma, Jingqi Li, and Somayeh Sojoudi. Tightened convex relaxations for neural network robustness certification. In Proceedings of the 59th IEEE Conference on Decision and Control, 2020.
Brendon G Anderson, Samuel Pfrommer, and Somayeh Sojoudi. Towards optimal randomized smoothing: A semi-infinite lincar programming approach. In ICML Workshop Formal Verification of Machine Learning (WFVML), 2022.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning, pp- 274 283. PMLR, 2018.
Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, and Aravindan Vijayaraghavan Adversarially robust low dimensional representations. In Conference on Learning Theory, pp. 237-325. PMLR, 2021.
Mitali Bafna, Jack Murtagh, and Nikhil Vyas. Thwarting adversarial examples: An Lo-robust sparse fourier transform. In Advances in Newral Information Processing Systems, volume 31, 2018.
Dimitri P. Bertsckas. Nonlinear Programming. Athena Scientific, third edition, 2016.
Arjun Nitin Bhagoji, Daniel Cullina, Chawin Sitawarin, and Prateck Mittal. Enhancing robustness of machine learning systems via data transformations. In 2018 52nd Arscual Conference on Informalion Sciences and Systems (CTSS), pp- 1-5. TEEE, 2018.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šrndić, 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, pp. 387-402. Springer, 2013.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint 16v: 07316, 2016.
Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pp. 3-14, 2017.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Cortified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310 1320. PMLR, 2019.
Francisco Eiras, Motasem Alfarra, M Pawan Kumar, Philip HS Torr, Puneet K Dokania, Bernard Ghanem, and Adel Bibi. Ancer: Anisotropic certification via sample-wise volume maximization. ar preprinl brXiv:2107.045700 2021.
Ecenaz Erdemir, Jeffrey Bickford, Luca Melis, and Sergul Aydore. Adversarial robustness with non-uniform perturbations. Advances in Neural Information Processing Systems, 34, 2021.
Kevin Eykholt, Ivan Evtimov, Earlence Fernandes, Bo Li, Amir Rahmati, Chaowei Xiao, Atul Prakash, Tadayoshi Kohno, and Dawn Song. Robust physical-wort world attacks on deep learning visual classification. Proceedings of the IEFE conference on computer vision and paltern recognition, pp. 1625-1634 2018.
13

---

Published in Transactions on Machine Learning Research (09/2023)
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathemalical Sociely, 29(4):983-1049) 2016.
Gerald B Folland. Real analysis: Modern techniques and their applications. John Wiley & Sons, second edition, 1999.
Douglas Hensley. Slicing the cube in r" and probability (bounds for the measure of central cube slice in r" by probability methods). Proceedings of the American Mathematical Sociely, 73(1):95 100, 1979. ISSN 00029939, 10886826.
Jongheon Jeong, Sejun Park, Minkyu Kim, Heung-Chang Lee, Do-Guk Kim, and Jinwoo Shin. Smooth- mix: Training confidence-calibrateed smoothed classifiers for certified robustness. In Advances in Neural Information Processing Systems, volume 34, pp. 30153 30168, 2021.
Susmit Jha, Uycong Jang, Somesh Jha, and Brian Jalaian. Detecting adversarial examples using data manifolds. In MILCOM 2018-200 2018 IEEE Military Communications Conference (MILCOM), pp. 547-552.
TEFE, 2018.
Hoki Kim. Torchattacks: A pytorch repository for adversarial attacks. arXiv preprint arXiv:2010.01950, 2020.
Weicong Kong, Zhao Yang Dong, Youwei Jia, David J Hill, Yan Xu, and Yuan Zhang. Short-term residential load forecasting based on Istan recurrent neural network. IEEE Transactions on Smart Grid, 10(1):841 851, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning, pp. 5458 5467.
PMLR, 2020.
Alexcy Kurakin, Ian Goodfellow, and Sany Bengio. Adversarial machine learning at scale. In International
Conference on Learning Representations, 2017.
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy, pp. 656-672. IEEE, 2019.
Guang-He He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. Advonces in Neural Information Processing Systems, 32, 2019.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against Wasserstein adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 3938 3944. PMLR, 2020.
Alexander Levine and Soheil Feizi. Improved, deterministic smoothing for & certified robustness. In International Conference on Machine Learning, pp. 6254-6264. PMLR, 2021.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems, volume 32, 2019.
Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double sampling randomized smoothing. arXiv preprint arXiv:2206.0799 2022.
Aishan Liu, Xianglong Liu, Jiaxin Fan, Yuging Ma, Anlan Zhang, Huiyuan Xie, and Dacheng Tao. Perceptual- sensitive gan for generating adversarial patches. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1038-1035, 2019a.
Chen Liu, Ryota Tomioka, and Volkan Cevher. On certifying non-uniform bounds against adversarial attacks. Tn International Conference on Machine Learning, pp. 4072-4081 PMLR, 2019b.
14

---

Published in Transactions on Machine Learning Research (09/2023)
Ziye Ma and Somayeh Sojondi. A sequential framework towards exact SDP verification of neural networks. In 2021 IEFE 8th International Conference on Data Science and Advanced Analylics (DSAA); pp- 1-8. LEEE, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Thibault Maho, Toddy Furon, and Erwan Le Merrer. Randomized smoothing under attack: How good is it in practice? In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2014-3018 IEFE, 2022.
Aamir Mustafa, Salman H Khan, Munawar Hayat, Jianbing Shen, and Ling Shao. Image super-resolution as a defense against adversarial attacks. TEFF Transactions on Image Processing,
2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning, 2011.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEFF Conference on Computer Vision and Pottern Recognition, pp. 427 436, 2015.
Aditi Raghumathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, pp. 10877-10887, 2018.
Rajeev Sahay, Rehana Mahfuz, and Aly El Gamal. Combatting adversarial attacks through denoising and dimensionality reduction: A cascaded autocncoder approach. In 2019 53rd Annual conference on information sciences and systems (CISS), pp. 1-6. IEEE, 2019.
Hadi Salman, Jerry Li, 1lya 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, volume 32, 2019.
Amartya Sanyal, Varun Kanade, Philip HS Torr, and Puneet K Dokania. Robustness via deep low-rank representations. arXiv preprint 1rxi 0004000040, 2018
Adi Shamir, Odelia Melamed, and Oriel BenShmuel. The dimpled manifold model of adversarial examples in machine learning. arXiv preprint ar Xrxi:22006. 10151, 2021.
Fumin Shen, Chunhua Shen, Rhys Hill, Anton van den Hengel, and Zhenmin Tang. Fast approximate to minimization: Speeding up robust regression. Computational Statistics & Data Analysis, 77:25-37, 2014.
Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input-dependent randomized smoothing, arXiv preprint arXic:2110.05300 2021.
Christian Szegedy, Wojciech Zaremba, Llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
Lucas Matthew Tecot. Robustness verification with non-uniform randomized smoothing. Master's thesis, University of California, Los Angeles, 2021.
Jiaye Teng, Guang- He Lee, and Yang Yuan. & adversarial robustness certificates: A randomized smoothing approach. Preprint, 2020.
Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems, volume 33, pp. 1633 1645, 2020.
Jonathan Uesato, Brendan O'donoghue, Pushmoct Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference on Machine Learning, pp. 5025-5034 PMIRR 2018.
15

---

Published in Transactions on Machine Learning Research (09/2023)
Jeffrey Vaaler. A geometric inequality with applications to linear forms. Pacific Journal of Mathematics, 83 (2):543-506 553, 1979.
Lei Wang, Runtian Zhai, Di He, Liwei Wang, and Li Jian. Pretrain cetrainntoo-ineeen f--finetuee adversarial training via sample-wise randomized smoothing. Preprint, 2021.
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, pp. 5276-5285. PMLR, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286 5295. PMLR, 2018.
Bichen Wu, Forrest landola, Peter H. Jin, and Kurt Keutzer. SqueezeDet: Unified, small, low power fully convolutional neural networks for real-time object detection for autonomous driving. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 129 137, 2017.
Greg Yang, Tony Duan, Edward Hu, Hadi Salman, llya. Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pp. 10693-10705. PMLR, 2020.
Huimin Zeng, Jiahao Su, and Furong Huang. Certified defense via latent space randomized smoothing with orthogonal encoders. ar preprinl arxiv:2108. 010492108.00491 2021.
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.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black- box certification with randomized smoothing: A functional optimization based framework. In Advances in Neural Information Processing Systems, volume 33, pp. 2316 2326, 2020a.
Yonggang Zhang, Xinmei Tian, Ya Li, Xinchao Wang, and Dacheng Tao. Principal component adversarial example. IEEE Transactions Image Processing, 29:4804-4815, 2020b.
16

---

Published in Transactions on Machine Learning Research (09/2023)
A Supplementary material for Section 3 (Robustness certificates)
Proposition Let x E Rd and R 2 0. If fa is certified at P(x) = U with radius R, then g(x + 5) = g(x)
for all E (R) C R., where
A (RR = e RR. | = R}
Proof. Let E (R). Then
g(a + 8) = arg max (P(r + 6)), arg max (a(())) U yEy
yEY
Since ||UTØ|| & R by definition of A ( and fä is certified at P(x) with radius R, we have that
g(x 8)
arg max (P()))) g(x).
Ney
Proposition 2 Let R 2 The certified region (R) con be expressed as the Minkowski sum ( d B (R) + NUUT) where By (R) Rd is a p-dimensional ball embedded into R(U):
(R) = {3108-p+1 + + Byva: |1||| S R, E }
Proof. Let y1 + y22 with E B (R) and E (UT).. Then
| vl = 10T y || = |3|| R
y (R).
On the other hand, let y E (R) as defined in Proposition 1 We can decompose y1 + for y1 E R(U)
and 3/2 E &N(UT). Then there exists 8 R2 such that y1 = UB Ei 3 so y = ||||| and therefore || < R.
Corollary 1 Let Sş be a k-dimensional linear subspace of Rd and rCdd be zero-centered cube of side length r>0 0. Then Vi(rOd n Sk) 2 rh.
Proof. Note that
rCdh n fo E Ed || Sr/2, St}
= frx E Rd ||r0|| S $r/2, ræ E Ss)
[rx E Rd || I 1/2,, E Sx).
since Sş if and only if rz: E Sk, by linearity of Sg. This is now equivalent to the set r(C nkk,, and we have scaled our k-dimensional subset by a uniform factor Therefore, Va(rC" S&) 5a)= V Va(r(C" (S))) VVV n Sk) by Folland (1999] Theorem 2.44). Thus, by Theorem ]
we have (r(rCd n Sp) 2 r..
Corollary 2 Let E Rdd and let. Sa(w) C & be the k-dimensiooal affine subspace
Sx(x)
Σ a, R
spanned by arbitrary vectors vi...., Us and passing through æ. Let t. 2 O be the minimal -nom of a point in Sa (x):
inf
||
inf aERt
+
awy
(5)
x' Se)
Then, for all 2t, holds that (a(rOd ( 2 (r 25)*
17

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. First, notice that the infirum in (5) is attained since || I1 is continuous and coercive, and Sx(a) is closed in the standard topology on IRd (Bertsekas) 2016). Let x" E (x(x) be point that attains the infimumm in 5 so that | = t. If r > 2t, then x² is contained in the interior of rC In this case, we can construct a nonempty cube centered at x" with side lengths r - 2t > that is contained in rC4. Now, the plane Sx(x) passes through x², and therefore Corollary [ yields the result since volume preserved under translation Folland 1999, Theorem 2.42).
Theorem Let x E Cd,, let t be defined as in at P(x) = UTx with radius R, then
(5) with &o = d - p, and let R E [0, t]. If fă is certified
T/2
Va(C" (A) Z
T(S +1) R 2R 21)
(6)
Proof. The characterixation of (R) in Proposition
yields
4 (R) B [R) S ddp (x))
where
Sa-9 S (x) (x) (x} + +((TT)
is the affine subspace of I& spanned by (N(UT) and passing through x, which has dimension d p. Therefore, the following is an inner-approximation of A (R):
(R) : B + (11 (1- S
( (x) _ B (R) + S (NUT (x)= (R).
If we can show that 3 (R) _ Od, then (R) S Od n A (R), in which case the volume of A (R) will bower-bound the volume of Cdd n (R). To prove that this holds, let y = yı + U2 A (R) with yr B (R)
and V/2 E - -2R)C n S
((UT) (x). Then
1 2R
μl S 11n Io + 1112/100 S R+
2
2'
by the fact that l/ boo S - || ||3|| for some R2 with || R due to the semi-orthogonality of U, and by the fact that 1/2 E (1- - 2R)CH. Therefore, indeed it holds that (R) C Cd. Thus, all that remains
is to lower-bound V 4 x (R)). To this end, notice that By (R) S R(U) and (1 - 2R)C4 n S (xT))))))) C (x) are contained in orthogonal affine subspaces, and therefore V Va(A (R)) = (B RR)) ( 2R)C4 n d-p (( (z)). The p-dimensional volume of the embedded ball
(WUT), so B (R) and (1 (((
ball By (R) is well-known (e.g., see Folland 1199.
Theorem 2.44, Corollary 2.55)) to be
TP/2
V V, (R))
RP.
I(5 + +1)
On the other hand, since 2R < 1 21, it holds that 1 - 2R > 2t. Hence Corollary 2 gives that the SN((UT)
(d - p)ddimensional volume of (1 CR) n Sd-p ((x:) is lower-bounded as
V Va-p((1 2*) n ns
((UUT) (x)) 2 (1 2R 2-
Therefore,
TP/2
V va(A" >
R1 2R -00
T(U 1)
which concludes the proof.
Proposition 3 Let and R be as in Theorem
The lower bound 6 is marimized as follows:
:= min { R. p(1 2t)
TP/2
arg max
r [ + +1) (1 2r 21)a-p.
(7)
2d
rE(o.R]
18

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. It suffices to maximize h(r) == r² (1 2r 2 over r E [0, R). The gradient of h vanishes at points satisfying
dh
dr (r) = =pr (1 2r 21) P- - 2(d - p)r (1 2r -21))---1
a-11 pp- (1 2r 21) 21) (p(1 2r 2t) 2(d p)r)
-pp11 (1 2r 21)
p-) p-1 (p 2pt 2dr)
O.
The sot of all critical points satisfying this polynomial equation for p(1-2))
1/2 -t.. Notice that <
2d
p(1-2t)
p(1-2t)
1/2 - t, and that dh de (r) 2 for all r E [0, p(1-20)
whereas de (r) S for all r E
2d
2p 1 Hence, h is unimodal on [o, 1/2 1] with the maximizer p(1-20) Therefore, if R < p
2d
p(1-21
21)
1/2-
2d
2d
2d
then h is monotone increasing on the feasible interval [0, RJ, which implies that the right endpoint r R is p(1-2t)
maximizer of 7 On the other hand, if R 2 2d then p(1-20 is contained in the feasible interval 00, R). and thus r* 201-20) is a maximizer of 2d
2d
As an aside, we note that the certified region of our method contains an fg-ball of radius usually comparable to that of standard randomized smoothing, although in general the certified region of Propositions 1 and 2
will be much larger as it captures the null space of the projection operator. We nevertheless include the following simple result for completeness.
Proposition 4. Let Rd and 2 0. If Jø is certified P(x) UT with radius R, then g(x + +5) g(x) for all E BR( for Rd || < R).
Proof. Let 8 E Ba(R). Then, since UT is a semi-orthogonal matrix, its lg-induced operator norm ||UT]] is less than or equal to 1. Thus, ||[Tō||| < ||||]|||||| < R. Therefore, Ba(lt) C (R)..
A.1 Finite-dimensional volume analysis
We complement. our asymptotic certified volume comparison in Section 3.3 with a simple finite-dimensional sweep over input dimension d and projected dimension p, the results of which shown in Figure 4
Here, we fix R = 0.5 and t = 0.4 as typical values for natural image datascts and sweep over range of choices of and d. We assume that the low-dimensional and high-dinensional certified radii are similar, as indicated by Figure [6] The plotted values provide the ratio our certified volume from Theorem 2 to the volume of a standard balball, as given Scction 3.3 o.g., a value of x30000 indicates that the volume of our certified region is 30000 times greater. This ratio grows rapidly as d increases due to the factorial growth
noted in Section 33
19

---

Published in Transactions on Machine Learning Research (09/202))
x30000
10000
9000
X 25000
8000
Inpur dimension d
X00000
7000
Cortified volume
6000
x 150000
5000
x10000
4000
3000
x5000
2000
100
200
300
400
500
600
700
800
900
1000
Projected dimension p
Figure 4: Ratio of projected randomized smoothing certified volume versus standard randomized smoothing certified volume for simulated values.
B Supplementary material for Section 4 (Experiments)
B.1 Random projections ablation
We compare the PCA projections used in our experiments with projection onto random subspace for CIFAR-10. As reconstruction fidelity is much poorer for random subspaces, we expect to need many more components to achieve a comparable clean accuracy to PCA projections. We correspondingly adjust the number of components to p = 1500 in Figure 5 for random projections, and retain p = 450 PCA components. As with the hyperparameter sweeps, we use n 10 smoothing samples. Figure 5 shows that projecting onto the PCA basis generally provides superior certificates. We also plot standard randomized smoothing for reference.
0.8
Certified accuracy
0.6
0.4
PROJECTEDRS PROJECTEDRRRRANDMM
0.2
RS
0.0
10-3o 30
10 10-20 20
10-1a
Volume
Figure 5: Ablation test comparing PCA basis projections with projection onto random orthonormal set of vectors.
20

---

Published in Transactions on Machine Learning Research (09/2023)
B.2 Subspace attack procedure
A typical PGD attack constructs adversarial examples by iteratively perturbing the image along the gradient of the loss and projecting onto the unit cube of feasible inputs:
x (f+1) = Poa (x Po* sign (voL(x!)) + +.4) - x 2111))
where x00) is the ith iterate of the PGD attack, L is the loss function, sign(-) is the clement-wise sign operator, is the step size hyperparameter, Pos projects point in Rd onto Od by simple clipping, and Pot is defined similarly for the zero-centered cube of sidelength 2e, We initialize (1)) æ, where (æ, y) are the original input and label from the dataset.
We desire final perturbation 8 such that x + 8 E Cd,, d Cd and ò ENUT). We first parameterize our perturbation in terms of the vectors Ui...., Vd-p spanning N(UT). Stacking these vectors columnwise to yield V E Rdxd-p, we can express our pertubation as ő = Vov with 5y E Rd-P, We then iterate over our parameterized perturbations 812, first solving for our "target" perturbation
((++))== = o44) + arignn (Vol(r - V(OV + +8).
We then project the perturbation satisly the lo connttraiis,, which takes the form of a quadratic program:
v (o + Vōv
minimize EVERd-P subject to
VVov S
|| + Vôv S 1/2.
This program is always feasible with &v = 0, and its solution satisfies our requirements for each iteration of the attack procedure.
B.3 CIFAR-10 additional results
Here we present an additional plot comparing the radii of the low-dimensionall projected randomized smoothing balls to the radii of standard randomized smoothing balls in the high-dimensional space. Those very similar, suggesting that the increase in the volume of the certified region comes from the "extrustion" of the ball, which amounts to added robustness against unnecessary features that are removed in the initial projection step. For the anisotropic ANCER method, we report the geometric mean of the radii along each coordinate axis, which Eiras et al. (2021) defines to be the "proxy radius." " We only compare methods with basede certified regions in this plot.
0.8
Certified accuracy
0.6
0.4
PROJECTEDRS*
0.2
RS
ANCER
0.0
0.00
0.25
0.50
0.75
1.00
1.25
Radius
Figure 6: Certified radii the CIFAR-10 10 dataset.
21

---

Published in Transactions on Machine Learning Research (09/2023)
B.4 Empirical manifold- peraeniccae robustness
While the focus of our work is certified robustness, for expository purposes we briefty compare the empirical performance of our model against that of standard randomized smoothing on an approximately manifold- perpendicular threat model. Specifically, following projected gradient descent iteration, we clamp the high-variance components of the perturbation to have norm at most R, where R is a parameter that we sweep over in the table below. An R of zero corresponds to maamfold-perpedicuul perturbations are allowed larger on-manifold component. We also range over the perturbation magnitude The reported numbers are CIFAR-10 empirical accuracies in percentages, with our method highlighted in bold.
attack, and as R increases
Table 2: CIFAR-10 empirical robust accuracy percentages subject to approximately manifold-pene peeefoood-peppenieulattt threat model, with randomized smoothing in non-bold font and our method in bold.
R
0.0
0.25
0.5
1.0
6
8/255
76 - 79
65 - 69
54 - 58
34 35
16 16/255
71 - 79
60 69
50 - 58
28 35
32/255
59 - 79
50 - 69
39 - 58
20 35
We evaluate over 500 test images and exccute smoothing for 100 samples at each input; while this is fewer than what is typically used for certification, it is standard number of samples for the prediction problem (Cohen et al. 2019
As seen in Table 2 our method consistently attains higher empirical robust accuracy than conventional randomized smoothing across all e-R pairs tested. The advantages of our projection-based method are most apparent for small R, where the underlying geometry of the data distribution which conventional randomized smoothing is naive to-is most inftuential, as well as for large where an attacker is able to create large off-manifold perturbations of the input data. As our theory suggests, we find that the empirical robust accuracy of our model remains constant over increasing for a fixed value R, indicating that our model not sensitive to increases in the off-manifold components an allack. On the contrary, we see that, for fixed R, e increases, the empirical robust accuracy of conventional randomized smoothing decreases, mcaning that conventional randomized smoothing is empirically sensitive to moving further away from the natural data manifold, an attack strategy that we have now shown our method to be both theoretically and empirically robust to.
B.5 Hyperparameter selection
To maintain consistency, all networks we consider are Wide ResNets pretrained with various noise distributions using the code provided by Yang al. (020). For networks composed with an initial projection, we finetune the network with a learning rate or 0.001, momentum of 0.9, and weight decay of 0.0005 for 20 epochs, decaying the learning rate by multiplicative factor of 0.95 per epoch.
B.5.1 Attack hyperparameters
We kept the attack hyperparameters fixed across both CIFAR-10 and SVHN. For the PGD attack, we use the torchattacks library with 40 steps and step size a = 2/255 Kim (2020). We lowered this to 5 steps with a = e/4 for SUbsPACEPGD due to the solve time of the projection step.
B.5.2 CIFAR-10 certification hyperparameters
We include the results of our hyperparameter swoeps for CIFAR-10 in Figure 7 For the RS4A é, method, we used uniform noise and stability training to reproduce the ttate-of-theart result from Yang et al. (2020). The RS4A foo sweep used Guassian noise, which we found to perform better in practice. Our sweep over
22

---

Published in Transactions on Machine Learning Research (09/2023)
the ANCER learning rate held the number of steps and regularization weight fixed at their defaults of 900 and 2, respectively. All sweeps were performed over 500 random test samples besides ANCER which was run over 100 samples due to the method's high computational burden.
The results from these sweeps informed the choice of hyperparameters Figure 3a Namely, we choose 0.25 for our RS4A - i baseline and o 0.15 for our RS4A &oo baseline, the clean accuracy drops substantially for higher variances without approaching comparable certified volume to the other methods considered. We choose learning rate of 0.01 for ANCER and p = 450 components for projected randomized smoothing. All experiments in the hyperparameter sweeps were performed with the smoothing hyperparameters ni = 100 samples to guess the smoothed class, n 10 samples to lower-bound the smoothed class probability, and a confidence of a = 0.001. For reproducing the final results Figure 3a we increasod n to 10 as standard (Cohen al. 2019) and used 500 test samples generate the plots. The allack experiment illustrated in Figure 2a conducted over 100 test samples.
0.8
0.8
Certified accuracy
Cortified accuracy
0.6
0.6
0.4
RS4A - 1
0.4
0.25
RS4A
600
a 0.50
σ = 0.15
0.2
0.2
0.75
0.25
a 1.00
o 0.50
0.0
0.0
10 -a
10 3a
10 4cx
10
10 2a
Volume
Volume
CTFAR-10 certified accuracy
0.8
0.8
Certified accuracy
PROJECTEDRS*
0.6
0.6
100
ANCER
p 200
0.4
0.4
Ir = 0.03
300
0.01
P 450
0.2
0.2
Ir 0.003
600
0.001
p 1000
0.0
0.0
10
1.6 11100-1440 1.4010
1:2010
10010-1.00 1.00
10 30
10 Volume
10-1a
Volume
Figure 7: Hyperparameter sweeps for the CIFAR-10 dataset. Here a = 3465 is a scaling constant corresponding the d-dimensional unit ball volume; i.c. Va(Ba(1)) 10-a
B.5.3 SVHN certification hyperparameters
The SVHN hyperparameter sweep, shown in Figure g is similar that for CIFAR-10, besides the use of fewer principal components in the projected randomized smoothing sweeps due to the higher compressibility
23

---

Published in Transactions on Machine Learning Research (09/2023)
of the data. Our final plots in Figure 3c 0.25 for the f1-baseline, 0.15 for the baselinn, ANCER learning rate of 0.01, and p = 150 for projected randomized smoothing.
0.8
0.8
Cerlified accuracy
Certified accuracy
0.6
0.6
RS4A - 1
0.4
0.4
a 0.25
RS4A
to0
0.50
0.15
0.2
0.2
0.75
0 0.25
1.00
0.50
0.0
0.0
10
10 30
10 13a 30
10 10-2n
Volume
Volume
0.8
SVHN cortifiod accuracy
0.8
Certified accuracy
PROJECTEDRS*
0.6
0.6
p 60
ANCER
100
0.4
0.4
Ir 0.03
p 150
Ir 0.01
200
0.2
0.2
ir 0.003
p 300
Ir 0.001
450
10
10-1a
10
10-1a
Volume
Volume
Figure 8: Hyperparameter sweeps for the SVHN dataset. Here Rz 3465 is scaling constant corresponding to the d-dimensional unit ball volume; i.e. V Va(Ba(1)) = 1
B.6
Licenses
The CIFAR-10 dataset covered by the MIT license, and the SVHN dataset is covered by the GPL 3 license.
24


Reviews:
[{"review_id": "mAmNrBKavc", "reviewer": "Reviewer_65nC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is the first to prove lower bound on the volume for the certified region when applying randomized smoothing on reduced dimensionality.\n2. The experiments demonstrates experimentally that adversarial vulnerabilities exist along subspaces which are not important for classification.\n3. Experimentally, the paper confirms that the volume certified by this technique is larger than those of existing techniques.\n\nWeaknesses:\n1. Volume might not be the best metric for certified adversarial robustness. For example, the standard 'minimum norm attack' metric (under various norms) is more suitable. Volume can be large, and yet there could be a small norm successful attack possible.\n\n2. The experiments in Section 4.1 consider $l_{\\infty}$ attacks, but the theory is proved for $l_2$ attacks.\n\n3. The theoretical results are somewhat intuitive and the proofs seem relatively straight-forward.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the technique of certified adversarial robustness where the input data is first projected down to a smaller dimension and then randomized smoothing is applied on the dimension-reduced input. For this technique, the paper proposes new lower bounds on the volume of the certified region. Experimentally, the paper shows that the directions along which the dimensions were reduced could have led to adversarial vulnerabilities, and that the volume of the certified region using this technique is larger than what is given by existing techniques.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Apart from the weaknesses in the section above, I have the following suggestion: The authors can include a discussion on if/how the results could be extended to norms other than the $l_2$ norm.\n\n", "broader_impact_concerns": "No concerns of ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dJk4Q6Ibbu", "reviewer": "Reviewer_xS7n", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper presents a novel projected RS approach\n2. The theoretical analysis shows that this approach in theory results in improved lower bound on the certified volume\n3. The paper is well-written and easy to follow\n\n**Weaknesses:**\n1. There is no ablation study to show that projecting on the Principal Component (PCA) works better than even projecting on random dimensions in terms volume of the certified region. \n\n2. This work does not show the effectiveness of the proposed technique on ImageNet. The explanation of why it is hard to validate its usefulness for ImageNet is quite short. It just says \"would likely need to leverage techniques from the large-scale l_\\inf-regression literature\". This explanation is quite unclear. \n\n**Questions:**\n1. Does the theoretical lower bound on the volume hold irrespective of the use of principal components? If yes, then can you explicitly state it in the text\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a randomized smoothing (RS) technique that improves the volume of the certified region, by using dimension-reducing projection. The paper computes a theoretical lower bound on the volume of the certified region. The evaluation shows that on CIFAR10 and SVHN, the technique yields larger volumes than prior SOTA methods. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide an ablation study showing the effectiveness of ProjectedRS using PCA dimensions over any randomly picked dimensions.  \n\n2. Add more explanation on why validating the effectiveness of the technique on ImageNet is hard and not done in this work", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ouK5e2OqQw", "reviewer": "Reviewer_UAzk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The idea of projecting to low-dimensional subspace is novel, reasonable, and theoretically sound, in terms of improving the volume of the certified region.\n2. A computable lower bound of volume is proposed, which extends the existing theoretical results to bring practical value.\n3. Experiments on CIFAR-10 and SVHN well justified the proposed method and also show such projection brings more robustness under existing attacks.\n\nWeaknesses:\n1. I don't think improving the volume of the certified region is a very important goal to pursue. Considering that the attacker aims to find an imperceptible adversarial example, we should not limit its ability. Hence, it should not be counted robust if the model is robust towards some perturbation directions but vulnerable to other perturbation directions, but this is indeed the goal implied by projection for maximizing certified volume.\n2. Large-scale experiments on ImageNet are preferred. One unique benefit of RS is its support of large-scale datasets like ImageNet. Also, ImageNet is a challenging dataset with large intrinsic data dimensionality. Hence, to evaluate the practicality of the proposed method, ImageNet experiments would be very useful. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to first project the input into a low-dimensional linear subspace, then add noises in such linear subspace with randomized smoothing, and finally project back to feed into the classifier. In this way, perturbations in the null space of the projector will not change model prediction, so we can achieve a drastic improvement of certifiably robust volume. A certified volume lower bound is derived, and compared to other RS regime to show superior certified volume on CIFAR-10 and SVHN.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Large-scale experiments on ImageNet would be great.\n2. Could you clarify \"dominating any exponentially-scaled concessions in the numerator of (6).\" a bit more on Page 7, Section 3.3?\n3. Some relevant work on improving randomized smoothing certificates is not discussed, e.g., [1][2].\n\n[1] Levine, A., and Feizi, S. Improved, deterministic smoothing for L_1 certified robustness. International Conference on Machine Learning. PMLR, 2021.\n[2] Li, L., Zhang, J., Xie, T. and Li, B. Double Sampling Randomized Smoothing. International Conference on Machine Learning. PMLR, 2022.", "broader_impact_concerns": "No additional broader impact concerns are raised.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper suggests an alternative robustness metric, where adversarial perturbations are constrained to lie on a data manifold chosen as a subspace coming out of a principal components analysis. The authors show that performing randomized smoothing in this restricted subspace leads to stronger guarantees (wrt to the restricted threat model). The reviewers raised questions on the notion of robustness considered and the value of the PCA (vs random projections) that were adequately addressed during the discussion phase. Hence I recommend acceptance.
Decision: Accept (poster)