mlsanityData to 7 Oct 2026

Distribution-Free Robust Linear Regression

arXiv 2102.12919 ↗First posted 25 Feb 2021math.ST cs.LG stat.MLcited by 19

Not on the map. Why?

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.

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

Builds on

19 of 86 references.

References · 19

  1. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  2. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  3. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  4. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 59
  5. 2013Loss minimization and parameter estimation with heavy tailscited by 50
  6. 2014Learning without Concentrationcited by 50
  7. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  8. 2017Sub-Gaussian estimators of the mean of a random vectorcited by 47
  9. 2014Empirical risk minimization for heavy-tailed lossescited by 37
  10. 2019Exact minimax risk for linear least squares, and the lower tail of sample covariance matricescited by 34
  11. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 31
  12. 2013Empirical entropy, minimax regret and minimax riskcited by 21
7 more
  1. 2014The Sample Complexity of Learning Linear Predictors with the Squared Losscited by 16
  2. 2020Robust k-means Clustering for Distributions with Two Momentscited by 14
  3. 2019Excess risk bounds in robust empirical risk minimizationcited by 9
  4. 2020Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictorscited by 9
  5. 2015On aggregation for heavy-tailed classescited by 7
  6. 2019Affine Invariant Covariance Estimation for Heavy-Tailed Distributionscited by 3
  7. 2020Learning bounded subsets of Lpcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 6; 2024: 1; 2025: 1; 2026: 3.

19 papers.

Sort:

  1. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  2. 2023The SSL Interplay: Augmentations, Inductive Bias, and Generalizationcited by 40
  3. 2022The One-Inclusion Graph Algorithm is not Always Optimalcited by 11
  4. 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
  5. 2023High-Probability Risk Bounds via Sequential Predictorscited by 9
  6. 2021Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizerscited by 8
  7. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
  8. 2023Local Risk Bounds for Statistical Aggregationcited by 3
  9. 2025Regularized least squares learning with heavy-tailed noise is minimax optimalcited by 3
  10. 2023Exploring Local Norms in Exp-concave Statistical Learningcited by 2
  11. 2023Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regressioncited by 2
  12. 2024The Limits of Assumption-free Tests for Algorithm Performancecited by 2
7 more
  1. 2023How many samples are needed to leverage smoothness?cited by 1
  2. 2026Self-Normalized Martingales and Uniform Regret Bounds for Linear Regressioncited by 1
  3. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  4. 2022Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecificationcited by 0
  5. 2022An Efficient Minimax Optimal Estimator For Multivariate Convex Regressioncited by 0
  6. 2026Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregationcited by 0
  7. 2026The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexitycited by 0