UC San Diego

We consider the problem of nonparametric regression, consisting of learning an arbitrary mapping f : X [arrow left] Y from a data set of (X,Y) pairs in which the Y values are corrupted by noise of mean zero. This statistical task is known to be subject to a so-called "curse of dimension'' : if X is a subset of RD̂, and if the only smoothness assumption on f() is that it satisfies a Lipschitz condition, it is known that any estimator based on n data points will have an error rate (risk) of [Omega](n⁻²/(2+D)). In other words a data size exponential in D is required to approximate f(), which is unfeasible even for relatively small D. Fortunately, high-dimensional data often has low-intrinsic complexity (e.g. manifold data, sparse data) and some nonparametric regressors perform better in such situations. This dissertation presents and analyzes various fast regressors that escape the curse of dimension in situations where data has low- intrinsic complexity. These nonparametric regressors, namely tree and tree-kernel-hybrid regressors, have strong theoretical guarantees which are verifiable on a wide range of real-world data