  Gradient Boosted Decision Tree (GBDT) is a widely-used machine learning
algorithm that has been shown to achieve state-of-the-art results on many
standard data science problems. We are interested in its application to
multioutput problems when the output is highly multidimensional. Although there
are highly effective GBDT implementations, their scalability to such problems
is still unsatisfactory. In this paper, we propose novel methods aiming to
accelerate the training process of GBDT in the multioutput scenario. The idea
behind these methods lies in the approximate computation of a scoring function
used to find the best split of decision trees. These methods are implemented in
SketchBoost, which itself is integrated into our easily customizable
Python-based GPU implementation of GBDT called Py-Boost. Our numerical study
demonstrates that SketchBoost speeds up the training process of GBDT by up to
over 40 times while achieving comparable or even better performance.
