跳转至

Kernel interpolation generalizes poorly

作者: Yicheng Li, Haobo Zhang, Qian Lin
来源: Biometrika
主题: 非参数 / 半参数
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

这篇论文聚焦于一个核心的“现代 vs. 经典”统计问题：当回归模型（这里是核回归）完美拟合训练数据（即实现零训练损失，即“插值”）时，它在测试集上的泛化误差会是多少？ 这是“良性过拟合”（Benign Overfitting）现象在核方法语境下的直接拷问。该现象的发现源于深度学习：深度神经网络可以完全记忆（插值）带噪声的训练标签，但依然在新数据上表现良好，这与经典统计对过拟合的恐惧截然相反。因此，理论界要回答：1） 核插值能否产生类似的“良性”泛化？2）如果能，在什么条件下（数据维度、核函数平滑性、信噪比）？3）如果不能，机理是什么？

发展脉络

本文的 introduction 和参考文献清晰地勾勒出这条脉络，分为“奠基-探索-反驳-本文”四阶段：

  1. 奠基：深度学习中的“良性过拟合”现象的发现

    • Zhang et al. [5] (2016)：通过实验展示，深度CNN能够完美拟合随机标签，但测试误差并未失控。这一“异常”现象动摇了经典正则化理论，点燃了对“良性过拟合”理论研究的热情。
    • Belkin et al. [1-3] (2018)：从实证角度系统化地展示，最小范数插值能在过参数化线性模型中泛化，并提出了“双下降”（double descent）的风险曲线，调和了经典的偏差-方差权衡与现代机器学习实践。他们为“什么样的过拟合是好的”提供了初步框架。

  2. 探索：核方法中的“良性过拟合”可能性与边界

    • Liang & Rakhlin [13] (2018)：首次在核回归中展示了“良性隔靴搔痒”的可能性。他们指出，对特定核（如某些点积核），当数据处于低维流形结构或样本量与维度满足特定比例（如 \( n \asymp d \)）时，核插值的泛化误差可以被控制。这是对“良性”叙事最直接的支持。
    • Bartlett et al. [4] / Montanari & Zhong [14] (2019/2020)：在线性回归和神经网络（NT神经切向核）的过参数化框架下，深入分析了最小范数插值的泛化误差，建立了基于协方差矩阵有效秩（effective rank）的刻画。这些工作表明，数据的内在维度和“有利”的结构（如协方差谱快速衰减）是良性过拟合的关键。
    • Rakhlin & Zhai [21] (2018，原文引用 [21])：这是一个关键的“反”信号。他们证明，对于 Laplace 核，当输入维度 \( d \) 是固定奇数时，核插值不能一致地泛化（即使选择最优带宽）。这形成了本文第一个直接的前提和技术基石。

  3. 反驳：核插值普遍“泛化差”的结论

    • Yicheng Li, Haobo Zhang, Qian Lin (本文)：本文推广了 Rakhlin & Zhai [21] 的结论，证明对于一大类核（包括高斯核、点积核、NTK等），在温和的假设下，无论噪声多小（哪怕无噪声），核插值的泛化误差都存在一个多项式慢的下界，即 \( \Omega(n^{-\varepsilon}) \) 对任意 \( \varepsilon > 0 \)。这一结果清晰地划出了一条分界线：如果核函数不具有非常特殊的、依赖数据低维结构的性质，那么核插值几乎必然泛化很差。

子线索聚类

  1. 良性过拟合的“正”面证据（支持者）：聚焦于在过参数化（高维）设定下，最小范数插值在线性回归或特定核（如NTK）中如何能泛化。主要工具是“有效秩”分析、谱分析和精确渐近理论（Mei & Montanari [16], AM & Ghorbani et al. [15-18]）。代表人物：Bartlett, Belkin, Montanari, Liang。
  2. 坏泛化的“反”面证据（警示者）：聚焦于核插值在固定维度或特定核函数下是不可行的。主要工具是 Fano 不等式和打包数与覆盖数（Rakhlin & Zhai [21], Li et al. [本文]）。代表人物：Rakhlin, Zhai, Li, Zhang, Lin。

追问的核心问题

  1. 数据的内在维度 vs. 表观维度：结论的正反面很大程度上取决于数据是落在低维流形上（支持良性）还是通过充分维度与核交互（反对良性）。如何形式化这种结构假设？
  2. 核函数的选择：哪些核函数是“坏的”（泛化差），哪些是“可能的好的”？本文给出的谱衰减条件（如多项式衰减）是充分条件，还是必要条件？
  3. 噪声的强度与性质：文中结果表明，即使噪声是 Rademacher （二值 ±1） 且无噪声，下界仍然成立。这是否意味着“噪声”不是这个问题的核心变量？
  4. 与神经网络的类比：既然 NTK 也是本文假设下的“坏核”，那为什么实际训练过的宽神经网络能泛化好？答案可能在于隐式正则化（implicit regularization）：梯度下降不是寻找最小范数插值解，而是可能在参数空间中找到一个有偏的解（比如NTK的线性近似在无限宽度下，或者早期停止在 NTK 的高频成分上）。

⚠️ 作者的 framing

作者将缺口 frame 为：“虽然已有 [13]、[14]、[21] 等零散的不可能或可能结果，但不存在一个涵盖一大类核函数的泛化下界。” 他们把自己定位为“封闭这一缺口”的工作。 * 他们淡化的竞争路线：直接忽略了或仅在引言末尾提及早期停止（early stopping）策略。虽然他们声明“真”的NT网络通过早期停止（如 Ghosh et al. [17]）可能绕过低范数解，但本文主要攻击无正则化的“纯粹”插值解。 * 明显该引但没引的：这篇阅读材料中未见明显遗漏。但可以查一下 “spectral algorithms” (如本文作者自己的 [21] 和 [22]) 的相关工作。这些工作证明了有正则化（如谱算法）在不同源条件下的最优率，而本文则在强调无正则化的插值解是多么差。这种对比在introduction中不够突显。 * 未见的张力：被引工作之间未见明显矛盾。结论相反的工作（良性 vs. 坏）是针对不同的核和数据结构条件（Liang vs. Rakhlin & Zhai, 以及本文），因此它们是条件依赖的，而非相互反驳。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

符号 * \( \mathcal{X} \)：输入空间（例如球面 \( S^{d-1} \subset \mathbb{R}^d \)，或者任何紧集）。 * \( \rho \)： \( \mathcal{X} \times \mathbb{R} \) 上的未知联合分布，定义了数据的生成过程。其边际分布 \( \rho_X \) 在 \( \mathcal{X} \) 上。 * \( (X_i, Y_i)_{i=1}^n \)：可观测数据，从 \( \rho \) 独立同分布采样。\( X_i \in \mathcal{X} \)，\( Y_i \in \mathbb{R} \)。 * \( f^*_{\rho}(x) = \mathbb{E}[Y | X=x] \)：未知的真实回归函数。这是我们要估计的参数/estimand。 * \( \mathcal{H} \)：一个再生核希尔伯特空间（RKHS），由正定核 \( k: \mathcal{X} \times \mathcal{X} \to \mathbb{R} \) 定义。它的范数 \( \| \cdot \|_{\mathcal{H}} \) 作为正则化项。 * \( k(x, x') \)：核函数。它是已知的，由研究者选择。 * \( K(X,X) \in \mathbb{R}^{n \times n} \)：核矩阵，\( [K(X,X)]_{ij} = k(X_i, X_j) \)。 * \( \hat{f}_n \)：核插值（Kernel Interpolation）解（也叫 “Ridgeless” 或最小范数插值解）。它定义为：

\[\hat{f}_n = \arg\min_{f \in \mathcal{H}} \|f\|_{\mathcal{H}} \quad \text{s.t.} \quad f(X_i) = Y_i \ \forall i=1,\ldots,n.\]
即，在所有完美拟合训练数据的函数中，找最有范数最小（最平滑）的那个。 * Generalization Error / Expected Risk：\( \mathcal{E}(\hat{f}_n) = \mathbb{E}_{X} [(\hat{f}_n(X) - f^*_{\rho}(X))^2] \)。在 \( X \) 独立于训练数据且服从 \( \rho_X \) 的条件下。这是我们要研究的量。 * \( \{ \mu_j \}_{j \ge 1} \)：核积分算子 \( T_k: L^2(\rho_X) \to L^2(\rho_X) \) 的特征值，非负且按非递增顺序排列。它由 \( (T_k f)(x) = \int k(x, x') f(x') d\rho_X(x') \) 定义。这些特征值的衰减速度决定了RKHS的平滑性和逼近能力。 * 假设(A1)：\( \| f^*_{\rho}\|_{L^\infty} \le M \)（真回归函数几乎处处有界）。 * 假设(A2)：\( \mu_j \) 的衰减速度。例如，多项式衰减 \( \mu_j \asymp j^{-\beta} \)，或者本文核心的一种“弱”衰减条件。这是模型的关键部分。 * 噪声模型：\( \epsilon_i = Y_i - f^*_{\rho}(X_i) \) 是可观测的噪声。论文考虑噪声方差有界（\( \mathbb{E}[\epsilon_i^2] \) 有界），并不要求噪声的高斯性，甚至可以使用 Rademacher 噪声（即 \( \epsilon_i = \pm 1 \) 等概率）。这是关键的自由度。

模型与可观测数据 * 数据生成机制：\( Y_i = f^*_{\rho}(X_i) + \epsilon_i \)。 * 可观测的：样本对 \( (X_i, Y_i) \)。核函数 \( k \) 是研究者定义的。 * 想估计但观测不到的：真实回归函数 \( f^*_{\rho} \) 和它的 \( L^2 \) 范数。

第二步：讲最小内核

为了让整篇论文的精神一目了然，考虑一个最简化的特例：

  • 最简特例 (1维球面，多项式核，无噪声极限)

    • 设定：输入空间是1维球面（单位圆）\( S^1 \)。核函数是点积核，例如 \( k(x, x') = (1 + x \cdot x')^p \)（多项式核），阶数 \( p \) 为正整数。数据分布 \( \rho_X \) 是球面上的均匀分布。
    • 在无噪声极限下：\( Y_i = f^*_{\rho}(X_i) \) 是确定性函数。那么核插值 \( \hat{f}_n \) 就是那个完美拟合所有点（\( f(X_i) = f^*_{\rho}(X_i) \) 对所有 i）且RKHS范数最小的函数。这等价于一个确定性插值问题：用RKHS中的函数来精确重建一个已知函数在 n 个点上的值。

  • 直观的核心逻辑：

    1. 核心困难：对于一个足够平滑的核（如高斯核或多项式核），其RKHS \( \mathcal{H} \) 中函数的“自由度”几乎是无限的。但数据点的数量 \( n \) 是有限的，用来插值。一个很坏的可能性是，插值得到的 \( \hat{f}_n \) 在训练点之间疯狂振荡，只为了满足这些精确插值点。这种振荡会导致巨大的测试误差。
    2. 关键想法 (转化为下界问题)：既然我们要证明 对任何 \( \hat{f}_n \)，其泛化误差 \( \mathcal{E}(\hat{f}_n) \) 都很大，我们就不需要去计算 \( \hat{f}_n \) 的形态。我们可以利用 Fano 的不等式：如果我们能够构造一个先验分布 \( \pi(f) \) 在 RKHS 上（它生成许多几乎正交的候选函数），并且这些候选函数在训练数据\( (X_i) \) 上几乎不可分辨（它们的似然几乎相同），那么任何插值方法（不要求它是 \( \hat{f}_n \) 还是其他规则）的期望泛化误差的下界就是由 \( \log (\text{候选函数个数}) / \text{样本量} \) 决定的。
    3. 最小内核操作（简化为打包和Fano）：
      • 构建包：在RKHS \( \mathcal{H} \) 的某个范数球 \( \|f\|_{\mathcal{H}} \le B \) 内，我们找到 \( N \) 个函数 \( f_1, \ldots, f_N \)，使得任两个函数之间在 \( L^2(\rho_X) \) 范数下的距离至少是某个 \( \delta > 0 \)（即它们是 \( \delta \) -可分辨的）。这可以通过对核积分算子 \( T_k \) 的特征函数构造包络来实现。
      • Fano 的应用：现在，假设真实函数是这 \( N \) 个候选者中的某一个，且以均匀概率被选中。由于它们都在范数球内，且数据 \( (X_i, Y_i) \) 只给出关于它们在观测点 \( X_i \) 上的值的有限信息（这导致一个困难的区分问题），Fano 不等式表明，任何程序（包括核插值）识别出真正候选者的误差至少为 \( (\delta^2 / 2) \times [1 - (\text{互信息}) / \log N] \)。
      • 关键的“差”信号：当特征值 \( \mu_j \) 衰减得太快（例如，指数衰减，对应高斯核），那么 \( \delta \) 很大（因为候选函数之间差异显著）而对数是 \( n \) 的幂次（十分缓慢），导致下界为 \( \Omega(n^{-\varepsilon}) \) 对任意小的 \( \varepsilon \)。

一句话总结：你看到的结果——\( \Omega(n^{-\varepsilon}) \)——本质上是因为核的特征值衰减过快，导致在范数球内可容纳的函数太多，以至于分离它们（‘插值掉噪音’）所需的信息量远远超过了 n 个样本所能提供的信息量，哪怕是 \( n \) 很大。

三、这篇论文做了什么

三句话

  • 研究问题：在温和条件下证明了，对于包含常见核（如高斯核、点积核、NTK等）的一大类核函数，核插值（最小范数插值）的泛化误差在任何噪声水平下都存在一个 \(\Omega(n^{-\varepsilon})\) 的多项式慢下界（\(\varepsilon\) 可任意小）。
  • 核心方法：利用特征值衰减（核积分算子谱的尾部的衰减速率）与 Fano 不等式的组合，通过构造一个在RKHS范数球内的大打包（packing），将泛化误差下界化约为一个“区分很多相似函数”的困难问题。
  • 主要结论：核插值普遍不能以多项式速率收敛到真回归函数，即它的泛化误差几乎是“停滞”的。这直接否定了“良性过拟合”在核方法中的天真类比，并揭示了在深度学习环境下，神经网络的过拟合机制可能并不是简单地等价于无正则化的核回归。

关键设定与假设（在第二节的基础上补充）

论文的核心假设（Assumption 1-2）非常精炼： * Assumption A1：真回归函数 \(f^*_{\rho}\) 本质有界，且边际分布 \( \rho_X \) 是非退化的（不会有 evanescent 支撑）。噪声的方差有界。 * Assumption A2 (核心假设)：核积分算子 \( T_k \) 的特征值 \( \{ \mu_j \}_{j \ge 1} \) 衰减至少是多项式或更快的（例如指数衰减）。具体来说，他们要求特征值的累积尾部满足某种条件，导致在RKHS范数球内，存在“足够多”的几乎正交的函数。这个“足够多”意味着特征值的总质量和（tail sum）随 \( n \) 增长而非常缓慢地趋于无穷，从而预先铺设一个很大的排序空间（packing size）。 * 对比已有文献：相比 Rakhlin & Zhai [21] 的 Laplace 核的特殊性（需要奇数维），本文的假设覆盖了更广义的核函数。相比 Liang & Rakhlin [13] 的“正”面结论（低维流形），本文的假设适用范围更广，且不要求数据有特殊的低维结构。

主要结果

论文的主要定理陈述了一个稳健的下界。

  • 定理 2 (核心定理)：在 Assumptions A1, A2 下，存在某个常数 \( c > 0 \)，使得对任意 \( \varepsilon > 0 \) 和任意足够大的 \( n \)，有
    \[\mathbb{E} [\mathcal{E}(\hat{f}_n)] \ge c \cdot n^{- \varepsilon}.\]
    • 直觉：下界可以任意接近于常数 \( c \)。这意味着样本量 \( n \) 从 \( 10^3 \) 增长到 \( 10^6 \)，泛化误差的下降也几乎可以忽略不计。
    • “坏核”的具体例子：
      1. Laplace 核（在 \( \mathbb{R}^d \) 上，d固定）：特征值按指数 \( \exp(-c j^{1/d}) \) 衰减，满足假设，因此泛化差。
      2. 点积核（包括多项式核及 NTK 在球面上）：满足多项式衰减 \( \mu_j \asymp j^{- \beta} \)（对 NTK 有 \( \beta = d/(d-1) \)）。此时下界同样成立。
      3. 高斯核（在球面上）：特征值衰减比多项式更快，同样落入下界范围。
  • 定理 3 (推广到NTK网络)：作为定理2的推论，对于宽度足够大的ReLU神经网络（在NTK近似下），如果网络仅被训练到完美插值（不提前停止），则其泛化误差也至少为 \( \Omega(n^{-\varepsilon}) \)。

证明路线与技术技巧

整体证明采用经典的“构造下界→Fano不等式”样板，处理得非常干净。

  • 整体路线 (3步)：

    1. 构造大打包：在真回归函数所在范数球 \( \{f \in \mathcal{H}: \|f\|_{\mathcal{H}} \le B \} \) 内，利用核特征值衰减的尾部分布，打包出 \( N = N(n) \) 个函数 \( f^{(1)}, ..., f^{(N)} \)，使得这些函数之间在 \( L^2(\rho_X) \) 范数下两两距离至少为 \( \delta > 0 \)。打包的大小 \( N \) 随着 \( n \) 增长，但膨胀速度只是亚多项式（例如 \( n^{\log n} \)）。
    2. 定义先验与似然：设 \( \pi \) 是 \( f^{(j)} \) 上的均匀先验。假设真实函数是 \( f^{(j)} \)，噪声是 Rademacher 变量（±1）。则观测到数据 \( D = (X_i, Y_i) \) 的似然比（在不同 \( j \) 之间）可以通过特征函数展开，表示为特征值衰减的函数。关键是，由于每个函数 \( f^{(j)} \) 在训练点上会给定不同的平均响应，但大包络内的函数高度相似，这个似然比在有界噪声下并不会变得太可区分。
    3. 应用 Fano 不等式：Fano 不等式给出一个下界：
      \[\mathbb{E}[\mathcal{E}(\hat{f}_n)] \ge \frac{\delta^2}{2} \left( 1 - \frac{I(\theta; D) + 1}{\log N} \right),\]
      其中 \( I(\theta; D) \) 是先验 \( \pi \) 与观测数据 \( D \) 之间的互信息，它被上界为 \( \frac{n}{2} \log (1 + \sigma^2 / \lambda^2_{\text{eff}}) \)，其中 \( \sigma^2 \) 是噪声方差，\( \lambda_{\text{eff}} \) 是核特征值的某种有效幅。当 \( n \) 大时，由于特征值衰减太快，\( \lambda_{\text{eff}} \) 很小，导致互信息项增长缓慢，使得 \( 1 - (\text{互信息})/\log N \) 这一项保持为正，于是得到 \(\Omega(n^{-\varepsilon})\) 下界。

  • 关键跳跃点：

    • 从特征值衰减到构造大打包：最难的部分是如何保证你打包出的 \( N \) 个函数即使在高频也在范数球内，但彼此在 \( L^2 \) 上距离很大。这需要对核进行特征展开，利用迹为有限来构造。
    • 互信息的控制：必须证明，对任何两个不同的打包候选函数 \( f^{(a)} \) 和 \( f^{(b)} \)，它们在数据上的 KL 散度很小。这依赖于核特征值的衰减，使得高维度上的差异几乎全被噪声“淹没”。

  • 技术技巧点名：

    • Fano 不等式：最核心的下界工具。
    • 特征值衰减分析：对核积分算子的谱进行分析。
    • 打包数与覆盖数：利用特征函数构造 \( L^2 \) 下的 \( \delta \)-包络。
    • 先验均匀分布：用于构造多候选者问题。
    • 概率放大：通过分析似然比，证明由噪声引起的随机性下，不同模型的可区分性被破坏。

真实例子与应用

本文为纯理论，无真实数据案例或模拟实验。引言的末尾提到了一个“例子” —— 神经网络NTK，并声称用作一个直接推论。这实际上是理论应用的展示。

  • 怎么用：将定理2的核假设套用到NTK（它在球面上具有点积核的结构，且特征值声称为多项式衰减）。因此，NTK插值（作为一个核）的泛化差下界自动成立。
  • 结论：即使是无限宽神经网络（在NTK等价下），如果它只是通过梯度下降训练到零损失（即“插值”），其泛化误差也会很差。
  • 这个例子想说明：深度学习中的“真”良性过拟合不能简单地用NTK插值来解释。真正的秘诀可能在于自然训练中出现的早期停止、数据增强、优化轨迹的隐式正则化等，而不是简单的“完美过拟合”。

🔎 结论是否比证明窄

是。 必须特别注意论文定理结论的适用范围。 * 核心定理(Biometrika 发表版本)的证明部分明确针对特征值多项式或更快衰减的核函数。这意味着有些核（比如所谓的“无限维”核，如某些具有不变性的平滑核，其谱衰减极慢的）可能不在下界范围内。 * 结论中泛化误差的下界是 \( \Omega(n^{-\varepsilon}) \)。虽然这个下界很慢，但它只是下界。论文没有证明这个下界是“紧”的（upper bound 更低或相同）。对于某些核，实际泛化误差可能比这个下界更差（甚至可以是一个常数），本文并未排除这种可能。 * 更重要的窄化是：该结论是针对“无任何额外结构”的核插值。不能用于否定具有数据（如低维流形）先验知识时的插值泛化能力（比如Liang的结果就只适用于低维）。作者没有声称适用于非各向同性的数据分布。真实世界中的图像数据往往具有极低的流形维度。

四、开放问题

  1. 下界是否紧？ 本文给出的是 \( \Omega(n^{-\varepsilon}) \) 的下界（对任意小的 \(\varepsilon\)）。那么，对具体核（如高斯核、Laplace核），能否证明一个下界为 \(\Omega(1)\) 或 \(\Omega( \sqrt{ \log n / n } )\) 这种更快的率？ 这需要构建更精巧的打包或信息论论证。扎根点：定理2中的式子 \( c n^{-\varepsilon} \)，作者没有声称这是最优的下界速率。
  2. 能否扩展到更一般的噪声模型？ 本文使用Rademacher噪声或方差有界噪声。如果噪声是高斯的，且方差极度的小，是否能绕开下界？或者，当输入分布 \( \rho_X \) 具有均匀性（如均匀分布在球面），证明了多项式衰减核的插值失败。如果 \( \rho_X \) 是低秩或高相关（如马尔可夫链上的数据）的，结论会改变吗？扎根点：证明中对噪声的独立性假设（IID）和边际分布的紧性假设（A1）。
  3. 如何解释NT网络的实际泛化好？ 既然NTK插值理论上泛化差，但有限宽度的真实神经网络（训练到零损失时）却能泛化好，这两者之间的差距到底有多大？是NTK的有限宽度效应，还是优化动力学（梯度下降而非最小范数）产生的隐式正则化（如早期停止、模型高秩偏好等）？这是一个高质量的问题，需要连接本文的下界与神经网络训练的实证研究。
  4. 能否设计一种“绕过”下界的核方法？ 研究是否存在一类核（其谱递减射极慢），同时对这种核进行插值可能表现出好的泛化。这需要对核函数提出新的“矛盾”条件：既能在训练集上完美过拟合，又能平滑推广到测试集。扎根点：本文的假设A2限制了特征值的衰减速度，使得下界成立。不符合此假设的核（如“慢谱”核）是潜在的突破口，但符合此假设的核已经涵盖了许多流行核。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论