Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts
Contributo in Atti di convegno
Data di Pubblicazione:
2023
Citazione:
Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts / D. Van Der Hoeven, C. Pike-Burke, H. Qiu, N. Cesa Bianchi (PROCEEDINGS OF MACHINE LEARNING RESEARCH). - In: International Conference on Machine Learning / [a cura di] A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, J. Scarlett. - [s.l] : PMLR, 2023. - pp. 34809-34830 (( convegno International Conference on Machine Learning tenutosi a Honolulu nel 2023.
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 $\mathcal{O}\big(K^2(\ln T)\sqrt{T}\big)$ 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 $T^{2/3}$ one would obtain in the standard Lipschitz bandit setting. Our algorithm is empirically evaluated on synthetic data.
Tipologia IRIS:
03 - Contributo in volume
Elenco autori:
D. Van Der Hoeven, C. Pike-Burke, H. Qiu, N. Cesa Bianchi
Link alla scheda completa:
Titolo del libro:
International Conference on Machine Learning