# Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 50 references that are in the map.
- First posted on arXiv 12 Oct 2025.

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

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [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)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Robust Regression via Hard Thresholding](https://mlsanity.com/paper/1506.02428/) (2015)
- [Generalized Resilience and Robust Statistics](https://mlsanity.com/paper/1909.08755/) (2019)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression](https://mlsanity.com/paper/1903.08192/) (2019)
- [Online Robust Regression via SGD on the l1 loss](https://mlsanity.com/paper/2007.00399/) (2020)
- [SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions](https://mlsanity.com/paper/2403.04744/) (2024)
- [Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers](https://mlsanity.com/paper/2111.02966/) (2021)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Higher degree sum-of-squares relaxations robust against oblivious outliers](https://mlsanity.com/paper/2211.07327/) (2022)
- [Optimal estimation of the null distribution in large-scale inference](https://mlsanity.com/paper/2401.06350/) (2024)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination](https://mlsanity.com/paper/2502.14772/) (2025)
- [SQ Lower Bounds for Learning Single Neurons with Massart Noise](https://mlsanity.com/paper/2210.09949/) (2022)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions](https://mlsanity.com/paper/2309.11657/) (2023)
- [First Order Stochastic Optimization with Oblivious Noise](https://mlsanity.com/paper/2408.02090/) (2024)

## Abstract (arXiv)

We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d. samples from a distribution (x, y) on ℝd × ℝ with x ~ N(0,Id) and y = x^top β + z, where z is drawn independently of x from an unknown distribution E. Moreover, z satisfies mathbbPE[z = 0] = α>0. The goal is to accurately recover the regressor β to small ℓ2-error. Ignoring computational considerations, this problem is known to be solvable using O(d/α) samples. On the other hand, the best known polynomial-time algorithms require Omega(d/α2) samples. Here we provide formal evidence that the quadratic dependence in 1/α is inherent for efficient algorithms. Specifically, we show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least tildeOmega(d1/2/α2).