Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed a new way of training decision trees, which extends the standard greedy tree fitting algorithms. The main idea is to consider Top-k features for each split, instead of just greedily using the top-1 feature. Theoretically, the authors present a sharp greediness hierarchy theorem that shows that even a Top-(k+1) tree can be much more power full than Top-k. Further, the empirical results also demonstrate the efficacy and efficiency of the proposed algorithm.
strength_and_weaknesses: Strength:

1. The proposed method is a simple and intuitive generalization of the standard tree-fitting algorithms, which naturally covers the optimal tree when $k$ equals the dimension $d$.

2. The new training algorithm is largely amenable to parallelization, despite the exponential increase in computational complexity.

3. The greediness hierarchy theorem demonstrates the power of choices in decision tree learning - even going from $k$ to $k+1$ brings significant improvement in performance.

4. The empirical evaluation also demonstrates the efficacy and efficiency of the proposed algorithm for relatively small $k$.

Questions and weaknesses:

1. One major concern is computational complexity. I'm not fully convinced by the discussion on page 5 about computational complexity. While the original complexity is $2^h$, the proposed algorithm has an additional multiplicative factor of $k^h$. Since this is a multiplicative factor, this is not negligible. The exponential factor is also empirically verified in Fig 4. This is prohibitive for a decent depth - for instance, for h = 10 and k = 3, training one tree in this way is equivalent to training 3^10 ~= 59,000 trees in a greedy way.

2. What is the difference between Theorem 3 and Theorem 4?

3. Scikit-learn is used as a baseline lib for all experiments. However, for tree-fitting algorithms, xgboost or lightgbm seem to be a more common choice and usually deliver better accuracy.

4. In the first paragraph of Section 5, the sentence "For numerical datasets,.... appropriate number of thresholds" is duplicated.
clarity,_quality,_novelty_and_reproducibility: The idea is simple and well-presented. The paper is easy to understand, though there seem to be some duplicated theorem statements and sentences.
summary_of_the_review: This paper presents a simple and intuitive extension of existing tree-fitting algorithms. One major concern is the multiplicative exponential factor in the computational complexity - I'm not fully convinced this is a scalable solution. See details in the weaknesses.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Learning decision trees from data is a simple and rich problem. The classic decision tree learning algorithms use a greedy strategy to select the best feature to evenly split the dataset. In this work, the authors look at k features and select an attribute that achieves maximal accuracy. This recovers the classic strategy for k=1.

They theoretically prove that for certain datasets their top-k algorithm achieves only $1/2+\epsilon$ accuracy whereas top-(k+1) achieves $1-\epsilon$ accuracy.

They also experimentally show that their algorithm betters both the classical top-1 algorithm and also more recent optimization algorithms which uses complicated and non-greedy strategies and hence are time-expensive.
strength_and_weaknesses: strength: the proposed approach is natural and simple. Authors have shown both theoretical and empirical evidence that shows that their algorithm is better.

weakness: the negative result would have been much stronger had they compared their top-(k+1) algorithm against any other algorithm, not just the top-k algorithm.
clarity,_quality,_novelty_and_reproducibility: The paper is clear and well-written. The power of choices, although a known strategy, has been introduced to learning decision trees for the first time. I believe the experiments are simple and can be reproduced.
summary_of_the_review: I prefer to accept the paper considering that they combine a classic algorithm with a classic strategy to give an algorithm for learning decision trees.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers a simple algorithm for learning decision trees with high accuracy. The authors prove that there exists a distribution over instances for which the algorithm with larger depth parameter k+1 outputs a tree with higher accuracy than that produced by the algorithm with depth parameter k. Furthermore, the author provides experimental results showing the advantages of the proposed algorithm. 
strength_and_weaknesses: Strength
- a simple but effective algorithm for learning more accurate trees than the standard greedy algorithms

Weakness
- The proofs do not seem accurate enough 
- implications of the theoretical results

The algorithm is an extension of the standard greedy decision tree algorithms such as ID3. The idea of using top-K features and finding an optimal tree is simple but effective. I agree with the statement that accurate small trees are important and the exponential time complexity is not high when the depth parameter is constant. Empirical results look promising as well.

On the other hand, I have serious concerns about the theoretical results of the paper. First, I think the proofs are not accurate enough since it lacks formal discussion, say, how to obtain information from the distribution. I raised some technical points below. 

Second, the implications of the theorems are neither clear nor meaningful. Roughly, the main theorems say that there is a good situation where the algorithm with a large depth parameter is better than that with a smaller depth parameter. This does not imply the larger parameter is always better. Contrarily, when given a small sample, larger trees could overfit and smaller trees are better.  



Some technical issues on theoretical proofs
The proofs are not accurate enough in the following reasons.
- In the proofs, the scoring function is not specified. At least, there should be some properties that the function should satisfy in order to make the proofs correct. 
- The topK algorithm takes a sample of labeled instances. But, in the theorems and proofs, it somehow has access to the distribution directly(?). You need to formalize the process, e.g., using an oracle. What can the algorithm obtain from the distribution?
- Sample complexity is not discussed. What is the sample complexity of the algorithm? This is related to the previous issue. In general, learning from a larger hypothesis class needs a larger sample, which is well-known in the statistical learning theory (e.g., PAC bound or VC-based generalization bounds). 
- The search space \calT need a formal definition. The definition should be defined without using the algorithm.
clarity,_quality,_novelty_and_reproducibility: Except for proofs, the paper is easy to follow. The algorithm seems novel. I think the proofs need a significant revision.
summary_of_the_review: The paper proposes a simple but effective decision tree algorithm. Empirical results are promising, showing advantages over previous work. However, theoretical proofs are not accurate enough and I feel the technical contribution is not strong enough unless the theoretical parts are fixed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a simple generalization of greedy algorithms for learning decision trees. At a given iteration, instead of growing the tree using the most promising (top-1) feature, the proposed algorithm uses the top-k features and builds a subtree for each of them.
The paper highlights that, even though the time complexity of the top-k algorithm is polynomial in $k$, the algorithm can be easily parallelized to obtain running times of the same order as top-1 algorithms' ones (unlike optimal tree methods).

Unsurprisingly, an empirical analysis shows that using a $k \in [2, 4]$ generally improves over the test accuracy of top-1 greedy algorithms (although it is more prone to overfitting) while having a time complexity (both in number of samples and of features) much smaller than optimal tree methods.
The paper further shows that there exist data distributions on which the test accuracy of the top-K algorithm is provably better than the test accuracy (Theorem 1) when using top-(K-1) for the same depth $h$ or (Theorem 2) when using top-k with $k < K$ and allowing for deeper trees (up to $h + K - k - 1$ depth) or (Theorem 3) when using top-k with $k \leq K - h$ for same depth budget $h$.
strength_and_weaknesses: ## Strengths
### Clarity. 
The paper is generally well-written: the contributions are clearly stated, the empirical analysis is described with enough level of detail and intuitions are provided for the theoretical results.

### Significance and impact. 
Partly due to its simplicity, the proposed generalization of standard greedy approaches is likely to be adopted in future works, both in the machine learning and the application-oriented communities.

## Weaknesses
### Mathematical rigour.
1. The notation, definitions and theoretical results are split over different sections in the main paper and the appendix. It makes it harder to understand the proofs as the reader has to jump forward and backward just to be able to follow them. More precisely, the theorems are stated in Section 1.1.2, the proofs and definitions are partially reported in Section 4.1 and completed in the appendix. It would really help that at least in the appendix all the elements needed to understand the theorems and the proofs are reported together. 

2. Incorrect or unclear results: 

- Lemma 3.2. Shouldn't it be a max over the trees and not a min?

- Fact B.2, hence the following results too, stands only for $h \leq k$.

- In proof of Lemma 4.2, the derivation of the two expectations should be reported.

- In proof of Lemma 4.4, why is Pr[T(x) = Tribes(x)| x follows path] is upper bounded by Exp[Tribes(x)|?

3. Missing notation: $x_i$ in Figure 1 (in particular its domain), $x, y, S$ in Definition 2. 

### Literature.
The paper never discusses the rich literature on learning optimal soft decision trees with gradient-based methods, e.g. [1], [2]. This literature is very relevant to the proposed work, as it shares the goal of learning decision trees with a scalability close to greedy algorithms and an accuracy close to optimal tree methods.
How does the proposed method compare to this literature?

### Empirical analysis.
1. In page 7, it is said that "We build decision trees corresponding to both gini and entropy as the impurity measure H, and report numbers for whichever of the two performed better on the test set". This is ambiguous and does not seem a rigorous way of comparing methods. Does this mean that within the same figure or subfigure the methods are optimized with different impurity scores? How much the choice of impurity score affect the performance gap?

2. The comparison with the baselines is carried out in terms of accuracy and running times independently. To have a better idea of the trade-off between the two, it would be valuable to plot these two metrics together and highlight in which regimes (in terms of k and depth) it is possible to improve accuracy without incurring into prohibitive running times.

3. Figure 4 is commented in the main paper but reported in the appendix. For the paper's main text to be self-contained, the figure and its description should be reported together.

### (minor) Interpretability. 
The theoretical results provide some intuition on how to choose $k$ and $h$, in particular so that learning a top-k tree would allow to reduce the depth of the tree without degrading accuracy. It is not clear however how this analysis relates to the interpretability of the decisions, which is one of the (if not the) principal reasons for learning decision tree-based models. My question is: does using $k > 1$ results in reducing the interpretability of the model, as the overall number of decision splits increases? It would be valuable to briefly discuss this point, showing how this affects the interpretability of the decision for a point and for a class.

### (minor) Typos

- Section 2: understanding the performances -> understanding of the performance

- Section 4 $f_{h, k}$ definition: in the multicase,  $f_{h, k} = $ -> $f_{h, k}(x) = $

- Page 7, footnote: seeing as -> as

- Page 15, last two lines: which was used to that (missing word)

[1] Ozan Irsoy, Olcay Taner Yildiz, Ethem Alpaydin: Soft decision trees. ICPR 2012

[2] Ryutaro Tanno, Kai Arulkumaran, Daniel C. Alexander, Antonio Criminisi, Aditya V. Nori: Adaptive Neural Trees. ICML 2019
clarity,_quality,_novelty_and_reproducibility: ### Clarity and quality
The paper's contributions, goals and empirical analysis are clearly presented. The presentation of the theoretical results should be improved and two intermediate results should be clarified/rectified, as detailed under "Weaknesses - Mathematical rigour".

### Novelty
The proposed method is a straightforward generalization of standard greedy algorithms, so the novelty is somehow limited.

### Reproducibility
The code for reproducing the experiments has not been submitted. However the pseudo-code of the algorithm is reported in Figure 1, and it would be easy to implement the proposed method.
summary_of_the_review: The paper's contributions are significant and potentially impactful. The theoretical and empirical analyses are sufficient to support the claims of the paper. 
Some work is needed to improve the presentation of the paper, in particular of the theoretical results. I would be happy to increase my score accordingly.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses:  The paper proposes a new way of training decision trees, which extends the standard greedy tree fitting algorithms. The main idea is to consider Top-k features for each split, instead of just greedily using the top-1 feature. A theoretical results is provided that shows that Top-(k+1) can be significantly better than Top-k. Numerical simulations are given, showing the efficacy of the Top-2,3,4 decision trees.

Strengths
- decision trees are key tools for machine learning: having strategies that improve their learning and generalization is key
- the write-up of the paper
- empirical results

Weaknesses
- the authors could state the general optimization problem that decision trees try to solve
- working on the point mentioned just before, if would be nice for the user to call notions that make greedy algorithms to be optimal or almost-optimal (see works on greedy sub modular optimization, on greedy learning on matroid, etc.)
- the incurred computational complexity by the Top-k method could be better described
- there is a lack of clarity in the statement of the results / their proofs.
justification_for_why_not_higher_score: There is a lack of perspective / zoomed-out reflection of the author on the algorithm provided.
There had been unclear statements
justification_for_why_not_lower_score: The algorithm proposed is sound, and the empirical results are compelling.
Decision: Reject