Robustness meets algorithms
<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 ea...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135599 |
| _version_ | 1811087168075988992 |
|---|---|
| author | Diakonikolas, Ilias Kamath, Gautam Kane, Daniel M Li, Jerry Moitra, Ankur Stewart, Alistair |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Diakonikolas, Ilias Kamath, Gautam Kane, Daniel M Li, Jerry Moitra, Ankur Stewart, Alistair |
| author_sort | Diakonikolas, Ilias |
| collection | MIT |
| description | <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>
<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> |
| first_indexed | 2024-09-23T13:41:09Z |
| format | Article |
| id | mit-1721.1/135599 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:41:09Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1355992023-02-23T16:52:34Z Robustness meets algorithms Diakonikolas, Ilias Kamath, Gautam Kane, Daniel M Li, Jerry Moitra, Ankur Stewart, Alistair Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory <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> <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> 2021-10-27T20:24:11Z 2021-10-27T20:24:11Z 2021 2021-09-27T14:54:42Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135599 en 10.1145/3453935 Communications of the ACM Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Association for Computing Machinery (ACM) ACM |
| spellingShingle | Diakonikolas, Ilias Kamath, Gautam Kane, Daniel M Li, Jerry Moitra, Ankur Stewart, Alistair Robustness meets algorithms |
| title | Robustness meets algorithms |
| title_full | Robustness meets algorithms |
| title_fullStr | Robustness meets algorithms |
| title_full_unstemmed | Robustness meets algorithms |
| title_short | Robustness meets algorithms |
| title_sort | robustness meets algorithms |
| url | https://hdl.handle.net/1721.1/135599 |
| work_keys_str_mv | AT diakonikolasilias robustnessmeetsalgorithms AT kamathgautam robustnessmeetsalgorithms AT kanedanielm robustnessmeetsalgorithms AT lijerry robustnessmeetsalgorithms AT moitraankur robustnessmeetsalgorithms AT stewartalistair robustnessmeetsalgorithms |