Margins are Insufficient for Explaining Gradient Boosting

Allan Grønlund, Lior Kamma, Kasper Green Larsen

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 Schapire 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 (Gronlund 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 for boosted classifiers 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).

The Margin Paradox in Modern Boosting

For over two decades, Margin Theory has been the primary framework for understanding why boosting works. The theory posits that as more weak learners are added to an ensemble, the "margin"—the distance of training points from the decision boundary—increases, thereby guaranteeing better generalization to unseen data. Larger margins were thought to be the definitive indicator of a model's ability to perform on new data.

However, a significant paradox has emerged with modern state-of-the-art gradient boosters like LightGBM and XGBoost. While these models frequently achieve superior test accuracy, they often produce significantly smaller margins than the classic AdaBoost algorithm. According to existing mathematical bounds, these low-margin models should be overfitting significantly. The researchers set out to find the "missing link" in the theory that explains why these low-margin models perform so well in real-world applications.

Comparison of margins between AdaBoost (ada) and LightGBM (lgb).

Methodology

To resolve this discrepancy, the researchers employed a two-pronged approach combining empirical experimentation with rigorous mathematical proof:

  1. Empirical Comparison: Head-to-head tests were conducted between AdaBoost and LightGBM across four diverse datasets: Forest Cover (large-scale prediction), Boone (ecological modeling), Higgs (high-energy physics), and Diabetes (classic medical classification). To ensure a fair comparison, the researchers kept tree sizes identical across models.
  2. Visualizing Predictions: The team analyzed the distribution of outputs from individual trees. They discovered a fundamental difference: while AdaBoost trees consistently output "strong" signals (values close to -1 or 1), LightGBM trees output values extremely close to 0 for the vast majority of data points.
  3. Refined Margin Bound: Based on these observations, the authors derived a new generalization bound. Unlike previous iterations that treat all base learners as arbitrary functions, this refined bound includes a term $N$ that depends on the magnitude of the base learners' predictions.
  4. Lower Bound Improvement: The study also improved upon recent generalization lower bounds, demonstrating that their refined theory is significantly closer to the actual behavior of boosting algorithms in practice.

Key Insights: The "Lazy" Tree Advantage

The core finding is that generalization is not solely a function of the margin, but also of the "complexity" or "effort" required to achieve that margin. Modern gradient boosters are essentially "lazy." A typical tree in LightGBM only significantly changes the prediction for a tiny fraction of the data (e.g., 1 in 5,000 points). Traditional margin theory ignores this, treating a "quiet" tree the same as a "loud" one.

By introducing a "Moment" metric to quantify prediction magnitude, the researchers found that AdaBoost is highly aggressive (e.g., a moment of 0.969 on Forest Cover), whereas LightGBM is extremely subtle (a moment of 0.025). The refined bound accounts for this by including a term $N$ that scales with the actual magnitude of the updates. If a model achieves a small margin using very small updates, it is less likely to overfit than a model achieving a large margin through aggressive updates.

Results and Theoretical Correction

The refined theory successfully explains the performance of modern boosters where previous bounds failed. In the Forest Cover dataset, while classic theory predicted AdaBoost would be vastly superior due to its larger margins, the new "Generalization Penalty" correctly identified that LightGBM's lower complexity resulted in comparable or better test error.

Generalization penalty comparison for AdaBoost vs LightGBM.

Across all tested datasets, the refined bound consistently aligned with observed test errors. This proves that the standard penalty for small margins ($1/\theta^2$) is overly pessimistic for gradient boosting algorithms that utilize small update steps. The authors show that the magnitude of the base learners is a critical factor that was previously overlooked.

Conclusion and Future Directions

This work demonstrates that margins alone are insufficient to explain the success of modern gradient boosting. By accounting for the magnitude of updates, the new refined bound provides a more accurate theoretical foundation for the field. While the paper focuses primarily on binary classification, the authors suggest that their new bound could be used as a regularization objective to develop even more accurate boosting variants in the future. Extending these refined bounds to multi-class problems or regression remains an important open area for future research.

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 Schapire 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 (Gronlund 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 for boosted classifiers 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