ED Mathématiques et Informatique
A Study of Nesterov Momentum Algorithm for Accelerated Nonconvex and Stochastic Optimization
by Julien HERMANT (IMB - Institut de Mathématiques de Bordeaux)
The defense will take place at 14h00 - Salle de conférence Université de Bordeaux, 351 cours de la Libération, Bâtiment A33, 33400, Talence
in front of the jury composed of
- Jean-François AUJOL - Professeur des universités - Université de Bordeaux - Directeur de these
- Aude RONDEPIERRE - Professeure des universités - INSA Toulouse - CoDirecteur de these
- Aris DANIILIDIS - Professor - TU Wien - Rapporteur
- Adrien TAYLOR - Chargé de recherche - Centre de Recherche INRIA de Paris - Rapporteur
- Antonin CHAMBOLLE - Directeur de recherche - Université Paris Dauphine-PSL - Examinateur
- Jalal FADILI - Professeur des universités - Université Caen Normandie - Examinateur
- Edouard PAUWELS - Professeur des universités - Toulouse School of Economics - Examinateur
Optimization algorithms play an important role in many applications. One of the key criteria for a good algorithm is fast convergence, which can be challenging to achieve due to the large scale of modern problems. Among the mechanisms enabling efficient algorithms, an important one is momentum. In particular, it is widely observed in a large range of learning applications that adding such a mechanism to gradient descent accelerates its convergence. While this acceleration phenomenon is well understood in the setting of smooth convex minimization using full gradients, many machine learning problems are non-convex and rely on stochastic mini-batch estimators of the gradient. This thesis provides a theoretical study of the acceleration induced by Nesterov's momentum mechanisms in such settings. Our first contribution is motivated by the observation that in several natural non-convex or stochastic settings, many existing analyses do not establish any acceleration property with momentum. We identify geometric conditions under which momentum provably yields acceleration. For non-convex functions satisfying a Polyak–Łojasiewicz condition, we show that the possibility of acceleration depends on the angle between the descent direction and the direction toward minimizers. In the convex stochastic finite-sum setting, if it verifies the interpolation assumption (typical of over-parameterized models), we show that acceleration is governed by the average correlation between the gradients composing the sum. Our second contribution builds on the recently proposed continuized Nesterov method. It can be understood as a Nesterov algorithm, which can be analyzed using continuous-time stochastic Lyapunov approaches. We extend this framework and use it to derive new results in non-convex optimization. In particular, we prove that Nesterov's Momentum, under a suitable stochastic parametrization, achieves the best known rate among gradient-based methods for approximating a critical point of functions with Lipschitz-continuous gradients and Hessians, without the momentum-reset mechanisms needed by existing works. We also improve existing convergence guarantees for strongly quasar-convex optimization by refining the rate and weakening assumptions on the set of minimizers.