Exponential Convergence Guarantees for Iterative Markovian Fitting

2025/10/23 by Silveri, Marta Gentiloni, Conforti, Giovanni, Durmus, Alain
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.2510.20871

Abstract

The Schrödinger Bridge (SB) problem has become a fundamental tool in computational optimal transport and generative modeling. To address this problem, ideal methods such as Iterative Proportional Fitting and Iterative Markovian Fitting (IMF) have been proposed-alongside practical approximations like Diffusion Schrödinger Bridge and its Matching (DSBM) variant. While previous work have established asymptotic convergence guarantees for IMF, a quantitative, non-asymptotic understanding remains unknown. In this paper, we provide the first non-asymptotic exponential convergence guarantees for IMF under mild structural assumptions on the reference measure and marginal distributions, assuming a sufficiently large time horizon. Our results encompass two key regimes: one where the marginals are log-concave, and another where they are weakly log-concave. The analysis relies on new contraction results for the Markovian projection operator and paves the way to theoretical guarantees for DSBM.

Citations

• Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance
• A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
• Theoretical guarantees in KL for Diffusion Flow Matching
• Adversarial Schrödinger Bridge Matching
• Efficient Sampling on Riemannian Manifolds via Langevin MCMC
• Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case
• Projected Langevin dynamics and a gradient flow for entropic optimal transport
• KL Convergence Guarantees for Score diffusion models under minimal data assumptions
• Error Bounds for Flow Matching Methods
• Quantitative contraction rates for Sinkhorn's algorithm: beyond bounded costs and compact marginals
• Diffusion Schrödinger Bridge Matching
• Stochastic Interpolants: A Unifying Framework for Flows and Diffusions
• Weak semiconvexity estimates for Schrödinger potentials and logarithmic Sobolev inequality for Schrödinger bridges
• Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions
• Building Normalizing Flows with Stochastic Interpolants
• Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions
• GeoDiff: a Geometric Diffusion Model for Molecular Conformation Generation
• Diffusion Schr "odinger Bridge with Applications to Score-Based\n Generative Modeling
• Zero-Shot Text-to-Image Generation
• Score-Based Generative Modeling through Stochastic Differential Equations
• Denoising Diffusion Probabilistic Models
• Language Models are Few-Shot Learners
• Generative Modeling by Estimating Gradients of the Data Distribution
• Sharp convergence rates for Langevin dynamics in the nonconvex setting
• Large-Scale Optimal Transport and Mapping Estimation
• Stochastic Optimization for Large-scale Optimal Transport
• Generalization of an Inequality by Talagrand and Links with the Logarithmic Sobolev Inequality

Related

• Exponential convergence rate for Iterative Markovian Fitting
• Diffusion & Adversarial Schrödinger Bridges via Iterative Proportional Markovian Fitting
• Twisted Schrödinger Bridge Matching
• Diffusion Schrödinger Bridge Matching
• Provably Convergent Schrödinger Bridge with Applications to Probabilistic Time Series Imputation