# Stability of Random Forests and Coverage of Random-Forest Prediction Intervals

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

## Key facts

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

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

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Predictive Inference Is Free with the Jackknife+-after-Bootstrap](https://mlsanity.com/paper/2002.09025/) (2020)
- [Concentration in unbounded metric spaces and algorithmic stability](https://mlsanity.com/paper/1309.1007/) (2013)
- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Narrowing the Gap: Random Forests In Theory and In Practice](https://mlsanity.com/paper/1310.1415/) (2013)

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

- [Synthetic Data Generation for Augmenting Small Samples](https://mlsanity.com/paper/2501.18741/) (2025)
- [Leave-One-Out Stable Conformal Prediction](https://mlsanity.com/paper/2504.12189/) (2025)
- [Towards Stable Machine Learning Model Retraining via Slowly Varying Sequences](https://mlsanity.com/paper/2403.19871/) (2024)
- [The Role of Depth, Width, and Tree Size in Expressiveness of Deep Forest](https://mlsanity.com/paper/2407.05108/) (2024)

## Abstract (arXiv)

We establish stability of random forests under the mild condition that the squared response (Y2) does not have a heavy tail. In particular, our analysis holds for the practical version of random forests that is implemented in popular packages like textttrandomForest in textttR. Empirical results show that stability may persist even beyond our assumption and hold for heavy-tailed Y2. Using the stability property, we prove a non-asymptotic lower bound for the coverage probability of prediction intervals constructed from the out-of-bag error of random forests. With another mild condition that is typically satisfied when Y is continuous, we also establish a complementary upper bound, which can be similarly established for the jackknife prediction interval constructed from an arbitrary stable algorithm. We also discuss the asymptotic coverage probability under assumptions weaker than those considered in previous literature. Our work implies that random forests, with its stability property, is an effective machine learning method that can provide not only satisfactory point prediction but also justified interval prediction at almost no extra computational cost.