ExactBoost: Directly Boosting the Margin in Combinatorial and Non-decomposable Metrics
Daniel Csillag, Carolina Piazza, Thiago Ramos, João Vitor Romano, Roberto I. Oliveira, Paulo Orenstein
Abstract
Many classification algorithms require the use of surrogate losses when the intended loss function is combinatorial or non-decomposable. This paper introduces a fast and exact stagewise optimization algorithm, dubbed ExactBoost, that boosts stumps to the actual loss function. By developing a novel extension of margin theory to the non-decomposable setting, it is possible to provably bound the generalization error of ExactBoost for many important metrics with different levels of non-decomposability. Through extensive examples, it is shown that such theoretical guarantees translate to competitive empirical performance. In particular, when used as an ensembler, ExactBoost is able to significantly outperform other surrogate-based and exact algorithms available.
BibTeX
@InProceedings{pmlr-v151-csillag22a,
title = { ExactBoost: Directly Boosting the Margin in Combinatorial and Non-decomposable Metrics },
author = {Csillag, Daniel and Piazza, Carolina and Ramos, Thiago and Vitor Romano, Jo\~ao and Oliveira, Roberto I. and Orenstein, Paulo},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {9017--9049},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/csillag22a/csillag22a.pdf},
url = {https://proceedings.mlr.press/v151/csillag22a.html},
abstract = { Many classification algorithms require the use of surrogate losses when the intended loss function is combinatorial or non-decomposable. This paper introduces a fast and exact stagewise optimization algorithm, dubbed ExactBoost, that boosts stumps to the actual loss function. By developing a novel extension of margin theory to the non-decomposable setting, it is possible to provably bound the generalization error of ExactBoost for many important metrics with different levels of non-decomposability. Through extensive examples, it is shown that such theoretical guarantees translate to competitive empirical performance. In particular, when used as an ensembler, ExactBoost is able to significantly outperform other surrogate-based and exact algorithms available. }
}