Publications > Preprint server > Preprint Number 2307
Preprint Number 2307
2307. Maryanthe Malliaris, Shay Moran The unstable formula theorem revisited E-mail: Submission date: 9 December 2022 Abstract: We first prove that Littlestone classes, those which model theorists call stable, characterize learnability in a new statistical model: a learner in this new setting outputs the same hypothesis, up to measure zero, with probability one, after a uniformly bounded number of revisions. This fills a certain gap in the literature, and sets the stage for an approximation theorem characterizing Littlestone classes in terms of a range of learning models, by analogy to definability of types in model theory. We then give a complete analogue of Shelah's celebrated (and perhaps a priori untranslatable) Unstable Formula Theorem in the learning setting, with algorithmic arguments taking the place of the infinite. Mathematics Subject Classification: Keywords and phrases: |
Last updated: December 20 2022 19:07 | Please send your corrections to: |