CS Paper Radar

Sinkhorn Linearization and the Spectral Proxy: Unifying the Statistical and Algorithmic Theory of Feature-Parameterized Inverse Optimal Transport via a Single Spectral Sandwich

Han Dong, Jiaming Li, Yongqiang Gong, Ruixi Li, Yin Liu

cs.LG stat.MLmath.OCmath.ST ·submitted 2026-08-13 13:03 UTC · v1

Abstract

We develop the statistical and algorithmic theory of inverse optimal transport (IOT) under the feature-parameterized cost C_theta(i,j) = -theta^T phi(i,j). The core technical contribution is the Sinkhorn linearization -- the implicit-function sensitivity of the entropic OT plan to the cost -- together with its spectral proxy, a formula that is spectrally exact yet geometrically transparent. The restricted Hessian on the tangent space satisfies the spectral sandwich (pi_min/epsilon) I <= H_T^{-1} <= (pi_max/epsilon) I, yielding the single core bound sigma_min >= (pi_min/(a_max epsilon)) sqrt(lambda_min(Sigma)) that drives the entire theory. On this core we establish four theorems and one observation. T1 (identifiability): theta is globally injective on the quotient of the gauge kernel, with dimension bound F <= (K-1)^2. T2 (sparsistency): the l1-penalized estimator recovers the true support under irrepresentability and score concentration, with exponential failure probability. T3 (well-posedness): the feature-moment map M(theta) = Phi^T x_theta is strongly monotone, and the inverse is Lipschitz with constant L <= epsilon ||Phi^T S_a||_op / (pi_min lambda_min(Sigma)). T4 (convergence): local strong convexity with mu >= pi_min^2 lambda_min(Sigma) / epsilon^2 guarantees monotone gradient descent convergence. O5 (misspecification): the estimator converges to the OT-model projection of the truth; the Holder continuity of the projection map is assessed numerically, yielding setting-dependent empirical exponents alpha_eff in (0,1).

Comment
32 pages, 16 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime

cs.LG math.ST ·2026-09-22 ·Tomas Gonzalez, Gonzalo Mena
theory similarity 0.65
Abstract

We study statistical rates in entropic optimal transport in the semi-discrete regime where one measure has finite support and the other is subGaussian. Our main result establishes parametric convergence rates for the empirical dual potentials to their population counterparts, with no dimension dependence in the leading term. Our result relies on tailored strong concavity analysis of the semi-dual objective, coupled with specialized bounds for the semi-discrete potentials. As a consequence, we obtain fast rates for downstream quantities derived from the optimal coupling. Chiefly, the empirical barycentric projection achieves a squared-error rate $n^{-1}$, matching the fully compact case and improving over the less favorable $n^{-1/2}$ rate known for fully subGaussian settings. Altogether, these results may indicate a lower complexity adaptation phenomenon whereby the statistical complexity of the barycentric projection is governed by the discrete measure. As an application, we analyze Sinkhorn-EM, an EM-type algorithm in which the E-step is replaced by an entropic optimal transport problem. In a well-specified and balanced two-component Gaussian mixture model, we prove $\sqrt{n}$-consistency of the empirical iterates to their population counterparts for any fixed number of iterations, matching classical EM rates up to a $\sqrt{\log n}$ factor. Simulations support the theory.

0.12

Second-order Sinkhorn Geometry and $\sqrt{n}$-Inference

cs.LG stat.MLmath.ST ·2026-10-27 ·Tristan Luca Saidi, Florian Gunsilius, Gonzalo Mena
theory similarity 0.62
Abstract

The Sinkhorn divergence, a debiased form of entropic optimal transport, has been widely used in various scientific disciplines due to its computational and statistical tractability. Unlike the Wasserstein distance, however, the Sinkhorn divergence is not a metric and it does not naturally admit a formal Riemannian structure. These properties are central to many applications of optimal transport methods that utilize interpolation, barycentric averaging, parallel transport or other geometric operations. Recent work addresses these shortcomings by constructing a formal Riemannian tangent space and a metric tensor on the space of probability measures that quadratically approximates the Sinkhorn divergence. In this work, we extend this framework with two major threads of contributions. For a suitable class of finite-smoothness cost functions, we prove Hadamard differentiability of the Sinkhorn metric tensor and we derive the Levi-Civita covariant derivative in this geometry; we then use the covariant derivative to obtain the geodesic and parallel transport equations, each of which amount to an ODE on a fixed Reproducing Kernel Hilbert Space (RKHS) with smooth coefficients. Our second contribution is to linearize the solutions to the geodesic and parallel transport equations using standard tools from Banach space ODE theory. We show that under standard regularity conditions these linearizations imply $\sqrt{n}$-limiting Gaussian processes centered at population values for the plugin estimators of the exponential map, the logarithmic map, parallel transport and the induced Sinkhorn distance. Moreover, we show that the nonparametric bootstrap is consistent for all objects mentioned. To the best of our knowledge, these are the first $\sqrt{n}$--limit theorems and bootstrap consistency results for canonical geometric operations in a transport-based geometry on the space of probability measures.

0.11

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

cs.LG stat.MLmath.OC ·2026-08-29 ·Denis Belomestny
theory similarity 0.61
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_{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.

0.34

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

cs.LG ·2026-08-28 ·Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren, Reuben Dorent
theorycode/data similarity 0.59
Abstract

Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with $N$ points, each iteration requires $O(N^2)$ operations, which restricts its use on large-scale datasets (e.g. $N\geq10^4$). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with $L$ slices, each resulting sparse Sinkhorn iteration costs $O(LN)$; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.

0.19

Efficient Online Inverse Optimization with $O(d)$ Regret

cs.LG cs.DS ·2026-09-11 ·Yang Cai, Anupam Gupta, Vineet Gupta, Guru Guruganesh, Yanchen Jiang +5 more
highly cited similarity 0.58
Abstract

We give a deterministic algorithm for online inverse linear optimization with regret $O(d)$, uniform in the horizon and $O(d^{2})$ time per round. A bound of this order was obtained recently by Dewasurendra, settling a question of Gollapudi et al.\ and of Oki and Sakaue, but by an improper rule that enumerates covers at every scale and costs $T^{Θ(d)}$ a round; ours is the first efficient such bound and the first proper one. We build on the variable-metric framework of Sakaue et al., adding a self-normalized rank-one update, and we replace the $\log\det$ potential by the trace power $\tr(H^{-1/2})$, which is bounded outright and removes the $\ln T$. The bound also holds against an expert that does not optimize, and we give corruption-robust and rank-adaptive variants, and an application to convex minimization.

0.45

From Tsallis to KL: Convergence and Error Estimates for Tsallis-Regularized Optimal Transport

cs.IT math.FAmath.OCmath.PR ·2026-09-06 ·Takeshi Suguro, Toshiaki Yachimura
similarity 0.57
Abstract · 24 pages

We study the Tsallis-to-Kullback--Leibler (KL) limit for entropy-regularized optimal transport with nonnegative bounded continuous costs. Fixing the regularization parameter $\varepsilon > 0$, we first derive an exact variational reformulation of Tsallis-regularized optimal transport in terms of the Tsallis information projection onto the set of couplings. The formula isolates an explicit correction term and thereby explains why, unlike in the KL case, the regularized transport problem and the corresponding information projection problem do not coincide exactly. We also establish existence and uniqueness for the Tsallis information projection. We then prove, with respect to the narrow topology, the $Γ$-convergence of the Tsallis-regularized functionals to the KL-regularized functional as $q\downarrow1$, together with narrow convergence of their unique minimizers. Finally, we obtain explicit error estimates of order $O(q-1)$ for both the regularized optimal transport values and the associated information projection values. These results quantify the passage from Tsallis regularization to the classical KL setting and clarify the relation between entropic regularization and information projection for $1 < q \leq 2$.

0.26

The information geometry of the Sinkhorn divergence on a Hilbert manifold

cs.IT math.ST ·2026-10-29 ·Paul Navas
similarity 0.56
Abstract

The Sinkhorn divergence, the debiased entropic optimal transport cost, determines a metric tensor on probability measures defined along curves, due to Lavenant et al. We construct a real-analytic Hilbert manifold of measures, the smooth stratum, on which this tensor is a weak Riemannian metric, and we continue Eguchi's construction of a geometry from a divergence to the third order. The stratum consists of the measures with a positive Sobolev density on a closed Riemannian manifold, and the strata form a scale whose intersection is the Fréchet manifold of smooth positive densities of Ay. Following it, we characterize the metric through the gradients of mean values: its cotangent form is a spectral reweighting of the Dirichlet form of a Markov chain, so the metric is of the same kind as the Fisher-Rao and the Otto metric, and on the stratum it is bounded by a multiple of the Fisher-Rao metric (but not conversely). At third order, the Sinkhorn divergence is self-dual: both connection forms of Eguchi's construction coincide with the Levi-Civita form of the metric, and the cubic tensor vanishes, as a consequence of the transposition symmetry of the transport problem. On every stratum, the Levi-Civita form is represented, so the stratum has a real-analytic Levi-Civita connection, which on the Fréchet manifold is the connection of Ay and Schwachhöfer.

0.17

Optimization Geometry of Equivalent Brownian RKHS Representations

cs.LG ·2026-09-18 ·Mahdi Mohammadigohari, Gustau Camps-Valls
theory similarity 0.55
Abstract

Equivalent finite parameterizations can represent the same functions and intrinsic norm yet induce different optimization algorithms. We study this effect in a controlled finite Brownian RKHS with nodal, increment, and spectral coordinates. Classical finite-element, RKHS-interpolation, Brownian-covariance, and mixed-boundary DCT identities make the shared hypothesis class, Brownian energy, approximation operator, and coordinate maps explicit. Our main results concern the optimization geometry of this fixed model. With mapped initialization, identical scalar steps, and identical minibatches, nodal and spectral GD/SGD have exactly the same mapped trajectories. Increment GD is an explicit Euler step for the constant Brownian/Sobolev metric, with factor $1/h$. For Brownian-regularized least squares, $κ_2(\mathbf H_{\mathrm{inc}})\le1+A/ρ$, independently of grid resolution $G$ for fixed $A$, $ρ>0$, and the stated normalization. Under the stated standard-Adam convention, the universal orthogonal equivariance group is exactly the signed permutations; the block DCT-VIII transform is not one. Float64 tests over five grids numerically verify the finite identities, mapped one-layer and recursive trajectories, conditioning predictions, and theorem-matched Adam separation. Thus coordinate effects are isolated without changing the represented functions, intrinsic regularizer, or approximation space.

0.25