跳到正文
返回论文列表
stat.ML提交于 已译

梯度正则化牛顿提升树及其全局收敛性

Gradient Regularized Newton Boosting Trees with Global Convergence

Nikita Zozoulenko · Daniel Falkowski · Thomas Cass · Lukas Gonon

中文摘要

梯度提升决策树(GBDT)在表格机器学习中占主导地位,XGBoost、LightGBM 和 CatBoost 等现代实现均基于牛顿提升(Newton boosting):在决策树空间中进行二阶下降。尽管经验上成功,牛顿提升的全局收敛性相比一阶提升仍缺乏理解。本文引入受限牛顿下降(Restricted Newton Descent),一个在希尔伯特空间上使用牛顿法、允许不精确迭代点的凸优化框架,基于余弦角和弱梯度边缘(weak gradient edge)概念。该框架将 GBDT 上的牛顿提升与经典有限维理论作为特例恢复。首先证明,对于满足 Hessian 主导条件的平滑强凸损失,原始牛顿提升达到线性收敛速率。为处理具有 Lipschitz Hessian 的一般凸损失,将最近的梯度正则化牛顿方案扩展到受限弱学习器设定,建立了二阶 GBDT 的首个全局 O(1/k^2) 收敛速率。该方案通过每轮引入与梯度范数平方根成正比的自适应 ℓ2 正则项,对经典算法做最小修改。数值实验表明,该方案收敛而原始牛顿提升可能发散。

关键要点

  1. 01牛顿提升的全局收敛性相比一阶提升缺乏理论理解,是本文要填补的空白。
  2. 02提出受限牛顿下降框架,统一了 GBDT 牛顿提升与经典有限维牛顿理论。
  3. 03证明原始牛顿提升在平滑强凸且满足 Hessian 主导条件下线性收敛。
  4. 04扩展梯度正则化牛顿方案,首次给出二阶 GBDT 的全局 O(1/k^2) 收敛速率。
  5. 05数值实验中正则化方案收敛,而原始牛顿提升可能发散。

解读

尚无解读。

原始英文摘要

arXiv:2605.00581v2 Announce Type: replace Abstract: Gradient Boosting Decision Trees (GBDTs) dominate tabular machine learning, with modern implementations like XGBoost, LightGBM, and CatBoost being based on Newton boosting: a second-order descent step in the space of decision trees. Despite its empirical success, the global convergence of Newton boosting is poorly understood compared to first-order boosting. In this paper, we introduce Restricted Newton Descent, a framework for convex optimization with Newton's method on Hilbert spaces with inexact iterates, based on the concepts of cosine angle and weak gradient edge. Within this framework, we recover Newton boosting with GBDTs and classical finite-dimensional theory as special cases. We first prove that vanilla Newton boosting achieves a linear rate of convergence for smooth, strongly convex losses that satisfy a Hessian-dominance condition. To handle general convex losses with Lipschitz Hessians, we extend a recent gradient regularized Newton scheme to the restricted weak learner setting, establishing the first global $\mathcal{O}(\frac{1}{k^2})$ convergence rate for second-order GBDTs. This scheme minimally modifies the classical algorithm by introducing an adaptive $\ell_2$-regularization term proportional to the square root of the gradient norm at each iteration. In numerical experiments, we show that this scheme converges while vanilla Newton boosting may diverge.

同方向论文 · stat.ML

查看全部 →