- 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 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
-
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.
-
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.
-
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.
-
The paper provides detailed mathematical derivations and additional experiments in the appendix. This helps readers understand the proposed method.
Critical weaknesses
-
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.
-
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).
-
The separability assumption is not clear. In the portfolio experiments, the authors assume that
However, they also set 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.
-
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 and , 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.
-
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 . This may make the comparison unfair.
Questions for authors
-
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?
-
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)?
-
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?
-
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?
-
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 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
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=5000 instance, the returned plan has maximum residuals of 1.6×10−11 for rows and 1.8×10−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≥1 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, without the extra GS term, and the O(δ−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=1 generally breaks the product form. The algorithm is the same for separable and general m (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 ε. 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 ε and therefore more iterations: NC-Sinkhorn is up to 36× faster at a 1% gap and up to 12× at 0.1%. The submission's >600× figure was measured at fixed ε=0.01, where the plan costs 9.98×10−3 against an LP optimum of 2.70×10−5 (rev. App. B.3). At a 3.8% gap on the N=5000 tax instance, a structure-specialized implementation is still over 600× 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 ε was tuned. The tuning budgets therefore differ, as rev. Table 12 shows. Without the warmup, at fixed α=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.