Near-Optimal Sample Compression for Nearest Neighbors

We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our performance bound is nearly optimal. Our result yields new insight into margin-based nearest neighbor classification in metric spaces and allows us to significantly sharpen and simplify existing bounds. Some encouraging empirical results are also presented.

• Publication year

  2014

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2014-04-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2018.2822267arXiv 1404.3368
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Foundations of Machine Learning

  2021cited by this paper
• Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions

  2017cited by this paper
• Active Nearest-Neighbor Learning in Metric Spaces

  2016cited by this paper
• Nearly Optimal Classification for Semimetrics

  2015cited by this paper
• Rates of Convergence for Nearest Neighbor Classification

  2014cited by this paper
• A Bayes consistent 1-NN classifier

  2014cited by this paper
• Understanding Machine Learning - From Theory to Algorithms

  2014influential reference
• Maximum Margin Multiclass Nearest Neighbors

  2014cited by this paper
• Efficient Classification for Metric Data

  2013cited by this paper
• Adaptive metric dimensionality reduction

  2013cited by this paper
• Proximity Algorithms for Nearly Doubling Spaces

  2013cited by this paper
• Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

  2011cited by this paper
• Proximity Algorithms for Nearly-Doubling Spaces

  2010cited by this paper
• NP-completeness of the problem of prototype selection in the nearest neighbor method

  2010cited by this paper
• Using the doubling dimension to analyze the generalization of learning algorithms

  2009cited by this paper
• Learning the set covering machine by bound minimization and margin-sparsity trade-off

  2009cited by this paper
• Learnability and the doubling dimension

  2006cited by this paper
• Cover trees for nearest neighbor

  2006cited by this paper
• Searching dynamic point sets in spaces with bounded doubling dimension

  2006cited by this paper
• Fast condensed nearest neighbor rule

  2005cited by this paper
• PAC-Bayesian Compression Bounds on the Prediction Error of Learning Algorithms for Classification

  2005influential reference
• Navigating nets: simple algorithms for proximity search

  2004cited by this paper
• On the hardness of approximating label-cover

  2004influential reference
• Distance-Based Classification with Lipschitz Functions

  2004cited by this paper
• Fast construction of nets in low dimensional metrics, and their applications

  2004cited by this paper
• The Set Covering Machine

  2003cited by this paper
• Fast minimization of structural risk by nearest neighbor rule

  2003cited by this paper
• Relating Data Compression and Learnability

  2003cited by this paper
• Open Problems in Geometric Methods for Instance-Based Learning

  2002cited by this paper
• Reduction Techniques for Instance-Based Learning Algorithms

  2000cited by this paper
• Generalization Performance of Support Vector Machines and Other Pattern Classifiers

  1999cited by this paper
• The Reduced Nearest Neighbor Rule

  1998cited by this paper
• Asymptotic expansions of the k nearest neighbor risk

  1998cited by this paper
• A Probabilistic Theory of Pattern Recognition

  1996cited by this paper
• An algorithm for approximate closest-point queries

  1994cited by this paper
• On the Strong Universal Consistency of Nearest Neighbor Regression Function Estimates

  1994cited by this paper
• Scale-sensitive dimensions, uniform convergence, and learnability

  1993cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• Nearest neighbor problems

  1991cited by this paper
• Discriminatory Analysis - Nonparametric Discrimination: Consistency Properties

  1989cited by this paper
• Quantifying Inductive Bias: AI Learning Algorithms and Valiant's Learning Framework

  1988cited by this paper
• A theory of the learnable

  1984cited by this paper
• An algorithm for a selective nearest neighbor decision rule (Corresp.)

  1975cited by this paper
• The reduced nearest neighbor rule (Corresp.)

  1972cited by this paper
• The condensed nearest neighbor rule (Corresp.)

  1968cited by this paper
• Nearest neighbor pattern classification

  1967cited by this paper
• The Condensed Nearest Neighbor Rule

  1967cited by this paper
• Journal of Graph Algorithms and Applications Low-distortion Embeddings of Trees

  year unknowncited by this paper

• A Differentiable Adversarial Framework for Task-Aware Data Subsampling

  2026cites this paper
• Sample Compression Scheme Reductions

  2024cites this paper
• Boolean Nearest Neighbor Language in the Knowledge Compilation Map

  2024cites this paper
• The Minimum Consistent Spanning Subset Problem on Trees

  2024cites this paper
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning

  2023cites this paper
• Weighted Distance Nearest Neighbor Condensing

  2023cites this paper
• On Error and Compression Rates for Prototype Rules

  2022influential citation
• Enhanced Nearest Neighbor Classification for Crowdsourcing

  2022cites this paper
• Refined Lower Bounds for Nearest Neighbor Condensation

  2022cites this paper
• Federated Nearest Neighbor Classification with a Colony of Fruit-Flies: With Supplement

  2021cites this paper
• Optimal Binary Classification Beyond Accuracy

  2021cites this paper
• A Theory of PAC Learnability of Partial Concept Classes

  2021cites this paper
• Non-uniform packings

  2020cites this paper
• Coresets for the Nearest-Neighbor Rule

  2020cites this paper
• When are Non-Parametric Methods Robust?

  2020cites this paper
• Multiclass Classification via Class-Weighted Nearest Neighbors

  2020cites this paper
• The Inverse Voronoi Problem in Graphs I: Hardness

  2020cites this paper
• Social Distancing is Good for Points too!

  2020influential citation
• Functions with average smoothness: structure, algorithms, and learning

  2020cites this paper
• Research on Matching Method of Ocean Observation Data Based on DC-WKNN Algorithm

  2020cites this paper
• Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound

  2020cites this paper
• Statistical Guarantees of Distributed Nearest Neighbor Classification

  2020cites this paper
• KNN Classification With One-Step Computation

  2020cites this paper
• Complexity of Classification Problems

  2019cites this paper
• Metric learning with Lipschitz continuous functions

  2019cites this paper
• Fast and Bayes-consistent nearest neighbors

  2019cites this paper
• Natively Interpretable Machine Learning and Artificial Intelligence: Preliminary Results and Future Directions

  2019cites this paper
• Generalization Error Analysis of Quantized Compressive Learning

  2019cites this paper
• Classification in asymmetric spaces via sample compression

  2019cites this paper
• Guarantees on Nearest-Neighbor Condensation heuristics

  2019influential citation
• Adversarial Examples for Non-Parametric Methods: Attacks, Defenses and Large Sample Limits

  2019cites this paper
• Universal Bayes Consistency in Metric Spaces

  2019cites this paper
• Robustness for Non-Parametric Classification: A Generic Attack and Defense

  2019cites this paper
• Robust randomized optimization with k nearest neighbors

  2019cites this paper
• On the Minimum Consistent Subset Problem

  2018cites this paper
• Agnostic Sample Compression Schemes for Regression

  2018cites this paper
• Sample Compression for Real-Valued Learners

  2018cites this paper
• L G ] 2 1 M ay 2 01 8 A New Lower Bound for Agnostic Learning with Sample Compression Schemes

  2018cites this paper
• A New Lower Bound for Agnostic Learning with Sample Compression Schemes

  2018cites this paper
• Nearest Neighbor Condensation with Guarantees

  2018cites this paper
• A Sharp Lower Bound for Agnostic Learning with Sample Compression Schemes

  2018cites this paper
• The inverse Voronoi problem in graphs

  2018cites this paper
• Distributed Nearest Neighbor Classification.

  2018cites this paper
• On Communication Complexity of Classification Problems

  2017cites this paper
• Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions

  2017influential citation
• Active Nearest-Neighbor Learning in Metric Spaces

  2016influential citation
• Nearly Optimal Classification for Semimetrics

  2015cites this paper
• Adaptive metric dimensionality reduction

  2013influential citation
• University of Birmingham Refined Lower Bounds for Nearest Neighbor Condensation

  year unknowncites this paper