A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k

Learning a Gaussian mixture model (GMM) is a fundamental problem in machine learning, learning theory, and statistics. One notion of learning a GMM is proper learning: here, the goal is to find a mixture of k Gaussians M that is close to the density f of the unknown distribution from which we draw samples. The distance between M and f is typically measured in the total variation or L1-norm. We give an algorithm for learning a mixture of k univariate Gaussians that is nearly optimal for any fixed k. The sample complexity of our algorithm is tildeO(frackε2) and the running time is (k · logfrac1ε)O(k4) + tildeO(frackε2). It is well-known that this sample complexity is optimal (up to logarithmic factors), and it was already achieved by prior work. However, the best known time complexity for proper learning a k-GMM was tildeO(frac1ε3k-1). In particular, the dependence between frac1ε and k was exponential. We significantly improve this dependence by replacing the frac1ε term with a log frac1ε while only increasing the exponent moderately. Hence, for any fixed k, the tildeO (frackε2) term dominates our running time, and thus our algorithm runs in time which is nearly-linear in the number of samples drawn. Achieving a running time of textrmpoly(k, frac1ε) for proper learning of k-GMMs has recently been stated as an open problem by multiple researchers, and we make progress on this question. Moreover, our approach offers an agnostic learning guarantee: our algorithm returns a good GMM even if the distribution we are sampling from is not a mixture of Gaussians. To the best of our knowledge, our algorithm is the first agnostic proper learning algorithm for GMMs.