🤖 machine learning

A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

本文提出了一种基于带有 L1 范数的 Rademacher 复杂度的分析框架，用于在不需要训练或概率假设的情况下估计线性回归模型的最佳早停时间，并通过线性探测展示了其在非线性神经网络中的适用性。

原作者： Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

发布于 2026-08-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

训练计算机识别模式——无论是识别照片中的猫，还是预测股票价格——都涉及一种微妙的平衡。机器通过观察示例进行学习，通过调整其内部设置来拟合所见数据。然而，如果它学习得过于完美，它就会开始记忆这些示例的具体特征，而不是理解底层的规则。这有点像一个学生背下了练习题的答案，却因为无法将逻辑应用于新问题而在正式考试中失败了。在人工智能领域，这种无法泛化的问题是一个主要的障碍。为了防止这种情况，研究人员经常使用一种称为“早停”（early stopping）的策略，即在恰当的时机停止学习过程——即在模型学到了规则之后，但在它开始记忆噪声之前。挑战始终在于如何准确知道那个时刻何时到来。传统上，寻找这个平衡点需要通过在不同的数据集上多次运行训练过程，这种方法速度慢、计算成本高，且往往依赖于猜测。

巴黎-萨克莱大学（Université Paris-Saclay）的一个研究小组提出了一种解决这一时机问题的新方法，而无需进行重复试验。他们没有采用猜测或运行额外的模拟，而是开发了一种数学方法，可以直接从数据本身预测理想的停止点。他们的方法依赖于一个被称为“拉德马赫复杂度”（Rademacher complexity）的概念，该概念本质上衡量了一个模型区分真实模式与随机噪声的能力。通过使用这一度量标准，研究人员创建了一条规则，可以告诉计算机何时停止学习。他们的工作的独特之处在于，它不需要对数据的形状或分布做出假设，而这是以往方法的一个常见要求。此外，他们发现使用一种特定的误差测量方式（称为 L1 范数），比该领域使用的标准方法能提供显著更准确的预测。

研究人员最初将工作重点放在线性模型上，线性模型是最简单的机器学习算法类型，但他们证明了其发现可以扩展到复杂的非线性神经网络。为了测试他们的理论，他们将该方法应用于一个经典问题：区分手写数字。在一个实验中，他们训练了一个神经网络来区分超过一万张图像数据集中的数字 3 和 5。使用他们的新规则，系统计算出的停止步数为 342 步。当他们将此结果与通过运行完整训练过程并检查单独测试集所得到的实际最佳停止时间进行比较时，发现实际最优值为 357 步。两者的差异微乎其微，且在预测停止时间停止的模型的性能，与在真实最优值停止的模型的性能几乎完全相同。在另一个涉及数字 0 和 1 的测试中，预测的停止时间为 415 步，而实际最优值为 418 步。在这两种情况下，使用他们规则训练的模型都避免了过拟合的陷阱，并针对未见数据达到了最佳准确度。

研究还表明，当相对于模型的复杂度有大量数据时，该方法的效果最好。当研究人员测试数据点较少的场景时，该方法变得不再精确，有时会建议停止时间为零，这意味着模型根本不应该进行训练。这符合“复杂模型需要足够数据来学习通用规则”的理解。研究人员还将他们的新方法与依赖于不同数据数学假设的旧技术进行了比较。他们发现，他们使用 L1 范数进行计算的方法，始终能产生比旧方法更接近真实最优值的停止时间。这表明，误差的测量方式与停止规则本身一样重要。

或许最重要的一点是，研究人员展示了“早停”不仅是一个理论概念，在许多情况下也是一种实际的必要手段。他们计算了如果允许训练无限期进行会发生什么。在他们研究的例子中，如果训练超过最优值继续进行，模型在新数据上的表现实际上会变差，这证实了早停可以防止模型性能退化。然而，他们也指出，在某些特定的、参数远多于数据点的极高复杂度场景中，继续训练最终可能会带来更好的结果，这种现象被称为“良性过拟合”（benign overfitting）。他们的方法有助于识别用户处于哪种情况，从而让他们决定是提前停止还是继续进行。

通过提供一种无需运行完整训练过程即可计算出理想停止时间的方法，这项工作为开发可靠的人工智能提供了一条更高效的路径。它消除了对试错的需求，节省了时间和计算资源。该方法特别适用于数据充足但计算能力有限，或者训练成本较高的场景。虽然目前的研究侧重于线性模型和特定类型的数据，但研究人员相信其框架可以被改编用于更复杂的系统和不同类型的输出。他们的工作为这个长期依赖猜测的问题提供了一个清晰的、数据驱动的答案，为在学习与记忆之间的权衡提供了更精确的工具。

技术摘要：一种基于 L1 范数 Rademacher 复杂度的依赖数据早期停止规则

问题陈述
训练神经网络需要平衡拟合训练数据与在未见输入上实现稳健性能之间的权衡，这种性质被称为泛化性。这由经验风险（ $L_S$ ）与期望总体风险（ $L_D$ ）之间的差距决定。泛化损失（ $L_G$ ）被定义为这两者之差。在梯度下降（GD）过程中， $L_S$ 通常会降低，而 $L_G$ 会增加，从而产生“偏差-方差”权衡。早期停止的目标是在最优时间 $t^*$ 处停止训练，以最小化总和 $L_S + L_G$ 。

经典方法通过监测单独的测试集（ $S_{test}$ ）来数值估计 $t^*$ 。此外，存在使用随机矩阵理论（RMT）的解析方法，但这些方法通常依赖于较强的概率假设，例如高斯数据分布或数据协方差矩阵的特定特征值分布（如 Marchenko–Pastur 分布）。本文旨在解决对无需单独测试集或限制性分布假设的解析早期停止规则的需求。

方法论
作者提出了一个基于 Rademacher 复杂度 (RC) 的解析框架，用于在不进行梯度下降的情况下估计最优停止时间。该方法侧重于线性模型和线性回归，并通过“线性探测（linear probing）”将其扩展到非线性网络。

L1 范数公式化： 与许多现有的使用 L2 范数的 RC 界限不同，本研究使用 L1 范数 来表达 Rademacher 复杂度。选择 L1 范数的动机是消除泛化误差界限中依赖数据的常数 $M$ （损失的上界）。通过在通用的 $L_p$ 范数界限中设置 $p=1$ ，作者推导出了一个仅取决于经验误差向量和模型范数的总体损失（ $L_D$ ）上界，从而避免了对 $M$ 的显式依赖。
梯度流动力学： 该问题在连续时间内使用梯度流（GF）进行建模。作者分析了训练误差向量 $v(t)$ 和模型参数 $a(t)$ 的动力学过程。总体损失上界（记作 $L^*_D(t)$ ）被证明是“U 型”的：最初随着经验损失的下降而下降，随后随着模型范数的增长而上升。
解析停止准则 ( $t^+$ )： 核心贡献在于推导出一个依赖数据的准则 $C(s)$ $C (s)$ ，该准则确保对于所有 $t \leq s$ $t \leq s$ ， $L^*_D(t)$ $L_{D}^{*} (t)$ 都是递减的。
- 作者将数据协方差矩阵的特征值分解为“信息性”（大）和“干扰性”（小）集合。
- 他们定义了一个涉及这些特征值和误差动力学的函数 $\Phi(t)$ 。
- 停止时间 $t^+$ 定义为使得对于所有 $t \in [0, s)$ ， $\Phi(t) > 0$ 成立的 $s$ 的上确界。
- 从数学上讲， $t^+$ 是 $\Phi(t)$ 首次穿过零点的时刻。文中证明了 $t^+$ 是真实最优时间 $t^*$ 的下界估计（即 $t^+ \leq t^*$ ）。在特定条件下（例如，当真实最小值位于第一个符号不变区间内时）， $t^+ = t^*$ 。
近似： 本文提供了一个简单的近似公式 $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ ，这类似于 RMT 文献中发现的信噪比（SNR）公式，但此处是在没有概率假设的情况下推导出来的。

主要贡献

无分布限制的解析估计： 本文引入了一种方法，可以在不假设高斯数据或特定数据分布特征值的情况下，解析地估计最优早期停止时间。
L1 范数的优势： 作者从理论和数值上证明，使用 L1 范数进行 Rademacher 复杂度计算得到的停止时间估计值（ $t^+$ ）比 L2 范数方法更接近数值最优解（ $t_{test}$ ）。
聚焦欠参数化领域： 该方法专门为欠参数化领域（ $m \leq n$ ）设计，在该领域，“良性过拟合（benign overfitting）”和“逐 epoch 双下降（epoch-wise double descent）”现象较少出现，使得早期停止成为一种有益的策略。
线性探测的应用： 虽然理论是针对线性模型推导的，但作者通过冻结隐藏层并仅训练输出层（线性探测），成功地将结果应用于非线性神经网络（特别是 MNIST 分类任务）。

结果
作者通过以下几个示例验证了其方法：

合成高斯数据： 在具有不同样本量（ $n=512$ 和 $n=16384$ ）的二分类任务中，解析估计值 $t^+$ 在第一种情况下与真实最优时间 $t^*$ 完全匹配，在第二种情况下提供了紧凑的下界。基于 L1 的估计值始终比基于 L2 的估计值更接近测试集最优解。
MNIST 分类 (3-5 和 0-1)： 使用 4 层 ReLU 网络进行线性探测，该方法准确预测了停止时间。对于 3-5 分类， $t^+ = 342$ ，而数值最优解 $t^* = 357$ ，测试集最优解 $t_{test} = 356$ 。对于 0-1 分类， $t^+ = 415$ ，与 $t^* = 415$ 相匹配，且接近 $t_{test} = 418$ 。
有益的停止： 在所有测试案例中，估计停止时间处的损失均低于无限训练时间时的损失（ $L^*_D(t^+) < L^*_D(\infty)$ ），证实了早期停止是有益的，并避开了“良性过拟合”阶段。
鲁棒性： 该方法在不同的数据分布（高斯、均匀、帕累托）下表现良好，且随着样本量与参数量之比（ $n/m$ ）的增加，性能有所提升。

意义与主张
本文声称其主要意义在于提供了一种依赖数据的、解析的早期停止规则，该规则可以在不需要单独验证集或对数据分布进行限制性概率假设的情况下运行。通过利用基于 L1 范数的 Rademacher 复杂度，作者提供了一个实用的工具，用于确定何时停止训练线性模型（以及通过线性探测应用于某些非线性网络），以最小化泛化误差。作者也谦虚地指出，虽然该方法在欠参数化模型中表现良好，但其目的并非针对出现“良性过拟合”的过参数化领域。他们还确定了未来的研究方向，包括直接应用于全非线性模型、向量化输出以及处理输入数据中的随机噪声。

类似论文