{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:50:53Z","timestamp":1784299853921,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":93,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Microsoft Research"},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1453261, CCF-1565235, CCF-1350196, DGE-1650441, DGE-1745302"],"award-info":[{"award-number":["CCF-1453261, CCF-1565235, CCF-1350196, DGE-1650441, DGE-1745302"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188748","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1021-1034","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Mixture models, robustness, and sum of squares proofs"],"prefix":"10.1145","author":[{"given":"Samuel B.","family":"Hopkins","sequence":"first","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_2_2_1","volume-title":"COLT (JMLR Workshop and Conference Proceedings)","volume":"35","author":"Anderson Joseph"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000512"},{"key":"e_1_3_2_2_4_1","unstructured":"P. Awasthi M. F. Balcan and P. M. Long. 2014.  P. Awasthi M. F. Balcan and P. M. Long. 2014."},{"key":"e_1_3_2_2_5_1","unstructured":"The power of localization for efficiently learning linear separators with noise. In STOC. 449\u2013458.  The power of localization for efficiently learning linear separators with noise. In STOC. 449\u2013458."},{"key":"e_1_3_2_2_6_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Awasthi Pranjal"},{"key":"e_1_3_2_2_7_1","unstructured":"Sivaraman Balakrishnan Martin J. Wainwright and Bin Yu. 2014.  Sivaraman Balakrishnan Martin J. Wainwright and Bin Yu. 2014."},{"key":"e_1_3_2_2_8_1","volume-title":"From population to sample-based analysis. CoRR abs\/1408.2156","author":"Statistical","year":"2014"},{"key":"e_1_3_2_2_9_1","unstructured":"Boaz Barak Jonathan A. Kelner and David Steurer. 2014.  Boaz Barak Jonathan A. Kelner and David Steurer. 2014."},{"key":"e_1_3_2_2_10_1","unstructured":"Rounding sum-ofsquares relaxations. In STOC. ACM 31\u201340.  Rounding sum-ofsquares relaxations. In STOC. ACM 31\u201340."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_2_12_1","unstructured":"Boaz Barak and Ankur Moitra. 2016.  Boaz Barak and Ankur Moitra. 2016."},{"key":"e_1_3_2_2_13_1","volume-title":"COLT (JMLR Workshop and Conference Proceedings)","volume":"49","author":"Tensor Noisy"},{"key":"e_1_3_2_2_14_1","volume-title":"Sum-of-squares proofs and the quest toward optimal algorithms. CoRR abs\/1404.5236","author":"Barak Boaz","year":"2014"},{"key":"e_1_3_2_2_15_1","unstructured":"Boaz Barak and David Steurer. 2017. The sos algorithm over general domains. http: \/\/www.sumofsquares.org\/public\/lecdefinitionsgeneral.html. (2017).  Boaz Barak and David Steurer. 2017. The sos algorithm over general domains. http: \/\/www.sumofsquares.org\/public\/lecdefinitionsgeneral.html. (2017)."},{"key":"e_1_3_2_2_16_1","unstructured":"{Online; accessed 11-1-2017}.  {Online; accessed 11-1-2017}."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_3_2_2_18_1","unstructured":"T. Bernholt. 2006.  T. Bernholt. 2006."},{"key":"e_1_3_2_2_19_1","volume-title":"Technical Report","author":"Compute Robust Estimators"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496887"},{"key":"e_1_3_2_2_22_1","unstructured":"1078\u20131087.  1078\u20131087."},{"key":"e_1_3_2_2_23_1","unstructured":"E. J. Cand\u00e8s X. Li Y. Ma and J. Wright. 2011.  E. J. Cand\u00e8s X. Li Y. Ma and J. Wright. 2011."},{"key":"e_1_3_2_2_24_1","volume-title":"11","author":"Robust","year":"2011"},{"key":"e_1_3_2_2_25_1","unstructured":"Moses Charikar Jacob Steinhardt and Gregory Valiant. 2016.  Moses Charikar Jacob Steinhardt and Gregory Valiant. 2016."},{"key":"e_1_3_2_2_26_1","volume-title":"CoRR abs\/1611.02315","author":"Untrusted Data Learning","year":"2016"},{"key":"e_1_3_2_2_27_1","unstructured":"Yeshwanth Cherapanamjeri Prateek Jain and Praneeth Netrapalli. 2017. Thresholding based Efficient Outlier Robust PCA. In COLT.  Yeshwanth Cherapanamjeri Prateek Jain and Praneeth Netrapalli. 2017. Thresholding based Efficient Outlier Robust PCA. In COLT."},{"key":"e_1_3_2_2_28_1","volume-title":"Foundations of computer science","author":"Dasgupta Sanjoy","year":"1999"},{"key":"e_1_3_2_2_29_1","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","author":"Dasgupta Sanjoy","year":"2007","journal-title":"Journal of Machine Learning Research 8"},{"key":"e_1_3_2_2_30_1","unstructured":"Constantinos Daskalakis and Gautam Kamath. 2014.  Constantinos Daskalakis and Gautam Kamath. 2014."},{"key":"e_1_3_2_2_31_1","volume-title":"Conference on Learning Theory.","author":"Faster"},{"key":"e_1_3_2_2_32_1","volume-title":"Conference on Learning Theory","author":"Daskalakis Constantinos","year":"2017"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"crossref","volume-title":"Robust Estimators in High Dimensions without the Computational Intractability","author":"Diakonikolas Ilias","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_3_2_2_34_1","unstructured":"Ilias Diakonikolas Gautam Kamath Daniel M. Kane Jerry Li Ankur Moitra and Alistair Stewart. 2017.  Ilias Diakonikolas Gautam Kamath Daniel M. Kane Jerry Li Ankur Moitra and Alistair Stewart. 2017."},{"key":"e_1_3_2_2_35_1","unstructured":"Being robust (in high dimensions) can be practical. In ICML.  Being robust (in high dimensions) can be practical. In ICML."},{"key":"e_1_3_2_2_36_1","unstructured":"Ilias Diakonikolas Gautam Kamath Daniel M. Kane Jerry Li Ankur Moitra and Alistair Stewart. 2017.  Ilias Diakonikolas Gautam Kamath Daniel M. Kane Jerry Li Ankur Moitra and Alistair Stewart. 2017."},{"key":"e_1_3_2_2_37_1","volume-title":"Efficiently. In Symposium on Discrete Algorithms.","author":"Gaussian Robustly Learning"},{"key":"e_1_3_2_2_38_1","unstructured":"Ilias Diakonikolas Daniel Kane and Alastair Stewart. 2017. personal communication. (2017).  Ilias Diakonikolas Daniel Kane and Alastair Stewart. 2017. personal communication. (2017)."},{"key":"e_1_3_2_2_39_1","volume-title":"Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. arXiv preprint arXiv:1611.03473","author":"Diakonikolas Ilias","year":"2016"},{"key":"e_1_3_2_2_40_1","volume-title":"Learning Geometric Concepts with Nasty Noise. arXiv preprint arXiv:1707.01242","author":"Diakonikolas Ilias","year":"2017"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_5"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_2_43_1","volume-title":"Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. arXiv preprint arXiv:1504.05287","author":"Ge Rong","year":"2015"},{"key":"e_1_3_2_2_44_1","unstructured":"F. R. Hampel E. M. Ronchetti P. J. Rousseeuw and W. A. Stahel. 1986.  F. R. Hampel E. M. Ronchetti P. J. Rousseeuw and W. A. Stahel. 1986."},{"key":"e_1_3_2_2_45_1","volume-title":"The approach based on influence functions","author":"Robust"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_2_48_1","unstructured":"Samuel B. Hopkins Tselil Schramm Jonathan Shi and David Steurer. 2016.  Samuel B. Hopkins Tselil Schramm Jonathan Shi and David Steurer. 2016."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897529"},{"key":"e_1_3_2_2_50_1","unstructured":"Samuel B. Hopkins Jonathan Shi and David Steurer. 2015.  Samuel B. Hopkins Jonathan Shi and David Steurer. 2015."},{"key":"e_1_3_2_2_51_1","volume-title":"COLT (JMLR Workshop and Conference Proceedings)","volume":"40","author":"Tensor"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90006-3"},{"key":"e_1_3_2_2_55_1","unstructured":"Adam Tauman Kalai Ankur Moitra and Gregory Valiant. 2010.  Adam Tauman Kalai Ankur Moitra and Gregory Valiant. 2010."},{"key":"e_1_3_2_2_56_1","unstructured":"Efficiently learning mixtures of two Gaussians. In STOC. ACM 553\u2013562.  Efficiently learning mixtures of two Gaussians. In STOC. ACM 553\u2013562."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222052"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"crossref","unstructured":"A. Klivans P. Long and R. Servedio. 2009. Learning Halfspaces with Malicious Noise. (2009).  A. Klivans P. Long and R. Servedio. 2009. Learning Halfspaces with Malicious Noise. (2009).","DOI":"10.1007\/978-3-642-02927-1_51"},{"key":"e_1_3_2_2_59_1","unstructured":"Pravesh Kothari and Jacob Steinhardt. 2017. Better Clustering via Relaxed Tensor Norms. personal communication. (2017).  Pravesh Kothari and Jacob Steinhardt. 2017. Better Clustering via Relaxed Tensor Norms. personal communication. (2017)."},{"key":"e_1_3_2_2_60_1","unstructured":"Pravesh Kothari and David Steurer. 2017. Outlier-robust moment estimation via sum-of-squares. personal communication. (2017).  Pravesh Kothari and David Steurer. 2017. Outlier-robust moment estimation via sum-of-squares. personal communication. (2017)."},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_2_62_1","volume-title":"Agnostic Estimation of Mean and Covariance","author":"Lai Kevin A."},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9221-0"},{"key":"e_1_3_2_2_64_1","volume-title":"Conference on Learning Theory.","author":"Li Jerry","year":"2017"},{"key":"e_1_3_2_2_65_1","unstructured":"Tengyu Ma Jonathan Shi and David Steurer. 2016.  Tengyu Ma Jonathan Shi and David Steurer. 2016."},{"key":"e_1_3_2_2_66_1","unstructured":"Polynomial-Time Tensor Decompositions with Sum-of-Squares. In FOCS. IEEE Computer Society 438\u2013446.  Polynomial-Time Tensor Decompositions with Sum-of-Squares. In FOCS. IEEE Computer Society 438\u2013446."},{"key":"e_1_3_2_2_67_1","unstructured":"Geoffrey McLachlan and David Peel. 2004.  Geoffrey McLachlan and David Peel. 2004."},{"key":"e_1_3_2_2_68_1","unstructured":"Finite mixture models. John Wiley & Sons.  Finite mixture models. John Wiley & Sons."},{"key":"e_1_3_2_2_69_1","volume-title":"Clustering subgaussian mixtures by semidefinite programming. Information and Inference: A Journal of the IMA","author":"Mixon Dustin G","year":"2017"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_2_71_1","unstructured":"Ryan O\u2019Donnell. 2017. SOS is not obviously automatizable even approximately. (2017).  Ryan O\u2019Donnell. 2017. SOS is not obviously automatizable even approximately. (2017)."},{"key":"e_1_3_2_2_72_1","volume-title":"Approximability and proof complexity","author":"O\u2019Donnell Ryan"},{"key":"e_1_3_2_2_73_1","unstructured":"Karl Pearson. 1894.  Karl Pearson. 1894."},{"key":"e_1_3_2_2_74_1","volume-title":"Philosophical Transactions of the Royal Society of London. A 185","author":"Contributions","year":"1894"},{"key":"e_1_3_2_2_75_1","volume-title":"Exact tensor completion with sum-ofsquares. CoRR abs\/1702.06237","author":"Potechin Aaron","year":"2017"},{"key":"e_1_3_2_2_76_1","volume-title":"On the Bit Complexity of Sumof-Squares Proofs. CoRR abs\/1702.05139","author":"Raghavendra Prasad","year":"2017"},{"key":"e_1_3_2_2_77_1","volume-title":"Symposium on Foundations of Computer Science.","author":"Regev Oded","year":"2017"},{"key":"e_1_3_2_2_78_1","volume-title":"Conference on Learning Theory","author":"Schramm Tselil","year":"2017"},{"key":"e_1_3_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244304773936072"},{"key":"e_1_3_2_2_80_1","unstructured":"Jacob Steinhardt Moses Charikar and Gregory Valiant. 2017.  Jacob Steinhardt Moses Charikar and Gregory Valiant. 2017."},{"key":"e_1_3_2_2_81_1","unstructured":"Resilience: A criterion for learning in the presence of arbitrary outliers. ITCS.  Resilience: A criterion for learning in the presence of arbitrary outliers. ITCS."},{"key":"e_1_3_2_2_82_1","unstructured":"Ananda Theertha Suresh Alon Orlitsky Jayadev Acharya and Ashkan Jafarpour. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. In Advances in Neural Information Processing Systems. 1395\u20131403.   Ananda Theertha Suresh Alon Orlitsky Jayadev Acharya and Ashkan Jafarpour. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. In Advances in Neural Information Processing Systems. 1395\u20131403."},{"key":"e_1_3_2_2_83_1","volume-title":"Adrian FM Smith, and Udi E Makov","author":"Titterington D Michael","year":"1985"},{"key":"e_1_3_2_2_84_1","unstructured":"Statistical analysis of finite mixture distributions. Wiley .  Statistical analysis of finite mixture distributions. Wiley ."},{"key":"e_1_3_2_2_85_1","first-page":"523","article-title":"Mathematics and picturing of data","volume":"6","author":"Tukey J.W.","year":"1975","journal-title":"Proceedings of ICM"},{"key":"e_1_3_2_2_86_1","volume-title":"Proceedings of the international congress of mathematicians","volume":"2","author":"Tukey John W","year":"1975"},{"key":"e_1_3_2_2_87_1","unstructured":"Leslie G. Valiant. 1985. Learning Disjunction of Conjunctions. In IJCAI. Morgan Kaufmann 560\u2013566.   Leslie G. Valiant. 1985. Learning Disjunction of Conjunctions. In IJCAI. Morgan Kaufmann 560\u2013566."},{"key":"e_1_3_2_2_88_1","unstructured":"Santosh Vempala and Grant Wang. 2002.  Santosh Vempala and Grant Wang. 2002."},{"key":"e_1_3_2_2_89_1","unstructured":"A Spectral Algorithm for Learning Mixtures of Distributions. In FOCS. IEEE Computer Society 113.   A Spectral Algorithm for Learning Mixtures of Distributions. In FOCS. IEEE Computer Society 113."},{"key":"e_1_3_2_2_90_1","unstructured":"CF Jeff Wu. 1983.  CF Jeff Wu. 1983."},{"key":"e_1_3_2_2_91_1","volume-title":"The Annals of statistics","author":"On","year":"1983"},{"key":"e_1_3_2_2_92_1","unstructured":"Ji Xu Daniel J Hsu and Arian Maleki. 2016.  Ji Xu Daniel J Hsu and Arian Maleki. 2016."},{"key":"e_1_3_2_2_93_1","unstructured":"Global analysis of expectation maximization for mixtures of two gaussians. In Advances in Neural Information Processing Systems. 2676\u20132684.  Global analysis of expectation maximization for mixtures of two gaussians. In Advances in Neural Information Processing Systems. 2676\u20132684."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188748","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188748","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:08Z","timestamp":1750212428000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":93,"alternative-id":["10.1145\/3188745.3188748","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188748","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}