.png){kind=icon}
.png){kind=icon}
Return
Shifted Composition III: Local Error Framework for KL Divergence
.png){kind=icon}
PRE
AI
DOI：10.1007/s10208-026-09753-x.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Coupling arguments are a central tool for bounding the deviation between two stochastic processes, but traditionally have been limited to Wasserstein metrics. In this paper, we apply the shifted composition rule—an information-theoretic principle introduced in our earlier work [3]—in order to adapt coupling arguments to the Kullback–Leibler (KL) divergence. Our framework combines the strengths of two previously disparate approaches: local error analysis and Girsanov’s theorem. Akin to the former, it yields tight bounds by incorporating the so-called weak error, and is user-friendly in that it only requires easily verified local assumptions; and akin to the latter, it yields KL divergence guarantees and applies beyond Wasserstein contractivity. We apply this framework to the problem of sampling from a target distribution $$\pi $$ . Here, the two stochastic processes are the Langevin diffusion and an algorithmic discretization thereof. Our framework provides a unified analysis when $$\pi $$ is assumed to be strongly log-concave (SLC), weakly log-concave (WLC), or to satisfy a log-Sobolev inequality (LSI). Among other results, this yields KL guarantees for the randomized midpoint discretization of the Langevin diffusion. Notably, our result: (1) yields the optimal $$\widetilde{O}(\sqrt{d}/\varepsilon )$$ rate in the SLC and LSI settings; (2) is the first result to hold beyond the 2-Wasserstein metric in the SLC setting; and (3) is the first result to hold in any metric in the WLC and LSI settings.
Keywords:
Coupling methods
Girsanov’s theorem
Kullback–Leibler divergence
Local error analysis
Markov chain Monte Carlo
Shifted composition
Journal
IF:
2.7
Papers:
69
Citations:
2.4K
Organization
No organization information available