  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.
