Outlier-robust estimation of a sparse linear model using ${\ell }_1$-penalized Huber's $M$-estimator

Abstract

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 ${\ell }_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.

This is a follow up paper of arXiv:1805.08020