Universal Online Learning with Unbounded Losses: Memory Is All You Need
  We resolve an open problem of Hanneke on the subject of universally
consistent online learning with non-i.i.d. processes and unbounded losses. The
notion of an optimistically universal learning rule was defined by Hanneke in
an effort to study learning theory under minimal assumptions. A given learning
rule is said to be optimistically universal if it achieves a low long-run
average loss whenever the data generating process makes this goal achievable by
some learning rule. Hanneke posed as an open problem whether, for every
unbounded loss, the family of processes admitting universal learning are
precisely those having a finite number of distinct values almost surely. In
this paper, we completely resolve this problem, showing that this is indeed the
case. As a consequence, this also offers a dramatically simpler formulation of
an optimistically universal learning rule for any unbounded loss: namely, the
simple memorization rule already suffices. Our proof relies on constructing
random measurable partitions of the instance space and could be of independent
interest for solving other open questions. We extend the results to the
non-realizable setting thereby providing an optimistically universal Bayes
consistent learning rule.
