Improved Estimation of Concentration Under $\ell_p$-Norm Distance Metrics Using Half Spaces
Authors: Jack Prescott
Xiao Zhang
David Evans
Venue: ICLR 2021 Poster (2021)
Keywords: Adversarial Examples
Concentration of Measure
Gaussian Isoperimetric Inequality

Abstract: Concentration of measure has been argued to be the fundamental cause of adversarial vulnerability. Mahloujifar et al. (2019) presented an empirical way to measure the concentration of a data distribution using samples, and employed it to find lower bounds on intrinsic robustness for several benchmark datasets. However, it remains unclear whether these lower bounds are tight enough to provide a useful approximation for the intrinsic robustness of a dataset. To gain a deeper understanding of the concentration of measure phenomenon, we first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures and arbitrary $\ell_p$-norms ($p \geq 2$). We leverage these theoretical insights to design a method that uses half-spaces to estimate the concentration of any empirical dataset under $\ell_p$-norm distance metrics. Our proposed algorithm is more efficient than Mahloujifar et al. (2019)'s, and experiments on synthetic datasets and image benchmarks demonstrate that it is able to find much tighter intrinsic robustness bounds. These tighter estimates provide further evidence that rules out intrinsic dataset concentration as a possible explanation for the adversarial vulnerability of state-of-the-art classifiers.

Published as a conference paper at ICLR 2021
IMPROVED ESTIMATION OF CONCENTRATION UNDER lp- NORM DISTANCE METRICS USING HALF SPACES
Jack B. Prescott, Xiao Zhang and David Evans Department of Computer Science University of Virginia [jbp2jn, shawn, @vans)@virginiaa.cmmmm
ABSTRACT
Concentration of measure has been argued to be the fundamental cause of adversar- ial vulnerability. Mahloujifaar et al. (2019b) presented an empirical way to measure the concentration of data distribution using samples, and employed to find lower bounds intrinsic robustness for several benchmark datasets. However, it remains unclear whether these lower bounds are tight enough to provide a useful approxima- tion for the intrinsic robustness of dataset. To gain deeper understanding of the concentration of measure phenomenon, we first extend the Gaussian Isoperimetric Inequality non-spherical Gaussian measures and arbitrary -n-ormss (p 2 2). We leverage these theoretical insights to design a method that uses half-spaces to estimate the concentration of any empirical dataset under é,- norn distance metrics. Our proposed algorithm is more efficient than Mahloujifar et al. (2019b)'s ss and our experiments on synthetic datasets and image benchmarks demonstrate that it is able to find much tighter intrinsic robustness bounds. These tighter estimates provide further evidence that rules out intrinsic dataset concentration as a possible explanation for the adversarial vulnerability of state-of of-the-art classifiers.
INTRODUCTION
Despite achieving exceptional performance in benign settings, modern machine learning models have been shown to be highly vulnerable to inputs, known as adversarial examples, crafted with targeted but imperceptible perturbations (Szegedy et al. 2014 Goodfellow et al. 2015). This discovery has prompted a wave of research studies to propose defense mechanisms, including heuristic approaches (Papernot al.] 2016 Mądry et | [0018] /hang et al. 2019) and certifiable methods (Wong & Kolter 2018 Gowal et al. 2019 Cohen al.) 2019). Unfortunately, none of these methods can successfully produce adversariall y-robust models, even for classification tasks on toy datasets such as CIFAR- 10.
To explain the prevalence of adversarial examples, line of theoretical works (Gilmer al. 2018
Fawzi et al. 2018 Shatahi et al. 2019 Dohmatob) 2019 Bhagoji et al., 2019) have proven upper bounds the maximum achievable adversarial robustness by imposing different assumptions i
the underlying metric probability space. In particular, Mahloujifar et al. (2019a) generalized the previous results showing that adversarial examples are inevitable as long as the input distributions are concentrated with respect to the perturbation metric. Thus, the question of whether or not natural image distributions are concentrated highly relevant, as if they are it would rule out any possibility of there being adversarially robust image classifiers.
Recently, Mahloujifar al.) (2019b) proposed an empirical method measure the concentration of an arbitrary distribution using data samples, then employed it to estimate lower bound on intrinsic robustness (see Definition for its formal definition) for several image benchmarks. By demonstrating the gap between the estimated bounds of intrinsic robustness and the robustness performance achieved by the best current models, they further concluded concentration of measure is not the sole reason behind the adversarial vulnerability of existing classifiers for benchmark image distributions. However, due to the heuristic nature of the proposed algorithm, it remains elusive whether the estimates it produces robustness limits, thus hindering understanding of how much of the actual adversarial risk can be explained by the concentration of measure phenomenon.
serve useful approximations of the underlying intrinsic

---

Published as a conference paper at ICLR 2021
In this work, we address this issue by first characterizing the optimum of the actual concentration problem for general Gaussian spaces, then using our theoretical insights to develop an alternative algorithm for measuring concentration empirically that significantly improves both the accuracy and efficiency of estimates of intrinsic robustness. While we do not demonstrate a specific classifier which achieves this robustness upper bound, our results rule out inherent image distribution concentration as the reason for our current inability to find adversarially robust models.
Contributions. We generalize the Gaussian Isoperimetric Inequality to non-spherical Gaussian distributions and Ey-norm distance metrics with p 2 2 (including 6o0) (Theorem (.3)). Motivated by the optimal concentration results for special Gaussian spaces (Remark 3.4). we develop a sample- based algorithm to estimate the concentration of measure using half spaces that works for arbitrary distribution and any fy-norm distance (Section 4) Compared with prior approaches, we empirically demonstrate the sigmificant increase in efficacy of our method under -norm distance metric (Section (6) Not only does the proposed method converge to its limit with an order of magnitude fewer data (Section (..2). it also finds a much tighter lower bound of intrinsic robustness for both simulated datasets whose underlying concentration function is analytically derivable and various benchmark image datasets (Section 6. In particular, we improve the best current estimated lower bound of intrinsic robustness from approximately 82% above 93% for CIFAR-10 10 under & -nom bounded perturbations with e = 8/255. These tighter concentration estimates produced by our algorithm provide strong evidence that concentration of measure should not be considered the main cause of adversarial vulnerability, at least for the image henchmarks evaluated in our experiments.
Related Work, Several prior works have sought to empirically estimate lower bounds on intrinsic robustness using data samples. The pioneering work Gflmer et al. (2018) introduced the connection between adversarial examples and the concentration phenomenon for uniform n-spheres, then proposed a simple heuristic to find a half space that expands slowly under Euclidean distance for the MNIST dataset. Our work can be seen as a strict generalization of Gilmer et al. (2018) 's which applies to arbitrary l f--norm distance metrics (including oo By characterizing the optimal transport cost between conditional distributions, Bhagoji et al. (2019) estimated a lower bound on the best possible adversarial robustness for several image datasets. However, when applied to adversaries beyond fg, such as Ex, the lower bound produced by their method is not informative (that is, it is close to zero). The most relevant previous work is Mahloujifar et al. (2019b), which proposed a general method for measuring concentration using special collections of subsets. Although the optimal value of the considered empirical concentration problem is proven to asymptotically converge to the actual concentration, there is guarantee that the proposed searching algorithm for solving the empirical problem finds the optimum. Our approach follows the framework introduced by Mahloujifar et al. (2019b)s, s, but considers a different collection of subsets for the empirical concentration problem. This not only results in optimality for theoretical Gaussian distributions, but also significantly improves the estimation performance for typical image benchmarks.
Another line of work attempts to provide estimates of intrinsic robustness upper bounds based on generative assumptions. In order to justify the theoretically-derived impossibility results, Fawzi et al. (2018) estimated the smoothness parameters of the sfute-of-the-art generative models on CIFAR- 10 and SVHN datasets, which yield approximated upper bounds on adversarial robustness for any classifiers. Zhang et al.) (2020) generalized their results to non- smoothed data manifolds, such as datasets that can be captured by a conditional generative model. However, these methods only work for simulated generative distributions, which may deviate from the actual distributions they are intended to understand.
Notation. For any n E Z denote by [n] the set (1,2...., n). Lowercase boldface letters denote vectors and uppercase boldface letters represent matrices. For any vector and p oo), let Zy, |al|pp and [|z]|oo be the j-th element, the fy-norm and the fnom of æ. For any matrix A, B is said to be square root of A if A BB, and the induced matrix p-norm of A is defined as || = sup [I] || / Denote by A' Σ) the Gaussian distribution with mean e and covariance matrix Σ. Let Yh be the probability measure of (V I.). where I, denotes the identity matrix. Let (b-) be the cumulative distribution function of N 1) and o --1(() be its inverse. For any set AA let (A)( and (.). be all measurable subsets and the indicator function of A. Let (X uu, A) be metric probability space, where A X' X - R20 denotes distance metric on X. Define the empirical measure with respect to a sample set (ie))e(m] as (A) m Eie(m) 1zx)))
2

---

Published as a conference paper at ICLR 2021
AAA E pow(2t). Let B(x, A) fa' x:: A(=',=) S c) be the ball around æ with radius. Define the e-expansion of as A( = { xx:33 33 E e,
PRELIMINARIES
In this section, introduce the problem of measuring concentration and its connection adversarial robustness. Consider a metric probability space of instances (X' μ., A). Given parameters 2 0 and 0, the concentration of measure problem can be cast as the following optimization problem:
minimize ((E(AA) subject to p(E) 2 a.
(2.1)
&EPow(X)
We focus the case where A is some fy-norm distance metric (including (,o) in this work.
Concentration measure has been shown to be closely related to adversarial examples (Gilmer et al. 2018 Fawzi et al., 2018 Mahloujifar al.) (0T99)). In particular, one prove that for given robust learning problem, if the input distribution is concentrated with respect to the perturbation metric, no adversarially robust model exists. The concentration parameter (which corresponds the optimal value of optimization problem (2.I) determines an inherent upper bound on the maximum adversarial robustness that any model can achieve for the given problem.
To explain the connection between concentration of measure and robust learning in more formal way. we lay out the definition of adversarial risk that we work with. We draw this definition from several previous works, including Gilmer et al. (2018 8y; Bubeck et al. (2019;; Mahloujifar et al. (2019a b)
Definition 2.1 (Adversarial Risk). Let (X, μ1, A) be the input metric probability space. Assume f is the underlying ground-truth classifier that gives labels to any input. Given classifier and 2 0, the adversarial risk of f with respect e-perturbations measured by Á is defined as:
AdvRisk, (f) = Pr B B(x, A) s.t. f(x') fax)
Correspondingly, we define the adversarial robustness of f as AdvRob, (f) = AdvRisk,())
When 0, adversarial risk degenerates to standard risk. In other words, it holds for any f that AdvRisko (f) = Risk(f) (f) == Prz-,I (xx) + [=]]]. We remark that this definition assumes the existence of an underlying ground-truth labeling function, which does not apply to the agnostic setting where inputs can have non-determiiistic labels.
Initially introduced in Mahloujifar et al. (2019b), intrinsic robustness captures the maximum adver- sarial robustness that can be achieved by any imperfect classifier for robust classification problem. Definition 2.2 (Intrinsic Robustness). Consider the same setting in Definition 2. For any a >> O, let F, = ( Risk(J)= 2 a be the set of imperfect classifiers whose risk least a. Then the intrinsic robustness of the given robust classification problem with respect to Fa is defined as:
AdvRob,(Fal 11 inf (AdvRisk, (f)) sup (fd)Rob.ff). feF.
JeFu
It is worth noting that the value of AdvRob. ) is only determined by the underlying input data distribution, the perturbation set and the risk threshold parameter a, which independent of the model class one would choose for learning.
By relating the robustness of a classifier to the cexxaansion of its induced error region, the following lemma, proved in Mahloujifar et al. (2019a), establishes fundamental connection between the concentration of measure and the intrinsic robustness one can hope for robust classification problem.
Lemma 2.3, Consider the same setting as in Definition 2.2 Let (AA) (a, e) be the concentration function that captures the optimal value of the concentration of measure problem (2.1)
(A) (a, e) inf {u(E(A)) E e pow(X') and p(E) 2 a).
Then, AdvRob
((()) (a. holds for any a > and c 2 0.
1 'The standard notion of concentration of measure Talagrand 1995 corresponds the case where a 0.5. 'Other related definitions, such as the one used in most empirical works for robustness evaluation, are equivalent to this, long small perturbations preserve the ground truth. See Diochnos al. (2018) for detailed comparison of these and other definitions of adversarial robustness.
3

---

Published as a conference paper at ICLR 2021
Lemma 2.3 suggests that one characterize the intrinsic robustness limit for robust classification problem by measuring the concentration of the input data with respect to the perturbation metric.
In this paper, aim to understand and empirically estimate the intrinsic robustness limit for typical robust classification tasks by measuring concentration. is worth noting that solving the concentration problem (2.1) itself only shows the existence of an error region & whose c-expansion has certain (small) measure. This further implies the possibility of existing an optimally robust classifier (with risk at least a), whose robustness matches the intrinsic robustness limit AdvRob, However, actually finding such optimal classifier using learning algorithm might be a much more challenging task, which is beyond the scope of this work.
3 GENERALIZING THE GAUSSIAN ISOPERIMETRIC INEQUALITY
Before proceeding to introduce the proposed methodology for solving the concentration of measure problem, we first present our main theoretical results of generalizing the Gaussian Isoperimetric Inequality. This theoretical result largely motivates our method.
To begin with, we introduce the Gaussian Ispoperimetric Inequality (Sudakov & Tsirelson 1974
Borell 1975). It characterizes the optimum of the concentration problem (2.1) with respect to standard Gaussian distribution and f2-distance, where half spaces proven to be the optimal sets.
Definition 3.1 (Half Space). Let w E R" and b E R. Without loss of generality, assume ||2|||2 1. An n-dimensional half space with parameters w and b is defined as:
+ b 0)- He,b {z E R² w 20
Lemma 3.2 (Gaussian Isoperimetric Inequality). Consider the standard Gaussian space (IR" 7n) with fi-distance. Let & E (Rw( and H be half space such that Tne (8) 7' (H), then for any e 2 0, it holds that 7/n (g( 2 The (H! 4 ( (7)( +c).
The proof of the Gaussian Isoperimetric Inequality can be found in Ledoux 1996
implies the concentration function of (R", Th: || |12) is (l) = (( + c). but only applies when the underlying distribution is spherical Gaussian and the metric function is f-- distance. Thus, it only gives a concentration function for estimating the the intrinsic robustness limit in very restrictive setting. To understand the concentration of measure for more general problems, we prove the following theorem that extends the standard Gaussian Isoperimetrie Incquality (Lemma 3.2 to non-spherical Gaussian measure and general f,-norm distance metries for any 2 2.
Lemma 3.2
Theorem 3.3 (Generalized Gaussian Isoperimetric Incquality). Let v be the probability measure of (0, E), where O e R2" and Σ is positive definite matrix in R=*x", Consider the probability space (R"", v) with Ey f--norm distance, where 2 2 (including (oo). For any & E pow(RR") and 2 0,
( 2 ( (v(E)) + e///>//1
(3.1)
where 1//2 is the square root of Σ, and / denotes the induced matrix p-norm of 1122
Remark 3.4. Theorem 3.3 suggests that for general Gaussian distribution A0 Σ) and any 6p-
norm distance (p 2 2). the corresponding concentration function is lower bounded by (
c/ 112p))) Due to the NP-hardness of approximating the matrix p-norm (Hendrickx & Olshevsky 2010). it is generally hard to infer whether the equality of (3.l) can be attained not. However, for specific special Gaussian spaces, we can derive optimal subsets that achieve the lower bound. In particular, for the case where Σ I, and p > 2, the optimum is attained when & is half space with axis-aligned weight vector (that is, w =j for some j E [n)).. For the case where Σ 4 I, and 2, the optimal solution is half space Ho,, where ei is the eigenvector with respect the largest eigenvalue of Σ. The proofs of these optimality results are provided in Appendix A.2
4 EMPIRICALLY MEASURING CONCENTRATION USING HALF SPACES
Recall that the primary goal of this paper is to measure the concentration of an arbitrary distribution. However, for typical classification problems, we might not know the density function of the underlying
4

---

Published as a conference paper at ICLR 2021
distribution μu, but instead we usually have access to a finite set of instances (i)))e(m)) sampled from μs. Following Mahloujifar et al. (2019b), we consider the following empirical counterpart of the actual concentration problem 22.
minimize imm (E(A1) subject to (E) 2 ax SEG
(4.1)
where Pm is the empirical measure based (Zg)ig())) and 9 S pow(Xt) denotes a particular collec- tion of subsets. Mahloujifar et al. (2019h) proposed the complement of union of T hyperrectangles as for foo and the union of 7 balls for &2. They proved that if one increases the complexity parameter T and the sample size m together in a careful way, the optimal value of the empirical concentration problem (4.1) converges to the actual concentration asymptotically. However, it is unclear how quickly it converges and how well the proposed heuristic algorithm in Mahloujilar et al. (2019b) finds the optimum of (4.1)
In this work, we argue that the set of half spaces is a superior choice for G with respect to any f. no-m distance. Apart from achieving the optimality for certain Gaussian spaces as discussed in Remark 3.4 estimating concentration using half spaces has several other advantages including the closed-form solution of fp-distance to half-space (Lemma D.T) and its small sample complexity requirement for generalization (Theorem 4.2). To be more specific, focus the following optimization problem based on the empirical measure im and the collection of half spaces HS(m)):
minimize (im(E (m! subject to (E) 2 a, (EHS(()
(4.2)
where (n5(n) (Ho,b Rd B and ||l|| 1} is the set of all half spaces in R
The following lemma, proven in Appendix B.I characterizes the closed- form solution of the & norm distance between point and half space. Such formulation enables exact computation of the empirical measure with respect to the e-expansion of any half space.
Lemma 4.1 (lp- -isttanee to Half Space). Let H.,b E HSS(n) (n) be an n-dimensional half space. For any vector x E R", the e--norm distance (p 2 1) from to He, is:
0,
w x x 0: otherwise.
(2 Hw,,t) =
(w x + b)/l[///ll
Here, q is real number that satisfies 1/p + 1/9 =
Lemma 4.1 implies that the e-expansion of any half space with respect to the fy-norm is still a half space. Since the VC-dimensions of both the set of half spaces and its expansion are bounded, we can thus apply the generalization theorem in Mahloujifar et al. (2019b). which yields the following theorem. proved in Appendix [.2 that characterizes the generalization of concentration with respect to the collection of half spaces.
Theorem 4.2 (Generalization of Concentration of Half Spaces). Consider the metric probability space. (X, || Ipp). where X C R and p 2 1. Let {x, Hejmm) be set of instances sampled from 1u, and let fimm be the corresponding empirical measure. Define the concentration functions regarding the collection of half spaces HS(n) with respect to μ
h((()) (.S(()))
inf seHS(n)
(u(E!fo): (xE) 2 a),
and let (1 (a, HS(n)) be its empirical counterpart with respect to p. For any E (0, 1),, there exists constants co and 01 such that with probability at least Co log
(tx) (a - 5, HS(()) - 5 < 11ft) HS(n)) S (h (6)) Am
(a + 8,e, HS(n))
holds, provided that the sample size m 2 C1 n log n//6".
Remark 4.3. Theorem 4.2 suggests that for the concentration of measure problem with respect to half spaces, in order to achieve 8 estimation error with high probability, it requires O(n log(n)/5*) number of samples. Compared with Mahloujifar et al. (2019b), our method using half spaces requires fewer samples in theory to achieve the same estimation error For standard Gaussian
'The proposed estimators for for and 6g in Mahloujifar al. (2019)) require 2(x (on.Tlog(n) log())/()) samples achieve & approximation, where T' is predefined number of hyperrectangles balls.
5

---

Published as a conference paper at ICLR 2021
inputs, the empirical concentration with respect to half spaces is guaranteed to converge to the actual concentration as in 2.Ip. i.c., limm--0o h (a, e, HS(n)) hy h((²) (a,e), e); whereas for distributions that are not Gaussian, there might exist a gap. However, this gap of empirical and actual concentration is shown to be uniformly small across various data distributions, as will be discussed in Section 6.2
Based on Lemma 4.1
estimating the empirical concentration using half spaces as defined in (.2 is
equivalent to solving the following constrained optimization problem:
minimize wER" .bER
1fw T x + S <e|lw|ll
+E(m]
(4.3)
subject to
1 m
1( 2; + 03 2 a and ||0|| = Σ iE(m]
The optimal solution would be half space Ho,P that satisfies the following two properties: (I) approximately a-fraction of data is covered by Hw and (2) most of the remaining data points least e-away from Hw.b under fy-norm distance metric.
Note that can always set b to be the c--uaanile of the projections {-w" ax; ; [m]] to satisfy the first property. In addition, to satisfy the second condition, inspired by the special case optimality results in Remark 3.4 we propose search for weight vector such that both the by -norm of w is small and the variation of the given sample set along the direction of w is large. These searching criteria guarantee that the given dataset {æz; [m]] when projected onto u then normalized by || will have large variance, which implies the second property.
We propose heuristic algorithm search for the desirable half space according to the aforementioned criteria (for the pseudocode and detailed analysis of the algorithm, see Appendix C). It first conducts a principal component analysis with respect to given empirical dataset, then iterates through all the principal components raised to arbitrary power with normalization candidate choices of the weight vector w. Finally, based on the optimal choice of 6, the algorithm outputs the best H.. that achieves the smallest empirical measure with respect to the e-expansion of Hw,. As see in the experiments in the next section, this algorithm is able to find near-optimal solutions to the concentration problem for various datasets.
ERROR ANALYSIS
The goal of measuring concentration is to provide an empirical estimate of concentration of measure that minimizes the overall approximation error. Here, we describe the еттог components based on the general empirical framework for measuring concentration, and then discuss its implications on how to choose the collection of subsets G for the empirical concentration problem (4.1
Error Decomposition. Let (X' μr, A) be the underlying input metric probability space and G be the selected collection of subsets for the empirical concentration problem. Suppose an algorithm that aims to solve the empirical concentration problem (4.1) returns & as a solution. For any E (0, 1) and 2 0, the approximation error between the empirical estimate concentration and the actual concentration can be decomposed into three error terms:
1 (A) (a. c) - Pm (E(A))
(A) (a, e) - (a, e, + (A) (a, 9) - (A) (a, 9)
approximation crror
modeling ervor
finite sample estimation esror
(A)
(5.1)
optimization
The modeling error denotes the difference between the actual concentration function and the con- centration function with respect to the selected collection of subsets G; the finite sample estimation error represents the generalization gap between the empirical concentration function and its limit; and the optimization error captures how well the algorithm approximates the empirical concentration problem. Such an error decomposition applies to both the empirical method proposed in this work as well as Mahloujifar al. (2019h)'s, 's despite the different choices of G.

---

Published as a conference paper at ICLR 2021
The complexity of g and the complexity of its e-expansion G. = {E, E E 9} control the finite sample estimation error. So, 9 should be selected such that the empirical concentration function (A) (a, e, () generalizes. If either 9 or Ge is too complex (e.g.. it has unbounded VC-dimension), it will be difficult to control the generalization of the empirical concentration function (see Remark 3.4 in Mahloujifar et al. (2019b) for a detailed discussion).
There exist tradeoff's among the three error terms in (5.)) and it is unlikely that there is a uniformly good choice for G that minimizes all these error terms. In particular, increasing the complexity of g typically reduces the modeling error, since the feasible set of the concentration function with respect to & becomes larger. However, according to the generalization of concentration, this will also increase the finite sample estimation error. Therefore, we should consider the effect of all these error terms when choosing G. including the hardness of the optimization problem with respect to the empirical concentration. It is favorable that the distance to any set in 9 has closed-form solution, which enables exactly computing the empirical measure of the 6-expansion of any set in G. In addition, will be easier to control the optimization error (i.e., develop an algorithm that produces tight estimates), if the empirical concentration problem is simpler. For instance, solving the empirical concentration problem with respect to the set of half spaces should be easier than solving it based on the union of hyperrectangles or balls, since there are more hyperparameters to optimize for the latter problem. Such simplicity further contributes to a tighter empirical estimate produced by our algorithm for the underlying concentration of measure problem.
Depending on the underlying distance metric Mahloujifar et al. (2019b) set 9 as a collection of the union of complement of hyperrectangles the union of balls, whereas we choose G as the set of half spaces for any f--norm distance. In this work, we show that the set of half spaces is a superior choice of G for measuring the concentration of typical image benchmarks. Other choices of G may be preferred for different settings, but the same error decomposition and criteria will apply.
6 EXPERIMENTS
In this section, we evaluate our empirical method for estimating concentration under & -orm distance and comparing its performance to that of the method proposed by MMahlujifar et al. (2019b). We first demonstrate that the estimate produced by algorithm is very close to the actual concentration for a spherical Gaussian distribution, and that our method is able to find much tighter bounds on the best possible adversarial risk for several image benchmarks. We then compare the convergence rates, and show that our method converges with substantially less data. Note that while we only provide results for the most widely-used -no-m perturbation metric adopted in the existing adversarial examples literature, our algorithm and experiments can be applied to any other 4p norm.
6.1 ESTIMATION ACCURACY
First, we evaluate the performance of our algorithm under 250 distance metric on a generated synthetic dataset consisting of 30,000 samples from NO0, 1784). Since the proposed method follows from the analytical results of concentration of multivariate Gaussian distributions, we expect results produced by our empirical method closely approach the analytical concentration on this simulated Gaussian dataset. We initially consider the case where = 1.0 and a = 0.5 for the actual concen- tration problem, requiring that the feasible set contains at least half of the data samples, and the adversary can perturb each entry by precisely the standard deviation of the underlying distribution. Our algorithm is able to produce a half space whose e-expansion has mean empirical measure 84. 84.18% over 5 repeated trials. According to Theorem 3.3 and Remark 3.4 the optimal value of the consid- ered concentration problem 84. 83%. This implies that our method performs very well when the underlying distribution is Gaussian, while in stark contrast, the method by Mahloujifar et al. (201bb) is not able to find a region whose expansion has measure less than on the same simulated sct. In addition, consider another setting for this dataset where = 1.0 is set the same and 0.05 is set to be much smaller. Similarly, we observe that our method significantly outperforms Mahloujifar ee al. (2019b)'s 's in terms of the estimation accuracy (see Table for the detailed comparison results).
Next, we evaluate our method on several image benchmarks. We set the values of a and e to be the same in Mahloujifar al. (2019h) for the loo case. For example, we use a 0.01,
7

---

Published as a conference paper at ICLR 2021
Table 1: Comparisons between our method of estimating concentration with loe -norm distance and the method proposed by Mahloujifar et al. 2019b) for different settings, For (0, 1781) with a 0.5 and c 1.0, the previous method is unable to produce nontrivial estimate. Results for the previous method are taken directly from the original paper (except for the Gaussian results).
Test Risk (%)
Test Adv. Risk (%)
Dataset
Prev. Method
Our Method
Prev. Method
Our Method
(O0 0.5
0.05
1.0
6.21 = 0.44
5.20 + 0.16
89.75 0.80
26.37 + 0.17 84.18 + 0.11
1.0
49.98 + 0.25
0.1
1.23 = 0.12
1.22 + 0.05
3.64 + 0.30
1.35 + 0.06
0.2
1.11 = 0.10
1.24 0.05
5.89 + 0.44
1.52 + 0.06
MNIST
0.01
0.3
1.15 0.13
1.25
7.24 + 0.38
1.75 0.05
0.4
1.21 0.09
1.27=0.00
9.92 0.60
1.98 = 0.08
2/255
5.72 = 0.25
5.14
8.13 0.26
5.28 : 0.12
4/255
6.05 0.40
5.22 - 0.20
13.66 0.33
5.68 0,21
CIFAR-10
0.05
8/255
5.94 = 0.34
5.22
18.13
6,28 = 0.13
16/255
5.28 0.23
4.19
28.83 0.46
7.34 + 0.15
0.1
5.92 = 0.85
5.33
11,56 0.84
6.04 : 0.13
Fashion-MNIST
0.05
0.2
6.00 1.02
5.34
14.82 0.71
6.82 - 0.19
0.3
6.13 0.93
0.14
17.46 + 0.53
8.01 0.19
SVHI
0.05
0.01
8.83 0.30
5.23 0.09
0.09
10.17 1 0.29
5.56 1 0.08
(0.1, 0.11,.2,000 0.4, for MNIST, and a = 0.05, E (2/255, 4/255, 8/ 8/255, 16/255} for CIFAR-10 These a values were selected roughly represent the standard error of the state-of-the-art classifiers.
Table demonstrates the risk and adversarial risk with respect to the best produced subsets using both methods, computed on a separate test dataset. In our context of measuring concentration, risk refers to the empirical measure of the produced subset, while adversarial risk corresponds to the empirical measure of its é-expansion. We use a 50/50 train-test split over the whole dataset to perform our evaluation, and determine the best exponent of each principal component based on a brute-force search. Though our method is deterministic for a given pair of training and testing sets, we account for the variance of our method over different train-test splits by repeating our experiments 5 times and reporting the mean and standard deviation of the results for each (a, It is worth noting that the randomness of the previous method is derived not only from the selection of the training and test sets, but also from the inherent randomness of the employed k-means algorithm.
We observe from Table I that in every case, the estimated adversarial risk is significantly lower for our method than for the one found by Mahloujifar et al. (2019b)'s Since both methods restrict the search space to some special collection of subsets, these estimates can be viewed as valid empirical upper bounds of the actual concentration as defined in (2.1) Therefore, the fact that our results are significantly lower indicates that our algorithm is able produce estimates that much closer to the optimum of the targeted problem. In addition, when translated to adversarial robustness, these tighter estimates prove the existence of a rather robust classifie that has risk least a, which further suggests that the underlying intrinsic robustness limit of each of these image benchmarks is actually much higher than previously thought.
For example, the best classifier produced by Mahloujifar et al. (2019b) has 18.1% adversarial risk under foc perturraaatio bounded by 8/255 on CIFAR-TO. However, our results demonstrate that the adversarial risk of the best possible robust classifier can be as low as 6.3% given the same risk constraint, indicating the underlying intrinsic robustness to above 93.7%. As the intrinsic robustness limits are shown to be very close to the trivial upper bound 1 across all the settings, our results reveal that the concentration of measure phenomenon not an important factor that causes the adversarial vulnerability of existing classifiers on these image benchmarks.
Baased on the ground-trutt f and the retumed set E of our algorithm, this classifier can be simply constructed by setting f(x (xz for & E and f(x) & f (ax) for E. Without knowing the ground-truth, we note that such classifier may may not be learnable. The learnability of such is beyond the scope of this paper.
8

---

Published as a conference paper at ICLR 2021
0.4
0.4
Hotroujfar methed = 0.03
Mar
test athe risk
0.3
test adv. ria
0.3
method
Hahrouj methed
8
5
250 6000 8000 10000
250
8000
250
8000 10000
samples training
samples training set
samples training
(a) (0, I784)
(b) MNIST
(c) CIFAR-10
Figure 1: The convergence curves of the best possible adversarial risk estimated using method and the method proposed by Mahloujifar et al. (2019b) as the number of training samples grows.
6.2 CONVERGENCE
shows the convergence rate our method compared with that of the method proposed by Mahloujifar et al. (2019b) under fxx -distance for Gaussian data from from.N(0 (0, 1784) (a 0.05, 1), as well as for MNIST (a = 0.01, e = 0.1) and CIFAR-10 (a = 0.05, e 2/255). We observe similar trends for other settings, thus defer these results to Appendix D For each graph. the horizontal r-axis represents the size of the dataset used to train the estimator, and the vertical y-axis shows the concentration bounds estimated for separate test set, which is of size 30, 000 for each case. We generate the means and standard deviations for these convergence curves by repeating both methods 5 times for different andomly-selecteed training and test tests. For the proposed algorithm in Mahloujifar et al. (2019b), we tune the number of the hyperrectangles T' for the optimal performance based on the empiricalll--bberved adversarial risk.
Figure 6.2
For the simulated Gaussian datasets, we include a horizontal line at y = 0.2595 to represent the true concentration of the underlying distribution, derived from Theorem 3.3 and Remark 3.4 This allows us to more accurately assess the convergence of our method, as it is the only case for which we know the optimal value that our empirical estimates should be converging to. We see that our estimates approach this line very quickly, coming within 0.01 of the true value given only about 1,000 samples.
While we do not have such a theoretical limit for other datasets, the risk threshold a can be viewed as lower bound of the actual concentration, which is useful in visually assessing the convergence performance our method. We can see that for both MNIST and CIFAR-IO, our estimates get very close to the horizontal line at y given several thousand training samples. Since the actual concentration must be no less than a and our estimated upper bound is approaching a from the above, immediate infer that the actual concentration of these data distributions with &o -norm distance should be a value sightly greater than a. These results not only demonstrate the superiority of our method over the method of Mahloujifar al. (2019b) in estimating concentration, but also show that concentration of measure is not the reason for our inability to find adversarially robust models for these image benchmarks.
7 CONCLUSION
Our results advance understanding of the intrinsic limits of adversarial robustness, strengthening the conclusion from|Mahhen MMaloujiifa et al. (201b)) which asserted that concentration of measure is not the sole cause of the vulnerability of existing classifiers to adversarial attacks. We generalized the standard Gaussian Isoperimetric Inequality, and then leveraged theoretical insights from that to construct an efficient method for empirically estimating the concentration of arbitrary data distribution using samples. Our method is able to generalize any ly norm distance metric, and surpasses previous approaches in both estimation accuracy and data-efficiency.
AVAILABILITY
An implementation of our method, and code for reproducing our experiments, is available under an open source license from https: http://gghhha.aacaaaaapeeeeeeeee
1fpaces)

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This work was partially funded by an award from the National Science Foundation SaTC program (Center for Trustworthy Machine Learning, #1804603). We thank Saeed Mauloujifär and Mohammad Mahmoody for valuable comments and discussions.
REFERENCES
Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robustness from optimal transport. In NeurIPS, 2019.
Christer Borell. The Brunn-Minkowski inequality in Gauss space. Inventiones mathematicae, 30(2): 207-216, 1975.
Sebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning. 2019.
Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarial risk and robustness:
General definitions and implications for the uniform distribution. In NeurIPS, 2018.
Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In International Conference Machine Learning, 2019.
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. In NeurlPS, 2018.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel Schoenholz, Maithra Raghu, Martin Wattenberg, and lan Goodfellow. Adversarial spheres. arXiv: 1801:027740 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. IEEE International Conference on Computer Vision, 2019.
Julien M Hendrickx and Alex Olshevsky. Matrix p-norms are NP-hard to approximate if * 1,2, co.
SIAM Journal on Matrix Analysis and Applications, 31),,, 2010.
Michel Ledoux. Isoperimetry and Gaussian analysis. In Lectures on Probability Theory and Statistics. Springer, 1996.
Saeed Mahloujifar, Dimitrios Diochnos, and Mohammad Mahmoody. The curse concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In AAAI Conference on Artificial Intelligence, 2019a.
Saced Mahloujifar, Xiao Zhang, Mohammad Mahmoody, and David Evans. Empirically measuring concentration: Fundamental limits on intrinsic robustness. In NewrIPS, 2019b.
Aleksander Mądry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT' Press, 2018.
Nicolas Papemot, Patrick McDaniel, Xi Wu. Somesh Jha, and Ananthram Swami. Distillation defense to adversarial perturbations against deep neural networks, In IEEE Symposium on Security and Privacy, 2016.
10

---

Published as a conference paper at ICLR 2021
Mustapha Raissouli and Iqbal Jebril. Various proofs for the decrease monotonicity of the Schatten's power norm, various families of -orms and some open problems. International Journal of Open Problems in Computer Science and Mathematics, 3(2):164-774, 2010.
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In International Conference on Learning Representations, 2019.
Vladimir Sudakov and Boris Tsirelson. Extremal properties of half-spaces for spherically invariant measures. Zapiski Nauchnykh Seminarov Leningrad Otdel Mathematical Institute Steklov (LOMI), 41:14-24, 1974.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014.
Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institul des Hautes Éludes Scientifiques, 81(1):33-205, 1995.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, 2018.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, 2019.
Xiao Zhang, Jinghui Chen, Quanquan Gu, and David Evans. Understanding the intrinsic robustness of image distributions using conditional generative models. In International Conference Artificial Intelligence and Statistics (AISTATS), 2020.
A PROOFS OF MAIN RESULTS IN SECTION 3
In this section, we provide the detailed proof' of our main theoretical results presented in Section 3
A.1 PROOF OF THEOREM 3.3
Before proving Theorem 3.3
we first lay out the following lemma regarding the monotonicity of no-norms. For a rigorous proof of this lemma, see Raissouli & Jebril (2010).
Lemma A.1 (Monotonicity of f,)). For any vector æ E IR.", the mapping p - ||>||p monotonically decreasing for any 2 (including p oc). That said, ||œ=|, < ||æ||,, holds for any p 2 q 2 1.
Now, we are ready to prove Theorem 3.3 In particular, we first include a high-level proof sketch, then present the complete proof after.
Proof Sketch of Theorem 3.3 We start with the spherical Gaussian distribution where v = =in More specifically, are going to prove that for any & C R" and n 2 O,
Tin (E(())) > +( (E)) + 1)) holds for p 2 2.
(A.1)
Note that for any vector & E IR, the mapping p - | is monotonically decreasing for any p 2 1,
thus show that effx)) C Ey (lp)) holds for any p q 2 Making use of the standard Gaussian Isoperimetric Inequality (Lemmal 3.2). we then immediately obtain
In (2)(5) 2 7n (g)6a) 2 2 10-11 (7)())) + n), for any p 2 2.
Moreover, to prove the concentration bound for general case where v is the probability measure of (0, E), build connections with the spherical Gaussian case by constructing subset A { 1/2 0) x E E). Based the affine transformation of Gaussian measure, we then prove:
(E (A) and ((E(())) Z (Aff))))) where e/1l > 12
(A.2)
Finally, combining (A.1) and A.2 completes the proof of Theorem 3.3
11

---

Published as a conference paper at ICLR 2021
Complete Proof of Theorem 3.3 To begin with, we consider the special case where the underlying
distribution is standard Gaussian (v/ = %n) Specifically, we are going to prove that for any & = IR" and 7) 2 0,
Yn (n( 2 $ ( ( + +1) holds for any p 2
(A.3)
Let p 2 According the definition of e-expansion of subset and Lemma A.1
we have
E(4,) = {a E R" 3 E E s.t. || - x|11 S n)
E 3 E & s.t. || - æ11p n7 E)(=)
(A.4)
where the inclusion is due to the fact that || ælIp S ||ar æz11 holds for any x' and æ. Therefore, by setting 2 in A.4). we further obtain that for any p 2 2,
The (e((e 2 7he (E
(
(7) +c),
where the second inequality is due the standard Gaussian Isoperimetric Inequality (Lemma 3.2 Thus, we have proven (A.3)
proving the concentration bound for the general Gaussian case. Let UAUT be the eigenvalue decomposition of Σ, where U E RR is an orthonormal matrix and A E Raxx is a diagonal matrix consisting of all the eigenvalues. Since E is positive definite, the square root of E can be expressed 11/2 UA Let Σ 1/2 TEA-1/2U" be the inverse matrix of 1//
Now
Construct subset A in RD such that A = Σ ( 0) E E}. Based on the construction of A, we can then prove the following results for any & C TR and 2
v(E) (.( and v(E((o)) 2 in (A(4 where //1
(A.5)
First, we prove the equality v v(E) (A). Since is the probability measure of N (0, E), we have
v( = Pr x E 8| Φ~~v æーE
Pr > 1/2 (x 0) E A] = Pr Iu E A] = (A(()) unann
(A.6)
where the third inequality is due to the affine transformation of Gaussian random variables.
Next, we prove the remaining inequality in A.5 By definition, for any u' E <A()), there exists E A such that ||aa u/Ip S 27. Let xr'
Σ 1/2 and = 0 11/2u, then we have
| æ1| = || | 1/2 -2)1, < Σ // ||
1)11,
ullp < 7/ E /311 Se.
(A.7)
where the first inequality is due to the definition of induced matrix p-norm and the last inequality holds because 17 1 | |/// p| By the construction of A and the fact that a E A, we have x E
Combining (..7) this further implies that for any u' E AA! 0 //2 c(6p) Thus, we have
(Ep)
v(E 2 v00 12
A/ (6)
Σ MEV
Pr
1/2 x
0) A!fo = 7 (A)))
(A.8)
/2 u: u Alf Therefore, based where 0 ++3 1/2 A denotes the transformed subset (0 + Σ 12 on (A.6) and (A.8) we prove the soundness of (A.5).
Finally, combining (A.3 and A.5 completes the proof of Theorem 3.3
A.2 PROOF OF THE OPTIMALITY RESULTS IN REMARK 3.4
Proof. First, we prove the optimality for the spherical Gaussian case, where v = The and > 2. Let H Hur, & be a half space with exis-aligned weight vector, that said w e, for some j [n]. Intuitively speaking, the c-expansion of H with respect to f--norm will only happen along the j-th dimension. More rigorously, we are going to prove the following results: for any e 0.
H
H((a) holds for any p 2 1.
(A.9)
By definition, H. = fx E R. : x, + b S 0}. For any x & H. let 2 E H be the closest point of x in terms of nn-norm. Since the weight vector of H is axis-aligned, thus T will only differ from by
12

---

Published as a conference paper at ICLR 2021
the j-th element. That said, T.r 2n for any j' and 23 = -. Thus for any p 2 have x -1Ip 2112 = Ij + b. Based on this observation, we further obtain that for any p 2 1,
H( {a R" 2j + b - k1
which proves
A.9
According to the Gaussian Isoperimetric Inequality (Lemma 3.2 we obtain
Toe (H! 7me (H!! 4 ( (?n))))) e).
Therefore, combining this with Theorem 3.3 we prove the optimality for the spherical Gaussian case.
Now we turn to prove the non-spherical Gaussian case with p p= 2. Based on Theorem 3.3 the lower bound $($
</||////1l2) when p = In the following, we are going to prove: if choose & = Ho,,b, b. where v1 is the eigenvector with respect to the largest eigenvalue of Σ, this lower bound is attained. Similarly to the proof of Theorem 3.3 we construct A 1/11/2(x 0)
E}.
Note that when is half space, the constructed set A also half space. In particular, for the case where & = Her for any u A, there exists an æ E R" such that u = Σ 22-1/2(a 0) and oi x < 0. This implies that v / + o 0 + - 0 for any u E A. Since 21 is the eigenvector of Σ, we further have that A is a half space with weight vector // = |/ 2z.
Note that according to (A.2). as in the proof of Theorem 3.3 for any & C IR" we have
v(E) = (A) and v(E!(t)) 2 Yn (Alf.)) where 7) = e/ Σ 1|2. For & _Ho,, based the explicit formulation of fz-distance half space, we can explicitly compute the fe-expansion of A as
Alaa {u R" 0 1/ 0j 4b 1
When we set - 1//2 22
1|2 further implies that
Nn (A(aa)
Pr -m
u 1/ /2 +
Pr Ewv
[0] b (
Finally, according to the optimality of the standard Gaussian Isoperimetric Inequality (Lemma 3.2) this completes the proof.
B PROOFS OF THEORETICAL RESULTS IN SECTION
In this section, we present the proofs to the theoretical results presented Scction 4
B.1 PROOF OF LEMMA
Proof of Lemma 4.1 trivially holds if w + b < 0. The problem of finding the fy-distance from given point æ to a half space Ho.b can be formulated as the following constrained optimization problem:
We only consider the case when w x + b>> 0, because (x, H.,,) is zero
min || x elpp.
subject to w" + S.
(B.1)
Let = z - x. then optimization problem B.
is equivalent to
min
subject to w To = w + + 0.
(B.2)
pr
ZER
According to Hölder's Inequality, for any R.th we have
-I
|| < w < w l1,
||
where 1/p + 1/q 1. Therefore, for any that satisfies the constraint B.2 we have
w T
||
(B.3)
Since |/m || 1, we have ||m||l > thus B. further suggests || > (w b)/ll/lll
13

---

Published as a conference paper at ICLR 2021
Up till now, have proven that the optimal value of (B.1 is lower bounded by (wTa x b)/ 10/lluu ///l|//) | The remaining task is to show this lower bound can be achieved. To this end, we construct as
T x +
1/p
2/ = 2j
for any j E [rd].
(e(n)) w/
where 1/p + +/4 1. We remark that for the extreme case where p oc, such choice of 2 can (w x + b) agm(w)/llw) where sgn(-) denotes the sign function for
be simplified as 2 vectors. According to the construction, can be verified that
x b
(5
w
1/D
w 2 b (wTx Ju b)
w 4
Σ w JE(m]
EEyela)
w/
0,
and [ 20 = (w T x. + b)/l|
B.2 PROOF OF THEOREM
Proof of Theorem 4.2 We write HS as HD((n) for simplicity. Let be a set of size m sampled from and Ag be the corresponding empirical measure. Note that the VC-dimension of HS(n) is n + (see Mohri et al. 2018), thus according to the VC inequality, we have
Pr sup (EHS(m)
(is(E) - m(E) 8] 8e(n+11 log())))) 1) /32
Stpm
In addition, according to Lemma we can directly apply Theorem 3.3 Mahloujifar et al. (2019b) to bound the generalization of concentration with respect to half spaces: for any d E (0, 1), we have
4.1 the c-expansion of any half space is still half space. Therefore,
11 (1p) (a 8,6, HS) 8 s 11(f)) (ax e, HS) h (fp)
Pr S Stp
(a 8, HS) +
us
32c (n+1) (2 (og(m++ 1)- /32
Finally, assuming the sample size 2 co n log n/22 for some constant co large enough, then there exists positive constant 6j such that
(Ep) (a e, HS) ó h1 ((ft) HS) 1 ps
(6)) (a o, HS) +
holds with probability at least Ci nlggn
C ALGORITHM FOR ESTIMATING CONCENTRATION
Algorithm 1: Heuristic Search for Robust Half Space under Ep -p-distance
Input set of samples {æ; [i{m): strength (in fp-norm); risk threshold o;; #iterations S.
Q compute the sample covariance matrix based on {x, )ejmm):
obtain the set of principal components by eigenvalue decomposition on Q:
for u E do
for s = ........ do
select from (xpow(u,s))
// pow() is defined according to C.I
b q-qunntiee the set f-w x; : [m]]:
AdvRisk (Hw,)) + Em 1ww x; + < w //;
end end
(w, b) + wrgmin (..)) AdvRisk, (Hw.b);
Output: Ha.
14

---

Published as a conference paper at ICLR 2021
0.9
0.100
0.7
0.6
0.075
0.5
ade
0.050
2 0.3
0.2
Our methed
0.025
0.1
Our miched
0.01
2000
6ODO 800O samples training set
0.000
2000
6000
8000 10000
0.00
2000 4000 6000 8000
samples training
semples in training
(a) (0, I784)
(b) MNIST
(c) CIFAR-10
Figure 2: The convergence curves of the best possible adversarial risk estimated using method under various settings as the sample size of the training dataset increases.
To solve the empirical concentration problem 4.33
Algorithm searches for desirable half space based on the principal components of the empirical dataset and their rotations defined by a power parameter. More specifically, the function pow( () takes vector E Rn and a positive integer E Z+, and returns the normalized s-th power of v (with sign preserved):
pw, s) sgn(v) [[bbs""""//l>>"]] {
///1,
if 8 is odd; otherwise.
(C.1)
sgn(v) v² /||0=112.
Note that all the functions used in (C.I) are element-wise operations for vectors, where sgn(v), abs(v), v" represent the sign, absolute value and the s-th power of v respectively, and the operator denotes the Hardamard product of two vectors.
Connected with the theoretical optimum regarding Gaussian spaces in Remark 3.4 the top principal component corresponds to the optimal choice of w if the perturbation metric is Eg-distance, whereas close-to-axis would be favourable for w when > 2. In addition, as implied by the empirical concentration problem (4.3) and the monotonicity of éy-mapping (Lemma A. 1), the value of ||/]|, will be more influential in affecting the e-expansion of half space grows larger. For example, the go -norm w can be as large as /n for the worst case (n denotes the input dimension), while ||w cl 1 if w aligns any axis. By searching through the region between each principal component and the closest axis, the proposed algorithm aims to find the optimal balance hetween ||wl|l and the variance of the given data along w that leads to the smallest e-xxpansion. Although there is theoretical guarantee that our algorithm will find the optimum to (4.3) for an arbitrary dataset, we empirically show (in Section 6) its efficacy in estimating concentration across various datasets.
Moreover, our algorithm is efficient in terms of both time and space complexities. Precomputing the principal components requires O(mn² + n²) time and O(n²) space store them, where m denotes the samples size and n is the input dimension. For each iteration step, the time complexity of computing w, and AdvRisk, (Hw.b) is (mm)). while the space complexity for saving the intermediate variables and the best parameters is O(m + n). With n outer iterations and S inner iterations, the total time complexity is (n3 + mn? The total space complexity is O( + mn). where the extra Om)) denotes the initial space requirement for saving all the input data. For our experiments, we observe AdvRisk, (Ho,,)) b) is not sensitive to small increment of the exponent parameter s, thus we choose to increase in more aggressive way, which further saves computation.
D ADDITIONAL EXPERIMENTS
Figure 2 shows the convergence performance of our algorithm under different experimental settings: a = 0.5. = 1 for the simulated Gaussian dataset, & = 0.01, e 0.4 for MNIST, and a = 0.05. 16/255 for CIFAR-10. Under these additional settings. the algorithm proposed by Mahloujifar et al. (2019b) either cannot provide meaningful estimates of concentration, or takes a substantial amount of time run. For instance, our algorithm takes around 2 days generate the convergence curve on CIFAR- (a 0.05, 16/255), whereas the previous method is at least 5 times slower, due the large number of rectangles I needed. Thus, we only report the convergence curves of our method, where the standard deviations are calculated over 3 repeated trials.
15


Reviews:
[{"review_id": "w96sBUsvDLO", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "$\\{\\\\bf \\{Problem\\~ setting\\~ and\\~ summary\\~ of\\~ results\\}\\}$:\n\nThis paper gives a theoretical analysis on the fundamental limits of adversarial robustness under general $\\\\ell_{p}$-norm attacks. It basically builds upon a series of recent  works, mainly by Mahloujifar et al. (2019a and 2019b), which establish a fundamental relation between the  concentration function of input distribution, denoted by  $h^{\\\\left(\\\\ell_p\\\\right)}_{\\\\mu}\\\\left(\\\\epsilon,\\\\alpha\\\\right)$, and its intrinsic robustness, i.e., maximum possible adversarial robustness for any model class in a robust learning problem. The paper's main contribution is to propose a new way for approximating the empirical value of $h^\\{\\\\left(\\\\ell_p\\\\right)\\}_\\{\\\\mu\\}\\\\left(\\\\epsilon,\\\\alpha\\\\right)$ for a given input dataset of $m$ samples. Approximation is based on replacing the true input measure by its empirical version, and also limiting the error regions in Eq. (2.1) by a more manageable class (in this work: Half-spaces). In this regard, authors have investigated the two following issues: 1) consistency of the approximation and corresponding generalization bounds, and 2) tightness of the final bounds on intrinsic robustness.\n\n$\\{\\\\bf \\{On\\~the\\~generalization\\~aspect\\}\\}$: Authors have shown that estimating the concentration function $h^{\\\\left(\\\\ell_p\\\\right)}_{\\\\mu}\\\\left(\\\\epsilon,\\\\alpha\\\\right)$, for any $p\\\\in\\\\left(1,\\\\infty\\\\right\\]$, through minimizing over the set of all half-spaces converges to its statistical value (i.e., when $m\\\\rightarrow\\\\infty$). The corresponding generalization bounds are given in Theorem 4.2, where a sample complexity similar to that of Mahloujifar et al., 2019, has been derived (authors claim that sample complexity has been improved w.r.t. prior works). Also, it should be noted that based on authors' claims in p.5, Mahloujifar et al. have only considered $\\\\ell_2$ and $\\\\ell_{\\\\infty}$-bounded attacks in their work while in this work $p$ is not restricted. Also, paper claims that the new proposed method converges to the optimal solution faster than previous works, however, no theoretical guarantees are given for this claim.\n\n$\\{\\\\bf \\{On\\~the\\~tightness\\~aspect\\}\\}$: Paper shows that when input data distribution is set to $\\\\mathcal{N}\\\\left(\\\\boldsymbol\\{\\\\theta\\},\\\\boldsymbol\\{\\\\Sigma\\}\\\\right)$, the concentration function becomes optimal and bounds are tight, if\n\na) $\\\\boldsymbol\\{\\\\Sigma\\}=\\\\boldsymbol\\{I\\}_n$ and $p>2$, or\n\nb) $\\\\boldsymbol\\{\\\\Sigma\\}\\\\neq\\\\boldsymbol\\{I\\}_n$ and $p=2$.\n\nFor other cases, a novel and interesting bound is given (by extending the Gaussian Isoperimetric Inequality to $\\\\ell_p$ norms). However, achievability of bounds in these cases are not guaranteed in this paper.\n\n------------------------------------------------------------------------------------------------------------------------------\n\n$\\{\\\\bf \\{Comments\\}\\}$:\n\nPaper is very well-motivated and fairly well-written. Mathematical notations are carefully crafted and results seem to be solid and understandable (I have not checked all of the proofs in Appendix). However, the contribution of the paper on the generalization aspect of the problem looks incremental and is similar to the prior works by Mahloujifar et al. (2019), however, in a relatively different setting. The main additions and improvements in this part are mostly heuristic and are backed solely through experiments.\nThe only exception is the sample complexity bound given in Theorem 4.2, where authors claim a substantial improvement has happened. However, this part need more explanation: How large parameter $T$ needs to be in (Mahloujifar et al., 2019) to guarantee the same error bound as this work? If $T$ is $O\\\\left(1\\\\right)$ w.r.t. dimension $n$, then I cannot see any considerable improvement (at least order-wise).\n\nOn the tightness issue, results are more novel and promising (in particular, Lemma 3.2). Again, the lack of theoretical guarantee for the achievability of Eq. (3.1) for the majority of cases has hampered the significance of the results in this part.\n\nOverall, I believe this paper could potentially make a breakthrough if authors can provide further solid theoretical guarantees for any of the above issues. Still, I think the paper is publishable even in its current form.", "extra_scores": {}, "extra_text": {}}, {"review_id": "h1sSzrlJWlN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper considers the estimation of the concentration of measures, which possibly causes of the vulnerability of machine learning models to adversarial attacks. Towards such a goal, the authors first extend the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures and arbitrary l_p norm. An algorithm that uses half-spaces as feasible set in the concentration of measure problem is then proposed. Empirical studies are conducted to show the efficiency as well as the efficacy of the proposed method when compared to [Mahloujifar et al. (2019b)].\n\nComment:\nThe paper is overall well written and the presentation is clear. While I am not an expert in this domain, I can easily follow the paper and understand the problem. While I cannot judge the novelty of Theorem 3.3, I very much appreciate Remark 3.4 which describes the limitations of Theorem 3.3 and clarifies the implication of such a result in several important special cases. In terms of the algorithm design, the choice of half spaces as feasible set in the concentration of measure problem seems natural given Lemma 3.2/Theorem 3.3 and is amenable to the generalization analysis. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "VAJBSvhT0pY", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The authors consider the problem of estimating intrinsic robustness using data samples. At a high level, intrinsic robustness is a measure that indicates the probability that a noisy version of a covariate would not be mislabeled. Mahloujifar et al. (2019a) have shown that estimating intrinsic robustness is closely related to the problem of estimating the concentration of measure. This problem focuses on finding a region such that it has the least likely epsilon neighborhood. In this work, the authors provide an efficient algorithm for measuring concentration empirically, which yields a more accurate estimation of the intrinsic robustness compared to the previous results.  \nOne of the key technical components was generalizing the Gaussian Isoperimetric Inequality to non-spherical gaussian distributions (with distance metric being ell_p for p >2). This result leads to an optimal concentration result for special gaussian spaces. \nAnother utilized technique was using half spaces to estimate the intrinsic robustness. Basically, for estimating the intrinsic robustness, instead of solving an optimization problem over all possible regions, they only consider half-space regions. This approach yields a new formulation of the problem in the form of a linear program which can be solved efficiently.\nIn the end, the authors provide an empirical evaluation of their results.\n\nOverall evaluation: The authors consider an important problem (understanding the robustness of a set of classifiers) from an interesting angle. The paper has substantial theoretical contributions that are empirically evaluated as well. The paper seems well-written. \n\nQuestion: What is the main advantage of half-spaces (compared to hyperrectangles or balls), which results in a more efficient algorithm? Where does the improvement come from the generalization part (bounded VC-dimension of the extensions)? Or is it because using half-spaces, the problem can be nicely stated as an LP? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-4FEQtjybFl", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review\nThe authors generalized the Gaussian Isoperimetric Inequality to non-spherical Gaussian measures with $\\ell_p$ metric structures $p\\geq 2$. Building on the generalized inequality, they propose a sample-based algorithm to estimate the concentration of measure using half-spaces. The main contribution is Theorem 3.3 followed by the empirical sample based algorithm for half-spaces that requires $\\Omega(n\\log(n) /\\delta^2)$ samples.\n\n\n#### Reason for score\nOverall, I vote for weak accept. The paper is very well written and it was a pleasure to go through it. Since I am not an expert in this research area, I have a low confidence in my decision. I would like to share a few minor concerns below to the authors that could improve further their submission.\n\n#### Strong points:\n- Paper is very well written and it was easy to go through the main contributions.\n- A lot of effort is put in having a consistent,clear notation and formalism.\n\n#### Minor Concerns\n- I would expect that Theorem 3.3 to be already known in the literature, since Lemma 3.2 and Gaussian stability could probably derive such a result. At least, I believe that there might be tools that could make the proof of Theorem 3.3 shorter ( I had a quick look at it).\n- Theorem 4.2: Why is this theorem stronger than the Mahloujifar et al. 2019? Both require $O(n\\log(n) / \\delta)$ samples but in footnote 3 you mention a parameter T. Is T a constant?\n- I would suggest to move your algorithm from the appendix to the main text.\n- Please make the argument stronger in the text on why \"concentration of measure is not the main reason for the adversarial vulnerability of classifiers\". Is this a definite conclusion?\n \n#### Minor comments\n- Abstract: Please rephrase the last sentence. \"is not the main reason\" could be rephrased.\n- Sentence before \"Contribution\" : fix \"to date to find\"\n- Why 8/255 in contribution? It looks like a magic number here.\n- Notation: introduce square root of a matrix here.\n- Notation: $\\Delta$ mention that is a metric.\n- Lemma 2.3 looks likea direct consequence of Defn. 2.1. Do you really need it?\n- Defn. 3.1: do you need to define halfspaces? You can simply put it in text.\n- All sets related should be measurable, i.e., Lemma 3.2, to avoid pathological cases.\n- Theorem 4.2: is it true for $p\\geq 1$ or $p\\geq 2$?\n- Footnote 3: Is T a constant or not? Please be specific. It is important since it compares with Theorem 4.2.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: High-quality theoretical paper that studies the connection between concentration of the data distribution and adversarial robustness. It contributes a method for more accurate estimation of concentration, which allows drawing stronger conclusions about adversarial robustness compared to previous work. The paper is highly technical, but written clearly and precisely. All reviewers give positive scores, with only minor negative comments.

One minor concern I have is that the potential audience of the paper might be small, given its highly technical nature and very specialized line of research it follows. Still, I believe it's a solid contribution, so I'm happy to recommend acceptance.
Decision: Accept (Poster)