40 citations · 192 across the 64 of their papers we have counts for
8 papers · 1 filter
Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound
Steve Hanneke, Aryeh Kontorovich
We analyze a family of supervised learning algorithms based on sample compression schemes that are stable, in the sense that removing points from the training set which were not se…
Non-parametric Binary regression in metric spaces with KL loss
Ariel Avital, Klim Efremenko, Aryeh Kontorovich +2
We propose a non-parametric variant of binary regression, where the hypothesis is regularized to be a Lipschitz function taking a metric space to [0,1] and the loss is logarithmic.…
Non-uniform packings
Lee-Ad Gottlieb, Aryeh Kontorovich
We generalize the classical notion of packing a set by balls with identical radii to the case where the radii may be different. The largest number of such balls that fit inside the…
Functions with average smoothness: structure, algorithms, and learning
Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich
We initiate a program of average smoothness analysis for efficiently learning real-valued functions on metric spaces. Rather than using the Lipschitz constant as the regularizer, w…
Learning discrete distributions with infinite support
Doron Cohen, Aryeh Kontorovich, Geoffrey Wolfer
We present a novel approach to estimating discrete distributions with (potentially) infinite support in the total variation metric. In a departure from the established paradigm, we…
On Biased Random Walks, Corrupted Intervals, and Learning Under Adversarial Design
Daniel Berend, Aryeh Kontorovich, Lev Reyzin +1
We tackle some fundamental problems in probability theory on corrupted random processes on the integer line. We analyze when a biased random walk is expected to reach its bottommos…