Research map / Learning theory and algorithms / Optimal transport
Linear convergence of Sinkhorn's algorithm for generalized static Schrödinger bridge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes Sinkhorn's algorithm to static Schrödinger bridges with arbitrary strictly convex divergences f and weights W, proving Kantorovich duality and linear convergence of the iterates under tameness conditions.
Problem
Solving the generalized static Schrödinger bridge (SSB) problem, which minimizes an arbitrary strictly convex f-divergence over matrices with prescribed weighted row/column margins, rather than only the KL/entropy case; existing Sinkhorn convergence guarantees cover only KL.
Approach
Defines a generalized Sinkhorn algorithm (GSA) by replacing the exp/log updates with (f')^{-1} updates, proves a Kantorovich dual with concave objective, shows the update is L∞-nonexpansive so iterates stay bounded, and derives linear convergence of the dual objective gap via strong convexity and smoothness on a compact set; dimension-independent bounds on potentials are given under conditions on
Key results
- Proves linear convergence of the dual objective gap for the generalized Sinkhorn algorithm under tameness of the margin, with asymptotic and non-asymptotic forms (Theorem 2.6).
- Shows the generalized Sinkhorn update is nonexpansive in L∞, giving a priori bounds on potentials (Lemma 3.1).
- Numerical experiments on dimension-100 problems show different f-divergences (KL, Jeffreys, JS, chi-square, binomial, squared Hellinger) converge at different rates, and KL is not always fastest.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use different strictly convex divergences in GSA instead of fixing KL divergence | GSA · Gaussian marginals, 100 × 100, L2 cost, ε = 10 | L1 marginal error convergence rate | Mixed |
| Use different strictly convex divergences in GSA | GSA transport maps · Gaussian marginals, 100 × 100, L2 cost, ε = 10 | transport map | Mixed |
Surprising findings
- KL divergence is not always the fastest-converging f-divergence in the experiments.
- Dimension-independent tameness can fail: the tameness parameter can vanish at arbitrary speed as dimensions grow for general margins.
Limitations
- Linear rate depends on tameness parameter delta and condition number kappa of the cost matrix; large kappa degrades rate.
- Asymptotic result for general margins has k0 depending on dimensions and f, W; dimension-independence only under additional conditions.
- Experiments are small synthetic settings only; no real-data application.
Experimental setup
Metrics: L1 marginal error / gradient norm of dual objective dual objective gap (log-scale) vs iteration
Baselines: Sinkhorn algorithm (KL divergence)
Builds on: Sinkhorn algorithm Carlier linear convergence analysis for entropic OT Lyu & Mukherjee generalized typical table analysis Franklin & Lorenz Hilbert metric convergence
Closest papers by meaning
- Statistical Analysis of the Sinkhorn Iterations for Two-Sample Schr\"{o}dinger Bridge Estimation (NeurIPS 2025 · similarity 0.90)
- Generalized Schrödinger Bridge Matching (ICLR 2024 · similarity 0.89)
- Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres (NeurIPS 2025 · similarity 0.88)
- Light Schrödinger Bridge (ICLR 2024 · similarity 0.87)
- Accelerating Sinkhorn algorithm with sparse Newton iterations (ICLR 2024 · similarity 0.87)
- Light and Optimal Schrödinger Bridge Matching (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.