Stochastic First and Second Order Optimization Methods for Machine Learning

L'objectif principal de ce travail est de proposer des méthodes d'optimisation du premier et deuxième ordre pour le contexte spécifique de l'apprentissage automatique et l'optimisation à grande échelle. Notre point de départ est le travail de recherche de Tiphaine Bonniot de Ruisselet, avec Prof. Dominique Orban, à l'intersection de l'optimisation déterministe et stochastique sans contraintes. Pour la première partie de notre travail, nous exploitons les méthodes de région de confiance afin de pouvoir définir un pas d'optimisation adaptatif. Nous utilisons aussi une méthode d'échantillonage adaptatif afin de réduire la variance des estimations du gradient au cours de l'optimisation. Plus précisément, nous utilisons un test stochastique afin de marquer la transition entre les deux phases d'optimisation stochastique suivantes : • La première phase est une phase de convergence vers une région d'intérêt, où se trouve potentiellement un optimum local ou global. Nous souhaitons que cette phase soit la plus courte possible, mais aussi qu'elle mène à une région de convergence promet-teuse. Donc, durant cette phase, nous utilisons un pas d'optimisation adaptatif en nous basant sur une méthode stochastique de région de confiance, tandis que la taille d'échantillonage reste fixe. • La deuxième phase est une phase de convergence vers un optimum local ou global dans la région d'intérêt. Durant cette phase, nous choisissons de réduire la variance des estimations du gradient pour assurer une convergence rapide, mais nous utilisons un pas d'optimisation strictement décroissant pour assurer la convergence globale. Ainsi, nous arrivons non seulement à définir une démarche de passage du cas déterministe au cas stochastique pour ce type de méthodes, mais nous réussissons également à proposer un nouvel algorithme adaptatif dont les performances sont prometteuses. Quant aux méthodes de deuxième ordre, nous proposons une variante de l'algorithme BFGS stochastique tronqué à mémoire limitée. Nous développons une heuristique pour contrôler les valeurs propres de l'estimation de la matrice hessienne. Cela permet d'avoir une meilleure performance pour les problèmes où cette approximation devient mal-conditionnée au cours de l'optimisation. Nous proposons également de combiner cet algorithme avec une méthode de réduction de variance afin d'améliorer la qualité de l'estimation de courbature obtenue. Nous prouvons que notre algorithme converge vers un point stationnaire. De plus, nous montrons empiriquement que le contrôle des bornes sur les valeurs propres de l'approximation de la matrice hessienne rend l'algorithme plus stable et robuste face aux problèmes mal-conditionnés.