Timezone: »
Poster
Near-optimal sample compression for nearest neighbors
Lee-Ad Gottlieb · Aryeh Kontorovich · Pinhas Nisnevitch
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 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.
Author Information
Lee-Ad Gottlieb (Ariel University)
Aryeh Kontorovich (Ben Gurion University)
Pinhas Nisnevitch (Ariel University)
More from the Same Authors
-
2023 Poster: Near-optimal learning with average Hölder smoothness »
Guy Kornowski · Aryeh Kontorovich · Steve Hanneke -
2021 Poster: Dimension-free empirical entropy estimation »
Doron Cohen · Aryeh Kontorovich · Aaron Koolyk · Geoffrey Wolfer -
2020 Poster: Learning discrete distributions with infinite support »
Doron Cohen · Aryeh Kontorovich · Geoffrey Wolfer -
2018 Poster: Learning convex polytopes with margin »
Lee-Ad Gottlieb · Eran Kaufman · Aryeh Kontorovich · Gabriel Nivasch -
2017 Poster: Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions »
Aryeh Kontorovich · Sivan Sabato · Roi Weiss -
2016 Poster: Active Nearest-Neighbor Learning in Metric Spaces »
Aryeh Kontorovich · Sivan Sabato · Ruth Urner -
2015 Poster: Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path »
Daniel Hsu · Aryeh Kontorovich · Csaba Szepesvari -
2014 Poster: Consistency of weighted majority votes »
Daniel Berend · Aryeh Kontorovich -
2013 Poster: Predictive PAC Learning and Process Decompositions »
Cosma Shalizi · Aryeh Kontorovich