# Optimal Robust Linear Regression in Nearly Linear Time

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

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

- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications](https://mlsanity.com/paper/2410.21194/) (2024)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Understanding In-Context Learning of Linear Models in Transformers Through an Adversarial Lens](https://mlsanity.com/paper/2411.05189/) (2024)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Kalman Filtering with Adversarial Corruptions](https://mlsanity.com/paper/2111.06395/) (2021)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (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)
- [Robust supervised learning with coordinate gradient descent](https://mlsanity.com/paper/2201.13372/) (2022)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noise](https://mlsanity.com/paper/2209.02856/) (2022)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [Linear Regression under Missing or Corrupted Coordinates](https://mlsanity.com/paper/2509.19242/) (2025)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [High-Dimensional Gaussian Mean Estimation under Realizable Contamination](https://mlsanity.com/paper/2603.16798/) (2026)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)
- [Adversarial robust weighted Huber regression](https://mlsanity.com/paper/2102.11120/) (2021)
- [A Bayesian Robust Regression Method for Corrupted Data Reconstruction](https://mlsanity.com/paper/2212.12787/) (2022)
- [Optimal Rates for Robust Stochastic Convex Optimization](https://mlsanity.com/paper/2412.11003/) (2024)
- [Batch List-Decodable Linear Regression via Higher Moments](https://mlsanity.com/paper/2503.09802/) (2025)
- [On efficient robust regression with subquadratic samples](https://mlsanity.com/paper/2605.18042/) (2026)

## Abstract (arXiv)

We study the problem of high-dimensional robust linear regression where a learner is given access to n samples from the generative model Y = langle X,w^* rangle + ε (with X ∈ ℝd and ε independent), in which an η fraction of the samples have been adversarially corrupted. We propose estimators for this problem under two settings: (i) X is L4-L2 hypercontractive, mathbbE [XX^top] has bounded condition number and ε has bounded variance and (ii) X is sub-Gaussian with identity second moment and ε is sub-Gaussian. In both settings, our estimators: (a) Achieve optimal sample complexities and recovery guarantees up to log factors and (b) Run in near linear time (tildeO(nd / η6)). Prior to our work, polynomial time algorithms achieving near optimal sample complexities were only known in the setting where X is Gaussian with identity covariance and ε is Gaussian, and no linear time estimators were known for robust linear regression in any setting. Our estimators and their analysis leverage recent developments in the construction of faster algorithms for robust mean estimation to improve runtimes, and refined concentration of measure arguments alongside Gaussian rounding techniques to improve statistical sample complexities.