List-decodable covariance estimation

Misha Ivkov, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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 languageEnglish (US)
Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
EditorsStefano Leonardi, Anupam Gupta
PublisherAssociation for Computing Machinery
Pages1276-1283
Number of pages8
ISBN (Electronic)9781450392648
DOIs
StatePublished - Sep 6 2022
Externally publishedYes
Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
Duration: Jun 20 2022Jun 24 2022

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/TerritoryItaly
CityRome
Period6/20/226/24/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint

Dive into the research topics of 'List-decodable covariance estimation'. Together they form a unique fingerprint.

Cite this