Accelerating Gradient Boosting Machine
This work addresses the computational efficiency issue for practitioners using GBM in machine learning competitions and applications, though it is incremental as it builds on existing GBM with acceleration techniques.
The authors tackled the problem of slow convergence in Gradient Boosting Machines (GBM) by proposing Accelerated Gradient Boosting Machine (AGBM), which incorporates Nesterov's acceleration techniques and uses a corrected pseudo residual to handle errors from weak learners, resulting in the first GBM algorithm with a theoretically-justified accelerated convergence rate and demonstrated effectiveness in numerical experiments.
Gradient Boosting Machine (GBM) is an extremely powerful supervised learning algorithm that is widely used in practice. GBM routinely features as a leading algorithm in machine learning competitions such as Kaggle and the KDDCup. In this work, we propose Accelerated Gradient Boosting Machine (AGBM) by incorporating Nesterov's acceleration techniques into the design of GBM. The difficulty in accelerating GBM lies in the fact that weak (inexact) learners are commonly used, and therefore the errors can accumulate in the momentum term. To overcome it, we design a "corrected pseudo residual" and fit best weak learner to this corrected pseudo residual, in order to perform the z-update. Thus, we are able to derive novel computational guarantees for AGBM. This is the first GBM type of algorithm with theoretically-justified accelerated convergence rate. Finally we demonstrate with a number of numerical experiments the effectiveness of AGBM over conventional GBM in obtaining a model with good training and/or testing data fidelity.