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.

Abstract

In this work, we explore promising research directions to improve upon existing first-, and second-order optimization algorithms in both deterministic and stochastic settings. Our starting point is the work developed by Tiphaine Bonniot de Ruisselet and Prof. Dominique Orban at the intersection of unconstrained deterministic and stochastic optimization. As for first-order optimization methods, we first define a framework to transform a semi-deterministic trust-region method, that takes exact function values and inexact gradient estimates, to a fully stochastic optimization algorithm that is adapted to the context of machine learning. Then, we go a step further to propose a novel first-order optimization algorithm that exploits the two-phase nature of stochastic optimization. The first phase is a global convergence phase. We would like to speed up the algorithm during this phase and converge to a region of interest that contains a good local or global optimum, while allowing some noise in the estimates which helps to explore the optimization landscape. Therefore, we propose to use a trust-region method during this phase to define the step size adaptively, allowing it to grow and shrink as needed. In the second phase, the objective is to converge to a specific optimum in the region of interest identified in the first phase. During this phase, we need to reduce the variance of the updates in order to improve their quality and converge fast. Hence, we propose to use adaptive sampling with a strictly decreasing step size in order to guarantee the overall convergence. Our work enables us to define a generic framework for adapting trust-region methods to the stochastic setting. We also demonstrate that our algorithm is competitive for machine learning problems. For second-order methods, we propose a new version of a stochastic damped L-BFGS method that is more robust on ill-conditioned problems. First, we prove that the eigenvalues of the Hessian approximation are bounded, using a less restrictive assumption compared to related works. Then we harness the potential of using these bounds to control the quality of the Hessian approximation. We prove that our algorithm has appealing theoretical properties, as it converges almost surely to a stationary point. We also demonstrate that it is more robust than a previously proposed stochastic damped L-BFGS algorithm in the highly non-convex case that charac-terizes problems in deep learning.