Research map / Learning theory and algorithms / Sample complexity
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that efficient statistical query algorithms for noiseless linear regression with Gaussian covariates and oblivious additive contamination need VSTAT simulation complexity about sqrt(d)/alpha^2, via an SQ-hard testing problem built on discrete Gaussian contamination.
Problem
Noiseless linear regression with Gaussian covariates under additive oblivious contamination in responses, where the inlier fraction alpha is small. Known efficient algorithms need about d/alpha^2 samples while the information-theoretic rate is d/alpha.
Approach
Choose the contamination as a discrete Gaussian with spacing about alpha (so it has mass at least alpha at zero), show the resulting testing problem is a conditional NGCA instance, and bound the SQ hardness by comparing to a continuous Gaussian contamination counterpart via Hermite analysis and random-projection concentration.
Key results
- Any efficient SQ algorithm for the testing version of oblivious-contamination linear regression needs VSTAT simulation complexity at least about sqrt(d)/alpha^2 (up to polylog factors), or super-polynomial d^{log^2(d/alpha)} queries.
- The hard instances are solvable with O(sqrt(d)/alpha^2) samples, so the lower bound does not match the conjectured d/alpha^2 sample complexity.
- Information-theoretically O(d/alpha) samples suffice for the estimation task.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require an SQ algorithm to solve noiseless linear regression with oblivious contamination | Noiseless linear regression with oblivious contamination, with \rho = \widetilde{\Theta}(\alpha) · Noiseless linear regression with oblivious contamination | VSTAT simulation complexity: at least \widetilde{\Omega}(\sqrt{d}/\alpha^2) | Hurt |
| Use an information-theoretic estimator instead of requiring computational efficiency | Noiseless linear regression with oblivious contamination · Noiseless linear regression with oblivious contamination | sample complexity: O(d/\alpha) vs. \Omega(d/\alpha^2) | Helped |
| Use an inefficient SQ algorithm rather than an efficient SQ algorithm | SQ algorithms for noiseless linear regression with oblivious contamination · Noiseless linear regression with oblivious contamination | VSTAT simulation complexity: \widetilde{O}(d/\alpha^2) vs. \widetilde{O}(d/\alpha) | Helped |
| Solve the constructed hard testing instance with an efficient algorithm | Hard testing instance · Hard testing instance | sample complexity: \widetilde{O}(\sqrt{d}/\alpha^2) | Helped |
Surprising findings
- The hard instances themselves are efficiently solvable with O(sqrt(d)/alpha^2) samples, so the d-dependence of the lower bound is not tight.
Limitations
- Lower bound only for SQ algorithms, not all polynomial-time algorithms.
- Dependence on d is sqrt(d) rather than the conjectured linear d.
- Requires alpha not too tiny (alpha >> d^{-polylog d}) and a specific discrete Gaussian contamination.
Experimental setup
Baselines: efficient estimators with d/alpha^2 samples
Builds on: non-gaussian component analysis SQ lower bounds statistical dimension (SDA) VSTAT oracle
Closest papers by meaning
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.89)
- The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.86)
- Truthful High Dimensional Sparse Linear Regression (NeurIPS 2024 · similarity 0.86)
- Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.85)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.85)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.