En apprentissage statistique et traitement du signal, de nombreuses tâches se formulent sous la forme d'un problème d'optimisation de grande taille. Dans ce contexte, les méthodes du premier ordre, qui utilisent uniquement l'information apportée par le gradient de la fonction objectif, sont privilégiées en raison de leur faible coup par itération et de leur simplicité. Nous étudions dans cette thèse les méthodes du premier ordre à distance de Bregman, qui constituent une généralisation de la célèbre méthode de descente de gradient. Cette généralisation consiste à remplacer la distance euclidienne par une distance plus générale, dite de Bregman, générée par une fonction convexe noyau suffisamment simple. La fonction noyau est choisie de manière à être adaptée à la géométrie de la fonction objectif, au travers d'une condition de régularité relative, introduite récemment par Bauschke, Bolte et Teboulle (2017).
Tout d'abord, nous appliquons les méthodes de Bregman aux problèmes d'optimisation portant sur des matrices à rang faible. Cette classe de problèmes dispose d'importantes applications en apprentissage non supervisé et en traitement du signal. Nous montrons comment plusieurs types de noyaux de Bregman peuvent être utilisés pour améliorer l'efficacité des méthodes d'optimisation à rang faible.
Ensuite, nous nous focalisons sur l'étude théorique de la complexité des méthodes de Bregman. Nous utilisons un procédé permettant d'obtenir de manière automatique les garanties de complexité des algorithmes de gradient. Cette méthode, appelée problème d'estimation de performance, a été initialement proposée par Drori et Teboulle (2014) dans le contexte des algorithms de gradient euclidiens. Nous étendons cet outil aux algorithmes de type Bregman afin d'en étudier la complexité.
En utilisant les problèmes d'estimation de performance, nous établissons une borne inférieure sur la performance de tout algorithme utilisant des distances de Bregman sur des problèmes vérifiant la condition de régularité relative. Ce résultat montre que, dans le pire cas, l'algorithme de Bregman standard est optimal sur cette classe de problèmes, et qu'il ne peut donc pas être accéléré.
Nous spécialisons par la suite les problèmes d'estimation de performance aux fonctions à géométrie entropique, et étudions les garanties de pire cas des algorithmes de Bregman dans ce contexte.
Enfin, nous étudions les versions stochastiques des algorithmes de Bregman, dont une version utilisant des techniques de réduction de variance afin d'optimiser des fonctions à somme finie.
|
We study large-scale optimization problems with applications to signal processing and machine learning. Such problems are typically solved with first-order methods that perform iterative updates using the gradient of the objective function. We focus on the class of Bregman first-order methods, for which the direction of the gradient step is determined by the Bregman divergence induced by a convex kernel function. The choice of the kernel is guided by the relative smoothness condition, which requires the kernel to be compatible with the objective through a descent inequality. This condition was introduced recently by Bauschke, Bolte and Teboulle in 2017 and has opened new perspectives in first-order optimization.
In the first part, we apply Bregman methods to minimization problems on the space of low-rank semidefinite matrices. By leveraging the matrix structure and using the relative smoothness property, we show that well-chosen Bregman kernels allow to improve performance over standard Euclidean methods.
Then, we study the theoretical complexity of these algorithms. An important question is to determine whether there exists an accelerated version of Bregman gradient descent which achieves a better convergence rate in the same setting. In the general case, we show that the answer is negative as the complexity of the standard Bregman gradient method cannot be improved for generic kernels. The proof relies on a pathological example which was discovered by analyzing the worst-case behavior of Bregman methods with a computer-aided technique called performance estimation. We also detail an attempt towards improving the convergence speed in a more restricted setting, by specializing the performance estimation framework to the entropic geometry.
Finally, we study a stochastic variant of Bregman gradient descent for expectation minimization problems, which are pervasive in machine learning, along with variance reduction methods for finite-sum objectives. |