- This event has passed.
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes, Shai Ben David (University of Waterloo)
April 29, 2019 @ 11:00 am - 12:00 pm IDT
Apr. 29th 2019, Sun. 11:00 , Shai Ben David (webpage).
University of Waterloo.
Location: CS Building (216), Room 201 .
Near-optimal Sample Complexity Bounds for Robust Learning of Gaussians Mixtures via Compression Schemes
We prove that Θ(kd2 /ε^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. 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 R^d admits a small-sized compression scheme.
(Joint work with Hassan Ashtiani, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian and Yaniv Plan)