Nearly Tight Sample Complexity Bounds For Learning Mixtures Of Gaussians Via Sample Compression Schemes

Authors:
Hassan Ashtiani McMaster University
Shai Ben-David University of Waterloo
Nick Harvey University of British Columbia
Christopher Liaw University of British Columbia
Abbas Mehrabian Mcgill University
Yaniv Plan University of British Columbia

Introduction:

The authors prove that ϴ(k d^2 / ε^2) samples are necessary and sufficient for learning a mixture of k Gaussians in R^d, up to error ε in total variation distance.

Abstract:

We prove that ϴ(k d^2 / ε^2) samples are necessary and sufficient for learning a mixture of k Gaussians in R^d, up to error ε in total variation distance. This improves both the known upper bounds and lower bounds for this problem. For mixtures of axis-aligned Gaussians, we show that O(k d / ε^2) samples suffice, matching a known lower bound.

You may want to know: