On Spectral Learning of Mixtures of Distributions

By Dimitris Achlioptas, Frank McSherry. Annual Conference Computational Learning Theory, 2005

294 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0efe7ae6fe5a4ce30b69fd2fdcde8bcb3715929b

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

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”
Weighted low rank approximations with provable guarantees (2016, background): “Low rank approximation is arguably one of the most wellstudied problems in randomized numerical linear algebra, with diverse applications to clustering [19, 23, 38, 18], data mining [5], distance matrix completion [13], information retrieval [45], learning mixtures of distributions [2, 32], recommen”
List-decodable robust mean estimation and learning mixtures of spherical gaussians (2017, unknown): “, [2, 4, 10, 34, 49], provides computationally efficient algorithms for recovering the parameters of a GMM under various separation assumptions between the mixture components.”
Mixture models, robustness, and sum of squares proofs (2017, background): “(1) Normalization: Ẽ[1] = 1 (2) Positivity: Ẽ[p(x)2] ≥ 0 for every p of degree at most d/2.”
A discriminative framework for clustering via similarity functions (2008, methodology): “Alternatively, methods developed both in the algorithms and in the machine learning literature for learning mixtures of distributions [1, 5, 23, 36, 17, 15] explicitly have a notion of ground-truth clusters which they aim to recover.”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, methodology): “In particular we give differentially private analogues of the algorithm of Achlioptas and McSherry [3], which requires that the means are separated by a factor proportional to √ k, but independent of the dimension d.”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “…2001], recommendation systems [Drineas et al. 2002], information retrieval [Papadimitriou et al. 2000], web search [Achlioptas et al. 2001; Kleinberg 1999], clustering [Drineas et al. 2004; McSherry 2001], and learning mixtures of distributions [Kannan et al. 2008; Achlioptas and McSherry 2005].”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, background): “For example, while k -means clustering is NP-hard in the worst-case [MNV09], there is an inﬂuential line of work providing spectral algorithms for clustering mixture models satisfying appropriate assumptions [AM05, KK10, AS12].”
A Method of Moments for Mixture Models and Hidden Markov Models (2012, background): “This and subsequent work (Arora and Kannan, 2001; Dasgupta and Schulman, 2007; Vempala and Wang, 2002; Kannan et al., 2005; Achlioptas and McSherry, 2005; Chaudhuri and Rao, 2008; Brubaker and Vempala, 2008; Chaudhuri et al., 2009) have focused on eﬃcient algorithms that provably recover the…”
Tensor decompositions for learning latent variable models (2012, background): “This was employed for parameter estimation of discrete Markov models [Cha96] using pair-wise and triple-wise probability tables, and later for other latent variable models such as hidden Markov models (HMMs), latent trees, Gaussian mixture models, and topic models such as latent Dirichlet allocation”
Finding and Leveraging Structure in Learning Problems (2012, background): “Another related line of work is on the problem of spectrally separating mixtures of Gaussians [Achlioptas and Mcsherry, 2005, Brubaker and Vempala, 2008, Kannan et al., 2005].”
Settling the Polynomial Learnability of Mixtures of Gaussians (2010, methodology): “Our algorithm employs hierarchical clustering and rescaling, together with delicate methods for backtracking and recovering from failures that can occur in our univariate algorithm.”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “A long line of work initiated by Dasgupta [21], [4], [72], [2], [54], [11] provides computationally efficient algorithms for recovering the parameters of a GMM under separability assumptions.”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, background): “…condition; a subsequent line of results relaxed (Arora and Kannan, 2001; Dasgupta and Schulman, 2007; Vempala and Wang, 2002; Kannan et al., 2005; Achlioptas and McSherry, 2005; Chaudhuri and Rao, 2008; Brubaker and Vempala, 2008; Chaudhuri et al., 2009) or removed these conditions (Kalai et…”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, methodology): “Prominent applications of low-rank matrix approximation by SVD include recommendation systems [25], information retrieval via Latent Semantic Indexing [13, 48], Kleinberg’s celebrated HITS algorithm for web search [43, 2], clustering [22, 47], and learning mixtures of distributions [42, 4] just to n”