Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, they proposed a MAB application for tree-based learning methods. Finding the best split takes O(n log(n)) time for a fixed feature, where n is the number of training instances. Their proposed algorithm, MABSplit, estimates the best split by drawing n' < n independent examples. MABSplit works as follows;
1. Define the feasible set as the set of pairs of features and thresholds.
2. While the size of the feasible set is greater than 1:
    a. Draw a batch sample from training instances.
    b. Shrink the feasible set.
They evaluated the computational complexity and verified the effectiveness of their algorithm by experiment.
strengths_and_weaknesses: Strength:
- a new application of bandit techniques to decision tree learning


Weakness:
- sone more explanation is necessary for the correctness of the algorithm
questions: - Correctness of algorithm 1 (please see the details at limitations part).
limitations: I have some concerns about the correctness of the paper. Estimating entropy or gini index via sampling can be only done approximately. In particular, the entropy changes significantly at both ends (0 and 1), and the gradient is infinitely large there. So, it would need a careful analysis to employ Hoeffding bounds and others (e.g., case analysis). Furthermore, to ensure the correctness of algorithm 1, it would need an assumption about the gap between gains of the best one and others.
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: In the paper "MABSplit: Faster Forest Training Using Multi-Armed Bandits", a splitting criterion for fitting decision trees is proposed based on multi-armed bandits as to improve training efficiency, i.e., the time to train an entire random forest. To this end tuples of features and thresholds are each considered an arm and pulled for an instance to build histograms. Thereby, a sublinear runtime complexity (wrt. to the number of instances) can be achieved instead of linear runtime.
strengths_and_weaknesses: ## Strengths
The problem addressed by the paper is an important one, especially with sustainability and the climate crisis in mind. Working towards more efficient algorithms reduces energy consumption but also makes the usage of RF even more responsive in the sense that models can be obtained more quickly.

To the best of my knowledge, while there are various works on different split criterions for decision trees, the approach of this paper is novel and presents an original idea.

Overall the paper is well structured and easy to read. However, I cannot induce the schema according to which the tables were colored and there is no explanation on that. Moreover there are still a few grammatical mistakes, e.g., l.22 "is then be aggregated", l.45 + l.241 "O(n) computation" -> computations, l. 112 the sentence is not complete, l.116 "a M" -> an M, l.224 "data point" -> data points. Furthermore sklearn's true name is scikit-learn.

## Weaknesses

While the general idea is quite interesting and the tackled problem is an important one, the paper falls short in terms of the scope of contribution. The theoretical contributions are relatively straightforward and the empirical study is quite limited. Although different variants of random forests are compared, only a single dataset (for a single split) for classification and a single artificial dataset for regression is used to benchmark and compare the proposed method with baselines. While this is already a good indicator that the method works indeed as intended, a more indepth evaluation of the proposed method is required to draw conclusions on a broader scale: How does MABSplit perform across various dataset sizes? For most tabular datasets MNIST already is comparably large, although for way smaller datasets there is not really a need for speeding up random forests. Anyways it would still be important to see how MABSplit compares for such smaller datasets. Then, the authors stated repeatedly that MNIST is only a small dataset. So, the question is how does it compare for datasets larger than MNIST? Does it scale as well as expected? For regression tasks the same arguments hold. Additionally, it is unclear why an artificial dataset was generated instead of using real-world data, e.g., from OpenML?

The result descriptions are quite descriptive without any more indepth explanations. The performance degradation in Table 2 was not addressed at all. How come that the performs degrades that much for ExtraTrees?

questions: * How does MABSplit perform across various datasets?
* Why was only an artificial dataset used for regression?
* What are limitations of MABSplit?
* What are potential drawbacks of MABSplit?
* Why does the performance for ExtraTrees in Table 2 degrade that much?

limitations: Limitations are not discussed in the paper. Thus, it is not clear what the strengths and the weaknesses of the approach are.
review_title: null

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 algorithm considers the selection of decision stumps using bandit algorithms. The decision stumps are used in algorithm such as random forest, extremely randomized forests, or random patches. The proposed method allows for a faster exclusion of candidate stumps that are not looking promising after a smaller number of evaluations (using Gini impurity or entropy).  Theoretical results offer some guarantees on the computational complexity. Empirical evaluation on the MNIST dataset show that the proposed selection technique results in much faster tree algorithms.  

strengths_and_weaknesses: Reducing the set of candidate stumps using statistical measures is natural. I am not aware of previous work published with similar effect, but I would not be surprised if it has been attempted before. The theoretical guarantees seem fairly straightforward.

The empirical results are fairly impressive. It would have been useful to replicate the results on different datasets.

The experiments use reimplemented variants of the baseline algorithms. I understand the authors' argument for this choice, nevertheless, it should be pointed out that the full evaluation of stumps makes the optimizations present in publicly available implementations much easier. These optimization techniques might not be possible (or more difficult) for the selection technique proposed in the paper. Therefore, it would have been useful to provide the walk clock time comparisons with the publicly available implementations as well.  

questions: Framing the proposed method as a bandit algorithm seems a bit misleading, since all candidate stumps are evaluated. There is some connection with the arm elimination, but the differences in the setup should be perhaps better clarified.  

limitations: As mentioned above, the proposed technique might be more difficult to implement/optimize effiently.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper "MABSplit: Faster Forest Training Using Multi-Armed Bandits" proposes to estimate the performance of the splits during DT induction instead of evaluating them exactly. To do so, it views the splitting procedure as a multi-armed bandit problem which enables confidence bounds for each split that in-turn can be used to eliminate unpromising features "early on" by evaluating them only on a small subset of data points.
strengths_and_weaknesses: The paper has a solid theoretical background and a novel algorithmic contribution, but lacks a thorough experimental evaluation. 
- [+] Novel and non-trivial extension of the node-splitting in DTs
- [+] Solid theoretical work
- [+] Solid literature review 
- [-] Experimental evaluation can be extended
- [-] Wording of the paper is sometimes unclear.

# Detailed Review
I  like the idea and find it really interesting. I do not think I came across such a combination of bandit learning and DT induction yet and as such I find it a valuable contribution. While the authors do not explicitly motivate their work, the benefit should be clear to the reader. The related work section is solid, although I was a bit confused that XGBoost/LightGBM/CatBoost are not mentioned explicitly, although they are cited multiple times in the paper [12,24] . Section 2 and the first part of section 3 were also easy to follow in my opinion. Starting with Algorithm 1 it gets a bit troublesome. To me, the runtime of the proposed method is somewhat unclear. The authors give a theorem with the expected runtime, however, there is no worst-case runtime? I think the worst-case runtime is at-least also quadratic which means that for certain use-cases the proposed method is worse than the standard approach implemented in many frameworks (see my question below). Additionally, the  authors refer to a "linear" runtime multiple times in the paper, but I don't know exactly what they mean by this. Last, I find the experimental evaluation weak. It makes perfect sense to compare the algorithmic contribution to a base-line implementation, although implementing MABSplit into Weka or Scikit-learn would certainly improve the paper. However, the method is practically only evaluated on synthetic data and MNSIT. While using synthetic data is very important to isolate certain effects (e.g. the effect of the number and type of features is not discussed at all in the paper), some real-world experiments are also important. Last, and more crucial to me, the authors do not compare their approach against existing methods. More specifically, they do not compare it against the estimations used by Hoeffding's Trees [13,30] or the F-Forest [16] although these seem to be the only to similar methods available. I think a comparison here is urgently required. 

## Things to improve if the paper is rejected
- Please refine what you mean by "linear runtime" throughout the paper. It would probably best to just give some pseudo-code of the exact split induction (with or without binning) to which you compare against. If space allows put that directly in the paper, otherwise use the appendix. 
- Point out the worst-case runtimes and the expected runtime of your method and related work. It should be clear that you win in terms of expected runtime and have better empirical results than the standard that is implemented in Scikit-learn/Weka etc.
- Compare against Hoeffding Trees and/or F-Forest. As you write, these methods are very related so that you cannot ignore them in your evaluation
- Add more (real-world) datasets. Personally, I think its fine to either go for classification or regression to simplify the analysis, but then use more datasets with varying amount of features and feature types. 
questions: 1) You keep referring to a linear runtime for the exact split computation and I think I understand how you mean this, but please clarify the following for me: A very naive solution of finding the exact split is to iterate over all feature / split pairs (of which there are at most $Nm$ where $m$ is the number of features) and then to iterate over all data points to compute the probabilities $p_{L,k}$ and $p_{R,k}$ . A more evolved approach (which is implemented in most frameworks) would first sort the data points in $\mathcal O(dN \log N)$ and then perform two linear scans in which the statistics for the left and the right node are updated. Last, we can perform binning of the feature values into histograms which then requires a linear scan through the data. The exact procedure and runtime depends on the binning method. Assuming one feature ($m=1$) we have:
	1) The very naive approach has $\mathcal O(N^2)$ runtime. 
	2) The standard approach has $\mathcal O(N \log N + 2N) = \mathcal O(N \log N)$ runtime
	3) The binning method has $\mathcal O(N)$ plus some additional overhead for the exact binning method.
	4) You refer to "linear runtime" to the linear scan in binning and not the linear scan in the "standard approach". This is confusing because you basically always talk about binning, but then mention sorting in line 306 (in the conclusion).
2) You claim that MABSplit has a (sub-)linear runtime and I understand your remark under Theorem 1. However, just to clarify: The worst case runtime can still be $\mathcal O(N^2)$ when we have $|\mathcal F| \cdot |\mathcal T_f|  \approx N$, correct? 
limitations: The expected runtime is analysed, but there is no worst-case runtime presented (see my question). Personally, this would improve the paper, but I don't think it absolutely necessary for acceptance.
The experimental evaluation is limited in a sense that they use a simple, non-optimized baseline. However, this is explicitly stated and makes sense in the context of the paper.
review_title: null

Meta-review: metareview: The reviewers agree that from a decision tree induction point of view, this paper provides a solid methodological approach in contrast to prior heuristics-based approaches. They found the author feedback satisfying, specifically, the additional experiments showcase that the proposed method generalizes most likely beyond development datasets.

We ask the authors that in the final version, please make a pass over the paper to incorporate the author-reviewer discussions.
confidence: Certain
Decision: Accept