Computational Optimal Transport
By G. Peyr'e, Marco Cuturi. 2018
2,757 citations recorded by the source corpus.
Optimal transport (OT) theory can be informally described using the words of the French mathematician Gaspard Monge (1746-1818): A worker with a shovel in hand has to move a large pile of sand lying on a construction site. The goal of the worker is to erect with all that sand a target pile with a prescribed shape (for example, that of a giant sand castle). Naturally, the worker wishes to minimize her total effort, quantified for instance as the total distance or time spent carrying shovelfuls of sand. Mathematicians interested in OT cast that problem as that of comparing two probability distributions, two different piles of sand of the same volume. They consider all of the many possible ways to morph, transport or reshape the first pile into the second, and associate a "global" cost to every such transport, using the "local" consideration of how much it costs to move a grain of sand from one place to another. Recent years have witnessed the spread of OT in several fields, thanks to the emergence of approximate solvers that can scale to sizes and dimensions that are relevant to data sciences. Thanks to this newfound scalability, OT is being increasingly used to unlock various problems in imaging sciences (such as color or texture processing), computer vision and graphics (for shape manipulation) or machine learning (for regression, classification and density fitting). This short book reviews OT with a bias toward numerical methods and their applications in data sciences, and sheds lights on the theoretical properties of OT that make it particularly useful for some of these applications.
Subfields: Civil and Structural Engineering, Molecular Biology, Optimization & Training, Mathematical Optimization
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Civil and Structural Engineering
- Silvia Chiappa
- Paul-Edouard Sarlin
- Luca Oneto
- François-Pierre Paty
- Jean Feydy
- Marc Hallin
- De-chuan Zhan
- Han-Jia Ye
In Molecular Biology
- Satoshi Hara
- Silvia Chiappa
- George Papamakarios
- Paul-Edouard Sarlin
- Michael M. Bronstein
- Luca Oneto
- François-Pierre Paty
- Maksim V. Plikus
In Optimization & Training
- James Martens
- Roger Baker Grosse
- Yoshua Bengio
- G. Peyr'e
- Oriol Vinyals
- Andriy Mnih
- Marco Cuturi
- Sergey Levine
In Mathematical Optimization
- G. Peyr'e
- François-Pierre Paty
- De-chuan Zhan
- Han-Jia Ye
- Rémi Flamary
- Nicolas Courty
- Carlo Ciliberto
- Paul-Edouard Sarlin
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].”
- Wireless Network Intelligence at the Edge (2018, methodology): “Instead, replacing the KL divergence minimization with calculating the Wasserstein distance in optimal transport (OT) [152] has recently become a promising solution, which yields a finite value even with nonoverlapping distributions.”
- Neural Architecture Search with Bayesian Optimisation and Optimal Transport (2018, background): “OT is a well studied problem with several efficient solvers [30].”
- Sorting out Lipschitz function approximation (2018, background): “3 APPLICATIONS OF LIPSCHITZ NETWORKS Wasserstein Distance Estimation Wasserstein-1 distance (also called Earth Mover Distance) is a principled distance metric between two probability distributions and has found many applications in machine learning in recent years [38, 17].”
- Subspace Robust Wasserstein distances (2019, methodology): “The optimal transport (OT) toolbox (Villani, 2009) is gaining popularity in machine learning, with several applications to data science outlined in the recent review paper (Peyré & Cuturi, 2019).”
- Large-scale Multi-modal Pre-trained Models: A Comprehensive Survey (2023, methodology): “•Word-Region Alignment (WRA) is used in UNITER [18] which target at explicitly achieves the fine-grained alignment between the multimodal inputs via Optimal Transport (OT) [120].”
- Identifying Ambiguous Similarity Conditions via Semantic Matching (2022, methodology): “We can show that when we use uniform marginal distributions and a square cost matrix in OT, the transportation will degenerate to the same solution as Hungarian’s output with special conditions [7].”
- Distribution Matching for Crowd Counting (2020, methodology): “In each training iteration, we use the Sinkhorn algorithm [34] to approximate α ∗ and β ∗ .”
- Distribution and quantile functions, ranks and signs in dimension d: A measure transportation approach (2021, methodology): “Determining such a coupling is a standard optimal assignment problem, which takes the form of a linear program for which efficient algorithms are available (see Peyré and Cuturi (2019) for a recent survey).”
- POT: Python Optimal Transport (2021, methodology): “We refer the interested reader to the book of Villani (2008) for a complete theoretical treatment, and to the book of Peyr´e and Cuturi (2018) for a more comprehensive study on OT’s computational aspects.”
- Discriminator optimal transport (2019, neutral): “The duality is called Kantorovich-Rubinstein duality [23, 24].”
- Repairing without Retraining: Avoiding Disparate Impact with Counterfactual Distributions (2019, background): “The optimal solution to (9) can be efficiently obtained via linear programming (LP) or other specialized techniques (see e.g., Peyré and Cuturi, 2017; Villani, 2008).”
- Fast geometric learning with symbolic matrices (2020, methodology): “As detailed in [37, 89], modern OT solvers rely on iterated reductions performed on a cost matrix C(xi, yj) = kxi yjk or (1)2kxi yjk 2 and stand to benefit greatly from our library.”
- Multivariate goodness-of-fit tests based on Wasserstein distance (2020, background): “…distances have a long history and continue to attract interest from diverse fields in statistics, machine learning, and computer science, in particular image analysis; see for instance the monographs and reviews by Santambrogio (2015), Peyré and Cuturi (2019), and Panaretos and Zemel (2019).”