On the Efficiency of Entropic Regularized Algorithms for Optimal Transport

article2022JMLR63 citations

Establishes improved computational complexity bounds for discrete optimal transport algorithms, matching Greenkhorn to Sinkhorn at $\tilde{O}(n^2\varepsilon^{-2})$ , correcting the convergence rate of adaptive primal-dual accelerated gradient descent, and introducing an accelerated Sinkhorn variant with superior error-dependence scaling.

Listen

Optimal transport provides a mathematically principled framework for comparing probability distributions and has become essential in modern data-driven applications, machine learning, and statistical inference. However, calculating exact transport distances involves heavy computational burdens and high-dimensional sample complexity. While adding entropy regularization helps resolve these statistical challenges and enables scalable approximation methods, existing algorithms face significant theoretical gaps, uncorrected complexity bounds, and practical performance trade-offs.

The article evaluates and enhances the computational efficiency of entropic regularized algorithms for discrete optimal transport problems with up to n support points. Its main objective is to establish tighter theoretical complexity bounds and develop faster accelerated algorithms that reduce the computational cost of achieving an approximate transportation plan with target accuracy ε.

To achieve this, the article establishes rigorous convergence proofs for coordinate descent and accelerated first-order optimization schemes applied to the smooth dual formulation of the regularized transport problem. The theoretical findings are validated through extensive empirical simulations on synthetic image data and real-world image benchmarks using the MNIST digit dataset across various regularization scales.

The key findings include:

The theoretical computational complexity of Greenkhorn—a greedy coordinate descent variant of the Sinkhorn algorithm—is improved from O(n²ε⁻³) to O(n²ε⁻²), matching the best-known theoretical bound for standard Sinkhorn while explaining why Greenkhorn updates fewer rows and columns in practice.
A deterministic accelerated Sinkhorn algorithm is developed, attaining an improved complexity bound of O(n⁷/³ε⁻⁴/³), which achieves superior scaling in high-precision regimes where ε is small compared to standard Sinkhorn.
The article proposes an adaptive primal-dual accelerated mirror descent method (APDAMD) and proves an iteration bound dependent on the mirror mapping regularity, while disproving a previously claimed faster complexity bound for adaptive primal-dual accelerated gradient descent (APDAGD) via a concrete counterexample and establishing its corrected bound of O(n⁵/²ε⁻¹).
Numerical evaluations show that Greenkhorn and accelerated Sinkhorn consistently reduce row and column updates relative to standard baselines, while APDAMD exhibits superior numerical stability compared to prior adaptive gradient methods.

These results provide a clear roadmap for selecting transport algorithms based on operational needs. In applications demanding high accuracy (such as economics and operations research where ε is very small), accelerated Sinkhorn significantly reduces runtime. Conversely, in large-scale settings with moderate precision requirements (such as image processing where n is very large relative to 1/ε), standard Sinkhorn and Greenkhorn remain the most computationally efficient options.

Decision-makers and engineering teams should deploy Greenkhorn as a direct, drop-in replacement for standard Sinkhorn to achieve empirical speedups without theoretical penalties. For future work, researchers should extend these accelerated methods to dimension-reduced formulations (such as sliced transport) and robust formulations designed to handle outlier-corrupted distributions.

University of California Berkeley University of Texas at Austin adaptive algorithms complexity results deterministic optimal transport entropic regularization Sinkhorn-Knopp algorithm

arXiv: 1906.01437

Paper: Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances, Marco Cuturi (2013). Introduces entropic regularization and the Sinkhorn-Knopp algorithm for optimal transport, establishing the foundational dual matrix-scaling formulation that the source directly accelerates and analyzes.
Paper: Computational Optimal Transport, Gabriel Peyré et al. (2018). Provides a comprehensive reference on computational optimal transport, entropic smoothing, and Sinkhorn iterations that form the core theoretical and algorithmic backdrop of the source.
Paper: A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights, Weijie Su et al. (2014). Develops the dynamical systems perspective and momentum mechanics of Nesterov acceleration, offering essential insight into the accelerated first-order optimization techniques adapted in the source.

Paper: Flow Matching for Generative Modeling, Yaron Lipman et al. (2023). Applies optimal transport principles to continuous generative modeling via Flow Matching, providing a downstream continuous-flow application that relies on efficient transport formulations.
Paper: Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow, Xingchao Liu et al. (2023). Uses straight-path probability transport trajectories to learn generative flows, generalizing discrete optimal transport couplings to continuous ODE-based domain transfers.
Paper: Stochastic Gradient Descent over P2, Maria Oprea et al. (2026). Extends optimization methodologies into the Wasserstein probability space by studying stochastic gradient descent dynamics directly over distribution manifolds.

Cover for On the Efficiency of Entropic Regularized Algorithms for Optimal Transport

Abstract

We present several new complexity results for the entropic regularized algorithms that approximately solve the optimal transport (OT) problem between two discrete probability measures with at most n atoms. First, we improve the complexity bound of a greedy variant of Sinkhorn, known as Greenkhorn, from Õ(n²ε⁻³) to Õ(n²ε⁻²). Notably, our result can match the best known complexity bound of Sinkhorn and help clarify why Greenkhorn significantly outperforms Sinkhorn in practice in terms of row/column updates as observed by Altschuler et al. (2017). Second, we propose a new algorithm, which we refer to as APDAMD and which generalizes an adaptive primal-dual accelerated gradient descent (APDAGD) algorithm (Dvurechensky et al., 2018) with a prespecified mirror mapping ϕ. We prove that APDAMD achieves the complexity bound of Õ(n²√δε⁻¹) in which δ > 0 stands for the regularity of ϕ. In addition, we show by a counterexample that the complexity bound of Õ(min{n⁹/⁴ε⁻¹, n²ε⁻²}) proved for APDAGD before is invalid and give a refined complexity bound of Õ(n⁵/²ε⁻¹). Further, we develop a deterministic accelerated variant of Sinkhorn via appeal to estimated sequence and prove the complexity bound of Õ(n⁷/³ε⁻⁴/³). As such, we see that accelerated variant of Sinkhorn outperforms Sinkhorn and Greenkhorn in terms of 1/ε and APDAGD and accelerated alternating minimization (AAM) (Guminov et al., 2021) in terms of n. Finally, we conduct the experiments on synthetic and real data and the numerical results show the efficiency of Greenkhorn, APDAMD and accelerated Sinkhorn in practice.

Topics

adaptive algorithms complexity results deterministic numerical results optimization problems

Keywords

optimal transport entropic regularization Sinkhorn-Knopp algorithm greedy coordinate descent Wasserstein distances transportation polytope unregularized OT problem minimum cost flows dual objective function

1. Introduction
2. Problem Setup
2.1 Linear programming representation
2.2 Entropic regularized OT and its dual form
2.3 Properties of dual entropic regularized OT
3. Greenkhorn
3.1 Complexity analysis-bounding dual objective values
3.2 Complexity analysis-bounding the number of iterations
4. Adaptive Primal-Dual Accelerated Mirror Descent
4.1 General setup
4.2 Properties of APDAMD
4.3 Complexity analysis for APDAMD
4.4 Revisiting APDAGD
5. Accelerating Sinkhorn
5.1 Algorithmic procedure
5.2 Technical lemmas
5.3 Main results
6. Experiments
6.1 Synthetic images
6.2 MNIST images
7. Conclusion
Acknowledgements
References

Knowls

Knowl 1 — Improved Computational Complexity of Greenkhorn for Optimal Transport
theoretical result
For discrete optimal transport between two probability distributions $r, c \in \Delta_n = \{v \in \mathbb{R}_+^n : \sum_{i=1}^n v_i = 1\}$ with cost matrix $C \in \mathbb{R}_+^{n \times n}$ , the Greenkhorn algorithm (a greedy coordinate descent variant of the Sinkhorn algorithm applied to entropic regularized optimal transport with marginal regularization and matrix rounding) returns an $\varepsilon$ -approximate transportation plan $\hat{X} \in \mathbb{R}_+^{n \times n}$ satisfying $\hat{X}\mathbf{1}_n = r$ , $\hat{X}^\top\mathbf{1}_n = c$ , and $\langle C, \hat{X} \rangle \le \langle C, X^* \rangle + \varepsilon$ in a total number of arithmetic operations bounded by:

$O\left(\frac{n^2 \|C\|_\infty^2 \log(n)}{\varepsilon^2}\right)$

where $\|C\|_\infty = \max_{1 \le i,j \le n} C_{ij}$ and $X^*$ is an optimal unregularized transportation plan. This improves the previous best-known complexity bound for Greenkhorn of $\tilde{O}(n^2 \varepsilon^{-3})$ and matches the state-of-the-art computational complexity bound of standard Sinkhorn.
Knowl 2 — Greenkhorn Algorithm for Approximate Optimal Transport
algorithm
The Greenkhorn algorithm is a greedy coordinate descent procedure for approximating the optimal transport problem. Given cost matrix $C \in \mathbb{R}_+^{n \times n}$ , target marginals $r, c \in \Delta_n$ , and accuracy $\varepsilon > 0$ , the overall scheme sets regularization $\eta = \frac{\varepsilon}{4 \log(n)}$ , tolerance $\varepsilon' = \frac{\varepsilon}{8 \|C\|_\infty}$ , perturbs the marginals to ensure strictly positive entries $\tilde{r} = (1 - \frac{\varepsilon'}{8})r + \frac{\varepsilon'}{8n}\mathbf{1}_n$ and $\tilde{c} = (1 - \frac{\varepsilon'}{8})c + \frac{\varepsilon'}{8n}\mathbf{1}_n$ , runs coordinate updates, and rounds the resulting plan to satisfy exact marginal constraints.
Input: Cost matrix $C \in \mathbb{R}_+^{n \times n}$ , marginals $r, c \in \Delta_n$ , error tolerance $\varepsilon > 0$
Set $\eta = \varepsilon / (4 \log n)$ and $\varepsilon' = \varepsilon / (8 \|C\|_\infty)$
Set $\tilde{r} = (1 - \varepsilon'/8)r + (\varepsilon'/(8n))\mathbf{1}_n$ and $\tilde{c} = (1 - \varepsilon'/8)c + (\varepsilon'/(8n))\mathbf{1}_n$
Initialize $t = 0$ , $u^0 = 0_n \in \mathbb{R}^n$ , $v^0 = 0_n \in \mathbb{R}^n$
Define matrix $B(u, v)_{ij} = \exp(u_i + v_j - C_{ij}/\eta)$ for all $i, j \in [n]$
Define progress measure $\rho(a, b) = b - a + a \log(a / b)$
while $\|B(u^t, v^t)\mathbf{1}_n - \tilde{r}\|_1 + \|B(u^t, v^t)^\top\mathbf{1}_n - \tilde{c}\|_1 > \varepsilon'/2$ do
     $I = \text{argmax}_{1 \le i \le n} \rho(\tilde{r}_i, (B(u^t, v^t)\mathbf{1}_n)_i)$
     $J = \text{argmax}_{1 \le j \le n} \rho(\tilde{c}_j, (B(u^t, v^t)^\top\mathbf{1}_n)_j)$
    if $\rho(\tilde{r}_I, (B(u^t, v^t)\mathbf{1}_n)_I) > \rho(\tilde{c}_J, (B(u^t, v^t)^\top\mathbf{1}_n)_J)$ then
         $u^{t+1}_I = u^t_I + \log(\tilde{r}_I) - \log((B(u^t, v^t)\mathbf{1}_n)_I)$
         $u^{t+1}_i = u^t_i$ for all $i \ne I$
         $v^{t+1} = v^t$
    else
         $v^{t+1}_J = v^t_J + \log(\tilde{c}_J) - \log((B(u^t, v^t)^\top\mathbf{1}_n)_J)$
         $v^{t+1}_j = v^t_j$ for all $j \ne J$
         $u^{t+1} = u^t$
    end if
     $t = t + 1$
end while
Let $\tilde{X} = B(u^t, v^t)$
Round $\tilde{X}$ to $\hat{X}$ such that $\hat{X}\mathbf{1}_n = r$ and $\hat{X}^\top\mathbf{1}_n = c$
Output: $\hat{X}$
Each iteration of coordinate selection and update takes $O(n)$ arithmetic operations, requiring $O(n \|C\|_\infty^2 \log(n) \varepsilon^{-2})$ iterations, which leads to total complexity $O(n^2 \|C\|_\infty^2 \log(n) \varepsilon^{-2})$ .
Knowl 3 — Accelerated Sinkhorn Algorithm for Optimal Transport
algorithm
Accelerated Sinkhorn is a deterministic algorithm that combines Nesterov's estimate sequences, coordinate updates, and a monotone line-search step to solve the dual entropic optimal transport problem.
Input: Cost matrix $C \in \mathbb{R}_+^{n \times n}$ , marginals $r, c \in \Delta_n$ , error tolerance $\varepsilon > 0$
Set $\eta = \varepsilon / (4 \log n)$ and $\varepsilon' = \varepsilon / (8 \|C\|_\infty)$
Set $\tilde{r} = (1 - \varepsilon'/8)r + (\varepsilon'/(8n))\mathbf{1}_n$ and $\tilde{c} = (1 - \varepsilon'/8)c + (\varepsilon'/(8n))\mathbf{1}_n$
Initialize $t = 0$ , $\theta_0 = 1$ , $\check{u}^0 = \tilde{u}^0 = \check{v}^0 = \tilde{v}^0 = 0_n$
Define dual objective $\phi(u, v) = \log(\|B(u, v)\|_1) - u^\top\tilde{r} - v^\top\tilde{c}$ with $B(u, v)_{ij} = \exp(u_i + v_j - C_{ij}/\eta)$
while $\|B(u^t, v^t)\mathbf{1}_n - \tilde{r}\|_1 + \|B(u^t, v^t)^\top\mathbf{1}_n - \tilde{c}\|_1 > \varepsilon'/2$ do
     $(\bar{u}^t, \bar{v}^t) = (1 - \theta_t)(\check{u}^t, \check{v}^t) + \theta_t(\tilde{u}^t, \tilde{v}^t)$
     $\tilde{u}^{t+1} = \tilde{u}^t - \frac{1}{2\theta_t}(\frac{B(\bar{u}^t, \bar{v}^t)\mathbf{1}_n}{\|B(\bar{u}^t, \bar{v}^t)\|_1} - \tilde{r})$
     $\tilde{v}^{t+1} = \tilde{v}^t - \frac{1}{2\theta_t}(\frac{B(\bar{u}^t, \bar{v}^t)^\top\mathbf{1}_n}{\|B(\bar{u}^t, \bar{v}^t)\|_1} - \tilde{c})$
     $(\hat{u}^t, \hat{v}^t) = (\bar{u}^t, \bar{v}^t) + \theta_t((\tilde{u}^{t+1}, \tilde{v}^{t+1}) - (\tilde{u}^t, \tilde{v}^t))$
    if $t$ is even then
         $\hat{u}^t_{new} = \hat{u}^t + \log(\tilde{r}) - \log(B(\hat{u}^t, \hat{v}^t)\mathbf{1}_n)$ and $\hat{v}^t_{new} = \hat{v}^t$
    else
         $\hat{u}^t_{new} = \hat{u}^t$ and $\hat{v}^t_{new} = \hat{v}^t + \log(\tilde{c}) - \log(B(\hat{u}^t, \hat{v}^t)^\top\mathbf{1}_n)$
    end if
     $(u^t, v^t) = \text{argmin}_{(u, v) \in \{(\check{u}^t, \check{v}^t), (\hat{u}^t_{new}, \hat{v}^t_{new})\}} \phi(u, v)$
    if $t$ is even then
         $\check{u}^{t+1} = u^t + \log(\tilde{r}) - \log(B(u^t, v^t)\mathbf{1}_n)$ and $\check{v}^{t+1} = v^t$
    else
         $\check{u}^{t+1} = u^t$ and $\check{v}^{t+1} = v^t + \log(\tilde{c}) - \log(B(u^t, v^t)^\top\mathbf{1}_n)$
    end if
     $\theta_{t+1} = \frac{\theta_t(\sqrt{\theta_t^2 + 4} - \theta_t)}{2}$
     $t = t + 1$
end while
Round $B(u^t, v^t)$ to $\hat{X}$ such that $\hat{X}\mathbf{1}_n = r$ and $\hat{X}^\top\mathbf{1}_n = c$
Output: $\hat{X}$
Knowl 4 — Computational Complexity of Accelerated Sinkhorn
theoretical result
The accelerated Sinkhorn scheme computes an $\varepsilon$ -approximate transportation plan for two discrete distributions of size $n$ in at most

$O\left(\frac{n^{7/3}\|C\|_\infty^{4/3} (\log(n))^{1/3}}{\varepsilon^{4/3}}\right)$

arithmetic operations. Each outer iteration requires $O(n^2)$ arithmetic operations to compute matrix-vector products with $B(\bar{u}^t, \bar{v}^t)$ , and the total iteration count is bounded by $O(n^{1/3} \|C\|_\infty^{4/3} (\log n)^{1/3} \varepsilon^{-4/3})$ . This bound improves upon Sinkhorn and Greenkhorn ( $O(\varepsilon^{-2})$ ) in terms of $1/\varepsilon$ and upon APDAGD and Accelerated Alternating Minimization ( $O(n^{5/2})$ ) in terms of $n$ , making it especially advantageous in higher precision regimes ( $n \ll 1/\varepsilon$ , e.g., $\varepsilon \le 10^{-4}$ ).
Knowl 5 — Adaptive Primal-Dual Accelerated Mirror Descent (APDAMD) for Optimal Transport
algorithm
APDAMD solves linearly constrained convex optimization problems of the form $\min_{x \in Q} f(x) \text{ s.t. } Ax = b$ via its smooth dual $\min_{\lambda} \tilde{\phi}(\lambda) := \langle \lambda, b \rangle + \max_{x} \{-f(x) - \langle A^\top\lambda, x\rangle\}$ , using a dual mirror mapping $\varphi$ with strong convexity parameter $1/\delta$ w.r.t. the $\ell_\infty$ -norm and an adaptive line search.
Input: Dual objective $\tilde{\phi}$ , matrix $A$ , vector $b$ , error tolerance $\varepsilon'$
Initialize $t = 0$ , $\bar{\alpha}_0 = 0$ , $z^0 = \mu^0 = \lambda^0 = 0_{2n}$ , $L^0 = 1$
repeat
     $M_t = L^t / 2$
    repeat
         $M_t = 2 M_t$
        Compute $\alpha_{t+1} = \frac{1 + \sqrt{1 + 4\delta M_t \bar{\alpha}_t}}{2\delta M_t}$
        Compute $\bar{\alpha}_{t+1} = \bar{\alpha}_t + \alpha_{t+1}$
        Compute $\mu^{t+1} = \frac{\alpha_{t+1} z^t + \bar{\alpha}_t \lambda^t}{\bar{\alpha}_{t+1}}$
        Compute $z^{t+1} = \text{argmin}_{z \in \mathbb{R}^{2n}} \{ \langle z - \mu^{t+1}, \nabla\tilde{\phi}(\mu^{t+1}) \rangle + \frac{B_\varphi(z, z^t)}{\alpha_{t+1}} \}$
        Compute $\lambda^{t+1} = \frac{\alpha_{t+1} z^{t+1} + \bar{\alpha}_t \lambda^t}{\bar{\alpha}_{t+1}}$
    until $\tilde{\phi}(\lambda^{t+1}) - \tilde{\phi}(\mu^{t+1}) - \langle \lambda^{t+1} - \mu^{t+1}, \nabla\tilde{\phi}(\mu^{t+1}) \rangle \le \frac{M_t}{2} \|\lambda^{t+1} - \mu^{t+1}\|_\infty^2$
    Compute primal average: $x^{t+1} = \frac{\alpha_{t+1} x(\mu^{t+1}) + \bar{\alpha}_t x^t}{\bar{\alpha}_{t+1}}$ where $x(\mu) = \text{argmax}_x \{ -f(x) - \langle A^\top\mu, x \rangle \}$
    Set $L^{t+1} = M_t / 2$
    Set $t = t + 1$
until $\|A x^t - b\|_1 \le \varepsilon'$
Output: $X^t$ where $x^t = \text{vec}(X^t)$
Knowl 6 — Computational Complexity of APDAMD for Optimal Transport
theoretical result
When applied to the entropic regularized optimal transport problem with a mirror mapping $\varphi$ that is $(1/\delta)$ -strongly convex with respect to the $\ell_\infty$ -norm on $\mathbb{R}^{2n}$ , the APDAMD scheme (combined with perturbed marginals $\tilde{r}, \tilde{c}$ and matrix rounding) outputs an $\varepsilon$ -approximate transportation plan in

$O\left(\frac{n^2 \sqrt{\delta} \|C\|_\infty \log(n)}{\varepsilon}\right)$

arithmetic operations. When using the Euclidean mirror mapping $\varphi(\lambda) = \frac{1}{2n}\|\lambda\|_2^2$ , the strong convexity parameter w.r.t. the $\ell_\infty$ -norm is $1/\delta$ with $\delta = n$ , leading to a complexity bound of $O\left(\frac{n^{5/2} \|C\|_\infty \log(n)}{\varepsilon}\right)$ .
Knowl 7 — Counterexample and Corrected Complexity Bound for APDAGD
theoretical result
The previously published complexity bound of $\tilde{O}(\min\{n^{9/4}\varepsilon^{-1}, n^2\varepsilon^{-2}\})$ for Adaptive Primal-Dual Accelerated Gradient Descent (APDAGD) applied to entropic optimal transport relies on the assumption that the $\ell_2$ -norm of the optimal dual solution $\bar{R} = \|(\alpha^*, \beta^*)\|_2$ is bounded independently of $n$ . This assumption is invalid.

Specifically, for the uniform instance where $C = \mathbf{1}_n \mathbf{1}_n^\top$ and $r = c = \frac{1}{n}\mathbf{1}_n$ , with regularization $\eta = \frac{\varepsilon}{4 \log(n)}$ and tolerance $\varepsilon \in (0, 1)$ , every optimal dual solution $(\alpha^*, \beta^*)$ of the dual entropic regularized OT problem satisfies:

$\|(\alpha^*, \beta^*)\|_2 \ge \frac{1}{2\sqrt{2}} \sqrt{n} = \Omega(\sqrt{n})$

Accounting for this tight lower bound $\bar{R} = \Theta(\sqrt{n})$ and including the necessary marginal perturbation and rounding step, the corrected computational complexity of APDAGD for finding an $\varepsilon$ -approximate transportation plan is:

$O\left(\frac{n^{5/2}\|C\|_\infty \sqrt{\log(n)}}{\varepsilon}\right)$
Knowl 8 — Smooth Dual Formulation and Optimal Solution Bounds in $\ell_\infty$-Norm
theoretical result
The dual problem of the entropic regularized optimal transport problem $\min_{X \in \mathbb{R}_+^{n \times n}, X\mathbf{1}_n=r, X^\top\mathbf{1}_n=c} \langle C, X \rangle - \eta H(X)$ (where $H(X) = -\langle X, \log(X) - \mathbf{1}_{n \times n}\rangle$ ) can be formulated under the change of dual variables $u = \eta^{-1}\alpha$ and $v = \eta^{-1}\beta$ as the smooth optimization problem:

$\min_{u, v \in \mathbb{R}^n} \phi(u, v) := \log(\|B(u, v)\|_1) - u^\top r - v^\top c$

where $B(u, v) \in \mathbb{R}^{n \times n}$ with $B(u, v)_{ij} = \exp(u_i + v_j - C_{ij}/\eta)$ .

The dual function $\phi$ is $2$ -gradient Lipschitz with respect to the $\ell_2$ -norm on $\mathbb{R}^{2n}$ . Furthermore, there exists an optimal dual solution pair $(u^*, v^*)$ bounded in $\ell_\infty$ -norm by:

$\|u^*\|_\infty \le R, \quad \|v^*\|_\infty \le R$

where $R := \frac{\|C\|_\infty}{\eta} + \log(n) - \log\left(\min_{1 \le i, j \le n}\{r_i, c_j\}\right)$ .
Knowl 9 — Definition of $\varepsilon$-Approximate Transportation Plan
definition
Given two discrete probability vectors $r, c \in \Delta_n = \{v \in \mathbb{R}_+^n : \sum_{i=1}^n v_i = 1\}$ , a cost matrix $C \in \mathbb{R}_+^{n \times n}$ , and an error tolerance $\varepsilon > 0$ , a matrix $\hat{X} \in \mathbb{R}_+^{n \times n}$ is called an $\varepsilon$ -approximate transportation plan for the optimal transport problem if it exactly satisfies the marginal constraints:

$\hat{X}\mathbf{1}_n = r \quad \text{and} \quad \hat{X}^\top\mathbf{1}_n = c$

and achieves transportation cost within $\varepsilon$ of the optimal cost:

$\langle C, \hat{X} \rangle \le \langle C, X^* \rangle + \varepsilon$

where $X^* \in \text{argmin}_{X \in \mathbb{R}_+^{n \times n}, X\mathbf{1}_n=r, X^\top\mathbf{1}_n=c} \langle C, X \rangle$ is an exact optimal transportation plan.
Knowl 10 — Empirical Robustness and Efficiency of Entropic Regularized OT Algorithms
empirical result
Empirical comparisons across synthetic images ( $20 \times 20$ ) and real MNIST handwritten digits ( $28 \times 28$ , normalized with $10^{-6}$ smoothing to ensure dense support) demonstrate three key findings:
1. Greenkhorn consistently requires fewer row/column updates than Sinkhorn across different regularization parameters $\eta \in \{1, 1/5, 1/9\}$ to achieve the same distance to the transportation polytope.
2. APDAMD (equipped with $\ell_\infty$ -norm adaptive line search and $\varphi(\lambda) = \frac{1}{2n}\|\lambda\|_2^2$ ) is significantly more numerically stable and robust than APDAGD and the stochastic baseline GCPB as regularization parameter $\eta$ decreases ( $1/\eta \in \{1, 5, 9\}$ ).
3. Deterministic Accelerated Sinkhorn outperforms standard Sinkhorn in terms of row/column updates, especially as higher accuracy is pursued.

Coverage note — Omitted only the intermediate algebraic convergence rate proofs (Lemmas 5, 10, 14, 15, 22, 23) and the standard matrix rounding subroutine from Altschuler et al. (2017) which is treated as an existing black box.

References

1.B. K. Abid and R. M. Gower. Greedy stochastic algorithms for entropy-regularized optimal transport problems. In AISTATS, 2018.
2.Z. Allen-Zhu, Y. Li, R. Oliveira, and A. Wigderson. Much faster algorithms for matrix scaling. In FOCS, pages 890–901. IEEE, 2017.
3.J. Altschuler, J. Weed, and P. Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In NeurIPS, pages 1964–1974, 2017.
4.J. Altschuler, F. Bach, A. Rudi, and J. Niles-Weed. Massively scalable Sinkhorn distances via the Nyström method. In NeurIPS, pages 4429–4439, 2019.
5.M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In ICML, pages 214–223, 2017.
6.Y. Balaji, R. Chellappa, and S. Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. In NeurIPS, 2020.
7.E. Bernton, P. E. Jacob, M. Gerber, and C. P. Robert. On parameter estimation with the Wasserstein distance. Information and Inference: A Journal of the IMA, 8(4):657–676, 2019.
8.D. Bertsimas and J. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
9.A. N. Bhagoji, D. Cullina, and P. Mittal. Lower bounds on adversarial robustness from optimal transport. In NeurIPS, pages 7498–7510, 2019.
10.J. Blanchet and K. Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565–600, 2019.
11.J. Blanchet, A. Jambulapati, C. Kent, and A. Sidford. Towards optimal running times for optimal transport. ArXiv Preprint: 1810.07717, 2018.
12.J. Blanchet, Y. Kang, and K. Murthy. Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830–857, 2019.
13.M. Blondel, V. Seguy, and A. Rolet. Smooth and sparse optimal transport. In AISTATS, pages 880–889, 2018.
14.N. Bonneel, J. Rabin, G. Peyré, and H. Pfister. Sliced and radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22–45, 2015.
15.M. Carrière, M. Cuturi, and S. Oudot. Sliced Wasserstein kernel for persistence diagrams. In ICML, pages 1–10, 2017.
16.D. Chakrabarty and S. Khanna. Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. In 1st Symposium on Simplicity in Algorithms, 2018.
17.L. Chizat, P. Roussillon, F. Léger, F-X. Vialard, and G. Peyré. Faster Wasserstein distance estimation with the Sinkhorn divergence. In NeurIPS, pages 2257–2269, 2020.
18.M. B. Cohen, A. Madry, D. Tsipras, and A. Vladu. Matrix scaling and balancing via box constrained Newton’s method and interior point methods. In FOCS, pages 902–913. IEEE, 2017.
19.N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(9): 1853–1865, 2017.
20.M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurIPS, pages 2292–2300, 2013.
21.M. Cuturi and A. Doucet. Fast computation of Wasserstein barycenters. In ICML, pages 685–693, 2014.
22.M. Cuturi and G. Peyré. A smoothed dual approach for variational Wasserstein problems. SIAM Journal on Imaging Sciences, 9(1):320–343, 2016.
23.M. Cuturi, O. Teboul, and J-P. Vert. Differentiable ranks and sorting using optimal transport. In NeurIPS, pages 6861–6871, 2019.
24.Y. Dong, Y. Gao, R. Peng, I. Razenshteyn, and S. Sawlani. A study of performance of optimal transport. ArXiv Preprint: 2005.01182, 2020.
25.R. M. Dudley. The speed of mean Glivenko-Cantelli convergence. The Annals of Mathematical Statistics, 40(1):40–50, 1969.
26.P. Dvurechenskii, D. Dvinskikh, A. Gasnikov, C. Uribe, and A. Nedich. Decentralize and randomize: Faster algorithm for Wasserstein barycenters. In NeurIPS, pages 10783– 10793, 2018.
27.P. Dvurechensky, A. Gasnikov, and A. Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm. In ICML, pages 1367–1376, 2018.
28.Olivier Fercoq and Peter Richtárik. Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization, 25(4):1997–2023, 2015.
29.J. Feydy, T. Séjourné, F-X. Vialard, S-I. Amari, A. Trouvé, and G. Peyré. Interpolating between optimal transport and MMD using Sinkhorn divergences. In AISTATS, pages 2681–2690. PMLR, 2019.
30.R. Flamary and N. Courty. POT: Python optimal transport library, 2017. URL https://github.com/rflamary/POT.
31.N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707–738, 2015.
32.H. N. Gabow and R. E. Tarjan. Faster scaling algorithms for general graph matching problems. Journal of the ACM (JACM), 38(4):815–853, 1991.
33.A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic optimization for large-scale optimal transport. In NeurIPS, pages 3440–3448, 2016.
34.A. Genevay, L. Chizat, F. Bach, M. Cuturi, and G. Peyré. Sample complexity of Sinkhorn divergences. In AISTATS, pages 1574–1583. PMLR, 2019.
35.I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of Wasserstein GANs. In NeurIPS, pages 5767–5777, 2017.
36.S. Guminov, P. Dvurechensky, N. Tupitsa, and A. Gasnikov. On a combination of alternating minimization and Nesterov’s momentum. In ICML, pages 3886–3898. PMLR, 2021.
37.W. Guo, N. Ho, and M. Jordan. Fast algorithms for computational optimal transport and Wasserstein barycenter. In AISTATS, pages 2088–2097. PMLR, 2020.
38.N. Ho, V. Huynh, D. Phung, and M. I. Jordan. Probabilistic multilevel clustering via composite transportation distance. AISTATS, pages 3149–3157, 2019.
39.A. Jambulapati, A. Sidford, and K. Tian. A direct tilde {O}(1/epsilon) iteration parallel algorithm for optimal transport. In NeurIPS, pages 11355–11366, 2019.
40.B. Kalantari and L. Khachiyan. On the complexity of nonnegative matrix scaling. Linear Algebra and its Applications, 240:87–103, 1996.
41.B. Kalantari, I. Lari, F. Ricca, and B. Simeone. On the complexity of general matrix scaling and entropy minimization via the RAS algorithm. Mathematical Programming, 112(2): 371–401, 2008.
42.L. V. Kantorovich. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), volume 37, pages 199–201, 1942.
43.P. A. Knight. The Sinkhorn-Knopp algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, 30(1):261–275, 2008.
44.S. Kolouri, K. Nadjahi, U. Simsekli, R. Badeau, and G. Rohde. Generalized sliced Wasserstein distances. In NeurIPS, pages 261–272, 2019.
45.H. W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83–97, 1955.
46.H. W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 3(4):253–258, 1956.
47.N. Lahn, D. Mulchandani, and S. Raghvendra. A graph theoretic additive approximation of optimal transport. In NeurIPS, pages 13813–13823, 2019.
48.Y. T. Lee and A. Sidford. Path finding methods for linear programming: Solving linear programs in $\tilde{O}(\text{sqrt}(\text{rank}))$ iterations and faster algorithms for maximum flow. In FOCS, pages 424–433. IEEE, 2014.
49.J. Lei. Convergence and concentration of empirical measures under wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767–798, 2020.
50.Q. Lin, Z. Lu, and L. Xiao. An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization. SIAM Journal on Optimization, 25(4):2244–2273, 2015.
51.T. Lin, N. Ho, and M. Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In ICML, pages 3982–3991, 2019a.
52.T. Lin, Z. Hu, and X. Guo. Sparsemax and relaxed Wasserstein for topic sparsity. In WSDM, pages 141–149. ACM, 2019b.
53.H. Lu, R. Freund, and V. Mirrokni. Accelerating greedy coordinate descent methods. In ICML, pages 3263–3272, 2018.
54.G. Mena and J. Niles-Weed. Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem. In NeurIPS, pages 4541–4551, 2019.
55.G. Monge. Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, 1781.
56.J. Munkres. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957.
57.Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
58.Y. Nesterov. Lectures on Convex Optimization, volume 137. Springer, 2018.
59.K. Nguyen, N. Ho, T. Pham, and H. Bui. Distributional sliced-Wasserstein and applications to generative modeling. In ICLR, 2021. URL https://openreview.net/forum?id=QYjO7OACDK.
60.X. Nguyen. Convergence of latent mixing measures in finite and infinite mixture models. Annals of Statistics, 4(1):370–400, 2013.
61.X. Nguyen. Borrowing strength in hierarchical Bayes: posterior concentration of the Dirichlet base measure. Bernoulli, 22(3):1535–1571, 2016.
62.J. B. Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109–129, 1997.
63.J. B. Orlin and R. K. Ahuja. New scaling algorithms for the assignment and minimum mean cycle problems. Mathematical Programming, 54(1):41–56, 1992.
64.J. B. Orlin, S. A. Plotkin, and E. Tardos. Polynomial dual network simplex algorithms. Mathematical Programming, 60(1):255–276, 1993.
65.F-P. Paty and M. Cuturi. Subspace robust Wasserstein distances. In ICML, pages 5072–5081. PMLR, 2019.
66.O. Pele and M. Werman. Fast and robust earth mover’s distance. In ICCV. IEEE, 2009.
67.G. Peyré and M. Cuturi. Computational optimal transport. Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
68.G. Peyré, M. Cuturi, and J. Solomon. Gromov-Wasserstein averaging of kernel and distance matrices. In ICML, pages 2664–2672, 2016.
69.M. S. Pydi and V. Jog. Adversarial risk via optimal transport and optimal couplings. In ICML, pages 7814–7823. PMLR, 2020.
70.K. Quanrud. Approximating optimal transport with linear programs. In SOSA, pages 61–69, 2019.
71.A. Rolet, M. Cuturi, and G. Peyré. Fast dictionary learning with a smoothed Wasserstein loss. In AISTATS, pages 630–638, 2016.
72.M. Schmidt, N. L. Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83–112, 2017.
73.M. H. Schneider and S. A. Zenios. A comparative study of algorithms for matrix balancing. Operations Research, 38(3):439–455, 1990.
74.J. Sherman. Area-convexity, $\ell_\infty$ regularization, and undirected multicommodity flow. In STOC, pages 452–460. ACM, 2017.
75.R. Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. Proceedings of the American Mathematical Society, 45(2):195–198, 1974.
76.M. Sommerfeld and A. Munk. Inference for empirical Wasserstein distances on finite spaces. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1):219–238, 2018.
77.M. Sommerfeld, Y. Zemel, and A. Munk. Optimal transport: Fast probabilistic approximation with exact solvers. Journal of Machine Learning Research, 20:1–23, 2019.
78.S. Srivastava, V. Cevher, Q. Dinh, and D. Dunson. WASP: Scalable Bayes via barycenters of subset posteriors. In AISTATS, pages 912–920, 2015.
79.S. Srivastava, C. Li, and D. Dunson. Scalable Bayes via barycenter in Wasserstein space. Journal of Machine Learning Research, 19(8):1–35, 2018.
80.I. Tolstikhin, O. Bousquet, S. Gelly, and B. Schoelkopf. Wasserstein auto-encoders. In ICLR, 2018.
81.J. van den Brand, Y. T. Lee, Y. P. Liu, T. Saranurak, A. Sidford, Z. Song, and D. Wang. Minimum cost flows, MDPs, and $\ell_1$ -regression in nearly linear time for dense instances. In STOC, pages 859–869, 2021.
82.C. Villani. Optimal Transport: Old and New, volume 338. Springer, 2009.
83.J. Weed and F. Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620–2648, 2019.

Citation

MLA

Lin, T., et al. “On the Efficiency of Entropic Regularized Algorithms for Optimal Transport”. Journal of Machine Learning Research, vol. 23, no. 137, 2022, pp. 1–2, https://www.jmlr.org/papers/v23/20-277.html.

APA

Lin, T., Ho, N., & Jordan, M. I. (2022). On the Efficiency of Entropic Regularized Algorithms for Optimal Transport. Journal of Machine Learning Research, 23(137), 1–42. https://www.jmlr.org/papers/v23/20-277.html

Chicago

Lin, T., N. Ho, and M. I. Jordan. 2022. “On the Efficiency of Entropic Regularized Algorithms for Optimal Transport”. Journal of Machine Learning Research 23 (137): 1–42. https://www.jmlr.org/papers/v23/20-277.html.

Harvard

Lin, T., Ho, N. and Jordan, M.I. (2022) “On the Efficiency of Entropic Regularized Algorithms for Optimal Transport”, Journal of Machine Learning Research, 23(137), pp. 1–42. Available at: https://www.jmlr.org/papers/v23/20-277.html.

Vancouver

1. Lin T, Ho N, Jordan MI (2022) On the Efficiency of Entropic Regularized Algorithms for Optimal Transport. Journal of Machine Learning Research 23:1–42

BibTeX

@article{JMLR:v23:20-277,
  author  = {Tianyi Lin and Nhat Ho and Michael I. Jordan},
  title   = {On the Efficiency of Entropic Regularized Algorithms for Optimal Transport},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {137},
  pages   = {1--42},
  url     = {http://jmlr.org/papers/v23/20-277.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On the Efficiency of Entropic Regularized Algorithms for Optimal Transport

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Improved Computational Complexity of Greenkhorn for Optimal Transport

Knowl 2 — Greenkhorn Algorithm for Approximate Optimal Transport

Knowl 3 — Accelerated Sinkhorn Algorithm for Optimal Transport

Knowl 4 — Computational Complexity of Accelerated Sinkhorn

Knowl 5 — Adaptive Primal-Dual Accelerated Mirror Descent (APDAMD) for Optimal Transport

Knowl 6 — Computational Complexity of APDAMD for Optimal Transport

Knowl 7 — Counterexample and Corrected Complexity Bound for APDAGD

Knowl 8 — Smooth Dual Formulation and Optimal Solution Bounds in $\ell_\infty$-Norm

Knowl 9 — Definition of $\varepsilon$-Approximate Transportation Plan

Knowl 10 — Empirical Robustness and Efficiency of Entropic Regularized OT Algorithms

References

Citation

BibTeX

Access the Paper