High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity

By Po-Ling Loh, Martin J. Wainwright. Neural Information Processing Systems, 2011

594 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/892fd05687f032b93cda33ed9a0b3b8c5435b54f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima (2013, background): “Following Loh and Wainwright [6], assume we instead observe pairs {(zi, yi)}i=1, where the zi’s are systematically corrupted versions of the corresponding xi’s.”
MAXIMUM LIKELIHOOD FOR SPARSE DIRECTED ACYCLIC GRAPHS (2013, methodology): “sequence of sub-Gaussian vectors as defined in Loh and Wainwright (2012) and replace Theorem 7.”
Confidence sets in sparse regression (2012, unknown): “Following an idea of Loh and Wainwright (2012), we then have sup θ ′∈BS ∣∣(θ ′ − θ lS(θ ′))T (θ ′ − θ lS(θ ′))∣∣ ≤ δ2 sup ϑ∈BS ϑT ϑ and also that supθ ′∈BS |(θ ′ − θ lS(θ ′))T θ | ≤ δ supϑ∈BS |ϑT ϑ |.”
Efficient Algorithms for Outlier-Robust Regression (2018, background): “y independent) noise parameter e and unknown weight vector θ ∈ ’d. For example, the recovery properties of LASSO and related algorithms in this context have been intensely studied (see e.g., [XCM10], [LW11]). For more challenging noisemodels,recentworkdue toDu,Balakrishnan, and Singh[DBS17] studiess”
The landscape of empirical risk for nonconvex losses (2016, background): “ gradient descent converges to such a neighborhood of the true θ0 within a small number of iterations. Results of this type have been proved, among others, for linear regression with noisy covariates [LW12], generalized linear models with non-convex regularizers [LW13], robust regression [LM13], and”
Fast global convergence of gradient methods for high-dimensional statistical recovery (2011, background): “, [45, 24, 19]), and SDP relaxations for various problems, including sparse PCA and low-rank matrix estimation (e.”
Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates (2013, background): “Some recent work [40] shows that certain types of non-convex programs arising from errors-in-variables can be solved efficiently; extending these types of results to private settings could be interesting.”
Robust Logistic Regression and Classification (2014, methodology): “We say that a random matrix and (2) for any unit vector u ∈ R p , the random variable The above sub-Gaussian random variables have several nice concentration properties, one of which is stated in the following Lemma [12].”
A unifying approach for doubly-robust $\ell_1$ regularized estimation of causal contrasts (2019, background): “Ning et al. (2018) propose estimators of the nuisance parameters that, like Tan’s and ours, are noniterative and based on solving convex optimization problems.”
$\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs (2012, background): “We assume that the rows of X form an i.i.d. sequence of sub-Gaussian vectors as deﬁned in Loh and Wainwright (2012) and replace Theorem 7.3 by their Lemma 15.”
Network Reconstruction From High-Dimensional Ordinary Differential Equations (2016, methodology): “We extend the recent work of Loh and Wainwright (2012) for lasso regression; related results can be found in Ma and Li (2010) and Rosenbaum and Tsybakov (2010).”
Challenges of Big Data Analysis (2013, unknown): “The most striking feature of cloud computing is its elasticity andabilitytoscaleupanddown,whichmakesitsuit-ableforstoringandprocessingBigData.”