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
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.
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
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
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.