Timezone: »

Differentially Private Algorithms for Learning Mixtures of Separated Gaussians
Gautam Kamath · Or Sheffet · Vikrant Singhal · Jonathan Ullman

Tue Dec 10:45 AM -- 12:45 PM PST @ East Exhibition Hall B + C #94

Learning the parameters of Gaussian mixture models is a fundamental and widely studied problem with numerous applications. In this work, we give new algorithms for learning the parameters of a high-dimensional, well separated, Gaussian mixture model subject to the strong constraint of differential privacy. In particular, we give a differentially private analogue of the algorithm of Achlioptas and McSherry. Our algorithm has two key properties not achieved by prior work: (1) The algorithm’s sample complexity matches that of the corresponding non-private algorithm up to lower order terms in a wide range of parameters. (2) The algorithm requires very weak a priori bounds on the parameters of the mixture components.

Author Information

Gautam Kamath (University of Waterloo)
Or Sheffet (University of Alberta)
Vikrant Singhal (Northeastern University)
Jonathan Ullman (Northeastern University)

More from the Same Authors