De la moyenne à l'accélération, il n'y a qu'un pas.

Résumé Nous montrons que la descente de gradient accélérée, la descente de gradient moyennée et la méthode de la boule lourde pour les problèmes non fortement convexes peuvent être reformulées comme des algorithmes d'équation aux différences du second ordre à paramètres constants, où la stabilité du système est équivalente à la convergence à un taux O(1/n 2), où n est le nombre d'itérations. Nous fournissons une analyse détaillée des valeurs propres du système dynamique linéaire correspondant, montrant divers comportements oscillatoires et non-oscillatoires, ainsi qu'un résultat de stabilité net avec des constantes explicites. Nous considérons également la situation où des gradients bruyants sont disponibles, où nous étendons notre résultat de convergence général, ce qui suggère un algorithme alternatif (c'est-à-dire avec différentes tailles de pas) qui présente les bons aspects de la moyenne et de l'accélération.