-
2025
En-Nebbazi Nassim
[abstract][résumé]
We consider a class of stochastic Heavy--Ball optimization schemes. Assuming that the objective function is strongly convex, we prove weak error estimate which is uniform in time for the error between the solution of the numerical scheme, and the solution of continuous-time modified (or high-resolution) differential equations at first order, with respect to the time-step size. At first order, the modified equation is deterministic. We go beyond existing results where the error estimates have been considered only on finite time intervals and were not uniform in time. This allows us to then provide a rigorous complexity analysis of the method in the large time and small time-step size regimes. We provide numerical experiments to illustrate the convergence result.
Nous considérons une classe de schémas d'optimisation stochastiques de type Heavy-Ball. En supposant que la fonction objectif est fortement convexe, nous démontrons une estimation de l'erreur faible, uniforme en temps, entre la solution du schéma numérique et la solution d'équations différentielles modifiées (ou à haute résolution) en temps continu à l'ordre un, par rapport au pas de temps. À l'ordre un, l'équation modifiée est déterministe. Nous allons au-delà des résultats existants, dans lesquels les estimations d'erreur n'étaient considérées que sur des intervalles de temps finis et n'étaient pas uniformes en temps. Cela nous permet ensuite de fournir une analyse de complexité rigoureuse de la méthode dans les régimes de grand temps et de petit pas de temps. Nous présentons des expériences numériques illustrant le résultat de convergence.
-
2025
Bréhier Charles-Édouard, Dambrine Marc andet En-Nebbazi Nassim
[abstract][résumé]
We study a semi-implicit scheme which can be applied to minimize objective functions which are decomposed as the sum of a quadratic term and of a nonlinear function, perturbed by noise. We exhibit modified deterministic and stochastic modified equations which are employed to analyze the convergence of the algorithm in terms of strong and weak error estimates. We compare the results with those obtained for a standard explicit stochastic gradient optimization scheme.
Nous étudions un schéma semi-implicite pouvant être appliqué à la minimisation de fonctions objectifs décomposées en la somme d'un terme quadratique et d'une fonction non linéaire, perturbées par un bruit. Nous exhibons des équations modifiées déterministes et stochastiques, que nous utilisons pour analyser la convergence de l'algorithme à travers des estimations d'erreur forte et faible. Nous comparons les résultats à ceux obtenus pour un schéma standard explicite d'optimisation par gradient stochastique.
-
2025
Bréhier Charles-Édouard, Dambrine Marc andet En-Nebbazi Nassim
[abstract][résumé]
We consider a class of stochastic gradient optimization schemes. Assuming that the objective function is strongly convex, we prove weak error estimates which are uniform in time for the error between the solution of the numerical scheme, and the solutions of continuous-time modified (or high-resolution) differential equations at first and second orders, with respect to the time-step size. At first order, the modified equation is deterministic, whereas at second order the modified equation is stochastic and depends on a modified objective function. We go beyond existing results where the error estimates have been considered only on finite time intervals and were not uniform in time. This allows us to then provide a rigorous complexity analysis of the method in the large time and small time-step size regimes. We provide numerical experiments to illustrate the convergence results.
Nous considérons une classe de schémas d'optimisation par gradient stochastique. En supposant que la fonction objectif est fortement convexe, nous démontrons des estimations de l'erreur faible, uniformes en temps, entre la solution du schéma numérique et les solutions d'équations différentielles modifiées (ou à haute résolution) en temps continu aux ordres un et deux, par rapport au pas de temps. À l'ordre un, l'équation modifiée est déterministe, tandis qu'à l'ordre deux elle est stochastique et dépend d'une fonction objectif modifiée. Nous allons au-delà des résultats existants, dans lesquels les estimations d'erreur n'étaient considérées que sur des intervalles de temps finis et n'étaient pas uniformes en temps. Cela nous permet ensuite de fournir une analyse de complexité rigoureuse de la méthode dans les régimes de grand temps et de petit pas de temps. Nous présentons des expériences numériques illustrant les résultats de convergence.