Margins are Insufficient for Explaining Gradient Boosting

Allan Grønlund, Lior Kamma, Kasper Green Larsen

This NeurIPS 2020 paper by Allan Grønlund, Lior Kamma, and Kasper Green Larsen challenges a long-standing pillar of machine learning theory: the idea that "margins" are the primary reason why boosting algorithms generalize so well.

The authors demonstrate that traditional margin-based theory fails to explain the success of modern gradient boosters like LightGBM and XGBoost, which often achieve superior accuracy despite having "worse" margins than AdaBoost. By introducing a refined generalization bound that accounts for the magnitude of base learner predictions, they provide a theoretical framework that finally aligns with the empirical reality of modern boosting.

The Margin Paradox

In the world of boosting, "margins" measure a classifier's confidence. If a voting classifier predicts a label correctly and with a high margin, it isn't just right; it’s certain. For decades, the dominant theory (pioneered by Schapire et al. in 1998) argued that boosting works because it aggressively maximizes these margins, even after the training error hits zero.

However, a paradox has emerged: modern gradient boosting decision tree (GBDT) frameworks like LightGBM and XGBoost frequently outperform the classic AdaBoost. According to existing margin theory, they shouldn't. When comparing margin distributions, LightGBM often produces much smaller margins than AdaBoost.

Margin distributions showing AdaBoost achieving much higher margins than LightGBM

Under old theoretical bounds, these smaller margins imply LightGBM should have a much higher generalization error (overfitting). Yet, in practice, it generalizes better. This paper seeks to bridge this glaring gap between theory and practice.

Methods and Key Insights

The authors combine empirical observation across standard datasets (Forest Cover, Boone, Higgs, and Diabetes) with rigorous mathematical proofs to uncover why modern boosters succeed.

  • The "Lazy" Learner Advantage: The paper's "aha moment" is the realization that gradient boosters are essentially "lazy." In each iteration, a LightGBM tree might only significantly update the prediction for a tiny fraction of the data (e.g., 1 in 5,000 points). While this shrinks the overall margin—making the model look less confident by traditional metrics—it also makes the model much less complex than previous theories assumed.
  • Margins are Relative: Traditional theory assumes all base learners output values in the range $[-1, 1]$ and treats them equally. This paper shows that if a learner's output is mostly near zero, the "complexity penalty" for that learner should be substantially lower.
  • A Refined Bound: The authors derived a new "refined margin generalization bound." Unlike previous versions that treated base learners as arbitrary functions, this new bound incorporates the magnitude of the predictions. It uses a "moment" term that stays small if the base learners make small or sparse updates.

Resolving the Paradox

Using their new bound, the authors successfully explain the paradox. They show that the true "generalization penalty" for LightGBM is actually lower than AdaBoost's, even though its margins are smaller.

New generalization penalty showing LightGBM with a lower penalty than AdaBoost

Across all evaluated datasets, the "moment" value (representing the magnitude of predictions) was significantly lower for LightGBM than for AdaBoost. This explains why LightGBM can afford to have smaller margins without overfitting. Furthermore, the authors proved a new lower bound that settles the generalization performance of boosting for a wide range of margin values, identifying exactly where previous theories lost a factor of $\log m$.

Limitations and Future Work

While the paper provides a much-needed explanation for why existing tools work, it doesn't introduce a brand-new boosting algorithm. However, the authors suggest their refined bound could be used as a regularization term to develop even more accurate boosters.

Additionally, the new bound is mathematically complex, involving high-order moments and log-factors, which might make it difficult for practitioners to calculate on the fly without optimized implementations. Future work could also explore the interplay between tree depth, leaf count, and the "small updates" characteristic of modern GBDTs.

Summary updated

Abstract

Boosting is one of the most successful ideas in machine learning, achieving great practical performance with little fine-tuning. The success of boosted classifiers is most often attributed to improvements in margins. The focus on margin explanations was pioneered in the seminal work by Schaphire et al. (1998) and has culminated in the $k$'th margin generalization bound by Gao and Zhou (2013), which was recently proved to be near-tight for some data distributions (Gr\o nlund et al. 2019). In this work, we first demonstrate that the $k$'th margin bound is inadequate in explaining the performance of state-of-the-art gradient boosters. We then explain the short comings of the $k$'th margin bound and prove a stronger and more refined margin-based generalization bound that indeed succeeds in explaining the performance of modern gradient boosters. Finally, we improve upon the recent generalization lower bound by Gr\o nlund et al. (2019).
BibTeX
@inproceedings{grnlund2020margins,
  author = {Allan Grønlund and Lior Kamma and Kasper Green Larsen},
  title = {{Margins are Insufficient for Explaining Gradient Boosting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=qPl8FkrbKUs},
}
Figure