Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

Abstract

Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice.

Cited by in corpus (106)

• Gromov-Wasserstein Learning for Graph Matching and Node Embedding
• A Fast Proximal Point Method for Computing Exact Wasserstein Distance
• Geometric Dataset Distances via Optimal Transport
• Faster Wasserstein Distance Estimation with the Sinkhorn Divergence
• Unsupervised Hyperalignment for Multilingual Word Embeddings
• Wasserstein Weisfeiler-Lehman Graph Kernels
• FlipTest: Fairness Testing via Optimal Transport
• On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms
• Linearized Optimal Transport for Collider Events
• Unsupervised Alignment of Embeddings with Wasserstein Procrustes
• Domain Adaptation for Robust Workload Level Alignment Between Sessions and Subjects using fNIRS
• Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching
• On the Complexity of Approximating Wasserstein Barycenter
• Asymptotics for semi-discrete entropic optimal transport
• On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
• Universal gradient descent
• A mathematical theory of cooperative communication
• Statistical and Topological Properties of Sliced Probability Divergences
• Screening Sinkhorn Algorithm for Regularized Optimal Transport
• On parameter estimation with the Wasserstein distance
• Biwhitening Reveals the Rank of a Count Matrix
• Optimal transportation of grain boundaries: A forward model for predicting migration mechanisms
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
• Word Mover's Embedding: From Word2Vec to Document Embedding
• Massively scalable Sinkhorn distances via the Nyström method
• Exponential ergodicity of mirror-Langevin diffusions
• Greedy stochastic algorithms for entropy-regularized optimal transport problems
• Ground Metric Learning on Graphs
• Linear Time Sinkhorn Divergences using Positive Features
• Domain decomposition for entropy regularized optimal transport
• Optimal Transport: Fast Probabilistic Approximation with Exact Solvers
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
• The data-driven Schroedinger bridge
• Differentiable Particle Filtering via Entropy-Regularized Optimal Transport
• Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport
• Towards Listening to 10 People Simultaneously: An Efficient Permutation Invariant Training of Audio Source Separation Using Sinkhorn's Algorithm
• An explicit analysis of the entropic penalty in linear programming
• On the Computation of Kantorovich-Wasserstein Distances between 2D-Histograms by Uncapacitated Minimum Cost Flows
• The statistical effect of entropic regularization in optimal transportation
• When Optimal Transport Meets Information Geometry
• Distributional Sliced-Wasserstein and Applications to Generative Modeling
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs
• Smooth $p$-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
• Limit Distribution Theory for the Smooth 1-Wasserstein Distance with Applications
• Semi-discrete optimal transport - the case p=1
• Sinkhorn Distributionally Robust Optimization
• Asymptotic Guarantees for Generative Modeling Based on the Smooth Wasserstein Distance
• Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory
• Balancing Gaussian vectors in high dimension
• Entropic estimation of optimal transport maps
• Structured Optimal Transport
• Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem
• Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?
• Learning High Dimensional Wasserstein Geodesics
• Optimal Transport for Stationary Markov Chains via Policy Iteration
• Making transport more robust and interpretable by moving data through a small number of anchor points
• Randomised Wasserstein Barycenter Computation: Resampling with Statistical Guarantees
• Fast and Smooth Interpolation on Wasserstein Space
• On Transportation of Mini-batches: A Hierarchical Approach
• Augmented Sliced Wasserstein Distances
• Tensor optimal transport, distance between sets of measures and tensor scaling
• Stochastic control liaisons: Richard Sinkhorn meets Gaspard Monge on a Schroedinger bridge
• Improving Mini-batch Optimal Transport via Partial Transportation
• Flow-based Alignment Approaches for Probability Measures in Different Spaces
• On Robust Optimal Transport: Computational Complexity and Barycenter Computation
• Projection Robust Wasserstein Barycenters
• Interpretable ICD Code Embeddings with Self- and Mutual-Attention Mechanisms
• Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent
• Neural Monge Map estimation and its applications
• CO-Optimal Transport
• Entropic Gromov-Wasserstein between Gaussian Distributions
• Improving Approximate Optimal Transport Distances using Quantization
• Tree-Sliced Variants of Wasserstein Distances
• Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
• Learning transport cost from subset correspondence
• A Metric on the Polycrystalline Microstructure State Space
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport
• Adaptive Softassign via Hadamard-Equipped Sinkhorn
• Supervised Quantile Normalization for Low-rank Matrix Approximation
• Topological Node2vec: Enhanced Graph Embedding via Persistent Homology
• Order Constraints in Optimal Transport
• Approximating Optimal Transport via Low-rank and Sparse Factorization
• Decentralized and Equitable Optimal Transport
• Approximation of Wasserstein distance with Transshipment
• Low-Complexity Data-Parallel Earth Mover's Distance Approximations
• An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems
• Sinkhorn Divergence of Topological Signature Estimates for Time Series Classification
• Low-Rank Sinkhorn Factorization
• Zero-Shot Recognition via Optimal Transport
• Permutation invariant networks to learn Wasserstein metrics
• Computational Optimal Transport for 5G Massive C-RAN Device Association
• Optimal transport weights for causal inference
• Relaxed Schroedinger bridges and robust network routing
• Convergence Rates of Smooth Message Passing with Rounding in Entropy-Regularized MAP Inference
• Coupling Matrix Manifolds and Their Applications in Optimal Transport
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity
• Sequential Ensemble Transform for Bayesian Inverse Problems
• Entropy-regularized optimal transport on multivariate normal and q-normal distributions
• Hawkes Processes on Graphons