结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
想象你反复审问一位知情人：他每次可以交出一本厚得吓人的笔录，可只要笔录是从一个（再庞大的）有限版本库里挑出来的，你真正套到的情报仍然有限。这篇论文做的就是这本”情报账”：它严格算清，反复观测一个隐藏信号时，哪怕每轮记录能大得像天文数字，信息也只能按轮数一点点漏出去。
关键词卡片
看个具体例子
在 @@M@@d=100@@ 维球面上均匀藏一个信号，每轮观测约 @@M@@d@@ 行、共 @@M@@t=3@@ 轮；每条消息最多可有 @@M@@\exp(A\cdot 100^2)@@ 个取值——这本”目录”比宇宙里的原子还多。但主定理保证（公式卡）：
@@M@@DI\bigl(S;\,W_1,Q_1,W_2,Q_2,W_3,Q_3\bigr)\ \le\ C\,d\,t\ =\ 300\,C\ \text{nats}@@
就算再白送三层”信号落在哪个小盒”的嵌套二进格子，三轮下来总泄密也只有几百 nats；而要精确到角精度 @@M@@\epsilon@@ 需要的信息是 @@M@@c\,d\log(1/\epsilon)@@ 量级，还差得远——于是内存只有 @@M@@o(d^2)@@ 的学习器必须再看那么多条新数据。
为什么值得关心
“定位信号在哪”这件事本身要花信息，这笔花销能否被收益抵偿，正是无噪回归下界证明中最难清算的一环；本文首次系统算账：付得起，且账算得清。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读里那位”每次交出厚笔录的知情人”，现在可以说得更具体：被审问的对象是藏在高维空间里的一个信号点；每轮审问就是一批精确的线性测量；”厚笔录”是学习器算出的一条消息——它再厚，也是从一个巨大但有限的目录里挑出来的。要算的账，是这些笔录合起来把信号位置缩小了多少。还有一个新角色：每轮结束后可以公开宣布”信号此刻落在哪个层层对半切出的小盒里”，这笔披露也要计入账单。
第二级台阶
用标准术语说：设 n=d−1，信号 Z 服从边长 1/√n 的方体上的均匀分布，经球坐标映射落到球面上；观测按 k=⌊n/16⌋ 行分块，每行是标准高斯向量配精确标签；第 i 条消息至多取 N≤exp(Ad²) 个值。信息量用互信息度量；二进格子是一列嵌套小盒；”几何铺开”条件要求后验在相对深度 j 的每个后代格子上质量不超过 B·2^(−nj/2)——即不确定性仍摊满整个维度，没有缩进低维角落。
第三级台阶
主定理在”消息加格子”的增广记录上陈述：可以选出一列包含 Z 的嵌套格子，使总互信息不超过 C·dt，且期望格子深度为 O(t)。铺开假设挡住的是”后验被压进小区域、下一条消息借势集中泄密”的麻烦；字母表条件挡住的是单块信息界中 log N 项失控。结论的关键账目是：指明一个深度 j 的重格子只花约 nj/2 比特，而”信号被困于深度 j 格子”本身认证 nj 比特——这一半的差价恰好付清披露成本。原始消息历史是增广记录的函数，自动继承同一界，于是内存 o(d²) 的学习器必须看 Ω(d·log(1/ε)) 条数据。
本文对”均匀立方体经球坐标映射”的先验证明：@@M@@t@@ 个 @@M@@\Theta(d)@@ 行精确高斯观测块、每条消息至多 @@M@@\exp(Ad^2)@@ 个取值时，只携带 @@M@@O_A(dt)@@ nats 信息，且在额外披露恢复几何铺开性的二进格子后界仍成立。
对无噪高斯回归逐块迭代信息界时，会撞上一个循环困难：块估计要求当前后验满足”几何铺开条件”（不向低维邻域集中），而消息本身恰恰破坏这一条件；要恢复它就得向分析披露包含信号的二进格子（dyadic cell），而披露本身要花信息——定位的代价能否被其收益抵偿？这就是本文主题”定位代价”（localization costs）。文献脉络上，Steinhardt–Duchi 与 Raz 建立了带噪与离散的内存–样本权衡，Dagan–Kur–Shamir 证明了一致线性方程组的二次空间下界；最接近的方法学前身是 Sharan–Sidford–Valiant（SSV）第七节的投影矩展开与逐次正交化。但精确标签情形必须重证多行密度估计，并首次系统清算每次定位的信息账单。
主定理（重复定位）说：令 @@M@@n=d-1@@，@@M@@Z@@ 在边长 @@M@@1/\sqrt n@@ 的方体上均匀分布，@@M@@S=\phi(Z)=(Z,\sqrt{1-\|Z\|^2})@@ 落在球面上；把观测分成 @@M@@k=\lfloor n/16\rfloor@@ 行一块，每条消息 @@M@@W_i@@ 至多 @@M@@N\le\exp(Ad^2)@@ 个值（@@M@@A@@ 固定）。则可以披露一列包含 @@M@@Z@@ 的嵌套二进格子 @@M@@Q_0\supset Q_1\supset\cdots\supset Q_t@@，使得增广记录 @@M@@\Pi_t=(W_1,Q_1,\ldots,W_t,Q_t)@@ 满足互信息 @@M@@I(Z;\Pi_t)\le Cdt@@，且期望格子深度 @@M@@\E J_t\le Ct@@。原始消息历史是 @@M@@\Pi_t@@ 的函数，故自动继承同一界。学习者推论：状态数 @@M@@M=o(d^2)@@ 的学习者若对每个信号都以 @@M@@\ge2/3@@ 概率成功，则 @@M@@T\ge c\,d\log(1/\epsilon)@@。论文还给出八条定位路线（极大得分、有限熵、有界密度分裂、似然截断、网格加细、侧投影、分离元组、前驱张成）与两种信息修正工具（核势 @@M@@\Phi@@ 与格子修正），覆盖立方体先验与球面均匀先验两类应用。
铺开条件要求：支在格子 @@M@@Q@@ 上的后验对每个相对深度 @@M@@j@@ 的后代格子质量 @@M@@\le B2^{-nj/2}@@。第一步证明加权投影估计：铺开条件经二进覆盖给出管道型估计 @@M@@\mu\{\mathrm{dist}(a(z),V)\le\delta\}\le BC^d\delta^{n/2-q}@@；把任意 @@M@@L^2@@ 权重塞进后验，对平滑标签密度的 @@M@@m@@ 次矩展开引入 @@M@@m@@ 个独立点，高斯行作用在差矩阵 @@M@@\mathsf D@@ 上时每行是协方差为 @@M@@\mathsf D^{\mathsf T}\mathsf D@@ 的高斯向量，其密度峰值反比于单纯体积 @@M@@V_*@@，平滑参数 @@M@@\eta@@ 的幂次恰好相消；再用尾部积分逐点控制 @@M@@\int D_i^{-k}@@，取对偶即得对权重一致的 @@M@@L^m@@ 密度界。第二步把密度换成信息：消息概率 @@M@@p_w(z)@@ 的 @@M@@L^2@@ 范数由对偶与 H"older 用参考概率 @@M@@b_w@@（标签换成均匀参考）控制，再经 Jensen 与 log-sum 不等式得单块界 @@M@@I\le Cd+\log B+(2/m+e^{-ck})\log N@@。第三步是定位记账：消息之后铺开性可能失效，于是披露”最深的重格子”（后验质量 @@M@@\ge2^{-nj/2}@@ 的最深祖先）；深度 @@M@@j@@ 处重格子至多 @@M@@2^{nj/2}@@ 个，指明一个只花约 @@M@@nj/2@@ 比特，而”信号落入深度 @@M@@j@@ 格子”本身认证 @@M@@nj@@ 比特信息，这一半的指数差就是支付披露与下一轮 @@M@@\log B@@ 的盈余。关键细节是记账须按”选中”该格子的概率而非落入概率归一化。第四步闭合迭代：链式法则给上界 @@M@@I\le Cdt+(\tfrac n2+2)\log2\,\E J_t@@，而相对熵恒等式 @@M@@\KL(\lambda\|\mu_0)=nJ_t\log2+\cdots@@ 给下界 @@M@@I\ge n\log2\,\E J_t@@，两相比较逼出 @@M@@\E J_t\le Ct@@，代回即得 @@M@@I\le Cdt@@。流式应用：固定一切随机性化为确定性学习者，块消息记状态（含块内停止偏移），@@M@@N\le(k+3)2^M+1@@ 满足字母表条件；成功帽体积 @@M@@\le(5\epsilon)^n@@，由数据处理不等式精确估计需 @@M@@\Omega(n\log(1/\epsilon))@@ 信息，故块数 @@M@@t\ge c\log(1/\epsilon)@@；最后用保留全部数据的端点论证消除取整，得 @@M@@T\ge c\,d\log(1/\epsilon)@@。
据任务文件，本文暂无 Lean 形式化证明，可信度依赖社区核验，读者宜谨慎对待细节常数。其最终结论与两篇已形式化的姊妹篇《Memory and precision…》《Posterior replicas…》一致，且其”前驱张成”路线直接引用后者的等标签测度定理（Theorem 3.3），另有一条混合投影矩取自同伴论文。按 OpenAI 官方声明：”未经形式化的结果可能有问题”。
问 1：整个证明最脆弱的一环在哪里？
（答：定位记账的归一化方式。深度 j 的”重格子”至多 2^(nj/2) 个，指明选中者花约 nj/2 比特，而”落入深度 j 格子”认证 nj 比特，盈余来自这个二倍差；但引言特别强调，记账必须按”选中该格子”的概率而非”落入”的概率归一化——若用后者，付不起下一轮的 log B，迭代无法闭合。这是全文最容易被常数误差毁掉的一步。）
问 2：消息至多 exp(Ad²) 个取值的字母表条件能否去掉？
（答：不能随意去掉。单块信息界含 (2/m+e^(−ck))·log N 项（m=⌊n/8⌋），N 无界时该项发散；只有 N≤exp(Ad²) 且 A 固定，它才能被吸收进常数 C_A。学习者应用里状态数 M=o(d²) 恰好保证块消息取值数满足此条件，两处假设是配套的。）
问 3：几何铺开条件挡住了什么？为什么分析者要主动”白送”二进格子？
（答：若早期消息已把后验压进小区域，下一条消息可借这种集中泄密，逐块信息界失效；铺开条件（相对深度 j 的后代质量 ≤B·2^(−nj/2)）正是投影密度估计的前提。麻烦在于消息本身会破坏铺开性，于是分析者披露”包含 Z 的最深重格子”来恢复它——披露花的正是问 1 中那笔差价，定理证明付得起。格子只进分析、不进学习器的状态。）
问 4：与 Sharan–Sidford–Valiant（SSV）相比，真正的新意是什么？
（答：SSV 处理带小噪声观测，其第七节引理 12 的投影矩逐次正交化是方法学前身；本文面对精确标签必须重证多行密度估计及其极限过程，并首次系统清算”恢复铺开性”的信息账单——即定位代价本身。与 Dagan–Kur–Shamir 的区别在于：他们给的是对固定方程组的残差保证，这里信号先固定、样本独立抽取，且下界追踪精度参数 ε。）
问 5：作为未经形式化的 AI 生成证明，它最可能以何种方式出错？
（答：典型风险在细账：无界对数在变分不等式中的可积性（论文称每次使用都补截断论证）、二倍差价的边界效应、取整与端点论证。此外它从两篇同伴论文借入长分析输入（等标签测度定理 3.3 与混合投影矩定理 3.1），错误可能藏在”借来的引理”而非本文正文；八条定位路线各有独立假设，一条出错不影响其余，但也意味着每条都需单独核验。）
问 6：谁会用到这个结果？
（答：内存–样本权衡社区。直接推论是：o(d²) 位持久内存的学习器在无噪高斯回归下要达到角精度 ε 需要 Ω(d·log(1/ε)) 条精确观测，为流式、低内存算法的样本复杂度提供匹配下界。）
总评
这项工作把无噪回归下界中最难清算的”定位代价”算清了，是内存–样本权衡版图上的关键补块；但未经形式化、又横跨十条证明路线与两份外部输入，细节常数的正确性仍需社区逐条核验。