Sinkhorn Distances: Lightspeed Computation of Optimal Transport
By Marco Cuturi. 2013
5,608 citations recorded by the source corpus.
Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the histograms' dimension exceeds a few hundreds. We propose in this work a new family of optimal transportation distances that look at transportation problems from a maximum-entropy perspective. We smooth the classical optimal transportation problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn-Knopp's matrix scaling algorithm at a speed that is several orders of magnitude faster than that of transportation solvers. We also report improved performance over classical optimal transportation distances on the MNIST benchmark problem.
Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Mathematical Optimization, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Medhi Bennis
- Jihong Park
- Francis R. Bach
- Martin Jaggi
- Sebastian U. Stich
- David A. Sontag
- Merouane Debbah
- Simon Lacoste-Julien
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Xiaogang Wang
- Ming-Hsuan Yang
- Jitendra Malik
- Andrew Zisserman
- Andrea Vedaldi
In Mathematical Optimization
- Mohammad Rostami
- Soheil Kolouri
- Martin Jaggi
- Simon Lacoste-Julien
- G. Peyr'e
- François-Pierre Paty
- De-chuan Zhan
- Han-Jia Ye
In Signal Processing
- Yoshua Bengio
- Bernhard Schölkopf
- Kyunghyun Cho
- Dong Yu
- Ruslan Salakhutdinov
- Neil Zeghidour
- Jesse Engel
- Li Deng
Citations in the corpus
- Unified Scaling Laws for Routed Language Models (2022, methodology): “First, we replace the auction algorithm for re-assigning expect selections with a continuous rebalancing process implemented via a Sinkhorn algorithm [Cuturi, 2013, Peyré and Cuturi, 2019].”
- Object-Centric Learning with Slot Attention (2020, background): “We leave the exploration of other matching algorithms [36, 37] for future work.”
- Emerging Properties in Self-Supervised Vision Transformers (2021, methodology): “2, 3, 4, 8, 14, 16, 18 [17] Marco Cuturi.”
- Exploring Simple Siamese Representation Learning (2020, methodology): “SwAV applies the Sinkhorn-Knopp (SK) transform [10] on the target branch (which is also symmetrized [7]).”
- Unsupervised Learning of Visual Features by Contrasting Cluster Assignments (2020, positive): “We consider a similar formulation to map representations to prototype vectors, but unlike [2] we keep the soft assignment produced by the Sinkhorn-Knopp algorithm [12] instead of approximating it into a hard assignment.”
- Improving GANs Using Optimal Transport (2018, background): “They start by taking an entropically smoothed generalization of the Earth Mover distance, called the Sinkhorn distance (Cuturi, 2013): DSinkhorn(p, g) = inf γ∈Πβ(p,g) Ex,y∼γ c(x,y), (4)”
- Self-labelling via simultaneous clustering and representation learning (2019, methodology): “Using the notation of (Cuturi, 2013), we relax matrix Q to be an element of the transportation polytope U(r, c) := {Q ∈ RK×N + | Q1 = r, Q>1 = c}.”
- Wasserstein Adversarial Examples via Projected Sinkhorn Iterations (2019, methodology): “Specifically, maximizing g with respect to α results in which is identical (up to a log transformation of variables) to the original Sinkhorn iterate proposed in Cuturi (2013).”
- Wireless Network Intelligence at the Edge (2018, background): “(b) Sinkhorn Divergence: Instead of the said dual approach, [153] tackles the primal formulation in (16) with an entropic approximation and the Sinkhorn algorithm [154].”
- Model Fusion via Optimal Transport (2019, methodology): “It is possible to further improve the runtime by adopting the entropy-regularized OT [22], but this looses slightly in terms of test accuracy compared to exact OT (c.”
- Wasserstein Fair Classification (2019, background): “It is easy to see that the optimal coupling T ∗ b,c is sparse and has at most O ( N b + N c ) nonzero entries (see Cuturi (2013)).”
- Learning to Simulate Complex Physics with Graph Networks (2020, methodology): “We also investigated distributional metrics including optimal transport (OT) (Villani, 2003) (approximated by the Sinkhorn Algorithm (Cuturi, 2013)), and Maximum Mean Discrep-ancy (MMD) (Gretton et al., 2012).”
- Machine learning unifies the modeling of materials and molecules (2017, positive): “It is possible to smoothly interpolate between the average and best match kernels using an entropy-regularized Wasserstein distance ( 43 ) construction.”
- Novel Class Discovery without Forgetting (2022, methodology): “An iterative Sinkhorn-Knopp algorithm [12] can be used”
- Co-Transport for Class-Incremental Learning (2021, methodology): “We solve OT with Sinkhorn algorithm [8].”
- Wasserstein Auto-Encoders (2017, background): “In a more general OT setting of Wc [14] proposed to penalize the objective of (1) with the KL-divergence λ ·DKL(Γ, P ⊗ Q) between the coupling distribution and the product of marginals.”
- MusicLM: Generating Music From Text (2023, methodology): “Then, we solve an optimal transport problem to find the matching cost between a pair of histograms using the Sinkhorn algorithm (Cuturi, 2013), considering only the sub-matrix corresponding to non-zero token counts in the two histograms.”
- Learning Generative Models with Sinkhorn Divergences (2017, methodology): “We propose a different route, by making two key simplifications: (i) approximate the function Eε(θ) by a size-(m,n) mini-batch sampling Êε(θ) to make it amenable to stochastic gradient descent ; (ii) approximate Êε(θ) by L-steps of the Sinkhorn algorithm [9] to obtain an algorithmic loss Ê ε (θ) whi”