# Shifted Composition III: Local Error Framework for KL Divergence

arXiv: https://arxiv.org/abs/2412.17997 · HTML: https://mlsanity.com/paper/2412.17997/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2024.

## Built on by (most cited first, 7 of 7)

- [Sublinear iterations can suffice even for DDPMs](https://mlsanity.com/paper/2511.04844/) (2025)
- [Pathway to O(√d) Complexity bound under Wasserstein metric of flow-based models](https://mlsanity.com/paper/2512.06702/) (2025)
- [When Langevin Monte Carlo Meets Randomization: New Sampling Algorithms with Non-asymptotic Error Bounds beyond Log-Concavity and Gradient Lipschitzness](https://mlsanity.com/paper/2509.25630/) (2025)
- [Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds](https://mlsanity.com/paper/2506.07614/) (2025)
- [Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data](https://mlsanity.com/paper/2605.11170/) (2026)
- [R'enyi Tracking Bounds for Langevin Dynamics with Moving Targets](https://mlsanity.com/paper/2609.17577/) (2026)
- [Nonlocal Hamiltonian Dynamics on Sparse L'evy Graphs: Spectral Analysis and Multimodal Sampling](https://mlsanity.com/paper/2610.06904/) (2026)

## Abstract (arXiv)

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--in order to adapt coupling arguments to the Kullback-Leibler (KL) divergence. Our framework combine 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 π. Here, the two stochastic processes are the Langevin diffusion and an algorithmic discretization thereof. Our framework provides a unified analysis when π 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 tilde O(√ d/ε) 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.