acceptodds
Under review as a conference paper at ICLR 2027

A Proximal-Sinkhorn-Newton Method for Entropic Optimal Transport

Abstract

Entropic optimal transport (OT) enables efficient distribution alignment via the Sinkhorn method, but suffers from numerical instability and slow convergence under weak entropic regularization. To address these challenges, we first employ an inexact proximal point method to decompose entropic OT into simpler subproblems, yielding numerically stable approximate solutions. We then introduce a dynamic Newton method with global convergence and a locally quadratic convergence rate to refine these solutions. We also establish, to the best of our knowledge, the first complexity result for Newton-type methods. Under relatively heavy entropic regularization, Sinkhorn scaling can serve as an alternative to the Newton method, since numerical instability is handled in the first stage. The resulting Proximal-Sinkhorn-Newton method combines the strengths of proximal, Sinkhorn, and Newton approaches and outperforms baseline methods across a wide range of regularization strengths and accuracy requirements.

Primary area:
optimization
Keywords:
Optimal transport, Proximal point method, Newton method, Sinkhorn scaling.

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_qPQSOpenReview ↗
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
  1. 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.

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

  1. 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 λ~\tilde{\lambda} and δ\delta, which inherit the factor exp⁡(−2βrˉsub)\exp(-\sqrt{2} \beta \bar{r}_{\mathrm{sub}}) through pLp_L, and it leaves kCGk_{\mathrm{CG}}, τavg\tau_{\mathrm{avg}}, and κeff\kappa_{\mathrm{eff}} 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
  1. 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?

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

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

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

1 comment

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.
Reviewer_1QMYOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies computational optimal transport and proposes a new solver: Proximal-Sinkhorn-Newton (PSN), combining an inexact proximal method for initialization with Sinkhorn or sparse Newton refinement for entropic optimal transport. The authors establish convergence results and provide a computational complexity analysis. Numerical experiments across different problem sizes, regularization strengths, and accuracy requirements demonstrate improvements over several existing solvers.

Critical strengths

The proposed combination of existing optimization techniques is sensible and seem practically appealing. The numerical experiments are extensive and convincing, showing substantial computational improvements over several baselines, particularly in challenging regularization regimes.

Critical weaknesses

1. Computational complexity.

While Theorem 5 provides a complexity bound, it analyzes a simplified Sinkhorn–Newton procedure rather than the actual proposed algorithm. Moreover, the bound contains a factor 1/(λ~δ)1/(\widetilde\lambda\delta), which appears particularly unfavorable. Substituting the constants provided in the appendices yields an exponentially poor dependence on β\beta and a dependence on nn worse than cubic, even for uniform marginals, leading to a worst case complexity bigger than O(n3/ε)O(n^3/\varepsilon). In that sense, the global convergence and local quadratic convergence asymptotic results seem to be misleading.

For an OT solver claiming improved computational efficiency, I would expect not only good practical performance but also theoretical guarantees competitive with the existing O~(n2/ε)\widetilde O(n^2/\varepsilon) complexity benchmarks for ε\varepsilon-approximate OT.

2. Gap between theory and implementation.

The actual algorithm relies on heuristic switching between Sinkhorn and Newton, inexact PCG solves, and Sinkhorn fallback steps. These components are not fully accounted for in the complexity analysis. Consequently, it remains unclear whether the theoretical guarantees meaningfully characterize the computational performance of the proposed algorithm.

Questions for authors

Q1. Can the authors provide an end-to-end complexity guarantee for Algorithm 3, including initialization, inexact Newton solves, and fallback steps?

Q2. What is the exact total complexity with respect to the number of points, weights, regularization and accuracy for Theorem 5?

1 comment

We thank the reviewer for highlighting the hidden parameter dependence. We now give an explicit bound for the dynamic Newton–Sinkhorn trajectory, and the detailed proof is added in Appendix R. Algorithm 3 combined with adaptive PCG stopping criterion yields O(n2)O(n^2) total arithmetic work. We state the full parameter dependence below.

For positive probability marginals, n≥2n\ge2, and β>0\beta > 0, write

\qquad s=\max(a_{\max},b_{\max}),\qquad \ell=\lceil\beta/\Delta\widehat\beta\rceil.$$ Our bound applies to Algorithm 3 with the following specified inner-solver rules. PCG stops at the first iterate residual satisfies $$\\|\widehat H_kp_k+g_k\\|_2\le\eta_k\rho_k,\quad \eta_k=\min\\{1/2,c\rho_k\\},\quad c=\frac1{2es}, \quad \rho_k=\\|g_k\\|_2.$$ Armijo–Wolfe tests finite steps with $0 < c_1 < 1/2$ and $c_1 < c_2 < 1$, and failure triggers $1$–$u_{\max}$ complete Sinkhorn sweeps. For the conservative curvature and radius constants explicitly chosen in our revised proof, $$\frac1{\widetilde\lambda\delta_{\mathrm{src}}} =\frac{12e^{1/e}D_{\mathrm{src}}}{\gamma_n w^2}e^{D+2\sqrt2\mathcal R},$$ where $D_{\mathrm{src}}=\sqrt{2}\\,n\left(a_{\max}b_{\max}+e^{D}-1\right)+s\sqrt{n(n-1)}\\,e^{D}$. The new counting argument uses the total mass $m_k$ and the number $q_k$ of retained cross entries. The IP-EOT warm start gives an objective-gap certificate $\Gamma_0\le D$, and descent keeps $m_k\le2(1+\Gamma_0)\le2(1+D)$, where $\Gamma_0=\sum_{i,j}a_ib_j\log(a_ib_j/P_{0,ij})$. Since each retained entry is at least $\rho_k$, every active solve satisfies $$q_k\rho_k\le m_k, \qquad q_k\le\min\\{n(n-1),2(1+D)/\varepsilon\\}.$$ IC(0) construction costs $O(n+q_k)$, as does each PCG iteration including its true-residual check. PCG terminates within $n$ iterations in exact arithmetic. Each complete attempt therefore costs $O((1+u_{\max})n^2+nq_k)$. A common sufficient-decrease bound limits the number of attempts by $$N_D(\varepsilon)=\left\lceil\frac{256D(1+D)}{c_1\varepsilon^2}\right\rceil.$$ Including IP-EOT initialization, the costs to reach the reduced marginal residual $\rho\le\varepsilon$ are $$W=\begin{cases} O(n^2\ell),&\text{direct return},\\\\[2mm] O\\!\left(n^2\left[\ell+ \left\lceil\dfrac{\log_+(\sqrt2/\varepsilon)}{-\log(\tanh^2(D/4))}\right\rceil\right]\right), &\text{Sinkhorn refinement},\\\\[2mm] O\\!\left(n^2\left[\ell+ \left(1+u_{\max}+\min\left\\{n-1,\dfrac{2(1+D)}{n\varepsilon}\right\\}\right) N_D(\varepsilon)\right]\right), &\text{dynamic Newton}. \end{cases}$$ For bounded $D,u_{\max}$, fixed line-search parameters, and $0 < \varepsilon\le1$, a simpler consequence is $$W_{\rm dyn}=O\\!\left(n^2\ell+\frac{n^2}{\varepsilon^2}+\frac{n}{\varepsilon^3}\right).$$ Thus fixed $\varepsilon > 0$ gives $O(n^2(\ell+1))$, and bounded $\ell$ gives $O(n^2)$ for a supplied cost matrix. Including cost construction gives $O(n^2(d+\ell+1))$, so a quadratic bound for that full pipeline also requires bounded $d$.
Reviewer_UoTQOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies entropic OT with weak regularization (large β\beta), where Sinkhorn can underflow or become slow. The proposed method, PSN, works in two stages. First, IP-EOT takes cheap proximal steps, one Sinkhorn sweep each, while β\beta grows to its target. The result projects onto the right entropic solution, so it can serve as a warm start. PSN then refines it with Sinkhorn or with a sparse Newton method preconditioned by incomplete Cholesky. The paper also gives convergence results and a complexity bound, presented as the first for Newton-type methods in entropic OT. Experiments on assignment, MNIST and ImageNet report large speedups at large β\beta.

Critical strengths

The pipeline is simple and fast at large β\beta. In this regime primal Sinkhorn can underflow, log-domain Sinkhorn is slow, and sparse Newton methods struggle without a good warm start. A cheap warm start followed by a sparse Newton refinement is a natural answer. The IP-EOT step needs no exp or log per step and is more robust to underflow than primal Sinkhorn, and Fig. 2 shows it reaching moderate accuracy faster than log-Sinkhorn. The experiments are also broad, with three problem families, β\beta up to 10410^4 and sizes up to 10510^5.

Critical weaknesses
  • My first main concern is novelty. The first stage, IP-EOT, is IPOT (Xie et al., 2020) with a single inner Sinkhorn iteration, and IPOT also carries the scalings from one step to the next. Theorem 1 says that each iterate projects onto the entropic solution at the current β\beta, which grows linearly. This is already Lemma 4.1 and Proposition 4.2 of MDOT (Kemertas et al., TMLR 2025), and it also follows from Shen et al. (CVPR 2024), which the paper cites. The IPOT paper itself already notes in its appendix that the effective β\beta grows linearly, so the trajectory was not as unclear as Section 2 suggests. In fact Theorem 1 holds for any diagonal scaling of exp⁡(−βC)\exp(-\beta C), even exp⁡(−βC)\exp(-\beta C) itself, so it does not tell us why IP-EOT is a good warm start.

  • The second stage is close to SSNS (Tang and Qiu, 2024), the paper's main baseline. SSNS already keeps the full diagonal of the Hessian, sparsifies only the off-diagonal blocks at a level tied to the gradient norm, and proves that the result stays positive definite. Eq. (16) uses the same construction, with an entrywise threshold instead of the row and column budgets of SSNS, and without its diagonal shift. SPLR (Wang and Qiu, ICML 2025), which is not cited, also uses this construction. The paper drops the shift because it may hinder incomplete Cholesky. I do not find this convincing, since a diagonal shift is the usual fix when incomplete Cholesky breaks down. Theorem 2 improves the dimension factor in the eigenvalue bound of SSNS by about nn, but it still depends on a lower bound on the plan entries that can be exponentially small in β\beta.

  • The same goes for the theory. Theorem 5 is presented as the first complexity result for Newton-type methods in entropic OT. However, entropic OT is a matrix scaling problem, and second order methods for matrix scaling already have complexity bounds (Cohen et al., 2017, Allen-Zhu et al., 2017). Blanchet et al. apply them to entropic OT. The bound in Theorem 5 is also for a simplified method (Sinkhorn first, then pure Newton), not for Algorithm 3, as the authors note. At a fixed marginal tolerance, it can grow exponentially with β\beta, while the usual bound for Sinkhorn alone grows linearly.

  • The convergence results also do not fully cover the algorithm as implemented. Theorem 3 gives an explicit radius for quadratic convergence, but it assumes the Newton systems are solved with no error. Algorithm 2 instead uses PCG, with no stated stopping rule that would keep this rate. The global convergence proof argues that the fallbacks to Sinkhorn eventually stop because Sinkhorn alone converges, but this does not follow when Newton and Sinkhorn steps alternate.

  • My second main concern is the experiments, mostly because of the warm start. At large β\beta, PSN starts its Newton phase from the IP-EOT output, while SSNS starts from scratch and SNS from log-domain Sinkhorn. So the speedups mix two effects, the warm start and the changes to the Newton phase, and SNS and SSNS are never run from the same warm start. Since the warm start is IPOT and the Newton matrix follows SSNS, it is not clear that anything new is behind the speedup. Sinkhorn is also missing from most figures, although the authors' Table 3 shows it as fast as or faster than PSN in 7 of the 9 entries at β=300\beta = 300. The paper also says that PSN is the only method that converges in all cases of Fig. 3, but the figure shows one trajectory per method, and the paper does not say what time or iteration budget each method had, or when a run counts as failed. Finally, the SSNS times are converted from C++ with a factor measured on dense Newton, which is a different algorithm.

  • On a minor note, several citations do not support what they are cited for. Theorem 6 is credited to Hestenes and Stiefel (1952), which has no such result. Chizat (2024) is cited for reducing complexity, although it gets a worse complexity bound for annealing than for Sinkhorn. Linial et al. (1998) is cited for the definition of OT, but it is a paper on matrix scaling and permanents. Theorem 6(3) is also wrong as printed, because removing pp outliers on each side uses 2p2p polynomial degrees, not 22. It is also not stated how the IP-EOT columns of Tables 3 to 5 are produced at a fixed β\beta, since for assignment at β=300\beta = 300 Algorithm 1 takes six steps, while Table 3 reports up to 1,466. The figures are hard to read with very small fonts and could be improved.

Overall, both stages are largely known, the claim of a first complexity result is not correct, and the experiments do not show what the new parts add, so I recommend rejection.

Questions for authors
  1. Could the authors run SSNS, SPLR and SNS from the same IP-EOT output, and add Sinkhorn at every β\beta, or say where and why it fails? This would show whether the new Newton phase adds anything beyond the warm start. A comparison with the truncated Newton method of Kemertas et al. (ICLR 2025), which also anneals with warm starts before a Newton-CG solver, would help as well. This would not change the overlap with prior work, though.

  2. Does the implementation use the threshold of eq. (16) in the switching test, as Algorithm 3 states? If so, the threshold is the current residual ρ\rho, so the switch also depends on how accurate the warm start is. The plan has total mass one, so at most 1/ρ1/\rho of its entries can be kept. I would expect far fewer than 35n35n or 70n70n nonzeros after IP-EOT unless the residual is already very small. Fig. 11(h) also reports 55n55n for MNIST L1 at β=300\beta = 300, below 70n70n, while Table 3 shows the Sinkhorn branch for this case. Were the two measured on the same instance and at the same point, and what were the residual and the number of nonzeros at the switch?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.