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 scale invariant characterization of PAC style learnability of such classes. The question of scale sensitive characterization remained open. In this paper we fully resolve the question by showing that there can be no scale sensitive combinatorial characterization of PAC style learnability of classes of probability distributions.