mlsanityData to 7 Oct 2026

List-Decodable Sparse Mean Estimation

arXiv 2205.14337 ↗First posted 28 May 2022cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

Robust mean estimation is one of the most important problems in statistics: given a set of samples in ℝd where an α fraction are drawn from some distribution D and the rest are adversarially corrupted, we aim to estimate the mean of D. A surge of recent research interest has been focusing on the list-decodable setting where α ∈ (0, frac12], and the goal is to output a finite number of estimates among which at least one approximates the target mean. In this paper, we consider that the underlying distribution D is Gaussian with k-sparse mean. Our main contribution is the first polynomial-time algorithm that enjoys sample complexity Obig(poly(k, log d)big), i.e. poly-logarithmic in the dimension. One of our core algorithmic ingredients is using low-degree sparse polynomials to filter outliers, which may find more applications.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 33 of its 73 references that are in the map. First posted on arXiv 28 May 2022.

Builds on

33 of 73 references.

References · 33

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  4. 2016Learning from Untrusted Datacited by 90
  5. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  6. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  7. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  8. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  9. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  10. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  11. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  12. 2019List-Decodable Linear Regressioncited by 42
21 more
  1. 2015Robust Regression via Hard Thresholdingcited by 39
  2. 2019List Decodable Learning via Sum of Squarescited by 37
  3. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  4. 2018High Dimensional Robust Sparse Regressioncited by 29
  5. 2020Efficient active learning of sparse halfspaces with arbitrary bounded noisecited by 29
  6. 2021Statistical Query Lower Bounds for List-Decodable Linear Regressioncited by 25
  7. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  8. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  9. 2020List Decodable Mean Estimation in Nearly Linear Timecited by 20
  10. 2020List-Decodable Mean Estimation via Iterative Multi-Filteringcited by 18
  11. 2020List-Decodable Mean Estimation in Nearly-PCA Timecited by 17
  12. 2016A Tight Bound of Hard Thresholdingcited by 16
  13. 2016Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Predictioncited by 15
  14. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  15. 2020List Decodable Subspace Recoverycited by 13
  16. 2020A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noisecited by 13
  17. 2020Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerancecited by 12
  18. 2021Sample-Optimal PAC Learning of Halfspaces with Malicious Noisecited by 11
  19. 2017Efficient PAC Learning from the Crowdcited by 7
  20. 2020Efficient PAC Learning from the Crowd with Pairwise Comparisonscited by 7
  21. 2020One-Bit Compressed Sensing via One-Shot Hard Thresholdingcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 3; 2025: 2; 2026: 2.

11 papers.

  1. 2022List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filteringcited by 13
  2. 2023High Dimensional Distributed Gradient Descent with Arbitrary Number of Byzantine Attackerscited by 7
  3. 2025The Power of Iterative Filtering for Supervised Learning with (Heavy) Contaminationcited by 7
  4. 2024Efficient PAC Learning of Halfspaces with Constant Malicious Noise Ratecited by 5
  5. 2023Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noisecited by 3
  6. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  7. 2023A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Normcited by 1
  8. 2024Robust Mixture Learning when Outliers Overwhelm Small Groupscited by 1
  9. 2025High-Accuracy List-Decodable Mean Estimationcited by 0
  10. 2026LLM-Augmented Computational Phenotyping of Long Covidcited by 0
  11. 2026Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterizationcited by 0