Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter

arXiv:2608.29152v1 Announce Type: cross Abstract: We study the empirical Sinkhorn estimator of the entropic optimal transport potentials under the uniform loss. Since the potentials are only unique up to additive constants, we measure the error using the quotient supremum norm, defined as d_infty([u],[v]) = inf_{ainR}|u-v-a|_infty. For a fixed regularization parameter arepsilon>0, we establish a non-asymptotic statistical rate of n^{-1/2}. This is achieved by combining the Birkhoff-Hopf contraction theorem with entropy bounds on normalized kernel sections. However, the constant in this bound grows exponentially with 1/epsilon. To improve this, we isolate geometric conditions under which the empirical estimator maintains the n^{-1/2} rate but features polynomial dependence on 1/arepsilon. The key requirement is a polynomial residual-stability estimate for the population Sinkhorn map. We provide sufficient criteria for this, including a polynomial contraction property and a local inverse estimate. Furthermore, we introduce two rigorously verifiable model classes an arepsilon-weak residual-interaction class obtained after separable centering and another based on connected tight-edge graphs for fixed discrete costs where the polynomial rate is guaranteed without relying on abstract resolvent assumptions. Finally, we establish matching minimax lower bounds demonstrating that the arepsilon n^{-1/2} rate cannot be uniformly improved in the bounded-interaction regime.

Related

• Sinkhorn Treatment Effects: A Causal Optimal Transport Measure
• Robust Sublinear Convergence Rates for Iterative Bregman Projections
• PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport

Source: arXiv cs.LG | 2026-09-01