Séminaire Français d’Optimisation

Le Séminaire Français d’Optimisation est un séminaire en ligne à destination de la communauté française d’optimisation. Il est  parrainé par le GDR MOA, PGMO et SMAI-MODE.

Il s’agit d’un séminaire régulier qui aura lieu deux fois par mois (à raison d’un séminaire toutes les deux semaines). La plateforme utilisée sera Zoom. Un lien sera donné deux jours avant la conférence.

Pour recevoir les annonces du séminaire, vous pouvez vous inscrire ici à la liste de diffusion.

Comité scientifique : S. Adly, J. Bolte, A. Chambolle, S. Charousset-Brignol, S. Gaubert, F. Santambrogio.

Prochains séminaires

Date : Jeudi 5 novembre 2020 à 16h
Orateur : Serge Gratton (ENSEEIHT)
Title : Optimization with inexact gradient and function

Abstrat : Important saving can be obtained on nowadays computer architectures by performing computation with reduced arithmetic: single precision, half precision, and even less. In this talk, we demonstrate that it is possible to produce robust optimization method that make use of an available hierarchy of arithmetic. In particular we propose adaptive algorithms that guarantee the same attainable accuracy accuracy as full precision algorithms. We propose a convergence theory for these algorithms as well as complexity guarantees. We will first address quadratic convex programming and then consider non convex situations.

Date : Jeudi 19 novembre 2020 à 16h
Orateur : Lénaïc Chizat (Paris Saclay)
Title : Analyse du flot de gradient pour les réseaux de neurones larges à deux couches

Abstrat : Les réseaux de neurones artificiels sont des familles paramétrées de fonctions de prédiction, utiles dans de nombreuses tâches en apprentissage automatique (classification, régression, modèles génératifs, etc). Pour une tâche d’apprentissage donnée, les paramètres du réseau sont ajustés à l’aide d’un algorithme de descente de gradient, de sorte que le prédicteur correspondant atteigne une bonne performance sur un jeu de données d’entraînement. Dans cet exposé, on présentera une analyse de cet algorithme pour les réseaux de neurones larges à deux couches en apprentissage supervisé, qui aboutit à une caractérisation précise du prédicteur appris. L’idée maîtresse consiste à étudier la dynamique d’entraînement en temps continu lorsque la taille du réseau de neurones tend vers l’infini: cet objet limite est un flot de gradient Wasserstein. Bien que la fonction objectif ne soit pas géodésiquement convexe, on montre que pour une initialisation adéquate, la limite de ce flot de gradient (si elle existe) est un minimiseur global. Nous étudierons aussi le “biais implicite” de cet algorithme quand l’objectif d’entraînement est la fonction de perte logistique sans régularisation : parmi la multitude de minimiseurs globaux, l’algorithme en choisit un en particulier, qui s’avère être un classifieur de type “marge maximale”. Enfin, nous discuterons des conséquences de ces résultats sur les performances statistiques de ces modèles en grande dimension. Il s’agit d’un travail en collaboration avec Francis Bach.

Séminaires passés

Date : Jeudi 15 octobre 2020 à 16h
Orateur : Emilie Chouzenoux (INRIA Saclay)
Title : Majorization-Minimization Subspace Algorithms for Large Scale Data Processing

Abstrat : Modern image recovery problems require powerful optimization frameworks to handle high dimensionality while providing reliable numerical solutions in a reasonable time. New optimization algorithms have thus to be designed, paying attention to computational complexity, scalability, and robustness. Majorization-Minimization (MM) approaches have become increasingly popular recently, in both signal/image processing and machine learning areas. My talk will present new theoretical and practical results regarding the MM Memory Gradient (3MG) algorithm [1], where the update of each iterate is restricted to a subspace of low dimension. I will show how to cast this efficient scheme into a block distributed version of it, named BD3MG, where blocks of variables are processed in an asynchronous manner, so as to take advantage of a distributed memory environment [2]. Convergence of the sequence built by the proposed BD3MG method will be analysed under mild assumptions. Application to the restoration of 3D images degraded by a depth-variant blur will illustrate the significant computational time reduction and the great scalability potential offered by the BD3MG approach when compared to several synchronous and asynchronous competitors.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 1er octobre 2020 à 16h
Orateur : Alessio Figalli (ETH Zürich)
Title : Strong rigidity of crystals

Abstrat : Geometric and functional inequalities play a crucial role in several problems in the calculus of variations, partial differential equations, geometry, etc. More recently, there has been a growing interest in studying the stability of such inequalities. This talk aims to give an overview of some results on this topic, focusing mainly on a recent stability result for anisotropic isoperimetric inequalities, which implies a robust rigidity property of crystals.

Date : Jeudi 17 septembre 2020 à 16h
Orateur : Francisco Silva (Université de Limoges)
Title : Approximation of first order mean field games

Abstrat : In this talk we will review some results on equilibria of first order mean field games and their approximation. The main focus of the talk will be a detailed exposition on how these equilibria can be approximated by equilibria of a suitable sequence of mean field games in discrete time and with finite state space.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 8 juillet 2020 à 17h
Orateur : Roberto Cominetti (Université Adolfo Ibañez, UAI, Chili)
Title : Large congestion games: Wardrop v/s Poisson ?

Abstrat : Congestion is a common phenomenon in transportation networks, both in large urban areas and telecommunication networks. We revisit the Wardrop equilibrium concept for routing games, as a continuous approximation for finite games with an increasing number of small players. We consider two scenarios: a deterministic model in which players have a small weight, as well as a stochastic scenario where players have non-negligible weights but are present with a small probability. In both cases, we obtain convergence towards two different Wardrop models, where in the second case the flows in the network retain their stochastic nature and are described by Poisson distributions. The latter can also be seen as a Poisson equilibrium in the sense of Myerson, and is consistent with the empirical flows observed in urban traffic.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 24 juin 2020 à 17h30
Orateur : Edouard Pauwels (Université Toulouse 3)
Titre : Un bestiaire de contre-exemples en optimisation convexe lisse.

Résumé : Cet exposé présente deux contre-exemples en optimisation convexe lisse coercitive. Le premier montre qu’en général la descente de gradient avec recherche linéaire exacte n’est pas convergente, le second que les trajectoires du système dynamique gradient n’ont pas de tangente à l’infini, contrairement au cas analytique (cf. conjecture de Thom établie par Kurdyka et al.). Ces exemples sont construits dans le plan à l’aide d’un résultat d’interpolation: étant donné une suite croissante d’ensembles convexes compacts dont la frontière est une courbe k fois différentiable (k > 1) à courbure positive, il existe une fonction convexe Ck pour laquelle chaque sous ensemble est un sous niveau. L’exposé portera sur les éléments de preuve de ce résultat d’interpolation et la manière dont il peut être utilisé pour construire les contre exemples annoncés. D’autres pathologies convexes lisses peuvent être produites grâce à cette approche : la méthode de Gauss-Seidel, les algorithmes de type Bregman, le flot de Newton, peuvent par exemple induire des trajectoires minimisantes non convergentes. Ces cas seront brièvement évoqués.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 10 juin 2020 à 17h30
Oratrice : Monique Laurent (Centrum Wiskunde & Informatica, Amsterdam and Tilburg University)
Title : Convergence analysis of approximation hierarchies for polynomial optimization.

Abstract : Minimizing a polynomial function f over a compact set K is a computationally hard problem. Upper bounds have been introduced by Lasserre (2011), which are obtained by searching for a degree 2r sum-of-squares density function minimizing the expected value of f over K with respect to a given reference measure supported by K. We will discuss several techniques that permit to analyse the performance guarantee of these bounds. This includes an eigenvalue reformulation of the bounds, links to extremal roots of orthogonal polynomials and to cubature rules, and reducing to the univariate case by means of push-forward measures. For simple sets K like the box, the unit ball, the simplex and the unit sphere one can show that the convergence rate to the global minimum is in O(1/r^2) and that this bound is tight for some classes of polynomials. These results extend to smooth strictly convex bodies satisfying some boundary conditions and, for general convex bodies, one can show a slightly weaker convergence rate in O((log(r)/r)^2). Based on joint works with Etienne de Klerk and Lucas Slot.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé