线性模型早停的谱过滤

在正特征方向上，$1-\eta d_j$ 是每轮保留下来的残差比例。若 $d_j$ 大，残差迅速消失；若 $d_j$ 小，要很多轮才追上响应。于是有限轮数天然抑制慢方向。但数据响应同时含信号和噪声，过滤器不会知道正在追上的是哪一种。

图采用后面的两方向模型。第一方向有信号且学得快，第二方向只含噪声且学得慢。第二轮以后，大部分信号已学到，继续追逐响应主要增加噪声方差；训练损失仍然下降。

从一维递推得到过滤因子 ​

令 $a_{j,t}=v_j^{\mathsf{T}}{\beta }_t$，将式(1)投影到 $v_j$，得到

有限几何级数求和给 $a_{j,t}=g_t(d_j)u_j^{\mathsf{T}}Y/\sqrt{n{d}_j}$，从而得到式(3)。在 $\ker X$ 上梯度恒为零，零初始化一直保持零；没有必要对零特征值写含 $1/\sqrt{d}$ 的表达式。若 $X=0$，单独规定 ${\beta }_t=0$、$S_t=0$ 即可。

再把误差写成 ${\hat{\mu }}_t-\mu =(S_t-I)\mu +S_t\epsilon$。第一项固定，第二项均值零，交叉项的期望消失；其平方范数期望为 ${\sigma }^2\mathrm{tr}(S_t{S}_t^{\mathsf{T}})$。$S_t$ 对称，再按正交特征方向求和，就证明式(4)、(5)。这是偏差—方差分解理路偏差、方差与均方误差Bias–variance decomposition · Mean squared error平方损失下将点态估计风险精确拆成抽样波动与系统位移，并说明两者的权衡边界。的向量版本，不要求噪声正态或各坐标独立，同方差不相关已足够。

两个特征值，第三轮开始付出更多噪声代价 ​

取 $n=p=2$，

这里 $U=I_2$，所以坐标就是特征方向，第一方向有信号、第二方向没有。过滤因子为 $g_t(d_1)=1-2^{-t}$、 $g_t(d_2)=1-(19/20{)}^t$。直接代入式(5)得

训练目标的期望则是

下面按同一固定模型重新抽取训练噪声，数值取六位小数。最后一列是均值风险，不含新响应本身的噪声。

从第二轮到第三轮，偏差平方从 $1/8$ 降到 $1/32$，但方差从 $0.286003125$ 升到 $0.3929834453125$，合计风险反而增加。风险曲线有一个较早的好位置，而训练优化的终点是继续吸收全部噪声。

这确实对应一种测试风险 ​

令独立新响应 $Y^{\prime }=\mu +{\epsilon }^{\prime }$ 在相同两个设计点生成，均值零噪声独立于训练资料，协方差也为 $I_2$。则

因此第三轮的同设计测试响应风险比第二轮高，虽然训练目标仍下降。它不是对某一次有限测试集随机分数必然上升的断言，而是对这个明确测试分布的期望风险结论。

若改成任意新输入分布，式(4)不能直接迁移。线性真模型下，令未来输入二阶矩为 ${\mathrm{\Sigma }}_{\ast }$，风险须用 $\mathbb{E}[({\beta }_t-{\beta }^0{)}^{\mathsf{T}}{\mathrm{\Sigma }}_{\ast }({\beta }_t-{\beta }^0)]$ 重算。只有例如 ${\mathrm{\Sigma }}_{\ast }⪯C\mathrm{\Gamma }$ 这类额外比较条件，才能从原设计均值误差得到相应上界。训练从未看到的零空间方向尤其不能由早停创造信息。

早停与 ridge 只是在尺度上相近 ​

线性核的岭回归理路核岭回归kernel ridge regression · KRR · least-squares regularization network用表示定理把 RKHS 平方损失正则化化为一个 Gram 线性系统。在参数空间中对应目标 $\Vert X\beta -Y{\Vert }_2^2/(2n)+(\lambda /2)\Vert \beta {\Vert }_2^2$，等价于将整个目标乘二后得到 KRR 页的平均平方损失加 $\lambda \Vert \beta {\Vert }_2^2$。因此其训练过滤因子为 $g_{\lambda }^{\mathrm{r}\mathrm{i}\mathrm{d}\mathrm{g}\mathrm{e}}(d)=d/(d+\lambda )$。对单个方向，给定 $t\ge 1$ 且 $0<g_t(d)<1$，可解出与早停匹配的

但这通常依赖 $d$。上例 $t=2$，第一方向要求 $\lambda =1/3$，第二方向要求 $\lambda =361/390$，不存在一个共同正则参数使两个预测过滤器完全相同。

当 $\eta td$ 很小时，$g_t(d)\approx \eta td$；岭过滤器在 $d\ll \lambda$ 时约为 $d/\lambda$，所以 $\lambda \approx 1/(\eta t)$ 是小特征值区的尺度对应。它不是全部谱上的恒等式；$\eta d=1$ 时早停一轮已完全拟合该方向，而任何有限正 $\lambda$ 的 ridge 仍有收缩。

训练下降为何没有阻止风险上升 ​

对每一个已经观察到的 $Y$，训练目标可精确写成

在主步长条件下，每个平方残差因子都不增，所以训练目标逐轮不增。这项结论不需要统计模型。式(5)却多出 $g_t(d_j{)}^2$ 的噪声项，它逐轮增加；两个目标优化的是不同量。这就是训练下降不能推出测试改善的证明机制。

收敛本身允许更宽的区间 $0<\eta <2/d_{max}$。但当某个 $\eta d_j>1$ 时，残差符号交替，$g_t(d_j)$ 可能大于一，方差也未必随 $t$ 单调。上述“逐方向从零向一吸收”的图像只在本页更窄的非振荡区间成立。线性平方损失的隐式偏置理路线性平方损失的隐式偏置Implicit bias in linear regression · Gradient descent minimum-norm bias · 线性回归隐式正则化证明固定步长梯度下降在任意线性平方损失上保留初始零空间分量，并选择离初值最近的最小二乘解。详细处理一般初始化与最小二乘极限；该页使用未归一化损失，其步长应换成这里的 $\eta /n$。

参数误差还要支付小特征值与零空间的代价 ​

若 $\mu =X{\beta }^0$，由式(3)可进一步得到

预测风险中每个已学方向的噪声代价是 ${\sigma }^2{g}_t^2/n$，参数风险中却多了 $1/d_j$。弱方向对系数估计特别昂贵；完全为零的方向还留下不可消除的真参数分量。早停是风险权衡，不能把不可识别参数变成可识别。

按有限预算返回，不必形成谱矩阵 ​

实现式(1)只需保存当前 ${\beta }_t$，每轮计算残差 $Y-X{\beta }_t$，再乘 $X^{\mathsf{T}}$ 并更新。按预定非负整数 $T$ 执行恰好 $T$ 轮，返回 ${\beta }_T$；若需训练拟合，再计算 $X{\beta }_T$。$T=0$ 直接返回零向量。

谱分解是本页分析工具，不是执行这条迭代的必需步骤。稠密实数算术下，每轮两个矩阵—向量乘法与向量更新共需 $O(np+n+p)=O(np)$ 工作，$T\ge 1$ 时共 $O(Tnp)$；额外工作空间为 $O(n+p)$，另计设计数据存储和输出。稀疏实现每轮为 $O(\mathrm{nnz}(X)+n+p)$。这些口径不包含浮点精度或取得可靠步长上界的成本，也没有把训练轮数和样本数量当成同一预算。

已知半径与方差时，不看响应也能选择停止点 ​

现在额外假设 $\mu =X{\beta }^0$，且在看到当前训练响应前，已经给定可靠的上界 $\Vert {\beta }^0{\Vert }_2\le R$ 和精确噪声方差 ${\sigma }^2$。$R\ge 0$；噪声条件仍是均值零及 $\mathrm{Cov}(\epsilon \mid X)={\sigma }^2{I}_n$。不需要 Gaussian 分布。固定非空有限网格 $\mathcal{T}\subset \{0,1,2,\dots \}$，并保留 $0<\eta \le 1/d_{max}$。网格与步长可以根据设计制定，但此后不根据当前响应、训练损失或拟合路径改变。

令 $a_t(d)=(1-\eta d{)}^t$，特别规定 $a_0(d)=1$。对非零设计定义

这不只是一个方便的上界。写 ${\mathcal{R}}_t(\beta )$ 表示真均值为 $X\beta$ 时的式(4)，则

证明从式(5)出发。令 $b_j=v_j^{\mathsf{T}}\beta$，则 ${\theta }_j=\sqrt{n{d}_j}{b}_j$，且没有 ${\mu }_{\perp }$ 项，于是

由于 $\sum _j{b}_j^2\le \Vert \beta {\Vert }_2^2\le R^2$，偏差平方至多是式(10)的第一项。反过来，取一个最大化 $d_j{a}_t(d_j{)}^2$ 的方向 $j_{\ast }$，并令 $\beta =R{v}_{j_{\ast }}$，便达到这个值；噪声项不随 $\beta$ 改变。若 $R=0$，唯一的真参数为零，同一等式仍成立。不同轮数的最坏方向可以不同，证明并没有要求一根向量同时使所有轮次达到最坏情形。

因此，可用确定的并列规则选择

符号上写了帽子，$\hat{t}$ 却只依赖 $X,\eta ,R,{\sigma }^2,\mathcal{T}$，并不读取 $Y$。给定这些输入后它就是固定整数，所以原来的风险恒等式直接适用。式(12)的极小极大结论只在网格列出的确定轮数之间比较：它没有在所有估计器、依赖响应的停止规则或随机混合规则之间求最优，也没有声称对每个真参数都选到其风险最小的那一轮。改变网格可能改变答案；渐近最优速率也不由这条有限比较自动得到。

零特征方向不贡献原设计上的预测偏差或方差。若把它们也列入式(10)，其贡献仍为零；不需要除以 $d_j$。$t=0$ 时所有 $a_0=1$、方差为零，故 $U(0)=R^2{d}_{max}$，包括有方向满足 $\eta d_j=1$ 的情形。若 $X=0$，在线性真模型下也有 $\mu =0$，直接定义所有 $U(t)=0$ 并返回 $min\mathcal{T}$；这里不定义 $1/d_{max}$。

同一设计，从事后看风险到事前作选择 ​

沿用双特征值设计，但选择时不再使用已知的具体信号 $\mu =(2,0)$。只给出 $R^2=2$、${\sigma }^2=1$、$\eta =1/2$ 和 $\mathcal{T}=\{0,1,\dots ,12\}$。式(10)变成

前四个值为 $U(0)=2$、$U(1)=501/800$，以及

第二轮的最坏偏差来自慢的第二方向，因为 $\frac{1}{10}(19/20{)}^4>1/16$；取 $\beta =\sqrt{2}{v}_2$ 达到包络。原先例子的真参数是 $\sqrt{2}{v}_1$，所以它在同一轮的风险 $0.411003125$ 严格小于包络，二者回答的是不同的信号信息量。

要排除网格中余下的轮数，可以只看方差：它逐轮不减，而且

因此 $4\le t\le 12$ 都不可能胜过第二轮，得到 $\hat{t}=2$。这个选择在读入标签之前已经完成；随后才按式(1)执行两次更新。同设计独立新响应的最坏风险再加 ${\sigma }^2=1$，即 $1.448904375$，停止选择不变。

如何计算，以及哪些信息不能省略 ​

若正特征值已经给定，可以从 $a_{j,0}=1$ 开始逐轮更新 $a_{j,t+1}=(1-\eta d_j)a_{j,t}$，到达网格点时计算式(10)，保留风险最小且轮数最早的候选。若网格按轮数递增给出，令 $M=max\mathcal{T}$，顺序扫描需要 $O(r(M+1)+|\mathcal{T}|)$ 次实数算术与 $O(r)$ 额外工作空间，输入网格存储另计；无需保存整条训练路径。任意顺序的网格列表须先排序，另需 $O(|\mathcal{T}|\log (1+|\mathcal{T}|))$ 次比较。稀疏网格也可以在各点用整数快速幂，但应把求幂成本算进去。附带复算程序采用后一种直接算法：它先排序、去重，再对每个候选独立求幂，没有实现逐轮扫描。若输入列出 $q$ 个特征值（可以含零），网格列表长度为 $m$，其单位成本算术与比较工作为 $O(mq\log (2+M)+m\log (1+m))$，$M=0$ 也适用。精确分数的分子、分母会随轮数增长，这个算术次数界不是有理数位复杂度界。

这个选择步骤与前面“给定 $T$ 后直接迭代”的成本不同。它确实需要谱信息；若从稠密 $X$ 计算全部正特征值，常规稠密 SVD 的算术成本为 $O(npmin(n,p))$。选好 $\hat{t}$ 后，再支付前面说明的梯度迭代成本。这些是单位成本实数算术口径，既没有包含精度认证，也没有把近似特征值算出的数自动当成严格风险证书。谱很大时，计算完整包络未必比训练更便宜。

半径和噪声模型也是真正的输入条件。半径取大仍给可靠但可能保守的保证；取小到不再覆盖真参数，则连上界都可能失效。例如错误地用 $R^2=1$ 计算上面的第二轮，得到 $293963/800000$；真参数若为 $\sqrt{2}{v}_2$，实际风险仍是 $718247/1600000$，高于这个数。

若只知道 $\mathrm{Cov}(\epsilon \mid X)⪯{\overline{\sigma }}^2{I}_n$，以 ${\overline{\sigma }}^2$ 代入仍能得到上界，因为方差至多为 ${\overline{\sigma }}^2\mathrm{tr}(S_t^2)/n$；但对实际噪声的精确等式(11)与由此得到的极小极大等式(12)便不再有保证。仅有次高斯上尺度也不能推出噪声方差恰好等于该尺度的平方，更不能据此断言正的方差下界：零噪声满足任意正的次高斯上尺度。若实际协方差为已知 $\mathrm{\Omega }$，精确方差应改为 $\mathrm{tr}(S_t\mathrm{\Omega }{S}_t^{\mathsf{T}})/n$；随意把它换成一个平均方差会改变所选规则与证书。

从当前响应估计 $R$ 或 ${\sigma }^2$ 再代入，也不属于已证明的设计先定规则。即使一个方差估计无偏，由它选出的轮数仍可能依赖训练噪声。若 $\mu \notin \mathrm{col}(X)$，则式(5)的不可表示误差也不能被参数球包络省略。所需的新分析分别是输入预算的可靠性、实际停止规则的统计风险，或模型错设误差，而不是把未知量换成一个数后沿用原等式。

选停止点时保留数据角色 ​

式(4)对预先固定的 $t$ 成立；若 $t,\eta$ 只由设计和独立 pilot 资料确定，可先条件于那些已经冻结的信息，再重新生成这里的训练响应。若从当前响应生成一整条拟合路径，再用独立验证集挑出某轮，所选 $t$ 仍通过候选路径依赖当前训练噪声，不能声称条件于这个 $t$ 后式(4)原样成立。

独立验证依然有价值：它比较候选的测试表现，而非训练残差。应预定候选轮次、验证损失和并列规则，并用未参与选择的测试资料评价整个结果；训练、选择与评价隔离理路留出法与交叉验证Holdout · Cross-validation · 交叉验证通过隔离训练、模型选择和最终评价的数据角色估计样本外风险，并识别反复查看测试集造成的选择偏差。说明了这些角色。也有直接分析数据依赖停止规则的理论，但它需要对实际规则另作证明，不能靠固定时刻公式代替。

正则化学习保证终点练习要求复算上述第三轮风险、比较 ridge 定标，并判断更换测试设计和随机停止规则后哪些结论仍保留。可选题进一步要求从已知半径与方差真正选出轮数，再把步长改到非振荡区间的端点，检查停止选择、零轮约定与错误预算的后果。精确分数复算程序只使用 Python 标准库，输出两个网格的完整风险比较；它不读取标签，也不代替式(11)的证明。