From learnable objects to learnable random objects
This work addresses foundational theoretical questions in machine learning about the generalization of learnability from deterministic to random objects, with incremental contributions to existing frameworks.
The paper tackles the problem of relating the learnability of a base class of functions to that of derived statistical functions, establishing improved sample complexity bounds for agnostic learning in both PAC and online settings, and providing counterexamples for realizable learning.
We consider the relationship between learnability of a "base class" of functions on a set $X$, and learnability of a class of statistical functions derived from the base class. For example, we refine results showing that learnability of a family $h_p: p \in Y$ of functions implies learnability of the family of functions $h_μ=λp: Y. E_μ(h_p)$, where $E_μ$ is the expectation with respect to $μ$, and $μ$ ranges over probability distributions on $X$. We will look at both Probably Approximately Correct (PAC) learning, where example inputs and outputs are chosen at random, and online learning, where the examples are chosen adversarily. For agnostic learning, we establish improved bounds on the sample complexity of learning for statistical classes, stated in terms of combinatorial dimensions of the base class. We connect these problems to techniques introduced in model theory for "randomizing a structure". We also provide counterexamples for realizable learning, in both the PAC and online settings.