Research map / Learning theory and algorithms / Sample complexity
Robust Sparse Regression with Non-Isotropic Designs
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.
Gives polynomial-time estimators for sparse linear regression with oblivious and adaptive adversaries and non-isotropic heavy-tailed designs, using SoS filtering plus weighted l1-penalized Huber loss, achieving O(sqrt(eps)) and o(sqrt(eps)) error.
Problem
Robust sparse linear regression with unknown non-isotropic covariance, under an adaptive adversary corrupting an epsilon-fraction of samples and an oblivious adversary corrupting the noise, for heavy-tailed designs.
Approach
Combines SoS filtering with elastic-constraint relaxations for quartic forms, plus thresholding of heavy-tailed design entries that is treated as additional adversarial corruption, and a novel analysis of weighted l1-penalized Huber loss under two adversaries.
Key results
- Polynomial-time estimator achieves error O(sigma sqrt(epsilon)) with n >= ~k^2 log d / epsilon under bounded 3rd and entrywise 4th moments, removing the dependence on ||beta*||.
- Under certifiable 4th and entrywise 8th moment bounds, an algorithm achieves error O(sigma eps^{3/4}) for Gaussian designs with n >= ~k^4/eps^3, beating sqrt(eps) error.
- Statistical query lower bounds suggest n ~ k^2 is needed for error o(1) and n ~ k^4 for error o(sqrt(eps)) in the Gaussian case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the certifiably bounded fourth-moment algorithm, with the stronger moment assumptions and sample requirement, instead of the third-/fourth-moment algorithm | Proposed robust sparse regression · Robust sparse regression with non-isotropic designs | error: O(\sigma \cdot \sqrt{\epsilon}) -> O(M\cdot \sigma \cdot\epsilon^{3/4} ) | Helped |
Surprising findings
- Thresholding of heavy-tailed design entries can be treated as extra adaptive corruptions, removing the polynomial dependence of sample complexity on the norm of beta*.
Limitations
- Sample complexity for error o(sqrt(eps)) requires certifiable moment bounds and is n ~ k^4/eps^3, with a worse eps-dependence that may be suboptimal.
- Entrywise fourth-moment assumption is not improvable with the current techniques.
- Nearly optimal error O(eps) with poly(k) samples remains open.
Experimental setup
Metrics: estimation error ||Sigma^{1/2}(beta_hat - beta*)|| sample complexity
Baselines: Huber loss with l1 regularizer under adaptive corruption prior robust sparse regression estimators with bounded fourth and eighth moments
Builds on: Huber loss regression with oblivious noise sum-of-squares filtering for robust statistics robust sparse mean estimation with SoS
Closest papers by meaning
- Consistent regression when oblivious outliers overwhelm (ICML 2021 · similarity 0.92)
- Hardness and Algorithms for Robust and Sparse Optimization (ICML 2022 · similarity 0.91)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.90)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.89)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.88)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.87)
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.