Optimalité statistique de la descente de gradient stochastique sur des problèmes d'apprentissage difficiles grâce à des passages multiples.

Résumé Nous considérons la descente de gradient stochastique (SGD) pour la régression des moindres carrés avec potentiellement plusieurs passages sur les données. Alors qu'il a été largement démontré que plusieurs passages sont pratiquement plus performants en termes de prédiction sur des données non vues, l'analyse théorique existante de la SGD suggère qu'un seul passage est statistiquement optimal. Bien que cela soit vrai pour les problèmes faciles de faible dimension, nous montrons que pour les problèmes difficiles, plusieurs passages conduisent à des prédictions statistiquement optimales alors qu'un seul passage ne le fait pas. Nous montrons également que dans ces modèles difficiles, le nombre optimal de passages sur les données augmente avec la taille de l'échantillon. Afin de définir la notion de dureté et de montrer que nos performances prédictives sont optimales, nous considérons des modèles potentiellement de dimension infinie et des notions typiquement associées aux méthodes à noyau, à savoir la décroissance des valeurs propres de la matrice de covariance des caractéristiques et la complexité du prédicteur optimal telle que mesurée par la matrice de covariance. Nous illustrons nos résultats sur des expériences synthétiques avec des méthodes à noyau non linéaires et sur un benchmark classique avec un modèle linéaire.