Submission date: 19 January 2018

Abstract:

About 25 years ago, it came to light that a single combinatorial property determines both an important dividing line in model theory (NIP) and machine learning (PAC-learnability). The following years saw a fruitful exchange of ideas between PAC learning and the model theory of NIP structures. In this article, we point out a new and similar connection between model theory and machine learning, this time developing a correspondence between stability and learnability in various settings of online learning. In particular, this gives many new examples of mathematically interesting classes which are learnable in the online setting.

Mathematics Subject Classification: 03C95, 03C98, 03C45

Keywords and phrases:

Full text arXiv 1801.06566: pdf, ps.