# On multivariate randomized classification trees: l0-based sparsity, VC~dimension and decomposition methods

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 50 references that are in the map.
- First posted on arXiv 9 Dec 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (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)

## Abstract (arXiv)

Decision trees are widely-used classification and regression models because of their interpretability and good accuracy. Classical methods such as CART are based on greedy approaches but a growing attention has recently been devoted to optimal decision trees. We investigate the nonlinear continuous optimization formulation proposed in Blanquero et al. (EJOR, vol. 284, 2020; COR, vol. 132, 2021) for (sparse) optimal randomized classification trees. Sparsity is important not only for feature selection but also to improve interpretability. We first consider alternative methods to sparsify such trees based on concave approximations of the l0 ``norm". Promising results are obtained on 24 datasets in comparison with l1 and l∞ regularizations. Then, we derive bounds on the VC dimension of multivariate randomized classification trees. Finally, since training is computationally challenging for large datasets, we propose a general decomposition scheme and an efficient version of it. Experiments on larger datasets show that the proposed decomposition method is able to significantly reduce the training times without compromising the accuracy.