Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Not on the map. Why?
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).
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
28 of 50 references.
References · 28
- 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
- 2016Agnostic Estimation of Mean and Covariancecited by 131
- 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
- 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
- 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
- 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
- 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
- 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 50
- 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
- 2015Robust Regression via Hard Thresholdingcited by 39
- 2019Generalized Resilience and Robust Statisticscited by 37
- 2020Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noisecited by 30
16 more
- 2021Learning General Halfspaces with General Massart Noise under the Gaussian Distributioncited by 27
- 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
- 2022Cryptographic Hardness of Learning Halfspaces with Massart Noisecited by 25
- 2019Adaptive Hard Thresholding for Near-optimal Consistent Robust Regressioncited by 23
- 2020Online Robust Regression via SGD on the l1 losscited by 20
- 2024SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptionscited by 13
- 2021Consistent Estimation for PCA and Sparse Regression with Oblivious Outlierscited by 9
- 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
- 2022Higher degree sum-of-squares relaxations robust against oblivious outlierscited by 6
- 2024Optimal estimation of the null distribution in large-scale inferencecited by 6
- 2025A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noisecited by 6
- 2025Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contaminationcited by 6
- 2022SQ Lower Bounds for Learning Single Neurons with Massart Noisecited by 5
- 2023Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noisecited by 5
- 2023Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptionscited by 1
- 2024First Order Stochastic Optimization with Oblivious Noisecited by 1
Built on by
Not cited yet.