High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
Authors:
- Po-Ling LohPLPo-Ling Loh
- Martin J. WainwrightMWMartin J. Wainwright
Preprint
Abstract
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 dependence, as well. 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 nonconvex, and it is difficult to establish theoretical guarantees on practical algorithms. While our approach also involves optimizing nonconvex programs, we are able to both analyze the statistical error associated with any global optimum, and more surprisingly, to prove that a simple algorithm based on projected gradient descent will converge in polynomial time to a small neighborhood of the set of all global minimizers. On the statistical side, we provide nonasymptotic 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 is guaranteed to converge at a geometric rate to a near-global minimizer. We illustrate these theoretical predictions with simulations, showing close agreement with the predicted scalings.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Reconstruction From Anisotropic Random MeasurementsIEEE Transactions on Information Theory, 2013
- Missing values: sparse inverse covariance estimation and an extension to sparse regressionStatistics and Computing, 2010
- Simultaneous analysis of Lasso and Dantzig selectorThe Annals of Statistics, 2009
- Lasso-type recovery of sparse representations for high-dimensional dataThe Annals of Statistics, 2009
- The sparsity and bias of the Lasso selection in high-dimensional linear regressionThe Annals of Statistics, 2008
- Covariate Selection for Linear Errors-in-Variables Regression ModelsCommunications in Statistics - Theory and Methods, 2007
- High-dimensional graphs and variable selection with the LassoThe Annals of Statistics, 2006
- Polynomial Regression and Estimating Functions in the Presence of Multiplicative Measurement ErrorJournal of the Royal Statistical Society Series B: Statistical Methodology, 1999
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Regression Shrinkage and Selection Via the LassoJournal of the Royal Statistical Society Series B: Statistical Methodology, 1996