Research map / Learning theory and algorithms / Sample complexity
Robust Sparse Estimation for Gaussians with Optimal Error under Huber 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.
Gives the first sample- and computationally-efficient robust estimators for Gaussian sparse mean estimation, sparse PCA, and sparse linear regression under Huber contamination with optimal O(epsilon) error, via a multidimensional sparse filter.
Problem
Gaussian sparse estimation (mean, PCA, linear regression) under Huber contamination: prior efficient algorithms incur error Omega(eps sqrt(log(1/eps))) rather than the information-theoretic optimal O(eps).
Approach
Extends the dense O(eps)-error multidimensional filter to the sparse regime by filtering along sparse matrices from a sparse Frobenius-norm relaxation, iteratively building a coordinate set H on which a dense estimator is run; for sparse PCA, reduces spike estimation to Gaussian (approximate) sparse mean estimation via conditional distributions.
Key results
- Robust k-sparse mean estimation with n = (k^2 log d + log(1/delta))/eps^2 polylog(1/eps) samples in poly(nd) time achieves l2 error O(eps), versus Omega(eps sqrt(log(1/eps))) for prior efficient algorithms.
- Robust sparse PCA achieves Frobenius error O(eps/rho) with probability 0.9 in poly(nd) time for spike strength rho in (Omega(eps log(1/eps)), 1).
- Sparse linear regression achieves l2 error O(sigma eps) in poly(nd) time with n >= k^2 log d / eps^2 polylog(1/eps) samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace prior efficient sparse mean estimation with sparse multidimensional filtering | Robust sparse mean estimation · Robust sparse mean estimation | ℓ2 error: \Omega(\epsilon \sqrt{\log(1/\epsilon)}) -> O(\epsilon) | Helped |
| Use the proposed sparse PCA reduction to Gaussian mean estimation | Robust sparse PCA · Robust sparse PCA | error: \Omega(\epsilon \sqrt{\log(1/\epsilon)}) -> O(\epsilon/\rho) | Helped |
| Exploit sparsity in robust linear regression | Robust sparse linear regression · Robust sparse linear regression | error: \Omega(\epsilon \sqrt{\log(1/\epsilon)}) -> O(\sigma\epsilon) | Helped |
| Incorporate sparsity instead of using the prior dense regression estimator | Robust linear regression · Robust linear regression | sample complexity: \Omega(d) -> \frac{k^2\log d}{\epsilon^2}\polylog(1/\epsilon) | Helped |
| Use the proposed sparse PCA approximation guarantee rather than guarantees without spike structure | Robust sparse PCA · Robust sparse PCA | approximation ratio: 1 - O(\epsilon \log(1/\epsilon)) -> 1 - O(\epsilon^2/\rho) | Helped |
Surprising findings
- Even dense robust PCA with polynomial time previously lacked an O(eps)-error algorithm; the paper's method provides the first such polynomial-time algorithm.
Limitations
- Results require Gaussian inliers; generic sub-Gaussian distributions incur higher information-theoretic error.
- Sparse PCA guarantee restricted to spike strength rho in (Omega(eps log(1/eps)), 1).
Experimental setup
Metrics: l2 estimation error Frobenius error for PCA sample complexity
Baselines: Prior efficient sparse robust mean estimators with Omega(eps sqrt(log(1/eps))) e Dense robust PCA and quasi-polynomial time O(eps) algorithm Sparse robust linear regression with O(sigma eps log(1/eps)) error
Builds on: dense robust mean estimation with optimal O(eps) error (filtering along multiple sparse robust mean estimation with sqrt(log(1/eps)) error (sparse filter relaxat
Closest papers by meaning
- Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression (NeurIPS 2023 · similarity 0.94)
- Outlier-robust estimation of a sparse linear model using $\ell_1$-penalized Huber's $M$-estimator (NeurIPS 2019 · similarity 0.92)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.90)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.89)
- A Subquadratic Time Algorithm for Robust Sparse Mean Estimation (ICML 2024 · similarity 0.88)
- Robust Estimation Under Heterogeneous Corruption Rates (NeurIPS 2025 · 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.