NeurIPS 2020

A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees


Meta Review

This paper is about employing advances in computational efficiency of mixed integer programming methods towards decision tree construction problems. While locally optimal methods can achieve an upper bound on the minimization problem efficiently, closing the optimality gap requires tight lower bounds. The authors use an interval relaxation and a support-vector machine procedure to tighten the lower bound. To scale the algorithm, the authors use a LP-based data selection procedure, and perform all experiments using this procedure. It is not clear whether the global optimality properties of the MIP formulation carry through with the data-selection procedure. Overall, the reviewers viewed the paper as a contribution to the field and the authors responded sufficiently to many of the comments. There is a great deal of interest in developing strong integer programming formulations to problems that were previously thought to be out of reach of MIP solvers and this paper advances the field on its own and suggests further steps for progress.