# Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2020.

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

- [Universal Online Learning: an Optimistically Universal Learning Rule](https://mlsanity.com/paper/2201.05947/) (2022)
- [Universal Online Learning with Bounded Loss: Reduction to Binary Classification](https://mlsanity.com/paper/2112.14638/) (2021)
- [The Local Approach to Causal Inference under Network Interference](https://mlsanity.com/paper/2105.03810/) (2021)
- [Universal Regression with Adversarial Responses](https://mlsanity.com/paper/2203.05067/) (2022)
- [Adversarial Rewards in Universal Learning for Contextual Bandits](https://mlsanity.com/paper/2302.07186/) (2023)
- [Metric-valued regression](https://mlsanity.com/paper/2202.03045/) (2022)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [Recursive Estimation of Conditional Kernel Mean Embeddings](https://mlsanity.com/paper/2302.05955/) (2023)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [On Rate-Optimal Partitioning Classification from Observable and from Privatised Data](https://mlsanity.com/paper/2312.14889/) (2023)
- [Unifying and extending Precision Recall metrics for assessing generative models](https://mlsanity.com/paper/2405.01611/) (2024)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [Metric space valued Fr'echet regression](https://mlsanity.com/paper/2602.05225/) (2026)
- [Consistency of the k-Nearest Neighbor Regressor under Complex Survey Designs](https://mlsanity.com/paper/2603.17551/) (2026)
- [On public and private binary classification with metric space valued predictors](https://mlsanity.com/paper/2605.31184/) (2026)
- [Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin](https://mlsanity.com/paper/2606.10361/) (2026)

## Abstract (arXiv)

We study universal consistency and convergence rates of simple nearest-neighbor prototype rules for the problem of multiclass classification in metric paces. We first show that a novel data-dependent partitioning rule, named Proto-NN, is universally consistent in any metric space that admits a universally consistent rule. Proto-NN is a significant simplification of OptiNet, a recently proposed compression-based algorithm that, to date, was the only algorithm known to be universally consistent in such a general setting. Practically, Proto-NN is simpler to implement and enjoys reduced computational complexity. We then proceed to study convergence rates of the excess error probability. We first obtain rates for the standard k-NN rule under a margin condition and a new generalized-Lipschitz condition. The latter is an extension of a recently proposed modified-Lipschitz condition from mathbb Rd to metric spaces. Similarly to the modified-Lipschitz condition, the new condition avoids any boundness assumptions on the data distribution. While obtaining rates for Proto-NN is left open, we show that a second prototype rule that hybridizes between k-NN and Proto-NN achieves the same rates as k-NN while enjoying similar computational advantages as Proto-NN. However, as k-NN, this hybrid rule is not consistent in general.