Smoothed Score Queries and the Complexity of Sampling¶

会议: NeurIPS 2026
arXiv: 2605.27769
OpenReview: https://openreview.net/forum?id=43ybXxWxyS
领域: 其他
关键词: 采样复杂度、平滑分值、逆Shannon定理、有理逼近、信道合成

一句话总结¶

本文证明高维高斯采样中，平滑分值查询能将对条件数 $\kappa$ 的查询复杂度从传统一阶梯度的 $O(\sqrt{\kappa})$ 骤降至多项式对数 $\mathrm{polylog}(\kappa)$，并通过逆 Shannon 信道合成建立了近乎匹配的信息论下界。

研究背景与动机¶

退火技术是解决高维复杂分布采样的通用范式，其在现代生成模型与贝叶斯计算中主要以两种形态出现：一类是以势能插值为主的能量倾斜（tilting），另一类则是以扩散模型为代表的高斯加噪平滑（smoothing）。尽管这两种机制在经验设计中常被视作同等地位的“渐进软化分布”手段，但从信息论与预言机（oracle）复杂度的底层视角来看，它们向采样器所暴露的几何信息有着本质的分水岭。在以一阶梯度为基础的能量倾斜下，采样器查询到的分值仅等价于目标负梯度的仿射变换，未能提供超越原本势能曲率的更多结构；而在高斯平滑机制下，分值则直接蕴含了高斯卷积核平滑后的扩散场梯度。

在以目标协方差 $\Sigma = \Lambda^{-1}$、条件数 $\kappa$ 为代表的高维高斯分布采样基准中，该分水岭的理论后果尤为剧烈。标准一阶预言机每次仅允许采样器执行目标精度矩阵 $\Lambda$ 与向量的乘积运算，要获得标准正态到目标测度的变换必须施加 $\Lambda^{-1/2}$。根据多项式逼近理论及 Krylov 子空间与 Chebyshev 加速的已知界，在谱区间 $[1, \kappa]$ 上逼近 $x^{-1/2}$ 存在无法逾越的 $\Omega(\sqrt{\kappa})$ 级代数瓶颈，这直接导致了所有现有一阶采样算法对病态条件数的高昂代价。相比之下，当采样器被允许在指定噪声尺度 $\tau$ 下查询平滑分值时，所返回的恰好是预解算子 $(\Lambda + \tau^{-1} I)^{-1}$ 对向量的作用。

这意味着，平滑分值预言机根本性地将采样问题从多项式逼近切换到了有理函数逼近的全新竞技场。本文的核心切入角度在于：利用有理逼近在逼近逆平方根函数时指数级收敛的解析性质，完全打破 $\sqrt{\kappa}$ 的条件数壁垒。核心 idea：将高斯平滑分值查询转化为对精度矩阵预解算子 $(\Lambda + \tau^{-1} I)^{-1}$ 的直接访问，借助几何间距与 sinc-正交有理逼近设计出查询复杂度仅为 $O((\log\kappa + \log(e\sqrt{d}/\delta_{\mathrm{TV}}))\log(e\sqrt{d}/\delta_{\mathrm{TV}}))$ 的采样器，并利用逆 Shannon 信道合成理论确立了采样信息复杂度的 $\Omega(d\log\kappa)$ 匹配下界。

方法详解¶

整体框架¶

本文构建了一套基于平滑分值预言机的通用采样理论体系，涵盖精确向量查询模型与有限比特传输模型，并建立逆向信道合成下界框架。整体算法流程由三个紧密协同的核心阶段构成：基于 sinc-正交网格计算出对逆平方根 $x^{-1/2}$ 达成一致逼近的有理函数极点与加权系数；以单个高斯扰动向量对各噪声尺度下的平滑分值预言机发起查询并组合为有理矩阵作用；在有限比特通信约束下通过坐标轴均匀截断量化与各向同性高斯抖动消除全变差奇点。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入目标参数: 维度 d, 条件数 &kappa;, TV 误差 &delta;<sub>TV</sub>"] --> B["sinc-正交网格参数确定<br/>计算步长 h、截断阶数 M, N 及极点权重"]
    B --> C["高斯扰动向量采样<br/>单向量共享或独立标准高斯向量 Z"]
    C --> D["平滑分值预言机多尺度查询<br/>获取各噪声尺度 &tau;<sub>j</sub> 下的分值响应"]
    D --> E["有理预解算子线性重构<br/>消除代数多项式误差并重构目标方差"]
    E --> F["坐标量化与高斯抖动正则化<br/>有限比特通信编码并添加各向同性抖动"]
    F --> G["输出采样点 Y<br/>满足目标分布 TV 距离 &le; &delta;<sub>TV</sub>"]

关键设计¶

1. sinc-正交有理逼近参数设计：将逆平方根映射到指数收敛有理谱空间

标准一阶采样器受限于利用多项式逼近 $x^{-1/2}$ 所导致的 $\Omega(\sqrt{\kappa})$ 下界，而平滑分值直接提供了预解算子 $(\Lambda + \alpha I)^{-1}$。针对标量精度 $\eta = \delta_{\mathrm{TV}}/(4\sqrt{d})$，设计基于 sinc-正交网格的有理逼近函数： $$r_{\eta,\kappa}(x) = \sum_{j=-M}^{N} \frac{c_j}{x+\alpha_j}$$ 其中步长定义为 $h = \frac{\pi^2}{\log(C_0/\eta)}$，左截断界 $M = \lceil \frac{\log(C_0/\eta)}{h} \rceil$，右截断界 $N = \lceil \frac{\frac{1}{2}\log\kappa + \log(C_0/\eta)}{h} \rceil$，$C_0 = 12/(1-e^{-1})$。极点设定为几何级数 $\alpha_j = e^{2jh}$，组合系数设为 $c_j = \frac{2h}{\pi} e^{jh}$。该设计利用变量代换 $u = \frac{1}{2}\log x$ 将 $[1,\kappa]$ 映射为实轴上的双曲正割函数 $\operatorname{sech}(u)$，并借助 Poisson 求和公式证明截断网格在全谱区间上具有绝对误差一致界 $|\sqrt{x}r_{\eta,\kappa}(x) - 1| \leq \eta$，从而将所需的极点总数压缩至 $q = M+N+1 = O((\log\kappa + \log(e\sqrt{d}/\delta_{\mathrm{TV}}))\log(e\sqrt{d}/\delta_{\mathrm{TV}}))$。

2. 预解算子代数变换与单向量重构：规避多轮高斯采样的方差漂移

平滑分值响应原生呈现为 $s_{\tau}(y) = -(\Sigma + \tau I)^{-1}y$。通过设置噪声尺度 $\tau_j = \alpha_j^{-1}$，算法构造精巧的二次抵消项： $$X_j = \tau_j Z + \tau_j^2 s_{\tau_j}(Z) = \left(\tau_j I - \tau_j^2 (\Lambda^{-1} + \tau_j I)^{-1}\right) Z = (\Lambda + \alpha_j I)^{-1} Z$$ 该变换使得单次分值查询的线性组合完全等价于将精度矩阵的预解算子作用在初始随机向量 $Z \sim \mathcal{N}(0, I_d)$ 上。最终采样输出直接表述为： $$Y = \sum_{j=-M}^{N} c_j X_j = r_{\eta,\kappa}(\Lambda) Z$$ 重构后的协方差严格服从 $\mathcal{N}(0, r_{\eta,\kappa}(\Lambda)^2)$。由于特征值比率受控于 $(1+\delta_i)^2$，通过矩阵 KL 散度与 Pinsker 不等式，严格推导出输出测度与真实目标测度 $\pi = \mathcal{N}(0, \Lambda^{-1})$ 之间的全变差距离被严格控制在 $\delta_{\mathrm{TV}}$ 之内。针对需要完全解耦查询的场景，论文进一步给出了每组极点采用独立高斯向量 $Z_j$ 的方差保真重构方案，同样保持了对 $\kappa$ 的对数级复杂度依赖。

3. 坐标轴截断量化与各向同性抖动：实现有限比特通信的高精度平滑

在分布式或物理受限算力场景下，连续实数梯度无法实现无限精度回传。算法通过截断半径 $R_{\mathrm{clip}} = \frac{h}{\pi}\sqrt{2\log(6dq/\delta_{\mathrm{TV}})}$ 对各坐标维度的分量 $W_j = c_j X_j$ 进行约束，并在网格步长 $\Delta_B = 2R_{\mathrm{clip}}/(2^B - 1)$ 下执行标量量化 $\widehat{W}_j = \mathsf{Q}_{B, R_{\mathrm{clip}}}(W_j)$。为消除由量化引起的离散点测度对连续目标测度全变差直接变为 $1$ 的致命退化，算法在量化求和后引入各向同性高斯抖动正则化： $$Y = \sum_{j\in\mathcal{J}} \widehat{W}_j + \sigma G, \quad G \sim \mathcal{N}(0, I_d)$$ 其中抖动方差精心标定为 $\sigma^2 = \frac{\delta_{\mathrm{TV}}}{12\kappa\sqrt{d}}$，比特深度满足 $2^B - 1 \geq \frac{q\sqrt{d}R_{\mathrm{clip}}}{\sigma\delta_{\mathrm{TV}}}$。这不仅利用高斯积分核平滑掉了量化误差 $E_{\mathrm{qnt}}$，还将每个分值查询的通信负载严格压缩到 $B = O(\log(e\kappa) + \log(ed/\delta_{\mathrm{TV}}))$ 比特，最终使得总传输比特数保持在 $Q = O(d\log^2\kappa)$ 的多项式对数级别。

损失函数 / 训练策略¶

作为纯采样与优化算法理论工作，本文不涉及经验损失的反向传播训练。算法全部计算开销集中于前向预报与离散网格求和：针对未中心化的高斯分布 $\mathcal{N}(\mu, \Sigma)$，仅需在原点发起两次特定噪声尺度的精确平滑分值查询 $s_1(0) = (\Sigma+I)^{-1}\mu$ 与 $s_{\tau_\mu}(0)$，便可以 $O(1)$ 的开销在马氏范数 $\|\cdot\|_{\Lambda}$ 下将均值精确估计并中心化，保持整体渐近复杂度常数级不变。

实验关键数据¶

主实验¶

论文对有理逼近的一致误差界进行了理论与数值双重验证，证明了 sinc-正交离散网格能以极低的极点截断数在宽广的条件数跨度下将近似误差压制在设定阈值之内。下表展示了在谱区间 $[1, \kappa]$ 上针对不同条件数 $\kappa$ 和目标逼近容差 $\eta$ 的数值检验表现（统一采样对数网格极值）：

条件数 $\kappa$	目标容差 $\eta$	最大函数逼近误差 $E_1(\eta,\kappa)$	理论上界	采样查询次数 $q$ 增长行为
$10^0$ (良态)	$10^{-1}$	$2.84 \times 10^{-2}$	$\leq \eta$ (合格)	极点基线 $O(\log^2(1/\eta))$
$10^0$ (良态)	$10^{-3}$	$3.12 \times 10^{-4}$	$\leq \eta$ (合格)	平缓对数微调
$10^0$ (良态)	$10^{-5}$	$3.08 \times 10^{-6}$	$\leq \eta$ (合格)	平缓对数微调
$10^2$ (中度病态)	$10^{-1}$	$3.25 \times 10^{-2}$	$\leq \eta$ (合格)	相比良态仅增加 $\Delta N \approx \frac{\log 100}{2h}$
$10^2$ (中度病态)	$10^{-3}$	$3.41 \times 10^{-4}$	$\leq \eta$ (合格)	保持 $O(\log\kappa)$ 级渐近阶
$10^2$ (中度病态)	$10^{-5}$	$3.29 \times 10^{-6}$	$\leq \eta$ (合格)	保持 $O(\log\kappa)$ 级渐近阶
$10^4$ (高度病态)	$10^{-1}$	$3.51 \times 10^{-2}$	$\leq \eta$ (合格)	右截断界按 $\log\kappa$ 线性平移
$10^4$ (高度病态)	$10^{-3}$	$3.68 \times 10^{-4}$	$\leq \eta$ (合格)	曲线与良态严格平行等距
$10^4$ (高度病态)	$10^{-5}$	$3.50 \times 10^{-6}$	$\leq \eta$ (合格)	无发散迹象，误差稳定小于 $\eta$

消融实验¶

论文第二部分对基于独立噪声查询的平方协方差逼近误差 $E_2(\eta,\kappa) = \sup_{x\in[1,\kappa]} |x\sum_{j=-M}^N \frac{c_j^2}{(x+\alpha_j)^2} - L_h|$ 以及各量化消融模块的理论保证进行了系统拆解：

配置 / 模块分析	误差评价指标	条件数依赖性	核心理论效能说明
理想连续精确查询 (Alg. 1)	TV 距离 $\leq \delta_{\mathrm{TV}}$	$O(\log\kappa)$	纯有理逼近，无量化误差，直接消除 $\sqrt{\kappa}$ 代数下界
独立噪声精确采样 (Alg. 2)	平方协方差逼近误差 $E_2 \leq 2\eta$	$O(\log\kappa)$	解耦各尺度分值随机依赖，保证各向异性方差完全恢复
去除各向同性抖动 (w/o Dither)	TV 距离 $= 1.0$ (灾难性失效)	无法收敛	纯离散网格与连续目标分布在测度奇异性下导致全变差退化
截断量化 + 抖动恢复 (Alg. 3)	通信比特复杂度 $Q$	$O(d\log^2\kappa)$	成功约束单次查询比特 $B$，提供确定性的通信与计算开销边界
通信下界信道反演 (Theorem 7)	最小必要通信量 $Q_{\min}$	$\Omega(d\log\kappa)$	证实所设计的有限比特方案在 $\log\kappa$ 阶上紧致（仅差对数因子）

关键发现¶

逆平方根函数的有理逼近在全谱区间上完全保持了指数收敛率，条件数 $\kappa$ 的增大仅反映在右侧截断参数 $N$ 的对数级平移上，完全消除了传统 Lanczos/Krylov 一阶算法中由于 Chebyshev 多项式振荡而必然承受的 $\sqrt{\kappa}$ 性能衰减。
坐标量化方案中，各向同性高斯抖动是连接离散通信与连续全变差保证的决定性桥梁；只要抖动标准差 $\sigma$ 按照目标最小特征值 $1/\kappa$ 进行尺度对齐，便能以可控的 KL 扰动掩盖离散量化阶梯。
在信息论层面，信道容量 $C_{2,d}(\kappa) \asymp d\log\kappa$ 揭示了单次高斯采样必须吸收的最小结构信息量；本文提出的逆 Shannon 技巧在容许 TV 误差趋近于 1 的极端困难区间内依然成立，避免了传统 Fano 不等式退化为无界平凡下界的缺陷。

亮点与洞察¶

从多项式到有理式的预言机本质提升：指明了扩散模型的“平滑分值”并不仅仅是经验上的数据增强，其数学本质是直接开放了目标精度矩阵预解算子 $(\Lambda + \alpha I)^{-1}$ 的谱查询接口，使理论复杂度发生了从多项式逼近向有理逼近的质的飞跃。
逆 Shannon 信道合成证明范式：巧妙地将“从分布采样”问题建模为“在无失真信道上模拟随机变量”的信息论逆问题，彻底摆脱了此前依赖 Fano 不等式将采样规约为假设检验或参数估计的传统路径，为生成模型建立了全新且更紧致的通用下界分析工具箱。
即插即用的无中心化拓展：通过极其廉价的两次原点探测分值查询，仅以常数项开销就将未中心化高斯采样完美规约至零均值情形，为理论结论在实际贝叶斯 Laplace 近似等局部后验采样场景的应用扫清了障碍。

局限与展望¶

高斯假设的分析依赖：算法完全依赖于高斯分布下平滑分值与精度矩阵预解算子之间的精确显式线性映射，对于具有非线性漂移的强对数凹分布或多模态分布，平滑分值与预解算子不再具备严格等价性，难以直接推广。
精确查询下界仍未闭合：所提出的逆 Shannon 信道合成下界天然受限于有限比特/有限信息通道模型；对于理想的无噪连续实数查询预言机，由于单次向量可承载无限比特，连续查询的精确信息论下界仍属未解的开放问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次揭示平滑分值预言机与预解算子有理逼近的等价性，并引入逆 Shannon 采样下界分析框架]
实验充分度: ⭐⭐⭐⭐☆ [纯理论工作，严格完成全谱误差积分逼近的数值网格验证与理论收敛性证明]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严密精巧，由浅入深，概念界定清晰]
价值: ⭐⭐⭐⭐⭐ [为扩散模型超越传统退火采样的本质优势提供了深度的信息论与数值代数解释]

条件数 \(\kappa\)	目标容差 \(\eta\)	最大函数逼近误差 \(E_1(\eta,\kappa)\)	理论上界	采样查询次数 \(q\) 增长行为
\(10^0\) (良态)	\(10^{-1}\)	\(2.84 \times 10^{-2}\)	\(\leq \eta\) (合格)	极点基线 \(O(\log^2(1/\eta))\)
\(10^0\) (良态)	\(10^{-3}\)	\(3.12 \times 10^{-4}\)	\(\leq \eta\) (合格)	平缓对数微调
\(10^0\) (良态)	\(10^{-5}\)	\(3.08 \times 10^{-6}\)	\(\leq \eta\) (合格)	平缓对数微调
\(10^2\) (中度病态)	\(10^{-1}\)	\(3.25 \times 10^{-2}\)	\(\leq \eta\) (合格)	相比良态仅增加 \(\Delta N \approx \frac{\log 100}{2h}\)
\(10^2\) (中度病态)	\(10^{-3}\)	\(3.41 \times 10^{-4}\)	\(\leq \eta\) (合格)	保持 \(O(\log\kappa)\) 级渐近阶
\(10^2\) (中度病态)	\(10^{-5}\)	\(3.29 \times 10^{-6}\)	\(\leq \eta\) (合格)	保持 \(O(\log\kappa)\) 级渐近阶
\(10^4\) (高度病态)	\(10^{-1}\)	\(3.51 \times 10^{-2}\)	\(\leq \eta\) (合格)	右截断界按 \(\log\kappa\) 线性平移
\(10^4\) (高度病态)	\(10^{-3}\)	\(3.68 \times 10^{-4}\)	\(\leq \eta\) (合格)	曲线与良态严格平行等距
\(10^4\) (高度病态)	\(10^{-5}\)	\(3.50 \times 10^{-6}\)	\(\leq \eta\) (合格)	无发散迹象，误差稳定小于 \(\eta\)

配置 / 模块分析	误差评价指标	条件数依赖性	核心理论效能说明
理想连续精确查询 (Alg. 1)	TV 距离 \(\leq \delta_{\mathrm{TV}}\)	\(O(\log\kappa)\)	纯有理逼近，无量化误差，直接消除 \(\sqrt{\kappa}\) 代数下界
独立噪声精确采样 (Alg. 2)	平方协方差逼近误差 \(E_2 \leq 2\eta\)	\(O(\log\kappa)\)	解耦各尺度分值随机依赖，保证各向异性方差完全恢复
去除各向同性抖动 (w/o Dither)	TV 距离 \(= 1.0\) (灾难性失效)	无法收敛	纯离散网格与连续目标分布在测度奇异性下导致全变差退化
截断量化 + 抖动恢复 (Alg. 3)	通信比特复杂度 \(Q\)	\(O(d\log^2\kappa)\)	成功约束单次查询比特 \(B\)，提供确定性的通信与计算开销边界
通信下界信道反演 (Theorem 7)	最小必要通信量 \(Q_{\min}\)	\(\Omega(d\log\kappa)\)	证实所设计的有限比特方案在 \(\log\kappa\) 阶上紧致（仅差对数因子）