Wednesday, January 10, 2024

Optimization by linear kinetic equations and mean-field Langevin dynamics

Lorenzo Pareschi (preprint arXiv:2401.05553)

Probably one of the most striking examples of the close connections between global optimization processes and statistical physics is the simulated annealing method, inspired by the famous Monte Carlo algorithm devised by Metropolis et al. in the middle of the last century. In this paper we show how the tools of linear kinetic theory allow to describe this gradient-free algorithm from the perspective of statistical physics and how convergence to the global minimum can be related to classical entropy inequalities. This analysis highlight the strong link between linear Boltzmann equations and stochastic optimization methods governed by Markov processes.

Thanks to this formalism we can establish the connections between the simulated annealing process and the corresponding mean-field Langevin dynamics characterized by a stochastic gradient descent approach. Generalizations to other selection strategies in simulated annealing that avoid the acceptance-rejection dynamic are also provided.