结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
还是猜方向的游戏，这次换”信息账本”来审：一整块 @@M@@d@@ 条精确证词被浓缩成一页摘要后，这页摘要里究竟还剩多少关于真相的信息？论文的妙招是造”平行宇宙”——读完数据后，从自己的信念里再抽几份信号副本，然后度量这些副本之间互通了多少情报。
关键词卡片
@@M@@W@@。看个具体例子
公式卡——主定理：@@M@@I(S;W\mid B,BS)\le H(W)/t+C\,d+C\log(2+\log L)@@，其中 @@M@@t\asymp d@@。代入摘要 @@M@@H(W)=10^6@@ 比特、@@M@@d=1000@@：剩余条件信息 @@M@@\lesssim 10^3+10^3@@ 比特量级——再厚的摘要也被 @@M@@d@@ 条观测摊薄。妙处还有两处：先验密度上界 @@M@@L@@ 只以双对数进入，条件化在极稀有状态上也不怕；侧投影是独立抽取、先于摘要公开的。逐块累加即得流式下界：@@M@@o(d^2)@@ 比特的学习者需 @@M@@\Omega(d\log(1/\epsilon))@@ 个无噪样本。
为什么值得关心
它为同一下界补上纯信息论的第二条独立路线，与”倒推”姊妹篇互相印证——同族几篇文章从互不相同的技术抵达同一结论；其等标签测度定理还被第三篇直接引用为解析输入。
已 Lean 形式化
第一级台阶
导读的比喻是”平行宇宙”：读完一块数据后，从自己的信念里再抽几份信号副本，度量这些副本之间互通了多少情报。换成半数学的说法：对象是一块约 @@M@@d@@ 条的精确观测（高斯行与其精确标签）以及学习者从中算出的一页有限比特摘要；操作是”造副本”——在给定数据后，从后验信念中独立抽出若干个与摘要条件独立的信号副本；要问的量是：这页摘要里究竟还剩多少关于真信号的信息。
第二级台阶
用本科术语精确化。信号 @@M@@S@@ 服从球面 @@M@@S^{d-1}@@ 上的先验 @@M@@p=f\sigma_d@@（密度 @@M@@f\le L@@ 有界）；消息 @@M@@W@@ 是由 @@M@@(A,AS)@@ 经可测核产生的有限值随机变量。互信息 @@M@@I(S;W)@@ 度量 @@M@@W@@ 携带的信号信息；本文的核心量是条件互信息 @@M@@I(S;W\mid B,BS)@@——在向分析师披露一条独立抽取的高斯投影 @@M@@(B,BS)@@ 之后 @@M@@W@@ 的剩余信息（@@M@@B@@ 只是分析变量，学习者看不见）。副本 @@M@@S_1,\ldots,S_t@@ 之间的依赖用总相关性（Watanabe 的 total correlation）度量：它们的联合 law 相对独立乘积 law 的相对熵。
第三级台阶
主定理（Gaussian replica block bound，thm:gaussian-block）在此语境下陈述：取 @@M@@k=2\lfloor d/16\rfloor@@、@@M@@t=m+1\asymp d@@、@@M@@\ell=4k@@，则 @@M@@I(S;W\mid B,BS)\le H(W)/t+Cd+C\log(2+\log L)@@，界对先验、密度界 @@M@@L@@ 与消息核一致成立。假设各自挡住一种麻烦：精确标签使后验支在低维纤维上、无密度可言，须用等标签测度直接计算；对 @@M@@L@@ 的双对数依赖则容纳”条件在稀有状态上、密度界高达 @@M@@1/p_v@@“的流式应用。由 Nishimori 恒等式，每对 @@M@@(S_i,W)@@ 保持原信号–消息 law，链式整理得 @@M@@tI\le H(W)+K-K'@@，于是全部困难集中于控制投影前后的相关性损失。流式推论（thm:streaming）：@@M@@o(d^2)@@ 比特、确定性时限的学习者在均匀先验下要达到角度误差 @@M@@\epsilon\le1/10@@，必有 @@M@@T\ge c\,d\log(1/\epsilon)@@。
本文用”后验副本”（posterior replicas）耦合证明：一整块精确高斯观测在向分析师披露一条独立侧投影后只剩 @@M@@O(H(W)/d+d+\log(2+\log L))@@ 条件信息，进而导出 @@M@@o(d^2)@@ 比特流式学习者需 @@M@@\Omega(d\log(1/\epsilon))@@ 个无噪样本。
无噪高斯回归的内存–样本权衡，除了”倒推成功概率”路线外，还有一条更信息论的表述：从一块精确观测算出的有限值消息（message）@@M@@W@@ 到底能保留多少关于信号的互信息（mutual information）？答案不能只靠样本数控制——若先前消息已把信号浓缩进小区域，后续消息会利用这种浓缩，因此先验分布的”几何铺开性”必须进入估计。Steinhardt–Duchi、Raz 与 Sharan–Sidford–Valiant（SSV）处理过带噪或离散情形；SSV 在微噪模型中得到 @@M@@\Omega(d\log r)@@，但其 @@M@@\Omega(d\log\log(1/\epsilon))@@ 精度推论限制在极小精度区间。精确标签、亚二次内存下的单对数精度代价 @@M@@\Omega(d\log(1/\epsilon))@@ 仍缺一条纯信息论证明。技术难点在于：精确观测的后验支在低维”等标签纤维”（equal-label fiber）上，常规密度方法失效。本文与两篇姊妹篇（同族的《Memory and precision…》及《Replacing Gaussian observations…》）互补分工。
主定理（高斯副本块估计）说：设先验 @@M@@p=f\sigma_d@@ 的密度 @@M@@f\le L@@ 有界，@@M@@A@@ 是 @@M@@k\asymp d@@ 行标准高斯矩阵，从数据 @@M@@(A,AS)@@ 产生有限值消息 @@M@@W@@；再独立抽取 @@M@@B@@（@@M@@\asymp d@@ 行）并向分析师披露投影 @@M@@(B,BS)@@，则 @@M@@I(S;W\mid B,BS)\le H(W)/t+Cd+C\log(2+\log L)@@，其中 @@M@@t\asymp d@@。消息熵代价被 @@M@@\Theta(d)@@ 摊薄；对 @@M@@L@@ 只有双对数依赖——这点至关重要，因为条件化在一个概率为 @@M@@p_v@@ 的稀有状态上会得到高达 @@M@@1/p_v@@ 的密度界。流式推论：状态数 @@M@@M(d)=o(d^2)@@、确定性停止时限的学习者，在球面均匀先验下以 @@M@@\ge 2/3@@ 概率达到角度误差 @@M@@\epsilon\le1/10@@，则必有 @@M@@T\ge c\,d\log(1/\epsilon)@@，@@M@@c@@ 为绝对常数。论文另外发展了四条块比较路线（距离箱、Haar 框架、合成高斯、Stiefel 关联），各自独立支撑流式迭代。
证明有两根支柱。第一根是副本信息不等式：给定数据 @@M@@(A,AS)@@，从后验独立抽取 @@M@@S_1,\ldots,S_t@@，且给定数据后与 @@M@@W@@ 独立——由 Nishimori 恒等式（Nishimori identity），每一对 @@M@@(S_i,W)@@ 都保持原来的信号–消息联合 law，但忘掉数据后副本彼此依赖（共享标签 @@M@@AS_i@@）。记 @@M@@K@@ 为副本间的总相关性（total correlation，Watanabe），@@M@@K'@@ 为经独立矩阵 @@M@@B@@ 投影后仍可见的相关性；链式法则的精确整理给出 @@M@@tI(S;W\mid B,BS)\le H(W)+K-K'@@，因此核心是控制”相关性损失”@@M@@K-K'@@，单边上界 @@M@@K@@ 会丢掉分析师仍能看见的几何依赖。第二根支柱是精确的等标签测度：论文证明一个有限测度恒等式——”先选矩阵与公共标签（按密度 @@M@@p_A^t@@ 加权），再在纤维上取独立点”与”先取独立信号、再取零化其差矩阵 @@M@@D@@ 的高斯行”两种描述，相差权重 @@M@@(2\pi)^{-km/2}J^{-k}@@，其中 @@M@@J=\det(D^{\mathsf T}D)^{1/2}@@ 是各点到前驱仿射张成的逐次距离之积（单纯体积）。由此得副本似然的显式公式，其分母 @@M@@p_A^{m}@@ 与逆体积因子 @@M@@J^{-k}@@ 的对数可积性由卡方分解与管道估计（tube estimate）保证，并给出总相关上界。最后对剩余投影密度比做二进分解，用投影副本的可观测检验配出匹配的逆体积项，几何项相消后只剩 @@M@@O(d)@@。流式证明则条件在当前状态上逐块套用该估计并对状态取平均：独立投影留下一个维度 @@M@@\asymp d@@ 的剩余球面，在其上精确恢复仍需 @@M@@\Omega(d\log(1/\epsilon))@@ 条件信息，逐块累加即得样本下界。
据任务文件，本文主结果已有 Lean 形式化证明。它与同族《Memory and precision…》（倒推路线）以完全不同的技术证明同一下界，互为印证；其等标签测度定理（Theorem 3.3）还被姊妹篇《Localization costs…》直接引用为解析输入。按 OpenAI 官方声明，未经形式化的结果可能有问题，读者应以形式化主定理为准。
问 1：证明的关键一步是什么，为什么单边控制 @@M@@K@@ 不行？
答：关键引理（lem:replica-information）给出 @@M@@tI(S;W\mid B,BS)\le H(W)+K-K'@@：由 Nishimori 恒等式每对 @@M@@(S_i,W)@@ 保序原信号–消息 law，但忘掉数据后副本共享标签 @@M@@AS_1=\cdots=AS_t@@ 而彼此依赖。若只单边上界总相关性 @@M@@K@@，就丢掉了分析师经 @@M@@(B,BS)@@ 仍看得见的几何依赖，界会失真；必须控制”损失”@@M@@K-K'@@——投影抹掉的相关性才算数。
问 2：等标签纤维上的测度恒等式为什么是全篇最硬的一块？
答：精确观测使后验支在低维纤维上、相对球面测度没有密度，常规密度法全部失效。Theorem thm:equal-label-measure 把”选矩阵与公共标签、再在纤维上取独立点”与”取独立信号、再取零化差矩阵 @@M@@D@@ 的高斯行”两种描述精确换算，权重差 @@M@@(2\pi)^{-km/2}J^{-k}@@（@@M@@J=\det(D^{\mathsf T}D)^{1/2}@@ 为逐次单纯高度之积）。副本似然分母中的 @@M@@J^{-k}@@ 的对数可积性由卡方分解与管道估计保证；这一步与 Federer 余面积公式、Drury 的单纯体积换元同源，但概率归一化是本文直接证明的。
问 3：对密度界 @@M@@L@@ 只剩 @@M@@\log(2+\log L)@@ 的双对数依赖，为什么至关重要？
答：流式迭代要把块估计条件在当前状态值 @@M@@v@@ 上，而条件在概率 @@M@@p_v@@ 的稀有状态上时先验密度界飙到 @@M@@1/p_v@@。若 @@M@@L@@ 线性进入界，稀有状态的平均信息代价就无法被 @@M@@p_v@@ 摊薄；双对数依赖使”条件化在极稀有状态上也不怕”，这是把块估计拼成流式定理的通行证。
问 4：与 SSV 及两篇姊妹篇相比，真正的新意是什么？
答：对 SSV：他们需要微噪（均匀噪声半宽 @@M@@2^{-d/5}@@）且精度推论困在 @@M@@\epsilon\le d^{-\Omega(\log d)}@@ 的区间；本文处理精确标签，给出单对数精度代价 @@M@@\Omega(d\log(1/\epsilon))@@——而带噪下界推不过来，因为持精确标签者可自行加噪。对姊妹篇：《Memory and precision》走”倒推成功概率”路线、《Replacing Gaussian observations》走两点纤维比较；本文的多副本总相关路线是第三条独立技术，五条块比较（距离箱、Haar、合成高斯、Stiefel 关联）各有分工，其等标签测度定理还被《Localization costs》引用为输入。
问 5：AI 生成这类信息论+几何的证明最可能在哪里出错？
答：可测性约定与迭代条件的顺序。论文在 Definition def:streaming-model 显式记录”整个实验联合可测”的完成可测性约定，并把合成高斯与 Stiefel 路线的迭代条件放在全历史上——条件结构的任何错位（先条件化再抽副本 vs 先抽副本再条件化）都会让 Nishimori 恒等式的适用前提失效。其次是 @@M@@J^{-k}@@ 对数可积性的尾部：管道估计的例外集若处理不净，@@M@@K-K'@@ 的界会多出一个 @@M@@o(d)@@ 级别的漂移。主结果已 Lean 形式化，风险显著降低，但四条备用比较路线的细节仍在形式化覆盖之外。
问 6：流式定理为什么要”确定性停止时限”，这个假设能松吗？
答：块估计的迭代需要预先固定的块划分与停止下标，随机停时会破坏”条件在当前状态、对未来取平均”的记账；论文未讨论随机时限的替代论证。这是模型的明确边界，与 @@M@@o(d^2)@@ 内存假设一起界定了结论范围——姊妹篇《Memory and precision》恰好补上 @@M@@M\le Ad^2@@（常数因子二次）的情形，两文拼起来才覆盖完整区间。
问 7：谁会用到它？
答：内存受限学习与信息论社区：条件信息块估计是可迁移的原语（任何”消息由数据经核产生、再被侧信息稀释”的场景都可套用）；等标签纤维测度对精确观测的统计推断有独立工具价值。对同族三篇论文，它是互相印证的第二条路线，把 @@M@@\Omega(d\log(1/\epsilon))@@ 从单点结果升级为多条独立技术收敛的结论。
总评
这是用纯信息论路线重证同一内存–样本下界的扎实工作，等标签测度恒等式是有独立价值的贡献，且有 Lean 形式化背书；最大保留在于它证明的是同族已知结论的第二条路，独立分量在技术而非命题，且四条备用比较路线的形式化覆盖尚不完整。