结果族 139：Subpolynomial query complexity for log-concave sampling · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
盲人要从一个看不见的多维”山谷”里按人口分布随机抽一位住址，每次只能问一个地点的海拔和坡度。山谷越是圆滑规整（曲率被夹在 @@M@@I@@ 与 @@M@@2I@@ 之间、谷底位置已知），问题应该越容易吧？可以前最好的方法也要问约 @@M@@d^{1/3}@@ 次，让人怀疑”维度的正幂是宿命”。本文证明：任何正幂都不必要，@@M@@d^{0.001}@@ 次也够；同时 @@M@@\log d@@ 次是绕不开的底线。
关键词卡片
@@M@@V@@，谷底已知、曲率被夹在 @@M@@I@@ 与 @@M@@2I@@ 之间。@@M@@e^{-V}@@ 加权的”山谷人口分布”，目标就是从它抽样。@@M@@(V(x),\nabla V(x))@@，下一问可自适应选择。@@M@@1/10@@。@@M@@Q(d)@@。看个具体例子
公式卡——定理掐出的夹缝：@@M@@c\log d\le Q(d)\le C_\varepsilon d^{\varepsilon}@@（对任意固定 @@M@@\varepsilon>0@@）。代入 @@M@@d=10^{12}@@、@@M@@\varepsilon=0.01@@：下限约 @@M@@28c@@ 次，上限 @@M@@C_{0.01}\cdot 10^{0.12}\approx 1.3\,C_{0.01}@@ 次；对比旧纪录 @@M@@d^{1/3}=10^4@@ 次。维度幂被钉死为零（常数 @@M@@C_\varepsilon@@ 会随 @@M@@\varepsilon@@ 变小而变大）。模型只计查询数：查询之间的计算不受任何限制；下界对任意随机化、自适应的算法成立，哪怕山谷是纯高斯形状。
为什么值得关心
主流采样法靠离散化 Langevin 动力学，误差总随维度涨；本文在预言机模型里干净地回答了”维度正幂是本质还是算法痕迹”这一尖锐问题：上下界合璧，最优维数指数恰为零。
已 Lean 形式化
第一级台阶
导读的比喻是盲人问山谷：每次只能问一个地点的海拔与坡度，要按”谷中人口”的分布随机抽一个住址。换成半数学的说法：对象是一个定义在高维空间上的碗形函数（越往谷底越深、形状足够规整）；操作是查询——选一个点，得到该处的高度与最陡下降方向；目标是产出服从”按深度指数加权的population分布”的一个随机样本。约束只计查询次数，查询之间的计算不花钱。要问的量：保证抽样质量所需的最坏查询次数随维度 @@M@@d@@ 怎么涨。
第二级台阶
用本科术语精确化。对数凹位势 @@M@@V:\mathbb{R}^d\to\mathbb{R}@@ 满足 @@M@@V(0)=0@@、@@M@@\nabla V(0)=0@@（谷底已知）且 Hessian 夹在 @@M@@I_d@@ 与 @@M@@2I_d@@ 之间（良条件）；目标分布是 Gibbs 律 @@M@@\pi_V(dx)\propto e^{-V(x)}dx@@。一阶预言机对每次查询返回 @@M@@(V(x),\nabla V(x))@@，允许自适应与随机化。两个分布的总变差距离度量其相近程度；查询复杂度 @@M@@Q(d)@@ 定义为：对类中每个位势都输出与 @@M@@\pi_V@@ 总变差 @@M@@\le 1/10@@ 的样本所需的最坏查询数。此前最好保证是 @@M@@\widetilde O(d^{1/3})@@。
第三级台阶
主定理（Theorem 1.1）在此语境下陈述：对每个固定 @@M@@\varepsilon>0@@ 存在常数 @@M@@C_\varepsilon@@ 使 @@M@@Q(d)\le C_\varepsilon d^\varepsilon@@ 对一切 @@M@@d\ge2@@ 成立；同时存在绝对常数 @@M@@c>0@@ 使 @@M@@Q(d)\ge c\log d@@，且该下界即使只限高斯位势、对任意随机化自适应算法也成立。”谷底已知、Hessian 上下夹紧”两条假设挡住的是定位谷底与病态曲率这两种额外困难；”计算不设限”假设则把结论严格限定在预言机复杂度、而非运行时间的意义上。合并两个界，最优维度指数 @@M@@\gamma_*=\limsup_{d\to\infty}\log Q(d)/\log d@@ 恰为零——@@M@@d@@ 的任何正幂都不是本质代价，@@M@@\log d@@ 却省不掉。
对 Hessian 介于 @@M@@I@@ 与 @@M@@2I@@、极小值点已知的对数凹位势，本文证明任意固定 @@M@@\varepsilon>0@@ 下只需 @@M@@C_\varepsilon d^\varepsilon@@ 次精确一阶查询即可把 Gibbs 分布采样到总变差 @@M@@1/10@@，并配 @@M@@\Omega(\log d)@@ 下界，确定该预言机模型的最优维度幂指数为零。
对数凹采样（log-concave sampling）问：要从 Gibbs 分布 @@M@@\pi_V(dx)\propto e^{-V(x)}dx@@ 取样，需要查询多少次位势信息？主流做法是对 Langevin 动力学作离散化，但离散化误差随维度增长。即便位势一致强凸且光滑（@@M@@I_d\preceq\nabla^2V\preceq2I_d@@，条件数与精度都固定），此前最好的保证也是 @@M@@\widetilde O(d^{1/3})@@ 次查询（Altschuler 的移位复合分析、Chen 等的路径空间拒绝采样），以及期望意义下的 @@M@@\widetilde O(d^{1/6})@@ 与 @@M@@\widetilde O(d^{1/5})@@（Picard 平滑与高斯云方法）。于是问题变得尖锐：维度的正幂究竟是本质代价，还是特定算法的痕迹？本文在精确一阶预言机（exact first-order oracle）模型中彻底回答了这一问题：查询返回 @@M@@(V(x),\nabla V(x))@@，允许自适应与随机性，查询之间的计算不受任何限制，且查询预算须在每次执行中一致成立——在此模型下，正幂并非本质，最优指数为零。
记 @@M@@Q(d)@@ 为满足如下要求的最坏查询数：对类 @@M@@\mathcal V_d@@ 中每个 @@M@@C^2@@ 位势 @@M@@V@@（@@M@@V(0)=0@@、@@M@@\nabla V(0)=0@@、@@M@@I_d\preceq\nabla^2V\preceq2I_d@@，即极小值点已知）都输出与 @@M@@\pi_V@@ 总变差（total variation）距离至多 @@M@@1/10@@ 的样本。主定理（Theorem 1.1）断言：对每个固定 @@M@@\varepsilon>0@@ 存在常数 @@M@@C_\varepsilon@@，使 @@M@@Q(d)\le C_\varepsilon d^\varepsilon@@ 对一切 @@M@@d\ge2@@ 成立；同时存在绝对常数 @@M@@c>0@@ 使 @@M@@Q(d)\ge c\log d@@，且该下界即使只限于高斯位势 @@M@@V(x)=x^TAx/2@@（@@M@@I\preceq A\preceq2I@@）也对任意随机化自适应算法成立。两者合并，最优维度指数 @@M@@\gamma_*=\limsup_{d\to\infty}\log Q(d)/\log d@@ 恰为零。须注意：上界并非 polylog 级，常数与逼近阶依赖 @@M@@\varepsilon@@；论文只计查询数，不对查询之间的实数计算施加任何复杂性或比特精度约束。
上界先化归为一个”近二次”原语（Theorem 2.1）：对 @@M@@X\sim\pi_V@@ 施加小高斯扰动后取条件律，得到 @@M@@\nu_{x,r}(dz)\propto e^{-|z|^2/2-F(x+rz)}dz@@，其中 @@M@@\Lip(\nabla F)\le\delta=d^{-e}@@ 极小，而求一次 @@M@@\nabla F@@ 恰好消耗一次原梯度查询；原语用 @@M@@\polylog(d)\delta^{-t}@@ 次查询输出”目标样本加一份独立高斯”。其内部有两个理想构件：一是高斯输运 @@M@@Y_\rho=\rho Z+\sqrt{1-\rho^2}N@@（概率流／随机插值观点），其速度场又是一个条件梯度均值，问题呈自相似结构；二是平稳配流（skew 矩阵动力学）把条件均值表示成路径积分加初始动量，精确等于 @@M@@u+sG@@。高阶导数用全分裂（all-split）张量范数逐阶控制（基于 Appell 多项式与高阶 Poincaré 不等式），每升一阶只损失 polylog 因子，@@M@@\sqrt d@@ 只在最终向量输出时付一次。真正的难点是嵌套条件均值的中心本身随机：编译器一节为每个例程建立逐点平移恒等式——中心平移 @@M@@\Delta@@ 可由种子平移 @@M@@v\otimes\Delta/r@@ 精确补偿，所有物理查询保持不变；再对种子做确定性协方差缩减，把中心处的高斯噪声原样吸收，使”噪声中心上的调用”恰为”固定中心的正确分布”（引理 7.1）。标签对 @@M@@(b,p)@@ 与两种深度（表达式依赖深度、例程调用高度）保证递归有限且查询上限在每次执行中成立。最后回到原目标：先跑收缩的近端链（每步 @@M@@W_2@@ 收缩 @@M@@1/(1+h)@@，共 @@M@@O(h^{-1}\log d)@@ 步）逼近加噪目标；再做 @@M@@O(\log d)@@ 层方差减半的条件下降（恒等式 @@M@@Z=Y/2+Z_{\rm new}/\sqrt2@@），把条件律化为近似高斯；以模式（mode）为中心的高斯加 @@M@@O(\log d)@@ 次不动点迭代收尾；有限个小维度用拒绝采样兜底。总查询为 @@M@@\polylog(d)\delta^{-(1+t)}=d^{e(1+t)+o(1)}@@，取 @@M@@2e<\varepsilon@@、@@M@@t<1@@ 即得 @@M@@d^\varepsilon@@。下界只看高斯：先以延迟揭示的 Haar 旋转把任意算法输出压入块 Krylov（block-Krylov）张成；再取谱 @@M@@\lambda_k=(3+\cos\theta_k)/2@@ 与余弦统计量 @@M@@\cos(n\theta_k)@@（@@M@@n=2q+1@@ 超过多项式次数的两倍），用离散余弦正交性证明该二次型在整个随机张成上一致地小；而目标高斯下同一统计量的均值为 @@M@@(d/\sqrt2)(-\varrho)^n@@（@@M@@\varrho=3-\sqrt8@@ 的几何级数恒等式），当 @@M@@q\le c\log d@@ 时远超阈值，Chebyshev 不等式分离两个联合实验，故查询太少必失败。
主结果（Theorem 1.1 的上、下界）已有 Lean 形式化证明（族内文档 lean/docs/139.md）；按 OpenAI 官方声明，未经形式化的结果可能有问题，正文其余构造性细节（张量估计、编译器例程等）仍以社区核验为准。上、下界在同一文中互相补足：上界说明 @@M@@d^\varepsilon@@ 可达，下界说明连 @@M@@\log d@@ 都不可省，合并才得到”指数为零”的完整刻画。本文面向预言机复杂度而非实际运行时间，常数随 @@M@@\varepsilon@@ 趋小而恶化，引用时须留意这一适用范围。
问 1：把 @@M@@d^{1/3}@@ 压到 @@M@@d^\varepsilon@@ 的支点是哪一步，哪里最脆？
答：支点是近二次原语（Theorem 2.1）：先把一般位势化为 @@M@@\nu_{x,r}(dz)\propto e^{-|z|^2/2-F(x+rz)}dz@@、@@M@@\Lip(\nabla F)\le\delta=d^{-e}@@ 极小的情形，再用自相似的高斯输运 @@M@@Y_\rho=\rho Z+\sqrt{1-\rho^2}N@@ 递归解出条件均值。最脆处是嵌套条件均值的中心本身随机：编译器一节靠逐点平移恒等式（中心平移 @@M@@\Delta@@ 由种子平移 @@M@@v\otimes\Delta/r@@ 精确补偿，引理 7.1 的协方差缩减）保证”噪声中心上的调用”恰为”固定中心的正确分布”——这层簿记一旦有近似未被吸收，递归每层漏一点误差，指数就回正幂。
问 2：@@M@@\Omega(\log d)@@ 下界为什么只看高斯位势就够？
答：高斯是子类，子类上的下界自动是全类的下界；且高斯情形能把问题变成纯谱问题：延迟揭示的 Haar 旋转把任意算法的输出压进块 Krylov 张成，取谱 @@M@@\lambda_k=(3+\cos\theta_k)/2@@ 与余弦统计量 @@M@@\cos(n\theta_k)@@（@@M@@n=2q+1@@ 超过多项式次数两倍），离散余弦正交性使该统计量在随机张成上一致地小，而目标高斯下其均值为 @@M@@(d/\sqrt2)(-\varrho)^n@@（@@M@@\varrho=3-\sqrt8@@），Chebyshev 分离两实验。构造干净，但只区分 @@M@@\log d@@ 量级——不足以排除 @@M@@\log^2 d@@。
问 3：与已有工作相比真正的新意是什么？
答：此前的 @@M@@\widetilde O(d^{1/3})@@（Altschuler 移位复合、Chen 等路径空间拒绝）与期望意义的 @@M@@\widetilde O(d^{1/6})@@、@@M@@\widetilde O(d^{1/5})@@ 全部基于离散化 Langevin 动力学，误差随维度涨是方法痕迹；本文证明在精确一阶预言机模型里维度正幂根本不必需——上界换用输运/条件均值递归而非离散化扩散，且查询预算在每次执行中一致成立（不是期望意义）。
问 4：”计算不设限”这个假设能去掉吗？
答：论文明确不对此施加约束，这是结果适用范围的边界而非疏漏：一次查询返回的 @@M@@(V(x),\nabla V(x))@@ 是精确实数，算法对它们做的实数运算、甚至超多项式时间的后处理都不计价。若要求比特精度受限的计算模型，@@M@@\polylog(d)\delta^{-t}@@ 次查询配套的计算量是否仍可控，论文未讨论——这也是本结果与”实际可跑的采样器”之间的鸿沟。
问 5：这类 AI 生成证明最可能的出错模式是什么，本篇风险如何？
答：典型风险是高阶张量估计与递归簿记的常数级联：全分裂张量范数（Appell 多项式 + 高阶 Poincaré）号称每升一阶只损失 polylog 因子、@@M@@\sqrt d@@ 只在最终输出付一次——每处差一个 @@M@@\sqrt d@@，@@M@@d^\varepsilon@@ 就不成立。但本篇主结果（Theorem 1.1 上下界）已有 Lean 形式化，这在同类论文里是最高等级的保险；正文其余构造细节（张量估计、编译器例程）仍需社区核验。
问 6：常数 @@M@@C_\varepsilon@@ 随 @@M@@\varepsilon\to0@@ 恶化到什么程度，有何后果？
答：总查询为 @@M@@\polylog(d)\delta^{-(1+t)}=d^{e(1+t)+o(1)}@@，要求 @@M@@2e<\varepsilon@@、@@M@@t<1@@，故 @@M@@C_\varepsilon@@ 大致按 @@M@@\delta=d^{-e}@@ 的负幂随 @@M@@\varepsilon@@ 收缩而爆炸；论文不追求 polylog 级上界。后果是”指数为零”是渐近论断：固定维度区间内，实际所需查询数可能远超旧算法，结果不能直接读作实践改进。
问 7：谁会用到它？
答：采样与无监督学习理论社区：它为 Langevin 类离散化方法的维度误差定基调——那些误差是可避免的，值得寻找非离散化的替代方案；预言机复杂度下界技术（Krylov 压缩 + 谱统计量）可迁移到带梯度访问的统计估计与优化问题。对 MCMC 实践者则更多是方向性信号而非即用算法。
总评
上下界合璧把预言机模型的维度指数干净地钉在零，且主定理有 Lean 形式化背书，是本批结果中可信度最高的一类；真正的分量在于宣判”维度正幂是算法痕迹”，最大保留是其结论不触及计算成本与常数实用性。