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, à la sélection de covariance, aux jeux matriciels, à la reconstruction de molécules, etc.

Informations pratiques

Non donné. Cette page sert d'archive, en complément du cours du M2 MVA.

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 vendredi 12 novembre 2021.

Examen

Le jeudi 13 janvier de 15:30-17:00, salle N. Bourbaki, 45 rue d'Ulm, 75005 Paris.