KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling

Key points

• For a target $p$ and the output law $qU$ of a schedule $U$ drawn afresh for each output, we compare the schedule-averaged divergence $\mathbb{E}U D{KL}(p\|qU)$ with the output-law divergence $D{KL}(p\|\mathbb{E}U qU)$, in nats.1
• 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.1
• 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 $\varepsilon>0$ is $Θ\varepsilon((\log n)^2)$ under the first criterion but $(e^{-\varepsilon}+o(1))\log2\ln n$ under the second, and the double-logarithmic order is attainable with the same round count on every run.1
• 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^{-\varepsilon}/2+o(1))\log2\log2n$, attained with rare $n$-round runs.1

Sources (1)

• [1]KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 9, 05:54 PM

  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 $\mathbb{E}_U D_{KL}(p\|q_U)$ with the output-law divergence $D_{KL}(p\|\mathbb{E}_U q_U)$, in nats.

Extractive summary: sentences quoted from the sources.