Approximation stochastique lisse non fortement convexe avec un taux de convergence O(1/n).

Résumé Nous considérons le problème d'approximation stochastique où une fonction convexe doit être minimisée, en ne connaissant que des estimations non biaisées de ses gradients en certains points, un cadre qui inclut des méthodes d'apprentissage automatique basées sur la minimisation du risque empirique. Nous nous concentrons sur les problèmes sans forte convexité, pour lesquels tous les algorithmes connus précédemment atteignent un taux de convergence pour les valeurs de la fonction de O(1/n^{1/2}). Nous considérons et analysons deux algorithmes qui atteignent un taux de O(1/n) pour les problèmes classiques d'apprentissage supervisé. Pour la régression des moindres carrés, nous montrons que la descente de gradient stochastique moyennée avec une taille de pas constante atteint le taux souhaité. Pour la régression logistique, cela est obtenu par un nouvel algorithme de gradient stochastique simple qui (a) construit des approximations quadratiques locales successives des fonctions de perte, tout en (b) préservant la même complexité de temps d'exécution que la descente de gradient stochastique. Pour ces algorithmes, nous fournissons une analyse non asymptotique de l'erreur de généralisation (en espérance, et aussi en haute probabilité pour les moindres carrés), et nous effectuons des expériences approfondies sur des repères standards d'apprentissage automatique montrant qu'ils surpassent souvent les approches existantes.