研究者提出并行扩散采样轮数下界

研究者 Yiwen Kou 与 Yimeng Wang 为近似分数下的扩散采样建立了首个多项式并行轮数下界。她们的结果显示：在 R^d 中采样平滑、近各向同性的高斯混合，至少需要 Ω̃(d^{1/3}) 轮；从单位球内各向异性轴对齐盒中均匀采样，至少需要 Ω(d) 轮，后者对该盒族是紧的。 这些下界对任意随机算法成立，即使每轮允许在任意位置和噪声水平做多项式次查询，只要分数误差为多项式倒数、总变差精度为常数。

AI 根据报道生成 · 2 小时前更新

还没有足够的连续观测数据，暂不绘制趋势。