结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
你用第一批顾客的评价挑出了想收藏的评论，然后反复研究这批”被选中的”评价——它们天生带着幸存者偏差；若换成一批全新的顾客，结论会差多少？这篇论文证明：差价极小，至多 @@M@@O(d)@@。这条”换新对比定理”直接锁死了小内存学习器的样本需求。
关键词卡片
@@M@@d^2@@@@M@@J(U)=I(S;U\mid G,GS)@@，随观测块数线性增长，却被成功输出逼出下界看个具体例子
比较两个实验：左边让”旧数据”参与挑选消息，右边换成全新独立数据——
差价是 @@M@@Kd@@，而达到角精度 @@M@@\epsilon@@ 所需的信息约 @@M@@c\,d\log(1/\epsilon)@@（@@M@@d=1000@@、@@M@@\epsilon=10^{-6}@@ 时约 @@M@@13800\,c@@ nats）——差价只占零头。于是每消化一块（@@M@@d/10@@ 条）观测，净信息至多涨 @@M@@Kd@@，逼出 @@M@@T=\Omega(d\log(1/\epsilon))@@。记账方式很直观：把”还剩多少不知道”当成水位，每块观测后水位至多升一格固定的 @@M@@Kd@@，而成功输出要求水位灌到 @@M@@c\,d\log(1/\epsilon)@@ 那么高，块数不够就注定灌不满。
为什么值得关心
它把”选择偏差要付多少信息代价”从哲学疑问变成了带绝对常数的定理，并以此为小内存学习器钉死了样本下界。
已 Lean 形式化
第一级台阶
导读里的”幸存者偏差”实验可以这样翻译：对象是藏在球面上的一个信号，操作是用一批高斯观测数据挑选出一条有限的消息，然后比较两种后续——继续持有这批”帮着做挑选”的旧数据，或者把它整体换成一批从未参与挑选的全新数据。要比较的量是”还剩多少关于信号的未知”：幸存者偏差的代价，就是两个实验里剩余未知程度的差。水位比喻则说：每消化一块新观测，未知度至多下降固定的一格。
第二级台阶
| 精确化的概念有三个。条件互信息 I(S;W | G,GS)：在已知一个全独立的辅助投影（矩阵 G 及其标签 GS）之后，消息 W 仍额外泄露的信号信息。消息熵 H(W)≤d²：允许 W 是可数消息、可与数据和信号有任意依赖，只限制其取值多样程度。两个”实验”：对齐实验保留实际行 A 并追加独立行 C，独立实验只给全新行 G——它们保持信号—消息与信号—矩阵的边缘分布不变，仅全联合律不同。 |
第三级台阶
| 主定理（临界半径比较）断言：I(S;W | G,GS) ≤ I(S;W | A,C,AS,CS)+Kd，K 为绝对常数、d 充分大。熵条件挡住的是”精细化标签本身的熵代价”失控（它需被 Kd 吸收）；行维与 d 成比例（m=⌊d/10⌋、ℓ=⌊d/2⌋）挡住的是高斯积分的维度账对不上；定理的机理是在每个点上取信息最浓缩的”临界半径”，让新旧两侧的偏差恰好对消。流式推论：内存 M=o(d²)、平均成功至少 3/5、角精度 ε≤1/10 的学习器，确定性视野必须 T=Ω(d·log(1/ε))——每块只涨 Kd 的水位，灌不满成功所需的 c·d·log(1/ε)。 |
本文证明”换行比较定理”：把参与挑选有限消息的高斯行整体换成全新独立行，关于信号的剩余条件互信息至多增加 @@M@@Cd@@；据此推出 @@M@@o(d^2)@@ 比特记忆的学习器达到 @@M@@3/5@@ 成功率、角精度 @@M@@0<\epsilon\le1/10@@ 需要 @@M@@\Omega(d\log(1/\epsilon))@@ 个精确观测。
从数据中选出的有限消息会改变这些数据的条件分布：条件在消息 @@M@@W@@ 上，曾用于挑选 @@M@@W@@ 的那些高斯行通常是有偏的。这正是记忆受限推断（memory-constrained inference）的核心困难——Raz（2016）的分支程序（branching program）下界、Steinhardt–Duchi（2015）的记忆依赖极小极大界、Sharan–Sidford–Valiant（2019）的连续回归框架都要面对它。无噪标签比噪声标签信息更多，SSV 的噪声下界因此不够用。另一方面，Russo–Zou（2016）与 Xu–Raginsky（2017）关于”自适应选择的统计量与独立参考之比较”的结果提示：选择本身要付信息代价，但代价几何此前未知。本文在与 @@M@@d@@ 成比例的行维下把这一代价精确到 @@M@@O(d)@@，几何计算则属于 Mattila（1975）以逆距离控制投影能量的传统。
主定理（临界半径比较，critical-radius comparison）：设 @@M@@S@@ 均匀分布于 @@M@@S^{d-1}@@，@@M@@m=\lfloor d/10\rfloor@@、@@M@@\ell=\lfloor d/2\rfloor@@，@@M@@A@@ 为 @@M@@m@@ 行标准高斯矩阵且与 @@M@@S@@ 独立，@@M@@W@@ 为可数消息、可与 @@M@@(S,A)@@ 有任意联合依赖、熵（entropy）@@M@@H(W)\le d^2@@；@@M@@C@@ 为与一切独立的 @@M@@\ell-m@@ 行高斯矩阵，@@M@@G@@ 为与 @@M@@(S,W)@@ 独立的 @@M@@\ell@@ 行高斯矩阵。则对充分大的 @@M@@d@@，
@@M@@DI(S;W\mid G,GS)\le I(S;W\mid A,C,AS,CS)+Kd,@@
其中 @@M@@K@@ 为绝对常数：把”帮着选消息的行”换成新鲜行，条件互信息只多花 @@M@@O(d)@@。流式推论：@@M@@M(d)=o(d^2)@@、均匀球面角精度 @@M@@0<\epsilon(d)\le1/10@@、成功概率至少 @@M@@3/5@@、确定性有限视野（deterministic finite horizon）的 learner 必须满足 @@M@@T=\Omega(d\log(1/\epsilon))@@。论文还发展另外两条比较路线——逐行替换的混合（hybrid）比较与固定纤维（fiber）测度比较——各自得到量级相同的流式端点。
比较两个实验：对齐实验保留实际行 @@M@@A@@ 并追加独立行 @@M@@C@@，独立实验只给全新行 @@M@@G@@；两者保持信号—消息与信号—矩阵的边缘分布不变，仅全联合律不同。信息差中含一个负的条件行信息项；数据处理不等式把它与”实际条件标签律对后验（posterior）@@M@@P_{S\mid W}@@ 投影”的散度挂钩，剩下的只有独立投影的熵与一个对齐对数密度。控制这个密度是分析的枢纽。
为此先证明混合矩估计（mixed moment）：在 @@M@@q@@ 阶矩中，实际行被全部 @@M@@q@@ 个因子共享，而独立辅助行在各个因子中分别平均；高斯积分产生逆长度与信号差向量的逆 Gram 行列式，一条局部质量界控制相继张成周围的细管，另一条控制小径向尺度之和。这与 SSV 的高矩展开一脉相承，但多行、精确标签、局部质量的版本是新的。
真正让两项相消的是临界半径精细化：对每对 @@M@@(w,s)@@，在二进半径 @@M@@R_j=2^{1-j}@@ 中取使 @@M@@R^{-\ell}F_w(B(s,R))@@ 达到最大的”临界半径”，并记录其对数质量水平 @@M@@q_w(s)=\lceil\log b_w(s)\rceil@@。在该半径上限制后验，独立实验的覆盖熵下降；同一个水平又把对齐投影密度抬高恰好相反的数量，于是两项对消。精细化标签的熵代价仅 @@M@@H(E\mid W)\le C\log(d+1+H(W))@@，在 @@M@@H(W)\le d^2@@ 时为 @@M@@O(\log d)@@，可被 @@M@@Kd@@ 吸收。
流式应用按块进行：定义信息位势 @@M@@J(U)=I(S;U\mid G,GS)@@，每块 @@M@@m=\lfloor d/10\rfloor@@ 个样本后 @@M@@J@@ 至多增加 @@M@@Kd@@，初始位势为零，故终态满足 @@M@@J(W_f)\le Kd\lceil T/m\rceil@@。另一方面，残差球引理给出成功输出必须携带的信息量：@@M@@J(W_f)\ge\frac{a-1}{2}(L-\log4)-\log2\ge c_0 dL@@，其中 @@M@@L=\log(1/\epsilon)@@、@@M@@a=d-\ell@@。两式相较即得 @@M@@T\ge c\,dL@@。沿途另设两道闸门：输出容量估计 @@M@@p\le(T+1)2^M\epsilon^{d-1}@@ 迫使 @@M@@L=o(d)@@；”白送全部数据”的对径式估计迫使 @@M@@T>d/4@@，保证块数至少为一。
主结果已 Lean 形式化（结果族 140 附 Lean 证明文档）。本文从信息论端（互信息比较）逼近族 140 的统一下界，姊妹篇《Projection moments…》与《Subsphere methods…》从几何测度论端给出互补证明，三者在模型与常数上互相校准。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本文的流式下界主定理已形式化，混合与纤维两条辅助比较的显式常数以论文文本为准。
问 1：证明中最关键、也最脆弱的一步是什么？
（答：临界半径精细化后的”两项对消”。信息差里的对齐对数密度，须在每对 (w,s) 上限制到使 R^(−ℓ)F_w(B(s,R)) 达到最大的二进半径，并记录对数质量水平；独立实验的覆盖熵下降与对齐投影密度的抬升必须恰好反号相消，精细化标签的熵代价还要小到能被 Kd 吸收。对消系数差一点，O(d) 差价就不成立。）
问 2：消息熵 H(W)≤d² 这个假设为什么不能去掉？
（答：精细化标签的条件熵上界形如 C·log(d+1+H(W))，若 H(W) 无界，这个代价无法装进 O(d) 的差价里，比较定理就失去意义。论文的”单水平”比较路线索性把熵依赖显式保留在结论中而非硬设 d² 上限，说明该假设是记账需要而非本质无害。）
问 3：与 Russo–Zou、Xu–Raginsky 的自适应选择分析相比，真正的新意是什么？
（答：他们给出”选择要付信息代价”的定性框架（散度差被选择信息控制），但代价的量级未知；本文把测试函数取为精确投影密度，用 q 阶混合矩让行信息以 1/q 系数出现，首次在与 d 成比例的行维下把代价定到 O(d)。与 SSV 相比则是从带噪单行、全局 L² 条件推进到精确多行、局部质量条件。）
问 4：为什么除临界半径外还要给 hybrid 与 fiber 两条比较路线？
（答：三条路线适用范围不同：临界半径路线允许可数消息、实际块 ⌊d/10⌋ 行；两标签路线处理有限消息、块 ⌊d/8⌋ 行，其高斯磨光密度版本支持任意固定目标点处的估计；单水平路线只用一个标签、块 ⌊d/32⌋ 行。hybrid 逐行替换并对辅助观测数取平均，fiber 构造同标签对上的有限测度——几何对象与量化方式各不相同，端点常数互补校准。）
问 5：作为 AI 生成证明，它最可能出错的模式是什么？
（答：典型风险是测度论细部：精确密度版本的选取、换行律与极限运算的次序、无界对数的可积性——引言承认这些次序”逐节处理”，恰是机器证明易含糊处。主定理已 Lean 形式化降低了核心风险，但 hybrid 与 fiber 两条辅助路线的显式常数未形式化，仍以文本为准。）
问 6：下游推论与使用者是谁？端点处有何讲究？
（答：直接锁死流式学习器的样本下界 T=Ω(d·log(1/ε))。两道闸门值得注意：输出容量估计 p≤(T+1)·2^M·ε^(d−1) 迫使 L=log(1/ε)=o(d)（否则信息不够装）；”白送全部数据”的对径式估计迫使 T>d/4，保证至少有一整块可记账。内存–样本权衡与在线学习理论社区会直接引用。）
总评
这篇论文把”选择偏差的信息代价”从哲学直觉变成带绝对常数的定理，是结果族 140 三面互证中最纯粹的信息论一环；最大风险藏在密度版本与运算次序这类测度论细节，好在主定理已形式化。