Consistent Non-Parametric Methods for Maximizing Robustness
Authors: Robi Bhattacharjee
Kamalika Chaudhuri
Venue: NeurIPS 2021 Poster (2021)
Keywords: non-parametric classifiers
adversarial examples
robustness
large sample limit

Abstract: Learning classifiers that are robust to adversarial examples has received a great deal of recent attention. A major drawback of the standard robust learning framework is the imposition of an artificial robustness radius $r$ that applies to all inputs, and ignores the fact that data may be highly heterogeneous. In particular, it is plausible that robustness regions should be larger in some regions of data, and smaller in other. In this paper, we address this limitation by proposing a new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier outside its support by using the label of the closest in-support point. We then argue that this classifier maximizes the size of its robustness regions subject to the constraint of having accuracy equal to the Bayes optimal. We then present sufficient conditions under which general non-parametric methods that can be represented as weight functions converge towards this limit object, and show that both nearest neighbors and kernel classifiers (under certain assumptions) suffice.

Consistent Non-Parametric Methods for Maximizing Robustness
Robi Bhattacharjee University of California San Diego rcbhattaßeng. ucsd. edu
Kamalika Chaudhuri University of California San Diego
kamalika@eng ucsd. edu
Abstract
Learning classifiers that are robust to adversarial examples has received great deal recent attention. A major drawback of the standard robust learning framework is there is an artificial robustness radius that applies to all inputs. This ignores the fact that data may be highly heterogeneous, in which case is plausible that robustness regions should be larger in some regions of data, and smaller in others. In this paper, we address this limitation by proposing new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier outside its support by using the label of the closest in-support point. We then argue that this classifier maximizes the size of its robustness regions subject the constraint of having accuracy equal to the Bayes optimal. We then present sufficient conditions under which general non- non-parametric methods that can be represented weight functions converge towards this limit, and show that both nearest neighbors and kernel classifiers satisfy them under certain conditions.
Introduction
Adversarially robust classification, that has been of much recent interest, is typically formulated as follows. We are given data drawn from an underlying distribution D, a metric d, as well as a pre-specified robustness radius r. We say that classifier is r-robust at input it predicts the same label on a ball of radius r around æ. Our goal in robust classification is to find a classifier e that maximizes astuteness, which is defined as accuracy on those examples where is also r-robust.
While this formulation has inspired a great deal of recent work, both theoretical and empirical [5, 17, 19, 20, 26, 15, 18. 21, 22, 23, 30], major limitation is that enforcing pre-specified robustness radius r may lead to sub-optimal accuracy and robustness. To see this, consider what would be an ideally robust classifier the example in Figure 1. For simplicity, suppose that we know the data distribution. In this case, classifier that has an uniformly large robustness radius will misclassify some points from the blue cluster on the left, leading to lower accuracy. This is illustrated in panel (a), in which large robustness radius leads to intersecting robustness regions, On the other hand, in panel (b), the blue cluster on the right is highly separated from the red cluster, and could be accurately classified with a high margin. But this will not happen if the robustness radius is set small enough to avoid the problems posed in panel (a). Thus, enforcing fixed robustness radius that applics to the entire dataset may lead to lower accuracy and lower robustness.
In this work, we propose an alternative formulation of robust classification that ensures that in the large sample limit, there is no wwwnsttess-accuracce trade off, and that regions of space with higher separation are classified more robustly. An extra advantage is that our formulation is achievable by existing methods. In particular, we show that two very common non-parametric algorithms - nearest neighbors and kernel classifiers achieve these properties in the large sample limit.
Our formulation is built on the notion of new large-sample limit. In the standard statistical learning framework, the harge-sample ideal is the Bayes optimal classifier that maximizes accuracy on the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

11
(a) Large robustness radii
(b) Small robustness radii
Figure 1: A data distribution demonstrating the difficulties with fixed radius balls for robustness regions. The red represents negatively labeled points, and the blue positive. If the robustness radius is set too large (panel (a)), then the regions of A and B intersect leading to a loss of accuracy. If the radius is set too small (panel (b)), this leads loss of robustness at point C where in principle should be possible to defend against larger amount of adversarial attacks.
data distribution, and is undefined outside. Since this is not always robust with radius r, prior work introduces the notion of r-optimal classifier [31] that maximizes accuracy on points where it is also r-robust. However, this classifier also suffers from the same challenges as the example in Figure
We depart from both by introducing a new limit that we call the neighborhood preserving Bayes optimal classifier, described as follows. Given an input that lies in the support of the data distribution D, it predicts the same label as the Bayes optimal. On an r outside the support, it outputs the prediction of the Bayes Optimal on the nearest neighbor of x within the support of D. The first property ensures that there is no loss of accuracy since it always agrees with the Bayes Optimal within the data distribution. The second ensures higher robustness in regions that are better separated. Our goal is now to design classifiers that converge to the neighborhood preserving Bayes optimal in the large sample limit; this ensures that with enough data, the classifier will have accuracy approaching that of the Bayes optimal, as well higher robustness where possible without sacrificing accuracy.
We next investigate how design classifiers with this convergence property. Our starting point is classical statistical theory [25] that shows that class of methods known as weight functions will converge to Bayes optimal in the large sample limit provided certain conditions hold; these include k-nearest neighbors under certain conditions on & and n. certain kinds of decision trees as well as kernel classifiers. Through an analysis of weight functions, we next establish precise conditions under which they converge to the neighborhood preserving Bayes optimal in the large sample limit. As expected, these are stronger than standard convergence to the Bayes optimal. In the large sample limit, we show that k, -earest neighbors converge to the neighborhood preserving Bayes optimal provided k2 = w(og nt), and kernel classifiers converge to the neighborhood preserving Bayes optimal provided certain technical conditions (such as the bandwidth shrinking sufficiently slowly). By contrast, certain types of histograms do not converge to the neighborhood preserving Bayes optimal, even if they do converge the Bayes optimal. We round these off with a lower bound that shows that for nearest neighbor, the condition that k, = w(log n) is tight. In particular, for k, = (log n), there exist distributions for which k, nearest neighbors provably fails converge towards the neighborhood preserving Bayes optimal (despite converging towards the standard Bayes optimal).
In summary, the contributions of the paper are as follows. First, we propose a new large sample limit the neighborhood preserving Bayes optimal and a new formulation for robust classification. We then establish conditions under which weight functions, a class of non-parametric methods, converge to the neighborhood preserving Bayes optimal in the large sample limit. Using these conditions, we show that k nearest neighbors satisfy these conditions when k, = wlog n)), and kernel classifiers satisfy these conditions provided the kernel function K has faster than polynomial decay, and the bandwidth parameter h,, decreases sufficiently slowly.
To complement these results, we also include negative examples of non-parametric classifiers that do not converge. We provide an example where histograms do not converge to the neighborhood preserving Bayes optimal with increasing n. We also show lower bound for nearest neighbors, indi-

---

cating that k, = (log n.) is both necessary and sufficient for convergence towards the neighborhood preserving Bayes optimal.
Our results indicate that the neighborhood preserving Bayes optimal formulation shows promise and has some interesting theoretical properties. We leave open the question of coming up with other alternative formulations that can better balance both robustness and accuracy for all kinds of data distributions, as well as are achievable algorithmically. We believe that addressing this would greatl help address the challenges in adversarial robustness.
Preliminaries
We consider binary classification over R x (=1]. and let p denote any distance metric on Rd We let j denote the measure over RRdd corresponding to the probability distribution over which instances E Rd are drawn. Each instance is then labeled as +1 with probability nnz) and -1 with probability 1 - nyx).. Together, and comprise our data distribution D = (14, 77) over I&d x {+1).
For comparison to the robust case, for classifier f IRd + {+1} and a distribution D over R x (#1), it will be instructive consider its accuracy, denoted D), which is defined as the fraction of examples from D that f labels correctly, Accuracy is maximized by the Bayes Optimal classifier: which we denote by g- It can be shown that for any supp(u), g(x) if ()x))
and g = -1 otherwise.
Our goal is to build classifiers Rd -> {+1] that are both accurate and robust to small perturbations. For any example x, perturbations to it are constrained to taking place in the robustness region of x, denoted Ug. We will let {U2 x R2) denote the collections of all robustness regions.
We say that a classifier f Rd + { is robust at x if for all x' E Uz f(x') f()). Combining robustness and accuracy, we say that classifier is astute at a point x if it is both accurate and robust. Formally, have the following definition.
Definition 1. A classifier f: Idd + {+1} is said to be astute at (x. with respect to robustness collection U if f(x)
and f is robust at a with respect to U. Df is a data distribution over Id x {+1]. the astuteness of f over D with respect to U, denoted Au(f,D) is the fraction of examples (x. ~ D for which f is astute at (x. y) with respect U. Thus
Aulf, D) = P(sa)) = y. Vxl E Uz].
Non- Non-parametric Classifiers We now briefly review several kinds of non-parametric classifiers that we will consider throughout this paper. We begin with weight functions, which are a general class of non-parametric algorithms that encompass many classic algorithms, including nearest neighbors and kernel classifiers.
Weight functions are built from training sets, S = {(11, V1), (I'2, V2. ..... (Zn: }n)} by assigning a function usς Rd > [0, 1] that essentially scores how relevant the training point (I4, y:) is to the example being classified. The functions wz are allowed depend on æ1,... Ty, but must be independent of the labels ......, Bn. Given these functions, point æ is classified by just checking whether Σ y (x) 2 0 or not. it is nonnegative, we output +1 and otherwise -1. complete description of weight functions is included in the appendix.
Next, we enumerate several common parmmtrtit classifiers that be construed as weight functions. Details can be found in the appendix.
Histogram classifiers partition the domain Rd into cells recursively by splitting cells that contain sufficienlly large number of points z,. This corresponds to a weight function in which ws (a) = b 4; is in the same cell as x, where k; denotes the number of points in the cell containing x.
1
ky nearest neighbors corresponds to weight function in which / (z) nearest neighbors of x, and w (x)) otherwise.
1. if Ir is one of the kp k,,
SernaltSimilarity classifiers are weight functions built from a kernel function K R2o + Rzo and a window size (ha)) such that wx(()) x K(p(z,x;)) x:)/ (we normalize by dividing by E K ((p(z, 2.)/),))))
3

---

Figure 2: The decision boundary of the neighborhood preserving Bayes optimal classifier is shown in green, and the neighborhood preserving robust region of shown in pink. The former consists of points equidistant from n² : and the latter consists of points equidistant from n=t
The Neighborhood preserving Bayes optimal classifier
Robust classification is typically studied by setting the robustness regions, 4 = {Ug hnERs, to be balls of radius r' centered at z, U2 {z' p(z,z') x²) r). The quantity is the robustness radius, and is typically set by the practitioner (before any training has occurred).
This method has limitation with regards to trade-offs between accuracy and robustness. To increase the margin or robustness, we must have a large robustness radius (thus allowing us to defend from larger adversarial attacks). However, with large robustness radii, this come cost of accuracy, as it is not possible to robustly give different labels to points with intersecting robustness regions.
For an illustration, consider Figure 1. Here we consider data distribution D = (Ju, 17) in which the blue regions denote all points with 1y(x)) > 0.5 (and thus should be labeled +), and the red regions denote all points with (2) < 0.5 (and thus should be labeled -). Observe that it is not possible to be simultancously accurate and robust at points A, B while enforcing a large robustness radius, as demonstrated by the intersecting balls. While this can be resolved by using smaller radius, this results in losing out on potential robustness at point C. In principal, we should be able to afford a large margin of robustness about C due to its relatively far distance from the red regions.
Motivated by this issue, we seek to find a formalism for robustness that allows us to simultaneously avoid paying for any cecuracy-oouustness trade-offs and adaptively size robustness regions (thus allowing us to defend against a larger range of adversarial attacks at points that are located more homogenous zones of the distribution support). To approach this, we will first provide an ideal limit object: a classifier that has the same accuracy as the Bayes optimal (thus meeting our first criteria) that has good robustness properties. We call this the the neighborhood preserving Bayes optimal classifier, defined as follows.
Definition 2. Ler D (n)))) be distribution over Rdd {+1}. Then the neighborhood preserving Bayes optimal classifier of D. denoted Ineighbors is the classifier defined as follows. Let 1u
{x : 17(x) 2 } and μ = fx 17(xx) }) Then for any x Rdd. Ineighhor (x) +1 if p(x, p+) S p(x,, 11 and gneighbor
otherwise.
This classifier can be thought of as the most robust classifier that matches the accuracy of the Bayes optimal. We call it neighborhood preserving because it extends the Bayes optimal classifier into local neighborhood about every point the support. For an illustration, refer to Figure 2, which plots the decision boundary of the neighborhood preserving Bayes optimal for example distribution.
Next, we turn our attention towards measuring its robustness, which must be done with respect to some set of robustness regions 2 = {U²}, J. While these regions Ug can be nearly arbitrary, we seek regions U, such that Au (9 D) Agbagess D) (our astuteness equals the maximum possible accuracy) and Uz are "as large as possible" (representing large robustness). To this end, we propose the following regions.
Definition 3. Let D = (n,1) be a data distribution over Idd x {+1}. Let μ+ = {x :)())))))))))))){())) }
4 {z n7(2)= < }.. and 1/2 for n7xx) = 1... For I E pt. we define the neighborhood

---

preserving robustness region, denoted Vz, as
V = {z' p(x,,²) < plu U u²² r')3.
consists of all point that are closer to x than they are to μ U 2//22 (points oppositely labeled from r). We can use similar definition for x E " if E p2 we simply set Va = {zr).
These robustness regions take advantage of the structure of the neighborhood preserving Bayes optimal. They can essentially be thought of as regions that maximally extend from any point in the support of to the decision boundary of the neighborhood preserving Bayes optimal. We include an illustration of the regions V2 for an example distribution in Figure 2.
As technical note, for supp(D) with 7/(x)) 0.5, we give them trivial robustness region. The rational for doing this is that (z)) 0.5 is an edge case that is arbitrary to classify, and consequently
enforcing robustness region at that point is arbitrary and difficult to enforce.
We now formalize the robustness and accuracy guarantees of the max-margin Bayes optimal classifier with the following two results.
Theorem 4. (Accuracy) Let 'D be a data distribution. Let V denote the collection of neighborhood
preserving robustness regions, and let g denote the Bayes optimal classifier. Then the neighborhood
preserving Bayes optimal classifier, Ineighhor. satisfies Ay(gnsighhor, D) A(g, D), where A(g, D) denotes the accuracy of the Bayes optimal. Thus, Ineighhor maximizes accuracy.
Theorem 5. (Robustness) Let 'D be a data distribution, let f be classifier, and let U be set of robustness regions. Suppose that Au(f, D) A(g, D), where g denotes the Bayes optimal classifier. Then there exists I E (D) such that V₂ & Uz. where Vz denotes the neighborhood preserving robustness region about x. In particular, we cannot have Vz be a strict subset of Ug. for all x.
Theorem 4 shows that the neighborhood preserving Bayes classifier achieves maximal accuracy, while Theorem 5 shows that achieving strictly higher robustness (while maintaining accuracy) is not possible; while it is possible to make accurate classifiers which have higher robustness than Ineighbor some regions of space, it not possible for this to hold across all regions. Thus, the neighborhood preserving Bayes optimal classifier can be thought of as a local maximum to the constrained optimization problem of maximizing robustness subject to having maximum (equal to the Bayes optimal) accuracy.
3.1 Neighborhood Consistency
Having defined the neighborhood preserving Bayes optimal classifier, we now turn our attention towards building classifiers that converge towards it. Before doing this, we must precisely define what it means converge. Intuitively, this consists of building classifiers whose robustness regions "approach" the robustness regions of the neighborhood preserving Bayes optimal classifier. This motivates the definition of partial neighborhood preserving robustness regions.
Definition 6. Let 0 < < 1 be a real number, and let D (p, be data distribution over Rdd x {+1). Let 1++ = {x n(x) > }), n² = {x nT(x)) < 2), and μ1/2 = {x : n(x) = 1)- For E ,t,, we define the neighborhood preserving rebustness region, denoted Vg, as
V& =x' {x' p(a,2') < kp(μ U Up)zz')}
consists of all points that are closer to x than they are to J Uu2/2 (points oppositely labeled from a) by a factor of k. We can use similar definition for x E p². Finally, if v(x)) 2. we simply set V*=
(x).
Observe that VK C V2 for all 0 < K < 1, and thus being robust with respect to V is a milder condition than Vg Using this notion, we can now define margin consistency.
Definition 7. A learning algorithm A is said to be neighborhood consistent if the following holds for any data distribution DD For any 0 < E, 6, < 1, there exists such that for all n 2 N, with probability at least - over S ~ D
(As, D) Alg. -e,
where 9 denotes the Bayes optimal classifier and Ag denotes the classifier learned by algorithm A from dataset S.
5

---

This condition essentially says that the astuteness of the classifier learned by the algorithm converges towards the accuracy of the Bayes optimal classifier. Furthermore, we stipulate that this holds as long as the astuteness is measured with respect to some V*. Observe that as k + 1, these regions converge towards the neighborhood preserving robustness regions, thus giving us classifier with robustness effectively equal to that of the neighhorhood preserving Bayes optimal classifier.
4 Neighhorhood Consistent Non-Parametric Classifiers
Having defined neighborhood consistency, turn the following question: which non-parametric algorithms are neighborhood consistent? Our starting point will be the standard literature for the convergence of non-parametric classifiers with regard to accuracy. We begin by considering the standard conditions for k, -earest neighbors to converge (in accuracy) towards the Bayes optimal.
conditions met: lim,,+oo k; and 1im Km 0. The first condition guarantees that each point is classified by using an increasing number of nearest neighbors (thus making the probability of misclassification small), and the second condition guarantees that each point is classified using only points very close to it. We will refer to the first condition as precision, and the second condition as locality. A natural question is whether the same principles suffice for neighborhood consistency well. We began by showing that without any additional constraints, the answer is no.
k, nearest neighbors is consistent if and only if the following
Theorem 8. Ler = (n, n) be the data distribution where denotes the uniform distribution over [0, and n is defined as: q(z) x. Over this space, let p be the euclidean distance metric. Suppose k (log n) for 1 S < cc. Then k nearest neighbors is not neighborhood consistent with respect D.
The issue the example above is that for smaller kns k nearest neighbors lacks sufficient precision. For neighborhood consistnecy, points must be labeled using even more training points than are needed accuracy. This is because the classifier must be uniformly correct across the entirety of V Thus, to build neighborhood consistent classifiers, we must bolster the precision from the standard amount used for standard consistency. To do this, we begin by introducing splitting numbers, a useful tool for bolstering the precision of weight functions.
4.1 Splitting Numbers
We will now generalize beyond nearest neighbors to consider weight functions. Doing so will allow us simultaneously analyze nearest neighbors and kernel classifiers. To do so, we must first rigorously substantiate our intuitions about increasing precision into concrete requirements. This will require several technical definitions.
Definition 9. Let μ be a probability measure over Rd. For any x E Rd, the probability radius Tz(2) is the smallest radius for which B(I,Tp(x) has probability mass at least p. More precisely, (x) = inf(r: μ(( ((xx r)) 2 p).
Definition 10. Let W be weight function and let S (2.. InJ be any finite subset of Rdd For any x E Rd, a 2 O, and 0 < B S. 1, let W....8 = {i p(x, S a, w² (x) 2 3}. Then the splitting number of W with respect S, denoted as T(W, 8) the number of distinct subsets generated by Wa,n.3 (las))=[[Wa....
ranges over Rd, ranges over [0, oo), and ranges over [0, 1). Thus Rdd, a, < 1)}--
Splitting numbers allow to ensure high amounts of precision over weight function. To prove neighborhood consistency, is necessary for a classifier to be correct at all points in given region. Consequently, techniques that consider single point will be insufficient. The splitting number provides mechanism for studying entire regions simultaneously. For more details on splitting numbers, we include several examples in the appendix.
4.2 Sufficient Conditions for Neighborhood Consistency
We now state main result.

---

Theorem 11. Let W be a weight function, D distribution over R x (+1), U a neighborhood preserving collection, and (t,)i be sequence of positive integers such that the following four conditions hold.
1. I.W is consistent (with resp. accuracy) with resp. to DD For any < < lim DS (suPreee Σx w (x) ((t.a)))))))) =
3. limn-+00 DS in supzer up [x)] =
4. limn-xoc ES-D"
log ((W.)) =0 0.
Then W is neighborhood consistent with respect to D.
Remarks:
Condition is necessary because neighborhood consistency implies standard consisteney or, convergence in accuracy to the Bayes Optimal. Standard consistency has been well studied for non-parametric classifiers, and there are a variety of results that can be used ensure it for example. Stone's s Theorem (included in the appendix).
Conditions 2. and 3. are stronger version of conditions 2. and 3. of Stone's 's theorem. In particular, both include a supremum taken over all a E R as opposed to simply considering a random point D. This is necessary for ensuring correct labels on entire regions of points simultaneously. We also note that the dependence on (x) (as opposed to some fixed r) is a key property used for adaptive robustness. This allows the algorithm to adjust to potential differing distance scales different regions in Rdd This idea is reminiscent of the analysis given in [6], which also considers probability radii.
Condition is an entirely new condition which allows us to simultaneously consider all T(W, S) subsets of S. This is needed for analyzing weighted sums with arbitrary weights.
Next, we apply Theorem 11 to get specific examples of margin consistent non non-parametric algorithms.
4.3 Nearest Neighbors and Kernel Classifiers
We now provide sufficient conditions for k. -earest neighbors to be neighborhood consistent.
Corollary 12. Suppose ( satisfies (1) limn->ec
0, and (2) lim Rn
log
0. Then
-yeneersst neighbors is neighborhood consistent.
As result of Theorem 8, corollary 12 is tight for nearest neighbors. Thus kn nearest neighbors is neighborhood consistent if and only if kn = w(logn) n).
Next, we give sufficient conditions for a kimel-simillrity classifier. Corollary 13.
Let W be a kernel classifier over Rd x (+1} constructed from RR+ + R and hn Suppose the following properties hold.
K decreasing, and satisfies Sea K (([x=|)dd < co.
lima-soc hn and 1om nh. DO.
3. For any c > 1, lim
K(xr) 0.
K(w)
4. For any 2 0, lim Ing
D0.
Then W is neighborhood consistent.
Observe that conditions 1. and 3. are satisfied by many common Kernel functions such as the Gaussian or Exponential kernel (K(z) exp(-z²)/ K(x) = exp(-z)). Condition 4. can be similarly satisfied by just increasing hn to be sufficiently large. Overall, this theorem states that Kernel classification is neighborhood consistent as long as the bandwidth shrinks slowly enough.
4.4 Histogram Classifiers
Having discussed neighborhood consistent nearest-neighhors and kernel classifier, we now turn attention towards another popular weight function, histogram classifiers, Recall that histogram
7

---

μ
11
Figure 3: we have a histogram classifier being applied to the blue and red regions. The classifier will be unable to construct good labels the cells labeled A, B, C, and consequently will not be robust with respect to V for sufficiently large K.
classifiers operate by partitioning their input space into increasingly small cells, and then classifying each cell by using a majority vote from the training examples within that cell (a detailed description be found in the appendix). We seek to answer the following question: is increasing precision sufficient for making histogram classifiers neighborhood consistent? Unfortunately, the answer this be no. The main issue is that histogram elassifiers have mechanism for performing classification outside the support of the data distribution.
turns
For example of this, refer to Figure 3. Here classifier. Observe that the cell labeled contains points that are strictly closer to fe* than μ and consequently, for sufficiently large K, VIN will intersect A for some point g A similar argument holds for the cells labeled B and C.. However, since A, B, C are all cells that will never contain any data, they will never be labeled in meaningful way. Because of this, histogram classifiers not neighborhood consistent.
distribution being classified by histogram
Validation
Exponential Kernel
Polynomial Kernel
tros-
62-
200
Training Sample size
Sumple Siiw
(a) exponential kernel
(b) polynomial kernel
Figure 4: Plots of astuteness against the training sample size. In both panels, accuracy is plotted in red, and the varying levels of robustness regions (x 0.1, 0.3, 0.5) are givne in blue, green and purple. In panel (a), observe that as sample size increases, every measure of astuteness converges towards 0.8 which as predicted by Corollary 13. panel (b), although the accuracy appears to converge, none of the robustness measure. In fact, they get progressively worse the larger gets.
To complement theoretical large sample results for parammetrii classifiers, several experiments to understand their behavior for finite samples. We seek to understand how quickly non-parametic classifiers converge towards the neighborhood preserving Bayes optimal.
include
We focus our attention on kernel classifiers and use two different kernel similarity functions: the first, exponential kernel, and the second, polynomial kernel. These classifiers were chosen that the

---

former meets the conditions of Corollary 13, and the latter does not. Full details on these classifiers can be found in the appendix.
To be able to measure performance with increasing data size, we look at a simple synthetic dataset over overlayed circles (see Figure 5 for illustration) with support designed that the data is intrinsically multiscaled. In particular, this calls for different levels of robustness in different regions. For simplicity, we use a global label noise parameter of 0.2, meaning that any sample drawn from this distribution is labeled differently than its support with probability 0.2. Further details about our dataset are given in section
Performance Measure. For given classifier, we evaluate its astuteness at a test point x with respect to the robustness region Vi (Definition 6). While these regions are not computable in practice due to their dependency on the support of the data distribution, we are able to approximate them for this synthetic example due our explicit knowledge of the data distribution. Details for doing this he found in the appendix. To compute the empirical astuteness of a kernel classifier Wx about test point x, we perform a grid search over all points V2 ensure that all points in the robustness region are labeled correctly.
For each classifier, we measure the empirical astuteness by using three trials of 20 test points and taking the average. While this is a relatively small amount of test data, it suffices as our purpose is to just verify that the algorithm roughly converges towards the optimal possible astuteness. Recall that for any neighborhood consistent algorithm, as n + 0o, Ay= should converge towards A", the accuracy of the Bayes optimal classifier, for any 0 < < 1. Thus, verify this holds, we R = 0.1, 0.3, 0.5. For each of these values, we plot the empirical astuteness as the training sample size n gets larger and larger. As baseline, also plot their standard accuracy on the test set.
The results are presented in Figure 4; the left panel is for the exponential kemel,, while the right one is for the polynomial kemnl. As predicted by our theory, we see that in all cases, the exponential kernel converges towards the maximum astuteness regardless of the value of k: the only difference is that the rate of convergence is slower for larger values of This is, of course, expected because larger values of k entail larger robustness regions.
Results and Discussion:
By contrast, the polynomial kernel performs progressively worse for larger values of k. This kernel was selected specifically to violate the conditions of Corollary 13, and particular fails criteria 3. However, note that the polynomial kernel nevertheless performs will with respect to accuracy thus giving another example demonstrating the added difficulty of neighborhood consistency.
Our results bridge the gap between our asymptotic theoretical results and finite sample regimes. In particular, we see that kernel classifiers that meet the conditions of Corollary 13 are able to converge in astuteness towards the neighborhood preserving Bayes optimal classifier, while classifiers that do not meet these conditions fail.
6 Related Work
There is a wealth of literature on robust classification, most of which impose the same robustness radius r on the entire data. [5, 17, 19, 20, 26, 15, 16, 18, 21, 22, 23], among others, focus primarily on neural networks, and robustness regions that are E, E2, or &o norm balls of a given radius r.
[7] and [12] show how to train neural networks with different robustness radii at different points by trading off robustness and accuracy; their work differ from ours that they focus on neural networks, their robustness regions are still norm balls, and that their work is largely empirical.
Our framework is also related large margin classification - in the sense that the robustness regions U induce a margin constraint on the decision boundary. The most popular large margin classifier the Support Vector Machine[9, 3, 14] - a large margin linear classifier that minimizes the worst- case margin over the training data. Similar ideas have also been used to design classifiers that are more flexible than linear; for example, [27] shows how to build large margin Lipschitz classifiers by rounding globally Lipschitz functions. Finally, there has also been purely empirical work on achieving large margins for more complex classifiers - such as [13] for deep neural networks that minimizes the worst case margin, and [29] for metric learning to find large margin nearest neighbors. Our work differs from these in that our goal to ensure a high enough local margin at each æ, (by considering the neighborhood preserving regions V₂) as opposed to optimizing global margin.
9

---

Finally, our analysis builds on prior work on robust classification for non parametric methods in the standard framework. [1. 24, 28, 31] provide adversarial attacks on non non-paramtrri methods. Wang et. al. [28] develops defense for 1-NN that removes subset of the training set to ensure higher robustness. Yang et. al [31] proposes the r-optimal classifier which is the maximally astute classifier in the standard robustness framework- and proposes a defense called Adversarial Pruning.
Theoretically, [4] provide conditions under which weight functions converge towards the r-optimal classifier in the large sample limit. They show that for r-separated distributions, where points from different classes are least distance 2r or more apart, nearest neighbors and kernel classifiers satisfy these conditions. In the more general case, they use Adversarial Pruning preprocessing step to ensure that the training data r-separated, and show that this preprocessing step followed by nearest neighbors or kernel classifiers leads to solutions that are robust and accurate in the large sample limit. Our result fundamentally differs from theirs in that we analyze a different algorithm, and our proof techniques are quite different. In particular, the fundamental differences between the r-optimal classifier and the neighborhood preserving Bayes optimal classifier call for different algorithms and different analysis techniques.
In concurrent work, [8] proposes similar limit the neighborhood preserving Bayes optimal which they refer to as the margin canonical Bayes. However, their work then focuses on a data augmentation technique that leads to convergence whereas we focus on proving the neighborhood consistency of classical non -on-aaametric classifiers.
References
[1] Laurent Amsaleg, James Bailey, Dominique Barbe, Sarah M. Erfani, Michael E. Houle, Vinh Nguyen, and Milos Radovanovic. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In 2017 IEEÉ Workshop on Information Forensics and Security, WIFS 2017, Rennes, France, December 4-7, 2017, pages 1 1-6, 2017.
[2] Robert B. Ash. Information theory. Dover Publications, 1990.
[3] Kristin P. Bennett and Erin J. Bredensteiner. Duality and geometry in SVM classifiers. In Pat Langley, editor, Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 - July 2, 2000, pages 57-64. Morgan Kaufmann, 2000.
[4] Robi Bhattacharjec and Kamalika Chaudhuri. When are non parametric methods robust? In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 832-841, PMLR, 2020.
[5] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26. 2017, pages 39-57, 2017.
[6] Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor clas- sification. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3437-3445. Curran Associates, Inc., 2014.
[7] Minhao Cheng. Qi Lei, Pin- Yu Chen, Inderjit S. Dhillon, and Cho-Jui Hsieh. CAT: customized adversarial training for improved robustness. CoRR, abs/2002.06789, 2020.
[8] Sadia Chowdhury and Ruth Urner. On the (un-)avoidabilityy of adversarial examples. CoRR, abs/2106. 13326, 2021.
[9] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Mach. Learn., 20(3):273-297, 1995.
[10] Sanjoy Dasgupta, Daniel J. Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 353-360, Curran Associates, Inc., 2007.
10

---

[11] Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition, volume 31 of Stochastic Modelling and Applied Probability. Springer, 1996.
[12] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. MMA training: Direct input space margin maximization through adversarial training. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020.
[13] Gamaleldin F. Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada, pages 850-860, 2018.
and Roman Garnett, editors, Advances in Neural
[14] Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. Mach. Learn., 37(3):777-296, 1999.
[15] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30, pages 2266-2276. Curran Associates, Inc., 2017.
[16] Guy Katz, Clark W. Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Towards proving the adversarial robustness of deep neural networks. In Proceedings First Workshop on Formal Verification of Autonomous Vehicles, FVAV iFM 2017, Turin, Italy, 19th September pages 19-26, 2017.
2017.,
[17] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
[18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
[19] Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against deep learning systems using adversarial examples. ASIACCS, 2017.
[20] Nicolas Papernot, Patrick D. McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In IEEE European Symposium on Security and Privacy, EuroS&P 2016, Saarbrücken, Germany, March 21-24, 2016, pages 372-387, 2016.
[21] Nicolas Papernot, Patrick D. McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016, pages 582-597, 2016.
[22] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In 6th International Conference on Learning Representattinss ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. 2018.
[23] Aman Sinha, Hongseok Namkoong, and John C. Duchi. Certifying some distributional ro- bustness with principled adversarial training. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018
[24] Chawin Sitawarin and David A. Wagner. On the robustness of deep k-nearest neighbors. In 2019 IEEE Security and Privacy Workshops, SP Workshops 2019, San Francisco, CA, USA, May 19-23, 2019, pages 1-7, 2019.
[25] Charles Stone, Consistent nonparametric regression. The Annals of Statistics, 5(4):595-645 1977.
11

---

[26] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14- 16, 2014, Conference Track Proceedings, 2014.
[27] Ulrike von Luxburg and Olivier Bousquet. Distance- classification with lipschitz functions. In Bernhard Schölkopf and Manfred K. Warmuth, editors, Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop. COLT/Kermel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pages 314-328. Springer, 2003.
[28] Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pages 5120-5129, 2018.
[29] Kilian Q. Weinberger, John Blitzer, and Lawrence Saul. Distance metric learning for large margin nearest neighbor classification. In Advances in Neural Information Processing Systems 18 [Neural Information Processing Systems, NIPS 2005, December 5-8, 2005, Vancouver, British Columbia, Canada), pages 1473-1480, 2005.
[30] Yao- Yuan Yang, Cyrus Rashtchian, Ruslan Salakhutdinov, and Kamalika Chaudhuri. A closer look at robustness vs. accuracy. In Neural Information Processing Systems (NeuRIPS), 2020.
[31] Yao- Yuan Yang, Cyrus Rashtchian, Yizhen Wang. and Kamalika Chaudhuri. Robustness for non-parametric methods: A generic attack and defense. In Artificial Intelligence and Statisties (AISTATS), 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] we express our claims through theorems
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] In the theorem statements
(b) Did you include complete proofs of all theoretical results? [Yes] in the appendix
3. If you experiments..
12

---

(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] in the appendix
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Many details are given in the main body, but a full explanation with all details is in the appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] In the appendix: this was not particularly needed for our very light experiments.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] Just simple personal computer.
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "uIov7f1jQJ5", "reviewer": "Reviewer_7R4w", "summary": "The authors argue that robustness regions should be larger in some regions of data, and smaller in others, and propose a new limit classifier, called the neighborhood optimal classifier, that extends the Bayes optimal classifier  outside its support by using the label of the closest in-support point. They argue that this classifier maximizes the size of its robustness regions subject to the constraint of having accuracy equal to the Bayes optimal, then present sufficient conditions under which general non-parametric methods that can be represented as weight functions converge towards this limit object, and show that both nearest neighbors and kernel classifiers (under certain assumptions) suffice.  ", "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": "The authors propose an alternative formulation of robust classification that ensures that in the large sample limit, there is no robustness-accuracy tradeoff, and that regions of space with higher separation are classified more robustly. To this end, the authors introduce a new large-sample limit, the neighborhood preserving Bayes optimal (NPBO) classifier. For an input x, it outputs the prediction of the Bayes Optimal on the nearest neighbor (including itself) in the support of the data distribution D. \n \n\nThey show that k_n-nearest neighbors converge to the NPBO provided k_n = ω(log n), and kernel classifiers converge to the NPBO provided certain conditions (the kernel function K has faster than polynomial decay, and the bandwidth parameter h_n decreases sufficiently slowly), but certain types of histogram classifiers do not converge to the NPBO, even if they do converge to the Bayes optimal. They also provide experiments to validate their claims.\n\nI feel this work is novel in motivation and solid in theory.  \n\nI have the following comments for improving the writing and organization: \nIn Section 1, \"astuteness\" is used without any citation in the first paragraph.  \nIn Section 2, there are many conceptions that are existed in previous papers, but the authors did not mention or give references, \nfor instance, Definition 1 \"astute and astuteness\", weight functions, histogram classfiers, etc.\nLine 259: Conditions 2. and 3. are ..., conditions 2. and 3. of ... .  I think the period \".\" is not needed after 2 and 3.\nLine 144: We call this the the neighborhood preserving ... \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not address the limitations and potential negative societal impact of their work.  A paragraph of discussion is needed. ", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20 hours"}, "extra_text": {}}, {"review_id": "ZZ0dRd6XqKf", "reviewer": "Reviewer_piq5", "summary": "This paper aims to give a new robust learning framework where the radius of adversarial attacks at different points can adaptively change. The main purpose is \"to increase robustness, without sacrificing accuracy\", as claimed by the author(s). In order to achieve this goal, author(s) have utilized a number of consistent non-parametric learning algorithms which are already proved to converge to an *optimal* classifier as the sample size increases (optimality could be defined in any certain sense, however, in this paper Bayes optimality has been mostly focused). Then, a new modification has been proposed in order to help such learning techniques to preserve as much adversarial robustness as they can, while still converge to the Bayes optimal classifier.\n\nThe main results are (most probably) solid, and maybe even interesting specially when we look at them from a pure theoretical standpoint. Moreover, I checked all the theoretical results and some of their proofs, and didn't find any notable technical mistakes or counter-intuitive conclusions. However, paper suffers from uninformative writing (specially in the introduction section) and lack of proper justification for some of the core ideas in real-world applications. The above problems, in addition to the fact that results are mostly asymptotic and centered around \"consistency\" of classifiers rather than their finite-sample performance, are the main weaknesses of the paper.\n\nMy vote at the current stage is weak-reject.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As far as I have understood, the main contribution of this paper is as follows: When the number of samples $n$ goes toward infinity and consequently the true data distribution becomes known to the learner,  then \"the most robust classifier which coincides with the Bayes optimal classifier inside the support\" would be trivial and easy to achieve. This paper gives a methodical approach so that some classes of non-paramteric classifiers (like $k$-nearest neighbor) can be computed for finite $n$, while are also guaranteed to converge to the trivial robust classifiers of $n=\\infty$ which are described above (The guarantees are all asymptotic in this work). There are some other contributions in proving the consistency of certain non-parametric classes of learners, which I assume to be additional results.\n\n---------------------------------------------------------------------------\n\nMain comments:\n\nPaper can greatly benefit from an improved writing, specially for the Introduction section. Some terms, such as \"accuracy and astuteness\" have been carelessly used in this section without being properly defined (they are both defined later in subsequent sections). This has made the Intro part to be somehow uninformative. Also, some motivations in the beginning of the paper have become lost and buried under tones of theorems and definitions inside the manuscript. For example, the abstract of the paper gives some motivations w.r.t. varying radius of attacks $r$ for different regions of the distribution. However, I do not see the results to be that much aligned with this particular motif. Maybe the abstract and parts of the introduction section should be rewritten.\n\nAnother issue is that paper lacks real-world justification for its main idea: Having robustness to out-of-distribution samples (for example, off-manifold data points which are usually the result of adversarial attacks) is interesting, but the discussions around this issue in the paper is slim to none. In other words, why should any reader be concerned with samples like $x$ which are not in the support of data distribution, i.e. $x\\notin\\mathrm{supp}\\left(\\mu\\right)$? One might assume the answer to be crystal clear for some well-informed audience, but that's not the case for general readers.\n\nAnother fundamental problem is that results in this work are asymptotic. No non-asymptotic bounds have been proposed to guarantee any type of performance measure when the number of samples $n$ is finite. Any type of guarantees on the adversarial robustness when $n$ is infinite and the true underlying data distribution (or at least the true data manifold) is revealed are not that much interesting. It would be nice if authors can give some certificate for robustness when $n$ is finite. Some of the cited works in this paper (Sinha et al., for example) have already done that for distributionally robust scenarios.\n\n--------------------------------------------------\n\nMinor comments:\n-(Line 144): \"the\" has been repeated.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "Bc3Yh5HPeKJ", "reviewer": "Reviewer_n6N3", "summary": "This paper studies classification rules that are \"astute\", that is, those that are accurate and robust. Importantly, the authors note that common definitions of robust classifiers, which are given in terms of a fixed parameter (typically a size of a perturbation set) are not astute, as they do not fully exploit the fact that margins are not uniform across the data distribution. This paper first studies conditions under their so-called \"neighborhood optimal classifier\" maximizes robustness while retaining the Bayes classifier accuracy in the unperturbed distribution. Furthermore, the authors show that several popular non-parametric classifier provide consistent estimates for this classifier. Finally, this is demonstrated numerically in a simple experimental setting.", "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": "This paper is very interesting, and a pleasure to read. The limitation of current approaches to study adversarial robustness is clear from the presented concepts, and the proposed solutions are intuitive and elegant. I have a few minor comments:\n\nMain comments:\n- While the authors present results of consistency of certain non-parametric classifiers, their finite-sample performance is only evaluated numerically. Can the authors comment, at least briefly, on the potential of extending the analysis of convergence rates of non-parametric classifiers (such as those in [Doring et al, 2018]) to the setting presented here?\n\n- In the paragraph on line 154, the authors motivate their definition of \"neighborhood preserving robustness regions\". To do so, they explain that they seek for regions U_x so that the astute accuracy of g_max equals the accuracy of the Bayes classifier. However, it's not totally clear what g_max is. Is it the one that maximizes the measure of U_x? A clarification would be appreciated.\n\n- On the paragraph following Theorem 5, the authors comment that g_neighbor can be thought of a local maximum to a constrained optimization problem. However, it is not clear why this is not a global maximum - how could one obtain a classifier with larger robustness constrained to having equal accuracy as the Bayes?\n\nMinor comments:\n- Lines 57: space missing on \"Instead [3]\"\n- The paragraphs on line 71 and 78 feel a bit repetitive, given that the preceding paragraphs just gave a summary of the presented contributions.\n- Line 96: coma instead of semicolon?\n- Line 137: principal -> principle\n- Line 144: \"the the\"\n- Line 171: the authors write \"max-margin Bayes\" classifier, but I believe they mean the neighborhood preserving Bayes classifier? This might be equivalent, but has not been defined as \"max-margin\" explicitely.\n- The notation of algorithm (A_S) and Accuracy is slightly confusing.\n- Line 222 \"consistnecy\" -> consistency\n- Line 222: \"needed accuracy\" -> \"needed for accuracy\"\n- On Corollary 12, the authors use the notation k_n^\\infty_1. There's a parenthesis that seems out of place. But also, this notation has not been defined?\n- On Corollary 13, the authors use h_n, but this seems undefined. Do they simply refer to the rule k_nn on the computed features?\n- Line 293: \"The answer this\" -> the answer to this\n- Figure 3 seems to have some strange gray edges on its bottom and left sides.\n- Line 335: \"performs will\" -> performs well.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6dABzUVl5jw", "reviewer": "Reviewer_z1YM", "summary": "This paper argues that the standard robust learning method ignores the data heterogeneity: the robustness radius is fixed as some artificial value r for all the examples. The authors then propose a new neighborhood optimal classifier to address this problem, and theoretically studies the convergence condition for a class of non-parametric methods, including histogram classifiers, nearest neighbors, and kernel classifiers. Synthetic experiments are provided to verify their theoretical results.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed robustness framework is well motivated and clearly defined. At a high level, introducing heterogeneous robustness regions for different examples seems to be a promising direction for a better robustness definition. The theoretical results are also clearly presented and easy to follow. Nevertheless, my main concern of this paper is the practicability of the proposed framework: the proposed definition of neighborhood optimal classifier requires the knowledge of the support of the conditional distribution, which seems to be not practical for typical classification problem. More specifically, I have the following questions:\n\n1.\tHow to apply Definition 3 to a more typical finite-sample classification problem? Are there ways to estimate the support of the ground-truth conditional distribution? \n\n2.\tWhat does the theoretical results suggest for robust learning using non-parametric methods? How can these results generalize beyond non-parametric methods?\n\n3.\tThe dataset of overlayed circles considered in Section 5 seems to be too artificial to me. Including the experimental results on other datasets, such as Gaussian mixtures or even some image benchmarks, will strength the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel and interesting idea to combine robustness and consistency.
It is well written and provides explicit examples how the general framework can be 
applied. On the negative side, only consistency is considered and more refined convergence
results such as learning rates or finite sample bounds are missing.
Decision: Accept (Poster)