Taux de convergence presque sûrs pour la descente de gradient stochastique et la boule lourde stochastique.

Résumé Nous étudions la descente de gradient stochastique (SGD) et la méthode de la boule lourde stochastique (SHB, également connue sous le nom de méthode du momentum) pour le problème général d'approximation stochastique. Pour la SGD, dans le cadre convexe et lisse, nous fournissons les premiers taux de convergence asymptotiques presque sûrs pour une moyenne pondérée des itérations. Plus précisément, nous montrons que le taux de convergence des valeurs de la fonction est arbitrairement proche de o(1/ √ k), et est exactement o(1/k) dans le cas dit surparamétré. Nous montrons que ces résultats sont toujours valables lorsque l'on utilise la recherche linéaire stochastique et les pas de Polyak stochastiques, ce qui constitue la première preuve de convergence de ces méthodes dans le régime non surparamétré. En utilisant une analyse sensiblement différente, nous montrons que ces taux sont également valables pour SHB, mais à la dernière itération. Cette distinction est importante car c'est la dernière itération de SGD et SHB qui est utilisée en pratique. Nous montrons également que la dernière itération de SHB converge vers un minimiseur presque sûrement. De plus, nous prouvons que les valeurs des fonctions de la HB déterministe convergent à un taux o(1/k), ce qui est plus rapide que le taux O(1/k) connu précédemment. Enfin, dans le cadre non convexe, nous prouvons des taux similaires sur la norme du gradient le plus faible le long de la trajectoire de SGD.