← 研踪 PaperTrailarXiv:2604.03787 · v2
Dimension-Free Sinkhorn for Optimal Transport: Bypassing Extremal Costs
首次提交 2026-04-05 00:24
版本更新 2026-11-07 09:57
雷达观测 2026-11-10 11:14
摘要
The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing bounds for achieving marginal accuracy $\varepsilon$ deteriorate severely in the presence of extreme entries, bottlenecked either by the global maximum regularized cost $η\|C\|_\infty$ (where $η$ is the regularization parameter and $C$ the cost matrix) or the matrix's minimum-to-maximum entry ratio $ν$. These bounds may be overly sensitive to rare extreme entries that do not dominate the overall matrix structure. We identify a broad structural regime in which the dependence on the magnitude of global extreme entries can be circumvented. For EOT, we introduce well-boundedness, a local mass property that captures the row- and column-wise bulk structure of the underlying matrix while maintaining robustness against scattered entrywise outliers. We prove that, governed by this structural condition, SK converges to the target transport plan for a problem of dimension $n$ in $O(\log n + \log(1/\varepsilon))$ iterations. This complexity bound is independent of the maximum regularized cost $η\|C\|_\infty$. A computationally negligible pre-scaling step eliminates this dimensional dependence, reducing the iteration complexity to a strictly dimension-free $O(\log(1/\varepsilon))$. Beyond EOT, we establish a sharp phase transition for general $(\boldsymbol{u},\boldsymbol{v})$-scaling governed by a critical matrix density threshold. We prove that when a matrix's density exceeds this threshold, the iteration complexity is strictly independent of $ν$. Conversely, when the density falls below this threshold, the dependence on $ν$ becomes unavoidable; in this sub-critical regime, we construct instances where SK requires $Ω(n/\varepsilon)$ iterations.
作者备注：70 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-07 09:57 · 最新观测版本
Dimension-Free Sinkhorn for Optimal Transport: Bypassing Extremal Costs
The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing bounds for achieving marginal accuracy $\varepsilon$ deteriorate severely in the presence of extreme entries, bottlenecked either by the global maximum regularized cost $η\|C\|_\infty$ (where $η$ is the regularization parameter and $C$ the cost matrix) or the matrix's minimum-to-maximum entry ratio $ν$. These bounds may be overly sensitive to rare extreme entries that do not dominate the overall matrix structure. We identify a broad structural regime in which the dependence on the magnitude of global extreme entries can be circumvented. For EOT, we introduce well-boundedness, a local mass property that captures the row- and column-wise bulk structure of the underlying matrix while maintaining robustness against scattered entrywise outliers. We prove that, governed by this structural condition, SK converges to the target transport plan for a problem of dimension $n$ in $O(\log n + \log(1/\varepsilon))$ iterations. This complexity bound is independent of the maximum regularized cost $η\|C\|_\infty$. A computationally negligible pre-scaling step eliminates this dimensional dependence, reducing the iteration complexity to a strictly dimension-free $O(\log(1/\varepsilon))$. Beyond EOT, we establish a sharp phase transition for general $(\boldsymbol{u},\boldsymbol{v})$-scaling governed by a critical matrix density threshold. We prove that when a matrix's density exceeds this threshold, the iteration complexity is strictly independent of $ν$. Conversely, when the density falls below this threshold, the dependence on $ν$ becomes unavoidable; in this sub-critical regime, we construct instances where SK requires $Ω(n/\varepsilon)$ iterations.
查看此版本解读 →查看此版本原文 ↗