acceptodds
Desk rejected at ICLR 2027

When Feature Bagging Helps Adaptive Search: SNR Theory and Prospective mtry Selection

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Feature bagging averages predictors fitted after restricting an adaptive search to random feature subsets. We study when this improves prediction and use the same search structure to tune mtry, the number of features searched at each forest split. Under an isotropic Gaussian signal model, an exact restriction–diversity identity gives a posterior signal-to-noise ratio (SNR) boundary for grouped nonlinear search with arbitrary candidate correlations. A complementary fixed-signal bound permits general feature covariance; under orthogonal weak signals, smaller feature fractions have lower asymptotic risk. A common-projection result extends the SNR identity to completed recursive fits. For tuning, we couple full-depth trees across budgets to share split searches and selectively refine promising candidates. On a development benchmark of 12 wide-feature regression tasks and five outer folds, with 39–85 candidate budgets, the selector attains 1.336% mean regret relative to the best 256-tree test-grid candidate, compared with 1.385% for successive halving. Its measured tuning and total wall-time ratios to halving are 0.3710 and 0.5123, respectively; total time includes the selected 256-tree forest.

Primary area:
learning theory
Keywords:
adaptive search, feature bagging, ensemble learning, random forests

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_HCbTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies feature bagging in adaptive search in two parts. In the first part, the authors study when feature bagging helps. They first establish a posterior signal-to-noise ratio (SNR) boundary for grouped nonlinear search under an isotropic Gaussian signal model, complemented by a fixed-signal bound under general feature covariance and a budget ordering under orthogonal weak signals. They then extend the SNR identity to recursive adaptive search under a common-projection condition. In the second part, the authors propose an algorithm for tuning mtry that couples full-depth trees across budgets to share split searches and selectively refines promising candidates. The numerical study covers 12 wide-feature regression tasks, each evaluated on five outer folds.

Critical strengths

The paper contains publishable results, including an exact posterior SNR identity for grouped adaptive search with arbitrary candidate correlations and its extension to recursive adaptive search. The proposed algorithm combines shared split search with successive halving and a corrected OOB target, resulting in a new selector that achieves accuracy comparable to successive halving with reduced measured wall time.

Critical weaknesses

(1) Limited novelty and practical scope of the theory. The theory in Section 2 essentially establishes that feature bagging helps at low SNR, which has been argued in prior work (Mentch & Zhou, 2020, as the authors cite). The authors derive the same conclusion under different model settings. The statement that may address strong signals, the boundary in Eq. 7, depends on D and V, which cannot be calculated in advance, so it provides little guidance for the moderate- and high-SNR settings where choosing mtry matters most. In Theorem 3.1, the authors extend the theory to recursive adaptive search, but part (i) conditions on shared non-feature randomness and part (ii) further requires a common projection geometry, which fails across bootstrap samples; the theorem therefore does not cover standard random forests with per-tree bootstrap. In addition, as the authors note, its low-SNR conclusion requires D_T ≥ 0, which can fail; this condition also cannot be verified in advance. More importantly, the theory developed in Sections 2 and 3 has only a weak connection with the mtry selector developed in Section 4 and evaluated in Section 5.

(2) Limited methodological novelty and a confounded speedup. The corrected OOB score is a per-row variant of the ECV finite-ensemble correction (Du et al., 2024). The corrected halving baseline, which combines the corrected score with successive halving, performs worse than plain SH (1.56% vs. 1.39%). Moreover, the proposed geometric refinement does not significantly outperform SH (the 95% CI of the paired difference contains 0). Although the proposed algorithm has the lowest wall time among the tuning methods (about half that of SH, the only directly measured comparison), it is unclear how much of the speedup comes from the lighter tree schedule (4–8–16 for the proposed method vs. 8–16–32 for SH). The reported speedup may therefore be substantially attributable to the schedule rather than to shared search.

Questions for authors

(1) Beyond providing exact formulas, what additional conceptual contribution does Section 2 make relative to prior low-SNR explanations of feature randomization (e.g., Mentch & Zhou, 2020)? Does it also provide practical guidance for moderate- and high-SNR settings, where the choice of mtry is more important?

(2) Beyond analytical convenience, what computational capabilities does Eq. 3 provide? At a single node, the winning subset can be identified by a lookup among the p featurewise winners, and the subset probabilities could likewise be estimated by sampling.

(3) How does Theorem 3.1 apply to standard random forests based on per-tree bootstrap samples, given that part (i) conditions on shared non-feature randomness and part (ii) requires a common projection geometry?

(4) Is there empirical evidence that the posterior SNR boundary in Eq. 15 predicts out-of-sample test performance? How should practitioners address the condition D_T ≥ 0, which may fail and cannot be verified in advance?

(5) The grouped-search structure is the standard CART split search, and the theory compares a fixed budget with a full search, whereas the selector compares budgets with one another. What does the theory contribute specifically to the selection problem?

(6) How much of the speedup over SH is attributable to shared search, and how much to the lighter 4–8–16 schedule? Can you report an ablation under a common schedule, with and without sharing?

(7) How sensitive are the results to the individual design choices: the schedule, retaining half, the half-corrected score, the two refinement triggers, and the 50-tree comparison? In the manuscript, only the midpoint has been ablated.

(8) Could Table 1 include confidence intervals so that readers can see directly that most accuracy differences are not statistically significant?

Reviewer_2DZeOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when feature bagging (mtry<p\texttt{mtry} < p) helps adaptive split-search ensembles such as random forests, and how to tune mtry\texttt{mtry} efficiently. For a single grouped search under an isotropic Gaussian signal model, the authors derive an exact posterior risk-gap identity, (2κ−1)D−(1−B−1)V(2\kappa - 1)D - (1 - B^{-1})V. It shows that restricting the search never increases risk at low SNR (κ≤1/2\kappa \le 1/2). At higher SNR, it helps only when ensemble diversity outweighs the SNR-weighted loss of training fit. They extend the analysis with a fixed-signal bound under general covariance, a weak-signal limit, and a recursive-tree version. On the computational side, candidate mtry\texttt{mtry} values share bootstrap samples and nested feature permutations, so split searches are reused while node states coincide. With a size-corrected OOB score and 4–8–16 screening plus optional 50-tree refinement, the method matches successive halving's accuracy across 12 regression benchmarks (1.336%1.336\% vs. 1.385%1.385\% regret; not significant) in about 37%37\% of the tuning time (51%51\% of total time).

Critical strengths

Elegant Unification of Search Restriction and Ensemble Diversity via Exact Combinatorics and Martingale Decomposition: Starting from the Krogh–Vedelsby ambiguity identity, the paper cleanly isolates the trade-off between losing greedy search energy (DD or alignment AβA_\beta) and gaining ensemble variance reduction ((1−B−1)V(1 - B^{-1})V). The exact hypergeometric rank distribution πr(m)=(p−rm−1)/(pm)\pi_r(m) = \binom{p-r}{m-1}/\binom{p}{m} for one-step group winners (Equation 3), the closed-form weak-signal asymptotic risk curve cγ,B=1B+(1−1B)γ2−γc_{\gamma, B} = \frac{1}{B} + (1 - \frac{1}{B})\frac{\gamma}{2-\gamma} in Corollary 2.3, and the Doob martingale stagewise decomposition with an explicit two-step reversal counterexample (Theorem 3.1 and Proposition D.1) are mathematically transparent and insightful. Why consequential: Classical random forest analyses typically treat mtry qualitatively through generic bias-variance bounds rather than deriving exact regime boundaries and asymptotic risk curves where restricting m<pm < p provably dominates full search.

Critical weaknesses

Isotropic Gaussian prior rewards arbitrary shrinkage rather than feature selection (Proposition 2.1 and Theorem 3.1(ii)): The exact SNR boundary κ<12+(1−B−1)V2D\kappa < \frac{1}{2} + (1 - B^{-1})\frac{V}{2D} relies on an isotropic prior F∼NH(0,a2I)F \sim \mathcal{N}_{\mathcal{H}}(0, a^2 I) where E[F∣Z]=κZ\mathbb{E}[F \mid Z] = \kappa Z shrinks every direction in H\mathcal{H} by the exact same scalar κ\kappa. Under this prior, no feature or cutpoint has higher prior SNR than any other; consequently, whenever κ<1/2\kappa < 1/2 (a2<ω2a^2 < \omega^2), restricting search (D>0D > 0) reduces risk even for a single tree (B=1B = 1) simply because picking a worse-fitting feature has smaller norm ∥hξ∥2<∥hF∥2\|h_\xi\|^2 < \|h_F\|^2 and thus acts as norm shrinkage toward zero. In realistic tabular settings where random forests excel, signal is concentrated on a sparse or low-dimensional subset of features rather than spread isotropically across all directions; restricting m<pm < p then risks dropping true signal features and incurring bias AβA_\beta (which remains unobservable in Theorem 2.2).

Questions for authors
  1. Separating the schedule effect from the search-sharing effect: The proposed selector screens on 4–8–16 (8G8G candidate–tree units before sharing), while the SH baseline uses warm-started 8–16–32 (16G16G units, Eq. 39). The schedule alone therefore halves the base work. How much of the 0.371×0.371\times tuning wall-time ratio comes from the shorter schedule, and how much from shared node searches? Please report measured tuning wall/CPU time, and split-search work counts, for: (a) a 4–8–16 halving schedule without search sharing, and (b) the same schedule with sharing, both stopping at the 16-tree default without 50-tree refinement, and using the same score as the proposed method (L^B\widehat{L}_B screening, half-corrected terminal score). Since sharing does not change predictions, can you please also report the regret of this 4–8–16 selector against 8–16–32 SH, to show whether the shorter schedule costs any accuracy?

  2. Out-of-sample validation of the frozen selector: The 4–8–16 schedule, half-corrected 16-tree score L^half\widehat{L}_{\text{half}}, block-reversal trigger Qk(m)Q_k(m), and geometric-midpoint rule were developed on the same 12-task library used for evaluation (Line 402; Appendix E.1, "Development sequence"). Could you evaluate the frozen selector, with no further changes, on an independent, pre-specified set of wide-feature regression tasks (e.g., chosen by a fixed eligibility rule from another OpenML or tabular suite)? Please report regret against SH and OOB50, trigger rates (the paper reports 24/60), and matched measured timings for all tuners. Optionally, could you discuss how the target-size OOB correction and the theory would extend to classification (e.g., via Brier score)?

Reviewer_6wwLOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper revisits two classic problems in random forests: 1) when feature bagging improves prediction, and 2) how to choose \texttt{mtry}, the number of features searched at a split, with less computation. A contribution of the paper is about how to share computations across different values of \texttt{mtry}, using shared split searches and selective refinement of promising candidates.

As a theoretical contribution, they study how restricting the search can limit noise driven selection and how averaging benefits from prediction diversity. Under an isotropic Gaussian signal and noise model, the authors obtain an exact posterior risk identity for one grouped adaptive search, showing that feature bagging cannot increase posterior risk relative to full search if signal variance is not greater than noise variance. This is a posterior comparison, rather than a guarantee for every fixed signal or for general random forests. Furthermore, the paper gives a fixed-signal bound for one-step, one-feature regression with general Gaussian feature covariance. With zero signal, this bound shows that feature bagging lowers risk relative to full search with probability tending to one.

Empirically, the authors evaluate the method on 1212 wide-feature regression tasks with five outer folds, with tuning and total wall-time ratios of 0.37100.3710 and 0.51230.5123 relative to successive halving. Total time includes completion of the selected forest to 256256 trees and prediction, starting from prepared inputs. The method has slightly lower mean regret than successive halving, 1.336%1.336\% compared to 1.385%1.385\%, while the overall accuracy difference is not statistically clear. However, the full-grid OOB256 search has lower mean regret on this benchmark, 0.976%0.976\% compared to 1.336%1.336\%, suggesting a trade-off between computation and accuracy.

Critical strengths
  1. The paper gives an exact posterior risk identity for grouped adaptive search, separating the effect of restricting search from the diversity benefit of averaging.

  2. The theory includes a fixed-signal bound with general Gaussian feature covariance complementing the isotropic signal model.

  3. The proposed method shares split computations across \texttt{mtry} values and selectively refines promising candidates making broad grid tuning more efficient.

  4. On 1212 regression tasks, the method roughly halves measured total wall time relative to successive halving and without a statistically clear difference in accuracy.

Critical weaknesses
  1. The posterior SNR boundary relies on an isotropic Gaussian signal and noise model and does not provide a guarantee for a fixed signal. The fixed-signal bound covers only one-step, one-feature fits and gives a signed conclusion only at zero signal.

  2. The selector was developed and evaluated on the same 1212-task library, limiting the evidence for generalization to unseen tasks.

  3. Only the timing comparison with successive halving is directly measured and the other tuners timing figures are provisional estimates.

  4. For a fixed budget and prefix size, the OOB correction is conditionally unbiased for an ensemble whose trees all omit the evaluated observation. However it does not provide a risk guarantee after adaptive screening and selection which leave the full selector with no population prediction risk guarantee.

Questions for authors
  1. Does the accuracy and cost advantage over successive halving hold on new task collections that were not used to develop the selector?

  2. Can the recursive SNR results be extended to population prediction risk for forests fitted with different row-bootstrap samples?

Reviewer_NceQOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Unfortunately, I ran into significant clarity issues throughout the first 3-4 pages of reading the paper, so I wasn't able to fully grasp what the contributions of this work are. Based on the abstract, it seems that the authors are studying the role of instance bagging at nodes, which use a random subset of the features for each element of the ensemble to fit the residual at that node. Specifically they are looking at the number of features chosen for the random subset when doing the bagging, and when/how that becomes relevant within an signal-to-noise ratio analysis of the residual.

Critical strengths

As I was having significant difficulty in parsing the work, unfortunately I have no strengths to enlist.

Critical weaknesses

The writing is significantly lacking and often uses non-conventional terms, making the paper hard to read. "cutpoints", "residualized direction". Phrasing is also often obscure: "compares featurewise winners", "noise-driven splits", "connect feature randomization to regularization at low SNR". The paper jumps into these terms without properly defining what the signal is, what is noise, what is regularization, what does a "winner" mean. "correlated adaptive candidates", "diversity gained by averaging". Unfortunately, most of this is just from one paragraph, and the writing is like this throughout the paper. Even the main question isn't clear "useful budget at less cost" what is the "cost" here?

The notation itself is not properly defined. Not sure what \mathcal{M} is, or what a "grid" is. Not sure what the information C here is, what the "expected square error" is computed on, what is the input, output.

Moving forward, in 2.1, not sure what the purpose of a "group" here is if it is just one feature. Not sure what it means to say we "allow" arbitrary correlations within and across groups. "subset calculation" is not dfined, not sure what we mean by a "response-derived" target Z. Not sure what the significance of L_j, p are. Although I can probably infer what the authors are trying to do here, but that is just very broad inferring based on certain cues. The presentation and notation is quite scattered and can be significantly improved and streamlined.

Continuing in 2.1, not sure what "deterministic tie rules" means. Not sure what a "restricted search" means in this context, not clear what a "fitted library" is. Also not sure what exactly is the "diversity" the authors are trying to refer, I'm assuming its the V term but there is no clear mention. Also h_F is introduced without introducing what F even is. I only see an F introduced later, nothing before that.

Unfortunately, I had to stop here. It was becoming very hard for me to continue reading without a full understanding of what was being presented. Without a full grasp of the theoretical setting I cannot review this paper accurately.

Questions for authors

Please see weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.