Outlier-robust estimation of a sparse linear model using l₁-penalized huber's M-estimator

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 `₁-penalized Huber's M-estimator based on n samples attains the optimal rate of convergence (s/n)¹/² + (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.