  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.

Machine Learning;Machine Learning