Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization

Gersende Fort, Eric Moulines, Hoi-To Wai

Abstract

The Expectation-Maximization (EM) algorithm is a cornerstone of statistical learning for models with latent variables. However, its scalability is limited by the need for full-data passes. We present Geom-SPIDER-EM, a variance-reduced stochastic EM variant that achieves state-of-the-art convergence rates. By integrating a geometric looping structure with the Stochastic Path-Integrated Differential EstimatoR (SPIDER) technique, our method reaches the optimal $O(\sqrt{n}/\epsilon)$ complexity for nonconvex finite-sum optimization. Empirical results on Gaussian Mixture Models demonstrate significant speedups over traditional and existing stochastic EM methods.

Introduction

The Expectation-Maximization (EM) algorithm is the standard approach for maximum likelihood estimation in models with hidden or missing data, such as Gaussian Mixture Models (GMMs) or Topic Models. Despite its popularity, traditional EM faces significant hurdles in the era of big data. It requires a full pass over the entire dataset of $n$ samples at every iteration, making it computationally prohibitive when $n$ is in the millions. Furthermore, the E-step often involves complex integrals that add to the computational burden.

While stochastic EM variants like Online-EM have been proposed to handle large datasets, they often suffer from high variance in their gradient estimates, leading to slow convergence. This paper introduces Geom-SPIDER-EM, an algorithm designed to be both computationally efficient per iteration and mathematically stable enough to converge rapidly.

Methodology: The g-SPIDER-EM Framework

The core of g-SPIDER-EM (generalized Stochastic Path-Integrated Differential EstimatoR EM) lies in several key innovations:

1. Variance Reduction via SPIDER

Instead of relying on a simple mini-batch to estimate the gradient, g-SPIDER-EM tracks the "path" of previous estimates. This Path-Integration technique significantly reduces the noise inherent in stochastic steps, allowing for larger step sizes and faster overall convergence.

2. Geometric Epoch Lengths

The algorithm operates using a nested loop structure. A thorough update is performed in an outer loop, followed by multiple rapid, variance-reduced updates in an inner loop. A primary theoretical contribution of this work is the use of random inner loop lengths following a geometric distribution. This "Geom" approach simplifies theoretical analysis and provides greater flexibility in adapting to data characteristics.

3. Flexible Initializations and Quadratic Growth

Unlike previous variance-reduced EM methods, g-SPIDER-EM allows for perturbations or partial updates at the start of each epoch. A particularly effective practical strategy identified is "quadratic growth," where the algorithm starts with small batches and few inner loops, gradually increasing them as optimization progresses. This balances the cost per iteration with the speed of convergence.

Experimental Evaluation

The researchers evaluated g-SPIDER-EM using the MNIST dataset (60,000 images of handwritten digits). The task was to fit a Gaussian Mixture Model (GMM) with 12 components. To ensure computational efficiency during testing, Principal Component Analysis (PCA) was used to reduce the dimensionality from 784 pixels to the 20 most significant features.

Convergence of g-SPIDER-EM variants compared to Online-EM over iterations.

As shown in Figure 1, the proposed g-SPIDER-EM variants (both deterministic "ctt" and geometric "geom" versions) significantly outperform the standard Online-EM. While Online-EM plateaus, the variance-reduced methods continue to drive the error down to much lower levels over successive iterations.

Key Insights and Results

  • Optimal Complexity: The paper proves that g-SPIDER-EM achieves the theoretical lower bound for complexity in this class of algorithms: $O(\sqrt{n}/\epsilon)$.
  • The "Lock-in" Phenomenon: The authors observe that once the algorithm nears a solution, it "locks in" and converges at a linear rate. This is formally linked to the Polyak-Łojasiewicz (PL) condition.
  • Efficiency of Quadratic Growth: The "quad-ctt" variant, which uses deterministic loops with quadratic growth, emerged as the most efficient strategy for practical use.
Error reduction relative to the number of gradient evaluations, demonstrating computational efficiency.

Figure 4 highlights the computational efficiency of the proposed methods. By plotting error against the total number of gradient evaluations, it is clear that the "quad" strategies reach high precision with significantly less total computation than "full" or "half" epoch strategies.

Conclusion

Geom-SPIDER-EM represents a significant step forward in making EM practical for massive, nonconvex optimization problems. While the fastest convergence proofs rely on the PL condition—which may not hold for all complex models—the empirical performance is robust. Future work includes extending this framework to deep latent variable models and adapting it for distributed computing environments.

Summary updated

Abstract

The Expectation Maximization (EM) algorithm is a key reference for inference in latent variable models; unfortunately, its computational cost is prohibitive in the large scale learning setting. In this paper, we propose an extension of the Stochastic Path-Integrated Differential EstimatoR EM (SPIDER-EM) and derive complexity bounds for this novel algorithm, designed to solve smooth nonconvex finite-sum optimization problems. We show that it reaches the same state of the art complexity bounds as SPIDER-EM; and provide conditions for a linear rate of convergence. Numerical results support our findings.
BibTeX
@inproceedings{fort2021geom,
  author = {Gersende Fort and Eric Moulines and Hoi-To Wai},
  title = {{Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  doi = {10.1109/icassp39728.2021.9414271},
}
Figure