Spotlight Poster
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
Ilias Diakonikolas · Daniel Kane · Jasper Lee · Ankit Pensia · Ankit Pensia · Thanasis Pittas
Great Hall & Hall B1+B2 (level 1) #1720
Abstract:
We study the problem of list-decodable Gaussian covariance estimation. Given a multiset of points in such that an unknown fraction of points in are i.i.d. samples from an unknown Gaussian , the goal is to output a list of hypotheses at least one of which is close to in relative Frobenius norm. Our main result is a sample and time algorithm for this task that guarantees relative Frobenius norm error of . Importantly, our algorithm relies purely on spectral techniques. As a corollary, we obtain an efficient spectral algorithm for robust partial clustering of Gaussian mixture models (GMMs) --- a key ingredient in the recent work of [BakDJKKV22] on robustly learning arbitrary GMMs. Combined with the other components of [BakDJKKV22], our new method yields the first Sum-of-Squares-free algorithm for robustly learning GMMs, resolving an open problem proposed by Vempala and Kothari. At the technical level, we develop a novel multi-filtering method for list-decodable covariance estimation that may be useful in other settings.
Chat is not available.