acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Standard resampling ratios, such as the bootstrap-inspired , are widely used in ensemble learning, yet their finite-sample interaction with the functional complexity of the base learner remains poorly understood. We use the Hoeffding–ANOVA decomposition to derive the first exact finite-sample variance decomposition for subagging with any symmetric square-integrable base learner, where denotes the training sample size and the subsample size. The resulting identity shows that subagging acts as a deterministic spectral filter: the -th order interaction component is attenuated by an explicit combinatorial factor , bounded by and converging to when the subsampling ratio is held fixed. This explains why fixed resampling ratios can under-regularize high-capacity interpolators, whose variance is concentrated in high-order interactions, and why smaller can suppress such noise exponentially. Building on this mechanism, we characterize how the optimal subsampling ratio shifts with the learner's interaction complexity and propose Complexity-Guided Adaptive Subsampling (CGAS), which empirically improves generalization over static resampling baselines.

Primary area:
learning theory
Keywords:
Subagging, Bagging, Ensemble Learning, Hoeffding-ANOVA Decomposition, Variance Decomposition

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 2 reviews, above 9% of the others.
Reviewer_p2QwOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

Subagging is the process of training a copy of the base learner on each of many random subsets of size kk drawn without replacement from the training set of size nn, and averaging the predictions. The fraction α=kn\alpha = \frac{k}{n} is called the subsampling ratio. The paper studies this setup for a symmetric and square-integrable base learner, and, using the Hoeffding–ANOVA decomposition, it derives an exact finite-sample variance formula for the subagged model. This result shows that subagging multiplies each order-cc component of the base learner variance by a factor γc≤αc\gamma_c \le \alpha^c, interpreted as a "spectral low-pass filter" that suppresses high-order interactions. Addressing the bias-variance tradeoff, the authors argue that the optimal subsampling ratio α∗\alpha^{\ast} (minimizing the authors' bound on the MSE) is lower (or equal) when more of the base learner’s variance comes from high-order interactions (which the authors describe as a heavier high-order spectrum).

The paper proposes CGAS, a method to choose α\alpha based on cross-validation, where the grid depends on the base learner's complexity: {0.6,0.7,0.8,0.9,0.95}\lbrace0.6,0.7,0.8,0.9,0.95\rbrace for low-complexity learners (e.g., shallow trees), and {0.1,0.2,0.3,0.4}\lbrace0.1,0.2,0.3,0.4\rbrace for high-complexity learners (e.g., deep trees). CGAS is evaluated on nine OpenML regression datasets against fixed α∈{0.632,0.8}\alpha \in\lbrace0.632, 0.8\rbrace, in two regimes: depth-3 trees on the original labels, and unlimited-depth trees on labels with added Gaussian noise, with standard deviation of 1.5 times that of the labels. CGAS outperforms both fixed ratios on all nine datasets in the high-complexity regime, while it is comparable or slightly better in the low-complexity regime.

Critical strengths
  1. A clean, explicit quantification of how subagging reduces variance (each order-cc component is scaled by γc≤αc\gamma_c \le \alpha^c), which explains why this process suppresses variance from high-order interactions much more strongly than low-order ones. However, its significance is limited as this formula is classical (see Weakness 1).

  2. The empirical experiments suggest that using a fixed subsampling ratio can be suboptimal, while tuning it according to the model's complexity (for example, using lower ratios for a complex base learner on noisy data) may lead to better results. In particular, in the high-complexity regime, CGAS improves over both fixed ratios on all nine datasets. This is useful for practitioners.

Critical weaknesses
  1. The main theoretical result of the paper (Theorem 3.1) is not novel, despite being presented in the abstract as ‘the first exact finite-sample variance decomposition for subagging’. As the authors note (Section 2.2), the subagged estimator in Equation (1) is a U-statistic of order kk with kernel hh. Since Equation (1) averages over all size-kk subsets, it is a complete one. Theorem 3.1 is exactly the classical variance formula obtained from Hoeffding’s H-decomposition. Indeed,

(kc)γc(n,k)=(kc)(n−ck−c)(nk)=k!c!(k−c)!⋅(n−c)!(k−c)!(n−k)!⋅(n−k)!k!n!=(k!(k−c)!c!)2⋅c!(n−c)!n!=(kc)2(nc).\binom{k}{c}\gamma_c(n,k) = \binom{k}{c}\frac{\binom{n-c}{k-c}}{\binom{n}{k}} = \frac{k!}{c!(k-c)!}\cdot \frac{(n-c)!}{(k-c)!(n-k)!}\cdot \frac{(n-k)!k!}{n!} = \left(\frac{k!}{(k-c)!c!}\right)^2 \cdot \frac{c!(n-c)!}{n!} = \frac{\binom{k}{c}^2}{\binom{n}{c}}.

(The first expression for γc\gamma_c in Equation (5) is a typo. The correct form, derived in Appendix F, is used above.)

Thus, Equation (4) is Var(F^n,k(x))=∑c=1k(kc)2(nc)−1ζc(x)\mathrm{Var}\big(\hat F_{n,k}(x)\big)=\sum_{c=1}^{k}\binom{k}{c}^2\binom{n}{c}^{-1}\zeta_c(x), the standard expression (e.g., Peng, Coleman & Mentch, "Rates of convergence for random forests via generalized U-statistics," Electron. J. Stat. 16(1), 2022; see Equation (18) in arXiv:1905.10651v3). Since the main result is already known, the paper must be judged mainly on Section 4 and the experiments.

  1. The experiments don't test the main claim of the paper, that α∗\alpha^{\ast} is governed by the base learner's interaction complexity. This is because CGAS restricts the search range in advance by tree depth (which is the paper’s proxy for complexity). This guarantees the shift of α∗\alpha^{\ast} in Figure 1 by construction. Searching the same full grid for all base learners would test this directly.

Together, these leave the paper’s contribution resting mainly on Theorem 4.5, which is not actually tested by the experiments.

Questions for authors
  1. What is the difference between Theorem 3.1 and the classical H-decomposition variance formula?
  2. Does the complexity-dependent shift in α∗\alpha^{\ast} survive when using a single shared grid {0.1,…,0.95}\lbrace0.1,\dots,0.95\rbrace for all base learners?
Reviewer_e5LDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Popular ensembles methods, bagging and subagging which are based on subsampling, reduce the variance of base learners without inflating bias. These methods often use a subsampling ratio based on heuristics and there is no principles way to select the subsampling ratio \alpha based on the complexity of the base learner. The paper derives finite sample bounds for subagging’s variance using the Hoeffding–ANOVA decomposition under certain assumptions on the base class. The bounds also take into account the complexity of the base learner. The resulting identity shows that subagging acts as a deterministic spectral filter: the cth order interaction component is attenuated by an explicit combinatorial factor bounded by and converging to \alpha^c when the subsampling ratio \alpha= k/n is held fixed.This explains why fixed resampling ratios can under-regularize high-capacity interpolators, whose variance is concentrated in high-order interactions, and why smaller \alpha can suppress such noise exponentially. This formalizes the transition in the bias-variance trade-off: low-capacity smoothers require larger \alpha for bias control, whereas models dominated by high-order interactions necessitate smaller \alpha to suppress noise. They also empirically validate their structural shift theorem, demonstrating that dynamically calibrating \alpha to the learner’s structural capacity systematically improves finite-sample generalization over static baselines.

Critical strengths
  • The paper studies an important question on how to choose the subsampling ratio for the ensemble methods. Bagging and subagging have been very important and popular techniques and this paper gives theoretical justification and a principled method to choose the subsampling parameter.
  • The presentation of the paper is clear.
  • Empirical results support the theoretical claims which is good to have.
Critical weaknesses
  • Theorem 4.5 compares spectra where some higher-order variance components increase and all lower-order components remain unchanged. This increases the total variance. A much informative comparison would have been if the total variance were the same but the distribution along different components were different.
  • The empirical algorithm proposed uses a different proxy of the spectral distribution. For decision trees, they use the tree depth. It is not clear how the tree depth relates to the spectral distribution of the learners. Hence, the empirical effectiveness of the method shown is disconnected from the theoretical arguments presented earlier in the paper.
Questions for authors
  • Can the authors comment on if this complexity is also related to the number of predictors that we should choose for different base learners?
  • Why do we consider two separate regimes in section 5.1? For both shallow and deep trees, it would be nice to do a grid search over all values of \alpha for completeness.
  • Also not clear to me why do we add Gaussian noise to the large depth trees?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.