NeurIPS 2018oral77 citations
Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes
Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, Yaniv Plan
Abstract
We prove that ϴ(k d^2 / ε^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(k d / ε^2) samples suffice, matching a known lower bound.
BibTeX
@inproceedings{NEURIPS2018_70ece1e1,
author = {Ashtiani, Hassan and Ben-David, Shai and Harvey, Nicholas and Liaw, Christopher and Mehrabian, Abbas and Plan, Yaniv},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/70ece1e1e0931919438fcfc6bd5f199c-Paper.pdf},
volume = {31},
year = {2018}
}