Outlier-robust moment-estimation via sum-of-squares

By Pravesh Kothari, David Steurer. 2017

72 citations recorded by the source corpus.

We develop efficient algorithms for estimating low-degree moments of unknown distributions in the presence of adversarial outliers. The guarantees of our algorithms improve in many cases significantly over the best previous ones, obtained in recent works of Diakonikolas et al, Lai et al, and Charikar et al. We also show that the guarantees of our algorithms match information-theoretic lower-bounds for the class of distributions we consider. These improved guarantees allow us to give improved algorithms for independent component analysis and learning mixtures of Gaussians in the presence of outliers. Our algorithms are based on a standard sum-of-squares relaxation of the following conceptually-simple optimization problem: Among all distributions whose moments are bounded in the same way as for the unknown distribution, find the one that is closest in statistical distance to the empirical distribution of the adversarially-corrupted sample.

Subfields: Artificial Intelligence, Control and Systems Engineering, Signal Processing

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

1. Ilias Diakonikolas
2. Alistair Stewart
3. Daniel M. Kane
4. Jerry Zheng Li
5. Jacob Steinhardt
6. Gautam Kamath
7. Gregory Valiant
8. Michela Meister

In Control and Systems Engineering

1. Alistair Stewart
2. Gregory Valiant
3. Ilias Diakonikolas
4. Jerry Zheng Li
5. Jacob Steinhardt

In Signal Processing

1. Gregory Valiant
2. Alistair Stewart
3. Ilias Diakonikolas
4. Daniel M. Kane
5. Jerry Zheng Li
6. Jacob Steinhardt
7. Pengkun Yang
8. Yihong Wu

Citations in the corpus

• Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “…tradeoffs [DKS17c, DKK + 18], establishing connections to PAC learning [DKS17a], tolerating more noise by outputting a list of hypotheses [CSV17, MV17, DKS17b], robust estimation of discrete structures [Ste17, QV17, SCV18], and robust estimation via sum-of-squares [KS17b, HL17, KS17a].”
• A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “There has been a flurry of very recent works both tightening these results and extending them to more general classes of distribution and other optimization or learning problems (Steinhardt et al., 2018; Kothari and Steinhardt, 2017; Kothari and Steurer, 2017; Diakonikolas et al., 2017a).”