Optimisation Convexe: Algorithmes et Applications en Appréntissage
Calendrier, planning et modalités
6 séances de cours-TD, le 19 septembre, 3, 10, 17 octobre, 7 et
14 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 (sous-parcours "Statistique et
applis": 10/10, 17/10, 7/11, 14/11; sous-parcours "Science des
données": 19/10, 24/10, 21/11, 28/11).
Les TP sont assurés par Roland Denis et Frédéric Lagoutière.
Programme du cours et références
1) (séance du 19/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é. Discussion sans preuves sur
l'algorithme de sous-gradient et sur la convergence sans uniforme convexité.
Références :
essentiellement le livre de Ph. Ciarlet Introduction
à l'analyse numérique matricielle et à
l'optimisation, chapitre 8.
2) (séance du 3/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.
Méthodes proximales pour l'optimisation non-lisse.
Opérateur proximal. Algorithme du gradient proximal pour min
f+g, dans le cas f elliptique ou juste lisse. Méthodes ISTA et FISTA.
Références Surtout
l'article
original de Beck et Teboulle sur la méthode FISTA.
3) (séance du 10/10)
Analyse convexe et dualité convexe
Définition de la transformée de
Fenchel-Legendre. f**=f. Liens avec
sous-différentiel et opérateurs
proximaux. Dualité.
Références Voir ces notes d'analyse convexe. Attention :
elles sont tirées d'un livre (en préparation) plus
vaste, sont écrites en considérant éventuellement
des espaces de dimension infinie, et contiennent des résultats
qu'on n'a pas développés. Une autre
référence possible, en dimension finie, est le livre de
R. T. Rockafellar Convex Analysis.
TD
Exos 1-3 de la feuille de
TD.
4) (séance du 17/10)
Algorithmes basés sur la dualité
Uzawa pour les contraintes d'égalités linéaires,
inégalités linéaires, inégalités
convexes. Lagrangien augmenté. Convergence d'Uzawa avec
contraintes déinégalités linéaires.
Références :
essentiellement le livre de Ph. Ciarlet Introduction
à l'analyse numérique matricielle et à
l'optimisation, chapitre 9.
TD
Exos 4-6 de la feuille de
TD.
5) (séance du 7/11)
Optimisation stochastique et algorithme de gradient
stochastique
Minimisation d'une espérance. Principe et preuve de convergence
de l'algorithme de gradient stoschastique pour une fonction lisse et
fortement convexe. Exemples d'applications. quelques mots sur
l'importance sampling.
Références Une preuve de la convergence de l'algo
de gradient stochastique très très
proche de celle faite en classe est disponible ici.
TD
Exos 7-10 de la feuille de
TD.
6) (séance du 14/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; minimisation d'une loss function.
Références (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)
: le livre récent de G. Carlier Classical and Modern
Optimization. Regarder aussi les sections 2.2.1 et 2.2.2 du livre
Learning Theory
from First Principles de F. Bach.
TD
Exos 11-13 de la feuille de
TD.
Annales
Malheureusement celle-ci est la première année que ce
cours est 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.