Universal Online Learning with Bounded Loss: Reduction to Binary
  Classification
  We study universal consistency of non-i.i.d. processes in the context of
online learning. A stochastic process is said to admit universal consistency if
there exists a learner that achieves vanishing average loss for any measurable
response function on this process. When the loss function is unbounded,
Blanchard et al. showed that the only processes admitting strong universal
consistency are those taking a finite number of values almost surely. However,
when the loss function is bounded, the class of processes admitting strong
universal consistency is much richer and its characterization could be
dependent on the response setting (Hanneke). In this paper, we show that this
class of processes is independent from the response setting thereby closing an
open question (Hanneke, Open Problem 3). Specifically, we show that the class
of processes that admit universal online learning is the same for binary
classification as for multiclass classification with countable number of
classes. Consequently, any output setting with bounded loss can be reduced to
binary classification. Our reduction is constructive and practical. Indeed, we
show that the nearest neighbor algorithm is transported by our construction.
For binary classification on a process admitting strong universal learning, we
prove that nearest neighbor successfully learns at least all finite unions of
intervals.
