Optimisation Convexe: Algorithmes et Applications en Appréntissage
Calendrier, planning et modalités
6 séances de cours-TD, le 18 septembre, 2, 9, 16 octobre, 6 et
10 novembre. Chaque séance a lieu de
14h à 17h15 (voir ADE pour les salles précises à
chaque fois).
4 séances de TP par groupe.
Les TP sont assurés par Roland Denis et Frédéric Lagoutière.
Programme du cours et références
Lors des séances marquées par un astérisque
le début se fera à 14h pile, la pause sera
légèrement écourtée, et on finira qqs
minutes avant.
1) (séance du 18/9)
Introduction à
l'optimisation et à ses applications en apprentissage.
Exemples de problèmes d'optimisation. Rappels sur l'existence
des minimiseurs et leur unicité.
Algorithmes de gradient dans le cas lisse et uniformément convexe.
Algorithme de gradient à pas fixe pour la minimisation sans
contraintes. Minimisation convexe sous contraintes,
projection. Gradient projeté.
2) (séance du 2/10*)
Gradient et gradient
accéléré pour l'optimisation lisse.
Ordre de convergence 1/k; ordre 1/k2 pour le gradient
accéléré de Nesterov.
Optimisation non-lisse.
Sous-différentiel et algorithme du sous-gradient.
Opérateur proximal. Algorithme du gradient proximal pour min
f+g, dans le cas f elliptique ou juste lisse. Méthodes ISTA et FISTA.
3) (séance du 9/10*)
Analyse convexe et dualité convexe
Définition de la transformée de
Fenchel-Legendre. f**=f. Lien avec le
sous-différentiel. Dualité.
TD
Exos 1-3 de la feuille de
TD.
4) (séance du 16/10)
Encoure dualité et algorithmes basés sur la dualité
TD
Exos 4-6 de la feuille de
TD.
5) (séance du 6/11*)
Algorithme de gradient stochastique
Principe et preuve de convergence
de l'algorithme de gradient stochastique pour une fonction convexe ou elliptique. Exemples d'applications. quelques mots sur
l'importance sampling.
TD
Exos 7-9 de la feuille de
TD. L'exo 12 a été résolu en CM.
6) (séance du 10/11)
Compléments
Exemples de problèmes d'optimisation convexe en apprentissage:
séparation linéaire de nuages de points;
résolution sparse d'un système linéaire par
minimisation de la norme 1.
TD
Exos 10, 11, 13 de la feuille de
TD.
Exercices et Annales
Feuille de TD: ici.
Voir ici le sujet de l'examen écrit de l'an dernier.
C'était la première année que ce
cours était enseigné tel quel. Cependant, d'autres cours
donnés par le passé à Orsay avaient un programme
similaire. Regarder par exemple le cours Optimisation convexe (M2
MathSV), et notamment l'examen de 2015 ou son rattrapage, ou celui de
2016 ou son rattrapage.
Sujet de l'examen du 11/12/23 ; ici
une version avec corrigé.
Références
Un poly informel sur le contenu du cours: voir ici ( en anglais).
Sinon vous pouvez consulter le livre de Ph. Ciarlet Introduction
à l'analyse numérique matricielle et à
l'optimisation, chapitre 8 et l'article
original de Beck et Teboulle sur la méthode FISTA; le livre récent de G. Carlier Classical and Modern
Optimization (en général pour
l'optimisation, y compris les bases de calcul
différentiel mais également les applications en sciences
de données au chapitre When optimization and data meet).