主要先修：8.5 其他不等式、18.6 多重检验与错误率、20.5 预测、正则化与模型选择。
这是从不等式、多重检验和模型选择进入的高维分支，不必先完成23.2–23.3。用23.2的信息下界可以进一步比较上界是否可改进。 查看全书依赖图与分支路线。
23.4.1 为什么单个方法的保证不够
若先看数据再选一个表现最好的模型，选中模型的训练误差通常偏低。第18.6节用同时错误率处理多个检验，本节对一组候选预测规则控制训练误差与总体风险的最大差异。该保证使数据选择后的规则也能纳入比较，条件是候选集合及评价损失的使用方式已被正确说明。
设\(Z_1,\ldots,Z_n\) iid来自\(P\)，候选类\(\mathcal F\)在使用这批样本之前固定，包含\(M\)个可测规则。对每个规则，损失\(\ell_f(Z)\in[0,1]\)。定义
经验风险最小化（ERM）取\(\widehat f\in\arg\min_f\widehat R_n(f)\)，并预先固定并列处理规则。超额风险是\(R(\widehat f)-R(f^*)\)，比较对象是同一候选类中最好的规则，而非所有可能预测方法中的最优者。
二分类的零一损失满足有界条件，普通平方损失通常不满足。把无界损失代入本节的同一Hoeffding公式不合法，必须另加尾部或矩条件。此处的总体风险表示独立未来数据上的期望，与第23.1节估计未知参数的风险形式有关，但目标及观测机制需要分别定义。
23.4.2 有限候选类的一致界
给定\(0<\alpha<1\)，令\(\varepsilon_{n,M}=\sqrt{\log(2M/\alpha)/(2n)}\)，其中对数取自然对数。则以至少\(1-\alpha\)的概率，
完整证明。对每个预先固定的\(f\)，损失值是iid有界变量，第8.5节的Hoeffding不等式给出\(P(|\widehat R_n(f)-R(f)|>\varepsilon)\le2e^{-2n\varepsilon^2}\)。取有限并集，失败概率不超过\(2Me^{-2n\varepsilon^2}\)，代入所定义的\(\varepsilon_{n,M}\)即得第一项。同时控制事件上，选中规则仍在集合中，因此
中间项由ERM不大于零，两侧均由统一事件控制。这个证明没有把随机的\(\widehat f\)误当成固定规则使用单个Hoeffding界。证毕。
若优化算法仅达到\(\widehat R_n(\widehat f)\le\min_f\widehat R_n(f)+\eta\)，结论增加\(\eta\)。候选类允许随\(n\)预先变化，令规模为\(M_n\)；当\(\log M_n/n\to0\)时，对任意固定正误差阈值，统一偏差趋于零。若先使用独立训练集生成有限候选模型，再用这批iid样本选择，可给定训练集应用同一证明；若候选模型直接在评价样本上拟合，不能仅按最后留下的模型数套用本命题。
取\(n=200,M=8,\alpha=0.05\)，则\(\log(320)\approx5.76832\)，统一偏差界约为\(0.12009\)，ERM超额风险界约为\(0.24017\)。这可能比实际误差保守，但确是有限样本上界。若希望统一偏差不超过\(0.1\)，充分样本量为\(n\ge\log(320)/(2\cdot0.1^2)\)，取整数得到289。若要求超额风险不超过\(0.1\)，则需\(\varepsilon\le0.05\)，同一方法给出至少1154个样本。
23.4.3 无限类需要定义复杂度
无限候选类不能把\(M=\infty\)代入后仍称得到有用界。覆盖数是在指定距离下，用有限多个半径\(r\)的球覆盖函数类所需的最小数量；使用它还要控制近似误差、选择合适距离并处理可测性。VC维数针对二分类类，定义为能够实现全部\(2^k\)种标签的最大点集大小。这些量不是参数数目的另一种写法；即使参数有限，规则类的结构仍影响统一收敛。
例如实轴阈值分类器\(f_t(x)=\mathbf1_{\{x\ge t\}}\)可打散任意一个点，却不能对两个有序点实现“左点为1、右点为0”的模式，故VC维数为1。与之相对，若允许记忆任意有限训练集，对连续输入分布可以令训练误差为零，未来误差仍为一：设真实标签总为1，规则只在出现过的训练输入上输出1，在其他位置输出0。每个固定有限记忆集合的未来概率为零。于是复杂度过大的类可能没有统一收敛；本节只解释覆盖数与VC维数的含义，完整无限类界见所列官方讲义。
23.4.4 高维回归：结构比惩罚名称更重要
令固定设计\(X\in\mathbb R^{n\times p}\)，\(y=X\beta^*+e\)。当\(p>n\)时，\(X^\mathsf TX\)奇异，不加结构通常无法区分\(\beta^*\)与\(\beta^*+v\)，其中\(Xv=0\)。ridge可以使优化问题唯一，却没有消除这种观测上的不可识别性。lasso能给出稀疏解，但一致估计和推断还需要真参数、设计及噪声条件。
取lasso目标\(\|y-X\beta\|^2/(2n)+\lambda\|\beta\|_1\)，\(\lambda>0\)，任取最小解\(\widehat\beta\)。假设真支撑\(S=\{j:\beta_j^*\ne0\}\)大小为\(s\ge1\)，并且固定设计在锥\(\|v_{S^c}\|_1\le3\|v_S\|_1\)上满足受限特征值条件：
若同时\(\lambda\ge2\|X^\mathsf Te/n\|_\infty\)，则
完整证明。记\(\Delta=\widehat\beta-\beta^*\)。最小化不等式、展开平方和Hölder不等式给出
左侧非负，故\(\Delta\)在指定锥中。再有\(\kappa\|\Delta\|_2^2\le\|X\Delta\|^2/n\le3\lambda\|\Delta_S\|_1\le3\lambda\sqrt s\|\Delta\|_2\)。若误差为零，结论直接成立；否则除以误差范数得到第一界，代回中间不等式得预测误差界。证毕。
若噪声独立且\(e_i\sim N(0,\sigma^2)\)，各列\(\|X_j\|\le\sqrt n\)，则正态尾界与并集给出\(\|X^\mathsf Te/n\|_\infty\le\sigma\sqrt{2\log(2p/\alpha)/n}\)的概率至少为\(1-\alpha\)。因此选择其两倍作为\(\lambda\)可代入命题。要让参数误差趋零，还需\(\kappa\)保持正下界及\(s\log p/n\to0\)等条件；惩罚本身没有保证这些条件。稀疏估计误差界也不等于所选支撑准确恢复，后者需另加信号强度及设计条件。
23.4.5 模型选择之后的区间
设\(Z_j\)独立服从\(N(\theta_j,1)\)，\(j=1,\ldots,10\)，所有真均值为零。每个固定坐标的区间\([Z_j-1.959964,Z_j+1.959964]\)有95%覆盖。现在取\(J=\arg\max_j|Z_j|\)，只报告第\(J\)项。这个区间不覆盖\(\theta_J=0\)，当且仅当至少一个坐标的绝对值超过临界值，故失败概率为\(1-0.95^{10}\approx0.40126\)，覆盖只有约59.87%。选中结果的区间并未保留固定坐标的95%保证。
若用Bonferroni同时区间，每项双侧失败概率取\(0.05/10\)，临界值为\(z_{0.9975}\approx2.80703\)，全部区间同时覆盖概率至少95%。从这一同时事件上再选择任何坐标，都保留对所选参数的边际覆盖下界。这是第18.6节同时控制的区间版本。
另一种办法是样本拆分：A组选目标，B组独立估计。给定A，目标选择已经固定；若对每个可能选择，B上的程序在所声明模型中都有效，就能条件于A得到覆盖，再取期望得到边际覆盖。对所选回归子模型，必须明确估计的是完整模型中的系数还是子模型的投影系数；遗漏变量会改变目标，独立拆分本身不会修正模型偏误。
选择后推断还可通过条件于选择事件来构造截断分布下的检验和区间，需要具体选择算法与模型；不能将一个普遍的“选择校正因子”乘到所有标准误上。第19.4节的固定维Wald近似也不能直接移用于\(p/n\)不小的模型。预测效果、变量选择、参数估计和区间覆盖是四个不同任务，应分别给出保证。
23.4.6 习题与解答
习题23.4-1 · 给定误差的样本量
损失在\([0,1]\)，候选数\(M=100\)，希望以95%概率使ERM超额风险不超过0.2。用命题给出一个充分整数样本量。
需要\(\varepsilon\le0.1\)，所以\(n\ge\log(2\cdot100/0.05)/(2\cdot0.1^2)=\log(4000)/0.02\approx414.7025\)，取415。这个计算保证的是同一预先固定候选类中的超额风险，不保证总体风险小于0.2；若最好的候选规则本身风险较大，总体风险仍可较大。
习题23.4-2 · 近似优化与数据选择
在统一偏差不超过\(\varepsilon\)的事件上，算法的经验风险距离最小值不超过\(\eta\)。证明超额风险上界。另解释为何评价数据上拟合100个模型，不自动满足有限类\(M=100\)的条件。
重复三项风险分解，两边各不超过\(\varepsilon\)，中间项现在不超过\(\eta\)，故总差不超过\(2\varepsilon+\eta\)。在评价数据上拟合时，每个候选规则自身是随机的，其评价损失未必是固定函数的iid和；最后输出数量100不能说明所有可能拟合函数只有100个。可以使用独立训练集后条件应用有限类界，或直接分析完整函数类的复杂度。
习题23.4-3 · 高维的不可识别方向
设设计只有一行\(X=(1,1)\)，观测为\(y=\beta_1+\beta_2+e\)。比较参数\((1,0)\)与\((0,1)\)，说明为什么仅假设一稀疏仍不足以恢复参数，以及命题的设计条件在哪里失败。
两参数都只有一个非零坐标，却给出同一均值和相同噪声分布，因此观测规律完全相同。差向量\(v=(-1,1)\)满足\(Xv=0\)。以第一个参数支撑\(S=\{1\}\)考察，\(\|v_{S^c}\|_1=\|v_S\|_1=1\)，它在要求的锥内，而\(\|Xv\|^2/n=0\)不可能大于正的\(\kappa\|v\|^2\)。受限特征值条件失败，惩罚选择不能创造观测中不存在的信息。
习题23.4-4 · 选择失败概率与独立复核
将例23.4-2改为两个独立坐标。求原区间选择后失败概率。若用独立的新观测\(W_j\sim N(\theta_j,1)\)报告\([W_J\pm z_{0.975}]\)，其覆盖如何？
全零参数下原区间失败概率为\(1-0.95^2=0.0975\)，因为选择最大的绝对值。新观测向量与原向量独立；给定原数据及选中的\(J\)，\(W_J-\theta_J\)仍服从标准正态，故新区间的条件覆盖为95%。再对原数据取期望，边际覆盖也是95%。若继续依据新观测筛选坐标或改区间，这个固定选择后的条件论证就需重新检查。
关键术语
经验风险：评价样本上的平均损失；超额风险：相对候选类最优规则的总体风险差；统一偏差：全部候选规则的最大经验与总体风险差；ERM：经验风险最小化规则；覆盖数：指定距离和半径下有限近似的规模；VC维数：二分类类能打散的最大点数；稀疏性：真参数非零坐标数量的限制；受限特征值：设计在特定误差锥中的正曲率；选择后推断：把目标或模型选择计入覆盖与检验分析；样本拆分：用独立数据分别选择和评价。
参考文献
- Sivaraman Balakrishnan. CMU 36-705 Lecture 8, 2019年9月13日，§8.2–8.7。统一收敛、过大函数类反例和经验风险的分解。
- Sivaraman Balakrishnan. CMU 36-709 Lecture 12: Estimation Error Bounds for the LASSO, 2020年2月27日，§12.2。稀疏回归与受限特征值条件；本节独立给出所用惩罚形式及常数的证明。