Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes

2017/10/14 by Ashtiani, Hassan, Ben-David, Shai, Harvey, Nick +3
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1710.05209

Abstract

We prove that Θ(k d² / ε²) samples are necessary and sufficient for learning a mixture of k Gaussians in ℝ^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 / ε²) samples suffice, matching a known lower bound. Moreover, these results hold in the agnostic-learning/robust-estimation setting as well, where the target distribution is only approximately a mixture of Gaussians. The upper bound is shown using a novel technique for distribution learning based on a notion of `compression.' Any class of distributions that allows such a 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 ℝ^d admits a small-sized compression scheme.

Related

• A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
• Tight bounds for learning a mixture of two gaussians
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians
• Sample-Efficient Private Learning of Mixtures of Gaussians
• Sample-Efficient Learning of Mixtures