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 ≥ d poly (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 n poly (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.

Authors

• Misha Ivkov
• Pravesh K. Kothari

Keywords

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