  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.
