# Fast Sparse Decision Tree Optimization via Reference Ensembles arXiv: https://arxiv.org/abs/2112.00798 ยท HTML: https://mlsanity.com/paper/2112.00798/ ## Key facts - Cited by 38 papers in the map (data through 14 Oct 2026). - Builds on 12 of its 49 references that are in the map. - First posted on arXiv 1 Dec 2021. ## Builds on (most cited first, 12 of 12) - [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019) - [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020) - [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018) - [In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Prediction](https://mlsanity.com/paper/2005.04176/) (2020) - [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020) - [Interpreting Tree Ensembles with inTrees](https://mlsanity.com/paper/1408.5456/) (2014) - [Making Tree Ensembles Interpretable: A Bayesian Model Selection Approach](https://mlsanity.com/paper/1606.09066/) (2016) - [Interpreting Models via Single Tree Approximation](https://mlsanity.com/paper/1610.09036/) (2016) - [An Optimization Approach to Learning Falling Rule Lists](https://mlsanity.com/paper/1710.02572/) (2017) - [Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches](https://mlsanity.com/paper/1907.02211/) (2019) - [GENESIM: genetic extraction of a single, interpretable model](https://mlsanity.com/paper/1611.05722/) (2016) - [Rectified Decision Trees: Towards Interpretability, Compression and Empirical Soundness](https://mlsanity.com/paper/1903.05965/) (2019) ## Built on by (most cited first, 30 of 38) - [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022) - [Amazing Things Come From Having Many Good Models](https://mlsanity.com/paper/2407.04846/) (2024) - [Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features](https://mlsanity.com/paper/2206.11844/) (2022) - [Optimal Sparse Regression Trees](https://mlsanity.com/paper/2211.14980/) (2022) - [Near Optimal Decision Trees in a SPLIT Second](https://mlsanity.com/paper/2502.15988/) (2025) - [Fast hyperboloid decision tree algorithms](https://mlsanity.com/paper/2310.13841/) (2023) - [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023) - [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025) - [Finding Interpretable Class-Specific Patterns through Efficient Neural Search](https://mlsanity.com/paper/2312.04311/) (2023) - [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022) - [Leveraging Predictive Equivalence in Decision Trees](https://mlsanity.com/paper/2506.14143/) (2025) - [ODTlearn: A Package for Learning Optimal Decision Trees for Prediction and Prescription](https://mlsanity.com/paper/2307.15691/) (2023) - [Harnessing the Power of Choices in Decision Tree Learning](https://mlsanity.com/paper/2310.01551/) (2023) - [Compact Rule-Based Classifier Learning via Gradient Descent](https://mlsanity.com/paper/2502.01375/) (2025) - [Beyond Interpretability: Exploring the Comprehensibility of Adaptive Video Streaming through Large Language Models](https://mlsanity.com/paper/2508.16448/) (2025) - [Fast Optimization of Weighted Sparse Decision Trees for use in Optimal Treatment Regimes and Optimal Policy Design](https://mlsanity.com/paper/2210.06825/) (2022) - [Supervised Feature Compression based on Counterfactual Analysis](https://mlsanity.com/paper/2211.09894/) (2022) - [Optimal Decision Tree Pruning Revisited: Algorithms and Complexity](https://mlsanity.com/paper/2503.03576/) (2025) - [Leo Breiman, the Rashomon Effect, and the Occam Dilemma](https://mlsanity.com/paper/2507.03884/) (2025) - [Optimal Recourse Summaries via Bi-Objective Decision Tree Learning](https://mlsanity.com/paper/2605.07598/) (2026) - [Policy learning for many outcomes of interest: Combining optimal policy trees with multi-objective Bayesian optimisation](https://mlsanity.com/paper/2212.06312/) (2022) - [Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees](https://mlsanity.com/paper/2408.01297/) (2024) - [Improving Decision Sparsity](https://mlsanity.com/paper/2410.20483/) (2024) - [Rare Event Detection in Imbalanced Multi-Class Datasets Using an Optimal MIP-Based Ensemble Weighting Approach](https://mlsanity.com/paper/2412.13439/) (2024) - [VAR: Visual Analysis for Rashomon Set of Machine Learning Models' Performance](https://mlsanity.com/paper/2507.22556/) (2025) - [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025) - [The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learning](https://mlsanity.com/paper/2511.21799/) (2025) - [A Fast Interpretable Fuzzy Tree Learner](https://mlsanity.com/paper/2512.11616/) (2025) - [Same Error, Different Function: The Optimizer as an Implicit Prior in Financial Time Series](https://mlsanity.com/paper/2603.02620/) (2026) - [Search Strategies for Optimal Classification and Regression Trees](https://mlsanity.com/paper/2607.28170/) (2026) ## Abstract (arXiv) Sparse decision tree optimization has been one of the most fundamental problems in AI since its inception and is a challenge at the core of interpretable machine learning. Sparse decision tree optimization is computationally hard, and despite steady effort since the 1960's, breakthroughs have only been made on the problem within the past few years, primarily on the problem of finding optimal sparse decision trees. However, current state-of-the-art algorithms often require impractical amounts of computation time and memory to find optimal or near-optimal trees for some real-world datasets, particularly those having several continuous-valued features. Given that the search spaces of these decision tree optimization problems are massive, can we practically hope to find a sparse decision tree that competes in accuracy with a black box machine learning model? We address this problem via smart guessing strategies that can be applied to any optimal branch-and-bound-based decision tree algorithm. We show that by using these guesses, we can reduce the run time by multiple orders of magnitude, while providing bounds on how far the resulting trees can deviate from the black box's accuracy and expressive power. Our approach enables guesses about how to bin continuous features, the size of the tree, and lower bounds on the error for the optimal decision tree. Our experiments show that in many cases we can rapidly construct sparse decision trees that match the accuracy of black box models. To summarize: when you are having trouble optimizing, just guess.