Understanding Randomization in Greedy Model Search
Organizations: Department of Operations Research and Financial Engineering, Princeton University, Sherrerd Hall, Princeton, NJ 08544. · Department of Statistics and Data Science, National University of Singapore, Block S16, Level 7, 6 Science Drive 2, Singapore 117546.
Abstract
We study feature subsampling in greedy model search, a randomization mechanism motivated by random forests and other ensemble methods. Although recent theory draws an analogy between this randomization and ridge regularization, these results largely rely on base learners optimized via ordinary least squares (OLS). We therefore investigate the effects of feature subsampling on greedy forward selection, a tractable abstraction of the adaptive split search used by decision trees. Assuming an orthogonal design, we prove that, under suitable conditions, ensembling with a fixed feature subsampling size can reduce expected training error without increasing degrees of freedom, thereby reducing fixed design prediction error. We also show that both the training error and degrees of freedom need not be monotone in the subsampling rate, breaking the analogy with standard shrinkage methods like the lasso or ridge regression under orthogonality. Furthermore, we characterize the exact asymptotic behavior of the estimator, showing that it adaptively reweights OLS coefficients based on their rank, with weights that are bounded by explicit logistic functions.
Figures & tables
Feature Selection
Feature selection identifies compact, informative variables or input dimensions to improve prediction, efficiency, interpretability, and statistical inference.
See all 213 papers