Sample Compression for Real-Valued Learners

Steve Hanneke, Aryeh Kontorovich, Menachem Sadigurschi

ALT 2019 pp. 466-488

/alt/2019/hanneke2019alt-sample/

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.

PDF ALT Semantic Scholar

Cite

Text

Hanneke et al. "Sample Compression for Real-Valued Learners." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.

Markdown

[Hanneke et al. "Sample Compression for Real-Valued Learners." Proceedings of the 30th International Conference on Algorithmic Learning Theory, 2019.](https://mlanthology.org/alt/2019/hanneke2019alt-sample/)

BibTeX

@inproceedings{hanneke2019alt-sample,
  title     = {{Sample Compression for Real-Valued Learners}},
  author    = {Hanneke, Steve and Kontorovich, Aryeh and Sadigurschi, Menachem},
  booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory},
  year      = {2019},
  pages     = {466-488},
  volume    = {98},
  url       = {https://mlanthology.org/alt/2019/hanneke2019alt-sample/}
}