Capacity Conscious Boosting for Complex Base Learners

19 concepts20 papers1 proposal

Traditional boosting algorithms were built on the premise of combining "weak learners"—simple models like decision stumps that perform only slightly better than random guessing. While this approach is theoretically elegant and computationally efficient, modern high-dimensional tasks in image processing, speech recognition, and complex ranking have exposed a fundamental representational gap. As zhanglin peng et al. note in Deep Boosting: Layered Feature Mining for General Image Classification, simple decision boundaries are often insufficient for modeling the intricate spatial relationships and textures found in natural scenes.

This realization has driven a shift toward integrating high-capacity base learners into boosting frameworks. However, moving beyond simple stumps introduces a new challenge: the risk of overfitting.

The Representational Limit of Weak Learners

The reliance on simple base functions, such as decision stumps or monomials, acts as a bottleneck for ensemble performance. In the context of Conditional Random Fields, Lin Liao et al. argue in Training Conditional Random Fields Using Virtual Evidence Boosting that stumps limit a model's ability to capture complex feature interactions, suggesting that feature conjunctions are necessary for more sophisticated dependencies.

Similar limitations appear in specialized domains:

The Complexity-Stability Trade-off

If simple learners are insufficient, why not simply use deep decision trees or neural networks as base learners? The primary obstacle is the interaction between learner complexity and ensemble stability. Llew Mason et al. laid the groundwork for this discussion in Boosting Algorithms as Gradient Descent, noting that the impact of high-capacity weak learners on the noise robustness of an ensemble was not yet fully understood.

When base learners become too complex, the boosting process can easily overfit the training data, especially in the presence of noise. As Corinna Cortes et al. explain in Deep Boosting, while increasing depth improves training accuracy, it often compromises the model's ability to generalize to unseen data.

Capacity-Conscious Optimization

The solution emerging from recent research is to make the boosting algorithm "capacity-conscious." Instead of treating all base learners equally, the optimization objective is modified to penalize hypotheses based on their individual structural complexity.

In Deep Boosting, the authors derive a novel theoretical learning bound that explicitly accounts for the complexity of each base classifier and the weight assigned to it. By minimizing this bound, the algorithm can safely utilize deep decision trees by balancing their representational power against their risk of overfitting. This framework was further extended to large-scale multi-class problems by Vitaly Kuznetsov et al. in Multi-Class Deep Boosting, providing data-dependent generalization bounds that scale linearly with the number of classes.

New Frontiers for Complex Learners

The push toward higher base learner complexity is now influencing diverse areas of ensemble learning:

By moving from "weak" to "complex but constrained" learners, researchers are enabling boosting to tackle high-dimensional problems that were previously the sole domain of deep monolithic architectures, all while maintaining the iterative interpretability and theoretical rigor of ensemble methods.

Key Foundational Work

Boosting interval based literals1 (2001) — contributed 1 concept elements to this direction.
A boosting approach for confidence scoring (2001) — contributed 1 concept elements to this direction.
Boosting Algorithms as Gradient Descent (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_base_learner_complexity_0e792247,
  title = {base learner complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/base-learner-complexity/rdr_0e792247dce74f8686f5c9906c64eaf4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_base_learner_complexity_0e792247_v1,
  title = {base learner complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/base-learner-complexity/rdr_0e792247dce74f8686f5c9906c64eaf4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake