# High Dimensional Robust Sparse Regression

arXiv: https://arxiv.org/abs/1805.11643 · HTML: https://mlsanity.com/paper/1805.11643/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2018.

## Built on by (most cited first, 29 of 29)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Robust Imitation Learning from Corrupted Demonstrations](https://mlsanity.com/paper/2201.12594/) (2022)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Robust Methods for High-Dimensional Linear Learning](https://mlsanity.com/paper/2208.05447/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Robust Estimation for Nonparametric Families via Generative Adversarial Networks](https://mlsanity.com/paper/2202.01269/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Robust Stochastic Optimization via Gradient Quantile Clipping](https://mlsanity.com/paper/2309.17316/) (2023)
- [Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination](https://mlsanity.com/paper/2403.10416/) (2024)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [Robust Testing in High-Dimensional Sparse Models](https://mlsanity.com/paper/2205.07488/) (2022)
- [Outlier-robust Estimation of a Sparse Linear Model Using Invexity](https://mlsanity.com/paper/2306.12678/) (2023)
- [A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval](https://mlsanity.com/paper/2409.04733/) (2024)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [Outlier-Robust Diffusion Solvers for Inverse Problems](https://mlsanity.com/paper/2605.09477/) (2026)
- [Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outliers](https://mlsanity.com/paper/2408.01336/) (2024)
- [Solving Sparse & High-Dimensional-Output Regression via Compression](https://mlsanity.com/paper/2410.15762/) (2024)
- [On robust recovery of signals from indirect observations](https://mlsanity.com/paper/2501.01935/) (2025)
- [Lasso and Partially-Rotated Designs](https://mlsanity.com/paper/2505.11093/) (2025)
- [Robust and Sparse Estimation of Unbounded Density Ratio under Heavy Contamination](https://mlsanity.com/paper/2512.09266/) (2025)

## Abstract (arXiv)

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.