Consistent Non-Parametric Methods for Maximizing Robustness
Year: 2022

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 there is an artificial robustness radius r that applies to all inputs. This ignores the fact that data may be highly heterogeneous, in which case it 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 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, and show that both nearest neighbors and kernel classifiers satisfy them under certain conditions.

heading: 1 Introduction
text: 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 a classifier c is r-robust at an input x if it predicts the same label on a ball of radius r around x. Our goal in robust classification is to find a classifier c that maximizes astuteness, which is defined as accuracy on those examples where c 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], a major limitation is that enforcing a 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, a classifier that has an uniformly large robustness radius r 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 a fixed robustness radius that applies 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 robustness-accuracy 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 a new large-sample limit. In the standard statistical learning framework, the large-sample ideal is the Bayes optimal classifier that maximizes accuracy on the
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
data distribution, and is undefined outside. Since this is not always robust with radius r, prior work introduces the notion of an 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 1.
We depart from both by introducing a new limit that we call the neighborhood preserving Bayes optimal classifier, described as follows. Given an input x that lies in the support of the data distribution D, it predicts the same label as the Bayes optimal. On an x 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 as higher robustness where possible without sacrificing accuracy.
We next investigate how to design classifiers with this convergence property. Our starting point is classical statistical theory [25] that shows that a class of methods known as weight functions will converge to a Bayes optimal in the large sample limit provided certain conditions hold; these include k-nearest neighbors under certain conditions on k 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 kn-nearest neighbors converge to the neighborhood preserving Bayes optimal provided kn = ω(log n), 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 to the Bayes optimal. We round these off with a lower bound that shows that for nearest neighbor, the condition that kn = ω(log n) is tight. In particular, for kn = O(log n), there exist distributions for which kn-nearest neighbors provably fails to 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 kn-nearest neighbors satisfy these conditions when kn = ω(log n), and kernel classifiers satisfy these conditions provided the kernel function K has faster than polynomial decay, and the bandwidth parameter hn 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 a lower bound for nearest neighbors, indi-
cating that kn = ω(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 greatly help address the challenges in adversarial robustness.

heading: 2 Preliminaries
text: We consider binary classification over Rd × {±1}, and let ρ denote any distance metric on Rd. We let µ denote the measure over Rd corresponding to the probability distribution over which instances x ∈ Rd are drawn. Each instance x is then labeled as +1 with probability η(x) and −1 with probability 1− η(x). Together, µ and η comprise our data distribution D = (µ, η) over Rd × {±1}.
For comparison to the robust case, for a classifier f : Rd → {±1} and a distribution D over Rd × {±1}, it will be instructive to consider its accuracy, denoted A(f,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 x ∈ supp(µ), g(x) = 1 if η(x) ≥ 12 , and g(x) = −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 Ux. We will let U = {Ux : x ∈ Rd} denote the collections of all robustness regions.
We say that a classifier f : Rd → {±1} is robust at x if for all x′ ∈ Ux, f(x′) = f(x). Combining robustness and accuracy, we say that classifier is astute at a point x if it is both accurate and robust. Formally, we have the following definition.
Definition 1. A classifier f : Rd → {±1} is said to be astute at (x, y) with respect to robustness collection U if f(x) = y and f is robust at x with respect to U . If D is a data distribution over Rd × {±1}, the astuteness of f over D with respect to U , denoted AU (f,D), is the fraction of examples (x, y) ∼ D for which f is astute at (x, y) with respect to U . Thus
AU (f,D) = P(x,y)∼D[f(x′) = y,∀x′ ∈ Ux].
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 = {(x1, y1), (x2, y2, ), . . . , (xn, yn)} by assigning a function wSi : Rd → [0, 1] that essentially scores how relevant the training point (xi, yi) is to the example being classified. The functions wSi are allowed to depend on x1, . . . , xn but must be independent of the labels y1, . . . , yn. Given these functions, a point x is classified by just checking whether ∑ yiw S i (x) ≥ 0 or not. If it is nonnegative, we output +1 and otherwise −1. A complete description of weight functions is included in the appendix.
Next, we enumerate several common Non-parametric classifiers that can 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 a sufficiently large number of points xi. This corresponds to a weight function in which wSi (x) = 1 kx if xi is in the same cell as x, where kx denotes the number of points in the cell containing x.
kn-nearest neighbors corresponds to a weight function in which wSi (x) = 1 kn if xi is one of the kn nearest neighbors of x, and wSi (x) = 0 otherwise.
Kernel-Similarity classifiers are weight functions built from a kernel function K : R≥0 → R≥0 and a window size (hn)∞1 such that w S i (x) ∝ K(ρ(x, xi)/hn) (we normalize by dividing by∑n
1 K((ρ(x, xi)/hn))).

heading: 3 The Neighborhood preserving Bayes optimal classifier
text: Robust classification is typically studied by setting the robustness regions, U = {Ux}x∈Rd , to be balls of radius r centered at x, Ux = {x′ : ρ(x, x′) ≤ r}. The quantity r is the robustness radius, and is typically set by the practitioner (before any training has occurred).
This method has a 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 can come at a 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 a data distribution D = (µ, η) in which the blue regions denote all points with η(x) > 0.5 (and thus should be labeled +), and the red regions denote all points with η(x) < 0.5 (and thus should be labeled −). Observe that it is not possible to be simultaneously 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 a 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 accuracy-robustness trade-offs and adaptively size robustness regions (thus allowing us to defend against a larger range of adversarial attacks at points that are located in 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. Let D = (µ, η) be a distribution over Rd ×{±1}. Then the neighborhood preserving Bayes optimal classifier of D, denoted gneighbor, is the classifier defined as follows. Let µ+ = {x : η(x) ≥ 12} and µ − = {x : η(x) < 12}. Then for any x ∈ R d, gneighbor(x) = +1 if ρ(x, µ+) ≤ ρ(x, µ−), and gneighbor(x) = −1 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 a local neighborhood about every point in the support. For an illustration, refer to Figure 2, which plots the decision boundary of the neighborhood preserving Bayes optimal for an example distribution.
Next, we turn our attention towards measuring its robustness, which must be done with respect to some set of robustness regions U = {Ux}. While these regions Ux can be nearly arbitrary, we seek regions Ux such that AU (gmax,D) = A(gbayes,D) (our astuteness equals the maximum possible accuracy) and Ux are “as large as possible" (representing large robustness). To this end, we propose the following regions.
Definition 3. Let D = (µ, η) be a data distribution over Rd × {±1}. Let µ+ = {x : η(x) > 12}, µ− = {x : η(x) < 12}, and µ 1/2 = {x : η(x) = 12}. For x ∈ µ +, we define the neighborhood
preserving robustness region, denoted Vx, as
Vx = {x′ : ρ(x, x′) < ρ(µ− ∪ µ 1 2 , x′)}.
It consists of all points that are closer to x than they are to µ− ∪ µ1/2 (points oppositely labeled from x). We can use a similar definition for x ∈ µ−. Finally, if x ∈ µ1/2, we simply set Vx = {x}.
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 x in the support of D to the decision boundary of the neighborhood preserving Bayes optimal. We include an illustration of the regions Vx for an example distribution in Figure 2.
As a technical note, for x ∈ supp(D) with η(x) = 0.5, we give them a trivial robustness region. The rational for doing this is that η(x) = 0.5 is an edge case that is arbitrary to classify, and consequently enforcing a 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, gneighbor, satisfies AV(gneighbor,D) = A(g,D), where A(g,D) denotes the accuracy of the Bayes optimal. Thus, gneighbor maximizes accuracy. Theorem 5. (Robustness) Let D be a data distribution, let f be a classifier, and let U be a set of robustness regions. Suppose that AU (f,D) = A(g,D), where g denotes the Bayes optimal classifier. Then there exists x ∈ supp(D) such that Vx 6⊂ Ux, where Vx denotes the neighborhood preserving robustness region about x. In particular, we cannot have Vx be a strict subset of Ux for all x.
Theorem 4 shows that the neighborhood preserving Bayes classifier achieves maximal accuracy, while Theorem 5 shows that achieving a strictly higher robustness (while maintaining accuracy) is not possible; while it is possible to make accurate classifiers which have higher robustness than gneighbor in some regions of space, it is 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.

heading: 3.1 Neighborhood Consistency
text: 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 to 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 = (µ, η) be a data distribution over Rd × {±1}. Let µ+ = {x : η(x) > 12}, µ − = {x : η(x) < 12}, and µ 1/2 = {x : η(x) = 12}. For x ∈ µ+, we define the neighborhood preserving robustness region, denoted Vx, as
Vx = {x′ : ρ(x, x′) < κρ(µ− ∪ µ 1 2 , x′)}.
It consists of all points that are closer to x than they are to µ− ∪ µ1/2 (points oppositely labeled from x) by a factor of κ. We can use a similar definition for x ∈ µ−. Finally, if η(x) = 12 , we simply set V κx = {x}.
Observe that V κx ⊂ Vx for all 0 < κ < 1, and thus being robust with respect to V κx is a milder condition than Vx. 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 D. For any 0 < , δ, κ < 1, there exists N such that for all n ≥ N , with probability at least 1− δ over S ∼ Dn,
AVκ(AS , D) ≥ A(g,D)− , where g denotes the Bayes optimal classifier and AS denotes the classifier learned by algorithm A from dataset S.
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 κ→ 1, these regions converge towards the neighborhood preserving robustness regions, thus giving us a classifier with robustness effectively equal to that of the neighborhood preserving Bayes optimal classifier.

heading: 4 Neighborhood Consistent Non-Parametric Classifiers
text: Having defined neighborhood consistency, we turn to 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 kn-nearest neighbors to converge (in accuracy) towards the Bayes optimal.
kn-nearest neighbors is consistent if and only if the following two conditions are met: limn→∞ kn = ∞, and limn→∞ knn = 0. The first condition guarantees that each point is classified by using an increasing number of nearest neighbors (thus making the probability of a 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 as well. We began by showing that without any additional constraints, the answer is no.
Theorem 8. Let D = (µ, η) be the data distribution where µ denotes the uniform distribution over [0, 1] and η is defined as: η(x) = x. Over this space, let ρ be the euclidean distance metric. Suppose kn = O(log n) for 1 ≤ n < ∞. Then kn-nearest neighbors is not neighborhood consistent with respect to D.
The issue in the example above is that for smaller kn, kn-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 κx . 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.

heading: 4.1 Splitting Numbers
text: We will now generalize beyond nearest neighbors to consider weight functions. Doing so will allow us to 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 ∈ Rd, the probability radius rp(x) is the smallest radius for which B(x, rp(x)) has probability mass at least p. More precisely, rp(x) = inf{r : µ(B(x, r)) ≥ p}. Definition 10. Let W be a weight function and let S = {x1, x2, . . . , xn} be any finite subset of Rd. For any x ∈ Rd, α ≥ 0, and 0 ≤ β ≤ 1, let Wx,α,β = {i : ρ(x, xi) ≤ α,wSi (x) ≥ β}. Then the splitting number of W with respect to S, denoted as T (W,S) is the number of distinct subsets generated by Wx,αβ as x ranges over Rd, α ranges over [0,∞), and β ranges over [0, 1]. Thus T (W,S) = |{Wx,α,β : x ∈ Rd, 0 ≤ α, 0 ≤ β ≤ 1}|.
Splitting numbers allow us to ensure high amounts of precision over a weight function. To prove neighborhood consistency, it is necessary for a classifier to be correct at all points in a given region. Consequently, techniques that consider a single point will be insufficient. The splitting number provides a mechanism for studying entire regions simultaneously. For more details on splitting numbers, we include several examples in the appendix.

heading: 4.2 Sufficient Conditions for Neighborhood Consistency
text: We now state our main result.
Theorem 11. Let W be a weight function, D a distribution over Rd × {±1}, U a neighborhood preserving collection, and (tn)∞1 be a sequence of positive integers such that the following four conditions hold.
1. W is consistent (with resp. to accuracy) with resp. to D. 2. For any 0 < p < 1, limn→∞ES∼Dn [supx∈Rd ∑n 1 w S i (x)1ρ(x,xi)>rp(x)] = 0.
3. limn→∞ES∼Dn [tn supx∈Rd w S i (x)] = 0.
4. limn→∞ES∼Dn log T (W,S)
tn = 0.
Then W is neighborhood consistent with respect to D.
Remarks: Condition 1 is necessary because neighborhood consistency implies standard consistency – 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 to ensure it – for example, Stone’s Theorem (included in the appendix).
Conditions 2. and 3. are stronger version of conditions 2. and 3. of Stone’s theorem. In particular, both include a supremum taken over all x ∈ Rd as opposed to simply considering a random point x ∼ D. This is necessary for ensuring correct labels on entire regions of points simultaneously. We also note that the dependence on rp(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 over different regions in Rd. This idea is reminiscent of the analysis given in [6], which also considers probability radii.
Condition 4. 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-parametric algorithms.

heading: 4.3 Nearest Neighbors and Kernel Classifiers
text: We now provide sufficient conditions for kn-nearest neighbors to be neighborhood consistent.
Corollary 12. Suppose (kn)∞1 satisfies (1) limn→∞ kn n = 0, and (2) limn→∞ logn kn = 0. Then kn-nearest neighbors is neighborhood consistent.
As a result of Theorem 8, corollary 12 is tight for nearest neighbors. Thus kn nearest neighbors is neighborhood consistent if and only if kn = ω(log n).
Next, we give sufficient conditions for a kernel-similarity classifier.
Corollary 13. Let W be a kernel classifier over Rd × {±1} constructed from K : R+ → R+ and hn. Suppose the following properties hold.
1. K is decreasing, and satisfies ∫ Rd K(||x||)dx <∞.
2. limn→∞ hn = 0 and limn→∞ nhdn =∞.
3. For any c > 1, limx→∞ K(cx) K(x) = 0.
4. For any x ≥ 0, limn→∞ nlognK( x hn ) =∞.
Then W is neighborhood consistent.
Observe that conditions 1. 2. and 3. are satisfied by many common Kernel functions such as the Gaussian or Exponential kernel (K(x) = exp(−x2)/ K(x) = exp(−x)). 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.

heading: 4.4 Histogram Classifiers
text: Having discussed neighborhood consistent nearest-neighbors and kernel classifier, we now turn our attention towards another popular weight function, histogram classifiers. Recall that histogram
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 can 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 turns out not to be no. The main issue is that histogram classifiers have no mechanism for performing classification outside the support of the data distribution.
For an example of this, refer to Figure 3. Here we see a distribution being classified by a histogram classifier. Observe that the cell labeled A contains points that are strictly closer to µ+ than µ−, and consequently, for sufficiently large κ, V κx will intersect A for some point x ∈ µ+. A similar argument holds for the cells labeled B and C.. However, since A,B,C are all in cells that will never contain any data, they will never be labeled in a meaningful way. Because of this, histogram classifiers are not neighborhood consistent.

heading: 5 Validation
text: To complement our theoretical large sample results for non-parametric classifiers, we now include 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.
We focus our attention on kernel classifiers and use two different kernel similarity functions: the first, an exponential kernel, and the second, a polynomial kernel. These classifiers were chosen so 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 an illustration) with support designed so 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 D.
Performance Measure. For a given classifier, we evaluate its astuteness at a test point x with respect to the robustness region V κx (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 to our explicit knowledge of the data distribution. Details for doing this can be found in the appendix. To compute the empirical astuteness of a kernel classifier WK about test point x, we perform a grid search over all points in V κx to 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→∞, AVκ should converge towards A∗, the accuracy of the Bayes optimal classifier, for any 0 < κ < 1. Thus, to verify this holds, we use κ = 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 a baseline, we also plot their standard accuracy on the test set.
Results and Discussion: The results are presented in Figure 4; the left panel is for the exponential kernel, while the right one is for the polynomial kernel. As predicted by our theory, we see that in all cases, the exponential kernel converges towards the maximum astuteness regardless of the value of κ: the only difference is that the rate of convergence is slower for larger values of κ. This is, of course, expected because larger values of κ entail larger robustness regions.
By contrast, the polynomial kernel performs progressively worse for larger values of κ. This kernel was selected specifically to violate the conditions of Corollary 13, and in 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.

heading: 6 Related Work
text: 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 `1, `2, or `∞ 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 in 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 to 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 is the Support Vector Machine[9, 3, 14] – a large margin linear classifier that minimizes the worstcase 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 is to ensure a high enough local margin at each x, (by considering the neighborhood preserving regions Vx) as opposed to optimizing a global margin.
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-parametric methods. Wang et. al. [28] develops a defense for 1-NN that removes a 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 at least distance 2r or more apart, nearest neighbors and kernel classifiers satisfy these conditions. In the more general case, they use Adversarial Pruning as a preprocessing step to ensure that the training data is 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 a similar limit to 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-parametric classifiers.

Review summaries:
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.  The 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.  My vote at the current stage is weak-reject.

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.

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.