# Generalization Properties of Decision Trees on Real-valued and Categorical Features

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 45 references that are in the map.
- First posted on arXiv 18 Oct 2022.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [CatBoost: gradient boosting with categorical features support](https://mlsanity.com/paper/1810.11363/) (2018)
- [An ensemble-based system for automatic screening of diabetic retinopathy](https://mlsanity.com/paper/1410.8576/) (2014)
- [Decision trees as partitioning machines to characterize their generalization properties](https://mlsanity.com/paper/2010.07374/) (2020)

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

- [Cross-Fitting-Free Debiased Machine Learning with Multiway Dependence](https://mlsanity.com/paper/2602.11333/) (2026)

## Abstract (arXiv)

We revisit binary decision trees from the perspective of partitions of the data. We introduce the notion of partitioning function, and we relate it to the growth function and to the VC dimension. We consider three types of features: real-valued, categorical ordinal and categorical nominal, with different split rules for each. For each feature type, we upper bound the partitioning function of the class of decision stumps before extending the bounds to the class of general decision tree (of any fixed structure) using a recursive approach. Using these new results, we are able to find the exact VC dimension of decision stumps on examples of ℓ real-valued features, which is given by the largest integer d such that 2ℓ ≥ binomdlfloorfracd2rfloor. Furthermore, we show that the VC dimension of a binary tree structure with LT leaves on examples of ℓ real-valued features is in O(LT log(LTℓ)). Finally, we elaborate a pruning algorithm based on these results that performs better than the cost-complexity and reduced-error pruning algorithms on a number of data sets, with the advantage that no cross-validation is required.