{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:00:52Z","timestamp":1787320852188,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["Young Investigator Award"],"award-info":[{"award-number":["Young Investigator Award"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CAREER Award CCF-1453261, Large CCF1565235"],"award-info":[{"award-number":["CAREER Award CCF-1453261, Large CCF1565235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","award":["Packard Fellowship"],"award-info":[{"award-number":["Packard Fellowship"]}],"id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","award":["Trustworthy AI Grant"],"award-info":[{"award-number":["Trustworthy AI Grant"]}],"id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451084","type":"proceedings-article","created":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T21:26:13Z","timestamp":1623792373000},"page":"518-531","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Settling the robust learnability of mixtures of Gaussians"],"prefix":"10.1145","author":[{"given":"Allen","family":"Liu","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Learning Theory","author":"Achlioptas Dimitris","unstructured":"Dimitris Achlioptas and Frank McSherry. 2005. On spectral learning of mixtures of distributions. In Learning Theory. Springer. Pages 458\u2013469."},{"key":"e_1_3_2_1_2_1","unstructured":"Martin Anthony and Peter L Bartlett. 2009. Neural network learning: Theoretical foundations. cambridge university press."},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the thirty-third annual ACM symposium on Theory of computing. Pages 247\u2013257","author":"Arora Sanjeev","year":"2001","unstructured":"Sanjeev Arora and Ravi Kannan. 2001. Learning mixtures of arbitrary gaussians. In Proceedings of the thirty-third annual ACM symposium on Theory of computing. Pages 247\u2013257."},{"key":"e_1_3_2_1_4_1","volume-title":"Vempala","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, and Santosh S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians."},{"key":"e_1_3_2_1_5_1","volume-title":"Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. arXiv preprint arXiv:2005.02970, 2020."},{"key":"e_1_3_2_1_6_1","volume-title":"Robust Linear Regression: Optimal Rates in Polynomial Time. arXiv preprint arXiv:2007.01394","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi and Adarsh Prasad. 2020. Robust Linear Regression: Optimal Rates in Polynomial Time. arXiv preprint arXiv:2007.01394, 2020."},{"key":"e_1_3_2_1_7_1","volume-title":"Conference on Learning Theory. Pages 169\u2013212","author":"Balakrishnan Sivaraman","year":"2017","unstructured":"Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. 2017. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory. Pages 169\u2013212."},{"key":"e_1_3_2_1_8_1","unstructured":"Boaz Barak. [n.d.]. Proofs beliefs and algorithms through the lens of sum-of-squares. [n.\\tmspace +\\thinmuskip .1667emd.]."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_11_1","volume-title":"Conference on Learning Theory. Pages 417\u2013445","author":"Barak Boaz","year":"2016","unstructured":"Boaz Barak and Ankur Moitra. 2016. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory. Pages 417\u2013445."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_3_2_1_13_1","unstructured":"Thorsten Bernholt. 2006. Robust estimators are hard to compute."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_15_1","volume-title":"Building Bridges","author":"Charles Brubaker S","unstructured":"S Charles Brubaker and Santosh S Vempala. 2008. Isotropic PCA and affine-invariant clustering. In Building Bridges. Springer. Pages 241\u2013281."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_3_2_1_17_1","volume-title":"Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. arXiv preprint arXiv:2010.04157","author":"Chen Sitan","year":"2020","unstructured":"Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. 2020. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. arXiv preprint arXiv:2010.04157, 2020."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"e_1_3_2_1_19_1","volume-title":"A two-round variant of em for gaussian mixtures. arXiv preprint arXiv:1301.3850","author":"Dasgupta Sanjoy","year":"2013","unstructured":"Sanjoy Dasgupta and Leonard Schulman. 2013. A two-round variant of em for gaussian mixtures. arXiv preprint arXiv:1301.3850, 2013."},{"key":"e_1_3_2_1_20_1","volume-title":"Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. arXiv preprint arXiv:2005.06417, 2020."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"e_1_3_2_1_22_1","volume-title":"International Conference on Machine Learning. Pages 1596\u20131606","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. 2019. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning. Pages 1596\u20131606."},{"key":"e_1_3_2_1_23_1","first-page":"1008","volume-title":"Proceedings of the 34th International Conference on Machine Learning-Volume 70","author":"Diakonikolas Ilias","year":"2017","unstructured":"Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. 2017. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. Pages 999\u20131008."},{"key":"e_1_3_2_1_24_1","volume-title":"Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_26_1","volume-title":"Robust statistics: the approach based on influence functions. 196","author":"Hampel Frank R","unstructured":"Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw, and Werner A Stahel. 2011. Robust statistics: the approach based on influence functions. 196, John Wiley & Sons."},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory. Pages 354\u2013375","author":"Hardt Moritz","year":"2013","unstructured":"Moritz Hardt and Ankur Moitra. 2013. Algorithms and hardness for robust subspace recovery. In Conference on Learning Theory. Pages 354\u2013375."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_1_31_1","volume-title":"Conference on Learning Theory. Pages 956\u20131006","author":"Hopkins Samuel B","year":"2015","unstructured":"Samuel B Hopkins, Jonathan Shi, and David Steurer. 2015. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory. Pages 956\u20131006."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_1_34_1","volume-title":"Robust statistics. 523","author":"Huber Peter J","unstructured":"Peter J Huber. 2004. Robust statistics. 523, John Wiley & Sons."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90006-3"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_3_2_1_37_1","volume-title":"Robust Learning of Mixtures of Gaussians. arXiv preprint arXiv:2007.05912","author":"Kane Daniel M","year":"2020","unstructured":"Daniel M Kane. 2020. Robust Learning of Mixtures of Gaussians. arXiv preprint arXiv:2007.05912, 2020."},{"key":"e_1_3_2_1_38_1","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. Pages 1420\u20131430","author":"Klivans Adam","year":"2018","unstructured":"Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. Pages 1420\u20131430."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_42_1","unstructured":"Jerry Zheng Li. 2018. Principled approaches to robust machine learning and beyond."},{"key":"e_1_3_2_1_43_1","volume-title":"Algorithmic aspects of machine learning","author":"Moitra Ankur","unstructured":"Ankur Moitra. 2018. Algorithmic aspects of machine learning. Cambridge University Press."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_45_1","unstructured":"Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization."},{"key":"e_1_3_2_1_46_1","first-page":"1894","article-title":"Contributions to the mathematical theory of evolution","volume":"185","author":"Pearson Karl","year":"1894","unstructured":"Karl Pearson. 1894. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185, 1894. Pages 71\u2013110.","journal-title":"Philosophical Transactions of the Royal Society of London. A"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/AAI28115249"},{"key":"e_1_3_2_1_48_1","volume-title":"Identifiability of mixtures. The annals of Mathematical statistics, 32, 1","author":"Teicher Henry","year":"1961","unstructured":"Henry Teicher. 1961. Identifiability of mixtures. The annals of Mathematical statistics, 32, 1, 1961. Pages 244\u2013248."},{"key":"e_1_3_2_1_49_1","volume-title":"A survey of sampling from contaminated distributions. Contributions to probability and statistics","author":"Tukey John W","year":"1960","unstructured":"John W Tukey. 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics, 1960. Pages 448\u2013485."},{"key":"e_1_3_2_1_50_1","first-page":"531","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Tukey John W","year":"1975","unstructured":"John W Tukey. 1975. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975. 2, Pages 523\u2013531."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451084","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451084","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451084","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:24:53Z","timestamp":1750181093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451084"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":51,"alternative-id":["10.1145\/3406325.3451084","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451084","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}