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 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 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.

Authors

• Ilias Diakonikolas
• Gautam Kamath 0001
• Daniel M. Kane
• Jerry Li 0001
• Ankur Moitra
• Alistair Stewart

Keywords

No keywords are indexed for this paper.