{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T10:29:21Z","timestamp":1760956161316,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519953","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1234-1247","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Robustly learning mixtures of<i>k<\/i>arbitrary Gaussians"],"prefix":"10.1145","author":[{"given":"Ainesh","family":"Bakshi","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Ilias","family":"Diakonikolas","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}]},{"given":"He","family":"Jia","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}]},{"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Santosh S.","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"volume-title":"Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT). 458\u2013469","author":"Achlioptas D.","unstructured":"D. Achlioptas and F. McSherry . 2005. On Spectral Learning of Mixtures of Distributions . In Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT). 458\u2013469 . D. Achlioptas and F. McSherry. 2005. On Spectral Learning of Mixtures of Distributions. In Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT). 458\u2013469.","key":"e_1_3_2_1_1_1"},{"volume-title":"Proceedings of the 33rd Symposium on Theory of Computing. 247\u2013257","author":"Arora S.","unstructured":"S. Arora and R. Kannan . 2001. Learning mixtures of arbitrary Gaussians . In Proceedings of the 33rd Symposium on Theory of Computing. 247\u2013257 . S. Arora and R. Kannan. 2001. Learning mixtures of arbitrary Gaussians. In Proceedings of the 33rd Symposium on Theory of Computing. 247\u2013257.","key":"e_1_3_2_1_2_1"},{"volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425","author":"Ashtiani H.","unstructured":"H. Ashtiani , S. Ben-David , N. Harvey , C. Liaw , A. Mehrabian , and Y. Plan . 2018. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes . In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425 . H. Ashtiani, S. Ben-David, N. Harvey, C. Liaw, A. Mehrabian, and Y. Plan. 2018. Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425.","key":"e_1_3_2_1_3_1"},{"unstructured":"A. Bakshi I. Diakonikolas H. Jia D. M. Kane P. K. Kothari and S. S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs\/2012.02119 (2020) arxiv:2012.02119. Available at https:\/\/arxiv.org\/abs\/2012.02119v3 A. Bakshi I. Diakonikolas H. Jia D. M. Kane P. K. Kothari and S. S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs\/2012.02119 (2020) arxiv:2012.02119. Available at https:\/\/arxiv.org\/abs\/2012.02119v3","key":"e_1_3_2_1_4_1"},{"unstructured":"A. Bakshi I. Diakonikolas H. Jia D. M. Kane P. K. Kothari and S. S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs\/2012.02119 (2020) arxiv:2012.02119. Available at https:\/\/arxiv.org\/abs\/2012.02119v2 A. Bakshi I. Diakonikolas H. Jia D. M. Kane P. K. Kothari and S. S. Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs\/2012.02119 (2020) arxiv:2012.02119. Available at https:\/\/arxiv.org\/abs\/2012.02119v2","key":"e_1_3_2_1_5_1"},{"unstructured":"A. Bakshi and P. Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139. A. Bakshi and P. Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139.","key":"e_1_3_2_1_6_1"},{"unstructured":"A. Bakshi and P. Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR abs\/2005.02970 (2020) arxiv:2005.02970. arxiv:2005.02970 A. Bakshi and P. Kothari. 2020. Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR abs\/2005.02970 (2020) arxiv:2005.02970. arxiv:2005.02970","key":"e_1_3_2_1_7_1"},{"doi-asserted-by":"crossref","unstructured":"A. Bakshi and A. Prasad. 2020. Robust linear regression: Optimal rates in polynomial time. arXiv preprint arXiv:2007.01394. A. Bakshi and A. Prasad. 2020. Robust linear regression: Optimal rates in polynomial time. arXiv preprint arXiv:2007.01394.","key":"e_1_3_2_1_8_1","DOI":"10.1145\/3406325.3451001"},{"volume-title":"Proc. 30th Annual Conference on Learning Theory. 169\u2013212","author":"Balakrishnan S.","unstructured":"S. Balakrishnan , S. S. Du , J. Li , and A. Singh . 2017. Computationally Efficient Robust Sparse Estimation in High Dimensions . In Proc. 30th Annual Conference on Learning Theory. 169\u2013212 . S. Balakrishnan, S. S. Du, J. Li, and A. Singh. 2017. Computationally Efficient Robust Sparse Estimation in High Dimensions. In Proc. 30th Annual Conference on Learning Theory. 169\u2013212.","key":"e_1_3_2_1_9_1"},{"volume-title":"Proceedings of the fortieth annual ACM symposium on Theory of computing. 671\u2013680","author":"Balcan M.-F.","unstructured":"M.-F. Balcan , A. Blum , and S. Vempala . 2008. A discriminative framework for clustering via similarity functions . In Proceedings of the fortieth annual ACM symposium on Theory of computing. 671\u2013680 . M.-F. Balcan, A. Blum, and S. Vempala. 2008. A discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing. 671\u2013680.","key":"e_1_3_2_1_10_1"},{"volume-title":"2015 ACM Symposium on Theory of Computing. ACM","author":"Barak B.","unstructured":"B. Barak , J. A. Kelner , and D. Steurer . 2015. Dictionary learning and tensor decomposition via the sum-of-squares method [extended abstract]. In STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM , New York, 143\u2013151. B. Barak, J. A. Kelner, and D. Steurer. 2015. Dictionary learning and tensor decomposition via the sum-of-squares method [extended abstract]. In STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM, New York, 143\u2013151.","key":"e_1_3_2_1_11_1"},{"doi-asserted-by":"crossref","unstructured":"M. Belkin and K. Sinha. 2010. Polynomial Learning of Distribution Families. In FOCS. 103\u2013112. M. Belkin and K. Sinha. 2010. Polynomial Learning of Distribution Families. In FOCS. 103\u2013112.","key":"e_1_3_2_1_12_1","DOI":"10.1109\/FOCS.2010.16"},{"volume-title":"Proc. 49th IEEE Symposium on Foundations of Computer Science. 551\u2013560","author":"Brubaker S. C.","unstructured":"S. C. Brubaker and S. Vempala . 2008. Isotropic PCA and Affine-Invariant Clustering . In Proc. 49th IEEE Symposium on Foundations of Computer Science. 551\u2013560 . S. C. Brubaker and S. Vempala. 2008. Isotropic PCA and Affine-Invariant Clustering. In Proc. 49th IEEE Symposium on Foundations of Computer Science. 551\u2013560.","key":"e_1_3_2_1_13_1"},{"volume-title":"Proc. 49th Annual ACM Symposium on Theory of Computing. 47\u201360","author":"Charikar M.","unstructured":"M. Charikar , J. Steinhardt , and G. Valiant . 2017. Learning from untrusted data . In Proc. 49th Annual ACM Symposium on Theory of Computing. 47\u201360 . M. Charikar, J. Steinhardt, and G. Valiant. 2017. Learning from untrusted data. In Proc. 49th Annual ACM Symposium on Theory of Computing. 47\u201360.","key":"e_1_3_2_1_14_1"},{"unstructured":"Y. Cheng I. Diakonikolas R. Ge and M. Soltanolkotabi. 2020. High-Dimensional Robust Mean Estimation via Gradient Descent. CoRR abs\/2005.01378 (2020) arxiv:2005.01378. arxiv:2005.01378 Y. Cheng I. Diakonikolas R. Ge and M. Soltanolkotabi. 2020. High-Dimensional Robust Mean Estimation via Gradient Descent. CoRR abs\/2005.01378 (2020) arxiv:2005.01378. arxiv:2005.01378","key":"e_1_3_2_1_15_1"},{"volume-title":"Proc. 33rd Annual Conference on Neural Information Processing Systems (NeurIPS). 10304\u201310316","author":"Cheng Y.","unstructured":"Y. Cheng , I. Diakonikolas , D. M. Kane , and A. Stewart . 2018. Robust Learning of Fixed-Structure Bayesian Networks . In Proc. 33rd Annual Conference on Neural Information Processing Systems (NeurIPS). 10304\u201310316 . Y. Cheng, I. Diakonikolas, D. M. Kane, and A. Stewart. 2018. Robust Learning of Fixed-Structure Bayesian Networks. In Proc. 33rd Annual Conference on Neural Information Processing Systems (NeurIPS). 10304\u201310316.","key":"e_1_3_2_1_16_1"},{"unstructured":"Y. Cherapanamjeri E. Aras N. Tripuraneni M. I. Jordan N. Flammarion and P. L. Bartlett. 2020. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137. Y. Cherapanamjeri E. Aras N. Tripuraneni M. I. Jordan N. Flammarion and P. L. Bartlett. 2020. Optimal robust linear regression in nearly linear time. arXiv preprint arXiv:2007.08137.","key":"e_1_3_2_1_17_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1109\/SFFCS.1999.814639"},{"unstructured":"I. Diakonikolas S. B. Hopkins D. Kane and S. Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. CoRR abs\/2005.06417 (2020) arxiv:2005.06417. arxiv:2005.06417 I. Diakonikolas S. B. Hopkins D. Kane and S. Karmalkar. 2020. Robustly Learning any Clusterable Mixture of Gaussians. CoRR abs\/2005.06417 (2020) arxiv:2005.06417. arxiv:2005.06417","key":"e_1_3_2_1_19_1"},{"volume-title":"Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 655\u2013664","author":"Diakonikolas I.","unstructured":"I. Diakonikolas , G. Kamath , D. M. Kane , J. Li , A. Moitra , and A. Stewart . 2016. Robust Estimators in High Dimensions without the Computational Intractability . In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 655\u2013664 . I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2016. Robust Estimators in High Dimensions without the Computational Intractability. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 655\u2013664.","key":"e_1_3_2_1_20_1"},{"volume-title":"Proc. 34th International Conference on Machine Learning (ICML). 999\u20131008","author":"Diakonikolas I.","unstructured":"I. Diakonikolas , G. Kamath , D. M. Kane , J. Li , A. Moitra , and A. Stewart . 2017. Being Robust (in High Dimensions) Can Be Practical . In Proc. 34th International Conference on Machine Learning (ICML). 999\u20131008 . I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2017. Being Robust (in High Dimensions) Can Be Practical. In Proc. 34th International Conference on Machine Learning (ICML). 999\u20131008.","key":"e_1_3_2_1_21_1"},{"key":"e_1_3_2_1_22_1","volume-title":"Sever: A Robust Meta-Algorithm for Stochastic Optimization. CoRR, abs\/1803.02815","author":"Diakonikolas I.","year":"2018","unstructured":"I. Diakonikolas , G. Kamath , D. M. Kane , J. Li , J. Steinhardt , and A. Stewart . 2018 . Sever: A Robust Meta-Algorithm for Stochastic Optimization. CoRR, abs\/1803.02815 (2018), arxiv:1803.02815. arxiv:1803.02815 Conference version in ICML 2019. I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. 2018. Sever: A Robust Meta-Algorithm for Stochastic Optimization. CoRR, abs\/1803.02815 (2018), arxiv:1803.02815. arxiv:1803.02815 Conference version in ICML 2019."},{"unstructured":"I. Diakonikolas and D. M. Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR abs\/1911.05911 (2019) arxiv:1911.05911 I. Diakonikolas and D. M. Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR abs\/1911.05911 (2019) arxiv:1911.05911","key":"e_1_3_2_1_23_1"},{"volume-title":"Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS). 73\u201384","author":"Diakonikolas I.","unstructured":"I. Diakonikolas , D. M. Kane , and A. Stewart . 2017. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures . In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS). 73\u201384 . I. Diakonikolas, D. M. Kane, and A. Stewart. 2017. Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. In Proc. 58th IEEE Symposium on Foundations of Computer Science (FOCS). 73\u201384.","key":"e_1_3_2_1_24_1"},{"volume-title":"Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1047\u20131060","author":"Diakonikolas I.","unstructured":"I. Diakonikolas , D. M. Kane , and A. Stewart . 2018. List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians . In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1047\u20131060 . I. Diakonikolas, D. M. Kane, and A. Stewart. 2018. List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1047\u20131060.","key":"e_1_3_2_1_25_1"},{"unstructured":"I. Diakonikolas S. Karmalkar D. Kane E. Price and A. Stewart. 2019. Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. In Advances in Neural Information Processing Systems 33 NeurIPS 2019. I. Diakonikolas S. Karmalkar D. Kane E. Price and A. Stewart. 2019. Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. In Advances in Neural Information Processing Systems 33 NeurIPS 2019.","key":"e_1_3_2_1_26_1"},{"volume-title":"Proc. 30th Annual Symposium on Discrete Algorithms (SODA). 2745\u20132754","author":"Diakonikolas I.","unstructured":"I. Diakonikolas , W. Kong , and A. Stewart . 2019. Efficient Algorithms and Lower Bounds for Robust Linear Regression . In Proc. 30th Annual Symposium on Discrete Algorithms (SODA). 2745\u20132754 . I. Diakonikolas, W. Kong, and A. Stewart. 2019. Efficient Algorithms and Lower Bounds for Robust Linear Regression. In Proc. 30th Annual Symposium on Discrete Algorithms (SODA). 2745\u20132754.","key":"e_1_3_2_1_27_1"},{"unstructured":"I. Diakonikolas S. Vempala and D. Woodruff. 2019. Research vignette: Foundations of Data Science. UC Berkeley Simons Institute newsletter September. I. Diakonikolas S. Vempala and D. Woodruff. 2019. Research vignette: Foundations of Data Science. UC Berkeley Simons Institute newsletter September.","key":"e_1_3_2_1_28_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1561\/0400000086"},{"doi-asserted-by":"crossref","unstructured":"A. Frieze M. Jerrum and R. Kannan. 1996. Learning Linear Transformations. In focs1996. 359\u2013368. A. Frieze M. Jerrum and R. Kannan. 1996. Learning Linear Transformations. In focs1996. 359\u2013368.","key":"e_1_3_2_1_30_1","DOI":"10.1109\/SFCS.1996.548495"},{"unstructured":"A. Garg N. Kayal and C. Saha. 2020. Learning sums of powers of low-degree polynomials in the non-degenerate case. CoRR abs\/2004.06898 (2020) arxiv:2004.06898. arxiv:2004.06898 A. Garg N. Kayal and C. Saha. 2020. Learning sums of powers of low-degree polynomials in the non-degenerate case. CoRR abs\/2004.06898 (2020) arxiv:2004.06898. arxiv:2004.06898","key":"e_1_3_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/2746539.2746616"},{"volume-title":"Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 584\u2013593","author":"Goyal N.","unstructured":"N. Goyal , S. Vempala , and Y. Xiao . 2014. Fourier PCA and robust tensor decomposition . In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 584\u2013593 . N. Goyal, S. Vempala, and Y. Xiao. 2014. Fourier PCA and robust tensor decomposition. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 584\u2013593.","key":"e_1_3_2_1_33_1"},{"unstructured":"F. R. Hampel E. M. Ronchetti P. J. Rousseeuw and W. A. Stahel. 1986. Robust statistics. The approach based on influence functions. Wiley New York. F. R. Hampel E. M. Ronchetti P. J. Rousseeuw and W. A. Stahel. 1986. Robust statistics. The approach based on influence functions. Wiley New York.","key":"e_1_3_2_1_34_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1145\/2746539.2746579"},{"volume-title":"Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1021\u20131034","author":"Hopkins S. B.","unstructured":"S. B. Hopkins and J. Li . 2018. Mixture models, robustness, and sum of squares proofs . In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1021\u20131034 . S. B. Hopkins and J. Li. 2018. Mixture models, robustness, and sum of squares proofs. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1021\u20131034.","key":"e_1_3_2_1_36_1"},{"doi-asserted-by":"crossref","unstructured":"D. Hsu and S. M. Kakade. 2013. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Innovations in Theoretical Computer Science ITCS \u201913. 11\u201320. D. Hsu and S. M. Kakade. 2013. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Innovations in Theoretical Computer Science ITCS \u201913. 11\u201320.","key":"e_1_3_2_1_37_1","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_38_1","volume-title":"Robust Estimation of a Location Parameter. Ann. Math. Statist., 35, 1","author":"Huber P. J.","year":"1964","unstructured":"P. J. Huber . 1964. Robust Estimation of a Location Parameter. Ann. Math. Statist., 35, 1 ( 1964 ), 03, 73\u2013101. P. J. Huber. 1964. Robust Estimation of a Location Parameter. Ann. Math. Statist., 35, 1 (1964), 03, 73\u2013101."},{"doi-asserted-by":"crossref","unstructured":"P. J. Huber and E. M. Ronchetti. 2009. Robust statistics. Wiley New York. P. J. Huber and E. M. Ronchetti. 2009. Robust statistics. Wiley New York.","key":"e_1_3_2_1_39_1","DOI":"10.1002\/9780470434697"},{"doi-asserted-by":"crossref","unstructured":"A. T. Kalai A. Moitra and G. Valiant. 2010. Efficiently learning mixtures of two Gaussians. In STOC. 553\u2013562. A. T. Kalai A. Moitra and G. Valiant. 2010. Efficiently learning mixtures of two Gaussians. In STOC. 553\u2013562.","key":"e_1_3_2_1_40_1","DOI":"10.1145\/1806689.1806765"},{"key":"e_1_3_2_1_41_1","volume-title":"Robust Learning of Mixtures of Gaussians. CoRR, abs\/2007.05912","author":"Kane D. M.","year":"2020","unstructured":"D. M. Kane . 2020. Robust Learning of Mixtures of Gaussians. CoRR, abs\/2007.05912 ( 2020 ), arxiv:2007.05912. arxiv:2007.05912 D. M. Kane. 2020. Robust Learning of Mixtures of Gaussians. CoRR, abs\/2007.05912 (2020), arxiv:2007.05912. arxiv:2007.05912"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1137\/S0097539704445925"},{"unstructured":"S. Karmalkar A. Klivans and P. Kothari. 2019. List-decodable linear regression. In Advances in Neural Information Processing Systems. 7423\u20137432. S. Karmalkar A. Klivans and P. Kothari. 2019. List-decodable linear regression. In Advances in Neural Information Processing Systems. 7423\u20137432.","key":"e_1_3_2_1_43_1"},{"volume-title":"Proc. 31st Annual Conference on Learning Theory (COLT). 1420\u20131430","author":"Klivans A.","unstructured":"A. Klivans , P. Kothari , and R. Meka . 2018. Efficient Algorithms for Outlier-Robust Regression . In Proc. 31st Annual Conference on Learning Theory (COLT). 1420\u20131430 . A. Klivans, P. Kothari, and R. Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Proc. 31st Annual Conference on Learning Theory (COLT). 1420\u20131430.","key":"e_1_3_2_1_44_1"},{"unstructured":"P. K. Kothari and J. Steinhardt. 2017. Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR abs\/1711.07465 (2017) arxiv:1711.07465. arxiv:1711.07465 P. K. Kothari and J. Steinhardt. 2017. Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR abs\/1711.07465 (2017) arxiv:1711.07465. arxiv:1711.07465","key":"e_1_3_2_1_45_1"},{"volume-title":"Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1035\u20131046","author":"Kothari P. K.","unstructured":"P. K. Kothari , J. Steinhardt , and D. Steurer . 2018. Robust moment estimation and improved clustering via sum of squares . In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1035\u20131046 . P. K. Kothari, J. Steinhardt, and D. Steurer. 2018. Robust moment estimation and improved clustering via sum of squares. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC). 1035\u20131046.","key":"e_1_3_2_1_46_1"},{"unstructured":"P. K. Kothari and D. Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. CoRR abs\/1711.11581 (2017) arxiv:1711.11581. arxiv:1711.11581 P. K. Kothari and D. Steurer. 2017. Outlier-robust moment-estimation via sum-of-squares. CoRR abs\/1711.11581 (2017) arxiv:1711.11581. arxiv:1711.11581","key":"e_1_3_2_1_47_1"},{"volume-title":"Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 665\u2013674","author":"Lai K. A.","unstructured":"K. A. Lai , A. B. Rao , and S. Vempala . 2016. Agnostic Estimation of Mean and Covariance . In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 665\u2013674 . K. A. Lai, A. B. Rao, and S. Vempala. 2016. Agnostic Estimation of Mean and Covariance. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS). 665\u2013674.","key":"e_1_3_2_1_48_1"},{"doi-asserted-by":"crossref","unstructured":"A. Liu and A. Moitra. 2020. Settling the Robust Learnability of Mixtures of Gaussians. arXiv preprint arXiv:2011.03622. A. Liu and A. Moitra. 2020. Settling the Robust Learnability of Mixtures of Gaussians. arXiv preprint arXiv:2011.03622.","key":"e_1_3_2_1_49_1","DOI":"10.1145\/3406325.3451084"},{"doi-asserted-by":"crossref","unstructured":"A. Moitra and G. Valiant. 2010. Settling the polynomial learnability of mixtures of Gaussians. In FOCS. 93\u2013102. A. Moitra and G. Valiant. 2010. Settling the polynomial learnability of mixtures of Gaussians. In FOCS. 93\u2013102.","key":"e_1_3_2_1_50_1","DOI":"10.1109\/FOCS.2010.15"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1098\/rsta.1894.0003"},{"unstructured":"A. Prasad A. S. Suggala S. Balakrishnan and P. Ravikumar. 2018. Robust Estimation via Robust Gradient Estimation. arXiv preprint arXiv:1802.06485. A. Prasad A. S. Suggala S. Balakrishnan and P. Ravikumar. 2018. Robust Estimation via Robust Gradient Estimation. arXiv preprint arXiv:1802.06485.","key":"e_1_3_2_1_52_1"},{"volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 161\u2013180","author":"Raghavendra P.","unstructured":"P. Raghavendra and M. Yau . 2020. List decodable learning via sum of squares . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 161\u2013180 . P. Raghavendra and M. Yau. 2020. List decodable learning via sum of squares. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 161\u2013180.","key":"e_1_3_2_1_53_1"},{"unstructured":"P. Raghavendra and M. Yau. 2020. List Decodable Subspace Recovery. arXiv preprint arXiv:2002.03004. P. Raghavendra and M. Yau. 2020. List Decodable Subspace Recovery. arXiv preprint arXiv:2002.03004.","key":"e_1_3_2_1_54_1"},{"key":"e_1_3_2_1_55_1","volume-title":"Spectral Signatures in Backdoor Attacks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Tran B.","year":"2018","unstructured":"B. Tran , J. Li , and A. Madry . 2018 . Spectral Signatures in Backdoor Attacks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018 . 8011\u20138021. B. Tran, J. Li, and A. Madry. 2018. Spectral Signatures in Backdoor Attacks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018. 8011\u20138021."},{"volume-title":"Proc. 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 113\u2013122","author":"Vempala S.","unstructured":"S. Vempala and G. Wang . 2002. A Spectral Algorithm for learning mixtures of distributions . In Proc. 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 113\u2013122 . S. Vempala and G. Wang. 2002. A Spectral Algorithm for learning mixtures of distributions. In Proc. 43rd IEEE Symposium on Foundations of Computer Science (FOCS). 113\u2013122.","key":"e_1_3_2_1_56_1"},{"unstructured":"B. Zhu J. Jiao and J. Steinhardt. 2020. Robust estimation via generalized quasi-gradients. arXiv preprint arXiv:2005.14073. B. Zhu J. Jiao and J. Steinhardt. 2020. Robust estimation via generalized quasi-gradients. arXiv preprint arXiv:2005.14073.","key":"e_1_3_2_1_57_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '22","name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519953","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519953","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519953"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":57,"alternative-id":["10.1145\/3519935.3519953","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519953","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}