Online Program Home
  My Program

All Times EDT

Abstract Details

Activity Number: 347 - Recent Advances in Clustering and Mixture Models Analysis
Type: Topic-Contributed
Date/Time: Thursday, August 12, 2021 : 10:00 AM to 11:50 AM
Sponsor: Section for Statistical Programmers and Analysts
Abstract #317067
Title: Structures of Local Minima in K-Means and the Likelihood of Mixture Models
Author(s): Yudong Chen* and Xumei Xi
Companies: School of ORIE, Cornell University and School of ORIE, Cornell University
Keywords:
Abstract:

Maximum likelihood estimation of mixture models poses non-convex problems. Standard algorithms such as EM generally converge to a spurious local minimizer, both in theory and practice. In this talk, we present two results on the structures of these local minima.

For a mixture of two symmetric components, we show that all local minima are globally optimal, and EM converges to a global optimum from random initialization. This result applies to a broad class of log-concave mixture problems including mixtures of Gaussians and linear regressions. Our analysis highlights the non-convergence of EM in Euclidean distance, necessitating the consideration of other metrics.

For a mixture of more than two components, spurious local minima provably exist. One such local minimizer puts multiple centers at one true component, and another center in the middle of multiple true components. We prove that this is essentially the only type of spurious local minima under a separation condition. Consequently, EM is guaranteed to converge to a solution that at least partially identify the true mixture model. We will discuss further algorithmic implications of these results for over-parameterization.


Authors who are presenting talks have a * after their name.

Back to the full JSM 2021 program