# On the Convergence of CART under Sufficient Impurity Decrease Condition

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 26 Oct 2023.

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

- [Estimation and Inference of Heterogeneous Treatment Effects using Random Forests](https://mlsanity.com/paper/1510.04342/) (2015)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Large Scale Prediction with Decision Trees](https://mlsanity.com/paper/2104.13881/) (2021)
- [Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods](https://mlsanity.com/paper/2202.00858/) (2022)
- [Analysis of purely random forests bias](https://mlsanity.com/paper/1407.3939/) (2014)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)
- [A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds](https://mlsanity.com/paper/2110.09626/) (2021)
- [On the Pointwise Behavior of Recursive Partitioning and Its Implications for Heterogeneous Causal Effect Estimation](https://mlsanity.com/paper/2211.10805/) (2022)

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

- [Revisiting Randomization in Greedy Model Search](https://mlsanity.com/paper/2506.15643/) (2025)
- [Pure interaction effects unseen by Random Forests](https://mlsanity.com/paper/2406.15500/) (2024)
- [The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forest](https://mlsanity.com/paper/2407.05108/) (2024)
- [A Central Limit Theorem for the permutation importance measure](https://mlsanity.com/paper/2412.13020/) (2024)
- [Regular Tree Search for Simulation Optimization](https://mlsanity.com/paper/2506.17696/) (2025)

## Abstract (arXiv)

The decision tree is a flexible machine learning model that finds its success in numerous applications. It is usually fitted in a recursively greedy manner using CART. In this paper, we investigate the convergence rate of CART under a regression setting. First, we establish an upper bound on the prediction error of CART under a sufficient impurity decrease (SID) condition citechi2022asymptotic -- our result improves upon the known result by citechi2022asymptotic under a similar assumption. Furthermore, we provide examples that demonstrate the error bound cannot be further improved by more than a constant or a logarithmic factor. Second, we introduce a set of easily verifiable sufficient conditions for the SID condition. Specifically, we demonstrate that the SID condition can be satisfied in the case of an additive model, provided that the component functions adhere to a ``locally reverse Poincar'e inequality". We discuss several well-known function classes in non-parametric estimation to illustrate the practical utility of this concept.