Active Nearest-Neighbor Learning in Metric Spaces

Abstract

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.

References in corpus (3)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Fast learning rates in statistical inference through aggregation
• Active Learning on Trees and Graphs

Cited by in corpus (7)

• On the Resistance of Nearest Neighbor to Random Noisy Labels
• Sequential Graph Convolutional Network for Active Learning
• Visual Transformer for Task-aware Active Learning
• Adaptivity to Noise Parameters in Nonparametric Active Learning
• K-NN active learning under local smoothness assumption
• Neural Active Learning with Performance Guarantees
• K-nn active learning under local smoothness condition