Sample-Efficient Learning of Mixtures

We consider PAC learning of probability distributions (a.k.a. density estimation), where we are given an i.i.d. sample generated from an unknown target distribution, and want to output a distribution that is close to the target in total variation distance. Let mathcal F be an arbitrary class of probability distributions, and let Fk denote the class of k-mixtures of elements of mathcal F. Assuming the existence of a method for learning mathcal F with sample complexity mF(ε), we provide a method for learning mathcal Fk with sample complexity O(klog k · mmathcal F(ε) /ε2). Our mixture learning algorithm has the property that, if the mathcal F-learner is proper/agnostic, then the mathcal Fk-learner would be proper/agnostic as well. This general result enables us to improve the best known sample complexity upper bounds for a variety of important mixture classes. First, we show that the class of mixtures of k axis-aligned Gaussians in ℝd is PAC-learnable in the agnostic setting with widetildeO(kd/ε ^ 4) samples, which is tight in k and d up to logarithmic factors. Second, we show that the class of mixtures of k Gaussians in ℝd is PAC-learnable in the agnostic setting with sample complexity widetildeO(kd2/ε ^ 4), which improves the previous known bounds of widetildeO(k3d2/ε ^ 4) and widetildeO(k4d4/ε ^ 2) in its dependence on k and d. Finally, we show that the class of mixtures of k log-concave distributions over ℝd is PAC-learnable using widetildeO(d(d+5)/2ε-(d+9)/2k) samples.