A Stochastic Path-Integrated Differential EstimatoR Expectation Maximization Algorithm

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 textttSPIDER-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-integrated differential estimator (tt SPIDER) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an ε-approximate stationary point, the complexity scales as K_operatornameOpt (n,ε )=cal O(ε-1) and K_operatornameCE( n,ε ) = n+ √n cal O(ε-1 ), where K_operatornameOpt( n,ε ) and K_operatornameCE(n, ε ) 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.