Seminar Details

Seminar Details


Monday

May 7

3:30 pm

Regression with noisy and missing covariates:

Martin Wainwright

Seminar

University of California Berkeley - Statistics and EECS

Prediction problems with noisy or missing covariates arise in many settings (e.g., on-line survey data, sensor failures in imaging, social network analysis). There are a variety of possible methods, including the EM algorithm and variants thereof, but many of them involve estimators based on non-convex optimization, for which rigorous guarantees are difficult to obtain.

We study these issues within the context of high-dimensional sparse linear regression problems. Our main contribution is to propose a simple estimator, based on solving a non-convex quadratic program. We first analyze the statistical error of this method, showing that up to constant factors, any global optimum achieves the minimax optimal rates in different settings. We then turn to the computational
challenge: how to efficiently compute a good approximation to such a global optimum? We prove that in many statistical settings, simple first-order gradient methods will converge rapidly up to the \\emph{statistical error} --- namely, the typical mean-squared error between any global optimum and the true parameter of interest.

Based on joint work with Po-Ling Loh
Pre-print available at:
http://arxiv.org/abs/1109.3714