Scalable particle-based alternatives to EM

Juan Kuntz, Adam M. Johansen

Abstract

Neal and Hinton (1998) recast maximum likelihood estimation of any given latent variable model as the minimization of a free energy functional $F$, and the EM algorithm as coordinate descent applied to $F$. Here, we explore alternative ways to optimize the functional. In particular, we identify various gradient flows associated with $F$ and show that their limits coincide with $F$'s stationary points. By discretizing the flows, we obtain practical particle-based algorithms for maximum likelihood estimation in broad classes of latent variable models. The novel algorithms scale to high-dimensional settings and perform well in numerical experiments.

Introduction

Latent variable models (LVMs) are fundamental to modern machine learning, yet training them often relies on the Expectation-Maximization (EM) algorithm. While EM is elegant, it faces challenges in high-dimensional settings or with complex probability landscapes where the E-step is analytically intractable. Traditional Monte Carlo EM variants often suffer from computational inefficiency due to restarting simulations at each iteration.

This work proposes a family of particle-based algorithms—Particle Gradient Descent (PGD), Particle Quasi-Newton (PQN), and Particle Marginal Gradient Descent (PMGD)—that treat maximum likelihood estimation as a joint gradient flow on a free energy functional.

Methods

The core innovation lies in recasting EM as the minimization of a Free Energy functional. Instead of alternating coordinate descent between parameters ($\theta$) and distributions ($q$), we move both simultaneously via gradient flows.

Particle-Based Algorithms

  • Particle Gradient Descent (PGD): Simulates $N$ persistent particles in the latent space using Langevin dynamics while simultaneously updating model parameters.
  • Particle Quasi-Newton (PQN): Employs a Hessian-based update for parameters to handle ill-conditioning when parameters and latent variables exist on different scales.
  • Particle Marginal Gradient Descent (PMGD): Optimized for models where the M-step is analytically solvable but the E-step is not.

Unlike standard MCMC-EM, these methods utilize persistent particles. By using the final positions of particles from one step as the starting point for the next, the algorithms effectively "warm-start" the inference, improving efficiency and robustness.

Algorithm comparison showing parameter convergence and latent probability distributions across different methods.

Experimental Evaluation

The proposed methods were evaluated on synthetic hierarchical models, Bayesian logistic regression (Wisconsin Breast Cancer), and deep learning tasks (MNIST and CelebA).

Key Insights

  • Joint Optimization: Treating parameters and latent distributions as a single joint problem allows the use of advanced optimization tools like Adam or Quasi-Newton methods.
  • Geometric Framework: The use of Wasserstein-2 geometry provides a rigorous mathematical foundation for pushing particle clouds toward the correct posterior.
  • Parallelization: The independent nature of particle updates makes these algorithms "embarrassingly parallel," leading to significant speedups on modern hardware.

Results

The particle methods demonstrated superior performance across multiple benchmarks. In Bayesian Neural Network experiments on MNIST, these methods successfully navigated multimodal posteriors where traditional approaches like SOUL struggled.

Performance comparison (Error and Time) for different particle numbers (N) on a classification task.

As shown in the table above, for $N=100$, the particle methods achieved significantly lower test errors (approx. 2.4%) compared to SOUL (6.85%) while being substantially faster. In Bayesian logistic regression, the methods were up to 10x faster than state-of-the-art MCMC alternatives due to better vectorization.

Conclusion

Particle-based gradient flows offer a scalable and robust alternative to the EM algorithm for training LVMs. By leveraging persistent particles and joint optimization, these methods handle high-dimensional data and complex distributions more effectively than traditional coordinate descent. While local optima and small asymptotic biases remain challenges, the framework's compatibility with modern GPU acceleration and advanced optimization techniques marks a significant step forward for latent variable modeling.

Summary updated

Abstract

Neal and Hinton, 1998) recast maximum likelihood estimation of any given latent variable model as the minimization of a free energy functional $F$, and the EM algorithm as coordinate descent applied to $F$. Here, we explore alternative ways to optimize the functional. In particular, we identify various gradient flows associated with $F$ and show that their limits coincide with $F$'s stationary points. By discretizing the flows, we obtain practical particle-based algorithms for maximum likelihood estimation in broad classes of latent variable models. The novel algorithms scale to high-dimensional settings and perform well in numerical experiments.
BibTeX
@misc{kuntz2022scalable,
  author = {Juan Kuntz and Adam M. Johansen},
  title = {{Scalable particle-based alternatives to EM}},
  year = {2022},
  eprint = {2204.12965},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.12965},
}
Figure