# Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 5 Apr 2026.

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

- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Robust regression with covariate filtering: Heavy tails and adversarial contamination](https://mlsanity.com/paper/2009.12976/) (2020)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Robust Regression via Mutivariate Regression Depth](https://mlsanity.com/paper/1702.04656/) (2017)
- [Online Robust Regression via SGD on the l1 loss](https://mlsanity.com/paper/2007.00399/) (2020)
- [Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2306.16352/) (2023)
- [Corrupted Sensing: Novel Guarantees for Separating Structured Signals](https://mlsanity.com/paper/1305.2524/) (2013)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [ERM and RERM are optimal estimators for regression problems when malicious outliers corrupt the labels](https://mlsanity.com/paper/1910.10923/) (2019)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models](https://mlsanity.com/paper/2505.21475/) (2025)
- [Robust estimation algorithms don't need to know the corruption level](https://mlsanity.com/paper/2202.05453/) (2022)

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

- [Algorithms for adaptive and heteroskedastic linear regression at the computational threshold](https://mlsanity.com/paper/2608.18402/) (2026)

## Abstract (arXiv)

We study robust regression under a contamination model in which covariates are clean while the responses may be corrupted in an adaptive manner. Unlike the classical Huber's contamination model, where both covariates and responses may be contaminated and consistent estimation is impossible when the contamination proportion is a non-vanishing constant, it turns out that the clean-covariate setting admits strictly improved statistical guarantees. Specifically, we show that the additional information in the clean covariates can be carefully exploited to construct an estimator that achieves a better estimation rate than that attainable under Huber contamination. In contrast to the Huber model, this improved rate implies consistency even when the contamination is a constant. A matching minimax lower bound is established using Fano's inequality together with the construction of contamination processes that match m> 2 distributions simultaneously, extending the previous two-point lower bound argument in Huber's setting. Despite the improvement over the Huber model from an information-theoretic perspective, we provide formal evidence -- in the form of Statistical Query and Low-Degree Polynomial lower bounds -- that the problem exhibits strong information-computation gaps. Our results strongly suggest that the information-theoretic improvements cannot be achieved by polynomial-time algorithms, revealing a fundamental gap between information-theoretic and computational limits in robust regression with clean covariates.