- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper provides a clear theoretical characterization of BDRS, and the linear-memory dual formulation and computable certificate are practically valuable. The large-scale experiments demonstrate scalability. However, convergence theory is missing, the independent benefit of O-BDRS is unclear, and the comparison with MDOT-TNT is not aligned at the same accuracy or tolerance.
Critical strengths
-
Valuable theoretical characterization. The paper proves that BDRS is equivalent to IPOT with a single inner iteration and reveals it as Annealed Sinkhorn with momentum and a cooler kernel. This explains the empirical observation that BDRS performs well with a fixed .
-
Reduced persistent memory. Proposition 1 eliminates the explicit transport plan and derives a dual recursion over cumulative scaling vectors, reducing persistent memory from to . The per-iteration work remains .
-
Linear-memory primal-dual certificate. Proposition 3 provides, in exact arithmetic, a computable bound without explicitly forming the transport plan, giving a meaningful optimality certificate.
-
Practical large-scale experiments. The color-transfer experiment and the -pixel, -implicit-entry experiment demonstrate the scalability of the linear-memory implementation.
Critical weaknesses
-
Limited novelty in the algorithmic procedure. BDRS is equivalent to IPOT with , so the iteration itself is not new. The paper should more clearly distinguish between a “new algorithm” and a “new interpretation/dual formulation/certificate” to avoid ambiguity about its contribution.
-
Missing convergence and complexity analysis. The paper provides no global or local convergence guarantee, convergence rate, or iteration complexity. The convergence conditions for IPOT and Annealed Sinkhorn do not directly apply. It would be helpful to discuss the convergence behavior under the inverse-linear schedule and the rate at which the certificate gap decreases.
-
Unclear independent benefit of O-BDRS. With fixed , the acceleration mainly comes from reaching a low effective temperature sooner. Once temperatures are matched, O-BDRS differs little from BDRS. The paper should clarify that primarily accelerates the schedule rather than the dynamics, and provide guidance for choosing
-
The comparison with MDOT-TNT is not aligned at the same accuracy or tolerance. In the experiment, BDRS runs for a fixed 1000 iterations, while MDOT-TNT uses a fixed final inverse temperature . They are not compared at the same true error or the same certified gap . Since MDOT-TNT is a second-order/Newton-type method and is typically more competitive in the high-accuracy regime, the reported speedup should be interpreted only for the specific setting and accuracy level tested. A comparison at matched tolerance or matched true error, including at least one high-accuracy regime, would strengthen the claim.
Questions for authors
-
Can the authors provide convergence conditions or a local convergence discussion for Dual BDRS under the inverse-linear schedule?
-
Since O-BDRS shows little gain after temperature matching, do the authors view mainly as a schedule-acceleration parameter? How should be selected in practice?
-
Can the authors compare BDRS and MDOT-TNT at the same true error or the same certificate tolerance, particularly in the high-accuracy regime? Is the claim intended to be limited to the current fixed setting?
3 comments
Response to Reviewer p4MA (Part 2/2)
W4 & Q3 - Comparison with MDOT-TNT, Matched Cost Speedup, and Scope of the Claim. The color transfer experiment largely follows Kemertas et al. (2025). More details can be found in Appendix G.4, Lines 1595 onwards. Nonetheless, we have three points to make here:
-
is unavailable at . Exact LP solvers are intractable for a problem at this scale. MDOT-TNT also does not provide a certificate but terminates at a final inverse temperature .
-
The speedup claim is conservative. Although is unknown, is the same for both problems. It is thus easy to see that any feasible plan with lower primal cost strictly achieves a smaller true error . Therefore, it is sufficient to simply compare the primal cost. We ran the authors' released MDOT-TNT code on identical L40S GPU on our cluster, at the published benchmark setting (, Kemertas et al., 2025) on both
float32andfloat64(see Line 1601.) The runtimes were 3.5 hours and 7 hours respectively, and both achieved identical costs. Therefore, we opted forfloat32runs to reflect practical situations (see Line 1603). Atfloat32, MDOT-TNT required 3.5 hours to obtain a repaired cost of 0.05074. In contrast, our method required 4 minutes to obtain a repaired cost of 0.05069 (at iteration 160), representing a speed up over MDOT-TNT at matched cost. Running our method for the full iterations yields a lower cost of and a duality gap of . In contrast, MDOT-TNT's cost after still leaves up to a gap).Thus, our speedup ( vs. ) was a conservative comparison over all iterations, in which BDRS also achieved substantially higher accuracy.
At MDOT-TNT's achieved cost, Dual BDRS is faster.
-
Accuracy regime and scope of the speedup claim (Q3). The speedup is specific to the published setting of MDOT-TNT, which is the image color transfer example with . In this comparison, Dual BDRS achieves a lower feasible cost in less time (3.5 hours vs 24 minutes). As mentioned above, even though is unknown, both instances share the same and comparison against the actual cost is sufficient. Our additional experiment described above also shows that Dual BDRS improves on MDOT-TNT’s final feasible cost after approximately 4 minutes. Our results show that we outperform MDOT-TNT on their published large-scale configuration. We further tested MDOT-TNT on and the discussion can be found on Line 1605.
-
Matched budget run with MDOT-TNT at . MDOT-TNT took 3.5 hours to obtain a duality gap of , computed with our lower bound. We ran Dual BDRS for 9K iterations at to obtain a gap of approximately in 3.5 hours.
-
Higher-accuracy MDOT-TNT evaluation (Q3; ongoing). To directly address the reviewer’s request, we are running MDOT-TNT with , each on a single H200 GPU in
float64. The low-memory implementation we used from the original authors (Kemertas et al., 2025) specifies a switch tofloat64when . We will report these costs separately since they are run in a different regime. Nonetheless, they assess the attainable primal costs and certified gaps.
The author addressed some of my questions, so I raised my score. Also, strangely, the BDRS citation does not include a journal or conference?
Response to Reviewer p4MA (Part 1/2)
We thank the reviewer for recognizing the value of the BDRS-IPOT-AS connection, the linear memory, the certificate, as well as the large-scale experiments. We address the questions and weaknesses below.
W1 - Algorithmic Novelty vs. Concurrent Literature. We respectfully disagree that our contribution has limited novelty simply because BDRS is equivalent to IPOT with L=1. We agree the BDRS iteration itself is not new and Dual BDRS produces identical iterates; the algorithmic contributions are O-BDRS and the linear-memory certificate. We would like to highlight two points. First, this equivalence itself was previously unrecognized, and we state it up front in Section 3.1 as a theoretical characterization. Second, neither IPOT (L=1) (Xie et al., 2020) nor primal-dual BDRS (Ma et al., 2025) can execute in O(N) memory.
The value of our dual reformulation is further supported by two concurrent preprints posted after our Sept 25, 2026 submission:
Both concurrent works independently validate treating the O(N)-memory log-dual recursion as a contribution in itself, and possibly a substantial one. They provide different perspectives that complement our work. In particular, our paper provides four contributions absent from both:
We will sharpen the wording in the final manuscript to ensure that there is no confusion over claims of a new algorithm.
W2 & Q1 - Convergence Guarantees. Please see G3 in the Global Response. There, we discuss two preprints that were posted after the ICLR submission deadline on Sept 25, 2026. They shed light on the convergence of BDRS and reinforce the practical role of our anytime certificate.
W3 & Q2 - Overrelaxation Benefit and Choosing λ. Please see G5 in the Global Response for more details. We agree that λ∈(1,2) does induce a steeper cooling schedule for O-BDRS (ϵk=η/(λk+1)). However, we would like to clarify that the dynamics of O-BDRS and BDRS are distinct and that O-BDRS does unify annealed and overrelaxed Sinkhorn.