Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
This work addresses the fundamental challenge of robust statistical estimation in high dimensions, providing efficient algorithms that extend classical one-dimensional error guarantees to modern settings, which is significant for machine learning and data science applications dealing with noisy data.
The paper tackles the problem of robustly learning the parameters of a high-dimensional Gaussian distribution when a fraction of samples are corrupted by an adversary, achieving optimal estimation error of O(ε) in total variation distance with polynomial sample complexity. For unknown mean, the algorithm runs in polynomial time with near-optimal robustness, and for unknown mean and covariance, it runs in quasipolynomial time.
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/ε$. 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.