Inherent limitations of dimensions for characterizing learnability of distribution classes

Tosca Lechner, Shai Ben-David
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3353-3374, 2024.

Abstract

We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. While for many learning tasks (such as binary classification and online learning) there is a notion of dimension whose finiteness is equivalent to learnability within any level of accuracy, we show, rather surprisingly, that such parameter does not exist for distribution learning. Concretely, our results apply for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing PAC-learnability for any of the tasks: classification learning w.r.t. a restricted set of marginal distributions and learnability of classes of real-valued functions with continuous losses.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-lechner24a, title = {Inherent limitations of dimensions for characterizing learnability of distribution classes}, author = {Lechner, Tosca and Ben-David, Shai}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {3353--3374}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/lechner24a/lechner24a.pdf}, url = {https://proceedings.mlr.press/v247/lechner24a.html}, abstract = { We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. While for many learning tasks (such as binary classification and online learning) there is a notion of dimension whose finiteness is equivalent to learnability within any level of accuracy, we show, rather surprisingly, that such parameter does not exist for distribution learning. Concretely, our results apply for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing PAC-learnability for any of the tasks: classification learning w.r.t. a restricted set of marginal distributions and learnability of classes of real-valued functions with continuous losses.} }
Endnote
%0 Conference Paper %T Inherent limitations of dimensions for characterizing learnability of distribution classes %A Tosca Lechner %A Shai Ben-David %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-lechner24a %I PMLR %P 3353--3374 %U https://proceedings.mlr.press/v247/lechner24a.html %V 247 %X We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. While for many learning tasks (such as binary classification and online learning) there is a notion of dimension whose finiteness is equivalent to learnability within any level of accuracy, we show, rather surprisingly, that such parameter does not exist for distribution learning. Concretely, our results apply for several general notions of characterizing learnability and for several learning tasks. We show that there is no notion of dimension that characterizes the sample complexity of learning distribution classes. We then consider the weaker requirement of only characterizing learnability (rather than the quantitative sample complexity function). We propose some natural requirements for such a characterization and go on to show that there exists no characterization of learnability that satisfies these requirements for classes of distributions. Furthermore, we show that our results hold for various other learning problems. In particular, we show that there is no notion of dimension characterizing PAC-learnability for any of the tasks: classification learning w.r.t. a restricted set of marginal distributions and learnability of classes of real-valued functions with continuous losses.
APA
Lechner, T. & Ben-David, S.. (2024). Inherent limitations of dimensions for characterizing learnability of distribution classes. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:3353-3374 Available from https://proceedings.mlr.press/v247/lechner24a.html.

Related Material