Gradient Regularized Newton Boosting Trees with Global Convergence

• URL: http://arxiv.org/abs/2605.00581v1
• Date: Fri, 01 May 2026 11:37:17 GMT
• Title: Gradient Regularized Newton Boosting Trees with Global Convergence
• Abstract summary: We introduce Newton Descent, which studies convex optimization with Newton's method on Hilbert spaces with inexact iterates.<n>Within this framework, we recover Newton boosting with GBDTs and classical finite-dimensional theory as special cases.<n>We show that our scheme converges while vanilla Newton boosting may diverge.
• Score: 5.627791592656776
• License: http://creativecommons.org/licenses/by/4.0/
• 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, 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.

Related papers

• Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models [18.386166970880478]
  We present the Hinge Tree (HRT) framework which reframes each oblique split as a nonlinear least-squares problem.<n>We propose HRT-Boost, a mathematically synergistic ensemble extension that node-level Newton updates with stagewise functional gradient descent.
  arXiv  Detail & Related papers  (2026-05-22T09:33:20Z)
• Boost Like a (Var)Pro: Trust-Region Gradient Boosting via Variable Projection [0.0]
  textttVPBoost fuses variable projection, a training paradigm for separable models, with a second-order weak learning strategy.<n>VPBoost learns an ensemble with improved evaluation metrics in comparison to gradient-descent-based boosting.
  arXiv  Detail & Related papers  (2026-03-24T19:01:07Z)
• A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees [34.85903827323451]
  We propose a new class of regularizers constructed from the current and previous gradients to solve regularized Newton equation.<n>The proposed algorithm is adaptive, requiring no prior knowledge of the Hessian Lipschitz constant.
  arXiv  Detail & Related papers  (2025-02-07T10:10:10Z)
• How to Boost Any Loss Function [63.573324901948716]
  We show that any loss function can be optimized with boosting. We also show that boosting can achieve a feat not yet known to be possible in the classical $0th$ order setting.
  arXiv  Detail & Related papers  (2024-07-02T14:08:23Z)
• Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian [53.044526424637866]
  We consider a nonconstrained unconstrained optimization problem minimizing a twice differentiable objective function with H"older Hessian.<n>We first propose a Newton-conjugate (Newton-CG) method for finding an approximate first- and second-order stationary point.<n>We present preliminary numerical results to demonstrate the superior practical performance of our parameter-free NewtonCG method.
  arXiv  Detail & Related papers  (2023-11-22T01:50:43Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity [70.65867695317633]
  We propose two simple accelerated gradient methods, restarted gradient descent (AGD) and restarted ball (HB) method. We establish that our methods achieve an $frac1epsilon)$ number of gradient iterations. Our algorithms are simple in the sense that they only consist of Nestov's classical AGD orak's HB as well as a restart mechanism.
  arXiv  Detail & Related papers  (2022-01-27T10:04:04Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
  We propose a gradient boosting algorithm for large-scale regression problems called textitGradient Boosted Binary Histogram Ensemble (GBBHE) based on binary histogram partition and ensemble learning. In the experiments, compared with other state-of-the-art algorithms such as gradient boosted regression tree (GBRT), our GBBHE algorithm shows promising performance with less running time on large-scale datasets.
  arXiv  Detail & Related papers  (2021-06-03T17:05:40Z)
• SnapBoost: A Heterogeneous Boosting Machine [9.532706363790053]
  We study a Heterogeneous Newton Boosting Machine (HNBM) in which the base hypothesis class may vary across boosting iterations. We describe how SnapBoost is implemented, with a focus on the training complexity. We present experimental results, using OpenML and Kaggle datasets, that show that SnapBoost is able to achieve better generalization loss than competing boosting frameworks.
  arXiv  Detail & Related papers  (2020-06-17T09:38:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.