结果族 140：Memory–sample lower bounds for noiseless Gaussian regression · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
猜一个藏在 @@M@@d@@ 维球面上的方向：每轮给你一条精确到无限小数位的投影线索，但你只有 @@M@@d^2@@ 比特的笔记本，每条线索看完必须压成摘要才能写下一条。看似无限精确的线索应该很快锁定答案？论文证明：想猜准到角度 @@M@@\epsilon@@，任何算法都得老老实实收下约 @@M@@d\log(1/\epsilon)@@ 条线索——记性受限，就得用脚投票。
关键词卡片
@@M@@y=\langle x,s\rangle@@ 完全精确、不带误差的线性方程，真方向从球面均匀抽取。@@M@@t@@ 步后期望误差 @@M@@(1-1/d)^t@@。看个具体例子
公式卡——Kaczmarz 天然尺度对照定理下界：由 @@M@@(1-1/d)^t\le\epsilon@@ 解得 @@M@@t\approx d\ln(1/\epsilon)@@。代入 @@M@@d=1000@@、@@M@@\epsilon=10^{-6}@@：@@M@@t\approx 1000\times 13.8\approx 1.4@@ 万步。定理说：内存 @@M@@\le Ad^2@@ 比特的任何流式学习者，想以至少 @@M@@2/3@@ 的概率把角度误差压到 @@M@@\epsilon\le 1/10@@，样本数都逃不开 @@M@@c\,d\log(1/\epsilon)@@ 这个量级——上下恰好咬合。模型还非常宽松：每块样本之间的计算与随机化完全不受限，输出只依赖终态。
为什么值得关心
精确观测下的精度代价一直是悬案（带噪情形的已知结论推不过来，因为拿精确标签者可自行加噪），本文正面解决；答案与 Kaczmarz 的天然尺度严丝合缝，且内存 @@M@@o(d^2)@@ 时常数是绝对的。
已 Lean 形式化
第一级台阶
导读的场景是猜球面上的隐藏方向：每轮收到一条精确到无限小数位的投影线索，但笔记本只有有限页，每条线索必须压成摘要才能记下一条。换成半数学的说法：对象是一个藏在 @@M@@d@@ 维球面上的未知方向；操作是逐条读取”它与某个随机方向的精确内积”并更新一份有限比特的记忆状态；目标是最终从记忆里报出一个与真方向夹角很小的猜测。要问的量是：记性被限制到某条线之下时，锁定方向所需的线索条数。
第二级台阶
用本科术语精确化。无噪高斯回归中，样本是高斯行向量 @@M@@x_t@@ 与精确标签 @@M@@y_t=\langle x_t,S\rangle@@，真信号 @@M@@S@@ 服从球面均匀分布 @@M@@\sigma_d@@；流式学习者持至多 @@M@@M@@ 比特的持久状态，块内计算与随机化不限，输出只依赖终态。角度误差 @@M@@\arccos\langle\widehat s,S\rangle@@ 度量猜测质量。经典参照是随机化 Kaczmarz 迭代：@@M@@t@@ 步后期望误差 @@M@@(1-1/d)^t@@，达到误差 @@M@@\epsilon@@ 需约 @@M@@d\ln(1/\epsilon)@@ 步——但它在实数寄存器上工作，不提供有限比特保证。内存–样本权衡问的正是：把实数记忆砍到 @@M@@O(d^2)@@ 比特，样本要多付多少？
第三级台阶
主定理（Theorem 1.2）在此语境下陈述：对每个固定 @@M@@A>0@@ 存在常数 @@M@@c_A,d_A@@，只要持久状态至多 @@M@@Ad^2@@ 比特，任何以至少 @@M@@2/3@@ 概率把角度误差压到 @@M@@\epsilon\le1/10@@ 的学习者，其样本时限必满足 @@M@@T\ge c_A\,d\log(1/\epsilon)@@。假设各自挡住一种逃逸：观测精确无噪（有噪下界推不过来，因为持精确标签者可自行加噪）；单遍流式、输出只看终态（排除多遍回看的旁路）。结论与 Kaczmarz 的天然尺度严丝合缝；两条推论再补：内存 @@M@@o(d^2)@@ 时常数绝对，”平均成功”换成”逐信号成功”下界依旧。@@M@@T\le d/4@@ 时即便保留全部数据成功率也不到 @@M@@2/3@@，大尺度端点同样被钉住。
本文证明：持有至多 @@M@@Ad^2@@ 比特状态的单遍学习者即便读的是无噪高斯线性方程，要把随机单位向量估计到角度误差（angular error）@@M@@\epsilon@@ 仍需 @@M@@\Omega_A(d\log(1/\epsilon))@@ 个样本，与 Kaczmarz 算法演示的天然尺度吻合。
一条精确观测 @@M@@\langle x_t,s\rangle@@ 是携带任意精度的实数：若全部样本可保留，@@M@@d@@ 条高斯方程几乎必然唯一确定未知向量。但单遍流式学习者只能把每次观测压缩进 @@M@@2^M@@ 个状态之一，这种压缩是否要多付样本？经典的随机化 Kaczmarz 算法迭代 @@M@@t@@ 步后期望误差为 @@M@@(1-1/d)^t@@，恰好解释了 @@M@@d\log(1/\epsilon)@@ 这个天然尺度，但它存储实数寄存器，不提供有限比特保证。理论方面，Steinhardt–Duchi 与 Raz 等人针对带噪或离散情形建立了内存–样本权衡；最接近的 Sharan–Sidford–Valiant（SSV）结果在带半宽 @@M@@2^{-d/5}@@ 微噪的高斯回归中，对 @@M@@d^2/4@@ 比特、精度 @@M@@\epsilon=d^{-r}@@ 证明了 @@M@@\Omega(d\log r)@@ 下界。然而带噪下界推不出精确观测的对应结论——持精确标签的学习者可自行加噪——因此无噪情形的精度代价是否仍为 @@M@@\Theta(d\log(1/\epsilon))@@ 一直是悬案，本文正面解决。
主定理（Theorem 1.2）说：对任意固定 @@M@@A>0@@ 存在常数 @@M@@c_A,d_A>0@@，只要 @@M@@d\ge d_A@@，任何持久状态至多 @@M@@M\le Ad^2@@ 比特的学习者逐条读取新高斯行 @@M@@x_t@@ 与精确标签 @@M@@y_t=\langle x_t,S\rangle@@，若在球面均匀先验（uniform prior on the sphere）@@M@@S\sim\sigma_d@@ 下以至少 @@M@@2/3@@ 概率做到 @@M@@\arccos\langle\widehat s,S\rangle\le\epsilon@@（@@M@@0<\epsilon\le1/10@@），则其样本时限必然满足 @@M@@T\ge c_A\,d\log(1/\epsilon)@@。模型极为宽松：块内计算与随机化完全不受限，输出只能依赖终态、停止下标与新随机数。两条推论：其一，当 @@M@@M=o(d^2)@@ 时常数 @@M@@c@@ 是绝对的；其二，把”平均成功”换成”对每个固定信号都成功”，同样的下界依然成立。论文还由此导出 SSV 带噪实验中的 @@M@@\Omega_A(dr\log d)@@ 推论。
证明采用沿时间”倒推”的归纳，最大障碍是后验奇异性：球面均匀先验被一条精确观测条件化后，信号被限制在超平面截面上，相对球面测度没有密度。作者的绕法是不动先验，转而研究从某个指定状态出发、只用未来样本的成功概率 @@M@@h(s)@@，维持不变量：对一切球 @@M@@B(z,r)@@ 有 @@M@@\int_{B(z,r)}h\,d\sigma_d\le(Rr)^{(d-1)/2}@@，其中尺度参数 @@M@@R@@ 度量成功信号集合的集中程度，终端输出规则天然给出 @@M@@R=\epsilon@@。倒推跨过含 @@M@@m\le q@@（@@M@@q\asymp d@@）条观测的块时，先由一般投影估计给出高斯矩阵及其精确标签联合 law 的 @@M@@L^q@@ 密度，其范数损失一个半径幂次；再注意到公共投影椭球体积至多 @@M@@e^{Cd}r^m@@，其 @@M@@1-1/q@@ 次幂在 H"older 不等式中恰好补回密度损失的幂次，半径指数完全相消；最后对 @@M@@N@@ 个可能的目的状态再用一次 H"older，选择代价只有 @@M@@N^{1/q}@@。由于把质量增长换算成尺度增长的是指数 @@M@@a\asymp d@@，最终得 @@M@@\log(R'/R)\le C(1+M/d^2)@@——二次内存正是在此处进入：@@M@@q\asymp d@@ 摊薄了 @@M@@\log N@@。于是每倒推一块 @@M@@R@@ 至多乘常数倍，而平均成功 @@M@@2/3@@ 迫使 @@M@@R@@ 有下界，故从 @@M@@\epsilon@@ 出发需要 @@M@@\Omega(\log(1/\epsilon))@@ 块、每块 @@M@@\asymp d@@ 条观测。大尺度端点由反射论证给出：把信号关于全部行的张空间作镜面对称，两个对称信号产生相同数据却相距超过 @@M@@2\epsilon@@，故即便保留全部数据，@@M@@T\le d/4@@ 时成功率也不超过 @@M@@1/2+T/(2d(1-\epsilon^2))<2/3@@。随机化规则与可测性（逐 seed 的 Borel 版本）在流式一节统一处理。
据任务文件，本文主结果已有 Lean 形式化证明。同族姊妹篇《Posterior replicas…》（副本耦合与条件信息）与《Localization costs…》（二进制定位）用独立技术路线得到同一 @@M@@\Omega(d\log(1/\epsilon))@@ 流式下界，三篇互相印证。按 OpenAI 官方声明，未经形式化的结果可能有问题；本文主定理已形式化，可信度较高。
问 1：证明的最大障碍是什么，绕法的关键一步在哪里？
答：障碍是后验奇异性：球面均匀先验被一条精确观测条件化后，信号被压在超平面截面上、相对球面测度没有密度，标准的”后验有界密度”论证无从下手。绕法是研究”从指定状态出发、只用未来样本的成功概率”@@M@@h(s)@@，维持不变量 @@M@@\int_{B(z,r)}h\,d\sigma_d\le(Rr)^{(d-1)/2}@@，对时间倒推归纳。关键一步在跨块估计：高斯矩阵与精确标签联合 law 的 @@M@@L^q@@ 密度损失一个半径幂次，而公共投影椭球体积 @@M@@e^{Cd}r^m@@ 的 @@M@@1-1/q@@ 次幂在 H"older 不等式中恰好补回——半径指数相消，@@M@@R@@ 每块至多乘常数倍。
问 2：@@M@@Ad^2@@ 比特的内存预算是在哪里”花掉”的？
答：在最后对 @@M@@N@@ 个可能目的状态的那一次 H"older：选择代价 @@M@@N^{1/q}@@，而 @@M@@q\asymp d@@ 的块长把它摊薄成 @@M@@\exp(O(M/d))@@；又因质量增长换算成尺度增长用的是指数 @@M@@a\asymp d@@，得 @@M@@\log(R'/R)\le C(1+M/d^2)@@——二次内存恰在此进入。这也解释了为何阈值取 @@M@@d^2@@：那是把 @@M@@d@@ 维方向”逐坐标记账”的自然比特量。
问 3：为什么带噪下界（SSV 等）推不过来，这个假设为什么关键？
答：持精确标签的学习者可以自己给数据加噪、把问题变回带噪情形再套用已知算法，故带噪下界不能自动迁移到无噪模型；反过来，无噪模型的下界更强——它说明即便信息无限精细，压缩状态仍是真瓶颈。论文还顺向导出 SSV 带噪实验的 @@M@@\Omega_A(dr\log d)@@ 推论，显示无噪技术反哺带噪情形。
问 4：大尺度端点 @@M@@T\le d/4@@ 的反射论证是什么？
答：把信号关于前 @@M@@T@@ 行的张空间作镜面对称：两个对称信号产生完全相同的数据，却相距超过 @@M@@2\epsilon@@，因此任何算法（哪怕保留全部数据）成功率不超过 @@M@@1/2+T/(2d(1-\epsilon^2))<2/3@@。这堵住了”少量样本靠运气”的缺口，与 @@M@@\Omega(d\log(1/\epsilon))@@ 的小尺度端首尾呼应。
问 5：AI 生成这类测度论证明最可能在哪里出错？
答：可测性与随机化的边界处理：论文专门在流式一节用逐 seed 的 Borel 版本处理随机化规则的可测性，这类”先固定随机带再谈测度”的顺序若颠倒，@@M@@h(s)@@ 的定义就会悬空。其次是幂次簿记：椭球体积的 @@M@@1-1/q@@ 次幂与密度损失的幂次必须严格相消，差一次幂下界就退化成 @@M@@\Omega(d\log(1/\epsilon)/\log\log)@@ 之类的弱式。本篇主定理已有 Lean 形式化，这两类风险已被大幅压低。
问 6：下界与 Kaczmarz 咬合，是否说明 Kaczmarz 就是最优算法？
答：只说明样本尺度最优：Kaczmarz 用约 @@M@@d\ln(1/\epsilon)@@ 条观测达到误差 @@M@@\epsilon@@，与下界同阶；但 Kaczmarz 存实数寄存器，内存按比特计可能远超 @@M@@Ad^2@@。论文未构造”同时满足 @@M@@d^2@@ 比特内存与 @@M@@O(d\log(1/\epsilon))@@ 样本”的匹配算法——上下界之间的算法空缺是留白，不是结论。
问 7：谁会用到它？
答：流式与内存受限学习理论社区（Steinhardt–Duchi、Raz 的内存–样本权衡一脉），以及关心”数据精度 vs 模型记忆”的机器学习理论研究者。对在线优化与随机化 Kaczmarz 的应用圈，它给出必须收取的样本税的精确尺度；姊妹篇用独立技术（副本耦合、二进制定位）得到同一下界，三重印证提高可信度。
总评
它干净地终结了”精确观测下精度代价”的悬案，尺度与经典算法严丝合缝、模型宽松、并有 Lean 形式化背书，是高可信度的定理级结果；最大留白在算法侧——匹配内存与样本双预算的构造仍未给出。