基于拉德马赫复杂度与L1-范数的数据依赖早停规则

# 基于Rademacher复杂度与L₁范数的数据依赖性早停规则  
来源：https://arxiv.org/html/2608.24210  
作者：Duy Hoang, Bastien Berret, Olivier Bruneau, Laurent Fribourg  
Duy Hoang [email protected]  
所属机构：巴黎-萨克雷大学，法国国家科学研究中心，巴黎高等师范学院-萨克雷校区，LMF  
地址：法国吉夫-叙尔-伊维特，91190  

Bastien Berret [email protected]  
Olivier Bruneau [email protected]  
所属机构：巴黎-萨克雷大学，巴黎高等师范学院-萨克雷校区，LURPA  
地址：法国吉夫-叙尔-伊维特，91190  

Laurent Fribourg [email protected]  
所属机构：巴黎-萨克雷大学，法国国家科学研究中心，巴黎高等师范学院-萨克雷校区，LMF  
地址：法国吉夫-叙尔-伊维特，91190  

###### 摘要  
训练神经网络需要平衡拟合训练数据与在未知输入上实现稳健性能之间的权衡。这种通常被称为泛化能力的能力，取决于训练集上的经验风险（“经验损失”）与数据分布上的期望风险（“泛化误差”）之间的差距。现有方法通常通过数值方式估计泛化误差，需要梯度下降训练和“早停”策略。本研究引入了一种分析框架，可以在无需训练的情况下估计最优早停时间。文献中也有其他分析估计方法，但它们大多基于随机矩阵理论，并常对数据分布或协方差矩阵的特征值分布作出假设。相比之下，本文基于Rademacher复杂度（RC），无需此类概率假设。出于理论和数值考虑，使用L₁范数而非L₂范数表达RC更为合适。我们聚焦于线性模型和线性回归问题。借助“线性探测”方法，我们的结果可成功应用于非线性神经网络，MNIST分类示例即为例证。  

关键词：泛化、偏差-方差权衡、线性回归。  

## 1 引言  
给定输入/输出对的分布𝒟，跨分布𝒟的期望损失称为“总体损失”，记为L_𝒟。利用神经网络（NN）和梯度下降（GD）过程，可以在从𝒟中随机选取的n个样本集合S上估计L_𝒟。这称为“经验损失”，记为L_S。泛化损失L_G是L_𝒟与L_S之差，反映了S之外数据的影响。在GD过程初期，L_S往往下降而L_G往往上升（“偏差-方差”权衡），因此早停策略旨在在时间t*终止GD，以最小化L_S + L_G。经典方法通过在独立数据集S_test上最小化经验损失来数值估计t*（参见Prechelt (2002) (https://arxiv.org/html/2608.24210#bib.bib4)）。利用随机矩阵理论（RMT），多项工作在无需执行GD的情况下解析估计t*（例如Raskutti et al. (2014) (https://arxiv.org/html/2608.24210#bib.bib12)；Liao and Couillet (2018) (https://arxiv.org/html/2608.24210#bib.bib1)；Ali et al. (2019) (https://arxiv.org/html/2608.24210#bib.bib9)；Advani et al. (2020) (https://arxiv.org/html/2608.24210#bib.bib24)）。但这些工作常假设分布𝒟为高斯分布，或数据协方差矩阵的特征值分布服从Marchenko-Pastur律（Le Cun et al. (1991) (https://arxiv.org/html/2608.24210#bib.bib8)）。本文则基于Rademacher复杂度（RC）理论（Bartlett and Mendelson (2002) (https://arxiv.org/html/2608.24210#bib.bib20)）解析估计t*，且不对数据分布作任何假设。  

我们的方法基于数据依赖准则𝒞(s)，确保对所有t ≤ s，L_S(t) + L_G(t)下降。我们证明满足𝒞(s)的最大s是t*的下界估计t⁺（见命题7 (https://arxiv.org/html/2608.24210#Thmtheorem7)）。我们还给出了保证t⁺ = t*的充分条件。为消除依赖于𝒟的因子M，我们使用L₁范数而非L₂范数估计RC（见注记2 (https://arxiv.org/html/2608.24210#Thmtheorem2)）。在示例中（见第4节 (https://arxiv.org/html/2608.24210#S4)），我们验证L₁范数得到的t⁺比L₂范数更接近数值停止时间t_test。我们还给出了t = ∞时L_S + L_G的解析形式（见3.3节 (https://arxiv.org/html/2608.24210#S3.SS3)）。通过与t = t⁺时的L_S + L_G比较，我们可判断是否应采用早停策略（参见Sonthalia et al. (2024) (https://arxiv.org/html/2608.24210#bib.bib14)；Bartlett et al. (2020) (https://arxiv.org/html/2608.24210#bib.bib13)；Belkin et al. (2018) (https://arxiv.org/html/2608.24210#bib.bib11)）。  

本文聚焦线性模型，但借助线性探测策略（见Alain and Bengio (2016) (https://arxiv.org/html/2608.24210#bib.bib5)），结果可应用于非线性神经网络。这在MNIST分类示例中得到体现（示例11 (https://arxiv.org/html/2608.24210#Thmtheorem11)和12 (https://arxiv.org/html/2608.24210#Thmtheorem12)，第4节 (https://arxiv.org/html/2608.24210#S4)）。证明详见附录。  

### 与相关工作的比较  
如前所述，多项工作利用RMT获得泛化损失的解析上界，并用于估计最优停止时间。具体而言，令λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ ≥ 0为数据协方差矩阵的特征值。例如在Advani et al. (2020) (https://arxiv.org/html/2608.24210#bib.bib24)中，他们通过确定每个模式i（i ∈ [n]）的相关误差来评估最小化平均泛化动态的停止时间。对于模式i，他们发现最优停止时间形式为 t^{opt} = (1/λ_i) ln(1 + λ_i · SNR)，其中SNR为信噪比。本文无需任何概率假设，利用Rademacher复杂度得到类似结果，即最优停止时间估计形式为（见方程(27) (https://arxiv.org/html/2608.24210#S3.E27)） t⁺ ≈ (1/λ₁) ln(Γ(0)/Ω(0))。分子Γ依赖于较高特征值λ₁, …, λ_α，包含“信息”部分（参见Oymak et al. (2019) (https://arxiv.org/html/2608.24210#bib.bib22)）。分母Ω依赖于较低特征值λ_{α+1}, …, λₙ，包含“干扰”部分。因此Γ/Ω可解释为一种信噪比形式。  

文献中，Rademacher复杂度（结合“神经切线核”理论）常用于寻找总体损失的解析界：参见Jacot et al. (2018) (https://arxiv.org/html/2608.24210#bib.bib25)；Du et al. (2018) (https://arxiv.org/html/2608.24210#bib.bib28)；Arora et al. (2019) (https://arxiv.org/html/2608.24210#bib.bib26)；Allen-Zhu et al. (2019) (https://arxiv.org/html/2608.24210#bib.bib6)；Oymak et al. (2019) (https://arxiv.org/html/2608.24210#bib.bib22)；Li et al. (2020) (https://arxiv.org/html/2608.24210#bib.bib27)。但这些研究要求神经网络参数数量m远大于样本数量n（过参数化）。此时会出现“良性过拟合”或“逐epoch双重下降”现象（参见Heckel and Yilmaz (2020) (https://arxiv.org/html/2608.24210#bib.bib18)；Stephenson and Lee (2021) (https://arxiv.org/html/2608.24210#bib.bib16)；Nakkiran et al. (2021) (https://arxiv.org/html/2608.24210#bib.bib15)）：损失L_test(t)在t = t_test处达到第一个局部最小值，随后上升，之后再次下降，收敛至低于t = t_test处的最小值。在此背景下，早停策略并非“有益”。相反，本文方法适用于欠参数化情况（即m ≤ n）。  

### 符号说明  
本文中，ℝ和ℕ分别表示实数集和自然数集。ℝᵖ表示p维欧几里得空间，ℝᵖˣʷ表示具有p行q列的实矩阵空间。向量用粗体字母表示，矩阵用粗体大写字母表示。对于给定矩阵M ∈ ℝᵖˣʷ，Mᵀ表示其转置，M†表示其Moore-Penrose（伪）逆。向量v的L_p范数记为‖v‖_p。i.i.d.表示独立同分布随机变量。[n]表示{1, …, n}，I表示单位矩阵。对于v ∈ ℝ，sgn(v)在v ≥ 0时取1，v < 0时取-1。对于v = (v₁, …, vₙ) ∈ ℝⁿ，sgn(v)表示(sgn(v₁), …, sgn(vₙ))。  

## 2 预备结果  
我们考虑分布𝒟在ℋ × 𝒴上的概率空间，其中ℋ ⊂ ℝᵐ是所有可能实例h的输入空间，𝒴 ⊂ ℝ是相应输出的空间。  

### 2.1 总体损失与Rademacher复杂度  
“训练集”S是由从𝒟中i.i.d.选取的n个输入/输出对{(h₁, y₁), …, (hₙ, yₙ)}组成的集合。令y = (y₁, …, yₙ) ∈ ℝⁿ。令K为以h₁, …, hₙ ∈ ℝᵐ为列的n × m矩阵。数据协方差矩阵H ∈ ℝⁿˣⁿ定义为 H = KKᵀ，即H的(i, j)元素为H_{i,j} = h_iᵀh_j（参见Du et al. (2018) (https://arxiv.org/html/2608.24210#bib.bib28)）。  

如Martin Xavier et al. (2025) (https://arxiv.org/html/2608.24210#bib.bib23)所示，本文聚焦L₁范数（见注记2 (https://arxiv.org/html/2608.24210#Thmtheorem2)）。在此背景下，数据分布𝒟上的总体损失L_𝒟[f]（简记为L_𝒟）定义为： L_𝒟[f] = 𝔼_{(h,y)~𝒟}[‖f(h) - y‖]，其中f: ℝᵐ → ℝ为给定函数。由于本文聚焦线性回归问题，f形式为： f(h) = aᵀh，其中a = (a₁, …, aₘ) ∈ ℝᵐ。S上的经验损失L_S定义为： L_S = (1/n) Σ_{i∈[n]} |aᵀh_i - y_i| = (1/n) Σ_{i∈[n]} |v_i| = (1/n) ‖v‖₁ (1)，其中 v_i = aᵀh_i - y_i ∈ ℝ (i ∈ [n]) (2)， v = (v₁, …, vₙ) = Ka - y ∈ ℝⁿ (3)。向量v称为经验误差向量（或训练误差向量）。  

我们寻求向量a以最小化跨整个数据分布𝒟的总体损失L_𝒟。由于𝒟未知，我们的目标实际上是最小化L_𝒟的上界。令M和C为满足以下条件的两个正实数： |aᵀh - y| ≤ M ∀(h,y) ∈ ℋ × 𝒴 (4)， 𝔼_{h~𝒟}[‖h‖₂²] ≤ C² (5)。令L_G*和L_𝒟*定义为： L_G* = (2‖a‖₂C)/√n (6)， L_𝒟* = L_S + L_G* = (1/n)‖v‖₁ + (2‖a‖₂C)/√n (7)。  

我们遵循基于RC的方法（见Martin Xavier et al. (2025) (https://arxiv.org/html/2608.24210#bib.bib23)）。在设定下，结果如下。  

###### 命题1（参见Martin Xavier et al. (2025) (https://arxiv.org/html/2608.24210#bib.bib23)的命题3）  
在大小为n的样本S上，以至少1-δ的概率，总体损失L_𝒟满足： L_𝒟 ≤ L_𝒟* + ε (8)，其中 ε = 3M √(log(2/δ)/(2n)) (9)。  

### 2.2 线性模型的梯度流  
为简化，我们在连续时间设定下表述问题，并考虑梯度流（GF）而非离散时间GD。思想是将GF应用于a，并在时间t*停止过程，此时L_𝒟*预计达到最小值（“早停”策略）。经典方法通过考虑独立数据集S_test并确定GF在该数据集上达到最小值的时间t_test来估计t*（参见Prechelt (2002) (https://arxiv.org/html/2608.24210#bib.bib4)）。本文给出一种无需独立数据集或执行GF即可解析估计t*的方法。  

更形式化地，我们考虑寻找a = (a₁, …, aₘ) ∈ ℝᵐ以最小化以下二次损失函数： ℒ(a) = (1/2) Σ_{i=1}^n (aᵀh_i - y_i)² = (1/2) Σ_{i=1}^n v_i² = (1/2) ‖v‖₂² (10)。最小化ℒ的向量a是...