Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

A Survey on Algorithmic Developments in Optimal Transport Problem with Applications

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This survey argues that optimal transport has matured from Monge's non-convex map problem into a widely used algorithmic framework, and it maps the theoretical formulations, the main approximation algorithms, and applications such as…

desk verdict A readable survey with no new results whose core algorithm restatements are mathematically wrong; the theory sections are salvageable but the paper as submitted should be desk-rejected. read the letter →

arxiv 2501.06247 v1 pith:N3QTF3XD submitted 2025-01-08 cs.DS cs.AIcs.LGmath.OCstat.ML

Sina Moradi This is my paper · ORCID
classification cs.DScs.AIcs.LGmath.OCstat.ML MSC 49Q2290C08
keywords optimaltransportWassersteindistanceKantorovichrelaxationentropicregularizationSinkhornalgorithmprimal-dualmethodsWarpingtimeseriesalignment
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is a survey of optimal transport (OT), the problem of moving one distribution of mass onto another at minimum cost. It aims to show that OT has grown from Monge's eighteenth-century transport-map problem and Kantorovich's plan relaxation into a practical framework for quantifying differences between probability distributions. The survey walks through the theoretical core—duality, entropic regularization, multi-marginal and unbalanced variants, and Wasserstein barycenters—then catalogues exact, approximate, and reduction-based algorithms with their complexity bounds. It closes by arguing that OT's practical reach includes machine learning, computer vision, and time-series analysis, with Optimal Transport Warping presented as a robust alternative to Dynamic Time Warping.

What carries the argument

The central object is the Kantorovich transport plan $P\in\mathbb{R}^{n\times m}_+$, a joint distribution whose row and column sums reproduce the source and target measures $a$ and $b$, with total cost $\langle C,P\rangle$. The structural workhorse is the dual pair of Kantorovich potentials $(w,z)$ and the C-transform, $w^C_j=\min_i C_{ij}-w_i$, which converts the dual problem into a concave piecewise-affine maximization and drives auction, primal-dual, and accelerated algorithms. On the computational side, the key identity is the Sinkhorn factorization $P=\operatorname{diag}(u)K\operatorname{diag}(v)$ with Gibbs kernel $K_{ij}=e^{-C_{ij}/\eta}$, which turns entropy-regularized transport into alternating row-and-column scaling updates.

What would settle it

Take the reduction of OT to a positive linear program printed in Section 3.2.3 and run it on a two-point example with $a=(0.5,0.5)$ and $b=(0.4,0.6)$: the printed constraints $Pa=b$, $P^\top \mathbf{1}=\mathbf{1}$ allow plans whose column sums do not match $a$, so the computed optimum will not equal the Wasserstein distance. If the survey's claim that this is an equivalent formulation were correct, that calculation would reproduce the true OT cost.

Watch

Extended reading notes

Core claim

No new theorem is proved; the paper's contribution is an organizing synthesis. Its central claim is that optimal transport provides a unifying mathematical and computational framework for comparing distributions, and that the field's algorithmic development has reached the point where large-scale problems are tractable through entropic regularization, primal-dual methods, and reductions to linear programs. The survey presents the Kantorovich relaxation as the cornerstone that turns Monge's non-convex problem into a convex linear program, identifies the C-transform as the structural mechanism behind dual algorithms, and traces a chain of complexity improvements from Sinkhorn scaling through Greenkhorn, primal-dual accelerated methods, and reduction-based approaches. It also claims that OTW, by framing time-series alignment as an optimal transport problem with an adaptively learned cost and entropic regularization, is more flexible and robust than standard alignment methods.

Load-bearing premise

The survey's value as a reference stands or falls on the assumption that every displayed formula and complexity bound faithfully restates the cited algorithm, because a survey supplies no new derivations to absorb transcription errors.

Editorial extensions

If this is right

  • If the survey's account is accurate, a reader can treat OT as a practical tool for high-dimensional distribution comparison, with epsilon-approximation algorithms reported at roughly $O(n^2/\epsilon)$ or $O(n^{2.5}/\epsilon)$ arithmetic operations in the balanced square case.
  • The Sinkhorn and Greenkhorn family makes entropy-regularized OT scalable, with each Sinkhorn iteration costing $O(mn)$ and with explicit dependence on the desired accuracy $\epsilon$ in the iteration bounds.
  • The reduction-based perspective connects OT to packing and covering linear programs and to bipartite matching, implying that faster-than-$O(n^2/\epsilon)$ OT algorithms would carry consequences for classical matching problems.
  • OTW gives a transport-based alternative to Dynamic Time Warping for time-series alignment, with an adaptively learned cost and an entropy term that balances temporal alignment against probabilistic structure.
  • The survey's organisation implies that Wasserstein barycenters, unbalanced OT, and multi-marginal OT are the natural frontiers where theoretical guarantees and scalable algorithms remain incomplete.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A reader could test the survey's narrative by picking one cited algorithm, implementing the displayed update rules, and checking whether the stated $\epsilon$ complexity is reproduced; discrepancies in transcribed formulas would matter more than the prose claims.
  • The paper's treatment of time-series warping suggests a concrete extension: applying the same transport-warping formulation to multivariate, unevenly sampled, or noisy time series, where Dynamic Time Warping's alignment assumptions are known to be brittle.
  • Because the survey presents complexity bounds drawn from different sources under different assumptions, an implicit takeaway is that these bounds should not be compared across sections without first checking assumptions like $m=n$, bounded costs, or entropic regularization.
  • If the Gibbs-kernel/Sinkhorn machinery is as central as the survey suggests, algorithmic improvements for entropy-regularized OT should transfer directly to time-series warping, since OTW uses the same regularized transport structure.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper is a survey of optimal transport (OT) aimed at a data-science and CS audience. It covers the classical Monge and Kantorovich formulations, duality and C-transforms, entropic regularization, multimarginal and unbalanced extensions, Wasserstein barycenters, and a broad range of algorithms (network simplex, auction, Sinkhorn, Greenkhorn, primal-dual methods, and reduction-based approaches). It also discusses applications, with a focus on Optimal Transport Warping for time series. The paper's stated value is to provide a detailed, self-contained examination of OT algorithms and theory.

Significance. If its restatements were reliable, this survey would be a useful entry point to computational OT and would help readers navigate recent algorithmic developments. The paper does cover many important modern results and makes a genuine effort to organize the literature, including the OTW application. However, a survey's contribution rests entirely on the accuracy of its exposition, and the manuscript contains several errors in load-bearing mathematical definitions and algorithmic statements. These errors currently prevent the paper from serving as a trustworthy reference, so the significance is contingent on substantial corrections.

major comments (3)
  1. [§3.2.3] The reduction of OT to a positive LP is stated with incorrect marginal constraints. The text gives min_{P∈R^{n×n}_+} {⟨C,P⟩ : Pa = b, P^T 1 = 1}. The Kantorovich marginals are P 1_m = a and P^T 1_n = b. As printed, the constraints are dimensionally inconsistent for rectangular plans, and even in the square case they define a different feasible set (for example, they do not enforce the target marginal on the columns). The same defect carries into the 'mixed packing and covering' and 'packing LP' formulations in this section, so the algorithmic content of the section is not reproducible.
  2. [§3.2.1] The Sinkhorn scaling variables are assigned impossible dimensions. The text states u, v ∈ R^{n×m}_+, but the correct domains are u ∈ R^n_+ and v ∈ R^m_+. With u and v as matrices, the factorization P = diag(u)K diag(v) and the elementwise update formulas u ← a/(Kv), v ← b/(K^T u) do not parse, since diag(u) of a matrix is undefined. This is not a cosmetic issue: the iteration cannot be implemented or even checked as written.
  3. [§2.6] The unbalanced optimal transport relaxation is misstated. The paper defines the relaxed problem as min_{\tilde a,\tilde b} L_C(a,b) + τ_1 D_φ(a‖\tilde a) + τ_2 D_φ(b‖\tilde b), but the transport cost term uses the fixed measures a and b rather than the optimization variables \tilde a and \tilde b. As written, the left-hand side is a constant plus two independent divergence terms and is not equal to the right-hand side min_{P} ⟨C,P⟩ + τ_1 D_φ(P1_m‖a) + τ_2 D_φ(P^T1_n‖b). The first term should be L_C(\tilde a, \tilde b). This is a definitional error in a core theoretical section.
minor comments (4)
  1. [End of manuscript] The manuscript contains an orphaned reference to a figure 'test.png' with a URL at the end of the text; this appears to be a leftover from the production process and should be removed.
  2. [§2.7] The sentence 'For K probability distributions {a_k} defined on a shared finite domain {x_k}' is unclear, since the barycenter is supposed to live on a common target domain while the input measures may have different supports. The notation should be made precise.
  3. [§3.2.2] In the APDAGD description, the phrase 'there exists some R > 0 where ‖λ*‖_2 ≤ R < +∞ and λ* is the optimal dual solution with objective value of ‖λ*‖_2' is garbled; the clause 'with objective value of ‖λ*‖_2' should be corrected or removed.
  4. [§4] The applications paragraph cites several works by 'Moradi et al.' on vehicle routing, electric vehicles, and simulated annealing without explaining how these works use optimal transport. The relevance of these citations to the OT applications under discussion should be stated explicitly, or the citations should be removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the survey compiles external, cited results; its mathematical transcription errors are correctness risks, not circular reasoning.

full rationale

This paper is a survey rather than a derivation: it presents no new theorem whose conclusion could coincide with its own premises. The algorithmic sections restate published results (Sinkhorn, Greenkhorn, APDAGD, APDRCD, and related methods) with citations to the originating papers, and the survey's account of OTW is explicitly attributed to the external work of Latorre et al. (2023). The author of the survey, Sina Moradi, does not appear among the cited sources in the theoretical or algorithmic sections, so no load-bearing self-citation chain is present. The Section 4 citations to 'Moradi et al.' are to Nima Moradi and coauthors, a different researcher, and concern vehicle routing, simulated annealing, and public health; those citations are at worst irrelevant padding rather than circular support. The manuscript does contain mathematical transcription errors, most notably in Section 3.2.3, where the reduced positive LP is written as min_{P} {<C,P> : Pa = b, P^T 1 = 1} instead of the standard Kantorovich marginals P 1_m = a and P^T 1_n = b, and in Section 3.2.1, where the Sinkhorn scaling variables are stated to lie in R^{n x m}_+ rather than R^n_+ and R^m_+. However, these are errors in restating external, independently published algorithms; they do not make the survey's claims equivalent to its inputs by construction, and they are better classified as correctness and reliability concerns than as circularity. Accordingly, the appropriate finding is no significant circularity, with score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new parameters, entities, or fitted values. It relies on standard optimal transport results and, unfortunately, on an incorrect restatement of a reduction-based LP formulation.

assumptions (3)
  • standard math Kantorovich duality and complementary slackness for discrete OT (Section 2.2).
    The paper uses strong duality and complementary slackness without proof; these are standard results in LP and OT.
  • standard math Convergence of entropic regularization to the maximum-entropy optimal coupling as η→0 (Section 2.4).
    The paper cites Cominetti and Martín (1994) for this convergence; it is a known theorem.
  • ad hoc to paper The equivalence between OT and a packing LP as stated in Section 3.2.3.
    The paper states 'min_{P} <C,P> : Pa=b, P^T 1=1' as the positive LP reduction. This is not a correct formulation of OT (the marginals are wrong), so the paper's claimed reduction is an ad hoc, inaccurate restatement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Survey on Algorithmic Developments in Optimal Transport Problem with Applications." pith.science (2026). https://pith.science/paper/N3QTF3XD

@misc{pith2026250106247,
  author       = {Pith},
  title        = {Pith review of: A Survey on Algorithmic Developments in Optimal Transport Problem with Applications},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3QTF3XD}},
  note         = {Machine review of arXiv:2501.06247}
}
read the original abstract

Optimal Transport (OT) has established itself as a robust framework for quantifying differences between distributions, with applications that span fields such as machine learning, data science, and computer vision. This paper offers a detailed examination of the OT problem, beginning with its theoretical foundations, including the classical formulations of Monge and Kantorovich and their extensions to modern computational techniques. It explores cutting-edge algorithms, including Sinkhorn iterations, primal-dual strategies, and reduction-based approaches, emphasizing their efficiency and scalability in addressing high-dimensional problems. The paper also highlights emerging trends, such as integrating OT into machine learning frameworks, the development of novel problem variants, and ongoing theoretical advancements. Applications of OT are presented across a range of domains, with particular attention to its innovative application in time series data analysis via Optimal Transport Warping (OTW), a robust alternative to methods like Dynamic Time Warping. Despite the significant progress made, challenges related to scalability, robustness, and ethical considerations remain, necessitating further research. The paper underscores OT's potential to bridge theoretical depth and practical utility, fostering impactful advancements across diverse disciplines.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. UG-UMRE: Uncertainty-Guided Modality Augmentation and Distributional Calibration for Unified Multimodal Relation Extraction

    cs.CV 2026-08 conditional novelty 6.0 of 10

    A multimodal relation extraction system that models text and image features as Gaussian distributions, denoises them with uncertainty-aware contrastive learning, and aligns the distributions with symmetric KL achieves...

  2. REMOTE: A Unified Multimodal Relation Extraction Framework with Multilevel Optimal Transport and Mixture-of-Experts

    cs.MM 2025-09 conditional novelty 5.0 of 10

    REMOTE is a unified multimodal relation extraction framework and dataset covering intra-modal and inter-modal relation triplets, reporting state-of-the-art F1 scores on three datasets.

Reference graph

Works this paper leans on

14 extracted references · 8 canonical work pages · cited by 2 Pith papers

  1. [3]

    The Monge-Kantorovich problem for distributions and applications

    Guy Bouchitté, Giuseppe Buttazzo, and Luigi De Pascale. The monge-kantorovich problem for distributions and applications. arXiv preprint arXiv:1312.5453,

    work page Pith review arXiv

  2. [8]

    doi: https://doi.org/10.1016/j.es wa.2024.125183

    ISSN 0957-4174. doi: https://doi.org/10.1016/j.es wa.2024.125183. URL https://www.sciencedirect.com/science/article/pii/S0957417424020505. Nima Moradi, V ahid Kayvanfar, and Majid Rafiee. An efficient p opulation-based simulated an- nealing algorithm for 0–1 knapsack problem. Engineering with Computers , 38(3):2771–2790,

    work page arXiv 2024

  3. [9]

    doi: https://doi.org/10.10 16/j.cie.2023.109552

    ISSN 0360-8352. doi: https://doi.org/10.10 16/j.cie.2023.109552. URL https://www.sciencedirect.com/science/article/pii/S0360835223005764. Nima Moradi, Niloufar Mirzavand Boroujeni, Navid Aftabi, a nd Amin Aslani. Two-echelon electric vehicle routing problem in parcel delivery: A lite rature review. arXiv preprint arXiv:2412.19395, 2024a. Nima Moradi, V ah...

    arXiv 2023

  4. [11]

    Approximating optimal transport with linear programs

    Kent Quanrud. Approximating optimal transport with linear programs. arXiv preprint arXiv:1810.05957,

    arXiv

  5. [12]

    doi: https://doi.org/10.1111/risa. 14033. URL https://onlinelibrary.wiley.com/doi/abs/10.1111/risa.14033. Robert E Tarjan. Dynamic trees as search trees via euler tour s, applied to the network simplex algorithm. Mathematical Programming, 78(2):169–177,

    doi:10.1111/risa

  6. [13]

    An accelerated sto chastic algorithm for solving the optimal transport problem

    Yiling Xie, Yiling Luo, and Xiaoming Huo. An accelerated sto chastic algorithm for solving the optimal transport problem. arXiv preprint arXiv:2203.00813,

    arXiv

  7. [1993]

    URL https://doi.org/10.1287/opre.41.2.338

    doi: 10.1287/opre.41.2.338. URL https://doi.org/10.1287/opre.41.2.338. 25 A PREPRINT - J ANUARY 14, 2025 Gabriel Peyré, Marco Cuturi, et al. Computational optimal t ransport: With applications to data science. F oundations and Trends® in Machine Learning, 11(5-6):355–607,

    work page doi:10.1287/opre.41.2.338 2025

  8. [2018]

    Fast algorithms fo r computational optimal transport and wasserstein barycenter

    Wenshuo Guo, Nhat Ho, and Michael Jordan. Fast algorithms fo r computational optimal transport and wasserstein barycenter. In International Conference on Artificial Intelligence and St atistics, pages 2088–2097. PMLR,

    work page

Show all 14 references
  1. [2019]

    Otw: Optimal transport warping for time series

    Fabian Latorre, Chenghao Liu, Doyen Sahoo, and Steven CH Hoi. Otw: Optimal transport warping for time series. In ICASSP 2023-2023 IEEE International Conference on Acousti cs, Speech and Signal Processing (ICASSP), pages 1–5. IEEE,

    2023

  2. [2021]

    Fast com- putation of optimal transport via entropy-regularized ext ragradient methods

    Gen Li, Y anxi Chen, Y u Huang, Y uejie Chi, H Vincent Poor, and Y uxin Chen. Fast com- putation of optimal transport via entropy-regularized ext ragradient methods. arXiv preprint arXiv:2301.13006,

    arXiv

  3. [2022]

    test.png

    26 This figure "test.png" is available in "png" format from: http://arxiv.org/ps/2501.06247v1

    arXiv

  4. [2023]

    On robust optimal transport: Computational complexity and barycent er computation

    24 A PREPRINT - J ANUARY 14, 2025 Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycent er computation. Advances in Neural Information Processing Systems, 34:21947–21959,

    2025

  5. [2024]

    URL https://doi.org/10.1080/24725854.2024.2439856

    doi: 10.1080/ 24725854.2024.2439856. URL https://doi.org/10.1080/24725854.2024.2439856. 23 A PREPRINT - J ANUARY 14, 2025 Navid Aftabi, Nima Moradi, Fatemeh Mahroo, and Farhad Kianf ar. Sd-abm-ism: An integrated system dynamics and agent-based modeling framework for inf ormati...

    2024

  6. [2025]

    doi: https://doi.org/ 10.1016/j.eswa.2024.125681

    ISSN 0957-4174. doi: https://doi.org/ 10.1016/j.eswa.2024.125681. URL https://www.sciencedirect.com/science/article/pii/S095741742402548X. Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigol let. Near-linear time approximation al- gorithms for optimal transport via sinkh...

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.