# Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2019.

## Built on by (most cited first, 30 of 31)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (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)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Heavy Lasso: sparse penalized regression under heavy-tailed noise via data-augmented soft-thresholding](https://mlsanity.com/paper/2506.07790/) (2025)
- [Minimax rate of consistency for linear models with missing values](https://mlsanity.com/paper/2202.01463/) (2022)
- [Robust Linear Regression for General Feature Distribution](https://mlsanity.com/paper/2202.02080/) (2022)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [Stochastic Mirror Descent for Large-Scale Sparse Recovery](https://mlsanity.com/paper/2210.12882/) (2022)
- [Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outliers](https://mlsanity.com/paper/2305.18974/) (2023)
- [Outlier-robust Estimation of a Sparse Linear Model Using Invexity](https://mlsanity.com/paper/2306.12678/) (2023)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)
- [Outlier-Robust Diffusion Solvers for Inverse Problems](https://mlsanity.com/paper/2605.09477/) (2026)
- [Adversarial robust weighted Huber regression](https://mlsanity.com/paper/2102.11120/) (2021)
- [Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators](https://mlsanity.com/paper/2303.11233/) (2023)
- [Estimation of sparse linear regression coefficients under L-subexponential covariates](https://mlsanity.com/paper/2304.11958/) (2023)
- [Purification Of Contaminated Convolutional Neural Networks Via Robust Recovery: An Approach with Theoretical Guarantee in One-Hidden-Layer Case](https://mlsanity.com/paper/2407.11031/) (2024)
- [Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outliers](https://mlsanity.com/paper/2408.01336/) (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)

## Abstract (arXiv)

We study the problem of estimating a p-dimensional s-sparse vector in a linear model with Gaussian design and additive noise. In the case where the labels are contaminated by at most o adversarial outliers, we prove that the ℓ1-penalized Huber's M-estimator based on n samples attains the optimal rate of convergence (s/n)1/2 + (o/n), up to a logarithmic factor. For more general design matrices, our results highlight the importance of two properties: the transfer principle and the incoherence property. These properties with suitable constants are shown to yield the optimal rates, up to log-factors, of robust estimation with adversarial contamination.