Timezone: »

High-Dimensional Variance-Reduced Stochastic Gradient Expectation-Maximization Algorithm
Rongda Zhu · Lingxiao Wang · Chengxiang Zhai · Quanquan Gu

Tue Aug 08 09:24 PM -- 09:42 PM (PDT) @ C4.4
We propose a generic stochastic expectation-maximization (EM) algorithm for the estimation of high-dimensional latent variable models. At the core of our algorithm is a novel semi-stochastic variance-reduced gradient designed for the $Q$-function in the EM algorithm. Under a mild condition on the initialization, our algorithm is guaranteed to attain a linear convergence rate to the unknown parameter of the latent variable model, and achieve an optimal statistical rate up to a logarithmic factor for parameter estimation. Compared with existing high-dimensional EM algorithms, our algorithm enjoys a better computational complexity and is therefore more efficient. We apply our generic algorithm to two illustrative latent variable models: Gaussian mixture model and mixture of linear regression, and demonstrate the advantages of our algorithm by both theoretical analysis and numerical experiments. We believe that the proposed semi-stochastic gradient is of independent interest for general nonconvex optimization problems with bivariate structures.

Author Information

Rongda Zhu (Facebook)
Lingxiao Wang (University of Virginia)
Chengxiang Zhai (University of Illinois at Urbana-Champaign)
Quanquan Gu (University of Virginia)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors