Since this talk falls on 9/11, we will be careful about confident predictions: sometimes the right action is to abstain.
We study online prediction with N experts and binary outcomes. Without abstention, the standard regret rate is Θ(√(T log N)). Neu and Zhivotovskiy show that allowing the learner to abstain at cost c < 1/2 changes the rate to Θ(min{log N / (1 − 2c), √(T log N)}).
Thus, for fixed c < 1/2, regret eventually stops growing with the number of rounds.
We will derive the algorithm from exponential weights, explain why its abstention probability tracks expert disagreement, and prove the upper bound through a one-variable inequality. We will then discuss the matching lower bound, varying abstention costs, and extensions to multiclass and infinite expert classes.
