From learnable objects to learnable random objects

Abstract

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 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.

Tasks

Reproductions