Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes *
We prove that Θ(kd 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(kd/ε 2 ) 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 compression. Any class of distributions that allows such a sample compression scheme can also be learned with few samples. Moreover, if a class of distributions has such a compression scheme, then so do the classes of products and mixtures of those distributions. The core of our main result is showing that the class of Gaussians in R d has a small-sized sample compression.
This paper is well written and issues a classical and well known studied problem from a new point of view.  The compression based analysis which is indeed deep, although less popular, is gaining more attention on the last couple of years. This paper join this line of work by extending it, proving some interesting properties if sample-compression schemes (such as the them being close under mixture or product) and go on and demonstrates the power of the obtained results by proving state of the art sample complexity upper bound for mixture of Gaussians. I think that the NIPS community will indeed benefit from this paper.  Remarks:  - there exists a line of work regarding the generalization guarantees of compression based learners. Most of them to the classification case but some for more general setting. How does your results differ from those? See for example      On statistical learning via the lens of compression,    PAC-Bayesian Compression Bounds on the Prediction Error of Learning          Algorithms for Classification,    Nearly optimal classification for semimetrics,    Sample Compression for Real-Valued Learners,    Adaptive Learning with Robust Generalization Guarantees, - Although the “robust compression implies  agnostic learning” is indeed of interest it isn’t in use on the specific case of mixture of Gaussians, I think that it should be stated more clearly as I got a bit of confused, especially as the proof is given for that case and not for the (more simple) realizable case - On line 317 you use a notion of a d dimensional ball. I know that this is standard notion but still it may be of help to mention you intention to make it more clear what each parameter means (so for example when you multiply the ball, you mean just scaling it?