Aryeh Kontorovich

Prof. Aryeh Kontorovich

orcid

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
8 June 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LGLee-Ad Gottlieb
Lee-Ad Gottlieb
AKAryeh Kontorovich
Aryeh Kontorovich
RKRobert Krauthgamer
Robert Krauthgamer
We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing an approximate Lipschitz extension- the smoothest function consistent with the observed data- after performing structural risk minimization to avoid overfitting. We obtain finite-sample risk bounds with minimal structural and noise assumptions, and a natural runtime-precision tradeoff. The offline (learning) and online (prediction) stages can be solved by convex programming, but this naive approach has runtime complexity O(n 3 ), which is prohibitive for large data sets. We design instead a regression algorithm whose speed and generalization performance depend on the intrinsic dimension of the data, to which the algorithm adapts. While our main innovation is algorithmic, the statistical results may also be of independent

2 April 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LGLee-Ad Gottlieb
Lee-Ad Gottlieb
AKAryeh Kontorovich
Aryeh Kontorovich
PNPinhas Nisnevitch
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 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.

11 October 2011 in Statistics and Computing
Verified
Journal Article
Closed access
PDF file
AKAryeh Kontorovich
Aryeh Kontorovich

1 December 2014 in Journal of Applied Probability
Verified
Journal Article
Closed access
PDF file
AKAryeh Kontorovich
Aryeh Kontorovich
RWRoi Weiss
Roi Weiss
We observe that the technique of Markov contraction can be used to establish measure concentration for a broad class of noncontracting chains. In particular, geometric ergodicity provides a simple and versatile framework. This leads to a short, elementary proof of a general concentration inequality for Markov and hidden Markov chains, which supersedes some of the known results and easily extends to other processes such as Markov trees. As applications, we provide a Dvoretzky-Kiefer-Wolfowitz-type inequality and a uniform Chernoff bound. All of our bounds are dimension-free and hold for countably infinite state spaces.

13 December 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LGLee-Ad Gottlieb
Lee-Ad Gottlieb
EKEran Kaufman
Eran Kaufman
AKAryeh Kontorovich
Aryeh Kontorovich
GNGabriel Nivasch
Gabriel Nivasch
We present an improved algorithm for quasi-properly learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about $t \log t$ halfspaces with constant-size margins in time polynomial in $t$ (where $t$ is the number of halfspaces forming an optimal polyhedron). We also identify distinct generalizations of the notion of margin from hyperplanes to polyhedra and investigate how they relate geometrically; this result may have ramifications beyond the learning setting.

14 October 2022 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
LGLaszlo Gyorfi
Laszlo Gyorfi
AKAryeh Kontorovich
Aryeh Kontorovich
RWRoi Weiss
Roi Weiss
We study the problem of estimating the density f (x) of a random vector X in R d . For a spanning tree T defined on the vertex set {1,..., d }, the tree density fT is a product of bivariate conditional densities. An optimal spanning tree minimizes the Kullback-Leibler divergence between f and fT . From i.i.d. data we identify an optimal tree T * and efficiently construct a tree density estimate fn such that, without any regularity conditions on the density f , one has lim n→∞ ∫| fn (x) – fT* (x)| d x = 0 a.s. For Lipschitz f with bounded support, E {∫| fn (x) – fT* (x)|dx} = O ( n -1/4 ), a dimension-free rate.