Nonuniform Learnability

Two learning guarantees look almost identical on the surface. In both, a learning algorithm receives a sample, produces a hypothesis, and that output must be $(\epsilon, \delta)$-competitive with every other hypothesis in the class. The two notions differ in one narrow place: whether the number of examples needed for the guarantee must stay the same across the different comparison hypotheses. This article follows that single question from start to finish.

Start with what the two notions have in common. The algorithm's output must be $(\epsilon, \delta)$-competitive with every other hypothesis in the class. The algorithm is not allowed to pick a hypothesis that is clearly worse than some competitor, at least with the stated confidence and accuracy. Nothing about this requirement is relaxed when we move from agnostic PAC learnability to nonuniform learnability.

So the question that separates the two notions is not which hypotheses are used for comparison. Every hypothesis in the class is still a comparison candidate. The real question is whether the number of examples needed for the guarantee must be uniform across those comparisons.

To compare the notions, fix a hypothesis h in the class and ask how the error of the algorithm's output compares with h. Under agnostic PAC learnability, the required sample size m cannot depend on which h was chosen for that comparison. One m must work for the comparison with every hypothesis in the class. The sample-size requirement is therefore h-independent.

The word uniform in this setting describes the sample-size condition. The algorithm still compares its output with every hypothesis in the class, but the required m is not allowed to change from one comparison hypothesis to another. This is a stronger requirement than allowing m to vary with h, which is why the uniform version is the more demanding of the two.

Notice what this example did not require. We did not compute any numerical value for m, and we did not need to know the class or the distribution. The decisive move was only to ask whether h is permitted to influence m. That is the same question the source treats as central.

Nonuniform learnability keeps the requirement that the output be $(\epsilon, \delta)$-competitive with every other hypothesis in the class. Its relaxation concerns only the sample-size policy: the bound may be different for different comparison hypotheses. Nonuniform learnability therefore permits a more flexible sample-size rule while retaining the same comparison requirement.

This is why nonuniform learnability is a relaxation of agnostic PAC learnability. Any guarantee that agnostic PAC learnability provides, with one sample size valid for every comparison, already meets the nonuniform condition, since a constant function of h is a special case of a function of h. Relaxing the sample-size rule can only enlarge the set of rules that qualify, so dropping the uniform requirement can only make the set of learnable classes larger, never smaller.

Under nonuniform learnability, each comparison hypothesis gets its own required sample size $m(h)$. Think of it as a lookup table: every key is a hypothesis, and the value stored under that key is the number of examples the guarantee needs when h is the comparator. The table is not forced to contain the same entry in every row.

Contrast this with agnostic PAC learnability. There the table would have one value shared by every row: a single m that works regardless of which hypothesis is the comparator. The keys are the same in both cases; only the constraint on the values differs.

Both notions require the output to be $(\epsilon, \delta)$-competitive with every other hypothesis in the class. They differ only in whether the sample size may depend on the comparison hypothesis h. Agnostic PAC learnability uses one h-independent sample size. Nonuniform learnability permits m(h) to vary with h, which makes it a relaxation of agnostic PAC learnability.