ExactBoost: Directly Boosting the Margin in Combinatorial and Non-Decomposable Metrics
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.
Cite
Text
Csillag et al. " ExactBoost: Directly Boosting the Margin in Combinatorial and Non-Decomposable Metrics ." Artificial Intelligence and Statistics, 2022.Markdown
[Csillag et al. " ExactBoost: Directly Boosting the Margin in Combinatorial and Non-Decomposable Metrics ." Artificial Intelligence and Statistics, 2022.](https://mlanthology.org/aistats/2022/csillag2022aistats-exactboost/)BibTeX
@inproceedings{csillag2022aistats-exactboost,
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ão and Oliveira, Roberto I. and Orenstein, Paulo},
booktitle = {Artificial Intelligence and Statistics},
year = {2022},
pages = {9017-9049},
volume = {151},
url = {https://mlanthology.org/aistats/2022/csillag2022aistats-exactboost/}
}