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.
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.
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