An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization

DOI10.1007/S10107-019-01381-4zbMATH Open1441.62168arXiv1706.03267OpenAlexW2627006445WikidataQ115385318 ScholiaQ115385318MaRDI QIDQ2188245FDOQ2188245

Reshad Hosseini, Suvrit Sra

Publication date: 10 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We consider maximum likelihood estimation for Gaussian Mixture Models (Gmms). This task is almost invariably solved (in theory and practice) via the Expectation Maximization (EM) algorithm. EM owes its success to various factors, of which is its ability to fulfill positive definiteness constraints in closed form is of key importance. We propose an alternative to EM by appealing to the rich Riemannian geometry of positive definite matrices, using which we cast Gmm parameter estimation as a Riemannian optimization problem. Surprisingly, such an out-of-the-box Riemannian formulation completely fails and proves much inferior to EM. This motivates us to take a closer look at the problem geometry, and derive a better formulation that is much more amenable to Riemannian optimization. We then develop (Riemannian) batch and stochastic gradient algorithms that outperform EM, often substantially. We provide a non-asymptotic convergence analysis for our stochastic method, which is also the first (to our knowledge) such global analysis for Riemannian stochastic gradient. Numerous empirical results are included to demonstrate the effectiveness of our methods.

Full work available at URL: https://arxiv.org/abs/1706.03267

Recommendations

• Riemannian online algorithms for estimating mixture model parameters
• Recent Advances in Stochastic Riemannian Optimization
• Statistical convergence of the EM algorithm on Gaussian mixture models
• Maximum likelihood estimation of Gaussian mixture models without matrix operations
• Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM

zbMATH Keywords

stochastic optimizationGaussian mixture modelspositive definite matricesretractionRiemannian optimizationnon-asymptotic rate of convergence

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Statistics on manifolds (62R30) Stochastic programming (90C15) Applications of differential geometry to data and computer science (53Z50)

Cites Work

• Manopt, a Matlab toolbox for optimization on manifolds
• The elements of statistical learning. Data mining, inference, and prediction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite mixture models
• Title not available (Why is that?)
• Machine learning. A probabilistic perspective
• Mixture Densities, Maximum Likelihood and the EM Algorithm
• Title not available (Why is that?)
• Geodesic Convexity and Covariance Estimation
• Statistical guarantees for the EM algorithm: from population to sample-based analysis
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Riemannian metrics on positive definite matrices related to means. II
• Low-rank matrix completion by Riemannian optimization
• Optimization methods on Riemannian manifolds and their application to shape space
• Title not available (Why is that?)
• Hessian Riemannian Gradient Flows in Convex Programming
• Conic Geometric Optimization on the Manifold of Positive Definite Matrices
• A survey and comparison of contemporary algorithms for computing the matrix geometric mean
• Stochastic Gradient Descent on Riemannian Manifolds
• Riemannian metrics on positive definite matrices related to means
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
• Learning Mixtures of Gaussians in High Dimensions
• Theoretical Statistics
• Global rates of convergence for nonconvex optimization on manifolds

Cited In (11)

• Learning with symmetric positive definite matrices via generalized Bures-Wasserstein geometry
• Accelerated Optimization in the PDE Framework: Formulations for the Manifold of Diffeomorphisms
• Fenchel conjugate via Busemann function on Hadamard manifolds
• TLS-EM algorithm of mixture density models for exponential families
• A trust region method for solving multicriteria optimization problems on Riemannian manifolds
• A Riemannian Newton trust-region method for fitting Gaussian mixture models
• Large-sample properties of unsupervised estimation of the linear discriminant using projection pursuit
• Recent Advances in Stochastic Riemannian Optimization
• Practical gradient and conjugate gradient methods on flag manifolds
• Nonconvex weak sharp minima on Riemannian manifolds
• GAT–GMM: Generative Adversarial Training for Gaussian Mixture Models

Uses Software

• Manopt
• PMTK
• k-means++
• PRMLT

This page was built for publication: An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2188245)