Rates of Convergence for Large-scale Nearest Neighbor Classification

Xingye Qiao, Jiexin Duan, Guang Cheng

Nearest Neighbor (NN) methods are beloved in machine learning for their simplicity and lack of a complex "training" phase. However, they suffer from a major bottleneck: they are memory-based. To classify a single point, a standard $k$-Nearest Neighbor ($k$NN) algorithm needs to scan the entire training set. In the era of "Big Data," loading billions of data points into a single machine's memory is often impossible.

Beyond hardware limits, modern data collection introduces issues of privacy and communication. If data is collected across different hospitals or banks, these institutions might be legally restricted from sharing raw data with a central server.

To tackle these challenges, researchers have introduced bigNN, a distributed "divide-and-conquer" framework for $k$NN classification designed for massive datasets. By splitting data across multiple machines and aggregating local predictions via majority voting, bigNN achieves the same optimal convergence rates as an "oracle" $k$NN (one with access to the entire dataset at once) while significantly reducing computation time and memory overhead.

The bigNN Framework

The authors propose two primary approaches to scale $k$NN:

  1. bigNN (The Base Framework): The total dataset ($N$) is divided into $s$ subsamples of size $n$, with each subsample living on a different "local" machine. When a query comes in, each machine finds the $k$ nearest neighbors within its own local data and makes a prediction. These local predictions are sent to a central hub, which uses majority voting to make the final classification.
  2. Denoised bigNN (The Accelerator): Standard $k$NN is notoriously slow at "prediction time." To fix this, the authors use a "denoising" technique. They pre-label the training data using the bigNN classifier. At prediction time, they only perform a 1-Nearest Neighbor search against a small, pre-processed subsample. This effectively shifts the computational burden from the prediction phase to a one-time pre-training phase.

Key Insights and Theoretical Guarantees

The core of the paper is a theoretical proof showing that if you choose the number of neighbors ($k$) and the number of partitions ($s$) correctly, the "regret" (excess risk) of this distributed system vanishes at the same rate as the best possible centralized $k$NN.

  • The "No-Loss" Property: The most surprising insight is that "divide-and-conquer" doesn't compromise accuracy. As long as the number of divisions ($s$) doesn't grow too fast relative to the total data size, the distributed ensemble is statistically as powerful as the oracle.
  • The Scaling of $k$: In a standard $k$NN, $k$ usually scales with the total sample size $N$. In bigNN, the optimal $k$ must scale with both $N$ and the number of partitions $s$. Local machines should use a "suboptimal" $k$ locally to ensure the "ensemble" becomes optimal after voting.
  • The Partition Limit: There is a theoretical "speed limit" for how much you can subdivide data. If you split the data into too many tiny pieces (high $s$), the "bias" of the local classifiers becomes too high to be corrected by the majority vote.
  • Privacy by Design: Because only the final class predictions (0 or 1) are transmitted to the central hub—not the raw data or even the local distances—the method is inherently more privacy-preserving than centralized approaches.

Empirical Results and Performance

The authors validated their theoretical findings using seven benchmark datasets from the UCI Machine Learning Repository, including high-energy physics data (SUSY) and handwritten digit recognition (Gisette).

Log-log plots of Regret and Classification Instability (CIS) against sample size N.
  • Theoretical Optimality: The authors proved that bigNN achieves a convergence rate of $O(N^{-\alpha(\beta+1)/(2\alpha+1)})$, which matches the minimax optimal rate for $k$NN.
  • Stability: The "Classification Instability" (CIS) of bigNN—a measure of how much the prediction changes if the training data is slightly perturbed—also matches the oracle rate, proving the method is robust.
Fitted vs. Observed values for log(regret) and log(CIS), demonstrating the accuracy of the theoretical bounds.
  • Massive Speedups: In empirical tests on the SUSY dataset (5 million observations), bigNN was up to 88 times faster than the oracle $k$NN while maintaining nearly identical error rates.
  • Denoising Efficiency: The "Denoised bigNN" achieved a 10x speedup over the standard bigNN at prediction time with negligible loss in accuracy, making it highly viable for real-time applications.

Limitations and Future Work

While the authors established that the number of partitions $s$ cannot grow too fast, finding the exact "sharp" upper limit for $s$ remains an open theoretical question. Furthermore, the current model assumes data is evenly distributed ($N=sn$). Future work could address "unbalanced" distributed systems where different machines have vastly different amounts or types of data. Finally, exploring the impact of this divide-and-conquer strategy on other popular algorithms like Support Vector Machines (SVM) or Random Forests would be a valuable next step.

Summary updated

Abstract

Nearest neighbor is a popular class of classification methods with many desirable properties. For a large data set which cannot be loaded into the memory of a single machine due to computation, communication, privacy, or ownership limitations, we consider the divide and conquer scheme: the entire data set is divided into small subsamples, on which nearest neighbor predictions are made, and then a final decision is reached by aggregating the predictions on subsamples by majority voting. We name this method the big Nearest Neighbor (bigNN) classifier, and provide its rates of convergence under minimal assumptions, in terms of both the excess risk and the classification instability, which are proven to be the same rates as the oracle nearest neighbor classifier and cannot be improved. To significantly reduce the prediction time that is required for achieving the optimal rate, we also consider the pre-training acceleration technique applied to the bigNN method, with proven convergence rate. We find that in the distributed setting, the optimal choice of the neighbor $k$ should scale with both the total sample size and the number of partitions, and there is a theoretical upper limit for the latter. Numerical studies have verified the theoretical findings.
BibTeX
@inproceedings{qiao2019rates,
  author = {Xingye Qiao and Jiexin Duan and Guang Cheng},
  title = {{Rates of Convergence for Large-scale Nearest Neighbor Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure