On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms

1 Introduction

• Large-scale applications of optimal transport in machine learning and statistics have increased demand for efficient algorithms.The cited applications include Bayesian posterior estimation and sampling, clustering, deep generative models, and domain adaptation.Source: §1 · p. 1
• Existing approaches include Sinkhorn, greedy Greenkhorn, and adapted optimization methods, but their theoretical analysis is still nascent.The paper situates its work against reported complexity bounds for Sinkhorn and Greenkhorn and an asserted APDAGD bound.Source: §1 · p. 2
• Greenkhorn’s complexity improves from eO(n^2ε^-3) to eO(n^2ε^-2), matching Sinkhorn’s best known bound and shedding light on Greenkhorn’s practical performance.The analysis uses a novel upper bound for the dual optimal solution in terms of the ℓ∞ norm.Source: §1 · p. 2
• APDAMD uses adaptive primal-dual accelerated mirror descent for regularized OT, with a complexity bound of eO(n^2√δε^-1).Here δ is the inverse strong-convexity modulus of the Bregman divergence with respect to ℓ∞; the paper states δ=n for a particular divergence choice.Source: §1 · pp. 2–3
• The paper shows that the asserted APDAGD complexity bound is not valid in general and establishes instead eO(n^2.5/ε).The earlier derivation depends on a parameter not explicitly estimated; the paper gives a lower bound showing that parameter depends on n.Source: §1 · p. 3

2 The Optimal Transport Problem

• The original OT problem seeks a minimum-cost nonnegative plan whose row and column sums equal the two input distributions.An ε-approximate plan is described through marginal feasibility and an approximation bound on transportation cost.Source: §2 · p. 4
• Because interior-point methods perform poorly on large-scale problems due to high per-iteration cost, entropic regularization is proposed as a more computationally efficient formulation.The regularized formulation retains the marginal constraints while modifying the objective with an entropy term.Source: §2 · p. 4
• The dual regularized OT problem is an unconstrained optimization model derived by minimizing the Lagrangian over the transportation plan.The section introduces a change of variables for the dual variables before presenting the dual problem.Source: §2 · p. 4
• The Greenkhorn procedure repeatedly selects the row or column with the largest marginal discrepancy and updates it until the stopping condition is met.The supplied algorithm steps identify the largest row and column discrepancies and choose which side to update based on their comparison.Source: §2 · p. 5

3 Greenkhorn

• The bound improves a previous bound ending in ∥C∥∞log(n)ε−3) [Altschuler et al., 2017] to O(n²∥C∥²∞log(n)ε−2), matching Sinkhorn’s best-known complexity.Source: §3 · p. 5

3.1 Complexity analysis—bounding dual objective values

• The analysis bounds an optimal dual solution’s ℓ∞ norm and uses it to bound the iterates’ dual-objective gap, addressing Greenkhorn’s lack of Sinkhorn’s shift property.The proof establishes an inductive bound for the iterates and uses the optimal-solution norm to bound f(u_t, v_t) − f(u*, v*).Source: §3.1 · pp. 6, 7, 9

3.2 Complexity analysis—bounding the number of iterations

• Greenkhorn reaches the stated stopping tolerance within t ≤ 2 + 112nR/ε′ iterations, with total arithmetic operations O(n^2∥C∥∞^2 log(n)ε^-2).The returned transport plan is described as satisfying the marginals and the paper’s approximation condition.Source: §3.2 · pp. 9–11

4.1 General setup

• APDAMD applies a dual method to a general constrained problem with strongly convex f and a mirror mapping that is (1/δ)-strongly convex and 1-smooth in ℓ∞ norm.The dual objective used for regularized OT has a Lipschitz-continuous gradient.Source: §4.1 · pp. 11, 13
• The section describes APDAMD’s dual-only regularization as yielding the best existing bound among that group of algorithms, while noting a later area-convex improvement.It attributes the cited bound to Dvurechensky et al. [2018] and the improvement to Jambulapati et al. [2019].Source: §4.1 · p. 13

4.2 Properties of the APDAMD algorithm

• Algorithm 3 has a finite line search, and its accumulating parameter satisfies ¯α_t ≥ η(t + 1)^2/(8δ∥A∥^2).The section also bounds the total gradient-oracle calls after each iteration.Source: §4.2 · pp. 13, 16

4.3 Complexity analysis for the APDAMD algorithm

• O(n^2√δ∥C∥∞log(n)ε^-1) arithmetic operations suffice for Algorithm 4 to return a feasible transport plan with objective error at most ε.Here δ depends on the mirror mapping used by APDAMD.Source: §4 · p. 11, §4.3 · p. 18
• The complexity bound’s dependence on δ highlights the role of the ℓ∞ norm in analyzing regularized OT and parallels the Greenkhorn analysis of optimal dual solutions.The section notes that Jambulapati et al. [2019] obtained eO(n^2ε^-1) using an area-convex mirror mapping.Source: §4.1 · p. 13, §4.3 · p. 18

4.4 Revisiting the APDAGD algorithm

• The claimed eO(min{n^9/4ε^-1, n^2ε^-2}) APDAGD bound does not hold for regularized OT, but its guarantee remains applicable to other regularized problems with bounded optimal dual solutions.The section reports a counterexample and provides a new APDAGD complexity bound for regularized OT.Source: §4.4 · p. 19
• The earlier analysis’s assumption that R is bounded independently of n is incorrect: the corrected upper bound is ~O(n^(1/2)).R also depends on the minimum entries of the marginals, so a valid algorithm must account for rounding error in r and c.Source: §4.4 · pp. 19–20
• Dvurechensky et al. [2018, Algorithm 4] lacks rounding, so the authors add a rounding procedure in Algorithm 5.Algorithm 5 uses Dvurechensky et al. [2018, Algorithm 3] in Step 3.Source: §4.4 · p. 20
• O(n^(5/2)||C||∞ log(n) ε^-1) arithmetic operations bound the corrected APDAGD algorithm’s cost for approximating regularized OT.Algorithm 5 returns a coupling satisfying the marginals and the stated approximation condition.Source: §4.4 · pp. 20–21
• With φ = (1/2n)||·||2 and δ = n, APDAMD has a complexity bound similar to corrected APDAGD and generalizes it.The authors say APDAMD’s ℓ∞-norm line-search criterion makes it more robust in practice.Source: §4.4 · p. 21

5 Experiments

• The study compares three algorithm pairs on ten randomly selected synthetic image pairs, varies η and foreground coverage, and also evaluates algorithms on MNIST images.Synthetic images are 20 × 20 pixels; foreground coverage varies across 10%, 50%, and 90%.Source: §5.1 · pp. 21–22, §5 · p. 21, §5.2 · p. 24

5.1 Synthetic images

• On synthetic images, Greenkhorn performs better than Sinkhorn and APDAMD in iteration count; APDAMD is more robust, but not faster, than APDAGD under the tested setting.For APDAMD, the tested setting uses δ = n and Bregman divergence (1/2n)∥·∥2; its ∥·∥∞ line-search criterion stabilizes training.Source: Figure 1 · p. 22, §5.1 · p. 23, Figure 2 · p. 23

5.2 MNIST images

• On MNIST, Greenkhorn is fastest by iteration count, while APDAMD outperforms APDAGD in robustness and efficiency and is faster and more robust than APDAGD and GCPB.The real-image results are reported as consistent with the synthetic-image results.Source: §5.2 · p. 24, Figure 4 · p. 25

• The Greenkhorn complexity bound improves to eO(n^2ε^-2), matching Sinkhorn’s best known bound; the authors suggest this helps explain Greenkhorn’s practical performance.Source: §6 · p. 25
• APDAMD has complexity eO(n^2√δ ε^-1), where δ is the inverse strong-convexity module of the Bregman divergence with respect to ∥·∥∞.Source: §6 · p. 25
• On MNIST real images, Figure 5 reports that APDAMD is faster and more robust than APDAGD and GCPB across regularization parameters η ∈ {1, 5, 9}.Source: Figure 5 · p. 26
• The paper establishes an APDAGD complexity bound of eO(n^2.5ε^-1) after giving a counterexample to an existing bound’s general validity.Source: §6 · p. 26
• APDAMD’s bound depends on δ; using the simple upper bound δ = n gives eO(n^2.5ε^-1), motivating investigation of whether δ’s dependence on n can be reduced.Source: §6 · p. 26