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

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. ------------------after response--------------------------------- After reading the authors' response, I do not think the authors answer my concerns, in particularly for the novelties and significances. As 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. I 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".

Strengths

1) It is an interesting problem on the theoretical understanding of random forests. 2) Some theoretical results on the convergence probability of prediction intervals constructed from the out-of-bag error of random forests. 3) 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. 2) 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? 3) 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. 4) 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. 5) The authors should have a good background on the theoretical analysis on random forests, for example, G. Biau, L. Devroye, G. Lugosi, Consistency of random forests and other averaging classifiers, JMLR 2008. M. Denil, D. Matheson, N. De Freitas, Narrowing the gap: random forests in theory and in practice, ICLM2014. W. Gao, F. Xu and Z.-H. Zhou. Towards convergence rate analysis of random forests for classification. AIJ, 2022.

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. 2) 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? 3) 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. 4) 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.

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

This is a pure theoretical work

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$. Theorem 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. One 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. The 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. Let 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.

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. * 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). * 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. * 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).

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. 2) 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)$ $$P\{\mu\{(x,y): |y-RF(x)|\leq q_\alpha(R_i) + \epsilon\}\geq 1-\alpha-\nu.$$ Could this stronger guarantee be obtained via the present methods. 3) 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? 4) Regarding Theorems 3 and 10: it would seem that a sufficient condition for the theorem to hold is that $Y-\mathbb{E}[Y\mid X]=:\eta$ satisfies: $$\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.$$ where $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$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

There is no explicit discussion of limitations, nor do I think one would be necessary.

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.

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. 2. The presentation usually benefits from working under a single set of assumptions instead of increasingly more assumptions (however this is a minor point).

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}$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None noted

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.

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.

Weaknesses

-- I think the writing can be slightly improved by articulating the use of absolute stability results for bagged algorithms. -- 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. -- 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. -- 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. -- 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.

Questions

Please see my suggestions above.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Everything on this front seems reasonable.

Thank you

Thank you very much for the rebuttal. I have nothing else to add at this point.