On Computable Online Learning
This work addresses foundational issues in online learning theory for researchers, showing incremental theoretical advancements in computability and optimality.
The paper tackles the problem of computable online learning by introducing new optimality conditions and showing that the Littlestone dimension does not characterize optimal mistake bounds in this setting. It proves computational separations between different optimality notions and demonstrates that finiteness of the Littlestone dimension no longer ensures learnability under weaker computability.
We initiate a study of computable online (c-online) learning, which we analyze under varying requirements for "optimality" in terms of the mistake bound. Our main contribution is to give a necessary and sufficient condition for optimal c-online learning and show that the Littlestone dimension no longer characterizes the optimal mistake bound of c-online learning. Furthermore, we introduce anytime optimal (a-optimal) online learning, a more natural conceptualization of "optimality" and a generalization of Littlestone's Standard Optimal Algorithm. We show the existence of a computational separation between a-optimal and optimal online learning, proving that a-optimal online learning is computationally more difficult. Finally, we consider online learning with no requirements for optimality, and show, under a weaker notion of computability, that the finiteness of the Littlestone dimension no longer characterizes whether a class is c-online learnable with finite mistake bound. A potential avenue for strengthening this result is suggested by exploring the relationship between c-online and CPAC learning, where we show that c-online learning is as difficult as improper CPAC learning.