Affine-invariant Cubic Newton with Weak Learners¶

会议: NeurIPS 2026
arXiv: 2610.33516
OpenReview: https://openreview.net/forum?id=fjyjg3gCmx
代码: https://github.com/nikitazozoulenko/global-newton-boosting
领域: 优化/理论
关键词: 梯度提升, 牛顿法, 仿射不变性, 弱学习器, 三次正则化

一句话总结¶

本文将仿射不变三次牛顿法（AICN）推广至弱学习器凸优化框架，证明其更新等价于步长由方向改善量显式确定的阻尼弱牛顿步，在半强自协调条件下实现全局 $\mathcal{O}(1/\overline{\Theta}_k^4 k^2)$ 收敛率并涵盖坐标下降法。

研究背景与动机¶

现代梯度提升决策树（GBDT）系统如 XGBoost、LightGBM 与 CatBoost 广泛利用二阶牛顿法拟合树叶权重，在表格数据与多种实际工业任务中取得了巨大的经验成功。然而，相比于一阶梯度提升拥有成熟的收敛保证，二阶牛顿提升的理论基础长期受到严重限制。这是由于未加正则化的经典牛顿法缺乏全局收敛性，即便针对光滑强凸的目标函数，若初始化远离最优解，迭代点也可能剧烈震荡甚至发散。近期文献通过受限牛顿下降框架将梯度正则化牛顿法（GRN）引入弱学习器，首次建立了牛顿提升全局 $\mathcal{O}(1/k^2)$ 收敛率。

然而，现有 weak-GRN 的收敛性分析存在明显的理论缺陷。一方面，GRN 的证明强依赖于欧几里得范数下的 Hessian 矩阵 Lipschitz 连续性，未能有效契合损失函数局部的自然 Hessian 几何结构；这导致其理论依赖于极度保守的“弱梯度边缘”参数 $\gamma$，使得收敛率对最差样本产生严重的 $\mathcal{O}(1/\gamma^{12}k^2)$ 依赖。另一方面，以往提升算法的弱学习器边缘普遍采用全序列最差界（infimum），一旦优化路径中存在单颗拟合极差的树，整套理论收敛保证便直接失效。

为了彻底摆脱欧氏几何与最差样本界限的理论束缚，本文将仿射不变三次牛顿法（AICN）拓展到带有弱学习器的凸优化问题中。通过在局部 Hessian 诱导范数下利用半强自协调性（semi-strong self-concordance）刻画函数正则度，算法完全实现了几何仿射不变性。核心 idea：将仿射不变三次牛顿法推广至弱学习器，利用局部 Hessian 范数下的方向改善量将三次子问题退化为显式可算的阻尼弱牛顿步，并在路径平均余弦角 $\overline{\Theta}_k$ 下建立全局 $\mathcal{O}(1/\overline{\Theta}_k^4 k^2)$ 的加速收敛保证。

方法详解¶

整体框架¶

在受限牛顿下降框架（Restricted Newton Descent）中，目标是在实希尔伯特空间 $\mathcal{H}$（如经验样本函数空间）上最小化凸且二阶可微的损失函数 $L(F)$。弱-AICN 不直接求解昂贵的非线性全局三次子问题，而是通过在局部二次泰勒模型上增加局部 Hessian 范数的三次正则项 $M_k(f) = Q_k(f) + \frac{C_{\text{est}}}{6}\|f\|_{H_k}^3$，并在可伸缩弱学习器族 $\mathcal{F}$（例如深度为 $J$ 的决策树或坐标基向量）中寻找使模型下降最大的方向与步长。

算法在每一轮迭代中，先通过最小化二次泰勒展开 $Q_k(f)$ 拟合出常规弱牛顿步 $f_{k+1}^{\text{wN}}$，并计算其在局部几何下的方向改善量 $\delta_k$；随后根据闭式解析公式直接计算阻尼因子 $\alpha_k$，执行更新 $F_{k+1} = F_k + \eta \alpha_k f_{k+1}^{\text{wN}}$。整个更新完全等价于带显式步长的阻尼弱牛顿下降。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["当前迭代模型状态 F_k"] --> B["计算梯度 g_k 与 Hessian 算子 H_k"]
    B --> C["1. 拟合弱牛顿方向<br/>求解 argmin Q_k(f) 得到 f_k+1^wN"]
    C --> D["2. 计算局部几何改善量<br/>评估方向改善标量 delta_k"]
    D --> E["3. 显式三次正则阻尼步长<br/>计算标量系数 alpha_k"]
    E --> F["更新模型参数 F_k+1 = F_k + eta * alpha_k * f_k+1^wN"]
    F --> G["4. 自适应三次正则调优<br/>weak-AdaAICN 回溯验证下降"]

关键设计¶

1. 拟合弱牛顿方向：由二次逼近确定最优弱学习器基底 经典全空间精确牛顿步满足 $f_{k+1}^{\text{N}} = -H_k^{-1} [g_k]$，需要昂贵的全矩阵求逆或高维线性求解，而在受限学习器集合 $\mathcal{F}$ 下，参数更新被严格限制在弱模型族内。算法在每一轮构造二阶泰勒展开 $Q_k(f) = \langle g_k, f\rangle + \frac{1}{2}\langle f, H_k[f]\rangle$，并在族 $\mathcal{F}$ 内求解极小化问题： $$f_{k+1}^{\text{wN}} \in \arg\min_{f\in\mathcal{F}} Q_k(f)$$ 当弱学习器族 $\mathcal{F}$ 对标量缩放封闭（即对任意实数 $c$ 与 $f\in\mathcal{F}$ 有 $cf\in\mathcal{F}$）时，沿任意非零射线方向 $f$ 的一维二次极小值由 $t^* = -\langle g_k, f\rangle / \|f\|_{H_k}^2$ 显式给出。因此，最小化二次逼近模型等价于沿各方向寻找使一阶负梯度投影最大化的基底。

2. 计算局部几何改善量：统一对齐度量与余弦角转换 为刻画弱学习器沿局部 Hessian 椭球主轴的几何对齐能力，本文定义了局部 Hessian 范数下的方向改善量 $\delta_k(f) = -\langle g_k, f\rangle / \|f\|_{H_k}$。当 $f$ 选为最优化弱牛顿解 $f_{k+1}^{\text{wN}}$ 时，方向改善量记为 $\delta_k = \sqrt{|\langle g_k, f_{k+1}^{\text{wN}}\rangle|}$，满足： $$\|f_{k+1}^{\text{wN}}\|_{H_k} = \delta_k = \Theta_k \|f_{k+1}^{\text{N}}\|_{H_k} = \Theta_k \|g_k\|_{H_k}^*$$ 其中 $\Theta_k$ 为弱牛顿步与真实精确牛顿步在内积 $\langle \cdot, \cdot\rangle_{H_k}$ 下的广义余弦角，$\|g_k\|_{H_k}^* = \sqrt{\langle g_k, H_k^{-1} g_k\rangle}$ 为梯度的对偶 Hessian 范数。这一代数恒等式将复杂的弱学习器对齐程度完全转化为了方向改善标量 $\delta_k$，为后续阻尼系数的显式求解建立了直接桥梁。

3. 显式三次正则阻尼步长：无需内层循环的一阶解析折减 经典欧氏三次牛顿法（CRN）需要在每轮迭代通过昂贵的三对角化或根寻找算法求解非线性三次子问题，而仿射不变三次牛顿（AICN）在目标中引入的是由当前局部度量诱导的三次惩罚项： $$M_k(f) = Q_k(f) + \frac{C_{\text{est}}}{6}\|f\|_{H_k}^3$$ 本文严格证明了在可伸缩弱学习器族上最小化 $M_k(f)$ 等价于沿弱牛顿方向 $f_{k+1}^{\text{wN}}$ 进行一维凸优化。令标量半径 $r = t\|f_{k+1}^{\text{wN}}\|_{H_k}$，目标函数关于 $r$ 的一阶最优性条件直接导出解析阻尼因子： $$\alpha_k = \frac{2}{1+\sqrt{1+2C_{\text{est}}\delta_k}}$$ 从而令弱-AICN 迭代完全简化为 $F_{k+1} = F_k + \eta \alpha_k f_{k+1}^{\text{wN}}$。不仅计算极其轻量，而且步长随着方向改善量 $\delta_k$ 的衰减平滑逼近 1，完美吻合优化后期残差变小、步长自然放大的理论直觉。

4. 自适应三次正则调优：无需重算梯度的 weak-AdaAICN 回溯机制 在实际问题中预先测定全域半强自协调常数 $C_{\text{ssc}}$ 往往过于保守或不可行。本文基于三次模型在极值处的显式代数形式，提出了自适应变体 weak-AdaAICN。在每次阻尼尝试中，代数恒等式给出三次模型的预测极小值为： $$M_k(\alpha_k f_{k+1}^{\text{wN}}) = \frac{\alpha_k(\alpha_k - 4)}{6}\delta_k^2$$ 算法检验实际函数值是否满足 $L(F_k + \alpha_k f_{k+1}^{\text{wN}}) \leq L(F_k) + M_k$。若不满足则令估计值翻倍 $C_k \leftarrow 2 C_k$ 并重算标量 $\alpha_k$。整个回溯验证过程只需标量运算与单次前向损失评估，无需重新拟合弱学习器树模型，亦无需重新计算 Hessian 与梯度；并在步长接受后温和衰减 $C_{k+1} \leftarrow C_k / 4$。

损失函数 / 训练策略¶

在半强自协调（Semi-Strong Self-Concordance, SSC）假设下，即对任意方向 $f$ 满足 $\|\nabla^2 L(F+f) - \nabla^2 L(F)\|_{\text{aff-op}, H_F} \leq C_{\text{ssc}}\|f\|_{H_F}$，三次模型 $M_k(f)$ 构成全局上界。由此导出的弱收缩点不等式（Weak Contracting-point Inequality）为： $$L(F_{k+1}) \leq (1-\eta \Theta_k^2) L(F_k) + \eta \Theta_k^2 \min_{f\in\mathcal{H}} \left( L(F_k) + M_k(f) \right)$$ 借助创新的序列调和级数递推分析，全局收敛率证明摆脱了对最差单步的依赖，推导出在 $k \geq k_0$ 后的全局加速率： $$L(F_k) - L(F^*) \leq \frac{9 C_{\text{est}} D^3}{\eta^2 (\overline{\Theta_{k_0, k}^2})^2 (k - k_0)^2} = \mathcal{O}\left(\frac{1}{\overline{\Theta}_k^4 k^2}\right)$$ 相比于 weak-GRN 极差的 $\mathcal{O}(1/\gamma^{12}k^2)$，弱-AICN 不仅将指数从 12 降至 4，而且用路径均值 $\overline{\Theta}_k$ 替代了下确界 $\inf_t \gamma_t$。此外，对于交叉熵等满足 $\|f_{k+1}^{\text{N}}\|_{H_k}^2 \geq c(L(F_k) - L_*)$ 的 Hessian-dominated 损失函数，算法无需求解学习率区间即可证明全局线性收敛。

实验关键数据¶

主实验¶

论文在 Nesterov 二阶下界极小化问题以及 UCI Wine Quality、HIGGS 等标准基准上进行了多维度对比实验。在二阶极小化问题（$d=100$ 精确全空间设置与 $d=20$ 坐标下降弱学习器设置）中验证了自适应三次正则调优机制的加速效益，在 Charbonnier 损失下验证了无阻尼牛顿发散现象，并在 HIGGS 10,000 样本二分类任务中系统对比了弱学习器边缘指标。

实验任务 / 设置	对比算法配置	核心收敛指标 / 表现	对比基线 (GRN / 经典牛顿)	性能特征与提升
Nesterov 二阶下界函数 ($d=100$)	AdaAICN (自适应 $C_k$)	达到极小值所需耗时 ~2.1s	静态非自适应 AICN ($C_{\text{best}}=81$): ~4.2s	迭代步数与墙上时钟均取得 2.0× 加速
Nesterov 二阶下界函数 ($d=20$, CD)	CD-AdaAICN (坐标弱学习器)	收敛至 $10^{-6}$ 损失值	静态非自适应 CD-AICN ($C_{\text{best}}=16$)	迭代复杂度明显降低，摆脱保守超参调节
UCI Wine Quality (Charbonnier 损失, $\eta=1.0$)	weak-AICN ($C_{\text{est}}=10$)	稳健平滑单调收敛至平稳值	原始牛顿提升 (Vanilla Newton)	原始牛顿彻底震荡发散；weak-AICN 稳健收敛
UCI Wine Quality (Charbonnier 损失, $\eta=0.1$)	weak-AICN	稳定收敛，与 weak-GRN 轨迹吻合	一阶提升 (First-order)	收敛显著快于无法利用曲率信息的一阶提升
HIGGS 二分类 (二元交叉熵, $J=4$)	weak-AICN ($\eta=0.1, \lambda_{\text{base}}=10^{-4}$)	路径平均角 $\overline{\Theta}_k \approx 0.10$	weak-GRN 梯度边缘 $\overline{\gamma}_k \approx 0.10$	两者均值相仿，但 AICN 具 $\Theta^4$ vs $\gamma^{12}$ 理论优势

消融实验¶

在 HIGGS 数据集与随机树投影构造模型下，论文对树深度 $J \in \{2, 4, 6\}$ 及不同树弱学习器拟合规则进行了详尽消融与理论下界校验：

实验配置	深度 $J$ / 样本 $n$	弱学习器几何对齐指标数值	理论下界 / 参考值	观测说明
weak-AICN 树提升 (HIGGS)	$J=2, n=10000$	稳态运行平均 $\overline{\Theta}_k \approx 0.05$	最差下确界 $\inf \Theta_k \approx 0.025$	树深较浅时表达能力有限，平均角偏低
weak-AICN 树提升 (HIGGS)	$J=4, n=10000$	稳态运行平均 $\overline{\Theta}_k \approx 0.10$	最差下确界 $\inf \Theta_k \approx 0.050$	树深增加 2 层，对齐角近似翻倍（二进倍增）
weak-AICN 树提升 (HIGGS)	$J=6, n=10000$	稳态运行平均 $\overline{\Theta}_k \approx 0.20$	最差下确界 $\inf \Theta_k \approx 0.100$	保持严格单调性，对齐余弦平方与 $2^J$ 成正比
随机树代理模型 (Rademacher 控制)	$n=64, p=16, J=4$	耦合目标角 $\theta^2 \approx 0.25$	代理无偏期望 $2^J/n = 16/64 = 0.25$	无结构白噪声下与各向同性基准线严格重合
随机树代理模型 (平滑/线性信号)	$n=64, p=16, J=4$	CART 耦合角 $\theta^2 \approx 0.42$	投影期望基准 $2^J/n = 0.25$	结构化信号下 CART 具有显著的正向耦合增益

关键发现¶

最差界与平均界的显著分化：在 HIGGS 实验中，无论是 Hessian 余弦角 $\Theta_k$ 还是梯度边缘 $\gamma_k$，最差下确界（约 0.05）仅为运行均值（约 0.10）的一半。weak-GRN 的十二次方依赖使得最差界放大为 $(0.05)^{12} \approx 2.44 \times 10^{-16}$，理论严重失效；而 weak-AICN 的平均四次方仅为 $(0.10)^4 = 10^{-4}$，理论上界更具实际指导意义。
树深度对齐能力的二进缩放定律（Dyadic Scaling）：理论推导的 Beta 分布下界证明了 $\mathbb{E}[(\widehat{\Theta}_{n,p,J}^{\text{prox}})^2] \geq \min(2^J, n)/n$。实证观察到深度每增加 2 层（叶子节点数扩大 4 倍），余弦值近似翻倍（平方项扩大 4 倍），高度符合理论预期。
阻尼系数随迭代平滑自松弛：在优化初期，方向改善量 $\delta_k$ 较大，$\alpha_k < 1$ 实施强力阻尼防止发散；优化后期残差逐步降至噪声水平，$\delta_k$ 衰减至 0，$\alpha_k \to 1.0$，弱-AICN 自动退化为标准牛顿提升，兼顾了全局稳定性与局部快速收敛。

亮点与洞察¶

牛顿坐标下降的统一泛化视角：揭示了牛顿坐标下降法正是弱学习器族取标准基向量 $\mathcal{F} = \{c e_i : c\in\mathbb{R}, 1\leq i\leq d\}$ 时的特例，其最优方向选择准则自然对应一维 Gauss-Southwell-Lipschitz 规则，避开了 $\mathcal{O}(d^3)$ 的全矩阵求逆开销。
无需重新拟合树模型的自适应调优：利用三次模型最优值可由标量 $\frac{\alpha_k(\alpha_k-4)}{6}\delta_k^2$ 显式表达的代数性质，weak-AdaAICN 回溯调参无需重新构建决策树或重新评估梯度与 Hessian，极大削减了计算开销。
首个树提升弱学习器概率对齐下界：针对决策树在奇偶校验等病态数据上最差余弦角恒为 0 的理论障碍，引入几何各向同性投影代理模型，利用 Beta 分布与非中心卡方分布首次证明了随树深以 $2^J/n$ 提升的随机下界。

局限与展望¶

病态条件下的数值脆弱性：weak-AICN 完全依托局部 Hessian 几何诱导范数，在遇到接近奇异的退化曲率或极小特征值时可能面临步长失控，必须手动引入静态基线正则 $\lambda_{\text{base}} I$；相比之下 weak-GRN 能够自适应施加梯度自适应 $\ell_2$ 正则化。
随机代理下界与高阶迭代耦合的差距：随机树代理下界主要建立在无耦合方向或首轮迭代的高斯假设上，在后续迭代中树分裂选择与残差高度强耦合，严格的迭代过程下界分析仍属开放难题。
树结构感知的高维自适应正则化：未来可探索根据不同叶子节点局部曲率差异分别自适应配置三次惩罚系数，进一步提升在稀疏不均衡数据上的拟合效率。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙融合仿射不变自协调几何与弱学习器受限优化，将收敛阶次和最差界依赖大幅改善。
实验充分度: ⭐⭐⭐⭐☆ 覆盖了二阶下界函数、病态发散损失、工业级分类基准以及随机代理消融，代码开源。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完备，符号体系自洽，定理与附录递推链条条理极为清晰。
价值: ⭐⭐⭐⭐⭐ 为广受工业界依赖的牛顿提升与坐标下降法补齐了关键的全局收敛理论短板，具备深远指导意义。

实验配置	深度 \(J\) / 样本 \(n\)	弱学习器几何对齐指标数值	理论下界 / 参考值	观测说明
weak-AICN 树提升 (HIGGS)	\(J=2, n=10000\)	稳态运行平均 \(\overline{\Theta}_k \approx 0.05\)	最差下确界 \(\inf \Theta_k \approx 0.025\)	树深较浅时表达能力有限，平均角偏低
weak-AICN 树提升 (HIGGS)	\(J=4, n=10000\)	稳态运行平均 \(\overline{\Theta}_k \approx 0.10\)	最差下确界 \(\inf \Theta_k \approx 0.050\)	树深增加 2 层，对齐角近似翻倍（二进倍增）
weak-AICN 树提升 (HIGGS)	\(J=6, n=10000\)	稳态运行平均 \(\overline{\Theta}_k \approx 0.20\)	最差下确界 \(\inf \Theta_k \approx 0.100\)	保持严格单调性，对齐余弦平方与 \(2^J\) 成正比
随机树代理模型 (Rademacher 控制)	\(n=64, p=16, J=4\)	耦合目标角 \(\theta^2 \approx 0.25\)	代理无偏期望 \(2^J/n = 16/64 = 0.25\)	无结构白噪声下与各向同性基准线严格重合
随机树代理模型 (平滑/线性信号)	\(n=64, p=16, J=4\)	CART 耦合角 \(\theta^2 \approx 0.42\)	投影期望基准 \(2^J/n = 0.25\)	结构化信号下 CART 具有显著的正向耦合增益

实验任务 / 设置	对比算法配置	核心收敛指标 / 表现	对比基线 (GRN / 经典牛顿)	性能特征与提升
Nesterov 二阶下界函数 (\(d=100\))	AdaAICN (自适应 \(C_k\))	达到极小值所需耗时 ~2.1s	静态非自适应 AICN (\(C_{\text{best}}=81\)): ~4.2s	迭代步数与墙上时钟均取得 2.0× 加速
Nesterov 二阶下界函数 (\(d=20\), CD)	CD-AdaAICN (坐标弱学习器)	收敛至 \(10^{-6}\) 损失值	静态非自适应 CD-AICN (\(C_{\text{best}}=16\))	迭代复杂度明显降低，摆脱保守超参调节
UCI Wine Quality (Charbonnier 损失, \(\eta=1.0\))	weak-AICN (\(C_{\text{est}}=10\))	稳健平滑单调收敛至平稳值	原始牛顿提升 (Vanilla Newton)	原始牛顿彻底震荡发散；weak-AICN 稳健收敛
UCI Wine Quality (Charbonnier 损失, \(\eta=0.1\))	weak-AICN	稳定收敛，与 weak-GRN 轨迹吻合	一阶提升 (First-order)	收敛显著快于无法利用曲率信息的一阶提升
HIGGS 二分类 (二元交叉熵, \(J=4\))	weak-AICN (\(\eta=0.1, \lambda_{\text{base}}=10^{-4}\))	路径平均角 \(\overline{\Theta}_k \approx 0.10\)	weak-GRN 梯度边缘 \(\overline{\gamma}_k \approx 0.10\)	两者均值相仿，但 AICN 具 \(\Theta^4\) vs \(\gamma^{12}\) 理论优势