Le, Tam (2023) Calcul non-lisse et optimisation pour l'apprentissage automatique : échantillonnage au premier ordre et différentiation implicite. École doctorale Mathématiques, Informatique et Télécommunications (Toulouse).

Preview

Text Download (2MB) | Preview

Abstract

Les problèmes d'apprentissage automatique se formulent souvent comme une minimisation de risques présentant de la non-lissité et de la non-convexité. Des sources importantes de non-lissité sont l'utilisation privilégiée d'instructions conditionnelles et la présence de problèmes de sous-niveau.Les méthodes stochastiques du premier ordre sont largement utilisées pour aborder ces problèmes en raison de leur simplicité et de leur scalabilité, ce qui en fait un choix attrayant pour les applications à grande échelle. Bien que les notions classiques de dérivées pour les fonctions non-lisses soient difficilement applicables dans de tels contextes, nous observons une tendance générale consistant à remplacer les dérivées classiques par l'algorithme de rétropropagation. Un modèle récemment introduit de dérivées appelé "gradients conservatifs" fournit une justification à une telle pratique en étendant les règles simples du calcul aux fonctions non-lisses, telles que la règle de chaîne ou la somme.Nous proposons deux extensions du calcul conservatif qui trouvent un large éventail d'applications dans l'apprentissage automatique. Un premier résultat répond à la question de l'interversion de la dérivation et de l'intégrale, ce qui permet de justifier l'échantillonnage du premier ordre dans un cadre non-lisse et non-convexe. Un deuxième résultat est une formule de différentiation implicite non-lisse afin de justifier les approches du premier ordre pour les problèmes bi-niveaux non-lisses, tels que l'optimisation des hyperparamètres et l'entraînement de couches implicites dans l'apprentissage profond.Nous utilisons ce calcul afin de mettre en place un cadre général stochastique non-lisse compatible avec les implémentations pratiques. Une règle de chaîne fondamentale le long des courbes permet d'appliquer des méthodes d'ODE non-lisses afin de démontrer la convergence de la méthode du sous-gradient stochastique et de sa version avec balle lourde. Certains résultats d'intégration de fonctions définissables sont explorés afin de garantir une propriété de Sard pour des distributions continues. En tant que modèle fidèle à la pratique, l'approche des gradients conservatifs conduit à une convergence vers un ensemble critique qui peut dépendre du calcul et conduire à des points limites absurdes. Pour la méthode du sous-gradient stochastique et sa version boule pesante, nous montrons que ces artefacts de calcul sont évités en randomisant l'initialisation, ce qui conduit à la convergence vers des points critiques classiques.

Machine learning problems often formulate as a risk minimization exhibiting nonsmoothness and nonconvexity. Important sources of nonsmoothness are the privileged use of conditional statements and the presence of sublevel problems.Stochastic first-order methods are widely employed to address these problems due to their simplicity and scalability, making them an attractive choice for large-scale applications. While classical notions of derivatives for nonsmooth functions are hardly implementable in such contexts, we see a general trend consisting in replacing classical derivatives with the backpropagation algorithm. A recently introduced model of derivatives called conservative gradients provides a justification for such a practice by extending simple calculus rules to nonsmooth functions, such as the chain rule or the sum.We propose two extensions of the conservative calculus finding a wide range of applications in machine learning. A first result answers the question of interchanging derivative and integral allowing to justify first-order sampling in a nonsmooth and nonconvex setting. A second result is a nonsmooth implicit differentiation formula in order to justify first-order approaches to nonsmooth bi-level problems, e.g. hyperparameter optimization, and the training of implicit layers in deep learning.We make use of this calculus in order to set up a general nonsmooth stochastic setting that is compatible with practical implementations. A fundamental chain rule along curves allows to apply nonsmooth ODE methods in order to show the convergence of the stochastic subgradient method and its heavy ball version. Some integration results of definable functions are explored in order to ensure a Sard property for continuous distributions.As a faithful model of practice, the conservative gradient approach yields convergence to a critical set which may depend on the calculus and lead to absurd limit points. For the stochastic subgradient method and its heavy ball version, we show that these calculus artifacts are avoided when randomizing the initialization, leading to the convergence to classical critical points.