SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems
Authors: Leonid Iosipoi
Anton Vakhrushev
Venue: NeurIPS 2022 Accept (2022)
Keywords: gradient boosting
decision trees
multiple outputs
multiclass classification
multilabel classification
multioutput regression

Abstract: 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.



SketchBoost: Fast Gradient Boosted Decision Tree for Multioutput Problems
Leonid Iosipoi
Anton Vakhrushev Sber Al Lab, Moscow, Russia btbpanda@gmail.. com
Sber Al Lab and HSE University, Moscow, Russia tosipoileonid@gmii.. com
Abstract
Gradient Boosted Decision Tree (GBDT) is widely-used machine learning al- gorithm that has been shown to achieve state-of-the-ard results on many standard data science problems. We are interested in its application multioutput problems when the output is highly multidimensional. Although there are highly effective GBDT implementations, their scalability such problems is still unsatisfactory. In this paper, we propose novel methods aiming to accelerate the training process of GBDT 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 Sketch speeds up the train- ing process of GBDT by up to over 40 times while achieving comparable or even better performance.
1 Introduction
Gradient Boosted Decision Tree (GBDT) is one the most powerful methods for solving prediction problems in both classification and regression domains. It is dominant tool today in application domains where tabular data abundant, for example, in e-commerce, financial, and retail industrics. GBDT has contributed to a large amount of top solutions in benchmark competitions such as Kaggle, This makes GBDT a fundamental component in the modern data scientist's toolkit.
The main focus of this paper is the scalability of GBDT to multioutput problems. Such problems in- clude multiclass classification (a classification task with more than two mutually exclusive classes), multilabel classification (a classification task with more than two classes that are not mutually ex- clusive), and multioutput regression (a regression task with a multivariate response variable). These problems arise in various areas such as Finance OObermann and Waack 2016). Multivariate Time Series Forecasting [Zhai, Yao. and Zhou| 2020]. Recommender Systems Jahrer, Töscher, and Leg enstein 2010 and others.
Training time for 100 Iterations
1200
XGDloctt
Cathooot
1000
sBc
600
400
200
110
5
25
50
100
250
500
Number Classss
Figure 1: Training time of XGBoost and CatBoost for different number of classes on a synthetic dataset for multiclass classification. Synthetic dataset con- tains 2000k instances, each described by 100 fea- tures. The maximal tree depth was limited to 6. The experiment was conducted on GPU. Further details are given in the Supplementary Material.
There are several extremely efficient, open-source, and production-ready implementations of gra- dient boosting such as XGBoost [Chen and Guestrin 2016), LightGBM [K, Meng, Finley, Wang, Chen, Ma, Ye, and Liu 2017]. and Cat-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Boost Prrohhorenkov,, Gusev, Vorobev, Dorogush. and Gulin 2018]. Even for them, learning GBDT model for moderately large datasets can require much time. Furthermore, this time also grows with the output size of a model. Figure [ how rapidly the training time of XGBoost and CatBoost grows with the output dimension. Consequently, the number of possible applications of GBDT in the multioutput regime is very limited.
GBDT is boosting-based algorithm that ensembles decision trees as "base learners". At each boosting step, a newly added tree improves the ensemble by minimizing the error of an already built composition. There are two possible strategies on how to use GBDT to handle a multioutput problem.
One-versus-all strategy. Here, at each boosting step, single decision tree is built for every output. Consequently, every output is handled separately. XGBoost and LightGBM use this strategy.
Single-tree strategy. Here, at each boosting step, a single multivariate decision tree is built for all outputs. Consequently, all outputs are handled together. CatBoost uses this strategy.
The computational complexity of both strategies is proportional to the number of outputs. Specifically, the one-versus-all strategy requires fitting separate decision tree for each single output at each boosting step. The single-tree strategy requires scanning all the output dimensions (a) to estimate the information gain during the search of the best tree structure and (b) to compute leaf values of decision tree with a given structure (see details in Section 2). A straightforward idea to reduce the training time of single-tree GBDT is to exclude some of the outputs during the search of the tree structure which is the most time-consuming step of GBDT. However, this turns out to be rather challenging since it is unclear what outputs contribute the most to the information gain. In this paper, we address this problem and propose novel methods for fast scoring of multivariate decision trees which show a significant decrease in computational overhead without compromising the performance of the final model.
Related work. Many suggestions have been made to speed up the training process of GBDT. Some methods reduce the number of data instances used to train each base learner. For example, Stochastic Gradient Boosting (SGB) [Friedman] 2002)] chooses a random subset of data instances, gradient-based one-side sampling (GOSS) Ke et 2017) keeps the instances with large gradients and randomly drops the instances with small gradients, and Minimal Variance Sampling (MVS) [lbragimov and Gusev 2019) randomly chooses the instances to maximize the estimation accuracy of split scoring. Similarly, some methods reduce the number of features. For example, one can choose random subset of features or use principal component analysis or projection pursuit to exclude
weak features; see [Jimenez and Landgrebe| 1999 Zhou| 2012] Appel al., 2013). LightGBM [Ke] et al.] [017]] uses exclusive feature bundling (EFB) where sparse features are greedily bundled together. CatBoost (Prokhorenkova et al.] 2018) replaces categorical features with numerical ones using a special algorithm based on target statistics. Finally, some methods reduce the number of split candidates during the split scoring. The pre-sorted algorithm [Mehta et al. 1996] enumerates all possible split points the pre-sorted feature values. The histogram
based based algorithm (Alsabti et al., 1998 Jin and Agrawal 2003b Li et al. 2007 buckets continuous feature values into discrete bins and uses these bins to construct feature histograms.
regime,, Regarding the multioutput regime, the existing methods to accelerate the training process of GBDT naturally fall into the following two categories: problem transformation and algorithm adaptation.
Transformation methods (see, for example, [Hsu et al.) 2009 Tai and Lin 2012 Kapoor et al.) 2012]
Cissé et al. 2012, Wicker et al. 20166) reduce the number of targets before training model. They mainly differ in the choice of compression and decompression techniques and significantly rely on the problem structure or data assumptions. These methods pay price in terms of prediction accuracy due to the loss of information during the compression phase, and as a result, they do not consistently outperform the full bascline. Adaptation methods directly extend some specific algorithms to efficiently solve multioutput problems. To the best of our knowledge, there are only two algorithm adaptation works for GBDT. Namely, (Si et al. 2017) and Zhang and Jung [ consider models with sparse output and discuss how to utilize this sparsity to enforce the leaf values to be also sparse. Their modifications of GBDT are called GBDT-Sparse and GBDT-MO (sparse).
We approach the problem of fast GBDT training in the multioutput regime from a different perspective. Namely, instead of employing the model sparsity, we, loosely speaking, approximate the scoring function used to find the best tree structure using the most essential outputs while keeping other boosting steps without change. The methods we suggest are completely different from the ones
2

---

mentioned above and can be applied to models with both dense and sparse outputs. Moreover, our methods can be easily combined with transformation methods (by compressing the outputs beforehand and decompressing predictions afterward) or the sparsity utilization as in GBDTT-Ppase and GBDTT-M (by computing the optimal leaf values with sparsity constraint as in these algorithms).
Contributions. The contributions of this work can be summarized as follows.
We propose and theoretically justify three novel methods speed up GBDT on multioutput tasks. These methods are generic, they can be used with any loss function and do not rely on any specific data assumptions (for example, sparsity or class hierarchy) or the problem structure (for example, multilabel or multiclass). Moreover, they do not drop down the model quality and can be easily integrated into any GBDT realization that uses the single-tree tree strategy.
We implemented the proposed methods in SketchBoost. SketchBoost itself is a part of our Python- based implementation of GBDT called Py-Booss This implementation seems to be of independent interest since it does not use low-level programming languages and is easily customizable. Although fast since it works on GPU.
it is written in Python,
We present empirical study using public datasets which demonstrates that SketchBoost achieves comparable or even better performance compared to the existing state-of-the-art boosting toolkits but in remarkably less time.
Paper Organization. First, we review the GBDT algorithm in Section Next, we propose methods leading noticeable reduction in the training time of GBDT on multioutput tasks in Section 3 We illustrate the performance of these methods on real-world datasets Section Proofs and experiment details are postponed to the Supplementary Material.
2 Preliminaries
Let {(r v= be dataset with samples, where I; E I an m dimensional input and ya Rd dl dimensional output. Let also F be class of base learners, that is, functions ʃ I Rd In Gradient Boosting, the idea of which goes back to SSchapire [1990), [Freund [1955], Freund and J and is trained in an additive and
[990),,Freundd
Schapiiee 1997]. the model Fr uses T E N base learners greedy manner. Namely, at the t-th iteration, a newly added base learner f imppoves the quality of an already built model F--1 by minimization of some specified loss function / F2 x Rd + R.
(()) - > i=1 [yyi F + f(x;)).
This optimization problem is usually approached by the Newton method using the second-order approximation of the loss function
(OT
OT f(::) + (((os)) H.f((:)) +
ft E argmin fEF
where we omitted term independent of here l(f) is a regularization term, usually added to build non-complex models, and
9:
11, 22 Via
(y.
(x))
Due to the complexity of optimization over large set of base learners F, the problem is solved typically in a greedy fashion which leads us to an approximate minimizer ft. Finally, the model F; is
updated by applying learning rate >> 0 typically treated as hyperparameter: F, F. Eft-
GBDT uses decision trees as the base learners F; see the seminal paper of Friedman [200T]. decision tree is a model built by recursive partition of the feature space into several disjoint regions. Each final leaf is assigned value, which a response of the tree in the given region. Based on this construction mechanism, decision tree ff can be expressed as
f(x) = Σ 0j [xr E Ry).
where [predicate] denotes the indicator function, J is the number of leaves, Rí is the j-th leaf, and My E [&d is the value of j-th leaf. The problem of learning fe can be naturally divided into two separate problems: (1) finding the best tree structure (dividing the feature space into J areas Ri,..., Ryy, and (2) fitting decision tree with a given structure (computing leaf values Ui,..., UJ).
3

---

Finding the leaf values. Since decision trees take constant values at each leaf, for decision tree ft with leaves R Ri...., R, we can optimize the objective function from (I) for each leaf R, separately,
= argmin "ER'
( H2v) RR
+ + | )
Σ Lr,en,
Σ LIEER,
96
where we employ /2 regularization on leaf values with parameter O; here / denotes the identity matrix and || denotes the Euclidean norm.
It is worth mentioning that if the loss function / is separable with respect different outputs, all Hessians i,...., H are diagonal. If it is not the case, it is common practice to purposely simplify them to this extent in order to avoid time-consuming matrix inversion. is done so most of the single-tree GBDT algorithms (for example, CatBoost, GBDT-Sparse, and GBDT-MO). We will also follow this idea in our work. For diagonal Hessians, the optimal leaf values can be rewritten as
gi
h
Eieng 0j Eien hy +
where gi
and H; =
(3)
Finding the tree structure. Substituting the leaf values from back into the objective function, and omitting insignificant terms, we obtain
d 1 Σ S(R,), where S(R) = =E (EZEn H2) j=l Ez 14 +
Loss(fi) =
(4)
The function S(.) will be referred as the scoring function. To find the best structure, greedy algorithm that starts from a single leaf and iteratively adds branches to the tree. At general step, we want split one of existing leaves. To do this, we iterate through all leaves, features, and algorithm). For all
thresholds for each feature (they are usually determined by the histogram- leaves R and all possible splits for R, say Run and Rright. we compute the impurity score given by S ((Rie)) + 5 (agga)) The best split is considered the one which achieves the largest impurity score. This is equivalent to maximization of the information gain which usually defined as the difference between values of the loss function before and after the split, that is.
Gain 0.5 (S(R) - (S(Rien) S S(Rright))
Similar to the previous step, some simplifications be made to speed up computation of the scoring function which is done a tremendous number of times. For instance, GBDT-Sparse does not use the second-order information at all (Hessians are simplified regime of CatBoost, the second-order derivatives are left out during the split search and are used only compute leaf values. GBDT-MO the second-order derivatives in both steps but increases the computational complexity twice (histograms for both gradients and Hessians need to be accumulated).
identity matrices). In the multioutput
Sketched Split Scoring
In this section, we propose three novel methods to speed up the split search for multivariate decision trees. These methods can achieve good balance between reducing the computational complexity in the output dimension and keeping the accuracy for learned decision trees. They generic and can be used together with the methods mentioned in the Related work section that aim at reducing the number sample instances, features, or split candidates. Moreover, the proposed methods are easy to implement upon modern boosting frameworks such as XGBoost, LightGBM, and CatBoost.
As it was mentioned before, there are two "best practices" to speed up the training of GBDT model on multioutput tasks: (a) to totally ignore the second-order derivatives during the split search and (b) to use only the main diagonal of the second-order derivatives compute the leaf values. It is done so, for example, in CatBoost, one of the few boosting toolkits that use the single-tree strategy and achieve state-of-the-art results on multioutput problems. We will also develop our work on this basis.
The proposed methods are applied at each boosting step before the search for the best tree structure
and after first- and second-order derivatives (see (2) are computed. The key idea of the proposed

---

methods is to reduce the number of gradient values used in the split search so that the scoring function from 4 or, equivalently, the information gain will not change much. Specifically, the scoring function without the second-order information can be rewritten as
gi
gi
9
[2] E R]
(R) = G UR|l ? [R| +
where G
and UR =
9n
[Irn E R|
Here G Raxd is the gradient matrix and UR the indicator vector the leaf R (its i-th coordinate is equal to 1 x; E R and O otherwise). Note that we added the subscript to S to indicate its dependence on the gradient matrix G. To reduce the complexity of computing SG in d, we approximate it with Sa. for some other matrix G& Raxk with k & d. We will refer to G as the sketch matrix and to I as the reduced dimension or sketching dimension. We emphasize that Gy is assumed be used only in building histograms and finding the tree structure. After this, the optimal leaf values of a tree are assumed to be computed fairly using the full gradient matrix G.
Further we discuss three novel methods to construct reasonably good sketches G₁- - Top Outputs, Random Sampling, and Random Projections. These methods are motivated by the minimization of the approximation error given by
Error(Se, Sc.) supn|So(RR) Sc. (R)
Here the supremum is taken over all possible leaves The reason for this choice is that we want the proposed approximation to be universal and uniformly accurate for all splits we will possibly iterate over. In the Supplementary Material, we show that the proposed methods lead to nearly-optimal upper bounds on the proposed error. Since the corresponding optimization problem is an instance of Integer Programming problem, methods leading to the optimal upper bounds can be obtained only by brute force, which is not an option in our case. For further details see the Supplementary Material.
3.1
Top Outputs
The key idea of Top Outputs is rather straightforward: to choose the columns of G' with the largest Euclidian norm. Namely, by a slight abuse of notation, let us denote the columns of G by -1....: Id- Let also in, . da be the indexes which sort the columns of G in descending order by their norm, that is, [1 |I 2 19:a11 2 2... 2 I1 Now the full gradient matrix and its sketch can be written as
G
91
92
Ia and
Gk
= 9b.
912
Pik
The parameter l: here can be chosen adaptively to the norms of g1,.... ... Gd. We have not considered this generalization here since, in our view, it will greatly complicate the algorithm. Moreover, the adaptive choice of & may result in large values for this parameter and hence less gain in training time.
It is worth pointing out that Top Outputs is akin to the Gradient-based One-Side Sampling (GOSS), which successively used in LightGBM; see [Ke al.] 2017]. In GOSS, data instances with small gradients are excluded to speed up the split search. Similarly, Top Outputs excludes output components with small gradient values.
This method has one major drawback. This method chooses top & output dimensions which may not vary much from step step. For instance, if several columns have large norms and others have medium norms, Top Outputs may completely ignore the latter columns during the split search. Below consider another method that deals with this problem by introducing the randomness in the choice of output dimensions.
3.2 Random Sampling
The probabilistic approach for algebraic computations, sometimes called the "Monte-Carle method", ubiquitous; we refer the reader to the monographs Robert and Casella [2005) Mahoney [201T). and Woodruff (2014). Here we consider its application to the fast split search.
The key idea of Random Sampling is randomly sample the columns of G with probabilities proportional to their norms. Namely, we define the sampling probabilities by
pt = =|
11,
= 1,...,d. d.
5

---

These probabilities are known to be optimal for random sampling since they minimize the variance of the resulting estimate; see, for example, [Robert and Casella [205]. Further, let ig...... dx be independent and identically distributed random variables taking values with probabilities Pj+ j = These random variables represent indexes of the chosen columns of G. Finally, we consider the following sketch
Gk = 9s1
912
Fir
where
9,
Vkps 9i-
The additional column normalization by 1/ //yk is needed for unbiasedness of the resulting estimate.
There is close affinity between Importance Sampling and Minimal Variance Sampling (MVS) of Ibragimov and Gusev [2019]. MVS decreases the number of sample instances in the split search by maximizing the estimation accuracy of split scoring. Our idea is the same with the only difference that it is applied to output dimensions rather than sample instances.
Random Sampling works well especially in the extreme cases as those mentioned above. For example, several outputs have large weights and others have medium weights, Random Sampling will not ignore the latter outputs due to randomness. Or, if the number of outputs with large weights is larger than k Random Sampling will choose different output dimensions different steps. As a result, the corresponding base learners will also be quite different, which usually leads to a better generalization ability of the ensemble; see Breiman 1996).
3.3 Random Projections
In the previous section, the sketch G3 was constructed by sampling columns from G' according to some probability distribution. This process can be viewed multiplication of G by matrix II, Gk = GII, where IT E Rdxk has independent columns, and each column is all zero except for a in random location. In Random Projections, we consider sampling matrices II, every entry of which is an independently sampled random variable. This results in using random linear combinations of columns of G as columns of Gg.
This approach is based on the and Lindenstrauss) (1984). They showed that projections II from d dimensions onto randomly chosen k-dimensional subspace do not distort the pairwise distances too much. Indyk and Motwani [998] proved that to obtain the same guarantee, one can independently sample every entry of II using the normal distribution. In fact, this is true for many other distributions; see, for example, Achlioptas [2003. Since there no significant difference between distributions in numerical experiments, we decided to focus on the normal distribution.
(JL) lemma; see the seminal paper of Johnson
In Random Projections, consider the following sketch
G GTT.
where IT Ra is random matrix filled with independently sampled k-)) entries. In the Supplementary Material, we discuss why this choice leads to nearly-optimal solution to the problem we consider and why the property of preserving the pairwise distances matters here.
Random Projections has the same merits as Random Sampling since it is also a random approach. Besides that, the sketch matrix G2 here uses gradient information from all outputs since each column of Gy is a linear combination columns of G.
3.4 Complexity analysis.
Most of the GBDT frameworks use histogram- based algorithm to speed up split finding; see [Alsabti] Ranka, and Singh 1998). (Tin and Agrawal| [203a], and (Li, Wu, and Burges 2008). Instead of finding the split points on all possible feature values, histogram-based algorithm buckets feature values into discrete bins and uses these bins construct feature histograms during training. Let us say that the number of possible splits per feature is limited to h & n (usually h < 256 to store the histogram bin index using single byte). It is shown in (e et al. 2017] that in the case of a single output, splitting leaf R with ni samples requires O(m)R) operations for histogram building and (hhm) operations for split finding. As result, if the actual tree construction performed using depth-first- search algorithm, the complexity of building complete tree of depth D is O(Dam + hmm) In the

---

multioutput scenario, this complexity increases by d times: splitting a leaf R with ag samples costs Om + hmd) and depth-wiss wise tree construction costs O(Dmnd + hmmd). The methods we propose reduce the impact of d to k with A: < d. They require preprocessing step which can be done, depending on the method, a complete tree of depth D using the depth-first search can be reduced from (Dmnd + hmmd) to (nd + Dmak + 2 hmnk). Taking into account that n, m, and d can be extremely large, these methods may lead to significant improvement in the training time.
(ndkk) or ((nd) operations. As result, the complexity of building
4 Numerical Experiments
In this section, we numerically compare (a) the proposed methods from Section to speed up GBDT in the multioutput regime and (b) existing state-of-art boosting toolkits supporting multioutput tasks.
Data. The experiments are conducted on 9 real-world publicly available datasets from Kaggle, OpenML, and Mular for multiclass (4 datasets) and multilabel (3 datasets) classification and multitask regression (2 datasets). The associated details are given in the Supplementary Material.
Py-Boost. We implemented simple and fast GBDT toolkit called Py-Boost. It is written in Python and hence is easily customizable. Py-Boost works only on GPU and uses Python GPU libraries such as CuPy and Numba. It follows the classic scheme described in [Chen and Guestrin 2016]; further details are provided in the Supplementary Material. Py-Boost is available on GitHut
SketchBoost. SketchBoost is a part of Py-Boost library which implements the following three sketching strategies for fast split search: Top Outputs (Section 3.1 Random Sampling (Section
and Random Projections (Section 3.3). For convenience, Py-Boost without any sketching strategy is referred to as SketchBoost Full. All the following experimental results and evaluation code are also available on GitHubi
Baselines. Primarily we compare SketchBoost with XGBoost (v1.6.0) and CatBoost (v1.0.5). There are two reasons why we have chosen these GBDT frameworks. First, they are commonly used among practitioners and represent two different approaches to multiouput tasks (one-vs-all and single-tree). Second, they be efficiently trained on GPU, which allows us compare their training time with GPU-based SketchBoost (with an exception for CatBoost which supports multilabel classification and multioutput regression tasks only on CPU). The reason why we have not considered LightGBM as a baseline is that it uses the same multiouput strategy as XGBoost (one-vs-all) and its latest version (v3.3.2) does not support multilabel classification and multioutput regression tasks without external wrappers. Further, we also compare SketchBoost with TabNet 1.1,, a popular deep learning model for tabular data; see [Arik and Pfister [02T]] Our aim here is not to make an exhaustive comparison with existing deep learning approaches, hes (it deserves its own investigation). but make a comparison with different in nature approach which moreover often has satisfactory complexity on large multioutput datasets.
Experiment Design. If there is no official train/test split, we randomly split the data into training and test sets with ratio 80%-20% Then each algorithm is trained with 5-fold cross-validation (the train folds are used to fit a model and the validation fold is used for carly stopping). We evaluate all the obtained models on the test and get 5 scores for each model. The overall performance of algorithms is computed as an average score. As performance measure, we use the cross-entropy also report the
for classification and RMSE for regression, but, for the sake of completeness, accuracy score for classification and R-squared score for regression in the Supplementary Material. For XGBoost, Catboost, and TabNet, do the hyperparameter optimization using the Optuna framework [Akiba, Sano, Yanase, Ohta, and Koyama| 2019]. For SketchBoost, we use the same do not expect that hyperparameters
hyperparameters for CatBoost (to speed up the experiment; will vary much since we use the same single-tree approach). The sketch size is is iterated through the grid (1, 2, 5, 10, 20} (or through a subset of this grid with values less than the output dimension). Further information on experiment design is given in the Supplementary Material.
http:///muaan.sourrcfoorgg hww.:/ggeeeennddteedeeeeeeeeeeee html
httpp::/githuu.ccmm// ai http:/ab..cco/bb-a-laaaaaaa--aaa Boost
https://github.comm wtt.:////w..aaa.aaaaaaaeeaaaaaaa paper
7

---

Table 1: Test errors (cross-entropy for classification and RMSE for regression)
= their standard deviation.
SketchBocst
Baseline
Datuset
Top Outputs [foe the Ao
Random Sumpling
Random Projection (ft the best R)
SketchBoost Full (muultioupp))
CatBoost (mallicuzyu))
XoBottt (oue-15-all)
TabNet
(for the bew
(malicongu)
Multiclass clussification Olto (9 classes)
0.4715
0,4636
0,4566
0.4697
0:4658
0,4599
0,5363
1:0,0035
1.0.0026
1.0,0023
1:0,0030
1.0,0033
2000028
1.0.0063
SF-Crime (39 classes)
2.2070
2.2037
2.2038
2.20667
2.2036
2.2208
2,4819
100,0005
1.0.0004
110,0001
210,0003
1.0.0005
2.0.0008
1.0.0199
Helena classes)
2,5123
2,5693
2,5673
2.5865
2,5889
2,7197
1000002
1:0.0022
110,0026
20000225
110.0025
20.0032
1.0.0235
Dionis (355 clesses)
0,3146
0,3040
0.2848
0.3114
0.3085
0.3502
0,4753
+0.0011
+000014
+0000112
=0.0009
+0.0010
=0.0020
+000126
Multilabel classification
Medianill (IDI labels)
0,07488
0.0745
0.0743
0.0747
0.0754
0.0758
0,0859
+:1,30044
+1.34-04
=1.3e004
+111e-04
=1.1e-14
+:333--3
MoA (206 lahels)
0,0163
0.0100
0.0160
0.0160
0.0161
0.0166
0.0193
152.e-05
11.0e-05
06
-90
1.2.6c-05
12.1e-05
O:3.0e-04
Delicious (983 labels)
0,0622
0.0619
0.0620
0.0619
0,0614
0.0620
0.0664
0.6.2e005
1.5 05
-56.2e005
55.
05
018.0e-01
Multitack regression
RFI (8 tasks)
1.1860
0.9944
0.9056
1.1687
0,8975
0,92.0
3,7948
1:0.1366
100.1015
1:0.0582
20000835
1:0.0384
-0.0307
1:355935
SCM20D (16 tusks)
88.7442
86.2961
85,8061
91,0142
90,9814
89.1045
87,3655
:1066346
2:0.4398
-10.5534
22.33397
.10.3652
-0.490
113333
Table 2: Training time per fold in seconds.
(CatBoost does not support multilabel classification and multioutput regression tasks in the GPU mode.)
ShetchBoost (GPU)
Baseline (CPUGPU)
Dataset
Top Outputs
Random Sampling (Tur the best A)
Rundom Projection
SketchBoost Full
CatRoost
XGBoost
TahNet (mulliostpu)
(Toe best
(Tur the bex
(mullisutut)
(mullisutpu)
(cnc-vs-all)
Multiclass classification
GPU
GPU
GPU
Olto (9 classes)
113
102
89
131
73
1211
903
classes)
612
1146
659
4016
Helena (100 cluses)
154
180
113
355
436
1036
1196
Dianis (355 classes)
1889
2038
419
23919
18600
18635
1853
Multilabel dassification
CPU
GPU
GPU
Mediamill (101 labels)
251
263
294
1777
10164
2074
1251
MoA (206 labels)
103
189
87
696
9398
376
672
Delicions labels)
575
1259
19553
20130
15795
2002
Multitask regression
CPU
GPU
GPU
RFI (8 ticks)
369
396
340
413
804
315
207
SCM2ND (16 tasks)
528
479
597
798
1432
296
The final test errors are summarized in Table I Experiments show that, in general, SketchBoost with a sketching strategy obtains results comparable or even better than the competing boosting frameworks. Promisingly. there is always a sketching strategy that outperforms "ketchBoost Full. Random Projection achieves the best scores, but Random Sampling also performs quite well. The deterministic Top Outputs strategy scores less than other baselines everywhere. In addition, it noticeable that the one-vs-all strategy implemented in XGBoost leads to a worse generalization ability than the single-tree strategy on most datasets.
Results.
The dependence of test scores on the sketch size k for four datasets is shown in Figure 2 for other datasets see the Supplementary Material. It confirms the idea that, in general, the larger values & we take, the better performance we obtain. Moreover, our numerical study shows that there is wide range of values of k for which sketching strategies work well; see the detailed results for all & in the Supplementary Material. For most datasets, < 10 is enough to obtain a result similar or even better than SketchBoost Full or other basclines. Loosely speaking, an intuitive explanation of why reducing the output dimension may increase the ensemble quality is that building a tree using all outputs often leads to bad split choices for some particular outputs. Sketching strategies use small groups of outputs, which leads to better tree structures for these outputs and a more diverse ensemble overall. In this connection, the optimal value of k strongly depends on the relations between the outputs in a given dataset. With limited resources in practice, we would recommend using predefined value k- 5. It is common in GBDTs: modern toolkits have more than 100 hyperparameters, and many of them are not usually tuned (default values typically work well). But at the same time, one can always add & to the set of hyperparameters that are tuned. In our view, an
8

---

SCM20D (16 tasés)
SF SF-Crime (39 classes)
MoA (206 labels)
Dionis (355 classes)
Pedscit Dinenioo
Cimerson
Factorer Devi Mide
and Deranienn
Outputs
Random Sampling
Random Projection
SketchBoost
CatBoost (multioupuut
XGBoost (one-vs-all)
Figure 2: Dependence of test errors (cross-entropy for classification and RMSE for regression) on sketch dimension A.
Learnang Curve for Outo defaoer
Low m2ng Curoer Mos debaset
Suathboen boen
Figure 3: Learning curves for validation error for SketchBoost Full and SketchBoost with Random Sampling.
additional hyperparameter will not play significant role here taking into account that hyperparameter optimization is usually done using the random search or Bayesian optimization.
Further, the learning curves for validation errors on some datasets are given in Figure 3 In general, it shows that small values of k result in slower error decay early iterations. But if is properly defined, the validation error of SketchBoost with a sketching strategy is comparable to the error of SketchBoost Full, and hence both algorithms need approximately the same number of steps to convergence. This means that the proposed sketching strategies do not result in more complex models and do not significantly affect the model size or inference time. Detailed information on the number of steps to convergence for all strategies and baselines is given in the Supplementary Material.
SketchBoost does good job in reducing the training time. In Table 2 we compare training times for SketchBoost, XGBoost, CatBoost, and TabNet. One can see that it significantly increases with the dataset size and, in partieular, the output dimension. If a dataset is small, as, for example, RF1 (8 targets, 9k rows, 64 features) or Otto (9 classes, 61k rows, 93 features), our Python implementation is slightly slower than the efficient CatBoost or XGBoost GPU implementations written on low-level programming languages. But for Dionis (355 classes, 416k rows, 60 fcatures), our implementation together with a sketching strategy becomes 40 times faster than XGBoost or CatBoost without sacrificing performance. Overall, we can conclude that the proposed sketching algorithms can significantly speed up SketchBoost Full and can lead to considcrably faster training than other GBDT baselines. We recall that CatBoost can be trained on GPU only for multiclass classification tasks, and hence the time comparison with other algorithms on other tasks is not fair for CatBoost.
Finally, we see that all the GBDT implementations outperform TabNet in terms of test score on almost all tasks; see Table T again. These results confirm the conclusion from the recent surveys [Borisov] Leemann, SeBler, Haug. Pawelczyk, and Kasneci| [202]] and [Qin, Yan, Zhuang, Tay, Pasumarthi Wang, Bendersky, and Najork| [2021] that algorithms based on gradient-boosted tree ensembles still mostly outperform deep learning models on tabular supervised learning tasks. Nevertheless, Table 2 shows that TabNet converges faster than GBDTs without sketching strategies. Moreover, TabNet is even faster than SketchBoost with sketching strategies on two regression tasks. The reason for this is that if the target dimension high, affects the complexity of a neural network only in the last layer and, in general, has little effect on the training time. Further, it is also worth mentioning that neural networks tend to have much more hyperparameters than GBDTs and, as the result, need more time to be properly fine-tuned. Further details on this experiment are given in the Supplementary Material.
Comparison with GBDT-MO. We also compare SketchBoost with GBDT-MO Full and GBDT- MO (sparse) from Zhang and Jung [2021] (we want to highlight that GBDT- from Si et al. (017 does not have an open-source implementation). As sketching strategies, we consider here only Random Sampling and Random Projection. As the baseline, we consider only CatBoost on CPU (to make it comparable to GBIT-MO which works only on CPU). The datasets to compare and the best hyperparameters were taken from the original paper.

---

Table 3: Test scores (accuracy for classification and RMSE for regression) + their standard deviation.
SketchBoodd
GBDT-MO
Baseline
Datasct
Random Sampling (Re the best 6)
Rundoo Projection
SketchBoost Full
GBDT-MO (sparse) (for the X)
GBDT-MO Full
CatBoost
(inlliooppa)
Coultiontgui
(mullionauu))
Multiclass classifccation MNIST (10 classes)
0,9755
0,9740
0,9730
0.9758
0.9760
0.9684
1.0.0042
2.0.0028
1.0.0018
1:000000
Caltech (101 classes)
0,5704
0.5623
0.5549
0.4796
0,4469
0.5049
1:0.0273
1:0.0159
110.0080
1:0.0375
1:0.0590
1:0.0167
Multiiabel classification NUS WIDE (81 labels)
0.9892
0,9897
0,9893
0.9892
0.9891
0.9893
1:000003
1:000003
2:0.0002
1:0.0006
1:0.0002
1:0.0001
Multitask regression
MNIST-REG (24 takks)
0.2661
0.2654
0,2660
0.2736
0.2723
0.2708
+-000019
+0.0012
+000019
+0.0017
+-0.0026
+-0.0023
Table 4: Training time per fold in seconds.
SketchBooot (GPU)
GBDT-MO (CPU)
Baseline (CPU)
Datasel
Randon Sampling (for the best A)
Random Projection (for the best k)
SketchEnost Full GBDT-MO (sparse)
GBDT-MO Full
CalBoost (miitootppt)
(muliionppr)
(for the best
(mmltiouruu)
Multiclass classification
MNIST classes)
66
362
156
Caltoch (101 classes)
15
16
13
1312
776
136
Multilabel classffication
NUS-WIDE labels)
72
3660
2606
13857
Multitask regression
MNIST-REG (24 tusks)
120
45
90
163
210
964
Summary results are presented in Table 3 and Table 4 SketchBoost with sketching strategies outperforms other algorithms on most datasets in terms of accuracy. GBDT-MO (sparse) is everywhere slower than GBDT-MO Full (because of optimization with a sparsity constraint). Furthermore, its training time is comparable to CatBoost. The time comparison with SketchBoost is not fair because of the GPU training. but, it is shown, it is orders of magnitude faster. It is worth noting that SketchBoost Full is sometimes faster than SketchBoost with a sketching strategy. The reason for this is that if the dataset is small, then each boosting iteration requires little time. Therefore, when sketching strategy is used, the speed up for each boosting iteration may be insignificant (especially because of ineffective utilization of GPU). At the same time, the number of iterations needed to convergence may be greater, which may result in an increase in the overall training time. Exactly this happened here. Further details on this experiment are given in the Supplementary Material.
Conclusion
Training time for 100 Iterations
In this paper, we presented effective methods to speed up GBDT on multioutput tasks. These meth- ods are generic and can be easily integrated into any single-tree GBDT realization. On real-world datasets, these methods achieve comparable and sometimes even better results to the existing state- of-the-art GBDT implementations but in remark- ably less time. The proposed methods are imple- mented in SketchBoost which itself a part of our bython-based implementation of GBDT called Py- Boost. Figure concludes this paper by showing the gain in training time of SkechBoost in the same experiment as Figure from the Introduction.
1200
XiZloost
CarBooct
1000
SkaschBboo::
Time, sec
800
600
200
25
250
Number Classss
Figure 4: Training time of XGBoost, CatBoost, and SkechBoost in the same experiment in Fig- ure[[] Here SketchBoost uses Random Projection with sketch dimension & 5. Further details are given in the Supplementary Material.
f
Acknowledgements
We would like thank Gleb Gusev and Bulat Ibragimov for helpful discussions and feedback for an earlier draft of this work, Dmitry Simakov and Mikhail Kuznetsov for the help with the TabNet experiments, and Maxim Savchenko and all the Sber AI Lab team for their support and active interest in this project. We would also like to thank the anonymous reviewers for their thoughtful feedback.
10

---

References
Dimitris Achlioptas. Database- ariibssefrienlly random projections: Johnson-LLindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671-66) 687, 2003.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A Dext-Generation Hyperparameter Optimization Framework. In Proceedings the 25th ACM SIGKDD international conference on knowledge discovery data mining, KDD '19, pages 2623 2623-2631, 2019.
Khaled Alsabti, Sanjay Ranka, and Vineet Singh. CLOUDS: A Decision Tree Classifier for Large Datasets. In Proceedings of the Fourth International Conference Knowledge Discovery and Data Mining, KDD 98, pages 2-8. AAAI Press, 1998.
Ron Appel, Thomas Fuchs, Piotr Dollár, and Pietro Perona. Quickly Boosting Decision Trees: Pruning Underachieving Features Early. In Proceedings of the 30th International Conference on International Conference on Machine Learning, number 3 in ICML' 13, pages 594 602. PMLR, 2013.
Sercan Ö, Arik and Tomas Pfister. Tabnet: Attentive Interpretable Tabular Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8):6679-6687, 2021.
Vadim Borisov, Tobias Leemann, Kathrin SeBler, Johannes Haug. Martin Pawelczyk, and Gjergji Kasneci. Deep Neural Networks and Tabular Data: A Survey, 2021.
Lco Breiman. Bagging Predictors. Machine learning. 24(2):123-14)) 1996.
Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '1, pages 785-794. Association for Computing Machinery, 2016.
M. Cissé, Artières, and Patrick Gallinari. Learning Compact Class Codes for Fast Inference in Large Multi Class Classification. In Proceedings of the 2012th European Conference on Machine Learning and Knowledge Discovery in Databases Volume Part ECMLPKDD" 12, pages 506-520, 2012.
Yoav Freund. Boosting Weak Learning Algorithm by Majority. Information and Computation, 121 (2):256-285, 1995.
Yoav Freund and Robert E Schapire. A Decision-Theone Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1):119-13,, 1997.
Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189 1232, 2001.
Jerome H. Friedman. Stochastic Gradient Boosting. Computational Statistics & Data Analysis, 38 (4):367-378, 2002.
Daniel Hsu, Sham M. Kakade, John Langford, and Tong Zhang. Multi-Label Prediction via Com- pressed Sensing. In Proceedings of the 22nd International Conference on Neural Information Processing Systems, NIPS'09, pages 772-780. Curran Associates Inc., 2009.
Bulat Ibragimov and Gleb Gusev. Minimal Variance Sampling in Stochastic Gradient Boosting, 2019.
Piotr Indyk and Rajeev Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC '98, pages 604-613, 1998.
Michael Jahrer, Andreas Töscher, and Robert Legenstein. Combining Predictions for Accurate Recommender Systems. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '10, pages 693-702, New York, NY, USA, 2010. Association for Computing Machinery.

---

L.O. Jimenez and D.A. Landgrebe. Hyperspectral Data Analysis and Supervised Feature Reduction via Projection Pursuit. IEEE Transactions on Geoscience and Remote Sensing, 37(6):2653-2666 1999.
Ruoming Jin and Gagan Agrawal. Efficient Decision Tree Construction on Streaming Data. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'03, pages 571-576, New York, NY, USA, 2003a. Association for Computing Machinery.
Ruoming Jin and Gagan Agrawal. Communication and Memory Efficient Parallel Decision Tree Construction. In Proceedings of the Third SIAM International Conference on Data Mining, pages 119-129. SIAM, 2003b.
William Johnson and Joram Lindenstrauss. Extensions of lipschitz maps into a hilbert space. Contemporary Mathematics, 26: 16:1189-066 1984.
Ashish Kapoor, Raajay Viswanathan, and Prateek Jain. Multilabel Classification using Bayesian Compressed Sensing. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25 of NIPS /2, pages Associates, Inc., 2012.
Curran
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang. Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. LightGBM: A Highly Efficient Gradient Boosting Decision Tree. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, pages 3149-3157. Curran Associates Inc., 2017.
Ping Li, Christopher J. C. Burges, and Qiang Wu. McRank: Learning to Rank Using Multiple Classification and Gradient Boosting. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS 07, pages 897-904. Curran Associates Inc., 2007.
Ping Li, Qiang Wu, and Christopher Burges, McRank: Learning to Rank Using Multiple Classification and Gradient Boosting. In Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008
Michael W. Mahoney. Randomized Algorithms for Matrices and Data. Foundations and Trends in Machine Learning, 3(2): 2011.
Manish Mehta, Rakesh Agrawal, and Jorma Rissanen. SLIQ: A Fast Scalable Classifier for Data Mining. International Conference on Extending Dutabase Technology, pages 18-32. Springer- Verlag, 1996.
Lennart Obermann and Stephan Waack. Interpretable Multiclass Models for Corporate Credit Rating Capable of Expressing Doubt. Frontiers in Applied Mathematics and Statistics, 2, 2016.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. CatBoost: Unbiased Boosting with Categorical Features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pages 6639-6649. Curran Associates Inc., 2018.
Zhen Qin, Le Yan, Honglei Zhuang, Tay, Rama Kumar Pasumarthi, Xuanhui Wang, Mike Bendersky, and Mare Najork. Are Neural Rankers still Outperformed by Gradient Boosted Decision Trees? In International Conference on Learning Representations, 2021.
Christian P. Robert and George Casella. Monte Carlo Statistical Methods (Springer Texts in Statistics). Springer-Verile Berlin, Heidelberg, 2005. ISBN 0387212396.
Robert F. Schapire. The Strength of Weak Learnability. Machine Learning, 5(2):197-227, 1990.
Si Si, Huan Zhang, S. Sathiya Keerthi, Dhruv Mahajan, Inderjit S. Dhillon, and Cho-Jui Hsieh. Gradient Boosted Decision Trees for High dimensional Sparse Output. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3182-3190. PMLR, 2017.
12

---

Farbound Tai and Hsuan-Tien Lin. Multilabel Classification with Principal Label Space Transforma- tion. Neural Computation, 24(9):2508 -24222 2012.
Jörg Wicker, Andrey Tyukin, and Stefan Kramer. Nonlinear Label Compression and Transformation Method for Multi-Label Classification using Autoencoders. In The 20th Pacific Asia Conference on Knowledge Discovery and Data Mining (PAKDD), volume 9651 of Lecture Notes in Computer Science, pages 328 -400,00 Switzerland, 2016. Springer International Publishing.
David P. Woodruff. Sketching Tool for Numerical Linear Algebra. Foundations and Trends in Machine Learning, 10(1-2):1-157, 2014.
Naiju Zhai, Peifu Yao, and Xiaofeng Zhou. Multivariate Time Series Forecast in Industrial Process Based on XGBoost and GRU. In 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), volume 9, pages 1397-1400. IEEE, 2020.
Zhendong Zhang and Cheolkon Jung. GBDT-MO: Gradient-Boosee Decision Trees for Multiple Outputs. IEEE Transactions on Neural Networks and Learning Systems, 32:3156-3161 2021.
Zhi Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC, 2012.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you the full of assumptions of all theoretical results? [Yes] See the Supplementary Material
(b) Did you include complete proofs of all theoretical results? [Yes] See the Supplementary Material
3. If you ran experiments...
(a) Did you include the code. data, and instructions needed reproduce the main ex- perimental results (either the supplemental material or as a URL)? [Yes] See the Supplementary Material
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See the Supplementary Material
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] See Section and Supplementary Material
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See the Supplementary Material
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See the Supplementary Material
(b) Did you mention the license of the assets? [Yes] use open source assets
(c) Did you include any new assets either the supplemental material or as URL? [Yes] See the Supplementary Material
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A] We use open source assets
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "gCLree-cVM", "reviewer": "Reviewer_B4Dg", "summary": "This paper aims to speed up the search process of the tree split in the training of Gradient Boosted Decision Tree (GBDT), especially for tasks with highly dimensional output. The authors propose three methods, Top-Outputs, Random Sampling and Random Projections,  to reduce the computational complexity of the split scoring function. Extensive experiments demonstrate the effectiveness of SketchBoost in terms of performance and efficiency.", "questions": "[Q1]: Random Projection appears to routinely outperform the other two methods; under what circumstances would you advise using the other two methods? It seems that the Random Projections is an advanced version of the other two proposed methods and the paper can be improved if the random matrix used in projection can be adaptive to the task datasets.\n\n[Q2]: The sensitivity analysis of sketch dimension k indicates that reducing dimensions can result in distinct performance patterns. A interesting discovery is that Random Projections perform optimally when k = 1. When use SketchBoost for datasets with varying output dimensions, will there be a recommendation for selecting k?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n[P1]: The paper is well written and organized in terms of clarity.\n\n[P2]: Extensive tests are conducted to demonstrate the efficacy of the proposed strategy. Test results demonstrate that SketchBoost can obtain results equivalent to or even superior to existing SOTA approaches. SketchBoost is an order of magnitude faster on multidimensional datasets such as Dionis (355 classes) and Delicious (983 labels).\n\nCons:\n\n[C1]: In order to deal with multi-dimensional tasks, some baseline could be considered. ( e.g LightGBM according to [1], a Deep learning-based solution[2][3])\n\n[C2]: A related discussion connecting to deep learning method would be better.\n\n[C3]: Some typo like line 110/257.\n\n\n[1] Deep Neural Networks and Tabular Data: A Survey, https://arxiv.org/abs/2110.01889\n\n[2]VIME: Extending the Success of Self- and Semi-supervised Learning to Tabular Domain https://proceedings.neurips.cc/paper/2020/file/7d97667a3e056acab9aaf653807b4a03-Paper.pdf\n\n[3] TabNet, https://arxiv.org/abs/1908.07442\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bQbR5vN_HLK", "reviewer": "Reviewer_psGW", "summary": "The submission presents three methods to speed up split finding in multi-output gradient boosted decision tree ensembles. The best-performing method applies Gaussian random projections to compress the gradient matrix before splits are found based on the compressed matrix. Empirical results on several multi-class, multi-label, and multi-target regression problems show that this yields much faster training times while maintaining a similar level of accuracy.\n", "questions": "N/A", "limitations": "There does not seem to be an explicit discussion of limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "What is proposed makes sense, and the paper is well written. The empirical results are presented \"for the best k\", which determines the amount of compression, and this seems to imply parameter tuning on the test set, which would be problematic. However, it seems doubtful that the overall findings would be affected significantly by this.\n\nWhat is of greater concern is that the proposed method should probably be compared to other, more generic approaches to multi-target prediction that are based on compressing the vector of targets, e.g.,\n\nTsoumakas, G., Spyromitros-Xioufis, E., Vrekou, A., & Vlahavas, I. (2014, September). Multi-target regression via random linear target combinations. In Joint european conference on machine learning and knowledge discovery in databases (pp. 225-240). Springer, Berlin, Heidelberg.\n\nHsu, Daniel J., Sham M. Kakade, John Langford, and Tong Zhang. \"Multi-label prediction via compressed sensing.\" Advances in neural information processing systems 22 (2009).\n\nJoly, A., Geurts, P., & Wehenkel, L. (2014, September). Random forests with random projections of the output space for high dimensional multi-label classification. In Joint European conference on machine learning and knowledge discovery in databases (pp. 607-622). Springer, Berlin, Heidelberg.\n\nKapoor, A., Viswanathan, R., & Jain, P. (2012). Multilabel classification using bayesian compressed sensing. Advances in neural information processing systems, 25.\n\nCissé, M., Artieres, T., & Gallinari, P. (2012, September). Learning compact class codes for fast inference in large multi class classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (pp. 506-520). Springer, Berlin, Heidelberg.\n\nWicker, J., Tyukin, A., & Kramer, S. (2016, April). A nonlinear label compression and transformation method for multi-label classification using autoencoders. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 328-340). Springer, Cham.\n\nThe choice of x axis in Figure 1, particularly given the small size of the font used to label the axis, may mislead the reader into thinking that dependence on the number of targets is not linear. Also, Figure 1 illustrates performance for multi-class classification. It seems multi-label classification would be a more obvious example. Finally, it is necessary to (somewhere) present details of the synthetic data and the exact configuration of the learning algorithms.\n\nTypos:\n\nThere is a broken reference on Line 110.\n\n\"on the most multiclass datasets\"\n\n\"it achieve\"\n\n\"it is order of magnitude faster\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6CphUQHtrmQ", "reviewer": "Reviewer_1K6v", "summary": "The authors present three approaches to improve Gradient Boosted Decision Trees (GBDT) for multi output problems. The main goal is to speed up the training time of GBDT especially for those datasets with high number of classes. The authors' approaches focuses on a more efficient way to compute the scoring function, which maintains similar levels of performance (predictive performance). \nThe authors approaches are not a substitute for XGBoost, CatBoost or any SOTA GBDT algorithm, but rather can be integrated with any of these solutions. \nFinally, the authors present extensive experiments to validate their solution, showing significant decrease in training time without compromising predictive performance. \n ", "questions": "The questions are part of the previous section (Strengths and Weaknesses). \nBut to summarize them\n- Table 1, error metrics reported of running everything on GPU?\n- Why in Table 4 SketchBoost Full is taking less training time?\n- Why GBDT-MO Sparse, Full and CatBoost (Table 4) are on CPU?", "limitations": "I don't have anything to add here. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe this paper is well-written, tackles a relevant problem, considering how often these kind of algorithms are used in industrial settings, has a solid theoretical background, which is then evaluated with extensive experiments on different datasets. \n\nIn particular, I believe the strengths of this paper are: \n- Problem that they tackle is relevant\n- The solution is built to be used on top of existing SOTA algorithms\n- SOTA algorithms are also compared to their solution, showing promising results\n- Nice description of the complexity analysis between their solution and having the standard approach (Section 3.4). \n- Nice comparison by running the baselines also on the GPU\n- Good and promising results overall. \n- Code available \n\nA few things to improve that are worth mentioning:\n- Conclusions section: I am missing a conclusions section where you summarize the goal of the paper and the findings. It reads strange and like there is something missing when the paper just ends in the last comparison of the algorithms. \n- Table 1: The error metrics reported are after running all algorithms in the GPU right? (same as for Table 2, that its mentioned explicitly). \n- Would be good to clarify why in Table 4 SketchBoost Full is taking less time to run than Random Sampling and Random Projection? I was expecting that the approaches presented by the authors would take less training time, as occurred during the comparison with CatBoost and XGBoost (Table 2). Is there a reason for this? \n- For the second experiment, the comparison against GBDT-MO sparse and full are conducted on the CPU. Same as for CatBoost. Is the reason for this because the implementations that are available for such algorithms are only for the CPU? It would be nice to clarify. Same as why in that case CatBoost is run on the CPU (I guess to make it comparable to the other two). \n- A figure similar to Figure 1 but with the authors proposed algorithms would be nice to include (I haven't checked if it's part of the supplementary material) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept