{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:49Z","timestamp":1750220449789,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1652862, 0953960, 1453261"],"award-info":[{"award-number":["1652862, 0953960, 1453261"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:p>In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model, but even when their assumptions are violated. Unfortunately, in high dimensions, being provably robust and being efficiently computable are often at odds with each other.<\/jats:p>\n          <jats:p>We give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian that is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute or could tolerate only an inverse-polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, but also it turns out to be highly practical in a variety of settings.<\/jats:p>","DOI":"10.1145\/3453935","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T14:14:22Z","timestamp":1619446462000},"page":"107-115","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Robustness meets algorithms"],"prefix":"10.1145","volume":"64","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"University of Wisconsin, Madison, WI"}]},{"given":"Gautam","family":"Kamath","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California, San Diego, CA"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research AI, Redmond, WA"}]},{"given":"Ankur","family":"Moitra","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}]},{"given":"Alistair","family":"Stewart","sequence":"additional","affiliation":[{"name":"Web3 Foundation, Zug, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591839"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 30th Annual Conference on Learning Theory, COLT '17","author":"Balakrishnan S.","year":"2017","unstructured":"Balakrishnan , S. , Du , S.S. , Li , J. , Singh , A. Computationally efficient robust sparse estimation in high dimensions . In Proceedings of the 30th Annual Conference on Learning Theory, COLT '17 ( 2017 ), 169--212. Balakrishnan, S., Du, S.S., Li, J., Singh, A. Computationally efficient robust sparse estimation in high dimensions. In Proceedings of the 30th Annual Conference on Learning Theory, COLT '17 (2017), 169--212."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML '17","author":"Diakonikolas I.","year":"2017","unstructured":"Diakonikolas , I. , Kamath , G. , Kane , D.M. , Li , J. , Moitra , A. , Stewart , A. Being robust (in high dimensions) can be practical . In Proceedings of the 34th International Conference on Machine Learning, ICML '17 ( 2017 ), JMLR, Inc., 999--1008. Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Moitra, A., Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML '17 (2017), JMLR, Inc., 999--1008."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.171"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML '19","author":"Diakonikolas I.","year":"2019","unstructured":"Diakonikolas , I. , Kamath , G. , Kane , D.M. , Li , J. , Steinhardt , J. , Stewart , A. Sever : A robust meta-algorithm for stochastic optimization . In Proceedings of the 36th International Conference on Machine Learning, ICML '19 ( 2019 ), JMLR, Inc., 1596--1606. Diakonikolas, I., Kamath, G., Kane, D.M., Li, J., Steinhardt, J., Stewart, A. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML '19 (2019), JMLR, Inc., 1596--1606."},{"key":"e_1_2_1_8_1","volume-title":"Recent advances in algorithmic high-dimensional robust statistics. CoRR, abs\/1911.05911","author":"Diakonikolas I.","year":"2019","unstructured":"Diakonikolas , I. , Kane , D.M. Recent advances in algorithmic high-dimensional robust statistics. CoRR, abs\/1911.05911 , 2019 . Diakonikolas, I., Kane, D.M. Recent advances in algorithmic high-dimensional robust statistics. CoRR, abs\/1911.05911, 2019."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"e_1_2_1_11_1","first-page":"24","article-title":"Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography","volume":"6","author":"Fischler M.A.","year":"1981","unstructured":"Fischler , M.A. , Bolles , R.C . Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography . Commun. ACM 6 , 24 ( 1981 ), 381--395. Fischler, M.A., Bolles, R.C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 6, 24 (1981), 381--395.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1922.0009"},{"key":"e_1_2_1_13_1","volume-title":"Robust Statistics: The Approach Based on Influence Functions","author":"Hampel F.R.","year":"2011","unstructured":"Hampel , F.R. , Ronchetti , E.M. , Rousseeuw , P.J. , Stahel , W.A. Robust Statistics: The Approach Based on Influence Functions . Wiley, Hoboken , New Jersey , 2011 . Hampel, F.R., Ronchetti, E.M., Rousseeuw, P.J., Stahel, W.A. Robust Statistics: The Approach Based on Influence Functions. Wiley, Hoboken, New Jersey, 2011."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470434697"},{"key":"e_1_2_1_16_1","first-page":"6","article-title":"The densest hemisphere problem","volume":"1","author":"Johnson D.S.","year":"1978","unstructured":"Johnson , D.S. , Preparata , F.P . The densest hemisphere problem . Theor. Comp. Sci. 1 , 6 ( 1978 ), 93--107. Johnson, D.S., Preparata, F.P. The densest hemisphere problem. Theor. Comp. Sci. 1, 6 (1978), 93--107.","journal-title":"Theor. Comp. Sci."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1755877"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.76"},{"key":"e_1_2_1_21_1","first-page":"456","article-title":"Genes mirror geography with","volume":"7218","author":"Novembre J.","year":"2008","unstructured":"Novembre , J. , Johnson , T. , Bryc , K. , Kutalik , Z. , Boyko , A.R. , Auton , A. , Indap , A. , King , K.S. , Bergmann , S. , Nelson , M.R. , Stephens , M. , Bustamante , C.D . Genes mirror geography with in Europe. Nature 7218 , 456 ( 2008 ), 98--101. Novembre, J., Johnson, T., Bryc, K., Kutalik, Z., Boyko, A.R., Auton, A., Indap, A., King, K.S., Bergmann, S., Nelson, M.R., Stephens, M., Bustamante, C.D. Genes mirror geography within Europe. Nature 7218, 456 (2008), 98--101.","journal-title":"Europe. Nature"},{"key":"e_1_2_1_22_1","volume-title":"Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485","author":"Prasad A.","year":"2018","unstructured":"Prasad , A. , Suggala , A.S. , Balakrishnan , S. , Ravikumar , P. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485 ( 2018 ). Prasad, A., Suggala, A.S., Balakrishnan, S., Ravikumar, P. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485 (2018)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-5438-0_20"},{"key":"e_1_2_1_24_1","volume-title":"Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling","author":"Tukey J.W.","year":"1960","unstructured":"Tukey , J.W. A survey of sampling from contaminated distributions . In Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling , Stanford University Press , Stanford, California , 1960 , 448--485. Tukey, J.W. A survey of sampling from contaminated distributions. In Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling, Stanford University Press, Stanford, California, 1960, 448--485."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Tukey J.W.","year":"1975","unstructured":"Tukey , J.W. Mathematics and the picturing of data . In Proceedings of the International Congress of Mathematicians ( 1975 ), American Mathematical Society, 523--531. Tukey, J.W. Mathematics and the picturing of data. In Proceedings of the International Congress of Mathematicians (1975), American Mathematical Society, 523--531."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453935","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453935","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453935","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:51Z","timestamp":1750193271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453935"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.1145\/3453935"],"URL":"https:\/\/doi.org\/10.1145\/3453935","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"2021-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}