Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
Constantinos Daskalakis, Gautam Kamath · 2014
We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians with-out any separability assumptions. Given Õ(1/ε2) samples from an unknown mixture, our algorithm outputs a mixture that is ε-close in total variation distance, in time Õ(1/ε5). Our sample complex-ity is optimal up to logarithmic factors, and significantly improves upon both Kalai et al. (2010), whose algorithm has a prohibitive dependence on 1/ε, and Feldman et al. (2006), whose algorithm requires bounds on the mixture parameters and depends pseudo-polynomially in these parameters. One of our main contributions is an improved and generalized algorithm for selecting a good candidate distribution from among competing hypotheses. Namely, given a collection of N hy-potheses containing at least one candidate that is ε-close to an unknown distribution, our algorithm outputs a candidate which is O(ε)-close to the distribution. The algorithm requires O(logN/ε2) samples from the unknown distribution and O(N logN/ε2) time, which improves previous such results (such as the Scheffe ́ estimator) from a quadratic dependence of the running time on N to quasilinear. Given the wide use of such results for the purpose of hypothesis selection, our im-proved algorithm implies immediate improvements to any such use.