- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces Proximal-Sinkhorn-Newton (PSN), a hybrid solver for entropically regularized optimal transport. The idea is to run inexact proximal iterations first, which gives an approximate transport plan without ever forming the Gibbs kernel at the target regularization level. The authors then show that taking an exact KL projection of this intermediate plan recovers the entropic OT solution they’re after. For the refinement stage, PSN picks between Sinkhorn scaling and a sparse Newton method depending on how sparse the truncated Hessian is. The Newton step solves its linear systems with conjugate gradients preconditioned by an incomplete Cholesky factorization. If the line search fails, it falls back to sinkhorn iterations.
On the theory side, the paper gives a positive lower bound on the eigenvalues of the truncated hessian, local quadratic convergence for an idealized version of the Newton iteration, some global convergence claims, and a complexity bound for a more conservative Sinkhorn-Newton variant. The experiments look at random assignment problems, MNIST, and ImageNet, across a range of regularization strengths and accuracy targets. The paper also demonstrates a memory-efficient variant, on an MNIST instance with 100,000 support points.
Critical strengths
-
A sensible combination of complementary solvers. The proximal stage is a practical way to build an intermediate plan before handing off to Sinkhorn or Newton refinement. The KL-projection identity (Lemma 2 / Theorem 1) is simple but gives a clean justification for this hand-off in exact arithmetic. I also like that the hessian truncation keeps the original diagonal blocks and only sparsifies the off-diagonal ones. This keeps the truncated Hessian compatible with incomplete Cholesky, and the positive-definiteness argument in Theorem 2 goes through. Together, these choices give a reasonable basis for combining numerical stability with fast local convergence.
-
Promising results, with thorough experiments that look at the individual components. The evaluation covers several problem types, regularization strengths, and accuracy levels instead of a single favorable setting. For example, on the 4096-point MNIST problem with squared-Euclidean cost, Table 5 reports 8.01s for PSN to reach marginal error 1e-8, compared with 33.4s for SSNS and 77.6s for SNS. The appendices also study the preconditioner, the proximal step size, the switching criterion, and variability over 20 random assignment trials. These help explain where the gains come from and make the case for the method’s practical value more convincing.
Critical weaknesses
- The convergence guarantees don’t fully cover the algorithm that is actually implemented. Theorem 3 analyzes an update that applies the inverse of the truncated Hessian exactly. Algorithm 2, however, computes an approximate direction with PCG. The paper never specifies a residual-based stopping rule that keeps the linear-solve error small enough to preserve quadratic convergence. A PCG tolerance ε_d does appear in the cost analysis in Appendix F, but it is not linked to the outer gradient norm or to the claimed local rate. This matters because a result for exact linear solves doesn’t automatically carry over to an inexact newton implementation.
The global-convergence argument also seems to have a gap. In the proof of lemma 9, the Newton-to-Sinkhorn transition steps are excluded from the preconditioned-gradient representation. The proof then argues that such transitions happen only finitely often, because Sinkhorn converges into the local Newton region. But convergence of uninterrupted Sinkhorn iterations doesn’t by itself imply this for a sequence that is repeatedly interrupted by Newton updates. The argument needs to handle repeated switching directly, or separately prove that switching eventually stops. In relation to that also, Lemma 8 states that the Armijo condition holds “naturally” for the Sinkhorn block update without proof, and it analyzes a single block step even though the fallback runs about 20 Sinkhorn iterations. Of course, none of this shows that PSN fails, but the stated guarantees for the actual algorithm are not yet fully established.
- The comparisons don’t yet establish an advantage over closely related methods.The paper doesn’t discuss or compare against A Truncated Newton Method for Optimal Transport (Kemertas, Farahmand, and Jepson, ICLR 2025). That work combines an annealing / mirror-descent framework with truncated Newton refinement, computes the Newton direction approximately with conjugate gradients, and proves local quadratic convergence. This is very close to the combination proposed here. Its experiments also include upsampled MNIST at n = 4096 with L1 and squared-L2 costs, which is essentially the setting of Table 5, so a direct comparison should be feasible.
The omission also bears on the claim of the first complexity analysis for Newton-type entropic OT methods. The authors should explain what their result establishes beyond existing analyses. As it stands, Theorem 5 applies to a conservative Sinkhorn–Newton surrogate rather than to PSN itself. Its bound depends on and , which inherit the factor through , and it leaves , , and as unbounded quantities. It's not clear how informative the bound is in the regimes the experiments cover.
The runtime comparison also needs clearer reporting. Footnote 3 says the C++ runtimes of SSNS were rescaled to MATLAB using a factor measured on a separate Newton implementation. I don't see a reason to expect that factor to transfer to sparse Newton methods, whose factorization and memory costs are different. Since runtime improvement is a central contribution, the paper should report the raw measured times alongside the adjusted ones and show whether the main conclusions depend on the adjustment. It should also state whether the same rescaling was applied to the C++ baselines in Appendix J.
Questions for authors
-
Clarification of the implemented Newton method: What stopping criterion is used for PCG? Can you show that its residual tolerance is sufficient to preserve the local quadratic rate claimed in Theorem 3, and account for the resulting linear-solve cost in Theorem 5?
-
Clarification of global convergence: How does the proof handle infinitely many Newton-to-Sinkhorn transitions? In particular, can the argument around Equations 214-218 be completed without assuming that repeated switching eventually stops?
-
Evidence that could affect my recommendation: How does PSN compare with the fixed-regularization projection solver from Kemertas et al., "A Truncated Newton Method for Optimal Transport" (ICLR 2025), at matched regularization and accuracy? Please also report the original SSNS runtimes before the C++/MATLAB adjustment. These comparisons would help establish the practical benefit of the proposed combination.
-
Clarification of the warm start: Algorithm 1 returns the last proximal step's scaling vectors, while the final plan contains the accumulated scalings from all proximal steps. How are these converted into the dual variables used by Algorithm 2 with the original cost matrix and final regularization parameter? Would help if you make this conversion explicit in the algorithm.
We thank the reviewer for their constructive feedback.
W1(a) & W2(b) & W2(c) & Q1. PCG stopping criterion, Newton stage convergence, and Algorithm 3 complexity
The complete proof is in Appendix R. We use the adaptive stopping criterion
\eta_k=\min\\{1/2,c\rho_k\\},\quad c=1/(2s\exp(1)).$$ Here $\rho_k=\\|g_k\\|_2$ and $s=\max(a_{\max},b_{\max})$. Locally, unit steps are accepted, therefore $$\rho_{k+1}\le Q\rho_k^2,\qquad N_{\rm local}=O(\log\log(1/\varepsilon)),$$ where $Q$ is a problem-dependent constant. Let $D=\beta\Delta_C$, $\ell$ count IP-EOT stages, and $u_{\max}$ bound complete fallback sweeps. The exact-arithmetic work is $$W_{\rm dyn}=O\\!\left(n^2\left[\ell+ \left(1+u_{\max}+\min\left\\{n-1,\frac{2(1+D)}{n\varepsilon}\right\\}\right) \left\lceil\frac{256D(1+D)}{c_1\varepsilon^2}\right\rceil\right]\right).$$ For bounded $D,u_{\max}$, and $q_k\le\min\\{n(n-1),2(1+D)/\varepsilon\\}$ fixed line-search parameters, and $0 < \varepsilon\le1$, $$W_{\rm dyn}=O\\!\left(n^2\ell+\frac{n^2}{\varepsilon^2}+\frac{n}{\varepsilon^3}\right).$$ Thus fixed absolute reduced marginal tolerance $\varepsilon > 0$ and bounded $\ell$ give $O(n^2)$. ##### W1(b) & Q2. Convergence with Sinkhorn fallback Lemmas 8–9 in Appendix F establish a common sufficient-decrease bound for accepted Newton steps: $$f(z_k)-f(z_{k+1})\ge \nu\\|\nabla f(z_k)\\|_2^2, \qquad \nu=\min\\!\left\\{ \frac{c_1(1-c_2)\widetilde{\lambda}^{\\,2}}{l_{\nabla f}^{\\,3}}, \frac{m_B}{6M_B^2} \right\\} > 0.$$ Summing this inequality and using the lower bound yields $\\|\nabla f(z_k)\\|_2\to0$. Remark 2 extends this argument to inexact PCG directions satisfying a uniform angle condition, with the Newton decrease constant replaced by $c_1(1-c_2)\gamma^2/l_{\nabla f}$. ##### W2(a) & Q3. Experimental comparison with TNT The comparison result of PSN with TNT are as follows. TNT iteration counts denote Chi-Sinkhorn + Newton iterations. $\beta=300$ | Case | Error | PSN # iters | PSN time | TNT # iters | TNT time | TNT/PSN* | | ----------- | --------- | ----------- | -------- | ----------- | -------- | -------- | | L2. $n=784$ | $10^{-4}$ | 109 | 0.020 | 155+0 | 0.112883 | 5.64× | | L2. $n=784$ | $10^{-6}$ | 324 | 0.030 | 203+1 | 0.514022 | 17.13× | | L2. $n=784$ | $10^{-8}$ | 540 | 0.040 | 203+2 | 0.813433 | 20.34× | | L1. $n=784$ | $10^{-4}$ | 114 | 0.040 | 119+0 | 0.077164 | 1.93× | | L1. $n=784$ | $10^{-6}$ | 354 | 0.070 | 187+1 | 0.526266 | 7.52× | | L1. $n=784$ | $10^{-8}$ | 617 | 0.130 | 187+2 | 0.750933 | 5.78× | $\beta=1200$ | Case | Error | PSN # iters | PSN time | TNT # iters | TNT time | TNT/PSN* | | ----------- | --------- | ----------- | -------- | ----------- | -------- | -------- | | L2, $n=784$ | $10^{-4}$ | 52+1 | 0.140 | 695+0 | 0.447374 | 3.20× | | L2, $n=784$ | $10^{-4}$ | 52+3 | 0.200 | 912+1 | 1.417695 | 7.09× | | L2, $n=784$ | $10^{-8}$ | 52+5 | 0.260 | 912+2 | 1.546506 | 5.95× | | L1, $n=784$ | $10^{-4}$ | 52+1 | 0.130 | 515+0 | 0.940649 | 7.24× | | L1, $n=784$ | $10^{-6}$ | 52+3 | 0.180 | 793+2 | 2.691803 | 14.95× | | L1, $n=784$ | $10^{-8}$ | 52+5 | 0.240 | 793+2 | 2.691803 | 11.22× | $\beta=200\ln n$ | Case | Error | PSN # iters | PSN time | TNT # iters | TNT time | TNT/PSN* | | ------------ | --------- | ----------- | -------- | ----------- | --------- | -------- | | L2. $n=4096$ | $10^{-4}$ | 68 | 5.150 | 606+0 | 6.940543 | 1.35× | | L2. $n=4096$ | $10^{-6}$ | 68+3 | 7.060 | 1082+1 | 13.531489 | 1.92× | | L2. $n=4096$ | $10^{-8}$ | 68+4 | 8.010 | 1082+2 | 14.023898 | 1.75× | | L1. $n=4096$ | $10^{-4}$ | 68+2 | 5.710 | 438+0 | 5.087150 | 0.89× | | L1. $n=4096$ | $10^{-6}$ | 68+4 | 7.530 | 959+1 | 12.852648 | 1.71× | | L1. $n=4096$ | $10^{-8}$ | 68+5 | 8.370 | 959+2 | 13.130963 | 1.57× | ##### W2(d). Unscaled SSNS runtimes SSNS runtimes were multiplied by 2 to account for C++/MATLAB runtime differences. In Appendix K, Tables 3–4, PSN remains at least $1.5\times$ faster using raw times. ##### Q4. Newton initialization from IP-EOT For $P^0=\mathbf1\mathbf1^\top/n^2$, the cumulative scalings $U_i=\prod_{t=1}^{\ell}u_i^{(t)}$ and $V_j=\prod_{t=1}^{\ell}v_j^{(t)}$ initialize Newton at the final $\beta$ as $$P^\ell_{ij}=n^{-2}U_i e^{-\beta C_{ij}}V_j, \qquad x_{0,i}=\frac{\log U_i+\log V_n+1-2\log n}{\beta}, \qquad y_{0,j}=\frac{\log V_j-\log V_n}{\beta}.$$ This enforces $y_{0,n}=0$ and exactly recover transport plan.