Understanding Randomization in Greedy Model Search

We study feature subsampling in greedy model search, a randomization mechanism motivated by random forests and other ensemble methods. While recent theory suggests that this randomization acts solely as a variance reduction mechanism analogous to ridge regularization, these results largely rely on base learners optimized via ordinary least squares (OLS). We 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 ensembling with feature subsampling can reduce both bias and variance, contrasting with the pure variance reduction of convex base learners. Specifically, we 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. 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 well approximated by a logistic function. These are mechanism level results for a tractable analogue of greedy selection that depends on the response, not performance guarantees for full random forests.