@article{Ashtiani_Ben-David_Mehrabian_2018, title={Sample-Efficient Learning of Mixtures}, volume={32}, url={https://ojs.aaai.org/index.php/AAAI/article/view/11627}, DOI={10.1609/aaai.v32i1.11627}, abstractNote={ <p> 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 F be an arbitrary class of probability distributions, and let F<sup>k</sup> denote the class of k-mixtures of elements of F. Assuming the existence of a method for learning F with sample complexity m(ε), we provide a method for learning F<sup>k</sup> with sample complexity O((k.log k .m(ε))/(ε<sup>2</sup>)). Our mixture learning algorithm has the property that, if the F-learner is proper and agnostic, then the F<sup>k</sup>-learner would be proper and 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 R<sup>d</sup> is PAC-learnable in the agnostic setting with O((kd)/(ε<sup>4</sup>)) samples, which is tight in k and d up to logarithmic factors. Second, we show that the class of mixtures of k Gaussians in R<sup>d</sup> is PAC-learnable in the agnostic setting with sample complexity Õ((kd<sup>2</sup>)/(ε<sup>4</sup>)), which improves the previous known bounds of Õ((k<sup>3</sup>.d<sup>2</sup>)/(ε<sup>4</sup>)) and Õ(k<sup>4</sup>.d<sup>4</sup>/ε<sup>2</sup>) in its dependence on k and d. Finally, we show that the class of mixtures of k log-concave distributions over R<sup>d</sup> is PAC-learnable using Õ(k.d<sup>((d+5)/2)</sup>ε<sup>(-(d+9)/2</sup>)) samples. </p> }, number={1}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Ashtiani, Hassan and Ben-David, Shai and Mehrabian, Abbas}, year={2018}, month={Apr.} }