Polynomial-time proper learning of univariate Gaussian mixtures
For an integer $k \ge 1$ let $\mathcal{G}_k$ be the set of densities on $\mathbb{R}$ of the form $$f(x) = \sum_{i=1}^k \frac{w_i}{\sqrt{2\pi}\,\sigma_i} \exp\Bigl(-\frac{(x - \mu_i)^2}{2\sigma_i^2}\Bigr), \qquad w_i \ge 0, \quad \sum_{i=1}^k w_i = 1, \quad \mu_i \in \mathbb{R}, \quad \sigma_i > 0,$$ with no separation of the components, no bound on the parameters and no lower bound on the nonzero weights. A proper learner receives $k$, $\varepsilon$ and independent samples from an unknown $f \in \mathcal{G}_k$, and outputs an explicit list of at most $k$ Gaussian components defining some $\widehat f \in \mathcal{G}_k$; it need not recover the components of $f$. Computation is in the model of Daskalakis and Kamath: infinite-precision real arithmetic, with exact evaluation of Gaussian densities, counting samples and arithmetic operations. Daskalakis and Kamath gave a proper learner for $k = 2$ using $\tilde O(1/\varepsilon^2)$ samples and time $\tilde O(1/\varepsilon^5)$, and Li and Schmidt one with $\tilde O(k/\varepsilon^2)$ samples and time $(k \log(1/\varepsilon))^{O(k^4)} + \tilde O(k/\varepsilon^2)$. Liu, Li and Moitra gave an algorithm running in time polynomial in $k/\varepsilon$ that outputs a mixture of $\tilde O(k)$ Gaussians within total variation distance $\tilde O(\varepsilon)$, and conjecture that learning without relaxing the number of components is computationally hard.
Problem. Is there a randomized algorithm and a polynomial $p$ such that, for every $k \ge 1$, every $0 < \varepsilon < 1$ and every $f \in \mathcal{G}_k$, the algorithm uses at most $p(k, 1/\varepsilon)$ samples and operations and outputs a proper hypothesis $\widehat f \in \mathcal{G}_k$ with $$\Pr\Bigl[d_{\mathrm{TV}}(f, \widehat f) = \frac12 \int_{\mathbb{R}} |f(x) - \widehat f(x)|\,dx \le \varepsilon\Bigr] \ge \frac23,$$ the probability being over the samples and the algorithm's randomness? The same polynomial must serve every $k$.
Source: Diakonikolas (2016), Open Problem 1.6.2, for k-mixtures of simple parametric classes; for univariate Gaussian mixtures see Li and Schmidt (2017), Section 1, and Liu, Li and Moitra (2022), Section 1.2, who conjecture that it is computationally hard. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- ST — Statistics Theory
- Keywords
- AIM Open Applied Problems, density estimation, Gaussian mixtures, proper learning
References
@incollection{diakonikolas2016,
author = {Diakonikolas, Ilias},
title = {Learning structured distributions},
booktitle = {Handbook of Big Data},
editor = {B{\"u}hlmann, Peter and Drineas, Petros and Kane, Michael and van der Laan, Mark},
publisher = {Chapman and Hall/CRC},
address = {Boca Raton, FL},
year = {2016},
pages = {283--300},
doi = {10.1201/b19567-24},
}
@inproceedings{li2017,
author = {Li, Jerry and Schmidt, Ludwig},
title = {Robust and proper learning for mixtures of {G}aussians via systems of polynomial inequalities},
booktitle = {Proceedings of the 2017 Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {65},
publisher = {PMLR},
year = {2017},
pages = {1302--1382},
eprint = {1506.01367},
archivePrefix = {arXiv},
}
@inproceedings{liu2022,
author = {Liu, Allen and Li, Jerry and Moitra, Ankur},
title = {Robust model selection and nearly-proper learning for {GMM}s},
booktitle = {Advances in Neural Information Processing Systems 35 (NeurIPS 2022)},
year = {2022},
pages = {22830--22843},
doi = {10.52202/068431-1659},
eprint = {2106.02774},
archivePrefix = {arXiv},
}
@inproceedings{daskalakis2014,
author = {Daskalakis, Constantinos and Kamath, Gautam},
title = {Faster and sample near-optimal algorithms for proper learning mixtures of {G}aussians},
booktitle = {Proceedings of The 27th Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {35},
publisher = {PMLR},
year = {2014},
pages = {1183--1213},
eprint = {1312.1054},
archivePrefix = {arXiv},
}
@misc{aim-univariate-gaussian-mixture-proper-learning,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-time proper learning of univariate Gaussian mixtures}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/347-univariate-gaussian-mixture-proper-learning.md},
note = {Entry 347 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00314, "Polynomial-time proper learning of univariate Gaussian mixtures", clopen.solutions.