# Large Scale Prediction with Decision Trees

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 28 Apr 2021.

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

- [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)
- [Hyperparameters and Tuning Strategies for Random Forest](https://mlsanity.com/paper/1804.03515/) (2018)
- [Understanding Random Forests: From Theory to Practice](https://mlsanity.com/paper/1407.7502/) (2014)
- [Randomization as Regularization: A Degrees of Freedom Explanation for Random Forest Success](https://mlsanity.com/paper/1911.00190/) (2019)
- [High-dimensional classification by sparse logistic regression](https://mlsanity.com/paper/1706.08344/) (2017)
- [Minimax optimal rates for Mondrian trees and forests](https://mlsanity.com/paper/1803.05784/) (2018)
- [Narrowing the Gap: Random Forests In Theory and In Practice](https://mlsanity.com/paper/1310.1415/) (2013)
- [AMF: Aggregated Mondrian Forests for Online Learning](https://mlsanity.com/paper/1906.10529/) (2019)
- [Estimation and Inference with Trees and Forests in High Dimensions](https://mlsanity.com/paper/2007.03210/) (2020)
- [Trees, Forests, Chickens, and Eggs: When and Why to Prune Trees in a Random Forest](https://mlsanity.com/paper/2103.16700/) (2021)
- [Sparse learning with CART](https://mlsanity.com/paper/2006.04266/) (2020)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)

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

- [Adaptive Conformal Prediction by Reweighting Nonconformity Score](https://mlsanity.com/paper/2303.12695/) (2023)
- [Synthetic Combinations: A Causal Inference Framework for Combinatorial Interventions](https://mlsanity.com/paper/2303.14226/) (2023)
- [Inference with Mondrian Random Forests](https://mlsanity.com/paper/2310.09702/) (2023)
- [On the Convergence of CART under Sufficient Impurity Decrease Condition](https://mlsanity.com/paper/2310.17114/) (2023)
- [Minimax Rates for High-Dimensional Random Tessellation Forests](https://mlsanity.com/paper/2109.10541/) (2021)
- [Local MDI+: Local Feature Importances for Tree-Based Models](https://mlsanity.com/paper/2506.08928/) (2025)
- [FACT: High-Dimensional Random Forests Inference](https://mlsanity.com/paper/2207.01678/) (2022)
- [When does Subagging Work?](https://mlsanity.com/paper/2404.01832/) (2024)
- [Statistical Advantages of Oblique Randomized Decision Trees and Forests](https://mlsanity.com/paper/2407.02458/) (2024)
- [Efficient Decision Trees for Tensor Regressions](https://mlsanity.com/paper/2408.01926/) (2024)
- [Ranking Perspective for Tree-based Methods with Applications to Symbolic Feature Selection](https://mlsanity.com/paper/2410.02623/) (2024)
- [EarlyStopping: Implicit Regularization for Iterative Learning Procedures in Python](https://mlsanity.com/paper/2503.16753/) (2025)
- [Revisiting Randomization in Greedy Model Search](https://mlsanity.com/paper/2506.15643/) (2025)
- [Prospective Learning in Retrospect](https://mlsanity.com/paper/2507.07965/) (2025)
- [Analyze Additive and Interaction Effects via Collaborative Trees](https://mlsanity.com/paper/2405.11477/) (2024)
- [Pure interaction effects unseen by Random Forests](https://mlsanity.com/paper/2406.15500/) (2024)
- [Consistency for Large Neural Networks: Regression and Classification](https://mlsanity.com/paper/2409.14123/) (2024)
- [Analyzing decision tree bias towards the minority class](https://mlsanity.com/paper/2501.04903/) (2025)
- [FairUDT: Fairness-aware Uplift Decision Trees](https://mlsanity.com/paper/2502.01188/) (2025)
- [Uniform convergence of the smooth calibration error and its relationship with functional gradient](https://mlsanity.com/paper/2505.19396/) (2025)
- [Earthquake Damage Grades Prediction using An Ensemble Approach Integrating Advanced Machine and Deep Learning Models](https://mlsanity.com/paper/2506.22129/) (2025)
- [Transfer Learning with Distance Covariance for Random Forest: Error Bounds and an EHR Application](https://mlsanity.com/paper/2510.10870/) (2025)
- [Empowering Decision Trees via Shape Function Branching](https://mlsanity.com/paper/2510.19040/) (2025)
- [Provable Recovery of Locally Important Signed Features and Interactions from Random Forest](https://mlsanity.com/paper/2512.11081/) (2025)
- [Covariance-Driven Regression Trees: Reducing Overfitting in CART](https://mlsanity.com/paper/2601.07281/) (2026)
- [Minimax Rates and Spectral Distillation for Tree Ensembles](https://mlsanity.com/paper/2605.11841/) (2026)
- [Decision Tree Learning on Product Spaces](https://mlsanity.com/paper/2605.12983/) (2026)
- [Kernel of Partition Paths: A Unified Representation for Tree Ensembles](https://mlsanity.com/paper/2606.18853/) (2026)

## Abstract (arXiv)

This paper shows that decision trees constructed with Classification and Regression Trees (CART) and C4.5 methodology are consistent for regression and classification tasks, even when the number of predictor variables grows sub-exponentially with the sample size, under natural 0-norm and 1-norm sparsity constraints. The theory applies to a wide range of models, including (ordinary or logistic) additive regression models with component functions that are continuous, of bounded variation, or, more generally, Borel measurable. Consistency holds for arbitrary joint distributions of the predictor variables, thereby accommodating continuous, discrete, and/or dependent data. Finally, we show that these qualitative properties of individual trees are inherited by Breiman's random forests. A key step in the analysis is the establishment of an oracle inequality, which allows for a precise characterization of the goodness-of-fit and complexity tradeoff for a mis-specified model.