{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T16:12:08Z","timestamp":1654963928373},"publisher-location":"New York, NY, USA","reference-count":91,"publisher":"ACM","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520014","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"source":"Crossref","is-referenced-by-count":0,"title":["Clustering mixture models in almost-linear time via list-decodable mean estimation"],"prefix":"10.1145","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, USA"}]},{"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Daniel","family":"Kongsgaard","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Kevin","family":"Tian","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.83"},{"key":"e_1_3_2_1_2_1","unstructured":"Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746. Jayadev Acharya Ashkan Jafarpour Alon Orlitsky and Ananda Theertha Suresh. 2014. Near-optimal-sample estimators for spherical gaussian mixtures. arXiv preprint arXiv:1402.4746."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_2_1_4_1","volume-title":"International Conference on Computational Learning Theory. 458\u2013469","author":"Achlioptas Dimitris","year":"2005","unstructured":"Dimitris Achlioptas and Frank McSherry . 2005 . On spectral learning of mixtures of distributions . In International Conference on Computational Learning Theory. 458\u2013469 . Dimitris Achlioptas and Frank McSherry. 2005. On spectral learning of mixtures of distributions. In International Conference on Computational Learning Theory. 458\u2013469."},{"key":"e_1_3_2_1_5_1","volume-title":"Conference on Learning Theory. 1135\u20131164","author":"Anderson Joseph","year":"2014","unstructured":"Joseph Anderson , Mikhail Belkin , Navin Goyal , Luis Rademacher , and James Voss . 2014 . The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures . In Conference on Learning Theory. 1135\u20131164 . Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, and James Voss. 2014. The more, the merrier: the blessing of dimensionality for learning large gaussian mixtures. In Conference on Learning Theory. 1135\u20131164."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1960.10489888"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000512"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems. 3416\u20133425","author":"Ashtiani Hassan","year":"2018","unstructured":"Hassan Ashtiani , Shai Ben-David , Nicholas JA Harvey , Christopher Liaw , Abbas Mehrabian , and Yaniv 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 . Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv 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_10_1","unstructured":"Pranjal Awasthi. 2021. September Personal communication Pranjal Awasthi. 2021. September Personal communication"},{"key":"e_1_3_2_1_11_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Awasthi Pranjal","unstructured":"Pranjal Awasthi and Or Sheffet . 2012. Improved spectral-norm bounds for clustering . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Springer , 37\u201349. Pranjal Awasthi and Or Sheffet. 2012. Improved spectral-norm bounds for clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 37\u201349."},{"key":"e_1_3_2_1_12_1","volume-title":"Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi , Ilias Diakonikolas , Samuel B. Hopkins , Daniel Kane , Sushrut Karmalkar , and Pravesh K. Kothari . 2020 . Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 . IEEE, 149\u2013159. Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, and Pravesh K. Kothari. 2020. Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE, 149\u2013159."},{"key":"e_1_3_2_1_13_1","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. arXiv preprint arXiv:2012.02119. Ainesh Bakshi Ilias Diakonikolas He Jia Daniel M Kane Pravesh K Kothari and Santosh S Vempala. 2020. Robustly Learning Mixtures of k Arbitrary Gaussians. arXiv preprint arXiv:2012.02119."},{"key":"e_1_3_2_1_14_1","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139. Ainesh Bakshi and Pravesh Kothari. 2020. List-Decodable Subspace Recovery via Sum-of-Squares. arXiv preprint arXiv:2002.05139."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-robust clustering of non-spherical mixtures. arXiv preprint arXiv:2005.02970. Ainesh Bakshi and Pravesh Kothari. 2020. Outlier-robust clustering of non-spherical mixtures. arXiv preprint arXiv:2005.02970.","DOI":"10.1109\/FOCS46700.2020.00023"},{"key":"e_1_3_2_1_16_1","volume-title":"Conference on Learning Theory. 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. 169\u2013212 . Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh. 2017. Computationally efficient robust sparse estimation in high dimensions. In Conference on Learning Theory. 169\u2013212."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374474"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5188-5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090818X"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 29th International Conference on Machine Learning, ICML 2012","author":"Biggio Battista","year":"2012","unstructured":"Battista Biggio , Blaine Nelson , and Pavel Laskov . 2012 . Poisoning Attacks against Support Vector Machines . In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 , Edinburgh, Scotland, UK, June 26 - July 1, 2012. Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning Attacks against Support Vector Machines. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012."},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"Brubaker S. Charles","year":"2009","unstructured":"S. Charles Brubaker . 2009 . Robust PCA and clustering in noisy mixtures . In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009 , New York, NY, USA , January 4-6, 2009, Claire Mathieu (Ed.). SIAM, 1078\u20131087. S. Charles Brubaker. 2009. Robust PCA and clustering in noisy mixtures. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, Claire Mathieu (Ed.). SIAM, 1078\u20131087."},{"key":"e_1_3_2_1_23_1","volume-title":"Isotropic PCA and Affine-Invariant Clustering. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008","author":"Charles Brubaker S.","year":"2008","unstructured":"S. Charles Brubaker and Santosh S. Vempala . 2008 . Isotropic PCA and Affine-Invariant Clustering. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 , October 25-28, 2008 , Philadelphia, PA, USA. 551\u2013560. S. Charles Brubaker and Santosh S. Vempala. 2008. Isotropic PCA and Affine-Invariant Clustering. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. 551\u2013560."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591848"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC","author":"Charikar Moses","year":"2017","unstructured":"Moses Charikar , Jacob Steinhardt , and Gregory Valiant . 2017 . Learning from untrusted data . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC , Canada , June 19-23, 2017. 47\u201360. Moses Charikar, Jacob Steinhardt, and Gregory Valiant. 2017. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017. 47\u201360."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2755\u20132771","author":"Cheng Yu","year":"2019","unstructured":"Yu Cheng , Ilias Diakonikolas , and Rong Ge . 2019 . High-dimensional robust mean estimation in nearly-linear time . In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2755\u20132771 . Yu Cheng, Ilias Diakonikolas, and Rong Ge. 2019. High-dimensional robust mean estimation in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. 2755\u20132771."},{"key":"e_1_3_2_1_27_1","volume-title":"Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Conference on Learning Theory. 727\u2013757","author":"Cheng Yu","year":"2019","unstructured":"Yu Cheng , Ilias Diakonikolas , Rong Ge , and David P Woodruff . 2019 . Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Conference on Learning Theory. 727\u2013757 . Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P Woodruff. 2019. Faster Algorithms for High-Dimensional Robust Covariance Estimation. In Conference on Learning Theory. 727\u2013757."},{"key":"e_1_3_2_1_28_1","unstructured":"Yu Cheng Ilias Diakonikolas Daniel Kane and Alistair Stewart. 2018. Robust learning of fixed-structure bayesian networks. In Advances in Neural Information Processing Systems. 10283\u201310295. Yu Cheng Ilias Diakonikolas Daniel Kane and Alistair Stewart. 2018. Robust learning of fixed-structure bayesian networks. In Advances in Neural Information Processing Systems. 10283\u201310295."},{"key":"e_1_3_2_1_29_1","volume-title":"List Decodable Mean Estimation in Nearly Linear Time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Cherapanamjeri Yeshwanth","year":"2020","unstructured":"Yeshwanth Cherapanamjeri , Sidhanth Mohanty , and Morris Yau . 2020 . List Decodable Mean Estimation in Nearly Linear Time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. Yeshwanth Cherapanamjeri, Sidhanth Mohanty, and Morris Yau. 2020. List Decodable Mean Estimation in Nearly Linear Time. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020."},{"key":"e_1_3_2_1_30_1","volume-title":"40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)","author":"Dasgupta Sanjoy","year":"1999","unstructured":"Sanjoy Dasgupta . 1999 . Learning mixtures of Gaussians . In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) . 634\u2013644. Sanjoy Dasgupta. 1999. Learning mixtures of Gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039). 634\u2013644."},{"key":"e_1_3_2_1_31_1","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical Gaussians","author":"Dasgupta Sanjoy","year":"2007","unstructured":"Sanjoy Dasgupta and Leonard Schulman . 2007 . A probabilistic analysis of EM for mixtures of separated, spherical Gaussians . Journal of Machine Learning Research, 8 , Feb (2007), 203 \u2013 226 . Sanjoy Dasgupta and Leonard Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. Journal of Machine Learning Research, 8, Feb (2007), 203\u2013226.","journal-title":"Journal of Machine Learning Research, 8"},{"key":"e_1_3_2_1_32_1","volume-title":"Training GANs with Optimism. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings.","author":"Daskalakis Constantinos","year":"2018","unstructured":"Constantinos Daskalakis , Andrew Ilyas , Vasilis Syrgkanis , and Haoyang Zeng . 2018 . Training GANs with Optimism. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. 2018. Training GANs with Optimism. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings."},{"key":"e_1_3_2_1_33_1","volume-title":"Conference on Learning Theory. 1183\u20131213","author":"Daskalakis Constantinos","year":"2014","unstructured":"Constantinos Daskalakis and Gautam Kamath . 2014 . Faster and sample near-optimal algorithms for proper learning mixtures of gaussians . In Conference on Learning Theory. 1183\u20131213 . Constantinos Daskalakis and Gautam Kamath. 2014. Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory. 1183\u20131213."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"e_1_3_2_1_35_1","volume-title":"Combinatorial methods in density estimation","author":"Devroye Luc","unstructured":"Luc Devroye and G\u00e1bor Lugosi . 2012. Combinatorial methods in density estimation . Springer Science & Business Media . Luc Devroye and G\u00e1bor Lugosi. 2012. Combinatorial methods in density estimation. Springer Science & Business Media."},{"key":"e_1_3_2_1_36_1","unstructured":"Ilias Diakonikolas Samuel B Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly learning any clusterable mixture of gaussians. arXiv preprint arXiv:2005.06417. Ilias Diakonikolas Samuel B Hopkins Daniel Kane and Sushrut Karmalkar. 2020. Robustly learning any clusterable mixture of gaussians. arXiv preprint arXiv:2005.06417."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"e_1_3_2_1_38_1","volume-title":"International Conference on Machine Learning. 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. 1596\u20131606 . 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. 1596\u20131606."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","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, ICML 2017 , Sydney, NSW, Australia , 6-11 August 2017. 999\u20131008. 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, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 999\u20131008."},{"key":"e_1_3_2_1_40_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Diakonikolas Ilias","year":"2019","unstructured":"Ilias Diakonikolas , Daniel Kane , Sushrut Karmalkar , Eric Price , and Alistair Stewart . 2019 . Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 10688\u201310699. http:\/\/papers.nips.cc\/paper\/9253-outlier-robust-high-dimensional-sparse-estimation-via-iterative-filtering Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. 2019. Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 10688\u201310699. http:\/\/papers.nips.cc\/paper\/9253-outlier-robust-high-dimensional-sparse-estimation-via-iterative-filtering"},{"key":"e_1_3_2_1_41_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Daniel Kane , and Daniel Kongsgaard . 2020 . List-Decodable Mean Estimation via Iterative Multi-Filtering . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual. Ilias Diakonikolas, Daniel Kane, and Daniel Kongsgaard. 2020. List-Decodable Mean Estimation via Iterative Multi-Filtering. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual."},{"key":"e_1_3_2_1_42_1","volume-title":"Advances in Neural Information Processing Systems","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas , Daniel Kane , Daniel Kongsgaard , Jerry Li , and Kevin Tian . 2021. List-Decodable Mean Estimation in Nearly-PCA Time . In Advances in Neural Information Processing Systems , M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.). 34, Curran Associates, Inc. , 10195\u201310208. https:\/\/proceedings.neurips.cc\/paper\/ 2021 \/file\/547b85f3fafdf30856386753dc21c4e1-Paper.pdf Ilias Diakonikolas, Daniel Kane, Daniel Kongsgaard, Jerry Li, and Kevin Tian. 2021. List-Decodable Mean Estimation in Nearly-PCA Time. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.). 34, Curran Associates, Inc., 10195\u201310208. https:\/\/proceedings.neurips.cc\/paper\/2021\/file\/547b85f3fafdf30856386753dc21c4e1-Paper.pdf"},{"key":"e_1_3_2_1_43_1","unstructured":"Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911. Ilias Diakonikolas and Daniel M Kane. 2019. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint arXiv:1911.05911."},{"key":"e_1_3_2_1_44_1","volume-title":"Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas and Daniel M. Kane . 2020 . Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 . IEEE, 184\u2013195. Ilias Diakonikolas and Daniel M. Kane. 2020. Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE, 184\u2013195."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310605"},{"key":"e_1_3_2_1_47_1","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems","author":"Dong Yihe","year":"2019","unstructured":"Yihe Dong , Samuel B. Hopkins , and Jerry Li. 2019. Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection . In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada . 6065\u20136075. Yihe Dong, Samuel B. Hopkins, and Jerry Li. 2019. Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada. 6065\u20136075."},{"key":"e_1_3_2_1_48_1","volume-title":"International Conference on Computational Learning Theory. 20\u201334","author":"Feldman Jon","year":"2006","unstructured":"Jon Feldman , Rocco A Servedio , and Ryan O\u2019Donnell . 2006 . PAC learning axis-aligned mixtures of Gaussians with no separation assumption . In International Conference on Computational Learning Theory. 20\u201334 . Jon Feldman, Rocco A Servedio, and Ryan O\u2019Donnell. 2006. PAC learning axis-aligned mixtures of Gaussians with no separation assumption. In International Conference on Computational Learning Theory. 20\u201334."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"e_1_3_2_1_50_1","volume-title":"Stahel","author":"Hampel Frank R.","year":"1986","unstructured":"Frank R. Hampel , Elvezio M. Ronchetti , Peter J. Rousseeuw , and Werner A . Stahel . 1986 . Robust Statistics: the Approach based on Influence Functions. Wiley Series in Probability and Mathematical Statistics. Frank R. Hampel, Elvezio M. Ronchetti, Peter J. Rousseeuw, and Werner A. Stahel. 1986. Robust Statistics: the Approach based on Influence Functions. Wiley Series in Probability and Mathematical Statistics."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703732"},{"key":"e_1_3_2_1_55_1","volume-title":"Robust statistics. 523","author":"Huber Peter J","unstructured":"Peter J Huber . 2004. Robust statistics. 523 , John Wiley & Sons . Peter J Huber. 2004. Robust statistics. 523, John Wiley & Sons."},{"key":"e_1_3_2_1_56_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"Jambulapati Arun","year":"2020","unstructured":"Arun Jambulapati , Jerry Li , and Kevin Tian . 2020. Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual. Arun Jambulapati, Jerry Li, and Kevin Tian. 2020. Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual."},{"key":"e_1_3_2_1_57_1","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 1246\u20131258","author":"Kane Daniel M","year":"2021","unstructured":"Daniel M Kane . 2021 . Robust learning of mixtures of gaussians . In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 1246\u20131258 . Daniel M Kane. 2021. Robust learning of mixtures of gaussians. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). 1246\u20131258."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445925"},{"key":"e_1_3_2_1_59_1","unstructured":"Sushrut Karmalkar Adam Klivans and Pravesh Kothari. 2019. List-decodable linear regression. In Advances in Neural Information Processing Systems. 7425\u20137434. Sushrut Karmalkar Adam Klivans and Pravesh Kothari. 2019. List-decodable linear regression. In Advances in Neural Information Processing Systems. 7425\u20137434."},{"key":"e_1_3_2_1_60_1","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. 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. 1420\u20131430 . Adam Klivans, Pravesh K Kothari, and Raghu Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory. 1420\u20131430."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_3_2_1_64_1","volume-title":"Conference on Learning Theory. 1302\u20131382","author":"Li Jerry","year":"2017","unstructured":"Jerry Li and Ludwig Schmidt . 2017 . Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities . In Conference on Learning Theory. 1302\u20131382 . Jerry Li and Ludwig Schmidt. 2017. Robust and proper learning for mixtures of gaussians via systems of polynomial inequalities. In Conference on Learning Theory. 1302\u20131382."},{"key":"e_1_3_2_1_65_1","volume-title":"Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Li Jerry","year":"2020","unstructured":"Jerry Li and Guanghao Ye . 2020 . Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual. Jerry Li and Guanghao Ye. 2020. Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual."},{"key":"e_1_3_2_1_66_1","volume-title":"Principled approaches to robust machine learning and beyond. Ph. D. Dissertation","author":"Jerry Zheng Li.","unstructured":"Jerry Zheng Li. 2018. Principled approaches to robust machine learning and beyond. Ph. D. Dissertation . Massachusetts Institute of Technology . Jerry Zheng Li. 2018. Principled approaches to robust machine learning and beyond. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_67_1","volume-title":"Myers","author":"Li Jun Z.","year":"2008","unstructured":"Jun Z. Li , Devin M. Absher , Hua Tang , Audrey M. Southwick , Amanda M. Casto , Sohini Ramachandran , Howard M. Cann , Gregory S. Barsh , Marcus Feldman , Luigi L. Cavalli-Sforza , and Richard M . Myers . 2008 . Worldwide Human Relationships Inferred from Genome-Wide Patterns of Variation . 319 (2008), 1100\u20131104. Jun Z. Li, Devin M. Absher, Hua Tang, Audrey M. Southwick, Amanda M. Casto, Sohini Ramachandran, Howard M. Cann, Gregory S. Barsh, Marcus Feldman, Luigi L. Cavalli-Sforza, and Richard M. Myers. 2008. Worldwide Human Relationships Inferred from Genome-Wide Patterns of Variation. 319 (2008), 1100\u20131104."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Allen Liu and Ankur Moitra. 2020. Settling the Robust Learnability of Mixtures of Gaussians. arXiv preprint arXiv:2011.03622. Allen Liu and Ankur Moitra. 2020. Settling the Robust Learnability of Mixtures of Gaussians. arXiv preprint arXiv:2011.03622.","DOI":"10.1145\/3406325.3451084"},{"key":"e_1_3_2_1_69_1","volume-title":"Conference On Learning Theory. 1530\u20131546","author":"Meister Michela","year":"2018","unstructured":"Michela Meister and Gregory Valiant . 2018 . A data prism: Semi-verified learning in the small-alpha regime . In Conference On Learning Theory. 1530\u20131546 . Michela Meister and Gregory Valiant. 2018. A data prism: Semi-verified learning in the small-alpha regime. In Conference On Learning Theory. 1530\u20131546."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax001"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_3_2_1_72_1","volume-title":"Machine learning: a probabilistic perspective","author":"Murphy Kevin P","unstructured":"Kevin P Murphy . 2012. Machine learning: a probabilistic perspective . MIT press . Kevin P Murphy. 2012. Machine learning: a probabilistic perspective. MIT press."},{"key":"e_1_3_2_1_73_1","volume-title":"Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems","author":"Musco Cameron","year":"2015","unstructured":"Cameron Musco and Christopher Musco . 2015. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition . In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 , December 7-12, 2015, Montreal , Quebec, Canada . 1396\u20131404. Cameron Musco and Christopher Musco. 2015. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada. 1396\u20131404."},{"key":"e_1_3_2_1_74_1","volume-title":"Ancestry informative markers for fine-scale individual assignment to worldwide populations. 47, 12","author":"Paschou Peristera","year":"2010","unstructured":"Peristera Paschou , Jamey Lewis , Asif Javed , and Petros Drineas . 2010. Ancestry informative markers for fine-scale individual assignment to worldwide populations. 47, 12 ( 2010 ), 835\u2013847. Peristera Paschou, Jamey Lewis, Asif Javed, and Petros Drineas. 2010. Ancestry informative markers for fine-scale individual assignment to worldwide populations. 47, 12 (2010), 835\u2013847."},{"key":"e_1_3_2_1_75_1","first-page":"466","article-title":"Method, apparatus, and system for clustering and classification","volume":"8","author":"Patinkin Seth","year":"2011","unstructured":"Seth Patinkin . 2011 . Method, apparatus, and system for clustering and classification . US Patent 8 ,010, 466 Seth Patinkin. 2011. Method, apparatus, and system for clustering and classification. US Patent 8,010,466","journal-title":"US Patent"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1894.0003"},{"key":"e_1_3_2_1_77_1","volume-title":"Sivaraman Balakrishnan, and Pradeep Ravikumar.","author":"Prasad Adarsh","year":"2018","unstructured":"Adarsh Prasad , Arun Sai Suggala , Sivaraman Balakrishnan, and Pradeep Ravikumar. 2018 . Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485. Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. 2018. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485."},{"key":"e_1_3_2_1_78_1","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 161\u2013180","author":"Raghavendra Prasad","year":"2020","unstructured":"Prasad Raghavendra and Morris Yau . 2020 . List decodable learning via sum of squares . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 161\u2013180 . Prasad Raghavendra and Morris 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_79_1","volume-title":"On Learning Mixtures of Well-Separated Gaussians. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Regev Oded","year":"2017","unstructured":"Oded Regev and Aravindan Vijayaraghavan . 2017 . On Learning Mixtures of Well-Separated Gaussians. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 , Berkeley, CA, USA , October 15-17, 2017. 85\u201396. Oded Regev and Aravindan Vijayaraghavan. 2017. On Learning Mixtures of Well-Separated Gaussians. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 85\u201396."},{"key":"e_1_3_2_1_80_1","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 85\u201396","author":"Regev Oded","year":"2017","unstructured":"Oded Regev and Aravindan Vijayaraghavan . 2017 . On learning mixtures of well-separated gaussians . In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 85\u201396 . Oded Regev and Aravindan Vijayaraghavan. 2017. On learning mixtures of well-separated gaussians. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 85\u201396."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1078311"},{"key":"e_1_3_2_1_82_1","volume-title":"Breeds: Benchmarks for subpopulation shift. arXiv preprint arXiv:2008.04859.","author":"Santurkar Shibani","year":"2020","unstructured":"Shibani Santurkar , Dimitris Tsipras , and Aleksander Madry . 2020 . Breeds: Benchmarks for subpopulation shift. arXiv preprint arXiv:2008.04859. Shibani Santurkar, Dimitris Tsipras, and Aleksander Madry. 2020. Breeds: Benchmarks for subpopulation shift. arXiv preprint arXiv:2008.04859."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/AAI28115249"},{"key":"e_1_3_2_1_84_1","volume-title":"Certified Defenses for Data Poisoning Attacks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Steinhardt Jacob","year":"2017","unstructured":"Jacob Steinhardt , Pang Wei Koh , and Percy Liang . 2017 . Certified Defenses for Data Poisoning Attacks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 , December 4-9, 2017, Long Beach, CA, USA. 3517\u20133529. Jacob Steinhardt, Pang Wei Koh, and Percy Liang. 2017. Certified Defenses for Data Poisoning Attacks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA. 3517\u20133529."},{"key":"e_1_3_2_1_85_1","unstructured":"Jacob Steinhardt Gregory Valiant and Moses Charikar. 2016. Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction. In Advances in Neural Information Processing Systems. 4439\u20134447. Jacob Steinhardt Gregory Valiant and Moses Charikar. 2016. Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction. In Advances in Neural Information Processing Systems. 4439\u20134447."},{"key":"e_1_3_2_1_86_1","unstructured":"Brandon Tran Jerry Li and Aleksander Madry. 2018. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems. 8000\u20138010. Brandon Tran Jerry Li and Aleksander Madry. 2018. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems. 8000\u20138010."},{"key":"e_1_3_2_1_87_1","unstructured":"John W Tukey. 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics 448\u2013485. John W Tukey. 1960. A survey of sampling from contaminated distributions. Contributions to probability and statistics 448\u2013485."},{"key":"e_1_3_2_1_88_1","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, 523\u2013531. John W. Tukey. 1975. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians, Vancouver, 1975. 2, 523\u2013531."},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"},{"key":"e_1_3_2_1_90_1","volume-title":"Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems","author":"Manfred","year":"2006","unstructured":"Manfred K. Warmuth and Dima Kuzmin. 2006. Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension. In Advances in Neural Information Processing Systems 19 , Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada , December 4-7, 2006 . 1481\u20131488. Manfred K. Warmuth and Dima Kuzmin. 2006. Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006. 1481\u20131488."},{"key":"e_1_3_2_1_91_1","volume-title":"Modern algorithms of cluster analysis","author":"Wierzcho\u0144 S\u0142","unstructured":"S\u0142 awomir T Wierzcho\u0144 and Mieczys\u0142 aw A K\u0142 opotek. 2018. Modern algorithms of cluster analysis . Springer . S\u0142 awomir T Wierzcho\u0144 and Mieczys\u0142 aw A K\u0142 opotek. 2018. Modern algorithms of cluster analysis. Springer."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:53:28Z","timestamp":1654876408000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":91,"alternative-id":["10.1145\/3519935.3520014","10.1145\/3519935"],"URL":"http:\/\/dx.doi.org\/10.1145\/3519935.3520014","relation":{},"published":{"date-parts":[[2022,6,9]]}}}