结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
把一亿像素的照片硬压成几百像素再传来传去，细节当然丢光——但丢完之后剩下的，是一团”位置随机、范围可算”的模糊。这篇论文证明：精确到无限位的实数观测，经过有限内存的算法消化后，剩下的也正是这样一个随机的小一号球面；于是内存远小于 @@M@@d^2@@ 的算法，注定要再看成千上万条新数据。
关键词卡片
@@M@@\Omega@@，而是明明白白的 @@M@@2^{-16}@@看个具体例子
定理说：内存 @@M@@M(d)=o(d^2)@@ 比特、成功率 @@M@@2/3@@、角精度 @@M@@0<\epsilon\le 1/10@@ 时（公式卡）：
@@M@@DT\ \ge\ 2^{-16}\cdot d\cdot\log_2(1/\epsilon)@@
代入 @@M@@d=1000@@：若 @@M@@\epsilon=2^{-20}@@（百万分之一精度），@@M@@T\ge 2^{-16}\times 1000\times 20\approx 305@@ 条；即便只要求 @@M@@\epsilon=1/10@@，也有 @@M@@T\ge 2^{-16}\times 1000\times 3.3\approx 50@@ 条。精度要求提高多少，样本就按对数成比例加多少——内存再省，这笔起步费免不了，因为每块观测消化完后，剩下的永远只是一个更小的随机球面。
为什么值得关心
它是同一结果族中唯一给出完全显式常数、且通过机器检验的版本；”实数再精确，有限内存装不下”从此有了可以查表的定量账单。
已 Lean 形式化
第一级台阶
导读里”一亿像素压成几百像素”的比喻可以落地了：对象是球面上的一个信号，原图的”无限细节”对应每条精确线性方程携带任意精细的实数信息；操作是一块块地消化这些方程、并把结果压进有限个持久状态。压完之后剩下的不是确定的点，而是一团”位置随机、范围可算”的模糊——论文证明这团模糊恰好是一个小一号的球面，且它的位置和大小有精确的概率规律。
第二级台阶
关键概念有三个。流式学习器：逐条读取观测、每步只保留至多 2^M 个状态之一的算法。残差子球：在一块 b 行高斯观测之后，目标信号条件分布是均匀分布在 z+p+ρS(K) 上——一个中心、半径都被观测决定的低维球面；其平方半径分数服从 Beta 分布。反事实延拓：从某个状态 v 继续运行下去的成功概率 g_v(s)，即使 v 在实际运行中不可达也要有定义。
第三级台阶
定理在如下语境陈述：记忆 M(d)=o(d²) 比特，信号均匀分布于球面，成功概率至少 2/3、角精度 ε 介于 0 与 1/10 之间。o(d²) 的记忆假设挡住的是”停止归约失效”——只有终止指标—状态对总数可控，才能推出成功运行至多含 o(d) 个块、测试球面始终保持大维度、向后归纳得以完成。结论是一张带显式常数的账单：T≥2^(−16)·d·log₂(1/ε)，阈值对一切精度一致，把 ε 取成 d^(−r) 即得 T≥2^(−16)·r·d·log₂d。
本文给出带显式常数的样本下界：@@M@@o(d^2)@@ 比特持久记忆的流式学习器，从独立精确高斯线性测量估计均匀随机单位向量，角精度 @@M@@0<\epsilon\le1/10@@、成功率 @@M@@2/3@@ 时至少需要 @@M@@2^{-16}d\log_2(1/\epsilon)@@ 个样本，对一切精度一致成立。
一条精确线性方程可以携带任意精细的实信息——@@M@@d@@ 条独立高斯方程几乎必然唯一确定向量。但流式（streaming）学习器只有有限个持久状态，无法按任意精度保存方程本身，于是要问：它究竟需要多少条新方程？Raz（2016）的分支程序下界处理离散学习任务；Sharan、Sidford 与 Valiant（2019）对连续回归证明：@@M@@d^2/4@@ 比特记忆、欧氏精度 @@M@@d^{-r}@@、噪声半宽 @@M@@2^{-d/5}@@ 时需要 @@M@@\Omega(d\log r)@@ 个样本。然而精确标签比噪声标签更有信息量，噪声下界推不出本文定理；”精确实数数据经任意计算压入有限状态后还剩什么”必须另行刻画。本文的答案是：剩下一个随机残差子球（residual subsphere）。
定理（显式无噪精度下界）：设 @@M@@M:\mathbb N\to\mathbb Z_{\ge0}@@ 满足 @@M@@M(d)=o(d^2)@@。存在仅依赖该记忆序列的维度阈值，使得对每个更大的 @@M@@d@@、每个 @@M@@0<\epsilon\le1/10@@、每个满足有限状态模型的 learner，若 @@M@@S@@ 均匀分布于 @@M@@S^{d-1}@@ 且
@@M@@D\Prob\{\arccos\langle\widehat s,S\rangle\le\epsilon\}\ge\frac23,@@
则 @@M@@T\ge 2^{-16}\,d\log_2(1/\epsilon)@@。阈值对精度一致，不要求精度与记忆之间有任何关系；取 @@M@@\epsilon=d^{-r}@@ 即得 @@M@@T\ge2^{-16}rd\log_2 d@@。推论把”均匀平均成功”换成”对每个固定信号都成功”，结论不变。论文另给三个平行的解析表述：半径加权和版本（每块代价 @@M@@W^{1/h}C^d@@，@@M@@h=\lfloor d/16\rfloor@@，成功率 @@M@@1/2@@）、对所有容许仿射子球面（affine subsphere）一致的显式版本、以及跨维度比较实际 learner 的固定长度版本；数值常数 @@M@@2^{-16}@@ 出自 β 混合证明。
先做两个模型归约：固定共享随机种子并把规则换成 Borel 核，使”从任意状态出发的反事实延拓（counterfactual continuation）”@@M@@g_v(s)@@——从状态 @@M@@v@@ 继续运行的成功概率——成为良定义的 Borel 函数，即便该状态在实际运行中根本不可达。
几何核心是块的确切残差律。把成功概率放到仿射子球面 @@M@@z+rS(H)@@（@@M@@z\perp H@@，@@M@@\|z\|^2+r^2=1@@）上测试。一块 @@M@@b@@ 行高斯观测揭示目标在其行空间上的投影 @@M@@p@@；条件在整块数据上，目标均匀分布于残差子球 @@M@@z+p+\rho S(K)@@，其中 @@M@@\rho^2=r^2-\|p\|^2@@、@@M@@K@@ 为行空间在 @@M@@H@@ 中的正交补；若只条件在投影 @@M@@p@@ 上，@@M@@K@@ 在 @@M@@H\cap p^\perp@@ 的 @@M@@(D-b)@@ 维子空间中均匀，平方半径分数服从 @@M@@\Beta((D-b)/2,b/2)@@。精确标签看似传递了实数，块处理之后剩下的却是一个随机子球。
状态选择在平均掉矩阵之前记费：@@M@@\E_K\max_v F_v(K)\le(\sum_v\E_KF_v(K)^h)^{1/h}@@，选择至多付 @@M@@W^{1/h}@@。真正的难点在于：@@M@@h@@ 个方向画在同一个随机空间 @@M@@K@@ 里，平均掉 @@M@@K@@ 后它们彼此相关——不能每个方向都花掉一个测试维度。β 混合比较（两分量支配）解决之：给定已暴露方向的张成 @@M@@V@@，下一方向的律被 @@M@@2^{D'}(\nu_0+\nu_1)@@ 支配，其中 @@M@@\nu_0@@ 是全空间均匀律，@@M@@\nu_1@@ 是”先在 @@M@@V@@ 中取方向、再在垂直纬面（latitude）上取均匀方向”的 β 混合；按垂直分量平方 @@M@@Q@@ 是否超过 @@M@@1/2@@ 分段比较 β 密度即可完成证明。于是每块只消耗两个测试维度（一个给投影方向、一个给比较纬面），尽管块内样本数与 @@M@@d@@ 成比例。
残差半径与纬面半径贡献逆半径矩，其平方分数服从 β 律，用有限 β 乘积显式控制；取矩阶 @@M@@h@@ 正比于 @@M@@d@@，得到对一切延拓一致的界，逐块向后归纳，终端是球冠（spherical cap）估计。归纳还需要足够的维度：停止归约数出至多 @@M@@(T+1)2^M@@ 个终止指标—状态对，球冠概率计数表明成功且 @@M@@T=O(d\log(1/\epsilon))@@ 的运行必有 @@M@@\log(1/\epsilon)=o(d)@@，即只含 @@M@@o(d)@@ 个块——测试球面始终够大，归纳得以完成。
主结果已 Lean 形式化（结果族 140 附 Lean 证明文档），且给出的是显式常数 @@M@@2^{-16}@@ 而非隐式 @@M@@\Omega@@。族内姊妹篇《Projection moments…》与《Replacing Gaussian observations…》以投影矩与信息论比较两条路线得到同阶下界，三篇互相印证。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本文主定理已形式化，加权、仿射、固定长度三个附加表述的常数以论文文本为准。
问 1：证明中最关键、最脆弱的一步是什么？
（答：β 混合比较。状态选择的高阶矩要平均 h 个方向，它们画在同一个随机子空间 K 里，平均掉 K 后彼此相关——若每个方向都花一个测试维度，维度立即耗尽。β 混合把下一方向的律支配为 2^{D’}(ν₀+ν₁)：ν₀ 是全空间均匀律，ν₁ 是”先在已暴露张成 V 中取方向、再在垂直纬面上取均匀方向”的两步律；按垂直分量平方是否超过 1/2 分段比较 β 密度。由此每块只消耗两个测试维度，尽管块内样本数与 d 成比例——这一步松动一点，整个归纳维度账就崩。）
问 2：M=o(d²) 这个记忆假设为什么不能去掉？
（答：它供养的是停止归约：终止指标—状态对至多 (T+1)·2^M 个，球冠概率计数表明成功且 T=O(d·log(1/ε)) 的运行必有 log(1/ε)=o(d)，即只含 o(d) 个块，测试球面才始终够大、向后归纳才闭合。若记忆达到 d² 量级，块数可能太多，测试维度被耗尽，归纳无从谈起。）
问 3：与 SSV（2019）相比真正的新意是什么？
（答：SSV 的第七节引理 12 同样用独立副本与逐次正交化算高阶矩，但处理的是”带噪区间投影＋全局 L² 密度假设”；本文条件在整块精确数据上，证明目标均匀落于随机残差子球的确切条件律，再局部控制它。且精确标签比噪声标签信息更多，SSV 的噪声下界推不出本定理——这是必须另起炉灶的理由。）
问 4：为什么要定义”不可达状态”的反事实延拓 g_v(s)？
（答：块后的状态选择可依赖整块矩阵与全部标签，必须在平均掉矩阵之前记账：成功率被 max over 状态 v 的 F_v(K) 控制，而 E max_v F_v ≤ (∑_v E F_v^h)^{1/h} 只付 W^{1/h} 的选择代价。max 里的每个 v 都可能是实际到不了的状态，所以 g_v 必须对一切状态良定义——这要求先固定随机种子并把规则换成 Borel 核的模型归约。）
问 5：作为 AI 生成证明，最可能的出错模式是什么？
（答：主定理已 Lean 形式化，核心风险转移到位：加权、仿射不变、固定长度三个附加表述的显式常数未形式化，只以文本为准；β 乘积的数值常数 2^{-16} 这类”机器算术”恰是文本证明易错处。另外维度阈值依赖记忆序列、无有效率，”充分大的 d”到底多大论文未给出。）
问 6：这个结果谁会用到？
（答：需要可查表下界的人。它是该结果族中唯一给完全显式常数且机器检验过的版本：设计流式回归算法的人可直接用 T≥2^{−16}·d·log₂(1/ε) 对照自己的样本复杂度；取 ε=d^{−r} 得 T≥2^{−16}·r·d·log₂d，推论还把”平均成功”换成”对每个固定信号都成功”，覆盖最坏情形保证。）
总评
用”随机残差子球”这一干净的几何刻画换到一张带显式常数、经机器检验的账单，是结果族 140 中最可引用的一块；最大风险在三个未形式化附加表述的常数与”阈值无效率”这一固有局限。