# Fast and Multiphase Rates for Nearest Neighbor Classifiers

arXiv: https://arxiv.org/abs/2308.08247 · HTML: https://mlsanity.com/paper/2308.08247/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 73 references that are in the map.
- First posted on arXiv 16 Aug 2023.

## Builds on (most cited first, 27 of 27)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Scaling Vision Transformers](https://mlsanity.com/paper/2106.04560/) (2021)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Generalized Random Forests](https://mlsanity.com/paper/1610.01271/) (2016)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Marginal Singularity, and the Benefits of Labels in Covariate-Shift](https://mlsanity.com/paper/1803.01833/) (2018)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression](https://mlsanity.com/paper/1804.09753/) (2018)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Local nearest neighbour classification with applications to semi-supervised learning](https://mlsanity.com/paper/1704.00642/) (2017)
- [On the sample complexity of parameter estimation in logistic regression with normal design](https://mlsanity.com/paper/2307.04191/) (2023)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [On Convergence of Nearest Neighbor Classifiers over Feature Transformations](https://mlsanity.com/paper/2010.07765/) (2020)
- [Functions with average smoothness: structure, algorithms, and learning](https://mlsanity.com/paper/2007.06283/) (2020)
- [Nearly optimal classification for semimetrics](https://mlsanity.com/paper/1502.06208/) (2015)
- [Near-optimal learning with average H"older smoothness](https://mlsanity.com/paper/2302.06005/) (2023)

## Built on by (most cited first, 1 of 1)

- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

We study the scaling of classification error rates with respect to the size of the training dataset. In contrast to classical results where rates are minimax optimal for a problem class, this work starts with the empirical observation that, even for a fixed data distribution, the error scaling can have diverse rates across different ranges of sample size. To understand when and why the error rate is non-uniform, we theoretically analyze nearest neighbor classifiers. We show that an error scaling law can have fine-grained rates: in the early phase, the test error depends polynomially on the data dimension and decreases fast; whereas in the later phase, the error depends exponentially on the data dimension and decreases slowly. Our analysis highlights the complexity of the data distribution in determining the test error. When the data are distributed benignly, we show that the generalization error of nearest neighbor classifier can depend polynomially, instead of exponentially, on the data dimension.