Research map / Optimization / Nonconvex and smooth optimization

Gradient Regularized Newton Boosting Trees with Global Convergence

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Restricted Newton Descent for Newton boosting with weak learners, proving linear convergence for Hessian-dominated losses and an O(1/k^2) global rate for a gradient-regularized Newton boosting variant.

Problem

Newton boosting (XGBoost, LightGBM, CatBoost) lacks global convergence theory; vanilla Newton with weak learners can diverge for general convex losses such as Charbonnier.

Approach

Formulates Newton boosting as Newton's method on a Hilbert space restricted to weak learners (Restricted Newton Descent), analyzed via a Hessian-induced cosine angle and a weak gradient edge; extends gradient regularized Newton (adaptive l2 term proportional to sqrt of gradient norm) to weak learners.

Key results

• Vanilla Newton boosting diverges on Charbonnier loss with learning rate 1 on Wine Quality, while gradient regularized Newton (GRN) decreases loss fastest.
• Gradient regularized restricted Newton achieves an O(1/k^2) global rate for convex losses with Lipschitz Hessians and finite sublevel sets; vanilla Newton achieves linear rate for smooth strongly convex Hessian-dominated losses.
• Cosine angle and weak gradient edge trajectories are remarkably similar on Higgs, and increase with tree depth.

Surprising findings

• The weak gradient edge and Hessian-induced cosine angle, defined in different geometries, follow remarkably similar trajectories in experiments.
• Vanilla Newton boosting diverges at learning rate 1 on Charbonnier loss while first-order boosting does not.

Limitations

• Global rate constants depend heavily on the weak gradient edge gamma (gamma^12 dependence) and cosine angle (Theta^2), which may be loose.
• Only linear rate proven for regularized scheme when eta<1 or gamma<1; superlinear rate conjectured unattainable.
• Experiments are small-scale (Wine Quality, Higgs subset) and do not benchmark against production GBDT systems on accuracy.

Experimental setup

Datasets: Wine Quality (UCI) Higgs (subset)

Benchmarks: Wine Quality UCI (Charbonnier train loss) Higgs subset (cosine angle and weak gradient edge)

Metrics: training loss cosine angle Theta_k weak gradient edge gamma_k

Baselines: vanilla Newton boosting first-order gradient boosting XGBoost-style l2-regularized Newton boosting

Builds on: XGBoost gradient regularized Newton method LogitBoost SnapBoost

Closest papers by meaning

• Affine-invariant Cubic Newton with Weak Learners (NeurIPS 2026 · similarity 0.90)
• Gradient descent with generalized Newton’s method (ICLR 2025 · similarity 0.87)
• A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.86)
• Convergence Analysis of Newton's Method for Neural Networks in the Overparameterized Limit (NeurIPS 2026 · similarity 0.86)
• Statistical Inference for Gradient Boosting Regression (NeurIPS 2025 · similarity 0.86)
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.86)