Differentially Private Algorithms for Learning Mixtures of Separated\n Gaussians

Learning the parameters of Gaussian mixture models is a fundamental and\nwidely studied problem with numerous applications. In this work, we give new\nalgorithms for learning the parameters of a high-dimensional, well separated,\nGaussian mixture model subject to the strong constraint of differential\nprivacy. In particular, we give a differentially private analogue of the\nalgorithm of Achlioptas and McSherry. Our algorithm has two key properties not\nachieved by prior work: (1) The algorithm's sample complexity matches that of\nthe corresponding non-private algorithm up to lower order terms in a wide range\nof parameters. (2) The algorithm does not require strong a priori bounds on the\nparameters of the mixture components.\n