结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
考试只许带一张小抄：小抄越小，你就得做越多的题才能过关。这篇论文给”小抄大小”与”做题数量”之间的兑换率开出了定量账单，而且用三条互不相干的路（投影矩、正支配、Riesz 估计）各推导一遍——像三个互不通气的审计员算出了同一个数。
关键词卡片
@@M@@Kt^\beta@@——”不许聚堆”看个具体例子
学习器要猜 @@M@@d=1000@@ 维球面上的均匀随机单位向量，角精度 @@M@@\epsilon=10^{-6}@@、成功率 @@M@@2/3@@。定理的兑换率长这样：
代入数字：@@M@@\log(1/\epsilon)=\log(10^6)\approx 13.8@@，故 @@M@@T\ge c\cdot 1000\cdot 13.8\approx 13800\,c@@ 条；只要内存 @@M@@M=o(d^2)@@（远小于 @@M@@d^2@@），这个量级纹丝不动。三条证明各有分工：投影矩路线盯着低维影子的密度，正支配路线把概率质量拆成一顶顶球冠帽子，Riesz 路线则借逆距离位势兜底——三条路殊途同归，都落在同一条兑换率曲线上。
为什么值得关心
这是首个对”精确无噪声数据”成立的完整记忆–样本下界，三条独立证明互相兜底，显著降低了单一路径出错的风险。
已 Lean 形式化
第一级台阶
导读里”小抄换做题量”的考试比喻，对象与操作可以这样落地：考生是只有有限内存的学习器，题目是一条条精确成立的线性方程，考题答案要指出藏在球面上的那个未知信号。小抄就是持久记忆状态——它越小，要过的题（观测）就越多。而”看影子”的比喻说：把高维信号随机压到低维，投影后的影子不能太亮太集中；”不许聚堆”说的是信号的不确定性必须摊开，任何小球上都不能堆太多概率质量。
第二级台阶
精确化的关键概念有三个。其一是局部质量条件：有限正测度 ν 在任何半径 t 的球上质量不超过 K·t^β（Frostman 型球增长条件）。其二是随机正交投影：P 是 k 行的 Haar 正交矩阵，推前测度 P#ν 带密度 g_P，密度矩 ∫g_P^q 度量影子”亮”的程度。其三是球冠与正支配：球冠是球面上以某点为中心的”小帽子”邻域；正支配指找到可数个规范化球冠测度之和，逐点压住目标测度。
第三级台阶
定理的语境是：均匀球面信号、逐条到达的精确高斯观测、持有 M=o(d²) 位记忆的学习器，要求平均成功概率至少 2/3、角精度 ε≤1/10。局部质量条件挡住”质量缩进低维邻域使投影密度爆炸”的麻烦；精确标签（无噪声）则让旧下界方法直接失效。结论是三条独立路线共同给出：学习器必需 T≥c·d·log(1/ε) 条观测，且显式权衡 T≥c·d·log(1/ε)/(1+M/d²) 对一切非负整数 M 成立——内存换样本的汇率由此定死，M 远小于 d² 时这个量级纹丝不动。
本文证明：只有 @@M@@o(d^2)@@ 比特持久记忆的单遍学习器，要从无噪高斯线性观测中以角精度 @@M@@0<\epsilon\le1/10@@、成功概率 @@M@@2/3@@ 恢复均匀随机单位向量，必需 @@M@@\Omega(d\log(1/\epsilon))@@ 个样本；支撑它的随机正交投影矩估计、球冠正支配与 Riesz 位势三套工具给出三个独立证明。
“记忆—样本”权衡问的是：限制算法能记住多少，会迫使它多看多少数据？Steinhardt、Valiant 与 Wager（2016）把这一问题与通信复杂度和统计查询模型相连，Raz（2016）对 parity 学习证明了二次记忆对指数样本的定性分离。在连续回归方向，Sharan、Sidford 与 Valiant（2019）证明：@@M@@d^2/4@@ 比特记忆、欧氏精度 @@M@@d^{-r}@@、加性噪声模型需要 @@M@@\Omega(d\log r)@@ 个样本。但他们的论证依赖噪声尺度与全局 @@M@@L^2@@ 密度条件；无噪（exact label）模型中每条方程携带任意精度的实信息，旧下界无法直接搬用。本文回到位势论（potential theory）的古典源头——Mattila（1975）的投影能量平均与 Drury（1984）的单纯体积雅可比——为精确标签建立局部质量条件下的投影矩理论。
三条分析主线。其一（投影矩，projection moment）：设 @@M@@\nu@@ 为 @@M@@\mathbb{R}^d@@ 上有限正测度，在每个半径 @@M@@t@@ 的球上质量至多 @@M@@Kt^\beta@@（Frostman 型局部质量条件），@@M@@P@@ 为 @@M@@k@@ 行随机正交矩阵（Haar 框架），@@M@@g_P@@ 为推前测度 @@M@@P_\#\nu@@ 的密度，则密度矩的框架平均 @@M@@\E_P\int g_P^q@@ 有关于维度、支撑半径与指数 @@M@@\beta@@ 显式的界。其二（正支配，positive domination）：对球冠（spherical cap）@@M@@B@@ 上的条件测度 @@M@@\mu_B@@ 经路由规则加权后的测度 @@M@@f_w\mu_B@@，存在可数个规范化球冠测度之和将其正支配，细半径的代价受一个参考路由概率的幂控制。其三（Riesz 估计）：受环境 Riesz 泛函 @@M@@V(h)=\sup_z\int h\|s-z\|^{-d/2}\,d\sigma@@ 控制的测试函数，其高斯投影密度在每个固定仿射偏移（affine offset）处有同一密度版本的一致矩界。
回归推论：记忆 @@M@@M(d)=o(d^2)@@、均匀球面平均成功概率至少 @@M@@2/3@@、角精度 @@M@@0<\epsilon(d)\le1/10@@ 的学习器必须 @@M@@T\ge c\,d\log(1/\epsilon)@@；且显式权衡 @@M@@T\ge \frac{c\,d\log(1/\epsilon)}{1+M/d^2}@@ 对一切非负整数 @@M@@M@@ 成立，故 @@M@@M\le Ad^2@@ 时得 @@M@@\Omega_A(d\log(1/\epsilon))@@。
综合矩估计的骨架是：把 @@M@@q@@ 阶密度矩展开为测度中 @@M@@q@@ 个点的标签碰撞概率，碰撞由 @@M@@q-1@@ 个差向量的投影控制。逐列观察 Haar 框架：正交框架的相继坐标有椭球密度，其行列式幂在连乘中逐项相消，只剩一个非负行列式幂与显式的 @@M@@\sqrt d@@ 尺度；再用 Gram–Schmidt 把剩余变量换成逆仿射高度（successive affine heights），其乘积恰是 Drury 式单纯体积（simplex volume）。对每个先前点的仿射张成作管状邻域（tube）并用球覆盖，局部质量假设便”从后往前”把这些高度积分掉。
回归应用中，先把高斯矩阵分解为正径向因子与独立的正交框架；路由规则可以用整个径向因子，对其取平均即产生框架与投影标签上的权重。投影支撑是一个 @@M@@k@@ 维球，其体积恰好抵消密度范数中的维度尺度，使输出的半径指数与进入的局部质量指数一致——因此”向后传播”穿过每个数据块都保持环境维度，停止指标（stopping index）在块内计数，最后用对径引理（antipodal bound：@@M@@T\le d/8@@ 时即使白送全部数据，成功也不超过 @@M@@5/8@@）去掉多余的加性 @@M@@d@@。
正支配路线方向相反：先由可数球冠字典上的有界测试推出重尺度测试测度的球质量界，再用归一化的矩定理控制 @@M@@f_w\mu_B@@；为把一列不等式变成真正的正支配测度，取加权的球冠密度族——每个尺度只留有限个球冠、加权成本使细尺度 @@M@@L^1@@ 尾趋于零，由此获得范数紧性；对闭的下调凸集（downward convex set）作严格分离，即产生恰好已被控制的正测度和。用它向前传播信号—状态联合律，停止指标只在最后求和一次。
Riesz 路线改用锚定在 @@M@@z@@ 处的 @@M@@q@@ 个向量（而非锚定在采样点的 @@M@@q-1@@ 个差向量），它们在高斯行下的像协方差为锚定 Gram 矩阵，所得球平均估计对一切固定偏移一致；取下极限密度版本并在每个偏移图上用 Fatou 引理保住估计，再用算子范数分箱与径向壳层控制此前延拓的位势。该路线保留 @@M@@1+\log(1/\epsilon)@@ 的壳层因子与全局终止时钟，两者由其自身的短程论证处理。
主结果已 Lean 形式化（结果族 140 附 Lean 证明文档）。三个证明相互独立、代价结构各有取舍，同一下界的多重推导显著降低了单一路径出错的风险；族内姊妹篇《Subsphere methods…》与《Replacing Gaussian observations…》分别以子球面条件化与信息论比较得到同阶下界，三面互证。按 OpenAI 官方声明，未经形式化的结果可能存在问题；本文的回归下界与显式记忆权衡已形式化，个别显式常数以论文文本为准。
问 1：三条证明路线里，哪一步是全局最脆弱的？
（答：投影矩路线中的换元步：q 阶矩展开成 q 个点的标签碰撞概率后，正交框架相继坐标的椭球密度行列式幂必须逐项相消，再经 Gram–Schmidt 化为逆仿射高度、恰好拼成 Drury 式单纯体积。这一串”相消—换元—体积”是整个分析的枢轴，任何一处归一化常数算错，界就不再显式成立。）
问 2：局部质量条件（球质量 ≤K·t^β）为什么不能去掉？
（答：若允许概率质量聚堆，被投影压扁后密度可以无界，∫g_P^q 矩估计直接失效；这个 Frostman 型条件是位势论的经典门槛（Mattila 1975），也是唯一约束”质量能藏多低维”的假设。论文的球冠路线甚至要从有界测试反推构造出这个条件，可见它不可省。）
问 3：既然一条路就够，为什么给三条独立证明？
（答：三条路的代价结构不同，引言的对比表写明：积分投影路线向后传播局部质量、停止指标逐块计数；正支配路线向前传播信号—状态联合律、停止指标最后只求和一次；Riesz 路线用固定偏移密度、多付 1+log(1/ε) 的壳层因子与全局终止时钟。多路互证正是为了降低单路出错风险——这对 AI 生成证明尤其重要。）
问 4：与 SSV（2019）相比真正的新意在哪里？
（答：SSV 第七节引理 12 处理的是”单个带噪区间＋全局 L² 密度条件”，依赖噪声尺度；本文处理精确多行标签，把全局密度条件换成局部球质量或 Riesz 位势条件，并首次给出 M 与 T 的显式权衡公式 T≥c·d·log(1/ε)/(1+M/d²)。）
问 5：Riesz 路线为什么死抠”同一个密度版本在每个固定偏移处”？
（答：积分型密度范数对”依赖矩阵的图上的修改”不敏感，本身无法给定点处的值定界；要在指定标签处控制密度，必须选定一个对一切偏移一致的密度版本（下极限版本），再用 Fatou 引理在每张偏移图上保住估计。这是该路线最微妙的技术点，也是 AI 证明容易含糊处——论文对此有明确限定。）
问 6：结果最可能的出错模式是什么？谁会用它？
（答：主结果已 Lean 形式化，风险集中在形式化范围之外：三条路线的显式常数、维数阈值对记忆序列的依赖、以及 Rokhlin 式端点（对径引理：T≤d/8 时白送全部数据成功也不超过 5/8）。用户是内存–样本权衡与流式学习下界社区：任何声称”少内存又少样本”的算法都被这条汇率约束。）
总评
这是首个对精确无噪声数据成立的完整记忆–样本下界，三路独立证明加 Lean 形式化使其成为该方向最扎实的一块基石；剩余风险只在显式常数与未形式化的细节论证。