High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity

DOI10.1214/12-AOS1018MaRDI QIDQ693741zbMATH OpenOpenAlexFDO

Authors Po-Ling Loh, Martin J. Wainwright

Publication date 10 December 2012

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3714, https://projecteuclid.org/euclid.aos/1346850068

zbMATH Keywords

M-estimationregularizationsparse linear regression

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Linear regression; mixed models (62J05) Numerical optimization and variational techniques (65K10) Estimation in multivariate analysis (62H12) Approximation algorithms (68W25)

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.

Recommendations

• Non-convex projected gradient descent for generalized low-rank tensor regression
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution

Cites work

• scientific article; zbMATH DE number 4088699 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 918103 (Why is no real title available?)
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Atomic Decomposition by Basis Pursuit
• Covariate Selection for Linear Errors-in-Variables Regression Models
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• High dimensional inverse covariance matrix estimation via linear programming
• High-dimensional graphs and variable selection with the Lasso
• High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
• Improved matrix uncertainty selector
• Lasso-type recovery of sparse representations for high-dimensional data
• Missing values: sparse inverse covariance estimation and an extension to sparse regression
• Multiplicative Errors-in-Variables Models with Applications to Recent Data Released by the U.S. Department of Energy
• On the conditions used to prove oracle results for the Lasso
• Polynomial Regression and Estimating Functions in the Presence of Multiplicative Measurement Error
• Reconstruction From Anisotropic Random Measurements
• Restricted eigenvalue properties for correlated Gaussian designs
• Simultaneous analysis of Lasso and Dantzig selector
• Sparse permutation invariant covariance estimation
• Sparse recovery under matrix uncertainty
• The sparsity and bias of the LASSO selection in high-dimensional linear regression

Cited in

(only showing first 100 items - show all)

• High-dimensional regression with potential prior information on variable importance
• An ensemble learning method for variable selection: application to high-dimensional data and missing values
• Rejoinder of ``Estimating structured high-dimensional covariance and precision matrices: optimal rates and adaptive estimation
• An improved algorithm for high-dimensional continuous threshold expectile model with variance heterogeneity
• Adaptive Bayesian SLOPE: Model Selection With Incomplete Data
• Inference for heteroskedastic PCA with missing data
• Kernel Ordinary Differential Equations
• Weighted l₁‐Penalized Corrected Quantile Regression for High‐Dimensional Temporally Dependent Measurement Errors
• A Unified Framework for Change Point Detection in High-Dimensional Linear Models
• Norm statement considered harmful: comment on `Evolution of unconditional dispersal in periodic environments'
• D4R: doubly robust reduced rank regression in high dimension
• Greedy algorithms for prediction
• Sparse recovery via nonconvex regularized \(M\)-estimators over \(\ell_q\)-balls
• Learning partial differential equations for biological transport models from noisy spatio-temporal data
• On parameter estimation for high dimensional errors-in-variables models
• Inference in high dimensional linear measurement error models
• Robust subspace clustering
• Are Latent Factor Regression and Sparse Regression Adequate?
• Non-convex projected gradient descent for generalized low-rank tensor regression
• UNIFORM-IN-SUBMODEL BOUNDS FOR LINEAR REGRESSION IN A MODEL-FREE FRAMEWORK
• Regularized estimation of high-dimensional factor-augmented vector autoregressive (FAVAR) models
• Lasso guarantees for \(\beta \)-mixing heavy-tailed time series
• Balanced estimation for high-dimensional measurement error models
• Variable selection for high‐dimensional generalized linear model with block‐missing data
• Bayesian vector heterogeneous autoregressive modelling
• Model selection in high-dimensional noisy data: a simulation study
• Multi-Task Learning with High-Dimensional Noisy Images
• Screening Methods for Linear Errors-in-Variables Models in High Dimensions
• Rate optimal estimation and confidence intervals for high-dimensional regression with missing covariates
• Confidence sets in sparse regression
• On higher order isotropy conditions and lower bounds for sparse quadratic forms
• Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• On consistency and sparsity for high-dimensional functional time series with application to autoregressions
• Robust variable selection under cellwise contamination
• On Robustness of Principal Component Regression
• Penalised robust estimators for sparse and high-dimensional linear models
• Minimax Optimal Procedures for Locally Private Estimation
• A Sparse Learning Approach to Relative-Volatility-Managed Portfolio Selection
• A tight bound of hard thresholding
• Nonparametric covariance estimation for mixed longitudinal studies, with applications in midlife women's health
• Structure estimation for discrete graphical models: generalized covariance matrices and their inverses
• Finite sample theory for high-dimensional functional/scalar time series with applications
• High-dimensional data segmentation in regression settings permitting temporal dependence and non-Gaussianity
• Sparse principal component analysis with missing observations
• Regularized estimation and testing for high-dimensional multi-block vector-autoregressive models
• On high-dimensional Poisson models with measurement error: hypothesis testing for nonlinear nonconvex optimization
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Robust inference of risks of large portfolios
• An \(\{\ell_{1},\ell_{2},\ell_{\infty}\}\)-regularization approach to high-dimensional errors-in-variables models
• Nonparametric classification with missing data
• Rejoinder
• scientific article; zbMATH DE number 7750672 (Why is no real title available?)
• On two recent nonconvex penalties for regularization in machine learning
• Lasso estimation for spherical autoregressive processes
• Estimating high-dimensional covariance and precision matrices under general missing dependence
• Calibrated zero-norm regularized LS estimator for high-dimensional error-in-variables regression
• Minimax rate-optimal estimation of high-dimensional covariance matrices with incomplete data
• Concentration of measure bounds for matrix-variate data with missing values
• The EAS approach for graphical selection consistency in vector autoregression models
• scientific article; zbMATH DE number 7306869 (Why is no real title available?)
• FNETS: Factor-Adjusted Network Estimation and Forecasting for High-Dimensional Time Series
• Lower bounds for finding stationary points I
• An efficient two step algorithm for high dimensional change point regression models without grid search
• Optimal nonparametric testing of missing completely at random and its connections to compatibility
• Sparse linear models and \(l_1\)-regularized 2SLS with high-dimensional endogenous regressors and instruments
• Multiple Change Point Detection in Reduced Rank High Dimensional Vector Autoregressive Models
• Low-rank matrix estimation via nonconvex optimization methods in multi-response errors-in-variables regression
• Oracle inequalities for local and global empirical risk minimizers
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
• Inference in Approximately Sparse Correlated Random Effects Probit Models With Panel Data
• MEBoost: variable selection in the presence of measurement error
• STRATOS guidance document on measurement error and misclassification of variables in observational epidemiology. II: More complex methods of adjustment and advanced topics
• Fast and Scalable Algorithm for Detection of Structural Breaks in Big VAR Models
• On the uniform convergence of empirical norms and inner products, with application to causal inference
• Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error
• Regularized estimation in sparse high-dimensional time series models
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• L ₀ -regularization for high-dimensional regression with corrupted data
• Sparse Identification and Estimation of Large-Scale Vector AutoRegressive Moving Averages
• Sparse estimation in high-dimensional linear errors-in-variables regression via a covariate relaxation method
• A Note on Cross-Validation for Lasso Under Measurement Errors
• Inference for high dimensional linear models with error-in-variables
• The generalized equivalence of regularization and min-max robustification in linear mixed models
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Regularized estimation of high‐dimensional vector autoregressions with weakly dependent innovations
• Weighted \(\ell_1\)-penalized corrected quantile regression for high dimensional measurement error models
• \(\ell_{0}\)-penalized maximum likelihood for sparse directed acyclic graphs
• Double bias correction for high-dimensional sparse additive hazards regression with covariate measurement errors
• Penalized Estimation and Forecasting of Multiple Subject Intensive Longitudinal Data
• High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
• Optimal sparse linear prediction for block-missing multi-modality data without imputation
• Linear regression with partially mismatched data: local search with theoretical guarantees
• Kernel Knockoffs Selection for Nonparametric Additive Models
• Scale calibration for high-dimensional robust regression
• The landscape of empirical risk for nonconvex losses
• Estimation of high-dimensional graphical models using regularized score matching
• Poisson Regression With Error Corrupted High Dimensional Features
• scientific article; zbMATH DE number 7625194 (Why is no real title available?)
• Estimating the Covariance of Fragmented and Other Related Types of Functional Data

Describes a project that uses

Uses Software

• PDCO

This page was built for publication: High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693741)