Boosting algorithms iteratively produce linear combinations of more and more base hypotheses and it has been observed experimentally that the generalization error keeps improving even after achieving zero training error. One popular explanation attributes this to improvements in margins. A common goal in a long line of research, is to obtain large margins using as few base hypotheses as possible, culminating with the AdaBoostV algorithm by Rätsch and Warmuth [JMLR’05]. The AdaBoostV algorithm was later conjectured to yield an optimal trade-off between number of hypotheses trained and the minimal margin over all training points (Nie, Warmuth, Vishwanathan and Zhang [JMLR’13]). Our main contribution is a new algorithm refuting this conjecture. Furthermore, we prove a lower bound which implies that our new algorithm is optimal.
Alexander Mathiasen (Aarhus University)
Kasper Green Larsen (Aarhus University, MADALGO)
Allan Grønlund (Aarhus University, MADALGO)
Related Events (a corresponding poster, oral, or spotlight)
2019 Poster: Optimal Minimal Margin Maximization with Boosting »
Tue Jun 11th 06:30 -- 09:00 PM Room Pacific Ballroom