# Generalized and Scalable Optimal Sparse Decision Trees

arXiv: https://arxiv.org/abs/2006.08690 · HTML: https://mlsanity.com/paper/2006.08690/

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 100)

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Scalable Rule-Based Representation Learning for Interpretable Classification](https://mlsanity.com/paper/2109.15103/) (2021)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Augmenting Interpretable Models with LLMs during Training](https://mlsanity.com/paper/2209.11799/) (2022)
- [A Path to Simpler Models Starts With Noise](https://mlsanity.com/paper/2310.19726/) (2023)
- [The Rashomon Importance Distribution: Getting RID of Unstable, Single Model-based Variable Importance](https://mlsanity.com/paper/2309.13775/) (2023)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022)
- [Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods](https://mlsanity.com/paper/2202.00858/) (2022)
- [Data-Driven Design for Metamaterials and Multiscale Systems: A Review](https://mlsanity.com/paper/2307.05506/) (2023)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Learning Interpretable Rules for Scalable Data Representation and Classification](https://mlsanity.com/paper/2310.14336/) (2023)
- [Fast Interpretable Greedy-Tree Sums](https://mlsanity.com/paper/2201.11931/) (2022)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [TimberTrek: Exploring and Curating Sparse Decision Trees with Interactive Visualization](https://mlsanity.com/paper/2209.09227/) (2022)
- [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022)
- [GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent](https://mlsanity.com/paper/2305.03515/) (2023)
- [Interpretable and Fair Boolean Rule Sets via Column Generation](https://mlsanity.com/paper/2111.08466/) (2021)
- [Learning Interpretable Differentiable Logic Networks](https://mlsanity.com/paper/2407.04168/) (2024)
- [A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds](https://mlsanity.com/paper/2110.09626/) (2021)
- [Scalable Optimal Multiway-Split Decision Trees with Constraints](https://mlsanity.com/paper/2302.06812/) (2023)
- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [Data Science with LLMs and Interpretable Models](https://mlsanity.com/paper/2402.14474/) (2024)
- [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025)

## Abstract (arXiv)

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift where it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over a variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several orders of magnitude relative to the state-of-the art.