Abstract We set up a general context in which one can prove Sauer–Shelah type lemmas. We apply our general results to answer a question of Bhaskar [1] and give a slight improvement to a result of Malliaris and Terry [7]. We also prove a new Sauer–Shelah type lemma in the context of $ \operatorname {\textrm{op}}$ -rank, a notion of Guingona and Hill [4].
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
Abernethy, Jacob ; Agarwal, Shivani (Ed.)We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of learning in terms of various combinatorial quantities. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. Our approach is flexible and powerful enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular ω-languages), in some cases also producing new bounds on the number of queries.more » « less
-
Abernethy, Jacob ; Agarwal, Shivani (Ed.)We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of learning in terms of various combinatorial quantities. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. Our approach is flexible and powerful enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular ω-languages), in some cases also producing new bounds on the number of queries.more » « less
-
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.more » « less
Full Text Available