Vers la réduction du fossé entre la théorie et la pratique du SVRG.

Résumé Parmi les toutes premières méthodes stochastiques à variance réduite pour résoudre le problème de minimisation du risque empirique, on trouve la méthode SVRG [11]. SVRG est une méthode basée sur une boucle interne et externe, où dans la boucle externe un gradient complet de référence est évalué, après quoi m ∈ N étapes d'une boucle interne sont exécutées où le gradient de référence est utilisé pour construire une estimation à variance réduite du gradient actuel. La simplicité de la méthode SVRG et de son analyse a conduit à de multiples extensions et variantes pour l'optimisation même non convexe. Pourtant, il existe un écart important entre les paramètres suggérés par l'analyse et ce qui est connu pour fonctionner correctement dans la pratique. Notre première contribution est que nous prenons plusieurs mesures pour combler cet écart. En particulier, l'analyse actuelle montre que m devrait être de l'ordre du nombre de conditions pour que la méthode résultante ait une complexité favorable. Pourtant, dans la pratique, m = n fonctionne bien, quel que soit le nombre de conditions, où n est le nombre de points de données. En outre, l'analyse actuelle montre que les itérations internes doivent être réinitialisées en utilisant la moyenne après chaque boucle externe. Pourtant, en pratique, SVRG fonctionne mieux lorsque les itérations internes sont mises à jour en continu et ne sont pas réinitialisées. Nous fournissons une analyse de ces paramètres pratiques mentionnés ci-dessus et montrons qu'ils atteignent la même complexité favorable que l'analyse originale (avec des constantes légèrement meilleures). Notre deuxième contribution est de fournir une analyse plus générale que ce qui avait été fait précédemment en utilisant l'échantillonnage arbitraire, ce qui nous permet d'analyser pratiquement toutes les formes de mini-batching à travers un seul théorème. Puisque notre configuration et notre analyse reflètent ce qui se fait en pratique, nous sommes en mesure de fixer les paramètres tels que la taille du mini-batch et la taille du pas en utilisant notre théorie de manière à produire un algorithme plus efficace en pratique, comme nous le montrons dans des expériences numériques approfondies.