Average-Case Information Complexity of Learning

Ido Nachum, Amir Yehudayoff
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:633-646, 2019.

Abstract

How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension $d$? Previous works have shown that even for $d=1$ the amount of information may be unbounded (tend to $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals $O(d)$ bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm \emph{knows} the underlying distribution on inputs, then there is a learner that reveals little information on an average concept \emph{without knowing} the distribution on inputs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v98-nachum19a, title = {Average-Case Information Complexity of Learning}, author = {Nachum, Ido and Yehudayoff, Amir}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {633--646}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/nachum19a/nachum19a.pdf}, url = {https://proceedings.mlr.press/v98/nachum19a.html}, abstract = {How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension $d$? Previous works have shown that even for $d=1$ the amount of information may be unbounded (tend to $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals $O(d)$ bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm \emph{knows} the underlying distribution on inputs, then there is a learner that reveals little information on an average concept \emph{without knowing} the distribution on inputs.} }
Endnote
%0 Conference Paper %T Average-Case Information Complexity of Learning %A Ido Nachum %A Amir Yehudayoff %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-nachum19a %I PMLR %P 633--646 %U https://proceedings.mlr.press/v98/nachum19a.html %V 98 %X How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension $d$? Previous works have shown that even for $d=1$ the amount of information may be unbounded (tend to $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals $O(d)$ bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm \emph{knows} the underlying distribution on inputs, then there is a learner that reveals little information on an average concept \emph{without knowing} the distribution on inputs.
APA
Nachum, I. & Yehudayoff, A.. (2019). Average-Case Information Complexity of Learning. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:633-646 Available from https://proceedings.mlr.press/v98/nachum19a.html.

Related Material