Gazagnadou, Nidham
[VerfasserIn]
;
Institut polytechnique de Paris
[MitwirkendeR];
Salmon, Joseph
[MitwirkendeR]
Expected smoothness for stochastic variance-reduced methods and sketch-and-project methods for structured linear systems ; Régularité moyenne pour les méthodes stochastiques à variance réduite et méthodes sketch-and-project pour systèmes linéaires structurés
Titel:
Expected smoothness for stochastic variance-reduced methods and sketch-and-project methods for structured linear systems ; Régularité moyenne pour les méthodes stochastiques à variance réduite et méthodes sketch-and-project pour systèmes linéaires structurés
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
L'augmentation considérable du volume de données ainsi que de la taille des échantillons complexifie la phase d'optimisation des algorithmes d'apprentissage, nécessitant la minimisation d'une fonction de perte. La descente de gradient stochastique (SGD) et ses variantes à réduction de variance (SAGA, SVRG, MISO) sont largement utilisées pour résoudre ces problèmes. En pratique, ces méthodes sont accélérées en calculant des gradients stochastiques sur un "mini-batch" : un petit groupe d'échantillons tiré aléatoirement. En effet, les récentes améliorations technologiques permettant la parallélisation de ces calculs ont généralisé l'utilisation des mini-batchs.Dans cette thèse, nous nous intéressons à l'étude d'algorithmes du gradient stochastique à variance réduite en essayant d'en trouver les hyperparamètres optimaux: taille du pas et du mini-batch. Cette étude nous permet de donner des résultats de convergence interpolant entre celui des méthodes stochastiques tirant un seul échantillon par itération et la descente de gradient dite "full-batch" utilisant l'ensemble des échantillons disponibles à chaque itération. Notre analyse se base sur la constante de régularité moyenne, outil fondamental de notre analyse, qui permet de mesurer la régularité de la fonction aléatoire dont le gradient est calculé.Nous étudions un autre type d'algorithmes d'optimisation : les méthodes "sketch-and-project". Ces dernières peuvent être utilisées lorsque le problème d'apprentissage est équivalent à la résolution d'un système linéaire. C'est par exemple le cas des moindres carrés ou de la régression ridge. Nous analysons ici des variantes de cette méthode qui utilisent différentes stratégies de momentum et d'accélération. L'efficacité de ces méthodes dépend de la stratégie de "sketching" utilisée pour compresser l'information du système à résoudre, et ce, à chaque itération. Enfin, nous montrons que ces méthodes peuvent aussi être étendues à d'autres problèmes d'analyse numérique. En effet, l'extension des méthodes de ...