Non-Uniform Random Scans in Gibbs Sampling and CAVI
Abstract
Gibbs sampling and coordinate ascent variational inference (CAVI) are two basic coordinate-wise methods for statistical computation. Recent analyses under strong log-concavity establish convergence rates for versions of these algorithms that update one uniformly selected block at each step. We extend both results to arbitrary fixed, strictly positive selection probabilities. The rates are governed by a selection-adapted convexity constant λ⋆θ, defined using the block-smoothness constants and the selection probabilities θ. The same constant yields a contraction of relative entropy for the Gibbs sampler and a contraction of the mean-field objective gap for random-scan CAVI. The new bounds recover the uniform-scan results, and are never weaker than the naive comparison based on the smallest selection probability. They provide a principled way to adapt the scan to heterogeneous block geometry using curvature information.
Related
- Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling
- Efficient sampling of the unlabeled structure of uniform random mappings and surjections
- Fast Almost-Uniform Sampling of Random k-SAT Solutions
- Uniform displacement bounds and Gibbs limits for periodic one-dimensional Riesz gases
- Jensen-Bregman split Gibbs sampling
BibTeX
@misc{power2026nonuniform,
title = {{Non-Uniform Random Scans in Gibbs Sampling and CAVI}},
author = {Sam Power},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00408},
eprint = {2609.00408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00408},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Non-Uniform Random Scans in Gibbs Sampling and CAVI
AU - Sam Power
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00408
UR - https://arxiv.org/abs/2609.00408
AB - Gibbs sampling and coordinate ascent variational inference (CAVI) are two basic coordinate-wise methods for statistical computation. Recent analyses under strong log-concavity establish convergence rates for versions of these algorithms that update one uniformly selected block at each step. We extend both results to arbitrary fixed, strictly positive selection probabilities. The rates are governed by a selection-adapted convexity constant λ^⋆_θ, defined using the block-smoothness constants and the selection probabilities θ. The same constant yields a contraction of relative entropy for the Gibbs sampler and a contraction of the mean-field objective gap for random-scan CAVI. The new bounds recover the uniform-scan results, and are never weaker than the naive comparison based on the smallest selection probability. They provide a principled way to adapt the scan to heterogeneous block geometry using curvature information.
ER -