# SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems

arXiv: https://arxiv.org/abs/2211.12858 · HTML: https://mlsanity.com/paper/2211.12858/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 54 references that are in the map.
- First posted on arXiv 23 Nov 2022.

## Builds on (most cited first, 11 of 11)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Revisiting Deep Learning Models for Tabular Data](https://mlsanity.com/paper/2106.11959/) (2021)
- [TabNet: Attentive Interpretable Tabular Learning](https://mlsanity.com/paper/1908.07442/) (2019)
- [Deep Neural Networks and Tabular Data: A Survey](https://mlsanity.com/paper/2110.01889/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [GBDT-MO: Gradient Boosted Decision Trees for Multiple Outputs](https://mlsanity.com/paper/1909.04373/) (2019)
- [Simple Modifications to Improve Tabular Neural Networks](https://mlsanity.com/paper/2108.03214/) (2021)
- [Minimal Variance Sampling in Stochastic Gradient Boosting](https://mlsanity.com/paper/1910.13204/) (2019)
- [Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds](https://mlsanity.com/paper/1310.1502/) (2013)
- [Approximate Matrix Multiplication with Application to Linear Embeddings](https://mlsanity.com/paper/1403.7683/) (2014)

## Built on by (most cited first, 6 of 6)

- [Scaling Up Diffusion and Flow-based XGBoost Models](https://mlsanity.com/paper/2408.16046/) (2024)
- [Improve Deep Forest with Learnable Layerwise Augmentation Policy Schedule](https://mlsanity.com/paper/2309.09030/) (2023)
- [Tsururu: A Python-based Time Series Forecasting Strategies Library](https://mlsanity.com/paper/2509.15843/) (2025)
- [Forecasting with Hyper-Trees](https://mlsanity.com/paper/2405.07836/) (2024)
- [Improving GBDT Performance on Imbalanced Datasets: An Empirical Study of Class-Balanced Loss Functions](https://mlsanity.com/paper/2407.14381/) (2024)
- [Fr'echet Geodesic Boosting](https://mlsanity.com/paper/2509.18013/) (2025)

## Abstract (arXiv)

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.