stat.MLJun 18, 2025

Understanding Randomization in Greedy Model Search

Authors: Xin Chen, Jason M. Klusowski, Yan Shuo Tan, Chang Yu

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

Explore similar work

Nov 9, 2026

CRAFT-GBM: Selecting Best Features for Gradient-Boosted Machine Learning

Feature subsampling is used to accelerate gradient-boosted trees, yet standard approaches fix the feature count in advance and largely ignore the split-gain evidence accumulated during training. We introduce CRAFT-GBM (Confidence-Ranked Adaptive Feature Tracking), a native LightGBM extension that uses this evidence to adapt which---and, by default, how many---features are searched each boosting round. CRAFT-GBM transforms root-split gains into bounded observations and constructs joint time-uniform bounds valid under adaptive, non-stationary training histories. In its default endogenous mode, after initialization, CRAFT-GBM retains exactly the features that cannot yet be ruled out as best, letting the selected feature-set size KtK_t emerge from training history rather than a pre-specified fraction. With probability at least 1−δ1-δ, every feature with the largest expected gain is retained jointly across all rounds after initialization. When a feature fraction ff is specified instead, CRAFT-GBM ranks features by their interval point estimates and provides an approximate top-KK guarantee for feature budget KfK_f. We implement CRAFT-GBM within LightGBM while preserving its native feature-bundling representation, and evaluate it across 14 public and synthetic dataset families and four noise-augmented settings. In the fully endogenous setting, CRAFT-GBM reduces per-fit training time by 39.74% with 1.04% lower test loss in the geometric mean across all 18 RQ1 experiments. Under pre-specified feature fraction ff, Exogenous CRAFT-GBM also yields aggregate training-time reductions up to 13.52 percentage points larger than random feature subsampling, with no increase in aggregate test loss relative to full-feature LightGBM. Accumulated training evidence can thus support adaptive feature search with statistical guarantees while retaining the practical advantages of native gradient boosting.
Aug 26, 2026

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees

Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.
Apr 12, 2026

Exact Finite-Sample Variance Decomposition of Subagging: A Spectral Filtering Perspective

Standard resampling ratios (e.g., α≈0.632α\approx 0.632) are widely used as default baselines in ensemble learning for three decades. However, how these ratios interact with a base learner's intrinsic functional complexity in finite samples lacks a exact mathematical characterization. We leverage the Hoeffding-ANOVA decomposition to derive the first exact, finite-sample variance decomposition for subagging, applicable to any symmetric base learner without requiring asymptotic limits or smoothness assumptions. We establish that subagging operates as a deterministic low-pass spectral filter: it preserves low-order structural signals while attenuating cc-th order interaction variance by a geometric factor approaching αcα^c. This decoupling reveals why default baselines often under-regularize high-capacity interpolators, which instead require smaller αα to exponentially suppress spurious high-order noise. To operationalize these insights, we propose a complexity-guided adaptive subsampling algorithm, empirically demonstrating that dynamically calibrating αα to the learner's complexity spectrum consistently improves generalization over static baselines.