Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence
| العنوان: | Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence |
|---|---|
| المؤلفون: | Gersende Fort, Pierre Gach, Eric Moulines |
| المساهمون: | Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Modélisation en pharmacologie de population (XPOP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Fondation Simone et Cino del Duca, Russian Academic Excellence Project '5-100', ANR-19-CE23-0017,MaSDOL,Mathématiques de l'optimisation déterministe et stochastique liées à l'apprentissage profond(2019), ANR-19-CHIA-0002,SCAI,Inférence statistique, méthodes numériques et Intelligence Artificielle(2019), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Statistics and Computing Statistics and Computing, Springer Verlag (Germany), In press, 31 (48) Statistics and Computing, In press, 31 (48), ⟨10.1007/s11222-021-10023-9⟩ |
| بيانات النشر: | HAL CCSD, 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | Statistics and Probability, FOS: Computer and information sciences, Computer Science - Machine Learning, Optimization problem, Computer Science - Artificial Intelligence, Incremental Expectation Maximization algorithm, Scale (descriptive set theory), Machine Learning (stat.ML), 010103 numerical & computational mathematics, Type (model theory), Stochastic approximation, 01 natural sciences, Theoretical Computer Science, Machine Learning (cs.LG), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 010104 statistics & probability, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, Momentum Stochastic Approximation, Expectation–maximization algorithm, Convergence (routing), 0101 mathematics, Mathematics, Discrete mathematics, Finite-sum optimization, Function (mathematics), [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH], Stationary point, Computational Statistical Learning, Artificial Intelligence (cs.AI), Computational Theory and Mathematics, Large Scale Learning, Statistics, Probability and Uncertainty, [STAT.ME]Statistics [stat]/Methodology [stat.ME] |
| الوصف: | 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 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 $$K_\mathrm {max}$$ . We propose two strategies for achieving an $$\epsilon $$ -approximate stationary point, respectively with $$K_\mathrm {max}= O(n^{2/3}/\epsilon )$$ and $$K_\mathrm {max}= O(\sqrt{n}/\epsilon ^{3/2})$$ , both strategies relying on a random termination rule before $$K_\mathrm {max}$$ and on a constant step size in the Stochastic Approximation step. Our bounds provide some improvements on the literature. First, they allow $$K_\mathrm {max}$$ to scale as $$\sqrt{n}$$ which is better than $$n^{2/3}$$ which was the best rate obtained so far; it is at the cost of a larger dependence upon the tolerance $$\epsilon $$ , thus making this control relevant for small to medium accuracy with respect to the number of examples n. Second, for the $$n^{2/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 design a less conservative choice of the step size and provide a better control of the convergence in expectation. |
| اللغة: | English |
| تدمد: | 0960-3174 1573-1375 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::87e42224ab0a892f1c4ea7a9c72d4915 https://hal.archives-ouvertes.fr/hal-02617725v2/file/FGM_HAL.pdf |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....87e42224ab0a892f1c4ea7a9c72d4915 |
| قاعدة البيانات: | OpenAIRE |
Find this article in full text from Springer Verlag. | تدمد: | 09603174 15731375 |
|---|