Instance optimal adaptive regression in high dimensions
Presenter
October 28, 2008
Keywords:
- High dimensions
MSC:
- 57Q45
Abstract
Joint work with Peter Binev, Ron DeVore,
and Philipp Lamby.
This talk addresses the recovery of functions of a large number of variables from point clouds in the context of supervised learning. Our estimator is based on two conceptional pillars.
First, the notion of sparse occupancy
trees is shown to warrant efficient computations even for a very large number of variables. Second, a properly adjusted adaptive tree-approximation scheme is shown to ensure instance optimal performance.
By this we mean the rapid decay (with increasing sample size) of
the probability that the estimator deviates from
the regression function (in a certain natural norm) by more than
the error of best n-term approximation in the sparse tree setting.