Speaker: Shay Moran (Technion)

Title: Learning: generalization and simplification of binary-labeled classes

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