No Scale Sensitive Dimension for Distribution Learning

Learning probability distributions is one of the most basic statistical learning tasks. While for many learning tasks learnability of a class can be characterized by a combinatorial dimension (like the VC-dimension for binary classification prediction), no such characterization is known for classes of probability distributions. A leap toward resolving this long-standing problem was made recently by Lechner and Ben-David who showed that there can be no \emph{scale invariant} characterization of PAC style learnability of such classes. The question of \emph{scale sensitive} characterization remained open. In this paper we fully resolve the question by showing that there can be no \emph{scale sensitive} combinatorial characterization of PAC style learnability of classes of probability distributions.