Online Classification with Predictions
This work addresses the challenge of enhancing online learning efficiency for scenarios where future data predictability can be leveraged, representing an incremental advance over prior methods using predictions or assumptions.
The paper tackles the problem of online classification by incorporating predictions about future examples, resulting in an online learner whose expected regret never exceeds worst-case regret and improves with prediction accuracy, sometimes significantly better than worst-case.
We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.