Un Mokameeting aura lieu le mercredi 13 septembre 2023, de 10h30 à 12h30, puis de 14h à 16h, dans la salle A415 à l’Inria Paris. Nous aurons le plaisir d’écouter six membres junior de Mokaplan : Médard Govoeyi, Guillaume Chazareix, Erwan Stampfli, Faniriana Rakoto Endor, Hugo Malamut et Maxime Sylvestre.

Séance du matin (10h30 – 12h30) dans l’ordre : Médard, Guillaume et Erwan

Médard Govoeyi
Titre : Euler incompressible et relaxation entropique
Abstract : Cet exposé portera sur l’équation d’Euler Incompressible et son lien avec le transport optimal.
Je discuterai d’une nouvelle approche de solution numérique basée sur le transport optimal régularisé par entropie.

Guillaume Chazareix
Title: Multi-Marginal Entropic Martingale Optimal Transport and applications to the calibration of Stochastic Processes.
Abstract: Martingale Optimal Transport has found extensive applications in various financial contexts, particularly in the calibration of stochastic processes. The numerical solutions for this problem involve tackling a variational problem that entails non-linear partial differential equations. In this presentation, we delve into a discretization approach for the continuous problem and introduce a relaxation technique by incorporating an entropy term. This relaxation enables the utilization of algorithms analogous to those employed in classical entropic optimal transport. Moreover, we outline potential methodologies for implementing this algorithm on a GPU platform, thereby enhancing computational efficiency.

Erwan Stampfli
Title : Multiphasic flow through the porous media, a study of the behaviour of gradient flow solutions for vanishing capillary pressure potentials
Abstract : We study a physical system of N+1 species of incompressible fluids contained in a spatial domain Omega. The particles of fluid are subjected to a potential force and the interaction of  different phases of fluids is driven by a capillarity potential parameter Pi. When the parameter Pi is  strongly convex, proof of existence of a solution to this system is achieved through a Wasserstein gradient flow approach. For a zero valued parameter Pi, the system takes the form of a hyperbolic system of conservation laws, and existence follows from general theorems of well posedness for such systems. Our result describes the behaviour of gradient flow solutions for vanishing capillarity potential parameters, and shows the gradient flow solutions converge toward the hyperbolic system of conservation laws solution as the capillary potential vanishes.  

Séance de l’après-midi (14h00-16h00) dans l’ordre : Tommy, Hugo et Maxime

Faniriana Rakoto Endor
Titre : Pourquoi l’heuristique de Burer-Monteiro fonctionne-t-elle ?
Abstract : On considère un problème d’optimisation semidéfinie (SDP) où on minimise une fonction linéaire d’une variable matricielle sujette à des contraintes affines d’une part et des contraintes de positivité d’autre part. Des méthodes existent pour résoudre ce problème, mais leur complexité croît rapidement avec le nombre de variables. Il existe souvent des solutions de faible rang. C’est là qu’est introduit l’heuristique de Burer-Monteiro où on factorise la variable en un produit de deux matrices plus fines. On optimise alors sur les facteurs, qui présentent moins de paramètres que la variable initiale. Toutefois, cette factorisation perd le caractère convexe du problème initial. Je parlerai de l’étude du problème pour des matrices très fines grâce à des études numériques du problème MaxCut.

Hugo Malamut
Titre : Equations semi-géostrophiques et transport entropique
Abstract : Les équations semi-géostrophiques permettent notamment de modéliser l’évolution des fronts de vent sur de larges échelles de temps et d’espace. Le transport optimal en fournit une interprétation simple et condensée. Je présenterai une méthode de résolution numérique basée sur la pénalisation entropique du transport optimal. De plus, j’expliquerai en quoi l’approximation entropique régularise ces équations et donne une nouvelle preuve d’existence de solutions faibles.

Maxime Sylvestre
Titre : Taux de convergence pour le transport régularisé : démêler la sous-optimalité et l’entropie
Abstract : Nous étudions le taux de convergence du coût entropique en utilisant une technique de découplage de l’entropie et de la sous-optimalité. Nous obtenons alors pour la classe des coût avec twist infinitésimal que la sous-optimalité est en epsilon et l’entropie en epsilon log epsilon.

Un Mokameeting aura lieu le mercredi 7 juin 2023, à 14h, dans la salle A415 à l’Inria Paris. Nous aurons le plaisir d’écouter Jean-Charles Gilbert (Inria Paris) et João-Miguel Machado (Inria Paris et Ceremade, université Paris Dauphine).

Jean-Charles Gilbert : Polyhedral Newton-min algorithms for complementarity problems

Résumé : The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system.

If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-square merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent
algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-square function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a “negative kink” of the minimum function and acts accordingly.

In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global convergence to regular points is proved.

If time permits, we will also talk about a related problem, that of the computation of the B-differential of the componentwise minimum of affine functions and the link this problem has with the arrangements of hyperplanes and the bipartitions of a finite set of points.

João-Miguel Machado : Approximation 1D des mesures dans l’espace de Wasserstein

Résumé : Nous proposons une méthode variationnelle pour approcher une mesure parmi les mesures uniformément distribuées sur un ensemble de dimension 1. Le problème consiste à minimiser la distance de Wasserstein comme terme d’attache aux donnés avec une pénalisation de la longueur du support. Comme montrer l’existence de solutions est délicat, nous proposons un problème relaxé qui admet toujours des solutions. Ensuite nous montrons que si l’espace ambiant est \(\mathbb{R}^2\), sous les hypothèses techniques, n’importe quelle solution du problème relaxé est uniformément distribuée, et étant alors une solution du problème originel. Finalement nous montrons que les solutions du problème relaxé, et donc du problème originel, sont Ahlfors régulières.

Un Mokameeting aura lieu le mercredi 24 mai 2023, à 14h, dans la salle A413 à Dauphine (attention à ce lieu inhabituel !). Nous aurons le plaisir d’écouter Luigi de Pascale (Università degli Studi di Firenze) et Pierre Lissy (Ceremade, université Paris Dauphine).

Pierre Lissy : contrôle désensibilisant pour l’équation de la chaleur par rapport à des variations du domaine

Résumé : Dans cet exposé, je présenterai quelques résultats récents obtenus en collaboration avec Sylvain Ervedoza et Yannick Privat sur le contrôle désensibilisant de l’équation de la chaleur posée sur un domaine borné. La question consiste à trouver un contrôle, distribué ici sur un sous-domaine, tel qu’une certaine fonctionnelle dépendant de la solution de l’équation de la chaleur (dans notre cas, l’énergie de la solution localisée sur un autre sous-domaine de l’équation de la chaleur) soit localement insensible à une certaine perturbation de l’équation. Ici, la principale originalité de notre travail repose sur le fait que la perturbation est le domaine lui-même, dans le sens où sa frontière peut être soumise à de petites variations. Je présenterai diverses définitions du problème de la désensibilisation et donnerai quelques résultats positifs et négatifs, en donnant une interprétation en termes de robustesse pour des questions de contrôlabilité.

Luigi de Pascale : 60 years of cyclical monotonicity

Résumé : In 2024 R.T. Rockafellar will be 90 years old. About 60 years ago he discovered, this is a celebrated “Rockafellar’s theorem”, that cyclical monotonicity characterizes the sub-differential of convex functions. Almost 30 years later, cyclical monotonicity met optimal transport and the concept was expanded in several directions, bringing to new versions of Rockafellar’s theorem and new problems. I will report on some works with Anna Kausamo and  K. Wyczesany and, if time permits, discuss some of the current open problems.  (If possible, the talk will be in French).

Un Mokameeting aura lieu le mercredi 8 mars 2023, à 14h, dans la salle A415. Nous aurons le plaisir d’écouter Jun Kitagawa (Michigan State University).

Titre : On nontwisted optimal transport problem on nonstrictly convex boundaries

Résumé : If the cost function satisfies the so-called bi-twist condition, solutions of the optimal transport problem with absolutely continuous source measure are given by a.e. single valued maps (Monge solutions). If the cost is ambient Euclidean distance squared restricted to the boundary of a convex body, bi-twist fails. Gangbo and McCann showed if the body is uniformly convex and source and target measures are absolutely continuous with respect to surface measure, with densities bounded away from zero and infinity, there is a unique Kantorovich solution; but this may not be a Monge solution. In this talk I discuss a recent result of ours showing: when the two measures have sufficiently small optimal transport cost, the solution is given by a Monge solution, when the body is \(C^1\) and convex (but not necessarily strictly convex). This result is sharp in the sense that the claim can fail for a non-\(C^1\) domain, even if it is uniformly convex. This talk is based on joint work with Seonghyeon Jeong.

Un Mokameeting aura lieu le mercredi 8 février 2023, à 14h, dans la salle A415. Nous aurons le plaisir d’écouter Alex Delalande (LMO & Inria)

PDF de la présentation

Titre : Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport

Résumé : In this talk, I will present some nearly tight and non-asymptotic convergence bounds for the solutions of entropic semi-discrete optimal transport problems with a quadratic ground cost. These bounds quantify the stability of the dual solutions of the regularized transport problem (sometimes called Schrödinger or Sinkhorn potentials) with respect to the regularization parameter, for which a better than Lipschitz dependence is showcased. Such facts may be a first step towards a mathematical justification of annealing or ε-scaling heuristics for the numerical resolution of regularized semi-discrete optimal transport. These bounds also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized optimal transport costs in the semi-discrete setting.
I will present the main arguments used to prove these bounds, which rely in particular on an estimation of the strong-convexity of the dual problem that holds beyond the semi-discrete and entropic setting.

Un Mokameeting aura lieu le mercredi 16 novembre 2022, à 14h, dans la salle A425. Nous aurons le plaisir d’écouter Kimia Nadjahi (LPSM, Sorbonne Université)

Titre : Sliced-Wasserstein Distance for Large-Scale Machine Learning: A Statistical Analysis

Résumé : The Sliced-Wasserstein distance (SW) is a computationally efficient metric between probability measures inspired by optimal transport theory, which has been increasingly used in various statistical and machine learning applications. However, the empirical success of SW-based algorithms was poorly understood, and there had been little work regarding the theoretical properties of SW. In this talk, we further explore the use of SW in modern statistical and machine learning problems, with a twofold objective: 1) provide new theoretical insights to understand in depth SW-based algorithms, 2) design novel tools inspired by SW to improve its applicability and scalability. We first prove a set of asymptotic properties on the estimators obtained by minimizing SW, as well as a central limit theorem whose convergence rate is dimension-free. Then, given that SW is commonly estimated with a simple Monte Carlo integration, we develop an alternative, principled method to alleviate the inefficiencies caused by the Monte Carlo error, by leveraging the concentration of measure phenomenon. Finally, we discuss generalizations of SW and focus on the class of adaptive Sliced-Wasserstein distances: we show that adaptive SW may be interpreted as an average risk, the quantity PAC-Bayesian bounds have been designed to characterize, and derive generalization bounds which can be optimized to increase the discriminative power of such metrics.

Un Mokameeting aura lieu le mercredi 23 novembre 2022, à 14h, dans la salle A425. Nous aurons le plaisir d’écouter Marina Krémé (Inria Nancy)

Titre : Time-frequency fading

Résumé : We consider a situation in which the signal of interest has been  degraded by an additive perturbation that is well localized in specific regions of the time-frequency plane. We are interested in the attenuation of energy in the masked time-frequency regions in order to estimate the signal of interest. This is referred to as time-frequency fading, and it is approached through the time-frequency filtering angle. To avoid phase issues, we formulate the optimization problem in the signal domain and propose  algorithmically efficient solutions.

The formulation of the problem allows to precisely control the level of  attenuation, by adjusting a trade-off between the energy in the areas to be attenuated and the approximation error outside these areas. The problem admits an analytical solution that involves the notion of Gabor multipliers. These operators’ dominant eigenvectors exhibit remarkable time-frequency  localization properties, and the decay of their eigenvalues allows for the use of reduced rank approximations. We propose algorithms based on  these approximations, as well as randomized decomposition algorithms and non-overlapping properties of the attenuated time-frequency regions.