École Nationale Supérieure de
Techniques Avancées

Résumé

Dans ce rapport, nous donnons des formules simples de la taille de minibatch optimale pour le célèbre algorithme de gradient stochastic moyenné (SAGA). Notre approche consiste à trouver la taille de minibatch qui minimise la complexité totale de l’algorithme SAGA. Cette dernière est définie comme étant le produit du nombre d’itérations par le nombre d’opérations effectuées par itération. Ces résultats de complexité sont tiré d’un récent travail de Gower, Richtárik et Bach (2018) ayant introduit l’objet au cœur de ce rapport : la constante de lissage moyenne. Cette constante, caractéristique du problème d’optimisation considéré, contrôle le nombre d’itérations de plusieurs méthodes de descente de gradient stochastique à variance réduite. Afin d’obtenir une formule analytique du minibatch optimal, nous commençons par élaborer des bornes supérieurs de la constante de lissage moyenne pour l’algorithme SAGA et un tirage sans remplacement. Pour ce faire, nous passons par des calculs directs ou utilisons des résultats sur les inégalités de concentration de matrices. Ensuite, nous réemployons ces bornes supérieurs dans les résultats de complexité, obtenant ainsi une sorte de complexité pessimiste, avant de trouver l’argument de son minimum : notre estimation du minibatch optimal.