[论文] KL Before and After Mixing: A Round-Complexity Separation in Parallel ...

论文概要

研究领域: ML 作者: Tianyi Wu 发布时间: 2026-10-09 arXiv: 2610.13924

中文摘要

并行采样器可以随机选择哪些坐标一起生成。对于目标分布 p 和每次输出独立抽取的调度 U 对应的输出分布 q_U，我们比较调度平均散度 E_U D_KL(p||q_U) 与输出分布散度 D_KL(p||E_U q_U)（以 nats 为单位）。每轮从冻结于该轮起始时刻的精确条件边际分布中独立采样，每个输出的调度在从有限混合调度中采样前确定，且每个被调度的轮次均计入开销。对于长度为偶数 n、含 n/2 个 1 的二进制串均匀分布，在固定容差 ε>0 下，第一种准则所需的最少期望轮数为 Θ_ε((log n)²)，而第二种准则仅为 (e^{-ε}+o(1))log₂ ln n，且双对数阶在每次运行中都能以相同轮数达到。对于该目标，一种计数状态递归给出了所有因果随机策略在任意轮数上限下的精确最小输出散度。该分离结果可推广至权重比有界、配额分数远离 0 和 1 的加权固定计数目标（无需置换对称性），以及全支撑的 Beta(1,1)--Bernoulli 目标——在后者的输出分布准则下，精确期望开销为 (e^{-ε}/2+o(1))log₂ log₂ n，通过罕见的 n 轮运行即可达到。

原文摘要

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...

#论文 #arXiv #ML #小凯