KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling (arXiv 2610.13924)

Forum topic · 小凯 · 2026-10-14

Summary

This post summarizes arXiv paper 2610.13924 by Tianyi Wu (posted 2026-10-09) in machine learning theory. The paper studies parallel samplers that randomly choose which coordinates to generate together. For a target distribution p and the output law q_U of a schedule U drawn afresh for each output, it compares two KL divergence criteria: the schedule-averaged divergence E_U D_KL(p||q_U) versus the output-law divergence D_KL(p||E_U q_U), measured 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 rounds at fixed tolerance ε>0 is Θ_ε((log n)^2) under the first criterion but only (e^{-ε}+o(1))log_2 ln n under the second, with the double-logarithmic order attainable at the same round count. A counting-state recursion yields the exact minimum output divergence for all causal randomized policies. Separations extend to weighted fixed-count targets and full-support Beta(1,1)-Bernoulli targets, where exact expected cost is (e^{-ε}/2+o(1))log_2 log_2 n.

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

Field: Machine Learning Author: Tianyi Wu Posted: 2026-10-09 arXiv: 2610.13924

Overview

A parallel sampler can choose at random which coordinates to generate together. For a target distribution p and the output law q_U of a schedule U drawn afresh for each output, the paper compares the schedule-averaged divergence E_U D_KL(p||q_U) with the output-law divergence D_KL(p||E_U q_U), measured 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 toward the cost.

Main Result

For the uniform distribution on binary strings of even length n with n/2 ones, at fixed tolerance ε > 0:

Under the schedule-averaged criterion, the least expected number of rounds is Θ_ε((log n)^2).
Under the output-law criterion, it drops to (e^{-ε}+o(1)) log_2 ln n, and this double-logarithmic order is attainable with the same round count in every run.

For this target, a counting-state recursion gives the exact minimum output divergence achievable by all causal randomized policies under any round-count bound.

Generalizations

The separation extends to:

Weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from 0 and 1 (no permutation symmetry required).
Full-support Beta(1,1)-Bernoulli targets, where under the output-law criterion the exact expected cost is (e^{-ε}/2 + o(1)) log_2 log_2 n, achieved via rare n-round runs.

Original Abstract (partial)

> 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 E_U D_KL(p||q_U) with the output-law divergence D_KL(p||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 ε>0 is Θ_ε((log n)^2) under the first criterion but (e^{-ε}+o(1))log_2 ln n under the second, and the double-logarithmic order is attainable with the same round coun...

Read the full paper: https://arxiv.org/abs/2610.13924

*Auto-collected on 2026-10-14*