# Distribution-Free Robust Linear Regression

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 86 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 19 of 19)

- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Loss minimization and parameter estimation with heavy tails](https://mlsanity.com/paper/1307.1827/) (2013)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [The Sample Complexity of Learning Linear Predictors with the Squared Loss](https://mlsanity.com/paper/1406.5143/) (2014)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Excess risk bounds in robust empirical risk minimization](https://mlsanity.com/paper/1910.07485/) (2019)
- [Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors](https://mlsanity.com/paper/2009.09304/) (2020)
- [On aggregation for heavy-tailed classes](https://mlsanity.com/paper/1502.07097/) (2015)
- [Affine Invariant Covariance Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/1902.03086/) (2019)
- [Learning bounded subsets of Lp](https://mlsanity.com/paper/2002.01182/) (2020)

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

- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [The Limits of Assumption-free Tests for Algorithm Performance](https://mlsanity.com/paper/2402.07388/) (2024)
- [Regularized least squares learning with heavy-tailed noise is minimax optimal](https://mlsanity.com/paper/2505.14214/) (2025)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [How many samples are needed to leverage smoothness?](https://mlsanity.com/paper/2305.16014/) (2023)
- [Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression](https://mlsanity.com/paper/2605.01628/) (2026)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)
- [Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation](https://mlsanity.com/paper/2603.02043/) (2026)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)

## Abstract (arXiv)

We study random design linear regression with no assumptions on the distribution of the covariates and with a heavy-tailed response variable. In this distribution-free regression setting, we show that boundedness of the conditional second moment of the response given the covariates is a necessary and sufficient condition for achieving nontrivial guarantees. As a starting point, we prove an optimal version of the classical in-expectation bound for the truncated least squares estimator due to Gy"orfi, Kohler, Krzy.zak, and Walk. However, we show that this procedure fails with constant probability for some distributions despite its optimal in-expectation performance. Then, combining the ideas of truncated least squares, median-of-means procedures, and aggregation theory, we construct a non-linear estimator achieving excess risk of order d/n with an optimal sub-exponential tail. While existing approaches to linear regression for heavy-tailed distributions focus on proper estimators that return linear functions, we highlight that the improperness of our procedure is necessary for attaining nontrivial guarantees in the distribution-free setting.