acceptodds
Under review as a conference paper at ICLR 2027

Non-Conservative Sinkhorn: Optimal Transport with Dissipation

Abstract

Optimal transport (OT) assumes mass is conserved, yet in many settings, including portfolio rebalancing with transaction costs, Mixture-of-Experts routing, and logistics with spoilage, mass dissipates in transit. We develop NC-Sinkhorn, the first scalable Sinkhorn-type solver for discrete non-conservative OT (NC-OT), where an edge-dependent preservation map encodes edge-dependent mass loss while hard marginal constraints are maintained. Edge-dependent mass loss breaks the rank-one factorization that makes classical Sinkhorn efficient; we identify a dual consistency condition unique to NC-OT and enforce it via a coupled Newton step that preserves per-iteration cost. We prove convergence to the unique optimum with an iteration complexity bound for feasibility tolerance (empirically linear), and show that structured preservation maps admit progressively cheaper updates, collapsing to a closed-form solution in the separable case. On benchmarks up to , NC-Sinkhorn achieves over speedup versus LP solvers. We demonstrate two applications: portfolio rebalancing with transaction costs and taxes, where the separable bid–ask structure yields real-time solves even at ; and Mixture-of-Experts routing, where NC-OT provides exact quality weighted load balance without auxiliary losses or token dropping while matching or exceeding standard baselines.

Primary area:
optimization
Keywords:
optimal transport, non-conservative, sinkhorn

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_D6yQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes NC-Sinkhorn, a Sinkhorn-type algorithm for discrete non-conservative optimal transport (NC-OT), where mass can dissipate during transportation according to edge-dependent preservation factors. Unlike conventional unbalanced OT, the proposed formulation maintains hard marginal constraints on the source distribution and the normalized arriving mass.

The main technical contribution is a coupled Newton update that enforces a dual consistency condition while maintaining an O(NM)O(NM) computational cost per iteration. The authors establish convergence under exact column updates and provide an iteration complexity bound for a related sequential projection algorithm. Experiments on portfolio rebalancing and Mixture-of-Experts (MoE) routing demonstrate substantial computational speedups over LP solvers and competitive performance against existing routing methods.

Critical strengths
  1. The problem is interesting and has practical applications. The paper considers mass loss during transport, which is not directly handled by standard OT. The motivation is clear.

  2. The proposed algorithm is efficient. The authors use the special structure of the Jacobian matrix to reduce the cost of the Newton step. The (O(NM)) complexity per iteration is a useful result.

  3. The paper includes many experiments. The authors compare NC-Sinkhorn with LP solvers and other routing methods. The results show good computational performance, especially for large problems.

  4. The paper provides detailed mathematical derivations and additional experiments in the appendix. This helps readers understand the proposed method.

Critical weaknesses
  1. The stopping condition may not guarantee feasibility. In Algorithm 1, the stopping condition only checks the column residuals. However, the column update may change the row sums after the row update. Therefore, even if the column residuals are small, the row constraints may still be violated. It is not clear whether the final solution satisfies all constraints.

  2. The convergence analysis does not fully cover the proposed algorithm. Theorem 1 assumes that each column update is solved exactly, but the experiments only use a fixed number of Newton steps. Also, Theorem 2 gives a complexity bound for a different sequential algorithm, not Algorithm 1. In addition, Proposition 10 claims that each Newton step increases the dual objective, but there is no line search or step size control. This claim may not hold in general. The dual objective in Eq. (27) also seems inconsistent with the Lagrangian in Eq. (8).

  3. The separability assumption is not clear. In the portfolio experiments, the authors assume that

mij=mi′mjm_{ij} = m'_i m_j

However, they also set mii=1m_{ii} = 1 in Appendix B.1. This change may break the separable structure of the matrix. Since the proposed algorithm uses this structure to improve efficiency, the authors should explain how this case is handled.

  1. The speed comparison may not be fully fair. NC-Sinkhorn solves an entropically regularized problem, while the LP solvers solve the original problem. These two problems may have different optimal solutions. For example, in Table 9, when N=1000N=1000 and ε=0.01\varepsilon=0.01, the objective gap is about 49% of the original optimal objective. Therefore, comparing only the running time may not be enough. The authors should also compare the methods under similar solution accuracy.

  2. Some details of the MoE experiments are not clear. The NC-OT constraints guarantee exact quality-weighted balance for the transport plan. However, the authors use Top-2 routing in practice, which may change the balance. It is not clear whether the final routing results still satisfy the exact balance constraints. Also, NC-OT uses more tuning choices, including a warmup schedule, while Balanced OT only tunes three values of ε\varepsilon. This may make the comparison unfair.

Questions for authors
  1. In Algorithm 1, why does the stopping condition only consider the column residuals? How do the authors make sure that the row constraints are also satisfied at the end?

  2. Can the authors provide a convergence guarantee for Algorithm 1 with a fixed number of Newton steps? Also, could the authors explain why the Newton update always increases the dual objective without a line search, and check the dual formulation in Eq. (27)?

  3. In the portfolio experiments, does the preservation matrix still have a separable structure after setting (m_{ii}=1)? If not, how is the separable algorithm used in these experiments?

  4. Can the authors compare the running time of NC-Sinkhorn and LP solvers under similar objective accuracy? How does the performance change when a smaller (\varepsilon) is used?

  5. In the MoE experiments, does the final Top-2 routing still satisfy exact quality-weighted balance? Also, can the authors explain why different tuning settings are used for NC-OT and Balanced OT?

I will be glad to improve me score if my concerns are resolved.

3 comments

Thank you for finding the problem practically relevant and the coupled Newton step efficient, and for the clear list of questions, which we answer in order.

W1, Q1. Stopping rule. You are right that a column update can change the row sums. The revised Algorithm 1 reconstructs the plan after the final column update and checks both the row residuals (including the sink) and the column residuals on that same plan. Rerunning the timed N=5000N=5000 instance, the returned plan has maximum residuals of 1.6×10−111.6\times10^{-11} for rows and 1.8×10−171.8\times10^{-17} for columns, with no negative entries.

W2, Q2. Fixed number of Newton steps. Yes. Rev. Theorem 2 proves convergence of Algorithm 1 to the entropic optimum, with a geometric rate, for any fixed number T≥1T\ge1 of Newton steps per column update, once each step uses Armijo backtracking (assumptions in rev. App. E.6.4). Without a line search, a full Newton step does not always increase the dual, so the claim in submission Proposition 10 was too strong; the safeguard fixes this. The corrected dual (rev. Eqs. 6 and 28) is μ⊤f−ε∑i∑j≥0πij\mu^\top f-\varepsilon\sum_{i}\sum_{j\ge0}\pi_{ij}, without the extra GSGS term, and the O(δ−2)O(\delta^{-2}) bound (rev. Theorem 8) is now stated for the sequential variant only. The submitted experiments used full Newton steps; rev. Remark 12 compares both versions numerically, and they reach the same plan with nearly identical iteration counts.

W3, Q3. Separability. No: mii=1m_{ii}=1 generally breaks the product form. The algorithm is the same for separable and general mm (rev. Table 1), so these instances are solved on the full matrix. The override appears only in the tax instances; there, the structure-specialized implementation treats the diagonal as a correction to the product form and checks the result on the original dense model. The scaling experiment and the separable-structure ablation use generators without an override. Rev. App. B.1 now describes each generator separately.

W4, Q4. Similar accuracy and smaller ε\varepsilon. We agree that runtime alone is not enough, as the 49% gap you cite shows. Rev. App. B.2 now compares NC-Sinkhorn with HiGHS on identical inputs at 1% and 0.1% gaps in unregularized cost, including all continuation time. Tighter targets need smaller ε\varepsilon and therefore more iterations: NC-Sinkhorn is up to 36×36\times faster at a 1% gap and up to 12×12\times at 0.1%. The submission's >600×>600\times figure was measured at fixed ε=0.01\varepsilon=0.01, where the plan costs 9.98×10−39.98\times10^{-3} against an LP optimum of 2.70×10−52.70\times10^{-5} (rev. App. B.3). At a 3.8% gap on the N=5000N=5000 tax instance, a structure-specialized implementation is still over 600×600\times faster.

W5, Q5. Top-2 routing and tuning. No. Exact quality-weighted balance holds for the converged transport plan, but Top-2 selection does not preserve it, and the 10-iteration router used in training leaves a residual. We measured the executed Top-2 routing over three seeds (rev. App. C.3): over the final 500 steps, the coefficient of variation across experts is 0.361 for NC-OT's token counts and 0.379 for its quality-weighted load. On tuning, NC-OT used an alpha warmup because a low alpha early in training caused expert collapse; Balanced OT has no preservation parameter, so only ε\varepsilon was tuned. The tuning budgets therefore differ, as rev. Table 12 shows. Without the warmup, at fixed α=0.95\alpha=0.95, NC-OT reaches a lower validation perplexity than Balanced OT (151.4 vs. 152.2).

We hope these answers resolve your questions. If they do, we would appreciate it if you would take them into account in your assessment, and we are happy to clarify anything further.

Thank you again for your thoughtful review. Given that the discussion period is ending soon, we would appreciate your feedback on whether our responses and the revised manuscript address your concerns.

Thank you for clarifying. I have one more question about the baseline as you mentioned in the paper that your method is 600x faster than LP solver. Have you compared your method with methods based on PDLP or other variants on large-scale instances, such as [1] and [2].

Reference [1] PDOT: a Practical Primal-Dual Algorithm and a GPU-Based Solver for Optimal Transport [2] A Memory-Efficient Hierarchical Algorithm for Large-scale Optimal Transport Problems

Reviewer_JvYMOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes NC-Sinkhorn, a Sinkhorn-type solver for non-conservative optimal transport with edge-dependent mass dissipation. The method introduces a dual consistency constraint and a coupled Newton update to handle the resulting dependencies while maintaining O(NM)O(NM) per-iteration complexity. The authors provide convergence analysis and evaluate the method on portfolio rebalancing and Mixture-of-Experts (MoE) routing, along with additional numerical and multi-stage experiments.

Overall, the paper presents an interesting extension of Sinkhorn to non-conservative optimal transport, supported by extensive experiments. However, I have concerns about the theoretical guarantees for the practical implementation and the empirical validation of the MoE application. I would raise my score if the authors address the concern.

Critical strengths
  1. Interesting algorithmic extension. The paper identifies a dual consistency condition arising from edge-dependent mass dissipation and develops an efficient coupled Newton update to enforce it. The comparison with independent column updates helps demonstrate the importance of this condition.

  2. Extensive experiments and diverse applications. The paper includes scalability comparisons, ablation studies, and sensitivity analyses, covering multiple application scenarios such as portfolio rebalancing, MoE routing, and multi-stage optimization. In particular, the application to quality-weighted MoE routing is interesting and demonstrates the potential usefulness of the proposed formulation.

Critical weaknesses
  1. Potential inconsistency in the theoretical analysis. The dual objective in Equation (27) appears inconsistent with the Lagrangian derivation, raising concerns about the validity of the subsequent dual-ascent convergence argument in Appendix E.6.4.

  2. Insufficient theoretical guarantees for the practical algorithm. The convergence theorem assumes exact inner projections, while the iteration complexity result applies to a different sequential algorithm. The theoretical behavior of the deployed finite-Newton implementation remains insufficiently justified.

Questions for authors
  1. Equation (27): Could the authors clarify the derivation of the dual objective? In particular, shifting all gjg_j by the same constant leaves gj−Gg_j-G, and hence the transport plan, unchanged, but appears to change the stated dual objective through the term involving S(f,g)S(f,g).

  2. MoE balance: Does the exact quality-weighted balance guarantee still hold after Top-2 expert selection? Could the authors report the actual balance violations and token-count distributions during training?

  3. Hyperparameter ablation: Could the authors separate the effects of α\alpha and the warmup schedule in Table 5? It would also be helpful to clarify whether Balanced OT receives a comparable tuning budget.

2 comments

Thank you for finding the dual consistency condition and the coupled Newton update an interesting extension, and the MoE application promising. Your questions helped us correct the dual and clarify which guarantee covers which algorithm.

W1, Q1. Dual objective. You are right that Eq. (27) contained an extra term. Minimizing the Lagrangian gives D(f,ℓ)=μ⊤f−ε∑i=1N∑j=0Mπij(f,ℓ)\mathcal D(f,\ell)=\mu^\top f-\varepsilon\sum_{i=1}^{N}\sum_{j=0}^{M}\pi_{ij}(f,\ell), including the sink entries; the GSGS term is already absorbed into the exponential plan. The corrected dual is rev. Eq. 28 (main text: rev. Eq. 6), and rev. App. E.6.4 now uses it. As you note, a constant shift of gg leaves both the plan and the dual unchanged, so uniqueness is now stated for ff and the centered potentials ℓ=(g−G1)/ε\ell=(g-G\mathbf 1)/\varepsilon, which satisfy ν⊤ℓ=0\nu^\top\ell=0.

W2. Guarantee for the finite-Newton algorithm. The revised Algorithm 1 now has its own guarantee. Rev. Theorem 2 covers exact row updates followed by Armijo-safeguarded Newton column steps, with any number T≥1T\ge1 of Newton steps per column update: the iterates converge to the entropic optimum and the dual gap decreases geometrically (assumptions in rev. App. E.6.4). The O(δ−2)O(\delta^{-2}) bound (rev. Theorem 8) is now stated for the sequential variant only. The submitted experiments used full Newton steps without the safeguard; rev. Remark 12 compares the two versions numerically. The unsafeguarded iteration occasionally decreases the dual, but both versions reach the same plan with nearly identical iteration counts.

Q2. Balance after Top-2 selection. No. Exact quality-weighted balance holds for the converged transport plan, but Top-2 selection does not preserve it, and the 10-iteration router used in training leaves a residual. The abstract, Table 5, and conclusion now state this. We measured the executed Top-2 routing on every training batch over three seeds (rev. App. C.3): over the final 500 steps, the coefficient of variation across experts is 0.361 for NC-OT's token counts and 0.379 for its quality-weighted load.

Q3. Alpha, warmup, and tuning budget. The alpha warmup moves alpha from 0.95 to its final value early in training; it is separate from the learning-rate warmup shared by all methods. To separate the two effects, we added a three-seed run at fixed α=0.95\alpha=0.95 without alpha warmup: NC-OT reaches a slightly lower validation perplexity than Balanced OT (151.4 vs. 152.2), so it remains competitive without the warmup. The tuning budgets were not matched: NC-OT searched over alpha and warmup, while Balanced OT has only ε\varepsilon to tune. Rev. Table 12 lists both search spaces, and the Table 5 caption notes the difference.

We hope these revisions address your concerns about the theoretical guarantees and the MoE evaluation. If so, we would be grateful if you would consider updating your score, and we would be happy to answer any further questions.

The revised manuscript shows improvement and addresses several issues I raised. I thank the authors for their detailed responses, as well as for the theoretical analysis and experimental clarifications. I have decided to increase my score to 3.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Summary of Revisions

We are glad that the reviewers found non-conservative OT an interesting problem with practical applications. We thank all reviewers for their detailed questions and comments; addressing them has improved our paper. Below, we summarize the main changes made in response to your comments, with detailed answers in the individual replies. In the uploaded revised manuscript, changes are marked in blue, and "rev." refers to its numbering.

  1. Dual and convergence guarantees. The dual objective is corrected (rev. Eqs. 6 and 28; the extra GSGS term is removed). A new result, rev. Theorem 2, proves convergence of Algorithm 1 with Armijo-safeguarded Newton column steps and any number T≥1T\ge1 of steps per update. The O(δ−2)O(\delta^{-2}) bound (rev. Theorem 8) is now stated for the sequential variant only, and rev. Remark 12 checks the unsafeguarded iteration used in the experiments numerically. The stopping rule now checks row and column residuals on the returned plan.

  2. Runtime at matched accuracy. Rev. App. B.2 compares NC-Sinkhorn with HiGHS on identical inputs at matched gaps in unregularized cost: NC-Sinkhorn is up to 36×36\times faster at a 1% gap, up to 12×12\times at 0.1%, and over 600×600\times at a looser 3.8% gap. The submission's speedup figure was a fixed-ε\varepsilon timing; we have included this clarification in the revised manuscript.

  3. MoE routing. Exact quality-weighted balance is now stated for the converged transport plan only. Rev. App. C.3 adds measurements of the executed Top-2 routing and a comparison without alpha warmup.

We also made smaller corrections to the column Newton Jacobian, the gauge lemma, and the fixed point of the uncoupled iteration. We hope these revisions address the reviewers' concerns, and we would be happy to answer any remaining questions during the discussion period.

Thank you for recognizing the structured solver, its O(NM)O(NM) computation with an O(M)O(M) coupling correction, and the exact-projection analysis, and for separating issues in the printed equations from a failure of the implementation. Your suggestion of a common-accuracy comparison led to the new runtime results.

W1, Q1. Corrected dual. You are right about the extra term. Minimizing the Lagrangian gives D=μ⊤f−ε∑i=1N∑j=0Mπij\mathcal D=\mu^\top f-\varepsilon\sum_{i=1}^{N}\sum_{j=0}^{M}\pi_{ij}, including the sink entries (rev. Eqs. 6 and 28). Since a constant shift of gg leaves the plan and the dual unchanged, uniqueness is now stated for ff and the centered column potentials ℓ\ell, with ν⊤ℓ=0\nu^\top\ell=0.

W1, Q1. Safeguard and guarantee. We agree that local Newton convergence does not imply ascent for every full step (submission Proposition 10). The revised Algorithm 1 uses Armijo backtracking: a step s∈{1,β,β2,…}s\in\{1,\beta,\beta^2,\ldots\} is accepted only if D(x+sd)≥D(x)+σs∇D(x)⊤d\mathcal D(x+sd)\ge\mathcal D(x)+\sigma s\nabla\mathcal D(x)^\top d. Rev. Theorem 2 covers this algorithm with exact row updates and any number T≥1T\ge1 of safeguarded Newton column steps: the iterates converge to the entropic optimum and the dual gap decreases geometrically (assumptions in rev. App. E.6.4). The O(δ−2)O(\delta^{-2}) bound (rev. Theorem 8) applies to the sequential variant only. The submitted experiments used full Newton steps, which Theorem 2 does not cover; rev. Remark 12 compares both versions numerically, and they reach the same plan with nearly identical iteration counts.

W1, Q1. Stopping rule. After the final column update, the revised Algorithm 1 reconstructs the plan, recomputes SS, and checks both the source residuals (including the sink) and the column residuals on that same plan. Rerunning the timed N=5000N=5000 instance (ε=0.01\varepsilon=0.01, tolerance 10−910^{-9}), the returned plan has maximum residuals of 1.6×10−111.6\times10^{-11} for rows and 1.8×10−171.8\times10^{-17} for columns, with no negative entries.

W2, Q2. Accuracy of the timed run. At ε=0.01\varepsilon=0.01, the timed plan costs 9.98×10−39.98\times10^{-3}, against an LP optimum of 2.70×10−52.70\times10^{-5}. The 607×607\times timing was therefore taken at fixed regularization, far from the LP optimum; rev. App. B.3 now reports both values.

W2, Q2. Common accuracy target. Following your suggestion, rev. App. B.2 compares NC-Sinkhorn with an optimal HiGHS solve on identical inputs at 1% and 0.1% gaps in unregularized cost, counting all continuation levels and requiring residuals of at most 10−910^{-9}. NC-Sinkhorn is up to 36×36\times faster at a 1% gap and up to 12×12\times at 0.1%; a structure-specialized implementation is over 600×600\times faster at a looser 3.8% gap.

Your review pinpointed where the guarantees and the timing claim needed to be made precise, and the revision is stronger for it. We would welcome your view on whether the safeguarded guarantee and the matched-accuracy comparison resolve your soundness concerns, and we are glad to run any further checks you find useful.

We appreciate your questions and comments. Given that the discussion period is ending soon, please let us know if any concerns remain so that we can provide further clarification.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.