Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that Sinkhorn-Knopp's local convergence rate matches the sharp asymptotic Jacobian rate $1-\sigma_2$, nonasymptotically and with explicit constants.

desk verdict First nonasymptotic local rate for Sinkhorn-Knopp that matches the Jacobian-based rate is genuinely new; the proof template is sound, but Theorem 3.2's displayed constants and s-dependence do not follow from the lemmas as written. read the letter →

arxiv 2608.11760 v2 pith:6GTEIWO7 submitted 2026-08-12 math.OC cs.LGstat.ML

Wenzhi Gao , Zhaonan Qu , Yinyu Ye , Madeleine Udell This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C2590C60
keywords Sinkhorn-Knoppmatrixscalinglocallinearconvergencenonasymptoticanalysisdoublystochasticalternatingminimizationsemi-dualacceleration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a nonasymptotic local linear convergence guarantee for Sinkhorn–Knopp (SK) that matches the asymptotic rate $1-\sigma_2$ obtained by Jacobian linearization, where $\sigma_2$ is the spectral gap of the normalized Laplacian of the optimally scaled matrix. Under the assumption that this gap is positive, SK reaches an $\varepsilon$-accurate scaling in $O(\|p\|_1 D^2/\min\{\sigma_2^4, s\sigma_2^2\} + (1/\sigma_2)\log(1/\varepsilon))$ iterations. A corollary is that doubly stochastic scaling is polynomial-time when $\sigma_2$ is treated as a fixed constant, with $O(n^3+\log(n/\varepsilon))$ iterations for general nonnegative matrices and $O(n+\log(n/\varepsilon))$ for positive matrices. The analysis also shows SK's unit step is locally suboptimal, leading to accelerated variants and to an improved dense matrix scaling complexity of $O(n^{9/4}/\sqrt{\varepsilon})$. This matters because SK's fast practical convergence was previously justified only asymptotically or through looser global bounds.

What carries the argument

The load-bearing object is the dual potential $\varphi(u,v)=\langle e^u, A e^{-v}\rangle - \langle p,u\rangle + \langle q,v\rangle$, minimized alternately by SK, together with its quadratic surrogate $\lambda$ built from the Hessian $\nabla^2\varphi(u^{\star},v^{\star})$. The spectral gap $\sigma_2 = \lambda_2(I - P^{-1/2}A^{\star}Q^{-1}(A^{\star})^{\top}P^{-1/2})$ serves as the contraction factor: alternating minimization on $\lambda$ contracts by $1-\sigma_2$, and Lemmas 3.4 and 3.5 transfer that contraction to $\varphi$ by controlling the difference between $\varphi$ and $\lambda$ in terms of $\sqrt{\varepsilon}$, $s=\|(p,q)\|_{-\infty}$, and $\sigma_2$.

What would settle it

Run Sinkhorn–Knopp on the two-by-two family in Appendix A.10 with parameter $\theta=1/2$, for which $\sigma_2=4\theta/(1+\theta)^2=8/9$, and record the ratio $(\varphi_{k+1}-\varphi^{\star})/(\varphi_k-\varphi^{\star})$ after the iterates enter the local threshold; if the ratio does not approach $(1-\sigma_2)^2=(1/9)^2$, the claimed tightness fails.

Watch

Extended reading notes

Core claim

The central discovery is that the local contraction of Sinkhorn–Knopp is governed, for all iterates sufficiently close to the optimum, by the same quantity $\sigma_2 = \lambda_2(I - P^{-1/2}A^{\star}Q^{-1}(A^{\star})^{\top}P^{-1/2})$ that appears in the asymptotic Jacobian analysis. The proof introduces a quadratic surrogate $\lambda$ of the dual potential $\varphi$, shows that alternating minimization on $\lambda$ contracts by $1-\sigma_2$, and then bounds the gap between $\varphi$ and $\lambda$ using the identity $\phi(\delta)=e^{\delta}-\delta-1$ and estimates on its first two derivatives. The resulting recursion, $\varphi_{k+1} \le (1-\sigma_2)\varphi_k + O(\varphi_k^{3/2}) + O(\varphi_k^2)$, becomes linear once the function-value gap is below the explicit threshold $s\sigma_2^2/1296$, closing the gap between asymptotic Jacobian rates and nonasymptotic analysis.

Load-bearing premise

The load-bearing premise is that the spectral gap $\sigma_2$ of the optimally scaled matrix is strictly positive, which means its bipartite support graph is connected; if $\sigma_2=0$, the contraction factor $1-\sigma_2$ degenerates, the burn-in bound diverges, and the polynomial-time corollary does not follow.

Editorial extensions

If this is right

  • For doubly stochastic scaling with $\sigma_2>0$ fixed, SK finds an $\varepsilon$-scaling in $O(n^3+\log(n/\varepsilon))$ iterations, improving to $O(n+\log(n/\varepsilon))$ for strictly positive matrices.
  • The local rate $1-\sigma_2$ per half-iteration is tight: there is a family of instances whose potential gap cannot shrink faster than $c+(1/(2\sigma_2))\log(1/\varepsilon)$.
  • SK's unit step is locally suboptimal; the minimax step $2/(1+\sigma_2)$ improves the contraction, and $2/(\sigma_2+\sigma_m)$ improves it further when the semi-dual block has full row rank.
  • Local acceleration is possible without knowing the rate in advance: online scaling gives $O((1/\sigma_2^{\star})\log(1/\varepsilon))$ and Nesterov acceleration gives $O((1/\sqrt{\sigma_2})\log(1/\varepsilon))$.
  • For dense matrices, the first-order matrix scaling complexity improves from $O(n^{7/3}/\varepsilon^{2/3})$ to $O(n^{9/4}/\sqrt{\varepsilon})$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because $\sigma_2$ is defined through the unknown optimally scaled matrix $A^{\star}$, the polynomial-time guarantee is a posteriori: a user cannot certify the rate from the raw problem data before solving it.
  • The local suboptimality argument suggests that other two-block alternating minimization schemes, whenever their updates act like identity-preconditioned gradient, may be accelerated by a deliberately larger step; testing this on other alternating algorithms would be a natural next step.
  • If the dense complexity improvement $O(n^{9/4}/\sqrt{\varepsilon})$ carries over to entropic optimal transport, high-accuracy regimes would favor semi-dual first-order methods over plain SK, although the stochastic variant pays for its better $\varepsilon$-dependence with randomness.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the local convergence of Sinkhorn-Knopp (SK) for matrix scaling, viewed as alternating minimization on the dual potential. It claims the first nonasymptotic local linear convergence analysis whose rate matches the asymptotic Jacobian rate 1 - σ2, where σ2 is the connectivity of the normalized Laplacian of the optimally scaled matrix. The main result, Theorem 3.2, states an iteration bound of O(‖p‖1 D² / min{σ2⁴, sσ2²} + (1/σ2) log(1/ε)) and is used to derive polynomial-time complexity for doubly stochastic scaling under fixed σ2 (Corollary 3.1). The paper also proposes accelerated variants based on the semi-dual formulation, including an online scaled gradient method (OSMS) and a preconditioned accelerated gradient method (PAGD), and reports numerical experiments on random and MNIST entropic optimal transport instances.

Significance. If the central quantitative claim were correct, the paper would close a real gap between asymptotic Jacobian-based reasoning and nonasymptotic convergence analysis for a widely used algorithm. The paper is self-contained in deriving the local contraction through the dual potential, and it provides an explicit lower-bound family that supports the qualitative tightness of the rate. The acceleration results, especially the local suboptimality of SK and the OSMS/PAGD comparisons, are interesting and backed by experiments. However, the main theorem's displayed iteration count contains internal inconsistencies with its own proof, so the headline quantitative statement and its corollaries are not currently supported. The qualitative local rate O((1/σ2) log(1/ε)) appears defensible after correction, which is why the issues are repairable.

major comments (3)
  1. [Lemma 3.4(1) and Appendix A.7] The statement of Lemma 3.4(1) is inconsistent with its proof. The lemma states ‖∇φ(u,v) - ∇λ(u,v)‖_{S⁻¹} ≤ 2√(sε) and ‖∇φ(u,v)‖_{S⁻¹} ≤ 2√ε + 2√(sε), but the proof in A.7 derives ‖∇φ(u,v) - ∇λ(u,v)‖_{S⁻¹} ≤ 2ε/√s and ‖∇φ(u,v)‖_{S⁻¹} ≤ 2√ε + 2ε/√s, placing s in the denominator rather than the numerator. This is not merely a typo: the proof of Lemma 3.4(3) invokes the erroneous 2√(sε) bound to conclude ‖∇λ(z)‖_{S⁻¹} ≤ 6√ε, and Lemma 3.5's Δ₂ bound is derived from the 2ε/√s version. The chain of lemmas as printed is therefore not self-consistent. The discrepancy appears fixable, since ε ≤ sσ₂²/1296 implies ε ≤ s and hence 2ε/√s ≤ 2√ε, so the 6√ε conclusion can be recovered, but the statements and subsequent constants must be corrected explicitly.
  2. [Theorem 3.2 and Appendix A.9] The displayed iteration count in Theorem 3.2 is not derivable from the proof in A.9. The proof shows local contraction only when the gap satisfies ε ≤ sσ₂⁴/1344² (taking the stricter of the two thresholds in A.9). Since Theorem 3.1 gives gap reduction at rate 2‖p‖₁D²/K, the global burn-in phase costs K = Θ(‖p‖₁D²/(sσ₂⁴)), not the displayed 2·1344²‖p‖₁D²/σ₂⁴ with no factor 1/s. Moreover, the theorem's O(‖p‖₁D²/min{σ₂⁴, sσ₂²}) is inconsistent with the proof's threshold: for s < σ₂², min{σ₂⁴, sσ₂²} = sσ₂², which is much larger than sσ₂⁴; for s ≥ σ₂², the expression loses the 1/s factor. Thus the theorem's explicit constant, its s-dependence, and the resulting polynomial-time statement in Corollary 3.1 are unsupported as written. The qualitative local rate O((1/σ₂) log(1/ε)) survives, but the main quantitative claim needs a corrected threshold and a corrected burn-in expression.
  3. [Theorem 3.2 assumptions] The theorem as stated assumes only A1, but the statement and proof require σ₂ > 0. If the bipartite support graph of A⋆ is disconnected, then σ₂ = 0, Lemma 3.3 gives no contraction, and all denominators in Theorem 3.2 and Lemma 3.5 blow up. The theorem should explicitly assume σ₂ > 0. The paper should also acknowledge that σ₂ is a property of the optimal scaling A⋆ rather than of the input matrix A directly, so this condition cannot be verified before solving the problem. This is a genuine limitation, not a fatal flaw, but it belongs in the formal statement of the main result.
minor comments (5)
  1. [Appendix A.10 and table of contents] The appendix lists two entries titled "A.10 Proof of Theorem 3.2." The second entry, which contains the lower-bound family with the 2×2 matrix, should be labeled as the proof of Proposition 3.2 or as a separate tightness proof.
  2. [Lemma 3.5 and Appendix A.8] The displayed coefficient in Lemma 3.5 is garbled: the proof in A.8 derives 336/(σ₂√s) ε^{3/2}, and Appendix A.9 also uses 336/(σ₂√s), but the lemma statement appears to place √s in the numerator. This should be corrected to match the proof.
  3. [Figures 1, 2, and 3] The figure captions and axis labels contain LaTeX substitution artifacts, e.g., "10!10" for 10⁻¹⁰, "Rand 1 (<2 = 0:81)" for σ₂, and "Sinkhorn (, = 1)" for Sinkhorn (α = 1). These should be fixed before publication.
  4. [Proposition 3.2 and Theorem 4.3] Both statements are labeled "Informal" in the text. For a journal paper, the lower-bound claim in Proposition 3.2 and the local acceleration claim in Theorem 4.3 should either be stated as formal theorems with all constants and conditions, or explicitly marked as informal discussion with pointers to precise versions.
  5. [Section 4.5] The constants in Lemma 4.4 and Theorem 4.4 should be checked for consistency with Lemma 4.1: the threshold min{σ₂²s/1296, σ₂³s²/(24‖p‖₁)} appears in Lemma 4.1 but the proof of Lemma 4.4 also introduces a factor min{4‖p‖₁⁻¹,1} whose provenance is not clearly explained in the main text.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the local rate is proved from a quadratic surrogate with the standard spectral gap; the only self-citations are auxiliary and not load-bearing for the central claim.

full rationale

The central derivation is not circular. Theorem 3.2 rests on Lemma 3.5, which is obtained by comparing the Sinkhorn update on the true potential phi with the quadratic surrogate lambda built from nabla^2 phi(u*,v*); the contraction factor 1 - sigma_2 in Lemma 3.3 is a direct spectral calculation for alternating minimization on lambda, and sigma_2 = lambda_2(I - P^{-1/2} A* Q^{-1} (A*)^T P^{-1/2}) is the standard spectral gap from the fixed-point literature, not a fitted parameter. Lemma 3.4 bounds |phi - lambda| and the gradient/Hessian deviations in terms of the function gap and data constants, so the local recursion and the O((1/sigma_2) log(1/epsilon)) rate follow from the same spectral quantity used in the asymptotic Jacobian analysis. The tightness family in A.10 is an explicit construction attaining the rate, and no parameter is fitted to force the stated complexity. The only self-citations are auxiliary: [35] supplies a monotonicity bound in the global phase, and [15] supplies the OSGM global convergence used to globalize the OSMS variant; neither feeds back into the main local-convergence claim. The skeptic's arithmetic objection that the displayed burn-in denominator does not match the s-dependent threshold from A.8/A.9 is a correctness/internal-consistency issue, not circularity: it concerns whether the stated constant is implied by the lemmas, not whether a quantity is defined in terms of itself or a fitted prediction is relabeled. I therefore find no significant circularity; at most a minor, non-load-bearing use of self-citations for an auxiliary accelerated variant.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted free parameters; σ2 and D are computed from the problem data and optimal solution, not estimated from runs. No new physical entities are introduced. The axioms are standard for the matrix scaling problem, with the connectivity assumption being the key algorithmic condition.

assumptions (4)
  • domain assumption A is scalable with respect to margins p,q (Assumption A1).
    Stated in Section 2.1. All convergence bounds depend on the existence of a finite optimal scaling pair.
  • domain assumption Margins p,q have strictly positive entries, so s=∥(p,q)∥_{-∞}>0.
    Used throughout Lemma 3.4 and the potential bounds; the proof requires dividing by √s.
  • domain assumption The spectral gap σ2 is strictly positive (connectivity of the optimal support).
    Required for the local contraction in Lemma 3.3 and for finite burn-in in Theorem 3.2; not implied by A1.
  • standard math Standard smoothness and strong convexity properties of the semi-dual ζ, and convergence of FISTA, Katyusha, and OSGM from cited references.
    Used in Section 4 and Appendix B; these are prior results cited from [26], [1], [15].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp." pith.science (2026). https://pith.science/paper/6GTEIWO7

@misc{pith2026260811760,
  author       = {Pith},
  title        = {Pith review of: Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6GTEIWO7}},
  note         = {Machine review of arXiv:2608.11760}
}
abstract

We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We show that under certain connectivity conditions, SK is a polynomial-time algorithm for doubly stochastic matrix scaling. With the developed tools, we showcase the local suboptimality of SK and provide accelerated variants. Finally, for dense matrices, we improve the complexity of existing first-order matrix scaling algorithms from $O(\tfrac{n^{7/3}}{\varepsilon^{2/3}})$ to $O(\tfrac{n^{9/4}}{\sqrt{\varepsilon}})$.

Figures

Figures reproduced from arXiv: 2608.11760 by the authors.

Figure 1
Figure 1. Local suboptimality of SK (m = 3, n = 300): the larger minimax (α = 2/(1 + σ2)) and optimal (α = 2/(σ2 + σm)) stepsizes contract faster than SK (α = 1) As our theory predicts, using a larger step size yields better local contraction than SK. 5.2 Accelerated variants of Sinkhorn-Knopp Figures 2 and 3 compare the accelerated variants on eight random and eight MNIST instances. Both PAGD and OSMS beat SK by several orde… view at source ↗
Figure 2
Figure 2. Accelerated variants of SK on eight random entropic optimal transport instances (m = n = 200): residual versus number of matrix-vector products. References [1] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1–51, 2018. (cited on 7, 27) [2] Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms f… view at source ↗
Figure 3
Figure 3. Accelerated variants of SK on eight MNIST entropic optimal transport instances (n = 784, η = 2×10−3 ). [10] Steven Diamond and Stephen Boyd. Stochastic matrix-free equilibration. Journal of Optimization Theory and Applications, 172(2):436–454, 2017. (cited on 2, 6) [11] Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Com￾plexity by accelerated gradient descent is better … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 40 canonical work pages

  1. [15]

    Gradient methods with online scaling part I

    Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, and Madeleine Udell. Gradient methods with online scaling part I. theoretical foundations.arXiv preprint arXiv:2505.23081, 2025. (cited on 8, 9)

    arXiv 2025

  2. [26]

    A geometric structure of acceleration and its role in making gradients small fast.Advances in Neural Information Processing Systems, 34:11999–12012, 2021

    Jongmin Lee, Chanwoo Park, and Ernest Ryu. A geometric structure of acceleration and its role in making gradients small fast.Advances in Neural Information Processing Systems, 34:11999–12012, 2021. (cited on 7, 26)

    work page 2021

  3. [1]

    Katyusha: The first direct acceleration of stochastic gradient methods.Journal of Machine Learning Research, 18(221):1–51, 2018

    Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods.Journal of Machine Learning Research, 18(221):1–51, 2018. (cited on 7, 27)

    work page 2018

  4. [2]

    Much faster algorithms for matrix scaling

    Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Much faster algorithms for matrix scaling. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 890–

    work page

  5. [3]

    Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.Advances in Neural Information Processing Systems, 30, 2017

    Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.Advances in Neural Information Processing Systems, 30, 2017. (cited on 1, 2)

    work page 2017

  6. [4]

    Estimating nonnegative matrices from marginal data.International Economic Review, 6(3):294–310, 1965

    Michael Bacharach. Estimating nonnegative matrices from marginal data.International Economic Review, 6(3):294–310, 1965. (cited on 1)

    work page 1965

  7. [5]

    Towards Optimal Running Times for Optimal Transport

    Jose Blanchet, Arun Jambulapati, Carson Kent, and Aaron Sidford. Towards optimal running times for optimal transport.arXiv preprint arXiv:1810.07717, 2018. (cited on 7)

    work page Pith review arXiv 2018

  8. [6]

    Better and simpler error analysis of the sinkhorn–knopp algorithm for matrix scaling.Mathematical Programming, 188(1):395–407, 2021

    Deeparnab Chakrabarty and Sanjeev Khanna. Better and simpler error analysis of the sinkhorn–knopp algorithm for matrix scaling.Mathematical Programming, 188(1):395–407, 2021. (cited on 1, 2)

    work page 2021

Show all 43 references
  1. [7]

    Matrix scaling and balancing via box constrained newton’s method and interior point methods

    Michael B Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu. Matrix scaling and balancing via box constrained newton’s method and interior point methods. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 902–913. IEEE, 2017. (cited on 2)

    2017

  2. [8]

    Semidual regularized optimal transport.SIAM Review, 60(4):941–965,

    Marco Cuturi and Gabriel Peyré. Semidual regularized optimal transport.SIAM Review, 60(4):941–965,

  3. [9]

    Acceleration methods.Foundations and Trends®in Optimization, 5(1-2):1–245, 2021

    Alexandre d’Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods.Foundations and Trends®in Optimization, 5(1-2):1–245, 2021. (cited on 9, 31) 11 0 100 200 300 400 500 10!10 10!5 100 Matrix scaling residual MNIST1(<2=0:033) Sinkhorn-Knopp Sinkhorn+Nesterov(PAGD) Si...

    2021

  4. [10]

    Stochastic matrix-free equilibration.Journal of Optimization Theory and Applications, 172(2):436–454, 2017

    Steven Diamond and Stephen Boyd. Stochastic matrix-free equilibration.Journal of Optimization Theory and Applications, 172(2):436–454, 2017. (cited on 2, 6)

    2017

  5. [11]

    Computational optimal transport: Com- plexity by accelerated gradient descent is better than by sinkhorn’s algorithm

    Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Com- plexity by accelerated gradient descent is better than by sinkhorn’s algorithm. InInternational Conference on Machine Learning, pages 1367–1376. PMLR, 2018. (cited on 1, 2, 17)

    2018

  6. [12]

    Parameterselectionandpreconditioningforagraphformsolver

    ChristopherFougnerandStephenBoyd. Parameterselectionandpreconditioningforagraphformsolver. In Emerging Applications of Control and Systems Theory: A Festschrift in Honor of Mathukumalli Vidyasagar, pages 41–61. Springer, 2018. (cited on 6)

    2018

  7. [13]

    On the scaling of multidimensional matrices.Linear Algebra and its applications, 114:717–735, 1989

    Joel Franklin and Jens Lorenz. On the scaling of multidimensional matrices.Linear Algebra and its applications, 114:717–735, 1989. (cited on 1, 2)

    1989

  8. [14]

    Non-asymptotic local convergence analysis of alternating minimization, April 2026

    Wenzhi Gao. Non-asymptotic local convergence analysis of alternating minimization, April 2026. Blog Post #4. (cited on 10)

    2026

  9. [16]

    Fast and large-scale unbalanced optimal transport via its semi-dual and adaptive gradient methods.arXiv preprint arXiv:2602.10697, 2026

    Ferdinand Genans. Fast and large-scale unbalanced optimal transport via its semi-dual and adaptive gradient methods.arXiv preprint arXiv:2602.10697, 2026. (cited on 6, 10)

    2026

  10. [17]

    On the efficiency of sinkhorn-knopp for entropically regularized optimal transport.arXiv preprint arXiv:2604.03787, 2026

    Kun He. On the efficiency of sinkhorn-knopp for entropically regularized optimal transport.arXiv preprint arXiv:2604.03787, 2026. (cited on 5)

    2026 arXiv

  11. [18]

    Phase transition of the sinkhorn-knopp algorithm

    Kun He. Phase transition of the sinkhorn-knopp algorithm. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4238–4284. SIAM, 2026. (cited on 1, 2, 5)

    2026

  12. [19]

    A review of matrix scaling and sinkhorn’s normal form for matrices and positive maps.arXiv preprint arXiv:1609.06349, 2016

    Martin Idel. A review of matrix scaling and sinkhorn’s normal form for matrices and positive maps.arXiv preprint arXiv:1609.06349, 2016. (cited on 1, 2, 3)

    2016 arXiv

  13. [20]

    A direct tilde{O}(1/epsilon) iteration parallel al- gorithm for optimal transport.Advances in Neural Information Processing Systems, 32, 2019

    Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct tilde{O}(1/epsilon) iteration parallel al- gorithm for optimal transport.Advances in Neural Information Processing Systems, 32, 2019. (cited on 7) 12

    2019

  14. [21]

    A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices.Linear Algebra and its Applications, 236:1–24, 1996

    Bahman Kalantari. A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices.Linear Algebra and its Applications, 236:1–24, 1996. (cited on 1)

    1996

  15. [22]

    On the rate of convergence of deterministic and randomized ras matrix scaling algorithms.Operations research letters, 14(5):237–244, 1993

    Bahman Kalantari and Leonid Khachiyan. On the rate of convergence of deterministic and randomized ras matrix scaling algorithms.Operations research letters, 14(5):237–244, 1993. (cited on 2)

    1993

  16. [23]

    Onthecomplexityofnonnegative-matrixscaling.Linear Algebra and its applications, 240:87–103, 1996

    BahmanKalantariandLeonidKhachiyan. Onthecomplexityofnonnegative-matrixscaling.Linear Algebra and its applications, 240:87–103, 1996. (cited on 2)

    1996

  17. [24]

    On the complexity of general matrix scaling and entropy minimization via the ras algorithm.Mathematical Programming, 112(2):371–401, 2008

    Bahman Kalantari, Isabella Lari, Federica Ricca, and Bruno Simeone. On the complexity of general matrix scaling and entropy minimization via the ras algorithm.Mathematical Programming, 112(2):371–401, 2008. (cited on 1, 2, 4, 16)

    2008

  18. [25]

    The sinkhorn–knopp algorithm: convergence and applications.SIAM Journal on Matrix Analysis and Applications, 30(1):261–275, 2008

    Philip A Knight. The sinkhorn–knopp algorithm: convergence and applications.SIAM Journal on Matrix Analysis and Applications, 30(1):261–275, 2008. (cited on 1, 2, 5, 6)

    2008

  19. [27]

    A note on overrelax- ation in the sinkhorn algorithm.Optimization Letters, 16(8):2209–2220, 2022

    Tobias Lehmann, Max-K Von Renesse, Alexander Sambale, and André Uschmajew. A note on overrelax- ation in the sinkhorn algorithm.Optimization Letters, 16(8):2209–2220, 2022. (cited on 9)

    2022

  20. [28]

    On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms

    Tianyi Lin, Nhat Ho, and Michael Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. InInternational Conference on Machine Learning, pages 3982–

  21. [29]

    A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents

    Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. InProceedings of the thirtieth annual ACM symposium on Theory of computing, pages 644–652, 1998. (cited on 2)

    1998

  22. [30]

    Softmax is $1/2$-lipschitz: A tight bound across all $\ell_p$ norms.Transactions on Machine Learning Research, 2026

    Pravin Nair. Softmax is $1/2$-lipschitz: A tight bound across all $\ell_p$ norms.Transactions on Machine Learning Research, 2026. (cited on 27)

    2026

  23. [31]

    On complexity of matrix scaling.Linear Algebra and its Applica- tions, 302:435–460, 1999

    Arkadi Nemirovski and Uriel Rothblum. On complexity of matrix scaling.Linear Algebra and its Applica- tions, 302:435–460, 1999. (cited on 2)

    1999

  24. [32]

    Springer Science & Business Media, 2013

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013. (cited on 7, 28)

    2013

  25. [33]

    Quantum entropic regular- ization of matrix-valued optimal transport.European Journal of Applied Mathematics, 30(6):1079–1102,

    Gabriel Peyré, Lenaic Chizat, François-Xavier Vialard, and Justin Solomon. Quantum entropic regular- ization of matrix-valued optimal transport.European Journal of Applied Mathematics, 30(6):1079–1102,

  26. [34]

    Now Foundations and Trends, 2019

    Gabriel Peyré and Marco Cuturi.Computational optimal transport: With applications to data science. Now Foundations and Trends, 2019. (cited on 1, 2, 5)

    2019

  27. [35]

    On sinkhorn’s algorithm and choice modeling.Operations Research, 2025

    Zhaonan Qu, Alfred Galichon, Wenzhi Gao, and Johan Ugander. On sinkhorn’s algorithm and choice modeling.Operations Research, 2025. (cited on 1, 2, 5, 16)

    2025

  28. [36]

    Concerning nonnegative matrices and doubly stochastic matrices

    Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343–348, 1967. (cited on 1)

    1967

  29. [37]

    Exact worst-case convergence rates of the proximal gradient method for composite convex minimization.Journal of Optimization Theory and Appli- cations, 178(2):455–476, 2018

    Adrien B Taylor, Julien M Hendrickx, and François Glineur. Exact worst-case convergence rates of the proximal gradient method for composite convex minimization.Journal of Optimization Theory and Appli- cations, 178(2):455–476, 2018. (cited on 8) 13

    2018

  30. [38]

    Overrelaxed sinkhorn–knopp algorithm for regularized optimal transport.Algorithms, 14(5):143, 2021

    Alexis Thibault, Lénaïc Chizat, Charles Dossal, and Nicolas Papadakis. Overrelaxed sinkhorn–knopp algorithm for regularized optimal transport.Algorithms, 14(5):143, 2021. (cited on 9)

    2021

  31. [39]

    mhc: Manifold-constrained hyper-connections.arXiv preprint arXiv:2512.24880, 2025

    Zhenda Xie, Yixuan Wei, Huanqi Cao, Chenggang Zhao, Chengqi Deng, Jiashi Li, Damai Dai, Huazuo Gao, Jiang Chang, Kuai Yu, et al. mhc: Manifold-constrained hyper-connections.arXiv preprint arXiv:2512.24880, 2025. (cited on 1)

    2025 arXiv

  32. [40]

    Accelerating sinkhorn for entropy-regularized optimal transport.arXiv preprint arXiv:2605.30267, 2026

    Zeyi Xu and Long Chen. Accelerating sinkhorn for entropy-regularized optimal transport.arXiv preprint arXiv:2605.30267, 2026. (cited on 6) 14 Appendix Table of Contents A Proof of results in Section 3 16 A.1 Auxiliary result . . . . . . . . . . . . . . . . . . . . . . . . . . ...

    2026 arXiv

  33. [43]

    For∆ 2, sinceℓ(u)is a quadratic function minimized atu−P −1∇ℓ(u), we have ∆2 =ℓ(u−P −1∇α(u))−ℓ(u−P −1∇ℓ(u)) = 1 2∥∇α(u)−∇ℓ(u)∥ 2 P−1 ≤ 1 2∥∇φ(u,v)−∇λ(u,v)∥ 2 S−1≤ 2 sε2

    Therefore,α(u−P −1∇α(u)) =γ(1)≤γ(θ max) =α(u), and it implies ∆1≤ 336 σ2 √s[φ(u,v)−φ(u ⋆,v⋆)]3/2. For∆ 2, sinceℓ(u)is a quadratic function minimized atu−P −1∇ℓ(u), we have ∆2 =ℓ(u−P −1∇α(u))−ℓ(u−P −1∇ℓ(u)) = 1 2∥∇α(u)−∇ℓ(u)∥ 2 P−1 ≤ 1 2∥∇φ(u,v)−∇λ(u,v)∥ 2 S−1≤ 2 sε2. 24 For∆ 3...

  34. [901]

    (cited on 2, 4, 7)

    IEEE, 2017. (cited on 2, 4, 7)

    2017

  35. [3991]

    (cited on 4, 7, 16)

    PMLR, 2019. (cited on 4, 7, 16)

    2019

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.