# Sparse learning with CART

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2020.

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

- [Large Scale Prediction with Decision Trees](https://mlsanity.com/paper/2104.13881/) (2021)
- [Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions](https://mlsanity.com/paper/2303.14226/) (2023)
- [A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds](https://mlsanity.com/paper/2110.09626/) (2021)
- [Muddling Label Regularization: Deep Learning for Tabular Datasets](https://mlsanity.com/paper/2106.04462/) (2021)
- [Consistent Sufficient Explanations and Minimal Local Rules for explaining regression and classification models](https://mlsanity.com/paper/2111.04658/) (2021)
- [Optimal Sparse Recovery with Decision Stumps](https://mlsanity.com/paper/2303.04301/) (2023)
- [Revisiting Randomization in Greedy Model Search](https://mlsanity.com/paper/2506.15643/) (2025)
- [AdaCap: Adaptive Capacity control for Feed-Forward Neural Networks](https://mlsanity.com/paper/2205.07860/) (2022)
- [Building Trees for Probabilistic Prediction via Scoring Rules](https://mlsanity.com/paper/2402.11052/) (2024)
- [Grafting: Making Random Forests Consistent](https://mlsanity.com/paper/2403.06015/) (2024)
- [Empowering Decision Trees via Shape Function Branching](https://mlsanity.com/paper/2510.19040/) (2025)
- [Covariance-Driven Regression Trees: Reducing Overfitting in CART](https://mlsanity.com/paper/2601.07281/) (2026)

## Abstract (arXiv)

Decision trees with binary splits are popularly constructed using Classification and Regression Trees (CART) methodology. For regression models, this approach recursively divides the data into two near-homogenous daughter nodes according to a split point that maximizes the reduction in sum of squares error (the impurity) along a particular variable. This paper aims to study the statistical properties of regression trees constructed with CART methodology. In doing so, we find that the training error is governed by the Pearson correlation between the optimal decision stump and response data in each node, which we bound by constructing a prior distribution on the split points and solving a nonlinear optimization problem. We leverage this connection between the training error and Pearson correlation to show that CART with cost-complexity pruning achieves an optimal complexity/goodness-of-fit tradeoff when the depth scales with the logarithm of the sample size. Data dependent quantities, which adapt to the dimensionality and latent structure of the regression model, are seen to govern the rates of convergence of the prediction error.