Material Detail

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

This video was recorded at 27th Annual Conference on Learning Theory (COLT), Barcelona 2014. We provide an algorithm for properly learning mixtures of two single-dimensional Gaussians without any separability assumptions. Given O(1/ε2) samples from an unknown mixture, our algorithm outputs a mixture that is ε-close in total variation distance, in time O(1/ε5). Our sample complexity is optimal up to logarithmic factors, and significantly improves upon both Kalai et al., whose algorithm has a prohibitive dependence on 1/ε, and Feldman et al., 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 hypotheses 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(NlogN/ε2) time, which improves previous such results (such as the Scheffé 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 improved algorithm implies immediate improvements to any such use.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.