The Taub Faculty of Computer Science Events and Talks

Generalization and simplification are two basic facets of learning. Learning theory gives several mathematical manifestations of these facets. We will present two of these:

(i) A generalization model: Probably Approximately Correct learning [Vapnik-Chervonenkis ’71, Valiant ’84], and
(ii) A simplification model: Sample compression schemes [Littlestone-Warmuth ’86].

Littlestone and Warmuth have shown that for these mathematical formalizations, the ability to simplify implies the ability to generalize, and asked whether the other direction holds. We will see an affirmative answer to this question.

No knowledge in machine learning will be assumed in the talk.

Based on a joint work with Amir Yehudayoff.