# Gradient Regularized Newton Boosting Trees with Global Convergence

arXiv: https://arxiv.org/abs/2605.00581 · HTML: https://mlsanity.com/paper/2605.00581/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 13 of 13)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [When Do Neural Nets Outperform Boosted Trees on Tabular Data?](https://mlsanity.com/paper/2305.02997/) (2023)
- [TabArena: A Living Benchmark for Machine Learning on Tabular Data](https://mlsanity.com/paper/2506.16791/) (2025)
- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [Gradient Regularization of Newton Method with Bregman Distances](https://mlsanity.com/paper/2112.02952/) (2021)
- [Functional Gradient Boosting based on Residual Network Perception](https://mlsanity.com/paper/1802.09031/) (2018)
- [Gradient and Newton Boosting for Classification and Regression](https://mlsanity.com/paper/1808.03064/) (2018)
- [Randomized Gradient Boosting Machine](https://mlsanity.com/paper/1810.10158/) (2018)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives](https://mlsanity.com/paper/1505.04243/) (2015)
- [Random Feature Representation Boosting](https://mlsanity.com/paper/2501.18283/) (2025)
- [OPTAMI: Global Superlinear Convergence of High-order Methods](https://mlsanity.com/paper/2410.04083/) (2024)

## Abstract (arXiv)

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 ℓ2-regularization term proportional to the square root of the gradient norm at each iteration. We establish a O(frac1k2) 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.