Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Summary

This paper presents a new approach to learn decision trees via sparse relaxation. The approach starts from a mixed-integer program that can simultaneously induce and prune optimal decision trees from data. The proposed technique aims to solve a continuous relaxation of this problem by combining (1) a tree induction routine, which uses isotonic optimization with (2) an efficient implementation that avoids the need for automatic differentiation. The paper includes experiments on publically available datasets, showing how the decision trees produced via sparse relaxation to decision trees produced using other tree induction approaches.

## Pros

- Interesting new technique for a canonical problem. 
- Proposed method produces trees that appear to perform well on classification, regression, and clustering problems.
- Paper showcases a deft approach to modern algorithm design

## Cons

- No theory or empirical results to characterize the optimality of trees produced via sparse relaxation. 

## Rating

I have awarded the paper a 6, though I am open to increasing my score if the authors can address some of the questions I include below. Overall, my chief concern about this work is that it does not include any evidence pertaining to the optimality for trees produced via sparse relaxation. In effect, the main argument for the proposed sparse relaxation technique is that it produces trees that perform well on five datasets. I believe that my concerns should be easy to address – either by reporting the optimality gap of the trees in the experimental results, or by including comparisons with methods that are guaranteed to find optimal trees. 


##  Questions / Comments

1. Have you evaluated the optimality of solutions of your method with respect to the exact tree-fitting optimization problem – i.e., problem (10) where the tree is a solution to the MIP in (2). All decision trees should be feasible with respect to this problem. In turn, it should be possible to report their "optimality gap." Reporting the optimality gap would provide some evidence to evaluate the integrity of the decisions you made in algorithm decision. It could also showcase the value of sparse relaxation as a feasibility heuristic for the MIP-based approach. 

2. In the experiments, what is the relative optimality gap of the solutions found by OPTREE? Is it finding certifiably optimal solutions (i.e., solutions with a relative optimality gap of 0%)? If not, it would be useful to include comparisons on a tabular dataset that is small enough for OPTREE to find a certifiably optimal solution. Two datasets to consider here are (1) UCI Mushrooms dataset (which is linearly separable and should be easy for all methods), and (2) the COMPAS dataset (also small, but not linearly separable). 

FWIW, the statement that "Bertsimas & Dunn (2017) phrased the objective of CART as a MIP that could be solved exactly" is misleading as it suggests that Bertsimas & Dunn (2017) are able to recover globally optimal solutions to the MIP. This is not the case. In many datasets, the proposed method can only find feasible solutions that perform well but have large optimality gaps. 

3. I am wondering why the authors did not consider the following methods to train optimal decision trees in their experiments:

- [Optimal Sparse Decision Trees](https://papers.nips.cc/paper/8947-optimal-sparse-decision-trees)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://proceedings.icml.cc/static/paper_files/icml/2020/3364-Paper.pdf)

This seems like a weird oversight given that: (i) the paper includes references to both of these works; (ii) both works include reliable implementation that could easily be used to train decision trees in the experimental section (see e.g., https://github.com/Jimmy-Lin/GeneralizedOptimalSparseDecisionTrees). 

The paper currently references both of these works in a way that suggests that they are MIP-based methods. This is misleading. These methods are able to fit certifiably optimal decision trees through specialized algorithms that do not require solving a MIP. I recognize that there has to be a limit to the number of experiments that one can perform. That being said, the trees produced by these methods are an important baseline to include in the experiments since they appear to outperform those produced by MIP-based approaches.
review_title: Recommending Weak Accept.

final_score: rating: 3: Clear rejection
review_content: The problem definitions are not somewhat unclear. It seems that (1)-(7) is to find a pruning of the given tree, which are not explicitly mentioned. 

It is not nontrivial that the problem (1) leads to a tree. It would be necessary to have some proposition that ensures the desired properties (e.g., solution represents a tree) of the solution or cites such previously known ones.

The obtained solutions in (3)-(7) are not discrete and how to round up continuous solutions to discrete ones are not shown. 

As a summary, the current writing lacks important information such as the correctness of the solutions, which significantly reduces the contribution of the paper, even if the experimental results look better than previous work.

review_title: The experimental results are promising but writing lacks important information

final_score: rating: 7: Good paper, accept
review_content: Summary: The paper provides an interesting way to learn binary trees that is faster than generic solvers of MIP. The trick is to use gradient-based methods for a new sparse relaxation of MPI. Authors compare their method to generic solvers and find a substantial improvement on runtime. This is certainly important for scalability.

The paper overall is of good quality. The story of the work is well-written which makes the contributions easier to digest.

In terms of theoretical contributions, the work is "weak" in the sense that the main result follows from a simple relaxation. However, authors show strong empirical evidence that their method is faster and competitive to existing results. Thus, in terms of scalability, the results are relevant.

If my understanding is correct, the appealing aspect of their method is the runtime. In the experiments section, authors show a huge gap in runtime between cvxpy and their implementation. I wonder if cvxpy is mostly implemented in Python, given that the authors implemented their method in C++, I would expect a better performance just from that. Although, the huge gap in runtime suggests that it wouldn't matter.

The topic is also of good significance given that decision trees are still widely used in practice. 


review_title: Good paper

final_score: rating: 4: Ok but not good enough - rejection
review_content: The given paper describes a novel approach of learning binary trees using a differentiable relaxation of MIP. For that matter, authors describe their approach of tree traversal for the given input x and a complete binary tree of depth D. This problem is formulated as MIP which is relaxed to make it differentiable. This MIP is then reformulated to learn a tree structure (i.e. tree pruning). Finally, a decision node parameters are optimized using backpropagation. The algorithm alternates between tree structure learning using relaxed MIP and tree parameters learning using SGD. 

Major advantageous:

  . The proposed method is interesting and addresses the tree learning algorithm from different perspective. I liked the idea of MIP relaxation and the proposed algorithm to solve the QP (using isotonic regression).

  . It is nice that the method is quite generic and can be applied to both (semi)supervised/unsupervised (e.g. clustering) problems.

Major concerns:

  . First of all, I found this paper is hard to follow and understand. Therefore, I have a couple of fundamental questions/comments regarding methodology:

    - The overall obj function (eq. 10) is minimized using backpropagation over decision node parameters \theta. However, in order to compute gradients w.r.t. \theta, we need to compute q(x) which is, I believe, non-differentiable (it involves max function). 

    - Are you solving the tree program (eq. 3) at each mini-batch update or it is done only once at the beginning of the minimization problem 10? Providing a pseudocode of the overall algorithm would be beneficial.

    - In conventional trees, a tree output is given by its leaf. However, here it seems the final prediction is obtained by f(.) and I don't understand why? What is the use of f(.)? I know that it is a linear function or MLP. But, why it takes z and x as arguments and makes the final prediction. It is not well described in the paper. By the way, figure 1 is not referenced anywhere...

  . Given all relaxations in the final algorithm, my impression is that these trees are look like a regular soft trees but with tree structure learning capability. 

  . Experiments lack sufficient evaluations (for regression and classification). For regression, comparison is performed only against CART. Moreover, why depth of the tree for CART is limited to {2,...,6}? I believe that it heavily under-represents CART since it is known that the depth for such trees should be sufficiently large. Most importantly, I strongly suggest authors to include more advanced baselines (e.g. [1,2,3]) for both classification and regression. Moreover, resulting table should contain model sizes in terms of number of parameters, at least (e.g. I'm confident that CART trees will be much smaller).

[1] Tanno, R., Arulkumaran, K., Alexander, D. C., Criminisi, A., and Nori, A. Adaptive neural trees. ICML 2019.

[2] Carreira-Perpinan, M. A. and Tavallali, P. (2018). Alternating optimization of decision trees, with application to learning sparse oblique trees. NeurIPS 2018.

[3] A. Zharmagambetov and M. A. Carreira-Perpinan (2020): Smaller, More Accurate Regression Forests Using Tree Alternating Optimization. ICML 2020

Minor concerns: 

  . I believe that the method cannot be used to train a regular axis-algined trees, i.e. to force each node to use only one feature. 

  . NDF baseline is always performs better than the proposed approach. I believe ANT[1] will perform even better. Given all of them have similar model sizes (including the proposed method), I don't see any practical benefits of the proposed method over the others.
review_title: Quite generic but unclear tree learning algorithm

Meta-review: The main problem as flagged by reviewers is the lack of formal evidence that the approach is a right one to carry out. Decision tree induction has early been the subject of formal studies in ML, whether in statistics (Friedman et al.) or ML (Kearns et al.). It is a bit sad that a new approach that relies on a much different standpoint on the problem and modelling of tree classification (Section 3, R2), with experimental results recognized by reviewers (R3, R4) is not accompanied by formal analyses on par with SOTA for related approaches (R3, R1). I would strongly suggest the authors fit in a few more Lemmata, either to follow up on specific problems (R1). The paper would tremendously benefit from extensive connections with the existing theory, be it from the generalization and overfitting standpoint (R2, remark #6) or the choice of the appropriate best contender using the boosting literature. Decision was taken not to accept the paper but I would very strongly encourage the authors to revise the draft.

Decision: Reject