Exploiting the Partially-Separable Structure in Quasi-Newton Methods for Unconstrained Optimization and Deep Learning

Cette thèse explore l’utilisation de la structure partiellement-séparable pour l’optimisation continue sans contrainte, en particulier pour les méthodes quasi-Newton et l’entraînement de réseaux de neurones. Une fonction partiellement-séparable est la somme de fonctions éléments, chacune de dimension inférieure à celle du problème total. Le Hessien peut être agrégé en approximant séparément le Hessien de chaque fonction élément avec une matrice dense. Cela préserve la structure creuse du Hessien, contrairement aux méthodes quasi-Newton à mémoire limitée. En pratique, ces méthodes nécessitent moins d’itérations qu’une méthode quasi-Newton à mémoire limitée et peuvent être parallélisées en distribuant les calculs liés aux fonctions éléments. Cependant, la revue de littérature de la thèse révèle certaines limites lorsque la dimension des fonctions éléments est grande. De plus, le seul logiciel d’optimisation libre exploitant la structure partiellement-séparable est inutilisable pour les utilisateurs inexpérimentés sans l’utilisation d’un langage de modélisation commercial. Dans cette thèse, des solutions sont proposées pour remédier à ces lacunes, ainsi qu’une application des concepts d’optimisation partiellement-séparable à l’apprentissage supervisé d’un réseau de neurones. La première contribution est une suite logicielle libre basée sur une détection automatique de la structure partiellement-séparable d’un problème, c’est-à-dire qu’elle retrouve chaque fonction élément de dimension réduite. Elle alloue des structures de données partitionnées nécessaires pour stocker les dérivées (approximées) et définit des méthodes d’optimisation quasi-Newton (à mémoire limitée) partitionnées. L’ensemble de la suite est intégré à l’écosystème JuliaSmoothOptimizers, qui rassemble de nombreux outils pour l’optimisation continue, notamment des algorithmes d’optimisation qui peuvent exploiter la séparabilité partielle détectée. Dans la deuxième contribution, l’approximation d’un Hessien élément par une matrice dense est remplacée par un opérateur linéaire quasi-Newton à mémoire limitée. Par conséquent, le coût en mémoire pour stocker et effectuer un produit entre l’approximation du Hessien et un vecteur n’est plus quadratiquement lié à la dimension des fonctions éléments. Une telle approximation partitionnée à mémoire limitée est alors applicable lorsque les fonctions éléments sont grandes, contrairement à une approximation partitionnée dense. La norme de chaque nouvel opérateur quasi-Newton partitionné à mémoire limitée peut être bornée, garantissant que sa méthode de région de confiance relative converge. De plus, les résultats numériques montrent que ces méthodes surpassent les méthodes quasi-Newton partitionnées ou à mémoire limitée lorsque les fonctions éléments sont larges. La dernière contribution examine l’exploitation de la structure partiellement-séparable dans l’entraînement supervisé d’un réseau de neurones. En général, le problème d’optimisation associé à l’entraînement n’est pas partiellement-séparable. Par conséquent, une fonction de perte partiellement-séparable et une architecture de réseau de neurones partitionnée sont introduites pour rendre l’entraînement partiellement-séparable. Les résultats numériques montrent qu’une combinaison de ces deux contributions est compétitive avec les architectures et fonctions de perte usuelles. L’entraînement de cette combinaison peut être réalisé en parallèle, de manière complémentaire aux techniques d’apprentissage supervisé parallèles existantes. Plus spécifiquement, les calculs de chaque fonction de perte élément peuvent être distribués à un travailleur qui opère uniquement sur un fragment du réseau de neurones. Le problème d’entraînement partiellement-séparable possède des larges éléments pour lesquels un entraînement quasi-Newton partitionné à mémoire limitée est proposé. Cet entraînement est empiriquement montré comme compétitif avec les méthodes d’entraînement de l’état de l’art et légèrement inférieur à Adam.

Abstract

This thesis investigates the use of the partially-separable structure for continuous unconstrained optimization, in particular for quasi-Newton methods and neural network training. A partially-separable function is the sum of element functions, each of lower dimension than the total problem. The Hessian can be aggregated by separately approximating the Hessian of each element function with a dense matrix. This preserves the sparsity pattern of the Hessian, in contrast to limited-memory quasi-Newton methods. In practice, these methods require fewer iterations than a limited-memory quasi-Newton method and can be parallelized by distributing the computations related to the element functions. However, the literature review of the thesis reveals some limitations, particularly when the dimension of the element functions is large. Additionally, the only open-source optimization software exploiting the partially-separable structure is unusable for inexperienced users without using a commercial modelling language. In this thesis, solutions are proposed to address these shortcomings, along with an application of partially-separable optimization concepts to supervised learning of a neural network. The first contribution is an open source software suite based on an automatic detection of the partially-separable structure of a problem, i.e., retrieves each reduced-dimensional element function. It allocates partitioned data structures necessary for storing (approximated) derivatives and defines (limited-memory) partitioned quasi-Newton optimization methods. The entire suite is integrated into the JuliaSmoothOptimizers ecosystem, which gathers numerous tools for continuous optimization, including optimization algorithms that can exploit the detected partial separability. In the second contribution, the approximation of an element Hessian by a dense matrix is replaced with a limited-memory quasi-Newton linear operator. As a result, the memory cost for storing and performing a Hessian-approximation vector product is no longer quadratically related to the dimension of the element functions. Such a limited-memory partitioned approximation is then applicable when the element functions are large, conversely to a dense partitioned approximation. The norm of each new limited-memory partitioned quasi-Newton operator can be bounded, ensuring that its relative trust-region method converges. Additionally, numerical results show that these methods outperform partitioned or limitedmemory quasi-Newton methods when the elements are large. The final contribution examines the exploitation of the partially-separable structure in the supervised training of a neural network. In general, the optimization problem associated with training is not partially-separable. Therefore, a partially-separable loss function and a partitioned network architecture are introduced to make the training partially-separable. Numerical results show that a combination of these two contributions is competitive with state-of-the-art architectures and loss functions. The training of this combination can be carried out in parallel, complementarily to existing parallel supervised learning techniques. More specifically, the calculations of each element loss function can be distributed to a worker who only needs to operate a fragment of the neural network. The partially-separable training problem possesses large elements for which a limited-memory partitioned quasi-Newton training is proposed. This training is empirically shown to be competitive with state-of-the-art training methods and slightly inferior to Adam.