Lecturer: | G. Garrigos |
Period: |
Term 1 |
ECTS: | 3 |
Schedule | 20h |
Fonction convexe. Sous-différentielle d'une fonction convexe. Conditions d'optimalité.
## Compétences visées
- Comprendre les algorithmes d’optimisation pour l’entrainement d’algorithmes d’apprentissage.
- Connaitre les propriétés de convergence de ces algorithmes.
- Savoir les mettre en oeuvre numériquement.
## Programme
1. Méthodes déterministes pour la minimisation d'une fonction
+ Algorithme du gradient. Cas convexe, fortement convexe, non-convexe. Convergence et vitesses.
+ Algorithme proximal et gradient-proximal. Convergence et vitesses. Exemple: apprentissage de dictionnaire.
+ Méthodes inertielles. Vitesse de convergence optimale.
1. Méthodes incrémentales et stochastiques pour la minimisation d'une somme de fonctions
+ Résolution de systèmes linéaires de grande taille. Rappels sur les méthodes déterministes (gradient conjugué, quasi-Newton). Algorithme de Kaczmarz.
+ Algorithme du gradient incrémental/stochastique. Etude de la convergence. Propriété de régularisation itérative.
+ Algorithmes stochastiques à variance réduite. Vitesse de convergence optimale.
1. Problèmes de point-selle. Liens avec les problèmes génératifs. Difficultés et résolution dans le cas monotone.
## Références
- Borwein, J.M. & Lewis, A.S. (2006).Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer.
- Nesterov Y. (2004). Introductory lectures on convex optimization. Springer.
- Peypouquet P. (2016). Convex Optimization in Normed Spaces. Springer