Exponential convergence rate for Iterative Markovian Fitting
This provides a theoretical guarantee for the convergence rate of IMF, which is incremental as it builds on known convergence results without introducing a new method.
The authors tackled the problem of quantifying the convergence speed of the Iterative Markovian Fitting (IMF) algorithm for the discrete-time Schrödinger bridge problem on a finite state space, establishing for the first time that it exhibits exponential convergence with an explicit contraction factor.
We consider the discrete-time Schrödinger bridge problem on a finite state space. Although it has been known that the Iterative Markovian Fitting (IMF) algorithm converges in Kullback-Leibler divergence to the ground truth solution, the speed of that convergence remained unquantified. In this work, we establish for the first time that IMF exhibits exponential convergence with an explicit contraction factor.