Skip to content

10:20-12:00, 37/201. Meni Sadigurski : "Efficient Conversion of Learners to Bounded Sample Compressors".

Apr. 16, 2018
10:20

Room 201 in building 37

A lot of attention was put on the field of learning theory to try and characterize what can and can't be learned. One of the directions was the combinatorial notion of sample compression.

The first to prove full equivalence between the two notion was Moran and Yehudayoff (2016).

We give an algorithmically efficient version of this learner-to-compression scheme conversion.

In extending this technique to real-valued function classes, we also obtain, for the first time (regardless of efficiency or boundedness), an efficient regression-to-sample-compression converter, guaranteeing uniform approximate reconstruction.

Along the way, we develop a generic procedure for constructing weak real-valued learners out of abstract real-valued learning algorithms

The talk assume no prior knowledge of learning theory

This is a joint work with Prof. Aryeh Kontorovich and Prof. Steve Hanneke