Research map / Learning theory and algorithms / Sample complexity
A Subquadratic Time Algorithm for Robust Sparse Mean Estimation
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 a subquadratic-time (roughly d^{1.62+3/q}) algorithm for robust sparse mean estimation with poly(k, log d, 1/eps) samples by combining stability-based sparse filtering with fast weak-correlation detection, and extends the approach to robust sparse PCA.
Problem
Robust sparse mean estimation of a k-sparse Gaussian mean N(mu, I_d) under eps-strong contamination; prior algorithms need Omega(d^2) time because they use the sample covariance matrix.
Approach
Replace explicit covariance computation with fast detection of weakly correlated coordinate pairs (Valiant-style light-bulb / correlation detection). If many pairs are tau-correlated, a random-sampling check finds a small set of coordinates with large Frobenius norm, which yields a sparse filter; otherwise the problem reduces to dense estimation on few coordinates.
Key results
- Subquadratic runtime d^{1.62+3/q} poly(log d, k^q, 1/eps^q) with n ~ (k^{2q} log d)/eps^{2q} samples achieving error O(eps sqrt(log(1/eps))) for robust sparse mean estimation.
- For constant q > 9 the runtime is d^{2-Omega(1)} poly(k/eps), the first sub-quadratic algorithm with poly(k, log d, 1/eps) samples; as q grows, exponent approaches 1.62.
- Robust sparse PCA gets the first subquadratic runtime d^{1.62+3/q} poly(n) with dimension-independent error sqrt(eps log(1/eps)/eta) in Frobenius norm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use fast correlation detection to avoid explicitly constructing the sample covariance matrix | Robust sparse mean estimation · Gaussian robust sparse mean estimation | runtime: d^2 -> d^{1.62 + \frac{3}{q}} | Helped |
| use fast correlation detection to avoid explicitly constructing the sample covariance matrix | Robust sparse PCA · Robust sparse PCA | runtime: \Omega(d^2) -> d^{1.62 + \frac{3}{q}} | Helped |
Surprising findings
- The sample complexity is polynomially larger than prior works (k^{2q} rather than k^2 log d), a trade-off required by the fast algorithm.
Limitations
- Sample complexity is polynomially larger (k^{2q}/eps^{2q}) than prior poly(k, log d, 1/eps) algorithms with d^2 runtime.
- Robust sparse PCA error is suboptimal by a polynomial factor (eps/eta optimal vs sqrt(eps log(1/eps)/eta) achieved).
- Runtime exponent 1.62 is bounded below by the correlation detection bottleneck; remains above linear time.
Experimental setup
Metrics: l2 estimation error runtime exponent in d sample complexity
Baselines: Diakonikolas et al. spectral sparse mean estimation (d^2 poly(k, log d, 1/eps)) Balakrishnan et al. ellipsoid/SDP-based robust sparse mean estimation coordinate-wise median sample mean with thresholding
Builds on: Valiant light-bulb / fast correlation detection Diakonikolas et al. spectral sparse mean estimation (d^2 runtime) randomized filtering sparse certificate lemma
Closest papers by meaning
- Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering (NeurIPS 2019 · similarity 0.92)
- List-Decodable Sparse Mean Estimation (NeurIPS 2022 · similarity 0.91)
- Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination (ICML 2024 · similarity 0.88)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.87)
- Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination (ICML 2025 · similarity 0.85)
- Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements (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.