An Online Minorization-Maximization Algorithm

Hien D. Nguyen, Florence Forbes, Gersende Fort, Olivier CappéStudies 2023 · DOI · OpenAlex

Abstract

Modern statistical and machine learning settings often involve high data volume and data streaming, which require the development of online estimation algorithms. The online Expectation–Maximization (EM) algorithm extends the popular EM algorithm to this setting via a stochastic approximation approach. We show that an online version of the Minorization–Maximization (MM) algorithm, which includes the online EM algorithm as a special case, can also be constructed in a similar manner. We demonstrate our approach via an application to the logistic regression problem and compare it to existing methods.

Introduction

In contemporary machine learning, the prevalence of streaming data—information arriving continuously and in volumes exceeding storage capacities—necessitates optimization algorithms that can process data sequentially. Traditional optimization methods, such as the Minorization-Maximization (MM) algorithm, are typically "batch" oriented, requiring access to the entire dataset for each parameter update.

While online variants of the Expectation-Maximization (EM) algorithm have been developed, existing online MM frameworks often rely on restrictive assumptions like strict convexity. This paper introduces a generalized Online MM framework that leverages stochastic approximation to handle complex models, such as Mixture of Experts (MoE), where latent variables may lack simple stochastic representations.

The Online MM Framework

The proposed algorithm adapts the MM principle to a stochastic setting. Instead of maximizing a complex objective function $f$ directly, the MM algorithm maximizes a simpler "surrogate" function, or minorizer, that lower-bounds the objective and matches it at the current estimate.

Stochastic Approximation and Update Rules

The core innovation lies in assuming the minorizer follows a specific functional form: a combination of a fixed function and a linear combination of sufficient statistics. Rather than updating the model parameters $\theta$ directly from a single data point, the algorithm maintains a running estimate of the expected sufficient statistics ($s_n$).

The update rule uses a step size ($\gamma$) to blend the previous estimate with new information:

  1. Statistic Update: $s_n = (1 - \gamma_n)s_{n-1} + \gamma_n \bar{s}(x_n, \theta_{n-1})$
  2. Parameter Update: $\theta_n = \arg\max_{\theta} Q(s_n, \theta)$

This approach is truly "online," requiring only the current data point and the current state of the statistics to proceed.

Numerical Illustration: Logistic Regression

The algorithm's performance was evaluated using a simulated logistic regression task with $10^5$ i.i.d. replicates. Features were drawn from a normal distribution, with labels generated via a Bernoulli distribution based on ground-truth parameters $\theta_0 = (3, -3)$. The results were benchmarked against the batch Maximum Likelihood Estimate (MLE) obtained via standard software.

Convergence of parameter estimates $\theta_1$ and $\theta_2$ for the online MM algorithm compared to stochastic gradient methods. The top row shows raw trajectories, while the bottom row displays the smoother Polyak averaged estimates.

Results and Discussion

The numerical experiments demonstrated that the Online MM algorithm is highly effective. The final parameter estimates (3.01, -3.03) were remarkably close to both the true values (3, -3) and the batch MLE (3.00, -3.05).

Key insights from the experiments include:

  • Stability: The MM approach acts as a stabilizer. While Stochastic Gradient (SG) descent can be slow and Stochastic Newton-Raphson (SNR) can be volatile, Online MM provides a smoother trajectory toward the batch estimate.
  • Efficiency via Averaging: When combined with Polyak averaging, the Online MM trajectory exhibited significantly less bias and noise than standard SG approaches, as seen in the bottom panels of the figure above.
  • Generalization: The framework successfully unifies Online EM and MM, showing that Online EM is a special case of this broader stochastic approximation framework.

Conclusion

This paper provides a robust Online MM framework suitable for high-volume streaming data. By replacing the Hessian in a Newton-Raphson update with a stable lower bound, the algorithm achieves a balance between speed and stability. Future work will extend this framework to Mixture of Experts (MoE) models, where the surrogate structure is particularly well-suited for handling complex latent variable structures.

Summary updated

Abstract

Abstract Modern statistical and machine learning settings often involve high data volume and data streaming, which require the development of online estimation algorithms. The online Expectation–Maximization (EM) algorithm extends the popular EM algorithm to this setting, via a stochastic approximation approach.We show that an online version of the Minorization–Maximization (MM) algorithm, which includes the online EM algorithm as a special case, can also be constructed in a similar manner. We demonstrate our approach via an application to the logistic regression problem and compare it to existing methods.
BibTeX
@inproceedings{nguyen2023online,
  author = {Hien D. Nguyen and Florence Forbes and Gersende Fort and Olivier Cappé and Hien Duy Nguyen},
  title = {{An Online Minorization-Maximization Algorithm}},
  booktitle = {Studies},
  year = {2023},
  doi = {10.1007/978-3-031-09034-9\_29},
}
Figure