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 paper proposes a branch-and-bound based approach to obtaining the optimal decision tree. The basic idea is to separate the problem into two stages, the first of which is about structure of tree and the second of which is about variables that specifies the allocation and cost of samples. 
strengths_and_weaknesses: - The basic idea would be reasonable and the empirical results suggest efficiency of the proposed method.

- In abstract: 

> find global optimal solutions with a small optimality gap for datasets with over 245,000 samples.

I feel that this statement is seemingly a bit exaggerated too much because the result is obtained by 1000 cores (though in the introduction, it is described). 

- If I correctly understand, the entire general framework (two stage decomposition with branch-and-bound) has been already studies in Cao and Zavala 2019, and Hua et al., 2021. There exist technical differences, but the basic idea of the bound and the algorithm was already established. Although the authors explain it mainly in Introduction, the fact that the proposed method is based on those past work is not fully clear from the descriptions in the paper. 

- The variables in (3) are not defined in the main text.

- A (minor) weak point of the paper would be its complexity of the technical writing. Because of the large number of variables and complicated definition of the optimization problem, the paper is a bit difficult to follow. More detailed explanations particularly for the problem (2) would help readers even if it is only in appendix (Actually, I had to check Bertsimas and Dunn 2017 to understand the basic formulation of (2)).
questions: In (6) and (10), 'min' should be the inside of \sum? Although the subscript 's' is in the sum index, it is also shown outside of the sum (m_s). 

In Algorithm 1, what does 'j \in {1,2} is infeasible' mean?
limitations: A limitation about the tree depth is described in Section 6.
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 presents a new approach for globally optimal decision trees. Inspired by the scalability issues of previous work, the paper proposes to formulate the problem as a two-stage optimization problem and develop a specialized branch and bound approach for training optimal decision trees for classification problems. The approach uses decomposition of bound computation that can be parallelized as well as a sample reduction technique. Experiments show the approach outperforms the well-known OCT approach and the heuristic algorithm CART.


-----
I thank the authors for their thoughtful response and their attempt to address the comments. Although the new results do not cover most of the approaches I suggested, I acknowledge it may be challenging to obtain and run the code in short time. It would be useful to add at least some of them once you successfully run them.

Also, the results for depth of 3 are promising and show the proposed approach outperforms the baselines.

I have therefore increased my score.
strengths_and_weaknesses: Strengths:
- Interesting and novel approach for globally optimal decision trees based on two-stage optimization and specialized branch and bound algorithm.
- Strong theoretical guarantees and focus on both quality solution and the optimality gap.
- Experiments show the approach significantly outperforms the baselines.

Weaknesses:
- Missing important baselines in experiments: current experiments only compare to OCT and ignore a large amount of approaches for optimal decision trees developed over the last year. In particular, despite the focus on MIP and continuous features, the work should compare against prominent non-MIP-based optimal approaches and approaches that first convert continuous values to discrete values using a transformation that maintains optimality (e.g., assigning a single variable to each value). Some examples include [1-5] listed below.
- Experiments are limited to trees of depth 2. This is a very shallow depth and many previous works have considered deeper trees.
- Ablation study: the paper would benefit from an analysis of the impact of different components (e.g., performance without the sample reduction technique).
- Minor points:
	* line 3, 36: "tailed" I think should be "tailored"?
	* line 104: "feature size" -> "number of features"?
	* line 214: "reduce" -> "reduces"

[1] Verwer, Sicco, and Yingqian Zhang. "Learning optimal classification trees using a binary linear program formulation." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.
[2] Aghaei, Sina, Andrés Gómez, and Phebe Vayanos. "Strong optimal classification trees." arXiv preprint arXiv:2103.15965 (2021).
[3] Aglin, Gaël, Siegfried Nijssen, and Pierre Schaus. "Learning optimal decision trees using caching branch-and-bound search." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.
[4] Hu, Hao, et al. "Learning optimal decision trees with maxsat and its integration in adaboost." IJCAI-PRICAI 2020, 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence. 2020.
[5] Shati, Pouya, Eldan Cohen, and Sheila McIlraith. "SAT-based approach for learning optimal decision trees with non-binary features." 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.

questions: I don't have any questions beyond my points above
limitations: I did not identify any issues related to limitations and potential negative societal impact.
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 propose an approach for finding exactly optimal decision trees using a two stage stochastic program, with the first stage problem consisting of the variables related to the structure of the tree such as splits, and the second stage variables consisting of example-related terms such as what leaves the sample falls into as it progresses in the tree structure. The approach uses a modified branch and bound approach to solve this two-stage problem and demonstrates improved runtime performance and testing accuracy over baselines in larger datasets which are either heuristic decision tree methods or optimal decision trees which are formulated as large mixed integer programs. 
strengths_and_weaknesses: Overall the paper’s main strength is making the guarantees of optimal decision trees applicable for larger datasets by proposing an intricate solving approach that enables efficient closing of the primal and dual bound. Furthermore, it Is able to demonstrate the benefit of having optimal classification trees by finding improved solutions that outperform standard methods in terms of test time performance. The proposed approach not only gives improved primal solutions in the case of large datasets, but also gives performance bounds for the dataset it is trained on and is able to determine how suboptimal the current solution can possibly be.

The paper itself is clear and well-written, adequately explaining the approaches in previous work and the significance with respect to the previous work. Furthermore, the solution algorithm is original and the different components seem to be well-founded in addressing limitations of previous work.

The proposed approach has several components that tackle different challenges of the optimal decision tree problem. It would strengthen the paper to display results corresponding to the strengths of the work to validate the approach. Specifically, it would be interesting to see the gap convergence plots for the given approach and potentially a baseline to show that the work done for improving the bound does indeed result in tighter bounds and better gap closure. Additionally, it would be interesting to see if these types of approaches could be integrated into previous work to understand the importance of the individual contributions.

questions: Can individual components of the proposed approach be integrated into previous work on optimal classification trees?

Does the proposed approach close the gap faster in terms of runtime? What does the gap convergence here look like compared to previous approaches? It would be helpful to give an idea of what this looks like throughout the solving process to understand how beneficial/harmful it would be to stop the solving procedure early given time constraints.

Is it possible to compute the gap for the CART models? Here you still have the quality of the primal solution and you might use one of the computed bounds to determine how suboptimal the CART solution is.

Is it possible to encode rules enforcing fairness into the solving procedure? Is the formulation flexible enough to address other objectives in the training procedure?

Small changes:
Line 50: handle large dataset[s]

limitations: The authors adequately address the limitation of only being able to solve for trees with limited depth as previous work is also limited by this constraint. It is a promising direction for future work but scalability here is one main limitation of the current work in optimal decision trees.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper presents an algorithm for learning the optimal decision tree w.r.t. regularized training loss. The algorithm is based on the branch-and-bound method, and takes a two-stage stochastic optimization approach to decompose the problem. The main novelty of the algorithm is the computation of the dual bound at each search node, where the authors: use separability to split the second stage problem into many "group" problems solved in parallel, and introduce a data reduction scheme to further reduce the node problem sizes. The authors present a computational study comparing their method against existing methods for training tree models in terms of model accuracy, optimality gap, and solve time. 
strengths_and_weaknesses: The paper is situated in an area of interest and significance to the NeurIPS community, and presents algorithmic improvements that are, to my knowledge, original. The computational results suggest an improvement over the state of the art, in terms of model accuracy and scalability of the training algorithm. The paper is somewhat difficult to read at points, and does not do as much to contextualize the results with the existing literature as it could.

My main concern with the paper is the hyperparameter selection in the computational study. The authors select a single regularization parameter value alpha for the entire study, seemingly arbitrarily. This regularization parameter can have a substantial impact on the model accuracy, as well as potentially on the solve time. It is not obvious to me that choosing the same value for the different algorithms is the "right" thing to do in order to get the highest quality models. It is certainly not the case that this value should remain fixed for different data sets, as the authors acknowledge on page 9.

Therefore, I think the computational study would be much stronger the regularization hyperparameter is selected through validation, done separately for each of the three methods and each of the data sets.
questions: * The typesetting of (2) appears pretty broken: Missing "for all" quantifiers, (2m) does not seem to make sense as s is not a decision variable, etc.
* Please situate (2) in the literature: Is this equivalent to the formulation of Bertsimas and Dunn, or are their modifications for which you are claiming novelty? If so, please highlight those modifications and, importantly, provide a formal proof of the validity of the formulation in the appendix.
* "BB node" is used in the abstract and introduction, but is only defined at the end of the introduction.
* The alpha symbol is reused with different meanings in (1) and Section 3.
* I believe you want to flip the min and sum in (6) and (8).
limitations: The authors do not explicitly address the potential negative social impact of their work. The discussion of limitations is terse, but sufficient.
review_title: null

Meta-review: metareview: This paper proposes a new approach for computing globally optimal decision trees that is more scalable than prior work. Reviewers gshW, fTBj, and 25Mp are all in favor of accepting the paper, with the main strengths being that:

1. The algorithmic approach is novel and improves scalability of learning globally optimal decision trees.
1. Experiments show that learning globally optimal decision trees improves over baseline methods.
1. The proposed algorithm is empirically shown to be more scalable than prior work.

Reviewer v4RW argues that the paper should be rejected. Their main concern is that the authors select a single regularization parameter for the entire study, seemingly arbitrarily. In response, the authors argue that keeping the regularization parameter fixed when comparing between their proposed method and baselines is to demonstrate the increased accuracy of the learned tree due to optimally solving the optimization problem. They authors also provided new experimental results during the discussion period where the regularization parameter is tuned for each method and dataset. Overall I am convinced by the authors response, and reviewer v4RW did not respond during the discussion period.

The other weaknesses discussed by the reviewers are:

1. Reviewer fTBj argued that the experiments were missing important baselines, experiments were only performed with depth-2 trees, and that the experiments would benefit from an ablation study showing how each component of the proposed algorithm helps performance.  In the discussion period the authors provided results with one additional baseline, trees of depth 3, larger datasets, and an ablation study. Reviewer fTBj was encouraged by these results and raised their score as a result.
1. Reviewer 25Mp asked for clarification on how the proposed method differs from Cao and Zavala (2019) and Hua et al. (2021). In the discussion period, the authors point out a number of technical differences between their work and the prior work, and committed to including this discussion in the paper. I am generally convinced by their arguments and reviewer 25Mp did not respond during the discussion period.

Overall, I feel that the points in favor of the paper outweigh the points against.

confidence: Less certain
Decision: Accept