Steepest descent as Linear Quadratic Regulation

Abstract

Concorder un modèle à certaines observations, voilà qui résume assez bien ce que l’apprentissage machine cherche à accomplir. Ce concept est maintenant omniprésent dans nos vies, entre autre grâce aux percées récentes en apprentissage profond. La stratégie d’optimisation prédominante pour ces deux domaines est la minimisation d’un objectif donné. Et pour cela, la méthode du gradient, méthode de premier-ordre qui modifie les paramètres du modèle à chaque itération, est l’approche dominante. À l’opposé, les méthodes dites de second ordre n’ont jamais réussi à s’imposer en apprentissage profond. Pourtant, elles offrent des avantages reconnus qui soulèvent encore un grand intérêt. D’où l’importance de la méthode du col, qui unifie les méthodes de premier et second ordre sous un même paradigme.

Dans ce mémoire, nous établissons un parralèle direct entre la méthode du col et le domaine du contrôle optimal ; domaine qui cherche à optimiser mathématiquement une séquence de décisions. Et certains des problèmes les mieux compris et étudiés en contrôle optimal sont les commandes linéaires quadratiques. Problèmes pour lesquels on connaît très bien la solution optimale. Plus spécifiquement, nous démontrerons l’équivalence entre une itération de la méthode du col et la résolution d’une Commande Linéaire Quadratique (CLQ).

Cet éclairage nouveau implique une approche unifiée quand vient le temps de déployer nombre d’algorithmes issus de la méthode du col, tel que la méthode du gradient et celle des gradients naturels, sans être limitée à ceux-ci. Approche que nous étendons ensuite aux problèmes à horizon infini, tel que les modèles à équilibre profond. Ce faisant, nous démontrons pour ces problèmes que calculer les gradients via la différentiation implicite revient à employer l’équation de Riccati pour solutionner la CLQ associée à la méthode du gradient. Finalement, notons que l’incorporation d’information sur la courbure du problème revient généralement à rencontrer une inversion matricielle dans la méthode du col. Nous montrons que l’équivalence avec les CLQ permet de contourner cette inversion en utilisant une approximation issue des séries de Neumann. Surprenamment, certaines observations empiriques suggèrent que cette approximation aide aussi à stabiliser le processus d’optimisation quand des méthodes de second-ordre sont impliquées ; en agissant comme un régularisateur adaptif implicite.

Machine learning entails training a model to fit some given observations, and recent advances in the field, particularly in deep learning, have made it omnipresent in our lives. Fitting a model usually requires the minimization of a given objective. When it comes to deep learning, first-order methods like gradient descent have become a default tool for optimization in deep learning. On the other hand, second-order methods did not see widespread use in deep learning. Yet, they hold many promises and are still a very active field of research. An important perspective into both methods is steepest descent, which allows you to encompass first and second-order approaches into the same framework. In this thesis, we establish an explicit connection between steepest descent and optimal control, a field that tries to optimize sequential decision-making processes. Core to it is the family of problems known as Linear Quadratic Regulation; problems that have been well studied and for which we know optimal solutions. More specifically, we show that performing one iteration of steepest descent is equivalent to solving a Linear Quadratic Regulator (LQR). This perspective gives us a convenient and unified framework for deploying a wide range of steepest descent algorithms, such as gradient descent and natural gradient descent, but certainly not limited to. This framework can also be extended to problems with an infinite horizon, such as deep equilibrium models. Doing so reveals that retrieving the gradient via implicit differentiation is equivalent to recovering it via Riccati’s solution to the LQR associated with gradient descent. Finally, incorporating curvature information into steepest descent usually takes the form of a matrix inversion. However, casting a steepest descent step as a LQR also hints toward a trick that allows to sidestep this inversion, by leveraging Neumann’s series approximation. Empirical observations provide evidence that this approximation actually helps to stabilize the training process, by acting as an adaptive damping parameter.