Feature Bagging Provides Stability

We study feature bagging through the lens of algorithmic stability. Feature bagging is an ensemble strategy that aggregates base learners trained on randomly subsampled feature subsets, possibly in a data-dependent manner. We introduce feature instability (FI), the feature-axis analogue of instance instability (II), which measures sensitivity to removing a single feature. Smaller values of II or FI correspond to stronger stability, and our experiments show that FI captures generalization-relevant information complementary to II. Within this framework, we analyze feature bagging in both a parametric linear model and a model-free setting inspired by recursive feature subsampling in random forests. In both settings, we establish formal guarantees showing that feature bagging improves the relevant stability relative to its non-bagged counterpart, with larger improvements under more aggressive subsampling. We further show that a modest number of bagging rounds is sufficient to approach the infinite-bagging stability level.

Modern machine-learning models can change noticeably when part of their training data changes. This paper studies whether feature bagging, a technique that trains many models using randomly chosen subsets of features and then averages them, can make learning algorithms more stable. Classical stability asks what happens when one training example is removed. We argue that feature bagging also requires a feature-side view: what happens when one input feature is removed? We introduce feature instability to measure this effect and show that it captures information not explained by instance-based stability alone. We then analyze feature bagging in linear regression and in model-free settings motivated by random forests. Across theory and experiments, we find that feature bagging improves stability, especially when each model uses a smaller subset of features, and that only a moderate number of bagging rounds is needed to approach the idealized infinite-ensemble behavior.