Optimal Sparse Recovery with Decision Stumps
This work addresses the theoretical gap in understanding feature selection guarantees for tree-based methods, which are widely used in practice, offering incremental improvements in bounds for specific criteria.
The paper tackles the problem of feature selection in high-dimensional sparse linear regression using decision stumps, providing tight finite sample bounds of O(s log p) that match Lasso and extend to non-linear regimes and arbitrary sub-Gaussian distributions.
Decision trees are widely used for their low computational cost, good predictive performance, and ability to assess the importance of features. Though often used in practice for feature selection, the theoretical guarantees of these methods are not well understood. We here obtain a tight finite sample bound for the feature selection problem in linear regression using single-depth decision trees. We examine the statistical properties of these "decision stumps" for the recovery of the $s$ active features from $p$ total features, where $s \ll p$. Our analysis provides tight sample performance guarantees on high-dimensional sparse systems which align with the finite sample bound of $O(s \log p)$ as obtained by Lasso, improving upon previous bounds for both the median and optimal splitting criteria. Our results extend to the non-linear regime as well as arbitrary sub-Gaussian distributions, demonstrating that tree based methods attain strong feature selection properties under a wide variety of settings and further shedding light on the success of these methods in practice. As a byproduct of our analysis, we show that we can provably guarantee recovery even when the number of active features $s$ is unknown. We further validate our theoretical results and proof methodology using computational experiments.