Stability of Random Forests and Coverage of Random-Forest Prediction Intervals
Authors: Yan Wang
Huaiqing Wu
Dan Nettleton
Venue: NeurIPS 2023 poster (2023)
Keywords: Stability
Prediction Intervals
Random Forests
TL;DR: We establish that even the greedy version of random forests used in practice is stable under mild conditions, and prove the coverage probability of prediction intervals constructed from the out-of-bag error of random forests.

Abstract: We establish stability of random forests under the mild condition that the squared response ($Y^2$) 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 \texttt{randomForest} in \texttt{R}. Empirical results show that stability may persist even beyond our assumption and hold for heavy-tailed $Y^2$. 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.

Stability of Random Forests and Coverage of Random-Forest Prediction Intervals
Yan Wang Department of Mathematics Wayne State University Detroit, MI 48202
Huaiqing Wu, Dan Nettleton
Department of Statistics Iowa State University
Ames, IA 50011
vangyan@vayne.edi
disuh diasttttttttttttttteeeettaaatttt
Abstract
We establish stability of random forests under the mild condition that the squared response (V²2) does not have heavy tail. In particular, analysis holds for the practical version of random forests that is implemented in popular packages like randomForest in Empirical results show that stability may persist even beyond our assumption and hold for heavy-tailed y Using the stability property, we prove a con-asymptotic lower bound for the coverage probability of prediction intervals constructed from the out-of-baz of- error of random forests. With another mild condition that is typically satisfied when is continuous, we also establish a complementary upper bound, which can be similarly established for the jack- knife 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 provide not only satisfactory point prediction but also justified interval prediction at almost no extra computational cost.
Introduction
Random forests (RFs) is a successful machine learning method that serves as a standard approach to tabular data analysis and has good predictive performance [10] 77. However, there is big gap between the empirical effectiveness of RFs and the limited understanding of its properties. Most known theoretical results established for variants of RFs not necessarily used in practice
25 22 14 30 For the RF version implemented in packages like FandomForest in R (21). little known without strong assumptions (6] 26 35]; RFs notoriously difficult analyze greedy algorithm. Here we show an important property for the RF used in practice (as well as for other variants) under realistic conditions.
1.1 Stability of random forests
The first main contribution of this work establishes the stability condition for the RF.
Theorem (Stability of random forests, informal). independent and identically distributed (iid) training data points (X,, YJ), ii (1....,n} [n]] and a test point (X,Y) Y), if the squared response
Y2 does not have a heavy tail, then the RF predictor RF a and any out-of-bug (OOB) predictor RF predict similar values, i.e.,
P RF RF RF > En,B) & Vn,B:
(1)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

where RFB B results from the aggregation of all B base tree predictors, while RF only those with the point (X,, Y2) excluded in training; B and Vn,B are small numbers depending on n and B.
This result is referred to as the stability of the RF because it indicates that single training point is extremely important in determining RF B in probabilisticc sense. Theorem I rrelies on a recent important work that establishes the absolute stability (see below for precise definition) of general bagged algorithms with bounded outputs [28]. We take advantage of the fact that the range of the RF output is conditionally dependent upon the maximal and minimal values of Y in the training set, and then we show in theory that the stability property of the RF is possible even if Y is marginally unbounded. To our knowledge, this is the first stability result established for the RF.
The technique used in our analysis requires that Y not have a heavy tail (to make B and Kn.B small). Though arguably already mild, we conjecture that this condition might be further relaxed. As shown below, numerical evidence suggests that the light-tail assumption may not be necessary for RF stability, which could hold even when Y follows a heavy-tail distribution like the Cauchy distribution.
1.2 Random-forest prediction intervals
Stability is a crucial property of a learning algorithm. For example, stability has a deep connection with the generalization error of an algorithm (9 19 [33. Moreover, stability also turns out to be
important in distribution-fres predictive inference. In particular, an algorithm being stable justifies
the jackknife prediction interval (PI, which otherwise has no coverage guarantee
K
In this work, we show that stability makes it possible to construct a PI with guaranteed coverage from the OOB error of the RF. The OOB error is defined as R = Y RF B X.) é e [n]. A main reason why such PI is appealing is that R2 can be obtained almost without extra effort. For example, one-shot training using the R package raanooFoorest gives us an RF predictor RF and all n OOB
predictions RF B for a test point (X, Y) is of the form "RF + proper quantile of {R,}" [7]
(X,). So, from the computational point of view, a convenient way to construct a PI
The second main contribution of this work constructs such Pis and theoretically proves, under mild conditions, the non-asymptotic lower and upper bounds for the coverage probability.
Theorem 2 (Coverage lower bound, informal). Under the same assumptions as in Theorem 7 and for a E (0. 1 we have the following lower bound of coverage probability:
P P[Y - RF BF)) & the [(n + 1)(1 l-] smallest R, + En,B) > 11 21-a-0(pP.B))
where [-] is the ceiling function. Big O and other related notations are used in the usual way.
Theorem (Coverage upper bound, informal). If we further assume that Y is continuous, resulting in distinct prediction errors, then also have the following upper bound:
1
P P(Y RF (X)( < the [(n 1)(1 - a:h smallest R. En,B) < a n n + Pn.B)
As detail below, the Pls we provide coverage guarantees for are neither the jackknife-with-stbbiie interval discussed in R. nor the fackknifee+-fter--oonttt
interval established in [8]. In our context, constructing the former needs n leave-one-out (LOO) predictors (rather than OOB predictors), i.e., n additional RFs with each built on a training set of size n - 1. Constructing the latter needs the explicit information of each RF B (.) rather than the OOB prediction RF (X;) for each X; only. Both these methods require additional, sometimes extensive, computation given current popular packages. In contrast, our results operationally more convenient. After one-shot training, we obtain not only a point predictor RF (-). but also a valid interval predictor at almost no extra cost. Under reasonable conditions, our results indicate that by slightly inflating (or deflating) the PI constructed from the [n + 1)(1 - a)) --th smallest Rd the coverage probability is guaranteed not to decrease (or increase) too much from the desired level of a. In fact, many numerical results, such as those in 17 35 suggest that
P(Y (X) & the [(n + 1)(1 - -+)]-th smallest R.) ~ a.
Motivated by this fact, we further establish an asymptotic result of coverage for such Pls.
When E (0, 1/(n + 1)), follow the convention that the (n + 1)-th smallest R; c..

---

Theorem 4. (Asymptotic coverage, informal) In addition to the conditions in the above theorems, also suppose the prediction error Y [X)] is continuous, and its cumulative distribution function (CDF) does not change too drastically for all sufficiently large n. Then
P P(Y (X) < the [(n + 1)(1 ai) 1-h smallest Ra) 1 as o0.
In [35. this asymptotic coverage was proved based on stronger assumptions. In particular, the true model is assumed to be additive such that "Y = (X) + noise" with the zero-mean noise independent of X, and RF B ((X) ) is assumed to converge to fo in probability. We do not require RF B to converge to anything in any sense when n - co. Technically, we need the family prediction error CDFs be uniformly equicontinuous.
Based on our results, the RF seems to be the only one, among existing popular machine learning algorithms, that can provide both point and interval predictors with justification in such a convenient way. This makes the RF appealing, especially for tasks where the computational cost a concern.
is also worth noting that the upper-bound result is of interest in its own right. It can be generalized to jackknife PIs that are constructed from any stable algorithm; the result serves complement to the lower bounds established previously [3 [8].
Summarizing, we
theoretically prove that the (greedy) RF algorithm is stable when y does not have heavy tail;
numerically show that RF stability may hold beyond the above light-tail assumption;
construct PIs based on the OOB error with finite-sample coverage guarantees: the lower bound of coverage does not need any additional assumption beyond stability; the upper bound needs an additional assumption, which usually satisfied when Y is continuous;
provide the upper bound of coverage for jackknife Pis constructed from general stable algorithms, assuming distinct LOO errors; and
prove asymptotically exact coverage for RF-based PIs under weaker assumptions than those previously considered in published work.
2 Concepts of algorithmic stability
Stability stands at the core of this work. There are different types of stability, each of which is used to assess quantitatively how stable (in some certain sense) an algorithm is with respect to small variations in training data 9 28 4 In recent work 4.. robust optimization is used to enhance the stability of algorithms classification tasks. In 28]. bagging is proved to be an efficient mechanism to stabilize algorithms in regression tasks. We focus on regression here. As will be made clear, the technique used in this work relies on the fact that the RF predictor in regression results from averaging tree predictors. However, the majority vote of tree predictors used in classification, and new ideas are needed to analyze the RF stability in this setting. For our purposes, we introduce three levels of stability from strongest to weakest. The strongest version of stability, introduced in [28). does not depend on the data distribution, and may be referred to as "absolute stability."
Definition (Absolute stability of algorithmss.. For any dataset consisting of n > 2 training points D= {(X1, Yi).... (Xn, Y.)} and any test point YX,Y), an algorithm A is defined to be (s, 6)- absolutely-stable if
1 Pe (((x)
> E
for some e, 8 > O, where denotes the possible innate randomness in the algorithm (such the node splitting procedure in the RF) and can be seen as random variable uniformly distributed in [o, 1]. f A(D; {) is the predictor trained D, and f-i A(D ; is the ith LOO predictor trained on Dー i.e., D without the ith point (X,, Y.). We might refer to the RF as both an algorithm (the learning procedure) and predictor (the learned function) for simplicity.
Many bagged algorithms, in particular those with bounded predicted values, can achieve absolute stability with both and converging to 0, as long and the number of bags B go to infinity.
3

---

However, the predicted value of the RF is in general unbounded (for regression tasks considered in this work), and we are more interested in another type of stability, investigated in (9) and called out-of-sample stability 3 For simplicity, we name it "stability." This notion of stability turns out to be important in validating jackknife prediction interval.
Definition 2 (Stability of algorithms).
For iid training and test data, algorithm A is (e, (e,6))stte -sttbble if
P PD
> E
for some E, e where D, D. f.X.f.f* are defined above.
We will establish this type of stability for the derandomized RF defined below, where the data- generating distribution is involved. To this end, will use the methods in (28), which aim provide absolute stability for bagged algorithms. Technically, we use such methods to first establish the "conditional stability" of algorithm with respect to given data.
Definition 3 (Conditional stability of algorithms). Conditional on D and X, an algorithm A is defined to (z, ( conditionalllyysttbble
PED. f(x))) <
for some e, 5 3 O, where D, X, S, f- are as defined above.
Once conditional stability is established for the derandomized RF algorithm, its stability can be consequently established by invoking
P (... ED.x (1),,x)
Stability of the derandomized RF provides the most essential ingredient for that of the practical RF, although the latter involves another type of stability, known as ensemble stability [18]. Ensemble stability justifies replacing the LOO predictor with the OOB predictor in (T). We may abuse the term "stability" in the following when the OOB, rather than the LOO, predictor is used.
3 Stability of random forests
3.1 Basics random forests
This work mainly considers using the RF to perform regression tasks, where the response Y E TR can unbounded. By construction, the RF predictor with B bags, denoted by RF B, bagged algorithm with the base algorithm being tree, and RF = Σ TREE,, where TREE, is the bth tree predictor, trained on the bth bag Tt, bootstrapped sample of the training D. The randomness in the tree predictor TREE originates from two independent sources: innate randomness & in the node splitting process and resampling randomness from the bag r. For the ith point, one can define the OOB / B B: Σ TREE, x I(i & ro), where I((.) denotes the indicator function, and B, = -' Iii $ r.). Define p = P(i E r) as the probability that the ith point included in bag r. Then it is clear that B, Binomial B, 1-p) for all i. We also denote rf and rf as the derandomized versions of RF, F and RF) respectively. Precisely, = (E,,(TTREE) and rf (TREE] $ r]. worth noting that, by definition, RF * RF for finite B, while rf rf the derandomized RF results from the aggregation of an infinite number trees. Since RF predictors are averages over tree predictors, the predicted values they output, given training set D, are bounded in [Ya)> Yoo]- where Y() and Y(m) the minimum and maximum of (Y....,, Yn). respectively. We also let Z, Y|| for all i, and denote the maximum Z(n) As result, we have that
RF predictor as RF
Irf't rf < Y (m))
Y()) & 2Z(
(2)
Remark 1. This is also true for RF B and RF for any finite B. In fact, this is a distinctive feature of the RF, irrespective of the node splitting rule. Other regression methods do not necessarily have such data-dependence bound. This observation helps to establish the conditional stability of the RF

---

Remark 2. Practically, when n is large, one might think that the bound 2 is crude. On one hand, look for bound valid for any finite n 2, then there is not much room for improvement for small n. On the other hand, we do expect that the typical stability of the RF can go beyond the finite-sample guarantee provided by 2 when n is big, which is consistent with the numerical results shown below. A more informative bound for large n is worth future investigation.
There are several quantities that are useful in establishing the RF stability; they can be calculated explicitly and are listed below. First, it is well known that
p P(i E r) = 1 (1 1/n)" 1 - 1/e O(1mn).
(3)
Actually, is monotonically decreasing for n >> 1. Second,
q = -Cov(Iff I[j E r}) = (1 1/n)²* - (1- (1-2/n)" = O(1/n),
(4)
as can be directly checked. Third, the moment generating function of B,
E [ R = (p + (1 (1-pp) ()e)))
(5)
In the following, we first perform the stability analysis for the derandomized RF (consisting of an infinite number of trees) and then extend the results to the practical finite case.
3.2 Derandomized random forests
The following theorem formalizes the conditional stability property for the derandomized RF, the proof of which a direct result of Theorem in [28], and is omitted here.
Theorem (Conditional stability of derandomized random forests). Conditional on training set D and test point (X, Y), for the derandomized random forest predictor rf we have that
Lin) p +
[x(() - Hx)/ =p. < 8(D.X) = z2n 1-p
(6)
2
(1
If (DD, X) 2 1, the statement is trivial, and we will focus on the case that 8(D, X) E (0, 1). We can now establish the stability property for the derandomized RF.
Theorem 6 (Stability of derandomized random forests). For iid training and test data and 0, the derandomized random forest predictor rf is stable with
BLZa (m)) ean 1- (1-p)2
(
+ 9 =V.
PD.
This result follows directly from the conditional stability 6 by averaging over D and X. There on n. On one hand, in order to make sense of
some freedom in choosing the dependence the word "stability," we do expect and to be small for large n. From (3) and (4), it is clear that the asymptotic behavior v is dominated by that of B| B|Z? // which can be tuned by manipulating e. For example, a matching convergence rate to 0 between and v might be desirable, and one can then set и = O (EL (m)
1,,l/))))) l/n)1/3) if the scaling of E[ZZ, = o(n) is known or can be
inferred. On the other hand, we can fix e to further investigate the relation between stability and the pewprrgenccein--oooaiiiie property of the RF. By 7 under the condition that ( 0 as
+ 00, one immediately comes to the conclusion that rf $t (X) - (X) converges to probability. Actually, stronger conclusion can be drawn under the same condition.
Corollary 1. For iid training and test data, we have
ED.xIIf((X) - (X))) <21
p
q
(8)
n
1 1- p
(1 - p)
Further assume that B[Y3] < co. Then we have
Exx([If(X) - Hx)(1)]] - 0 and rf(x) (x)( P. 0 0as c0.
(9)
5

---

Remark 3. The additional assumption that B| x is mild. Many commonly encountered random variables have light tail and thus a finite second moment, irrespective of the detailed information of the distribution in question. Note that the bound 2 itself can be crude, and our result expected to be valid even beyond this mild condition.
Remark 4. This result indicates that the difference is diminishing between rf and rf built on n and n 1 1 training data points, respectively. However, there no indication that the derandomized rf rX) itself will converge to anything. This idea inspires the proposal of Theorem 11
The proof of this result, as well as others below, will be deferred to the Appendix. So far, we have investigated the derandomized version of the RF, which is a limiting case and can be seen as consisting of an infinite number of trees, averaging out all kinds of possible randomness in the predictor construction process. In order to make the results more relevant to applied machine learning, the finite-B B analysis for the RF conducted below.
3.3 Finite-B random forests
We now consider the difference between RFB and RF We denote & = (f1,...,EB) EB) and r (Ti,...,TB) as the corresponding sources of randomness in B trees. We also consider conditional stability first and then move to the stability of RFB.
Theorem 7 (Conditional stability of finite-B B random forests). Conditional on training set and test point (X, for a random forest predictor RF B that consists of B trees, we have for ε >> 0 that
22 In (1)
1 n
|RFE(() (RFF(X)-RE((X)) > 21 21
PERID.
8
D, X
& 35 (,t,,,
B
where ó is short for o(D, X) defined in (6) and g(p, 6, B) 2(p + (1 p)
Next, we consider the case of iid data and investigate the RF stability by averaging out the randomness in data. Note that Zin) and 8 are random and depend on the data distribution, while we are interested
in probability bound for (RF((X) RF RF (X)) greater than a deterministic quantity, which is only a function of B and n. In this finite B case, the stability of RF cannot be directly obtained from its conditional stability as in the derandomized situation.
Theorem 8 (Stability of finite-B B random forests). Assume training points in set D and the test point (X, are iid, drawn from fixed distribution. For the random forest predictor RF consisting of B trees and trained on D, we have
PD. (RFFB())RFF)) -F > En.B) Vn,B.
(10)
where En -i Es and Va Ei_1% Ui. The pair of (E2, v2/ satisfies the derandomized
RF stability condition with X > Moreover, E1 E3 1 2XE In( 22 1/BB 21
2 + (z,) > 2 and 1/3 = g(p, 12, B) + 21P (P.) > 2E[2?,,
On a high level, the establishment of this theorem relies on two observations: (i) the stability of the derandomized RF, so that the difference |rf(X) - - (X)) is controlled, and (ii) the concentration of measure, so that the differences |RF (X)) rf(x) and |RF (X) - rf' (x)) are controlled. In order to make full sense of the word "stability,"" it is desirable that ER and Pa,B can converge to O. It is known that E[ Y < oc suffices to ensure E[ = o(n) 13). and hence the stability of the derandomized RF. Now in the finite-B B case, we need an additional distributional assumption to control the tail probability P(ZZ.,) >BLZZ,)) 1). It turns out that for typical light-tailed Y such
a tail probability will converge to 0 as n - oc. Technically, we can assume y to be sub-gamma g. Note that bounded and sub-Gaussian random variables are sub- gamma. Hence the sub-gamma assumption is not strong and can be satisfied by distributions underlying many real datasets.
Definition 4 (Sub-gamma random variables gamma (on the right tail) with parameters
A random variable W is said to be sub- where c > 0, In Ble -BDWT) B[e-(W- <
? for all (0, 1/c).

---

Prediction error 0OB error
0.8
0.2 044
Denalyy
Density
-10
-5
log10(Absolute Difference)
log10/Absolute Error)
Figure 1: Left: Density plots the log10 absolute difference |RF B (RF)(X) RF ( for 3000
OOB predictors RF V on 1000 test points. We let B 1000. The RF stability 10p seems to persist, even though Y follows the (heavy-tailed) standard Cauchy distribution. Numerically, we set B,,B 0.05 and calculated the maximum of the 0.95 quantile of the 3000 empirical distributions to have ê. 0.237. Right: Density plots of 1000 log absolute prediction errors
&
|Y
RF BX)]
and of 3000 log10 absolute OOB errors YY; RF (X,)). The similarity between the plots supports the idea that the OOB errors can be used to construct Pls.
Lemma 1. Suppose Y2 is sub-gamma with parameters (a² c) with 0, and (K)) clnn with a < c. For >> c/a, we have lim,--zo IP P(Z)))) XE 22 (m) =
above. If O, then y2 in fact sub- Gabssaassinn, and the tail probability can be controlled similarly. If 2 is upper bounded by some constant M the stability analysis even simpler. and there no need consider the tail probability all, we can use M² in place of (n) in the conditional stability of the RF and then take expectation with respect to data.
Remark 5. We have set
Example 1. Consider Y ~ Exp(1), the exponential distribution with scale parameter 1. known that Y² is sub-gamma with (o?, = (1, [), and E Zt,,] -
Hn with In(n + 1)), where 7 s 0.577 is Fuler's constant. Hence H lnn + o(I n), and straightforward calculation reveals that lim,--o PC (( AB[2),)) 0 as long
H, (7 + In In
7 n,
1.
From such results, taking this additional assumption, is indeed possible that both B, and Vn,B converge to
that the vanishing tail probability is not a stringent condition. By
Corollary 2. For the same setting as Theorem 8 suppose Y2 sub-gamma with parameters (o²,c) with O and E[Z[n,] a In with
Let X > c/a be a fixed number, and let B depend Then for E2 that satisfies both E2 w( ll////nnnn and o(1), and B Q21n² n). we have limm- B = limn-- Vn
It is worth noting that there are multiple ways to let En, B and V,, approach 0, as the dependence of 82, B, and even on n can all be manipulated. The point is that, theoretically, even the greedy can be stable with vanishing parameters. In practice, however, the stability of RF, seems to hold in broader situations where both the moment and tail assumptions on y can be relaxed.
3.4 Stability in practice and limitations of theory
We created a virtual dataset consisting of n 4000 points. We let Y be standard Cauchy random variable, which even without a well-defined mean. The feature vector X e R is determined as X = [0.5Y + sin(Y). y 3, ,IY > 0) + <1" where Ç is standard normal random variable. We used 3000 of the points for training and 1000 of them as test points. Using the randomForest package with default setting (except letting B 1000), we had output RF predictor RF B. We also aggregated corresponding tree predictors to have 3000 OOB predictors RF For each [3000], caleulated the absolute difference |RF (X) RF 3 (X) on 1000 test points to come up with

---

density plot for such a difference, shown in Fig. | We also calculated 1000 absolute prediction errors [X) that are incurred by RF B on test points, and 3000 OOB errors |Y; - RF; each incurred by an OOB predictor RF & on its OOB point (X, Y.). The computation can be done within a few minutes on laptop. The density plots of these two kinds of errors are also shown in Fig. []] This example shows that the RF stability can be present beyond the realm guaranteed by the light-tail assumption. As mentioned above, this is because the bound (2) can be conservative when n is large. We hope our results can inspire future study towards more informative bound. Also, the similarity between the prediction error and the OOB error this heavy-tail case indicates that the RF-based Pis analyzed below find more applications in practice than justified by the current theory.
4
Random-forest prediction intervals
4.1 Comparison with related methods
With the stability property of the RF, it is possible to construct PIs with finite-sample guaranteed coverage. Recent years have witnessed the development of distribution-fres predictive inference [1] with the full 33 27 split (24 31 20), and jackknife+ 3 32 conformal prediction methods being three milestones. The full conformal method is computationally prohibitive when used in practice. The split method greatly reduces the computational cost but fails to thoroughly extract the available information of training data. The jackknife+ (J+) method maximizes the usage of data at a computational cost in between those of full and split methods. In [8], jackknife--afffer-ooottra (J+aB) was proposed for bagged algorithms to achieve the same goal as in J+, while the training cost can be further reduced. However, the number of bags B is required to be Binomial random variable, which might seem unnatural. It turns out that by further imposing the assumption of ensemble stability (which is essentially the concentration of resampling measure), J+aB can still have guaranteed coverage with a fixed B. Ensemble stability is defined for bagged algorithms. It measures how typical bootstrap sample is, and is different from the algorithmic stability that quantifies the influence of removing one training point. If algorithmic stability is also imposed, then not only J+aB, but also jackknife can provide guaranteed coverage, which is otherwise impossible 29 3).
Conceptually, the J+ approach and its variants under stability conditions are particularly relevant to this work. As the stability we establish for the RF contains both ensemble and algorithmic components, we will generally refer to the J+aB method with both ensemble and algorithmic stability as J+aBS and the jackknife method with algorithmic stability JS. Our method might be best described as aarrkkiiif--atter-boottraa witt-stabilitt (JaBS)" tailored for the RF, which is different from both JS and J+aBS. Our method requires the least effort of computing as only one output predictor is needed, while all others require at least n output predictors.
There also exist RF-based PIs 17 35 that are essentially of the jackknife after-foett-rstee and almost identical to ours practically when is small and n equals the size of typical dataset. However, without stability, there is, in general, no guarantee for the coverage of such Pls. although the asymptotic coverage
(JaB) type
a can be established based on strong assumptions (55 We take advantage of the stability of the RF algorithm to establish the lower bound of coverage in Theorem DaeeemDDell below. An upper bound is established in Theorem I0 with an additional mild assumption. We also propose a weaker assumption for asymptotic coverage in Theorem
We compare these relevant methods to ours in Table algorithm for all methods and (c, v/) is general pair of stability parameters. We define an ( R In [R.). I R and g/ ) as follows. Given {ai....,anh ).
I and Table
2 where the RF is set as the working
qn an tas} atta (a;) = the [(1 an + 1) smallest value of an).
la = the [[1 on.nn-nnnnn smallest value of {ai...., ",))
In (a.) = the |a(n + 1) smallest value of (aI...... J,
where I:] is the floor function. Let R1.00 |Y; - RF RF (Xx) be the LOO error, where RF is trained without the ith training point, and by definition RF RF)
In Table D we list the corresponding PI constructed from each method and the output predictors of each method. The number of output predictors directly reflects the computational cost. It is
8

---

Table Methods to construct prediction intervals using random forests: computational cost
Method
Output predictors
Prediction interval for future Y
J+ 3
RFg B , E [n]]
I9. (X) R,-00), gz (RF + R[-00
J+aB 18
RF B: i [n]
9n. (RF (XX) R2), 4r (RF) (X) R.j]
JS 3
RF B and RFB i [n]
RF + [ (R..00 +
J+aBS [8]
RF B:
[n]]
9n.. ( (RF)) B RR}) E, F. (RF) (X) + R.) + E]
JaB
RF
RFB(X) i (R.] [17
(FB(X)
(R.) [35]
Ours (JaBS)
RF
RF (FB(X) I In.a [,, + (Theorem
RF RFB(X (X) + 9n,a R (Theorem
RF (X) I In,a [2, (Theorem 11
[R,)
Table Methods to construct prediction intervals using random forests: theoretical coverage
Method
Theoretical coverage
Additional conditions
J+ B
> 2a
None Binomial B
J+aB [18
> 1 - 2a
IS 3
S - a (vv))
Stability (algorithmic)
J+aBS
18
> 1
((V))
Stability (ensemble algorithmic)
JaB
No guarantee
[35
Strong (additive model, consistency of RF predictor)
Ours (JaBS)
3 - a (VvD)
Stability (Theorem 9)
$ - a + n+I O(V))
+ Distinct residuals (Theorem 10
1
+ Uniformly equicontinuous CDF of RFB(X)
and vanishing E, (Theorem
worth noting that acquiring the LOO predictor RF B needs substantial computation. In packages like randomForest, aggregating tree predictors to obtain the OOB predictor RF); also needs extra be obtained immediately by calling the predict() function. The fact that the value of RF (X) on a test point is not needed further reduces the computational cost JaB and our method, which only need one output RF predictor, and are more favorable computationally.
computation. However, the predicted value RF
! (X;)
In Table list the coverage of the PI constructed from each method, as well as the additional conditions (beyond iid data) needed to achieve the coverage. Note that J+ does not require any additional conditions to achieve the coverage lower bound 2a, but J+aB requires that the number of trees B be Binomial random variable. For JS, J+aBS, and our method, stability is needed to O(VD). With additional mild assumptions, the coverage upper bound and asymptotic coverage of our method can be established. However, there is no guarantee of coverage for JaB without strong assumptions.
achieve the coverage lower bound
In summary, our theoretical work provides a series of coverage guarantees to a computationally feasible method for constructing PIs based on the RF algorithm. In the following, will establish the lower and upper bound of coverage, as well as the asymptotic coverage.
4.2 Non-asymptotic coverage guarantees
Theorem 9 (Coverage lower bound). Suppose the RF predictor RF satisfies the stability condition as Theorem K Then we have for a test point (X,Y) that
IP E RF + on.o En.B)) a- - 22/12 22/13.
(11)
This result is established by starting from the analysis of imaginary extended dataset D) DO {(,,)), where the test point is assumed to be known. We denote (X, Y) as (Xn+1. Bost1.Yno Yo+1) for
>/ convenience. For all points in D. consider the derandomized RF predictor rf that is built on data

---

11. One can then define the OOB error 7; = |Y;-rfff // Since
points without the ith point in D, i [n+ all data are iid, we have that P( & 9n.o (f:)
a, where on is the [(1 - a) + 1
smallest value of (fi...., F.... Next, notice in = |Y++1 - .t (iatt)) 1) (Xn+1)) = 11 xf(nn+1)))))))
by the definitions of rf (x+1)) and rf. By concentration of measure, rf(XXn+ can be approximated by B (Xn+1)), which is desired.
RF (-xnn)+ and thus Fn+ can be roughly replaced with |Y,+1 RF
Then by stability of rf, (7r] can be approximated by {r; = |Y; - - (x,)) Although {ra} is still unavailable in practice, by applying the idea of concentration of measure again, (r.) can be further
approximated by R. which is accessible given D. Eventually, we can bound | - RF (X
in terms of { [. The approximations are accounted for by the stability parameters in Theorem
If we further assume that there are no ties among ( [n+ 1], a typical case when continuous, then we can also establish the upper bound of coverage.
Theorem 10 (Coverage upper bound). Suppose there are no ties in (fi), i E [n + 17, and the RF
predictor RF n satisfies the stability condition as in Theorem 8 Then
P(Y RF (X) I qn,a En,Bl) < a n 1
+ 1/2 + 2/12 + 2/13.
(12)
The upper bound can be established because if there are no ties among fI...., Fn+1 then PP & In,a (Fi)) & 1 _
n+1. The apparent symmetry between the lower and upper bound originates from the fact that they both are established by using the RF stability once and the concentration of
measure twice. Note that this idea can be applied to intervals for an arbitrary stable algorithm in exactly the same way, providing complement to the lower bound for JS intervals established in [3].
Corollary 3 (Coverage upper bound for trained iid data points and f be the LOO predictor without the ith point. Suppose f is stable with P(I f-((x)
intervals). Let f be predictor
e) & U, and the L.00 errors are distinct on the extended training set thut includes an iid test point (X.Y). Then we have P (YY j(x) & yn -s}) &
1 +
1
2/V.. where Ts are the LOO errors on the original training set.
n+1
4.3 Asymptotic coverage guarantee
As shown above, the stability parameters (En,B, Pn,B) can vanish when n - cc. It is reasonable a in this limit, is consistent with numerous empirical observations 17 35 However, to achieve this goal, it seems that more assumptions are unavoidable. In 35,, the guaranteed coverage of the JaB method is established by assuming that RF converges to some fo(X) in probability as n - 00, where fo is the true regression function of an additive model that generates the data. We show that this can be done under weaker conditions.
to expect that IP(Y' RF B (X) + qa RR)) -
Theorem 11 (Asymptotic coverage). Denote Fn as the CDF Y - RF RF (X) Suppose ( [ is uniformly equicontinuous for some nig Then P(Y RF (X) + (n (R.)) 1 a as oD Theorem 10 and Corollary P are satisfied.
when conditions in Theorem 9
B that are trained on 1 points to approximate those from RFB. trained on n points, we only need this approximation to be exact asymptotically. There is no need for RF g itself to converge to anything. This is one major conceptual difference between our work and [55, and is in this sense that our assumption is weaker. Practically, this kind PI is recommended as it does not involve (E,, Mn,B), and has great performance numerous datasets.
Remark 6. Intuitively, using errors from RF):
5 Conclusion
In this work, for the first time, we theoretically establish the stability property of the greedy version of random forests, which is implemented in popular packages. The theoretical guarantee is based on a light-tail assumption of the marginal distribution of the squared response Y However, numerical evidence suggests that this stability could persist in much broader situations. Based on the stability property and some mild conditions, we also establish finite-sample lower and upper bounds of coverage, as well as the exact coverage asympiotically, for prediction intervals constructed from the out-of-bag error of random forests, justifying random forests as an appealing method to provide both point and interval prediction simultaneously.
10

---

Acknowledgments and Disclosure of Funding
Much of the work was completed while Yan Wang was PhD student in the Department of Statisties at Iowa State University. This research was supported in part by the US National Science Foundation under grant HDRPPOS 19-34884.
References
[1] Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 16(4):494-591, 2023.
[2] Arthur Asuncion and David Newman. UCI Machine Learning Repository, 2007.
[3] Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, (::86) 507, 2021.
[4] Dimitris Bertsimas, Jack Dunn, and Ivan Paskov. Stable classification. The Journal of Machine Learning Research, 23(1):3401-13453 2022.
[5] Gérard Biau. Analysis of random forests model. The Journal of Machine Learning Research, 13())10633-1055, 2012.
[6] Gérard Biau, Lue Devroye, and Gäbor Lugosi. Consistency of random forests and other averaging classifiers. The Journal of Machine Learning Research, 9()):2015-2033, 2008
[7] Gérard Biau and Erwan Scornet. A random forest guided tour. Test, 25:197-2211 2016.
[8] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
[9] Olivier Bousquet and André Elisseeff. Stability and generalization, The Journal of Machine Learning Research, 2:499-526, 2002.
[10] Leo Breiman. Random forests. Machine Learning, 45(1):5-32, 2001.
[11] Thomas F Brooks, D Stuart Pope, and Michael A Marcolini. Airfoil Self-Noise and Prediction. National Aeronautics and Space Administration, Office of Management, 1989.
[12] Andrea Coraddu, Luca Oneto, Aessandro Ghio, Stefano Savio. Davide Anguita, and Massimo Figari. Machine learning approaches for improving condition based maintenance of naval propulsion plants. Proceedings of the Institution of Mechanical Engineers, Part M: Journal of Engineering for the Maritime Environment,
153, 2016.
[13] José R Correa and Matías Romero. On the asymptotic behavior of the expectation of the maximum of iid random variables. Operations Research Letters, 49(5):785-786, 2021.
[14] Misha Denil, David Matheson, and Nando De Freitas. Narrowing the gap: Random forests in theory and in practice. In International Conference on Machine Learning, pages 665-673. PMLR, 2014.
[15] Peter Downey. Distribution-fres bounds the expectation of the maximum with scheduling applications. Operations Research Letters, 9(3): 189-201, 1990.
[16] Francesca Grisoni, Viviana Consonni, Marco Vighi, Sara Villa, and Roberto Todeschini. Inves- tigating the mechanisms of bioconcentration through QSAR classification trees. Emvironment International, 88:198 105- 2016.
[17] Ulf Johansson, Henrik Boström, Tuve Löfström, and Henrik Linusson. Regression conformal prediction with random forests. Machine Learning, 97:155- -76, 2014.
[18] Byol Kim, Chen Xu, and Rina Barber. Predictive inference is free with the jackknife+-after bootstrap. Advances in Neural Information Processing Systems, 33:4138 138-41499 2020.
[19] Aryeh Kontorovich. Concentration unbounded metric spaces and algorithmic stability. In International Conference Machine Learning, pages 28-36. PMLR, 2014.

---

[20] Jing Lei. Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution free predictive inference for regression. Journal of the American Statistical Associ- ation, 1094-23)00441111,, 2018.
[21] Andy Liaw and Matthew Wiener. Classification and regression by randomForest. R News, 2(3):18-22 2002.
[22] Yi Lin and Yongho Jeon. Random forests and adaptive nearest neighbors. Journal of the American Statistical Association, 101(474):578-59) 2006.
[23] Andreas Maurer and Massimiliano Pontil. Concentration inequalities under sub-Gaussian and sub-exponential conditions. Advances in Neural Information Processing Systems, 34:7588-7597, 2021.
[24] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pages 345-356. Springer, 2002.
[25] Erwan Scornet. Random forests and kernel methods. IEEE Transactions on Information Theory, 6283):1485-1500, 2016.
[26] Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests. The Annals of Statisticx,
2015.
[27] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008.
[28] Jake Soloff, Rina Foygel Barber, and Rebecca Willett. Bagging provides assumption-free stability. arXiv preprint N..iv:2301.120000 2023.
[29] Lukas Steinberger and Hannes Leeb. Conditional predictive inference for stable algorithms. The Annals of Statistics, (113):290-31,, 2023.
[30] Cheng Tang, Damien Garreau, and Ulrike von Luxburg. When do random forests fail? Advances in Neural Information Processing Systems, 31, 2018.
[31] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian Conference on Machine Learning, pages 475-490. PMLR, 2012.
[32] Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74(1):9-28, 2015.
Learnigg in a Random [33] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning World. Springer Science & Business Media, 2005.
[34] I-C Yeh. Modeling of strength of high-performance concrete using artificial neural networks. Cement and Concrete Research, 28(12):1797-1) 1998.
[35] Haozhe Zhang, Joshua Zimmerman, Dan Nettleton, and Daniel Nordman. Random forest prediction intervals. The American Statistician, 74(4):392 406, 2020.
12


Reviews:
[{"review_id": "yLrIbVuyJf", "reviewer": "Reviewer_1UHc", "summary": "The paper presents new and strong set of results on stability of (greedy version of) random forests. Theoretical (resp. numerical) evidence is provided to support stability for light-tail (and heavy-tail) assumptions on marginal distribution of squared response. New finite sample upper and lower bounds are provided for prediction intervals constructed from OOB effort of random forests. The paper can be regarded as a demonstrative work that justifies the merit of random forests for both point and interval prediction. \n\n\n\n", "questions": "Please see my suggestions above. ", "limitations": "Everything on this front seems reasonable. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The style of results and overall content of paper are very appealing. I like the way in which stability and prediction interval results were informally stated first and then rigorously discussed later. A clear review of algorithmic stability concepts helped me understand the proof ideas.  \n\n", "weaknesses": "-- I think the writing can be slightly improved by articulating the use of absolute stability results for bagged algorithms. \n-- The transition from derandomized version of RF to finite-B case through the route of conditional stability analysis is a bit abrupt and needs more explanation, particularly with regard to concentration of measure. \n-- The limitation/extension of theory to heavy-tailed case is interesting but some comments about the key bottlenecks in the proof technique that would need to be overcome to achieve such a generalization would make the contribution stronger. Also where does the theory break? The experimental results are not very clear in this regard. \n-- On the prediction interval part, Table 1 can be enhanced and repositioned to include computational advantages as well. Finally, the discussion around “jackknife-after bootstrap-with-stability (JaBS)” is a bit hard to follow since the discussion on J+aB and J+aBS is intertwined with the intuition on how subsequent results in the paper build on stability results – it is desirable to streamline this discussion a bit. \n-- please consider citing and discussing relevant work in OR on optimal classification/prescriptive trees by Bertsimas and co-authors as well as their work on Stable Classification. Your approach and focus is different, but given the stated goal of putting the stability of random forests on a stronger footing, it may be worthwhile to make a connection.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We gratefully thank the reviewer for the positive comments of our work, and the suggestion of a “Strong Accept.” The reviewer states that “the paper can be regarded as a demonstrative work that justifies the merit of random forests for both point and interval prediction.” This statement contains exactly the message we want to convey to the machine learning community: for typical tabular datasets, random forests can provide justified interval prediction at almost no extra computational cost, in addition to good point prediction. We believe our theoretical results in this work can have a strong impact on machine learning practice in various fields. In the revised manuscript, we will fully address the points raised by the reviewer to further improve our work. Below are our point-by-point responses to the reviewer’s “Weaknesses” comments.\n1. “Articulating the use of absolute stability results for bagged algorithms.” This kind of stability is addressed in Ref. [25] and serves as an important foundation of our work. In this case, stability can be established with the only requirement that the base learner outputs bounded predicted values, and the data distribution is irrelevant. This can be appealing in certain tasks such as 2-class classification, where $Y$ itself is naturally bounded. One can use logistic regression, the tree predictor, or any other learning algorithm with bounded output as the base learner, and by aggregating results obtained on bootstrapped samples, a stable predictor can be achieved, in the sense that arbitrarily removing a single training data point will not much influence its prediction on a future data point. (It is worth stressing that in general regression tasks, $Y$ is unbounded, so requiring base learners to output unconditionally bounded predictive values can be a problem. However, inspired by the underlying idea of absolute stability, we in this work address this problem by first considering conditional stability and then averaging over the data distribution.)\n2. \"The transition from derandomized version of RF to finite-B case...needs more explanation.\" The derandomized version can be effectively seen as the $B=\\infty$ case. That is, each bootstrap sample is drawn with equal probability an infinite number of times, resulting in the population mean $\\mathsf{rf}(x)$ of tree predictors for any future $x$. In practice, $B$ is finite, and each bootstrap sample is drawn with equal probability a finite number of times, resulting in the sample mean $\\mathsf{RF}(x)$ of tree predictors. The difference between $\\mathsf{rf}(x)$ and $\\mathsf{RF}(x)$, when conditioned on training data, can be quantified by Hoeffding's inequality, a standard concentration inequality. This approach was also used in previous works, c.f. Refs. [15], [25].   \n3. The issue of heavy-tail distributions and bottlenecks of our theory. Our proof mainly relies on the upper bound $2Z_{(n)}$ of the difference between $\\mathsf{rf}$ and $\\mathsf{rf}^{\\backslash i}$ when conditioned on training data. It is a valid bound for many variants of random forests and for any training set with size no less than two. However, it is unclear whether this bound is tight in general. Developing our results on a possibly crude bound leads to the conclusion that the random forest is stable when $Y$ is not heavy tailed. Please note that this is a SUFFICIENT, rather than necessary, condition for random forest stability. Numerically, we found that even for heavy-tailed distributions, the stability seemed to persist. This indicates that there might exist a more informative bound, at least for non-pathological data generating distributions and for datasets of typical size. Once such an informative bound is established, our theory can be modified to more thoroughly explain the experimental result. Our work serves as an important initiation point for research in this direction.\n4. \"Table 1 can be enhanced and repositioned to include computational advantages.\" We will revise the manuscript accordingly. Also, with an extra one page for accepted papers, we expect to be able to provide the information of guaranteed coverages of those algorithms as well. \n5. The discussion around JaBS is hard to follow. We are sorry for the unclarity. The length limit forced us to write it this way. We will streamline this discussion in the revised manuscript as suggested.  \n6. Bertsimas and co-authors's work. Thanks for introducing this line of work to us. It is not only relevant, but also inspiring. For example, combining the JMLR paper \"Stable Classification\" and the \"stability by bagging\" idea seems to immediately suggest the method of \"importance aggregating.\" That is, we aggregate the best-performing base learners with more weights, which are trained on some \"good\" bootstrap samples. This can be a potential topic. We will discuss and cite the relevant papers.\n\nWe hope we have fully addressed the points raised by the reviewer, and we appreciate the reviewer's valuable suggestions."}, {"review_id": "kx7CwEiGpf", "reviewer": "Reviewer_sZkt", "summary": "In this paper the authors considers the issue of stability of the often used in practice Random Forest algorithm and provide theoretical bounds on the $\\varepsilon$-stability upto an order of $O_{\\mathbb{P}}(|Y|^2_{(n)}/n)$ (i.e. the largest in magnitude observation) when fitting the method with $n$-iid sample points $(X_i,Y_i)$. A light tailed assumption on $Y^2$ thereby yields suitable control over the asymptotic behavior of $|Y|^2_{(n)}/n$. Further, the stability results are used to derive $n$-dependent lower and upper bounds (under increasingly more assumptions) for the coverage probability of prediction intervals constructed from out-of-bag error of random forests. In comparison to many other results in the literature, this paper works with a practical version of random forests.", "questions": "If one assumes that $Y=f(X)+\\eta$ for $\\eta \\sim F$ for some suitable light tailed distribution and $f\\in \\mathcal{F}$ in some classical function class, can one have modified rates for stability bounds depending on $F$ and $\\mathcal{F}$?", "limitations": "None noted", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. In comparison to many other results in the literature, this paper works with a more practical version of random forests.", "weaknesses": "1. It was not clear whether the stability bounds were optimal or could be improved.\n2. The presentation usually benefits from working under a single set of assumptions instead of increasingly more assumptions (however this is a minor point).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for considering that \"this paper works with a more practical version of random forests.\" We also believe the most important point of our results is that they apply to the practical version of random forests, and are thus strongly relevant to applied machine learning. We theoretically prove in this work that random forests can be used to provide justified prediction intervals at almost no extra computational cost, which is appealing particularly for tasks where uncertainty quantification is desired and the computing resource is limited. Below are point-by-point responses to the reviewer's \"Weaknesses\" and \"Questions\" comments.\n1. \"It was not clear whether the stability bounds were optimal or could be improved.\" We agree with the reviewer on this point. On one hand, our bound is valid for a training set that contains at least two data points, and it seems that there is not much room for further improvement in the most general situation. On the other hand, for a dataset of typical size in practice, and for non-pathological data generating distributions, our numerical experiment (Sec. 3.4 of the manuscript) seems to suggest that the current bound could be improved. One of our research goals is to find a more informative bound that holds at least for TYPICAL cases, while the current bound we use holds for the WORST case. By providing the first stability result for random forests, we hope our work can draw the attention of more researchers to work towards a more satisfactory bound. \n2. \"The presentation usually benefits from working under a single set of assumptions instead of increasingly more assumptions (however this is a minor point).\" We agree that stating all assumptions first makes the presentation of results clearer. Our structure basically follows previous works such as Ref. [17]. We start with the stability result (Theorem 7) and the coverage lower bound (Theorem 8), which hold under minimal assumptions and already carry sufficient useful information to guide machine learning practice. In many works on distribution-free  prediction, such as Refs. [3], [15], the aim is to establish the lower bound. Statisticians such as the authors of Ref. [17] also pay much attention to the upper bound, which cannot be obtained without more assumptions. Such assumptions are mild, and can usually be satisfied by typical data distributions. Hence we also include this in our work (Theorem 9). Lastly, in order to compare with a previous asymptotic result on the coverage of random-forest prediction intervals in Ref. [32], we also derive a similar one (Theorem 10). This part is somewhat independent from the stability result and non-asymptotic lower and upper bounds. The assumptions made in Theorem 10 are also less intuitive than those made in Theorems 7-9. To highlight the most important contributions, we decided to state the assumptions in the present way. We thank the reviewer and hope our structure can be considered as reasonable.\n3. If the true model is known, \"can one have modified rates for stability bounds?\" Thanks for raising this insightful question. While our theory provides a sufficient condition for stability of random forests, we do not expect its optimality in all cases. If we do know the true model, then we might perform some other analysis by fully taking advantage of the information about the data distribution and the function class. As long as one is able to come up with a more informative bound for $|\\mathsf{rf}-\\mathsf{rf}^{\\backslash i}|$, the convergence rate can be modified. In the present work, our focus is the model-agnostic case. Again, our work serves as an important initiation point towards research in random forest stability, and we leave the quantitative improvement of the present work as future study.\n\nWe hope we have fully addressed the reviewer's comments, and have made clearer the qualitative importance and practical relevance of our work. "}, {"review_id": "f0ZA7UnDmU", "reviewer": "Reviewer_mxxw", "summary": "Random forests are one of the most used Machine Learning methods. Its standard variant (for regression) takes the following form. GIven a random sample $D=(X_i,Y_i)_{i\\leq n}$ of covariate/response pairs, one takes $B$ bootsrapped samples from $D$ and trains a tree regressor on each boostrapped sample (using one of many possible criteria). The estimated regression function $RF(x)$ is the average of the $B$ tree regressors on $x$. \n\nTheorem 1 of the present paper is a kind of stability property for $RF$ vis a vis its \"out-of-bag\" variant $RF^{\\backslash i}$. Here $i\\in [n]$ and $RF^{\\backslash i}$ is the version of $RF$ where bootstrapped samples not containing the $i$-th sample point are discarded. The paper then shows that one can use this stability property to build predictive intervals from the \"OOB residuals\" $|Y_i-RF^{\\backslash i}(X_i)|$. Theorem 2 proves that these intervals, after a slight enlargement, provide good coverage at near-nominal-levels, whereas Theorem 3  gives exact $1-\\alpha$ coverage in the limit, under suitable assumptions. \n\nOne of the main assumptions the authors impose for these last results is that the response variables be light-tailed. However, a small set of experiments suggests that similar properties would hold even for very heavy tailed covariates.\n\nThe present paper joins string of recent works dealing with uncertainty quantification for ML methods without resorting to a calibration sample (in which case one could use conformal prediction). The authors argue that main distinguishing feature of Theorems 2 and 3 is that their predictive intervals are much less demanding computationally. As computing the OOB predictors comes as a byproduct of the RF computations. By contrast, related work (eg. on jacknife type estimators) require the regression method to be rerun several times on leave-one-out samples. \n\nLet me also say a few words about proofs. The idea is to first explore the $B\\to +\\infty$ limit of $RF$ and $RF^{\\backslash i}$ and prove stability in that setting, via arguments from arXiv:2301.12600. ", "questions": "1) It seems from reading arXiv:2301.12600 that $Z_{(n)}$ could be replaced with the range $\\max_{1\\leq i<j\\leq n}|Y_i-Y_j|$ throughout the analysis. Is this true? One advantage of the range is that it is centered. \n\n2) The authors obtain what is called a \"marginal coverage\" guarantee: if one single extra point $(X,Y)$ is given, then everything work. A stronger guarantee would be this: letting $\\mu$ denote the distribution of $(X,Y)$\n\n$$P\\{\\mu\\{(x,y): |y-RF(x)|\\leq  q_\\alpha(R_i) + \\epsilon\\}\\geq 1-\\alpha-\\nu.$$\n\nCould this stronger guarantee be obtained via the present methods. \n\n3) As noted in a previous field, computing how large $B$ needs to be seems to be a pressing problem. Checking the bound in Theorem 12 in arXiv:2301.12600 (v2), it seems that the present paper skips the variance-based proof for the variability of $RF_B$ and goes straight to the range-based bound. This means that the parameter $\\epsilon_{n,B}$ in Theorem 2 is a sum of two parts: one that would be there even if $B=+\\infty$, and a second term that comes from finite $B$. It seems to me, however, that this second term could be controlled via suitable empirical concentration inequalities such as Lemma E.4 in https://arxiv.org/pdf/2212.09900.pdf: in practice, this would mean that the second error term just mentioned could be controlled for finite B. This, in turn would make the method a bit heavier, but more quantifiable. Could the authors comment on this?\n\n4) Regarding Theorems 3 and 10: it would seem that a sufficient condition for the theorem to hold is that \n$Y-\\mathbb{E}[Y\\mid X]=:\\eta$ satisfies:\n$$\\lim_{h\\searrow 0}\\mathbb{E}[\\sup_{x,y\\in\\mathbb{R}\\,:\\,|x-y|\\leq h}|F_{\\eta\\mid X}(x)-F_{\\eta\\mid X}(y)|]=0.$$\nwhere $F_{\\eta\\mid X}$ is the conditional cdf of $\\eta$ given $X$. This kind of condition is very natural: eg. it holds if the density of $\\eta\\mid X$ is uniformly bounded. Would it indeed be sufficient to require this condition on $\\eta$?", "limitations": "There is no explicit discussion of limitations, nor do I think one would be necessary.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "As noted above, the paper obtains a lightweight method to compute (nearly-)valid prediction intervals from random forests, which are often used in practice. This means that the result is significant (though see the next field). It also seems to be original. The exposition is fairly clear. ", "weaknesses": "* Mathematically, it seems that much of the work behind the paper comes from arXiv:2301.12600 by Soloff, Barber and Willett. \n* The nonasymptotic Theorem 2 is a bit unsatisfying in that both the interval length and the coverage are subject to errors that are hard to quantify in practice (still, since people will use RF anyway, it's nice to have some result of this kind). \n* The results do not give a good bound on how large $B$ needs to be in order for the method to work well. This is clearly related not just to the maximum $Z_{(n)}$, but to how small an error one wants to allow when defining the interval.  \n* One very minor comment: Theorem 3.4 from arXiv:2301.12600 (quoted in line 163) should be Theorem 9 (the numbering seems to have changed from v1). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments on our work. In particular, we are happy that the reviewer considers that \"the result is significant\" and \"original,\" obtaining \"a lightweight method to compute (nearly-)valid prediction intervals from random forests, which are often used in practice.\" The most important message in our work is indeed that random forests can be used to construct justified prediction intervals at almost no extra computational cost. Below are our point-by-point responses to the reviewer's comments in \"Weaknesses\" (W) and \"Questions\" (Q).\n1. (W1) We agree that Ref. [25] (arXiv:2301.12600) serves as an important foundation of this work. However, there are two key developments in this work to achieve the random forest stability. First, we consider regression problems where the base tree learner does not output unconditionally bounded predictive values. This is tackled by introducing the conditional stability property first and then averaging over the data distribution. As such, we arrive at the out-of-sample stability as discussed in Ref. [3], which is different from the absolute stability (Definition 4 in the updated version of Ref. [25]). Definition 11 in the updated version of Ref. [25]  is like our definition of conditional stability where a data-dependent range is involved. Second, in our work, each $B_i$, the number of times the $i$th data point is not included in a bootstrap sample, is random, while in Ref. [25], it is fixed to be a constant. Our setting is technically trickier, as the lack of a universal constant lower bound for $B_i$ makes the analysis more difficult and results in a slower convergence rate for the $|\\mathsf{rf}^{\\backslash i}-\\mathsf{RF}^{\\backslash i}|$ term. \n2. (W2) We also agree that the stability parameters can be hard to quantify in practice. Nonetheless, the most important point of our work is to qualitatively prove that the practical version of random forests is stable under mild conditions, and we hope our work will inspire more research in this direction. We thank the reviewer for considering that \"it's nice to have some result of this kind.\"\n3. (W3) We thank the reviewer for this insightful question. On one hand, the current framework of analysis involves many factors: the data distribution, the dependence of $\\varepsilon_i$ and $\\lambda$ on $n$, etc. For such relatively simple situations as $Y$ is bounded, from Corollary 5 in the Appendix, we can conclude that $B$ does not need to be extremely large. A sublinear dependence on $n$ suffices. However, there are six terms in $\\varepsilon_{n,B}$ and $\\nu_{n,B}$, and there is some freedom in choosing each term's convergence rate, which may also depend on factors other than $B$, such as the dependence of $\\varepsilon_1$ on $n$. Rather than look for some \"optimal\" convergence rate, we focus on presenting the important qualitative result that $\\varepsilon_{n,B}$ and $\\nu_{n,B}$ can converge to 0 under mild conditions. On the other hand, the current framework of analysis itself is not necessarily the \"optimal\" one. For example, we have required $\\varepsilon_1=\\varepsilon_3$ in our proof for simplicity, but doing so removes a degree of freedom. Moreover, all the analysis in this work is built on the upper bound $2Z_{(n)}$ for the difference between $\\mathsf{rf}$ and $\\mathsf{rf}^{\\backslash i}$. This bound could be crude for a typical dataset, as hinted by our numerical results in Sec. 3.4. So, at this stage, we focus on the qualitative aspect of our work, leaving the quantitative improvements as future study.\n4. (W4) Thanks for pointing out this change in the updated version of Ref. [25]. We will revise our manuscript accordingly.\n1. (Q1) Yes. $\\max_{i<j}|Y_i-Y_j| \\leq 2Z_{(n)}$, both serving as a measure of the spread of $Y$. We think your statement that \"One advantage of the range is that it is centered\" refers to that $Y_i-Y_j$ is centered. Please let us know if this is not what you mean. The main reason we use $Z_{(n)}$ is that in some cases, the scaling or even the exact expression of $\\mathbb{E}[Z_{(n)}^2]$ is handy to use, thus simplifying the analysis. \n2. (Q3)  We are not completely sure about the LaTeX expression, which seems to address the coverage probability conditioned on the training set. If so, then this is a very insightful question with strong practical relevance. Our theory basically follows the idea of conformal prediction, and thus cannot provide guarantees conditional on the training set. We note there are several recent works that try to generalize the marginal coverage to various kinds of conditional coverages such as arXiv:2305.12616. We hope in the future some conditional coverage of random forest prediction intervals can be established. \n3. (Q3) Thanks very much for raising the point of using a potentially sharper concentration inequality in our analysis. We believe the situation is like the choice between variance tensorization (Theorem 2.3 in Ramon van Handel's notes \"Probability in High Dimension\") and bounded difference inequalities (Corollary 2.4, ibid.). Our choice of using $2Z_{(n)}$ as the bound corresponds to the latter, which is technically more tractable when a precise calculation of the variance is not easy. If there is a way to calculate the variance, of course a better bound can be established. (But at this moment, we are unaware of any such results.)\n4. (Q4) The asymptotic coverage that we establish concerns the continuity property of the CDF of the residual $|Y-\\mathsf{RF}(X)|$, and there is no requirement for the CDF of $Y-\\mathbb{E}[Y|X]$. As $Y-\\mathsf{RF}(X)$ does not necessarily converge to $Y-\\mathbb{E}[Y|X]$ in probability, the CDF of the latter is not relevant. \n\nWe greatly thank the reviewer for a careful reading of the technical details, useful suggestions, and many insightful questions.     "}, {"review_id": "vtI4XIlhub", "reviewer": "Reviewer_BF9X", "summary": "This work studies the random forests stablity for regression problem, and the authors presents theoretical analysis on the upper and lower boudns for the coverage probability of prediction intervals constructed from the out-of-bag error of random forests. The theoretical guarantee is based on a light-tail assumption of the marginal distribution of the squared response. \n\n------------------after response---------------------------------\n\nAfter reading the authors' response, I do not think the authors answer my concerns, in particularly for the novelties and significances. \n\nAs a theoreical work, it is very important to evaluate from theoretical novelties and techniques, while I find some inremental results based on well-known techniques.\n\nI do not find any experiments, and I do not know why the authors could claim that \"Our work applies to many variants of random forests ... which makes it particularly relevant in theory and practice\".", "questions": "1) The problem is not very clear. The authors should first present the studied problem, i.e. the original ranfom forests for regression, or randomf forest interval, or  prediction intervals constructed from the out-of-bag error of random forests. It is very confused to understand the main contributions in the current submission and relevant work. For completeness, it would be better to present the detailed algorithm, rather than finding some other research work for other readers.\n\n2) The main conclusions are not clear. The main contribution of this work is the stability of random forests in Theorem 1. Generally, a theoretical work concerns seriously the convergence rate of stability, and how tight of this rate. It would be better to present the specific expression for \\nu_{n,B}, and make necessary discussions. What's factors affect the stability rate?\n\n3) Some important definitions and notions are missing. For example, where is the definition of \"light tail\"， whichi is the basic assumption in main theoretical results. How to characaterize light tail and its relevant factors.\n\n4) The authros should clearify the novelty and significance of the main results, for example, how about the theoretical new insghts on the technical proof in this work. As an pure theoretical problem, it is importnat to present some new technical proof, rather than simple extension of the current techiniques. What's the siginificance of the main results, is it possible to present some pratical guidance and suggest some new algorithms.", "limitations": "This is a pure theoretical work", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) It is an interesting problem on the theoretical understanding of random forests.\n\n2) Some theoretical results on the convergence probability of prediction intervals constructed from the out-of-bag error of random forests. \n\n3) Limited theoretical techinical contributions", "weaknesses": "1) The problem is not very clear. The authors should first present the studied problem, i.e. the original ranfom forests for regression, or randomf forest interval, or  prediction intervals constructed from the out-of-bag error of random forests. It is very confused to understand the main contributions in the current submission and relevant work. For completeness, it would be better to present the detailed algorithm, rather than finding some other research work for other readers.\n\n2) The main conclusions are not clear. The main contribution of this work is the stability of random forests in Theorem 1. Generally, a theoretical work concerns seriously the convergence rate of stability, and how tight of this rate. It would be better to present the specific expression for \\nu_{n,B}, and make necessary discussions. What's factors affect the stability rate?\n\n3) Some important definitions and notions are missing. For example, where is the definition of \"light tail\"， whichi is the basic assumption in main theoretical results. How to characaterize light tail and its relevant factors.\n\n4) The authros should clearify the novelty and significance of the main results, for example, how about the theoretical new insghts on the technical proof in this work. As an pure theoretical problem, it is importnat to present some new technical proof, rather than simple extension of the current techiniques. What's the siginificance of the main results, is it possible to present some pratical guidance and suggest some new algorithms.\n\n5) The authors should have a good background on the theoretical analysis on random forests, for example, \nG. Biau, L. Devroye, G. Lugosi, Consistency of random forests and other averaging classifiers, JMLR 2008.\nM. Denil, D. Matheson, N. De Freitas, Narrowing the gap: random forests in theory and in practice, ICLM2014.\nW. Gao, F. Xu and Z.-H. Zhou. Towards convergence rate analysis of random forests for classification. AIJ, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for agreeing that \"It is an interesting problem on the theoretical understanding of random forests.\" We will seriously take the reviewer's comments into consideration and make revisions accordingly. Below are point-by-point responses to the reviewer's \"Weaknesses\" comments.\n1. We want to make it clear here that there are two major contributions of our work. The first is establishing the stability of random forests under mild conditions; the second is providing non-asymptotic coverage guarantees for random forest prediction intervals (RFPIs), which is based on the stability property. It is worth stressing that methods to construct RFPIs have been proposed in Refs. [14] and [32]. However, in Ref. [14], there is no theoretical guarantee for the coverage probability; in Ref. [32], the coverage probability is established under very strong assumptions and it is an asymptotic result. It is NOT our aim to provide a completely new way to construct RFPIs. Rather, we provide further theoretical justifications to existing methods under much weaker assumptions. To the best of our knowledge, our non-asymptotic guarantees (Theorems 8 and 9) are the first such results for the practical version of the random forest algorithm. We hope this clarifies the main points of our work. In the revised manuscript, we will clarify the goals of our work and add a complete description of the RFPI algorithm for which our theory provides coverage guarantees.\n2. The stability we are considering is also referred to as \"out-of-sample stability\" in Ref. [3]. The parameters $(\\varepsilon,\\nu)$ characterize a \"spectrum\" of how stable an algorithm is (per Professor Barber's recent talk on stability of black-box algorithms), and in general there is no requirement that $(\\varepsilon,\\nu)$ must converge to 0 for a given algorithm. That said, a vanishing pair of $(\\varepsilon,\\nu)$ is practically appealing. We show in Theorem 7 that such parameters depend on the data distribution, number of data points $n$, and number of trees $B$ in the random forest algorithm. For non-heavy-tailed distributions, letting $n$ and $B$ go to infinity can result in vanishing $(\\varepsilon_{n,B},\\nu_{n,B})$. In the revised manuscript, we will present the \"specific expression for $\\nu_{n,B}$, and make necessary discussions,\" as suggested by the reviewer, which was partially addressed in the Appendix (C.4). \nThe tightness of the convergence rate is relevant. An inspection of our proof shows that there is some freedom in choosing the dependence of $B$, as well as of $\\lambda$, on $n$ to have vanishing $(\\varepsilon_{n,B},\\nu_{n,B})$, and the optimal rate depends on the data distribution (through $\\mathbb{E}[Z_{(n)}^2]$). However, $\\mathbb{E}[Z_{(n)}^2]$ originates from the bound for $|\\mathsf{rf}-\\mathsf{rf}^{\\backslash i}|$, and it is unclear whether this is the tightest bound in general, as it only takes advantage of the range of the predicted values of tree predictors. Whether we can find a more informative bound for $|\\mathsf{rf}-\\mathsf{rf}^{\\backslash i}|$ is an open problem, and only after this is resolved can we discuss the optimal rate of convergence for $(\\varepsilon_{n,B},\\nu_{n,B})$. To find such an improved bound is one of our future research directions, as stated in Sec. 3.4. \n3. By light-tail we mean non-heavy-tail. Please note that \"light tail\" appears in the informal Theorem 1 and other qualitative discussions, and when formally presenting our stability result with vanishing $(\\varepsilon_{n,B},\\nu_{n,B})$ in Corollary 3, we technically use sub-gamma distributions, which are well defined. We understand that \"light tail\" could be confusing for some readers, and we will make revisions accordingly. \n4. The reviewer mainly addresses two points here: \"new technical proof\" and \"new algorithm.\" For the first point, we want to emphasize that our aim in this work is not to provide new techniques. Rather, we use recently established techniques (stability by bagging) and standard concentration inequalities to provide new understanding of the random forest algorithm used in practice. We show that the practical version of random forests is stable, and the previously proposed methods to construct prediction intervals are almost provably valid approaches, both under mild conditions. These are the two major contributions of this work. (Corollary 4 is also a new result for the jackknife-with-stability method.) We don't believe that the techniques in our proofs are \"simple extensions of current techniques.\" There are at least two key developments: first, we notice the range of tree predictors is bounded conditioned on training data, which does not hold for a general learning algorithm; second, we take into account that $B_i$, the number of times the $i$th data point is not included in a bootstrap sample, is random, rather than fixed. We also provide the complete proof of an important result, Lemma 5, in the Appendix, and we establish the upper bound result by noticing the symmetry in the probabilistic deviation bound in the Appendix (E). None of this work is trivial. For the second point, again, it is not our aim in this work. However, our stability results do inspire new algorithms in other topics. Some of our ongoing work uses the stability property of random forests to perform active learning, which will be reported elsewhere.\n5. We will cite the suggested papers. Please note that although there are many theoretical results for random forests, few apply to the greedy random forest used in practice. Our work applies to many variants of random forests, including the greedy one, which makes it particularly relevant in theory and practice. \n\nWe hope after we fully address the comments, the reviewer will consider our work important and raise the score."}]

Author rebuttal:
We want to thank all reviewers for their time and comments. 

We are encouraged that three of them give positive evaluations to our work and suggest to accept our manuscript with ratings 6, 7, and 8, respectively. All three reviewers agree that our theoretical work is relevant for applied machine learning. Actually, this is the most important message we want to convey in this work. We prove that, under mild conditions, the practical version of random forests can be used to construct justified prediction intervals at almost no extra computational cost. Given the well-known fact that random forests have good performance on point prediction, our result "can be regarded as a demonstrative work that justifies the merit of random forests for both point and interval prediction," as per Reviewer 1UHc. We appreciate this reviewer's summary of our work, and we are happy to share it with more machine learning researchers in various fields. Following Reviewer BF9X’s suggestions, we will further clarify our problem, conclusions, the definitions of some terms, and the novelty and significance. We will try our best to make the revised manuscript more accessible to a broader readership.
 
Each reviewer's comments are addressed separately below.   

Meta-review: Three out of four reviewers have acknowledged the strength of the contributions of the paper. Even though some concerns have been raised at the initial reviews, the authors have addressed them adequately. Hence, I am recommending an acceptance. Please implement all the changes promised in the rebuttal.
Decision: Accept (poster)