List-decodable covariance estimation

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.