Trading-off payments and accuracy in online classification with paid stochastic experts
File(s)van-der-hoeven23a.pdf (2.15 MB)
Accepted version
Author(s)
van der Hoeven, Dirk
Pike-Burke, Ciara
Qiu, Hao
Cesa-Bianchi, Nicolò
Type
Conference Paper
Abstract
We investigate online classification with paid stochastic experts. Here, before making their prediction, each expert must be paid. The amount that we pay each expert directly influences the accuracy of their prediction through some unknown Lipschitz “productivity” function. In each round, the learner must decide how much to pay each expert and then make a prediction. They incur a cost equal to a weighted sum of the prediction error and upfront payments for all experts. We introduce an online learning algorithm whose total cost after T rounds exceeds that of a predictor which knows the productivity of all experts in advance by at most O(K2(lnT)T−−√) where K is the number of experts. In order to achieve this result, we combine Lipschitz bandits and online classification with surrogate losses. These tools allow us to improve upon the bound of order T2/3 one would obtain in the standard Lipschitz bandit setting. Our algorithm is empirically evaluated on synthetic data.
Date Issued
2023-07-23
Date Acceptance
2023-04-24
Citation
Proceedings of Machine Learning Research, 2023, 202, pp.34809-34830
ISSN
2640-3498
Publisher
ML Research Press
Start Page
34809
End Page
34830
Journal / Book Title
Proceedings of Machine Learning Research
Volume
202
Copyright Statement
Copyright © The authors and PMLR 2023. MLResearchPress.
Source
40th International Conference on Machine Learning
Publication Status
Published
Start Date
2023-07-23
Finish Date
2023-07-29
Coverage Spatial
Hawaii, USA