A Comparison of New and Old Algorithms for A Mixture Estimation Problem

this paper. Our experimental evidence suggests that setting j ? 1 results in a more effective update. These results agree with the infinitesimal analysis in the limit of n !1 based on a stochastic approximation approach [12, 13, 14]. For the exponentiated gradient algorithm, we are able to prove rigorous polynomial bounds on the number of iterations needed to get an arbitrarily good ML-estimator. However, this result assumes that there is a positive lower bound on the probability of each sample point under each of the given distributions. When no such lower bound exists (i.e., when some point has zero or near-zero probability under one of the distributions), we are able to prove similar but weaker bounds for a modified version of EG j . We obtain our global convergence results by viewing the mixture estimation problem as an on-line learning problem. Each iteration becomes a trial where the algorithm is charged a 2 2. Definitions and Problem Statement "loss" of \GammaLogLike(w t ), so minimizing the loss corresponds to maximizing the log-likelihood. Note that the ML solution will also have a loss on each trial. By bounding the extra loss of the algorithm over the loss incurred by the ML solution u over a sequence of iterations, we can show that at least one of the w t vectors produced by the algorithm is reasonably good. Note that these results show convergence in log-likelihood rather than convergence of the mixture vector to the ML solution. Furthermore, the standard convergence results usually apply only when the algorithm is started with a vector near the ML solution, whereas our results show global convergence. The derivations of the learning rules using the above framework are simple and can readily be applied to other settings. They are similar to previous deriv..