High Dimensional Robust Sparse Regression

Abstract

We provide a novel -- and to the best of our knowledge, the first -- algorithm for high dimensional sparse regression with constant fraction of corruptions in explanatory and/or response variables. Our algorithm recovers the true sparse parameters with sub-linear sample complexity, in the presence of a constant fraction of arbitrary corruptions. Our main contribution is a robust variant of Iterative Hard Thresholding. Using this, we provide accurate estimators: when the covariance matrix in sparse regression is identity, our error guarantee is near information-theoretically optimal. We then deal with robust sparse regression with unknown structured covariance matrix. We propose a filtering algorithm which consists of a novel randomized outlier removal technique for robust sparse mean estimation that may be of interest in its own right: the filtering algorithm is flexible enough to deal with unknown covariance. Also, it is orderwise more efficient computationally than the ellipsoid algorithm. Using sub-linear sample complexity, our algorithm achieves the best known (and first) error guarantee. We demonstrate the effectiveness on large-scale sparse regression problems with arbitrary corruptions.

References in corpus (10)

• Optimal Solutions for Sparse Principal Component Analysis
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Robust Regression via Hard Thresholding
• A Tight Bound of Hard Thresholding
• Efficient Algorithms for Outlier-Robust Regression
• Exact recoverability from dense corrupted observations via $L_1$ minimization
• Robust Regression via Mutivariate Regression Depth
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Efficient learning with robust gradient descent

Cited by in corpus (18)

• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Generalized Resilience and Robust Statistics
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• A Unified Approach to Robust Mean Estimation
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Robust and Differentially Private Mean Estimation
• Choosing the Sample with Lowest Loss makes SGD Robust
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Robust Meta-learning for Mixed Linear Regression with Small Batches
• Iterative Least Trimmed Squares for Mixed Linear Regression
• Robust estimation with Lasso when outputs are adversarially contaminated
• Outlier-robust estimation of a sparse linear model using ${\ell }_1$-penalized Huber's $M$-estimator
• Robust Estimation for Random Graphs
• Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
• Robust Structured Statistical Estimation via Conditional Gradient Type Methods
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time