# A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Estimation and Inference of Heterogeneous Treatment Effects using Random Forests](https://mlsanity.com/paper/1510.04342/) (2015)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [Recursive Partitioning for Heterogeneous Causal Effects](https://mlsanity.com/paper/1504.01132/) (2015)
- [ranger: A Fast Implementation of Random Forests for High Dimensional Data in C++ and R](https://mlsanity.com/paper/1508.04409/) (2015)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Iterative Random Forests to detect predictive and stable high-order interactions](https://mlsanity.com/paper/1706.08457/) (2017)
- [Local Linear Forests](https://mlsanity.com/paper/1807.11408/) (2018)
- [Data-driven Advice for Applying Machine Learning to Bioinformatics Problems](https://mlsanity.com/paper/1708.05070/) (2017)
- [Trees, forests, and impurity-based variable importance](https://mlsanity.com/paper/2001.04295/) (2020)
- [Estimation and Inference with Trees and Forests in High Dimensions](https://mlsanity.com/paper/2007.03210/) (2020)
- [Sparse learning with CART](https://mlsanity.com/paper/2006.04266/) (2020)
- [Bridging Breiman's Brook: From Algorithmic Modeling to Statistical Learning](https://mlsanity.com/paper/2102.12328/) (2021)
- [Additive Models with Trend Filtering](https://mlsanity.com/paper/1702.05037/) (2017)
- [Linear Aggregation in Tree-based Estimators](https://mlsanity.com/paper/1906.06463/) (2019)

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

- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods](https://mlsanity.com/paper/2202.00858/) (2022)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [Fast Interpretable Greedy-Tree Sums](https://mlsanity.com/paper/2201.11931/) (2022)
- [An initial alignment between neural network and target is needed for gradient descent to learn](https://mlsanity.com/paper/2202.12846/) (2022)
- [On the Convergence of CART under Sufficient Impurity Decrease Condition](https://mlsanity.com/paper/2310.17114/) (2023)
- [Local MDI+: Local Feature Importances for Tree-Based Models](https://mlsanity.com/paper/2506.08928/) (2025)
- [Analyze Additive and Interaction Effects via Collaborative Trees](https://mlsanity.com/paper/2405.11477/) (2024)
- [Covariance-Driven Regression Trees: Reducing Overfitting in CART](https://mlsanity.com/paper/2601.07281/) (2026)

## Abstract (arXiv)

Decision trees are important both as interpretable models amenable to high-stakes decision-making, and as building blocks of ensemble methods such as random forests and gradient boosting. Their statistical properties, however, are not well understood. The most cited prior works have focused on deriving pointwise consistency guarantees for CART in a classical nonparametric regression setting. We take a different approach, and advocate studying the generalization performance of decision trees with respect to different generative regression models. This allows us to elicit their inductive bias, that is, the assumptions the algorithms make (or do not make) to generalize to new data, thereby guiding practitioners on when and how to apply these methods. In this paper, we focus on sparse additive generative models, which have both low statistical complexity and some nonparametric flexibility. We prove a sharp squared error generalization lower bound for a large class of decision tree algorithms fitted to sparse additive models with C1 component functions. This bound is surprisingly much worse than the minimax rate for estimating such sparse additive models. The inefficiency is due not to greediness, but to the loss in power for detecting global structure when we average responses solely over each leaf, an observation that suggests opportunities to improve tree-based algorithms, for example, by hierarchical shrinkage. To prove these bounds, we develop new technical machinery, establishing a novel connection between decision tree estimation and rate-distortion theory, a sub-field of information theory.