%0 Journal Article %1 diakonikolas2017robustly %A Diakonikolas, Ilias %A Kamath, Gautam %A Kane, Daniel M. %A Li, Jerry %A Moitra, Ankur %A Stewart, Alistair %D 2017 %K learning robustness stats %T Robustly Learning a Gaussian: Getting Optimal Error, Efficiently %U http://arxiv.org/abs/1704.03866 %X We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an $\varepsilon$-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error $O(\varepsilon)$ 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 $2$ and the running time is polynomial in $d$ and $1/\epsilon$. When both the mean and covariance are unknown, the running time is polynomial in $d$ and quasipolynomial in $1/\varepsilon$. 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.

@article{diakonikolas2017robustly, abstract = {We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an $\varepsilon$-fraction of our samples were chosen by an adversary. We give robust estimators that achieve estimation error $O(\varepsilon)$ 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 $\sqrt{2}$ and the running time is polynomial in $d$ and $1/\epsilon$. When both the mean and covariance are unknown, the running time is polynomial in $d$ and quasipolynomial in $1/\varepsilon$. 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.}, added-at = {2020-02-26T13:41:35.000+0100}, author = {Diakonikolas, Ilias and Kamath, Gautam and Kane, Daniel M. and Li, Jerry and Moitra, Ankur and Stewart, Alistair}, biburl = {https://www.bibsonomy.org/bibtex/23b91a638fa7a0b90b14ed461bda28c57/kirk86}, description = {[1704.03866] Robustly Learning a Gaussian: Getting Optimal Error, Efficiently}, interhash = {db771bfbe907a2a34642c62614320e6c}, intrahash = {3b91a638fa7a0b90b14ed461bda28c57}, keywords = {learning robustness stats}, note = {cite arxiv:1704.03866Comment: To appear in SODA 2018}, timestamp = {2020-02-26T13:41:35.000+0100}, title = {Robustly Learning a Gaussian: Getting Optimal Error, Efficiently}, url = {http://arxiv.org/abs/1704.03866}, year = 2017 }