Trading-Off Payments and Accuracy in Online Classification

We consider online binary classification where in each round, before making a prediction the learner can choose to ask some a number of stochastic experts for their advice. In contrast to the standard experts problem, we investigate the case where each expert needs to be paid before they provide their advice, and that the amount we pay them directly influences the accuracy of their prediction through some unknown 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 and analyse its total cost compared to that of a predictor which knows the productivity of all experts in advance. In order to achieve this result, we combine Lipschitz bandits and online classification with surrogate losses.

Joint work with: Dirk van der Hoeven, Hao Qiu, Nicolo Cesa-Bianchi

• Speaker: Ciara Pike-Burke (Imperial College London)
• Friday 20 October 2023, 14:00–15:00
• Venue: MR12, Centre for Mathematical Sciences.
• Series: Statistics; organiser: Qingyuan Zhao.