# Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence

arXiv: https://arxiv.org/abs/2012.14670 · HTML: https://mlsanity.com/paper/2012.14670/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

## Built on by (most cited first, 7 of 7)

- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Federated Expectation Maximization with heterogeneity mitigation and variance reduction](https://mlsanity.com/paper/2111.02083/) (2021)
- [Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization](https://mlsanity.com/paper/2301.00631/) (2023)
- [The Perturbed Prox-Preconditioned SPIDER algorithm for EM-based large scale learning](https://mlsanity.com/paper/2105.11732/) (2021)
- [Towards frugal unsupervised detection of subtle abnormalities in medical imaging](https://mlsanity.com/paper/2309.02458/) (2023)
- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)
- [Fast Model Selection and Stable Optimization for Softmax-Gated Multinomial-Logistic Mixture of Experts Models](https://mlsanity.com/paper/2602.07997/) (2026)

## Abstract (arXiv)

Fast Incremental Expectation Maximization (FIEM) is a version of the EM framework for large datasets. In this paper, we first recast FIEM and other incremental EM type algorithms in the em Stochastic Approximation within EM framework. Then, we provide nonasymptotic bounds for the convergence in expectation as a function of the number of examples n and of the maximal number of iterations kmax. We propose two strategies for achieving an ε-approximate stationary point, respectively with kmax = O(n2/3/ε) and kmax = O(√n/ε3/2), both strategies relying on a random termination rule before kmax and on a constant step size in the Stochastic Approximation step. Our bounds provide some improvements on the literature. First, they allow kmax to scale as √n which is better than n2/3 which was the best rate obtained so far; it is at the cost of a larger dependence upon the tolerance ε, thus making this control relevant for small to medium accuracy with respect to the number of examples n. Second, for the n2/3-rate, the numerical illustrations show that thanks to an optimized choice of the step size and of the bounds in terms of quantities characterizing the optimization problem at hand, our results desig a less conservative choice of the step size and provide a better control of the convergence in expectation.