Des taux de convergence plus durs, meilleurs, plus rapides et plus forts pour la régression par les moindres carrés.

Résumé Nous considérons l'optimisation d'une fonction objectif quadratique dont les gradients ne sont accessibles qu'à travers un oracle stochastique qui renvoie le gradient à tout point donné plus une erreur aléatoire de variance finie de moyenne nulle. Nous présentons le premier algorithme qui atteint conjointement les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, à la fois en termes d'oubli des conditions initiales en O(1/n 2), et en termes de dépendance au bruit et à la dimension d du problème, en O(d/n). Notre nouvel algorithme est basé sur la descente de gradient régularisée accélérée moyenne, et peut également être analysé par des hypothèses plus fines sur les conditions initiales et la matrice hessienne, conduisant à des quantités sans dimension qui peuvent encore être petites alors que les termes " optimaux " ci-dessus sont grands. Afin de caractériser l'étanchéité de ces nouvelles limites, nous considérons une application à la régression non paramétrique et utilisons les limites inférieures connues de la performance statistique (sans limites de calcul), qui correspondent à nos limites obtenues à partir d'un seul passage sur les données et montrent ainsi l'optimalité de notre algorithme dans une grande variété de compromis particuliers entre le biais et la variance.