Abstract
Gradient Boosting Machine (GBM) introduced by Friedman (2001) is a widely popular ensembling technique and is routinely used in competitions such as Kaggle and the KDDCup. Despite their empirical success, GBMs are theoretically viewed as a form of functional gradient descent, which typically converges at a rate of $O(1/m)$ where $m$ is the number of iterations. This paper introduces the Accelerated Gradient Boosting Machine (AGBM), the first boosting framework to successfully incorporate Nesterov’s acceleration, achieving a theoretical convergence rate of $O(1/m^2)$.
Introduction: The Acceleration Hurdle
Gradient Boosting Machines are the "Swiss Army knives" of machine learning, powering everything from Kaggle-winning models to large-scale industrial ranking systems. In the world of convex optimization, Nesterov’s acceleration is a well-known technique to speed up convergence to $O(1/m^2)$. However, applying this to GBMs is notoriously difficult. GBMs rely on weak learners (like shallow decision trees) that only provide an approximation of the gradient. In a standard momentum setup, these approximation errors accumulate and amplify, often causing the algorithm to diverge rather than accelerate.
Methodology: Bridging Theory and Practice
The authors propose two primary algorithmic contributions to enable acceleration in boosting:
- Corrected Pseudo Residuals: This is the core innovation. Instead of simply fitting a weak learner to the current negative gradient, AGBM maintains an inductive "error-corrected" target. This target accounts for the discrepancy between the ideal gradient and what the weak learner actually captured in previous steps, ensuring that errors don't "snowball" in the momentum term.
- Three-Sequence Framework: Following Nesterov’s design, the algorithm maintains three sequences of models: a primary model ($f^m$), a momentum (look-ahead) model ($h^m$), and a weighted average ($g^m$) where the gradient is actually computed.
- AGBMR (Restarting): For cases where the loss function is strongly convex (like logistic loss), the authors introduce a version with "restarts" that achieves an accelerated linear convergence rate.
Experimental Results
The authors evaluated AGBM against standard GBM using several public datasets from the UCI repository and LIBSVM (e.g., a1a, w1a, german, sonar, housing) using CART (Classification and Regression Trees) as weak learners.
Faster Training and Efficiency
As shown in the training loss plots, AGBM reached lower training loss in far fewer iterations than standard GBM across various learning rates ($\eta = 1, 0.1, 0.01$). In many scenarios, AGBM with 50 trees outperformed a standard GBM with 100 trees. This results in a "sparser" ensemble, which is faster for inference in production environments.
Convergence Stability
The paper formalizes why "Vanilla" accelerated boosting (VAGBM) often fails. Without error correction, the momentum term treats the approximation error of a decision tree as a "signal" to be amplified, leading to instability. The error-corrected AGBM, however, converges reliably to the optimum.
Test Performance and Overfitting
While AGBM focuses on training optimization, it matched or outperformed GBM on test sets for most datasets when using a moderate number of trees (30–50). However, because AGBM minimizes training loss so aggressively, it can overfit earlier than standard GBM, especially on small datasets like housing. The authors note that early stopping or more aggressive regularization is essential when using accelerated methods.
Conclusion
AGBM is the first work to provide a rigorous finite-time convergence guarantee for an accelerated GBM that works with any type of weak learner. While the current analysis focuses on first-order gradient steps, extending this acceleration to second-order methods (like XGBoost) and conducting a joint theoretical study of its effects on generalization remain open challenges.
Summary updated