# List Decodable Mean Estimation in Nearly Linear Time

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2020.

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

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering](https://mlsanity.com/paper/2206.05245/) (2022)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [List-Decodable Covariance Estimation](https://mlsanity.com/paper/2206.10942/) (2022)
- [High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackers](https://mlsanity.com/paper/2307.13352/) (2023)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation](https://mlsanity.com/paper/2312.11769/) (2023)
- [Entangled Mean Estimation in High-Dimensions](https://mlsanity.com/paper/2501.05425/) (2025)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm](https://mlsanity.com/paper/2305.00966/) (2023)
- [Robust Mixture Learning when Outliers Overwhelm Small Groups](https://mlsanity.com/paper/2407.15792/) (2024)

## Abstract (arXiv)

Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a high dimensional distribution under natural assumptions in the presence of even a small fraction of outliers. In this paper, we consider robust statistics in the presence of overwhelming outliers where the majority of the dataset is introduced adversarially. With only an α < 1/2 fraction of "inliers" (clean data) the mean of a distribution is unidentifiable. However, in their influential work, [CSV17] introduces a polynomial time algorithm recovering the mean of distributions with bounded covariance by outputting a succinct list of O(1/α) candidate solutions, one of which is guaranteed to be close to the true distributional mean; a direct analog of 'List Decoding' in the theory of error correcting codes. In this work, we develop an algorithm for list decodable mean estimation in the same setting achieving up to constants the information theoretically optimal recovery, optimal sample complexity, and in nearly linear time up to polylogarithmic factors in dimension. Our conceptual innovation is to design a descent style algorithm on a nonconvex landscape, iteratively removing minima to generate a succinct list of solutions. Our runtime bottleneck is a saddle-point optimization for which we design custom primal dual solvers for generalized packing and covering SDP's under Ky-Fan norms, which may be of independent interest.