Volume 8 (2025)
Miclo, Laurent
On the convergence of global-optimization fraudulent stochastic algorithms
Annales Henri Lebesgue, Volume 8 (2025), pp. 569-587

Metadata

DOI10.5802/ahl.242
Keywords Global optimization, stochastic algorithms, diffusion processes on Riemannian manifolds, almost sure convergence, Morse functions, Bessel processes.

Abstract

We introduce and analyse the almost sure convergence of a new stochastic algorithm for the global minimization of Morse functions on compact Riemannian manifolds. This diffusion process is called fraudulent because it requires the knowledge of minimal value of the function to minimize. Its investigation is nevertheless important, since in particular it appears as the limit behavior of non-fraudulent and time-inhomogeneous swarm mean-field algorithms used in global optimization.


References

[BMV24] Bolte, Jérôme; Miclo, Laurent; Villeneuve, Stéphane Swarm gradient dynamics for global optimization: the density case, Math. Program., Volume 205 (2024) no. 1-2, pp. 661-701 | MR | DOI | Zbl

[CLN06] Chow, Bennett; Lu, Peng; Ni, Lei Hamilton’s Ricci flow, Graduate Studies in Mathematics, 77, American Mathematical Society, 2006 | Zbl

[EK86] Ethier, Stewart N.; Kurtz, Thomas G. Markov processes. Characterization and convergence, Wiley Series in Probability and Statistics, John Wiley & Sons, 1986 | DOI | MR | Zbl

[HKS89] Holley, Richard A.; Kusuoka, Shigeo; Stroock, Daniel W. Asymptotics of the spectral gap with applications to the theory of simulated annealing, J. Funct. Anal., Volume 83 (1989) no. 2, pp. 333-347 | MR | DOI | Zbl

[IW89] Ikeda, Nobuyuki; Watanabe, Shinzo Stochastic differential equations and diffusion processes, North-Holland Mathematical Library, 24, North-Holland; Kodansha Ltd., 1989 | MR | Zbl

[LG15] Le Gall, Jean-François Bessel processes, the Brownian snake and super-Brownian motion, Séminaire de Probabilités XLVII, Springer, 2015, pp. 89-105 | DOI | Zbl

[LTE19] Li, Qianxiao; Tai, Cheng; E, Weinan Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations, J. Mach. Learn. Res., Volume 20 (2019), 40, 47 pages | MR | Zbl

[MZLU22] Mori, Takashi; Ziyin, Liu; Liu, Kangqiao; Ueda, Masahito Power-Law Escape Rate of SGD, Proceedings of the 39th International Conference on Machine Learning (Chaudhuri, Kamalika; Jegelka, Stefanie; Song, Le; Szepesvari, Csaba; Niu, Gang; Sabato, Sivan, eds.) (Proceedings of Machine Learning Research), Volume 162, PMLR (2022), pp. 15959-15975

[RY99] Revuz, Daniel; Yor, Marc Continuous martingales and Brownian motion, Grundlehren der Mathematischen Wissenschaften, 293, Springer, 1999 | Zbl | DOI | MR

[Sil86] Silverman, Bernard W. Density estimation for statistics and data analysis, Monographs on Statistics and Applied Probability, CRC Press, 1986 | MR | Zbl

[SV97] Stroock, Daniel W.; Varadhan, S. R. Srinivasa Multidimensional diffusion processes, Classics in Mathematics, Springer, 1997 | MR | Zbl

[Woj24] Wojtowytsch, Stephan Stochastic gradient descent with noise of machine learning type. II: Continuous time analysis, J. Nonlinear Sci., Volume 34 (2024) no. 1, 16, 45 pages | MR | DOI | Zbl

[WWS22] Wu, Lei; Wang, Mingze; Su, Weijie The alignment property of SGD noise and how it helps select flat minima. A stability analysis, NeurIPS 2022 (Koyejo, Sanmi; Mohamed, S.; Agarwal, Alekh; Belgrave, Danielle; Cho, Kyunghyun; Oh, Alice H., eds.) (Advances in Neural Information Processing), Volume 35, Curran Associates, Inc. (2022), pp. 4680-4693