PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation and computation of the geodesic Sinkhorn distance

Hugo Lavenant, Jonas Luckhardt, Bernhard Schmitzer

arXiv:2610.02007v1math.NAcs.NAmath.MGmath.OC

TL;DR

The paper studies how to approximate and compute a geodesic metric derived from the Sinkhorn divergence, whose square root does not satisfy the triangle inequality. It uses a change of variables and projection-based spatial discretization; the finite-space metrics converge to the full metric in the Gromov–Hausdorff sense. Its Gaussian examples lie outside the stated technical assumptions.

  • Problem

    The square root of the Sinkhorn divergence does not satisfy the triangle inequality, motivating a geodesic metric built from it.

    Source: §1.1 · p. 4

  • Method

    A change of variables embeds probability measures into an RKHS, and a projection onto finite base spaces supports spatial approximation of the metric.

    Source: The Riemannian geometry of Sinkhorn… · p. 5, §3 · p. 13, §3.2 · p. 15

  • Results

    The finite-space metric spaces converge to the full space in the Gromov–Hausdorff sense, with the projection used in the construction.

    Source: §3 · p. 13, §3.2 · p. 15

  • Takeaways & Limitations

    Numerical examples provide evidence that one-dimensional normal distributions might be geodesically convex for the Sinkhorn distance.

    Source: §6.3 · p. 42

    Normal distributions fall outside the technical assumptions of the article and the cited prior work.

    Source: §6.3 · p. 42

Abstract

from arXiv · show

In [H. Lavenant, J. Luckhardt, G. Mordant, B. Schmitzer, L. Tamanini, The Riemannian geometry of Sinkhorn divergences. Ann. Inst. H. Poincar\'e Anal. Non Lin\'eaire 43 (2026)] we introduced a Riemannian metric $\mathsf{d}_S$ on the space of probability distributions obtained from entropic optimal transport, specifically from the Sinkhorn divergence $S_\varepsilon$. In the present work we discuss how to approximate and compute $\mathsf{d}_S$. Spatially, we prove Gromov--Hausdorff convergence of the metric and convergence of geodesics for increasingly fine Eulerian discretization of the base space. Temporally, we show $\Gamma$-convergence of the chain discretization $N \sum_{k=0}^{N-1} S_\varepsilon(\mu_k, \mu_{k+1})$ to the energy functional defining $\mathsf{d}_S$. We deduce and implement numerical schemes to compute approximations of $\mathsf{d}_S$.

1 Introduction

The introduction motivates a geodesic metric derived from the Sinkhorn divergence and develops the paper’s spatial and temporal approximations. It outlines convergence results, local estimates, and numerical schemes for approximating the metric and its geodesics.

1.1 Context: Sinkhorn divergence and its geometry

  • Entropic regularization smooths the computationally challenging optimal-transport problem, while debiasing addresses the fact that the regularized cost is not a metric.The Sinkhorn divergence is obtained by a simple debiasing of entropic optimal transport.Source: §1.1 · pp. 3–4

The Riemannian geometry of Sinkhorn divergences.

  • The Sinkhorn divergence is a useful loss but its square root fails the triangle inequality, motivating a metric tensor from its Hessian and a path-action distance dS.The metric is defined by minimizing the action over admissible paths; the paper studies it for compact base spaces.Source: §1.1 · p. 4, The Riemannian geometry of Sinkhorn… · p. 4

1.2 Outline and contributions

  • As the base-space discretization is refined, the finite-space metrics converge to dS in the Gromov–Hausdorff sense, and their geodesics converge to geodesics of dS.The projection R_M is used to construct the spatial approximation.Source: §1.2 · p. 5
  • For the Sinkhorn divergence, Sε(µ,ν) is bounded below by dS(µ,ν)^2; its reverse bound has a remainder in the stronger one-Wasserstein norm, while at small scales vertical and arc interpolations have approximately minimal energy.Source: §1.2 · p. 6
  • The time-discrete Sinkhorn-chain functional Γ-converges to the path energy, and interpolations of minimizing chains converge to geodesics.The result provides a theoretical foundation for numerical approximation of dS and its geodesics.Source: §1.2 · p. 6
  • Eulerian and Lagrangian chain discretizations capture splitting effects, but the chain energy can stabilize well before the paths visually approach their limit.The proposed Eulerian scheme alternates optimization over even and odd links and refines the chain after convergence.Source: §1.2 · p. 7

2 Preliminaries

The preliminaries set the compact-space and kernel assumptions, recall the entropic dual formulation, and lay out the RKHS-based framework for the Sinkhorn metric and its geodesics.

2.1 Setting and notation.

  • The setting fixes ε > 0 on a compact metrizable space X with a symmetric continuous cost inducing a positive definite universal kernel; the ε → 0 limit is outside the paper’s scope.Source: §2.1 · p. 7

2.2 The entropic dual problem

  • The entropic dual problem has Schrödinger potentials, and these determine the unique optimal transport plan in the primal formulation.Source: §2.2 · p. 8

2.3 The Riemannian geometry of Sinkhorn divergences

  • The RKHS change of variables represents probability measures in a common Hilbert space, where the metric tensor is comparable to the flat Hilbert-space tensor.Source: §2.3 · p. 11
  • Admissible paths are those whose transformed curves lie in H1((0, 1); Hc), and minimizing the associated energy defines dS, a metric with minimizers called geodesics.Source: §2.3 · p. 12

3 Gromov–Hausdorff convergence of spatial discretization

The paper projects probability measures onto increasingly fine finite supports and proves convergence of the resulting geodesic metric spaces and their geodesics. The projection also supports the energy approximation arguments used in this section.

3.2 Projection to a finite base space

  • The map RM is built by projecting the transformed measure in Hc onto the finite-support cone and normalizing; it converges in norm and preserves energy in the limit.Source: §3 · p. 13, §3.2 · pp. 15–17

3 Gromov–Hausdorff convergence of spatial discretization

  • As M grows, (P(XM), dS,M) converges to (P(X), dS) in the Gromov–Hausdorff sense, and finite-space geodesics converge along subsequences to geodesics on P(X).Source: §3 · p. 14

3.1 Regularity of the energy functional

  • The energy E is lower semicontinuous in the weak H1 topology and continuous in the norm H1 topology.Source: §3.1 · p. 14

3.3 Proof of Gromov–Hausdorff convergence

  • The projected distances converge uniformly to dS after pointwise convergence is upgraded using equicontinuity on the compact measure space.Source: §3.3 · p. 18

4 Local expansion of the Sinkhorn divergence and its geodesic distance

This section develops local estimates and expansions relating the Sinkhorn divergence to the geodesic Sinkhorn distance, including continuity of the metric tensors involved. It examines how arc, vertical, and Wasserstein interpolations relate to geodesics, with examples showing that approximate geodesics need not resemble the exact one.

4 Local expansion of the Sinkhorn divergence and its geodesic distance

  • Theorem 4.2 gives a uniform local expansion of the geodesic Sinkhorn distance, including estimates for interpolating paths near a reference measure and as two measures approach each other.The theorem also compares the distance along the vertical interpolation with the distance between its endpoints.Source: §4 · p. 19
  • Theorem 4.3 provides uniform estimates for the Sinkhorn divergence, including an upper bound by the one-Wasserstein distance built from d_c on compact metrizable spaces.Unlike the previously established upper bound cited in [25, Rem. 5.11], this result does not require differentiability of the cost function.Source: §4 · p. 20

4.1 Continuity of the metric tensor

  • The metric-tensor operators vary continuously in operator norm, and the Schrödinger potentials can be chosen continuously in the Lipschitz function space.The section establishes continuity of both the off-diagonal operators G_{µ,ν} and the operator defining the metric tensor at µ.Source: §4.1 · pp. 22–23

4.2 Proof of the local expansion for the distance

  • The proof’s displayed expression equals ν−µ+o(dS(µ,ν)); a bound is completed for all t∈[0,1], with convergence as ∥β1−β0∥Hc→0 uniform over t.Two rewritings of the Sinkhorn divergence give bounds (4.5), (4.7), and (4.6); off-diagonal operators naturally appear when rewriting the divergence.Source: §4.2 · pp. 25–26, §4.3 · p. 26

4.3 Proof of the local expansion for the Sinkhorn divergence

  • The proof of estimate (4.5) obtains the squared Sinkhorn geodesic distance up to o(Wc(µ, ν)^2) in the local expansion.The authors note that obtaining a remainder o(dS(µ, ν)^2) would require estimates in Hc involving off-diagonal operators they do not know how to define in the needed Banach spaces.Source: §4.3 · pp. 27–28

4.4 Approximate geodesics in our metric

  • Arc and vertical interpolations generate approximate geodesics, but this does not imply that they resemble the exact geodesic.For translations under squared-distance cost, the exact geodesic between Dirac measures travels along a straight line, whereas these interpolations remain supported on the endpoint supports; nevertheless, they are approximately geodesic as r → 0.Source: §4.4 · pp. 30–31
  • In the splitting-Dirac example, arc and vertical interpolations have almost identical energies, while the Wasserstein-2 geodesic has significantly higher energy and is not approximate as r → 0.The interpolations match the Sinkhorn divergence and optimal splitting curve asymptotically; Figure 1 illustrates the energy comparison.Source: §4.4 · pp. 31–32, Figure 1 · p. 31
  • For squared-distance cost on Rd, constant-speed translations are exact dS-geodesics with dS(µ0, µ1) = ∥v∥ [25, Thm. 5.16].In particular, the geodesic between δ0 and δr is the straight-line point-mass path, which is also the Wasserstein-2 geodesic.Source: §4.4 · p. 31
  • The splitting-Dirac example shows that Wasserstein geodesics need not be approximate geodesics for the Sinkhorn metric, and no bound of the form Wc ≲ dS can be expected.For a Dirac measure splitting into two symmetric atoms, the Wasserstein geodesic is not approximately constant-speed in the Sinkhorn metric.Source: §4.4 · pp. 31–32

5 Gamma convergence of Sinkhorn chain

The section establishes Γ-convergence of Sinkhorn-chain energies to the path energy, then derives convergence of minimum chain costs and geodesics. It also states a joint spatial and temporal limit.

5 Gamma convergence of Sinkhorn chain

  • The chain energies Γ-converge to the path energy in the uniform dS topology, with bounded-energy compactness and recovery sequences.Source: §5 · p. 33
  • The minimum N-step Sε-chain cost converges to dS(µ, ν)^2, and subsequential limits of minimizing interpolants are geodesics.Source: §5 · p. 34
  • A continuous-time metric-tensor alternative is expected to Γ-converge, but may be less tractable numerically because its tensors depend on the footpoint.Source: §5 · p. 34
  • Joint spatial and temporal refinement needs no constraint on the ratio of step sizes; minimum values converge to dS and interpolated minimizers converge to geodesics.Source: §5 · p. 35

5.1 Gamma-liminf

  • Bounded chain energies yield relatively compact piecewise arc interpolants, whose limits satisfy the path-energy lower bound.Source: §5.1 · p. 35

5.2 Gamma-limsup

  • Recovery sequences project paths onto finite supports and use endpoint interpolation to restore prescribed endpoints while retaining energy convergence.Source: §5.2 · pp. 36–37

6 Numerical computation of dS

The paper develops Eulerian and Lagrangian discretizations and optimization schemes for Sinkhorn chains, illustrating their behavior on several measure families and optimization settings.

6 Numerical computation of dS

  • Eulerian discretization fixes support points and optimizes weights, while Lagrangian discretization fixes masses and optimizes positions, trading convexity for flexibility.With an equal number of points, Lagrangian discretization can in principle approximate a larger set of measures, while its optimization is harder to analyze.Source: §6 · p. 38

6.1 Eulerian discretization: method

  • Eulerian chain energy is separately convex in each intermediate measure, enabling alternating convex minimization over odd and even links.The proposed refinement scheme starts with a two-step chain, inserts intermediate measures, then alternates optimization of new and old links.Source: §6.1 · p. 39

6.2 Lagrangian discretization: method

  • Lagrangian optimization encodes measures as fixed-mass particles and minimizes the full chain by gradient descent, losing the partial convexity used by the Eulerian scheme.Multiple lighter particles can represent each source and target particle to capture mass splitting; the gradient approach requires at least a C1 cost.Source: §6.2 · pp. 40–41

6.3 Examples

  • Computed Gaussian variance evolution agrees with the formal prediction, but Gaussian geodesic convexity remains numerical evidence rather than an established minimum.Normal distributions fall outside the technical assumptions because of their non-compact support; Gaussian initialization also keeps the chain Gaussian.Source: §6.3 · p. 42
  • On finer Eulerian grids, the chain appears to recover the limiting moving-Dirac curve, although its midpoint is not supported solely at x=1.Source: §6.3 · p. 43
  • Splitting can occur rapidly at first because opposite mass motions are cheap at the Sinkhorn blur scale; motion becomes more gradual beyond distance √ε.The same rapid splitting appears for measures with densities, forming concentrated spikes before relaxation.Source: §6.3 · p. 43

6.4 Comments on the optimization

  • Chain energy can approach its minimum before the path visually stabilizes, and resolving spike structure may require many iterations because small energy changes accompany it.The Sinkhorn distance barely distinguishes a measure from a slightly blurred version, and even 25,000 iterations left a circle rotated by half a discretization angle in the reported example.Source: §6.4 · pp. 44–45
  • Velocity parametrization quickly recovers the known constant-speed translation and yielded equal or better results than position encoding in the reported experiments.It also lets gradient information pass through the entire chain at once.Source: §6.4 · p. 46
Loading 2610.02007v1…