Master M1 ENS. Optimisation convexe.

Description

Etude de la complexité de classes de problèmes convexes et d'algorithmes de performance optimale. Applications à l'approximation de problèmes combinatoires et en apprentissage statistique, imagerie, jeux, etc.

Thèmes abordés:
Algorithmes du premier ordre de performance optimale. Régularité et classes de complexité. Optimisation stochastique. Régularisation déterministe et stochastique. Algorithmes de localisation, projections alternées, ellipsoïde, centre analytique. Résolution d'inégalités variationelles. Approximation de problèmes combinatoires. Bornes d'approximations par méthodes probabilistes. Applications à l'estimation parcimonieuse, au filtrage collaboratif (NETFLIX), à la sélection de covariance, aux jeux matriciels, à la reconstruction de molécules, etc.

Informations pratiques

Premier semestre 2020. Le cours sera inversé: cours magistraux en vidéo, questions/réponses en visio toutes les semaines.

  • Horaires: Questions/réponses tous les jeudis en visio ici à 14:00, jusqu’à épuisement des questions.

  • Important: Inscrivez-vous sur le moodle du cours pour que je puisse vous contacter.

Programme


  • Fondamentaux

    • Rappels de convexité et dualité

  • Complexité algorithmique

    • Méthodes de point intérieur, self-concordance

    • Méthodes du premier ordre, localisation

  • Applications récentes

    • Statistiques, apprentissage

    • Problèmes géométriques, graphes

    • etc.

  • Approximations, asymptotique, convexité cachée

    • Concentration de la mesure

    • S-lemma, MaxCut, solutions de rang faible pour SDP

    • Géométrie en grandes dimensions

    • Reconstruction l1, complétion de matrices, déconvolution convexe, etc.

Organisation


Notes

Références


Exercices

Les cinq premiers exercices sont extraits du livre de Boyd et Vandenberghe. Merci de renvoyer vos DMs scannés et votre code (Python, Julia, MATLAB, etc.) à dm.daspremont@gmail.com.

  • DM1 pour le jeudi 12 novembre 2020.

Examen

L'examen est organisé sous forme de projet cette année. Il est maintenant en ligne et devra être rendu sous forme de dossier compressé avant le vendredi 15 janvier à 14:00 CET, par email à aspremon@ens.fr avec en sujet “Exam M1”.