# List-Decodable Covariance Estimation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 41 references that are in the map.
- First posted on arXiv 22 Jun 2022.

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

- [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)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians](https://mlsanity.com/paper/1711.07211/) (2017)
- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Robustly Learning any Clusterable Mixture of Gaussians](https://mlsanity.com/paper/2005.06417/) (2020)
- [Outlier-robust moment-estimation via sum-of-squares](https://mlsanity.com/paper/1711.11581/) (2017)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Better Agnostic Clustering Via Relaxed Tensor Norms](https://mlsanity.com/paper/1711.07465/) (2017)
- [List Decodable Mean Estimation in Nearly Linear Time](https://mlsanity.com/paper/2005.09796/) (2020)
- [Outlier-Robust Clustering of Non-Spherical Mixtures](https://mlsanity.com/paper/2005.02970/) (2020)
- [Fast Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1902.01998/) (2019)
- [List-Decodable Mean Estimation via Iterative Multi-Filtering](https://mlsanity.com/paper/2006.10715/) (2020)
- [List-Decodable Mean Estimation in Nearly-PCA Time](https://mlsanity.com/paper/2011.09973/) (2020)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally](https://mlsanity.com/paper/2110.11853/) (2021)
- [List Decodable Subspace Recovery](https://mlsanity.com/paper/2002.03004/) (2020)
- [Smoothing the gap between NP and ER](https://mlsanity.com/paper/1912.02278/) (2019)
- [List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time](https://mlsanity.com/paper/2002.05139/) (2020)
- [Quantum entanglement, sum of squares, and the log rank conjecture](https://mlsanity.com/paper/1701.06321/) (2017)

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

- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination](https://mlsanity.com/paper/2505.20177/) (2025)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [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)
- [High-Accuracy List-Decodable Mean Estimation](https://mlsanity.com/paper/2511.17822/) (2025)

## Abstract (arXiv)

We give the first polynomial time algorithm for list-decodable covariance estimation. For any α > 0, our algorithm takes input a sample Y subseteq ℝd of size n≥ d^mathsfpoly(1/α) obtained by adversarially corrupting an (1-α)n points in an i.i.d. sample X of size n from the Gaussian distribution with unknown mean μ_* and covariance Sigma_*. In n^mathsfpoly(1/α) time, it outputs a constant-size list of k = k(α)= (1/α)^mathsfpoly(1/α) candidate parameters that, with high probability, contains a (hatμ,hatSigma) such that the total variation distance TV(N(μ_*,Sigma_*),N(hatμ,hatSigma))<1-Oα(1). This is the statistically strongest notion of distance and implies multiplicative spectral and relative Frobenius distance approximation for parameters with dimension independent error. Our algorithm works more generally for (1-α)-corruptions of any distribution D that possesses low-degree sum-of-squares certificates of two natural analytic properties: 1) anti-concentration of one-dimensional marginals and 2) hypercontractivity of degree 2 polynomials. Prior to our work, the only known results for estimating covariance in the list-decodable setting were for the special cases of list-decodable linear regression and subspace recovery due to Karmarkar, Klivans, and Kothari (2019), Raghavendra and Yau (2019 and 2020) and Bakshi and Kothari (2020). These results need superpolynomial time for obtaining any subconstant error in the underlying dimension. Our result implies the first polynomial-time exact algorithm for list-decodable linear regression and subspace recovery that allows, in particular, to obtain 2^-mathsfpoly(d) error in polynomial-time. Our result also implies an improved algorithm for clustering non-spherical mixtures.