# Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures

arXiv: https://arxiv.org/abs/2205.11078 · HTML: https://mlsanity.com/paper/2205.11078/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 23 May 2022.

## Builds on (most cited first, 17 of 17)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [An Exponential Learning Rate Schedule for Deep Learning](https://mlsanity.com/paper/1910.07454/) (2019)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences](https://mlsanity.com/paper/1609.00978/) (2016)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression](https://mlsanity.com/paper/1810.05752/) (2018)
- [Sharp Analysis of Expectation-Maximization for Weakly Identifiable Models](https://mlsanity.com/paper/1902.00194/) (2019)
- [Regularized EM Algorithms: A Unified Framework and Statistical Guarantees](https://mlsanity.com/paper/1511.08551/) (2015)
- [Instability, Computational Efficiency and Statistical Accuracy](https://mlsanity.com/paper/2005.11411/) (2020)
- [Estimating the Number of Components in Finite Mixture Models via the Group-Sort-Fuse Procedure](https://mlsanity.com/paper/2005.11641/) (2020)
- [High Dimensional Expectation-Maximization Algorithm: Statistical Optimization and Asymptotic Normality](https://mlsanity.com/paper/1412.8729/) (2014)
- [Overfitting Bayesian Mixture Models with an Unknown Number of Components](https://mlsanity.com/paper/1502.05427/) (2015)
- [An Exponentially Increasing Step-size for Parameter Estimation in Statistical Models](https://mlsanity.com/paper/2205.07999/) (2022)

## Built on by (most cited first, 2 of 2)

- [Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression](https://mlsanity.com/paper/2405.18237/) (2024)
- [Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models](https://mlsanity.com/paper/2206.02455/) (2022)

## Abstract (arXiv)

The Expectation-Maximization (EM) algorithm has been predominantly used to approximate the maximum likelihood estimation of the location-scale Gaussian mixtures. However, when the models are over-specified, namely, the chosen number of components to fit the data is larger than the unknown true number of components, EM needs a polynomial number of iterations in terms of the sample size to reach the final statistical radius; this is computationally expensive in practice. The slow convergence of EM is due to the missing of the locally strong convexity with respect to the location parameter on the negative population log-likelihood function, i.e., the limit of the negative sample log-likelihood function when the sample size goes to infinity. To efficiently explore the curvature of the negative log-likelihood functions, by specifically considering two-component location-scale Gaussian mixtures, we develop the Exponential Location Update (ELU) algorithm. The idea of the ELU algorithm is that we first obtain the exact optimal solution for the scale parameter and then perform an exponential step-size gradient descent for the location parameter. We demonstrate theoretically and empirically that the ELU iterates converge to the final statistical radius of the models after a logarithmic number of iterations. To the best of our knowledge, it resolves the long-standing open question in the literature about developing an optimization algorithm that has optimal statistical and computational complexities for solving parameter estimation even under some specific settings of the over-specified Gaussian mixture models.