Learning GMMs with Nearly Optimal Robustness Guarantees

Allen Liu, Ankur Moitra
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:2815-2895, 2022.

Abstract

In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with $k$ components from $\epsilon$-corrupted samples up to accuracy $\widetilde{O}(\epsilon)$ in total variation distance for any constant $k$ and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. The main challenge is that most earlier works rely on learning individual components in the mixture, but this is impossible in our setting, at least for the types of strong robustness guarantees we are aiming for. Instead we introduce a new framework which we call {\em strong observability} that gives us a route to circumvent this obstacle.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-liu22c, title = {Learning GMMs with Nearly Optimal Robustness Guarantees}, author = {Liu, Allen and Moitra, Ankur}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {2815--2895}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/liu22c/liu22c.pdf}, url = {https://proceedings.mlr.press/v178/liu22c.html}, abstract = {In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with $k$ components from $\epsilon$-corrupted samples up to accuracy $\widetilde{O}(\epsilon)$ in total variation distance for any constant $k$ and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. The main challenge is that most earlier works rely on learning individual components in the mixture, but this is impossible in our setting, at least for the types of strong robustness guarantees we are aiming for. Instead we introduce a new framework which we call {\em strong observability} that gives us a route to circumvent this obstacle.} }
Endnote
%0 Conference Paper %T Learning GMMs with Nearly Optimal Robustness Guarantees %A Allen Liu %A Ankur Moitra %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-liu22c %I PMLR %P 2815--2895 %U https://proceedings.mlr.press/v178/liu22c.html %V 178 %X In this work we solve the problem of robustly learning a high-dimensional Gaussian mixture model with $k$ components from $\epsilon$-corrupted samples up to accuracy $\widetilde{O}(\epsilon)$ in total variation distance for any constant $k$ and with mild assumptions on the mixture. This robustness guarantee is optimal up to polylogarithmic factors. The main challenge is that most earlier works rely on learning individual components in the mixture, but this is impossible in our setting, at least for the types of strong robustness guarantees we are aiming for. Instead we introduce a new framework which we call {\em strong observability} that gives us a route to circumvent this obstacle.
APA
Liu, A. & Moitra, A.. (2022). Learning GMMs with Nearly Optimal Robustness Guarantees. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:2815-2895 Available from https://proceedings.mlr.press/v178/liu22c.html.

Related Material