Session III.3 - Computational Optimal Transport
Talks
Monday, June 19, 14:00 ~ 15:00
On the existence of Monge maps for the Gromov-Wasserstein problem
François-Xavier Vialard
Univ. Gustave Eiffel, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
For the L2-Gromov-Wasserstein distance, we study the structure of minimizers in Euclidean spaces for two different costs. The first cost is the scalar product for which we prove that it is always possible to find optimizers as Monge maps and we detail the structure of such optimal maps. The second cost is the squared Euclidean distance for which we show that the worst case scenario is the existence of a map-anti-map structure. Both results are direct and indirect consequences of an existence result on costs that are defined by submersions. In dimension one for the squared distance, we show that a monotone map is optimal in some non-symmetric situations, thereby giving insight on why such a map is often found optimal in numerical experiments. In addition, we show numerical evidence for a negative answer to the existence of a Monge map under the conditions of Breniers theorem, suggesting that our result cannot be improved in general. arXiv: 2210.11945
Joint work with Théo Dumont, Théo Lacombe..
Monday, June 19, 15:00 ~ 16:00
Interpretable Optimal Transport in High-Dimensions with Feature-Sparse Maps
Marco Cuturi
Apple, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Optimal transport (OT) theory focuses, among all maps that can morph a probability measure onto another, on those that are the ``thriftiest'', i.e. such that the average cost between and its image is as small as possible. Many computational approaches have been proposed to estimate such Monge maps when that cost is the squared-Euclidean distance, using for instance neural networks. Such methods have been successfully applied to single-cell genomics, but have limitations in that they do not work well in high-dimensions, and require typically a massive drop in data dimensionality before being applied (e.g. using PCA to lower dimension of 35k dimensional gene counts to a few 50 directions). After recalling how these methods operate, I will present a recent method that allows the recovery of feature-sparse maps, e.g. such that the displacement vector $T(x)-x$ be sparse. I will detail its construction, and explain how this method can recover interpretable OT maps in high dimensions.
Joint work with Michal Klein (Apple) and Pierre Ablin (Apple).
Monday, June 19, 16:30 ~ 17:00
A discussion on Wasserstein geodesic extrapolation and the construction of variational second order scheme for Wasserstein gradient flows.
Thomas Gallouët
Inria Paris, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We introduce a time discretization for Wasserstein gradient flows based on the classical Backward Differentiation Formula of order two. The main building block of the scheme is the notion of geodesic extrapolation in the Wasserstein space, which in general is not uniquely defined. We propose several possible definitions for such an operation, and we prove convergence of the resulting scheme to the limit PDE, in the case of the Fokker-Planck equation. For a specific choice of extrapolation we also prove a more general result, that is convergence towards EVI flows. Finally, we propose a variational finite volume discretization of the scheme which numerically achieves second order accuracy in both space and time.
Joint work with Andrea Natale (Inria Lille, France) and Gabriele Todeschi (Université Grenoble-Alpes, France).
Monday, June 19, 17:00 ~ 17:30
Minimax estimation of discontinuous optimal transport maps: The semi-discrete case
Aram-Alexandre Pooladian
New York University - This email address is being protected from spambots. You need JavaScript enabled to view it.
We consider the problem of estimating the optimal transport map between two probability distributions, $P$ and $Q$ in $\mathbb{R}^d$, on the basis of i.i.d. samples. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution $Q$ is a discrete measure supported on a finite number of points in $\mathbb{R}^d$. We study a computationally efficient estimator initially proposed by [PNW21], based on entropic optimal transport, and show in the semi-discrete setting that it converges at the minimax-optimal rate $n^{−1/2}$, independent of dimension. Other standard map estimation techniques both lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. We confirm these results in numerical experiments, and provide experiments for other settings, not covered by our theory, which indicate that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems.
[PNW21] Pooladian, Aram-Alexandre, and Niles-Weed, Jonathan. "Entropic estimation of optimal transport maps", preprint, 2021
Joint work with Vincent Divol (CEREMADE, Université Paris-Dauphine - PSL) and Jonathan Niles-Weed (New York University).
Monday, June 19, 17:30 ~ 18:00
Numerical methods for high-dimensional multi-marginal optimal transport problems
Gero Friesecke
Technical University of Munich, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Multi-marginal OT problems arise naturally in application fields such as electronic structure, fluid dynamics, and data science, but pose a huge challenge for computation. This is because the number N of marginals corresponds, respectively, to the number of particles, timesteps, and datasets, hence one is interested in large N, but the number of unknowns after discretization scales exponentially in N. I will survey some promising recent avenues for tackling the curse of dimension in these problems, with particular emphasis on the Genetic Column Generation algorithm developed jointly with Daniela Voegler, Andreas S. Schulz and Maximilian Penka (SIAM JSC 2022; arXiv:2209.09081 2022) and its applications.
Monday, June 19, 18:00 ~ 18:30
Sparsity results for moment-constrained approximation of the Lieb functional
Virginie Ehrlacher
Ecole des Ponts ParisTech & INRIA, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
The aim of this talk is to present new sparsity results about the so-called Lieb functional, which is a key quantity in Density Functional Theory for electronic structure calculations for molecules. The Lieb functional was actualy shown tby Lieb o be a convexification of the so-called Lévy-Lieb functional. Given an electronic density for a system of N electrons, which may be seen as a probability density defined on the set R^3, the value of the Lieb functional for this density is defined as the solution of a quantum multi-marginal optimal transport problem, which reads as a minimization problem defined onto the set of trace-class operators acting on the space of electronic wavefunctions that are antisymmetric L^2 functions of R^{3N}, with partial trace equal to the prescribed electronic density. We introduce a relexation of this quantum optimal transport where the full partial trace constraint is replaced by a finite number of moment constraints on the partial trace of the set of operators. We show that, provided that the electronic density decays to 0 at infinity fast enough, there exists sparse minimizers to the moment-constrained approximation of the Lieb (MCAL) functional that read as operators with rank at most equal to the number of moment constraints. We also prove under appropriate assumptions on the set of moment functions that the value of the MCAL functional converges to the value of the exact Lieb functional as the number of moments go to infinity.
Joint work with Luca Nenna (Laboratoire de Mathématiques d'Orsay, France).
Tuesday, June 20, 14:00 ~ 15:00
Unbalanced Optimal Transport across Metric Measured Spaces
Gabriel Peyré
CNRS and ENS, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Optimal transport (OT) has recently gained a lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by several issues, and in particular: (i) the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension, (ii) sensitivity to outliers, since it prevents mass creation and destruction during the transport (iii) impossibility to transport between two disjoint spaces. In this talk, I will review several recent proposals to address these issues, and showcase how they work hand-in-hand to provide a comprehensive machine learning pipeline. The three key ingredients are: (i) entropic regularization which defines computationally efficient loss functions in high dimensions (ii) unbalanced OT, which relaxes the mass conservation to make OT robust to missing data and outliers, (iii) the Gromov-Wasserstein formulation, introduced by Sturm and Memoli, which is a non-convex quadratic optimization problem defining transport between disjoint spaces. More information and references can be found on the website of our book "Computational Optimal Transport" https://optimaltransport.github.io/
Tuesday, June 20, 15:00 ~ 16:00
LCP methods for equilibrium transport
Alfred Galichon
NYU and Sciences Po, USA and France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Equilibrium transport is a generalization of optimal transport particularly well-suited for economic applications. We review the theory of equilibrium transport and discuss computational aspects thought a formulation in terms of linear complementarity problems.
Tuesday, June 20, 16:30 ~ 17:00
Entropic transfer operators for data-driven analysis of dynamical systems
Bernhard Schmitzer
Göttingen University, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
The transfer operator is an elegant way to capture the behaviour of a (stochastic) dynamical system as a linear operator. Spectral analysis can then in principle reveal (almost) invariant measures, cyclical behaviour, as well as separation of the dynamics into different time scales. In practice this analysis can rarely be done analytically, due to the complexity of the operator or since it may not be known in closed form. A central objective is therefore to numerically approximate this operator (or its adjoint: the Koopman operator) or to estimate it from data. In this talk we introduce a new estimation method based on entropic optimal transport and show convergence to a smoothed version of the original operator as more data becomes available. This involves an interplay between three different length scales: the discretization scale given by the data, the blur scale introduced by entropic transport, and the spatial scale of eigenfunctions of the operator.
Joint work with Oliver Junge (TU Munich, Germany) and Daniel Matthes (TU Munich, Germany).
Tuesday, June 20, 17:00 ~ 17:30
Convergence rate of entropy-regularized multi-marginal optimal transport costs
Luca Nenna
(LMO) Université Paris-Saclay, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We investigate the convergence rate of multi-marginal optimal transport costs that are regularized with the Boltzmann-Shannon entropy, as the noise parameter $\varepsilon$ tends to 0. We establish lower and upper bounds on the difference with the unregularized cost of the form $C\varepsilon\ log(1/\varepsilon) + O(\varepsilon)$ for some explicit dimensional constants $C$ depending on the marginals and on the ground cost, but not on the optimal transport plans themselves. Upper bounds are obtained for Lipschitz costs or costs with Lipschitz gradient, and lower bounds for $\mathcal C^2$ costs satisfying some signature condition on the mixed second derivatives that may include degenerate costs, thus generalizing results previously obtained by Carlier, Pegon, Tamanini and Eckstein, Nutz in the 2-marginal case and for non-degenerate costs. We obtain in particular matching bounds in some typical situations where the optimal plan is deterministic, like in the case of Wasserstein barycenters.
Joint work with Paul PEGON (Université Paris-Dauphine-PSL, France).
Tuesday, June 20, 17:30 ~ 18:00
Exponential convergence of Sinkhorn algorithm for quadratic costs and weakly log- concave marginals
Giovanni Conforti
IPParis, FRANCE - This email address is being protected from spambots. You need JavaScript enabled to view it.
Over the past decade, Entropic Optimal Transport problem has emerged as a versatile and computationally more tractable proxy for the Optimal Transport (Monge-Kantorovich) problem for applications in data science and statistical machine learning. One of the reasons behind the interest in adding an entropic penalty in the Monge Kantorovich problem is the fact that solutions can be computed by means of Sinkhorn’s algorithm, a.k.a. Iterative Proportional Fitting Procedure. While the exponential convergence of Sinkhorn’s iterates is well understood in a discrete setting or for compactly supported measures and bounded costs, when moving to unbounded costs and non compact marginals the picture is far less clear. In this talk, we shall present an exponential convergence result in the landmark example of quadratic entropic optimal transport and approximately log-concave marginals. The main innovation in the proof strategy are new propagation of weak convexity results along Hamilton Jacobi Bellman equations, that may be of independent interest.
Joint work with Alain Durmus (IPParis), Giacomo Greco (TU Eindhoven) and Maxence Noble (IPParis).
Tuesday, June 20, 18:00 ~ 18:30
Learning to optimize transport plans
Giulia Luise
Microsoft Research - This email address is being protected from spambots. You need JavaScript enabled to view it.
Optimal transport distances and their regularized versions are a powerful tool to compare probability measures, that proved successful in many machine learning applications. In this talk, I will give a brief introduction on (entropy-regularized) optimal transport and dive into 'learning to optimize' transport plans leveraging amortized optimization.
Joint work with Brandon Amos (META), Samuel Cohen (UCL), Ievgen Redko (Aalto University).
Wednesday, June 21, 14:00 ~ 14:30
Wasserstein adversarial robustness for NN
Jan Obloj
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
We develop applications of tools from the optimal transport theory to adversarial robustness of NN. The latter refers to the phenomenon where a successfully trained NN architecture can be fooled by humanly imperceptible changes to the inputs. First discussed in the seminal work of \href{https://arxiv.org/pdf/1412.6572.pdf} {Goodfellow et al (2015)}, the task of understanding sensitivity to such attacks and of developing training methods which are robust to such adversarial data attacks, is an important topic in the ML literature. We refer to \href{http://robustbench.github.io}{RobustBench} for a list of papers and a zoo of benchmarks. We re-interpret the problem as a distributionally robust optimization, interpret data as probability measures and employ Wasserstein balls to characterise potential adversarial perturbations. We then rely on the results in \href{https://doi.org/10.1098/rspa.2021.0176}{Bartl, Drapeau, Obloj and Wiesel (2021)} to obtain explicit first-order approximations to the robust value and robust optimizers. This allows us to quantify, for small perturbations, the adversarial robustness and derive candidates for robust training methods. We show in particular how these allow to recover some classical approaches, such as the FGSM. We test our theoretical predictions on the model zoo available through RobustBench and report the observed empirical fit.
Joint work with Xingjian Bai (University of Oxford, UK), Yifan Jiang (University of Oxford, UK) and Guangyi He (University of Oxford, UK).
Wednesday, June 21, 14:30 ~ 15:00
Causal optimal transport with entropic regularization
Stephan Eckstein
ETH Zürich, Switzerland - This email address is being protected from spambots. You need JavaScript enabled to view it.
This talk showcases the use of entropic regularization for the causal (also called adapted) optimal transport problem. Causal optimal transport is applied in settings where the marginals are distributions of a time-series, and where one imposes an additional constraint on the couplings enforcing a temporal structure. As in the classical optimal transport problem, we show that the approximation error arising from entropic regularization can be controlled for causal optimal transport. Further, the proof of convergence can be used to obtain quantitative error estimates which are sharp even in the classical case. Further, we will define an adapted version of Sinkhorn's algorithm and show that it converges linearly, which builds on the dual formulation and causal versions of the Schrödinger equations.
Joint work with Marcel Nutz (Columbia University, USA) and Gudmund Pammer (ETH Zürich, Switzerland).
Wednesday, June 21, 15:00 ~ 16:00
The Wasserstein-Martingale projection of a Brownian motion given initial and terminal marginals
Julio Backhoff
University of Vienna, Austria - This email address is being protected from spambots. You need JavaScript enabled to view it.
In classical optimal transport, a central quest is to determine the stochastic process interpolating between initial and terminal marginals which is as close as possible to a constant speed process. In the emerging field of martingale optimal transport we claim that the analogous question is: what is the stochastic process interpolating between initial and terminal marginals which is as close as possible to a constant volatility process (i.e. Brownian motion)?
The answer to the above question is the so-called stretched Brownian motion. In this talk we will introduce this object and present its remarkable connection to Brenier maps. This is achieved via duality techniques which are at the same time remarkably similar and yet substantially different from the classical optimal transport case. To date, little is known about how to compute / approximate these objects, but a number of open questions concerning such computational aspects will be provided.
Joint work with Based on joint works with Mathias Beiglböck, Walter Schachermayer, Bertram Tschiderer (University of Vienna, Austria), Martin Huesmann (University of Münster, Germany) and Sigrid Källblad (KTH, Sweden)..
Wednesday, June 21, 16:30 ~ 17:30
Quantifying arbitrage
Beatrice Acciaio
ETH Zurich, Switzerland - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this talk I will present a way to quantify arbitrage, that allows to deal with model uncertainty without imposing the no-arbitrage condition. In markets that admit "small arbitrage", we can still make sense of the problems of pricing and hedging. The pricing measures here will be such that asset price processes are close to being martingales, and the hedging strategies will need to cover some additional cost. We show a quantitative version of the Fundamental Theorem of Asset Pricing and of the Super-replication theorem. We study robustness of the amount of arbitrage and existence of respective pricing measures, showing stability with respect to a new, strong adapted Wasserstein distance.
Joint work with Julio Backhoff-Veraguas (University of Vienna) and Gudmund Pammer (ETH Zurich).
Wednesday, June 21, 17:30 ~ 18:00
Globally Lipschitz (non-optimal) transport maps
Max Fathi
Université Paris Cité, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Lipschitz transport maps allow to transfer functional and isoperimetric inequalities, such as logarithmic Sobolev inequalities, from one probability measure to another. For uniformly log-concave measures on Euclidean spaces, this can be done using quadratic optimal transport, thanks to Caffarelli's contraction theorem. In this talk, I will discuss a stochastic construction of Lipschitz transport maps due to Kim and Milman, and how it works in other settings, including some non-log-concave measures and Riemannian manifolds.
Joint work with Dan Mikulincer (MIT) and Yair Shenfeld (MIT).
Wednesday, June 21, 18:00 ~ 18:30
Optimizing healthcare provider network with principal-agent approach and optimal transport
Hadrien De March
Qantev, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Designing the optimal healthcare providers network is a challenge for insurance companies that wish to bring the best quality of care to their members for the best price. However, insurers have no direct control on the choice of healthcare providers of their members, they can only steer them through incentive. Then the matching between the members and the providers can be modeled through optimal transport as done by economists for modeling pairings. We show the existence of a solution to the optimal problem and build an algorithm that finds the optimum.
Joint work with Nathan Sauldubois (CMAP, Ecole Polytechnique) and Nizar Touzi (CMAP, Ecole Polytechnique).
Posters
Gradient descent with a general cost
Pierre-Cyril Aubin
INRIA SIERRA, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
How to design algorithms that extend classical methods (and their convergence theory) beyond the Euclidean setting? How to integrate different families of algorithms into a unified framework? How to systematically approximate optimization problems? We show that c-transforms allow to build majorizing surrogates, which can be tackled through alternating minimization. The ``five-point property'' of Csiszar and Tusnady gives (sub)linear convergence rates for the values of the iterates. This property corresponds to a novel notion of c-semiconvexity, extending relative strong convexity, and intimately related to the MTW tensor . The mirror/Riemannian/natural gradient descent algorithms can all be cast in this formalism, leading to novel convergence conditions and rates.
Joint work with Flavien Léger (INRIA MOKAPLAN, France).
Nonlinear reduced basis using mixture Wasserstein barycenters: application to an eigenvalue problem
Maxime Dalery
Laboratoire de Mathématiques de Besançon, UMR CNRS 6623, Université de Franche-Comté, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We are interested in the computation of the ground state of a given molecular system composed of $M$ nuclei characterized by their positions $r_1, \dots, r_M$ in space and their electric charges $z_1, \dots, z_M$. The ground state of this system is an eigenfunction with lowest corresponding eigenvalue (called energy) of an operator, called Hamiltonian. Ground states are generally computed using linear approximations such as Galerkin methods, but such methods rely heavily on the heuristic of a good choice for the basis. Moreover, determining the ground state is in general very costly, especially when it needs to be computed for a lot of different geometries, as in geometry optimization and molecular dynamics.
In this poster, I will focus on a one-dimensional Hamiltonian, with Dirac delta potentials placed at atomic positions $r_1, \dots, r_M$, for which ground states are fully described in [4]. In [3], a method based on optimal transport was proposed for different problems, where solutions were approximated as Wasserstein barycenters between solutions for different parameters. However, this method is not expected to scale with the dimension due to the high-computational cost of Wasserstein barycenters.
In this work, we propose a new approach based on a decomposition of the ground state as a mixture of Slater functions, for which modified Wasserstein barycenters can be computed efficiently [1, 2]. In this method, we select a few representative solutions using a greedy algorithm in a first phase, called offline phase, which serves the purpose of reducing computational time for solution computations and can be done only once. Solutions are then computed on-the-fly in an online phase, as barycenters of the previously selected solutions. Some numerical results will illustrate our approach.
References
[1] J. Delon and A. Desolneux, A Wasserstein-Type distance in the space of gaussian mixture models, SIAM J. Imaging Sci., 13 (2020), pp. 936–970.
[2] G. Dusson, V. Ehrlacher, and N. Nouaime, A wasserstein-type metric for generic mixture models, including location-scatter and group invariant measures, (2023).
[3] V. Ehrlacher, D. Lombardi, O. Mula, and F.-X. Vialard, Nonlinear model reduction on metric spaces. application to one-dimensional conservative PDEs in wasserstein spaces, Esaim Math. Model. Numer. Anal., 54 (2020), pp. 2159–2197.
[4] D. H. Pham, Galerkin method using optimized wavelet-Gaussian mixed bases for electronic struc- ture calculations in quantum chemistry, PhD thesis, Université Grenoble Alpes, June 2017.
Joint work with Geneviève Dusson (Laboratoire de Mathématiques de Besançon, UMR CNRS 6623, Université de Franche-Comté), Alexei Lozinski (Laboratoire de Mathématiques de Besançon, UMR CNRS 6623, Université de Franche-Comté) and Virginie Ehrlacher (CERMICS, École des Ponts & Inria Paris).
Solving the shallow-water semi-geostrophic equations through Sinkhorn's algorithm
Jacob Francis
Imperial, UK - This email address is being protected from spambots. You need JavaScript enabled to view it.
We propose a novel application of the generic Sinkhorn algorithm as proposed by L. Chizat et al. (2016), to solve the shallow-water semi-geostrophic (SWSG) equations. The method provides a numerical and geometrically intuitive algorithm to model large-scale oceanic phenomena through the methods devised by Cullen and Gangbo (2001), which are based on the Cullen-Purser Stability Principle (Cullen and Purser, 1984). Specifically, we solve the SWSG equations stated as an optimal transport problem, with one $L^2$-norm divergence and one indicator function divergence imposed on the marginals. Solutions of the equations correspond to energy minimisation states which allow us to cast the problem as an OT one. We are then able to artificially add KL regularisation so that we can leverage the results of Chizat et al, in particular the Sinkhorn updates for generic marginal constraints.
In this first phase we examine the initialisation process. Initialisation is achieved by starting from an analytical ocean height, which can be mapped to the geostrophic domain through Hoskin's transformations. The algorithm is then given these known geostrophic densities and calculates the corresponding minimum height associated to this density. In this case, height solutions correspond to the analytical height which we input. We check convergence for these known initial states and investigate best practises for keeping errors low.
Joint work with Colin Cotter (Imperial College London, UK) and Jean-David Benamou (INRIA Paris, France).
Unsupervised Ground Metric Learning using Wasserstein Singular Vectors
Geert-Jan Huizing
ENS PSL, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Defining meaningful distances between samples in a dataset is a fundamental problem in machine learning. Optimal Transport (OT) lifts a distance between features (the "ground metric") to a geometrically meaningful distance between samples. However, there is usually no straightforward choice of ground metric. Supervised ground metric learning approaches exist but require labeled data. In absence of labels, only ad-hoc ground metrics remain. Unsupervised ground metric learning is thus a fundamental problem to enable data-driven applications of OT. In this paper, we propose for the first time a canonical answer by simultaneously computing an OT distance between samples and between features of a dataset. These distance matrices emerge naturally as positive singular vectors of the function mapping ground metrics to OT distances. We provide criteria to ensure the existence and uniqueness of these singular vectors. We then introduce scalable computational methods to approximate them in high-dimensional settings, using stochastic approximation and entropic regularization. Finally, we showcase Wasserstein Singular Vectors on a single-cell RNA-sequencing dataset.
Joint work with Laura Cantini (ENS PSL) and Gabriel Peyré (ENS PSL).
Approximation of Splines in Wasserstein Spaces
Jorge Justiniano
University of Bonn, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
This paper investigates a time discrete variational model for splines in Wasserstein spaces to interpolate probability measures. Cubic splines in Euclidean space are known to minimize the integrated squared acceleration subject to a set of interpolation constraints. As generalization on the space of probability measures the integral over the squared acceleration is considered as a spline energy and regularized by addition of the usual action functional. Both energies are then discretized in time using local Wasserstein-2 distances and the generalized Wasserstein barycenter. The existence of time discrete regularized splines for given interpolation conditions is established. On the subspace of Gaussian distributions, the spline interpolation problem is solved explicitly and consistency in the discrete to continuous limit is shown. The computation of time discrete splines is implemented numerically, based on entropy regularization and the Sinkhorn algorithm. A variant of the iPALM method is applied for the minimization of the fully discrete functional. A variety of numerical examples demonstrate the robustness of the approach and show striking characteristics of the method. As a particular application the spline interpolation for synthesized textures is presented.
Joint work with Martin Rumpf (University of Bonn) and Matthias Erbar (University of Bielefeld).
Linearized Wasserstein dimensionality reduction with approximation guarantees
Varun Khurana
University of California, San Diego, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
We introduce LOT Wassmap, a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. The algorithm is motivated by the observation that many datasets are naturally interpreted as probability measures rather than points in $\mathbb{R}^n$, and that finding low-dimensional descriptions of such datasets requires manifold learning algorithms in the Wasserstein space. Most available algorithms are based on computing the pairwise Wasserstein distance matrix, which can be computationally challenging for large datasets in high dimensions. Our algorithm leverages approximation schemes such as Sinkhorn distances and linearized optimal transport to speed-up computations, and in particular, avoids computing a pairwise distance matrix. We provide guarantees on the embedding quality under such approximations, including when explicit descriptions of the probability measures are not available and one must deal with finite samples instead. These approximation guarantees provide a framework for using different finite sample approximations of the optimal transport map even when the underlying distributions are supported on all of $\mathbb{R}^n$. Experiments demonstrate that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
Joint work with Keaton Hamm (University of Texas at Arlington, Arlington, TX), Alex Cloninger (University of California, San Diego, CA) and Caroline Moosmueller (University of North Carolina at Chapel Hill, NC).
Estimating pollution spread in water networks as a Schrödinger bridge problem with partial information
Michele Mascherpa
Kungliga Tekniska högskolan (KTH), Sweden - This email address is being protected from spambots. You need JavaScript enabled to view it.
Incidents where water networks are contaminated with microorganisms or pollutants can result in a large number of infected or ill persons, and it is therefore important to quickly detect, localize and estimate the spread and source of the contamination. In many of today’s water networks only limited measurements are available, but with the current internet of things trend the number of sensors is increasing and there is a need for methods that can utilize this information. Motivated by this fact, we address the problem of estimating the spread of pollution in a water network given measurements from a set of sensors. We model the water flow as a Markov chain, representing the system as a set of states where each state represents the amount of water in a specific part of the network, e.g., a pipe or a part of a pipe. Then we seek the most likely flow of the pollution given the expected water flow and the sensors observations. This is a large-scale optimization problem that can be formulated as a Schrödinger bridge problem with partial information, and we address this by exploiting the connection with the entropy regularized multimarginal optimal transport problem. The software EPANET is used to simulate the spread of pollution in the water network and will be used for testing the performance of the methodology.
Joint work with Isabel Haasler (EPFL, Switzerland), Bengt Ahlgren (RISE Research Institutes of Sweden) and Johan Karlsson (KTH).
Genetic Column Generation: Convergence proof and application to transport splines on the Wasserstein space
Maximilian Penka
Technische Universität München, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Solving multi-marginal optimal transport problems numerically is a challenging task as it suffers from the curse of dimension. The curse occurs not only in computing time, but already in data complexity. For $N$ marginals, each of them discretized on $\ell$ support points, the corresponding linear program has $\ell^N$ unknowns. On the other hand, the problem is known to have an extremal solution with support size at most $N(\ell - 1) + 1$, equal to the number of independent constraints. This gave rise to a new algorithm that updates the set of admissible support points genetically while maintaining its guaranteed sparsity.
On my poster, I will briefly explain the algorithm, provide a proof of convergence for the classical $N = 2$ marginal case, and demonstrate a numerical application for second-order interpolations on the Wasserstein space.
Joint work with Gero Friesecke (Technische Universität München, Germany).
Minimax estimation of discontinuous optimal transport maps: The semi-discrete case
Aram-Alexandre Pooladian
New York University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
We consider the problem of estimating the optimal transport map between two probability distributions, $P$ and $Q$ in $\mathbb{R}^d$, on the basis of i.i.d. samples. All existing statistical analyses of this problem require the assumption that the transport map is Lipschitz, a strong requirement that, in particular, excludes any examples where the transport map is discontinuous. As a first step towards developing estimation procedures for discontinuous maps, we consider the important special case where the data distribution $Q$ is a discrete measure supported on a finite number of points in $\mathbb{R}^d$. We study a computationally efficient estimator initially proposed by (Pooladian and Niles-Weed, 2021), based on entropic optimal transport, and show in the semi-discrete setting that it converges at the minimax-optimal rate $n^{-1/2}$, independent of dimension. Other standard map estimation techniques both lack finite-sample guarantees in this setting and provably suffer from the curse of dimensionality. We confirm these results in numerical experiments, and provide experiments for other settings, not covered by our theory, which indicate that the entropic estimator is a promising methodology for other discontinuous transport map estimation problems.
References: Pooladian, A-A., and Niles-Weed, J. "Entropic estimation of optimal transport maps", arXiv preprint arXiv:2109.12004, 2021
Joint work with Vincent Divol (Ceremade, Université Paris Dauphine-PSL, France) and Jonathan Niles-Weed (New York University, USA).
Using optimal transport to define viscosity solutions of control problems
Averil Prost
INSA Rouen, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We consider optimal control problems over the Wasserstein space. On the one hand, there is now a stable theory of absolutely continuous curves of measures, characterized as the solutions of the continuity equation. In particular, for sufficiently regular dynamics, the trajectories enjoy a nice representation as the pushforward through the semigroup of the underlying ODE. On the other hand, control problems are naturally linked to the viscosity solutions of Hamilton-Jacobi (HJ) equations. Our aim is to contribute to the extension of the viscosity theory over the Wasserstein space. We explore the choice of a particular set of test functions, including the squared distance, that allows us to obtain a weak comparison principle and verify that the value function of the control problem is the unique Lipschitz and bounded solution of the corresponding HJ equation. In addition, this choice bears strong links with subdifferential notions of the literature.
Joint work with Othmane Jerhaoui (INSA Rouen, France) and Hasnaa Zidani (INSA Rouen, France).
An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
Guillaume Wang
EPFL, Switzerland - This email address is being protected from spambots. You need JavaScript enabled to view it.
We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust learning. In those applications, the strategy sets are high-dimensional and thus methods based on discretisation cannot tractably return high-accuracy solutions.
In this paper, we introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem. This method consists in parametrizing the mixed strategies as atomic measures and applying proximal point updates to both the atoms' weights and positions. It can be interpreted as a time-implicit discretization of the "interacting" Wasserstein-Fisher-Rao gradient flow.
We prove that, under non-degeneracy assumptions, this method converges at an exponential rate to the exact mixed Nash equilibrium from any initialization satisfying a natural notion of closeness to optimality. We illustrate our results with numerical experiments and discuss applications to max-margin and distributionally-robust classification using two-layer neural networks, where our method has a natural interpretation as a simultaneous training of the network's weights and of the adversarial distribution.
Joint work with Lénaïc Chizat (EPFL, Switzerland).