Beyond EM Algorithm on Over-specified Two-Component Location-Scale Gaussian Mixtures
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.