# Online Robust Regression via SGD on the l1 loss

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

## Key facts

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

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

- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [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)
- [Adversarial for Good? How the Adversarial ML Community's Values Impede Socially Beneficial Uses of Attacks](https://mlsanity.com/paper/2107.10302/) (2021)
- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression](https://mlsanity.com/paper/2504.08178/) (2025)
- [Exact Recovery for System Identification with More Corrupt Data than Clean Data](https://mlsanity.com/paper/2305.10506/) (2023)
- [Gradient Aligned Regression via Pairwise Losses](https://mlsanity.com/paper/2402.06104/) (2024)
- [Strategyproof Learning: Building Trustworthy User-Generated Datasets](https://mlsanity.com/paper/2106.02398/) (2021)
- [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)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)
- [Robust Regression via Model Based Methods](https://mlsanity.com/paper/2106.10759/) (2021)
- [An Artificial Neural Network Functionalized by Evolution](https://mlsanity.com/paper/2205.10118/) (2022)
- [A Bayesian Robust Regression Method for Corrupted Data Reconstruction](https://mlsanity.com/paper/2212.12787/) (2022)
- [Online and Offline Robust Multivariate Linear Regression](https://mlsanity.com/paper/2404.19496/) (2024)
- [Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination](https://mlsanity.com/paper/2510.10665/) (2025)
- [Quantile-based Loss Filtering for Outlier-Robust Stochastic Gradient Descent](https://mlsanity.com/paper/2609.13040/) (2026)

## Abstract (arXiv)

We consider the robust linear regression problem in the online setting where we have access to the data in a streaming manner, one data point after the other. More specifically, for a true parameter θ^*, we consider the corrupted Gaussian linear model y = langle x ,  θ^* rangle + varepsilon + b where the adversarial noise b can take any value with probability η and equals zero otherwise. We consider this adversary to be oblivious (i.e., b independent of the data) since this is the only contamination model under which consistency is possible. Current algorithms rely on having the whole data at hand in order to identify and remove the outliers. In contrast, we show in this work that stochastic gradient descent on the ℓ1 loss converges to the true parameter vector at a tildeO( 1 / (1 - η)2 n ) rate which is independent of the values of the contaminated measurements. Our proof relies on the elegant smoothing of the non-smooth ℓ1 loss by the Gaussian data and a classical non-asymptotic analysis of Polyak-Ruppert averaged SGD. In addition, we provide experimental evidence of the efficiency of this simple and highly scalable algorithm.