Block-distributed Gradient Boosted Trees
  The Gradient Boosted Tree (GBT) algorithm is one of the most popular machine
learning algorithms used in production, for tasks that include Click-Through
Rate (CTR) prediction and learning-to-rank. To deal with the massive datasets
available today, many distributed GBT methods have been proposed. However, they
all assume a row-distributed dataset, addressing scalability only with respect
to the number of data points and not the number of features, and increasing
communication cost for high-dimensional data. In order to allow for scalability
across both the data point and feature dimensions, and reduce communication
cost, we propose block-distributed GBTs. We achieve communication efficiency by
making full use of the data sparsity and adapting the Quickscorer algorithm to
the block-distributed setting. We evaluate our approach using datasets with
millions of features, and demonstrate that we are able to achieve multiple
orders of magnitude reduction in communication cost for sparse data, with no
loss in accuracy, while providing a more scalable design. As a result, we are
able to reduce the training time for high-dimensional data, and allow more
cost-effective scale-out without the need for expensive network communication.
