A General Online Algorithm for Optimizing Complex Performance Metrics

Wojciech Kotlowski, Marek Wydmuch, Erik Schultheis, Rohit Babbar, Krzysztof Dembczynski
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:25396-25425, 2024.

Abstract

We consider sequential maximization of performance metrics that are general functions of a confusion matrix of a classifier (such as precision, F-measure, or G-mean). Such metrics are, in general, non-decomposable over individual instances, making their optimization very challenging. While they have been extensively studied under different frameworks in the batch setting, their analysis in the online learning regime is very limited, with only a few distinguished exceptions. In this paper, we introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm’s update and prediction rules are appealingly simple and computationally efficient without the need to store any past data. We show the algorithm attains $\mathcal{O}(\frac{\ln n}{n})$ regret for concave and smooth metrics and verify the efficiency of the proposed algorithm in empirical studies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-kotlowski24a, title = {A General Online Algorithm for Optimizing Complex Performance Metrics}, author = {Kotlowski, Wojciech and Wydmuch, Marek and Schultheis, Erik and Babbar, Rohit and Dembczynski, Krzysztof}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {25396--25425}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/kotlowski24a/kotlowski24a.pdf}, url = {https://proceedings.mlr.press/v235/kotlowski24a.html}, abstract = {We consider sequential maximization of performance metrics that are general functions of a confusion matrix of a classifier (such as precision, F-measure, or G-mean). Such metrics are, in general, non-decomposable over individual instances, making their optimization very challenging. While they have been extensively studied under different frameworks in the batch setting, their analysis in the online learning regime is very limited, with only a few distinguished exceptions. In this paper, we introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm’s update and prediction rules are appealingly simple and computationally efficient without the need to store any past data. We show the algorithm attains $\mathcal{O}(\frac{\ln n}{n})$ regret for concave and smooth metrics and verify the efficiency of the proposed algorithm in empirical studies.} }
Endnote
%0 Conference Paper %T A General Online Algorithm for Optimizing Complex Performance Metrics %A Wojciech Kotlowski %A Marek Wydmuch %A Erik Schultheis %A Rohit Babbar %A Krzysztof Dembczynski %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-kotlowski24a %I PMLR %P 25396--25425 %U https://proceedings.mlr.press/v235/kotlowski24a.html %V 235 %X We consider sequential maximization of performance metrics that are general functions of a confusion matrix of a classifier (such as precision, F-measure, or G-mean). Such metrics are, in general, non-decomposable over individual instances, making their optimization very challenging. While they have been extensively studied under different frameworks in the batch setting, their analysis in the online learning regime is very limited, with only a few distinguished exceptions. In this paper, we introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm’s update and prediction rules are appealingly simple and computationally efficient without the need to store any past data. We show the algorithm attains $\mathcal{O}(\frac{\ln n}{n})$ regret for concave and smooth metrics and verify the efficiency of the proposed algorithm in empirical studies.
APA
Kotlowski, W., Wydmuch, M., Schultheis, E., Babbar, R. & Dembczynski, K.. (2024). A General Online Algorithm for Optimizing Complex Performance Metrics. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:25396-25425 Available from https://proceedings.mlr.press/v235/kotlowski24a.html.

Related Material