Back to search

Cornell University

Local Minima in Mixture Problems and their Algorithmic Implications

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qian, Wei
Chair dc:contributor.chair
  • Chen, Yudong
Committee members dc:contributor.committeemember
  • Weinberger, Kilian Quirin
  • Renegar, James

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
13278010
Dc Identifier Other
ProQuest Submission ID: 12062
ProQuest Publication ID: 28002375

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Qian, Wei. Local Minima in Mixture Problems and their Algorithmic Implications. Doctor of Philosophy thesis, Cornell University, 2020. https://hdl.handle.net/1813/102985