Combinatorial Characterizations of the Learnability of Conditional Distributions

The paper studies classes of functions that map inputs to probability distributions over a finite label set. Labels are drawn from the conditional distribution of an unknown target in the class, and learning is measured by excess risk under a bounded proper loss satisfying two mild conditions.

The authors define the fat-\(\gamma\) Natarajan dimension, which generalises both the fat-shattering and Natarajan dimensions, and prove that its finiteness at every \(\gamma > 0\) is necessary and sufficient for learnability. A fat-\(\gamma\) graph dimension gives an equivalent characterisation, and a class is learnable if and only if each coordinate class is learnable in the probabilistic concept model. This extends the classical combinatorial theory of PAC learning to probabilistic prediction.