解析梯度提升在高维下如何良性过拟合,揭示其$oldsymbol{ ext{ℓ}_1}$隐式偏差的失效机制。
When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias
- 通过连续时间$oldsymbol{ ext{ℓ}_2}$-Boosting建模,结合凸高斯极小极大定理分析风险
- 发现噪声被稀疏化聚集,过拟合误差以$oldsymbol{ ext{log}(p/n)}$速率衰减
- 提出无需调参的早停规则,实现$oldsymbol{ ext{ℓ}_1}$有界信号的最优预测性能
在高维情形下,$oldsymbol{ ext{ℓ}_2}$几何中的良性过拟合已有充分刻画,但贪婪集成的$oldsymbol{ ext{ℓ}_1}$隐式偏差行为仍具挑战。其分析障碍源于坐标选择阈值的非线性耦合,导致标准谱解方法失效。本文研究连续时间$oldsymbol{ ext{ℓ}_2}$-Boosting在$oldsymbol{p}$个特征、$oldsymbol{n}$个样本下的高维风险。结合凸高斯极小极大定理与双侧截断高斯矩的精细渐近展开,解析求解了非光滑$oldsymbol{ ext{ℓ}_1}$插值器。在各向同性纯噪声模型下,证明良性过拟合以线性速率失败:贪婪选择将噪声局域化为稀疏活跃集,超额方差以$oldsymbol{Θ(σ^2/ ext{log}(p/n))}$速率衰减($oldsymbol{σ^2}$为噪声方差)。我们指出,尽管此局域化机制在信号存在时可能依然成立,但精确的信号-噪声分解仍是开放问题。对于具有$oldsymbol{k^*}$个主特征值和$oldsymbol{r_2 = p - k^*}$个尾部维度的尖峰各向同性设计,当$oldsymbol{r_2 r n}$时风险趋于零,但仅以$oldsymbol{Θ(σ^2/ ext{log}(r_2/n))}$速率衰减,慢于$oldsymbol{ ext{ℓ}_2}$几何中的线性衰减。为避免此缓慢收敛,分析了提升流的非光滑次微分动力学,导出一种无须调参的早停规则,在$oldsymbol{ ext{ℓ}_1}$路径有界条件下恢复Lasso基本不等式,并达到$oldsymbol{ ext{ℓ}_1}}$-有界信号的极小极大最优经验预测率。
原文摘要 · Abstract (English)
Benign overfitting is well-characterized in $\ell_2$ geometries, but its behavior under the $\ell_1$ implicit bias of greedy ensembles remains challenging. The analytical barrier stems from the non-linear coupling of coordinate selection thresholds, which invalidates standard spectral resolvent tools. To isolate this algorithmic bias, we characterize the high-dimensional risk of continuous-time $\ell_2$-Boosting over $p$ features and $n$ samples. By coupling the Convex Gaussian Minimax Theorem with delicate asymptotic expansions of double-sided truncated Gaussian moments, we analytically resolve the non-smooth $\ell_1$ interpolant. Under an isotropic pure-noise model, we prove that benign overfitting fails at the linear rate: greedy selection localizes noise into sparse active sets, and the excess variance decays at a logarithmic rate $Θ(σ^2/\log(p/n))$ for noise variance $σ^2$. We remark that while this localization mechanism should persist in the presence of signals, the exact signal-noise decomposition remains an open problem. For spiked-isotropic designs with $k^*$ head eigenvalues and $r_2 = p - k^*$ tail dimensions, the risk converges to zero when $r_{2} \gg n$, but only at a logarithmic rate $Θ(σ^2/\log(r_2/n))$, which is slower than the linear decay observed in $\ell_2$ geometries. To avoid this slow convergence, we analyze the non-smooth subdifferential dynamics of the boosting flow. This yields a tuning-free early stopping rule that, under a bounded $\ell_1$-path condition, recovers the Lasso basic inequality and attains the minimax-optimal empirical prediction rate for $\ell_1$-bounded signals.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。