Open Collections

Learning mixtures of Gaussians under much less separation

Banff International Research Station for Mathematical Innovation and Discovery

For every epsilon > 0, we give an efficient algorithm to learn the cluster centers of a mixture of poly(k) standard Gaussians in k dimensions, under the condition that every pair of centers is at least k^epsilon apart in Euclidean distance. The best previously known algorithms for this problem are spectral methods, which break down when epsilon = 1/4; i.e. when the centers are separated by k^(1/4), the distance at which clusters may be separated by computing pairwise distances of all the samples. We use the sum of squares method to show that the means remain efficiently learnable when the separation of each pair of means is much smaller. Our algorithm draws on many ideas from the approximation algorithms literature; in particular it relies on sum-of-squares proofs of Gaussian hypercontractivity inequalities first proved to analyze unique games integrality gaps. Joint work with Jerry Li

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Cornell University

2018-05-15

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65875

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/