Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell University Graduate School
  3. Cornell Theses and Dissertations
  4. Local Minima in Mixture Problems and their Algorithmic Implications

Local Minima in Mixture Problems and their Algorithmic Implications

File(s)
Qian_cornellgrad_0058F_12062.pdf (2.05 MB)
Permanent Link(s)
https://doi.org/10.7298/jjj2-wa43
https://hdl.handle.net/1813/102985
Collections
Cornell Theses and Dissertations
Author
Qian, Wei
Abstract

We study the location estimation problem for a balanced mixture of k distributions. The geometry of this non-convex optimization problem differs according to the number of components. In the case of a balanced mixture of two Gaussians, the negative log-likelihood function has only two local minima, which both correspond to a true location parameter. This benign landscape allows for the global convergence of generic algorithms for solving the maximum likelihood estimator (MLE), such as gradient descent (GD) and the expectation-maximization (EM) algorithm. In particular, the iterates exhibit the following dynamics: (1) the l2 distance to a true parameter decreases at a linear rate; (2) the angle with a true parameter decreases at a linear rate. Generalizing the angle decreasing property, we further show that the EM-type algorithm efficiently learns a true location parameter from a random initialization in the case of a balanced mixture of two log-concave and rotation invariant distributions. However, when the number of components is at least three, the landscape of the negative log-likelihood function changes: there exist local minima other than the true parameter. As a result, popular algorithms for the mixture model such as the EM algorithm and Lloyd's algorithm could converge to a spurious local minimum with high probability. Nonetheless, we explicitly characterize the structure of all the local minima under a separation condition of the true clusters. Specifically, we prove that every local minimum of the k-means objective function, which is closely related to the negative log-likelihood function, has the following configuration: either multiple fitted centers are close to a true center, or a fitted center is in the middle of multiple true centers. This characterization pertains to a balanced mixture of k Gaussians or bounded distributions. On the one hand, this structural result corroborates existing empirical observations and provides justifications for several improved algorithms for clustering. On the other hand, it sheds light on methods to devise new algorithmic procedures to further improve a local solution.

Description
149 pages
Date Issued
2020-08
Keywords
Expectation Maximization
•
Gaussian Mixture Model
•
K-means
•
Non Convex Optimization
Committee Chair
Chen, Yudong
Committee Member
Weinberger, Kilian Quirin
Renegar, James
Degree Discipline
Operations Research and Information Engineering
Degree Name
Ph. D., Operations Research and Information Engineering
Degree Level
Doctor of Philosophy
Type
dissertation or thesis
Link(s) to Catalog Record
https://catalog.library.cornell.edu/catalog/13278010

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance