Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

Yizhen Wang; Somesh Jha; Kamalika Chaudhuri

Source-linked AI summary

Analyzing the Robustness of Nearest Neighbors to Adversarial Examples

Yizhen Wang, Somesh Jha, Kamalika Chaudhuri

arXiv:1706.03922v6Jun 13, 2017stat.MLcs.CRcs.LG

TL;DR

The paper asks whether adversarial examples arise from data properties or limited training samples, an issue relevant to robust deployment in security-critical applications. It develops a bias-variance-inspired framework, analyzes k-nearest neighbors, and proposes a modified 1-nearest neighbor classifier. Robustness varies sharply with k, approaches Bayes-optimal robustness for sufficiently fast-growing k, and the modified classifier retains good robustness empirically at reasonable data sizes.

Problem
Whether adversarial examples arise from inherent data properties or insufficient training samples remains poorly understood, despite the need for robust models in safety-critical applications.
Method
The paper develops a theoretical robustness framework analogous to bias-variance theory, analyzes k-nearest neighbors, and introduces a modified 1-nearest neighbor classifier.
Results
Robustness is zero for constant k in certain mixed-label regions, approaches Bayes-optimal robustness when k = Ω(√dn log n), and the proposed classifier performs better than or about as well as baselines against popular attacks.
Takeaways & Limitations
The modified 1-nearest neighbor algorithm has good robustness properties in the large-sample limit and may retain them for reasonable training-data sizes.
Takeaways & Limitations
Open questions include the gap between the analyzed k regimes and developing nearest-neighbor methods with better robustness guarantees.

Abstract

from arXiv · show

Motivated by safety-critical applications, test-time attacks on classifiers via adversarial examples has recently received a great deal of attention. However, there is a general lack of understanding on why adversarial examples arise; whether they originate due to inherent properties of data or due to lack of training samples remains ill-understood. In this work, we introduce a theoretical framework analogous to bias-variance theory for understanding these effects. We use our framework to analyze the robustness of a canonical non-parametric classifier - the k-nearest neighbors. Our analysis shows that its robustness properties depend critically on the value of k - the classifier may be inherently non-robust for small k, but its robustness approaches that of the Bayes Optimal classifier for fast-growing k. We propose a novel modified 1-nearest neighbor classifier, and guarantee its robustness in the large sample limit. Our experiments suggest that this classifier may have good robustness properties even for reasonable data set sizes.

1 Introduction

The paper addresses why adversarial examples arise by separating distributional, finite-sample, and algorithmic effects, then analyzes robustness in nearest neighbors. It shows that robustness depends strongly on k and introduces a modified 1-nearest neighbor method with theoretical and empirical support.

Prior work leaves unclear whether adversarial examples reflect inherent data properties or insufficient training samples.
The framework distinguishes distributional robustness, finite-sample robustness, and algorithmic robustness as separate sources of classifier robustness.These notions extend bias-variance theory to robustness.
Constant-k nearest neighbors has zero robustness in the large-sample limit where p(y = 1|x) lies in (0, 1), despite potentially high accuracy there.
For k = Ω(√dn log n), nearest-neighbor robustness approaches that of the Bayes Optimal classifier in the large-sample limit.Here d is the data dimension and n is the sample size; the required growth is faster than that needed for accuracy convergence.
The proposed modified 1-nearest neighbor classifier has superior large-sample robustness under certain distributional properties.It operates on a modified training set.
Experiments on three datasets find performance better than or about as good as standard 1-nearest neighbors and adversarial training.The results suggest useful robustness even for realistic training-set sizes.

2 The Setting and Definitions

The paper studies white-box test-time attacks against binary classifiers under Euclidean perturbations and defines local, distributional, and accuracy-aware robustness measures. Its framework separates distributional, finite-sample, and algorithmic sources of robustness.

The adversary knows the classifier, training data, and parameters, but cannot modify the training process.
The attack perturbs an input within radius r under an application-specific metric, with this paper using Euclidean distance and binary classification.Multiclass extensions are left for future work.
The robustness radius is the shortest distance from x to an input receiving a different label from classifier f.It measures local robustness at an instance.
Robustness with respect to a distribution is the fraction of instances whose robustness radius is at least r.
Astuteness measures the fraction of examples that are both correctly classified and robust at radius r.The paper uses it as a joint robustness-and-accuracy measure and approximates it experimentally through resistance to standard attacks.
The framework separates distributional robustness in the infinite-sample limit, finite-sample robustness as sample size varies, and algorithmic robustness across training procedures.

3 Robustness of Nearest Neighbors

The robustness of k-nearest neighbors depends critically on k: fixed k is inherently non-robust in mixed-label regions, while sufficiently fast-growing k approaches Bayes-optimal robustness in the large-sample limit.

k-nearest neighbors has distinct robustness regimes for constant k and k = Ω(√(dn log n)).
Low k regime: For fixed k, robustness converges to zero where η(x) lies in (0, 1), under the stated regularity conditions.
Low k regime: 1-NN can retain high accuracy even as its robustness vanishes in mixed-label regions.
Large k regime: For k = Ω(√(dn log n)), the robustness region and astuteness approach those of the Bayes Optimal classifier as n grows.
Large k regime: The larger-k result relies on uniform convergence of empirical label averages over neighborhoods, ensuring agreement with the Bayes Optimal classifier near x.
Large k regime: The required growth rate for k is more stringent than the rate known for accuracy, and whether it is necessary remains open.

4 A Robust 1-NN Algorithm

The paper modifies 1-nearest neighbors by filtering and selecting training points to enforce local label consistency and separation, then proves large-sample robustness guarantees.

Because the theoretically robust k regime is impractical, the paper seeks a more robust 1-NN method for smaller k.
The modified classifier removes selected training points so oppositely labeled points are separated while retaining confident, locally consistent examples.
Algorithm: The algorithm marks points red when their confident label agrees with the training label and nearby points receive the same label.
Algorithm: It then computes the largest r-separated subset containing all red points and runs nearest neighbors on the resulting training set.
Performance guarantees: The performance theorem gives a high-probability guarantee for Algorithm 1 under choices of Δ_n, δ, k_n, p_n, and margin τ.
Performance guarantees: The guaranteed robust region is approximately the high-density subset of the robust strict interior, and can approach it for smooth distributions as n grows.

5 Experiments

The experiments evaluate RobustNN against standard and adversarially trained nearest-neighbor baselines on three datasets under white-box and black-box attacks. RobustNN generally performs best on denser datasets, while its advantage is smaller or reversed for sparse MNIST at low attack radii.

Experimental setup: Three datasets with differing training sizes relative to dimension are evaluated against white-box and black-box attacks.The datasets are Halfmoon, MNIST 1v7, and Abalone.
Experimental setup: RobustNN is compared with StandardNN, ATNN, and ATNN-all.ATNN and ATNN-all augment the training set with adversarial examples generated by one or all attack methods, respectively.
White-box attacks: RobustNN outperforms all baselines on Halfmoon and Abalone across all white-box attack radii.On MNIST, its accuracy is slightly lower at low attack radii but higher at large attack radii.
White-box attacks: RobustNN mostly outperforms StandardNN, ATNN, and ATNN-all, with larger gains when training size is large relative to dimension.Its advantage is reported for Halfmoon and Abalone, while sparse MNIST shows lower accuracy at small attack radii and higher accuracy otherwise.
Black-box attacks: Black-box attacks are less effective than white-box attacks for all algorithms, and kernel substitutes attack nearest neighbors more effectively than neural-network substitutes.The similar structure between kernel classifiers and nearest neighbors is offered as the explanation for the latter comparison.
Black-box attacks: RobustNN outperforms the baselines for both black-box attacks on Halfmoon and Abalone but performs worse for small-radius MNIST neural-network-substitute attacks.The results associate stronger performance with denser datasets having more training data relative to dimension.

6 Conclusion

The paper introduces a theoretical framework distinguishing distributional and finite-sample robustness, applies it to k-nearest neighbors, and proposes a modified 1-nearest-neighbor method. Experiments indicate that the proposed robustness properties persist for reasonable data sizes, while several theoretical and methodological questions remain open.

Contributions: The paper introduces a theoretical framework for learning robust to adversarial examples and notions of distributional and finite-sample robustness.The framework is used to study how data properties and sample size relate to robustness.
Contributions: The framework analyzes k-nearest neighbors and motivates a modified 1-nearest-neighbor algorithm with good large-sample robustness properties.The stated guarantee concerns the large sample limit.
Empirical support: Experiments show that the proposed robustness properties are retained for reasonable data sizes.
Open questions: Open questions include the intermediate-k regime, nearest-neighbor algorithms with stronger robustness guarantees, and analogous analyses for other supervised methods.The paper describes this work as a first step toward analyzing how training-data size affects robustness.

A.1 Proofs for Constant k

The constant-k proof shows that, under the stated mixed-label conditions, sufficiently large samples contain nearby regions whose k nearest neighbors are unanimously labeled differently. This forces a nearby prediction change and establishes non-robustness.

Robustness implication: Because the two nearby points receive opposite unanimous neighbor labels, one of them must differ from the prediction at x.Thus a point within distance ϵ can always be found with a changed prediction.
Lemma construction: For sufficiently large n, two distinct points x+ and x− within B(x, ϵ) have k nearest neighbors labeled entirely 1 and entirely 0, respectively, with probability at least 1−δ.The proof constructs disjoint neighborhood balls and shows that each contains enough training points, then finds balls with unanimous labels.
Lemma construction: Disjoint neighborhood balls make the labels of the k nearest neighbors associated with different centers independent.
Robustness implication: The proof combines high-probability events for finding an all-1 neighborhood and an all-0 neighborhood.The corresponding points are denoted x+ and x−.

A.2 Theorem and proof for k-nn robustness lower bound.

The robustness lower-bound analysis identifies a robust interior where k-nearest neighbors remain stable when neighborhoods contain enough same-label training points. Under pure-label conditions, the theorem gives high-probability robustness and an associated astuteness lower bound.

Theorem statement: k-NN is inherently non-robust in the low-k regime when η(x) lies in (0,1), but can be robust when η(x) is 0 or 1.
Theorem statement: The r-robust (p, Δ)-interior defines points whose neighborhoods satisfy the required local robustness condition.The supplied theorem discussion distinguishes this robust interior from the low-k mixed-label regime.
Lower-bound proof: Under absolute continuity and η(x)∈{0,1}, fixed-k k-NN is robust at radius r in the robust interior with high probability.The theorem assumes a sufficiently large sample size n0.
Lower-bound proof: Robustness follows when every nearby neighborhood contains at least k training points and more than ⌊k/2⌋ share the classifier’s label.The pure-label condition ensures the label-majority requirement once the sample-count condition holds.
Lower-bound proof: The sample-count condition is obtained by choosing a threshold n that ensures every relevant ball contains enough training points with high probability.The proof uses empirical mass bounds and a threshold derived from the displayed inequalities.
Lower-bound proof: The resulting guarantee states that, with probability at least 1−2δ, robustness is at least r throughout the robust interior.The same high-probability analysis supports a lower bound on astuteness.

A.3.1 Robustness of the Bayes Optimal Classifier

For points in the positive region, the Bayes Optimal classifier preserves its label throughout the stated robustness ball and predicts correctly with probability η(x).

For x in X+, every x′ in B_o(x,r) remains positively classified, so the robustness radius at x is at least r.
At x, the Bayes Optimal classifier predicts the correct label with probability η(x).

A.3.2 Robustness of k-Nearest Neighbor

The k-nearest-neighbor analysis uses uniform convergence over Euclidean balls to establish high-probability robustness and astuteness guarantees under suitable choices of k and margin parameters.

Choosing k_n and Δ_n so that Δ_n→0 and the stated concentration condition holds yields the theorem’s large-sample robustness regime.
With probability at least 1−3δ, k_n-NN has robustness radius r at all x∈X+ under the theorem’s parameter conditions.
With probability at least 1−δ, k_n-NN achieves the theorem’s stated astuteness lower bound under the same parameterization.
The analysis defines J(B)=E[Y·1(X∈B)] and its empirical counterpart to relate local label behavior to neighborhood robustness.
The proof controls empirical quantities uniformly over Euclidean balls using functions with VC dimension at most d+1.

B Proofs from Section 4

The proofs establish robustness guarantees for Algorithm 1 through separated Red points, local training coverage, and majority-label concentration. Experiments illustrate attack behavior on MNIST and show that Robust_1NN retains non-trivial accuracy at attack radius r = 3, while larger perturbations approach human perceptual ambiguity.

Robustness proof: Algorithm 1’s Red points form an r-separated subset of the training set, preventing oppositely labeled Red points from occurring within the relevant neighborhood.This separation underlies the robustness-radius argument for points whose neighborhoods contain a Red training example.
Experiments: Figure 4 compares clean MNIST digit 1 images with direct, white-box kernel, black-box kernel, and black-box neural-net substitute attacks.The evaluation also measures substitute-classifier training accuracy, test accuracy, and agreement with the target classifier.
Robustness proof: A Red point found within B_o(x, τ) gives Algorithm 1 robustness radius at least r − 2τ at x.The guarantee follows because oppositely labeled training points must lie more than 2r away, forcing nearby queries to receive the Red point’s label.
Robustness proof: For suitable local neighborhoods, majority-label concentration implies Algorithm 2 reports the correct label on all relevant training points with probability at least 1 − δ, so those points are marked Red.The argument applies a tail bound to k_n-neighbor votes and then uses a union bound.
Robustness proof: With probability at least 1 − 2δ, Algorithm 1 achieves robustness radius at least r − 2τ on X_R and astuteness at that radius at least E[η(X) · 1(X ∈ X +The theorem combines local sample coverage, robust-interior conditions, Red-point marking, and a union bound.
Experiments: At r = 3, neural-net substitute attacks perturb many pixels and are ineffective against nearest neighbors, while Robust_1NN retains non-trivial classification accuracy despite human-level class ambiguity.The paper cautions that robustness should not be expected for substantially larger attack radii because r = 3 examples are already close to the boundary of human perception.

C.2 Training Subset Selected by Robust_1NN

Robust_1NN removes noisy points between the halfmoons, and increasing the defense radius produces a wider gap between the classes.

Robust_1NN cleans the noisy inter-halfmoon region and creates a gap between the red and blue classes.
The gap width between the halfmoons increases with the defense radius r.
Substitute classifiers are evaluated on training accuracy, test accuracy, and agreement with the target classifier on the test set.
On Halfmoon and MNIST, substitutes achieve high training and test accuracy and agree closely with the target, whereas Abalone emulation is weaker because of higher noise.