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

Özetle: A parallel sampler can choose at random which coordinates to generate together.

Özet

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_{mathrm{KL}}(p|q_U)$ with the output-law divergence $D_{mathrm{KL}}(p|mathbb{E}_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 $varepsilon>0$ is $Θ_varepsilon((log n)^2)$ under the first criterion but $(e^{-varepsilon}+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^{-varepsilon}/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_varepsilon((log n)^2)$ upper bounds on both extensions.

Orijinal Özet (İngilizce)

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_{mathrm{KL}}(p|q_U)$ with the output-law divergence $D_{mathrm{KL}}(p|mathbb{E}_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 $varepsilon>0$ is $Θ_varepsilon((log n)^2)$ under the first criterion but $(e^{-varepsilon}+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^{-varepsilon}/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_varepsilon((log n)^2)$ upper bounds on both extensions.

Kaynak: arXiv:2610.13924 · PDF