Timezone: »
Poster
Active Nearest-Neighbor Learning in Metric Spaces
Aryeh Kontorovich · Sivan Sabato · Ruth Urner
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. Our algorithm is based on a generalized sample compression scheme and a new label-efficient active model-selection procedure.
Author Information
Aryeh Kontorovich (Ben Gurion University)
Sivan Sabato (Ben-Gurion University of the Negev)
Ruth Urner (MPI Tuebingen)
More from the Same Authors
-
2021 : Learning Losses for Strategic Classification »
Tosca Lechner · Ruth Urner -
2021 : Learning Losses for Strategic Classification »
Tosca Lechner · Ruth Urner -
2021 : Implications of Modeled Beliefs for Algorithmic Fairness in Machine Learning »
Ruth Urner · Jeff Edmonds · Karan Singh -
2021 Poster: Dimension-free empirical entropy estimation »
Doron Cohen · Aryeh Kontorovich · Aaron Koolyk · Geoffrey Wolfer -
2021 Poster: A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering »
Tom Hess · Michal Moshkovitz · Sivan Sabato -
2020 Poster: Learning discrete distributions with infinite support »
Doron Cohen · Aryeh Kontorovich · Geoffrey Wolfer -
2019 Poster: Epsilon-Best-Arm Identification in Pay-Per-Reward Multi-Armed Bandits »
Sivan Sabato -
2018 Poster: Learning convex polytopes with margin »
Lee-Ad Gottlieb · Eran Kaufman · Aryeh Kontorovich · Gabriel Nivasch -
2018 Poster: Learning from discriminative feature feedback »
Sanjoy Dasgupta · Sivan Sabato · Nicholas Roberts · Akansha Dey -
2017 Poster: Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions »
Aryeh Kontorovich · Sivan Sabato · Roi Weiss -
2016 Poster: Lifelong Learning with Weighted Majority Votes »
Anastasia Pentina · Ruth Urner -
2015 : On Weight Ratio Estimation for Covariate Shift »
Ruth Urner -
2015 Poster: Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path »
Daniel Hsu · Aryeh Kontorovich · Csaba Szepesvari -
2014 Poster: Active Regression by Stratification »
Sivan Sabato · Remi Munos -
2014 Poster: Near-optimal sample compression for nearest neighbors »
Lee-Ad Gottlieb · Aryeh Kontorovich · Pinhas Nisnevitch -
2014 Poster: Consistency of weighted majority votes »
Daniel Berend · Aryeh Kontorovich -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2013 Poster: Predictive PAC Learning and Process Decompositions »
Cosma Shalizi · Aryeh Kontorovich -
2013 Poster: Auditing: Active Learning with Outcome-Dependent Query Costs »
Sivan Sabato · Anand D Sarwate · Nati Srebro -
2012 Poster: Multiclass Learning Approaches: A Theoretical Comparison with Implications »
Amit Daniely · Sivan Sabato · Shai Shalev-Shwartz -
2012 Spotlight: Multiclass Learning Approaches: A Theoretical Comparison with Implications »
Amit Daniely · Sivan Sabato · Shai Shalev-Shwartz -
2010 Poster: Tight Sample Complexity of Large-Margin Learning »
Sivan Sabato · Nati Srebro · Naftali Tishby