CS Paper Radar

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

Takeshi Suguro, Toshiaki Yachimura

cs.IT math.FAmath.OCmath.PR ·submitted 2026-09-06 07:16 UTC · v1

Abstract

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$.

Comment
24 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Transport PAC-Bayes Bounds

cs.LG ·2026-10-12 ·Armin Beck, Peter Ochs, Jalal Fadili
similarity 0.59
Abstract

PAC-Bayesian generalization bounds are among the strongest distribution-dependent guarantees in statistical learning and are typically expressed in terms of the Kullback-Leibler (KL) divergence between a prior and posterior distribution. While analytically convenient, the KL divergence requires the posterior to be absolutely continuous w.r.t. the prior, imposing support constraints that can substantially restrict the choice of posterior. Moreover, the KL divergence does not account for the underlying geometry of the probability space. In this work, we derive new PAC-Bayesian bounds replacing the KL divergence with general optimal transport (OT) distances, including the total variation and Wasserstein-$p$ distances.

0.33

Expected free energy as an information constraint on the Bethe Lagrangian

cs.IT cs.AIeess.SYstat.ML ·2026-08-17 ·Wouter M. Kouw
similarity 0.58
Abstract · 17 pages, 4 figures, table 2. International Workshop on Active Inference

Active inference selects actions by minimising an expected free energy functional over predicted futures. However, adding an expectation over yet-unobserved outcomes means the free energy functional no longer has a Kullback-Leibler structure, which hinders message passing treatments of inference procedures. We propose an alternative formulation based on a Bethe free energy functional, fully supporting inference by message passing. The epistemic drive is maintained by imposing an information constraint, next to normalisation, marginalisation and form constraints, insisting that the mutual information between future observations, states and parameters given actions must be at least as large as the entropy of the goal prior. For a specific value of the corresponding Karush-Kuhn-Tucker multiplier, the stationary point of this constrained Bethe Lagrangian recovers the expected free energy solution. We show that, as the information demand is varied, the solved multiplier moves through its inactive, interior, and saturated regimes. In the inactive regime the agent's epistemic drive switches off entirely, while in the saturated regime it is maximal. We compare the performance of the constrained Bethe agent on three tasks against EFE and Q-MDP.

0.37

Some remarks on the connection between generative diffusion and optimal transport

cs.LG stat.MLcond-mat.dis-nn ·2026-10-09 ·Giulio Biroli, Marc Mézard
similarity 0.57
Abstract

We discuss three simple connections between generative diffusion and optimal transport. First, the joint law of the data and of their Ornstein-Uhlenbeck noising is, at every time, the solution of an entropic optimal-transport problem, at a temperature set by the noise level. Backward diffusion can consequently be read as an annealing which gradually decreases the entropic regularization. Second, we study the speciation transition--how the modes of the data distribution emerge during generation--and compare how it happens in diffusion and flow matching with respect to optimal transport. Using Gaussian mixtures as high-dimensional example, we show that the dynamical instability through which diffusion and flow matching separate the modes becomes, for optimal transport, an exponentially thin boundary layer at the beginning of generation, which is rounded by entropic regularization. Third, considering a generic forward dynamics with a general confining potential, we show that the backward process driven by the score also satisfies a drift-based variational principle whose minimal cost is the entropy difference between initial and final distributions.

0.29

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

cs.LG stat.MLmath.OCmath.ST ·2026-08-13 ·Han Dong, Jiaming Li, Yongqiang Gong, Ruixi Li, Yin Liu
similarity 0.57
Abstract · 32 pages, 16 figures

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).

0.10

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.56
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

Topology and Information in Regularized Transport on Graphs

cs.DM cond-mat.softcs.IT ·2026-10-30 ·Shintaro Yoshizawa
theory similarity 0.56
Abstract · 50 pages

We study how two geometries of mass on a finite graph interact: the information geometry of the generalized entropy $F_q$ used for regularized transport, and the arithmetic of divisors governed by the Riemann--Roch theorem of Baker and Norine and by the Jacobian. Because the correction term of $F_q$ is affine, $F_q$-regularization at strength $γ$ is Tsallis regularization at temperature $γ/q$. Over the reals, chip-firing connects all configurations of equal degree, so the Jacobian enters transport only through integrality. We introduce the transport defect, the worst-case cost of steering $d$ chips towards a target by chip-firing, and prove $1/d\leδ_{\TV}(D)\le(d-r(D))/d=(g-1-r(K-D))/d\le\min(1,g/d)$ whenever $g\ge1$; vertex multiplicities give a lower bound and an equality criterion. A regularized topological gap $Γ_{q,γ}(D,E)$ tends to the chip-move defect as $γ\to0$, lies in an explicit window, has a high-temperature slope given by Tsallis coupling entropies, and admits a positive regime if and only if $g\ge1$. Dual potentials certify exactly the convex relaxation of a linear system; the remainder is an integrality gap. Zeros in optimal plans occur only for $q>1$, by a mechanism different from the sign change of $Γ$. Exact computations on $1784$ divisor classes find the rank bound $(d-r(D))/d$ attained in $1769$ of them, an observed frequency. Experiments on honeycomb and Erdős--Rényi networks with $10^2$ to $10^5$ nodes test the statements on regularized plans, not $Γ$; over $10^3\le n\le10^5$ their transport costs are consistent with growth like $n^{1/2}$ and $\log n$, respectively.

0.30

Physics of Information Geometry - Part I: Principle of Least Action on the Probability Simplex

cs.IT cond-mat.stat-mech ·2026-09-08 ·C. Emre Koksal, Deniz Sargun
similarity 0.55
Abstract

We develop a least-action framework for describing how a probability distribution can evolve from an equilibrium state to a prescribed nonequilibrium state under constrained incremental changes. Taking a Gibbs distribution as the equilibrium reference, the framework gives a direct physical meaning to the geometry of the probability simplex: distance from equilibrium corresponds to nonequilibrium free energy, while changes between successive distributions carry an informational kinetic cost. The Pythagorean structure of relative entropy then provides the central insight of the work. It shows that intermediate distributions chosen via sequential information projections can reduce the kinetic cost of large transitions and establishes an energy-conservation-like relation between the kinetic expenditure along a path and the free energy accumulated in reaching the target distribution. Motivated by this geometry, we construct a greedy least-action path through successive information projections, obtain a closed-form characterization of each projection through the Lambert W function, and establish a finite-step performance guarantee. We further show that state-dependent costs can be incorporated naturally by reshaping the underlying Gibbs reference, providing a thermodynamic interpretation of path penalties as modifications of the effective energy landscape. Together, these results provide a unified view of distributional evolution through least action, information geometry, and nonequilibrium thermodynamics.

0.41

On Minimum Divergence for Distribution Reconstruction

cs.IT math.ST ·2026-10-15 ·Justin Bec, Thomas Le Corre, Aurélien Garivier
similarity 0.55
Abstract

We study the possibility of generalizing maximum-entropy reconstruction, which approximately recovers a probability distribution from finitely many (generalized) moments by minimizing the Kullback--Leibler (KL) divergence to a reference measure. The reconstruction lies in an exponential family and is also the best KL approximation of the unknown distribution within that family: moment matching and information projection coincide. Replacing KL by a smooth f-divergence, the reconstruction still exists in an associated family, but the best approximation property does not. Specifically, a family is called entropy-adapted if the projection of any distribution matches its moments. We show that, up to equivalence, KL is the only $C^2$ f-divergence that is entropy-adapted, whatever the choice of the generalized moments. We illustrate the consequences of this failure numerically.

0.22