Non-uniform Online Learning: Towards Understanding Induction
Zhou Lu
Can a physicist make only finite errors in the endless pursuit of the law of
nature? This millennium-old question of inductive inference is a fundamental,
yet mysterious problem in philosophy, lacking rigorous justifications. While
classic online learning theory and inductive inference share a similar
sequential decision-making spirit, the former's reliance on an adaptive
adversary and worst-case error bounds limits its applicability to the latter.
In this work, we introduce the concept of non-uniform online learning, which we
argue aligns more closely with the principles of inductive reasoning. This
setting assumes a predetermined ground-truth hypothesis and considers
non-uniform, hypothesis-wise error bounds. In the realizable setting, we
provide a complete characterization of learnability with finite error: a
hypothesis class is non-uniform learnable if and only if it's a countable union
of Littlestone classes, no matter the observations are adaptively chosen or iid
sampled. Additionally, we propose a necessary condition for the weaker
criterion of consistency which we conjecture to be tight. To further promote
our theory, we extend our result to the more realistic agnostic setting,
showing that any countable union of Littlestone classes can be learnt with
regret $\tilde{O}(\sqrt{T})$. We hope this work could offer a new perspective
of interpreting the power of induction from an online learning viewpoint.