# Efficient Optimal Transport Algorithm by Accelerated Gradient descent

arXiv: https://arxiv.org/abs/2104.05802 · HTML: https://mlsanity.com/paper/2104.05802/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 12 Apr 2021.

## Builds on (most cited first, 20 of 20)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Wasserstein Auto-Encoders](https://mlsanity.com/paper/1711.01558/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Hierarchical Optimal Transport for Document Representation](https://mlsanity.com/paper/1906.10827/) (2019)
- [On Scalable and Efficient Computation of Large Scale Optimal Transport](https://mlsanity.com/paper/1905.00158/) (2019)
- [Screening Sinkhorn Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1906.08540/) (2019)
- [Multiscale Strategies for Computing Optimal Transport](https://mlsanity.com/paper/1708.02469/) (2017)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [AE-OT-GAN: Training GANs from data specific latent distribution](https://mlsanity.com/paper/2001.03698/) (2020)
- [Approximating optimal transport with linear programs](https://mlsanity.com/paper/1810.05957/) (2018)
- [Greedy stochastic algorithms for entropy-regularized optimal transport problems](https://mlsanity.com/paper/1803.01347/) (2018)
- [A Direct tildeO(1/ε) Iteration Parallel Algorithm for Optimal Transport](https://mlsanity.com/paper/1906.00618/) (2019)
- [A Fast Proximal Point Method for Computing Exact Wasserstein Distance](https://mlsanity.com/paper/1802.04307/) (2018)

## Abstract (arXiv)

Optimal transport (OT) plays an essential role in various areas like machine learning and deep learning. However, computing discrete optimal transport plan for large scale problems with adequate accuracy and efficiency is still highly challenging. Recently, methods based on the Sinkhorn algorithm add an entropy regularizer to the prime problem and get a trade off between efficiency and accuracy. In this paper, we propose a novel algorithm to further improve the efficiency and accuracy based on Nesterov's smoothing technique. Basically, the non-smooth c-transform of the Kantorovich potential is approximated by the smooth Log-Sum-Exp function, which finally smooths the original non-smooth Kantorovich dual functional (energy). The smooth Kantorovich functional can be optimized by the fast proximal gradient algorithm (FISTA) efficiently. Theoretically, the computational complexity of the proposed method is given by O(n^frac52 √log n /ε), which is lower than that of the Sinkhorn algorithm. Empirically, compared with the Sinkhorn algorithm, our experimental results demonstrate that the proposed method achieves faster convergence and better accuracy with the same parameter.