Author: "Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN)"' showing total 193 results

Start Over Author "Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN)"

193 results on '"Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN)"'

1. On Representer Theorems and Convex Regularization

Author: Vincent Duval, Yohann De Castro, Antonin Chambolle, Claire Boyer, Pierre Weiss, Frédéric de Gournay, Département de Mathématiques et Applications - ENS Paris ( DMA ), École normale supérieure - Paris ( ENS Paris ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Probabilités, Statistique et Modélisation ( LPSM UMR 8001 ), Université Paris Diderot - Paris 7 ( UPD7 ) -Sorbonne Université-Centre National de la Recherche Scientifique ( CNRS ), Centre de Mathématiques Appliquées - Ecole Polytechnique ( CMAP ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Mathématiques d'Orsay ( LMO ), Université Paris-Saclay-Centre National de la Recherche Scientifique ( CNRS ), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales ( MOKAPLAN ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Toulouse UMR5219 ( IMT ), Université Toulouse 1 Capitole ( UT1 ) -Université Toulouse - Jean Jaurès ( UT2J ) -Université Toulouse III - Paul Sabatier ( UPS ), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-PRES Université de Toulouse-Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Centre National de la Recherche Scientifique ( CNRS ), Institut des Technologies Avancées en sciences du Vivant ( ITAV ), Centre National de la Recherche Scientifique ( CNRS ), Département de Mathématiques et Applications - ENS Paris (DMA), École normale supérieure - Paris (ENS Paris)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Institut des Technologies Avancées en sciences du Vivant (ITAV), Université Toulouse III - Paul Sabatier (UT3), The work of Antonin Chambolle was partially supported by a grant of the Simons Foundation., Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Laboratoire de Probabilités, Statistiques et Modélisations (LPSM (UMR_8001)), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Toulouse (UT)-Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), and École normale supérieure - Paris (ENS Paris)
Subjects: FOS: Computer and information sciences, Inverse problems, [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Class (set theory), Computer Science - Information Theory, 0211 other engineering and technologies, 010103 numerical & computational mathematics, 02 engineering and technology, [ MATH.MATH-IT ] Mathematics [math]/Information Theory [math.IT], 01 natural sciences, Theoretical Computer Science, FOS: Mathematics, Applied mathematics, 0101 mathematics, Extreme point, Mathematics - Optimization and Control, Mathematics, Representer theorem, Total variation, 021103 operations research, Vector space, Information Theory (cs.IT), Regular polygon, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], Extension (predicate logic), Inverse problem, Optimization and Control (math.OC), Convex regularization, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Convex function, Software
Abstract: International audience; We establish a general principle which states that regularizing an inverse problem with a convex function yields solutions which are convex combinations of a small number of atoms. These atoms are identified with the extreme points and elements of the extreme rays of the regularizer level sets. An extension to a broader class of quasi-convex regularizers is also discussed. As a side result, we characterize the minimizers of the total gradient variation, which was still an unresolved problem.
Published: 2018

2. Regularity of solutions of the Stein equation and rates in the multivariate central limit theorem

Author: Gallouët , Thomas, Mijoule , Guillaume, Swan , Yvik, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département de Mathématiques [Liège], Université de Liège, FNRS under Grant MIS F.4539.16., Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales ( MOKAPLAN ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, and Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria )
Subjects: Probability (math.PR), Mathematics - Statistics Theory, Statistics Theory (math.ST), [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], [ MATH.MATH-AP ] Mathematics [math]/Analysis of PDEs [math.AP], Mathematics - Analysis of PDEs, Mathematics::Probability, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, AMS subjects classification. 60F05, 35B65, 35J15, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Stein's method, [ MATH.MATH-ST ] Mathematics [math]/Statistics [math.ST], [ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR], Berry-esseen bounds, Mathematics - Probability, Analysis of PDEs (math.AP), Elliptic regularity
Abstract: Consider the multivariate Stein equation $\Delta f - x\cdot \nabla f = h(x) - E h(Z)$, where $Z$ is a standard $d$-dimensional Gaussian random vector, and let $f\_h$ be the solution given by Barbour's generator approach. We prove that, when $h$ is $\alpha$-H\"older ($0
Published: 2018

3. Variational methods in imaging and geometric control

Author: Thomas Haberkorn, Gabriel Peyré, Jean-Baptiste Caillau, Maïtine Bergounioux, Christoph Schnörr, Mathématiques - Analyse, Probabilités, Modélisation - Orléans (MAPMO), Université d'Orléans (UO)-Centre National de la Recherche Scientifique (CNRS), Mathematics for Control, Transport and Applications (McTAO), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Université de Bourgogne (UB)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Heidelberg University, Centre National de la Recherche Scientifique (CNRS)-Université d'Orléans (UO), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Caillau, Jean-Baptiste, Mathématiques - Analyse, Probabilités, Modélisation - Orléans ( MAPMO ), Université d'Orléans ( UO ) -Centre National de la Recherche Scientifique ( CNRS ), Mathematics for Control, Transport and Applications ( McTAO ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Institut de Mathématiques de Bourgogne [Dijon] ( IMB ), Université de Bourgogne ( UB ) -Centre National de la Recherche Scientifique ( CNRS ), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales ( MOKAPLAN ), CEntre de REcherches en MAthématiques de la DEcision ( CEREMADE ), Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ) -Inria de Paris, Université Paris-Dauphine-Centre National de la Recherche Scientifique ( CNRS ), and Heidelberg University, Heidelberg
Subjects: [ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Geometric control, Applied mathematics, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: International audience
Published: 2017

4. Convergence rate of entropy-regularized multi-marginal optimal transport costs

Author: Nenna, Luca, Pegon, Paul, Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011)
Subjects: Primary: 49Q22, Secondary: 49N15, 94A17, 49K40, Entropic regularization, Schrödinger problem, Multi-marginal optimal transport, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Functional Analysis (math.FA), Convex analysis, Mathematics - Functional Analysis, Mathematics - Analysis of PDEs, Optimization and Control (math.OC), Optimal transport, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, 49Q22, 49N15, 94A17, 49K40, Analysis of PDEs (math.AP)
Abstract: 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 locally semi-concave costs for a finer estimate, 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 in the two marginals case and for non-degenerate costs. We obtain in particular matching bounds in some typical situations where the optimal plan is deterministic.
Published: 2023

5. Stability of optimal shapes and convergence of thresholding algorithms in linear and spectral optimal control problems: Supplementary material

Author: Chambolle, Antonin, Mazari-Fouquer, Idriss, Privat, Yannick, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Recherche Mathématique Avancée (IRMA), Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), TOkamaks and NUmerical Simulations (TONUS), Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), and ANR-18-CE40-0013,SHAPO,Optimisation de forme(2018)
Subjects: Quantitative inequalities, 49M05, 49M41, 49N05, 49Q10, Thresholding scheme AMS classification: 49M05, Convergence analysis, Numerical algorithms in optimal control, PDE constrained optimisation, Shape optimisation, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract: We address the convergence of thresholding schemes for spectral optimisation problems and linear control problems.
Published: 2023

6. A mean field model for the interactions between firms on the markets of their inputs

Author: Yves Achdou, Guillaume Carlier, Quentin Petit, Daniela Tonon, Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), EDF R&D (EDF R&D), EDF (EDF), Università degli Studi di Padova = University of Padua (Unipd), All the authors were partially supported by the ANR (Agence Nationale de la Recherche) through MFG project ANR-16-CE40-0015-01.Y.A. acknowledges partial support from the Chair Finance and Sustainable Development and the FiME Lab (Institut Europlace de Finance) . G.C. acknowledges the support of the Lagrange Mathematics and Computing Research Center., and ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016)
Subjects: Heterogeneous agents, Interactions betwen firms, Factors of production, Long term equilibria, State constraints, Statistics and Probability, Mathematics - Analysis of PDEs, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Statistics, Probability and Uncertainty, Finance, Analysis of PDEs (math.AP)
Abstract: International audience; We consider an economy made of competing firms which are heterogeneous in their capital and use several inputs for producing goods. Their consumption policy is fixed rationally by maximizing a utility and their capital cannot fall below a given threshold (state constraint). We aim at modeling the interactions between firms on the markets of the different inputs on the long term. The stationary equlibria are described by a system of coupled non-linear differential equations: a Hamilton-Jacobi equation describing the optimal control problem of a single atomistic firm; a continuity equation describing the distribution of the individual state variable (the capital) in the population of firms; the equilibria on the markets of the production factors. We prove the existence of equilibria under suitable assumptions.
Published: 2023

7. Entropic Optimal Transport Solutions of the Semigeostrophic Equations

Author: Benamou, Jean-David, Cotter, Colin, Malamut, Hugo, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Imperial College London
Subjects: 2000 MSC: 78A46, 49Q22, 65K10, [MATH]Mathematics [math]
Abstract: The Semigeostrophic equations are a frontogenesis model in atmospheric science. Existence of solutions both from the theoretical and numerical point of view is given under a change of variable involving the interpretation of the pressure gradient as an Optimal Transport map between the density of the fluid and its push forward. Thanks to recent advances in numerical Optimal Transportation, the computation of large scale discrete approximations can be envisioned. We study here the use of Entropic Optimal Transport and its Sinkhorn algorithm companion.
Published: 2023

8. Stochastic Primal Dual Hybrid Gradient Algorithm with Adaptive Step-Sizes

Author: Chambolle, Antonin, Delplancke, Claire, Ehrhardt, Matthias, Schönlieb, Carola-Bibiane, Tang, Junqi, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), EDF R&D (EDF R&D), EDF (EDF), Department of Mathematical Sciences [Bath], University of Bath [Bath], Department of Applied Mathematics and Theoretical Physics [Cambridge] (DAMTP), Faculty of mathematics Centre for Mathematical Sciences [Cambridge] (CMS), University of Cambridge [UK] (CAM)-University of Cambridge [UK] (CAM), School of Mathematics [Birmingham], University of Birmingham [Birmingham], MJE acknowledges support from the EPSRC (EP/S026045/1, EP/T026693/1, EP/V026259/1) and the Leverhulme Trust (ECF-2019-478)., and CBS acknowledges support from the Philip Leverhulme Prize, the Royal Society Wolfson Fellowship, the EPSRC advanced career fellowship EP/V029428/1, EPSRC grants EP/S026045/1 and EP/T003553/1, EP/N014588/1, EP/T017961/1, the Wellcome Innovator Awards 215733/Z/19/Z and 221633/Z/20/Z, the European Union Horizon 2020 research and innovation programme under the Marie Skodowska-Curie grant agreement No. 777826 NoMADS, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute.
Subjects: 47N10, 49J40, 65D18, 65K10, 90C06, 90C15, 90C25, 92C55, 94A08, Optimization and Control (math.OC), FOS: Mathematics, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: In this work we propose a new primal-dual algorithm with adaptive step-sizes. The stochastic primal-dual hybrid gradient (SPDHG) algorithm with constant step-sizes has become widely applied in large-scale convex optimization across many scientific fields due to its scalability. While the product of the primal and dual step-sizes is subject to an upper-bound in order to ensure convergence, the selection of the ratio of the step-sizes is critical in applications. Up-to-now there is no systematic and successful way of selecting the primal and dual step-sizes for SPDHG. In this work, we propose a general class of adaptive SPDHG (A-SPDHG) algorithms, and prove their convergence under weak assumptions. We also propose concrete parameters-updating strategies which satisfy the assumptions of our theory and thereby lead to convergent algorithms. Numerical examples on computed tomography demonstrate the effectiveness of the proposed schemes., 28 pages, 8 figures
Published: 2023

9. A free discontinuity approach to optimal profiles in Stokes flows

Author: Bucur, Dorin, Chambolle, Antonin, Giacomini, Alessandro, Nahon, Mickaël, Laboratoire de Mathématiques (LAMA), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Matematica [Universita di Brescia], Università degli Studi di Brescia = University of Brescia (UniBs), Max-Planck-Institut für Mathematik in den Naturwissenschaften (MPI-MiS), Max-Planck-Gesellschaft, and Bucur, Dorin
Subjects: 49Q10, 76D07, 76D55, 35R35, Free discontinuity problems, Mathematics - Analysis of PDEs, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], Stokes flow, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AP] Mathematics [math]/Analysis of PDEs [math.AP], Navier boundary conditions, Drag, Analysis of PDEs (math.AP)
Abstract: In this paper we study obstacles immerged in a Stokes flow with Navier boundary conditions. We prove the existence and regularity of an obstacle with minimal drag, among all shapes of prescribed volume and controlled surface area, taking into account that these shapes may naturally develop geometric features of codimension 1. The existence is carried out in the framework of free discontinuity problems and leads to a relaxed solution in the space of special functions of bounded deformation (SBD). In dimension 2, we prove that the solution is classical.
Published: 2023

10. 1d approximation of measures in Wasserstein spaces

Author: Chambolle, Antonin, Duval, Vincent, Machado, Joao Miguel, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019)
Subjects: Mathematics - Analysis of PDEs, optimal transport, geometric measure theory, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 1D shape optimization, Analysis of PDEs (math.AP)
Abstract: We propose a variational approach to approximate measures with measures uniformly distributed over a 1 dimentional set. The problem consists in minimizing a Wasserstein distance as a data term with a regularization given by the length of the support. As it is challenging to prove existence of solutions to this problem, we propose a relaxed formulation, which always admits a solution. In the sequel we show that if the ambient space is $\mathbb{R}^2$ , under techinical assumptions, any solution to the relaxed problem is a solution to the original one. Finally we manage to prove that any optimal solution to the relaxed problem, and hence also to the original, is Ahlfors regular.; 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 admets toujours des solutions. En suite nous montrons que si l'space 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.
Published: 2023
Full Text: View/download PDF

11. Wasserstein medians: robustness, PDE characterization and numerics

Author: Carlier, Guillaume, Chenchene, Enis, Eichinger, Katharina, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Karl-Franzens-Universität Graz, Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), European Project: 861137,TraDE-OPT(2020), and European Project: 754362,MathInParis(2017)
Subjects: FOS: Computer and information sciences, Duality, Douglas-Rachford splitting method, p-Laplace system approximation, Statistics - Applications, Mathematics - Analysis of PDEs, Optimization and Control (math.OC), Optimal transport, FOS: Mathematics, Applications (stat.AP), Beckmann's problem, [MATH]Mathematics [math], Mathematics - Optimization and Control, Wasserstein medians, Analysis of PDEs (math.AP)
Abstract: We investigate the notion of Wasserstein median as an alternative to the Wasserstein barycenter, which has become popular but may be sensitive to outliers. In terms of robustness to corrupted data, we indeed show that Wasserstein medians have a breakdown point of approximately $\frac{1}{2}$. We give explicit constructions of Wasserstein medians in dimension one which enable us to obtain $L^p$ estimates (which do not hold in higher dimensions). We also address dual and multimarginal reformulations. In convex subsets of $\mathbb{R}^d$, we connect Wasserstein medians to a minimal (multi) flow problem \`a la Beckmann and a system of PDEs of Monge-Kantorovich-type, for which we propose a $p$-Laplacian approximation. Our analysis eventually leads to a new numerical method to compute Wasserstein medians, which is based on a Douglas-Rachford scheme applied to the minimal flow formulation of the problem., Comment: 38 pages, 6 figures
Published: 2023
Full Text: View/download PDF

12. Régularisation par la variation totale pour la reconstruction d'images constantes par morceaux : identification du support et méthodes numériques sans grille

Author: Petit, Romain, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Vincent Duval, and Yohann De Castro
Subjects: Inverse problems, Total variation, Variation totale, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Problèmes inverses, Parcimonie, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Sparsity
Abstract: This thesis is devoted to the recovery of piecewise constant images from noisy linear measurements. We aim at analyzing variational reconstruction methods based on total (gradient) variation regularization. The total variation functional has been extensively used in imaging since the 90's. Its minimization is known to produce piecewise constant images, which hence have some kind of sparsity (they can be decomposed as the superposition of a few simple shapes). However, the performance of this regularizer has to our knowledge not extensively been studied from a sparse recovery viewpoint. This thesis aims at bridging this gap.We first focus on noise robustness results. We assume that sought-after image is sparse, and study the structure of reconstructions in a low noise regime: are they sparse, made of the same number of shapes, and are these shapes close to those appearing in the unknown image? We then turn to numerical methods for total variation regularization. Existing techniques rely on the introduction of a fixed spatial discretization, which often yield reconstruction artifacts such as anisotropy or blur. We propose an algorithm which does not suffer from this grid bias, and produces a sparse representation of the reconstructed image.; On s'intéresse dans cette thèse à une famille de problèmes inverses, qui consistent à reconstruire une image à partir de mesures linéaires possiblement bruitées. On cherche à analyser les méthodes de reconstruction variationnelles utilisant un régulariseur spécifique, la variation totale (du gradient). Cette fonctionnelle est utilisée en imagerie depuis les travaux de Rudin Osher et Fatemi, menés en 1992. Alors qu'il est bien connu que sa minimisation produit des images constantes par morceaux, présentant une forme de parcimonie (elles sont composées d'un petit nombre de formes simples), ce point de vue n'a à notre connaissance pas été privilégié pour analyser les performances de ce régulariseur. Dans cette thèse, on se propose de mener cette étude. Dans un premier temps, on considère les reconstructions obtenues par minimisation de la variation totale dans un régime de faible bruit, et on étudie leur proximité avec l'image inconnue. Puisque cette dernière est supposée parcimonieuse, on s'intéresse particulièrement à la structure de la reconstruction: est-elle elle-même parcimonieuse, est-elle composée du même nombre de formes, et ces formes sont-elles proches de celles présentes dans l'image inconnue ? Dans une seconde partie, on propose une méthode numérique pour résoudre les problèmes variationnels associés à ce régulariseur. On introduit un algorithme ne reposant pas sur l'introduction d'une discrétisation spatiale fixe. Ceci a l'avantage, contrairement aux techniques existantes, de n'introduire ni flou ni anisotropie dans les images reconstruites, et d'en produire une représentation parcimonieuse.
Published: 2022

13. Wasserstein interpolation with constraints and application to a parking problem

Author: Buttazzo, Giuseppe, Carlier, Guillaume, Eichinger, Katharina, Dipartimento di Matematica [Pisa], University of Pisa - Università di Pisa, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), The ﬁrst author is member of the Gruppo Nazionale per l’Analisi Matematica, la Probabilita e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM), his work is part of the project 2017TEXA3H 'Gradient ﬂows, Optimal Transport and Metric Measure Structures' funded by the Italian Ministry of Research and University. This work was initiated during a visit of GC and KE at the Dipartimento di Matematica of the University of Pisa, the hospitality of this institution is gratefully acknowledged as well as the support from the Agence Nationale de la Recherche through the project MAGA (ANR-16-CE40-0014). G.C. acknowledges the support of the Lagrange Mathematics and Computing Research Center. KE acknowledges that this project has received fund-ing from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 754362., ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), Eichinger, Katharina, and Monge-Ampère et Géométrie Algorithmique - - MAGA2016 - ANR-16-CE40-0014 - AAPG2016 - VALID
Subjects: 49Q22, 49J45, 49M29, 49K99, Optimization and Control (math.OC), Optimal parking regions, FOS: Mathematics, Optimal transport, Measure interpolation, [MATH] Mathematics [math], Wasserstein distance, 2010 Mathematics Subject Classiﬁcation: 49Q22, 49J45, 49M29, 49K99, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: We consider optimal transport problems where the cost for transporting a given probability measure $\mu_0$ to another one $\mu_1$ consists of two parts: the first one measures the transportation from $\mu_0$ to an intermediate (pivot) measure $\mu$ to be determined (and subject to various constraints), and the second one measures the transportation from $\mu$ to $\mu_1$. This leads to Wasserstein interpolation problems under constraints for which we establish various properties of the optimal pivot measures $\mu$. Considering the more general situation where only some part of the mass uses the intermediate stop leads to a mathematical model for the optimal location of a parking region around a city. Numerical simulations, based on entropic regularization, are presented both for the optimal parking regions and for Wasserstein constrained interpolation problems., Comment: 30 pages, 7 figures
Published: 2022

14. A general compactness theorem in G(S)BD

Author: Chambolle, Antonin, Crismale, Vito, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Matematica 'Guido Castelnuovo' [Roma I] (Sapienza University of Rome), and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)
Subjects: [PHYS.COND.CM-MS]Physics [physics]/Condensed Matter [cond-mat]/Materials Science [cond-mat.mtrl-sci], [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA]
Abstract: We give a new, simpler proof of a compactness result in GSBDp , p > 1, by the same authors, which is also valid in GBD (the case p = 1), and shows that bounded sequences converge a.e., after removal of a suitable sequence of piecewise innitesimal rigid motions, subject to a fixed partition.
Published: 2022

15. L1-Gradient Flow of Convex Functionals

Author: Chambolle, Antonin, Novaga, Matteo, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Dipartimento di Matematica [Pisa], University of Pisa - Università di Pisa, and Chambolle, Antonin
Subjects: Mathematics - Functional Analysis, Mathematics - Analysis of PDEs, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-AP] Mathematics [math]/Analysis of PDEs [math.AP], Analysis of PDEs (math.AP), Functional Analysis (math.FA)
Abstract: We are interested in the gradient flow of a general first order convex functional with respect to the $L^1$-topology. By means of an implicit minimization scheme, we show existence of a global limit solution, which satisfies an energy-dissipation estimate, and solves a non-linear and non-local gradient flow equation, under the assumption of strong convexity of the energy. Under a monotonicity assumption we can also prove uniqueness of the limit solution, even though this remains an open question in full generality. We also consider a geometric evolution corresponding to the $L^1$-gradient flow of the anisotropic perimeter. When the initial set is convex, we show that the limit solution is monotone for the inclusion, convex and unique until it reaches the Cheeger set of the initial datum. Eventually, we show with some examples that uniqueness cannot be expected in general in the geometric case., Comment: 24 pages
Published: 2022

16. Lipschitz Continuity of the Schrödinger Map in Entropic Optimal Transport

Author: Carlier, Guillaume, Chizat, Lénaïc, Laborde, Maxime, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Polytechnique Fédérale de Lausanne (EPFL), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: Wasserstein gradient flows, 49Q22, 49K40, 35A15, Optimization and Control (math.OC), Entropic Optimal Transport, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Schrödinger map, Analysis of PDEs (math.AP)
Abstract: The function that maps a family of probability measures to the solution of the dual entropic optimal transport problem is known as the Schrödinger map. We prove that when the cost function is $\mathcal{C}^{k+1}$ with $k\in \mathbb{N}^*$ then this map is Lipschitz continuous from the $L^2$-Wasserstein space to the space of $\mathcal{C}^k$ functions. Our result holds on compact domains and covers the multi-marginal case. As applications, we prove displacement smoothness of the entropic optimal transport cost and the well-posedness of certain Wasserstein gradient flows involving this functional, including the Sinkhorn divergence and a multi-species system.
Published: 2022

17. A simple city equilibrium model with an application to teleworking

Author: Achdou, Yves, Carlier, Guillaume, Petit, Quentin, Tonon, Daniela, Université Sorbonne Paris Cité (USPC), Centre National de la Recherche Scientifique (CNRS), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), EDF R&D (EDF R&D), EDF (EDF), Università degli Studi di Padova = University of Padua (Unipd), All the authors were partially supported by the ANR (Agence Nationale de la Recherche) through MFG project ANR-16-CE40-0015-01. Y.A. and Q.P. acknowledge partial support from the Chair Finance and Sustainable Development and the FiME Lab (Institut Europlace de Finance). G.C. acknowledges the support of the Lagrange Mathematics and Computing Research Center., and ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016)
Subjects: Optimization and Control (math.OC), Teleworking, FOS: Mathematics, MS Classiﬁcation: 90B85, 49Q22, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Spatial equilibria, Mathematics - Optimization and Control
Abstract: We propose a simple semi-discrete spatial model where rents, wages and the density of population in a city can be deduced from free-mobility and equilibrium conditions on the labour and residential housing markets. We prove existence and (under stronger assumptions) uniqueness of the equilibrium. We extend our model to the case where teleworking is introduced. We present numerical simulations which shed light on the effect of teleworking on the structure of the city at equilibrium.
Published: 2022

18. Faces et points extrémaux des ensembles convexes pour la résolution des problèmes inverses

Author: Duval, Vincent, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole doctorale SDOSE, and Guillaume Carlier
Subjects: Inverse problems, Points extrémaux, Total variation, Extreme points, Variational methods, Variation totale, Problèmes inverses, Radon measures, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mesures de Radon, [MATH]Mathematics [math], Méthodes variationnelles, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Published: 2022

19. Stability of Semi-Dual Unbalanced Optimal Transport: fast statistical rates and convergent algorithm

Author: Vacher, Adrien, Vialard, François-Xavier, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel
Subjects: [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST]
Abstract: In this paper, we derive stability results for the semi-dual formulation of unbalanced optimal transport. From a statistical point of view, the gain of stability with respect to the balanced case allows to employ localization arguments while only assuming strong convexity of potentials and recover superparametric rates. Then we derive a provably convergent theoretical algorithm to minimize the semi-dual: if the potentials are constrained to be strongly convex, both the values and minimizers converge at a 1/k rate. Under an additional smoothness assumption, the convergence is exponential in the balanced case. Finally we instantiate a tractable version of our theoretical algorithm in the case of strongly convex, possibly smooth potentials. We benchmark the method in the balanced case on a 2D experiment and in the unbalanced case on a medium dimension synthetic experiment.
Published: 2022

20. Convergence rate of general entropic optimal transport costs

Author: Guillaume Carlier, Paul Pegon, Luca Tamanini, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Bocconi University [Milan, Italy], Bocconi Institute for Data Science and Analytics (BIDSA), and G.C. acknowledges the support of the Lagrange Mathematics and Computing Research Center.
Subjects: convex analysis, Applied Mathematics, Schrödinger problem, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Functional Analysis (math.FA), entropic regularization, Settore MAT/05 - ANALISI MATEMATICA, 2020 Mathematics Subject Classification. Primary: 49Q22, Secondary: 49N15, 94A17, 49K40, Mathematics - Functional Analysis, Mathematics - Analysis of PDEs, optimal transport, Optimization and Control (math.OC), Entropy dimension, entropy dimension, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, 49Q22 (Primary) 49N15, 94A17, 49K40 (Secondary), Analysis, Analysis of PDEs (math.AP)
Abstract: We investigate the convergence rate of the optimal entropic cost $v_\varepsilon$ to the optimal transport cost as the noise parameter $\varepsilon \downarrow 0$. We show that for a large class of cost functions $c$ on $\mathbb{R}^d\times \mathbb{R}^d$ (for which optimal plans are not necessarily unique or induced by a transport map) and compactly supported and $L^{\infty}$ marginals, one has $v_\varepsilon-v_0= \frac{d}{2} \varepsilon \log(1/\varepsilon)+ O(\varepsilon)$. Upper bounds are obtained by a block approximation strategy and an integral variant of Alexandrov's theorem. Under an infinitesimal twist condition on $c$, i.e. invertibility of $\nabla_{xy}^2 c(x,y)$, we get the lower bound by establishing a quadratic detachment of the duality gap in $d$ dimensions thanks to Minty's trick.
Published: 2022

21. Fenchel-Young inequality with a remainder and applications to convex duality and optimal transport

Author: Carlier, Guillaume, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Mathematics::Functional Analysis, Tilted convex duality, Mathematics::Optimization and Control, Brøndsted-Rockafellar theorem, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Fenchel-Young inequality in quantitative form, Stability of optimal transport
Abstract: This short note is devoted to some applications of a simple quantitative form of the Fenchel-Young inequality in Hilbert spaces. Our initial motivation comes from a stability question in optimal transport. We derive from the quantitative form of the Fenchel-Young inequality a simple and constructive proof of the Brøndsted-Rockafellar theorem and a perturbed primal-dual attainment result in Hilbert spaces.
Published: 2022

22. Stability and upper bounds for statistical estimation of unbalanced transport potentials

Author: Vacher, Adrien, Vialard, François-Xavier, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel
Subjects: [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Mathematics - Statistics Theory, Statistics Theory (math.ST)
Abstract: In this note, we derive upper-bounds on the statistical estimation rates of unbalanced optimal transport (UOT) maps for the quadratic cost. Our work relies on the stability of the semi-dual formulation of optimal transport (OT) extended to the unbalanced case. Depending on the considered variant of UOT, our stability result interpolates between the OT (balanced) case where the semi-dual is only locally strongly convex with respect the Sobolev semi-norm H1 dot and the case where it is locally strongly convex with respect to the H 1 norm. When the optimal potential belongs to a certain class C with sufficiently low metric-entropy, local strong convexity enables us to recover super-parametric rates, faster than 1 / root n.
Published: 2022

23. Mass concentration in rescaled first order integral functionals

Author: Monteil, Antonin, Pegon, Paul, Laboratoire Analyse et Mathématiques Appliquées (LAMA), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), A. M. acknowledges support by Leverhulme grant RPG-2018-438., Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Pegon, Paul
Subjects: Relaxation, H-mass, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], semicontinuity, [MATH] Mathematics [math], convergence of measures, Functionals on measures, Mathematics - Analysis of PDEs, integral functionals, branched transport, Primary: 28A33, 49J45, 46E35, Secondary: 49Q20, 76T99, 49Q22, 49J10, Γ-convergence, Optimization and Control (math.OC), FOS: Mathematics, concentration-compactness, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-AP] Mathematics [math]/Analysis of PDEs [math.AP], [MATH]Mathematics [math], Mathematics - Optimization and Control, Cahn-Hilliard fluids, Analysis of PDEs (math.AP), Calculus of variations
Abstract: We consider first order local minimization problems of the form $\min \int_{\mathbb{R}^N}f(u,\nabla u)$ under a mass constraint $\int_{\mathbb{R}^N}u=m\in\mathbb{R}$. We prove that the minimal energy function $H(m)$ is always concave on $(-\infty,0)$ and $(0,+\infty)$, and that relevant rescalings of the energy, depending on a small parameter $\varepsilon$, $\Gamma$-converge in the weak topology of measures towards the $H$-mass, defined for atomic measures $\sum_i m_i\delta_{x_i}$ as $\sum_i H(m_i)$. We also consider space dependent Lagrangians $f(x,u,\nabla u)$, which cover the case of space dependent $H$-masses $\sum_i H(x_i,m_i)$, and also the case of a family of Lagrangians $(f_\varepsilon)_\varepsilon$ converging as $\varepsilon\to 0$. The $\Gamma$-convergence result holds under mild assumptions on $f$, and covers several situations including homogeneous $H$-masses in any dimension $N\geq 2$ for exponents above a critical threshold, and all concave $H$-masses in dimension $N=1$. Our result yields in particular the concentration of Cahn-Hilliard fluids into droplets, and is related to the approximation of branched transport by elliptic energies.
Published: 2022

24. Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems

Author: Antonin Chambolle, Juan Pablo Contreras, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universidad Adolfo Ibáñez [Santiago], and Juan Pablo Contreras was supported by a doctoral scholarship from ANID-PFCHA/Doctorado Nacional/2019-21190161
Subjects: Wasserstein barycenter, Primal-dual method, Optimization and Control (math.OC), FOS: Mathematics, Optimal transport, Saddle-point, General Medicine, General Chemistry, Mathematics - Optimization and Control, AMS subject classifications. 49Q22, 65Y20, 90C05, 90C06, 90C08, 90C47, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: International audience; This paper discusses the efficiency of Hybrid Primal-Dual (HPD) type algorithms to approximate solve discrete Optimal Transport (OT) and Wasserstein Barycenter (WB) problems, with and without entropic regularization. Our first contribution is an analysis showing that these methods yield state-of-the-art convergence rates, both theoretically and practically. Next, we extend the HPD algorithm with linesearch proposed by Malitsky and Pock in 2018 to the setting where the dual space has a Bregman divergence, and the dual function is relatively strongly convex to the Bregman's kernel. This extension yields a new method for OT and WB problems based on smoothing of the objective that also achieves state-of-the-art convergence rates. Finally, we introduce a new Bregman divergence based on a scaled entropy function that makes the algorithm numerically stable and reduces the smoothing, leading to sparse solutions of OT and WB problems. We complement our findings with numerical experiments and comparisons.
Published: 2022

25. Is interpolation benign for random forest regression?

Author: Arnould, Ludovic, Boyer, Claire, Scornet, Erwan, Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Mathematics - Statistics Theory, Statistics Theory (math.ST)
Abstract: Statistical wisdom suggests that very complex models, interpolating training data, will be poor at predicting unseen examples.Yet, this aphorism has been recently challenged by the identification of benign overfitting regimes, specially studied in the case of parametric models: generalization capabilities may be preserved despite model high complexity.While it is widely known that fully-grown decision trees interpolate and, in turn, have bad predictive performances, the same behavior is yet to be analyzed for Random Forests (RF).In this paper, we study the trade-off between interpolation and consistency for several types of RF algorithms. Theoretically, we prove that interpolation regimes and consistency cannot be achieved simultaneously for several non-adaptive RF.Since adaptivity seems to be the cornerstone to bring together interpolation and consistency, we study interpolating Median RF which are proved to be consistent in the interpolating regime. This is the first result conciliating interpolation and consistency for RF, highlighting that the averaging effect introduced by feature randomization is a key mechanism, sufficient to ensure the consistency in the interpolation regime and beyond.Numerical experiments show that Breiman's RF are consistent while exactly interpolating, when no bootstrap step is involved.We theoretically control the size of the interpolation area, which converges fast enough to zero, giving a necessary condition for exact interpolation and consistency to occur in conjunction.
Published: 2022

26. Stability in Gagliardo-Nirenberg-Sobolev inequalities: flows, regularity and the entropy method

Author: Bonforte, Matteo, Dolbeault, Jean, Nazaret, Bruno, Simonov, Nikita, Instituto de Ciencias Matemàticas [Madrid] (ICMAT), Universidad Carlos III de Madrid [Madrid] (UC3M)-Universidad Complutense de Madrid = Complutense University of Madrid [Madrid] (UCM)-Universidad Autónoma de Madrid (UAM)-Consejo Superior de Investigaciones Científicas [Madrid] (CSIC), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Université Paris 1 Panthéon-Sorbonne (UP1), Fédération Parisienne de Modélisation Mathématique (FP2M), Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Project MTM2017-85757-P (Ministry of Science and Innovation, Spain) and the Spanish Ministry of Science and Innovation, through the 'Severo Ochoa Programme for Centres of Excellence in R&D' (CEX2019-000904-S)E.U. H2020 MSCA programme, grant agreement 777822Project EFI (ANR-17-CE40-0030) of the French National Research Agency (ANR)Inria Mokaplan teamDIM Math-Innov of the Region Île-de-France, ANR-17-CE40-0030,EFI,Entropie, flots, inégalités(2017), and European Project: 777822,GHAIA(2017)
Subjects: intermediate asymptotics, Mathematics::Analysis of PDEs, fast diffusion equation, rates of convergence, stability, Harnack Principle, Hardy-Poincaré inequalities, spectral gap, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], self-similar Barenblatt solutions, asymptotic behavior, 2020 Mathematics Subject Classification.26D10, 46E35, 35K55, 49J40, 35B40, 49K20, 49K30, 35J20, Gagliardo-Nirenberg inequality, entropy methods
Abstract: Ce document contient hal-02887010, v1: Stability in Gagliardo-Nirenberg inequalities and hal-02887013, v1: Stability in Gagliardo-Nirenberg inequalities. Supplementary material, avec plusieurs additions dont: Chapitre 1 (variational methods) et Chapitre 6 (Sobolev's inequality).; International audience; The purpose of this work is to establish a quantitative and constructive stability result for a class of subcritical Gagliardo-Nirenberg-Sobolev inequalities which interpolates between the logarithmic Sobolev inequality and the standard Sobolev inequality (in dimension larger than three), or Onofri's inequality in dimension two. We develop a new strategy, in which the flow of the fast diffusion equation is used as a tool: a stability result in the inequality is equivalent to an improved rate of convergence to equilibrium for the flow. The regularity properties of the parabolic flow allow us to connect an improved entropy - entropy production inequality during an initial time layer to spectral properties of a suitable linearized problem which is relevant for the asymptotic time layer. Altogether, the stability in the inequalities is measured by a deficit which controls in strong norms (a Fisher information which can be interpreted as a generalized Heisenberg uncertainty principle) the distance to the manifold of optimal functions. The method is constructive and, for the first time, quantitative estimates of the stability constant are obtained, including in the critical case of Sobolev's inequality. To build the estimates, we establish a quantitative global Harnack principle and perform a detailed analysis of large time asymptotics by entropy methods.
Published: 2022

27. Stability of optimal traffic plans in the irrigation problem

Author: Antoine Prouff, Antonio De Rosa, Andrea Marchese, Maria Colombo, Paul Pegon, Ecole Polytechnique Fédérale de Lausanne (EPFL), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Department of mathematics/Dipartimento di Matematica [Univ. Trento], Università degli Studi di Trento (UNITN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Maria Colombo was partially supported by the Swiss National Science Foundation grant 200021_182565. Antonio De Rosa has been supported by the NSF DMS Grant No. 1906451. Andrea Marchese acknowledges partial support from GNAMPA-INdAM., Department of Mathematics [College Park], University of Maryland [College Park], University of Maryland System-University of Maryland System, Bocconi Institute for Data Science and Analytics (BIDSA), Bocconi University [Milan, Italy], Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, M. C. was partially supported by the Swiss National Science Foundation grant 200021_182565. A. D. R. has been supported by the NSF DMS Grant No. 1906451 and the NSF DMS Grant No. 2112311. A. M. acknowledges partial support from GNAMPA-INdAM. A.P. was supported by the Fondation Mathématiques Jacques Hadamard. P.P and A.P. both acknowledge EPFL for hosting them during the semester this paper was prepared., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)
Subjects: BRANCHED TRANSPORT, Mathematical optimization, Irrigation, TRAFFIC PLANS, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Stability (probability), symbols.namesake, Mathematics - Analysis of PDEs, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Computer Science::Networking and Internet Architecture, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Discrete Mathematics and Combinatorics, Limit (mathematics), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, TRANSPORTATION NETWORK, BRANCHED TRANSPORT, IRRIGATION PROBLEM, TRAFFIC PLANS, STABILITY, STABILITY, IRRIGATION PROBLEM, Applied Mathematics, TRANSPORTATION NETWORK, 010102 general mathematics, Eulerian path, Flow network, 010101 applied mathematics, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Lagrangian, Analysis of PDEs (math.AP)
Abstract: We prove the stability of optimal traffic plans in branched transport. In particular, we show that any limit of optimal traffic plans is optimal as well. This result goes beyond the Eulerian stability proved in [7], extending it to the Lagrangian framework.
Published: 2022

28. Model-based Clustering with Missing Not At Random Data

Author: Sportisse, Aude, Biernacki, Christophe, Boyer, Claire, Josse, Julie, Marbac Lourdelle, Matthieu, Celeux, Gilles, Laporte, Fabien, Université Côte d'Azur (UCA), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UNIV-RENNES), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Economie et Statistique [Bruz] (CREST), Université Lille Nord (France), MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé - UMR 8524 (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Sorbonne Université (SU), Laboratoire de Probabilités, Statistique et Modélisation (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Médecine de précision par intégration de données et inférence causale (PREMEDICAL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Desbrest de santé publique (IDESP), Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université de Montpellier (UM), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris-Saclay, Nantes Université (Nantes Univ), Institut du Thorax [Nantes], INSERM U649, Nantes, Institut National de la Santé et de la Recherche Médicale (INSERM), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), ANR-16-IDEX-0006,MUSE,MUSE(2016), Inria Lille - Nord Europe, Université Catholique de l'Ouest (UCO), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université de Rennes (UR), Laboratoire Paul Painlevé (LPP), Statistique mathématique et apprentissage (CELESTE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Laboratoire de Probabilités, Statistiques et Modélisations (LPSM (UMR_8001)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPC), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Statistics - Machine Learning, Missing Not At Random (MNAR) Data, Model-based Clustering, Machine Learning (stat.ML), Identifiability, EM and Stochastic EM Algorithms, Machine Learning (cs.LG), Medical Data
Abstract: In recent decades, technological advances have made it possible to collect large data sets. In this context, the model-based clustering is a very popular, flexible and interpretable methodology for data exploration in a well-defined statistical framework. One of the ironies of the increase of large datasets is that missing values are more frequent. However, traditional ways (as discarding observations with missing values or imputation methods) are not designed for the clustering purpose. In addition, they rarely apply to the general case, though frequent in practice, of Missing Not At Random (MNAR) values, i.e. when the missingness depends on the unobserved data values and possibly on the observed data values. The goal of this paper is to propose a novel approach by embedding MNAR data directly within model-based clustering algorithms. We introduce a selection model for the joint distribution of data and missing-data indicator. It corresponds to a mixture model for the data distribution and a general MNAR model for the missing-data mechanism, which may depend on the underlying classes (unknown) and/or the values of the missing variables themselves. A large set of meaningful MNAR sub-models is derived and the identifiability of the parameters is studied for each of the sub-models, which is usually a key issue for any MNAR proposals. The EM and Stochastic EM algorithms are considered for estimation. Finally, we perform empirical evaluations for the proposed submodels on synthetic data and we illustrate the relevance of our method on a medical register, the TraumaBase ® dataset.
Published: 2022

29. From geodesic extrapolation to a variational BDF2 scheme for Wasserstein gradient flows

Author: Gallouët, Thomas, Natale, Andrea, Todeschi, Gabriele, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut des Sciences de la Terre (ISTerre), Institut national des sciences de l'Univers (INSU - CNRS)-Institut de recherche pour le développement [IRD] : UR219-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel-Université Grenoble Alpes (UGA), TOG acknowledges the support of the french Agence Nationale de la Recherche through the project MAGA (ANR-16-CE40-0014). GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 754362. This work was supported in part by the Labex CEMPI (ANR-11-LABX-0007-01)., ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), and ANR-11-LABX-0007,CEMPI,Centre Européen pour les Mathématiques, la Physique et leurs Interactions(2011)
Subjects: Wasserstein gradient flows, Wasserstein extrapolation, Mathematics - Analysis of PDEs, BDF2, Optimal transport, FOS: Mathematics, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], MSC(2020): 49Q22, 35A15, 65M08, Mathematics - Numerical Analysis, Numerical Analysis (math.NA), [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Analysis of PDEs (math.AP)
Abstract: 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.
Published: 2022
Full Text: View/download PDF

30. A geometric Laplace method

Author: Léger, Flavien, Vialard, François-Xavier, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, F.L. was supported by ERC grant NORIA and by the French government under management of Agence Nationale de la Recherche, as part of the 'Investissements d’avenir' program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute). F.L. also received funding from the European Research Council under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement no. 866274).The work of F.-X. Vialard was partly supported by the Bézout Labex (New Monge Problems), funded by ANR, reference ANR-10-LABX-58., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), ANR-10-LABX-0058,Bézout,Models and algorithms: from the discrete to the continuous(2010), Léger, Flavien, PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID, and Laboratoires d'excellence - Models and algorithms: from the discrete to the continuous - - Bézout2010 - ANR-10-LABX-0058 - LABX - VALID
Subjects: Mathematics - Differential Geometry, Differential Geometry (math.DG), FOS: Mathematics, Mathematics - Statistics Theory, [MATH] Mathematics [math], Statistics Theory (math.ST), [MATH]Mathematics [math]
Abstract: A classical tool for approximating integrals is the Laplace method. The first-order, as well as the higher-order Laplace formula is most often written in coordinates without any geometrical interpretation. In this article, motivated by a situation arising, among others, in optimal transport, we give a geometric formulation of the first-order term of the Laplace method. The central tool is the Kim-McCann Riemannian metric which was introduced in the field of optimal transportation. Our main result expresses the first-order term with standard geometric objects such as volume forms, Laplacians, covariant derivatives and scalar curvatures of two different metrics arising naturally in the Kim-McCann framework. Passing by, we give an explicitly quantified version of the Laplace formula, as well as examples of applications.
Published: 2022
Full Text: View/download PDF

31. Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM

Author: Aubin-Frankowski, Pierre-Cyril, Korba, Anna, Léger, Flavien, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Nationale de la Statistique et de l'Analyse Economique (ENSAE), Ecole Nationale de la Statistique et de l'Analyse Economique, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, 49Q22, 90C25, Machine Learning (stat.ML), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract: International audience; Many problems in machine learning can be formulated as optimizing a convex functional over a vector space of measures. This paper studies the convergence of the mirror descent algorithm in this infinite-dimensional setting. Defining Bregman divergences through directional derivatives, we derive the convergence of the scheme for relatively smooth and convex pairs of functionals. Such assumptions allow to handle non-smooth functionals such as the Kullback--Leibler (KL) divergence. Applying our result to joint distributions and KL, we show that Sinkhorn's primal iterations for entropic optimal transport in the continuous setting correspond to a mirror descent, and we obtain a new proof of its (sub)linear convergence. We also show that Expectation Maximization (EM) can always formally be written as a mirror descent. When optimizing only on the latent distribution while fixing the mixtures parameters -- which corresponds to the Richardson--Lucy deconvolution scheme in signal processing -- we derive sublinear rates of convergence.
Published: 2022
Full Text: View/download PDF

32. Quantitative Stability of Barycenters in the Wasserstein Space

Author: Carlier, Guillaume, Delalande, Alex, Merigot, Quentin, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), G.C and Q.M. acknowledge the support of the Lagrange Mathematics and Computing Research Center and of the ANR (MAGA, ANR-16-CE40-0014), and ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016)
Subjects: [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Statistics Theory, Mathematics - Numerical Analysis, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Numerical Analysis (math.NA), Statistics Theory (math.ST), Mathematics - Optimization and Control, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: Wasserstein barycenters define averages of probability measures in a geometrically meaningful way. Their use is increasingly popular in applied fields, such as image, geometry or language processing. In these fields however, the probability measures of interest are often not accessible in their entirety and the practitioner may have to deal with statistical or computational approximations instead. In this article, we quantify the effect of such approximations on the corresponding barycenters. We show that Wasserstein barycenters depend in a H{\"o}lder-continuous way on their marginals under relatively mild assumptions. Our proof relies on recent estimates that quantify the strong convexity of the dual quadratic optimal transport problem and a new result that allows to control the modulus of continuity of the push-forward operation under a (not necessarily smooth) optimal transport map.
Published: 2022
Full Text: View/download PDF

33. Efficient preconditioners for solving dynamical optimal transport via interior point methods

Author: Facca, Enrico, Todeschi, Gabriele, Natale, Andrea, Benzi, Michele, Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Bergen (UiB), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut des Sciences de la Terre (ISTerre), Institut national des sciences de l'Univers (INSU - CNRS)-Institut de recherche pour le développement [IRD] : UR219-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel-Université Grenoble Alpes (UGA), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Scuola Normale Superiore di Pisa (SNS), This work was supported in part by the Labex CEMPI (ANR-11-LABX-0007-01), EF work was partially supported by EU MSCA project N°104109101(NIOT)., ANR-11-LABX-0007,CEMPI,Centre Européen pour les Mathématiques, la Physique et leurs Interactions(2011), Department of Mathematics and Computer Science [Emory University], and Emory University [Atlanta, GA]
Subjects: 35Q93, 49M41, 65K10, 65F08, 65F50, Optimization and Control (math.OC), FOS: Mathematics, Optimal transport, Saddle point problem, Benamou-Brenier formulation, Algebraic multigrid methods, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Mathematics - Optimization and Control, Preconditioners, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: In this paper we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer as $\boldsymbol{B}\boldsymbol{B}$-preconditioner. A series of numerical tests show that the $\boldsymbol{B}\boldsymbol{B}$-preconditioner is the most efficient among those presented, with a CPU-time scaling only slightly more than linearly with respect to the number of unknowns used to discretize the problem.
Published: 2022

34. Convex geometry of finite exchangeable laws and de Finetti style representation with universal correlated corrections

Author: Guillaume Carlier, Gero Friesecke, Daniela Vögler, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Zentrum Mathematik [Munchen] (TUM), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Technische Universität München [München] (TUM)
Subjects: Statistics and Probability, Hewitt-Savage theorem, 60G09, 52-XX, 90C06, Probability (math.PR), Multi-marginal optimal transport, Bayesian statistics, Finite exchangeability, Optimization and Control (math.OC), N-representability, de Finetti, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistics, Probability and Uncertainty, Choquet theory, Mathematics - Optimization and Control, Extremal measures, Analysis, Mathematics - Probability
Abstract: We present a novel analogue for finite exchangeable sequences of the de Finetti, Hewitt and Savage theorem and investigate its implications for multi-marginal optimal transport (MMOT) and Bayesian statistics. If $(Z_1,...,Z_N)$ is a finitely exchangeable sequence of $N$ random variables taking values in some Polish space $X$, we show that the law $\mu_k$ of the first $k$ components has a representation of the form $\mu_k=\int_{{\mathcal P}_{\frac{1}{N}}(X)} F_{N,k}(\lambda) \, \mbox{d} \alpha(\lambda)$ for some probability measure $\alpha$ on the set of $1/N$-quantized probability measures on $X$ and certain universal polynomials $F_{N,k}$. The latter consist of a leading term $N^{k-1}\! /{\small \prod_{j=1}^{k-1}(N\! -\! j)\, \lambda^{\otimes k}}$ and a finite, exponentially decaying series of correlated corrections of order $N^{-j}$ ($j=1,...,k$). The $F_{N,k}(\lambda)$ are precisely the extremal such laws, expressed via an explicit polynomial formula in terms of their one-point marginals $\lambda$. Applications include novel approximations of MMOT via polynomial convexification and the identification of the remainder which is estimated in the celebrated error bound of Diaconis-Freedman between finite and infinite exchangeable laws.
Published: 2021

35. SISTA: learning optimal transport costs under sparsity constraints

Author: Guillaume Carlier, Arnaud Dupuy, Alfred Galichon, Yifei Sun, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Luxembourg [Luxembourg], Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), NYU System (NYU), Département d'économie (Sciences Po) (ECON), Sciences Po (Sciences Po)-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)
Subjects: FOS: Computer and information sciences, Coordinate descent, 050208 finance, 05 social sciences, Inverse optimal transport, Methodology (stat.ME), Optimization and Control (math.OC), ISTA, 0502 economics and business, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], 050207 economics, Mathematics - Optimization and Control, Statistics - Methodology
Abstract: In this paper, we describe a novel iterative procedure called SISTA to learn the underlying cost in optimal transport problems. SISTA is a hybrid between two classical methods, coordinate descent ("S"-inkhorn) and proximal gradient descent ("ISTA"). It alternates between a phase of exact minimization over the transport potentials and a phase of proximal gradient descent over the parameters of the transport cost. We prove that this method converges linearly, and we illustrate on simulated examples that it is significantly faster than both coordinate descent and ISTA. We apply it to estimating a model of migration, which predicts the flow of migrants using country-specific characteristics and pairwise measures of dissimilarity between countries. This application demonstrates the effectiveness of machine learning in quantitative social sciences.
Published: 2021

36. Dynamical Programming for off-the-grid dynamic Inverse Problems

Author: Duval, Vincent, Tovey, Robert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), ANR-19-CE48-0017,CIPRESSI,Traitement d'images continues: modèles et algorithmes(2019), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: Optimization and Control (math.OC), FOS: Mathematics, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Mathematics - Optimization and Control
Abstract: In this work we consider algorithms for reconstructing time-varying data into a finite sum of discrete trajectories, alternatively, an off-the-grid sparse-spikes decomposition which is continuous in time. Recent work showed that this decomposition was possible by minimising a convex variational model which combined a quadratic data fidelity with dynamical Optimal Transport. We generalise this framework and propose new numerical methods which leverage efficient classical algorithms for computing shortest paths on directed acyclic graphs. Our theoretical analysis confirms that these methods converge to globally optimal reconstructions which represent a finite number of discrete trajectories. Numerically, we show new examples for unbalanced Optimal Transport penalties, and for balanced examples we are 100 times faster in comparison to the previously known method.; Dans cet article, nous considérons des algorithmes de reconstruction sans grille pour des mesures parcimonieuses à partir de données dynamiques. En particulier, le signal reconstruit est une somme finie de mesures de Dirac dont les positions et les amplitudes varient continûment. Des travaux récents ont montré qu'une telle décomposition était possible dans un cadre variationnel convexe qui combine une attache aux données quadratique avec la formulation dynamique du transport optimal. Nous généralisons ce cadre et proposons une nouvelle méthode numérique qui exploite des algorithmes efficaces classiques de plus court chemin sur des graphes acycliques orientés. Notre analyse théorique confirme que ces méthodes convergent vers des minimiseurs globaux. Nous illustrons ces méthodes sur des exemples nouveaux impliquant le transport optimal non-équilibré, et, pour le transport classique, notre méthode est près de 100 fois plus rapide que l'état de l'art.
Published: 2021

37. Entropic Unbalanced Optimal Transport: Application to Full-Waveform Inversion and Numerical Illustration

Author: Yu, Miao, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Paris, Jean-Pierre Vilotte, Jean-David Benamou, Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: Inversion de formes d’onde, Transport-optimal entropique non-équilibré, [SDU]Sciences of the Universe [physics], Unbalanced entropic optimal transport, Sinkhorn divergence, Full-waveform inversion, Divergence de Sinkhorn, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: Seismic tomography aims at inferring physical properties and reconstructing quantitatively the “model”, i.e. structures of the Earth interior, from the mechanical waves – radiated by natural and man-made seismic sources – that are recorded at the surface by receivers in the form of seis-mograms. Over the past decades, Full-Waveform inversion (FWI) has been actively developed in both academia and industry, and has proven to be a powerful tool that dramatically improved the capability to estimate physical properties and structures of various geological targets from global to local scales.Full-waveform inversion (FWI) is formulated as a nonlinear, PDE-based optimisation problem that is classically solved by iterative minimisation of an objective function – measuring the misÿt bet-ween synthetic and observed seismic waveforms – using adjoint-based solution methods. Adjoint-based solution methods allow the computation of the derivative of the objective function with respect to the model parameters by combining the synthetic forward waveÿeld and an adjoint waveÿeld governed by a set of adjoint equations and adjoint subsidiary conditions.In practice, however, solving FWI problems using local, nonlinear optimisation methods is facing challenges that preclude routine use. The quality of the inversion, simultaneously dealing with long and short wavelengths information, is degraded by the lack of low frequencies and also depends on a good starting model. These limitations are linked to the ill-posed nature of the inverse problem which can be easily trapped into a local minimum.One proposed research direction to reduce the dependency on the initial model, is to replace the classical least-squares based misÿt by other objective functions – possibly involving nonlinear transformation of the seismic signal –hence promoting the convexity and trying to enlarge the basin of attraction of the global minimum.Optimal Transport (OT) theory has recently been use in inverse problems and machine learning. Optimal Transport lifts the properties of the squared Euclidean distance to the space of probability distributions. The optimal value (squared) of the transport itself deÿnes a distance called the 2-Wasserstein distance. This quantity is again convex but now on the set of probability distributions.This trend is already active for FWI, this thesis is part of it. The OT approach is still largely open on three fronts : Seismic Waveforms are not probability distributions, lacking positivity and nor-malised total mass. Convexity with respect to the model is not guaranteed and ÿnally the actual computation of the OT distance is not cheap.In this work we use and combine – from an academic point of view – two recent extensions of OT in the context of FWI. First the “unbalanced” OT distance, which rigorously deÿnes a distance on the set of positive Radon measure thus by-passing the data normalisation issue (but not the positivity problem). Then, the entropic regularisation OT framework and in particular the simple and easy to compute variant called Sinkhorn divergence providing a good approximation of the 2-Wasserstein distance. The Sinkhorn divergence can be naturally extended to unbalanced OT.We use these tools to construct and implement our unbalanced OT misÿt and discuss its use in the context of full-waveform inversion through a number of academic examples and classical benchmark problems.; Les méthodes de tomographie sismique visent à inférer les propriétés physique et reconstruire le “modèle”, i.e. les structures de l’intérieur de la Terre, à partir des ondes mécaniques - radiées par des sources naturelles ou anthropogéniques - enregistrées par des récepteurs en surface sous la forme de sismogrammes. Les méthodes d’inversion de formes d’onde ont été activement déve-loppées dans les contextes académiques et industriels et sont devenus des outils puissants pour améliorer l’estimation des propriétés physiques et des structures d’objets géologiques depuis les échelles globales jusqu’aux échelles locales de la géophysique d’exploration.L’inversion de formes d’onde est formulée comme un problème d’optimisation non linéaire, as-socié à un système d’équations aux dérivées partielles. Il est classiquement résolu par des mé-thodes d’optimisation locale via la minimisation itérative d’une fonction coût qui mesure la di˙é-rence entre les sismogrammes observés et synthétiques, et utilisent des méthodes d’état adjoint. Les méthodes d’état adjoint permettent le calcul des dérivées de la fonction coût par rapport aux paramètres du modèle en combinant le champ d’onde direct et un champ d’onde adjoint gou-verné par un système d’équations adjointes et des conditions adjointes complémentaires.Les méthodes d’inversion de forme d’onde, qui inversent simultanément les courtes et grandes longueurs d’onde, sou˙rent malheureusement en pratique de di°cultés qui restreignent leur uti-lisation pratique. Leurs capacités se détériorent du fait du déÿcit en basse fréquence des obser-vations et d’un bon modèle initial. Des limitations qui sont associées à la nature mal posée du problème inverse qui peut facilement être piégé dans un minimum local.Une direction proposée, aÿn de réduire la dépendance vis à vis du modèle initial, est de rem-placer la fonction classique, basée sur une distance de type moindres carrés, par de nouvelles fonctions coûts, pouvant impliquer une transformation non linéaire du signal, aÿn de promouvoir la convexité et élargir le bassin d’attraction du minimum global.La théorie du Transport Optimal (OT) a récemment été utilisée dans le cadre des problèmes in-verses et de l’apprentissage automatique. Le transport optimal généralise les propriétés de la distance euclidienne au carré à l’espace des distributions de probabilité. La valeur optimale (au carré) du transport lui-même déÿnit une distance appelée distance 2-Wasserstein. Cette quantité est à nouveau convexe mais maintenant sur l’ensemble des distributions de probabilité.Le Transport Optimal est déjà utilisé en FWI, cette thèse en fait partie. L’approche OT est encore largement ouverte sur trois fronts : les formes d’onde sismiques ne sont ni positives ni de masse totale normalisée. La convexité par rapport au modèle n’est pas garantie et ÿnalement le calcul réel de la distance OT est coûteuse.Dans ce travail, nous utilisons et combinons - d’un point de vue académique - deux extensions ré-centes d’OT dans le contexte FWI. D’abord la distance OT “non-équilibrée”, qui déÿnit rigoureuse-ment une distance sur l’ensemble des mesures de Radon positives contournant ainsi le problème de normalisation des données (mais pas le problème de positivité). Puis le cadre du Transport Optimal entropique et en particulier la variante simple et facile à calculer appelée divergence de Sinkhorn fournissant une bonne approximation de la distance 2-Wasserstein. La divergence de Sinkhorn peut être naturellement étendue au transport “non-équilibré”.Nous utilisons ces outils pour construire et mettre en œuvre une fonction coût OT “non-équilibrée”. Nous discutons de son utilisation dans le contexte FWI au travers d’un certain nombre d’exemples académiques et de problèmes de référence classiques.
Published: 2021

38. A spatial Pareto exchange economy problem

Author: X. Bacon, G. Carlier, B. Nazaret, Statistique, Analyse et Modélisation Multidisciplinaire (SAmos-Marin Mersenne) (SAMM), Université Paris 1 Panthéon-Sorbonne (UP1), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, GC is grateful to the Agence Nationale de la Recherche for its support through the projects MAGA (ANR-16-CE40-0014) and MFG(ANR-16-CE40-0015-01)., ANR-16-CE40-0014,MAGA,Monge-Ampère et Géométrie Algorithmique(2016), ANR-16-CE40-0015,MFG,Jeux Champs Moyen(2016), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: TheoryofComputation_MISCELLANEOUS, Sinkhorn algorithm, Control and Optimization, Convex duality, Exchange economy Pareto optimality, Applied Mathematics, MESH: MS Classiﬁcation: 49Q22, 91B72, Second welfare theorem, Optimal transport, TheoryofComputation_GENERAL, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Entropic optimal transport
Abstract: We use convex duality techniques to study a spatial Pareto problem with transport costs and derive a spatial second welfare theorem. The existence of an integrable equilibrium distribution of quantities is nontrivial and established under general monotonicity assumptions. Our variational approach also enables us to give a numerical algorithmà la Sinkhorn and present simulations for equilibrium prices and quantities in one-dimensional domains and a network of French cities.
Published: 2021

39. Parameter tuning and model selection in optimal transport with semi-dual Brenier formulation

Author: Vacher, Adrien, Vialard, François-Xavier, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, and Université Gustave Eiffel
Subjects: [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Semi-dual, FOS: Mathematics, Optimal transport, Mathematics - Statistics Theory, Statistics Theory (math.ST), Model selection
Abstract: Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in a stochastic setting, where distributions are represented by samples and where the goal is to find the closest map to the ground truth OT map, unknown in practical settings. So far, no quantitative criterion has yet been put forward to tune the parameters of these models and select maps that best approximate the ground truth. To perform this task, we propose to leverage the Brenier formulation of OT.Theoretically, we show that this formulation guarantees that, up to sharp a distortion parameter depending on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimization, enables parameter tuning and model selection among entropic regularization of OT, input convex neural networks and smooth and strongly convex nearest-Brenier (SSNB) models.We also use this criterion to question the use of OT in Domain-Adaptation (DA). In a standard DA experiment, it enables us to identify the potential that is closest to the true OT map between the source and the target. Yet, we observe that this selected potential is far from being the one that performs best for the downstream transfer classification task.
Published: 2021

40. Finite volume approximation of optimal transport and Wasserstein gradient flows

Author: Todeschi, Gabriele, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), PSL Université Paris Dauphine, Jean-David Benamou, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Université Paris sciences et lettres, Clément Cancès, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: Wasserstein gradient flows, Optimization, Volumes finis, Transport optimal, Finite volumes, Optimal transport, Optimisation, [MATH]Mathematics [math], [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], Flots de gradient Wasserstein
Abstract: This thesis is devoted to the design of locally conservative and structure preserving schemes for Wasserstein gradient flows, i.e. steepest descent curves in the Wasserstein space. The time discretization is based on variational approaches that mimic at the discrete in time level the behavior of steepest descent curves. These discretizations involve the computation of the Wasserstein distance, an instance of optimal transport problem. The space discretization is based on Two-Point Flux Approximation (TPFA) finite volumes, a well-known methodology particularly suited for the discretization of partial differential equations that present a conservative structure. In order to preserve the variational structure at the discrete level, we follow a first discretize then optimize approach. We start by presenting TPFA discretizations for the Wasserstein distance based on the Benamou-Brenier dynamical formulation. We expose some stability issues related to these discetizations, propose a possible solution to overcome them and derive quantitative estimate on the convergence of the discrete model. To solve the discrete optimization problem, we introduce an interior point strategy. Then, we propose first and second order accurate schemes for Wasserstein gradient flows. At this level, to reduce the computational complexity, we use an implicit linearization of the Wasserstein distance. By taking adavantage of the monotonicity of the upwind reconstruction, we propose a first order scheme which can be efficiently solved with a Newton method and show its convergence towards distributional solutions of the Fokker-Planck equation. In order to higher the accuracy in space, we use a centered reconstruction, which requires a different optimization technique. We use again the interior point strategy for this purpose. Finally, we propose a modified variational BDF2 time discretization and prove its convergence towards Wasserstein gradient flows. Thanks to these new discretizations, we design a second order accurate scheme in both time and space. All our approaches are validated with several numerical results.; Cette thèse a pour objet la construction de schémas numériques localement conservatif et préservant la structure pour des flots de gradient Wasserstein, c’est à dire des courbes de descente maximale dans l’espace de Wasserstein. Les discrétisations en temps reposent sur des formulations variationnelles imitant au niveau discret ce comportement de courbes de descente maximale. Ces discrétisation font intervenir le calcul de la distance de Wasserstein, un exemple de problèmes de transport optimal. Les discrétisations en espaces sont basées sur des approximations volumes finis avec reconstructions à deux points des flux, également appelés schémas TPFA. Ces méthodes sont bien connues et particulièrement adaptées pour discrétiser des équations conservatives. Afin de conserver les structures variationnelles au niveau discret, notre approche est de d’abord discrétiser puis optimiser. Dans une première partie nous présentons des discrétisations TPFA pour la distance de Wasserstein, basées sur la formulation dynamique de Benamou-Brenier du transport optimal. Nous montrons des problèmes de stabilité liés à ces discrétisations et proposons une méthode permettant de les surmonter. Nous dérivons des estimations quantitatives de convergence pour ce model discret. Afin de résoudre le problème d'optimisation discret, nous introduisons une stratégie de point intérieur. Ensuite nous proposons des schémas d’ordre un puis deux pour des flots de gradients Wasserstein. Afin de réduire la complexité numérique des problèmes étudiés nous utilisons une linéarisation implicite de la distance de Wasserstein. En exploitant la monotonie de la reconstruction upwind, nous proposons un schéma d'ordre un que l'on peut résoudre efficacement avec une méthode de Newton et nous montrons sa convergence vers des solutions faibles de l'équation de Fokker-Planck. Pour augmenter l’ordre de convergence en espace, nous utilisons une reconstruction centrée qui nécessite une technique d’optimisation différente. Nous utilisons à nouveau la stratégie du point intérieur pour cela. Finalement, pour monter en ordre en temps, nous proposons une version modifiée de la discrétisation variationnelle BDF2 pour laquelle nous prouvons la convergence vers des flots de gradient Wasserstein. À l'aide de ces nouvelles discrétisations, nous construisons un schéma d'ordre deux en espace et en temps. Tous les schémas proposés sont accompagnés de nombreux résultats numériques.
Published: 2021

41. Convex transport potential selection with semi-dual criterion

Author: Vacher, Adrien, Vialard, François-Xavier, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Gustave Eiffel, Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel
Subjects: model selection, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Semi-dual, Optimal transport
Abstract: Over the past few years, numerous computational models have been developed to solve Optimal Transport (OT) in a stochastic setting, where distributions are represented by samples. In such situations, the goal is to find a transport map that has good generalization properties on unseen data, ideally the closest map to the ground truth, unknown in practical settings. However, in the absence of ground truth, no quantitative criterion has been put forward to measure its generalization performance although it is crucial for model selection. We propose to leverage the Brenier formulation of OT to perform this task. Theoretically, we show that this formulation guarantees that, up to a distortion parameter that depends on the smoothness/strong convexity and a statistical deviation term, the selected map achieves the lowest quadratic error to the ground truth. This criterion, estimated via convex optimization, enables parameter and model selection among entropic regularization of OT, input convex neural networks and smooth and strongly convex nearest-Brenier (SSNB) models. Last, we make an experiment questioning the use of OT in Domain-Adaptation. Thanks to the criterion, we can identify the potential that is closest to the true OT map between the source and the target and we observe that this selected potential is not the one that performs best for the downstream transfer classification task.
Published: 2021

42. Near-optimal estimation of smooth transport maps with kernel sums-of-squares

Author: Muzellec, Boris, Vacher, Adrien, Bach, Francis, Vialard, François-Xavier, Rudi, Alessandro, Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Université Gustave Eiffel, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, and Département d'informatique de l'École normale supérieure (DI-ENS)
Subjects: FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Statistics - Machine Learning, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Machine Learning (stat.ML), Mathematics - Statistics Theory, Statistics Theory (math.ST), Machine Learning (cs.LG)
Abstract: It was recently shown that under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. However, rather than the distance itself, the object of interest for applications such as generative modeling is the underlying optimal transport map. Hence, computational and statistical guarantees need to be obtained for the estimated maps themselves. In this paper, we propose the first tractable algorithm for which the statistical $L^2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation. Our method is based on solving the semi-dual formulation of optimal transport with an infinite-dimensional sum-of-squares reformulation, and leads to an algorithm which has dimension-free polynomial rates in the number of samples, with potentially exponentially dimension-dependent constants.
Published: 2021

43. A FreeForm Optics Application of Entropic Optimal Transport

Author: Rukhaia, Giorgi, Benamou, Jean-David, Ijzerman, Wilbert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres, Jean-David Benamou, Wilbert IJzerman, European Project: 765374,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions / H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,ROMSOC(2017), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, PSL Université Paris Dauphine, INRIA Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: Non-Linear optimization, Problème inverse du reflecteur, Optimisation non linéaire, Optimisation non linèaire, Non-linear opti- mization, Transport Optimal entropique, Inverse Reflector Problem, Algorithme de Sinkhorn, Sinkhorn algorithm, [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], Entropic Optimal Transport, Extended source, Problème inverse du réflecteur, [MATH]Mathematics [math], Source lumineuse étendue
Abstract: In this work, we address the “freeform optics” inverse problem of designing a reflector surface mapping a prescribed source distribution of light to a prescribed target far-field distribution, for the point light source and the extended light source. When the source is a point source, the light distribution has support only on the optics ray directions. In this setting, the inverse problem is well-posed for arbitrary source and target probability distributions. It can be recast as an optimal transport problem and is a classic example of an optimal transport problem with a non-euclidean displacement cost. We explore the use of entropic Optimal Transport and the associated Sinkhorn algorithm to solve it numerically. As the reflector modeling is based on the Kantorovich potentials, several questions arise. First, on the convergence of the discrete entropic approximation and here we follow the recent work of Berman and in particular the imposed discretization requirements therein. Secondly, the correction of the bias induced by the entropic Optimal Transport using the recent notion of Sinkhorn divergences is shown to be necessary to achieve satisfactory results. For the point source problem, we discuss the necessary mathematical and numerical tools needed to produce and analyze the obtained numerical results. We find that Sinkhorn algorithm may be adapted to the resolution of the point source to far-field reflector problem.We are not aware of any similar mathematical formulation in the extended source case: i.e. the source has an “étendue” with support in the product space: physical domain-ray directions. We propose to leverage the well-posed variational formulation of the point source problem to build a smooth parameterization of the reflector and the map modeling the reflection. Under this parametrization, we can construct a smooth cost function to optimize for the best solution in this class of reflectors. Both steps, the parameterization and the cost function, are related to entropic optimal transport distances. We also take advantage of recent progress in the optimization techniques and the efficient implementations of Sinkhorn algorithm to perform a numerical study.; Dans ce travail, nous abordons un problème inverse en optique anidolique consistant à déterminer une surface capable de réflechir une distribution de lumière source à une distribution cible en champ lointain, toutes deux prescrites. La source lumineuse peut être ponctuelle ou étendue. Lorsque la source est une source ponctuelle , la distribution est supportée uniquement sur les directions des rayons optiques. Dans ce contexte, le problème inverse est bien posé pour des distributions de probabilité source et cible arbitraires. Il peut être reformulé comme un problème de transport optimal et constitue un exemple célébre de transport optimal sous un coût de déplacement non euclidien. Nous explorons l’utilisation du transport optimal entropique et de l’algorithme Sinkhorn associé pour le résoudre numériquement. La modélisation du réflecteur étant basée sur les potentiels de Kantorovich, plusieurs questions se posent. Premièrement, sur la convergence de l’approximation entropique discrète et nous suivons ici les travaux récents de Berman et en particulier les exigences de discrétisation qui y sont imposées. Deuxièmement, nous montrons que la correction du biais induit par le transport entropique Optimal peut être atteinte en utilisant la notion récente de divergences Sinkhorn. Pour le problème de source ponctuelle, nous discutons des outils mathématiques et numériques nécessaires pour produire et analyser les résultats numériques obtenus. Nous trouvons que l’algorithme Sinkhorn peut être adapté à la résolution du problème de la source ponctuelle au réflecteur en champ lointain.Nous ne connaissons pas de formulation mathématique similaire dans le cas de la source étendue : la distribution de lumière source a support sur l’espace produit: domaine physique-directions des rayons. Nous proposons de tirer parti de la formulation variationnelle bien posée du problème de source ponctuelle pour construire une paramétrisation lisse du réflecteur et de l’application modélisant la réflexion. Sous cette paramétrisation, nous pouvons construire une fonction de coût lisse à optimiser pour trouver la meilleure solution dans cette classe de réflecteurs. Les deux étapes, la paramétrisation et la fonction de coût, sont liées à des distances de transport entropiques optimales. Nous profitons également des progrès récents des techniques d’optimisation et des implémentations efficaces de l’algorithme Sinkhorn pour réaliser une étude numérique.
Published: 2021
Full Text: View/download PDF

44. Point Source Regularization of the Finite Source Reflector Problem

Author: Benamou, Jean-David, Chazareix, Guillaume, Rukhaia, Giorgi, Ijzerman, Wilbert, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Signify Research, Scientific Computing, Computational Illumination Optics, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris
Subjects: Computational Mathematics, Numerical Analysis, Optimal transportation, Physics and Astronomy (miscellaneous), Inverse reﬂector problem, Non-linear optimization, Applied Mathematics, Modeling and Simulation, Inverse reflector problem, 2000 MSC: 78A46, 49Q22, 65K10, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Computer Science Applications
Abstract: International audience; We address the “freeform optics” inverse problem of designing a reﬂector surface mapping a prescribed source distribution of light to a prescribed far ﬁeld distribution, for a ﬁnite light source. When the ﬁnite source reduces to a point source, the light source distribution has support only on the optics ray directions. In this setting the inverse problem is well posed for arbitrary source and target probability distributions. It can be recast as an Optimal Transportation problem and has been studied both mathematically and nu-merically. We are not aware of any similar mathematical formulation in the ﬁnite source case: i.e. the source has an “´etendue” with support both in space and directions. We propose to leverage the well-posed variational formulation of the point source problem to build a smooth parameterization of the reﬂec-tor and the reﬂection map. Under this parameterization we can construct a smooth loss/misﬁt function to optimize for the best solution in this class of reﬂectors. Both steps, the parameterization and the loss, are related to Optimal Transportation distances. We also take advantage of recent progress in the numerical approximation and resolution of these mathematical objects to perform a numerical study.
Published: 2021

45. Computation of optimal transport with finite volumes

Author: Andrea Natale, Gabriele Todeschi, Reliable numerical approximations of dissipative systems (RAPSODI ), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754362. AN acknowledges that this work was supported by a public grant as part of the Investissement d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH., ANR-11-LABX-0056,LMH,LabEx Mathématique Hadamard(2011), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Inria Lille - Nord Europe, Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 754362., GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 754362. AN acknowledges that this work was supported by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH., European Project: 754362,MathInParis(2017), and GT acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 754362.
Subjects: Computation, Barrier method, 010103 numerical & computational mathematics, Type (model theory), 01 natural sciences, Convexity, Quadratic equation, Convergence (routing), FOS: Mathematics, Applied mathematics, Polygon mesh, Mathematics - Numerical Analysis, 0101 mathematics, [MATH]Mathematics [math], Mathematics, Numerical Analysis, Finite volume method, Finite volumes, Applied Mathematics, Dynamical optimal transport, Numerical Analysis (math.NA), 010101 applied mathematics, Computational Mathematics, Modeling and Simulation, Analysis, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], 65N08, 35A15, 65K10, 49M29, 90C51
Abstract: International audience; We construct Two-Point Flux Approximation (TPFA) finite volume schemes to solve the quadratic optimal transport problem in its dynamic form, namely the problem originally introduced by Benamou and Brenier. We show numerically that these type of discretizations are prone to form instabilities in their more natural implementation, and we propose a variation based on nested meshes in order to overcome these issues. Despite the lack of strict convexity of the problem, we also derive quantitative estimates on the convergence of the method, at least for the discrete potential and the discrete cost. Finally, we introduce a strategy based on the barrier method to solve the discrete optimization problem.
Published: 2021

46. A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

Author: Vacher, Adrien, Muzellec, Boris, Rudi, Alessandro, Bach, Francis, Vialard, Francois-Xavier, Université Gustave Eiffel, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Statistical Machine Learning and Parsimony (SIERRA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grants SEQUOIA 724063 and REAL 947908), and Région Ile-de-France., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), European Project: 724063,ERC-2016-COG,SEQUOIA(2017), European Project: 947908,REAL, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Optimization and Control (math.OC), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], FOS: Mathematics, Mathematics - Statistics Theory, 62G05, Statistics Theory (math.ST), Mathematics - Optimization and Control
Abstract: It is well-known that plug-in statistical estimation of optimal transport suffers from the curse of dimensionality. Despite recent efforts to improve the rate of estimation with the smoothness of the problem, the computational complexity of these recently proposed methods still degrades exponentially with the dimension. In this paper, thanks to an infinite-dimensional sum-of-squares representation, we derive a statistical estimator of smooth optimal transport which achieves a precision $\varepsilon$ from $\tilde{O}(\varepsilon^{-2})$ independent and identically distributed samples from the distributions, for a computational cost of $\tilde{O}(\varepsilon^{-4})$ when the smoothness increases, hence yielding dimension-free statistical and computational rates, with potentially exponentially dimension-dependent constants., Comment: 30 pages
Published: 2021

47. Impact of Missing Data on Mixtures and Clustering

Author: Biernacki, Christophe, Boyer, Claire, Celeux, Gilles, Josse, Julie, Laporte, Fabien, Marbac Lourdelle, Matthieu, Sportisse, Aude, Vandewalle, Vincent, MOdel for Data Analysis and Learning (MODAL), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Statistique mathématique et apprentissage (CELESTE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Génétique Quantitative et Evolution - Le Moulon (Génétique Végétale) (GQE-Le Moulon), AgroParisTech-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Biernacki, Christophe, Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris
Subjects: [STAT.ME] Statistics [stat]/Methodology [stat.ME], [STAT.ME]Statistics [stat]/Methodology [stat.ME], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021

48. Nonnegative Matrix Factorization with Side Information for Time Series Recovery and Prediction

Author: Yohann De Castro, Jiali Mei, Georges Hébrail, Jean-Marc Azaïs, Yannig Goude, Institut de Mathématiques de Toulouse UMR5219 (IMT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), EDF (EDF), Laboratoire de Business Intelligence Télécom-ParisTech/EDF (BILab), Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom ParisTech-Telecom Orange-EDF (EDF), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)
Subjects: FOS: Computer and information sciences, Computer science, Machine Learning (stat.ML), 02 engineering and technology, Statistics - Applications, 01 natural sciences, Matrix decomposition, Non-negative matrix factorization, 010104 statistics & probability, Kernel (linear algebra), Matrix (mathematics), [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Applications (stat.AP), 0101 mathematics, Time series, Series (mathematics), 020206 networking & telecommunications, Computer Science Applications, Computational Theory and Mathematics, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], Convex optimization, Identifiability, Algorithm, Information Systems
Abstract: International audience; Motivated by the reconstruction and the prediction of electricity consumption, we extend Nonnegative Matrix Factorization~(NMF) to take into account side information (column or row features). We consider general linear measurement settings, and propose a framework which models non-linear relationships between features and the response variables. We extend previous theoretical results to obtain a sufficient condition on the identifiability of the NMF in this setting. Based the classical Hierarchical Alternating Least Squares~(HALS) algorithm, we propose a new algorithm (HALSX, or Hierarchical Alternating Least Squares with eXogeneous variables) which estimates the factorization model. The algorithm is validated on both simulated and real electricity consumption datasets as well as a recommendation dataset, to show its performance in matrix recovery and prediction for new rows and columns.
Published: 2019

49. Lecture notes on non-convex algorithms for low-rank matrix recovery

Author: Waldspurger, Irène, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris
Subjects: Mathematics - Statistics Theory, [MATH]Mathematics [math], Mathematics - Optimization and Control
Abstract: Low-rank matrix recovery problems are inverse problems which naturally arise in various fields like signal processing, imaging and machine learning. They are non-convex and NP-hard in full generality. It is therefore a delicate problem to design efficient recovery algorithms and to provide rigorous theoretical insights on the behavior of these algorithms. The goal of these notes is to review recent progress in this direction for the class of so-called "non-convex algorithms", with a particular focus on the proof techniques. Although they aim at presenting very recent research works, these notes have been written with the intent to be, as much as possible, accessible to non-specialists. These notes were written for an eight-hour lecture at Collège de France. The original version, in French, is available online 1 and the videos of the lecture can be found on the Collège de France website 2. The beginning takes inspiration from the review articles [Davenport and Romberg, 2016] and [Chen and Chi, 2018].
Published: 2021

50. Dealing with missing data in model-based clustering through a MNAR model

Author: Biernacki, Christophe, Boyer, Claire, Celeux, Gilles, Josse, Julie, Laporte, Fabien, Lourdelle, Matthieu, Sportisse, Aude, MOdel for Data Analysis and Learning (MODAL), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille)-Université de Lille, Sciences et Technologies, Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Statistique mathématique et apprentissage (CELESTE), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Mathématiques d'Orsay (LMO), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria), Génétique Quantitative et Evolution - Le Moulon (Génétique Végétale) (GQE-Le Moulon), AgroParisTech-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Ecole Nationale Supérieure des Sciences Agro-Industrielles [Univ Ngaoundéré] (ENSAI), Université de Ngaoundéré/University of Ngaoundéré [Cameroun] (UN), Modèles et algorithmes pour l’intelligence artificielle (MAASAI), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (JAD), Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Paul Painlevé (LPP), Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Evaluation des technologies de santé et des pratiques médicales - ULR 2694 (METRICS), Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-Université de Lille-Centre Hospitalier Régional Universitaire [Lille] (CHRU Lille)-École polytechnique universitaire de Lille (Polytech Lille), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Laboratoire Jean Alexandre Dieudonné (LJAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Laboratoire Paul Painlevé - UMR 8524 (LPP), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Université de Lille, Sciences et Technologies-Inria Lille - Nord Europe, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, and Biernacki, Christophe
Subjects: [STAT.ME] Statistics [stat]/Methodology [stat.ME], [STAT.ME]Statistics [stat]/Methodology [stat.ME], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

193 results on '"Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources