Estimation and Inference with Trees and Forests in High Dimensions
This work addresses the challenge of estimation and inference for high-dimensional data in machine learning, providing theoretical guarantees for tree-based methods under sparsity, which is incremental but important for practical applications.
The paper tackles the problem of analyzing regression trees and forests in high-dimensional settings with sparse relevant features, proving that shallow trees achieve mean squared error rates that depend logarithmically on the ambient dimension and that fully grown honest forests enable asymptotically valid inference.
We analyze the finite sample mean squared error (MSE) performance of regression trees and forests in the high dimensional regime with binary features, under a sparsity constraint. We prove that if only $r$ of the $d$ features are relevant for the mean outcome function, then shallow trees built greedily via the CART empirical MSE criterion achieve MSE rates that depend only logarithmically on the ambient dimension $d$. We prove upper bounds, whose exact dependence on the number relevant variables $r$ depends on the correlation among the features and on the degree of relevance. For strongly relevant features, we also show that fully grown honest forests achieve fast MSE rates and their predictions are also asymptotically normal, enabling asymptotically valid inference that adapts to the sparsity of the regression function.