Skip to Main content Skip to Navigation
Theses

Bregman Gradient Methods for Relatively-Smooth Optimization

Radu-Alexandru Dragomir 1, 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : 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 de la condition de régularité relative, introduite en 2017 par Bauschke, Bolte et Teboulle. Depuis son apparition, cette condition a fait naître de nouvelles perspectives en optimisation du premier ordre. Tout d’abord, nous appliquons les méthodes de Bregman aux problèmes d’optimisation sur des espaces de matrices de rang faible. En exploitant la structure matricielle et en utilisant la propriété de régularité relative, nous proposons des noyaux de Bregman qui permettent d’améliorer la performance numérique par rapport aux méthodes euclidiennes. Ensuite, nous nous penchons sur la complexité théorique de ces algorithmes. Un des prob- lèmes les plus importants est de déterminer s’il existe une version accélérée de l’algorithme de gradient de Bregman qui possède un meilleur taux de convergence. Dans le cas général, nous démontrons que la réponse est négative : la complexité de la descente de gradient de Bregman standard ne peux pas être améliorée pour des noyaux génériques. La preuve repose sur un contre-exemple pathologique qui a été découvert au travers de méthodes d’analyses de pire cas par ordinateur. Nous évoquons aussi une tentative pour obtenir des résultats posi- tifs d’accélération en spécialisant cette analyse dans le contexte plus restreint de la géométrie entropique. Enfin, nous étudions la version stochastique de l’algorithme de Bregman pour minimiser des fonctions sous la forme d’espérance, ainsi que des méthodes de réduction de variance lorsque la fonction objectif est une somme finie.
Document type :
Theses
Complete list of metadata

https://hal.inria.fr/tel-03389344
Contributor : Radu-Alexandru Dragomir Connect in order to contact the contributor
Submitted on : Wednesday, October 20, 2021 - 11:40:31 PM
Last modification on : Wednesday, November 17, 2021 - 12:33:30 PM

File

these_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03389344, version 1

Citation

Radu-Alexandru Dragomir. Bregman Gradient Methods for Relatively-Smooth Optimization. Optimization and Control [math.OC]. UT1 Capitole, 2021. English. ⟨tel-03389344⟩

Share

Metrics

Record views

50

Files downloads

171