METANOLIN
(METAstability for NOnLINear processes)
ANR-19-CE40-0009 2019 -- 2024
Principal Investigator: Julian Tugaut
News:
The paper "Measure-dependent non-linear diffusions with superlinear drifts: asymptotic behaviour of the first exit-times" from Ashot Aleksian and me is accepted for publication in Electronic Journal of Probability. In this work, we establish the asymptotics of the exit-times for self-stabilizing diffusions, without assuming convexity assumption neither on the confining potential nor on the interacting one.
Past News:
Ashot ALEKSIAN, the PhD student of Aline and me, has defended his excellent thesis on Monday 20th of November 2023.
In 2023 (from Wednesday 31st of May to Friday 2nd of June), Aline Kurtzmann and me have organized a workshop in Nancy.
In 2022 (from Tuesday 17th of May to Friday 20th of May), the ANR projects METANOLIN and QuAMProcs organized a common workshop in Saint-Étienne. Organizers: Aline Kurtzmann, Laurent Michel, Julien Reygner and me. This workshop was planned in November 2020 but it has been postponed due to pandemie.
Project METANOLIN (and University Jean Monnet) has funding for one PhD student (for three years). Subject. If you are interested, please send us (Julian Tugaut and Aline Kurtzmann) a mail with a CV and a letter of intent (in french or in english) before the 29th of May 2020. The position is filled.
Abstract:
The main objective of the team of this project is to tackle metastability problems related to stochastic processes having non-linear dynamics (meaning that such dynamics involve the law or the path of the process itself). Roughly speaking, the metastability problems arise when one is interested in intricate optimization problem involving method related to stochastic gradient approach, which is precisely the setting of this project. Especially, we will use these properties in order to obtain faster algorithms than the usual ones.
The optimization problem of a given cost function naturally appears in many fields of science e.g. in deep learning (which is of particular interest in artificial intelligence). To answer it, the gradient descent method appears to be well adapted. When using this algorithm, we are led to consider the dynamical system which follows the line of the potential (i.e. the cost function). Assuming that the potential is convex outside a compact of interest, we know that the dynamical system does converge towards a critical point. Unfortunately, nothing ensures us that this is the argument of the global minimum nor that this corresponds to a local minimum of the potential.
A typical strategy then consists in adding some Brownian noise to the system in order to leave the critical points which are not local minima. When doing so, we face two problems related to the intensity of the noise added in the system. On the one hand, if this intensity is too large, the system will not consider the geometry of the potential anymore so that the algorithm becomes inefficient. On the other hand, if this intensity is too small, a classical result of Freidlin and Wentzell (large deviations theory, see (8)) tells us that the process will spend an exponentially large time in each local minimum visited: this is what is called a metastability phenomenon. It is plain to see that, in this last case, the convergence rate of the algorithm will be dramatically impacted..
These local minima are called the wells of the potential and the result of Freidlin and Wentzell says that the time spent by the process in those wells is in the exponential of the height of the wells divided by the square of the intensity of the noise: this rule is known as the Kramers'type law (or the Arrhenius-type law). Hence, to handle such a competition (between large and small intensities), the main idea consists in adding a time-varying coefficient in the front of the noise which will precisely allow to adjust its intensity: one talks about simulated annealing algorithm.
In this project, we build faster simulated annealing algorithms based on non-linear diffusions processes that, despite of being more complex, allow to obtain a better exploration of the phase space, see (1). Since the rate of convergence of the algorithm is characterized by the exit-time of the process from the basins of attraction of the local minima, our project will involve techniques linked to the exit-time of non-linear processes. Especially, we will focus on two main classes of such processes: the self-stabilizing one (which is of McKean-Vlasov type) and the self-interacting one.
The first class can be seen as the hydrodynamical limit of a mean-field interacting particles system (see (3)). In other words, let us consider a large number of particles living in an external potential (the cost function) and interacting each other through the empirical measure of the system (so that the interaction is in mean-field) we get, thanks to the independence of the Brownian perturbations of each particle, that the asymptotic dynamics of the particles are given by independent processes with drift depending on their own law. Crucially, from a numerical point of view, we expect that a repulsion between the particles facilitates the exploration of the phase space since they will try to avoid themselves. Indeed, it can be deduced from the works of J.T. and his collaborators (see (10), (11), (19), (20), (21), (22) and (23)), that this exit-time, for a concave interacting potential, is smaller than without interaction and, in turn, the rate of convergence of the algorithm is better.
For the second class, namely the self-interacting process, the main particularity comes from the dependence of the dynamics w.r.t. its own history (meaning that the coefficient depends on the path itself). When the interacting potential is quadratic, the drift involves the temporal mean of the path (see (4), (9), (13) and (14)). Pierre Del Moral, A.K. and J.T. recently provide a similar result from the above one (see (7)): when the interacting potential is concave, the exit-time will be smaller than without interaction so that this will accelerate the convergence of the algorithm..
Our aim is then to carry out the rigorous analysis of the previously described metastability phenomenon associated with non-linear processes (in particular the study of the exit-time from wells when the interacting potential is concave). The first step (see (7) for the self-interacting diffusion and (10), (11), (19), (20), (21), (22) and (23) for the self-stabilizing one) being given, the next questions are typically: the case where the potentials are not convex (especially if the interacting one is concave), the case with time-varying diffusion coefficient (see (1)) and the one where the interacting potential is singular (see (2), (5), (6), (12) and (18)).
Bibliography:
[1] Convergence analysis of Adaptive Biasing Potential methods for diffusion processes. Preprint. M. Benaïm and C-E. Bréhier.
[2] Dynamics of a planar Coulomb gas. Preprint. F. Bolley, D. Chafaï and J. Fontbona.
[3] Probabilistic approach for granular media equations in the non-uniformly convex case. Probability Theory and Related Fields 140 (2008), no 1-2, 19-40. P. Cattiaux, A. Guillin and F. Malrieu.
[4] Some particular self-interacting diffusions : ergodic behaviour and almost sure convergence. Bernoulli 17 (2011), no 4, 1248-1267. S. Chambeu and A. Kurtzmann
[5] Strong existence and uniqueness for stochastic differential equations with Hölder drift and degenerate noise. Annales de l'Institut Henri Poincaré (B). P-E. Chaudru de Raynal
[6] Strong well-posedness of McKean-Vlasov stochastic differential equation with Hölder drift. Preprint. P-E. Chaudru de Raynal.
[7] A Kramers'type law for self-interacting diffusions. Preprint. P. Del Moral, A. Kurtzmann and J. Tugaut. In revision for Bernoulli.
[8] Large deviations techniques and applications. Stochastic Modelling and Applied Probability, 38. Springer-Verlag, Berlin, 2010, xvi+396 pp. ISBN : 978-3-642-03310-0. A. Dembo and O. Zeitouni
[9] Strongly self-interacting processes on the circle. To appear in Stochastics. C-E. Gauthier and P. Monmarché
[10] Large deviations and a Kramers'type law for self-stabilizing diffusions. Annals of Applied Probability 18, no 4, (2008), pp 1379-1423. S. Herrmann, D. Peithmann and P. Imkeller
[11] Mean-field limit versus small-noise limit for some interacting particle systems. Communications On Stochastics Analysis, Vol 10. No 1 (2016) 39-55. S. Herrmann and J. Tugaut
[12] Mean-field limit of a particle approximation of the one-dimensional parabolic-parabolic Keller-Segel model without smoothing. To appear in Electronic Communications in Probability. J-F. Jabir, D. Talay and M. Tomasevic.
[13] Ergodicity of self-attracting motion. Electronic Journal of Probability 17 (2012) no 50, 37 pp. V. Kleptsyn and A. Kurtzmann
[14] The ODE method for some self-interacting diffusions on R^d. Ann. Inst. Henri Poincaré Prob. Stat. 46 (2010) no 3, 618-643. A. Kurtzmann
[15] Piecewise deterministic simulated annealing. ALEA vol. 13(1), 357-398, 2016. P. Monmarché
[16] Hypocoercivity in metastable settings and kinetic simulated annealing. To appear in Probability Theory and Related Fields. P. Monmarché
[17] Weakly self-interacting piecewise deterministic bacterial chemotaxis. To appear in Markov Processes and Related Fields. P. Monmarché
[18] A new McKean-Vlasov stochastic interpretation of the parabolic-parabolic Keller-Segel model : The one dimensional case. Preprint. D. Talay and M. Tomasevic.
[19] Exit problem of McKean-Vlasov diffusions in convex landscape. Electronic Journal of Probability 17 (2012) no 76, 1-26. J. Tugaut
[20] A simple proof of a Kramers'type law for self-stabilizing diffusions. Electronic Communications in Probability. Volume 21 (2016) paper no 11, 7pp. J. Tugaut
[21] Exit problem of McKean-Vlasov diffusion in double-wells landscape. Journal of Theoretical Probability. Volume 31 (2018), Issue 2, pages 1013-1023. J. Tugaut
[22] A simple proof of a Kramers'type law for self-stabilizing diffusions in double-wells landscape. To appear in ALEA. J. Tugaut.
[23] Exit-time of mean-field particles system. To appear in ESAIM Probability and statistics. J. Tugaut.