Timezone: »
Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
Meyer Scetbon · Gabriel Peyré · Marco Cuturi
Event URL: https://arxiv.org/abs/2106.01128 »
The ability to compare and align points across datasets that are known to be related, yet incomparable--because they live in heterogeneous spaces--plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem. Its goal is to seek a low-distortion assignment between points taken across these incomparable datasets.As a non-convex and quadratic generalization of optimal transport (OT), GW is NP-hard. Although heuristics are known to work reasonably well (e.g. by solving a sequence of nested regularized OT problems), they still remain too costly to scale, with \emph{cubic} complexity in the number of samples $n$. As a result GW is far less used in practice than usual OT.We examine in this work how a recent variant of the OT problem that narrows down the set of admissible couplings to those admitting a low rank factorization of two sub-couplings is particularly well suited to the resolution of GW.By updating alternatively each sub-coupling, our algorithm computes a stationary point of the problem in time $O(n^2)$. When cost matrices have low rank , our algorithm becomes linear in $n$.We demonstrate the efficiency of our method on simulated and real data.
The ability to compare and align points across datasets that are known to be related, yet incomparable--because they live in heterogeneous spaces--plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem. Its goal is to seek a low-distortion assignment between points taken across these incomparable datasets.As a non-convex and quadratic generalization of optimal transport (OT), GW is NP-hard. Although heuristics are known to work reasonably well (e.g. by solving a sequence of nested regularized OT problems), they still remain too costly to scale, with \emph{cubic} complexity in the number of samples $n$. As a result GW is far less used in practice than usual OT.We examine in this work how a recent variant of the OT problem that narrows down the set of admissible couplings to those admitting a low rank factorization of two sub-couplings is particularly well suited to the resolution of GW.By updating alternatively each sub-coupling, our algorithm computes a stationary point of the problem in time $O(n^2)$. When cost matrices have low rank , our algorithm becomes linear in $n$.We demonstrate the efficiency of our method on simulated and real data.
Author Information
Meyer Scetbon (CREST-ENSAE)
Gabriel Peyré (Université Paris Dauphine)
Marco Cuturi (Google Brain CREST - ENSAE)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 : Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs »
Dates n/a. Room
More from the Same Authors
-
2021 : Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe »
Thibault Sejourne · Francois-Xavier Vialard · Gabriel Peyré -
2021 : Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe »
Thibault Sejourne · Francois-Xavier Vialard · Gabriel Peyré -
2023 Poster: Unbalanced Low-rank Optimal Transport Solvers »
Meyer Scetbon · Michal Klein · Giovanni Palla · Marco Cuturi -
2022 Poster: Low-rank Optimal Transport: Approximation, Statistics and Debiasing »
Meyer Scetbon · Marco Cuturi -
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é -
2020 Poster: Linear Time Sinkhorn Divergences using Positive Features »
Meyer Scetbon · Marco Cuturi -
2019 Workshop: Optimal Transport for Machine Learning »
Marco Cuturi · Gabriel Peyré · Rémi Flamary · Alexandra Suvorikova -
2019 Poster: Comparing distributions: $\ell_1$ geometry improves kernel two-sample testing »
Meyer Scetbon · Gael Varoquaux -
2019 Spotlight: Comparing distributions: $\ell_1$ geometry improves kernel two-sample testing »
Meyer Scetbon · Gael Varoquaux -
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é