Affine-invariant Cubic Newton with Weak Learners

Nikita Zozoulenko; Daniel Falkowski; Thomas Cass; Lukas Gonon

stat.MLOct 24, 2026

Affine-invariant Cubic Newton with Weak Learners

Authors: Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon

Organizations: Imperial College London · Stockholm University · University of St. Gallen

Abstract

Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/γ^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $γ^{12}$ dependence on a worst-case `weak gradient edge' $γ$ . In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overlineΘ_k$ along the optimization path and directional improvements $δ_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $δ_k$ . Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overlineΘ_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

Figures & tables

Panel of Figure 1 — Figure 1: Comparison of weak learner edges for tree boosting on HIGGS ( $n=10000,\ J=4$ ): Hessian cosine angle $\Theta_{k}$ for weak-AICN, weak gradient edge $\gamma_{k}$ for weak-GRN, and Euclidean cosine angle $\Theta_{k}^{E}$ for first-order boosting. Left: Edges against boosting iterations. Right: Edges against training loss. Solid lines show arithmetic running averages; dashed lines show running infima. The dotted line shows the proxy expectation lower bound from Section 4.1 as a reference value.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Performance of exact AdaAICN versus non-adaptive AICN on Nesterov’s second-order lower bound function ( $d=100$ ). Left: Loss against the number of optimization iterations. Right: Loss against wall-clock time (seconds).

Panel of Figure 3 — Figure 3: Performance of Newton coordinate descent AdaAICN versus non-adaptive AICN on Nesterov’s second-order lower bound function ( $d=20$ ). Left: Loss against the number of optimization iterations. Right: Loss against wall-clock time (seconds).

Figure 4: Training loss trajectories on the UCI Wine Quality dataset using the Charbonnier loss. We compare weak-AICN, weak-GRN, vanilla Newton boosting, and first-order gradient boosting at two learning rates:

\eta=1.0

(left) and

\eta=0.1

(right). Vanilla Newton boosting fails to converge without sufficient dampening (

\eta=1.0

), while weak-AICN and weak-GRN converge robustly across both settings.

Panel of Figure 5 — Figure 5: Convergence metrics on the HIGGS dataset using Binary Cross Entropy ( $\eta=0.1,J=4$ ). Top left: Training loss convergence for weak-AICN, weak-GRN, and first-order gradient boosting. Top right: Evolution of the weak-AICN dampening factor $\alpha_{k}$ , which approaches $1.0$ as optimization progresses. Bottom left: Evolution of the effective adaptive $\ell_{2}$ regularization $\lambda_{k}$ used by weak-GRN. Bottom right: Directional improvement $\delta_{k}$ of the weak Newton update used by weak-AICN.

Figure 7: Squared-loss first-iteration proxy comparison for $n=64$ , $p=16$ , and $J=0,\dots,6$ . Rows correspond to dyadic and CART fitting; columns correspond to Rademacher, linear, and smooth label models. Each panel compares the coupled target $\Theta_{J,\mathsf{A}}(X;f_{1}^{\mathrm{N}}\mid I)^{2}$ with the uncoupled proxy $\Theta_{J,\mathsf{A}}(X;U_{I}\mid I)^{2}$ . Shaded bands are bootstrap $95\%$ confidence intervals for the mean.

Figure 8: Binary logistic-loss first-iteration proxy comparison for $n=64$ , $p=16$ , and $J=0,\dots,6$ . Rows correspond to dyadic and CART fitting; columns correspond to Rademacher, linear, and smooth label models. Each panel compares the coupled Newton direction $\Theta_{J,\mathsf{A}}(X;f_{1}^{\mathrm{N}}\mid H_{0})^{2}$ with the uncoupled metric-matched proxy $\Theta_{J,\mathsf{A}}(X;U_{H_{0}}\mid H_{0})^{2}$ . Shaded bands are bootstrap $95\%$ confidence intervals for the mean.

Figure 9: Coupling advantage $\Delta_{J,\mathsf{A}}$ as a function of tree depth. Rows correspond to dyadic and CART fitting; columns correspond to squared and logistic losses. Shaded bands are bootstrap $95\%$ confidence intervals for the mean paired difference. Positive values indicate that the coupled first Newton direction is more tree-alignable than an uncoupled metric-isotropic direction in the same geometry.

Curvature-Aware Optimization

See all 25 papers

Gradient Regularized Newton Boosting Trees with Global Convergence
May 1, 2026Nikita Zozoulenko, Daniel Falkowski, Thomas Cass +1Gradient-Boosted Decision Trees Optimization Convergence Analysis
Department of Mathematics, Imperial College London, UK · Department of Mathematics, Stockholm University, Sweden · School of Computer Science, University of St. Gallen, Switzerland
Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
Feb 23, 2023El Mahdi Chayti, Martin Jaggi, Nikita DoikovSecond-Order Optimization Stochastic Optimization Convergence
Machine Learning and Optimization Laboratory (MLO), EPFL
Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence
Aug 22, 2026Rodion PodorozhnySecond-Order Optimization Neural Network Optimization
Texas State University

May 1, 2026J/K move · Enter open · S save

Gradient Regularized Newton Boosting Trees with Global Convergence

Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon

Department of Mathematics, Imperial College London, UK · Department of Mathematics, Stockholm University, Sweden · School of Computer Science, University of St. Gallen, Switzerland

Gradient-Boosted Decision Trees Optimization Convergence Analysis Second-Order Optimization

Open paper AskPDF 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

\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.

Abstract

Curvature-Aware Optimization

Explore similar work

Gradient Regularized Newton Boosting Trees with Global Convergence

Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods

Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence