List-decodable robust mean estimation and learning mixtures of spherical gaussians

By Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart. 2017

160 citations recorded by the source corpus.

We study the problem of list-decodable (robust) Gaussian mean estimation and the related problem of learning mixtures of separated spherical Gaussians. In the former problem, we are given a set T of points in n with the promise that an α-fraction of points in T, where 0< α < 1/2, are drawn from an unknown mean identity covariance Gaussian G, and no assumptions are made about the remaining points. The goal is to output a small list of candidate vectors with the guarantee that at least one of the candidates is close to the mean of G. In the latter problem, we are given samples from a k-mixture of spherical Gaussians on n and the goal is to estimate the unknown model parameters up to small accuracy. We develop a set of techniques that yield new efficient algorithms with significantly improved guarantees for these problems. Specifically, our main contributions are as follows: List-Decodable Mean Estimation. Fix any d ∈ + and 0< α <1/2. We design an algorithm with sample complexity Od ((nd/α)) and runtime Od ((n/α)d) that outputs a list of O(1/α) many candidate vectors such that with high probability one of the candidates is within ℓ2-distance Od(α−1/(2d)) from the mean of G. The only previous algorithm for this problem achieved error Õ(α−1/2) under second moment conditions. For d = O(1/), where >0 is a constant, our algorithm runs in polynomial time and achieves error O(α). For d = Θ(log(1/α)), our algorithm runs in time (n/α)O(log(1/α)) and achieves error O(log3/2(1/α)), almost matching the information-theoretically optimal bound of Θ(log1/2(1/α)) that we establish. We also give a Statistical Query (SQ) lower bound suggesting that the complexity of our algorithm is qualitatively close to best possible. Learning Mixtures of Spherical Gaussians. We give a learning algorithm for mixtures of spherical Gaussians, with unknown spherical covariances, that succeeds under significantly weaker separation assumptions compared to prior work. For the prototypical case of a uniform k-mixture of identity covariance Gaussians we obtain the following: For any >0, if the pairwise separation between the means is at least Ω(k+√log(1/δ)), our algorithm learns the unknown parameters within accuracy δ with sample complexity and running time (n, 1/δ, (k/)1/). Moreover, our algorithm is robust to a small dimension-independent fraction of corrupted data. The previously best known polynomial time algorithm required separation at least k1/4 (k/δ). Finally, our algorithm works under separation of Õ(log3/2(k)+√log(1/δ)) with sample complexity and running time (n, 1/δ, klogk). This bound is close to the information-theoretically minimum separation of Ω(√logk). Our main technical contribution is a new technique, using degree-d multivariate polynomials, to remove outliers from high-dimensional datasets where the majority of the points are corrupted.

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

Sever: A Robust Meta-Algorithm for Stochastic Optimization (2018, background): “Since the dissemination of [DKK + 16, LRV16], there has been a ﬂurry of research activity on algorithmic robust estimation in a variety of high-dimensional settings, including learning graphical models [DKS16], understanding computation-robustness tradeoﬀs [DKS17c, DKK + 18], establishing connection”
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.”
A Data Prism: Semi-verified learning in the small-alpha regime (2018, background): “The works (Steinhardt et al., 2016) and (Charikar et al., 2017) and the very recent work (Diakonikolas et al., 2017b) consider the setting where a minority of the data is “good” (i.e. α 1/2), with (Charikar et al., 2017) formally proposing the “semi-verified” learning model where one may obtain a…”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, methodology): “There are many ways the objective can be defined, including clustering [20, 21, 5, 64, 3, 17, 16, 52, 7, 59, 41, 27, 51], parameter estimation [46, 54, 10, 42, 4, 11, 40, 38, 66, 23, 6], proper learning [35, 36, 22, 63, 26, 53], and improper learning [15].”
Learning under p-Tampering Attacks (2018, background): “These works led to an active line of work (e.g., see [CSV17, DKS17, DKS18a, DKK + 18, PSBR18, DKS18b] and references therein) exploring the possibility of robust statistics over poisoned data with algorithmic guarantees.”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, background): “By now, a sequence of results (Dasgupta et al., 2007, 2006; Arora and Kannan, 2005; Vempala and Wang, 2004; Achlioptas and McSherry, 2005; Kannan et al., 2005; Vempala, 2007; Hsu and Kakade, 2013; Ge et al., 2015b; Kalai et al., 2012; Belkin and Sinha, 2010; Kalai et al., 2010; Kothari and Steinhard”