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 $\eta\|C\|_\infty$ (where $\eta$ is the regularization parameter and $C$ the cost matrix) or the matrix's minimum-to-maximum entry ratio $\nu$. 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 $\eta\|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 $\nu$. Conversely, when the density falls below this threshold, the dependence on $\nu$ becomes unavoidable; in this sub-critical regime, we construct instances where SK requires $\Omega(n/\varepsilon)$ iterations.