[edit]

# Sample Compression for Real-Valued Learners

*Proceedings of the 30th International Conference on Algorithmic Learning Theory*, PMLR 98:466-488, 2019.

#### Abstract

We give an algorithmically efficient version of the
learner-to-compression scheme conversion in Moran and Yehudayoff
(2016). We further extend this technique to real-valued hypotheses,
to obtain a bounded-size sample compression scheme via an efficient
reduction to a certain generic real-valued learning strategy. To our
knowledge, this is the first general compressed regression result
(regardless of efficiency or boundedness) guaranteeing uniform
approximate reconstruction. Along the way, we develop a generic
procedure for constructing weak real-valued learners out of abstract
regressors; this result is also of independent interest. In
particular, this result sheds new light on an open question of
H. Simon (1997). We show applications to two regression problems:
learning Lipschitz and bounded-variation functions.