Randomized Gradient Boosting Machine
  Gradient Boosting Machine (GBM) introduced by Friedman is a powerful
supervised learning algorithm that is very widely used in practice---it
routinely features as a leading algorithm in machine learning competitions such
as Kaggle and the KDDCup. In spite of the usefulness of GBM in practice, our
current theoretical understanding of this method is rather limited. In this
work, we propose Randomized Gradient Boosting Machine (RGBM) which leads to
substantial computational gains compared to GBM, by using a randomization
scheme to reduce search in the space of weak-learners. We derive novel
computational guarantees for RGBM. We also provide a principled guideline
towards better step-size selection in RGBM that does not require a line search.
Our proposed framework is inspired by a special variant of coordinate descent
that combines the benefits of randomized coordinate descent and greedy
coordinate descent; and may be of independent interest as an optimization
algorithm. As a special case, our results for RGBM lead to superior
computational guarantees for GBM. Our computational guarantees depend upon a
curious geometric quantity that we call Minimal Cosine Angle, which relates to
the density of weak-learners in the prediction space. On a series of numerical
experiments on real datasets, we demonstrate the effectiveness of RGBM over GBM
in terms of obtaining a model with good training and/or testing data fidelity
with a fraction of the computational cost.
