[Colloquium] TTIC Talks: Samory Kpotufe, Max Planck Institute

[Liv Leader]

When:     Tuesday, January 31 @ 11 a.m.

Where:   TTIC Conference Room #526, 6045 S. Kenwood Avenue, 5th Floor

Who:      Samory Kpotufe, Max Planck Institute

Title:      The curse of dimension in nonparametric regression.

Abstract:
Nonparametric regression consists of learning an arbitrary mapping f:\X to
\Y from a data set of (X,Y) pairs in which the Y values are corrupted by
noise. This statistical task is at the core of many problems in engineering
and the sciences. Unfortunately, it is subject to a so-called "curse of
dimension": if \X is a subset of R^D (i.e. each data point X consists of D
input variables), we might require a number of samples exponential in D in
order to approximate f.

Fortunately, high-dimensional data often has low "intrinsic dimension" due
to irrelevant variables and correlations between variables. Common examples
in machine learning are data that lie near a low-dimensional manifold, and
sparse data. Some nonparametric regressors perform better in such
situations as their risks depend only on the intrinsic dimension of the
data, appropriately formalized. These methods which are "adaptive" to
intrinsic dimension therefore require no dimension reduction!

I will start with a short discussion of some traditional methods (e.g. k-NN
regression, kernel regression) which are adaptive, then move on to
computationally efficient methods which are also adaptive. Such efficient
methods are based on adaptive space partitioning procedures, example of
which is the random projection tree, and tree-kernel hybrids. These
efficient methods have strong theoretical guarantees which are verifiable on
a range of real-world data.

This talk is based on joint-work with Sanjoy Dasgupta and Nakul Verma.

Host: Nati Srebro, nati at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120124/2155b84e/attachment.htm