Robustly Learning a Gaussian: Getting Optimal Error, Efficiently

By Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Zheng Li, Ankur Moitra, Alistair Stewart. 2017

142 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Byzantine Stochastic Gradient Descent (2018, background): “In both lower bounds, we reduce the problem to the following well-known hardness result: Lemma 5.3 (folklore, c.f. Lemmata 16 and 17 in [13]) .”
Being Robust (in High Dimensions) Can Be Practical (2017, background): “, 1986), and under certain models it is in fact optimal in terms of its resilience to noise (Dvoretzky et al., 1956; Massart, 1990; Chen, 1998; Daskalakis & Kamath, 2014; Diakonikolas et al., 2017).”
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure (2018, background): “The works of (Charikar, Steinhardt, and Valiant 2017; Diakonikolas, Kane, and Stewart 2018) performed list-docodeable learning, and (Diakonikolas et al. 2018; Prasad et al. 2018) studied supervised learning.”
SGD: Decentralized Byzantine Resilience (2019, background): “Over the past two years, a growing body of work [10, 5, 14, 42, 7, 18, 40, 41] (and about 30 other papers) encompassed resilience to Poisoning inside a wider project, Byzantine Resilient Machine Learning .”
AGGREGATHOR: Byzantine Machine Learning via Robust Gradient Aggregation (2019, background): “Workers can be subject to software bugs and to address Byzantine-resilience without replicating the workers (Blanchard et al., 2017; Diakonikolas et al., 2017).”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, methodology): “This holds for a reason: [31] gives a poly(n) · 2 log(1/ ) time algorithm with O( ) error in Huber’s model.”