{"id":"f93f64ba-dc6a-435e-be33-11de9eab92d2","arxiv_id":"2608.11760","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SK converges linearly at rate 1-σ2 once near the optimum, with explicit burn-in, and can be accelerated by gradient methods on the semi-dual.","lead":"Sinkhorn-Knopp, the standard matrix-scaling algorithm, is shown to converge locally at the previously conjectured sharp rate, with explicit nonasymptotic bounds. The paper also introduces accelerated variants and a better worst-case complexity for dense matrix scaling.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2's displayed iteration count is not derivable from Lemma 3.5: the local threshold gives a burn-in O(||p||_1 D^2 / (s sigma_2^2)), not the stated O(||p||_1 D^2 / min{sigma_2^4, s sigma_2^2}), and Lemma 3.4(1) disagrees with its own proof.","rationale":"The reader's verdict is CONDITIONAL, and my stress-test supports that posture. The most load-bearing issue I find is not the conceptual condition sigma_2 > 0, which the paper explicitly assumes, but the internal inconsistency in the main theorem: the burn-in complexity displayed in Theorem 3.2 is not derivable from the lemmas as written. Lemma 3.5's threshold, taken with the coefficient computed in Lemma 3.4's proof, forces a burn-in proportional to ||p||_1 D^2 / (s sigma_2^2), whereas Theorem 3.2 states a term proportional to ||p||_1 D^2 / sigma_2^4 and an O-notation with min{sigma_2^4, s sigma_2^2}. This is a concrete, checkable algebraic mismatch, not a vague concern about condition numbers. The proof structure is otherwise plausible: Lemma 3.3 gives the sharp quadratic contraction, Lemma 3.4 supplies the needed perturbation bounds, and the tightness example in A.10 supports the order-wise rate. The qualitative claim that SK locally converges in O((1/sigma_2) log(1/epsilon)) iterations is likely defensible after correcting constants and the dependence on s. I therefore see no reason to move the verdict to REJECT; the paper needs a corrected theorem statement and a reconciled Lemma 3.4(1), after which the central result should be re-checkable. I partly agree with the reader: the reader flagged the same internal inconsistencies in the rationale, but chose sigma_2 > 0 as the weakest assumption. My concern is aimed at the testable mismatch in the main theorem's proof, which I regard as the more immediate barrier to accepting the theorem as stated.","tokens_in":30883,"tokens_out":15447,"duration_ms":148234,"concrete_test":"Independently re-derive Lemma 3.5 from Lemma 3.4(3) using the proof's actual bound ||nabla phi - nabla lambda||_{S^{-1}} <= 2 epsilon / sqrt(s) and the exact |phi - lambda| bound. Then compute the threshold on epsilon needed to absorb the two extra terms into (sigma_2 / 4) epsilon and the resulting burn-in from Theorem 3.1. Check whether the displayed K_epsilon in Theorem 3.2 follows; if the burn-in is O(||p||_1 D^2 / (s sigma_2^2)) rather than O(||p||_1 D^2 / sigma_2^4), the theorem statement must be corrected accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim is Theorem 3.2. Its proof in A.9 relies on Lemma 3.5, whose recursion is obtained by combining Lemma 3.3's (1 - sigma_2) contraction for the surrogate quadratic lambda with Lemma 3.4(3)'s bound |phi - lambda| <= (168 / sigma_2)(epsilon^{3/2} / sqrt(s) + epsilon^2 / s). In A.8, the epsilon^{3/2} coefficient is computed as 336 / (sigma_2 sqrt(s)), using epsilon <= s to absorb the epsilon^2 / s term. Absorbing both extra terms into (sigma_2 / 4) epsilon then requires the local threshold epsilon <= s sigma_2^2 / 1344^2. The global phase (Theorem 3.1) must reduce phi - phi* from at most 2(||A||_1 + ||p||_1)D to this threshold, costing Theta(||p||_1 D^2 / (s sigma_2^2)). Yet Theorem 3.2 states K_epsilon = O(||p||_1 D^2 / min{sigma_2^4, s sigma_2^2}) and displays first term 2 * 1344^2 ||p||_1 D^2 / sigma_2^4, with no 1/s. For s << sigma_2^2, min = s sigma_2^2, so the explicit term is too small by a factor 1/s; for s >= sigma_2^2, the O(min{sigma_2^4, s sigma_2^2}) is weaker than the proof's actual D^2 / (s sigma_2^2). Separately, Lemma 3.4(1) as stated gives ||nabla phi - nabla lambda||_{S^{-1}} <= 2 sqrt(s epsilon), while A.7 proves 2 epsilon / sqrt(s); Lemma 3.5's Delta_2 bound uses the latter to obtain 2 epsilon^2 / s. As written, the theorem's explicit iteration count and its polynomial dependence on s are not consequences of the lemmas. This does not invalidate the qualitative local rate O((1/sigma_2) log(1/epsilon)), but the main theorem's claimed constants are unsupported and need correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31356,"tokens_out":8386,"duration_ms":84669,"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":[{"comment":"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.","section":"Lemma 3.4(1) and Appendix A.7"},{"comment":"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.","section":"Theorem 3.2 and Appendix A.9"},{"comment":"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.","section":"Theorem 3.2 assumptions"}],"minor_comments":[{"comment":"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.","section":"Appendix A.10 and table of contents"},{"comment":"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.","section":"Lemma 3.5 and Appendix A.8"},{"comment":"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.","section":"Figures 1, 2, and 3"},{"comment":"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.","section":"Proposition 3.2 and Theorem 4.3"},{"comment":"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.","section":"Section 4.5"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a sincere and largely self-contained analysis, and the qualitative local-linear-rate claim appears likely to be correct after fixing the threshold and constant errors. However, the main theorem's displayed iteration count is currently contradicted by its own proof, so I would not accept the paper in its present form. The errors are localized and repairable, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth taking seriously. The main new thing is a nonasymptotic local convergence analysis of Sinkhorn-Knopp with the same 1−σ2 rate as the asymptotic Jacobian argument, plus a lower-bound family showing the rate is attained. The template — compare the AM potential φ to its quadratic surrogate λ near the optimum, control ∇φ−∇λ and φ−λ using σ2, then recurse — is clean and should transfer to other alternating minimization schemes. The semi-dual view of SK as suboptimal preconditioned gradient descent is a nice observation, and the accelerated variants are a plausible dividend. No fitted parameters, no circularity; the tightness example is convincing.\n\nBut the central theorem as printed is not backed by its proof. Two concrete mismatches. Lemma 3.4(1) states ∥∇φ−∇λ∥_{S−1} ≤ 2√(sε); the proof in A.7 derives 2ε/√s. Lemma 3.5 uses the proof's version, so the statement of Lemma 3.4(1) is simply wrong as written. More importantly, A.9 needs the gap below sσ2^4/1344² before the (1−σ2/2) contraction starts. That makes the burn-in from Theorem 3.1 of order ∥p∥1D²/(sσ2^4). Theorem 3.2 displays 2·1344²∥p∥1D²/σ2^4 — no 1/s — and writes the complexity as O(∥p∥1D²/min{σ2^4, sσ2²}), which does not match the proof's denominator either. So the s-dependence and the constants in the headline bound are unsupported. The qualitative local rate O((1/σ2)log(1/ε)) and the local phase itself look defensible; this looks like a typo or accounting problem in the burn-in rather than a flaw in the core recursion.\n\nOther soft spots are minor. The connectivity assumption σ2>0 is a property of the solution, not checkable from A, but that is normal for local analysis. The acceleration sections lean on [15] and [26] as black boxes; acceptable. Experiments are indicative rather than extensive.\n\nWho this is for: people working on matrix scaling, Sinkhorn, and alternating minimization. It deserves a serious referee. I would send it out, with a request to fix Lemma 3.4(1) and re-derive Theorem 3.2's iteration count. After that, the paper should be in decent shape.","headline":"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.","tokens_in":31962,"tokens_out":7466,"would_cite":true,"duration_ms":65025,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that Sinkhorn-Knopp's local convergence rate matches the sharp asymptotic Jacobian rate $1-\\sigma_2$, nonasymptotically and with explicit constants.","keywords":["Sinkhorn-Knopp","matrix scaling","local linear convergence","nonasymptotic analysis","doubly stochastic scaling","alternating minimization","semi-dual","acceleration"],"falsifier":"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.","tokens_in":30618,"feed_emoji":"📊","tokens_out":11437,"duration_ms":106674,"temperature":0.7,"pith_summary":"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.","feed_headline":"Nonasymptotic proof pins Sinkhorn-Knopp's true local rate","feed_subtitle":"With a connected optimal support graph, Sinkhorn–Knopp is polynomial-time and its rate is provably tight.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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})$."],"supporting_citations":[{"why":"It introduces the Sinkhorn–Knopp algorithm that is the subject of the local analysis.","marker":"[36]"},{"why":"It provides the asymptotic Jacobian-based rate $1-\\sigma_2$ that the paper matches nonasymptotically.","marker":"[25]"},{"why":"It supplies the global sublinear convergence argument used in the proof of Theorem 3.1 for the initial phase.","marker":"[11]"},{"why":"It supplies the logarithmic solution-norm diameter bound $D$ used in the global and local iteration counts.","marker":"[24]"},{"why":"Its Lemma 2 bounds how far Sinkhorn iterates drift from the optimum, which the global-phase proof relies on.","marker":"[35]"},{"why":"It defines the semi-dual function $\\zeta$ used by all accelerated variants.","marker":"[8]"},{"why":"It provides the online scaled gradient method whose local analysis underlies the OSMS acceleration.","marker":"[15]"},{"why":"It supplies the potential-function framework used to prove the Nesterov-accelerated local rate.","marker":"[9]"},{"why":"It gives the prior first-order matrix scaling complexity that the dense-matrix result improves.","marker":"[2]"}],"fun_headline_variants":["Sinkhorn-Knopp's local rate proven optimal nonasymptotically","Nonasymptotic proof nails Sinkhorn-Knopp's contraction rate","Polynomial-time Sinkhorn-Knopp under connectivity, local rate tight","First tight nonasymptotic local convergence for Sinkhorn-Knopp"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sinkhorn-Knopp's local rate proven optimal nonasymptotically","Nonasymptotic proof nails Sinkhorn-Knopp's contraction rate","Polynomial-time Sinkhorn-Knopp under connectivity, local rate tight","First tight nonasymptotic local convergence for Sinkhorn-Knopp"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000142,"raw_usage":{"total_tokens":1150,"prompt_tokens":907,"completion_tokens":243,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":160}},"tokens_in":523,"tokens_out":243,"duration_ms":2932,"temperature":1.0,"reasoning_tokens":160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:30:23.784068+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Concerning nonnegative matrices and doubly stochastic matrices","cited_arxiv_id":null,"evidence_quote":"It introduces the Sinkhorn–Knopp algorithm that is the subject of the local analysis."},{"cited_title":"The sinkhorn–knopp algorithm: convergence and applications.SIAM Journal on Matrix Analysis and Applications, 30(1):261–275, 2008","cited_arxiv_id":null,"evidence_quote":"It provides the asymptotic Jacobian-based rate $1-\\sigma_2$ that the paper matches nonasymptotically."},{"cited_title":"Computational optimal transport: Com- plexity by accelerated gradient descent is better than by sinkhorn’s algorithm","cited_arxiv_id":null,"evidence_quote":"It supplies the global sublinear convergence argument used in the proof of Theorem 3.1 for the initial phase."},{"cited_title":"On the complexity of general matrix scaling and entropy minimization via the ras algorithm.Mathematical Programming, 112(2):371–401, 2008","cited_arxiv_id":null,"evidence_quote":"It supplies the logarithmic solution-norm diameter bound $D$ used in the global and local iteration counts."},{"cited_title":"On sinkhorn’s algorithm and choice modeling.Operations Research, 2025","cited_arxiv_id":null,"evidence_quote":"Its Lemma 2 bounds how far Sinkhorn iterates drift from the optimum, which the global-phase proof relies on."},{"cited_title":"Semidual regularized optimal transport.SIAM Review, 60(4):941–965,","cited_arxiv_id":null,"evidence_quote":"It defines the semi-dual function $\\zeta$ used by all accelerated variants."},{"cited_title":"Acceleration methods.Foundations and Trends®in Optimization, 5(1-2):1–245, 2021","cited_arxiv_id":null,"evidence_quote":"It supplies the potential-function framework used to prove the Nesterov-accelerated local rate."},{"cited_title":"Much faster algorithms for matrix scaling","cited_arxiv_id":null,"evidence_quote":"It gives the prior first-order matrix scaling complexity that the dense-matrix result improves."}],"review_version":1}