# Consistent regression when oblivious outliers overwhelm

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2020.

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

- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [DecoR: Deconfounding Time Series with Robust Regression](https://mlsanity.com/paper/2406.07005/) (2024)
- [On the Robustness of Kernel Ridge Regression Using the Cauchy Loss Function](https://mlsanity.com/paper/2503.20120/) (2025)
- [Robust Linear Regression for General Feature Distribution](https://mlsanity.com/paper/2202.02080/) (2022)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Outlier-Robust Diffusion Solvers for Inverse Problems](https://mlsanity.com/paper/2605.09477/) (2026)
- [Robust Mean Estimation Without Moments for Symmetric Distributions](https://mlsanity.com/paper/2302.10844/) (2023)

## Abstract (arXiv)

We consider a robust linear regression model y=Xβ^* + η, where an adversary oblivious to the design X∈ ℝn× d may choose η to corrupt all but an α fraction of the observations y in an arbitrary way. Prior to our work, even for Gaussian X, no estimator for β^* was known to be consistent in this model except for quadratic sample size n gtrsim (d/α)2 or for logarithmic inlier fraction α≥ 1/log n. We show that consistent estimation is possible with nearly linear sample size and inverse-polynomial inlier fraction. Concretely, we show that the Huber loss estimator is consistent for every sample size n= ω(d/α2) and achieves an error rate of O(d/α2n)1/2. Both bounds are optimal (up to constant factors). Our results extend to designs far beyond the Gaussian case and only require the column span of X to not contain approximately sparse vectors). (similar to the kind of assumption commonly made about the kernel space for compressed sensing). We provide two technically similar proofs. One proof is phrased in terms of strong convexity, extending work of [Tsakonas et al.'14], and particularly short. The other proof highlights a connection between the Huber loss estimator and high-dimensional median computations. In the special case of Gaussian designs, this connection leads us to a strikingly simple algorithm based on computing coordinate-wise medians that achieves optimal guarantees in nearly-linear time, and that can exploit sparsity of β^*. The model studied here also captures heavy-tailed noise distributions that may not even have a first moment.