02/23/2012 - 16:10
02/23/2012 - 17:30
Short Title:
STA/BST 290: Martin Wainwright (UC Berkeley)
Short Desc:
: Sparse and smooth: an optimal convex relaxation for high-dimensional kernel regression

## STATISTICS COLLOQUIUM

Thursday, February 23rd, 2012 at 4.10pm, MSB 1147 (Colloquium Room)

Refreshments: 3.30pm, MSB 1147 (Colloquium Room)

Speaker:  Martin Wainwright (UC Berkeley)

Title:        Sparse and smooth: an optimal convex relaxation for high-dimensional kernel regression

Abstract:  The problem of non-parametric regression is well-known to suffer from a severe curse of dimensionality, in that the required sample size grows exponentially with the dimension $d$.  Consequently, the success of statistical estimation in high dimensions relies on some kind of low-dimensional structure.  This talk focuses on non-parametric estimation within the family of sparse additive models, which consist of sums of univariate functions over $s$ unknown
co-ordinates.

We derive a simple and intuitive convex relaxation for estimating sparse additive models described by reproducing kernel Hilbert spaces, including polynomial fits, splines, Sobolev classes as instances.  The method involves solving a second-order cone program (SOCP), and so is suitable for large-scale problems.  Working within a high-dimensional framework that allows both the dimension $d$ and sparsity $s$ to scale, we derive convergence rates that consist of two terms: a \emph{subset selection term} that captures the difficulty of finding the unknown $s$-sized subset, and an \emph{estimation error} that captures the difficulty of estimation over kernel classes.  Using information-theoretic methods, we derive
matching lower bounds on the minimax risk, showing that the SOCP-based method is optimal.

Based on joint work with Garvesh Raskutti and Bin Yu, UC Berkeley Arxiv paper:  http://arxiv.org/abs/1008.3654