Timezone: »

 
Oral
High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity
Po-Ling Loh · Martin J Wainwright

Tue Dec 13 08:10 AM -- 08:30 AM (PST) @
in Oral Session 5 »

Although the standard formulations of prediction problems involve fully-observed and noiseless data drawn in an i.i.d. manner, many applications involve noisy and/or missing data, possibly involving dependencies. We study these issues in the context of high-dimensional sparse linear regression, and propose novel estimators for the cases of noisy, missing, and/or dependent data. Many standard approaches to noisy or missing data, such as those using the EM algorithm, lead to optimization problems that are inherently non-convex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing non-convex programs, we are able to both analyze the statistical error associated with any global optimum, and prove that a simple projected gradient descent algorithm will converge in polynomial time to a small neighborhood of the set of global minimizers. On the statistical side, we provide non-asymptotic bounds that hold with high probability for the cases of noisy, missing, and/or dependent data. On the computational side, we prove that under the same types of conditions required for statistical consistency, the projected gradient descent algorithm will converge at geometric rates to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing agreement with the predicted scalings.

Author Information

Po-Ling Loh (University of Wisconsin - Madison)
Martin J Wainwright (UC Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors