4

There has been a recent line of work on computable learnability: http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf This seems to be exactly the sort of thing you're asking about. You also ask about the implications $1\implies 2$ and $2\implies 3$. The latter is indeed ...


3

The standard no-free-lunch argument can be stated and understood without any knowledge or deep understanding of VC theory. (The upper bound, with its reliance on Sauer’s lemma, is intimately intertwined with VC theory.) Let $\mathcal{X}=\mathbb{N}$ be the set of all natural numbers and let $\mathcal{C}$ be the collection of all Boolean functions (classifiers)...


2

I believe a common name for what you describe as $\mathcal{N}(\mathcal{F},2n)$ is the "growth function". For a concept class $\mathcal{F} = \{ h : X \to \{0,1\} \}$ and $S = (x_1,\dots,x_n) \subseteq X^n$ we define $$ \mathcal{F} \Big|_S = \{(h(x_1,\dots,h(x_n)) ~|~ h \in \mathcal{F}\}.$$ Then, the "growth function" for $\mathcal{F}$ is: $...


1

I know it's generally considered bad form to add another answer on top of an accepted one, but this one is by special request and it's a topic that deserves its own discussion. The topic is: Effective learning algorithms vs. learning rules. A learning rule is simply a mathematically well-defined mapping from a labeled sample to some function class. (The ...


Only top voted, non community-wiki answers of a minimum length are eligible