Model Theory and Machine Learning

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 \emph{stability} and learnability in various settings of \emph{online learning.} In particular, this gives many new examples of mathematically interesting classes which are learnable in the online setting.

13 pages

References in corpus (1)

• Online Learning: Beyond Regret

Cited by in corpus (8)

• An Equivalence Between Private Classification and Online Prediction
• The Amalgamation Property for automorphisms of ordered abelian groups
• Closure Properties for Private Classification and Online Prediction
• Model theory and combinatorics of banned sequences
• Thicket Density
• Regular partitions of gentle graphs
• Mixing Deep Learning and Multiple Criteria Optimization: An Application to Distributed Learning with Multiple Datasets
• Littlestone and VC-dimension of families of zero sets