It seems that MLE (via EM) is widely used in machine learning / statistics to learn the parameters of a mixture of Gaussians. I'm assuming we're given random samples from the mixture.

My question is: Are there any proven quantitative bounds on the error in terms of the number of samples (and perhaps the parameters of the Gaussian)?

For example, what is the runtime required to estimate the parameters up to a certain error?

Ideally, these bounds would not assume that we start in a local neighborhood of the optimal solution or any such thing. (If EM is not the method of choice and there is a better way of doing it, please point this out, as well.)

  • 2
    $\begingroup$ EM is not a heuristic, it is an algortihm for maximizing likelihood with known properties. The error you are looking for probably has nothing to do with EM, but rather the efficiency of the maximum likelihood estimate. This will surely depend on the unknown parameters, and not just the sample size. $\endgroup$
    – Aniko
    Aug 24, 2010 at 0:00
  • $\begingroup$ Yep, my question refers to those "known properties". It is used as a heuristic in the sense that I see people apply it on "good faith" beyond what is explained by provable bounds. I changed the wording of the question, since this is really not the issue I'm interested in. $\endgroup$
    – Moritz
    Aug 24, 2010 at 0:59

1 Answer 1


EM essentially solves the maximum likelihood problem and therefore has the same properties w.r.t. sample sizes. EM for Gaussian mixture models is known to converge asymptotically to a local maximum and exhibits first order convergence (see this paper).

BTW, there are some results which quantify how good the EM solution is in terms of the parameters of the data distribution. See this paper which shows that the goodness depends on the separation of mixture components (measured by variances). A lot of papers have analyzed mixture models using this criteria.

If you don't want to use EM for mixture models, you can take a fully Bayesian approach.

  • $\begingroup$ @Moritz : In reply to your comment about EM being a heuristic, EM does have strong theoretical foundations and it is known to provably converge to a local maximum. $\endgroup$
    – ebony1
    Aug 24, 2010 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.