GOWER Robert

Nous étudions la descente de gradient stochastique (SGD) et la méthode de la boule lourde stochastique (SHB, également connue sous le nom de méthode du momentum) pour le problème général d'approximation stochastique. Pour la SGD, dans le cadre convexe et lisse, nous fournissons les premiers taux de convergence asymptotiques presque sûrs pour une moyenne pondérée des itérations. Plus précisément, nous montrons que le taux de convergence des valeurs de la fonction est arbitrairement proche de o(1/ √ k), et est exactement o(1/k) dans le cas dit surparamétré. Nous montrons que ces résultats sont toujours valables lorsque l'on utilise la recherche linéaire stochastique et les pas de Polyak stochastiques, ce qui constitue la première preuve de convergence de ces méthodes dans le régime non surparamétré. En utilisant une analyse sensiblement différente, nous montrons que ces taux sont également valables pour SHB, mais à la dernière itération. Cette distinction est importante car c'est la dernière itération de SGD et SHB qui est utilisée en pratique. Nous montrons également que la dernière itération de SHB converge vers un minimiseur presque sûrement. De plus, nous prouvons que les valeurs des fonctions de la HB déterministe convergent à un taux o(1/k), ce qui est plus rapide que le taux O(1/k) connu précédemment. Enfin, dans le cadre non convexe, nous prouvons des taux similaires sur la norme du gradient le plus faible le long de la trajectoire de SGD.

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.

Nous proposons un théorème général mais simple décrivant la convergence du SGD sous le paradigme de l'échantillonnage arbitraire. Notre théorème décrit la convergence d'un ensemble infini de variantes de SGD, chacune d'entre elles étant associée à une loi de probabilité spécifique régissant la règle de sélection des données utilisée pour former les minibatchs. C'est la première fois qu'une telle analyse est réalisée, et la plupart de nos variantes de SGD n'ont jamais été explicitement considérées dans la littérature auparavant. Notre analyse s'appuie sur la notion récemment introduite de régularité attendue et ne repose pas sur une limite uniforme de la variance des gradients stochastiques. En spécialisant notre théorème à différentes stratégies de mini-batching, telles que l'échantillonnage avec remplacement et l'échantillonnage indépendant, nous obtenons des expressions exactes pour le stepsize en fonction de la taille du mini-batch. Nous pouvons ainsi déterminer la taille du mini-lot qui optimise la complexité totale et montrer explicitement que la taille optimale du mini-lot augmente avec la variance du gradient stochastique évalué au minimum. Pour une variance nulle, la taille optimale du mini-lot est de un. De plus, nous prouvons des règles de changement de pas qui décrivent quand on doit passer d'un régime de pas constant à un régime de pas décroissant.

Nous présentons le premier algorithme randomisé accéléré pour la résolution de systèmes linéaires dans les espaces euclidiens. Un problème essentiel de ce type est le problème d'inversion de matrice. En particulier, notre algorithme peut être spécialisé pour inverser les matrices définies positives de telle sorte que tous les itérés (solutions approximatives) générés par l'algorithme sont eux-mêmes des matrices définies positives. Cela ouvre la voie à de nombreuses applications dans le domaine de l'optimisation et de l'apprentissage automatique. Comme application de notre théorie générale, nous développons les premières mises à jour quasi-Newton accélérées (déterministes et stochastiques). Nos mises à jour conduisent à des approximations plus agressives de l'inverse du Hessian, et permettent des gains de vitesse par rapport aux règles classiques non accélérées dans les expériences numériques. Des expériences de minimisation empirique du risque montrent que nos règles peuvent accélérer la formation de modèles d'apprentissage automatique.

Nous développons une méthode de Newton randomisée capable de résoudre des problèmes d'apprentissage avec des espaces de caractéristiques de très grande dimension, ce qui est un cadre commun dans des applications telles que l'imagerie médicale, la génomique et la sismologie. Notre méthode exploite l'esquisse ran-domisée d'une nouvelle manière, en trouvant la direction de Newton contrainte à l'espace couvert par une esquisse aléatoire. Nous développons une théorie de convergence linéaire globale simple qui s'applique à pratiquement toutes les techniques d'esquisse, ce qui donne aux praticiens la liberté de concevoir des approches d'esquisse personnalisées adaptées à des applications particulières. Nous réalisons des expériences numériques qui démontrent l'efficacité de notre méthode par rapport à la descente de gradient accélérée et à la méthode complète de Newton. Notre méthode peut être considérée comme un raffinement et une extension aléatoire des résultats de Karimireddy, Stich et Jaggi [18].

Nous développons la première méthode incrémentale stochastique pour calculer le pseu-doinverse de Moore-Penrose d'une matrice réelle. En tirant parti de trois caractérisations alternatives des matrices pseudo-inverse, nous concevons trois méthodes de calcul de la pseudo-inverse : deux méthodes générales et une méthode spécialisée dans les matrices symétriques. Il est prouvé que les deux méthodes générales convergent linéairement vers la pseudo-inverse de toute matrice donnée. Pour le calcul de la pseudo-inverse des matrices de rang complet, nous présentons deux autres méthodes spécialisées qui bénéficient d'un taux de convergence plus rapide que les méthodes générales. Nous indiquons également comment développer des méthodes aléatoires pour calculer des projections approximatives de l'espace des portées, un outil très nécessaire dans les méthodes inexactes de type Newton ou les solveurs quadratiques lorsque des contraintes linéaires sont présentes. Enfin, nous présentons des expériences numériques de nos méthodes générales de calcul des pseudo-inverses et montrons que nos méthodes surpassent largement la méthode de Newton-Schulz sur les matrices de grande dimension.