Adaptive Concentration of Regression Trees, with Application to Random Forests
arXiv:1503.06388
Abstract
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 carry out valid post-selection inference in the sense of Berk et al. [2013] for subgroups defined by tree leaves.
References in corpus (1)
Cited by in corpus (36)
- Double Machine Learning based Program Evaluation under Unconfoundedness
- Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
- Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers
- Non-parametric efficient causal mediation with intermediate confounders
- Double/Debiased Machine Learning for Treatment and Causal Parameters
- Trees, forests, and impurity-based variable importance
- Nonparametric estimation of causal heterogeneity under high-dimensional confounding
- Model-robust and efficient covariate adjustment for cluster-randomized experiments
- Estimation and Inference with Trees and Forests in High Dimensions
- Estimating heterogeneous treatment effects with right-censored data via causal survival forests
- Consistency of survival tree and forest models: splitting bias and correction
- A Unified Framework for Random Forest Prediction Error Estimation
- Sharp Analysis of a Simple Model for Random Forests
- Tree-Values: selective inference for regression trees
- Analysing a built-in advantage in asymmetric darts contests using causal machine learning
- Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees
- Double Machine Learning for Partially Linear Mixed-Effects Models with Repeated Measurements
- Boulevard: Regularized Stochastic Gradient Boosted Trees and Their Limiting Distribution
- Efficient Difference-in-Differences Estimation with High-Dimensional Common Trend Confounding
- Tree-based Synthetic Control Methods: Consequences of moving the US Embassy
- Regularizing Double Machine Learning in Partially Linear Endogenous Models
- Doubly-robust evaluation of high-dimensional surrogate markers
- Regularized Orthogonal Machine Learning for Nonlinear Semiparametric Models
- Interval censored recursive forests
- Doubly robust estimators for the average treatment effect under positivity violations: introducing the -score
- On the use of Harrell's C for clinical risk prediction via random survival forests
- Targeting predictors in random forest regression
- High-dimensional Inference for Dynamic Treatment Effects
- Asymptotic Normality for Multivariate Random Forest Estimators
- Best-scored Random Forest Classification
- Global and Local Two-Sample Tests via Regression
- Statistical Inference for Data-adaptive Doubly Robust Estimators with Survival Outcomes
- Censored Quantile Regression Forests
- Robust and Heterogenous Odds Ratio: Estimating Price Sensitivity for Unbought Items
- Comments on Leo Breiman's paper 'Statistical Modeling: The Two Cultures' (Statistical Science, 2001, 16(3), 199-231)
- Learning Optimal Distributionally Robust Individualized Treatment Rules