- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes an optimal transport (OT) cost matrix compression method inspired by the Thorup–Zwick sampling scheme. By retaining exact local distances and approximating non-local distances via landmarks, the method achieves sub-quadratic space complexity with bounded metric distortion. Based on this compressed representation, the authors adapt the push-relabel algorithm to accelerate approximate OT computation and extend the framework to incremental minimum-cost bipartite matching, establishing the corresponding complexity bounds and approximation guarantees.
Critical strengths
- The proposed algorithm reduces both space and computational complexity while retaining theoretical approximation guarantees.
- In experiments, the proposed algorithm demonstrates a clear memory advantage (over dense baselines such as Sinkhorn).
Critical weaknesses
Insufficient baselines: For example, a simple baseline can randomly partition the uniformly weighted samples into batches of size , solve each batch exactly via POT (ot.emd), and merge them into a globally valid coupling. In preliminary experiments on a Gaussian-to-data benchmark with cost (, ), this method achieved a relative objective error around with faster runtime. Although this setup differs from the paper, it indicates that simple classical baselines can be competitive. The authors should include such baselines.
Questions for authors
- Figures 1, 4, and 7 suffer from formatting and readability problems: legends, axis ticks, and labels frequently overlap, and subplots are noticeably misaligned. This significantly degrades the readability of the experimental results. Unless there is a specific justification for this layout, the authors should redraw these figures properly.
- In lines 688–690, the paper deduces that -feasibility under implies standard dual feasibility under because . Could the authors clarify how this inference is derived?
- Is the proposed algorithm limited only to uniformly weighted points with equal support sizes ()? Can the framework be extended to more general settings, such as non-uniform marginals and differing support sizes ()?
- Have the authors considered scalable approaches based on hierarchical, multi-scale, or column-generation schemes? To the best of my knowledge, certain methods in these categories can obtain high-precision solutions with a linear memory footprint and high efficiency, while also being accelerated on GPUs. If relevant to the scope of this work, it would be beneficial to incorporate them into the related work discussion.
Response to Reviewer xT82
We thank the reviewer for their careful reading and thoughtful feedback.
Response: Thank you for suggesting this baseline. Random batching produces a valid coupling, but its relative error can be unbounded even for two independent sets of points sampled uniformly from the unit square, using Euclidean distance as the ground cost.
For two sets of n points, the expected average Euclidean edge length in an optimal matching is Θ(logn/n), which approaches zero as n increases (Ajtai, Komlós, and Tusnády, 1984). If we independently partition the sets into random batches of size B, pair the batches independently of their coordinates, and solve each batch pair exactly, the expected average cost is instead Θ(logB/B). Consequently, the ratio of expected costs is $\frac{\mathbb{E}[C_{\mathrm{batch}}]} {\mathbb{E}[\mathrm{OPT}_n]}= \Theta\left(\sqrt{\frac{n\log B}{B\log n}}\right)$, which grows without bound for fixed B as n→∞.
This does not contradict the favorable results reported on the reviewer’s benchmark, but shows that random batching lacks a uniform constant approximation guarantee. Our compressed representation provides a bounded factor 3-approximation independent of n. Our experiments show the same trend: with fixed batch size B=128, the mean cost ratio increases from 1.6010 at n=512 to 4.8696 at n=4096, while our two-level GPU solver achieves mean ratios of 1.0405–1.0491 across these sizes, using additive ε=0.001 on diameter-normalized inputs and evaluating matching costs under the original Euclidean metric.
Response: We agree and will redraw the affected figures with larger labels, consistent subplot alignment, and sufficient spacing between legends, ticks, and axes.
Response: The reviewer is correct that domination of the original costs by the rounded proxy costs does not imply dual feasibility under the original costs. We have corrected the argument. The revised analysis establishes the additive guarantee under the proxy costs and then uses the distortion bound to obtain the approximation factor.
Response: The framework extends to non-uniform masses through the reduction of Lahn, Mulchandani, and Raghvendra, as described in Appendix E.1. The reduction creates collocated copies of support points. While compression is still performed over the original support points, storing the expanded matching requires an additional O(n/ε) space, which is now included in our bounds (See Theorem 2 and Appendix E)
Response: Thank you for highlighting these approaches. Our experiments already include a comparison with HiRef, a hierarchical-refinement method that produces explicit matchings. We will expand the related-work discussion to address multiscale and column-generation approaches and clarify their assumptions and guarantees.
Our contribution is a compressed representation of general metric costs with provable distortion, together with algorithms that operate directly on this representation. We will make this distinction clearer when discussing other approaches to reducing OT memory usage.