# A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation

arXiv: https://arxiv.org/abs/2403.04726 · HTML: https://mlsanity.com/paper/2403.04726/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 28 references that are in the map.
- First posted on arXiv 7 Mar 2024.

## Builds on (most cited first, 18 of 18)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection](https://mlsanity.com/paper/1906.11366/) (2019)
- [High-Dimensional Robust Mean Estimation in Nearly-Linear Time](https://mlsanity.com/paper/1811.09380/) (2018)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering](https://mlsanity.com/paper/1911.08085/) (2019)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Robust estimation via generalized quasi-gradients](https://mlsanity.com/paper/2005.14073/) (2020)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [An Illuminating Algorithm for the Light Bulb Problem](https://mlsanity.com/paper/1810.06740/) (2018)
- [A faster subquadratic algorithm for finding outlier correlations](https://mlsanity.com/paper/1510.03895/) (2015)
- [Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time](https://mlsanity.com/paper/1606.05608/) (2016)

## Built on by (most cited first, 1 of 1)

- [Revisiting Active Sequential Prediction-Powered Mean Estimation](https://mlsanity.com/paper/2604.18569/) (2026)

## Abstract (arXiv)

We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Specifically, the algorithm observes a corrupted set of samples from N(μ,Id), where the unknown mean μ ∈ ℝd is constrained to be k-sparse. A series of prior works has developed efficient algorithms for robust sparse mean estimation with sample complexity poly(k,log d, 1/ε) and runtime d2 poly(k,log d,1/ε), where ε is the fraction of contamination. In particular, the fastest runtime of existing algorithms is quadratic (Omega(d2)), which can be prohibitive in high dimensions. This quadratic barrier in the runtime stems from the reliance of these algorithms on the sample covariance matrix, which is of size d2. Our main contribution is an algorithm for robust sparse mean estimation which runs in subquadratic time using poly(k,log d,1/ε) samples. We also provide analogous results for robust sparse PCA. Our results build on algorithmic advances in detecting weak correlations, a generalized version of the light-bulb problem by Valiant.