acceptodds
Under review as a conference paper at ICLR 2027

Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory

Abstract

We characterize Bregman Douglas–Rachford splitting (BDRS) for unregularized discrete optimal transport and develop an anytime primal–dual certificate in linear memory. We first establish that BDRS coincides with warm-started Inexact Proximal point method for exact Optimal Transport (IPOT) using a single inner Sinkhorn iteration. By eliminating the primal transport plan from the updates, we derive an equivalent dual formulation that reveals BDRS as annealed Sinkhorn under an implicit inverse-linear temperature schedule, with an additional log-scaling momentum term and a cooler kernel. While this explains the role of the temperature parameter in BDRS as an initial temperature, it also reduces the solver's memory requirement from quadratic to linear. Utilizing this annealing perspective, we introduce overrelaxed BDRS, which combines annealing and overrelaxed scaling within a single recursion. We derive a primal–dual certificate for both methods that can be evaluated in linear memory without transport plan construction, thus providing a computable stopping rule. On the DOTmark benchmark, combining momentum with the cooler kernel produces substantially smaller optimality gaps than annealed Sinkhorn under the same schedule. For pixel-level color transfer between images, BDRS attains a lower repaired transport cost than MDOT-TNT with a 9 speed up, reaching a relative duality gap of in 24 minutes. We further demonstrate a color transfer with images, yielding 10 million pixels per image and approximately one hundred trillion implicit transport entries, reaching a best relative duality gap of and within 35 hours in each direction on a single NVIDIA L40S GPU.

Primary area:
optimization
Keywords:
optimal transport, annealed sinkhorn, bregman douglas-rachford splitting, proximal point methods, primal-dual certification, large-scale optimization, linear memory algorithms

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_p4MAOpenReview ↗
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
  1. 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 η\eta.

  2. Reduced persistent memory. Proposition 1 eliminates the explicit transport plan XkX^k and derives a dual recursion over cumulative scaling vectors, reducing persistent memory from O(N2)\mathcal O(N^2) to O(N)\mathcal O(N). The per-iteration work remains O(N2)\mathcal O(N^2).

  3. Linear-memory primal-dual certificate. Proposition 3 provides, in exact arithmetic, a computable bound L≤p⋆≤UL\le p^\star\le U without explicitly forming the transport plan, giving a meaningful optimality certificate.

  4. Practical large-scale experiments. The 1024×10241024\times1024 color-transfer experiment and the 10710^7-pixel, 101410^{14}-implicit-entry experiment demonstrate the scalability of the linear-memory implementation.

Critical weaknesses
  1. Limited novelty in the algorithmic procedure. BDRS is equivalent to IPOT with L=1L=1, 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.

  2. 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.

  3. Unclear independent benefit of O-BDRS. With fixed η\eta, 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 λ\lambda primarily accelerates the schedule rather than the dynamics, and provide guidance for choosing λ\lambda

  4. The 9×9\times comparison with MDOT-TNT is not aligned at the same accuracy or tolerance. In the 1024×10241024\times1024 experiment, BDRS runs for a fixed 1000 iterations, while MDOT-TNT uses a fixed final inverse temperature γ=210\gamma=2^{10}. They are not compared at the same true error ⟨C,P(t)⟩−p⋆\langle C,P^{(t)}\rangle-p^\star or the same certified gap U−L≤τU-L\le\tau. Since MDOT-TNT is a second-order/Newton-type method and is typically more competitive in the high-accuracy regime, the reported 9×9\times 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
  1. Can the authors provide convergence conditions or a local convergence discussion for Dual BDRS under the inverse-linear schedule?

  2. Since O-BDRS shows little gain after temperature matching, do the authors view λ\lambda mainly as a schedule-acceleration parameter? How should λ\lambda be selected in practice?

  3. 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 9×9\times claim intended to be limited to the current fixed setting?

3 comments
AuthorsOpenReview ↗

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=1L=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=1L=1) (Xie et al., 2020) nor primal-dual BDRS (Ma et al., 2025) can execute in O(N)\mathcal{O}(N) memory.

The value of our dual reformulation is further supported by two concurrent preprints posted after our Sept 25, 2026 submission:

  1. Xu & Ma (Oct 3, 2026) (co-authored by an original author of BDRS) list as their first contribution log dual BDRS, which reduces memory from O(mn)\mathcal{O}(mn) to O(m+n)\mathcal{O}(m+n) on GPUs.
  2. Hou & Toh (Oct 6, 2026) also proposes a log dual update Bregman ADMM formulation and its O(m+n)\mathcal{O}(m+n) implementation.

Both concurrent works independently validate treating the O(N)\mathcal{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:

  1. Theoretical unification: Both papers do not connect BDRS to IPOT(L=1L=1) or reveal it as Annealed Sinkhorn (Chizat, 2024) with log-scaling momentum on a cooler kernel, explain why BDRS cools implicitly at fixed η\eta (Ma et al., 2025, Remark 5.1), or unifies annealed and overrelaxed Sinkhorn via O-BDRS.
  2. Feasible primal-dual cost certificate in O(N)\mathcal{O}(N) memory: Instead of terminating the algorithm with ℓ1\ell_1 marginal errors or KKT residuals of a near feasible iterate (Xu & Ma, 2026), Proposition 3 provides a duality gap of a feasible repaired plan in linear memory, with some additional computation.
  3. Non-separable scale: We demonstrate dense, non-separable point cloud OT at 107×10710^7 \times 10^7 (101410^{14} implicit entries) with a certified 2.412.41\\% gap on a single GPU. Hou & Toh (2026) use separable 2D grids for up to 4.19×1064.19\times 10^6 points.

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 λ\lambda. Please see G5 in the Global Response for more details. We agree that λ∈(1,2)\lambda \in (1,2) does induce a steeper cooling schedule for O-BDRS (ϵk=η/(λk+1)\epsilon_k = \eta/(\lambda 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.

AuthorsOpenReview ↗

Response to Reviewer p4MA (Part 2/2)

W4 & Q3 - Comparison with MDOT-TNT, Matched Cost Speedup, and Scope of the 9×9\times Claim. The 1024×10241024 \times 1024 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:

  1. p⋆p^{\star} is unavailable at N=106N = 10^6. 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 γ\gamma.

  2. The 9×9\times speedup claim is conservative. Although p⋆p^{\star} is unknown, p⋆p^{\star} is the same for both problems. It is thus easy to see that any feasible plan with lower primal cost ⟨C,Z^⟩\langle C, \hat{Z}\rangle strictly achieves a smaller true error ⟨C,Z^⟩−p⋆\langle C, \hat{Z}\rangle - p^\star. 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 (γ=210\gamma = 2^{10}, Kemertas et al., 2025) on both float32 and float64 (see Line 1601.) The runtimes were 3.5 hours and 7 hours respectively, and both achieved identical costs. Therefore, we opted for float32 runs to reflect practical situations (see Line 1603). At float32, 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 53×53\times speed up over MDOT-TNT at matched cost. Running our method for the full 1,0001,000 iterations yields a lower cost of 0.049690.04969 and a duality gap of 1.591.59\\%. In contrast, MDOT-TNT's 0.050740.05074 cost after 3.5 hours3.5\text{ hours} still leaves up to a 3.633.63\\% gap).

    Thus, our 9×9\times speedup (24 min24\text{ min} vs. 3.5 hours3.5\text{ hours}) was a conservative comparison over all 1,0001,000 iterations, in which BDRS also achieved substantially higher accuracy.

    At MDOT-TNT's achieved cost, Dual BDRS is >53×>53\times faster.

  3. Accuracy regime and scope of the speedup claim (Q3). The 9×9\times speedup is specific to the published setting of MDOT-TNT, which is the 1024×10241024\times1024 image color transfer example with γ=210\gamma=2^{10}. In this comparison, Dual BDRS achieves a lower feasible cost in less time (3.5 hours vs 24 minutes). As mentioned above, even though p⋆p^{\star} is unknown, both instances share the same p⋆p^{\star} 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 γ=25\gamma=2^{5} and the discussion can be found on Line 1605.

  4. Matched budget run with MDOT-TNT at γ=210\gamma = 2^{10}. MDOT-TNT took 3.5 hours to obtain a duality gap of 3.633.63\\%, computed with our lower bound. We ran Dual BDRS for 9K iterations at η=0.1\eta=0.1 to obtain a gap of approximately 0.30.3\\% in 3.5 hours.

  5. Higher-accuracy MDOT-TNT evaluation (Q3; ongoing). To directly address the reviewer’s request, we are running MDOT-TNT with γ∈{211,212,213,214}\gamma\in\{2^{11},2^{12},2^{13},2^{14}\}, 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 to float64 when γ>210\gamma>2^{10}. 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?

Reviewer_i7t5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents BDRS for unregularized optimal transport. It shows that BDRS matches warm-started IPOT with one inner Sinkhorn step, and rewrites the updates using only scaling vectors. This reveals an implicit annealing schedule with log-scaling momentum and removes the need to store the transport matrix. The authors also introduce an overrelaxed variant and a primal–dual stopping certificate, with experiments on DOTmark and large-scale color transfer.

Critical strengths
  1. The connection between BDRS, single-step IPOT, and annealed Sinkhorn is useful. The reformulation removes the dense transport state without changing the BDRS iterates.

  2. The experiments include a helpful separation of momentum and kernel timing. I also appreciate the matched-temperature ablation, which makes clear that much of the overrelaxation gain comes from faster cooling.

Critical weaknesses
  1. The main AS comparison uses the inverse-linear temperature schedule inherited from BDRS, even though it falls outside the cited convergence conditions for standard AS. This is useful as a controlled ablation, but I would also like to see AS and DAS evaluated with schedules suited to those methods.

  2. The certificate does not resolve the convergence question for BDRS or O-BDRS. The paper is clear about this, but it remains an important gap, we can check whether a tolerance has been reached without knowing when or whether it will be reached.

  3. The added benefit of O-BDRS is not yet clear beyond faster cooling. The matched-temperature results largely remove its objective advantage, so I would be cautious about treating overrelaxation as a separate acceleration contribution.

Questions for authors

How do the results change when AS and DAS use independently tuned annealing schedules, with the same tuning budget for all methods?

After matching the temperature schedules, does O-BDRS still improve certified stopping time or stability, even when its transport costs are almost identical to BDRS?

Are there instances where the momentum or overrelaxation causes persistent oscillation or failure to reach the requested tolerance?

2 comments
AuthorsOpenReview ↗

Response to Reviewer i7t5 (Part 1/2)

Thank you for recognizing the usefulness of the BDRS–IPOT–AS connection and the ablations. We address the questions and weaknesses below.

W1 & Q1 - Independently Tuned Baselines (AS & DAS). Please see G4 in the Global Response. We keep Dual BDRS fixed at its single untuned default (η=1.0\eta = 1.0) while evaluating AS (κ=1/2\kappa = 1/2) and DAS (κ=2/3\kappa = 2/3) under Chizat (2024)'s recommended schedules. We tune η∈{1.0,0.1,0.01,0.001}\eta \in \{1.0, 0.1, 0.01, 0.001\}.

W2 - 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 - Overrelaxation Benefit and Choosing λ\lambda. Please see G5 in the Global Response for more details. We agree that λ∈(1,2)\lambda \in (1,2) does induce a steeper cooling schedule for O-BDRS (ϵk=η/(λk+1)\epsilon_k = \eta/(\lambda 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.

Q2 - Certified Stopping Time and Stability Under Matched Temperatures. First, we clarify a subtlety in "matching the temperature schedules". Dual BDRS updates with effective kernel temperature ϵkB=ηBk+1\epsilon_k^B = \frac{\eta_B}{k+1}, whereas O-BDRS updates with ϵkO=ηOλk+1\epsilon_k^O = \frac{\eta_O}{\lambda k + 1} (Section 3.4; Appendix G.2, Line 1408). Based on these effective temperatures, there is no way to match exactly the two temperature schedules across all iterations when λ\lambda differs. We proposed two regimes to study this (Appendix G.2):

  • Regime 1 (Appendix G.2, Table 2a): Match the initial temperatures (ηB=ηO=1\eta_B = \eta_O = 1) and compare the algorithms as O-BDRS cools ≈λ×\approx \lambda\times faster per step. As an easy argument, suppose λ=2\lambda=2, which is right outside the range of valid values, but makes for an easy illustration. We run BDRS for 100K iterations (effective temperature ≈1/100000\approx 1/100000) and compare the result obtained by O-BDRS after 50K iterations (effective temperature ≈1/100000\approx 1/100000).

  • Regime 2 (Appendix G.2, Table 2b): Match the terminal temperatures at a given budget TT (ηB=T+1λT+1ηO\eta_B = \frac{T+1}{\lambda T + 1}\eta_O), which requires starting the two methods at different initial temperatures (ϵ0B≈ηO/λ\epsilon_0^B \approx \eta_O/\lambda vs. ϵ0O=ηO\epsilon_0^O = \eta_O). This forces the two methods to start at different initial temperatures, making it unsuitable as an apples-to-apples stopping time comparison. As an easy illustration again, we assume λ=2\lambda=2 even though it is invalid. We run BDRS at η=0.5\eta=0.5 for 100K iterations and O-BDRS at η=1\eta=1 for 100K iterations. The terminal temperatures are effectively the same here.

In other words, Regime 1 matches the initial temperature but uses a different number of iterations. Regime 2 matches the terminal temperature but runs for the same number of iterations.

Consequently, under a fair common initial temperature, Figure 2 already shows the stopping time effect: O-BDRS reaches certified tolerances τ\tau earlier possibly due to its faster cooling schedule.

Regarding stability, we answer it in the next question.

AuthorsOpenReview ↗

Response to Reviewer i7t5 (Part 2/2)

Q3 - Instances of Oscillation or Failure to Reach Requested Tolerance. In our experiments, we found that occurrence of oscillations depends primarily on two factors: (1) the initial temperature η\eta for Dual BDRS (momentum), and (2) keeping the overrelaxation parameter within λ∈[1,2)\lambda \in [1, 2).

  1. Momentum (Dual BDRS, λ=1\lambda = 1) and initial temperature η\eta: With a sufficiently large initial temperature (e.g., default η=1\eta = 1), Dual BDRS decreases smoothly without oscillation across all 450 DOTmark instances (Figures 1, 7–11). However, we observe oscillations if η\eta is set too small. As noted in Appendix G.4 (Lines 1588–1594), when tuning η\eta on color transfer, η≥0.1\eta \ge 0.1 yields a somewhat monotonic duality gap curve, whereas η<0.1\eta < 0.1 induces oscillations. For instance, in our 4238×23654238 \times 2365 run with η=0.01\eta = 0.01, the duality gap reaches its minimum of 2.412.41\\% at iteration 840 before moving upwards as it progresses towards iteration 1000 (see Table 4). Notably, this seems to match the theory put forth by Hou & Toh (2026) (Global Response G1), where η\eta has to be sufficient large to guarantee R-linear convergence. We will add the duality gap trajectories for both large-scale color transfer experiments in our final manuscript.

  2. Overrelaxation (λ\lambda) given a well-chosen η\eta: At η=1\eta = 1, O-BDRS with λ∈(1,2)\lambda \in (1, 2) in general does not exhibit oscillations on all of our DOTMark experiments. There is only some instability when λ=1.99\lambda=1.99, which is very close to the boundary. We observed this in the MicroscopyImages and Shapes dataset, where there is some degradation in the later iterations (see Figure 10 and 11), likely caused by numerical sensitivity exacerbated by the 10−1510^{-15} mass assigned to zero-mass pixels (our goal was to solve dense OT so we did not merge them). Once λ≥2\lambda \ge 2, we do observe persistent oscillation and divergence.

Reaching a requested tolerance τ\tau: In our large-scale color transfer experiments, we found that a larger η\eta provides a smooth and somewhat monotonic decrease in the duality gap, with minimal or no oscillations (much larger η\eta has no oscillations). However, choosing a smaller η\eta results in oscillations but could reach a smaller duality gap within the same iteration budget. Specifically, in the 4238×23654238 \times 2365 run, η=0.01\eta=0.01 reaches 2.412.41\\% (at iteration 840) within 1000 iterations, while η=0.05\eta=0.05 achieves a best duality gap of 5.285.28\\% (at iteration 1000) within the same budget. We will include the curves showing the duality gaps for our large-scale color transfer experiments in the final manuscript.

Reviewer_pYbPOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies BDRS for unregularized discrete OT. It establishes an exact equivalence with warm-started IPOT using a single inner Sinkhorn iteration and derives a dual formulation that reveals BDRS as annealed Sinkhorn with log-scaling momentum and a cooler kernel. This formulation enables linear memory execution when pairwise costs can be evaluated on demand from a linear size representation. The authors also introduce an variant with over relaxation, O-BDRS, and a primal dual certificate that can be evaluated in linear memory. Experiments on DOTmark and large-scale image color transfer assess the update mechanisms, the practical usefulness of the certificate, and the scalability of the approach.

Critical strengths
  1. The exact equivalence between BDRS and warm-started IPOT with a single inner Sinkhorn iteration, under matched initialization, provides a useful connection between operator splitting and proximal point methods. The characterization as annealed Sinkhorn with log-scaling momentum and a cooler kernel further connects these perspectives to matrix scaling and explains the implicit cooling in BDRS.
  2. O-BDRS combines over-relaxation and implicit annealing in a single recursion and achieves smaller aggregate rounded primal optimality gaps at a fixed initial temperature and iteration budget. The matched-temperature ablation further clarifies that much of this improvement can be reproduced by lowering BDRS's initial temperature.
  3. The primal dual certificate can be evaluated in linear memory without explicitly constructing the transport plan. In exact arithmetic, it bounds the sub-optimality of a feasible repair of the intermediate plan, providing a computable stopping criterion tied to transport-cost accuracy.
Critical weaknesses
  1. Lack of convergence guarantees. The paper does not establish global convergence or convergence rates for either BDRS or O-BDRS. As the authors acknowledge, a valid optimality certificate does not ensure that the algorithm will eventually reach a prescribed tolerance.
  2. Limited comparison with independently tuned baselines. The main comparisons with AS and DAS use the inverse linear temperature schedule induced by BDRS. This controlled design helps isolate the effects of the updates, but leaves open how BDRS compares with independently tuned alternatives under a comparable tuning budget.
Questions for authors
  1. Proposition 3 establishes the certificate in exact arithmetic, whereas the large-scale experiments use float32. Could you clarify how finite-precision errors may affect the reported primal and dual bounds, and what numerical evidence supports the reliability of the reported duality gaps?
  2. Section 4 (line 418) and the beginning of Appendix G.3 state that the certification experiment uses a budget of 10410^4 iterations, whereas line 1536 states 10510^5. Do these refer to different experiments, or is this a typo?
  3. Beyond image color transfer, which applications would benefit most from linear-memory, certified unregularized OT?
3 comments
AuthorsOpenReview ↗

Response to Reviewer pYbP (Part 1/2)

Thank you for the positive assessment of the equivalence results, the ablations, and the certificate. We also appreciate the conciseness of your review. We address the weaknesses and questions below.

W1 - 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.

W2 - Independently Tuned Baselines (AS & DAS). Please see G4 in the Global Response. We keep Dual BDRS fixed at its single untuned default (η=1.0\eta = 1.0) while evaluating AS (κ=1/2\kappa = 1/2) and DAS (κ=2/3\kappa = 2/3) under Chizat (2024)'s recommended schedules. We tune η∈{1.0,0.1,0.01,0.001}\eta \in \{1.0, 0.1, 0.01, 0.001\}.

Q1 - Finite Precision Errors All DOTmark benchmarks - where tight tolerances down to τ=10−4\tau = 10^{-4} and optimality gaps near 10−910^{-9} are evaluated - are run in float64 (εmach≈2.2×10−16\varepsilon_{\text{mach}} \approx 2.2 \times 10^{-16}), where finite precision error is negligible relative to the tested tolerances and Lbest≤p∗≤UbestL^{\text{best}} \le p^* \le U^{\text{best}} holds across all 450 instances. We use float32 (εmach≈1.2×10−7\varepsilon_{\text{mach}} \approx 1.2 \times 10^{-7}) only in the large-scale color-transfer experiments (N=106N = 10^6 and 10710^7), where target relative gaps are at the percent level (1.591.59\\%\text{–}2.80\\%).

At a high level, float32 errors accumulate in the iteration itself: in Dual BDRS, rounding errors accumulate in the scaling vectors, so the resulting implicit plan may differ slightly from a float64 run. However, because Proposition 3 holds for any positive scaling vectors regardless of how they were generated, the suboptimality of this resulting plan is still validly bounded by U−LU - L, up to the float32 evaluation error of LL and UU themselves. The computation of LL is not significantly affected and we focus the discussion on UU.

The computation of UU involves computing δ=12∥s−c∥1\delta = \frac{1}{2}\Vert s-c\Vert_1, where ss is the column sums of the intermediate plan ZZ and cc is the column marginals (see Algorithm 2). We can then rewrite the terms inside as s~−c=(sexact−c)+ϵfp32\tilde{s} - c = (s^{\text{exact}} - c) + \epsilon_{\text{fp32}}, where ϵfp32\epsilon_{\text{fp32}} is the float32 error introduced in the column sums. Since the intermediate plan ZZ has zero true row error in exact arithmetic (Zexact1n=rZ^{\text{exact}}\mathbf{1}_n = r), the empirical row ℓ1\ell_1 residuals in Tables 3 and 4 approximate ∥ηfp32∥1\Vert{}\eta_{\text{fp32}}\Vert{}_1 directly (2.94×10−52.94\times 10^{-5} at N=106N=10^6 and 1.16×10−41.16\times 10^{-4} at N=107N=10^7). Further observe in both Tables 3 and 4 that the corresponding column marginal ℓ1\ell_1 residuals is higher than the row marginal ℓ1\ell_1 residuals.

This corresponds to a perturbation in UU of roughly 0.030.03\\% (N=106N=10^6) to 0.60.6\\% (N=107N=10^7) relative to UU - below the reported 1.591.59\\%\text{–}2.80\\% relative gaps. Furthermore, the error is additive to the primal upper bound so it is still remains a valid bound. The reported primal and dual bounds for our large-scale experiments accurate to within thesee margins and we will add this discussion to the Appendix in the final version.

We will also run a float64 comparison in the final manuscript to thoroughly address this concern, but omit now as the runtime for this experiment can be substantial.

AuthorsOpenReview ↗

Response to Reviewer pYbP (Part 2/2)

Q2 - Typo Indeed, this was a typo. Thank you for pointing this out. The certification experiment uses a budget of 10410^4 iterations. We will correct this in the final version of the manuscript.

Q3 - Beyond Image Color Transfer. Thank you for this question. It helps us clarify the applications of our method. Since Cuturi (2013), entropic OT solved with Sinkhorn has been the default in machine learning. The iterations are GPU-friendly and is fully differentiable. The issue here is that the entropic problem is a relaxation of unregularized OT. In other words, the final cost obtained is not the true Wasserstein cost. In contrast, BDRS (and Dual BDRS) targets the unregularized problem. We expect the largest benefit to occur when three conditions hold at once.

  1. The unregularized solution is what is wanted. For example, entropy is only added to make the problem tractable and amenable to the Sinkhorn algorithm.
  2. Scale is a bottleneck. For example, storing the N×NN \times N plan is simply not possible. At the same time, the cost can be evaluted on the fly from a linear size representation such as point coordinates or features (see Sec 3.2).
  3. Solution quality matters. A certified gap is more informative than a marginal residual threshold.

Example: EMD between dense point clouds. EMD is used both as a reconstruction loss and as an evaluation metric in point cloud completion and generation. In Liu et al. 2020, a linear memory implementation was proposed to compute an approximation of the cost. Subsequent work from Zhang et al. 2024, provided a more accurate approximation and showed that it improves the trained networks. Our method directly fits the use case as it meets the three conditions described above. First, the unregularized solution is indeed what one wants when computing the EMD. Second, scale is the bottleneck and our method can unlock even larger point clouds. Third, the approximation error matters and thus a duality gap can be helpful in providing a stopping criterion.

Additional Usefulness of Certificate. In practice, Sinkhorn is run for a fixed number of iterations or terminates when a marginal error threshold is reached (which does not bound the transport cost). BDRS is less sensitive to the initial temperature, but a fixed number of iterations must still be chosen. The certificate complements the fixed number of iterations with a target duality gap - one could choose to terminate either based on the fixed number of iterations or the target gap.

We hope these responses address the reviewer's concerns and would be glad to clarify anything further.

Thank you for the response. It has addressed some of my concerns, and I will keep my score unchanged.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Global Responses (Part 1/2)

We sincerely thank the reviewers for their constructive suggestions. The global response consists of 5 points: G1 to G5. G1 is a post submission development. G2 to G5 address weaknesses and questions raised by the reviewers.

G1 - Concurrent Independent Work on Log-Dual BDRS

Following our ICLR submission (Sept 25, 2026), two independent optimization preprints - Xu & Ma (Oct 3, 2026) and Hou & Toh (Oct 6, 2026) - concurrently derived O(m+n)\mathcal{O}(m+n)-memory log-domain/dual-vector formulations of BDRS for GPU OT, demonstrating strong speedups over existing GPU solvers. These two independent preprints underscores the significance of eliminating the O(N2)\mathcal{O}(N^2) primal plan in BDRS. In fact, these two preprints complement our work. Specifically, they do not (1) establish the equivalence to single-step IPOT, (2) characterize BDRS as Annealed Sinkhorn with log-momentum and a cooler kernel, (3) introduce overrelaxation (O-BDRS), (4) certify primal–dual cost suboptimality U−LU - L of a feasible plan Z^∈Π(r,c)\hat{Z} \in \Pi(r,c) in O(N)\mathcal{O}(N) memory, or (5) scale non-separable OT to 107×10710^7 \times 10^7 (101410^{14} implicit entries).

G2 - Matched-Accuracy Comparison with MDOT-TNT (>53x Speedup)

We now address questions regarding the fixed iteration budget vs. matched accuracy (or cost) runtime comparisons on the 1024×10241024 \times 1024 color transfer (N≈106N \approx 10^6, float32) experiment in Kemertas et al. (2025) We note that while the exact LP optimum p⋆p^{\star} is intractable at 101210^{12} decision variables (and MDOT-TNT provides no duality-gap certificate), p⋆p^\star is an identical constant for both solvers on the same instance, meaning matching repaired feasible cost ⟨C,Z^⟩\langle C, \hat{Z}\rangle is equivalent to matching true error ⟨C,Z^⟩−p⋆\langle C, \hat{Z}\rangle - p^\star.

We ran both our method and MDOT-TNT on L40S GPU using the authors' published high-precision setting (γ=210\gamma = 2^{10}). MDOT-TNT required 3.5 hours to reach a repaired feasible cost of 0.050740.05074. In contrast, Dual BDRS (ran for 1K iterations) obtains a cost of 0.050690.05069 at iteration 160 in 4 minutes, representing a >53×>53 \times speedup over MDOT-TNT at matched cost. Furthermore, UU remains strictly below 0.050740.05074 at every subsequent iteration. Our current runtime of 24 minutes (9×9\times faster) figure reflects running all 1,0001{,}000 iterations to reach a lower cost of 0.049690.04969 with a certified 1.591.59\\% relative duality gap. We will scope our speedup claims to the large-scale float32 regime in the final manuscript.

G3 - Convergence Guarantees

All three reviewers noted the absence of global convergence guarantees. Our paper focuses on two complementary goals: (i) theoretically unifying BDRS with single-step IPOT (Xie et al., 2020), Annealed Sinkhorn (Chizat, 2024), and Overrelaxed Sinkhorn (Thibault et al., 2021), and (ii) practically enabling both solving and certifying dense unregularized discrete OT in O(N)\mathcal{O}(N) memory to a dense 107×10710^7 \times 10^7 instance (101410^{14} implicit entries) with a certified relative duality gap of 2.412.41\\% on a single GPU.

Two concurrent preprints posted after the ICLR submission deadline (Sept 25, 2026) discuss the convergence of BDRS:

  1. Ma (Sept 28, 2026) constructs a 72×1272 \times 12 OT counterexample, disproving unconditional convergence.
  2. Hou and Toh (Oct 6, 2026) study a logarithmic-dual-update Bregman ADMM (which coincides with BDRS when stepsize s=1s=1 and Z0=0Z^0=0, see Remark 2.1 in Hou and Toh (2026)) that in certain conditions, have R-linear convergence. Additionally, their convergence condition requires ρ0\rho_0 that is problem dependent (it depends on (C,a,b,X0,s)(C, a, b, X^0, s), see Theorem 3.1 in Hou and Toh (2026)).

These results reinforce the practical necessity of our anytime certificate (Proposition 3) for two reasons. First, unconditional convergence fails. Second, setting ρ≥ρ0\rho \geq \rho_0 depends on computing a chain of values (see Figure 2, Hou and Toh (2026)) and one cannot a priori compute this value. Setting a large ρ\rho in general is also not a practical solution as it can take many iterations before convergence. However, our primal-dual certificate remains valid at every iteration and can be computed in linear memory, independent of any convergence conditions.

AuthorsOpenReview ↗

Global Responses (Part 2/2)

G4 - Independently Tuned Baselines (AS & DAS)

Reviewers pYbP and i7t5 both mentioned this as a weakness. As they rightly point out, the current comparisons use the inverse linear scheduled induced by BDRS to isolate the effects of the momentum term and the cooler kernel. They do not show how BDRS compares with AS and DAS run under their own schedules.

We follow the schedule parameters suggested by Chizat (2024), using the recommended exponents κ=1/2\kappa = 1/2 for AS and κ=2/3\kappa = 2/3 for DAS. In Appendix A, Chizat (2024) uses β0=10\beta_0 = 10 - equivalent to η=0.1\eta = 0.1 under our normalized cost - and notes that performance under these slow schedules is sensitive to the initial temperature. However, our DOTmark experiments use a default of η=1.0\eta = 1.0, which was not tuned and is one of the strengths of BDRS since there is implicit annealing. We use η=1.0\eta = 1.0 for the zero tuning baseline and to account for temperature sensitivity, we evaluate across η∈{1.0,0.1,0.01,0.001}\eta \in \{1.0, 0.1, 0.01, 0.001\} for AS and DAS.

BDRS and O-BDRS with η=1\eta=1 outperforms AS and DAS at every κ\kappa and η\eta values we tested. Interestingly, DAS with κ=1\kappa=1 and η=1.0\eta=1.0 outperforms DAS with κ=2/3\kappa=2/3 and η=0.01\eta=0.01. This would be an interesting direction for future work. The graph will be uploaded in the final manuscript, and we omit adding the link to the image in the rebuttal to err on the side of caution.

G5 - Role of Overrelaxation and Practical Guidance for λ\lambda

We agree with Reviewers i7t5 and p4MA that on DOTmark, most of O-BDRS's empirical improvement in rounded primal cost at fixed η\eta comes from reaching lower effective temperatures sooner (ϵk=η/(λk+1)\epsilon_k = \eta/(\lambda k + 1)), which is why we included the matched temperature ablation (see Appendix G.2). It is important to note that in this experiment (Table 2 in Appendix), it is the average of all the difference in rounded transport costs acrosss all 450 DOTmark pairs at a given iteration that is reported. Specifically, observe in Table 2(a) that the average trajectory for λ=1.99\lambda=1.99 is slightly steeper, with values on the order of 10−510^{-5} at k=1,000k=1,000, compared to λ=1.2\lambda=1.2 and λ=1.5\lambda=1.5, which is on the order of 10−410^{-4}. However, at k=100,000k=100,000, λ=1.99\lambda=1.99 performs worse and this is consistent with our observation in Figure 10 and 11. This immediately shows the trajectories followed by O-BDRS is not identical to BDRS.

Furthermore, we note that O-BDRS is not algebraically identical to rescaling η\eta in Dual BDRS. Observe how the Dual O-BDRS equations (see equations 34a, 34b, 34c) are distinctly different from Dual BDRS equations (see equations 6a, 6b, 6c). The dynamics are indeed different but from a practical perspective, the final results obtained in terms of the optimality gap does not show a significant difference. This was noted in Line 1447, where we mentioned that it motivates separating temperature selection from the effect of the update dynamics in future comparisons.

We thank the reviewers for these comments and will clarify this distinction up front in the main content.

Practical guidance for λ\lambda (p4MA Q2):

  • When tuning η\eta is feasible: Use λ=1\lambda = 1 (Dual BDRS) and tune η\eta directly (as in Section G.4). As η\eta decreases, BDRS is unstable and might oscillate. Tune to the point where oscillations are not observed and run for a large iteration budget.
  • When tuning η\eta is not feasible: Set η=1\eta=1 and use a λ\lambda value that is safely away from the λ→2\lambda \to 2 stability boundary. If oscillations are observed, reduce λ\lambda.

We thank the reviewers for these comments and will revise the final manuscript to clarify the distinction between O-BDRS and Dual BDRS.

AuthorsOpenReview ↗

Human Written Rebuttals

As the review process concludes, we would like to thank the AC and the three reviewers for their time in reviewing our manuscript. We apologize for not submitting the rebuttals earlier, as it was pretty much a herculean effort to address every point. We endeavored to write the content largely on our own, using AI as a tool to help guide the responses. We hope these human rebuttals will be refreshing for all of you.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.