Boosting in the Limit: Maximizing the Margin of Learned Ensembles

Adam J. Grove, Dale SchuurmansAAAI 1998 · OpenReview

Abstract

The "minimum margin" of an ensemble classifier is the smallest vote it gives to any correct training label. While AdaBoost is known for producing large minimum margins—a trait often credited for its success—this paper investigates whether maximizing this margin further improves performance. By introducing "LPboosting" algorithms that achieve the theoretical maximum margin, we demonstrate that a larger minimum margin does not always yield better generalization. Our experiments show that AdaBoost eventually overfits if run long enough, and that the entire distribution of margins, rather than just the minimum, is critical for performance.

Introduction: The Magic of AdaBoost

In the late 1990s, AdaBoost was considered a "magic" algorithm in machine learning. It was remarkably effective at reducing test error and, unlike many other methods, appeared immune to overfitting even after reaching zero training error. The prevailing explanation, proposed by Schapire et al., was the Margin Theory. This theory suggested that AdaBoost works because it focuses on increasing the "margin"—a measure of confidence—particularly the minimum margin on the most difficult training examples.

This paper challenges that theory by asking a pointed question: If maximizing the minimum margin is the secret to AdaBoost's success, shouldn't an algorithm that explicitly maximizes that margin perform even better?

Methods: Pushing the Margin to the Limit

To test the margin hypothesis, the authors developed two new approaches based on Linear Programming (LP):

  1. LP-Adaboost: This method uses the same hypotheses generated by a standard AdaBoost run but re-calculates their weights using an LP solver to find the optimal weights that maximize the minimum margin for that specific ensemble.
  2. DualLPboost: A entirely new boosting procedure that uses the mathematical "dual" of the margin maximization problem to select hypotheses. Unlike AdaBoost, which only approaches the optimal margin asymptotically, DualLPboost is guaranteed to find the absolute best possible margin for a given hypothesis space.

These methods were evaluated across 13 UCI datasets using decision stumps (FindAttrTest) and decision trees (C4.5) as base learners.

The Concentration Effect

A striking finding was that LP-Adaboost and DualLPboost—despite achieving significantly higher minimum margins than AdaBoost—frequently performed worse on test data. This is attributed to the concentration effect.

Cumulative distribution of margins showing the 'squashing' effect of LP-based methods.

As shown in the margin distribution plots, forcing the minimum margin to be as large as possible often "squashes" the rest of the distribution. While the worst-case examples improve, many other examples that previously had high margins see their margins decrease. This suggests that the entire distribution of margins is more important for generalization than the single worst-case margin.

AdaBoost Overfits (Eventually)

Contrary to the folklore of the time, the authors demonstrated that AdaBoost is not immune to overfitting. By running the algorithm for an unprecedented number of rounds (up to $10^6$), they showed that test error eventually starts to climb.

Long-run error curves for AdaBoost showing eventual overfitting.

As illustrated in the figure, AdaBoost reaches peak performance around 100–1,000 rounds for certain datasets. If pushed to 1,000,000 rounds, the test error increases significantly, even as the margin continues to improve. This debunked the idea that more boosting is always better and showed that AdaBoost eventually converges to the same optimal margin as an LP solver, albeit much more slowly.

Conclusion

The "minimum margin story" is incomplete. While margins are important, the single-minded pursuit of the smallest margin can lead to overfitting. The authors conclude that the crucial question of why boosting works so well remains partially open, suggesting that future research should focus on optimizing the entire distribution of margins and identifying principled stopping criteria.

Summary updated

Abstract

The "minimum margin" of an ensemble classifier on a given training set is, roughly speaking, the smallest vote it gives to any correct training label. Recent work has shown that the Adaboost algorithm is particularly effective at producing ensembles with large minimum margins, and theory suggests that this may account for its success at reducing generalization error. We note, however, that the problem of finding good margins is closely related to linear programming, and we use this connection to derive and test new "LPboosting" algorithms that achieve better minimum margins than Adaboost.However, these algorithms do not always yield better generalization performance. In fact, more often the opposite is true. We report on a series of controlled experiments which show that no simple version of the minimum-margin story can be complete. We conclude that the crucial question as to why boosting works so well in practice, and how to further improve upon it, remains mostly open.Some of our experiments are interesting for another reason: we show that Adaboost sometimes does overfit--eventually. This may take a very long time to occur, however, which is perhaps why this phenomenon has gone largely unnoticed.
BibTeX
@inproceedings{grove1998boosting,
  author = {Adam J. Grove and Dale Schuurmans},
  title = {{Boosting in the Limit: Maximizing the Margin of Learned Ensembles}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
  url = {https://openreview.net/forum?id=Byb7vaedbr},
}
Figure