Reproduce “Gradient Regularized Newton Boosting Trees with Global Convergence” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon

Researchers from Imperial College London and Stockholm University developed Gradient Regularized Newton (GRN) boosting, a scheme that provides global O(1/k²) convergence rates for general convex losses with Lipschitz Hessians, applicable to Gradient Boosting Decision Trees (GBDTs). This framework extends theoretical guarantees to Newton boosting, which previously lacked such assurances for general cases, and is designed for integration into existing GBDT frameworks with minimal overhead.

Key insights

  • Vanilla Restricted Newton Descent achieves a linear convergence rate for a class of 'Hessian-dominated' smooth and strongly convex losses, extending prior theoretical understandings.
  • Adaptive ℓ₂-regularization in the GRN scheme ensures global O(1/k²) convergence for general convex losses with Lipschitz continuous Hessians.
  • Regularity properties (e.g., Lipschitz Hessian) of element-wise loss functions directly transfer to the overall empirical risk in the boosting function space.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.