TY - JOUR
AU - Ashtiani, Hassan
AU - Ben-David, Shai
AU - Mehrabian, Abbas
PY - 2018/04/29
Y2 - 2024/07/19
TI - Sample-Efficient Learning of Mixtures
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - AAAI Technical Track: Machine Learning
DO - 10.1609/aaai.v32i1.11627
UR - https://ojs.aaai.org/index.php/AAAI/article/view/11627
SP -
AB - <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>
ER -