Randomized parallel sampling improves accuracy beyond deterministic adaptive methods
Randomization Beyond Deterministic Adaptivity in Parallel Sampling
Information Theory
Summary
When collecting data in parallel, deciding which parts to sample and when can affect how well we understand the whole. This work shows that using a little randomness in choosing sample batches can give better results than carefully adapting choices based on previously seen data. The authors prove that for certain data types, random selection outperforms any deterministic approach that changes its strategy based on earlier samples. This finding highlights how randomness can be a useful tool to get more accurate estimates in parallel data collection.
What this means in practice
- •For data engineers: Use randomized batch sampling schedules to improve the accuracy of parallel data collection in large-scale systems with limited rounds.
- •For probabilistic modelers: Incorporate small random choices in coordinate sampling to achieve better convergence properties than adaptive deterministic sampling in complex models.
A theory result. No direct application yet.
Authors
Da Li, Bo Jin, Xiaopeng Wei
Abstract
We study parallel samplers that reveal each coordinate once and draw the coordinates of each batch independently from their exact conditional marginals. Under the same sampling interface and a hard three-round cap, randomization can improve accuracy beyond every deterministic policy that adapts its batches to previously observed values. For an explicit full-support binary family, the optimal deterministic adaptive forward Kullback-Leibler divergence grows linearly with the dimension, while a uniform mixture of four fixed schedules has exponentially small divergence. Only two independent fair bits are needed to select the schedule. We determine the asymptotic additive constant in the deterministic optimum and show that its optimal total variation tends to one quarter. An outward-rounded finite-sum certificate establishes divergence separation at dimension 389. The mechanism combines an irreversible first-batch dependence loss with posterior concentration in the randomized components. A density-coverage lemma describes how their mixture restores the target. A complementary noisy-matching family exhibits a growing round gap for nonadaptive schedules, although uniform random coordinate order still has linear mixture error. These results concern known finite structures and exact conditional marginals.