# Active Nearest-Neighbor Learning in Metric Spaces

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2016.

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

- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Neural Active Learning Beyond Bandits](https://mlsanity.com/paper/2404.12522/) (2024)
- [Visual Transformer for Task-aware Active Learning](https://mlsanity.com/paper/2106.03801/) (2021)
- [SegCol Challenge: Semantic Segmentation for Tools and Fold Edges in Colonoscopy data](https://mlsanity.com/paper/2412.16078/) (2024)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [Active Nearest Neighbor Regression Through Delaunay Refinement](https://mlsanity.com/paper/2206.08061/) (2022)
- [A Two-Stage Active Learning Algorithm for k-Nearest Neighbors](https://mlsanity.com/paper/2211.10773/) (2022)
- [Nearest Neighbor Classifier with Margin Penalty for Active Learning](https://mlsanity.com/paper/2203.09174/) (2022)
- [Active learning using region-based sampling](https://mlsanity.com/paper/2303.02721/) (2023)
- [Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate](https://mlsanity.com/paper/2610.13442/) (2026)

## Abstract (arXiv)

We propose a pool-based non-parametric active learning algorithm for general metric spaces, called MArgin Regularized Metric Active Nearest Neighbor (MARMANN), which outputs a nearest-neighbor classifier. We give prediction error guarantees that depend on the noisy-margin properties of the input sample, and are competitive with those obtained by previously proposed passive learners. We prove that the label complexity of MARMANN is significantly lower than that of any passive learner with similar error guarantees. MARMANN is based on a generalized sample compression scheme, and a new label-efficient active model-selection procedure.