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

DOI10.1214/12-AOS1018zbMATH Open1257.62063arXiv1109.3714OpenAlexW2099210013MaRDI QIDQ693741FDOQ693741

Authors: Po-Ling Loh, Martin J. Wainwright 

Publication date: 10 December 2012

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

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.

Full work available at URL: https://arxiv.org/abs/1109.3714

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

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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• A Unified Framework for Change Point Detection in High-Dimensional Linear Models
• Learning partial differential equations for biological transport models from noisy spatio-temporal data
• Title not available (Why is that?)
• Greedy algorithms for prediction
• Sparse recovery via nonconvex regularized \(M\)-estimators over \(\ell_q\)-balls
• Robust subspace clustering
• Inference in high dimensional linear measurement error models
• Lasso guarantees for \(\beta \)-mixing heavy-tailed time series
• Balanced estimation for high-dimensional measurement error models
• 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
• On Robustness of Principal Component Regression
• On consistency and sparsity for high-dimensional functional time series with application to autoregressions
• Minimax Optimal Procedures for Locally Private Estimation
• Penalised robust estimators for sparse and high-dimensional linear models
• Structure estimation for discrete graphical models: generalized covariance matrices and their inverses
• Finite sample theory for high-dimensional functional/scalar time series with applications
• Sparse principal component analysis with missing observations
• Optimal Sparse Linear Prediction for Block-missing Multi-modality Data Without Imputation
• Robust inference of risks of large portfolios
• An \(\{\ell_{1},\ell_{2},\ell_{\infty}\}\)-regularization approach to high-dimensional errors-in-variables models
• 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
• Title not available (Why is that?)
• Minimax rate-optimal estimation of high-dimensional covariance matrices with incomplete data
• Lower bounds for finding stationary points I
• Multiple Change Point Detection in Reduced Rank High Dimensional Vector Autoregressive Models
• Sparse linear models and \(l_1\)-regularized 2SLS with high-dimensional endogenous regressors and instruments
• 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
• On the uniform convergence of empirical norms and inner products, with application to causal inference
• Regularized estimation in sparse high-dimensional time series models
• Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error
• Inference for high dimensional linear models with error-in-variables
• On Parameter Estimation for High Dimensional Errors-in-Variables Models
• The generalized equivalence of regularization and min-max robustification in linear mixed models
• Regularized estimation of high‐dimensional vector autoregressions with weakly dependent innovations
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Weighted \(\ell_1\)-penalized corrected quantile regression for high dimensional measurement error models
• \(\ell_{0}\)-penalized maximum likelihood for sparse directed acyclic graphs
• Title not available (Why is that?)
• High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity
• Penalized Estimation and Forecasting of Multiple Subject Intensive Longitudinal Data
• Oracle Inequalities for Local and Global Empirical Risk Minimizers
• Scale calibration for high-dimensional robust regression
• Kernel Knockoffs Selection for Nonparametric Additive Models
• A Tight Bound of Hard Thresholding
• Poisson Regression With Error Corrupted High Dimensional Features
• The landscape of empirical risk for nonconvex losses
• Title not available (Why is that?)
• Estimating the Covariance of Fragmented and Other Related Types of Functional Data
• Estimation of high-dimensional graphical models using regularized score matching
• Performance bounds for parameter estimates of high-dimensional linear models with correlated errors
• Scalable interpretable learning for multi-response error-in-variables regression
• Optimal detection of sparse principal components in high dimension
• Going beyond oracle property: selection consistency and uniqueness of local solution of the generalized linear model
• 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
• High-dimensional regression with potential prior information on variable importance
• Title not available (Why is that?)
• Kernel Ordinary Differential Equations
• D4R: doubly robust reduced rank regression in high dimension
• Are Latent Factor Regression and Sparse Regression Adequate?
• UNIFORM-IN-SUBMODEL BOUNDS FOR LINEAR REGRESSION IN A MODEL-FREE FRAMEWORK
• Bayesian vector heterogeneous autoregressive modelling
• Variable selection for high‐dimensional generalized linear model with block‐missing data
• Multi-Task Learning with High-Dimensional Noisy Images
• Screening Methods for Linear Errors-in-Variables Models in High Dimensions
• Model selection in high-dimensional noisy data: a simulation study
• Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• Robust variable selection under cellwise contamination
• A Sparse Learning Approach to Relative-Volatility-Managed Portfolio Selection
• Nonparametric covariance estimation for mixed longitudinal studies, with applications in midlife women's health
• High-dimensional data segmentation in regression settings permitting temporal dependence and non-Gaussianity
• 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
• Norm statement considered harmful: comment on ‘evolution of unconditional dispersal in periodic environments’
• Nonparametric classification with missing data
• Rejoinder
• Title not available (Why is that?)
• Concentration of measure bounds for matrix-variate data with missing values
• Calibrated zero-norm regularized LS estimator for high-dimensional error-in-variables regression
• The EAS approach for graphical selection consistency in vector autoregression models
• FNETS: Factor-Adjusted Network Estimation and Forecasting for High-Dimensional Time Series
• Optimal nonparametric testing of missing completely at random and its connections to compatibility
• Low-rank matrix estimation via nonconvex optimization methods in multi-response errors-in-variables 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
• 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
• Double bias correction for high-dimensional sparse additive hazards regression with covariate measurement errors
• Linear regression with partially mismatched data: local search with theoretical guarantees
• Preserving privacy between features in distributed estimation
• Analysis of global and local optima of regularized quantile regression in high dimensions: a subgradient approach

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)