Source-linked AI summary
Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter
Denis Belomestny
TL;DR
The paper addresses finite-sample uniform estimation of entropic optimal-transport potentials modulo additive constants, where fixed-ε parametric bounds can have exponential dependence on 1/ε. It combines uniform empirical-process control with contraction and residual-stability analysis, obtaining polynomial dependence under verifiable geometric conditions and a matching ε/√n lower bound in the bounded-interaction regime.
Problem
The central problem is obtaining nonasymptotic n^-1/2 control of empirical Sinkhorn potentials in quotient sup norm while avoiding exponential deterioration as ε decreases.
Method
The paper combines entropy bounds for normalized kernel sections with Sinkhorn-map contraction and polynomial residual-stability estimates, then verifies these conditions in weak-interaction and connected tight-graph model classes.
Results
For fixed ε, the estimator has an n^-1/2 rate; under additional geometric assumptions, the constant grows polynomially in 1/ε, while a bounded-interaction minimax lower bound has order ε/√n.
Takeaways & Limitations
The joint dependence on n and ε is optimal up to universal constants in the bounded-interaction model class.
Takeaways & Limitations
The estimator is the exact empirical Schrödinger-system solution and does not include optimization error from terminating Sinkhorn’s algorithm after finitely many iterations; the weak-interaction definition also does not cover arbitrary fixed nonseparable costs.
Abstract
from arXiv · showhide
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_{a\in\mathbb{R}}\|u-v-a\|_\infty$. For a fixed regularization parameter $\varepsilon>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/ε$. To improve this, we isolate geometric conditions under which the empirical estimator maintains the $n^{-1/2}$ rate but features polynomial dependence on $1/\varepsilon$. 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 $\varepsilon$-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 $\varepsilon n^{-1/2}$ rate cannot be uniformly improved in the bounded-interaction regime.
1. Introduction
The paper studies empirical Sinkhorn potentials in quotient sup norm, establishing fixed-ε parametric convergence and identifying conditions for polynomial rather than exponential dependence on 1/ε. It supplies verifiable model classes and matching lower bounds in the bounded-interaction regime.
- Problem setup: The empirical Sinkhorn estimator solves the empirical Schrödinger system using sampled marginal measures, and optimization error from finite Sinkhorn iterations is excluded.The estimator is the exact empirical-system solution.
- Polynomial regime: Polynomial dependence on 1/ε follows when empirical complexity, normalized-kernel envelopes, and population residual stability are each controlled polynomially.The abstract principle separates entropy, envelope, and inverse-stability contributions.
- Verifiable models: Two model classes make the stability assumptions verifiable: ε-weak interactions with controlled oscillation and regularity, and finite-state costs with connected tight graphs and strict complementarity.Both yield inverse-stability constants controlled polynomially in ε^-1.
- Lower bound: A two-point minimax lower bound of order ε/√n shows that the joint n- and ε-dependence is optimal up to universal constants in the bounded-interaction class.The lower bound includes the corresponding deviation dependence.
2. Literature overview
Prior work established fixed-regularization parametric behavior, stability results, asymptotic limits, and polynomial dependence in other losses. This paper targets finite-sample quotient-supremum control with explicit regularization dependence and matching lower bounds under verifiable assumptions.
- Statistical estimation: Earlier studies obtained n^-1/2 convergence for fixed regularization, but their constants may deteriorate rapidly as ε decreases.Related work also includes dimension-free and complexity-adaptive results for other entropic-transport quantities.
- Stability and regularity: Existing stability and regularity results do not by themselves provide a nonasymptotic n^-1/2 quotient-supremum bound with explicit polynomial dependence on ε.Those results establish continuity and regularity mechanisms for Schrödinger potentials and couplings.
- Limit theory: Limit-theory work derives central limit and Gaussian-process results for fixed ε, whereas this paper seeks finite-sample sup-norm estimates tracking deterioration as ε decreases.The cited asymptotic theory explains why a root-n scale is natural when ε is fixed.
- Small regularization: Research on ε→0 convergence, decreasing-regularization regimes, and Schrödinger-bridge plug-in estimators addresses related but distinct asymptotic or path-space questions.These studies concern Kantorovich limits, changing regularization, or metrics on path measures.
- Positioning: Compared with prior empirical L2 results having polynomial ε-dependence, this work provides uniform control modulo constants through quotient-supremum analysis and inverse stability.For fixed ε the rate is parametric, and under geometric assumptions its ε-dependence is polynomial.
3. Parametric Rates with Exponential Dependence
For fixed ε, empirical Sinkhorn potentials achieve the parametric n^-1/2 rate in quotient sup norm under finite entropy conditions, but the bound has exponential dependence on 1/ε.
- τ_ε is defined from the cost oscillation as tanh(C_c/(2ε)), providing the contraction factor for the Sinkhorn analysis.
- Under Lipschitz costs and finite entropy integrals for normalized kernel sections, the estimation errors satisfy a high-probability uniform bound.
- For fixed ε>0, the quotient sup-norm error converges at the parametric rate O_P(n^-1/2).
- The exponential dependence on 1/ε arises from normalizing-integral lower bounds and global projective contractions.
4. Parametric Rates with Polynomial Dependence
Polynomial dependence on 1/ε is obtained by combining polynomial empirical complexity with polynomial residual stability of the population Sinkhorn map, under assumptions that can be checked through geometric criteria.
- The polynomial regime assumes envelope and entropy bounds that grow polynomially or polylogarithmically in 1/ε.
- Polynomial residual stability requires the quotient distance to the population potential to be bounded by K_0 ε^-r times the population residual.
- Theorem 4.4 combines these assumptions with a sample-size condition to yield a high-probability polynomial-rate estimation bound.
- For 0<ε≤1 and p≥a, the theorem simplifies to an explicit rate whose ε-dependence remains polynomial, ignoring logarithms in H_ε.
- A local inverse estimate supplies polynomial residual stability when the derivative is invertible, its inverse has norm O(ε^-r), and the remainder is quadratic.
- Polynomial envelopes for normalized Gibbs sections require additional geometric assumptions and do not alone establish entropy or residual stability.
5. Verifiable Model Classes
The paper gives two verifiable model classes where polynomial dependence on 1/ε can be established: separably centered weak interactions and fixed discrete costs with connected tight-edge graphs.
- Overview: The criteria use endpoint-support geometry and cost structure to secure polynomial bounds without unverified abstract curvature assumptions.These criteria are introduced as verifiable alternatives for controlling the relevant stability bounds.
- 5.1. Polynomial-Interaction Model Class: Separable cost shifts leave the entropic coupling unchanged, so potential errors can be analyzed through the residual cost.Rectangular centering provides a residual whose norm and oscillation are controlled by rectangular interaction oscillation.
- 5.1. Polynomial-Interaction Model Class: The ε-weak-interaction class writes the cost as c_ε = a_ε + b_ε + εℓ_ε, with controlled interaction oscillation and regularity.The class is defined through support covering numbers, interaction oscillation, and global Lipschitz conditions.
- 5.1. Polynomial-Interaction Model Class: Under γ_osc = q = 0, the weak-interaction class yields quotient-supremum error of order εn^-1/2, up to logarithmic deviation factors.The stated corollary gives a constant depending on A_0, L_0, D*, and d* multiplying εn^-1/2.
6. A matching minimax lower bound in the bounded-interaction regime
The paper proves matching minimax lower bounds in a binary bounded-interaction subclass, showing that neither the ε factor nor the n^-1/2 factor can be uniformly improved.
- Lower-bound setup: The lower-bound argument applies to arbitrary measurable estimators, not only the empirical Sinkhorn estimator.The experiment may even reveal the common marginal and cost to the estimator, making the bound apply to a more informative setting.
- Lower-bound setup: The hard subclass uses two-point endpoint spaces with discrete metrics and belongs to the bounded-interaction class with γ_osc = q = 0.Its geometric parameters satisfy D_X = D_Y = 1 and d_X = d_Y = 1.
- Testing argument: The binary construction separates the two potentials by a quantity proportional to ε|t| for small |t|.The local lower bound on the characteristic function yields the stated potential separation.
- Minimax conclusion: No estimator can uniformly improve either the ε factor or the n^-1/2 factor in the upper bound over bounded-interaction classes containing the binary subclass.The lower bound is therefore minimax and applies beyond the empirical estimator.
- Minimax conclusion: The deviation factor 1 + √log(1/δ) is also unavoidable up to constants in the stated range of n and δ.This sharpness statement concerns the bounded weak-interaction regime.
7. Conclusion
The conclusion states that quotient-supremum convergence is parametric in n, while polynomial dependence on 1/ε requires both empirical complexity control and residual stability.
- Conclusion: For fixed ε, empirical Sinkhorn potentials converge in quotient sup norm at the parametric rate n^-1/2.The baseline result assumes finite entropy for normalized kernel sections.
- Conclusion: Standard global arguments can produce constants exponential in 1/ε, whereas polynomial dependence requires polynomial empirical complexity and polynomial residual stability.The conclusion identifies both conditions as primary requirements for retaining the n^-1/2 rate.
- Conclusion: The paper supplies practical frameworks based on weak interactions and verifiable geometric conditions, together with matching minimax lower bounds in the weak-interaction regime.These frameworks address polynomial dependence without weakening the parametric sample-size rate.
Appendix A: Proofs
The appendix derives the statistical bounds by combining kernel contraction, empirical-process control, and stability estimates, then verifies the model-specific polynomial rates.
- Kernel contraction: Birkhoff–Hopf contraction controls the integral kernel operator in Hilbert’s projective metric.Applying the result to exponentiated potentials transfers the contraction to the Sinkhorn transform.
- Empirical-process control: Symmetrization, Dudley’s entropy inequality, and McDiarmid’s inequality yield n^-1/2 empirical-process bounds for normalized kernel-section classes.The proof separately controls expected suprema and bounded-difference deviations.
- Residual stability: Residual stability converts empirical Sinkhorn-map errors into quotient-potential errors through contraction or local inverse estimates.The appendix derives both global contraction-based and localized inverse-stability inequalities.
- Polynomial envelopes: Local Hölder behavior and lower-mass conditions produce polynomial envelopes for normalized Gibbs sections.The proof localizes around a maximizer and lower-bounds the denominator using the mass of a metric ball.
- Fixed-cost discrete proof: For the fixed-cost discrete class, connected tight-edge structure and positivity make the limiting constrained Jacobian invertible.Lipschitz dependence on the empirical marginals then yields the linear-in-ε potential bound.