Uniform Convergence of Random Forests via Adaptive Concentration

By Stefan Wager, Guenther Walther. 2015

24 citations recorded by the source corpus.

We study the convergence of the predictive surface of regression trees and forests. To support our analysis we introduce a notion of adaptive concentration for regression trees. This approach breaks tree training into a model selection phase in which we pick the tree splits, followed by a model fitting phase where we find the best regression model consistent with these splits. We then show that the fitted regression tree concentrates around the optimal predictor with the same splits: as d and n get large, the discrepancy is with high probability bounded on the order of sqrt(log(d)log(n)/k) uniformly over the whole regression surface, where d is the dimension of the feature space, n is the number of training examples, and k is the minimum leaf size for each tree. We also provide rate-matching lower bounds for this adaptive concentration statement. From a practical perspective, our result enables us to prove consistency results for adaptively grown forests in high dimensions, and to derive generalization bounds for a large class of regression forests.

Subfields: Artificial Intelligence, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Local Linear Forests (2018, neutral): “Biau, Devroye, and Lugosi (2008) and Wager and Walther (2015) relied on large leaves, while the results of Scornet, Biau, and Vert (2015) on fully grown trees rely on an unchecked high-level assumption.”
The Econometrics of Randomized Experiments (2016, background): “Other related approaches include Wager and Walther (2015), who discuss corrections to confidence intervals (widening the confidence intervals by a factor) as an alternative to sample splitting; however, since confidence intervals need to be inflated fairly substantially, it is not clear whether…”
Estimation and Inference of Heterogeneous Treatment Effects using Random Forests (2015, methodology): “Scornet et al. [2015] found that, under conditions on the data-generating function, the risk of CART random forests converges to the Bayes risk, 6 i.e., the test set error of a random forest converges to the Bayes error as n → ∞ . are in Meanwhile, Wager and Walther [2015] show that adaptive trees w”
Recursive partitioning for heterogeneous causal effects (2015, background): “Finally, Wager and Walther (30) adjust confidence intervals to account for adaptive estimation, and List et al.”
Optimization of Tree Ensembles (2017, background): “Recently, Wager and Walther (2015) showed that certain forms of regression trees and random forests converge uniformly over the feature space to the true regression function, while Wager and Athey (2015) considered how to use random forests for causal inference.”
Asymptotic Theory for Random Forests (2014, unknown): “[32] Stefan Wager and Guenther Walther.”