Bagging in the real world
Bagging is one of the most successful, practical heuristics in Machine Learning (as of now > 16,000 references). Part of its success is its generality: given any method for learning predictors from data, Bagging aims to produce an ensemble of predictors that combined together outperform in accuracy the single one. However, Bagging is a heuristic and thus occasionally fails. We ask in what sense one can develop theory for this immensy popular machine learning method that occasionally has a very bad behavior (no bounds how bad things can become). And we want to do that without adding a number of ad hoc assumptions. To that end, we provide a new (practical and theoretical) framework and mathematical tools, and then by adapting ideas from stochastic coupling, de-randomization and pseudo-randomness we construct the first, provably and universally better-than-Bagging-heuristic. This is joint work with Jia Xu and Cao Zhu.