Timezone: »
Unbalanced optimal transport (UOT) extends optimal transport (OT) to take into account mass variations to compare distributions. This is crucial to make OT successful in ML applications, making it robust to data normalization and outliers. The baseline algorithm is Sinkhorn, but its convergence speed might be significantly slower for UOT than for OT. In this work, we identify the cause for this deficiency, namely the lack of a global normalization of the iterates, which equivalently corresponds to a translation of the dual OT potentials. Our first contribution leverages this idea to develop an accelerated Sinkhorn algorithm (coined ”translation invariant Sinkhorn”) for UOT, bridging the computational gap with OT. Our second contribution focusses on 1-D UOT and proposes a Frank-Wolfe solver applied to this translation invariant formulation. The linear oracle of each steps amounts to solving a 1-D OT problems, resulting in a linear time complexity per iteration. Our last contribution extends this method to the computation of UOT barycenter of 1-D measures. Numerical simulations showcase the convergence speed improvement brought by these three approaches.
Author Information
Thibault Sejourne (CNRS, Projet Noria, ENS, PSL)
After graduating from Ecole Polytechnique, I enrolled into the master’s degree MVA (“Mathematiques, Visison, Apprentissage”) of Ecole Normale Superieure Paris-Saclay. I am now a second year PhD candidate at ENS Paris under the supervision of Gabriel Peyré and François-Xavier Vialard. I am currently working on the applications of the theory of Optimal Transport for Machine learning applications.
Francois-Xavier Vialard (University Gustave Eiffel)
Gabriel Peyré (Université Paris Dauphine)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 : Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe »
Dates n/a. Room
More from the Same Authors
-
2021 : Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs »
Meyer Scetbon · Gabriel Peyré · Marco Cuturi -
2021 : Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs »
Meyer Scetbon · Gabriel Peyré · Marco Cuturi -
2022 Poster: Parameter tuning and model selection in Optimal Transport with semi-dual Brenier formulation »
Adrien Vacher · Francois-Xavier Vialard -
2022 Poster: On global convergence of ResNets: From finite to infinite width using linear parameterization »
Raphaël Barboni · Gabriel Peyré · Francois-Xavier Vialard -
2021 Poster: Smooth Bilevel Programming for Sparse Regularization »
Clarice Poon · Gabriel Peyré -
2021 Poster: The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation »
Thibault Sejourne · Francois-Xavier Vialard · Gabriel Peyré -
2019 : Poster Session »
Lili Yu · Aleksei Kroshnin · Alex Delalande · Andrew Carr · Anthony Tompkins · Aram-Alexandre Pooladian · Arnaud Robert · Ashok Vardhan Makkuva · Aude Genevay · Bangjie Liu · Bo Zeng · Charlie Frogner · Elsa Cazelles · Esteban G Tabak · Fabio Ramos · François-Pierre PATY · Georgios Balikas · Giulio Trigila · Hao Wang · Hinrich Mahler · Jared Nielsen · Karim Lounici · Kyle Swanson · Mukul Bhutani · Pierre Bréchet · Piotr Indyk · samuel cohen · Stefanie Jegelka · Tao Wu · Thibault Sejourne · Tudor Manole · Wenjun Zhao · Wenlin Wang · Wenqi Wang · Yonatan Dukler · Zihao Wang · Chaosheng Dong -
2019 Poster: Region-specific Diffeomorphic Metric Mapping »
Zhengyang Shen · Francois-Xavier Vialard · Marc Niethammer -
2017 Workshop: Optimal Transport and Machine Learning »
Olivier Bousquet · Marco Cuturi · Gabriel Peyré · Fei Sha · Justin Solomon -
2016 Poster: A Multi-step Inertial Forward-Backward Splitting Method for Non-convex Optimization »
Jingwei Liang · Jalal Fadili · Gabriel Peyré -
2016 Poster: Sparse Support Recovery with Non-smooth Loss Functions »
Kévin Degraux · Gabriel Peyré · Jalal Fadili · Laurent Jacques -
2016 Poster: Stochastic Optimization for Large-scale Optimal Transport »
Aude Genevay · Marco Cuturi · Gabriel Peyré · Francis Bach -
2015 Poster: Biologically Inspired Dynamic Textures for Probing Motion Perception »
Jonathan Vacher · Andrew Isaac Meso · Laurent U Perrinet · Gabriel Peyré -
2015 Spotlight: Biologically Inspired Dynamic Textures for Probing Motion Perception »
Jonathan Vacher · Andrew Isaac Meso · Laurent U Perrinet · Gabriel Peyré -
2014 Workshop: Optimal Transport and Machine Learning »
Marco Cuturi · Gabriel Peyré · Justin Solomon · Alexander Barvinok · Piotr Indyk · Robert McCann · Adam Oberman -
2014 Poster: Local Linear Convergence of Forward--Backward under Partial Smoothness »
Jingwei Liang · Jalal Fadili · Gabriel Peyré