CS Paper Radar

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

Wenzhi Gao, Zhaonan Qu, Yinyu Ye, Madeleine Udell

cs.LG math.OCstat.ML ·submitted 2026-08-12 07:56 UTC · v3

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}})$.

Closest papers

Nearest neighbours by meaning across the whole index.

Global Sinkhorn Convergence and Spectral Stability of Matrix Scaling

cs.DS ·2026-11-06 ·Kun He
theory similarity 0.66
Abstract · 71 pages

We give a global spectral bound for the Sinkhorn--Knopp (SK) algorithm. Let $A$ be a row-stochastic nonnegative $n\times n$ matrix admitting a finite doubly stochastic scaling $B$. Define \[ g=1-s_2(B)^2>0, \qquad D=\min\left\{\|(u,v)\|_\infty: B=\operatorname{diag}(e^u)A\operatorname{diag}(e^{-v})\right\}. \] From the standard initialization, SK achieves total marginal $\ell_1$ error $\varepsilon$ in \[ O\!\left(\frac{D+\log n+\log(1/\varepsilon)}{g}\right) \] iterations. A scale-invariant potential contracts globally according to the spectrum of $B$. The linear dependence on $D$ is necessary in the fixed-gap regime: we construct strictly positive inputs with constant input and endpoint spectral gaps, $D=Θ(n)$, and an $Ω(n)$ iteration lower bound at error $n^{-2}$. Our upper bound gives $O(n)$ iterations on this family. We next give spectral certificates for scalability and short scaling distance. For a row-stochastic input $A$ with positive column sums $c_j$, set \[ K=\frac{\max_jc_j}{\min_jc_j},\qquad σ=s_2\!\left(A\operatorname{diag}(c)^{-1/2}\right). \] The input-only condition $\sqrt K\,σ<1$ certifies exact scalability and polynomial scaling distortion, with $D=O(\log n)$ for fixed $K$ and a fixed positive spectral margin. Given a finite scaling $B$, the weaker condition $\sqrt K\,σs_2(B)<1$ gives the same structural bounds. With a constant endpoint gap, these bounds imply logarithmic SK iteration complexity. Boundary constructions show that the strict spectral inequalities cannot uniformly be replaced by nonstrict ones.

0.30

Near-Optimal Parallel $M$-Matrix Scaling

cs.DS math.OC ·2026-10-15 ·Chih-Hung Liu, Aaron Sidford, Ta-Wei Tu
similarity 0.62
Abstract

In this paper we consider the problem of computing a positive diagonal scaling of a $d \times d$ symmetric $M$-matrix so that all row and column sums are $1$. We provide a poly-logarithmic iteration algorithm that solves this problem to high accuracy, where the cost of each iteration is dominated by the cost of solving a Laplacian system. This improves upon the recent $\tilde{O}(d^{1/3})$ iteration bound of [Vladu STOC 2025] and yields a randomized algorithm for the problem that runs in near-linear time and poly-logarithmic parallel depth.

0.52

Near-Optimal Nonconvex Matrix Completion

cs.LG math.NA ·2026-09-15 ·Jian-Feng Cai, Xiliang Lu, Juntao You
similarity 0.61
Abstract

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

0.38

Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation

cs.LG math.OCeess.SY ·2026-11-10 ·Ramanan Tamizholi, Siddharth Chandak, Rahul Singh
similarity 0.60
Abstract · 23 pages

We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.

0.08

Stable and Online Algorithms for Random Matrix Discrepancy

cs.DS cs.CCcs.DMmath.CO+1 ·2026-10-01 ·Eren C. Kızıldağ, Shuangping Li
theoryhighly cited similarity 0.59
Abstract

We study the average-case matrix discrepancy problem: given independent normalized $d\times d$ Gaussian orthogonal ensemble matrices $A_1,\dots,A_N$ and a fixed margin $κ>0$, find signs $σ_1,\dots,σ_N\in\{-1,1\}$ such that the operator norm of $\sum_{i=1}^N σ_i A_i$ is at most $κ\sqrt{N}$. Focusing on the proportional regime $N/d^2\to τ\in(0,\infty)$ as $d\to\infty$ followed by the small-margin limit $κ\downarrow 0$, we characterize the density required by stable offline algorithms and by online algorithms. In the offline setting, we construct a polynomial-time \emph{recenter-and-round} algorithm that is noise-stable and succeeds whenever $τ=Ω(\frac{1}{κ^2\log(1/κ)})$, along with a matching lower bound for all stable algorithms. In the online setting where each sign must be chosen irrevocably upon observing the corresponding matrix, we determine the exact limiting performance of the \emph{Frobenius-greedy} algorithm, establishing that it succeeds when $τ>τ_{\rm FG}(κ)\sim \fracπ{4κ^2}$, as well as a matching lower bound for all online algorithms by conditioning on a revealed prefix. At the core of our algorithms lies rotational symmetry, which enables us to transfer Frobenius norm control into operator norm guarantees. Together, our results identify the algorithmic phase transition points for random matrix discrepancy: $Θ(\frac{1}{κ^2\log(1/κ)})$ for stable offline algorithms and $Θ(\frac{1}{κ^2})$ for online algorithms. Both thresholds lie far above the satisfiability scale $Θ(\log(1/κ))$, as shown by Maillard~\cite{maillard2025}.

0.30

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

cs.DS math.FAmath.OCmath.PR ·2026-09-14 ·Zhao Song, Lichen Zhang
theory similarity 0.59
Abstract

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ with $\|\sum_{i=1}^n\varepsilon_iA_i\|=O(\sqrt n)$. We prove it: a signing of discrepancy below $8\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\operatorname{polylog}(1/p)$ arithmetic operations in the real-arithmetic model. This matches the size $n^3$ of the dense input up to subpolynomial factors. In the other direction, we prove that for every $n$ there are collections of symmetric matrices such that every signing has discrepancy at least $(2-o(1))\sqrt{n}$. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body $\{x\in \mathbb{R}^n:\|\sum_ix_iA_i\|\le R\}$ that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant $7\cdot10^9$. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The $n^{3+o(1)}$ time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.

0.47

Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials

cs.DS math.PRmath.NAmath.ST ·2026-09-23 ·Yihan Zhang
similarity 0.59
Abstract

We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = λvv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(λ)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods with random initialization is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.

0.18

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer

cs.DS ·2026-09-16 ·Tarun Kathuria
theory similarity 0.58
Abstract · The authors explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for …

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.49