Let $X$ be some input domain (a measurable space). Then let $D$ be some class of probability distributions on $X\times\{0,1\}$. We will call such distributions learning tasks. We say that $D$ is uniformly learnable if there exists a learning procedure $L$ mapping finite subsets of $X\times\{0,1\}$ onto functions $X\to\{0,1\}$ such that for any $\epsilon,\delta$, the test error of $L$ is at most $\epsilon$ with probability at least $1-\delta$ over random training sets of size $n$, for sufficiently large $n$.
This is just the standard setting of PAC learnability.
Let $F$ be some class of binary functions on $X$. For any $f\in F$ and any probability measure on $\mu$, we can construct a learning task by sampling from $X$ using $\mu$ and then labelling that input using $f$. Denote this distribution by $f(\mu)$. Now let $D$ denote the class of learning problems of all $f(\mu)$ for all probability measures $\mu$ and all $f\in F$. Then $D$ is uniformly learnable if and only if $F$ is of finite VC dimension (Shalev-Shwartz/Ben-David, Theorem 6.7). This is sometimes called the distribution-free setting.
In the fixed-distribution setting, $D$ is instead the set of all measures $f(\mu)$ for $f\in F$ and $\mu$ a specific probability measure. When is $D$ uniformly learnable?
I suspect this is related to Rademacher complexity, but I can't find any clear statement in any source of an if-and-only-if condition for uniform learnability.
