## Abstract

We give the first polynomial time algorithm for list-decodable covariance estimation. For any α > 0, our algorithm takes input a sample Y † d of size n≥ dpoly(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 ς∗. In npoly(1/α) time, it outputs a constant-size list of k = k(α)= (1/α)poly(1/α) candidate parameters that, with high probability, contains a (μ,ς) such that the total variation distance TV(N(μ∗,ς∗),N(μ,ς))<1-Oα(1). This is a statistically strongest notion of distance and implies multiplicative spectral and relative Frobenius distance approximation with dimension independent error. Our algorithm works more generally for 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 [Karmalkar-Klivans-Kothari 2019, Bakshi-Kothari 2020, Raghavendra-Yau'19, 20]. Even for these special cases, the known error guarantees are weak and in particular, the algorithms need super-polynomial time for any sub-constant (in dimension d) target error in natural norms. Our result, as a corollary, yields the first polynomial time exact algorithm for list-decodable linear regression and subspace recovery that, in particular, obtain 2-(d) error in polynomial-time in the underlying dimension.

Original language | English (US) |
---|---|

Title of host publication | STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Stefano Leonardi, Anupam Gupta |

Publisher | Association for Computing Machinery |

Pages | 1276-1283 |

Number of pages | 8 |

ISBN (Electronic) | 9781450392648 |

DOIs | |

State | Published - Sep 6 2022 |

Externally published | Yes |

Event | 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy Duration: Jun 20 2022 → Jun 24 2022 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 |
---|---|

Country/Territory | Italy |

City | Rome |

Period | 6/20/22 → 6/24/22 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- list-decodable learning
- robust statistics
- sum-of-squares