Stabilized Nearest Neighbor Classifier and its Statistical Properties

Will Wei Sun, Xingye Qiao, Guang Cheng

Abstract: The stability of statistical analysis is an important indicator for reproducibility, which is one main principle of scientific method. It entails that similar statistical conclusions can be reached based on independent samples from the same underlying population. In this paper, we introduce a general measure of classification instability (CIS) to quantify the sampling variability of the prediction made by a classification method. Interestingly, the asymptotic CIS of any weighted nearest neighbor classifier turns out to be proportional to the Euclidean norm of its weight vector. Based on this concise form, we propose a stabilized nearest neighbor (SNN) classifier, which distinguishes itself from other nearest neighbor classifiers, by taking the stability into consideration. In theory, we prove that SNN attains the minimax optimal convergence rate in risk, and a sharp convergence rate in CIS. The latter rate result is established for general plug-in classifiers under a low-noise condition. Extensive simulated and real examples demonstrate that SNN achieves a considerable improvement in CIS over existing nearest neighbor classifiers, with comparable classification accuracy. We implement the algorithm in a publicly available R package snn.

Introduction

In the quest for higher accuracy, the machine learning community often overlooks stability. A stable classifier should yield similar predictions even when trained on different independent samples from the same underlying population. If a model is highly sensitive to minor sampling variations, its results are difficult to reproduce—a major issue for scientific integrity and user trust. Most existing nearest neighbor methods, like the Optimal Weighted Nearest Neighbor (OWNN), focus strictly on minimizing "regret" (the gap between the model's risk and the theoretical minimum Bayes risk) without considering how much the predictions fluctuate across different training sets.

Measuring Classification Instability (CIS)

The authors formalize Classification Instability (CIS) as the probability that two classifiers, trained on independent and identically distributed (i.i.d.) samples, will disagree on the label of a new observation. A key methodological contribution of this work is the CIS-Weight Link: the proof that for any Weighted Nearest Neighbor (WNN) classifier, the asymptotic CIS is proportional to the Euclidean norm of its weight vector ($\|w\|_2$). This provides a simple geometric target for optimization.

The Stabilized Nearest Neighbor (SNN) Classifier

Building on this link, the authors propose the Stabilized Nearest Neighbor (SNN) algorithm. It is formulated as a constrained optimization problem: minimize the CIS (stability) subject to the constraint that the classification regret (accuracy) remains below a certain threshold.

In theory, SNN attains the minimax optimal convergence rate in regret—meaning it is as accurate as the best possible theoretical models—while also achieving a "sharp" convergence rate in CIS. This allows researchers to navigate the trade-off between being perfectly tuned to a specific dataset and being consistent across datasets via a tuning parameter ($\lambda$).

A major finding of the paper is that stability is often "cheaper" than accuracy. The regret of SNN approaches the optimal regret faster than the instability of other models approaches that of SNN. In practice, this means a massive boost in stability can be gained for a very tiny "price" in accuracy.

The stability-accuracy trade-off curve, showing SNN achieving lower CIS with minimal regret increase.

As shown in the figure above, SNN (represented by the blue triangle) sits on the Pareto front of the trade-off curve, significantly reducing CIS compared to the "min regret" point (red square) while maintaining nearly identical regret levels.

Empirical Performance and Convergence

The authors validated SNN using both controlled simulations (bivariate normal, bimodal, and Toeplitz covariance structures) and real-world benchmarks from the UCI Machine Learning Repository, including Breast Cancer (Wisconsin), Credit Approval, and Haberman’s Survival datasets.

Convergence of Regret and CIS as sample size increases for kNN, OWNN, and SNN.

In all simulations, SNN consistently achieved the lowest CIS compared to standard $k$NN and OWNN. As illustrated in the convergence plots, while all models improve with larger sample sizes ($n$), SNN maintains a distinct advantage in stability (lower CIS) while remaining competitive in regret. Empirical results showed that in high-dimensional scenarios (e.g., $d=10$), SNN can even outperform other methods in both stability and accuracy.

Conclusion and Future Work

The SNN classifier provides a robust framework for prioritizing reproducibility in statistical learning. While the current work focuses on binary classification, future research directions include generalizing SNN to multi-category problems and exploring stability in "divide-and-conquer" big data architectures. The algorithm is currently available for use via the snn package in R.

Summary updated

Abstract

The stability of statistical analysis is an important indicator for reproducibility, which is one main principle of the scientific method. It entails that similar statistical conclusions can be reached based on independent samples from the same underlying population. In this article, we introduce a general measure of classification instability (CIS) to quantify the sampling variability of the prediction made by a classification method. Interestingly, the asymptotic CIS of any weighted nearest neighbor classifier turns out to be proportional to the Euclidean norm of its weight vector. Based on this concise form, we propose a stabilized nearest neighbor (SNN) classifier, which distinguishes itself from other nearest neighbor classifiers, by taking the stability into consideration. In theory, we prove that SNN attains the minimax optimal convergence rate in risk, and a sharp convergence rate in CIS. The latter rate result is established for general plug-in classifiers under a low-noise condition. Extensive simulated and real examples demonstrate that SNN achieves a considerable improvement in CIS over existing nearest neighbor classifiers, with comparable classification accuracy. We implement the algorithm in a publicly available R package snn. Supplementary materials for this article are available online.
BibTeX
@article{sun2014stabilized,
  author = {Will Wei Sun and Xingye Qiao and Guang Cheng},
  title = {{Stabilized Nearest Neighbor Classifier and its Statistical Properties}},
  journal = {Journal of the American Statistical Association},
  year = {2014},
}
Figure