mlsanityData to 7 Oct 2026

Robust regression with covariate filtering: Heavy tails and adversarial contamination

arXiv 2009.12976 ↗First posted 27 Sep 2020math.ST cs.LG stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

We study the problem of linear regression where both covariates and responses are potentially (i) heavy-tailed and (ii) adversarially contaminated. Several computationally efficient estimators have been proposed for the simpler setting where the covariates are sub-Gaussian and uncontaminated; however, these estimators may fail when the covariates are either heavy-tailed or contain outliers. In this work, we show how to modify the Huber regression, least trimmed squares, and least absolute deviation estimators to obtain estimators which are simultaneously computationally and statistically efficient in the stronger contamination model. Our approach is quite simple, and consists of applying a filtering algorithm to the covariates, and then applying the classical robust regression estimators to the remaining data. We show that the Huber regression estimator achieves near-optimal error rates in this setting, whereas the least trimmed squares and least absolute deviation estimators can be made to achieve near-optimal error after applying a postprocessing step.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 27 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 15; 2023: 10; 2024: 9; 2025: 5; 2026: 4.

49 papers.

Sort:

By area:

  1. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  2. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  3. 2023A New Approach to Learning Linear Dynamical Systemscited by 23
  4. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  5. 2021Distribution-Free Robust Linear Regressioncited by 19
  6. 2024RobustTSF: Towards Theory and Design of Robust Time Series Forecasting with Anomaliescited by 17
  7. 2021Robust Regression Revisited: Acceleration and Improved Estimation Ratescited by 15
  8. 2023High-dimensional robust regression under heavy-tailed data: Asymptotics and Universalitycited by 15
  9. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  10. 2021Heavy-tailed Streaming Statistical Estimationcited by 10
  11. 2023Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCAcited by 10
  12. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
37 more
  1. 2021Consistent Estimation for PCA and Sparse Regression with Oblivious Outlierscited by 9
  2. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  3. 2021Robust Estimation for Random Graphscited by 8
  4. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  5. 2024Insufficient Statistics Perturbation: Stable Estimators for Private Least Squarescited by 7
  6. 2022Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Modelscited by 6
  7. 2022Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariatescited by 6
  8. 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
  9. 2022Robust Methods for High-Dimensional Linear Learningcited by 5
  10. 2022Efficient List-Decodable Regression using Batchescited by 5
  11. 2022Robust estimation algorithms don't need to know the corruption levelcited by 4
  12. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  13. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  14. 2025High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noisecited by 4
  15. 2022Robust supervised learning with coordinate gradient descentcited by 3
  16. 2022Robust Estimation for Nonparametric Families via Generative Adversarial Networkscited by 3
  17. 2023Linear Regression using Heterogeneous Data Batchescited by 3
  18. 2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
  19. 2024DecoR: Deconfounding Time Series with Robust Regressioncited by 2
  20. 2024Robust Gradient Descent for Phase Retrievalcited by 2
  21. 2025Sample-Optimal Private Regression in Polynomial Timecited by 2
  22. 2022Nearly minimax robust estimator of the mean vector by iterative spectral dimension reductioncited by 1
  23. 2023Robust empirical risk minimization via Newton's methodcited by 1
  24. 2024Robust Sparse Regression with Non-Isotropic Designscited by 1
  25. 2025Linear Regression under Missing or Corrupted Coordinatescited by 1
  26. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
  27. 2022A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance & heterogeneous noisecited by 0
  28. 2022A Bayesian Robust Regression Method for Corrupted Data Reconstructioncited by 0
  29. 2023Robust Mean Estimation Without Moments for Symmetric Distributionscited by 0
  30. 2023The Adaptive τ-Lasso: Robustness and Oracle Propertiescited by 0
  31. 2024Sparse Linear Regression when Noises and Covariates are Heavy-Tailed and Contaminated by Outlierscited by 0
  32. 2024Adaptive and Stratified Subsampling for High-Dimensional Robust Estimationcited by 0
  33. 2025LARP: Learner-Agnostic Robust Data Prefilteringcited by 0
  34. 2025Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contaminationcited by 0
  35. 2026High-Dimensional Gaussian Mean Estimation under Realizable Contaminationcited by 0
  36. 2026Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barrierscited by 0
  37. 2026Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruptioncited by 0