# Characterizations of uniformly learnable function classes in the distribution-specific setting

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.

$$D$$ is uniformly learnable if and only if $$F$$ is totally bounded in the sense of the $$L_1$$ metric.
The non-uniform case is covered in a second paper by the same authors, Nonuniform learning. The condition then is that $$F$$ be countably bounded, meaning for any $$\epsilon$$ it is covered by a countable collection of $$\epsilon$$-balls.