Linear convergence of Sinkhorn's algorithm for generalized static Schrödinger bridge
Authors: Rahul Choudhary
Hanbaek Lyu
Venue: ICML 2025 poster (2025)
Keywords: Schrödinger bridges
Sinkhorn algorithm
entropic optimal transport
linear convergence
Primary area: optimization->convex

Abstract: The classical static Schrödinger Bridge (SSB) problem, which seeks the most likely stochastic evolution between two marginal probability measures, has been studied extensively in the optimal transport and statistical physics communities, and more recently in machine learning communities in the surge of generative models. The standard approach to solve SSB is to first identify its Kantorovich dual and use Sinkhorn's algorithm to find the optimal potential functions. While the original SSB is only a strictly convex minimization problem, this approach is known to warrant linear convergence under mild assumptions. In this work, we consider a generalized SSB allowing any strictly increasing divergence functional, far generalizing the entropy functional $x\log x$ in the standard SSB. This problem naturally arises in a wide range of seemingly unrelated problems in entropic optimal transport, random graphs/matrices, and combinatorics. We establish Kantorovich duality and linear convergence of Sinkhorn's algorithm for the generalized SSB problem under mild conditions. Our results provide a new rigorous foundation for understanding Sinkhorn-type iterative methods in the context of large-scale generalized Schrödinger bridges.

Linear Convergence of Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Rahul Choudhary' Hanback Lyu
Abstract
work is to solve the following matrix optimization problem:
The classical static Schrödinger Bridge (SSB) problem, which seeks the most likely stochastic evolution between two marginal probability mea- sures, has been studied extensively in the optimal transport and statistical physics communities, and more recently in machine learning communities in the surge of generative models. The standard ap- proach to solve SSB is to first identify its Kan- torovich dual and use Sinkhorn's 's algorithm to find the optimal potential functions. While the orig- inal SSB is only strictly convex minimization problem, this approach is known warrant lin- ear convergence under mild assumptions. In this work, we consider generalized SSB allowing any strictly increasing divergence functional, far generalizing the entropy functional xlog.x x in the standard SSB. This problem naturally arises in a wide range of seemingly unrelated problems in en- tropic optimal transport, random graphs/matrices, and combinatorics. We establish Kantorovich du- ality and linear convergence of Sinkhorn's 's algo- rithm for the generalized SSB problem under mild conditions. Our results provide a new rigorous foundation for understanding Sinkhorn-type iter- ative methods in the context of large-scale gener- alized Schrödinger bridges.
z : argmin
g(X)= T-=Er f(x)))W))
(1)
X-(xylERmsn
"
m
subject to
Σ
Xi Wi) r()), Σ x W wij=c(j)Vi.
We call the optimal matrix z above the (generalized) static Schrödinger bridge (SSB) for margin (r,c) w.r.t. weight W and divergence f- The entries 2 are taken to be arbitrary where Wij = O. We call the set Fw(r, c) of all real m n matrices X= (xi)) satisfying the margin constraint in (1) the (W-weighted) transportation polytope with margin (r,c). The matrix optimization problem above enjoys a rich connection (discrete instances of) wide range of important problems.
First, our SSB problem (1) is f problem formulated terms the relative density (Carlier et al., 2017; Lorenz & Mahler, 2022: Terjék & González- Sánchez, 2022). Suppose and e give probability mass functions [m] := (l...., m) and [n] and W gives joint probability mass function on the lattice [m] [n]. Then f- divergence SSB between the margins and e w.r.t. W is the probability measure H solving the following constrained minimization problem
the f-divergence SSB
D
de dw
min Hellir.
dw
(2)
1. Introduction
where the minimum is for all probability measures H [m] [n] that is absolutely continuous w.r.t. W and has marginal density (r, Rewriting the above in terms of the relative density X deZ
Fix an m real nonnegative matrix W. A pair of vectors (r, E R x Rd is called a margin if we have the same total sum: 1) = (c, 1). Fix twiee-differentiable strictly con- vex function f R - R u !. Our central interest in this
E m gives exactly our SSB problem (1). Specializing to the KL-divergence by tak- ing fxx xlogxx it further becomes the classical SSB be- tween marginal densities r and e w.r.t. the reference mea- w (see, e.g., (Fortet, 1940; Pavon et al., 2021)).
dF
University of Wisconsin- Madison, Madison, Wisconsin. Correspondence to: Rahul Choudhary <rahul.choudhary @ @isc.eddu> Hanbaek Lyu <hlyu@ mathu@matt.wiie www.........uu......
'Equal contribution
Second, if we take the KL-divergence and W in the follow- ing form
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Wij x e Si ( c())
(3)
By Jensen's inequality, the domain of f. dom(f) [[) < oo) is an interval. We understand differentiability of
f for restricted on the interior of its domain.

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
for some cost matrix C = (Gry) " and regularization parameter O, then (1) becomes the entropic optimal transport (EOT) problem with marginal densities (r, c) and cost matrix C (Villani, 2021).
respectively. Since the SSB z is assumed to satisfy the margin constraint z E Fw((,,,), c), necessarily the potentials need to solve the (generalized) Schrödinger systemmm
y Wij (()) r(i) visism TH Wiy.
Third, if we take the KL--divergence and uniform marginals are r= m mm m and c = n 1,, then (I) becomes the clas- sical matrix sealing problem, which is find the doubly stochastic matrix that minimizes the KL-divergence from W (Sinkhorn, 1964). Indeed, such a doubly stochastic trix is given by z o WW where Z is the SSB in (1) for the uniform margin and @ denotes the entrywise product.
(5)
LA s
Note that since f twice-differentiable and strictly convex, f 0 f" is strictly increasing, it admits strictly increasing inverse (f')
In order to solve (5), we propose the following Sinkhorn- type iterative algorithm where for given potentials (az-1. at iteration k. one first finds the new column potential ag that satisfies the Schrödinger system for the column sums using the current row potential a;-1, and then updates the row potential using the updated column potential B% similarly:
Fourth, (1) is also connected to the rypical table problem in the combinatorics literature (Barvinok, 2010), which is central to the enumeration of integer-valued nonnegative matrices with prescribed row sum column sum (con- tingency tables with margin (x, For this, we may take w I m I and f(x) = (x logg(( + 1) xlogx, which is the negative of the entropy of the geometric distribu- tion with mean x. The solution of the corresponding in- stance of (1) is called the typical table for margin (x, c) and it is known that uniformly random contingency table with margin (r,c) c) is sharply concentrated around the typical ta- ble (Barvinok, 2010; Lyu & Mukherjee, 2024).
vI n. Bx( unique & c(j) c(j)= (f') 1 (a< 11) + Bj]:i. Visism, ax( - unique a R s.t.
GSA:
(6)
r(i) "リ (a+))~~(++++)+;;;;
Since (f')-1 is strictly increasing, the solution to (6) for each iteration & is unique if it exists.
Fifth, if we take = == d, a sequence of degrees of an n-node simple graph and f(x) = xlogx* + (1 - xx log(1 - xx (negative entropy of the Bernoulli distribution with mean x) with W = , then the adjacency matrix of a uniformly random n-node graph with degree sequence d is concen- trated to the solution of (1) in the cut metric (Chatterjee et al., 2011).
We call the above the generalized Sinkhorn algorithm (GSA), Indeed, notice that when f(x) = xlogxx so that our main problem (1) reduces to the classical static Schrödinger bridge and entropic optimal transport, f'(x) = + log.x so (f)) exp(0 1). In this case, (6) reduces to the cel- ebrated Sinkhorn's 's algorithm (SA) (a.k.a. iterative pro- portional fitting procedure) used to solve various classical problems such as matrix scaling, static Schrödinger bridge, and entropic optimal transport (Franklin & Lorenz, 1989; Cuturi, 2013):
Lastly, (1) is also connected to a problem in random matrix theory. Namely, the m x n random matrix with i.i.d. entry with entrywise distribution μ conditioned to have row sum r and column sum e is known to be concentrated around the solution of (1) (a.ka. generalized typical table) in cut- norm, in which we take W I, J and f(x) is the KL- divergence from j to the exponential tilting of to have mean x (Lyu& & Mukherjee, 2024).
v1 s is n, Bi(()) - log E W.jesplat-10) SA:
e(f)
V1 vis m. a1) - log yH, Wiy e
r0
The overarching goal in this work is to propose a Sinkhorn- style algorithm that solves a 'Kantorovich dual' of (I). For a gentle introduction, consider writing down the multivari- ate Lagrange multiplier equations for (1). There are m n linear equations (in fact one of them is redundant due to the consistency condition (r, I) = (c, 1)) for the (weighted) row sum (m) and column sum (n) constraints. Since the objec- tive of (1) is strictly convex, existence of a solution implies that the solution - = (zij) is uniquely determined by
Convergence of SA (7) has been studied extensively in the literature. Franklin and Lorenz showed that the conver- gence rate is exponential (linear in the log scale) in the space of margins endowed with Hilbert's projective met- ric (Franklin & Lorenz, 1989). A similar result was ob- tained for the continuous setting by Chen and Pavon (Chen et al., 2016a). Rüschendorf (Ruschendorf, 1995) estab- lished asymptotic convergence of Sinkhorn algorithm in the continuous case from the perspective of information pro- jection. Marino and Gerolin extended a similar result to the multi marginla case (Marino & Gerolin, 2020). Carlier established linear convergence of marginl Sinkhorn algorithm in the Euclidean metric (Carlier, 2022).
I' f( (i + B()
whenever Wij 0, (4)
where (a. B) E RM x "h are vectors of Lagrange multipliers. We call a and B the row potential and column potential,
2

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
All of the convergence results mentioned above concern the KL divergence (f(x) = xllogx) with there being known convergence results for other divergence measures and weight matrices. Below in Theorem 2.6, we establish that the generalized Sinkhorn algorithm (6) for arbitrary di- vergence and weight matrix converges at a linear rate in the sense that the objective value gap decays exponentially fast.
In recent years, various approaches have been proposed to leverage Schrödinger bridges for generative modeling and density estimation. For instance, it has been shown that SB can be viewed as a stochastic control or diffusion- based process that interpolates between given marginals, often leading to dynamic formulations in the continuous- time setting (Chen et al., 201 More recently, sev- eral works have explored proaches, bringing together ideas from score-based diffu- sion models and the classical Schrödinger bridge problem to design generative algorithms that are both statistically efficient and robust to numerical issues arising in unregu- larized cost minimization (Wang et al., 2021; De Bortoli et al., 2021; Jiao et al., 2024). We refer to these works for detailed expositions on how iterative Schrödinger bridge solvers can be coupled with score-matching ideas in gen- erative modeling.
Satttiiinn-crrdinnnee bridge ap-
1.1. Contributions
We show that any potential functions (a, (a. charac- terizing the generalized static Schrödinger bridge z solve dual problem, which is the Kantorovich dual to (1). See Theorem 2.4 for details.
Under mild conditions on the divergence f. weight W, and margin (r, c), we establish that the generalized Sinkhorn algorithm (6) decreases the dual objective at a linear rate. This rate may or may not be dimension independent depending on how fast the margins grow with the dimension. Theorem 2.6 covers the linear convergence result in detail.
Beyond direct use in generative methods, Schrödinger bridges also appear in other machine learning tasks in- volving distribution alignment or adaptation. For exam- ple, SBs can be used to perform domain adaptation where one aims to transport empirical distributions across dif- ferent domains (Benamou al., 2015) or to regularize large-scale graph alignment problems. The major appeal in all of these settings lies in the entropic regularization that smooths the transport plan, often translating into more sta- ble optimization problems and efficient numerical methods.
In order to arrive at dimension independent linear con- vergence, we show sufficient conditions for the bound- edness of the iterates of our generalized Sinkhorn algo- rithm. These sufficient conditions ensure that the tame- ness parameter (see Def. 2.5) for the given problem margins are dimension independent. Consequently, di- mension independent linear convergence of our gen- eralized Sinkhorn algorithm ensues, making our algo- rithm particularly attractive for high dimensional prob- lems. This result assumes uniformly bounded cost function. For more details, see Theorems 2.7 and 2.8.
1.2.2. SINKHORRN ALGORITIM FOR STATIC SCHRÓDINGER BRIDGE
At the heart of many Schrödinger bridge (and entropic op- timal transport) algorithms is the Sinkhorn algorithm, also called the iterative proportional fitting procedure (IPFP). In the classical setting where the problem is the conver- gence to a doubly stochastic limit of sequence of ma- trices obtained from a non-negative matrix- the Sinkhorn algorithm dates back to the work of Sinkhorn and Knopp (Sinkhorn & Knopp. 1967), and has been extensively ana- lyzed in the matrix analysis and statistics literature (Dem- ing & Stephan, 1940; Franklin & Lorenz, 1989). Franklin and Lorenz (Franklin & Lorenz, 1989) established linear convergence (i.e., exponential decay of the error) in the Hilbert projective metric, and Rüschendorf (Ruschendorf, 1995) extended the analysis to continuous measures via an information projection viewpoint. Subsequent works by Chen and Pavon (Chen et al., 2016a) further analyzed the continuous entropic Schrödinger bridge problem with similar iterative strategy, Marino and Gerolin (Marino & Gerolin, 2020) and Carlier (Carlier, 2022) extended conver- gence results to establishing linear rates under reasonable conditions on the reference measures.
Recently, Lyu and Mukherjee (Lyu & Mukherjee, 2024) established linear convergence of the generalized Sinkhorn algorithm (6) for the generalized typical table problem in random matrix theory context. This is a special case of (1) where W 1m 1 and f(x is the KL-divergence from μ to the exponential tilting of µ to have mean x (see Appendix A for details). Our analysis in this work is inspired by their approach and we generalize it to the abstract setting (1).
1.2. Related works
1. SCHRÓDINGER BRIDGE IN MACHINE LEARNING
The Schrödinger Bridge (SB) problem has gained increas- ing attention in the machine learning community due to its connections with probabilistic modeling and optimal trans- port. Starting from the seminal work of Fortet (Fortet, 1940) and more recent expositions by Léonard (Léonard, 2013), the SB problem has been reinterpreted as an entropic variant of optimal transport, often called entropic optimal transport, and as such it has found applications in large- scale generative modeling.
Sinkhorn algorithms, again
3

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
More recently, the Sinkhorn algorithm has become a main- stay in computational optimal transport, thanks largely to the seminal paper by Cuturi (Cuturi, 2013) that popular- ized the entropic regularization perspective. This line of work has led to an extensive suite of efficient implemen- tations and theoretical studies on the stability, complexity, and generalization of Sinkhorn-based methods in high di- mensions (Peyré et al.. 2019). Despite these advancements, most classical convergence guarantees have focused KL divergence (or equivalently f(x) = xlogx). In practice, though, there are many settings where one may wish to re- place the standard KL divergence by other strictly convex divergences- - leading to the generalized static Schrödinger bridge problem considered in this work.
2.1. Generalized Kantorovich duality
Notice that since an SSB z in (I), if exists, is member of (w, n (A, necessary condition for the existence of SSB. In the fol- lowing lemma, we show that this condition is also sufficient for the existence of SSB, in which case it is also unique.
mxx" m)x" Hence this set being non-empty is
Lemma 2.3 (Existence and uniqueness of generalized SSB), Assume 2.1 holds. For an m x n margin (r, c) and weight matrix W. the SSB z in (I) exists if and only if the set Tw(r, c) n (A, BymoR is non-empry. Furthermore, the SSB is unique if it exists.
Inspired by the Kantorovich dual for the entropic optimal transport (Nutz & Wiesel, 2022) and also the maximum likelihood formulation of the typical table problem in (Lyu & Mukherjee, 2024), we seek to construct a dual problem for (1) that is directly solved by the potentials solving the Schrödinger system (5). Let wr(y) , f(x)) de- note the convex conjugate of f. Since f is differentiable and strictly convex, the supremum for vr(y) is attained at y fx)). Denoting o= f', this gives
Overall, by bridging the gap between classical matrix- scaling arguments and modern-day generative modeling, our work provides a conceptual and theoretical foundation for generalized Sinkhorn algorithms across a broad range of entropic transports and divergences.
2. Statements of results
f(x) = xx((x)xx (x((((x)).
(9)
Since the divergence f: RR(oo) is convex, By Jensen's
inequality, the domain of f. dom(f) := (x E [f] < oot is an interval. We will write its interior as (A, B) for some extended reals A, B. Note that f = Inte)))r(dom(()).
Also, using f" 0, we deduce v' = by differenti- ating both sides of the above relation.
>
In (Lyu & Mukherjee, 2024), it was found that if f(x) Dri. (Haco lIμ), the KL--divergence from a probability mea- sure μ and its exponential tilt (oox) with mean x, the function & maps tilt parameters to the mean after tilting, w' = Φ maps the target mean the corresponding tilt parameters, and the convex conjugate y of f is the log- Laplace transform of μ.
Assumption 2.1. f is tiice-diiferentiabbl on (A,B) with f 0 and takes co R [A, Furthermore, lim, fx) -oo if |AI < oo; and lim,/ co if [B] <o..
Without loss of generality we can assume every row sum of W is positive since if, for instance, the first row of W entirely zero, then we may as well omit the first row of n entirely from our problem setting (1) and consider only the (m- 1) n submatrix. Similarly, we may assume that every column sum of W is also positive. Furthermore, we will impose that the weight matrix W satisfies the following structural assumption.
Now consider the following (not strictly) concave maxi- mization problem:
sup g gg (ar, :r:)):;(()))) + (c, -) -W B))). (10) a.B
where a e f denotes the m x n matrix with entries a(i) + B(j) and the supremum in (10) is over all (a, B) E RM R" such that v(a f) is well-defined and the inner product between matrices is the sum of the entrywise products, as usual. We will call the above the Kantorovich dual for (1) due to the following result. Note that its first-order opti- mality condition is exactly the Schrödinger system (5).
Assumption 2.2. W Couv for some positive mx ma- trix C and positive vectors uE R" VE R", where denotes the Hadamard product.
Comparing with the standard choice (3) in entropic opti- mal tranport, C plays the role of the (exponentiated) cost matrix and uv is the prior product distribution, which is often taken as re" from the target margin (r, c). In our anal- ysis, the following "condition number' of C will play important role:
Theorem 2.4 (Generalized Kantorovich duality). Assume 2.1 holds. Fix an m x n margin (I,c) and weight matrix W.
i Suppose the SSB 2 for margin (r,c) w.t.. W exists. Then there is a potential (a. for (r, c) such that
K == Cmax//min
(8)
Zi = w/ (ix(i) + B(j)
visis m, 1 1s jsn. (11)
where Cmax and Cmin are maximum and minimum entries of C respectively.
Also, (ac, B) is a solution to the dual problem (10).
4

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
(ii) Suppose (a, BB) is a solution the dual problem (10). Then the SSB = for margin (r,c) uniquely exists and
Theorem 2.6 (Linear convergence of generalized Sinkhorn
iterates). Assume 2.1 and 2.2 hold. Let (ak. Bg). k 0 de- note the iterates produced by the Sinkhorn algorithm (6) for some m x margin (r, c) such that (w(r,c)n(A) B) ") is non-empty. Choose 8 > O small enough so that (r is 8-tame. Fix a potential (a', ,B') and denote DR == g= .B')- gt<(a,, (resp., a
z w/ p))
(12)
Furthermore, the SSB (1) and the dual (10) problems are in strong duality:
For each E > O, let (e( 0, (E)2) denote the infimum (resp., supremum) vf (b(.Ae))(BBB Let be as in (8).
inf g(X) sup (r.e
gh (a, B).
(13)
a
Note that the potentials for margin (r (defined below (4)) are not unique. In fact, if (a, B) is a potential, then (a+ + alm. B - aln) is a potential for any scalar a R. But it can be made unique once further linear constraint, say (at, mm) = 0, is imposed. We call such potential where the coordinates of the row potential a sum to zero standard potential for (r,c).
(Asymptotic linear convergence) There exists an inte- ger Ko 0 that may depend on m, following holds with = 812:
f. m,n, f.W such that the
11(x @ xB*) - -axx @ BB)l s Ax
(16)
2
s 1 1 0_())) k- ( A vk2 (17)
2.2. Convergence of generalized Sinkhorn algorithm
(ii (Non-asymptotic linear convergence) Let Do span(ao x²)) max(as a²)) min(an a ) If
As we noted before, the Kantorovich dual (10) is con- cave maximization problem and the objective function is not strictly concave. While linear convergence of standard optimization algorithms for such problems is not usually expected, our main result (Thm. 2.6) below establishes linear convergence where the rate of convergence depends sensitively on the "quality of the optimizer'. Namely, will be erucial to assess how far the entries of the SSB z are bounded away from the boundary values A and B, or equiv- alently, how far the entries of the 'direct-sum potential' a @ B are bounded away from the boundary values (f(A) and (BB). We make this precise via the following notion of '6 -tammness'' of margin cr.
+ a' e B s (lBB) - Do (18)
for some E > 0, then (16) holds with ko = 1.
Part (i) states that whenever SSB z exists so that the prob- lem is well-defined, the generalized Sinkhorn iterates (6) converges linearly asymptotically, meaning that the linear convergence kicks in after some unknown number ko of it- erations. The linear rate of convergence is degraded if the condition number for the cost matrix C is large. Part (ii) states in fact the linear convergence holds from the very first iteration if the -all around a e B with radius Dn takes entries from the domain of y. (BB))), This holds if ao is sufficiently close to a up to translation.
Definition 2.5 (Tame margins). Fix 6 > O. We call a margin (r,c) 8-tame if the SSB w.r.t. the weight matrix W, say z exists and its entries satisfy
A sufficient condition for > to satisfy (18) with zero ini- tialization (by shifting the potentials appropriately so that || 1low s (cp(Bs) - ((AA))/2) is
Ag: = max A - 1 s min B 88-8, () =: (14)
or, equivalently (due to Theorem 2.4),
((AA) s 24p(As) ((BB), 24((8)) - ((As)= s ((B)). (19)
((As) = a + p (BB)).
(15)
One can always find small > satisfying the above pro- vided ((A)) < 24b(As) - (bBs) and 2cp(Bs) (b(Bs)-((AA) (BB). The latter conditions always hold if (cb(A), ((B)) R. which is the case for entropic optimal transport.
We remark that since T takes entries from (A, B), any margin (r for which SSB zro w.r.t. W exists, it is 8- tame for some 8 > that may depend on (r, c), and hence on the dimensions m and n.
2.3. A priori bound on potentials
Now we state the main result in this work. We establish that the generalized Sinkhorn algorithm (6) converges at a linear rate in the sense that the objective value gap as well as the L2- ee-esmimation error of the direct-sum potentials decay exponentially fast. For the statement below, define ||All := 2.,, A7, v())vi) for mx x matrix A.
Our last concern is to obtain fimeension-independenn lin- ear convergence rate of the generalized Sinkhorn iterates. This is crucial in computing generalized SSBs for large- scale problems using the proposed Sinkhon algorithm. The contraction rate in 2.6 is determined by (E()), which are essentially determined by the tameness parameter for the
5

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
target margin (r, Hence, we only need to show that such 8 is dimension-inddeeendntt.
improved since the specialized result in (Lyu & Mukher- jee, 2024) is already known be sharp. This means that there is sequence of margins with growing dimension sat- isfying the strict reverse inequality in (21) with vanishing tameness parameter. Third, the set of possible (s, t) satis- rying the condition (21) shrinks as the condition number k increases. Intuitively, it should be harder to guarantee dimension-independee tameness for wildly varying cost matrix C. See Fig. 1.
As it turns out, one can easily create sequence of margins for which the tameness parameter vanishes at an arbitrary speed as the dimensions m, n - co. In fact, determining whether a given margin (r, c) is 8-tame for some dimension- independent ō is an important problem in entropic optimal transport (Marino & Gerolin. 2020; Carlier, 2022), ran- dom graphs with given degree sequences (Chatterjee et al., 2011; Barvinok & Hartigan, 2013; Dhara & Sen, 2022), enumeration of graphs with given degree sequences (Barvi- nok & Hartigan, 2013) and contingency tables (Barvinok & Hartigan, 2012; Lyu & Pak, 2022: Dittmer et al., 2020), and random matrices with given margins (Lyu & Mukher- jee, 2024).
(x*1s +xl? = 4x" sssstsl
10
1.0
0.-
0.5
04
0.4
In what follows, we will provide some sufficient conditions for domension-inddpendeen tameness. We will use easily- checked conditions on the margin of the following form: there exists some positive s< t such that the target margin (I, c) satisfies the linear bounds
0.
0.2
1
K
0.0
0.2
5.4
0.6
5.5
1.2
0.5
0.2
0.6
0.8
0.8
1.0
Figure Red regions depict the solution set of the tameness con- dition (21) in Thm. 2.7 for B = 1 and k 1,2.
r(i) s W st and
c(j) W.;
$5
st for all i.j. (20)
Lastly, we consider the case when f has unbounded do- main. For instance, if f(x) = xloggx as in Entropic Opti- mal Transport (EOT), then (A, B) = (0) and (r(0)= el so (f' (BB)) = R. The following theorem gives sufficient condition for tameness for similar but more general cases.
We then seek for conditions on s and f such that (r,c) is 8-tame for some 6 that depends only on the divergence f and s, It is hard to seek simple condition that covers all possible range of problems entailed in the generalized SSB problem as the problem of tameness is known to depend very sensitively on the nature of the problem in the litera- ture above. We will provide two such results depending on whether f assumes bounded or unbounded domain.
Theorem 2.8 (Bound on potentials when f has un- bounded domain). Suppose (A, B) (0) and (0) s ((()). Let W and k be as before. Fix constants s, E (0) with s S t. Let (r,c) be a m x n margin such that [w(r, c), B) mxn is nonempty and satisfies (20). Let (a, B) be a potential for (r)c) w.r.f. W. Denote
We first consider the case when f has bounded do- main. Without loss of generality, we can then assume Interior(dom(())= (0, B) for some positive finite B.
x2 ((---11- ((--)())))
Theorem 2.7 (Bound on potentials when f has bounded domain). Suppose A = 0 and e oo) and let W and k be as above. Fix constants s <<t such that
c(E;s, :)
<5((11111 ())))
(22)
ES
Then entrywise.
kI < V2Bs/K - s/K or (x s+x0)2 < 's. (21)
((s) inf c(E:s, f+ Bs ((1)+ + inf c(E; f). ec(0.1)
ec(0.1)
(23)
Then there exists constant C= C(f,s,t) with the fol- lowing property: If any margin (r,c) satisfies (20) and Fw( (A,B)=* is nonempty, then there exists a po- tential (a. f) for margin (r,c) w.E.t W such that | C and 181 S C. In particular, (r, c) is 8 8-tame for some 8 > 0 depending only on f,x, s, and t.
In particular, (r, c) is 8-tame for some 0 > 0 depending only on f,x,s, s, and t the left-hand side of (23) is strictly larger than (A)
Consider again EOT, where (g(A), = R and (00)= 1+ logg. In this case, the infimum in (23) is attained at
A few remarks are in order. First, the above result gener- alizes a similar result in (Lyu & Mukherjee, 2024) when W = IT and f is the KL-divergence between a com- pactly supported probability measure and its exponential tilting. Second, the result in Theorem 2.7 above cannot be
e' /---( which yields
1 - 2logx + +2logs - 2logs
s a + B 1 +2lgg + +log-- -logs +oogs+22lll//r /1+ VI-s). -).
6

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
In entropic optimal transport, one takes (see (3)),
Proof of Theorem 2.4. First we show (i). By the hypothe- sis, the SSB for margin (r, uniquely exists, which we de- note by Zee Since f = o. we have Vg(Z)= = (db(z;)) Since & is differentiable, grange multiplier method, to conclude the existence of dual variables a' E and f E RR such that x(Zzy) aj D whenever Wij > 0. Hence (a", ..") is potential for (r, Since T e e. c), (a"", ."") satisfies the Schrödinger sys- tem (5), which is exactly the first-order optimality condi- tion for the dual (10). Since the dual problem is concave maximization problem, it implies that (a", (a*,"") is a global maximizer for it. This shows (i).
Cij = exp(-cti,))e)
(24)
where & > now is the entropic regularization parameter.
can apply the multivariate La-
Then
x= (maxx)))) (maxe((,)
- min
exp((Icllo_/e). (25)
So our bound on the potentials above says
a + f O(Iiclla//)) + O(log(t/s))
(26)
The corresponding bound on potentials for EOT in (Marino & Gerolin, 2020) and (Carlier, 2022) depend only on / and there is no dependence on the margin (r, This because such bounds assume specific structure of the divergence (e.g., f(x) xlogx) and uv re" as in (3). Our bound above does not assume uv =rc Further- more, our general bound in (23) works for general diver- gence f.
Now suppose (d, (3) is a solution for the dual problem (10). Then x e T.w((, c) n (A, B) mxn,, so the above yields
(ā. B) g(x =g
sup (aagg"" (a, a.
(29)
Furthermore, by Lemma 2.3, the SSB for margin (r)c) uniquely exists, which we denote by z By part (i), there exists potential (a',8") for margin (r,c) such that 2=c= 8 Then by using (29) with (a",B") and (ā. B).
3. Analysis
Here we give high-level sketches of our analysis. Some of the proofs are relegated to Appendix B.
it follows that
sup gapg* ga Bj = g(x" $ )= =(( g(x".))
3.1. Generalized Kantorovich duality
a. = =g B) =
sup g (a (a,
For each (a, (3 Rm R", define
a.B
xa. = w/ @a @ B).
(27)
Thus all terms that appear above must equal, verifying (13). Since g is strictly convex, zre must be its unique global minimizer over Fw( Since xa. E e.T((r,c), c), the above yields that zZre
Using the key relation (9) and denoting X (xy) with X,)= : W.j. we can relate the primal objective function for SSB in (1) evaluated at x to the dual objective in (10)
evaluated at (a,, B) as follows:
3.2. Convergence of generalized Sinkhorn
g g(Xa.
Σ
X Xijo((,,)) -- Wij
Recall that the Kantorovich dual (10) is a concave maxi- mization problem and the objective function is not strictly concave. For such problems, linear convergence of stan- dard optimization algorithms is not usually expected unless one already knows that the trajectory of algorithm will be confined in a compact set and has an access on the strong convexity parameter of the objective function restricted on that set. Hence, key difficulty in establishing convergence of the generalized Sinkhorn algorithm 6 is showing that the sequence of dual variables along the trajectory of the Sinkhorn algorithm stays bounded. In the special case of entropic optimal transport, uniform bound on the norm of the dual variables (e.g., (Marino & Gerolin, 2020)) is estab- lished relying heavily on the closed form of Sinkhorn iter- ates (7), which is enjoyed only for the special case. In the lemma below, we establish that the generalized Sinkhorn algorithm a non-expanding operator in the norm..
(a + B(J))
Σ
D(
[,
11 B())
Σ a<ii) Σ X,)
Σ
X1j
Σ ((aai)++ + BCDWWi
|=1
|=1
1=1
m
m
(a, B) Σ a<(i)
r(i)
Σ 1=1
XIj
Σ P() c()) J=1
Σ
X11
(28)
1=1
where (a B) is defined in (10). This gives direct rela- tion between the primal and the dual objectives. Note that if W satisfies row and column margin (r, c), or equivalently, if x has w-weighted margin (r, c), then the above identity yields f( = (a, B). This is the essence of our proof of generalized Kantorovich duality stated in Theorem 2.4. The remaining details of the proof are given below.
Lemma 3.1 (L -mnootooniyyyyy of the Sinkhorn iterates). Suppose Tw (r, c) n (A, Bym is non-empty. Let (a, B.).
7

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
2 denote the iterates produced by the Sinkhorn algo- rithm (6). Let (á, Bi be an arbitrary potential for the mar- gin (r)c) W.E. W. Then for each to 0,
existing literature of EOT and typical tables. Unlike in EOT, we cannot rely on separability of dual objective, i.e., v' (a () = v (a)y' (B) (since v'(x) exp(x)), and unlike in the typical table problem with uniform weight W Im 1 (with constant cost), we cannot use reduction techniques developed in (Lyu & Mukherjee, 2024) that rely on the symmetry of the weights.
sup (I B.) (d. ml s a à @oloo. f
(30)
A special case of the above lemmas was first obtained by (Lyu & Mukherjee, 2024) for analyzing Sinkhorn al- gorithm for typical table problems arising from random matrix with given margin. Their key idea was to realize that the Jacobian matrix of the mappings at-1 - 4x and fx- 0g are row-stochastic matrices by using the implicit function theorem rather than using a closed-form expres- sion of these updates, which is only available for special cases such as EOT. Our proof of Lemma 3.1 above follows their approach.
Theorem 2.7 deals with the case when dom( is bounded. Without loss of generality assume a(1) .... a(m) and B(1) S ...... - B(n).. In order to arrive at a dimension inedpne- dent sufficient condition we analyze how different shifts in the potentials (using the shift invariance property) can im- pact the relative contributions of vectors u and v in arriving at a pair of constants 0 < s < which satisfy condition (21). Once (21) is satisfied, it is easy to find constant C, using bb is continuous and increasing, such that || C and Bl s C. which readily translates to d-tameness for some 6 > 0 that depends on C. and k. Since C itself depends on f, s, and f, we get that 8 depends on f,K, s, and r.
Note that by shift invariance of potentials, the bound (30) in Lemma 3.1 continues to hold if we replace the row po- tential & with any translation + m- Hence the right- hand side of (30) takes the minimum value of 2Do, where Do is defined in Thm. 2.6 (ii). This means that all fu- ture Sinkhorn iterates (a, stay within the Loo neigh- borhood of (á, P) with side length 2Dg. If such a box is contained in the box ($p(A)), ((lo))(((B)) (BBg))(m++))) (m)+))) for some 8 > 0, this would imply that every intermediate potential (,) is 8-tame. When ($(As). = R (e.g.. for EOT when ((xx) = fx)x + logx and A 0, B oo), this is always the case. However, one has to pay additional care when ((Ba)) is not the entire real line (c.g., it is (-oo,0) when f(x)= = xlogx+ + (1 log(( - x) for random graphs with given degree sequence).
Theorem 2.8 deals with the unbounded case. The first step is to bound the largest coordinate of the column potential by ((n) s (b1).. Indeed.
M W Wiy'' (any' +
IW., 2 c(n) =
Σ
W (B()) = v' w'((n).....
Next, we look at the smallest row sum r(1). The key insight here is to break the weighted sum for r(1) depending on whether B(j) is smaller than Φb(1 - A)s) This is because if most of p(j)'s are less than this value, then the first row sum will be too small and it will violate the lower bound on r(1) in terms of the quantity& s. Proceeding this way.
Once we establish a priori bounds on the generalized Sinkhorn iterates, we can analyze linear convergnece of the iterates by following the appraoch of Carlier (2022) for EOT, which was recently generalized by (Lyu & Mukher- jee, 2024) for the generalized typical table problem. We adopt their approach to prove Theorem 2.6. Fssentially, the idea is to use the strong convexity and smoothness of the entrywise dual objective y (see (10)) within a com- pact interval. This interval comes from the a priori bound of Sinkhorn iterates given in Lemma 3.1. Using this, one can show that the algorithm is a contraction in the space of direct-sum potentials a B, equipped with the weighted norm || T introduced above the statement of Thm. 2.6. Since linear convergence occurs at the level of direct-sum potentials, this does not contradict the fact that there are in- finitely many solutions to the Kantorovich dual (10) com- ing from the shift-invariance of potentials.
sW,. s(1)
Σ (j)<<(1--13)
WIJW (B()))
+
Σ
W V1/w'((())
s M((I (1 A)s) W1. -A)s.
where we denote M := ()= Wij. Rearranging
terms and since W,,, s > 0, we deduce
W M = r- (1- A)s
As
0.
(31)
Thus linear fraction of j's satisfy B(j) ((((1()))))) ())s). Us- ing this fact, this can be used to upper bound (mm) Since both the row and column potentials are now upper bounded and since the row and column sums are lower bounded, the smallest row and column potentials now cannot be too small. This leads to lower bounds on (1)) and B(1).
3.3. A priori bounds on the potentials
In our theory of generalized SSB, obtaining a priori bounds on the potentials requires substantial innovation from the
8

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
4. Numerical Experiments
Cascsiaa Lrande to Dacala Costa opccianice
In this section, we present results on the effectiveness of our GSA (6) for various strictly convex divergences. We consider the following six strictly convex f-divergences:
KL divergence: f(x) = xlogx,
Jeffreys divergence: f(x) = (x - logx,
Aanooa YOu The (eDmn))
divergence: f(x) = [xlogxx (x 1) (
Neyman x² divergence: f(x) = (x - 1)²
Binomial divergence: f(x)= = 10log( -ياي" and
Squared Hellinger divergence: f(x) = (V-
For different combinations of the (source and target) marginals and the cost matrix, we plot the log-scale im- provement in the L' errors of the GSA iterates of the r- divergences above versus the iteration count. We highlight two such combinations here, in Fig. 2 and Fig. 3. For the sake of brevity, we plot only the resultant transporta- tion map given by Jeffrey's ' divergence, while covering all remaining transportation maps in Appendix C.
Figure 3. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals in dimensions = 100 and n 100, I.2 cost function, and entropic regularization parameter = 10. The marginals are shown in the subplot (1.1), the cost matrix Cs shown at (2.1), and the 1." gradient norm of the dual objective (also the 1,1 marginal error) is shown (1,2). Plot (2,2) shows the transport map given by Jeffiey's 's divergence. For more thorough transport map com- parison, we direct the reader to Figure 9.
benefit of using more adapted divergence functions in EOT problem formulations. We postpone a more detailed expo- sition of our numerical experiments to Appendix C.
5. Conclusion
In this paper, we present the generalized static Schrödinger bridge problem, establish its Kantorovich dual, and show that the associated generalized Sinkhorn algorithm con- verges linearly in a dimension independent manner under mild assumptions on the general divergence functional f. weight matrix W and margin (r,c). We now discuss some immediate open problems. One question of particular in- terest is if our analysis, which crucially uses centering argument (possible by shift-invariance of dual potentials) can be extended to the more general problem considered in (Luo & Tseng, 1992) of the form
Figure 2. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals in dimensions m = 100 and n = 100, 12 cost function, and entropic regularization parameter e 10. The marginals shown in the subplot (1,1), the cost matrix C is shown at (2,1), and the I.! gradient norm of the dual objective (also the 1.! marginal error) is shown at (1,2). Plot (2,2) shows the transport map given by Jeffrey's 's divergence. For more thorough transport map com- parison, we direct the reader to Figure 8.
min f(x) = g g(Ex) + (b,x) S.f. XEX,
where g is strictly convex to achieve non-asymptotic linear convergence for alternating minimization and even coor- dinate descent methods under milder assumptions than al- ready known. Another key question is whether the priori bounds on potentials can be strengthened to sharp condi- tions such as those for Barvinok margins.
We observe that using different divergence functions shows different linear convergence rates; sometimes, the standard KL divergence is not the fastest one. In addition, the trans- port maps in Appendix C show qualitative differences de- pending on the divergence. This indicates the potential

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Impact statement
Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information pro- cessing systems, 26, 2013.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences our work, none of which feel must be specifically highlighted here.
De Bortoli, V., Thornoon, J., Heng. J., and Doucet, A. Diffusion schrödinger bridge with applications score- based generative modeling. Advances in Neural Infor- mation Processing Systems, 34: 34:17695-17709 2021.
References
Barvinok, A. What does random contingeney table look like? Combinatorics, Probability and Compuling, 19(4): 517-539, 2010.
Deming, W. E. and Stephan, F. On a least squares ad- justment of sampled frequency table when the expected marginal totals are known. The Annals of Mathematical Statistics, 1 11(4):427-444, 1940.
Barvinok, A. and Hartigan, J. An asymptotic formula for the number of non-negative integer matrices with pre- scribed row and column sums. Transactions of the Amer- ican Mathematical Society, 364(8):4333-4368, 2012.
Dhara, S. and Sen, S. Large deviation for uniform graphs with given degrees. Amn. Appl. Probab., 32(3):2327-53, 2022.
Dittmer, S., Lyu. H., and Pak, I. Phase transition in random contingency tables with non-uniform margins. Trans- actions of the American Mathematical Society, 373(12): 8313-8338, 2020.
Barvinok, A. and Hartigan, J. A. The number of graphs and a random graph with a given degree sequence. Random Structures & Algorithuss, 42(3))30 2013.
Benamou, J.-D., Carlier, G., Cuturi, M., Nenna. L., and Peyré, G. Iterative bregman projections for regularized transportation problems, SIAM Journal on Scientific Computing, 37(2) 2015.
Fortet, R. Résolution d'un système d' d'équations de m. schrödinger. Journal de Mathématiques Pures Ap- pliquées, 19(1-4):33-105, 1940.
Franklin, and Lorenz, J. On the scaling of multidimen- sional matrices. Linear Algebra and its applications, 114:717-735, 1989.
Bertsekas, D. P. Nonlinear programming. Journal of the Operational Research Society, 48(3):334-334, 1997.
Jiao, Y., Kang. L., Lin, H., Liu, J., and Zuo, H. Latent schr (\" of dinger bridge diffusion model for generative learning. arXiv preprint arXiv:2404. 240..339..33 2024.
Carlier, G. On the linear convergence of the multimarginal sinkhorn algorithm. SIAM Journal Optimization, 32 (2):786-794, 2022.
Léonard, C. survey of the schr\" odinger problem and some of its connections with optimal transport. arXiv preprint arXiv: 1308: 3ete:0218........ 2013.
Carlier, G., Duval, V., Peyré, G., and Schmitzer, B. Con- vergence of entropic schemes for optimal transport and gradient flows. SIAM Journal on Mathematical Analy- sis, 38544 2017.
Lorenz, D. and Mahler, H. Orlicz space regularization of continuous optimal transport problems. Applied Mathe- matics & Optimization, 85(2):14, 2022.
Chatterjee, S., Diaconis, P., and Sly, A. Random graphs with a given degree sequence. The Annals of Applied Probability, 1400)))1400-435, 2011.
Luo, Z.-Q. and Tseng, P. On the convergence the coordi- nate descent method for convex differentiable minimiza- tion. Journal of Optimization Theory and Applications, 72(1):7-35, 1992.
Chen, Y., Georgiou, T., and Pavon, M. Entropic and dis- placement interpolation: a computational approach using the hilbert metric. SIAM Journal on Applied Mathemat- ics, 76(6):2355-2366 2016a.
Lyu, and Mukherjee, S. Large random matrices with given margins. arXiv preprint arXiv:2407. /4942, 2024.
Chen, Y., Georgiou, T. T., and Pavon, M. On the rela- tion between optimal transport and schrödinger bridges: stochastic control viewpoint. Journal of Optimization Theory and Applications, 169:671-691, 2016b.
Lyu, H. and Pak, I. On the number of contingency tables and the independence heuristic. Bulletin of the London Mathematical Society, 54(1):242-255, 2022.
Marino, S. D. and Gerolin, A. An optimal transport ap- proach for the schrödinger bridge problem and conver- gence sinkhorn algorithm. Journal of Scientific Com- puting, 85(2):27, 2020.
Csiszár, I-divergence geometry of probability distribu- tions and minimization problems. The annals of proba- bility, pp. 146-158, 1975.
10

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Nutz, M. Introduction to entropic optimal transport. Lec- ture notes, Columbia University, 2021.
Nutz, M. and Wiesel, Entropic optimal transport: Con- vergence of potentials. Probability Theory and Related Fields, 184(1):401-224, 2022.
Pavon, M., Trigila, G., and Tabak, E. G. The data-driven schrödinger bridge. Communications on Pure and Ap- plied Mathematics, 74(7):1545-1573, 2021.
Peyré, G., Cuturi, M., et al. Computational optimal trans- port: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-600 2019.
Ruschendorf, L. Convergence of the iterative proportional fitting procedure. The Annals of Statistics, pp. 1160- 1174, 1995.
Sinkhorn, R. A relationship between arbitrary positive trices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-88) 879, 1964.
Sinkhorn, and Knopp, Concerning nonnegative ma- trices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-333 348, 1967.
Terjék, D. and González- González-Sáncheez Sánchez, D. Optimal trans- port with f-divergence regularization and generalized sinkhorn algorithm. In International Conference Arti- ficial Intelligence and Statistics, pp. 1165- PMLR, 2022.
Villani, C. Topics optimal transportation, volume 58.
American Mathematical Soc., 2021.
Wang, G., Jiao, Y., Xu, Q. Wang, Y., and Yang, C. Deep generative learning via schrödinger bridge. In Inter- national conference on machine learning, pp. 10794- 10804. PMLR, 2021.

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Linear Convergence of Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge Supplementary Material
A. Background
Connection to static Schrödinger Bridge. Our prime motivation to study the problem (1) is the classical static Schrödinger bridge. Suppose we have probability measure H on 2. x 2. representing our prior knowledge on the joint behavior of two X-valued random variables, say X and Y. Suppose that we are given marginal distributions of X and Y, say Px and Hy, respectively. The static Schrödinger bridge in this setting is to find the 'most natural' joint probability measure H for (X, Y) such that (1) it has the correct marginal distributions (μx, and (2) it is as close as possible to the prior distribution St.
More precisely, given two probability measures v the same measureable space, define the relative entropy (or the Kullback-Leibler (KL) divergence) of from by
[ dA (1) log dv 100
dA (w) v(du) & &
(32)
otherwise,
where < v means that A is absolutely continuous w.r.t. v and dA denotes the Radon-Nikodym derivative of A with respect to v. Now the static Schrödinger bridge problem introduced informally above can be stated as
dv
min Fell(xx.
(33)
where my) denotes the set of all joint distributions in 2' L that has marginal distributions μx and μy. The joint probability measures H that solves the above problem is called the static Schrödinger bridge between marginal distributions Hx and jy w.E.t R.
The base model is often taken to be the product measure A = μl U2. In this case, there exists functions a 42 RR R known as the Schrödinger potentials that characterize the Schrödinger bridge as (see, e.g., (Léonard, 2013; Nutz & Wiesel, 2022) and Sec. (B) of (Csiszár, 1975))
d.Hl d (x, y) = (x))xx+)()
R-a.s.
(34)
To make the connection between our main problem (1) and the static Schrödinger bridge (33) clear, consider the following discrete setting where the random variables X and Y take m and n distinct values, respectively. We will identify them with the integers in [m] := (I...., m) and [n], respectively. Then the prior measure E lives on the integer lattice [m] x [n] and the marginal distributions μx and jy live on [m] and [n], respectively. Then writing (33) as an optimization problem involving the Wadon-Nikodyae derivative X
d.t ds
we obtain
min Σ (xi logx1)) (=(X))ERR 1.j
(35)
n
Σ s.t. x R(i = (x)(), Σ x =(.
Notice that the above is special case of (1) with weight matrix W R, margin (μx, and divergence f(x) xlog.x
Connection to Entropic Optimal Transport. Schrödinger bridges and entropic optimal transport (EOT) are intimately related as evidenced by the problem formulation that arises in EOT. More precisely, given a measurable cost function c:Mx x 2 - Rao and a fixed regularization parameter & > 0, the entropic optimal transport problem is
I
min py)
cd.fe + eDr Hx py)
(36)
12

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
which is the same as (33) for [(d(x, y) & cl (dy We differentiate between the cost matrix Gjj and the margin by boldface. In a manner similar to earlier, consider the discrete case and denote the Radon-Nikodym derivative as X dxk Then (35) further reduces to ds
min
Σ (Xix logxij)e 1 (x(0)
(37)
X R0 50
1.J
x S.L. Σ
xiee
qple ur(()))))(
1, Σ xije Snyl px 4x(0)=
The above may look a bit different from a direct discretization of the standard formulation of the EOT (36). The difference that while (36) is formulated in temrs the joint coupling H as the optimization variable, (37) is formulated in terms of the Kadon-Nikody.
Recall that (37) is special case of our main problem (I) with weight Wij o (e (e-eiyl px py Miy, margin (r, c) = (y) and divergence f(x) = xlogx.
drivative X = d.f
dix
Connection Random matrices with given margins. Recently, Lyu and Mukherjee (Lyu & Mukherjee. 2024) discov- ered that the random matrix with i.i.d entries from a common distribution μ conditioned to have a prescribed row margin re RM and column margin C R² concentrates around the solution of special case of (1). Specifically, it is the case when W = -1 (uniform prior) and fxx = Dxz. (Hopoo ll p), where Ho is the exponential tilt of μ defined dp
due (x) = exp(Ox--((O),,
yr (0) -los exx p(dx) is the log-Laplace transform of μ. and Φ is the strictly increasing inverse of the 'tilt-to-mean' func- tion w'.
The key insight in (Lyu & Mukherjee, 2024) is that the margin-conditioned random matrix X can be well-approximated by another random matrix Y with independent entries, where the laws of the entries are suitable exponential tilt of the base measure μ.. The authors show that among such parameterized models by entrywise exponential tilts, the best one is given by a rank-one tilting, where Yıj ~ +a for some vectors a RM and f RR.. The best such dual variables can be computed by solving the maximun-likelihood estimation problem, which is precisely (10) with W 11 Since the log-likelihood function ga (3) is strictly concave, the MLE must be a critical point, yielding the MLE equation
EIY] v/ (a @ B) E (T,c).
(38)
Here, the equality follows from the definition and (r, c) = (r, c) is the transportation polytope of all m x n real matrices with margin (r, c) (recall W )) This consists of m n linear equations (one being redundant) that precisely correspond to the system of Schrödinger equations (see, e.g., (Nutz, 2021))
Once the MLE (a, (3 is found, then the best approximating model Y for X is given by
Y - Hasp.
(39)
meaning that Yijs are independent and Vij- ~ Matn+(f.- In (Lyu & Mukherjee, 2024), Lyu and Mukherjee established trranfference principles', which roughly say that X = Y. Given this, it is natural to expect that X concentrates around the mean of Y. which is precisely the matrix v'(a @ B). This matrix is known as the typical table for the margin (r, c) and base measure i in (Lyu & Mukherjee, 2024). According to our Theorem 2.4, the typical table can also be viewed as the corresponding generalized static Schrödinger bridge.
Much of the theories we develop in this work are in parallel to and generalize those in (Lyu & Mukherjee, 2024) for non-uniform weight matrix W and general divergence function f()) that is not of the form (xr,( p).
B. Postponed Proofs
Recall that we denote Interior(dom(()) (A, B) for some A, B BRRURRR (oo) and @ := Interior(dom(y)).
Proof of Lemma 2.3. Since the domain of f' (A,B), if a SSB z exists, it belongs to the intersection Tw(r, c) n (A, B) mxn For the other direction, suppose there exists some X (xij) E B) Then there exists o such that X LAg, Bs] mxx (see Def. 2.5). Let ((k) be a sequence of matrices in (A, B) m*n (w c) such that
g(Z!0) 5
inf Ze.T (t.
gZZ) + k
(40)
13

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
if the infimum is finite, and require g(Z otherwise. We begin by showing that for any i, such that Wij >0,
A < liminfZ (k) ijj
= <limsup / B.
(41)
K-00
k--00
By passing subsequence, assume that 7/10) real-valued matrix. Let
1/000 [A, BJ for all iʃ, where 7i00) (2/100) is (possibly) extended
F [0I,]) 21 0/000 A. >0]
(42)
8B (). 11 0/000 B, B. > >0),
(43)
AA ((I. D) / (A, B)).
(44)
For any E [0,1] set ((kA))= = (1 () AX, and note that ( E Fw () [Aa5, B151 mxn Hence
inf Xes Moxn m g(x) = g(z(k.)))+ 1 k
1 k
g(z
(45)
for all sufficiently large k 1. By convexity of g.
()
(())
2 (Vg(z(k.)), (o
(2(2.))) (2))
Wi))
(46)
KA
A
1,j
Letting k- - oo followed by A N 0 in (46) we get
- - T [z - Wij
(47)
= Σ ((A)(A x11 Wij+
Σ 4(B) WI) (i,E
1Z -.jj U.fEEA
Σ
(48)
&
Note that AA= = Ø if A 0o and (AA) = 00 if A is finite by Assumption 2.1. Similarly, FB = Ø if B = oo and &(B) = 0o finite. Since the third term above finite, the above equality holds only if A = IB = Ø. which gives (41).
Given (41), we have the existence of 8 0 such that
inf Xes
g(Z)
inf Ag mmn g(Z).
(49)
But the RHS above focuses on a compact set, and minimizes strictly convex function. Hence the existence of a unique optimizer follows.
Proof of Lemma 3.1. By permuting the rows and columns if necessary, may assume that &(1) .... (m) and B(I) ...s B(n). Fix (ac, B) e Rh x R². Let ß- <(p) a' denote the Sinkhorn update for the first dual variable given the second one B. This update is characterized by (5) as r(i) Σ, w' (a' + B()):;; for all i. We would like to compute the Jacobian of this map. To do so, define the function F: pR" R - RM by setting the ith coordinate of F(a. B) E R²" for i= l,... m as
r(i) Σ v' B())W...... f
(50)
Then a' =E()) is the unique zero of the equation FC. p) = Let E = E(a', .B) be the n matrix whose (i. entry is -a" B()')W, and let Fj. denote the ith row sum of E for i i= I,..., m. Then the Jacobian of F with respect to and B. respectively, are given by
UFa(a' 1Bl''',)lmmm diag:E Em-),
Unpla' pal'',p0lmxm = E.
(51)
The first Jacobian matrix above is always invertible since v" > 0 on the domain. Hence by the implicit function theorem,
Ual:plmx -a B0 UF,p(a', p)
(52)
=-Iala', /)i,/ ():+))mxx
(53)
14

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Importantly, we observe that- pll''pl :l is row-stochastic matrix.
Now fix any potential (a, B) for the margin (r,c). Note that E(B) Let = (1 B) sB denote the linear interpolation between P and B. Then denoting Ps == - we have
a' - à = - -E(B) = !oo Pādss B).
(54)
The matrix P defined above is row-stochastic since every intermediate negative Jacobian matrix row-stochastic by the earlier observation. particular, since P| = 1, this yields
|| a - @clco = |l B - -Blloo = 11B--B 11lloolooo
(55)
By a symmetric argument, it also holds that
B Bl = l a alo..
(56)
where B' denotes the output of the Sinkhorn update for the second dual variable given the first dual variable a. It then follows that, for all 200.
1lki1 - â lo. 11
Bllox lax 0lloo s 11fx -Blooo
(57)
By induction, from the above, deduce (i).
Proof of Theorem 2.6. We first claim the following: (16) holds if all Sinkhorn iterates (at.Pz) for k z ko well as the potential (a", ff") are e-tame. Before proving this claim, we will first deduce parts (i)- from this claim. First remark that there some well-known results from the optimization literature that are directly applicable to the generalized Sinkhorn algorithm (6). Since each sub-problem in (6) has unique solution due to strong concavity of the block-restricted dual objective, asymptotic convergence to the critical point of (6) follows from general result for alternating maximization (e.g.. Prop. 2.7.1 in (Bertsekas, 1997)). Every critical point the dual objective is an MLE, which is global optimum by Lemma 2.4. Thus follows that æg @ Bg
@ f as k - ao entrywise. In particular, we choose > small enough so that (r. c) E-tame (i.e., ((AA) s a @ B² (BB))) then there exists kg such that (bAg/22 - a e B = (((B21) for all 2 kg. Then (i) follows from the claim. For (ii), the hypothesis of the claim is directly justified by Lemma 3.1.
It now suffices to show the claim. Our analysis for this is inspired by the proof of linear convergence of Sinkhorn algorithm for entropic optimal transport due to Carlier (Carlier, 2022). For simplicity denote F: -ge Consider the following centered Sinkhorn iterates (x.BBp) for k where (æa. Ba) (aa. Po) and for k 1, (ā B is obtained from B by the same Sinkhorn update in (6) but follow by centering (adding and subtracting the same constants to å and B respectively) so that (u, à 0. By an induction, easy to verify
a + B = a BR
for all k O.
In particular, F(xx.Bp)) F(āx, BB) for all 2 Denote o = (E), which are defined in the statement. Note that
F(a, ddaag u(i) Σ v" PL
diag v(j) = ('"""(aai+p@@)iiiaa)))
If (a. (3) and (B) are both e-tame, then so is their convex combination. Hence F(a,)) +) restricted on its jth coordinate is Mi) convex and Cmxx) -mooth on the secant line between (a, f)) and (a',, f¹). Denote
p.. = (1, B, B. 1
(re)(m)
15

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
for j = O,..., 11 and let BI,. Bi+ Notice that the dual problem (10) restricted to optimizing for f is separable over each coordinate of B. Hence the first-order optimality of Bi+ implies "y = 0, which in turn implies
Fla (=
=0 for j I...,,
Hence by the second-order growth property,
Cmin [B,(j) -x:
F(a,, Pr.z) F(a Broj+))
for all j= 1,,.,,, n Summing over j, we obtain
u. Cmin σ²
F( F(ã F(ik....11)
11 F+ B,
2
where denote the v-weighted norm || R by |laly: VE, a(j))v(j). Define the u-weighted norm || similarly. Then using similar argument as before with V Va.(@r-1.
get
F( ((+1) -Fat B(11) 2. || à llu
2
Combining the two inequalities above and recalling = F(ā B.) - -F((", , we obtain
A Ar+1 V. || a + 11: B C
(58)
Next, note that y os-strongly convex and of smooth (b(AA)),((BB))) In particular, for each x, in that interval,
0² - (x (x- (xx) w(y) w'(00x y)
(59)
Then e-tameness, (59), and (u) = (u, a give
Σ (a' (t) + - B,
Cmin
w (a, B,(j))(a'' (1) 6p* (f) a,()) -, (()
o²
II(a" BO) - (ā, 11 + 2
(60)
2v.llæ l uu II -B,
Then using VaF(a,, B,) = VpF(a, Br+1) O, we can deduce the following strong-convexity-type incquality
A = ((tt B,) - (a' (f)),
Σ v(a (i) (1)) (i) B,CD+).)))
(V F(ā B,), a - a,)) (V))+(VVV(@... B.), B B.)
2
+
[v.llee - -. u. -B,1
2
/VF B,) F(ā B.11)1i
2u.
2
ai ar (v.
11 B,)
2
16

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
12 where (a) follows from coordinate-ve wise Young's inequality (ab Age + Zx for a, and A u.v(j)Cmino2 for jth coordinate) and (b) follows from the Lipschitz continuity of VpF and including an additional nonpositive term for the lower bound. Combining with (58) and recalling x
Gmax
Cmin
A 1 Ar+1).
Rearranging, this A,+1 s (01xx-3 (1 (0-10+)*) A, similar argument as above also shows
A 2
I1(x @ fB*) (ax, @ B
Combining, obtain (16) claimed.
Proof of Theorem 2.8. By the hypothesis, (A, (0,00), s ssr(i 1 and s c(j/W.., = for all i.j. By Lemma 2.4, there exists potential (a, (B) for (r,c) w.r.t. W. Note that d(zij) a(i) B()) ((((A))(())) for all i,
Denote K = Cmax/ Cmin and define
x21 1
(1;;s,))= Φ
(I - (1 - 2),)) --6((1 - A)1),
(61)
As
which is well-defined whenever E som
()) 50 - = (0, under the hypothesis. Note that xs (1-(1) (1-1)s)
2
so we get c(A;s, () 20))) Φ([1 - A) = 0. We claim that for all í,j and À dom(c(-;s, O))
Φb()) c(A;s, f) (i) B(j) = ((t) + c).
(62)
This will directly imply (23). For the second part of the conclusion, note that, since is continuous, we may choose A E (0, 1) such that (0(1-))s), + A)t) e O" and E(A; () ==
( r) 2 0 is so small that
Φ(s) - f) t
(63)
Also, since 0 c(d;s,t) f) E(A; r), it follows that from (63), we have
(i) ((j) e (pb(s) - E(A; ((t) + c(A; ()) (0, = for all i,
(64)
Therefore, (r,c) is 6-tame for 8 small enough that = ((s) r)A; and ((() c(A;s,t) Bg.
Now it remains to show (62). We may assume that 0 a(1) ... S (m) and p(1) S .... B(n) by shifting the potentials and permuting the rows and columns if necessary. We first note that ((n) = (ft), which follows from
m
IW., 2 c(n)
Σ ( ((n) 2
Winw Winw'(B(n) (B()))
(65)
and (tt) e O". Define
M:
Σ
W1/-
(66)
Note that
sW, rr(1)=
Σ W Wif WIjW'(B(1) (B())+ Σ
W1jw
(67)
(()=0((1-A1)))
#()=((11A1))
s M(r (1 A)s) W1.(1- A)ss.
(68)
Rearranging terms and since WI.,5 0, we deduce
M
As
> 0.
(69)
W t- (1 A)s
17

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Hence there exists index j" such that B(j*) 2 <((1 ()))). Let such be small possible. Next, we claim that
x² I (t- (1-11111))0011) Als) ('((())
(70)
As
To show this, observe that ('((m)) + +(1)) 0 since
m
< sW, sc()) Σ (a() s v' ((1)
(71)
Hence,
r(m)
Wmi (a((m) + +B("
Wmj
z
Σ
Σ
y (a(m) + B(1))
(72)
W m
W m=
Wm.
j2]
プzz Wmj ((a(m))+Bi+
(73)
W Wm.
Now from the hypothesis that W Co uv and recalling x Cmax/ Cmin.
Wmj
CI,v(i), Wij Σز2 Cmjv(j) / Civ(i, Σ₁2l Cmin Cmxxv(((
E | Cmax
W1. E,Cmjv(j) E,Civ((i) 2
=k
(74)
W
Σ, Cmin
Combining with the previous inequality and using (69), get
t 12K- - As
v (a(mm) B()
(75)
t- (1-1Js A)s
Simplifying the above yields (70).
Then applying & both sides of (70) and using ((j*) <p[(1 A)r), get
x2 [(t 1 (1-A)s)
a(m) s &
(76)
As
In turn, can deduce lower bound on F(1) from
c(1) Wi ((((((++++ s s/ (a((m) ((1),,
$5 W.
(77)
W.1
which reads f(1) z (b(s) ((m) = ((s)) r). Therefore, <(1)+ ((1) (((s) - c(A; r) and a(m)+ +(t)) f). This shows (62), as desired.
Proof of Theorem 2.7. Without loss of generality, assume m 2 n. Let Z be the SSB for margin (r,c) w.r.t. W and (a, B)
be potential for (r,c) w.t.t W. respectively. By Lemma 2.4, we have v' B). Write a = (a),..., am) and ß = ($I..... Bn). Without loss generality, we assume ai S ... am well B, ..... =B,
Recall that for any A R, (a A1 f A1 is also potential for margin (r,c) w.r.t. W. Define functions
p(A): Σ Eu(hiaa +A20 A20) and y()):= 1 -v
(78)
where a. := (1,a) for vector a. Note that p(A) is a right-continuous non-decreasing stepfunction and y(A) is a left- continuous non-increasing stepfunction. If A min(p), -a m)) then am + 2 < and β1 - A 0, so p(A) = 0 and y(A) 1. Similarly, max(-a1, then a1 + A 0 and 8, - < 0, so y(A) = 1 and y(A) = 0. Hence there must be an intermediate value of A, say 2", where the graphs p(2) and (()) cross.
18

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Then near A", either (1) P is constant and y drops down vertically or (2) y is constant and p jumps up vertically, Without loss of generality, we will assume (1) holds (the other case can be handled by symmetric argument). Then we have
p p= w v.
-v(j)117 -)) v. Σ [v > 0) for some w [0,1].
(79)
In the remainder of the proof, we will consider the shifted potential (a (a","") := (a 1 1 mm - 1n), We will denote a' = (ai....,,a,, am) and 6* = (fi..... and := p(A*) and y y(A))
Fix sufficiently small. Note that <b(e) oo as E and (BB 0o \ 0. Hence there are constants c, (depending E) such that
((c(E) + (B -) ((s-)), E), ( + + C2E) 4b(( E).
(80)
(81)
Then, for fixed E, or, C2. we may choose C3 C4 small enough so that
((B (bs- (lae))((B-c4e) 2 +))+
(82)
(83)
We claim that
(b) ((qE) s aj s nm
(0)
$ & C2E), (c) - B B (d)
(84)
((CGE)
b c48).
(85)
Since <b(Z,)) = a + BB and ob is non-decreasing, the assertion follows immediately from this claim. Inequalities (c) and (d)
follow easily from assuming (a) and (b). Indeed, suppose (d) not true while (a) holds. Then
tW., 2 c(n)= = WWin''co (aj + (T,) z W., v (b(c))))) + 4(B - cεe) = (1 + W)
(86)
which is a contradiction. Thus if we show (a) holds, then (d) also holds. Similarly, if (c) is not true while (b) holds, then
sW.i s c(1) - WWaw'aa (a; + (J) = W., v [ØLB c26) + ((c3e)) s ee)....
(87)
which is a contradiction. Therefore, it remains show (B))
Suppose for contradiction (a) does not hold, i... aj ((ciE). Then necessarily 8 > &BB E), since otherwise for all isjsn, n.
w = [a] + BJ) s v'aa + B7) s w ( s w (p(ss -)) s
(88)
(s- This implies (s a contradiction.
Now since ai <((cEe and B > ( E),
Zi, v la; ( 2 (')
a
(89)
Z,j w/ (aj B7) = v'(aa) v
((((CEE) =CE
(90)
Then we have
VC))x,(2)u, 2 /W,, c(n) = Σ Zin
Σ WinZZin ka <0
(91)
2 (B- (B-e) E)
Σ
W Zn,
Σ Win
(92)
Bap
1,7500
2 (B E)v(n)
Σ
(in,uii)Z,,nvie
Σ Ci,,(ii,,
(93)
k z0
1a
z (B (8-e)v(n) Cmin
Σ
u(i) + (n) Cmin
Σ u(i),
(94)
lap 20
1sa <0
19

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
where for the last inequality, we used the fact that Zi,j ddom(f") S (0, This gives
Cmin Cmax
Cmin (1 11-00 p).
12 (B E) p In
(95)
Cmax
Similarly but now using (79),
4Cminu(1)v. sWW.
(96)
sr(1)=
Σ
Wi,jZ +11 w) =:07=0
Σ Zi.jZu.j
+
Σ Wi,jZas+ + Σ Wi.
(97)
1:,,50
1:0/=0
1:0720
s Cm
Σ v(-)+(1-u) w)
Σ v(j)
1 W v(i+ Σ v(1)
(98)
1:
1:0750
s ccu(())Cmx(l) -Iv,,, + 13)
(99)
Simplifying, we get
Cmax (1 11-p)+
Cmax Cmiin
s C1
+
p.
(100)
Cmin
Thus far we have obtained the following inequalities
3: 11-511ppp00 pplcr pZA,.. x= + p)Zz,
(101)
Denote Zi, Since p E 1].
T+
s-c
(102)
This yields
i
(103)
where the first and the last inequalities above from (102). The middle inequality above uses that the function x - 2v Bx x is increasing for x (0, B). Thus if
pB+z 2
vpBT and the fact
B(S (3-
(104)
then this leads to contradiction. Note that (104) holds for e,C, sufficiently small if B5- (5+ 7)? < 4B3. The last condition reads
(x ++<k))> 4Bx 1s
(105)
Thus we conclude that (84) (a) hold. An entirely similar argument also shows (84) (b). This completes the proof.
C. Additional Numerical Experiments
In this section, we consider a total of twelve settings (two of which we already cover earlier in Section 4) in dimension 100, combining the three hyperparameter settings:
Marginal distributions: (1) Each coordinate uniformly sampled from (0,1) and then normalized; and (2) Gaussian distributions with 1- or 2-modes.
Cost functions: (1) Each coordinate is uniformly sampled from (0,1); (2) L -cost function
Entropic regularization: (1) (2) e= 10, and (3) e 100.
20

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
As before, consider the following six strictly convex f-divergences:
KI. divergence: f(x) xllgxx
Jeffreys divergence: f(x) = (x- 1x
divergence: f(x) (xlogxx (x+ 1) lo ( ))
Neyman x² divergence: f(x) (x - 1)².
Binomial divergence: f(x) = 10log(-10 - and
Squared Hellinger divergence: f(x) 2 1)
Each experiment is organized (3,3) plot. Marginal distributions shown in the subplot (1.1), the cost matrix C is shown at (1,2), and the I." gradient norm of the dual objective (also the L. marginal error) is shown at (1,3). The second and the third rows show the optimal transport maps found by the GSA with the corresponding divergence functions. Figures through 15 cover all the remaining ten of the twelve combinations.
Nattab Higar Seabel
Cal Sture tit epuleets
11 Erte Jocule
Tourpent the 1832
Trrppeti the tithoodl
Tranpec Fax Dheors Oheasid
Trempett Pas Dlense Seauedi
Tranpent Pie Iterekt
sreepentte (feaeed Helrord
Asa
300
Figure 4. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for uniformly random marginals dimensions m = 100 and n= 100, L cost function, and entropic regularization parameter e 1. The marginals are shown in the subplot 1,1), the cost matrix Cis shown at (1,2), and the L gradient norm of the dual objective (also the z marginal error) is shown at (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
21

---

Sinkhorn's 's Algorithm for Generalized Static Schrödinger Bridge
Nacghasl (ialter Zeoder
Can Mearr (12 epolo 200
14 Ervers beratie
1300
Trunug Plac
Treeppat Fan (ktron)
Trarppt: Zun Oraviy Chaaoee
Toanpert the (ee
Themaut Sun (iteerd
Traaqprt Pae Uigarel Hede get)
Figure 5. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for uniformly random marginals dimensions m= 100 and n = 100, 1.2 cost function, and entropic regularization parameter 10. The marginals are shown in the subplot (1,1), the cost matrix C is shown at (1,2), and the z gradient norm of the dual objective (also the z marginal error) is shown at (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
Mirthaaa Chtber Narden!
Con Mante (12, mocke-tos
LI Errers Dematee
Thinepwer Tite 4023
Tranegon Fax (Iffreen)
Thymeer Lhe (leme Shrnesy
Tromeet Fixs Dlonne Seward)
Tratppet Fixz mten
Thenset Masibbaand Helbast
200
Figure 6. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for uniformly random marginals dimensions m = 100 and 100, 1.2 cost function, and entropic regularization parameter e 100. The marginals are shown in the subplot (1,1), the cost matrix C is shown at (1,2), and the f.1 gradient norm of the dual objective (also the 1, marginal error) is shown (1,3). The second third rows show the optimal transport maps found by GSA with corresponding divergence functions.
22

---

Sinkhorn's 's Algorithm for Generalized Static Schrödinger Bridge
Mirgiaaii
speiiam1
Harchall Daaaudie (readete
Coe Stami epabee
11 Emerss beratee
Tonepen Pie 1802
Trnepen Pee (jthwe)))
Traeppan Fas (reass Durese
Trasppet Plyyas Squandi
Tranqun Fur tineeat
Traraeen Pir diquadd Hellaged
Figure 7. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals in dimensions m = 100 and n 100, 1.2 cost function, and entropic regularization parameter e = 1. The marginals are shown in the subplot (1,1), the cost matrix is shown at (1,2), and the L gradient norm of the dual objective (also the Z marginal error) shown (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
Margrove
Mirgea' Simasas srado 2ecid)
Cart Mitrrs apalaaoe
timer Seritaee
Tranppn Paa 1E1
Traeapat Pan (HDbro
Traurpot Plac Ttrase Shannes
Transee the (haees Spauc!)
Thanped Zan dhacsall
Trempptt Flas ISpand in Iutass)
Figure 8. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals dimensions m = 100 and n = 100, 1 cost function, and entropic regularization parameter = 10. The marginals are shown in the subplot 1,, the cost matrix C is shown at (1,2), and the f. gradient norm of the dual objective (also the 1.1 marginal error) is shown (1.3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
23

---

Sinkhorn's 's Algorithm for Generalized Static Schrödinger Bridge
Con Matra 112 epthe-
11 Emmers Tematee
Torepan Pas (kfree)
Thoppor The (hease Sheezs)
Trasppo:: Tha Ulecao Squaned
Traspptt Fas (lreeat
Traapet Scued lielppr
Figure 9. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals dimensions m 100 and n 100, 1.2 cost function, and entropic regularization parameter = 100. The marginals are shown in the subplot (1,1), the cost matrix Cs shown at (1,2), and the I gradient of the dual objective (also the L marginal error) shown (1.3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
Margirali
spelion...
Drod Marr thme fondior mpslisa-11
Et Seme en leeetee
Thcowet Nan riehroa
Tramont Whe Cheawer
Tranepet Phe Diocass Spard:
Trarpon dloweaa
Transpat Fias Eppard lhdinges
Aat
Figure Convergence of dual objective gradient norms GSSB, transportation maps various f-divergences for uniformly random marginals in dimensions m 100 and n 100, uniformly random cost function, and entropic regularization parameter e == 1. The marginals are shown subplot (1,1), cost matrix C shown at (1,2), and the L gradient norm dual objective (also the I marginal error) is shown at (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
24

---

Sinkhorn's 's Algorithm for Generalized Static Schrödinger Bridge
Margtaate
spoler-11
Morro Btatirn Pankes miikeeti
tiver
Teanpent Plx Ustiond
Teanseect Plice Uniice
Trarppen Pos ah Spanch
Tratspat Pire tha
Tronggett Fon dicuree Wellaged
Figure 11. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for uniformly random marginals in dimensions m 100 and π = 100, uniformly random cost function, and entropic regularization parameter e = 10. The marginals shown in the subplot 11, the cost matrix is shown (1, (1,2), and the I.! gradient norm of the dual objective shown (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
Mangizate Uritor Randen, Cach thittenn Rusdens speice. 138
Variie Rordare
Frer
Jahae ti Si-tei
(efrren)
Fle
Tranqpe: DNeraa Segamet
Troagen Paon depaadd Hellager
Figure 12. Convergence of dual objective gradient norms GSSB. transportation maps for various f-divergences for uniformly random marginals in dimensions m 100 and n 100, uniformly random cost function, and entropic regularization parameter = 100. The marginals are shown the subplot (1,1), the cost matrix C shown at (1,2), and the L! gradient norm of the dual objective (also the I marginal error) is shown at (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
25

---

Sinkhorn's 's Algorithm for Generalized Static Schrödinger Bridge
Mangraale
spedredd
Porpiiak Strasskee toace (19000))
Drok Mairs 200 fondor opstiaml)
Tresspan Pax
Adde
Tocppet Nie riehool
Alce
Tramspot Than Traves Gossell
Tranepor Pae dieceas Spard)
Tarrpon Hitwead
Transpart Flas iipard tnllrges
Figure 13. Convergence of dual objective gradient norms of GSSB, transportation maps for various I-divergences Gaussian marginals in dimensions m = 100 and 100, uniformly random cost function, and entropic regularization paramcter e = 1. The marginals are shown in the subplot (1,1), the cost matrix is shown (1,2), and 1.2 gradient norm the dual ohjective is shown (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
Mergeoss: Uras 2unaae
Cbel: Listorn Nandons apainc-10
Martach (Senoke:
Trrapert Dhe
Tnraperi the (ltbboa
Trcrppen Fan Oheres
Tranppet Zas Dieras Sqrandi
Tranapen Fex tineeat
Tracapon Plae tiganed Hillagen
200
Figure 14. Convergence of dual objective gradient norms of GSSB, transportation maps for various f f-divergences for Gaussian marginals dimensions m 100 and = 100, uniformly random cost function, and entropic regularization parameter e = 10. The marginals are shown in the subplot (I, the cost matrix C is shown at (1,2), and the L gradient norm of the dual objective (also the L marginal error) is shown at (1.3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
26

---

Sinkhorn's Algorithm for Generalized Static Schrödinger Bridge
Mardeda (Gauatt 1-zekr22ssk
Cue Styste Fiadbrr Butdas upiiave 301
L1 Erme Ieoske
Ban
3010
Trasspat Plan
Trerpon Pas (iftren
Themert The fleaee Sherer)
Transee:: Tik Uhecann Seuared
Transpet Thes Ithemntt
Themset (Scuree Iieltaprt
Figure 15. Convergence of dual objective gradient norms of GSSB, transportation maps for various f-divergences for Gaussian marginals dimensions m 100 and n = 100, uniformly random cost function, and entropic regularization parameter e = 100. The marginals are shown in the subplot (1,1), the cost matrix is shown (1,2), and the Z gradient norm of the dual objective is shown (1,3). The second and third rows show the optimal transport maps found by GSA with the corresponding divergence functions.
27


Reviews:
[{"review_id": "O4YQkrxppf", "reviewer": "Reviewer_U8FC", "summary": "This paper studies the generalized static Schrödinger bridge (SSB) problem, which extends the classical SSB by replacing the entropy divergence with any strictly convex function. Then it derives the Sinkhorn-type algorithm for solving the generalized SSB, and proves the linear convergence of the algorithm. Moreover, this paper examines the conditions under which the convergence rate is independent of the dimensions of the problem.\n\n## Update after rebuttal\n\nAfter reading the rebuttal, I am satisfied with the further clarifications, and I decide to keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our work and further suggestions. \n\n**Other Comments or Suggestions**\n \n1. Thank you for pointing out this typo, we shall make the change to refer to iteration count by $k$ instead of $t$.\n2. In the revision we will maintain $t$ for the upper bound on the tameness condition and use $k$ for the iteration count throughout. \n3. Noted and changed. \n4. This is an excellent point raised by the reviewer. In fact, below Thm. 2.8, we have already discussed how our general results specializes to the EOT setting. Carlier '22 shows that the linear convergence rate of Sinkhorn for EOT is proportional to $\\exp(\\Vert c\\rVert_{\\infty} /\\epsilon)$, where $c$ is the cost function and $\\epsilon$ is the entropic regularization parameter. Our Thm. 2.6 (i) shows that Sinkhorn for GSSB has linear convergence rate proportional to the quantity $\\kappa$ defined as \n$$\n\\kappa := \\frac{C_{\\max}}{C_{\\min}},\n$$\nwhere $C$ here is the cost matrix. Specifically in the EOT setting, we have $C_{ij} = \\exp(-c(i,j)/\\epsilon)$, so $\\kappa$ becomes \n$$\n \\kappa  = \\exp\\left( \\epsilon^{-1}( \\max c(\\cdot,\\cdot) - \\min c(\\cdot,\\cdot)) \\right)\\le  \\exp(\\Vert c \\Vert_{\\infty}/\\epsilon). \n$$\nThus our convergence rate in Thm. 2.6 shows the same dependence on the regularization parameter $\\epsilon$ in the literature, which is inverse exponential. One interesting point is that $\\kappa$ above depends only on the span semi-norm of the cost function $c$, which can be significantly smaller than the supermum norm of $c$. But one could WLOG assume $\\min c$ is zero, so both quantities are the same. \n\n\n**Questions for Authors**\n\nWe thank the reviewer for asking this excellent question. We in fact have tried to establish linear convergence of Sinkhorn for GSSB in this way. In a nutshell, as you correctly pointed out, the dual objective becomes strictly concave once we eliminate one redundant degrees of freedom by, e.g., setting $\\alpha_1 = 0$ throughout, so we only have $n+m-1$ dual variables to optimize. Let's assume $m=n$ for simplicity of the discussion. But the main issue in this approach is that the condition number of the Hessian can be as large as order $n$, since the largest eigenvalue of the Hessian is always order $n$ but the smallest eigenvalue can be order 1. In turn, Sinkhorn viewed as alternating maximization for the dual objective restricted in the subspace of $\\alpha_1=0$ gives only a dimension-dependent linear convergence rate $(1-O(n^{-1}))^k=\\exp(O(k/n))$. \n\nWe'd like to provide further details on this point. The Hessian of the dual objective restricted to the subspace $\\alpha_1 = 0$ has the following 2 x 2 block structure \n$$\nH(\\alpha,\\beta) =\n\t\\begin{bmatrix} \n\t\tE_{2\\bullet} &   & & E_{21} & \\dots & E_{2n} \\\\\\\\\n\t\t& \\ddots &  & & \\ddots & \\\\\\\\\n\t\t& & E_{n\\bullet} & E_{n1} & \\dots & E_{nn} \\\\\\\\\n\t\t\\hline\n\t\tE_{21} & \\dots & E_{n1} &  E_{\\bullet 1} & &  \\\\\\\\\n\t\t& \\ddots & &  &\\ddots &  \\\\\\\\\n\t\tE_{2n} & \\dots & E_{nn} &  & & E_{\\bullet n}\n\t\\end{bmatrix}\n$$\nwhere $E_{ij}=\\psi''(\\alpha_i + \\beta_j)$. $E_{i\\bullet}$ and $E_{\\bullet j}$ denotes the row and column sums, respectively. That the Hessian is positive definite can be seen by Girshgorin's circle theorem, since the diagonal entries are strictly larger than the absolute row sums by a single entry $E_{1j}$. for the first row block, and similarly for the second. The $O(1)$ gap essentially gives that the typical size of the minimum eigenvalue is $O(1)$. On other hand, the maximum eigenvalue is about 2 times the row sums of E, which is of order $n$. \n\nFor a concrete example, consider the quadratic divergence $f(x)=x^2/2$, in which case $\\psi(\\theta)=\\theta^2/2$ so $\\psi''(\\theta)=1$. Hence the Hessian has diagonal entries all $n$ and the off-diagonal blocks have entries all 1. The eigenvalues for this matrix are $n$ (with multiplicity $2n-3$) and $n\\pm \\sqrt{n(n-1)}$. The same computation holds for general divergence when $\\alpha$, $\\beta$ are constant vectors. \n\nThank you very much for your feedback and questions. We are happy to engage in further discussions.", "claims_and_evidence": "Yes, the theoretical claims are supported by proofs.", "methods_and_evaluation_criteria": "This is a theoretical paper and does not involve numerical experiments.", "theoretical_claims": "I have not checked every detail of the proof, but the overall correctness should be ensured.", "experimental_designs_or_analyses": "This is a theoretical paper and does not involve numerical experiments.", "relation_to_broader_scientific_literature": "The analysis provided by this paper may be used to understand the convergence property of other related optimization problems.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I think this paper is a solid contribution to the understanding of Sinkhorn-type algorithms, given that some popular models are special cases of the generalized SSB. The convergence results are also presented in a clear way, which offer many insights on the behavior of algorithms.", "other_comments_or_suggestions": "Here are a few additional comments aiming at helping the author(s) further improve the article:\n1. Some symbols in Theorem 2.6 may be misused. For example, both $k/k_0$ and $t/t_0$ are used for the iteration number.\n2. The same letter is used in different contexts, which may bring confusions to readers. For example, $t$ is the iteration number in Theorem 2.6 but also the bound constant in equation (18). $\\varepsilon$ is used in Theorems 2.6 and 2.8 but also the regularization parameter of entropic-regularized optimal transport in equation (22).\n3. Typo, above equation (30), $\\mu$ should be $\\lambda$.\n4. This is not mandatory, but it would be interesting to see how the convergence rate of the Sinkhorn algorithm is affected by the regularization parameter $\\varepsilon$ in entropic-regularized optimal transport. Such an analysis might be helpful since it is typically believed that a smaller regularization makes the Sinkhorn algorithm converge slower, and a quantitative analysis would provide more insights.", "questions_for_authors": "This is more of a request for clarification: above equation (9), the text says that the concavity of the objective function is not strict. Is it solely due to the one redundant degree of freedom in $(\\alpha,\\beta)$? Once we remove this redundancy, e.g., by setting $\\alpha_1=0$, does the concavity becomes strict?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A0XTa274gc", "reviewer": "Reviewer_n3cT", "summary": "This paper presents a generalized SSB problem for any divergence and provides a new Sinkhorn-type algorithm to solve this problem. The paper focuses on the formalization of SB in a matrix optimization problem (1). The authors first construct the generalized Kantorovich duality and propose the generalized Sinkhorn algorithm (GSA).\n\n## update after rebuttal\n\nAfter carefully reading the rebuttal, I still feel that this paper needs full numerical evaluation to verify the authors' claims. Therefore, I would like to keep my current score.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful and helpful comments. \n\n**Claims and Evidence**\n\nWhile our work was motivated and inspired by the works the reviewer mentioned, our primary motivation was to identify the core mathematical structures that enable the elegant theory of SA/EOT in a significantly broader setting. In this way we can (1) provide deeper insights on the existing theory of SA/EOT,  (2) bring the powerful and elegant theory of GSA/GSB to many problems in math/stat (that we listed in the introduction), and (3) broaden the already powerful applicability of SA/EOT to GSB problems for new possibility of applications. \n\nFor point (1), existing convergence analysis for EOT (e.g.,  Carlier '22) and boundedness of potentials along the Sinkhorn iterates depend heavily on the specific structure for the entropic divergence $f(x)=x\\log x$ (e.g., separability of the corresponding dual function $\\psi'(\\theta)=\\exp(\\theta)$ leads into close-form Sinkhorn update)  Before this work, it remained unclear whether the essential mathematical structure in the theory of Sinkhorn and EOT can be generalized beyond the single particular divergence function. \n\nFor point (2), we discussed wide applicability of our GSB frameworks that include random graphs, contingency tables in statistics, and random matrices in probability in the introduction. \n\nFor point (3), advantages of using general $f$-divergence include: \n\n1.\tAsymmetry: KL divergence is asymmetric, leading to different behaviors when swapping distributions. Symmetric f-divergences (e.g., Jensen–Shannon) may be preferable, as seen in many GAN variants.\n2.\tTail Sensitivity: KL’s logarithmic nature heavily penalizes tail discrepancies, which isn’t always desirable.\n3.\tRobustness: KL is sensitive to support mismatches and outliers, making it less robust in certain applications.\n\nPotential applications of GSSB/GSA include:\n\n1.\tGANs: Many GAN variants use f-divergences (e.g., Jensen–Shannon, Pearson’s ￼) for better stability. Our GSSB extends these to diffusion/generative models like Schrödinger bridge-based approaches.\n\n2.\tVariational Inference: KL divergence in variational inference favors either mode-seeking (forward) or mass-covering (reverse). Using f-divergences (e.g., α or Rényi divergences) allows finer control, especially for multi-modal posteriors, avoiding mode collapse.\n\n**Theoretical Claims**\n\nWe thank the reviewer for appreciating our results. We would like to point out some key differences between our work and the references the reviews mentioned. \n\n1. (Carlier 2022): Please refer to our earlier discussion for point (1). \n\n2. (Marino and Gerolin 2020) The authors prove asymptotic convergence in the L^p space, but linear convergence was not established. Moreover, again in their work the KL divergence is used, whereas our work addresses for a broad class of divergences. \n\n3. In (Lyu and Mukherjee 2024) Please see the questions section. \n\n\n**Experimental Designs**\n\nWe thank the reviewer for their suggestion. Following this, we add simulations of our GSA method for different f-divergences (https://ibb.co/Q7JRkRF1) with more thorough simulations in the revision.\n\n**Other Strengths and Weaknesses**\n\nWe are not entirely sure which details about theorem 2.6 and 2.8 the reviewer refers to. \n\n**Other Comments Or Suggestions**\n\n1. We are adding experiments for different f-divergences.\n\n2. We thank the reviewer for bringing the Orlicz space paper [1] to our attention. Our setting is indeed closely related to that in [1], where their Young's function corresponds to our $f$-divergence in the discrete setting. However, their Young's function is required to have at least linear growth, which rules out cases like quadratic $x^2$ (e.g., Gaussian prior) divergence. Our work relaxes the class of divergences by only requiring strict convexity of f. Finally, their T-convergence result is asymptotic, but we establish linear convergence with sharp sufficient condition for the rate being dimension-independent. \n\n**Questions**\n\n1. Why GSB? Due to the space constraint, we kindly refer the reviewer to our response to reviewer fQdq in \"Other Strengths and Weaknesses\". \n\n2. (Lyu and Mukherjee '24) The authors consider margin constrained random matrices with i.i.d. entries from distribution $\\mu$ and show that such random matrices are concentrated around a deterministic matrix, called the typical table, in the cut norm. They showed that the typical table is in fact a GSB between the row/column margins with the divergence $f$ being the KL-divergence between the exponential tilting of $\\mu$ from $\\mu$. When $\\mu=Poisson(1)$, the divergence becomes $x\\log x - x$, which is equivalent to the EOT divergence $x\\log x$ since the total sum is constant over set of matrices with fixed row and column sums. In order to cast the typical table problem into the Sinkhorn setting (5), we only need to compute $(f')^{-1}$. The authors showed that this is simply the log of the Laplace transform of $\\mu$.", "claims_and_evidence": "Entropic optimal transport, or SSB, is the standard formulation of regularized OT. This paper deals with a one possible way of generalization where similar results that can be found in EOT literature. In this sense, I think the overall claim of this paper is sound, and overall results can be adopted in the SB theory. However, I have some concern on the significance of the result and justification for general OT researchers regarding necessity to consider GSSB problem (1). The authors are advised to elaborate on the significance of their work for the application side of GSSB.", "methods_and_evaluation_criteria": "This paper does not explicitly propose a method other than the generalized Sinkhorn algorithm. This part must be evaluated in the other section.", "theoretical_claims": "The main theoretical claim of this paper is in the generalization of linear convergence of Sinkhorn. I think the overall results are interesting and well-presented. However, I would like to stress that the majority of results are from the direct interpretation of well-founded results, especially (Carlier, 2022), (Marino and Gerolin, 2020), and (Lyu & Mukherjee, 2024). Since these results are already known, I would like to point out that the theoretical contributions should be considered by the justification of GSSB and GSA.", "experimental_designs_or_analyses": "The experiments for GSA are not provided. Nonetheless, I would like to encourage the authors to at least show basic convergence properties using a (discrete) toy setup for a broader group of audience.", "relation_to_broader_scientific_literature": "Optimal transport and Schrodinger bridge problems has a lot of applications in other ML problems, and other domains such as scientific modeling, natural language processing, economics.", "essential_references_not_discussed": "Essential references are well-discussed and properly placed.", "other_strengths_and_weaknesses": "As I mentioned, I have some questions for the authors of technical details on Theorem 2.6 and 2.8 other than applying some technical SSB results to GSSB in the same manner.\n\nCurrently, my review shows some concerns about the significance of GSA since the linear convergence of Sihkorn is well known. I am open to changing my scores when the authors address my concerns in their rebuttal.", "other_comments_or_suggestions": "* I would like to suggest the authors show an experiment of GSB (other than entropic regularization) using actual code following analysis Cuturi, 2013. \n* There are may possible ways of generalization of OT. For example [1] shows another solid framework for regularized OT problems with mathematical rigor using the Orlicz space. The authors are encouraged to elaborate on contributions of their version of generalization GSA and matrix optimization problem (1).\n\n[1] Lorenz, D., & Mahler, H. (2022). Orlicz space regularization of continuous optimal transport problems. Applied Mathematics & Optimization, 85(2), 14.", "questions_for_authors": "* If both the Sinkhorn algorithm and GSA show linear convergence (see Carlier, 2022), why do we have to consider GSA, knowing that Sinkhorn can be implemented in a very efficient manner and shows an almost perfect solution with just a few iterations in practice (Cuturi, 2013)? \n* It was hard for me to understand recent result of Lyu & Mukherjee, 2024. Could you explain the random matrix theory for Sinkhorn and how you applied the theory into Eq. (5)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0NeoHbNZWz", "reviewer": "Reviewer_fQdq", "summary": "The authors leverage the process of Lyu and Mukherjee'24 to identify the linear convergence of the generalized Sinkhorn algorithm for a general class of metrics and solve the problem suffered by the KL divergence.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and for raising some great questions. \n\n**Theoretical Claims**\n\n>The existing linear results assume a bounded domain or bounded cost functions, while yours do not explicitly specify that in the introduction or assumption section? Am I missing something? The authors did assume if f is 2nd differenable on (A, B), I am not sure if this is a standard assumption of boundedness in the optimization community. I believe this part should be sufficiently clarified or discussed if the boundedness is not required.\n\nWe thank the review for these questions and we will clarify on this point in the revision. Below is our detailed response to the raised questions.  \n\n1. By \"domain\", we believe the reviewer means the domain of the marginal distributions. Since we consider the discrete generalized static Schrodinger bridge (\"GSSB\") problem, our domain is always assumed to be bounded. \n\n2. The EOT setting corresponds to the divergence $f(x)=x\\log x$, which is defined on $(0,\\infty)=(A,B)$ and is twice differentiable. Our framework of GSSB generalizes the divergence to be arbitrary strictly convex and twice-differentiable function on a domain $(A,B)$, which can be arbitrary. Divergences with bounded domain (e.g., Entropy of Binomial $x$, $f(x)=x\\log x + (1-x)\\log (1-x)$ on $(0,1)$) has been used for large deviations rate functions of random graphs with given degree sequence. It is less common, however, in the EOT literature. Our GSSB framework unifies both regimes, but their analysis needs separate treatment (see Thm. 2.7 vs. Thm. 2.8). \n\n3.  The reviewer is correct in that our analysis requires boundedness of cost function, which we expressed in terms of the quantity \n$$\n\\kappa := \\frac{C_{\\max}}{C_{\\min}},\n$$\nwhere $C$ is the cost matrix. Our convergence rate in Thm. 2.6 depends on $\\kappa$ and it blows up if $\\kappa=\\infty$. Specifically in the EOT setting, we have $C_{ij} = \\exp(-c(i,j)/\\epsilon)$ for a cost function $c$, and $\\kappa<\\infty$ only if $c$ is bounded. This point was discussed in eq. (23). Furthermore boundedness of the potential functions also depend on the quantity $\\kappa$ (see Thm. 2.7, Thm. 2.8). \n\n**Other Strengths and Weaknesses:**\n\n>The linear convergence of EOT on bounded cost/ domains is fairly standard. I am unable to determine whether the extension to general metrics is sufficiently significant. I will leave the evaluation of this submission to the other reviewers.\n\nThank you very much for raising this fair point. We will clarify this point better in the revision. Below is our detailed response. \n\n1. Indeed, linear convergence of EOT on bounded cost/domains is well-known in the literature. However, existing convergence analysis and boundedness of potentials along the Sinkhorn iterates depend heavily on the specific structure for the entropic divergence $f(x)=x\\log x$ in EOT (e.g., separability of the corresponding dual function $\\psi'(\\theta)=\\exp(\\theta)$ leads into close-form Sinkhorn update). Before this work, it remained unclear whether the essential mathematical structure in the theory of Sinkhorn and EOT can be generalize beyond the single particular divergence function. Our work identifies the core mathematical structures that enable general theory and methods. \n\n\n\n2. As we have discussed in the introduction, there are many important problems in probability, statistics, and combinatorics that can be cast as a generalized static Schrodinger bridge problem. Our work brings the power and the elegance of Sinkhorn algorithm for computing the corresponding potential functions in these problems. \n\n\n\n3. Another significance is that researchers can now custom-design appropriate divergence function $f$ for their specific domain of application. The entropic divergence $f(x)=x\\log x$ comes form the KL-divergence between probability measures, and certainly KL-divergence is one particular choice that can be used. If one tries to find optimal Schrodinger bridges between data such as text, image, or video, researchers are now free to choose the most effective divergence and can even parameterize it and learn it from the training data. In these regards, we believe our contribution also brings some significant practical implications.\n\n4. We establish linear convergence with sharp sufficient conditions for the rate being dimension-independent, which can be immensely helpful for high-dimensional data such as images and audio.", "claims_and_evidence": "NA", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "The existing linear results assume a bounded domain or bounded cost functions, while yours do not explicitly specify that in the introduction or assumption section? Am I missing something? The authors did assume if f is 2nd differenable on (A, B), I am not sure if this is a standard assumption of boundedness in the optimization community.\n\nI believe this part should be sufficiently clarified or discussed if the boundedness is not required.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "This paper appears to be a fundamental paper extending the Sinkhorn algorithm to a generalized version supporting more general metrics", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "The linear convergence of EOT on bounded cost/ domains is fairly standard. I am unable to determine whether the extension to general metrics is sufficiently significant. I will leave the evaluation of this submission to the other reviewers.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please discuss or clarify the boundedness assumptions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces a generalized formulation of the static Schrödinger bridge (SSB) problem by replacing the standard entropy divergence with a general strictly convex function. It develops a corresponding Sinkhorn-type algorithm, establishes its linear convergence, and identifies conditions where the convergence rate does not depend on the problem’s dimension. The work is recognized as a solid contribution—especially since many well-known models fit within this generalized framework. Although the mathematical claims are well-supported and aligned with known results in entropic optimal transport (EOT), there are concerns regarding its practical significance for the broader optimal transport community. (Further numerical experiment is suggested) The paper motivates the need for general divergence functions by discussing their advantages over the traditional Kullback–Leibler divergence, including improved symmetry, more balanced tail sensitivity, and enhanced robustness.
Decision: Accept (poster)