Learning mixtures of spherical gaussians: moment methods and spectral decompositions

By Daniel J. Hsu, Sham M. Kakade. 2012

336 citations recorded by the source corpus.

This work provides a computationally efficient and statistically consistent moment-based estimator for mixtures of spherical Gaussians. Under the condition that component means are in general position, a simple spectral decomposition technique yields consistent parameter estimates from low-order observable moments, without additional minimum separation assumptions needed by previous computationally efficient estimation procedures. Thus computational and information-theoretic barriers to efficient estimation in mixture models are precluded when the mixture components have means in general position and spherical covariances. Some connections are made to estimation problems related to independent component analysis.

Subfields: Analytical Chemistry, Artificial Intelligence, 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 Analytical Chemistry

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Beyond CCA: Moment Matching for Multi-View Models (2016, positive): “…within the moment matching framework: ICA (e.g., Cardoso & Comon, 1996; Comon & Jutten, 2010), mixtures of Gaus-sians (e.g., Arora & Kannan, 2005; Hsu & Kakade, 2013), latent Dirichlet allocation and topic models (Arora et al., 2012; 2013; Anandkumar et al., 2012; Podosinnikova et al., 2015),…”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “…learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of k Gaussians with identical spherical covariances.”
Provable Bounds for Learning Some Deep Representations (2013, neutral): “1”
Tensor decompositions for learning latent variable models (2012, methodology): “Relative to previous works on moment-based estimators for latent variable models (e.g., Anandkumar et al., 2012c,a; Hsu and Kakade, 2013), Theorem 4.”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “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].”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “1To circumvent the information-theoretic bottleneck of parameter learning, a related line of work has studied parameter learning in a smoothed setting [48], [9], [3], [44].”
A tutorial on task-parameterized movement learning and retrieval (2015, methodology): “spectral approaches with circular covariances [84, 52, 42], or based on an iterative clustering algorithm [82].”
Rich Component Analysis (2015, background): “However, we can write P = ZR where Z ∈ R10×2 is an orthonormal matrix (Z>Z = I), and R ∈ R2×2 and then hope to find M†1 such that M † 1M1 = ZZ > (this is possible because we can let M†1 := Z(WR >)†).”
Mixture models, robustness, and sum of squares proofs (2017, methodology): “Tensor-decomposition methods: Another line of algorithms focus on settings where the means satisfy algebraic non-degeneracy conditions, which is the case for instance in smoothed analysis settings [2, 30, 37].”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, background): “( If the cluster means are in general position, other lines of work yields results for Gaussians [ KMV10, MV10, BS10, HK13, BCV14, GVX14, BCMV14, ABG + 14, GHK15] or for distributions satisfying independence assumptions [HKZ09, AGH + 13].”
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”
On Bayes Risk Lower Bounds (2014, methodology): “Smoothed analysis has been successfully applied to analyze linear programming (Blum and Dunagan, 2002; Dunagan et al., 2011; Hsu and Kakade, 2013; Spielman and Teng, 2003), integer programming (Röglin and Vöcking, 2007), binary search trees (Manthey and Reischuk, 2007), and other combinatorial probl”