Near-optimal Sample Complexity Bounds for Robust Learning of Gaussian Mixtures via Compression Schemes

Citation

Authors: Hassan Ashtiani, Shai Ben-David, Nicholas J. A. Harvey, Christopher Liaw, Abbas Mehrabian, Yaniv Plan
Year: 2020
Venue: Journal of the ACM 67(6), 1-42
arXiv: arXiv:1710.05209
URL: https://doi.org/10.1145/3417994

One-Line Takeaway

Ashtiani et al. establish near-optimal sample-complexity bounds for learning Gaussian-mixture densities, showing that density estimation can be characterized sharply through compression-scheme arguments even in the robust setting.

Technical Summary

Setup: the task is density estimation in total variation for $k\text{-mix}(\mathcal G_d)$ , where $\mathcal G_d$ is the class of Gaussians on $\mathbb{R}^d$ , with agnostic target $g$ allowed to lie outside the class. The objective is an $(\epsilon,C)$ -approximation in $\|\,\cdot\,\|_1 = 2\,\mathrm{TV}$ .
Compression principle: if a class $\mathcal F$ admits robust $(\tau,t,m)$ compression, then it has agnostic sample complexity $\widetilde O(m+(\tau+t)/\epsilon^2)$ . The paper proves that robust compression is preserved under products and mixtures.
Gaussian consequence: $d$ -dimensional Gaussians admit a small robust compression scheme, which yields $\widetilde \Theta\!\left(\frac{k d^2}{\epsilon^2}\right)$ samples for learning $k$ -mixtures of general Gaussians and $\widetilde \Theta\!\left(\frac{k d}{\epsilon^2}\right)$ for axis-aligned mixtures, both tight up to polylogarithmic factors.
Scope: these are sharp density-learning rates, not latent-parameter recovery guarantees; the main theorem gives near-optimal minimax sample complexity while leaving computational efficiency largely open.

Assumptions And Limits

This is a density-learning result, not a parameter-recovery result. It therefore says much less about when one can recover the actual component identities or latent labels, especially near singular or overlapping mixtures.

Relevance To This Project

This paper is a useful counterpoint for the x -> z -> y program: learning the observable distribution p(y | x) can be much easier than recovering a meaningful latent strategy variable z. The note helps separate "we can model the output law accurately" from "we can identify the latent decomposition that generated it."

Comparison Notes

Hardt and Price (2015) study parameter recovery and local conditioning; Ashtiani et al. study density learning, which is often much easier. Moitra and Valiant (2010) address learnability of the actual Gaussian mixture components for fixed k, not just approximation of the mixture density.

Source Note

Retrieval: alphaXiv MCP get_paper_content on arXiv:1710.05209 (the public arXiv version corresponding to the later JACM paper); no local cache or downloaded source artifacts were created.

Verified from source: title, authors, arXiv identifier, the robust-compression-to-learning reduction, the $\widetilde\Theta(k d^2/\epsilon^2)$ and $\widetilde\Theta(k d/\epsilon^2)$ sample-complexity rates, and the paper's explicit emphasis on density estimation rather than parameter recovery were checked against the alphaXiv-extracted arXiv text. The canonical citation remains the 2020 JACM version, while the source read here was the public arXiv version.