Minimax Limits of k-Fold Cross-Validation via Majority¶
作者: Ido Nachum, R\"udiger Urbanke, Thomas Weinberger
主题: 数理统计 / 假设检验
相关性: 8/10
链接: https://arxiv.org/abs/2605.25859
一、核心问题与贡献¶
①研究了 \(k\) 折交叉验证（CV）作为风险估计器时，其均方误差（MSE）如何随折数 \(k\) 变化这一长期悬而未决的问题。②核心工具是对最简非平凡 ERM（Majority 算法）的精细组合与渐近分析，并由此建立 minimax 框架。③主要结论是：当折数 \(k\) 随样本量 \(n\) 增长时，没有任何 ERM 算法能达到 \(O(1/n)\) 的 minimax MSE，下界为 \(\Omega(\sqrt{k}/n)\)；且现有基于稳定性的理论在此简单算法上即失效或 vacuous。
二、基础设定¶
- 核心概念与符号：
- \(S_n\): 样本量 \(n\) 的 i.i.d. 数据集；\(S_i, S_{-i}\): 第 \(i\) 折验证集与训练集。
- \(\hat{L}^{(k)}_{CV}(A, S_n)\): \(k\) 折 CV 风险估计器；\(L(A(S_n))\): 全样本算法的真实风险。
- \(\text{MSE}^{(k)}_{CV}(A, D) := \mathbb{E}[(\hat{L}^{(k)}_{CV} - L)^2]\): CV 风险估计的均方误差。
- \(\Re_{CV}(A) := \min_{k|n} \max_{D} \text{MSE}^{(k)}_{CV}(A, D)\): 算法 \(A\) 的 minimax CV 风险。
- Majority 算法 \(A_{maj}\): 输出常数假设 \(h_0\) 或 \(h_1\)，取决于样本中标签 1 的计数是否过半。
- 关键假设：
- ERM 算法假设：算法为经验风险最小化器（非平凡，\(|\mathcal{H}| \ge 2\)）。含义：排除了常数算法（其 CV MSE 可达 \(O(1/n)\)），聚焦于有学习行为的算法；与已有文献相比，这是标准假设，但本文首次证明其在此假设下必然无法达到 \(1/n\) 最优率。
- 随机标签模型：\(y_i \sim \text{Ber}(1/2)\) 且与 \(x_i\) 独立。含义：构造最坏分布，使得算法处于决策边界最不稳定的状态；强化了特定设定以获取精确闭式解，但 minimax 下界通过归约证明其对所有分布成立。
- 对称性假设：算法对样本置换不变。含义：标准统计假设，保证折间估计的对称性。
- 问题背景：现有 CV 理论（如 Kearns & Ron 1997, Kumar et al. 2013）基于算法稳定性给出的 MSE 上界，随 \(k\) 减小反而变松，甚至与真实行为相反。本文指出这些上界在 Majority 算法上相差 \(\Theta(\sqrt{n})\) 或 \(\Theta(n)\) 倍，且发现 Kearns & Ron 1997 和 Kale et al. 2011 存在数学错误。最相关文献区别：Kumar et al. 2013 基于损失稳定性，本文证明该概念对 MSE 不必要且上界 vacuous；Bengio & Grandvalet 2004 证明 CV 方差无偏估计不存在，本文则直接给出 MSE 的精确量级与 minimax 下界。
三、主要定理 / 核心结果¶
定理 9 (Majority Asymptotics) 1. 原文陈述：在随机标签模型下，Majority 算法的 \(k\) 折 CV 协方差 \(\text{Cov}(n, m) = \Theta(\sqrt{k}/n)\)，且 MSE 在 \(k=2\) 时最小，为 \(\text{MSE}^{(2)}_{CV} = 1/(4n) + 1/(2\pi n) + o(n^{-1})\)。 2. 直观解释：数据复用导致折间估计强正相关，且这种相关性随折数 \(k\) 增大而恶化（因为训练集重叠增加）。折数越少，训练集差异越大，反而削弱了正相关，降低了 MSE。这解释了为何 \(k=2\)（最不重叠）是最优的。 3. 解决了什么技术难点：精确量化了折间相依结构。以往工作只能给出粗略的稳定性参数界，本文通过 "Factorization" 将协方差计算归
Maintained by 陈星宇 · Homepage · Source on GitHub