# Robust Regression via Hard Thresholding

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2015.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [BARACK: Partially Supervised Group Robustness With Guarantees](https://mlsanity.com/paper/2201.00072/) (2021)
- [Convergence of uncertainty estimates in Ensemble and Bayesian sparse model discovery](https://mlsanity.com/paper/2301.12649/) (2023)
- [Making Paper Reviewing Robust to Bid Manipulation Attacks](https://mlsanity.com/paper/2102.06020/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [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)
- [Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares](https://mlsanity.com/paper/2404.15409/) (2024)
- [Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models](https://mlsanity.com/paper/2206.04777/) (2022)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Learning Deep Neural Networks under Agnostic Corrupted Supervision](https://mlsanity.com/paper/2102.06735/) (2021)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Linear Regression using Heterogeneous Data Batches](https://mlsanity.com/paper/2309.01973/) (2023)
- [SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning](https://mlsanity.com/paper/2310.04918/) (2023)
- [DecoR: Deconfounding Time Series with Robust Regression](https://mlsanity.com/paper/2406.07005/) (2024)
- [Heavy Lasso: sparse penalized regression under heavy-tailed noise via data-augmented soft-thresholding](https://mlsanity.com/paper/2506.07790/) (2025)
- [Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach](https://mlsanity.com/paper/2102.05954/) (2021)
- [Analysis and Detectability of Offline Data Poisoning Attacks on Linear Dynamical Systems](https://mlsanity.com/paper/2211.08804/) (2022)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [Robust Sparse Regression with Non-Isotropic Designs](https://mlsanity.com/paper/2410.23937/) (2024)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)
- [Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements](https://mlsanity.com/paper/2604.11584/) (2026)
- [AGGLIO: Global Optimization for Locally Convex Functions](https://mlsanity.com/paper/2111.03932/) (2021)
- [Mutual Information Learned Regressor: an Information-theoretic Viewpoint of Training Regression Systems](https://mlsanity.com/paper/2211.12685/) (2022)
- [Corruption-tolerant Algorithms for Generalized Linear Models](https://mlsanity.com/paper/2212.05430/) (2022)

## Abstract (arXiv)

We study the problem of Robust Least Squares Regression (RLSR) where several response variables can be adversarially corrupted. More specifically, for a data matrix X ∈ Rp x n and an underlying model w*, the response vector is generated as y = X'w* + b where b ∈ Rn is the corruption vector supported over at most C.n coordinates. Existing exact recovery results for RLSR focus solely on L1-penalty based convex formulations and impose relatively strict model assumptions such as requiring the corruptions b to be selected independently of X. In this work, we study a simple hard-thresholding algorithm called TORRENT which, under mild conditions on X, can recover w* exactly even if b corrupts the response variables in an adversarial manner, i.e. both the support and entries of b are selected adversarially after observing X and w*. Our results hold under deterministic assumptions which are satisfied if X is sampled from any sub-Gaussian distribution. Finally unlike existing results that apply only to a fixed w*, generated independently of X, our results are universal and hold for any w* ∈ Rp. Next, we propose gradient descent-based extensions of TORRENT that can scale efficiently to large scale problems, such as high dimensional sparse recovery and prove similar recovery guarantees for these extensions. Empirically we find TORRENT, and more so its extensions, offering significantly faster recovery than the state-of-the-art L1 solvers. For instance, even on moderate-sized datasets (with p = 50K) with around 40% corrupted responses, a variant of our proposed method called TORRENT-HYB is more than 20x faster than the best L1 solver.