Optimal Minimal Margin Maximization with Boosting

Alexander Mathiasen, Kasper Green Larsen, Allan Grønlund
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4392-4401, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-mathiasen19a, title = {Optimal Minimal Margin Maximization with Boosting}, author = {Mathiasen, Alexander and Larsen, Kasper Green and Gr{\o}nlund, Allan}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4392--4401}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/mathiasen19a/mathiasen19a.pdf}, url = {https://proceedings.mlr.press/v97/mathiasen19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Optimal Minimal Margin Maximization with Boosting %A Alexander Mathiasen %A Kasper Green Larsen %A Allan Grønlund %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-mathiasen19a %I PMLR %P 4392--4401 %U https://proceedings.mlr.press/v97/mathiasen19a.html %V 97 %X 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.
APA
Mathiasen, A., Larsen, K.G. & Grønlund, A.. (2019). Optimal Minimal Margin Maximization with Boosting. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4392-4401 Available from https://proceedings.mlr.press/v97/mathiasen19a.html.

Related Material