Local Minima in Mixture Problems and their Algorithmic Implications
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.