Timezone: »

A Stochastic Path Integral Differential EstimatoR Expectation Maximization Algorithm
Gersende Fort · Eric Moulines · Hoi-To Wai

Thu Dec 10 09:00 AM -- 11:00 AM (PST) @ Poster Session 5 #1443
The Expectation Maximization (EM) algorithm is of key importance for inference in latent variable models including mixture of regressors and experts, missing observations. This paper introduces a novel EM algorithm, called {\tt SPIDER-EM}, for inference from a training set of size $n$, $n \gg 1$. At the core of our algorithm is an estimator of the full conditional expectation in the {\sf E}-step, adapted from the stochastic path integral differential estimator ({\tt SPIDER}) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an $\epsilon$-approximate stationary point, the complexity scales as $K_{Opt} (n,\epsilon )={\cal O}(\epsilon^{-1})$ and $K_{CE}( n,\epsilon ) = n+ \sqrt{n} {\cal O}( \epsilon^{-1} )$, where $K_{Opt}( n,\epsilon )$ and $K_{CE}(n, \epsilon )$ are respectively the number of {\sf M}-steps and the number of per-sample conditional expectations evaluations. This improves over the state-of-the-art algorithms. Numerical results support our findings.

Author Information

Gersende Fort (CNRS)
Eric Moulines (Ecole Polytechnique)
Hoi-To Wai (The Chinese University of Hong Kong)

More from the Same Authors