We consider the long-standing question of finding a parameter of a class of probability distributions that characterizes its PAC learnability. We provide a rather surprising answer - no such parameter exists. Our techniques allow us to show similar results 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 (or characterization of learnability) for any of the tasks: classification learning for distribution classes, learning of binary classifications w.r.t. a restricted set of marginal distributions, and learnability of classes of real-valued functions with continuous losses.

本文考虑了一类概率分布的PAC可学习性的参数，并提供了一个令人惊讶的答案-没有这样的参数。作者使用自己的技术证明了相似的结果，并表明不存在可以描述学习复杂性的维度概念，并且对于这些类型分布的学习可行性没有描述性的特征。此外，该研究还表明，对于分类学习、二元分类、连续损失函数的学习，不存在描述性维度或学习可行性的特征。

无法描述分布学习——一个解决长期问题的简单方案