Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes

We prove that Θ(^e kd²/ε²) 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^e(kd/ε²) samples suffice, matching a known lower bound. The upper bound is based on a novel technique for distribution learning based on a notion of sample …