Margins are Insufficient for Explaining Gradient Boosting
This work addresses a foundational theoretical gap in understanding gradient boosting for machine learning researchers, though it is incremental as it refines existing margin theory rather than introducing a new paradigm.
The paper tackles the problem that existing margin-based generalization bounds are insufficient for explaining the performance of state-of-the-art gradient boosting classifiers, and it proves a stronger margin-based bound that successfully explains this performance while also improving upon a recent generalization lower bound.
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ønlund et al. (2019).