mlsanityData to 7 Oct 2026

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

arXiv 1802.04367 ↗First posted 12 Feb 2018cs.DS math.OCcited by 111

Not on the map. Why?

Abstract (arXiv)

We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size n, up to accuracy varepsilon. For the first algorithm, which is based on the celebrated Sinkhorn's algorithm, we prove the complexity bound widetildeOleft(n2/varepsilon2right) 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 widetildeOleft(minleftn9/4/varepsilon, n2/varepsilon2 rightright) arithmetic operations. Both bounds have better dependence on varepsilon than the state-of-the-art result given by widetildeOleft(n2/varepsilon3right). Our second algorithm not only has better dependence on varepsilon in the complexity bound, but also is not specific to entropic regularization and can solve the OT problem with different regularizers.

Key facts. Cited by 111 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 21; 2022: 20; 2023: 22; 2024: 14; 2025: 20; 2026: 14.

111 papers.

Sort:

By area:

  1. 2021Entropic estimation of optimal transport mapscited by 87
  2. 2023Diffusion Bridge Mixture Transports, Schr"odinger Bridge Problems and Generative Modelingcited by 80
  3. 2024Optimal Flow Matching: Learning Straight Trajectories in Just One Stepcited by 74
  4. 2021Low-Rank Sinkhorn Factorizationcited by 66
  5. 2023Training neural operators to preserve invariant measures of chaotic attractorscited by 43
  6. 2021Improving Mini-batch Optimal Transport via Partial Transportationcited by 40
  7. 2023Optimal Transport for Treatment Effect Estimationcited by 32
  8. 2023Transformed Distribution Matching for Missing Value Imputationcited by 31
  9. 2022Trajectory Inference via Mean-field Langevin in Path Spacecited by 29
  10. 2021On Robust Optimal Transport: Computational Complexity and Barycenter Computationcited by 27
  11. 2023Novel Class Discovery for Long-tailed Recognitioncited by 19
  12. 2023Light Schr"odinger Bridgecited by 18
38 more
  1. 2022On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Errorcited by 16
  2. 2023Unified Mask Embedding and Correspondence Learning for Self-Supervised Video Segmentationcited by 16
  3. 2021On the complexity of the optimal transport problem with graph-structured costcited by 14
  4. 2022Adaptive Distribution Calibration for Few-Shot Learning with Hierarchical Optimal Transportcited by 14
  5. 2021Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solutioncited by 13
  6. 2021Entropic Gromov-Wasserstein between Gaussian Distributionscited by 12
  7. 2022Discovering Conservation Laws using Optimal Transport and Manifold Learningcited by 12
  8. 2023A relaxed proximal gradient descent algorithm for convergent plug-and-play with proximal denoisercited by 12
  9. 2023Lower Complexity Adaptation for Empirical Entropic Optimal Transportcited by 12
  10. 2025Flow Matching with Semidiscrete Couplingscited by 12
  11. 2022Approximate Policy Iteration with Bisimulation Metricscited by 11
  12. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 10
  13. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  14. 2021Entropy Regularized Optimal Transport Independence Criterioncited by 9
  15. 2022Hilbert Curve Projection Distance for Distribution Comparisoncited by 9
  16. 2024Accelerating Sinkhorn Algorithm with Sparse Newton Iterationscited by 9
  17. 2021On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexitycited by 8
  18. 2025Fourier Sliced-Wasserstein Embedding for Multisets and Measurescited by 8
  19. 2021Optimal transport weights for causal inferencecited by 7
  20. 2023Improved Rate of First Order Algorithms for Entropic Optimal Transportcited by 7
  21. 2023On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methodscited by 7
  22. 2024GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descentcited by 7
  23. 2022Neural Score Matching for High-Dimensional Causal Inferencecited by 6
  24. 2022An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenterscited by 6
  25. 2022Gaussian Processes on Distributions based on Regularized Optimal Transportcited by 6
  26. 2023Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradientscited by 6
  27. 2024Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasingcited by 6
  28. 2025Improved Training Technique for Shortcut Modelscited by 6
  29. 2021Improving Approximate Optimal Transport Distances using Quantizationcited by 5
  30. 2021Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transportcited by 5
  31. 2021Bounding Wasserstein distance with couplingscited by 5
  32. 2022Mirror Sinkhorn: Fast Online Optimization on Transport Polytopescited by 5
  33. 2023Generating Synthetic Datasets by Interpolating along Generalized Geodesicscited by 5
  34. 2023Topological Node2vec: Enhanced Graph Embedding via Persistent Homologycited by 5
  35. 2025Categorical Schr"odinger Bridge Matchingcited by 5
  36. 2025A Truncated Newton Method for Optimal Transportcited by 5
  37. 2021First-Order Methods for Convex Optimizationcited by 4
  38. 2022Unsupervised Sentence Textual Similarity with Compositional Phrase Semanticscited by 4

50 most cited of 111 All 111 (JSON)