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.
Chapter PDF
Similar content being viewed by others
Keywords
References
Bohning, D.: Multinomial logistic regression algorithm. Ann. Inst. Stat. Math. (1992)
Borkar, V.S.: Stochastic approximation: A dynamical systems viewpoint. Springer (2009)
Cappé, O., Moulines, E.: On-line expectation-maximization algorithm for latent data models. J. Roy. Stat. Soc. B Stat. Meth. 71, 593–613 (2009)
Cui, Y., Pang, J.: Modern nonconvex nondifferentiable optimization. SIAM, Philadelphia (2022)
Delyon, B., Lavielle, M., Moulines, E.: Convergence of a stochastic approximation version of the EM algorithm. Ann. Stat. 27, 94–128 (1999)
Dempster, A. P., Laird, N. M., Rubin, D. B.: Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. B Stat. Meth. 39, 1–38 (1977)
Fort, G., Gach, P., Moulines, E.: Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence. Stat. Comput. 31, 1–24 (2021)
Fort, G., Moulines, E., Wai, H. T.: A stochastic path-integrated differential estimator expectation maximization algorithm. In: Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS) (2020)
Hazan, E.: Introduction to online convex optimization. Foundations andTrends in Optimization. 2 (2015)
Karimi, B., Miasojedow, B., Moulines, E., Wai, H. T.: Non-asymptotic analysis of biased stochastic approximation scheme. Proceedings of Machine Learning Research. 99, 1–31 (2019)
Karimi, B., Wai, H. T., Moulines, R., Lavielle, M.: On the global convergence of (fast) incremental expectation maximization methods. In: Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS) (2019)
Kuhn, E., Matias, C., Rebafka, T.: Properties of the stochastic approximation EM alpgorithm with mini-batch sampling. Stat. Comput. 30, 1725–1739 (2020)
Kushner, H. J., Yin, G. G.: Stochastic Approximation and Recursive Algorithms and Applications. Springer, New York (2003)
Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning. Springer, Cham (2020)
Lange, K.: MM Optimization Algorithms. SIAM, Philadelphia (2016)
Mairal, J.: Stochastic majorization-minimization algorithm for large-scale optimization. In: Advances in Neural Information Processing Systems, pp. 2283–2291 (2013)
McLachlan, G. J., Krishnan, T.: The EM Algorithm And Extensions.Wiley, New York (2008)
Mokhtari, A., Koppel, A.: High-dimensional nonconvex stochastic optimization by doubly stochastic successive convex approximation. IEEE Trans. Signal Process. 68, 6287–6302 (2020)
Nguyen, H.D., Forbes, F., McLachlan, G. J.: Mini-batch learning of exponential family finite mixture models. Stat. Comput. 30, 731–748 (2020)
Nguyen, H. D., McLachlan, G. J.: Laplace mixture of linear experts. Comput. Stat. Data Anal. 93, 177–191 (2016)
Polyak, B. T., Juditsky, A. B.: Acceleration of stochastic approximation by averaging. SIAM J. Contr. Optim. 30, 838–855 (1992)
Razaviyayn, M., Sanjabi, M., Luo, Z.: A stochastic successive minimization method for nonsmooth nonconvex optimization with applications to transceiver design in wireless communication networks. Math. Program. Series B. 515–545 (2016)
Shalev-Shwartz, S.: Online learning and online convex optimization. Foundations and Trends in Machine Learning. 4, 107–194 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this paper
Cite this paper
Nguyen, H.D., Forbes, F., Fort, G., Cappé, O. (2023). An Online Minorization-Maximization Algorithm. In: Brito, P., Dias, J.G., Lausen, B., Montanari, A., Nugent, R. (eds) Classification and Data Science in the Digital Age. IFCS 2022. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, Cham. https://doi.org/10.1007/978-3-031-09034-9_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-09034-9_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-09033-2
Online ISBN: 978-3-031-09034-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)