# On Error and Compression Rates for Prototype Rules

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 16 Jun 2022.

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

- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Rates of Convergence for Nearest Neighbor Classification](https://mlsanity.com/paper/1407.0067/) (2014)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces](https://mlsanity.com/paper/2010.00636/) (2020)
- [Active Nearest-Neighbor Learning in Metric Spaces](https://mlsanity.com/paper/1605.06792/) (2016)
- [Achieving the time of 1-NN, but the accuracy of k-NN](https://mlsanity.com/paper/1712.02369/) (2017)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)
- [Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions](https://mlsanity.com/paper/1705.08184/) (2017)
- [Functions with average smoothness: structure, algorithms, and learning](https://mlsanity.com/paper/2007.06283/) (2020)
- [An adaptive multiclass nearest neighbor classifier](https://mlsanity.com/paper/1804.02756/) (2018)

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

- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)

## Abstract (arXiv)

We study the close interplay between error and compression in the non-parametric multiclass classification setting in terms of prototype learning rules. We focus in particular on a recently proposed compression-based learning rule termed OptiNet (Kontorovich, Sabato, and Urner 2016; Kontorovich, Sabato, and Weiss 2017; Hanneke et al. 2021). Beyond its computational merits, this rule has been recently shown to be universally consistent in any metric instance space that admits a universally consistent rule--the first learning algorithm known to enjoy this property. However, its error and compression rates have been left open. Here we derive such rates in the case where instances reside in Euclidean space under commonly posed smoothness and tail conditions on the data distribution. We first show that OptiNet achieves non-trivial compression rates while enjoying near minimax-optimal error rates. We then proceed to study a novel general compression scheme for further compressing prototype rules that locally adapts to the noise level without sacrificing accuracy. Applying it to OptiNet, we show that under a geometric margin condition, further gain in the compression rate is achieved. Experimental results comparing the performance of the various methods are presented.