Exponential convergence rate for Iterative Markovian Fitting

• URL: http://arxiv.org/abs/2508.02770v1
• Date: Mon, 04 Aug 2025 09:48:21 GMT
• Title: Exponential convergence rate for Iterative Markovian Fitting
• Authors: Kirill Sokolov, Alexander Korotin,
• Abstract summary: Iterative Markovian Fitting (IMF) algorithm converges in Kullback-Leibler divergence to the ground truth solution.<n>We establish for the first time that IMF exhibits exponential convergence with an explicit contraction factor.
• Score: 58.760054965084656
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the discrete-time Schr\"odinger 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.

Related papers

• Diffusion & Adversarial Schrödinger Bridges via Iterative Proportional Markovian Fitting [87.37278888311839]
  Iterative Markovian Fitting (IMF) procedure successfully solves the Schr"odinger Bridge (SB) problem.<n>We show a close connection between IMF and the Iterative Proportional Fitting (IPF) procedure.<n>We refer to this combined approach as the Iterative Proportional Markovian Fitting (IPMF) procedure.
  arXiv  Detail & Related papers  (2024-10-03T15:43:17Z)
• Sixth-order time-convolutionless master equation and beyond: Late-time resummations, two types of divergences, and the limits of validity [1.7620619500719317]
  We analyze the time-convolutionless (TCL) master equation, expanded to order 2n.<n>We show that while van Kampensants suppress early-time secular growth, they ultimately diverge at long times.<n>For exponentially decaying correlations, the method recovers a proper Markovian limit below a critical coupling threshold.
  arXiv  Detail & Related papers  (2024-06-16T22:15:07Z)
• Non-Markov quantum belief propagation [0.0]
  We provide a rigorous proof of approximate convergence of sliding-window quantum belief-propagation. In particular, we confirm the hypothesis outlined in this work that the approximation error of each step in the belief-propagation algorithm decreases exponentially with the sliding-window size.
  arXiv  Detail & Related papers  (2024-06-10T15:20:23Z)
• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies [7.70133333709347]
  We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output.
  arXiv  Detail & Related papers  (2024-05-02T16:15:46Z)
• Softening of Majorana edge states by long-range couplings [77.34726150561087]
  Long-range couplings in the Kitaev chain is shown to modify the universal scaling of topological states close to the critical point. We prove that the Majorana states become increasingly delocalised at a universal rate which is only determined by the interaction range.
  arXiv  Detail & Related papers  (2023-01-29T19:00:08Z)
• Rigorous convergence condition for quantum annealing [0.0]
  We derive a generic bound on the rate of decrease of transverse field for quantum annealing to converge to the ground state of a generic Ising model. Our theorem is based on a rigorous upper bound on the excitation probability in the infinite-time limit.
  arXiv  Detail & Related papers  (2022-07-25T12:05:59Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Determination of the critical exponents in dissipative phase transitions: Coherent anomaly approach [51.819912248960804]
  We propose a generalization of the coherent anomaly method to extract the critical exponents of a phase transition occurring in the steady-state of an open quantum many-body system.
  arXiv  Detail & Related papers  (2021-03-12T13:16:18Z)
• On the Local Linear Rate of Consensus on the Stiefel Manifold [39.750623187256735]
  We restrict the convergence of properties of the Stfelian gradient over the Stiefel problem (for an un connected problem) The main challenges include (i) developing a technical for analysis, and (ii) to identify the conditions (e.g., suitable step-size and under which the always stays in the local region) under which the always stays in the local region.
  arXiv  Detail & Related papers  (2021-01-22T21:52:38Z)
• A Unified Linear Speedup Analysis of Federated Averaging and Nesterov FedAvg [49.76940694847521]
  Federated learning (FL) learns a model jointly from a set of participating devices without sharing each other's privately held data. In this paper, we focus on Federated Averaging (FedAvg), one of the most popular and effective FL algorithms in use today. We show that FedAvg enjoys linear speedup in each case, although with different convergence rates and communication efficiencies.
  arXiv  Detail & Related papers  (2020-07-11T05:59:08Z)
• The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
  We introduce a new convergence indicator that can be used to calculate whether the particles will finally converge to a single point or diverge. Using this convergence indicator we provide the actual bounds completely characterizing parameter regions that lead to a converging swarm.
  arXiv  Detail & Related papers  (2020-06-06T19:08:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.