Gradient Regularized Newton Boosting Trees with Global Convergence
| Authors | Nikita Zozoulenko et al. |
| Year | 2026 |
| Field | Statistics / ML |
| arXiv | 2605.00581 |
| Download | |
| Categories | stat.ML, cs.LG |
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 -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.
Engineering Breakdown
Plain English
This paper addresses a long-standing gap in the theory of Gradient Boosting Decision Trees (GBDTs)—specifically Newton boosting methods used by XGBoost, LightGBM, and CatBoost—by proving they achieve linear convergence rates under smooth, strongly convex conditions. The authors introduce Restricted Newton Descent, a framework that analyzes Newton's method on Hilbert spaces with inexact iterates, using concepts like cosine angle and weak gradient edge to unify the theory of GBDT boosting with classical finite-dimensional optimization. The key finding is that vanilla Newton boosting converges linearly when applied to convex objectives, filling a critical theoretical gap compared to the well-understood first-order boosting methods that practitioners have long relied on. This work bridges the empirical dominance of Newton boosting in production systems with rigorous convergence guarantees.
Core Technical Contribution
The main technical novelty is the Restricted Newton Descent framework, which generalizes Newton's method to Hilbert spaces with inexact iterates—a setting that directly maps to decision trees in GBDT implementations. Rather than analyzing Newton boosting directly in tree space (which is complex), the authors develop a unified theory using geometric concepts (cosine angle, weak gradient edge) that recovers both Newton boosting with GBDTs and classical finite-dimensional Newton methods as special cases. They prove that under convexity and smoothness assumptions, Newton boosting achieves linear convergence rates—matching first-order methods in terms of rate, but with the second-order benefits Newton methods provide. This is novel because prior convergence analyses of Newton boosting were either incomplete or required unrealistic assumptions about tree fitting quality.
How It Works
The framework operates in three layers. First, at the Hilbert space level, the authors formalize Newton descent with inexact iterates, where the 'iterate' is not computed exactly but approximately (as tree fits are in practice). The key geometric insight is using cosine angle—a measure of how well the inexact Newton step aligns with the true Newton direction—to quantify approximation quality without requiring exact solutions. Second, they define weak gradient edge, a relaxation of the classical full-rank assumption, which allows the theory to handle settings where the loss function's curvature properties aren't perfect (common with real decision tree fits). Third, they instantiate this framework to GBDT Newton boosting: each iteration fits a tree to approximate the negative Hessian-scaled gradient, and the convergence proof shows that as long as the tree fit maintains reasonable alignment (captured by cosine angle bounds), the overall sequence converges linearly to the optimum. The output is a sequence of models (ensemble of trees) where the loss decreases geometrically with iteration count.
Production Impact
For engineers maintaining or building GBDT systems, this work provides theoretical justification for tuning Newton boosting hyperparameters with confidence. Production XGBoost/LightGBM users can now rely on convergence guarantees when using second-order methods, reducing uncertainty around when to stop boosting rounds or how aggressive learning rates can be. The theory suggests that tree depth and quality of tree fits (measured implicitly by cosine angle bounds) directly control convergence speed, giving practitioners a principled way to set max_depth and num_leaves parameters. However, the convergence guarantees assume smooth, strongly convex losses—many real applications (classification, ranking, custom loss functions) violate these assumptions, so the theory applies cleanly mainly to regression and convex surrogates. The practical implementation cost is minimal since it doesn't require algorithm changes; it's purely theoretical validation of existing methods, so integration friction is near zero, though practitioners should be aware the linear rate applies only to convex settings.
Limitations and When Not to Use This
The paper's main limitation is its restriction to convex, strongly convex loss functions—most real-world GBDT use cases involve non-convex objectives (logistic loss for classification, custom ranking losses, etc.), where the convergence guarantees do not apply. The theory assumes inexact iterates (tree fits) satisfy certain cosine angle bounds, but the paper does not fully characterize how standard tree-fitting algorithms (greedy splits) achieve these bounds in practice, leaving a gap between theory and implementation. Additionally, the analysis does not account for regularization (L1/L2 penalties, tree pruning) that are essential in production GBDTs to prevent overfitting, so the theory is incomplete for real deployed systems. The framework also does not address non-smooth losses common in GBDT practice (hinge loss, quantile loss), multiclass objectives, or the discrete nature of tree construction, meaning the applicability to actual production systems is narrower than the impressive coverage of XGBoost-like implementations might suggest.
Research Context
This work builds on decades of optimization theory (Newton's method in Hilbert spaces) and recent empirical successes of GBDT methods, particularly the observation that Newton boosting variants outperform first-order boosting in practice despite less theoretical understanding. The paper draws from classical convex analysis and extends results from first-order boosting theory (which had linear convergence proofs) to the second-order setting. It positions itself as filling a theoretical gap that has existed since the rise of modern GBDT libraries—practitioners have used Newton boosting successfully for over a decade, but the mathematical foundations lagged behind implementations. The work opens research directions toward non-convex extensions, tighter characterization of tree-fitting approximation quality, and convergence rates under realistic (non-smooth, regularized) objectives that practitioners actually optimize.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::