Timezone: »

 
Spotlight
Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
Meyer Scetbon · Gabriel Peyré · Marco Cuturi

Tue Jul 19 11:45 AM -- 11:50 AM (PDT) @ Room 318 - 320
in Optimization »
The ability to align points across two related yet incomparable point clouds (e.g. living in different spaces) plays an important role in machine learning. The Gromov-Wasserstein (GW) framework provides an increasingly popular answer to such problems, by seeking a low-distortion, geometry-preserving assignment between these points.As a non-convex, quadratic generalization of optimal transport (OT), GW is NP-hard. While practitioners often resort to solving GW approximately as a nested sequence of entropy-regularized OT problems, the cubic complexity (in the number $n$ of samples) of that approach is a roadblock.We show in this work how a recent variant of the OT problem that restricts the set of admissible couplings to those having a low-rank factorization is remarkably well suited to the resolution of GW:when applied to GW, we show that this approach is not only able to compute a stationary point of the GW problem in time $O(n^2)$, but also uniquely positioned to benefit from the knowledge that the initial cost matrices are low-rank, to yield a linear time $O(n)$ GW approximation. Our approach yields similar results, yet orders of magnitude faster computation than the SoTA entropic GW approaches, on both simulated and real data.
Keywords: Optimization · PM: Structure Learning

Author Information

Meyer Scetbon (CREST, ENSAE)
Gabriel Peyré (CNRS and ENS)
Marco Cuturi (Apple)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors