Linear convergence of Sinkhorn's algorithm for generalized static Schrödinger bridge

We thank the reviewer for their positive comments and for raising some great questions.

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. I believe this part should be sufficiently clarified or discussed if the boundedness is not required.

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

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

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

3. The reviewer is correct in that our analysis requires boundedness of cost function, which we expressed in terms of the quantity

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

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.

Thank you very much for raising this fair point. We will clarify this point better in the revision. Below is our detailed response.

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

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

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

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

We thank the reviewer for their insightful and helpful comments.

Claims and Evidence

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

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

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

For point (3), advantages of using general $f$-divergence include:

1. Asymmetry: 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.
2. Tail Sensitivity: KL’s logarithmic nature heavily penalizes tail discrepancies, which isn’t always desirable.
3. Robustness: KL is sensitive to support mismatches and outliers, making it less robust in certain applications.

Potential applications of GSSB/GSA include:

1. GANs: 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.

2. Variational 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.

Theoretical Claims

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

1. (Carlier 2022): Please refer to our earlier discussion for point (1).

2. (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.

3. In (Lyu and Mukherjee 2024) Please see the questions section.

Experimental Designs

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

Other Strengths and Weaknesses

We are not entirely sure which details about theorem 2.6 and 2.8 the reviewer refers to.

Other Comments Or Suggestions

1. We are adding experiments for different f-divergences.

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

Questions

1. Why GSB? Due to the space constraint, we kindly refer the reviewer to our response to reviewer fQdq in "Other Strengths and Weaknesses".

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

We thank the reviewer for the positive evaluation of our work and further suggestions.

Other Comments or Suggestions

1. Thank you for pointing out this typo, we shall make the change to refer to iteration count by $k$ instead of $t$.
2. In the revision we will maintain $t$ for the upper bound on the tameness condition and use $k$ for the iteration count throughout.
3. Noted and changed.
4. 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

where $C$ here is the cost matrix. Specifically in the EOT setting, we have $C_{ij} = \exp(-c(i,j)/\epsilon)$, so $\kappa$ becomes

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

Questions for Authors

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

We'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

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

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

Thank you very much for your feedback and questions. We are happy to engage in further discussions.