The unstable formula theorem revisited via algorithms
This work addresses foundational gaps in learning models for researchers in theoretical machine learning and model theory, though it appears incremental by building on existing analogies and recent work.
The paper tackles the interaction between model theory and algorithmic learning by introducing a new statistical learning model called 'Probably Eventually Correct' (PEC) and characterizing Littlestone classes in terms of it, leading to a complete algorithmic analogue of Shelah's Unstable Formula Theorem.
This paper is about the surprising interaction of a foundational result from model theory, about stability of theories, with algorithmic stability in learning. First, in response to gaps in existing learning models, we introduce a new statistical learning model, called ``Probably Eventually Correct'' or PEC. We characterize Littlestone (stable) classes in terms of this model. As a corollary, Littlestone classes have frequent short definitions in a natural statistical sense. In order to obtain a characterization of Littlestone classes in terms of frequent definitions, we build an equivalence theorem highlighting what is common to many existing approximation algorithms, and to the new PEC. This is guided by an analogy to definability of types in model theory, but has its own character. Drawing on these theorems and on other recent work, we present a complete algorithmic analogue of Shelah's celebrated Unstable Formula Theorem, with algorithmic properties taking the place of the infinite.