  Gradient Boosted Decision Trees (GBDTs) are widely used for building ranking
and relevance models in search and recommendation. Considerations such as
latency and interpretability dictate the use of as few features as possible to
train these models. Feature selection in GBDT models typically involves
heuristically ranking the features by importance and selecting the top few, or
by performing a full backward feature elimination routine. On-the-fly feature
selection methods proposed previously scale suboptimally with the number of
features, which can be daunting in high dimensional settings. We develop a
scalable forward feature selection variant for GBDT, via a novel group testing
procedure that works well in high dimensions, and enjoys favorable theoretical
performance and computational guarantees. We show via extensive experiments on
both public and proprietary datasets that the proposed method offers
significant speedups in training time, while being as competitive as existing
GBDT methods in terms of model performance metrics. We also extend the method
to the multitask setting, allowing the practitioner to select common features
across tasks, as well as selecting task-specific features.
