Query Lower Bounds for Diffusion Sampling¶

会议: NeurIPS 2026
arXiv: 2604.10857
OpenReview: https://openreview.net/forum?id=ZXOqN26lhR
领域: 其他
关键词: 扩散模型, 查询下界, 采样复杂度, 假设检验, 噪声调度

一句话总结¶

首次证明高维扩散采样在多项式精度分数预言机下需要至少 $\widetilde{\Omega}(\sqrt{d})$ 次自适应查询，且必须在至少 $\widetilde{\Omega}(\sqrt{d})$ 个不同噪声尺度上扫描，从信息论层面揭示了多尺度噪声调度的必要性。

研究背景与动机¶

扩散模型已成为现代生成模型的核心支柱，其之所以能在高保真图像生成、视频合成以及科学计算等领域取得巨大成功，关键在于将原本极其困难的高维单步概率分布建模任务分解为沿着连续时间反向扩散的渐进式去噪过程。通过多步迭代查询神经网络估计出的平滑分数函数（smoothed score），扩散采样器能稳定将标准高斯噪声推向复杂的数据流形。然而，采样过程的计算开销完全由神经网络的前向评估次数（即分数查询次数）主导，这推动了大量致力于降低采样步数的研究，例如高阶微分方程求解器（DPM-Solver、UniPC）、优化的离散化步长设计以及流匹配（Flow Matching）与整流流（Rectified Flow）。理论上，近期收敛性上界证明了在有界二阶矩或有界加噪等标准假设下，仅需 $\widetilde{O}(d)$ 次查询即可保证全变差（Total Variation, TV）距离收敛至常数水平。

然而，理论与实践之间存在着耐人寻味的巨大反差：在真实应用中，经验求解器通常只需 10 至 50 步便能生成极具真实感的样本，远少于最差情况下的 $d$ 阶依赖；更重要的是，从信息论视角来看，每次查询平滑分数均返回一个完整的 $d$ 维向量，理论上可提供 $\Omega(d)$ 比特的信息量，且高斯平滑卷积自然将全局几何结构编织进局部梯度中，使得查询看似具备高效探索高维空间的潜力。这便引出了一个根本性的理论疑虑：在高维空间中，利用平滑分数预言机进行扩散采样的内在信息论极限究竟是什么？计算复杂度对维度 $d$ 的多项式依赖是否根本无法规避，还是说有可能被彻底压缩至 $\mathrm{polylog}(d)$ 甚至 $O(1)$？既有针对特定 SDE/ODE 求解器的离散化误差累积下界受限于特定的数值格式，无法回答这一算法无关的本质问题。

本文跳出了分析具体离散化误差的传统思路，从信息论预言机模型出发，直接探究利用平滑分数重构目标分布所需的自适应查询复杂度下界。核心 idea：将扩散采样下界规约至零假设检验问题，构造由高维平面正交圆环乘积码本构成的混合高斯硬分布族与自适应掩码预言机，证明由于高维高斯壳层厚度波动，任何单一噪声尺度仅能在极窄的 $O(\sqrt{d})$ 码本容量窗口内暴露有效信号，迫使任何多项式总预算内的采样算法必须遍历搜索至少 $\widetilde{\Omega}(\sqrt{d})$ 个互不相同的噪声尺度。

方法详解¶

整体框架¶

本文构建了扩散采样的信息论博弈框架：算法 $\mathcal{A}$ 只能自适应地向平滑分数预言机 $\widehat{s}_\sigma(x)$ 提交查询点 $x$ 与噪声尺度 $\sigma$，以获取带有 $L^p$ 误差保证的分数估计；算法的目标是以最少的查询次数输出一个样本 $\widehat{X}$，使得其法则与真实目标分布 $\pi$ 在全变差距离或 Wasserstein 距离下足够接近。证明的核心机制是构造一个无法与均匀全集“零假设”区分的随机种植（planted）混合高斯分布族。在绝大多数噪声尺度下，对抗预言机均可直接返回全集对应的零分数（null score）而不违反 $L^p$ 精度要求；只有当算法恰好猜中与随机隐藏码本大小严格匹配的特定噪声尺度时，查询才能获得有效信息。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：目标分布族与预言机查询设定<br/>维度 d / 支撑集半径 R / 平滑参数 γ / 精度 ε_err"] --> B["硬实例构造：基于二维圆环乘积码本的混合高斯族<br/>b=⌊d/2⌋ 个正交圆环乘积 / 对数码本容量 Θ(d log(R/γ))"]
    B --> C["自适应掩码预言机：基于似然比的双侧平滑截断机制<br/>稀疏侧用平滑掩码屏蔽盲查 / 密集侧平滑收敛至零分布"]
    C --> D["狭窄信息窗口：单噪声尺度下的信息集中与对数码本尺度限制<br/>高维高斯壳层涨落 O(τ^2 √d) / 单噪声仅覆盖 O(√d) 对数容量"]
    D --> E["零假设耦合与采样下界规约：多尺度噪声扫描的必要性证明<br/>对数均匀容量先验 / 盲查耦合至零预言机 / 似然检验函数导出 TV ≥ 0.99"]
    E --> F["输出：查询复杂度下界 Ω(√d) 与必须扫描不同噪声尺度"]

关键设计¶

1. 硬实例构造：基于二维圆环乘积码本的混合高斯族 为建立严苛且具有最强区分度的几何下界，作者摒弃了普通的超立方体离散集合，转而设计了由正交二维平面圆环构成的乘积结构。将 $d$ 维空间划分为 $b = \lfloor d/2 \rfloor$ 个二维子空间，并在每个子空间的半径为 $R$ 的圆周上等间距布置 $M = \lceil \pi R / \gamma \rceil$ 个离散点 $V$。全集支撑集的大小达到 $|V| = M^b$，其对数容量为 $\Theta(d \log(R/\gamma))$，这在数学上为后续多尺度扫描提供了跨越 $\Theta(d \log(R/\gamma))$ 的对数区间，且保持了高维正交独立块的良好集中性。种植目标分布由从全集中独立同分布均匀抽取的 $n$ 个码字 $S = \{Y_1, \dots, Y_n\}$ 构成经验均匀分布，再经过标准差为 $\gamma$ 的高斯平滑获得： $$\pi_S = \nu_S * \mathcal{N}(0, \gamma^2 I_d), \quad \nu_S = \frac{1}{n} \sum_{i=1}^n \delta_{Y_i}$$ 参考的零分布 $\pi_{\mathrm{null}}$ 则是对全部 $M^b$ 个点组成的均匀分布 $\nu_{\mathrm{null}}$ 施加相同的平滑。由此，算法若要成功采样，本质上必须在庞大的全集中定位出这 $n$ 个真实存在的码字。

2. 自适应掩码预言机：基于似然比的双侧平滑截断机制 为确保预言机在向算法隐匿信息的同时严格满足理论界常用的多项式 $L^p$ 精度与全局 Lipschitz 连续性，作者设计了一个双侧自适应掩码预言机。在总噪声尺度 $\tau = \sqrt{\gamma^2 + \sigma^2}$ 下，根据 Tweedie 公式，真实分数由后验均值决定 $s_{S,\tau}(x) = (\mathbb{E}[Y \mid X=x] - x)/\tau^2$。预言机的行为根据码本规模 $n$ 与该尺度下的互信息 $I_\tau$ 分为两侧平滑控制： $$\widehat{s}_{S,\tau}(x) = \begin{cases} s_{\mathrm{null},\tau}(x), & \mathcal{M}_{p,\tau}(S) \le (\varepsilon_{\mathrm{err}}/\tau)^p \\ s_{\mathrm{null},\tau}(x) + \psi_{S,\tau}(x) \nabla r_{S,\tau}(x), & \mathcal{M}_{p,\tau}(S) > (\varepsilon_{\mathrm{err}}/\tau)^p \end{cases}$$ 其中 $r_{S,\tau}(x) = \log(f_{S,\tau}(x) / f_{\mathrm{null},\tau}(x))$ 为经验对数似然比，$\psi_{S,\tau}(x)$ 是一个以 $r_{S,\tau}(x) + \log n - I_\tau + w/2 + 1$ 为自变量的 1-Lipschitz 平滑截断函数。在密集侧（$\log n \ge I_\tau + w$），大数定律与 Bernstein 集中不等式保证种植分布与零分布的分数均方差极小，预言机可完全切换为零分数；在稀疏侧（$\log n \le I_\tau - w$），算法在未命中码字周围时，似然比极低，掩码函数 $\psi_{S,\tau}(x)$ 恒为 0，预言机同样输出零分数。由此构成的预言机处处全局 $O(d)$-Lipschitz，且 $L^p$ 误差严格受控。

3. 狭窄信息窗口：单噪声尺度下的信息集中与对数码本尺度限制 这是下界之所以为 $\widetilde{\Omega}(\sqrt{d})$ 而非更高或更低的核心机制。直觉上，若高斯分布在半径 $\tau \sqrt{d}$ 的球壳上完全均匀，则后验均值仅取决于落在球壳内的码字数量，每个噪声尺度覆盖的多项式窗口可导出 $\Theta(d / \log d)$ 的下界；然而，真实的高维高斯分布在径向距离平方上存在厚度为 $\Theta(\tau^2 \sqrt{d})$ 的次高斯涨落。对于两个相距 $\Theta(\tau^2 \sqrt{d})$ 的半径，其高斯似然权重之比可达 $\exp(\Theta(\sqrt{d}))$，而该厚度壳层内的几何表面积也恰好相差 $\exp(\Theta(\sqrt{d}))$。这种权重与体积的精准抵消效应，导致在固定噪声尺度 $\tau$ 下，后验信号从“完全由于稀疏而无法命中”过渡到“完全由于均值化而抹平差异”之间，存在一个宽度高达 $\exp(\widetilde{\Theta}(\sqrt{d}))$ 的缓冲带。换言之，一个固定的噪声尺度 $\tau$ 只能在对数码字规模满足以下极窄窗口时产生可区分的非零响应： $$|\log n - I_\tau| \le w = O(\sqrt{d H} + H)$$ 其中 $H = \log(d/\varepsilon_{\mathrm{err}}) + \log(R/\gamma)$。在这一窗口之外，任何盲查点获得非零信号的概率被严格压制在多项式极小值 $\delta_d$ 之内。

4. 零假设耦合与采样下界规约：多尺度噪声扫描的必要性证明 为了将单点预言机的不可区分性转化为对采样算法总查询次数与尺度数的强下界，作者将隐藏参数 $\log n$ 置于区间 $[0, m_d]$（其中 $m_d \asymp d \log(R/\gamma)$）上的连续均匀先验分布。由于单个尺度只能覆盖长度为 $O(\sqrt{dH})$ 的对数区间，每次在新的噪声尺度上查询，击中信息窗口的先验概率至多为 $O(w / m_d) = \widetilde{O}(1/\sqrt{d})$。通过构造真实种植执行与纯零预言机执行之间的联合耦合（Coupling），在至多 $Q$ 次查询且使用 $\ell$ 个不同噪声尺度的情况下，算法察觉到差异的总体发散概率满足： $$\mathbb{P}_{S,\Xi}(\mathsf{Div}) \le \frac{C \ell w}{m_d} + Q \delta_d$$ 若不同尺度数量 $\ell \le c B_d$（其中 $B_d = \frac{d \log(R/\gamma)}{\sqrt{dH}+H} = \widetilde{\Omega}(\sqrt{d})$），则算法在极高概率下经历的完全是全集零预言机。通过构造基于平滑对数似然的有界检验统计量 $g_S(x) = \min\{1, (r_{S,\gamma}(x))_+ / m_d\}$，证明算法输出在种植分布下的期望接近 1，而在零耦合输出下的期望接近 0，由此利用全变差的对偶变分特征严格得出 $\mathrm{TV}(\widehat{X}, \pi_S) \ge 1 - \rho \ge 0.99$。

损失函数 / 训练策略¶

本篇纯理论论文探讨的是采样复杂度下界，其核心理论设定关注预言机的误差规范与正则性约束。预言机满足标准多项式 $L^p$ 阶误差界（Assumption 2）： $$\mathbb{E}_{X \sim \pi_\sigma}\left[\|\widehat{s}_\sigma(X) - s_{\pi,\sigma}(X)\|_2^p\right] \le \frac{\varepsilon_{\mathrm{err}}^p}{\sigma^p}, \quad \varepsilon_{\mathrm{err}} = \frac{1}{\mathrm{poly}(d)}$$ 该条件与去噪分数匹配（Denoising Score Matching, DSM）的实际训练目标完全对齐。同时，构造的真实分数与预言机分数处处满足全局 Lipschitz 连续性： $$\mathrm{Lip}(\widehat{s}_{S,\tau}) \le \frac{1}{\tau^2} + \frac{5 R^2 d}{\tau^4}$$ 当推广至亚指数误差尾部假设（Assumption 3）时，误差尾部受到更强的指数控制 $\mathbb{P}(\|\widehat{s}_\sigma(X) - s_{\pi,\sigma}(X)\|_2 \ge z) \le 2\exp(-z\sigma/\varepsilon_{\mathrm{err}})$，此时信息窗口宽度展宽至 $O(d^{3/4})$，对应的查询下界调整为 $\Omega(d^{1/4})$。

实验关键数据¶

主实验¶

论文通过严格数学推导给出了不同预言机模型与距离度量下的查询复杂度下界，并与既有理论上界及特殊假设下的算法复杂度进行了全面对照：

方法 / 理论界	查询复杂度	误差度量	核心假设	意义与结论
DDPM 上界 (Benton 等, 2024)	$\widetilde{O}(d)$	$\mathrm{TV} \le 0.01$	有界二阶矩, $L^2$ 准确分数	既有最紧的通用上界
最小数据假设上界 (Li 等, 2025)	$\widetilde{O}(d)$	$\mathrm{TV} \le 0.01$	紧支撑加噪, $L^2$ 准确分数	确立了一般分布收敛阶
Lipschitz 结构加速 (Zhang 等, 2025)	$\widetilde{O}(L \sqrt{d})$	$\mathrm{TV} \le \varepsilon$	分数全局 $L$-Lipschitz	引入平滑结构时的上界
实例相关加速 (Jiao 等, 2025)	$\widetilde{O}(\min\{d, L^{1/3}d^{2/3}, L d^{1/3}\})$	$\mathrm{TV} \le \varepsilon$	分数高阶 Lipschitz 正则	亚线性步长上界
一维高精度采样 (Chen 等, 2026)	$\mathrm{polylog}(1/\varepsilon)$	$\mathrm{TV} \le \varepsilon$	$d=1$, $L^2$ 准确分数	排除了一维多项式下界
本文主定理 (Theorem 1.3)	$\widetilde{\Omega}(\sqrt{d})$	$\mathrm{TV} \ge 0.99$	有界加噪, $L^p$ 准确分数 ($p \ge 2$)	首个通用下界，排除 $\mathrm{polylog}(d)$
本文 Lipschitz 含义 (Remark 1.4)	排除 $a+b < 1/2$	$\mathrm{TV} \ge 0.99$	$L_\sigma = O(d)$, 形式 $\widetilde{O}(L^a d^b)$	给出 Lipschitz 求解器极限
本文 Wasserstein 界 (Theorem 1.5)	$\widetilde{\Omega}(\sqrt{d})$	$W_q \ge c \sqrt{d}$	有界加噪, $L^p$ 准确分数	无法超越输出原点的平凡界
本文亚指数尾部界 (Theorem 1.6)	$\Omega(d^{1/4})$	$\mathrm{TV} \ge 0.99$	有界加噪, 亚指数误差尾部	强尾部保证下的非平凡下界

消融实验¶

论文在附录 H 中给出了超立方体合成族（$\kappa = 0.2$）的理论代理指标数值仿真，分析了高维壳层占有率、不同噪声机制以及权重扰动对信息窗口的影响：

理论配置 / 机制分支	有效窗口对数宽度 $w$	预言机行为与信息泄漏	对算法查询的要求	对应理论依据
稀疏侧 ($\log n \le I_\tau - w$)	无穷远至 $I_\tau - w$	预言机以 $\ge 1 - \delta_d$ 概率恒等输出零分数	无法获取任何种植样本信号	引理 B.3 / 命题 C.2(a)
**信息窗口 ($	\log n - I_\tau	\le w$)**	$O(\sqrt{dH} + H)$	掩码开启，暴露出有效梯度校正
密集侧 ($\log n \ge I_\tau + w$)	$I_\tau + w$ 至全集容量	混合分布向全集集中，分数均方差极小	预言机直接进入零分支	引理 C.1 / 命题 C.2(b)
理想单壳层高斯 (假设方差为 0)	$O(\log d)$	无壳层厚度抵消，窗口极其尖锐	需要扫描 $\Theta(d/\log d)$ 尺度	论文第 2.1 节预演分析
真实高维高斯壳层涨落	$O(\sqrt{d})$	高斯似然比与表面积精准对消 $\exp(\Theta(\sqrt{d}))$	必须扫描 $\widetilde{\Omega}(\sqrt{d})$ 尺度	核心机理分析与图 3 仿真
多项式重加权码本 ($\\|\eta\\|_\infty \le d^{C_{\mathrm{wt}}}/n$)	窗口漂移 $\le C_{\mathrm{wt}} \log d$	信息窗口仅发生对数级平移，下界不变	依然要求 $\widetilde{\Omega}(\sqrt{d})$ 尺度	命题 E.1 (非均匀权重)
亚指数强误差模型	$O(d^{3/4})$	误差约束更紧，窗口展宽至 $d^{3/4}$	依然要求 $\Omega(d^{1/4})$ 尺度	附录 F / 定理 1.6

关键发现¶

多尺度扫描是算法的内在刚需：下界不仅证明了总查询次数受限于 $\widetilde{\Omega}(\sqrt{d})$，更深刻指出在任何多项式总查询预算 $d^a$ 下，算法都必须在至少 $\widetilde{\Omega}(\sqrt{d})$ 个互不相同的噪声尺度上进行探测，这完美契合了实际中必须使用多步噪声调度（noise schedule）而非固定单尺度去噪的工程实践。
高斯壳层波动的双刃剑效应：高维高斯向量范数的涨落方差为 $\Theta(\tau^2 \sqrt{d})$，这使得似然权重和高维球面表面积发生 $\exp(\Theta(\sqrt{d}))$ 的竞争，将有效信息窗口从直觉上的 $O(\log d)$ 展宽为 $O(\sqrt{d})$，从而精确确立了 $\sqrt{d}$ 这一关键指数。
Lipschitz 加速的理论边界：当目标分布具有 $L$-Lipschitz 连续的分数时，若算法试图取得形如 $\widetilde{O}(L^a d^b)$ 的收敛界，由于本硬实例中 $L = O(d)$，其总复杂度必为 $\widetilde{O}(d^{a+b})$，从而直接封死了 $a+b < 1/2$ 的任何可能性。

亮点与洞察¶

将生成式采样转化为假设检验：不同于常规优化或采样下界直接分析局部梯度方差，本文通过构建对数容量先验与零假设耦合，巧妙将“生成一个好样本”的几何难题简化为“算法能否判断当前预言机是否来自全集”的信息论判别问题。
双侧自适应掩码设计：构造出同时在稀疏侧（依靠盲查失配）和密集侧（依靠均值抵消）完美隐匿真实信号、且处处满足全局 Lipschitz 与 $L^p$ 精度界的分数预言机，技术构思严谨自洽。
理论对工程经验的深刻解释：首次从信息论第一性原理给出了“为什么单步或极少数步扩散采样难以泛化至通用分布”的数学解释，指明了多尺度退火与渐进降噪的本质源于高维信息的尺度局域性。

局限与展望¶

与既有上界仍存在半个维度的理论鸿沟：当前最好的通用算法上界为 $\widetilde{O}(d)$，而本文建立的下界为 $\widetilde{\Omega}(\sqrt{d})$。彻底消除这一 $\sqrt{d}$ 差距是极具挑战的公开问题，可能需要超越假设检验框架，直接量化连续生成流形上样本的概率测度输运代价。
预言机函数类的无约束性：本文构造的对抗掩码预言机虽然严格满足 $L^p$ 精度与 Lipschitz 连续性，但并未显式限制预言机必须来自紧凑的多项式大小神经网络参数族，也未涉及精确分数预言机（exact score）的情形。
未考虑真实数据的低维几何结构：实际图像与文本数据往往集中在低维子流形上或具有多尺度分形结构，探索如何将数据流形的本征维度（intrinsic dimension）纳入信息论下界框架，是弥合“最差理论下界”与“实用少步采样”的关键方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 建立了扩散采样领域首个信息论意义下的查询复杂度下界，从理论上解答了核心悬疑问题。
实验充分度: ⭐⭐⭐⭐ 纯理论开创性工作，数学证明链条严密完整，并配有清晰的合成数据壳层占有率仿真验证。
写作质量: ⭐⭐⭐⭐⭐ 叙述逻辑严丝合缝，从简单几何直觉逐步推演至严谨的多尺度耦合证明，概念极为清晰。
价值: ⭐⭐⭐⭐⭐ 为扩散模型算法加速设定了不可逾越的信息论基石，深刻阐明了多尺度噪声调度的必要性。

方法 / 理论界	查询复杂度	误差度量	核心假设	意义与结论
DDPM 上界 (Benton 等, 2024)	\(\widetilde{O}(d)\)	\(\mathrm{TV} \le 0.01\)	有界二阶矩, \(L^2\) 准确分数	既有最紧的通用上界
最小数据假设上界 (Li 等, 2025)	\(\widetilde{O}(d)\)	\(\mathrm{TV} \le 0.01\)	紧支撑加噪, \(L^2\) 准确分数	确立了一般分布收敛阶
Lipschitz 结构加速 (Zhang 等, 2025)	\(\widetilde{O}(L \sqrt{d})\)	\(\mathrm{TV} \le \varepsilon\)	分数全局 \(L\)-Lipschitz	引入平滑结构时的上界
实例相关加速 (Jiao 等, 2025)	\(\widetilde{O}(\min\{d, L^{1/3}d^{2/3}, L d^{1/3}\})\)	\(\mathrm{TV} \le \varepsilon\)	分数高阶 Lipschitz 正则	亚线性步长上界
一维高精度采样 (Chen 等, 2026)	\(\mathrm{polylog}(1/\varepsilon)\)	\(\mathrm{TV} \le \varepsilon\)	\(d=1\), \(L^2\) 准确分数	排除了一维多项式下界
本文主定理 (Theorem 1.3)	\(\widetilde{\Omega}(\sqrt{d})\)	\(\mathrm{TV} \ge 0.99\)	有界加噪, \(L^p\) 准确分数 (\(p \ge 2\))	首个通用下界，排除 \(\mathrm{polylog}(d)\)
本文 Lipschitz 含义 (Remark 1.4)	排除 \(a+b < 1/2\)	\(\mathrm{TV} \ge 0.99\)	\(L_\sigma = O(d)\), 形式 \(\widetilde{O}(L^a d^b)\)	给出 Lipschitz 求解器极限
本文 Wasserstein 界 (Theorem 1.5)	\(\widetilde{\Omega}(\sqrt{d})\)	\(W_q \ge c \sqrt{d}\)	有界加噪, \(L^p\) 准确分数	无法超越输出原点的平凡界
本文亚指数尾部界 (Theorem 1.6)	\(\Omega(d^{1/4})\)	\(\mathrm{TV} \ge 0.99\)	有界加噪, 亚指数误差尾部	强尾部保证下的非平凡下界

理论配置 / 机制分支	有效窗口对数宽度 \(w\)	预言机行为与信息泄漏	对算法查询的要求	对应理论依据
稀疏侧 (\(\log n \le I_\tau - w\))	无穷远至 \(I_\tau - w\)	预言机以 \(\ge 1 - \delta_d\) 概率恒等输出零分数	无法获取任何种植样本信号	引理 B.3 / 命题 C.2(a)
**信息窗口 ($	\log n - I_\tau	\le w$)**	\(O(\sqrt{dH} + H)\)	掩码开启，暴露出有效梯度校正
密集侧 (\(\log n \ge I_\tau + w\))	\(I_\tau + w\) 至全集容量	混合分布向全集集中，分数均方差极小	预言机直接进入零分支	引理 C.1 / 命题 C.2(b)
理想单壳层高斯 (假设方差为 0)	\(O(\log d)\)	无壳层厚度抵消，窗口极其尖锐	需要扫描 \(\Theta(d/\log d)\) 尺度	论文第 2.1 节预演分析
真实高维高斯壳层涨落	\(O(\sqrt{d})\)	高斯似然比与表面积精准对消 \(\exp(\Theta(\sqrt{d}))\)	必须扫描 \(\widetilde{\Omega}(\sqrt{d})\) 尺度	核心机理分析与图 3 仿真
多项式重加权码本 (\(\\|\eta\\|_\infty \le d^{C_{\mathrm{wt}}}/n\))	窗口漂移 \(\le C_{\mathrm{wt}} \log d\)	信息窗口仅发生对数级平移，下界不变	依然要求 \(\widetilde{\Omega}(\sqrt{d})\) 尺度	命题 E.1 (非均匀权重)
亚指数强误差模型	\(O(d^{3/4})\)	误差约束更紧，窗口展宽至 \(d^{3/4}\)	依然要求 \(\Omega(d^{1/4})\) 尺度	附录 F / 定理 1.6