BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Learning mixtures of Gaussians under much less separation Hopkins, Samuel


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

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International