# Sparsity in Optimal Randomized Classification Trees

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

## Key facts

- Cited by 13 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 21 Feb 2020.

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

- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [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)
- [Optimal Decision Diagrams for Classification](https://mlsanity.com/paper/2205.14500/) (2022)
- [Generating collective counterfactual explanations in score-based classification via mathematical optimization](https://mlsanity.com/paper/2310.12822/) (2023)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [Rule Generation for Classification: Scalability, Interpretability, and Fairness](https://mlsanity.com/paper/2104.10751/) (2021)
- [Rolling Lookahead Learning for Optimal Classification Trees](https://mlsanity.com/paper/2304.10830/) (2023)
- [Soft regression trees: a model variant and a decomposition training algorithm](https://mlsanity.com/paper/2501.05942/) (2025)
- [Dive into Decision Trees and Forests: A Theoretical Demonstration](https://mlsanity.com/paper/2101.08656/) (2021)
- [On multivariate randomized classification trees: l0-based sparsity, VC~dimension and decomposition methods](https://mlsanity.com/paper/2112.05239/) (2021)
- [Loss-Optimal Classification Trees: A Generalized Framework and the Logistic Case](https://mlsanity.com/paper/2306.00857/) (2023)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)

## Abstract (arXiv)

Decision trees are popular Classification and Regression tools and, when small-sized, easy to interpret. Traditionally, a greedy approach has been used to build the trees, yielding a very fast training process; however, controlling sparsity (a proxy for interpretability) is challenging. In recent studies, optimal decision trees, where all decisions are optimized simultaneously, have shown a better learning performance, especially when oblique cuts are implemented. In this paper, we propose a continuous optimization approach to build sparse optimal classification trees, based on oblique cuts, with the aim of using fewer predictor variables in the cuts as well as along the whole tree. Both types of sparsity, namely local and global, are modeled by means of regularizations with polyhedral norms. The computational experience reported supports the usefulness of our methodology. In all our data sets, local and global sparsity can be improved without harming classification accuracy. Unlike greedy approaches, our ability to easily trade in some of our classification accuracy for a gain in global sparsity is shown.