Shortest Program Interpolation Learning

Naren Sarayu Manoj, Nathan Srebro
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4881-4901, 2023.

Abstract

We prove that the Minimum Program Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asymptotic behavior in the presence of random label noise.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-manoj23a, title = {Shortest Program Interpolation Learning}, author = {Manoj, Naren Sarayu and Srebro, Nathan}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {4881--4901}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/manoj23a/manoj23a.pdf}, url = {https://proceedings.mlr.press/v195/manoj23a.html}, abstract = {We prove that the Minimum Program Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asymptotic behavior in the presence of random label noise.} }
Endnote
%0 Conference Paper %T Shortest Program Interpolation Learning %A Naren Sarayu Manoj %A Nathan Srebro %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-manoj23a %I PMLR %P 4881--4901 %U https://proceedings.mlr.press/v195/manoj23a.html %V 195 %X We prove that the Minimum Program Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asymptotic behavior in the presence of random label noise.
APA
Manoj, N.S. & Srebro, N.. (2023). Shortest Program Interpolation Learning. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:4881-4901 Available from https://proceedings.mlr.press/v195/manoj23a.html.

Related Material