KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
Abstract
A parallel sampler can choose at random which coordinates to generate together. For a target p and the output law qU of a schedule U drawn afresh for each output, we compare the schedule-averaged divergence 𝔼U DKL(p|qU) with the output-law divergence DKL(p|𝔼U qU), in nats. Rounds commit independent draws from exact conditional marginals frozen at the round's start, each output's schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length n with n/2 ones, the least expected number of rounds at a fixed tolerance ε>0 is Θε((log n)2) under the first criterion but (e−ε+o(1))log2ln n under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta(1,1)--Bernoulli target, where the sharp expected cost under the output-law criterion is (e−ε/2+o(1))log2log2n, attained with rare n-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its Oε((log n)2) upper bounds on both extensions.
Related
- Glauber Dynamics for Sampling Colorings: Rapid Mixing above (1+1/e)Δ via Hidden Hard-Core Models
- Randomized Parallel Complexity of Weakly Convex Optimization
- Rapid Mixing of Stereographic MCMC for Heavy-Tailed Sampling
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Randomization Beyond Deterministic Adaptivity in Parallel Sampling
BibTeX
@misc{wu2026before,
title = {{KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling}},
author = {Tianyi Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13924},
eprint = {2610.13924},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13924},
}
RIS
TY - UNPB
TI - KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
AU - Tianyi Wu
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13924
UR - https://arxiv.org/abs/2610.13924
AB - A parallel sampler can choose at random which coordinates to generate together. For a target p and the output law q_U of a schedule U drawn afresh for each output, we compare the schedule-averaged divergence 𝔼_U D_KL(p|q_U) with the output-law divergence D_KL(p|𝔼_U q_U), in nats. Rounds commit independent draws from exact conditional marginals frozen at the round's start, each output's schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length n with n/2 ones, the least expected number of rounds at a fixed tolerance ε>0 is Θ_ε((log n)^2) under the first criterion but (e^−ε+o(1))log_2ln n under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta(1,1)--Bernoulli target, where the sharp expected cost under the output-law criterion is (e^−ε/2+o(1))log_2log_2n, attained with rare n-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its O_ε((log n)^2) upper bounds on both extensions.
ER -