Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

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.

What 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.,

Tsoumakas, 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.

Hsu, Daniel J., Sham M. Kakade, John Langford, and Tong Zhang. "Multi-label prediction via compressed sensing." Advances in neural information processing systems 22 (2009).

Joly, 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.

Kapoor, A., Viswanathan, R., & Jain, P. (2012). Multilabel classification using bayesian compressed sensing. Advances in neural information processing systems, 25.

Cissé, 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.

Wicker, 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.

The 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.

Typos:

There is a broken reference on Line 110.

"on the most multiclass datasets"

"it achieve"

"it is order of magnitude faster"
questions: N/A
limitations: There does not seem to be an explicit discussion of limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Pros:

[P1]: The paper is well written and organized in terms of clarity.

[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).

Cons:

[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])

[C2]: A related discussion connecting to deep learning method would be better.

[C3]: Some typo like line 110/257.


[1] Deep Neural Networks and Tabular Data: A Survey, https://arxiv.org/abs/2110.01889

[2]VIME: Extending the Success of Self- and Semi-supervised Learning to Tabular Domain https://proceedings.neurips.cc/paper/2020/file/7d97667a3e056acab9aaf653807b4a03-Paper.pdf

[3] TabNet, https://arxiv.org/abs/1908.07442

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.

[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?

limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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). 
The authors approaches are not a substitute for XGBoost, CatBoost or any SOTA GBDT algorithm, but rather can be integrated with any of these solutions. 
Finally, the authors present extensive experiments to validate their solution, showing significant decrease in training time without compromising predictive performance. 
 
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. 

In particular, I believe the strengths of this paper are: 
- Problem that they tackle is relevant
- The solution is built to be used on top of existing SOTA algorithms
- SOTA algorithms are also compared to their solution, showing promising results
- Nice description of the complexity analysis between their solution and having the standard approach (Section 3.4). 
- Nice comparison by running the baselines also on the GPU
- Good and promising results overall. 
- Code available 

A few things to improve that are worth mentioning:
- 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. 
- Table 1: The error metrics reported are after running all algorithms in the GPU right? (same as for Table 2, that its mentioned explicitly). 
- 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? 
- 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). 
- 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) 
questions: The questions are part of the previous section (Strengths and Weaknesses). 
But to summarize them
- Table 1, error metrics reported of running everything on GPU?
- Why in Table 4 SketchBoost Full is taking less training time?
- Why GBDT-MO Sparse, Full and CatBoost (Table 4) are on CPU?
limitations: I don't have anything to add here.
review_title: null

Meta-review: metareview: After rebuttal, the reviewers unanimously agree that the submission should be accepted for publication at NeurIPS. Reviewers were excited about the achieved speed-up.
confidence: Certain
Decision: Accept