Ch15.1.5 回归下界：从参数打包到函数空间

来源：Francis Bach，Learning Theory from First Principles，锁定版本 §15.1.1–15.1.5，印刷页 428–438；依据 2026-10-15 学习讨论整理，2026-10-16 整理成文。状态：note_unverified。本文为助手辅助讲解整理，包含 Exercise 15.1 的参考推导，不代表学习者已独立完成证明或掌握整章。

1. 下界究竟限制什么

固定设计线性回归的观测模型是

\[ y=\Phi\theta^*+\varepsilon,\qquad \varepsilon\sim N(0,\sigma^2I_n),\qquad \Theta=\{\theta\in\mathbb R^d:\|\theta\|_2\le D\}. \]

设计矩阵 \(\Phi\) 已知且固定，真参数 \(\theta^*\) 未知。估计器 \(\widehat\theta\) 根据观测产生参数估计。以下假设 \(D,\sigma>0\)；\(D=0\) 时参数已知，下界为零。

一个估计器在一个真参数下的风险为

\[ R(\widehat\theta,\theta^*) =\mathbb E_{\theta^*}\|\widehat\theta-\theta^*\|_2^2. \]

期望对训练噪声及算法可能的随机性取。极小极大风险为

\[ R^*=\inf_{\widehat\theta}\sup_{\theta^*\in\Theta} \mathbb E_{\theta^*}\|\widehat\theta-\theta^*\|_2^2. \]

\(R^*\ge L\) 表示每一种估计方法在整个参数球上的最坏情况风险都至少为 \(L\)，不表示每个参数下、每次观测后的误差都至少为 \(L\)。例如总输出零的估计器在 \(\theta^*=0\) 时没有误差，但不能同时准确估计其他参数。

2. 预测误差中的 n 到哪里去了

本例假设非中心经验二阶矩满足

\[ \frac1n\Phi^\top\Phi=I_d. \]

这表示设计矩阵各列正交、每列平方范数为 \(n\)，并要求 \(n\ge d\)。令 \(u=\theta-\theta'\)，则

\[ \begin{aligned} \delta(\theta,\theta')^2 &=\frac1n\sum_{i=1}^n[f_\theta(x_i)-f_{\theta'}(x_i)]^2\\ &=\frac1n\|\Phi u\|_2^2 =u^\top\left(\frac{\Phi^\top\Phi}{n}\right)u =\|u\|_2^2. \end{aligned} \]

\(n\) 与 \(\Phi^\top\Phi=nI_d\) 中的因子抵消了。没有这个假设，预测误差一般是由 \(\Phi^\top\Phi/n\) 加权的参数误差。

“过量测试误差”在这里使用固定设计点上的预测度量。若在相同设计点生成独立测试标签，平方损失的期望等于 \(\sigma^2+\mathbb E\delta(\widehat\theta,\theta^*)^2\)；减去噪声风险 \(\sigma^2\)，才是这里的过量风险，不是训练残差，也不自动对应任意新输入分布。

3. 为什么要构造候选参数

选出 \(M\) 个候选 \(\theta_1,\ldots,\theta_M\in\Theta\)。对任何估计器，

\[ \sup_{\theta^*\in\Theta}R(\widehat\theta,\theta^*) \ge\frac1M\sum_{j=1}^M R(\widehat\theta,\theta_j). \]

所以，只要证明在这个有限子集上的平均风险不能太小，就能得到整个参数球的最坏风险下界。候选必须兼顾两件事：参数分得够开，使认错有误差代价；数据分布又要足够难分，使认错概率不太小。

3.1 打包约束与阈值 a

用 \(a>0\) 表示平方误差阈值，避免与原书估计器记号混淆。要求

\[ \min_{i\ne j}\delta(\theta_i,\theta_j)^2\ge4a. \]

根据估计值选择最近候选 \(\widehat J=\arg\min_k\delta(\widehat\theta,\theta_k)\)。真候选为 \(\theta_j\)、却选择 \(\theta_k\) 时，由最近候选规则与三角不等式，

\[ 2\sqrt a\le\delta(\theta_j,\theta_k) \le\delta(\theta_j,\widehat\theta)+\delta(\widehat\theta,\theta_k) \le2\delta(\theta_j,\widehat\theta). \]

因此认错意味着平方误差至少为 \(a\)。这里保留非严格不等号，可涵盖平局：

\[ \frac1M\sum_j\mathbb E_j\delta(\theta_j,\widehat\theta)^2 \ge a\frac1M\sum_jP_j(\widehat J\ne j). \]

例如候选为 \(-2,2\)，若真值是 \(-2\) 却选到 \(2\)，估计值至少到达中点 \(0\)，平方误差至少为 \(4\)。两候选平方距离为 \(16=4a\)，这里可取 \(a=4\)。

3.2 Fano 控制的是识别错误概率

令编号 \(J\) 在 \(\{1,\ldots,M\}\) 上均匀分布，给定 \(J=j\) 时数据 \(\mathcal D\) 服从 \(P_j\)。推论 15.1 给出

\[ P_e=P(\widehat J\ne J) \ge1-\frac{\overline{\mathrm{KL}}}{\log M}-\frac{\log2}{\log M}, \qquad \overline{\mathrm{KL}}=\frac1{M^2}\sum_{i,j}D_{\mathrm{KL}}(P_i\|P_j). \]

其来源是互信息形式的 Fano 不等式及 \(I(J;\mathcal D)\le\overline{\mathrm{KL}}\)。这里的对数为自然对数。

Fano 本身不要求 \(P_e\ge1/2\)。为了得到方便的常数下界，我们主动采用充分条件

\[ \overline{\mathrm{KL}}\le\tfrac14\log M, \qquad M\ge16. \]

于是 \(P_e\ge1-1/4-1/4=1/2\)，进而 \(R^*\ge a/2\)。两个 \(1/4\) 是一种充分条件的分配，不是从 \(P_e\ge1/2\) 反推出来的必要条件，也不是唯一可选的常数。

4. 引理 15.2 与 beta 的引入

4.1 从编码结构到几何尺度

引理 15.2（Varshamov–Gilbert）在 \(\alpha=1/2\) 时，给出 \(v_1,\ldots,v_M\in\{0,1\}^d\)，满足

\[ M\ge e^{d/8},\qquad h(v_i,v_j)\ge d/4\quad(i\ne j). \]

\(h\) 是不同坐标的数量。\(v_j\) 是构造的编码向量，与训练输入 \(x_i\) 不同；\(M\) 是候选数量，\(n\) 是观测数量。

先把 \(0/1\) 变成 \(-1/+1\)，再引入可调的缩放系数 \(\beta>0\)：

\[ \theta_j=\beta(2v_j-\mathbf1_d)\in\{-\beta,\beta\}^d. \]

\(\beta\) 是证明者选择的候选尺度，不是从数据估计的未知参数，也不是学习算法的超参数。

4.2 范数与双边距离

\[ \|\theta_j\|_2^2=d\beta^2, \qquad \|\theta_i-\theta_j\|_2^2=4\beta^2h(v_i,v_j). \]

所以

\[ \beta^2d\le\|\theta_i-\theta_j\|_2^2 \le4\beta^2d\le32\beta^2\log M. \]

左端来自 \(h\ge d/4\)，中间来自 \(h\le d\)，最后一步来自 \(d\le8\log M\)。

4.3 KL 约束如何限制 beta

候选 \(\theta_j\) 对应观测分布 \(P_j=N(\Phi\theta_j,\sigma^2I_n)\)。同协方差高斯分布的 KL 为

\[ D_{\mathrm{KL}}(P_i\|P_j) =\frac1{2\sigma^2}\|\Phi(\theta_i-\theta_j)\|_2^2 =\frac n{2\sigma^2}\|\theta_i-\theta_j\|_2^2. \]

要求统一上界不超过 \(\tfrac14\log M\)：

\[ 32\beta^2\log M\frac n{2\sigma^2}\le\frac14\log M \quad\Longleftrightarrow\quad \beta^2\le\frac{\sigma^2}{64n}. \]

这是为了使用 Fano 而施加的选择条件，不是任意 \(\beta\) 都自动满足的事实。固定噪声与样本数时，\(\beta\) 增大使候选更容易识别，但认错的代价更大；\(\beta\) 减小则相反。

5. 从两个约束到式（15.10）

现在有两条不同的推理线：

已知条件	用途
\(\beta^2\le\sigma^2/(64n)\) 且 \(M\ge16\)	Fano 保证平均识别错误概率至少为 \(1/2\)
\(\\|\theta_i-\theta_j\\|^2\ge\beta^2d\)	可令 \(4a=\beta^2d\)，认错时平方误差至少为 \(a\)

因此 \(a=\beta^2d/4\) 并不是从 KL 条件中推出来的，而是从距离下界中选出来的。合并两条线得到

\[ R^*\ge\frac a2=\frac{\beta^2d}{8}. \]

还要保证候选在参数球内，即 \(\beta^2d\le D^2\)。在两个限制下选最大的 \(\beta\)：

\[ \beta^2=\min\left\{\frac{D^2}{d},\frac{\sigma^2}{64n}\right\}, \qquad R^*\ge\frac18\min\left\{D^2,\frac{\sigma^2d}{64n}\right\}. \tag{15.10} \]

当 \(D^2\ge\sigma^2d/(64n)\) 时，下界为 \(\sigma^2d/(512n)\)。普通最小二乘有

\[ \widehat\theta_{\mathrm{OLS}}-\theta^*=\frac1n\Phi^\top\varepsilon, \qquad \mathbb E\|\widehat\theta_{\mathrm{OLS}}-\theta^*\|^2=\frac{\sigma^2d}{n}. \]

若估计器必须取值于 \(\Theta\)，将最小二乘估计投影回球内不会增加误差。零估计器的最坏风险又不超过 \(D^2\)，因此完整风险的量级为 \(\min\{D^2,\sigma^2d/n\}\)。

维数条件。 本条 Fano 推导还要求 \(M\ge16\)。仅由 \(M\ge e^{d/8}\)，在整数 \(d\ge23\) 时可直接保证该条件；小维数不能跳过这一步。下一节给出对所有 \(d\ge1\) 可用、但常数更松的体积构造，保证同阶结论，不声称由此逐字补齐式（15.10）的全部数值常数。

6. Exercise 15.1：改用引理 15.1

以下是助手补充的参考推导。打包约束是一项要求；引理 15.1 和引理 15.2 是满足要求的两种工具。

引理 15.1 说：单位球中两两距离至少为 \(2\epsilon\) 的点的最大数量 \(M\) 满足

\[ (2\epsilon)^{-d}\le M\le(1+\epsilon^{-1})^d. \]

这里的上界是点数的上界。两点距离的上界来自球的直径，不能混淆。

取 \(0<r\le D\)，把单位球内的打包缩放到半径 \(r\) 的球内。选 \(\epsilon=1/4\)，则

\[ M\ge2^d,\qquad \frac{r^2}{4}\le\|\theta_i-\theta_j\|^2\le4r^2. \]

右端由三角不等式得到。于是 KL 的统一上界为 \(2nr^2/\sigma^2\)。由于 \(\log M\ge d\log2\)，充分条件是

\[ \frac{2nr^2}{\sigma^2}\le\frac{d\log2}{4}, \qquad r^2\le\frac{\sigma^2d\log2}{8n}. \]

取 \(a=r^2/16\)，并选允许的最大半径，得到

\[ R^*\ge\frac1{32}\min\left\{D^2,\frac{\sigma^2d\log2}{8n}\right\}. \]

此构造在 \(d\ge4\) 时由 \(M\ge2^d\) 保证 \(M\ge16\)。若要求统一覆盖所有 \(d\ge1\)，改取 \(\epsilon=1/32\)：此时 \(M\ge16^d\)，\(a=r^2/1024\)，从而

\[ R^*\ge\frac1{2048}\min\left\{D^2,\frac{\sigma^2d\log16}{8n}\right\}. \]

常数变松，但仍得到 \(\min\{D^2,\sigma^2d/n\}\) 的量级。

7. 随机设计与 Hilbert 空间中的非参数估计

7.1 未知对象从向量变为函数

随机设计回归为

\[ X_i\overset{\mathrm{i.i.d.}}\sim p,\qquad Y_i=f^*(X_i)+\varepsilon_i, \qquad \varepsilon_i\overset{\mathrm{i.i.d.}}\sim N(0,\sigma^2), \]

噪声与输入独立。若仍为有限维线性模型并有 \(\mathbb E[\phi(X)\phi(X)^\top]=I_d\)，则总体预测距离仍等于参数距离。非参数设置则不预先把所有目标函数限制在固定的有限维模型中。

例如已知目标为直线 \(f(x)=ax+b\) 时，只需估计两个数；若目标可在一整个受约束的函数类中变化，则通常需要无穷多个系数来描述。

Hilbert 空间 \(L^2(p)\) 用

\[ \langle f,g\rangle_{L^2(p)}=\int f(x)g(x)\,dp(x), \qquad \|f-g\|_{L^2(p)}^2=\mathbb E_{X\sim p}[f(X)-g(X)]^2 \]

定义函数的内积与距离；相差仅在 \(p\)-零测集上的函数视为同一个元素。观测模型可选取可测代表，这不会改变数据分布或风险。本节的极小极大风险是

\[ \inf_{\widehat f}\sup_{f^*\in\mathcal F} \mathbb E_{\mathcal D}\|\widehat f-f^*\|_{L^2(p)}^2. \]

7.2 椭球约束如何表达

设 \(T\) 是紧、半正定、自伴算子，正特征值 \(\lambda_1\ge\lambda_2\ge\cdots>0\) 对应正交归一特征函数 \(\psi_m\)。在这些正特征方向上定义函数类

\[ \mathcal F= \left\{f=\sum_{m\ge1}c_m\psi_m: \sum_{m\ge1}\frac{c_m^2}{\lambda_m}\le D^2\right\}. \]

书中用 \(\theta\) 表示这里的函数，并简写为 \(\langle\theta,T^{-1}\theta\rangle\le D^2\)。严格地说，这是 \(\|T^{-1/2}\theta\|^2\) 的二次型写法，定义在 \(T^{1/2}\) 的值域上，不应额外假定每个这样的函数都在算子 \(T^{-1}\) 的定义域内。若 \(T\) 有核，以上函数类不包含核方向的自由分量。

二维对应式为 \(c_1^2/\lambda_1+c_2^2/\lambda_2\le D^2\)，半轴长度是 \(D\sqrt{\lambda_1},D\sqrt{\lambda_2}\)。无穷维椭球同样限制每个方向的系数；光滑性解释取决于具体的基与权重，并非任意特征序号都自动代表频率。

7.3 无限维为什么能做有限计算

只选前 \(K\) 个正特征方向构造候选：

\[ f_i=\beta\sum_{m=1}^{K}(2(v_i)_m-1)\psi_m, \qquad v_i\in\{0,1\}^K. \]

后面的系数精确为零。这些是原函数类中的特定函数，不是对任意真函数进行截断近似，因此这一步不产生截断偏差。对任何估计器，完整函数类上的最坏风险至少是这个有限候选集上的平均风险；也没有要求估计器只能在前 \(K\) 个方向中输出。

由正交归一性，

\[ \left\|\sum_{m=1}^{K}(c_m-b_m)\psi_m\right\|_{L^2(p)}^2 =\sum_{m=1}^{K}(c_m-b_m)^2. \]

函数距离因此化为有限维系数距离。用引理 15.2，得到

\[ M\ge e^{K/8},\qquad \beta^2K\le\|f_i-f_j\|_{L^2(p)}^2 \le4\beta^2K\le32\beta^2\log M. \]

系数核对： 距离下界是 \(\beta^2K\)，来自 \(4\beta^2(K/4)\)，不是 \(4\beta^2K\)。

候选的椭球约束为

\[ \sum_{m=1}^{K}\frac{\beta^2}{\lambda_m} \le\frac{K\beta^2}{\lambda_K}\le D^2. \]

最后一个条件是方便的充分条件，并非精确刻画所有可行尺度。随机设计下，联合数据分布满足

\[ D_{\mathrm{KL}}(P_i\|P_j) =\frac n{2\sigma^2}\|f_i-f_j\|_{L^2(p)}^2. \]

因此再次要求 \(\beta^2\le\sigma^2/(64n)\)，并取 \(a=\beta^2K/4\)。在候选数量满足 \(M\ge16\) 时，选择

\[ \beta^2=\min\left\{\frac{D^2\lambda_K}{K},\frac{\sigma^2}{64n}\right\} \]

得到

\[ R^*\ge\frac{\beta^2K}{8} =\frac18\min\left\{D^2\lambda_K,\frac{\sigma^2K}{64n}\right\}. \]

等号依赖于上述最大可行尺度的选择，不能对任意满足上界约束的 \(\beta\) 都写出这个等号。仅凭引理的数量保证，\(K\ge23\) 足以使用这组 Fano 常数。选取更强打包或另作小维数分析可以处理其余情形。

8. 接下来要补的推导

本文整理到“无限维函数类里选有限维候选，再优化候选尺度”的论证。后续待展开的数学内容包括：

Sobolev 光滑性如何对应 \(T\) 与特征值衰减 \(\lambda_K\)；需要哪些定义域和分布条件。
在 \(\lambda_K\ge CK^{-\alpha}\)、\(\alpha=2s/d\) 下，如何选择整数 \(K\)，并处理 \(K\ge1\)、候选数量及小样本边界，得到适用范围内的 \(n^{-2s/(2s+d)}\) 量级。
Fano 不等式与引理 15.1、15.2 的完整证明，以及 §15.1.6 贝叶斯下界。

相关正文：Ch3 岭回归与极小极大下界、Ch7.6 核岭回归理论、阅读映射。