Combler le fossé entre la descente de gradient stochastique à pas constant et les chaînes de Markov.

Résumé Nous considérons la minimisation d'une fonction objective en ayant accès à des estimations non biaisées de son gradient par la descente de gradient stochastique (SGD) avec une taille de pas constante. Bien que l'analyse détaillée n'ait été effectuée que pour des fonctions quadratiques, nous fournissons une expansion asymptotique explicite des moments des itérations SGD moyennées qui souligne la dépendance aux conditions initiales, l'effet du bruit et de la taille du pas, ainsi que l'absence de convergence dans le cas général (non quadratique). Pour cette analyse, nous introduisons des outils issus de la théorie des chaînes de Markov dans l'analyse du gradient stochastique. Nous montrons ensuite que l'extrapolation de Richardson-Romberg peut être utilisée pour se rapprocher de l'optimum global et nous montrons les améliorations empiriques du nouveau schéma d'extrapolation.