Learn Together, Stop Apart: a Novel Approach to Ensemble Pruning
Authors: Bulat Ibragimov
Gleb Gennadjevich Gusev
Venue: ICLR 2022 Submitted (2022)
Keywords: ensemble
boosting
regularization
clusterization

Abstract: Gradient boosting is the most popular method of constructing ensembles that allow getting state-of-the-art results on many tasks. One of the critical parameters affecting the quality of the learned model is the number of models in the ensemble, or the number of boosting iterations. Unfortunately, the problem of selecting the optimal number of models still remains open and understudied. In this paper, we propose a new look at the hyperparameter selection problem in ensemble models. In contrast to the classical approaches that select the universal size of the ensemble from a hold-out validation subsample, our algorithm uses the hypothesis of heterogeneity of the sample space to adaptively set the required number of steps in one common ensemble for each group of objects individually. Experiments on popular implementations of gradient boosting show that the proposed method does not affect the complexity of learning algorithms and significantly increases quality on most standard benchmarks up to 1.5\%.

Under review as a conference paper at ICLR 2022
LEARN TOGETHER, STOP APART: A NOVEL APPROACH TO ENSEMBLE PRUNING
Anonymous authors Paper under double-blind review
ABSTRACT
Gradient boosting is the most popular method of constructing ensembles that al- low getting ofate-of-the-art results on many tasks. One of the critical parameters affecting the quality of the learned model is the number of models in the ensemble, or the number of boosting iterations. Unfortunately, the problem of selecting the optimal number of models still remains open and understudied. In this paper, we propose a new look at the hyperparameter selection problem in ensemble models. In contrast the classical approaches that select the universal size of the ensemble from a hold-out validation subsample, our algorithm uses the hypothesis of hetero- geneity of the sample space to adaptively set the required number of steps in one common ensemble for different regions of data points individually. Experiments popular implementations of gradient boosting show that the proposed method does not affect the complexity of learning algorithms and significantly increases quality on most standard benchmarks up to 2%.
INTRODUCTION
There are still many areas where classical machine learning algorithms prevail over deep neural networks despite the dramatic growth of their usage in artificial intelligence research. One of such classical algorithms is Gradient Boosting (GB) (Friedman (200T). It allows obtain high-quality models on table data with no multimedia (e.g.. images, audios, videos), with samples full of cate- gorical features, noisy features and labels, missing data (Zhang & Haghani [0155] Li et al. [007] Babajide Mustapha & Saeed] 2016). Also, the undoubted advantage of the boosting method is the low computational complexity of training and inference (Deng et al., 2018). For these reasons, Gra- dient Boosting is widely used in ranking (Chapelle & Chang. 2011] I). recommender systems (Cheng ctt al. 2014), meta-learning (LeDell & Poirier 2020), and many other tasks (Touzani et al. 2018
Trofimov et al. 2012 Ling al. 2017).
In recent years, many hyperparameters and additional options have been proposed for GB influenc- ing the performance of the learned model (Ke et al.) 2017: Ibragimov & Gusev 2019). But the learning rate (weight each model the ensemble) and the size of the ensemble are the key ones. Large models are responsible for revealing complex dependencies in the data but require more time for training and inference (Friedman, 2002). In comparison, the smaller ones are less expressive but more time-efficient. The standard approach select an optimal number of training steps is to control the quality of the model by measuring it on a hold-out sample called validation set, which separate from the training data. The idea is moment (overfitting point) when the validation score stops growing and begins going down. Then one can prune the ensemble the retrieved number of iterations.
a large enough size of the model and find the
The described method has a significant and surprisingly understudied weakness. The approach as- sumes the existence of a universal ensemble size equally effective for any instance in the sample. In other words, the hypothesis is that all samples require approximately the same number of learners to them well. However, in practice, the learning task can consist of different subtasks, which correspond to different regions in the input space of the dataset, where examples follow different distributions with diversified complexities and functional dependencies. In particular, the data space may contain regions of both simple and complex surfaces for training. For the first ones, the ensem- ble needs a relatively small number of boosting rounds to be trained well, while the latter requires a way longer path until convergence. In this case, the generic boosting size selected by the least regret

---

Under review as a conference paper at ICLR 2022
principle is compromise between simple and complex areas. This approach encourages models with a composition of overfitted and underfitted regions in the dataset.
method to prune large GB models based adaptive choice of the optimal size of the ensemble. As the standard version GB (Friedman 2001). we train sequence of learners in ensemble but apply different number of learned models different regions in the dataset. Namely, we build an additional model that divides the input space into regions where the distribution of data points has homogeneous complexity and representativity. Then optimize the ensemble size to each region individually. Our method incurs meager computational costs and can be easily incorporated into any existing learning pipeline. We apply the proposed approach to state-of- state-of-the-art open-source GB algorithms and demonstrate its ability to outperform on popular publicly available benchmarks consistently. We show that the described problem of the universal stopping moment highly affects the quality of trained models. To the best of our knowledge, this the first research devoted to adaptive, instance-we wise early stopping in GB, and we hope this paper will encourage further research of the GB algorithm.
To handle this issue, propose
The rest of the paper organized as follows. Section introduces notations and background on GB. Previous works on early stopping and ensemble pruning are discussed in Section 3 In Section 4 we reveal the details of the proposed approach and present theoretical reasoning and discussions. In Section 5, the effectiveness of the algorithm is empirically studied using several popular datasets. Section 6 makes conclusions and proposes ideas for future work.
BACKGROUND
In this section, we introduce necessary notations and briefly discuss basic concepts concerning gra- dient boosting and cross cross- validation for clarity and independent reading reasons.
2.1 GRADIENT BOOSTING
Let S = (ax, Pi= be a sample from some fixed but unknown distribution P(æ: y). where æ; = (u., vr.t. E X is m-dimensional feature representation and y; target value of the i-th observation. The classical formulation of the learning problem consists in constructing a function F: minimizing the expected target prediction error, which is calculated using loss function L
C(P, F) Eea
y) min
Since the distribution is not given and the sample S is the only source of data, the task reduces to empirical risk minimization problem:
1 n 7 Σ L(F(z.).)) min
((S (
The ability achieve smaller value of empirical risk is bounded by the complexity of the set FF from which the desired function F' E F is selected. A common approach to increase the expres- siveness of the learned model build composition Gradient Boosting (GB) constructs an ensemble FB of size B as weighted sum of base functions (J1, J2, ..., [n] C F::
an ensemble) of functions from
FB( = Σ aaf((z)
When the set of available base functions F is closed under scalar multiplication, multipliers ag usually fixed and equal: Vi a; a, where is a hyperparameter of the GB algorithm called learning rate. Having constructed the first terms, the learning algorithm aimes to select the next function Ji sequentially solution of:
2

---

Under review as a conference paper at ICLR 2022
(s F = π
Σ 1=1
L [(Ft-1(7))) + fe(2a)) + min ft
The approximate solution of the latter equation GB is usually constructed as follows. Algorithm calculates first and second order derivatives é at the point Ft-1 w.r.t. predicted values g: gf =
0L( 09:
h
8 L(
and selects a least squares estimator to Newton's (
09g
= (m.)
gradient step in the functional space:
10-00((((i ( hf v.)
))
Eni vi ((()))
ft = arg min FEF
(2)
(Chen & Guestrin 2016 for details.
2.2 MODEL SELECTION VIA CROSS- VALIDATION
Since the quality estimation based on a train set used in the learning process is biased (Prokhorenkova al. (017) (the inference is performed on the unseen data), conventional to use a separate independent set, called validation set, to control the generalization ability of the algorithm. The whole dataset is split into two disjoint sets Straen and Spatid. where the first one used for learning and the latter for quality estimation.
The final result of this procedure is often highly dependent on the particular train-validation split and, therefore, quality estimation can be very noisy. To tackle this issue, validation (Stone 1974) method: split the data S into subsets of approximately equal size, or
cross-
Sk) folds, (S1, .... Sx) s.t. S = L S. and perform k rounds training-evaluation cycle using ;=1
S- S/S; as the training set and S; as the validation data for each i E 21,2,..., k). Then the estimated quality is calculated as the mean value of qualities on validation sets over all iterations of described procedure.
Another source of bias in the quality estimator is mismatch of target distributions in the training and validation samples. Because the splits in the standard cross-validation procedure are generated randomly the weights of positive samples (in binary classification tasks) in the trained model may differ from the data on which quality control is performed. To avoid this effect stratified sampling scheme (preserving the proportions of the target) is usually applied.
RELATED WORK
3.1
EARLY STOPPING
Early stopping is a task of controlling the learning process and interrupting it to avoid unnecessary boosting steps, which increase complexity of the model and can lead overfitting. Since the num- ber of learning steps is directly connected to the complexity of the model, larger ensemble sizes lead to models of smaller bias but larger variance (bias-variance tradeoff). One of the ideas pro- posed in the literature (Chang et al. 22110), Mayr et al. (2012) is to penalize the complexity of the models, e.g., via AlC-based methods by approximating the ensemble's 's degrees of freedom. Some works use generalization bounds of the algorithm employing VC-dimension (Freund & Schapire (1977), Rademacher complexity (Cortes Wei al. (2017)). These methods do not require separate validation control, but in most cases, not applicable real-wor world tasks since the obtained bounds are distribution -agnostic. Therefore the approximations are very rough.
al. (2019), or in the PAC setting (Yao al. (2007),
Standard approaches of early stopping mentioned most of the well-known implementations of GB utilize the simple "waiting" idea: if the validation quality does not change for some "reasonable" number of iterations, then the training must be stopped (see, e.g., et al.) (216))) It is important to note that this kind of early stopping may be performed simultaneously with the boosting learning
3

---

Under review as a conference paper at ICLR 2022
procedure step-by-step that the training is stopped at the same time when specific criterion is met. Unfortunately, this method has nothing to do with the double- descent problem (Belkin et al. 2019), and the choice of the required number of waiting rounds remains at the researcher discretion based on experience or heuristic assumptions.
3.2 ENSEMBLE PRUNING
Pruning often refers to various techniques for compressing models for efficient storage and inference compexity. Several papers addressed this topic in ensembles, since they usually contain large number of models. For example, some studies address the problem of adaptive online pruning
in Multiple Classifier Systems setting. where classifiers are learned independently like in bagging,
see Cruz et al. (2015) and (Cruz al., 2018) for review; (Oliveira et al., 2017) and (Hernández-)
Lobato et al., 2008) propose an instance wise pruning methods that allows to halt some models at inference time, while in (Soto et al. 2014) both static (training time) and dynamic (inference time) pruning in AdaBoost are investigated. In this paper, consider Gradient Boosting, where crucial regularisation technique is early stopping based on on pruning (e.g. (Fan et al.] 2002)). noticeable that we can get the ensemble with significantly better quality. The latter can be provided by eliminating the flaws of the model obtained due to the greedy learning algorithm.
practice and in other works can that it also have regularizing effect, it is often
The classic work on this task (Margineantu Dietterich, 1997) compared five different pruning methods applied boosting algorithm. In most cases pruned models were able to maintain and increase the original quality with a moderate reduction in the size. Most of modern pruning tech- niques based on the fact that similar learners in the ensemble duplicate the information about the dataset, so they can be eliminated from a model sequence (Cavalcanti et al. 2016 Li et al. 2012). There also have been tries formulate ensemble pruning as an optimization problem and apply genetic algorithms (Zhou & Tang 2003) or semi-definite programming (Zhang et al. 2006) to find a solution.
In this paper we follow standard pruning scheme described in (Margineantu & Dietterich, 1997):
shrink the model to the first .M learners, giving the best validation score. But unlike all previous works gradient boosting, instead of universal constant, we strive to select this number adaptively for different regions at training time, taking into account the distribution the training data.
ADAPTIVE EARLY STOPPING
In Section we have described the boosting ensemble in the form Fn(æ:) = Σ fzr) where B is the total number of models in the ensemble. When we apply k-fold cross cross-validation scheme to determine the optimal number M of addends, we get i different B-sized models (F 1/
(x(()) = Σ (x),
learned by training sets {S-
The j-th valss-aaiiatiion step provides quality estimator L, ....,,(6) - obtained by ap- plying all the prefixes of the model F& to validation set Sy. In other words.
(
1
Σ
r. (F(((()))))
S
(m.
where Fg Eim af?. The final estimator I - 2o2 2, , further used to define estimated value of M as AM : arg min 16) The model shrinked to the first M iterations provides an estimator with
18i5B
the test quality close to min ((a)) ((F (2), But the problem is that the desired estimator
M
should be selected with the goal be an approximation P mi (atp:/mminnLFMMM. (F) v)], due to an
obvious inequality:
4

---

Under review as a conference paper at ICLR 2022
E(m min(L(Fa((())) y)1 1 min B M
(3)
This simple mathematical fact convinces us that the existing pruning scheme is being used ineffec- tively. Adaptive selection of numbers for specific examples can achieve better quality by eliminating the theoretical gap given by inequality 3 In the following sections, we describe possible approaches to adaptive iteration count selection and evaluation of its effect.
4.1 MAIN IDEA
Suppose the input space is divided into C' disjoint regions (D1, D2.... Dc) in such way that all samples in D; are close each other in some sense (they follow the same latent distribution or geometry). Note that this partition is unrelated to the split induced by cross-validation since the latter split is done randomly and there no reason expect closeness of samples inside a single fold. We assume that (D1, D2,... .... De) is a clustering in the sense that data points of the same cluster D; behave similarly during the procedure of training an ensemble. particular, the optimal number of boosting iterations M, estimated for D, may differ lot from the one estimated for Dj. Therefore, by analogy with the inequality 3 we can conclude that ensemble size selection based on partition D, where the size is chosen individually for each cluster D,, can have better quality compared one "universal" common size:
Ep min[L(EM(()))).... S ED,-D min E[L (x),,)) S min (P(L(FM(())))) M
M
Setting C' = may achieve the theoretical lower bound the left-hand side of Equation 4 How- ever, the size M of the ensemble will be optimized based on the empirical estimation the loss, and the growth in C' is accompanied by the growth of the variance of this estimation for each region D;. So the number of regions should be selected reasonably (we discuss further in the text).
The upper-level training algorithm consists of 4 steps: 1) Cross-validatee training of k models; 2) Distributed- based partition (D,, D22 ..., Pc) of the sample space; 3) Selecting optimal number of iterations (M₁ M2, .... Mc) for each region obtained on the step 2; 4) Retraining the model on the whole training data. The formal description presented in the Algorithm
The framework described above has two additional byperaarameters: number of clusters C' and the minimal size of cluster (optional), both can be tuned. Section (44,, we describe tuning approach, which makes minor contribution to the total computational cost comparing to the ensemble training as our tuning method does not require any retraining.
Algorithm 1 Adaptive stopping procedure
Input: S = (X(.y
folds +- S2,, ...., Sx) + CuSplit(k, ev Predicttions Cu (olddd)ct(oolds)
partition t (Di, D2...., ) & Get GetPariition(S)
DestimaateBesttterattiiee Po prredictiions,prttiti final M odel + Train X, partition, best festlterations)
return Minal
4.2 UNSUPERVISED PARTITION
As it was mentioned in Section 4.1 the partition should reflect the internal structure of the data to be sophisticated enough to select a proper number models. Let us use a reasonable assumption that observations that are close in the feature space also close in their properties. Then can use one of clusterization algorithms (e.g.. KMeans (Looyd 1982), EM (Dempster et al. 1977). agglomerative method (Sibson 1973 get data partition (function Partition in Algorithm]
is essential to preserve the initial geometry of the input space since most of the modern implemen- tations of Gradient Boosting Decision Tree (Breiman al. 2017) base learner. Decision
5

---

Under review as a conference paper at ICLR 2022
Tree constructs thecewise-constane approximations at each step, and it is more likely for close in- stances to get into the same leaves during training and inference, so they tend to fit equally. The unsupervised partition method allows controlling the number of partition regions and their sizes via setting the desired number of clusters and minimal samples count in each cluster.
This method being applied real data exhibits several disadvantages. First, clustering does not work well with data in which non-numeric categorical features are present. Numeric encoding of high- cardinality categorical features leads to sparse input space and dramatically affects clusterization's capacity. Second, unsupervised partition does not consider the labels of the data points, although they may contain valuable information about the required number of boosting steps. Last, some advanced clusterization algorithms require high computational costs what can become bottleneck when training a model.
4.3 TREE-BASED PARTITION
To avoid issues described in the previous paragraph, the partition unit (function GetPartition in Algorithm[] [ should be scalable, interpretable in terms of built subspaces, and tolerant to heteroge- neous feature input. We find the Decision Tree model to be suitable candidate since satisfies all the listed properties: training algorithm is parallelizable and not memory consuming (Sharp) 2008). cluster manifolds are similar to the ones built by base learners, there are efficient categorical feature supporting methods (Prokhorenkova et al. 2017).
The partition procedure boils down training a single decision tree on the initial training samples and targets. Then, we denote each leaf as separate cluster of the data forming the partition. Since the tree learning process utilizes both geometry of feature space and target distribution in leaves to split the data, this method is encouraged to find the regions similar by feature representation and label. In other words, uses available information about the data.
This partition tree may be trained separately from the primary boosting model as well as be the first booster in the ensemble. The latter means that this step does not affect the training time all. However, since Gradient Boosting usually consists of hundreds and thousands of trees, the effect on time costs using a separate partition model is negligible.
The number of clusters and cluster sizes can be controlled via setting an appropriate number of leaves in the tree and minimal Ieaf size.
4.4 VALIDATION PROTOCOL
is still an open question how select the values Mi..., Mc for each cluster (function Estimate Bww.eeeeetttttonn in Algorithm|11 I). Also, adopting new options to any machine learning algorithm raises questions on the limits of applicability and the possibility of extending experimen- tal results and theoretical calculations to real problems and data. New hyperparameters, as a rule, make training procedure more complex and increase the tuning time due enlarged hyperparame- ter search space. In this section, we demonstrate that evaluation and tuning of the proposed method require only one model training step and one inference. All the rest of the work can be done just with the help of precalculated trossvvalidated predictions, so it is cheap to determine the optimal parameters and estimate the possible effect on the quality of the final model.
Let us denote D.,, D, S, the set of observations from the j-th fold belonging the cluster D; and n4,j = Dr,ll- Naive approach (Algorithm 2) of evaluation consists of applying cross- vrals-validttion model trained the sample S-j to the validation set Sj for any j. obtaining quality estimators l.z:
Σ (Fg(()).)).
Tid (a.v)ED.,,
The resulting estimator L; for each cluster i a weighted sum of corresponding cluster estimators over all folds:

---

Under review as a conference paper at ICLR 2022
12.
nijj
(1(0)
Σ
n1.
then M, arg min L; and the cross-validation score of cluster i equals min L. The total complexity of the described procedure is OCC(B + k) nB), which is meager compared to the ensemble training complexity, which is at least (nmddB) (Friedman, 2001 (for m binary features and trees of depth d).
Algorithm Best Iteration Selection
procedure ESSTMATTBESS//TERATONNNCCC co eoPredictions, parlition)
for D. + partition do
L
vector of zeros
<- 0 for S, < folds do
D&g + Dj D,
ni.j + Disl
L, L, + Evval Pred(cnPPedicccoons(:::: mis
elementwise vector
n, + n, + n4s
end for
L; + Li/n;
M, < arg min L;
end for return (M: end procedure
Obviously, the quality assessment obtained in the way described above is biased and always gives an optimistic estimate. In particular, it impossible to use this quality estimator to determine an optimal number of clusters, it always monotonically increases with finer clustering. For more accurate assessment of generalization ability, we suggest using the following cross-validation evaluation procedure in Algorithm 3 which does allow target leakage and strong bias. For each fold Sy, we compute an optimal stopping moment for cluster i by averaging evaluation metrics for all observations from cluster that do not belong to fold Sy. More formally, we compute Li,-g as
(6) Edeg Bay 4.
Ejjg Mij
by applying Estimate EstimateBest.terrae BestTterations (Algorithm to all folds except the q-th one (ignoring Sy from folds). After this step, we have (M₁. ..., MM2 estimated on S-q. Then we use S, as a set validating the quality of predicted (M ..., M2). After averaging the obtained results over folds S,, we get a more accurate estimation of the quality of clustering, which is used to select the number and size of clusters and to estimate the possible profit of applying adaptive stopping procedure, all this with minor additional time consumption relative to the training time of the ensemble model. There is still some bias because fold S,, used both to train models applied S-g and estimate the performance of stopping points. However, the desired property of not using the same set for both tuning and evaluating M satisfied and allows to get useful estimations.
5 EXPERIMENTS
In this section, perform numeric experiments, analyze the effectiveness of the proposed frame- work, and validate statements made in Section[4] We take a popular sour-s Gradient Boosting library, CatBoost (CatBoost 2017). It is known for achieving SOTA results large number of

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Evaluation Procedure
procedure EVALUATE(folds, cuPredictions, partition)
for S t folds do
{M k- BstimateeBet. ffods \ Sq. cu Predicttions, partition)
predictions, + cuPredictionss
for D; + pertition do
Shrink(predictionss, N2,, M() end for Ly Enalppredictions) end for (L))
return Mean( (g)) end procedure
Table Datasets
Adult
Amazon
KDD Upselling
Kick
KDD Internet
Click 400K
Higgs
Marketing 45K
Defauit 23
HEPMASS
Kummlees
5UK
73K
840K
Meeature
15
10
231
36
69
12
28
16
25
benchmarks (Bentéjac al., 2021) with the use of default settings and efficient integrated cate- gorical feature handler. We train each model for B = 5000 iterations with the learning rate set in such a way that the cross validated optimal point is close the 2500-th iteration ensure conver- gence of the training proceess. Datasets used in this investigation and their properties are listed in Table [ their links can be found in references. Most of them are taken from the list of benchmarks of the original CatBoost paper (Prokhorenkova et al. 2017) and the proposed tuned hyperparameters from the paper were used.
We hold out 20% from each dataset for the test. The 5-fold stratified cross-validation is utilized determine the optimal stopping moment. We use the standard pruning algorithm as a baseline and compare it with the method proposed in Section 4 The clustering is performed by training a separate non-symmetric decision tree ("Lossguide" training policy) on the train data and initial labels, where each leaf is an individual cluster. To control cluster count and minimal cluster size, we utilize "num_leave" and "min_data_in__ deaf decision tree parameters respectively.
Does it matter to select a different number of iterations for different regions? To address this question, we train boosting and clustering models on the train data, apply the model to the test set and evaluate metrics after each prediction step (iteration). Then compare the universal optimal step number, calculated as the minimum point of the whole test data loss, and adaptive by independently calculating the optimal size for each cluster. The described procedure was carried out 20 times for different train/test splits. If the assumption from Section is false, we would see that step numbers calculated for clusters iteration. Nevertheless, in reality, we face the situation when the best iteration differs from the ones obtained for each cluster. For example, Figure 3 in Appendix (each line is different train/test split) demonstrates evaluation history for the whole dataset and its two clusters with discrepant optimal stops.
not diversified lot and distributed close the general optimal
These observations motivate our research and confirm the inefficiency of the classical approach. Also, it interesting to note that many clusters and instances are well-trained long before the optimal moment is reached. Therefore, subsequent iterations work in vain, wasting time on their training, not to mention that these examples add additional noise to the predictions for the remaining examples. It is also easy to notice that significant part of the clusters has the best iteration value close to the size of the ensemble B. The latter means that there are plenty underfitted data points (B steps is not enough) that can not be caught by the classical method. However, the partitioning proposed in this article allows them to be detected and trained for an additional number of steps.
Does the validation protocol proposed in Section 4.4 have good generalization ability? For this investigation we applied naive validation control, described in Section |4.] and advanced evaluation procedure (briefly in Algorithm 3) every dataset. As see from Figure aand Figure naive
8

---

Under review as a conference paper at ICLR 2022
Table 2: Quality estimation, 0-1 loss / logloss, relative error change
Adult
Amazon
KDD Upselling
Kick
KDD Internet
Baseline
0.1264 / 0,2723
0.0447 70,1400
0.0494 / 701666
0.0496 / 70,2857
0.1004 / 002220
Adaptive pruning
-0.24% -0.24%
-1.37% / -0.53%
-0.20% / -0.10%
+0.11% -0.19%
-2.46% / -0.52%
Click
Higgs
Marketing
Default
HEPMASS
Baseline
0,3617
0.2364 / 0,4810
0,0926 0.37
0.1865 70.4327
0.1258 0,2778
Adaptive pruning
+0.04% -0.03%
-0.14% / -0.14%
-2.27% / 40.71%
-2.50% / -0.07%
-0.17% / -0.16%
validation protocol monotonically decreases with the number of clusters, as it was expected, and it gives no insight about the optimal cluster count and possible improvement compared the baseline. In contrast, the quality estimation produced by the advanced approach is highly correlated with test quality. The quality patterns for test and validation are repeated, and there is an opportunity to make an informed choice of number of clusters and other parameters affecting clustering.
3800
Figure 1: Upsel, validation
Figure 2: Kick, validation
Does the proposed algorithm help to increase the quality of boosting models? In this paragraph, we carry out an extensive search of the best partition in terms of two loss metrics (lower is better): Logloss and 0-1 loss. The number of clusters is tuned according the procedure from Section 4.4 Then we find the optimal iteration count for each cluster and apply the corresponding number of trees (boosters) each test sample (as in Algortithm D The comparison with the baseline is presented in the Table 2 The results show the superiority of the proposed technique over the classic early stopping on most settings. The improvements test with p value < 0.001, except for datasets Click and Kick. From this, we can conclude that modern Gradient Boosting implementations do not use the full power of the models, limiting themselves to the shared stopping moment for all examples. At the same time, the personalized selection of this parameter allows significant improvements in the algorithm's performance. paper, we select the optimal number of clusters under the assumption of using separate clustering tree. However, at the same time, we firmly believe that the optimal construction of the clusters themselves (for example, taking into account the learning history of the instance) can bring even greater success.
significant according to Wilcoxon signed-rank
this
6 CONCLUSION AND FUTURE WORK
In this paper, we discovered problem of ensemble pruning previously uncovered in the literature. We discussed possible problems that the simultaneous stopping rule brings the modern boosting models and proposed a cluster-based framework of early stopping that can be directly applied to any implementation of Gradient Boosting (and possibly other ensemble methods) without harming its quality and training/inference time. We proposed evaluation protocol for our method, so it is sim- ple and at the same time computationally cheap to determine whether the adaptive stopping works well for any particular data. Our experiments with the well-known implementation of boosting demonstrate the validity of the assumptions and conclusions made in the paper and great potential for applications and further research since this work still uncovers many problems.

---

Under review as a conference paper at ICLR 2022
REFERENCES
UCT KDD Archive. Kdd internet dataset. https://koo ics. .uc htt.suuc..eeb//aaaaaassss internet intemnet_wsaee/nteeeeettt usage/internet wwwgua htmll 1998.
Ismail Babajide Mustapha and Faisal Saced. Bioactive molecule prediction using extreme gradient boosting. Molecules, 21(8):983, 2016.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical blas-vrriane trade-off. Proceedings of the National Academy of Sciences, 166322:15844--15855 2019.
Candice Bentéjac, Anna Csörgö, and Gonzalo Martinez-Muñoz. A comparative analysis of gradient boosting algorithms. Artificial Intelligence Review, 54(3):137-1167,, 2021.
Lco Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone. Classification and regression trees. Routledge, 2017.
CatBoost. Catboost
2017.
George DC Cavalcanti, Luiz Oliveira, Thiago JM Moura, and Guilherme V Carvalho. Combining diversity measures for ensemble pruning. Pattern Recognition Letters, 74:38 2016.
Yuan-Chin Ivan Chang, Yufen Huang, and Yu-Pai Huang. Early stopping 12boosting. Computa- fional Statisties & Data Analysis, 54(10))2003-2211, 2010.
Olivier Chapelle and Yi Chang- Yahoo! learning rank challenge overview. In Proceedings of the learning to rank challenge, pp. 1-24. PMLR, 2011.
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, pp. 785-794, 2016.
Chen Cheng, Fen Xia, Tong Zhang, Irwin King, and Michael R Lyu. Gradient boosting factorization machines. In Proceedings of the 8th ACM Conference on Recommender systems, pp. 265 272, 2014.
Cliff Click, Michal Malohlava, Arno Candel, Hank Roark, and Viraj Parmar. Gradient boosting machine with h2o. H20. ai, 11:12, 2016.
Corinna Cortes, Mchryar Mohri, and Dmitry Storcheus. Regularized gradient boosting. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL hhttps::/prooeeddingg weweeeddiinnnnnnneineeeeeee neurips cttppp..cc//apee//////1eee Paap:///6......aaaaaaaa..a.... Paper.pds
R. M. Cruz, R. Sabourin, G. D. Cavalcanti, and T. I. Ren. Meta-des: A dynamic ensemble selection framework using meta-learning Pattern Recognition, 48: 18:1955-1935. 2015.
Rafael MO Cruz, Robert Sabourin, and George DC Cavalcanti. Dynamic classifier selection: Recent advances and perspectives. Information Fusion, 41:195 2018.
KDD Cup. Kdd upselling dataset.
http:// http://ww..kd..orr//dddouuyyvp
kdd-cup-2200 /aata 2009.
KDD) Cup. Click prediction dataset.
http://www..ddd.orgg/dd-----gg
kdd fold-cup-i 2012- 22, 2012.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series (Methodological), 39(1): 1-22, 1977.
Lei Deng, Juan Pan, Xiaojie Xu, Wenyi Yang, Chuyao Liu, and Hui Liu. Pdrigb: precise dna- binding residue prediction using a light gradient boosting machine. BMC bioinformatics, 19(19): 135-145, 2018.
10

---

Under review as a conference paper at ICLR 2022
Wei Fan, Fang Chu, Haixun Wang, and Philip S Yu. Pruming and dynamic scheduling of cost- sensitive ensembles. In AAAI/AAA,, pp.
Yoav Freund and Robert E Schapire. A decision-theoree generalization of on-line learning
and an application to boosting. Journal of Computer and System Sciences, 15(1):119-139 1997. ISSN 0022-0000. doi:
19t. 1504. URL https: / www.
sciencedirect. ott.a//ccc.....oa.........././/d
Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Jerome H Friedman. Stochastic gradient boosting. Computational statistics & data analysis, 38(4): 367-378, 2002.
Daniel Hernández-Lobatte Gonzalo Martinez-Munoo and Alberto Suárez. Statistical instance- based pruning in ensembles of independent classifiers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(2):64-336, 2008.
Bulat Ibragimov and Gleb Gusev. Minimal variance sampling in stochastic gradient boosting. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp- 15087-15097, 2019.
Kaggle. Kick prediction dataset.
httpgs//ww..kaggll..o//////ooote
2012.
Kaggle.
Amazon
dataset.
http://ww.kk.t http:://www.kaggle..
amazzon-emplooye--cccs----alalla
2013.
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: highly efficient gradient boosting decision tree. Advances neural information processing systems, 30:3146-3154, 2017.
Ronny Kohavi and Barry Becker.
Adult.
httpss:/arcchive..es....ll edd.mm/m.eddm
Batasets/Adull
Erin LeDell and Sebastien Poirier.
H2o automl: Scalable automatic machine learning. In Proceed- ings of the AutoML Workshop at ICML, volume 2020, 2020.
Nan Li, Yang Yu, and Zhi-Hua Zhou. Diversity regularized ensemble pruning. In Joint European conference on machine learning and knowledge discovery databases, pp. 330-345. Springer, 2012.
Ping Li, Qiang Wu, and Christopher Burges. Mcrank: Learning to rank using multiple classification and gradient boosting. Advances in neural information processing systems, 20:897-904, 2007.
Xiaoliang Ling, Weiwei Deng, Chen Gu, Hucheng Zhou, Cui Li, and Feng Sun. Model ensemble for click prediction in bing search ads. In Proceedings of the 26th International Conference on World Wide Web Companion, pp. 689-698, 2017.
Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982. doi: 10. 10.1109/TT..1982.105566
Dragos Margineantu and Thomas Dietterich. Pruning adaptive boosting. ICML., volume 97, pp. 211-218. Citeseer, 1997.
Andreas Mayr, Benjamin Hofner, and Matthias Schmid. The importance of knowing when to stop. Methods of Information in Medicine, 51 (02): 2012.
Dayvid VR Oliveira, George DC Cavalcanti, and Robert Sabourin. Online pruning of base classifiers for dynamic ensemble selection. Pattern Recognition, 72:44-58, 2017.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features. arXiv preprint 1rXiv:1706.099) 2017.
11

---

Under review as a conference paper at ICLR 2022
Toby Sharp.
Implementing decision trees and forests on gpu. In European conference computer vision, pp. 595-608. Springer, 2008.
Robin Sibson. Slink: an optimally efficient algorithm for the single-link cluster method. The com- puter journal, 16(1):30-34, 1973.
Víctor Soto, Sergio Garcia-Moratille Gonzalo Martinez-Muñoz, Daniel Hemández-Lobato and Alberto Suárez. A double pruning scheme for boosting ensembles. IEEE transactions on cyber- netics, (11))2226 2695,, 2014.
Mervyn Stone. Cross- vallstyali choice and assessment of statistical predictions. Journal of the royal statistical society: Series B (Methodological), 36(2):111-133, 1974.
Samir Touzani, Jessica Granderson, and Samuel Fernandes. Gradient boosting machine for mod- cling the energy consumption of commercial buildings. Energy and Buildings, 158:1533-1543, 2018.
Ilya Trofimov, Anna Kornetova, and Valery Topinskiy. Using boosted trees for click-through rate prediction for sponsored search. In In Proceedings of the Sixth International Workshop Data Mining for Online Advertising and Internet Economy, pp. 1-6, 2012.
Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boost- ing algorithms: A general analysis with localized complexities.
In I. Guyon, U. V. Luxburg, S. Bengio, Н. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL httpss//pprcceedass..eerre httppsccc/ppppee https/ccc/pper/1///eeeee pdf
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. early stopping in gradient descent learn- ing. Constructive Approximation, 26:289-3155 08 2007. doi: 10. 10.1007/s00365-006 006-0663-.--
Yanru Zhang and Ali Haghani. A gradient boosting method to improve travel time prediction. Transportation Research Part C: Emerging Technologies, 58:308-324 2015.
Yi Zhang, Samuel Burer, W Nick Street, Kristin P Bennett, and Emilio Herrnddee.rnnneez.. Ensem- ble pruning via semi-definite programming. Journal of machine learning research, 7(7), 2006.
Zhi-Hua Zhou and Wei Tang. Selective ensemble of decision trees. In International workshop on rough sets, fuzzy sets, data mining, and granular-soft computing, pp. 476-483, Springer, 2003.
APPENDIX
Figure 3: Click, evaluation history. Blue lines indicate runs for different train/test splits, red lines are averages over all runs. Dots specify the minimum.
12


Reviews:
[{"review_id": "m2vRCb-DfW", "reviewer": "Reviewer_EFwa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Adapting the ensemble size in an instance-wise fashion is an interesting problem. It is not new however, unlike what is claimed in the paper. This is addressed at least in these papers:\n\n[1] Hernández-Lobato D, Martínez-Muñoz G, Suárez A. Statistical instance-based pruning in ensembles of independent classifiers. IEEE Trans Pattern Anal Mach Intell. 2009 Feb;31(2):364-9.\n[2]  Dayvid V.R. Oliveira, George D.C. Cavalcanti, Robert Sabourin, Online pruning of base classifiers for Dynamic Ensemble Selection, Pattern Recognition, Volume 72, 2017.\n[3] V. Soto, S. García-Moratilla, G. Martínez-Muñoz, D. Hernández-Lobato and A. Suárez, \"A Double Pruning Scheme for Boosting Ensembles,\" in IEEE Transactions on Cybernetics, vol. 44, no. 12, pp. 2682-2695, Dec. 2014, doi: 10.1109/TCYB.2014.2313638.\n[4] Rafael M.O. Cruz, Robert Sabourin, George D.C. Cavalcanti, Dynamic classifier selection: Recent advances and perspectives, Information Fusion, Volume 41, 2018, Pages 195-216.\n\nThe method proposed in the present paper, based on clustering and cross-validation, seems however novel and significantly different from these works, which perform pruning in an online way, i.e. when a prediction needs to be done. In addition, the motivation of most of these works is also to reduce memory and computing times more than improving accuracy. I think the related work discussion should nevertheless includes these approaches.\n\nThe proposed method is very straightforward. It makes sense overall but I don't totally buy some of the arguments that are given in Section 4 to motivate it:\n- First, the discussion focuses only on the impact of pruning on predictive performance. While pruning can be very useful to reduce storage requirement or computing times at inference (and this is angle adapted in, e.g., [3] above), I'm not sure that it is that useful for improving predictive performance. Boosting has been shown to be quite robust with respect to the ensemble size (if the learning rate is small enough) and actually, experiments in Figure 1 and 2 confirm this fact, since most error curves are monotonically decreasing (I see only one curve that really significantly increases at some point). So, I was not expecting a priori a huge improvement in terms of predictive performance. \n- Second, some statements to motivate the idea of clustering are not really supported either by a theoretical or an empirical analysis (although I agree that they make sense intuitively). If you want to show that \"It is essential to preserve the initial geometry\" and to exploit the labels at the clustering stage, then you should provide experiments to show that not doing so is indeed detrimental (by using e.g. unsupervised clustering). \n- Third, the fact that the clustering is carried out without consideration of the boosting model makes the approach also suboptimal by design. There is no guarantee that the clustering will be optimal when it comes to tune the ensemble size in each cluster.\n\nThe idea of the cross-validation approach based on a single model (per fold) is sound and very relevant to reduce the computational cost of the approach. Note however that the cost is still important with respect to no pruning at all since it requires to grow k+1 boosting ensembles instead of 1. But I agree that there is a negligible overhead with respect to tuning globally the ensemble size.\n\nThe empirical validation is carried out correctly from a statistical point of view. I find however that the authors overemphasize the significance of the improvement they obtain with their approach. Looking at Table 2, their local pruning technique brings an improvement of less than 1% in terms of 0-1 loss on four problems out of six and on the other two problems, the difference remains very small. I'm not sure that such level of improvement is actually worth the effort if one is only interested in predictive performance. These results are also obtained with a single dataset split (if I understand correctly). Given how small the difference is, I think it would have been important to repeat the experiment several times with different splits to get standard deviations and maybe also to carry out a statistical test to check whether the improvements are statistically significant.\n\nI don't think either that the experiments provide a satisfactory answer to the first two questions asked in Section 5. As already discussed above, to me, Figures 1 and 2 show that one can not expect strong benefit from the clustering since most error curves are monotonically decreasing. Part of the important diversity in the optimal size in the clusters seems to be due to the fact that long flat regions are observed which lead to an instable position of the optimum. I would have like also a more systematic and quantitative experiment on all datasets to answer the second question about the relevance of the validation protocol. Why not compare the optimum found by this protocol with the \"theoretical\" optimum found on the test set?\n\nFinally, I'm surprised that the authors don't talk at all about the benefit of pruning on computing times at inference. To me, this is one of the main motivation for using pruning in the context of ensembles. I would be interested to know how global and cluster-based pruning compare from this point of view.\n\nMinor comments:\n- In 3.1, the following sentence is unclear: \"This method has nothing to do with the double-descent problem\". What do you mean?\n- It's not clear how you fix the number of leaves in a decision tree? In the standard algorithm, the order in which the nodes are expanded is arbitrary. Do you apply some best-first strategy? Which one?\n- If I understand correctly the baseline in Table 2 is the standard globally pruned model. If so, I would like to see also the performance of a unpruned ensemble.\n- Only one setting of the boosting algorithm is explored (B=5000, a learning rate of 0.02 and default parameters for the CatBoost model). Yet, one expects that these parameters will have an impact on the performance (it's obvious for B at least). I think that more combinations should be explored to make the conclusions more general.\n- Looking at Figure 2, there are more error curves above the average curve than below, which suggest that clusters are potentially unbalanced. It would be interesting to report the size of these clusters.", "summary_of_the_paper": "This paper proposes to tune the number of models in a boosting ensemble in an instance-wise fashion. The idea is to first cluster the samples using a decision tree and then to tune the size of the ensemble independently for each cluster, instead of doing it globally for all instances. An efficient two-level cross-validation procedure is designed to tune both the number of terms in each cluster and the number of clusters. Experiments are conducted on 6 large-scale problems that show that local pruning brings some improvement with respect to the more standard global pruning technique.\n", "summary_of_the_review": "The paper is well written and the proposed method makes sense and is original. But it lacks a bit of theoretical motivation and I'm not convinced of its practical relevance, given the very marginal improvements observed in the experiments.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dkM81nubzAw", "reviewer": "Reviewer_xGqg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Strong points:**\n- Very simple method, with easy implementation (making its reproduction straightforward);\n- Elegant idea for incorporating the approach within a cross-validation procedure.\n- Strong results (albeit in a short amount of datasets).\n\n**Weak points:**\n- Very limited experimental analysis. For addressing that I would recommend:\n    - You should try it on dozens of datasets, given that the method is allegedly very fast.\n    - You should compare your approach with several methods for hyperparameter optimization, not only with the naive CV procedure. I am curious to see whether a more sophisticated hyperparameter tuning approach can outperform you simple approach, and if so, with which efficiency it would do it.\n    - You should employ statistical tests for better assessing the statistical significance of results. In particular, there are several nonparametric tests that can help you pointing out significant differences, and also post-hoc methods for pointing out pairwise differences for the case of multiple methods being executed over multiple datasets.\n\n**Questions:**\n- You say you define the number of clusters (leaves in the decision tree) according to the procedure described in Section 4.4. It is not clear to me which procedure is that. Do you mean running Alg. (3) several times with distinct number of clusters, and using the one with the best results? How exactly did you do that? Since defining the number of leaves in decision-tree induction is not straightforward (you need to try and control that via tree height or minimum number of instances per leaf), I would guess that this step is a little bit more complicated than you make it appear (and also, the increased computational cost of running your entire procedure - which has a non-negligible cost itself - multiple times). I think that is a vital part of the method whose discussion is not done at all in the paper.\n- The \"shrink\" method in Alg. (3) is not detailed at all, so I am assuming it means getting the predictions of the full model executed over fold $S_q$ and \"cutting off\" the results that use more than $M_i^q$ models, would that be correct? I am sorry for the confusion, but that is not totally clear to me.\n- In inference (test) time, I would assume you need to see in which cluster the new instance falls on, and then using the number of models defined for that cluster, is that also correct? I ask because there is no mention on that at all in the paper.", "summary_of_the_paper": "The paper proposes a novel method to set the optimal ensemble size in gradient boosting. In particular, the authors propose an adaptive strategy that sets distinct ensemble sizes for different regions of the input space. For that, they propose dividing the input space in coherent regions (whose instances are similar both in terms of features and labels) and estimating the optimal ensemble size within those regions. For clustering data, they propose using a decision tree induced from the entire training set, and the leaves of the trees are the clusters that comprise the data partition.\nThey show the results of both a biased and a less-biased estimator for finding out the optimal ensemble size per region, and they compare their findings with the traditional strategy of simply pruning the ensembles based on a single optimal number of learners estimated from a cross-validation procedure. Results in 6 public datasets show that in at least 4 of those datasets the method seems to provide better results.", "summary_of_the_review": "Paper with a nice, elegant, and very simple idea for adaptively generating different number of ensemble sizes throughout the input space, in an attempt to generating better results.\nThe weak point is that the experimental analysis is not up to the standards that one would expect here, as I would have expected the method to be tested over dozens of datasets, with a proper analysis against other hyperparameter optimization approaches, and statistical tests to validate the significance of the results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4XG5rKQHqaa", "reviewer": "Reviewer_meXP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The idea of partitioning the input space and using a varying number of models in the ensemble makes a lot of sense to me and is novel, to the best of my knowledge. Gradient boosting and similar techniques do indeed remain widely used and very competitive for small-to-medium dimension tabular data, so the practical significance of the method is clear. Although some minor edits are needed, the presentation of the technique is clear for the most part.  \n\nMy main concern is that the number of benchmark datasets is smaller than I would have liked. Given the option nowadays to rent computing power temporarily via the cloud, it's not unreasonable to expect much more than 6 benchmarks to be tested for a method like this. For instance, I once refereed a paper for another conference which tested their method on 40 benchmarks- and (although I liked the paper), the paper got rejected ! I am not saying 40 is required, but maybe 12 or 15 benchmarks would make me more comfortable with the results than just 6.\n\nWith that said, the method is elegant and intuitive and widely applicable, so I don't mind at all if this paper is accepted. The small number of benchmarks is the reason I can only give it a 6.\n\nOne major suggested edit: the author use the term 'object' in a non-standard way, to refer to what are normally referred to as examples, ( or data points, instances, observations, etc), i.e. the labelled (x,y) pairs used to train a supervised learning model. I suggest choosing a term other than 'objects'.\n\nOne minor complaint: on page 6, it is claimed that cluster surfaces are hard to validate. In fact, clustering can be evaluated out of sample much in the same way as supervised learning, by looking e.g. at likelihood on a holdout sample, so as to choose an optimal number of mixtures in a mixture of gaussians. It is also possible to construct objective functions for something like k-means which trade off K with distance of each data point to its cluster mean. Nonetheless, it does make sense to me to partition with a decision tree, so I am not bothered by this misstatement much.\n\nA few other suggested edits:\n\nPage 3 The early stopping -> early stopping\n\nPage 8 Does the validation protocol proposed in Section 4.4 has good generalization ability? Has -> have", "summary_of_the_paper": "An enhancement of the popular gradient boosting method is presented wherein the input space is subdivided into regions and the cross-validated optimal number of trees to include in the ensemble is chosen on a per-region basis rather than using a single global number of trees for the entire input space. Consistently superior performance relative to standard gradient boosting across 6 benchmark datasets is reported.", "summary_of_the_review": "A method for partitioning the input space for a gradient boosting algorithm and choosing a different number of trees to be included in the ensemble in a partition-dependent way is presented. Improvements on 6 benchmark datasets relative to standard gradient boosting are reported. The method is intuitive and elegant but the number of benchmark datasets is not as large as it could be, and for that reason, the paper gets a 6 (marginal accept).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers agree that the paper contains interesting ideas and the method is elegant, it unfortunately does not meet the bar for acceptance. I strongly encourage the authors to revise their paper, in particular using the numerous comments made throughout the discussion phase; for example:

* It is important that the authors polish their work, in particular for the updates provided (e.g. Figure 3, see EFwa)

* Reviewers pointed the lack of updates on important claims by the authors (in particular the claim regarding clustering vs decision trees, see EFwa, the comments on the lack of diverse datasets, see meXP, )

* Some answers might have gained in clarity, such as the reply to EFwa on the application and conclusions following Wilcoxon sign test.
Decision: Reject