CS Paper Radar

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

Yuansi Chen, Yunbum Kook

cs.DS cs.LGmath.OCmath.PRstat.CO ·submitted 2026-08-28 17:43 UTC · v1

Abstract

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.

Comment
36 pages. AI disclosure included

Closest papers

Nearest neighbours by meaning across the whole index.

A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra

cs.DS stat.ML ·2026-08-26 ·Zhao Song, Lichen Zhang
similarity 0.76
Abstract

We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.

0.12

Optimal mixing of random-to-random shuffling on linear extensions

cs.DS math.PR ·2026-11-15 ·Haoran Wang
theory similarity 0.62
Abstract

Uniform sampling of linear extensions is a basic problem in randomized algorithms and the study of finite posets. We prove that the random-to-random shuffle of Ayyer, Schilling, and Thiéry mixes in $O(n\log n+n\log(1/\varepsilon))$ steps on every $n$-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an $\varepsilon$-approximate uniform sampler using $O(n^2(\log n+\log(1/\varepsilon)))$ elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor $1-1/n$ for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound $(n+1)/n^2$.

0.31

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

cs.LG math.PRstat.COstat.ML ·2026-09-23 ·Stefan Oberdörster
similarity 0.58
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.

0.22

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.58
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

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.58
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

Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-08-13 ·Yuchen Xin, Zhihua Zhang
theory similarity 0.58
Abstract

We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target \[ π(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d, \] where \(f\) is \(m\)-strongly convex with \(L_f\)-Lipschitz gradient and \(g\) is convex and \(G\)-Lipschitz. Let \(g_λ\) be the Moreau envelope of \(g\), \(π_λ\) the corresponding smoothed target, and \(a_λ=\operatorname{tr}H_λ\), where \(H_λ\) is the a.e./weak Hessian of \(g_λ\). We show that the leading MYULA discretization error is controlled by the reference active trace \(B_{\mathrm{ref}}\), the average of \(a_λ\) along the heat substep of one MYULA update started from \(π_λ\), rather than by the global curvature bound \(d/λ\). If \(M_λ\) is an a.e. upper bound for \(a_λ\), then, up to logarithmic factors, \[ N \lesssim \frac{1}{m} \left[ L_f + \frac{ τ_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_λ}{\varepsilon_{\mathrm{alg}}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x), \] iterations suffice to ensure \(\sqrt m\,W_2(μ_N,π_λ)\leq\varepsilon_{\mathrm{alg}}\), where \(μ_N\) is the law of the \(N\)-th iterate and \(W_2\) is the quadratic Wasserstein distance. We also prove the Moreau-bias bound \[ \sqrt m\,W_2(π_λ,π) \leq \frac{G^2λ}{4}. \] Thus, choosing \(λ\asymp\varepsilon/G^2\) gives an end-to-end guarantee for \(π\). The universal estimate \(B_{\mathrm{ref}}\leq d/λ\) yields \(\widetilde O(\varepsilon^{-3})\) accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature--tube estimates make \(B_{\mathrm{ref}}\) independent of \(λ\), yielding \(\widetilde O(\varepsilon^{-2})\) for the same classical MYULA kernel.

0.34

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

cs.DM math.PRcs.DS ·2026-10-18 ·Zhidan Li, Kuan Yang
theory similarity 0.57
Abstract · 52 pages

We study the mixing time of the single-site Glauber dynamics for sampling proper $q$-colorings on sparse Erdős-Rényi random graphs $\mathcal{G}(n, d/n)$. We prove that, whenever $q \ge (1 + o_d(1))d$, Glauber dynamics mixes in polynomial time with high probability over $\mathcal{G}(n, d/n)$ for all sufficiently large integers $n$. This improves the previous bound $q = (α^* + o_d(1))d$ where $α^* = 1.7632...$ is the unique solution of $x = \exp(1/x)$ on $[1, \infty)$ by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

0.49

Dimension-free regimes for unadjusted Langevin in ridge-separable models: A subspace robust Wasserstein analysis

cs.LG stat.MLmath.PRmath.ST+1 ·2026-10-22 ·Yuansi Chen, Francesco Pedrotti, Peter A. Whalley
theory similarity 0.57
Abstract · 30 pages, 4 figures

The Unadjusted Langevin Algorithm (ULA) is widely used for high-dimensional Bayesian inference. Classical analyses in Wasserstein-2 distance predict an asymptotic bias and a mixing time that grow with dimension, but this metric is stronger than necessary for many statistical tasks. We instead analyze the bias in subspace robust Wasserstein distance, which controls the mean and arbitrary low-dimensional marginals and is therefore well suited to observables typically estimated in practice. For ridge-separable potentials formed with i.i.d. data, we prove high-probability bounds showing a bell-shaped mixing profile as the number of data points $N$ varies relative to the dimension $d$. In the overparameterized regime, the effective dimension is the rank $N$ of the data-dependent perturbation, leading to complexity depending on $N$ rather than $d$. In the large-sample regime, Gaussian-perturbation estimates yield dimension-free complexity once $N$ is sufficiently large. In contrast, near the proportional regime $\asymp d$, we prove that dimension-free guarantees are impossible in general.

0.14