# Optimal Sparse Regression Trees

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 48 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 6 of 6)

- [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)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [Learning Optimal Classification Trees: Strong Max-Flow Formulations](https://mlsanity.com/paper/2002.09142/) (2020)

## Built on by (most cited first, 13 of 13)

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration](https://mlsanity.com/paper/2511.03344/) (2025)
- [Conditional Density Estimation with Histogram Trees](https://mlsanity.com/paper/2410.11449/) (2024)
- [Piecewise Polynomial Regression of Tame Functions via Integer Programming](https://mlsanity.com/paper/2311.13544/) (2023)
- [Soft regression trees: a model variant and a decomposition training algorithm](https://mlsanity.com/paper/2501.05942/) (2025)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Improving the Validity of Decision Trees as Explanations](https://mlsanity.com/paper/2306.06777/) (2023)
- [Locally Pareto-Optimal Interpretations for Black-Box Machine Learning Models](https://mlsanity.com/paper/2508.15220/) (2025)
- [Optimal hypersurface decision trees](https://mlsanity.com/paper/2509.12057/) (2025)
- [Surrogate Graph Partitioning for Spatial Prediction](https://mlsanity.com/paper/2510.07832/) (2025)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)
- [DICS: Data-Informed Centroid Splitting for Decision Tree Classifiers](https://mlsanity.com/paper/2608.20258/) (2026)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)

## Abstract (arXiv)

Regression trees are one of the oldest forms of AI models, and their predictions can be made without a calculator, which makes them broadly useful, particularly for high-stakes applications. Within the large literature on regression trees, there has been little effort towards full provable optimization, mainly due to the computational hardness of the problem. This work proposes a dynamic-programming-with-bounds approach to the construction of provably-optimal sparse regression trees. We leverage a novel lower bound based on an optimal solution to the k-Means clustering algorithm in 1-dimension over the set of labels. We are often able to find optimal sparse trees in seconds, even for challenging datasets that involve large numbers of samples and highly-correlated features.