Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise | where an "-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error O(ϵ) in the total variation distance, which is optimal u...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Society for Industrial and Applied Mathematics
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116214 https://orcid.org/0000-0003-0048-2559 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0001-7047-0495 |
| _version_ | 1826193440087474176 |
|---|---|
| author | Stewart, Alistair Diakonikolas, Ilias Kamath, Gautam Chetan Kane, Daniel M Li, Jerry Zheng Moitra, Ankur |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Stewart, Alistair Diakonikolas, Ilias Kamath, Gautam Chetan Kane, Daniel M Li, Jerry Zheng Moitra, Ankur |
| author_sort | Stewart, Alistair |
| collection | MIT |
| description | We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise | where an "-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error O(ϵ) in the total variation distance, which is optimal up to a universal constant that is independent of the dimension. In the case where just the mean is unknown, our robustness guarantee is optimal up to a factor of p 2 and the running time is polynomial in d and 1/ϵ. When both the mean and covariance are unknown, the running time is polynomial in d and quasipolynomial in 1/ϵ. Moreover all of our algorithms require only a polynomial number of samples. Our work shows that the same sorts of error guarantees that were established over fifty years ago in the one-dimensional setting can also be achieved by efficient algorithms in high-dimensional settings. |
| first_indexed | 2024-09-23T09:39:16Z |
| format | Article |
| id | mit-1721.1/116214 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:39:16Z |
| publishDate | 2018 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1162142022-09-30T15:59:06Z Robustly Learning a Gaussian: Getting Optimal Error, Efficiently Stewart, Alistair Diakonikolas, Ilias Kamath, Gautam Chetan Kane, Daniel M Li, Jerry Zheng Moitra, Ankur Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Physics Diakonikolas, Ilias Kamath, Gautam Chetan Kane, Daniel M Li, Jerry Zheng Moitra, Ankur We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise | where an "-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error O(ϵ) in the total variation distance, which is optimal up to a universal constant that is independent of the dimension. In the case where just the mean is unknown, our robustness guarantee is optimal up to a factor of p 2 and the running time is polynomial in d and 1/ϵ. When both the mean and covariance are unknown, the running time is polynomial in d and quasipolynomial in 1/ϵ. Moreover all of our algorithms require only a polynomial number of samples. Our work shows that the same sorts of error guarantees that were established over fifty years ago in the one-dimensional setting can also be achieved by efficient algorithms in high-dimensional settings. 2018-06-11T17:27:24Z 2018-06-11T17:27:24Z 2018-01 2018-05-29T13:19:50Z Article http://purl.org/eprint/type/JournalArticle 0368-4245 http://hdl.handle.net/1721.1/116214 Diakonikolas, Ilias, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. “Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.” Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (January 2018): 2683–2702. https://orcid.org/0000-0003-0048-2559 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0001-7047-0495 http://dx.doi.org/10.1137/1.9781611975031.171 Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Stewart, Alistair Diakonikolas, Ilias Kamath, Gautam Chetan Kane, Daniel M Li, Jerry Zheng Moitra, Ankur Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title_full | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title_fullStr | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title_full_unstemmed | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title_short | Robustly Learning a Gaussian: Getting Optimal Error, Efficiently |
| title_sort | robustly learning a gaussian getting optimal error efficiently |
| url | http://hdl.handle.net/1721.1/116214 https://orcid.org/0000-0003-0048-2559 https://orcid.org/0000-0002-9937-0049 https://orcid.org/0000-0001-7047-0495 |
| work_keys_str_mv | AT stewartalistair robustlylearningagaussiangettingoptimalerrorefficiently AT diakonikolasilias robustlylearningagaussiangettingoptimalerrorefficiently AT kamathgautamchetan robustlylearningagaussiangettingoptimalerrorefficiently AT kanedanielm robustlylearningagaussiangettingoptimalerrorefficiently AT lijerryzheng robustlylearningagaussiangettingoptimalerrorefficiently AT moitraankur robustlylearningagaussiangettingoptimalerrorefficiently |