CS Paper Radar

Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler

Stefan Oberdörster

cs.LG math.PRstat.COstat.ML ·submitted 2026-09-23 16:17 UTC · v1

Abstract

Local geometric mixing localizes geometric mixing by requiring geometric convergence to equilibrium in total variation only over finitely many transitions. It accommodates local convergence rates and captures rapid local equilibration, even when global mixing is much slower. We establish and discuss local geometric mixing bounds through Dobrushin contraction. We then apply this approach to Diffusion Path Monte Carlo, a recently proposed Markov chain Monte Carlo method, aimed at leveraging advances in score-based modeling, whose ideal transitions coincide with those of the Proximal Sampler. Our analysis covers both the ideal method and its implementable Metropolis-adjusted counterpart, providing mixing guarantees under minimal assumptions. For the ideal method, these guarantees complement recent spectral gap estimates, which we develop into mixing time bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

High-probability Uniform Mixing via Dobrushin Contraction and Accelerated Hamiltonian Monte Carlo

cs.LG math.PRstat.COstat.ML ·2026-11-16 ·Stefan Oberdörster
theory similarity 0.68
Abstract

Hamiltonian Monte Carlo, since its invention and subsequent rise to widespread use, has been motivated by its ability to accelerate convergence to equilibrium compared to diffusive methods, both in terms of dependence on condition number and dimension. In the present work, we establish this acceleration simultaneously in both aspects for critically damped Metropolis-adjusted kinetic Langevin with persistent uniforms. More precisely, for target measures $μ(dx)\propto e^{-U(x)}dx$ with $m$-strongly convex, $L$-gradient Lipschitz, and $L_H$-Frobenius Hessian Lipschitz potentials, we show that the method mixes to $\varepsilon$-accuracy in total variation using $\mathcal O\bigl((κ^{1/2}+L_H^{1/2}m^{-3/4})\,d^{1/4}\bigr)$ gradient evaluations up to logarithmic factors, both uniformly over starting points in domains of high equilibrium probability and from warm starts. The proof incorporates ideas from previous studies by Bou-Rabee and Chen et al. that show either aspect of acceleration separately, into novel coupling technology. This new coupling technology for general Markov chains extends earlier frameworks aimed at capturing fast local equilibration in the presence of slow global mixing. Specifically, via a weak-$(1,1)$ maximal inequality that follows from Hopf's maximal ergodic theorem, we uncover a stability mechanism in high-probability domains with respect to equilibrium. This enables straightforward localization to naturally arising domains of fast local mixing, and seamlessly fits broad local frameworks via Dobrushin contraction, Wasserstein contraction and local Harris' theorems. We develop the Dobrushin formulation.

0.15

On the Impossibility of Estimating the Average Mixing Time

cs.IT math.ST ·2026-10-07 ·Nathan A. Judd, Amedeo Roberto Esposito
similarity 0.66
Abstract

We establish nearly-matching converse bounds on the sample complexity of estimating the average mixing time of a Markov chain from a single stationary trajectory. Unlike the worst-case mixing time, which maximises the total-variation distance to stationarity over all initial states, the average mixing time averages this distance under the stationary distribution and can therefore be substantially smaller. Our converse bounds establish when estimation is impossible, and match the key dependencies in existing achievability bounds, up to logarithmic factors. Together, these bounds provide nearly-tight PAC guarantees for estimating the average mixing time.

0.18

Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials

cs.LG math.OCmath.PRstat.ML ·2026-10-01 ·Nikolaos Makras, Sotirios Sabanis
theory similarity 0.59
Abstract · 26pages

We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.

0.43

On two proofs of $d^2$ mixing of weighted Dikin walks

cs.DS cs.LGmath.OCmath.PR+1 ·2026-08-28 ·Yuansi Chen, Yunbum Kook
similarity 0.58
Abstract · 36 pages. AI disclosure included

We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\barν$-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis--Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $χ^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $χ^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.

0.09

Rényi Tracking Bounds for Langevin Dynamics with Moving Targets

cs.LG stat.ML ·2026-08-25 ·Yuchen Xin, Jingxin Zhan, Zhihua Zhang
similarity 0.57
Abstract

We study Langevin diffusion and Langevin Monte Carlo (LMC) when the target distribution changes over time. Under a log-Sobolev inequality (LSI), we derive non-asymptotic Rényi-divergence guarantees for tracking the current target. The framework covers continuous-time Langevin diffusion and its discretizations. We then apply the results to nonsmooth sampling based on successive Moreau envelopes. For this scheme, we give explicit choices of the smoothing parameters and step sizes, together with corresponding complexity bounds. To our knowledge, these are the first non-asymptotic Rényi-divergence tracking bounds for Langevin dynamics with discrete target updates.

0.33

Direct Intermediate Initialization for Tilted Diffusion Samplers

cs.LG stat.ML ·2026-10-05 ·Gregory D. Bellchambers
publishedbenchmark similarity 0.57
Abstract · Accepted at the NeurIPS 2026 Workshop on AI for Stochastic Dynamics (STODY)

Some diffusion posterior samplers construct Gaussian-tilted intermediate distributions along the reverse process. We observe that these targets can be pulled back to clean-space posteriors with weaker conditioning, with samples transported analytically to the corresponding noisy-space target through a Gaussian bridge. For the sequential Monte Carlo (SMC) sampler MCGDiff, the effective observation variance of this pulled-back problem is up to twice the diffusion-noise variance. We exploit this structure to initialize MCGDiff directly at an intermediate time: an approximate solver samples the softened clean-space posterior, the Gaussian bridge maps these samples to the tilted target, and only the remaining SMC suffix is run. This trades asymptotic consistency for finite-particle performance. With moment-matching posterior sampling (MMPS) as the solver, the hybrid improves sliced Wasserstein distance by roughly $2\times$ at matched particle count on a structured Gaussian-mixture inverse problem, and by more than an order of magnitude when the posterior-relevant mode is rare under the prior. A prior-initialization control, which retains the bridge but drops the clean-space conditioning, shows that on MCGDiff's standard Gaussian-mixture benchmark most of the improvement is insensitive to the conditioning. Conditioning the initialization gives a further consistent gain on the structured problem, and becomes decisive on a rare-mode problem, where resampling cannot repopulate a mode absent from the initial population.

0.35

Metropolized backward sampling for conditional sequential Monte Carlo

eess.SP stat.COmath.PRstat.ME+1 ·2026-10-28 ·Adrien Corenflos
theory similarity 0.57
Abstract · 12 pages + appendix. A Lean formalization was AI-generated after the draft of the paper was written as an experiment. I have subsequently ed…

Particle Gibbs samplers with backward sampling are widely used for sampling the smoothing distribution of state-space models, but, with few particles, the new trajectory often coincides with the current one at many time steps. A known but rarely used remedy replaces the random selection of the final particle by a Metropolis--Hastings move which avoids the current particle. We show that, with backward sampling, this remedy only helps at the last time steps, because its effect on the update rates decays geometrically with the distance to the final time. We propose instead Metropolized backward sampling, which makes such a move at every step of the backward pass, forcibly switching trajectories whenever possible. Additionally, we introduce a coupled version which prevents proposing the current trajectory, maximizing the chances of an actual switch versus the current trajectory and performing perfect sampling when the state-space model has no observations, a feature not shared by backward sampling. We prove that, at every time step, both methods dominate backward sampling as they update the state more often and have smaller lag-one autocorrelations than it does. Our methods are drop-in replacements for backward sampling, and can be used to improve any particle Gibbs sampler.

0.27

Direct Conditional Transition Sampling for Diffusion Inverse Problems

cs.CV stat.ML ·2026-09-13 ·Qi Yu, Hanlin Wu, Xiaohui Sun
similarity 0.56
Abstract

Training-free diffusion inverse solvers typically choose between local measurement guidance and costly clean-space posterior updates. Independent posterior refresh can improve global correction by sampling a clean conditional and re-noising it, but its practical realization requires probability-flow ODE integration and clean-space Markov chain Monte Carlo (MCMC). We propose Direct Conditional Transition Sampling (DCTS), a direct stochastic-flow approximation to the same ideal refresh target. Rather than explicitly drawing a clean sample, DCTS estimates the measurement-conditioned clean mean along a short inner path and transports Gaussian source noise directly to the next noisy state. A denoiser-compatible sufficient statistic and a covariance-scaled operator update enable this conditional-mean estimation. Experiments on four inverse problems demonstrate that DCTS achieves competitive reconstruction quality with up to $16.8\times$ speedups over competing methods.

0.06