Certified Robustness against Sparse Adversarial Perturbations via Data Localization
Authors: Ambar Pal
Rene Vidal
Jeremias Sulam
Venue: Accepted by TMLR ()

Abstract: Recent work in adversarial robustness suggests that natural data distributions are localized, i.e., they place high probability in small volume regions of the input space, and that this property can be utilized for designing classifiers with improved robustness guarantees for $\ell_2$-bounded perturbations. Yet, it is still unclear if this observation holds true for more general metrics. In this work, we extend this theory to $\ell_0$-bounded adversarial perturbations, where the attacker can modify a few pixels of the image but is unrestricted in the magnitude of perturbation, and we show necessary and sufficient conditions for the existence of $\ell_0$-robust classifiers. Theoretical certification approaches in this regime essentially employ voting over a large ensemble of classifiers. Such procedures are combinatorial and expensive or require complicated certification techniques. In contrast, a simple classifier emerges from our theory, dubbed Box-NN, which naturally incorporates the geometry of the problem and improves upon the current state-of-the-art in certified robustness against sparse attacks for the MNIST and Fashion-MNIST datasets.

Published in Transactions on Machine Learning Research (10/2024)
Certified Robustness against Sparse Adversarial Perturba- tions via Data Localization
Ambar Pal
AMBARQ.JU.EI
Deportment of Computer Science & Mathematical Institute for Data Science Johns Hopkins University Baltimore, MD 21218, USA
René Vidal
VIDALROUPENS. EDU
Department of Electricol and Systems Engineering Center for Innovaaion in Dala Engineering end Science University of Pennsyleaana Philadelphia, PA 19104, USA
Jeremias Sulam
JSULAM] @JU..EDU
Deportment of Biomedical Engineering & Mathematical Instibute for Data Science Johns Hopkins Universily Ballimore, MD 21218, USA
Reviewed on OpenReview: https: openreview. net/ forun? id= 17Ld3da
Abstract
Recent work in adversarial robustness suggests that natural data distributions are localized, i.e,, they place high probability in small volume regions of the input space, and that this properly can be utilized for designing classifiers with improved robustness guaranlees for bz-bounedd perturbations. Yet, it is still unclear if this observation holds true for more general metrics. In this work, we extend this theory to fo-bounded adversarial perturbations, where the attacker can modify a few pixels of the image but is unrestricted in the magnitude of perturbation, and we show necessary and sufficient conditions for the existence of fg-robust classifiers. Theoretical certification approaches in this regime essentially employ voting over large ensemble of classifiers. Such procedures complicated certification techniques. In contrast, a simple classifier emerges from our theory, dubbed Box-NN, which naturally incorporates the geometry of the problem and improves upon the current state-of-the-art in certified robustness against sparse attacks for the MNIST and MaSHion-MNIST datasets.
combinatorial and expensive or require
Introduction
It by now well known that adversarial attacks affect Machine Learning (MI.) systems that can potentially be used for security sensitive applications. However, despite significant efforts on robustifying ML models against adversarial attacks, it has been observed that their performance most tasks under adversarial perturbation is not close to human levels. This motivated researchers to obtain theoretical impossibblty results for adversarial robustness Shafahi et al. (2018); Dohmatob (2019); Dai & Gifford (2022), which state that for general data distributions, no robust classifier exists against adversarial adversary is limited to making small fp-norm-boune bounded perturbations. However, such results are seemingly in conflict with the fact that humans can classify most natural images quite well under small fy-norm-bounded perturbations, Even more, there rich literature on certified robustness, e.g., Zhang al. (2018); Cohen et al. (2019); Pal & Vidal (2020); Fischer et. al. (2020); Jeong & Shin (2020); Jia. et al. (2022); Pfrommer
innturbations, even when the

---

Published in Transactions on Machine Learning Research (10/2024)
et al. (2023); Salman et al. (2022); Eiras et al. (2022); Pal & Sulam (2023), where the goal is to obtain and analyze methods with provable guarantees on their robustness under adversarial attacks.
Pal et al. (2023) recently provided a solution to this apparent conflict, noting that existing impossibility results become vacuous when the data distribution is such that a large probability mass is concentrated on very small volume in the input space, a property they call (C, e, - This characterization implies that at least 1-6 ô probability mass is found in region of volume at most Ce-ne for small 8 ss 0 and large c. As an example, this property dictates that sampling random 224 x 224 dimensional image is extremely likely to not be natural image. This property is intuitively satisfied for natural datasets like ImageNet, and Pal et al. (2023) formally show that whenever a classifier robust against small fz-bounded attacks exists for a data distribution (e.g., humans for natural images), this distribution must be concentrated. This shows that indeed, robust classifiers against &g attacks can be obtained for natural image distributions, and there no impossibility.
While these results are encouraging, atlacks that are bounded in Euclidean norm have nice analytical properties that facilitated the results in Pal et al. (2023). In this work, we seek to understand if similar notions can provide insights on provable defenses against sparse adversarial attacks (bounded in their to distance) where the adversary is limited to modifying a few pixels on the image, but those pixels can be modified in an unbounded fashion. Even though for humans it seems trivial to correctly classify a natural image corrupted in a few pixels, this problem has stood out as a particularly hard task for machine learning models. The difference is extreme: Su et al. (2019) demonstrated that adversarially modifying a single pixel leads to large performance degradation of many state of the art image recognition models. Standard ideas for improving robustness, like adversarial training, seem to be empirically ineffective against sparse attacks. Since then, researchers have resorted to enumerating a large number of subsets of the input pixels, and taking majority vote over the class predicted from each subset, as means of obtaining classifiers robust to sparse attacks. The resultant methods (Levine & Feizi, 2020b) are expensive, and need probabilistic certificates due to the combinatorial blow-up in the number of subsets needed as the number of attacked pixels increases. Follow-up work by Jia el al. (2022) has employed complicated certification schemes to reduce the slack in these certificates, while still remaining computationally expensive. Most recently, Hammoudeh & Lowd (2023) carefully selected these subsets to speed up the cortificate computation. However, none of these existing methods utilizes the geometry of the underlying data distribution highlighted by our results. Departing from this stream of research, we propose a classifier that closely utilizes this underlying geometry to obtain robustness certificates. As a result, we provide a classifier that is lighter and simpler than all existing works, and an associated certification algorithm with Eu cortificates that are better than prior work.
Our proof techniques extend results in Pal et al. (2023) to sparse adversarial attacks. In practice, one can always project the pixel values to lie in some predefined range, say [0, I], before classification, so we can consider adversarial perturbations to lie within [o, 1]" without any loss of generality. In other words, our adversary at power e is allowed to modify techniques in Pal et al. (2023) break down under such an adversary, as their first assumption is to restrict attention to adversarial perturbations such that & + v cannot lie e-close to the boundary of the image domain. In our case, the geometry of the problem is radically different: even a perturbation of size 1 is sufficient to take any image to the boundary of the domain [0, 1]" (simply perturb any pixel to 1). As a result, although we are motivated by Pal al. (2023), our theory and certification algorithms are markodly different from those in that work.
image from to x' such that ||x - x' loo S e, |, S 1. The
In the above setting, we show that whenever there exists a classifier robust to adversarial modification of a few entries in the input, the underlying data distribution places a large mass, i.c., localizes, on low-volume subsets of the input space. We further show that the converse holds too, albeit with a strengthening of the localization condition; i.., we show that when the data distribution localizes on low-volume subsets of the input space, and these subsets are sufficiently separated from one another, then a robust classifier exists. These results suggest that such underlying geometry in natural image distributions should be exploited for constructing classifiers robust against lo attacks Indeed, we then propose simple classifier, called Box Nearest Neighbors (Box-NN), that utilizes this underlying geometry by having decision regions that are unions of axis-aligned rectangular boxes in the input space. Such a classifier naturally allows for Eo robustness certificates that improve upon prior work for certified defenses in a wide regime.
2

---

Published in Transactions on Machine Learning Research (10/2024)
To summarize, we make the following contributions in this work:
In Section 2 we show that a data-distribution p defining multi-class classification problem admits a robust classifier whose error is most 8 under sparse adversarial perturbations to e pixels, then there is subset S of volume at most Ce- and class & such that the class conditional 9s places large mass (S) 2 1 8 on S, i.c., 9& is (C, e² /n, 8)-localized. The constant C captures certain geometric properties of the robust classifier, and will be clarified later.
we show that a stronger notion of localization, which ensures that the class conditional distributions are sufficiently separated with respect to the Eg distance, is sufficient for the existence of robust classifier. In fact, this result generalizes to any distance d, showing the existence of robust classifier w.r.t. perturbations bounded in distance d whenever the data distribution p is strongly localized with respect to d.
In Section 3,
In Section 4, we propose a classifier certifiably robust against sparse adversarial attacks, called Box-NN, and derive cortificates of &g robustness for We then provide empirical evaluation on the MNIST and the Pashion-MNISS datasels, and demonstrate that Box-NN obtains stale-of-the-art. results in certified Eo robustness.
2 Existence of an Robuut Classifier implies Localization
We will take our data domain to be [0, 1]", to mimic the standard natural image classification tasks', i.e., == (z: | S 1}. We will take our label domain to be y {1, ...,, K), and assume that have a classification task defined by a joint data distribution over X' x V The marginal distribution over the classes will be denoted by py. The conditional distribution PxjY= for each class k E y will be denoted by =. Further, we will say that the classes are balanced when py(k) (k) k for all & E.
In this work, we will study adversarial robustness for non-trivial classifiers that are not constant over the entire domain X. For any such classifier f: X' - V, we recall the standard definition of robust risk Ra(f, c) against perturbations bounded in a distance d as
ea(s,)== = P (EE E Ba(I, é) such that f(z) # y) (..
Similarly, we define a classifier f to be (e, ()robbstt with respect to a distance d if the robust risk against perturbations at a distance bounded by is al most 5, iee,, Ra(J,e) S 6.
For the rest of this section, we will assume that p defines a task for which one can obtain a classifier f such that (f, cu) S 8, where Eo is a non-negative integer denoting the maximum number of co-ordinates that an adversary can perturb. Given such an S; we will show that p should satisfy the special property of localization. In other words, will obtain necessary condition for lo robustness. This special property of (C, c, localizatton is similar to Pal et al. (2023, Definition 2.2), with slight modification:
Definition 2.1 (Localized Distribution, modification of Pal et al. (2023)). A probability distribution over domain X' C Ra is said to be (C, (.C,,,lloallized if there exists subset S C X such that 4(S) > 1 - 5 but Vol(S) < Cexp(-e). Here, Vol denotes the standard Lebesgue measure on R", and g(S) denotes the measure of S under g.
Definition 2.1 is similar to Pal et al. (2023, Definition 2.2) but it removes the explicit dimension of the problem, i.e., n, from the volume constraint. This allows one to state the results in Pal et al. (2023), as well as ours, under the same definition. Additionally, we rename the property from concentration in Pal et al. (2023) to localization, order to distinguish ourselves from the well known notion of concentration of measure. These two notions are related and, before proceeding, we compare them in more detail.
1. Albbit with scaling natural images typically stored with each pixel value in |0, 255).
2The conditional dcusity is defined in standard fashion (x(x) = p(z, (k) Here, the quantity C, similar e and 8, parameter localization, and controls the extent of localization. C can be determined directly given access distribution p. or indirectly via Theorem 2.2 given access robust classifier.
3

---

Published in Transactions on Machine Learning Research (10/2024)
The notion of measure concentration from high dimensional probability theory roughly states that for a given large dimension n, "a well behaved function h of the random variables Z1, 71, 7n takes values close to its mean E Eh( Zn) with high probability" (Talagrand, 1996). A popular quantification of this notion states that for a metric space (R, d) and a probability distribution over X, the concentration function a defined as
sup (q sgx, g(5)21/2
1- q(
(1)
decreases "very fast" with f, where recall that S = f- E A:: d(x, S) S tJ. We typically say that q has the property of measure concentration if there is an exponential decay as (g.a(t) ~ exp(->t) for all 2 0, and some universal constant 7.
In contrast, the definition of (C, e, locaaliiinnionn requires the existence of S such that ((S) 2 8 and Vol (S) I Cexp(-c). Concentration and localization are similar in the underlying message: most of the mass in q is concentrated near a small region in space. However, the mathematical formalization is different, as localization ion does not require a fast enough rate of decay of the measure, and hence does not require an underlying metric on the space X. In order to show that a given distribution localizes, it is sufficient to provide a single instance of a set S S X that satisfics the localization paramcters. For our data domain X = [0, 1)"; we will consider a family and comment on their localization and measure concentration parameters, to shed light into their similarities and differences.
probability distributions given by la = Uni a)") for a E (0, 1],
For any S C [0, aa" C C,, we can simplify 1 1 ō
- S (s() + Vol S _ exp(-e) to obtain that
1 Ia is log (1-8) + n log
(1) (2).0) localized for any 8 E [0.1]. 1].
From the above we can see that keeping a < 1 fixed, becomes "more localized" as the dimension n increases. Similarly, keeping 5, n fixed, la becomes more localized as a gets closer to O. In this sense, the localization parameters depend on the scale of the support of the underlying distribution.
In contrast, as measure concentration depends on an underlying metric, the concentration parameters are independent of the scale of the support when the metric is invariant to scaling. As example, for X' equipped with the hamming metric, do(x, x²) ||æ x'Ilo, the concentration function for the distribution la can be shown to be
22
agg do (t) S 2 exp
(2)
Armed with the above definition, we will now derive a necessary condition for lo-robustness in terms of localization, by using measure-concenntationn result w.r.t. the Ey distance due to Talagrand (1995).
Theorem 2.2. If there erists a non-trivial (e, (..88)robust classifier f with respect to the to distance for data distribution p. then at least one of the class conditionals q1, 92..... 9K must be (C,ē/n, /n. -locaiize according to Definition 2.1. Further, if the classes are balanced, then all the class conditionals are (Cmax, e //, K8)- localized. Here, C and Cmax are constants dependent on f.
Proof. We are given a classifier f which (c.bu-robust w.r.t. perturbations bounded in the by distance. In other words, we have Re, (f) ) 5. Expanding this we get
Σ P a (r, such that S(T) Py -k) 8.
In other words, there exists class W' satisfying qu (fx X: 37 E Be, (2, such that f(ā) * k)) S 8. Defining the unsafe set for the class K' as Up = fo E X: 3a E Bio t) such that f(z) # kJ}, we have shown
q (Uw) ) & 8.
4

---

Published in Transactions on Machine Learning Research (10/2024)
Define Av C L to be the region where predicts W, f.e., A f X: f(x) = k}. Further, for any set Z. define Z+ to be all the points in the domain X' which are at most away from Z in to distance, i.c., Z = f E :: 3r E Z such that I - = S Then, we have
Up = {ar X: l such that I - x S e, f()) + k'}
{ir X: le E (x Ax) such that || æ|1o S c)
(X) Agr)*
Now, we will use measure concentration the unit cube from Talagrand (1995, Proposition 2.1.1): Lemma 2.3 (Proposition 2.1.1 in Talagrand (1995)). For B S 1]", dist(r, B) = minzen | =llo, any measure μ on [0, 1], we have
1 P xappe (x E B)
P (dist(B,x) (2) Roup
exp(-12/n)
Note that since the domain [0, 1] has n-dimensional volume 1, i.e. Vol( 1] = the uniform measure of any set u²( Vol(B), for S [0, Substituting B = X \ Ak' L =; e, μ = Unif((O, I)), in Lemma 2.3, we obtain
Vol(X Ax) exp(-eé (00-e2/n))
Vol(X' \ AAr))
Using Vol(X') \ Uv)) =1 - Vol(X \ As we obtain
Vol(X' Uk) < cxp(-c2/n)
(4)
Vol(d' | AAw)
Finally, combining (3), (4), and taking S X' Uk, we have
qr-(S) 2 8, Vol(S) S Cexp(--2/n).
where C' = T- + showing that qu is (C, e² /n, localizze If the classes were balanced, repeating the above argument for each class shows that is (C,e//n, Koy-localized for all E y for Cmax max; (1/(1 Vo)(A.))).
Discussion on Theorem 2.2. A few comments are in order for the above result.
1. Theorem 2.2 demonstrates that whenever a non-constant ln robust classifier exists for a data distribution, this distribution must be localized. This could be instantiated for real data sets like ImageNet to obtain interesting observations about the underlying distribution. For instance, humans are robust perturbation of a few pixels to any image in ImageNet. Then, Theorem 2.2 tells that ImageNet is localized. Note, however, that the localization parameters (ie., C,e,8 for the human classifier) are unknown.
The localization parameters in Theorem 2.2 are different than the concentration parameters Pal el al. (2023, Theorem 2.1). Specifically, Pal al. (2023, Theorem 2.1) shows that 8), connenttraii is necessary condition for ég-robustness under Definition 2.1, and will now show that (C, e /n, localization is necessary condition for fo-robustness. This demonnstates that the existence of classifier robust to 4n classifier implies a different kind of localization of the data distribution than robustness to l perturbations. While Pal et al. (2023) assume that their data lies in unit & ball with adversarial perturbation strength E [0, 1], we assume that our data lies in a unit Lo ball and with perturbation strength E
n... As such a direct comparison of the parameters not immediate as our work deals with objects very different from Pal et al. (2023).
Theorem 2.2 suggests that for obtaining l, robust classifiers, we should try to find and classify over the sets that the distribution localizes on. This a significant departure from the existing literature on fo-robust classifiers Levine & Feizi (2020a); Jia et al. (2022); Hammoudch & Lowd (2023), and indeed, we will obtain classifier in Section 4 that respects such geometry.
5

---

Published in Transactions on Machine Learning Research (10/2024)
We have now demonstrated that localization is a necessary condition for the existence of classifier robust to perturbations bounded in the Eo distance, i.e., perturbations having small support. Inspired by the investigations in Pal et al. (2023), we will now consider whether this condition is also sufficient.
3 d-Strong Localization implies Existence of d-Robust Classifier
Localization of the data distribution ensures that each class conditional concentrates on a small volume subset of X. However, as noted in Pal al. (2023), these subsets might intersect too much, in which case there might not exist classifier with low standard risk, i.c., Rea (f,0). Hence, one cannot expect localization to be sufficient for the existence of classifier with low robust risk, i.e., Rıg (J,e) with > 0. However, if these subsets were seporated enough, then one can expect to use them to build robust classifier. Indeed, we will now formalize this intuition to obtain a condition stronger than localization, which will be shown to be sufficient for the existence of a robust classifier.
Definition 3.1 (d-Strongly Localized Distributions, generalizing Pal et al. (2023)). A distribution is said to be (c, 6, ())sstongly-localline with respect to a distance d, if each class conditional distribution q localizes over the set Sy C such that (Sx) 2 1 8, and qk (UrreR S S ys where S denotes the e-expansion of the set S d, i.e., 5++ {x:: 77 E S such that d(xr, F) 5.
With the above definition, we will now obtain a generalization of Pal et al. (2023, Theorem 3.1) to an arbitrary distance
Theorem 3.2. p is (c, ststonglyy localized with respect to distance d, then there erists a classifier f such that R)(f,() S 7
Proof. At a high level, we will construct a classifier g that predicts the label k over an e-expansion of the set Sk on which the class conditional 9k localizes. We will then "shave off" some regions from each Sş to ensure g well defined. For the rest of the input space X' we will predict an arbitrary label, as we incur at most. y in robust risk. Our construction of the robust classifier is same that in Pal et al. (2023), extended to general d. However, bounding the robust risk of f needs technical innovations, since we are bounding the robust risk with respect to general distance d, opposed to the lz norm in Pal et al. (2023).
set For cach & E {1,2,... ..., K}, let Ss be the set over which the conditional density is localized, i.c., (xx) < 1-5.
Define S+ to be the e-expansion of the set S, as S+ = {x: Exd E S, d(c,x') S e). Define C2 to be the e-expanded version of the localized region S but removing the e-expanded version of all other regions Sk,, as
C (st \ Uk nx.
Similar to the construction in Pal et al. (2023), we will use these regions to define the classifier f: X
{1,2, 11.,....A K) as
1. i Ci if C2
2,
f(x)
K, if f Ck
1, otherwise
We will now show that ea(f.e) +8+% which can be recalled to be
Ra(f.e) = Σ (Ux)pr (y k),
(5)
where the qk mass in (5) is over the set of all points E X that admit e-adversarial example for the class k, defined as
Up (xr X: 35 Ba(a,e) n such that f(ō) + k).
(6)

---

Published in Transactions on Machine Learning Research (10/2024)
As saw earlier in the proof of Theorem 2.2, Us (X) Ck) nXX. ga (U&), which will in turn give upper bound on c))
nx We will obtain an upper bound on = =AN(AUUB)
Let A = St N and B = U. As C. - A B, we have
2 C. X (ANB
(XNA))
- (X)(()))) U (Unzl()n
Then, expand (X) Cz)te
(x (S
from the property (U (UUV) Uttuttt uvts Now, since all the mass of qu lies in N, i.e, qx(2) 1, we have (x(2 n VV (V) for any set V. Applying this, we have
gx (Uk) qx(d' \ Cx)
S th (X ( ($#9)** + + + (Uwza(enstt"
S qh (($t))) + qu (U))
Now applying Lemma A.1 we have (( = ((St) (V+e)-t2 V for any set V. Hence, we have ((St)
Again from Lemma A.1 we know that
C Si. Continuing,
(Ux))) S qu (5t) + qu (U
S + 7
Finally, as Expr k)) = from (6) we have Ra(J,e) e) S 6
We note that (Pal et al., 2023, Theorem 3.2) follows as direct corollary of our result Theorem 3.2 by taking d to be the le distance.
Implications for Existing Impossibility Results. In our setting, Shafahi el (2018) prove that for any classifier f: X X (1,2, (1. K} for any class with P(Y = k) s 1/2, any point Q either mis-classified, or admits an e-adversarial example with probability at least
-- S.g exp (-²/n).
where By. sup, (x) depends on the class conditional (k- When qs is localized, 3qz can grow faster than exp (-e/n), making the lower bound vacuous. This implics that for localized data-distributions there no impossibillly, and there is wide class of high-dimensional classification problems for which robust classifiers exist. We now provide concrete example.
Example 3.1. Let us consider a problem with classes defined by the distribution p such that P(Y 0) P(Y 1) = 1/2, the class conditional a P(X 1) Uni (1,c)), and similarly 92 = P(X 2) (-, For this distribulion, Bn Bog = exx(nn), and the lower bound (7) becomes vacuous for S Vn as
1- exp (-2/n) = - 2exp( m)) 5.
Even though Example 3.1 is quite simple, the construction of small loo balls in the input space containing most of the mass of the distribution quite general, and depicts a wide class of data-distributions where existing impossibility results are vacuous. We will now demonstrate that these general theoretical ideas lead to practical &p robust classifiers.

---

Published in Transactions on Machine Learning Research (10/2024)
4 l- Adversaaiilll Robust Classification via the Box-NN classifier
In this section, our aim will be to derive fo-robust classifier by utilizing the geometry exposed by Theorem 3.2. To this end, we will first investigate how a robust classifier looks like for simple 2-class problem in 3- dimensions. This will motivate a general form of a classifier whose decision regions are axis-aligned cuboids, or boxes, Finally, we will generalize this classifier to obtain a fg-robust classifier and derive corresponding &g certificates.
4.1 Development and Robustness Certification
Consider n = 3, and say there are two classes, CAT and DOG, defining conditional distributions qi and 92. strongly localized over S1 and S2 respectively, such that qı (1(5 = and (2( = 0. In such a situation, Theorem 3.2 (invoked with 1) constructs robust classifier fa the following:
dog,
if E St1 if E st otherwise.
fa(x)
cat,
cat,
However, in practice, S1, S2 might be very complex, and hence fA might be computationally hard to evaluate. For instance, Fig. shows an illustration where these sets (shaded green and orange) have complicated shapes.
Ba
Bust
Figure S1 the green shaded region around Tdog where the class dog localized, and S2 is the orange shaded region around Teat; where the class cat localized.
S2, From Fig. 1, see that the classifier fA is robust 1-pixel perturbations whenever S1
Theorem 3.2 predicts. More importantly, we see that a perturbation of single pixel of any Teat E S2 lies within the union of the orange cuboids. In other words, {x' E [0, | S 1, E Si} = St1 C ORANGE, and similarly for the dog class. Furthermore, we see that the intersection of these orange cuboids is given by the cube Beat- We can see that for any Beat; no single-pixel perturbation v can take x + outside the orange region ORANGE, and similarly for the dog class. However, Beats Bdog are very efficiently described, they are simply axis-aligned polyhedra enclosing S2 and S1 respectively. This motivates modified classifier fB,
dog,
if B+1
fa(x)
cat, if x E B+1
cat,
otherwise.
While fB efficient describe, it ignores large portion of the input region outside the green and the orange cuboids, i.e., X') B U B+1 by making the constant prediction cat in this region. We can further extend fB to attempt to correctly classify those regions well, by computing to distances to our boxes Beat, Baog.
fc(x)
arg min dist(z, By), yE (cat,
8

---

Published in Transactions on Machine Learning Research (10/2024)
where
dis S) = min ||ello sub. to x uue
(8)
gives the minimum number of pixel changes needed to get from x to S. While solving (8) computationally hard for general 8, the following lemma shows that for our axis-aligned boxes B, (8) can be computed
efficiently, in closed form. The proofs of all our results can be found in Appendix A.
Lemma 4.1 (cg distance to axis-aligned boxes). For an acis aligned box B b) specified as B(a, b) = {x: a as S b}, where a, b, x E RR,, and all inequalities are element- wise, we have
dist(r, B(a, b))
Σ (x. $ b.l)
which can be computed in (nn) operations.
For real data distributions, however, having a single box per class would be overly simplistic and not provide good accuracy. Thus, we generalize fc to our Box-NN classifier operating on boxes {Bi, B2,..., BM } such that we have an label Im {1, ........ K, associated with each Bm Our Box-NN classifier is then defined as
Box-NN(r, B) ym* where m arg min dist(r, B.n)
Note that, so far, we have not described how these boxes B are learned from data. This will be the subject of Section 4.2 and onward. We can now obtain to robustness certificate for Box-NN via the following Theorem.
Theorem 4.2 (Robustness Certificate for Box-NN). Given a set of boxes B and their associated labels define
m² arg min dist(x, Ba),
di = cist Bm)),
and
min d2 m: Um # Fmm=
dist(x, Bm).
Then, with margin(x)) mx)gin(z)/2.
d2 d1, we have BOx-NN(x, B) Box-NN(x', BB) whenever || æ/1o <
Key Intuition. Our robust classifier Box-NN essentially a generalization of the nearest-ncighbor classifier to nearest-box classifier, specifically suited to to metrics. This simple form lurns out the right choice, in the sense of the theoretical motivation of our previous section, for defending against sparse perturbations. As we will shortly see, Box-NN also empirically produces better certificates than prior work in several regimes.
Having developed the geometric intuition and the theorctical robustness guarantees for Box-NN, we will now describe how we learn our classifier from data, and the associated challenges.
4.2 Learning Box-NN from Data
In this section, we are concerned with learning boxes {Bm} } and their associated labels {um such that Box-NN obtains a high accuracy under sparse adversarial perturbations. For the rest this section, we will refer to the classifier Box-NN as fe, with the learnable parameters {ax, by, yk M following the notation in Lemma 4.1.
The quantity we interested in maximizing is the robust accuracy, defined 1 Re, (So,<) following our notation in Section 2. As we do not have access to the data distribution, will instead be concerned with maximizing the empirical robust accuracy RobustAce(fo. defined over a set of samples {2,, 1 given by
N
1 Vv' || - -xyllo S c, fo(x') = vil
(9)
N
9

---

Published in Transactions on Machine Learning Research (10/2024)
The objective in (9) is complicated object, and direct maximization w.r.t. 9 is challenging. In the following, we will first lower bound (9) and then use several optimization tricks to efficiently maximize this lower bound.
Recall from Theorem 4.2 that fo(x) = Jo(x') for all x' satisfying I I'llo S Co(x) def margin(x)/2, where Co a pointwise certificate (at x) of robustness for fo- With this, we have the certified accuracy lower bound RobustAco(fo..)) 2 CertAco(Ja. defined as
N
CertAcc(fe, E)
def
Σ 1=1
[ff((a)) = vol ([)a(a)) 2 el.
(10)
N
We will take a gradient based optimization approach to maximize (10) over 0. However, since the gradients of [[] are zero almost everywhere (and discontimoos otherwise), we will progressively relax the indicators in (10). To this end, we maximize the integral of Cert over all 2 instead treating it point-wise",
leading to the objective
(i
1 N
Σ [fo(s.)) -.))CC(ms.
(11)
Approximating min. Recall from Theorem 4.2 that the margin involves the min function,
margin(x)) min dist(a; Bm) min dist(x, Bm).
3m Fu..
The gradient of min w.r.t. its input (ct,..., Cm) is extremely sparse", and hence very small number of parameters 0, are updated at each step of gradient descent using gradients of (11). As a result, optimization is extremely slow. We remedy this by using a soft approximation to min which has dense gradients,
min, fei........................... cMs def
M
exp(-Tcm)
(12)
m== E, exp(-re,)
where T is a parameter that approximately controls the sparsity of the gradients. The function min, is equal to min the limit t + oc, and reduces to the average when t =
Furthermore, we find that for many data points rs, a small number of boxes m contribute a lot to the final loss due to large distances dist(z;, Bm). As a result, learning is slow for parameters corresponding to the remaining boxes. To prevent such imbalance, we clip the certificates to 50. With these approximations, we obtain
(2
1 N
Σ
lffo(x.) vil Co(as),
where Co(xr) is defined as
min, dist(x, Bm), 50) 50).
min min, dist(x, Bm) m
(13)
me: ym #um
Relaxing Indicator Functions. Now observe that Lg is still function of indicator functions, due to the dist function in (13), which was derived in Lemma 4.1 to be dist B(a,b) b)) = E (a; & [aa, b:]). Again, as the gradients of [|:] are zero almost everywhere, we perform a conical approximation to 1 (z, & [a bi)) which has non-zero gradients:
conical(1, a; b:) def max(a; - x, 0) + max(x - bi, 0).
(14)
Finally, we replace the indicator 1[fx(x;) = y:] in L2 by where 8; = +1 if f(x;) and = -1 otherwise, to have the misclassified data-points contribute to the loss. These modifications lead to our final objective L(0).
Li,, J:z0 1/c alde
5V min((i, (2..... Cm) = (0....,..
0, 1,0,....
.,. ........)
egr, where ey is the jth standard hasis vector, and j = arg min, Sy.
10

---

Published in Transactions on Machine Learning Research (10/2024)
Improving Initialization. We initialize 0 by using set of boxes defined from the data. This is done by first drawing subset 7 of size M uniformly at random from the training data-points, and then initializing with axis-aligned boxes centered at these data-points, as {(B(r 0.1, x + 0.1) y): (x, y) E Th, where the scalar is added to, or subtracted from, every co-ordinate of the vector. Having described all the tricks used for optimizing Box-NN, we now proceed to performing an empirical evaluation Section For the interested reader, we also ablate over the training strategies mentioned above Appendix B.2.
5 Empirical Evaluation
In this section, we will briefly describe existing methods for probabilistic 4y certification, (Levine & Feizi, 2020b) and (Jia et al., 2022) as well as deterministic & certification (Hammoudeh & Lowd, 2023), and then empirically compare our (deterministic) to certified defense Box-NN these approaches.
Levine & Feizi (2020b) and Jia et al. (2022) extend the technique of randomized smoothing (Cohen al., 2019) to randomized ablation (RA), where given any classifier J (e-g., neural network), they produce a smoothed classifier by zeroing out pixels uniformly at random:
(Ap(z) = arg max P (f(z0v)=
(15)
k u~Unif(V,)
where V {v E {0, 13":: ||o|o = p} is the discrete of all binary vectors of length n having exactly p ones, and O denotes the Hadamard product. For this construction in (15), counting argument leads to the robustness certificate in Levine & Feizi (2020b), which we compare to in Fig. 2. A more complicated analysis based on the Serman--Paarso, lemma leads to a tighter certificate in Jia et al. (2022), which is also included in our comparison in Fig. 3 (left), denoted by RA Both these certificates are randomized, &e., they hold with a confidence 1 1-a a, where a. p are ayper-parameters that trado-off benign accuracy to robustness, and can be chosen empirically. According to standard practice, we fix a 0.05 and produce plots for varying p. The interested reader can refer to Appendix B.3 for description of the certification procedures developed in Levine & Fcizi (2020b); Jia et al. (2022).
1.00
1.00
RA
RA
BA
BAg
RA
RA
Certified Accuracy
0.75
RA
Certified Accuracy
0.75
RAgo
BoxNN
BoxNN
0.50
0.50
0.25
0.25
0
10
20
30
40
50
0
10
20
30
40
50
Certified Radius
Certified Radius
Figure 2: Comparison of Randomized Ablation (Levine & Feizi, 2020b) to our method Box-NN on the MNIST (left) and FashionMNIST (right) datasets. In each figure, the dotted lines correspond to different hyperparameter settings p. Details in text.
More recently, given any classifier f, Hammoudeh & Lowd (2023) produce a determinstic to certified classifier into disjoint partitions V, and then producing the majority
by partitioning the set of pixels prediction of over V:
FPA(x) Majority(f(av))ver
(16)
where f(zv) is defined the prediction of obtained after zeroing out the pixels x not in V. Hammoudeh & Lowd (2023) then produce a certificate by counting the difference in the votes of the majority label to the
11

---

Published in Transactions on Machine Learning Research (10/2024)
1.00
1.00
RA
FTAD
RA
FPA
Certified Accuracy
0.75
RAI
Certified Accuracy
0.75
FPA
RA
FPA
BoxNN
FPA
0.50
0.50
BoxNN
0.25
0.25
0
20
40
30
50
Certified Radius
Certified Radius
Figure 3: Comparison of Jia et al. (2022) (left) and Hammoudeh & Lowd (2023) (right) to our method Box-NN on the MNIST dataset. The dotted lines correspond to different settings for the hyperparameter p. Details are mentioned in text.
Table 1:
Comparison of the median certified radius F obtained by our Box-NN to the best hyperparameter settings for prior work.
DATASET
МETHON
F
Box-NN
13
RA Levine & Feizi (2020b)
MNIST
RA Jia et al. (2022)
10
FPA Hammoudeh & Lowd (2023)
9
FPA Hammoudeh & Lowd (2023)
12
Box-NN
22
FMNIST
RA Levine & Feizi (2020b)
16
runner-up label in (16). In Fig. 3 (right), we compare to the best performing strategy for constructing V (Hammoudeh & Lowd, 2023) named "strided" and denoted by FPA where equally spaced pixels are selected for each partition, i.e., V j = mod p)--) Here is a hyper-parameted as earlier, and we vary p to produce the plots in Fig. 36. Note that (Hammoodeh & Lowd, 2023) also obtain an improved certificate by using an aggregation more complicated than the majority vote (called "FPA with run-off elections"), which is compared to in Fig. 10, where is denoted by FPA B The interested reader can refer to Appendix B.3 for p.
more details.
Results Recall from Section 4.2 Eq. (10) that the certified accuracy of classifier g against e-bounded adversarial perturbations, CertAcc(g, c), can be obtained given point-wise certificate C' for For each of the methods described so far, we plot Ace against using the corresponding robust classifier and the certificate C over samples from the test set of the datasets mentioned.
A commonly used metric for comparing certified accuracy curves adopted the litcrature (Levine & Feizi, 2020b; Jia al., 2022; Hammoudeh & Lowd, 2023) the median certified radius, which is the largest perturbation strength under which classifier is certified to have atleast. 50% robust accuracy. As can be seen in Table our method Box-NN outperforms all existing methods under all hyperppormmtter settings this metric.
The median certified radius captures a small slice of the full certified accuracy curve, which provides a complete picture. Observe that the dotted curves Figs. 2 and 3 remain lower than our red curve except at small allack strengths. This shows that Box-NN able to produce better certificates al most radii, and trades-off
We the results reported Hammoudeh & Lowd (2023, Table 27) given that no public implementation of the method is available, to the best of our knowledge.
12

---

Published in Transactions on Machine Learning Research (10/2024)
robustness at higher radii for benign accuracy small radii. Without any dedicated hyper-pane paper-prreetter tuning, Box-NN dominates any single dotted curve for a large range of attack strengths, demonstrating that certified defenses closely utilizing properties of the data-distribution can outperform complicated ausembling-base defenses which ignore properties of the data.
6 Conclusion, Limitations and Future Work
In this work, we developed a theoretical to exploit properties of the data distribution for robustness against sparse adversarial attacks. We showed that data localization the property that a data distribution p places most of its mass on very small volume sets in the input space characterizes the existence of 4--robsst. classifier for p. Following this theory, developed a defense against sparse adversarial attacks, and derived corresponding robust.ness certificate. We showed that this certificate empirically improves upon existing shate-of-the-art in several broad regimes.
The primary limitation of our work the difficulty in efficiently learning classifiers that have axiseel decision regions. While we are able to successfully employ several optimization tricks for datasets like MNIST and Fashion MNIST, the task becomes harder on more complicated datasets, even though the geometry required for the underlying data-distribution remains the same due to our general theoretical results. These optimization difficulties mostly stem from the strict requirement of axis-aligned boxes for distance computation in Lemma 4.1. In the future, we hope to trade-off efficiency in the distance computation in favor of richer decision boundaries that can be learnt esficiently and generalize well.
Acknowledgements
The authors thank the anonymous reviewers for their valuable suggestions, which helped improve this manuscript. This work was supported by Amazon (via the JHU-Amazon Initiative for Interactive AI, A12AT), DARPA (via GARD HR00112020010 and HR00112000004) and NSF (via Grant 2031985 and 2212457).
References
Jeremy Cohen, Flan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310 1320. PMLR, 2019.
Zheng Dai and David Gifford. Fundamental limits on the robustness of image classifiers. Tn The Fleventh International Conference on Learning Representations, 2022.
Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In International Conference on Machine Learning, pp. 1646-1654. PMLR, 2019.
Francisco Eiras, Motasem Alfarra, Philip Torr, M Pawan Kumar, Puneet K Dokania, Bernard Ghanem, and Adel Bibi. Ancer: Anisotropic certification via sample-wise volume maximization. Transactions of Machine Learning Research, 2022.
Mare Fischer, Maximilian Baader, and Martin Vochev. Certified defense to image transformations via randomized smoothing. Advances in Neural Information Processing Systems, 33:8404 8417, 2020.
Zayd Hammoudch and Danicl Lowd. Feature partition aggregation: A fast certified defense against a union of sparse adversarial attacks. arXiv preprinl arXi::2302.1163 11628 2023.
Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothod classifiers. Advances in Neural Information Processing Systems, 33:10558 10570, 2020.
Jinyuan Jia, Binghui Wang, Xiaoyu Cao, Hongbin Liu, and Neil Zhenqiang Gong. Almost tight 10-norm certified robustness of top-k predictions against adversarial perturbations. In International Conference on Learning Representations, 2022.
Alexander Levine and Soheil Feizi (de) randomized smoothing for certifiable defense against patch attacks.
A Advances in Newral Information Processing Systems, 33:6465-665 (4755,66667666 2020a.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, 2020b.
Ambar Pal and Jeremias Sulam. Understanding noise-angmented training for randomized smoothing. Transactions Machine Learning Research, 2023.
Ambar Pal and Rene Vidal. A game theoretic analysis of additive adversarial attacks and defenses. Advances in Neural Information Processing Systems, 2020.
Ambar Pal, Jeremias Sulam, and René Vidal. Adversarial examples might be avoidable: The role of data concentration in adversarial robustness. Advances in Newrul Information Processing Systems, 2023.
Samuel Pfrommer, Brendon G Anderson, and Somayeh Sojoudi. Projected randomized smoothing for certified adversarial robustness. Transactions Machine Learning Research, 2023.
Hadi Salman, Saachi Jain, Eric Wong, and Aleksander Madry. Certified patch robustness via smoothed vision transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pallern Recognition, pp. 15137 15147, 2022.
Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? arXiv preprint 1rXii:1809.02100 2018.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5))828-841, 2019.
Michael Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifigues, 81:73-205, 1995.
Michel Talagrand. A new look at independence. The Annals of probability, pp. 1-34, 1996.
Huan Zhang, Weu Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
14

---

Published in Transactions on Machine Learning Research (10/2024)
A Auxilliary Lemmas and Proofs
Lemma A.1 (Properties of expansion and contraction, extending Pal et al. (2023)). For a distance d, set A S [0, 1]", define A+ = {i e [o, : dista(æ, A) S c), and A = fx E [0, 1 Ba(a, c) S A}. Then, for N,O5 C [0,1]", we have
-Wnno===NNo
= (N+ where e denotes complement [0, 1)
(N = N \0
4. (N N
5. (ata)ta C (+atta)
Proof. The first four assertions of this Lemma are standard results in mathematical morphology, dealing with the erosion and dilation of sets, and are reproduced here from Pal et al. (2023) for clarity.
Let M Nno.
= (r:ZE M, C (x: N,
Let M No.
M fr: x E M, Ba(z,e) S a Ba(z,e) CNT
fx:x# & N, Va E c) x' N
{x: Va' E d'
= (M (x: 3t's E
N
= -
3. Let M O, we have M = by Property 1, and then N ~0
N n (O+eje by Properly 2.
4. Let = We have M = No Taking c-contractions, and applying the first and second properties get M N+ u
5. For set M, and any 6 0, c2 0, have
(M+a) to ç M
The above property be derived from the triangle inequality applied to d, as
(M tra
(r: 3x's E M d(x,x)) S {2)
{x: Fr E X, E M, d(z', xx) $ 62, d(x" , ,f) $
{a: Er" M, d(z", x) < + Mta+ta)
Lemma 4.1 (en distance to axis-aligned boxes). For an uxis aligned bor B(a, b) specified as B(a, (x: S b}, where b, z E RR" and all inequalities are deementwwsse we have
dist(r, B(a. b)) = Σ (as & Jar bz]).
1=1
which be computed in (nn) operations.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. For any given 2, recall the definition of dist to be dist(x, ((a, B(at(x,B(a,b) b)) min ye | Vllo- For any B(a,b) we have,
n
| - vilo- = Σ (z + 1/1
Σ
1 (s & Jas, bil) Jai, (ai,b:)) Σ (as [as,bi)
(17)
i=1
(2; & (ai, bil). Then, consider yn E B(a, b) defined as The above implies min g(a.g) || yllo 2 Ei=
az V
if x; & (ai, bj] otherwise
(18)
We have l1v* - z:lo- Ei= 1ax, (a,, b,l), which attains the lower bound dist(z, ((a, The result follows.
Theorem 4.2 (Robustness Certificate for Box-NN), Given set of boxes B and their associated labels LM (ym) mm=1, define
m" = arg min dist(x, Bm), dp = =dsst Bm-),
m
and
d2
min mi Um # Vm
dist(xr, Bm).
Then, with margin(x) def d2 di, we have BOX-NN(r, = Box-NN(a', ,B) whenever || - æ/1o < mr)2i
Proof. Let x, x' E X. Define B, =B Um = Um }. and B2 = {Bm= Vm + ymu }. Further, define d, d2 as
d1(x') = min dist(x', B); dz(x') min dist (i's B); BEB₂
BEB
Our goal would be demonstrate that as long as ||0- x' margin(x)/2 we have d2(x') > di (x'), implying that the prediction remains the same x'. Consider any B B2, and apply the triangle inequality to get
dist(x', B) || s' 2 dist(x; B).
(19)
where (19) can be seen
dist(x', B) ||:r 2'11o
min 11y 1/11o ||=c x lo 2 min
|ly æl1o dist(r, B).
(20)
yEB
yEB
Further, taking a minimum on both sides of (19) over all B E B2 leads to
dz(x') + | x' llo d2
(21)
Similarly, consider any B E Bi, and apply the triangle inequality to get dist(r, B) + || x'1lo 2 dist(x', B), Taking minimum over both sides of (22) over all B B1 leads to
(22)
di || - x llo 2 di (z').
(23)
Adding (21) and (23), have
dz(x') - d1 (xx') + 2| 2'1lu 2 d2 d1 = dz(x') ) dx(x)) 2 margin(a)) 21| x'1lo.
(24)
(25)
from where can see that dz(x') - di (x') > 0 whenever || x'llo < marginnxx/22 required.
0
16

---

Published in Transactions on Machine Learning Research (10/2024)
B Additional Experiments
B.1
Additional Details for Figures
We provide fine-grained numerical details for Figs. 2, 3 and 10. We sample the r-axis at equally spaced
intervals of size 4 and report the certified accuracies at certified radii of {0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 403 in Tables and 3.
Table 2: Certified Accuracy on MNIST corresponding to plots in Fig. 2 (left), Fig. 3, and Fig. 10.
CERTIFIED RADIUS
METHOD
12
16
24
40
Box-NN
89.74
80.68
68.61
55.63
43.95
33.34
24.71
16.54
8.26
3.57
1.48
RA10
76.62
20.81
16.36
13.1
10.8
8.39
5.99
3.72
1.47
0.09
0
RA20
91.33
17.19
33.69
23.49
15.15
7.3
0.49
RA
96.51
76.08
50.76
16.03
0
0
RAso
97.96
83.84
34.45
0
RAD B
98.75
86.1
0
0
RA
97.78
88.45
39.75
0
0
0
RA R
10
96
85
62
21
0
0
0
RA
90
76
39
12.98
2.7
FPA
98
87
0
0
0
FPA
95
86
66
20
0
0
FPA
91
79
59
35
13
0
0
FPA
83
70
39
26
7
FPA
74.99
61
47
34.97
25
17.9
12.43
8.11
3.89
0.42
0
FPAB
99
87
FPA 25
96
88
71
20
0
0
0
0
0
FPA
93
83
67
44
14
0
0
FPA 65
87
76
50
37
23
12.14
2.97
FPA
81
68
56.44
44.65
34.68
25
17.82
11.09
5.28
0.45
0
Table 3: Certified Accuracy on Pashion-MNIST corresponding to plots in Fig. 2 (right...
CERTIFIED RADIUS
METHOD
0
8
12
16
20
24
28
32
36
40
Box-NN
78.43
73.84
69.31
64.44
59.26
53.86
48.39
43.43
38.73
34.05
29.97
RA10
78.96
64.28
59.15
53.86
48.32
42.32
36.07
30
24.08
17.69
11.31
RA
84.05
73.65
67.54
60.05
50.35
37.17
18.03
0
0
RAw
87.7
77.1
65.4
39.9
0
RAga
89.22
76.54
48.89
0
0
0
0
0
17

---

Published in Transactions on Machine Learning Research (10/2024)
B.2 Ablation Study
We provide ablation study on the various stralegies used to effectively train BoxNN developed in Section 4.2. For each of the following certified accuracy plots in our ablation study, we fix all the other paramcters at the values specified in Table (those values correspond to those reported in the main text, and are explained in the following description), and vary the parameter specified. The red curve the same in all the plots, and corresponds the BoxNN plots in the main text.
Table 4: Default Parameters (red curve) for Ablation Study of BOxNN.
min
INDICATOR APPROXIMATION
BOXES M
CLIPPING 3
OPTIMIZER
APPROXIMATION
INTTIALIZATION
mini
conical
0.1
2500
50
Vanilla SGD (0.2)
Indicator Relaxation. Rocall that we relax the indicator function using the conical approximation (14) (both applied element-wise to vectors). We ablate with approximatious, which call 4, defined as
(12, a, 3) || aal1 + || B11
(26)
and 12, defined as,
12(x, 0) = || - - + 1 B12.
(27)
Notice that without any approximation, the indicator function has zero gradient wherever is differentiable, and hence gradient based optimization does not make any progress. Hence, we omit the option of no approximation from ablation in Fig. 4.
1.00
BoxNN(couical)
BoxNN(2)
BoxNN(4)
Certified Accuracy
0.75
0.50
0.25
0
10
20
30
40
50
Certified Radius
Figure& 4: Ablation over the choice of the relaxation for the indicator function.
Initialization. For each box, we choose the location and size at initialization. For location, we find that centering boxes initially on training data points is always much better than random initialization, and hence we omit this from our ablation. We ablate on the size of the box a, such that the boxes at initialization are defined as {(B(x a, a), v): (x. y) T), for subset T of size M chosen uniformly at random from the training data, mentioned in Section 4.2. The resultant ablation is shown in Fig. 5.
18

---

Published in Transactions on Machine Learning Research (10/2024)
1.00
(oxNN 0
Bo 0.1)
BoxNN(a 0.2)
Certified Accuracy
0.75
BoxNN(a 0.3)
BoxNN(a= 0.35)
BoxNN(a 0.4)
0.50
0.25
0
10
20
30
40
50
Certified Radius
Figure 5: Ablation over the size of the inital boxes a. Note that the initial guides the optimization process to trade off benign accuracy (radins 0) with certified accuracy at higher radii.
3. Number of Boxes M. The number of boxes M above controls the expressive power of BoxNN. In order to maintain balance across classes, we assign an equal number of boxes for each of the 10 classes, and ablate on the number of boxes per class M/10 in Fig.
1.00
BoxNN/M 500)
BoxNN(M 1000)
BoxNN(M 2500)
Certified Accuracy
0.75
BoxNN(M 3000)
0.50
0.25
10
20
30
40
50
Certified Radius
Figure 6: Ablation over the number of boxes M.
4. Clipping Certificates Recall that in (13), we clipped the robust certificates in the optimization objective to 50 pixels to prevent few boxes from dominating the loss. We ablate over this clipping value B in Fig. 7.
Optimizer. We ablate over a few choices of the gradient- optimizer for our problem: (a) vanilla SGD with learning rate of 0.02, (b) SGD with learning rate of 0.02, momentum of 0.9, and weight decay of 0.0005, and (c) Adam with learning rate of 0.001, and standard decay factors, in Fig. 8.
Approximation of min. Recall that we replace the function min by an approximation obtain non-sparse gradients aid the optimization process. We describe the approximation min, in Eq. (12), and ablate {0, 0.5, 1, 0o), where recall that ming is same as the average function, and
19

---

Published in Transactions on Machine Learning Research (10/2024)
1.00
BoxNN(3 = 100)
BoxNN = 50)
BoxNNG3 10)
Certified Accuracy
0.75
BoxNN(3 5)
0.50
0.25
10
20
30
40
50
Certified Radius
Figure Ablation over certificate clipping value B. Note that the 3 100 line is almost the same as the B 50 line, there is no further effect due to clipping after 50.
1.00
1.00
BoxNN(SGD)
BoxNN(min
BoxNN(SGG + Momentum)
BoxiN(mingo)
BoxNN (dam))
BoxNN(ming)
Certified Accuracy
0.75
Certified Accuracy
0.75
BoxNN(mings)
BoxNN(ming)
BoxNN(-LSE)
0.50
0.50
0.25
0.25
10
30
50
10
20
30
40
50
Cortified Radius
Certified Radius
Figure 8: Ablation over the choice of the optimizer.
Ablation over Approximation of min.
Figure
that min is the standard min function. the logsumexp function,
We also compare to approximation by using
min(e1, ....., CM) -logsumexp(-ar -2, ....... -CM) log Σ
exp( (m
(28)
m=1
The resulting ablation is presented in Fig. 9.
20

---

Published in Transactions on Machine Learning Research (10/2024)
B.3 Additional Details and Certification Procedures
In this section, for the sake of completeness, we will brielly summarize the certification procedures developed in Levine & Feizi (2020a); Jia et al. (2022); Hammoudeh & Lowd (2023), which form our baselines for comparison in Section 5.
Certification procedure for RA (Levine & Feizi, 2020a). Recall from Eq. (15) that given a base classifier f, Levine & Feizi (2020a) produce a smoothed classifier g as
RAp(2) = arg max VVUn)(((V))
P P (f(=@))=
((15) revisited)
where V, {w E {0, ||o|o = p} is the discrete set of all binary vectors of length n having exactly P ones, and @ denotes the Hadamard product. The method to produce a certificate of to robustness in Levine & Feizi (2020a) follows the technique developed in Cohen et al. (2019), which is to bound the change in the probability assigned to the top class k* in (15) when x is perturbed. In other words, letting (c( = P Uni((V()))) (f(r Ô v) k) for & E 21, K.. and k* = arg max (t(T)), Levine & Feizi (2020a)
show that
TRAA) p
if pk- (z) > 1.5-
then RA,(x)= = k- Va' such that || - z S TRA,
(29)
Thus, the greatest quantity TRA, that satisfies the if condition in (29) becomes the to robustness certificate for the classfier RAp at the input point x.
However, obtaining of the probability P& (2) exactly is computationally infeasible, due to the exponentially large size of pp, and hence evaluation of the classifier RA, and the certified radius TRA, is computationally produce such randomized smoothing certificates in practice is
infeasible. Nevertheless, the technique to obtain high confidence lower bound on p&* using several samples from (V,) following standard statistical estimation literature, and use this lower bound for computing FRA, (Cohen et al., 2019, See 3.2.2).
Certification procedure for RA (Jia et al., 2022). Jia et al. (2022) produce tighter analysis of the certificate of robustness for the classifier defined in (15). Their primary contribution is to develop techniques that can provide to robustness certificates for the top-k predictions where k can be greater than 1. For the purposes of comparison to our work, we are only concerned for the special case of k k= 1 in their certificate (Jia et al., 2022, Theorem 1). As Jia et al. (2022) remark, in this case, the form of the certificate is identical to Levine & Feizi (2020a), with the important difference that Jia et al. (2022) utilize the fact that each of the probabilities pk (x) are integer multiples of - by incrementing the empirically computed lower bounds (:)
on these probabilities to the nearest integer multiple of (-) As these modilied probabilities (1)) satisly
"RAB) is equal to or
(x( 2 pk(2), the largest radius TRAy that satisfies the condition pb(x)) > 1.5
greater than VRA,, resulting in a higher certified accuracy curve.
Certification procedures for FPA (Hammoudeh & Lowd, 2023). As opposod to the randomized defenses above, Hammoudeh & Lowd (2023) build a classifier that is simply a majority vote among several sub-classifiers, each looking at a subset of the pixels of the full input image. More formally, partitioning the set of pixels (1, into disjoint partitions V, recall that the classifier certified in Hammoudeh & Lowd (2023) is
FPAA(r) = arg max (V E V: f(vv) = =k),,
((16) rewritten)
k
where f(vv) is the prediction obtained from a classifier that zeroes out the pixels of x not in V. Defining the number of votes for class & as n = I[V E V: f(v))= = k}l for l E f1, K), the winning class as k = arg max, ng, and the runner-up class as TTT = arg max ni, Hammoudeh & Lowd (2023) present the robustness cortificate by a simple counting:
FPA (x') = 18* Vx' such that || - æ01o S TPPA^ 2
def Tkk- T1jaa
(30)
21

---

Published in Transactions on Machine Learning Research (10/2024)
For evaluating the above certificate "PPAA for any imput 2, one needs to compute ny for all the classes. This is easily done by counting the votes for each class from each classifier f(av), V E.V.
Hammoudeh & Lowd (2023) then note that the above certificate discards the information from all the classifiers which did not predict k* or km, and remedy this in their improved certificate ТEPАв. For this, the idea to first determine k' and kTu, and then get all the classifiers f(vv) vote for one of these two classes. The predicted label is the majority winner of this vote, i.e.
FPA B (a) Majority(vote (vote ".")
(31)
While the above description of a two-round voting is quite general, the actual voting scheme in Hammoudeh & Lowd (2023) is implemented by setting f be a neural network classifier, and the vote decided by which class among fk", ,"") is assigned large probability by the network. Evaluation of the certificate "PPAB now becomes much more complicated due to the complicated relationship between the label predicted and ny- Nevertheless, "FPA is typically larger than TEPAΛ, and we produce a comparison to our method BoxNN. Specifically, in Fig. 10, we compare BoxNN against the numbers reported in Hammoudeh & Lowd (2023, Table 27) ("FPA with run-off elections"). We observe that BoxNN improves upon the median certified robustness against FPAB, and more generally mirrors the observations in Section with respect to other baselines.
1.00
FPA
FPA
Certified Accuracy
0.75
FPA
FPA
FPA
0.50
BoxNN
0.25
10
20
30
50
Certified Radius
Figure 10: Comparison of Hammoudeh & Lowd (2023) (dotted lines) to our method Box-NN (red line) on the MNIST dataset. The dotted lines correspond different settings for the hyperparameter p. Details are mentioned in Section 5.
22


Reviews:
[{"review_id": "w5xvRIX3qv", "reviewer": "Reviewer_yfCE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The theoretical results expand the existing works on understanding the existence of robust classifiers to a new threat model.\n\n- Box-NNs are simple and can efficiently provide certified $\\ell_0$-robustness. Moreover, in the experiments outperform existing methods especially at large radii.\n\n- The paper is well-written, and the presentation of the different parts easy to follow.\n\nWeaknesses:\n- In practice, it seems that Box-NNs, given their simplicity, might struggle on more complex datasets e.g. of natural images like CIFAR-10. It seems, in fact, from Fig. 2 and Fig. 3 that already on MNIST clean performance is relatively low, and the drop would likely be larger compared to classifiers which don't aim at certified robustness.", "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 studies provable robustness of classifiers against $\\ell_0$-bounded adversarial attacks. First, it provides theoretical results which connect the existence of $\\ell_0$-robust classifiers and the localization property of the data distribution, building upon and extending the work of Pal et al. (2023). Moreover, the paper introduces Box-NN, a classifier which can provide by design certification on the $\\ell_0$-robustness at little computational cost compared to existing methods. In the experiments on MNIST and F-MNIST, the paper shows how to efficiently train Box-NNs, and that these often outperform existing methods in terms of certified robustness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- [Minor] While the robustness curves provide a comprehensive picture, I think it'd be helpful to additionally have (in appendix) some tables with (a subset of) the corresponding results to e.g. easily read clean performance.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IZTm7ptYVp", "reviewer": "Reviewer_RovY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper presents novel theoretical results and shows it improves over the prior work $l_0$ classifier robustness\n- The paper is well-written and gives good intuition on the theoretical results\n- The paper has similarities to Pal et. al. 2023 work on $l_2$ robustness, and extends the theoretical results for  $l_0$ robustness. I appreciate the comparison and contrasting of the results of current paper and Pal et. al. 2023 throughout the paper.\n\n Weakness:\n- The main weakness of the work is the challenge in learning classifiers that have axis-aligned decision regions. Thus, the experiments are limited to MNIST and Fashion-MNIST dataset. This limitation is clearly stated in the limitation section of the paper. \n\n\nComments:\n> Contribution 1 and Def. 2.1\n\nDefine C here.\n\n> The conditional distribution $pX|Y =k$ for each $k \\in Y$ will be denoted by $q_k$.\n\nCan you make a separate definition and discussion of class conditionals, given its importance throughout the paper\n\n>  Definition 2.1 \n\nIf $\\epsilon$  is used as $l_0$ norm, can you use a different variable here for defining localized distribution $(C, \\epsilon, \\delta)$\n\n> Theorem 2.2: “If the classes are balanced”\n\nCan you formally state what balanced is?\n\n> Theorem 2.2: regarding  $A_{k’} \\subseteq \\mathcal{X}$\n\nWhat if $\\mathcal{X} = A_{k’}$? What is C in this case?\n\n>  Section 4.2 defines optimization tricks to maximize this lower bound\n\nCan you do an ablation study to show the effect of these optimizations?", "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 technique for certification against sparse adversarial attacks. The paper shows that if a $l_0$-robust classifier exists for a data distribution, this distribution must be localized. Further, it shows that if the class conditional distributions are sufficiently separated, then it is sufficient for the existence of a robust classifier. Based on the theoretical results, the paper proposes a classifier robust against sparse adversarial attacks, called Box-NN. In the evaluation, Box-NN is shown to be better than prior works.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ptwABbd8fK", "reviewer": "Reviewer_HDkE", "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 authors make novel theoretical contributions to adversarial machine learning. Their modified definition of localization seems novel, and this notion will be useful for other researchers interested in the relationship between data distribution and the possibility of robust classification.\n2. The experiments demonstrate that the proposed method has better-certified radii. This can be considered remarkable progress in the certified defense of adversarial examples.\n\n### Weaknesses\n1. As the authors pointed out, the proposed method is not easy to train efficiently.\n2. It seems that Box-NN's experimental result for small certified radii is slightly worse than that of other methods.", "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 makes theoretical progress in the relationship between the classifier robustness against adversarial examples and the localization property of the data distribution. Specifically, the authors extend the existing work, which proved that the existence of a robust classifier against $\\ell_2$-norm bounded attack implies the concentration property of the data distribution. As a result, the authors proved a similar implication: if there exists a robust classifier against $\\ell_0$-norm bounded attack, the data distribution should be localized. Furthermore, the authors also proved that the converse is true with a stronger definition of localization. Then, the authors propose a new $\\ell_0$-adversarially robust classifier, Box-NN. From a few experiments, the authors compare the performance of Box-NN to the existing methods with $\\ell_0$-certifications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I’m interested in some practical applications of those theoretical results. If I understand correctly, Theorem 2.2 can be used to quantify the localization of the data distribution. Is it possible to quantify the localization of MNIST and Fashion MNIST data from the Box-NN classifier used in the experiment?\n2. I’m not entirely convinced that the definition of localization needs to be compared to the traditional notion of measuring concentration. If this is not necessary, consider moving this discussion to the Appendix.\n3. Can the experimental results for small certification radii (less than 5) be justified?\n4. Rather than referring to papers to describe certification procedures, create a separate section in the Appendix and add a description of the experimental details.", "broader_impact_concerns": "I don’t see a particular broader impact concern regarding this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends a recent theoretical result on certified adversarial robustness from l2 attacks to l0-bounded attacks, leading to a novel algorithm/architecture for neural classifiers that have certified robustness guarantees against l0-bounded attacks. The theoretical results are sound, non-trivial, and original; and empirical results validate the theoretical claims. Reviewers did not have much criticism in their initial review, other than empirical validation being limited to relatively simple datasets, with some theoretical concerns regarding the applicability of the method to complex datasets. The criticism has been sufficiently addressed by the authors, and all reviewers recommend accepting the paper. I agree with their recommendation, and since there are no open issues or remaining improvements, I argue for accepting the paper as is.
Decision: Accept (poster)