Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm

Abstract

We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size $n$, up to accuracy $\epsilon$. For the first algorithm, which is based on the celebrated Sinkhorn's algorithm, we prove the complexity bound $\tilde{O}\left(n^2/{\epsilon }^2\right)$ arithmetic operations. For the second one, which is based on our novel Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) algorithm, we prove the complexity bound $\tilde{O}\left(\min \left\{n^{9/4}/\epsilon ,n^2/{\epsilon }^2\right\}\right)$ arithmetic operations. Both bounds have better dependence on $\epsilon$ than the state-of-the-art result given by $\tilde{O}\left(n^2/{\epsilon }^3\right)$. Our second algorithm not only has better dependence on $\epsilon$ in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.

arXiv commentAccepted for ICML 2018

Cited by in corpus (21)

• On the Complexity of Approximating Multimarginal Optimal Transport
• Universal gradient descent
• Optimal Transport Graph Neural Networks
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• 2-Wasserstein Approximation via Restricted Convex Potentials with Application to Improved Training for GANs
• Massively scalable Sinkhorn distances via the Nyström method
• Ground Metric Learning on Graphs
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
• Approximating the Quadratic Transportation Metric in Near-Linear Time
• Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
• The statistical effect of entropic regularization in optimal transportation
• Stochastic Optimization for Regularized Wasserstein Estimators
• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• Tree-Wasserstein Barycenter for Large-Scale Multilevel Clustering and Scalable Bayes
• Improving Approximate Optimal Transport Distances using Quantization
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• Supervised Quantile Normalization for Low-rank Matrix Approximation
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Tessellated Wasserstein Auto-Encoders
• Low-Rank Sinkhorn Factorization