# Revisiting Randomization in Greedy Model Search

arXiv: https://arxiv.org/abs/2506.15643 · HTML: https://mlsanity.com/paper/2506.15643/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 19 of 19)

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Dropout Training as Adaptive Regularization](https://mlsanity.com/paper/1307.1493/) (2013)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Randomization as Regularization: A Degrees of Freedom Explanation for Random Forest Success](https://mlsanity.com/paper/1911.00190/) (2019)
- [Large Scale Prediction with Decision Trees](https://mlsanity.com/paper/2104.13881/) (2021)
- [The Implicit Regularization of Ordinary Least Squares Ensembles](https://mlsanity.com/paper/1910.04743/) (2019)
- [Data-driven Advice for Applying Machine Learning to Bioinformatics Problems](https://mlsanity.com/paper/1708.05070/) (2017)
- [Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers](https://mlsanity.com/paper/2402.01502/) (2024)
- [Estimation and Inference with Trees and Forests in High Dimensions](https://mlsanity.com/paper/2007.03210/) (2020)
- [Sparse learning with CART](https://mlsanity.com/paper/2006.04266/) (2020)
- [Subsample Ridge Ensembles: Equivalences and Generalized Cross-Validation](https://mlsanity.com/paper/2304.13016/) (2023)
- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Generalized equivalences between subsampling and ridge regularization](https://mlsanity.com/paper/2305.18496/) (2023)
- [Randomization Can Reduce Both Bias and Variance: A Case Study in Random Forests](https://mlsanity.com/paper/2402.12668/) (2024)
- [On the Convergence of CART under Sufficient Impurity Decrease Condition](https://mlsanity.com/paper/2310.17114/) (2023)
- [Exogenous Randomness Empowering Random Forests](https://mlsanity.com/paper/2411.07554/) (2024)
- [When do Random Forests work?](https://mlsanity.com/paper/2504.12860/) (2025)

## Built on by (most cited first, 1 of 1)

- [LOCO-AdaMP: Built-in LOCO Inference for Adaptive Minipatch Ensembles with Enhanced Prediction](https://mlsanity.com/paper/2609.36396/) (2026)

## Abstract (arXiv)

Feature subsampling is a core component of 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. We investigate the effects of feature subsampling on greedy forward selection, a model that better captures the adaptive nature of 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. More precisely, we show that both the training error and degrees of freedom can be non-monotonic 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 results elucidate the distinct role of algorithmic randomization when interleaved with greedy optimization.