{"id":"cc0fe349-56d9-4358-bd20-4bee73a059e5","arxiv_id":"2607.26964","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Feature bagging provably lowers leave-one-feature-out instability in linear regression, random forward selection, and a dyadic random forest model.","lead":"This paper introduces feature instability, a measure of how much a model's prediction changes when a single input feature is removed, and proves that averaging models trained on random feature subsets reduces this instability. Exact formulas for linear regression and upper bounds for forward selection and dyadic random forests show that smaller feature subsampling ratios give larger stability gains.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The model-free random-forest guarantee rests entirely on condition (4.3), verified only for dyadic fixed-midpoint splits; standard CART thresholds break the encoding and the stability proof.","rationale":"The reader's weakest assumption and my concern coincide: the recursive pith condition (4.3) is the hinge. For random forward selection, Theorem 4.5 verifies it only under the orthogonal-design assumption; for forests, Theorem 4.7 verifies it only for the max-edge dyadic midpoint-split rule. The rest of the random-forest argument—including the affine map K(w) in Proposition 4.6 and the F-norm encoding—uses dyadic thresholds as a necessary condition. Without standard CART, the broad claim that feature bagging stabilizes random forests is not proven; the dyadic simplification is load-bearing for the proof, not a cosmetic restriction. This is a correctness risk for the breadth of the claim, not an internal inconsistency: the paper is explicit about the simplification in Section 4.2.2, and the linear-model analysis in Section 3 is self-contained and independently supported by exact asymptotics and matching simulations. The suggested empirical/analytical check of (4.3) would settle whether the simplification is benign or whether the random-forest claim should be stated only for dyadic forests. Because the reader already issued a CONDITIONAL verdict and identified the same assumption, I recommend the verdict remain unchanged.","tokens_in":59916,"tokens_out":8714,"duration_ms":104609,"concrete_test":"Run a targeted check of condition (4.3) for standard CART: simulate d=8, n=300 correlated Gaussian features (ρ=0.5) with a MARSadd-style response; for each removed feature j and 10^4 coupled seeds, compute w_1, w_1^{-j} and then the ratio R_j = ||E[S^{-j}_{ξ_2}(w_1)-S^{-j}_{ξ_2}(w_1^{-j})]||_F / ||E[Δ_1]||_F using the real CART split rule (data-dependent threshold) with feature subsampling ratio q=0.25. If max_j R_j ≤ 1+√2 for all nonzero denominators, the dyadic verification extends in the nontrivial first recursive step; if the ratio is unbounded or requires a constant growing with n or d, condition (4.3) fails for standard CART and Theorem 4.7 cannot be transported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the one-step pith condition (4.3): Proposition 4.4 converts per-step Lipschitz constants δ_t into the recursive FI bound (4.4), and the claimed stability gain over the non-bagged 2T/d baseline for random forests depends entirely on Theorem 4.7 verifying (4.3) with δ_t = √2 for the 'max-edge dyadic' forest. That verification uses two simplifications that are essential, not cosmetic: (i) thresholds are fixed midpoints, so the local cell is a deterministic function of the sequence of split features; (ii) the max-edge candidate rule gives the increment bound ||U^{-j}(w)-U^{-j}(w')||_F ≤ √2·1{w≠w'}. For a standard CART split, the threshold is data-dependent and changes when a feature is removed; the feature-removed tree's partition is no longer encoded by split counts alone, and the affine map K(w) of Proposition 4.6 no longer holds because thresholds affect leaf predictions. Thus the central model-free claim that feature bagging provably stabilizes random forests is strictly proven only for the dyadic midpoint-split simplification. The paper states this simplification, but the abstract and introduction say the theory 'applies to ... random forests'; without verification of (4.3) for CART-type splits, that transfer is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces feature instability (FI), a leave-one-feature-out analogue of instance instability, and studies whether feature bagging improves stability along the feature axis. In the parametric setting (Section 3), the authors analyze bagged minimum-norm least squares under proportional asymptotics and give an exact decomposition of FI and II into variance and signal terms with closed-form limits (Theorem 3.1 and Table 1). In the model-free setting (Section 4), they propose a recursive stochastic-process framework with a one-step pith condition (4.3), apply it to randomized forward selection and a dyadic midpoint-split random forest, and give finite-bagging concentration bounds (Proposition 4.8). The paper also reports experiments suggesting that FI carries generalization-relevant information complementary to II.","tokens_in":60203,"tokens_out":4922,"duration_ms":56527,"significance":"If the results hold as stated, the linear-model exact asymptotics are a genuine contribution: they provide parameter-free closed forms for the effect of instance/feature subsampling and bagging on both stability axes, and the finite-B decomposition cleanly separates same-submodel and cross-submodel contributions. The model-free framework is also conceptually useful and yields the first feature-side analogue of the assumption-free instance-bagging stability results. The empirical finding that FI is complementary to II is plausible and well supported by the bootstrap/R2 noise-control checks described in the appendix. However, the model-free results are proven only for substantially simplified algorithms, and the paper's abstract and introduction overstate the scope by saying the theory applies to random forests without qualification. The central claims are defensible for the analyzed simplifications, but the manuscript needs to either extend the proofs or carefully re-scope the claims.","major_comments":[{"comment":"The random-forest guarantee is stated for the 'max-edge dyadic randomized forest' with fixed midpoint splits, but the abstract and introduction claim the theory applies to random forests. The proof of δ_t=√2 and the affine encoding K(w) both rely essentially on the simplification that thresholds are deterministic midpoints, so the local cell containing x is a function only of the split-count matrix w. In a standard CART split, thresholds are data-dependent; removing a feature can change thresholds on other features, the partition is no longer encoded by w alone, and the affine map K(w) of Proposition 4.6 does not hold. Unless condition (4.3) is verified for CART-type splits, all random-forest claims should be explicitly restricted to the dyadic midpoint-split setting.","section":"§4.2.2, Theorem 4.7 and Proposition 4.6"},{"comment":"Theorem 4.5 is stated for Algorithm 1 without any design assumption, but the proof uses the orthogonal design X⊤X=nI_d. In particular, the residual-sum-of-squares decrease formula (S.8), the score-ordering argument, and the structural 'auxiliary fact' about D_t^j all depend on this assumption. For correlated designs, the one-step condition (4.3) is not established. The orthogonal-design condition needs to appear in the theorem statement, or the proof must be extended to general designs.","section":"§4.2.1, Theorem 4.5"},{"comment":"The bound (4.7) depends on A_T^2 with A_T = ∑_{t=1}^T (1+√2)^{T−t}, which grows exponentially in T. The text compares this with the non-bagged baseline 2T/d only through the informal phrase 'for shallow trees and sufficiently small q'. As written, no explicit regime is given in which the right-hand side of (4.7) is smaller than 2T/d. The paper should state a concrete depth/regime condition (for example T=O(log d) and q below some threshold) under which the claimed strict improvement is guaranteed.","section":"§4.2.2, Theorem 4.7"}],"minor_comments":[{"comment":"The displayed informal instability quantities are missing the square on the difference; as written the expressions are not squared deviations.","section":"Eqs. (1.1) and (1.2)"},{"comment":"The sentence 'The assumption ET[U1^T U1] = ... appears less natural, but is important...' appears to be a dangling editorial note. It should be moved into the lemma statement or removed.","section":"Appendix S.2.2, after Lemma S.2.4"},{"comment":"Using the superscript B for the signal/bias terms while B also denotes the number of bagging rounds is confusing even with the inline caveat. Consider renaming the bias terms (e.g., Δ^sig or Δ^μ).","section":"Notation, Section 3"},{"comment":"Theorem 4.5 uses the regime T≲q^{-1}, while the prose comparison with the non-bagged baseline uses T≲(1−q)/q. These are different conditions; the relation should be stated precisely.","section":"§4.2.1 and §4.3"},{"comment":"The proof of Proposition 4.4 is only one sentence ('recursively applying equation (S.7) and Proposition 4.3'). Since this proposition is the backbone of Section 4, the recursive derivation and the handling of the sup terms in M_T should be expanded.","section":"Appendix S.3.3"}],"recommendation":"major_revision","confidential_remarks":"The linear-model analysis (Theorem 3.1, Table 1) appears solid and is the strongest part of the paper. The main concern is scope: the model-free random-forest result is proven only for a dyadic midpoint-split simplification, yet the abstract and introduction claim applicability to random forests. If the authors cannot verify (4.3) for CART-type splits, the claims need to be carefully re-scoped. The paper builds legitimately on prior work; I see no novelty or attribution concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it. The core is real: FI is a well-defined feature-axis analogue of II, and this is the first formal treatment of feature bagging as a stabilizer along that axis. The peeling/pith recursion in Prop 4.4 is the genuine technical contribution—it converts a one-step Lipschitz condition on expected transitions into a recursive bound, with the scalar bagging result as the base case. Theorem 3.1 with Table 1 is serious asymptotics, and the q^2/d scaling of the feature-removal bias term is a real observation that II can't see. The RFS theorem is clean: in the orthogonal-design regime, bagged forward selection provably beats the non-bagged 2T/d baseline whenever T is below (1-q)/q. The experiments are honest in the important sense—empirical curves are compared against theoretical ones, not fit to them, and the PMI noise controls are the right kind of sanity check.\n\nThe soft spots, in size order. The random-forest claim is the thin one. Theorem 4.7 verifies the load-bearing condition (4.3) only for dyadic midpoint splits with the max-edge rule, and both simplifications are doing real work: fixed midpoints make the cell a deterministic function of the split-feature sequence, and the √2 increment bound comes from the max-edge candidate rule. Standard CART thresholds are data-dependent, so removing a feature changes the partition in a way the encoding can't represent, and the affine map in Prop 4.6 fails. The paper does disclose the dyadic simplification in 4.2.2, so this is a scope gap rather than a false proof—but the abstract's 'applies to random forests' is a genuine overstatement, and a referee should push to align the language with the theorems.\n\nSmaller things: RFS is verified only under orthogonal design; the auxiliary fact inside Theorem 4.5 is an induction sketch, probably true but needing a full write-up; and the linear-model appendix is heavy going, with at least one garbled editing leftover in Lemma S.2.4 (the 'less natural assumption' comment). I found no circular reasoning or fitting-to-data moves; the theory is parameter-free.\n\nSend it to review. The FI measure and the recursion deserve the field's attention. The main revision request is to match the claims to the dyadic scope and tighten the compressed spots.","headline":"FI and the peeling/pith recursion are real contributions, but the random-forest guarantee is proven only for dyadic midpoint splits—the abstract overstates, and it deserves review with that fix.","tokens_in":60686,"tokens_out":4636,"would_cite":true,"duration_ms":49033,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Feature bagging provably stabilizes predictions against feature removal.","keywords":["feature instability","feature bagging","algorithmic stability","random forests","random forward selection","leave-one-feature-out","recursive subsampling","bagging"],"falsifier":"Measure the leave-one-feature-out prediction change for a standard random forest with data-dependent thresholds on correlated features while decreasing q; if FI increases as q decreases, or exceeds q A_T^2/((d-1)(1-q)) at shallow depth T, the recursive stability claim fails for real forests. More directly, estimate the ratio ||E[S^{-j}_ξ(w)-S^{-j}_ξ(w^{-j})]|| / ||E[Δ]|| across splits; values above 1+√2 would refute the dyadic contraction condition.","tokens_in":59786,"feed_emoji":"🛡️","tokens_out":5850,"duration_ms":60787,"temperature":0.7,"pith_summary":"The paper argues that feature bagging—training an ensemble on random subsets of features and averaging—reliably reduces an algorithm's sensitivity to losing any single feature, a quantity it names feature instability (FI). In a linear-regression model it derives exact asymptotic formulas showing how bagging shrinks both instance and feature instability and how the gains depend on the instance and feature subsampling ratios. Outside parametric models, it proves bounds for recursive feature subsampling in random forward selection and a simplified dyadic random forest, with the average leave-one-feature-out change controlled by the feature-subsampling ratio q. More aggressive subsampling yields stronger guarantees, and a modest number of bagging rounds approaches the infinite-bagging stability level. Experiments indicate FI carries generalization-relevant signal that instance instability misses.","feed_headline":"Feature bagging provably stabilizes against feature removal","feed_subtitle":"New bounds show aggressive feature subsampling plus averaging shrinks leave-one-feature-out sensitivity.","key_machinery":"Feature instability (FI), the leave-one-feature-out average of squared prediction changes, together with the feature-subsampling ratio q and averaging over resampled feature sets. The recursive results are carried by a one-step condition—the propagated feature-removal discrepancy may grow by at most a factor 1+δ_t per step—plus a peeling recurrence (Proposition 4.4) and a Hilbert-space radius bound. In the linear-model part, an affected-axis resampling coupling and sketching matrices allow exact asymptotic moment calculations.","core_discovery":"The paper's central claim is that feature bagging—averaging learners trained on randomly subsampled feature sets—is provably less sensitive to single-feature removal than the same algorithm without feature bagging. In the linear model, Theorem 3.1 gives an exact large-B decomposition of FI and II, with the bagged instability falling to order 1/n away from the interpolation threshold. In the model-free setting, Theorem 4.5 bounds the feature instability of random forward selection by T^2/(d-1) · q/(1-q) when T ≲ 1/q, compared with a non-bagged value of 2T/d, so bagging wins whenever T ≲ (1-q)/q. Theorem 4.7 extends the bound to a dyadic max-edge random forest with factor q A_T^2/((d-1)(1-q)).","pith_inferences":["One could treat feature bagging as an explicit stability-regularization knob for tree ensembles, choosing q by the desired tolerance for feature-removal sensitivity—an implication the paper motivates but does not develop into a tuning rule.","The dyadic-forest bound likely extends to standard CART only if the one-step condition (4.3) holds for data-dependent split thresholds; a direct check of that condition on real random forests would settle how far the guarantee reaches.","Because FI scales with 1/(d-1) and q/(1-q), the stability effect should be largest in wide-but-shallow settings (large d, small q, small T); experiments on tabular data with d ≫ n could expose where the bound is tight.","The complementarity of FI and II suggests a two-axis stability diagnostic that could be computed alongside model selection, though the paper stops short of recommending a specific procedure."],"forward_implications":["Smaller feature-subsampling ratios q produce strictly stronger FI guarantees in the analyzed regimes.","Finite bagging with B proportional to d(1-q)/q already matches the infinite-bagging stability bound up to an O(1/B) term.","Feature instability and instance instability carry complementary generalization information, so stability reports should track both axes.","In the shallow-recursion regime (T ≲ (1-q)/q), feature-bagged random forward selection and dyadic random forests beat their non-bagged counterparts on FI.","In linear regression, bagging flattens the double-descent instability peak of single subsampled estimators."],"supporting_citations":[{"why":"Supplies the instance-bagging stability framework and the averaging-stability result whose feature-axis dual the paper proves.","marker":"Soloff et al. 2024a"},{"why":"Defines algorithmic stability and its generalization link, the motivation for II and FI.","marker":"Bousquet and Elisseeff 2002"},{"why":"Introduces random forests and recursive feature subsampling, the target application of the model-free theory.","marker":"Breiman 2001"},{"why":"Proposes the randomization-as-regularization explanation that motivates studying feature bagging through stability.","marker":"Mentch and Zhou 2020"},{"why":"Provides the bagged least-squares/sketched estimator reformulation and proportional-asymptotic setting used in Section 3.","marker":"Wu and Sun 2025"},{"why":"Supplies proportional-asymptotics and universality results for ridgeless regression underlying the exact limits.","marker":"Hastie et al. 2022"},{"why":"Analyzes sketched ridgeless regression with downsampling, the technical baseline for feature-subsampled linear models.","marker":"Chen et al. 2023"},{"why":"Studies implicit regularization of OLS ensembles and supplies an expectation lemma for subsampled designs.","marker":"LeJeune et al. 2020"}],"fun_headline_variants":["Feature bagging provably reduces single-feature removal sensitivity","Feature bagging: provably less sensitive to feature removal","Feature bagging provably improves stability under feature removal","Averaging feature subsets provably reduces sensitivity to loss"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The recursive guarantees rest on a one-step condition—after removing one feature the expected discrepancy between full and reduced runs may grow by at most a factor 1+δ_t each step—which is verified for orthogonal-design random forward selection and dyadic max-edge forests, but not for standard random forests with data-dependent thresholds or correlated features.","fun_headline_variants_meta":{"raw":{"variants":["Feature bagging provably reduces single-feature removal sensitivity","Feature bagging: provably less sensitive to feature removal","Feature bagging provably improves stability under feature removal","Averaging feature subsets provably reduces sensitivity to loss"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000743,"raw_usage":{"total_tokens":3130,"prompt_tokens":702,"completion_tokens":2428,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":446,"completion_tokens_details":{"reasoning_tokens":2362}},"tokens_in":446,"tokens_out":2428,"duration_ms":18208,"temperature":1.0,"reasoning_tokens":2362,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T04:20:31.150430+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Measure the leave-one-feature-out prediction change for a standard random forest with data-dependent thresholds on correlated features while decreasing q; if FI increases as q decreases, or exceeds q A_T^2/((d-1)(1-q)) at shallow depth T, the recursive stability claim fails for real forests. More directly, estimate the ratio ||E[S^{-j}_ξ(w)-S^{-j}_ξ(w^{-j})]|| / ||E[Δ]|| across splits; values above 1+√2 would refute the dyadic contraction condition.","supporting_citations":[],"review_version":2}