提出可全局收敛的二阶决策树提升算法,解决传统方法发散问题。
Gradient Regularized Newton Boosting Trees with Global Convergence
- 基于限制牛顿下降框架,引入梯度正则化项改进牛顿提升
- 实现 $\mathcal{O}(\frac{1}{k^2})$ 收敛率,匹配一阶加速方法
- 适合追求高精度与稳定性的表格数据建模场景
梯度提升决策树(GBDT)在表格数据机器学习中占据主导地位,现代实现如 XGBoost、LightGBM 和 CatBoost 均基于牛顿提升:在决策树空间中进行二阶下降。尽管其经验表现优异,但相比一阶提升,牛顿提升的全局收敛性仍不明确。本文提出受限牛顿下降框架,基于余弦角和弱梯度边概念,在希尔伯特空间中研究带近似迭代的牛顿法。在此框架下,我们恢复了基于 GBDTs 的牛顿提升及经典有限维理论作为特例。首先证明,朴素牛顿提升在满足海森矩阵主导条件的光滑强凸损失下达到线性收敛率。为处理具有利普希茨海森算子的一般凸损失,我们将近期提出的梯度正则化牛顿方案扩展至受限弱学习器设置。该方案通过引入与梯度范数平方根成比例的自适应 $\ell_2$ 正则项,对经典算法最小修改。我们建立该方案的 $\mathcal{O}(\frac{1}{k^2})$ 收敛率,从而获得全局收敛的二阶 GBDT 算法,其收敛速度与带奈斯特罗夫动量的一阶提升相当。数值实验表明,所提方案能收敛,而朴素牛顿提升可能发散。
原文摘要 · Abstract (English)
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, which studies 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. 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. We establish a $\mathcal{O}(\frac{1}{k^2})$ rate for this scheme, thereby obtaining a globally convergent second-order GBDT algorithm with a rate matching that of first-order boosting with Nesterov momentum. In numerical experiments, we show that our scheme converges while vanilla Newton boosting may diverge.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。