# Why does PAC learning focus on learnability of the hypothesis class and not the target function?

The definition of PAC learning is roughly

An algorithm is a PAC learning algorithm if it given enough data, for any target function, it asymptotically does as well as it possibly could given the functions it's capable of representing.

This definition seems sort of unambitious. In reality, I care more about approximating the target function well in an absolute sense, not just approximating it as well as my hypothesis class can muster. By some kind of no-free-lunch principle, it's probably not possible to be able to do this for all target functions, so we need to be satisfied with algorithms that learn well on a class of target functions. If I were to take a shot at defining a notion of "learning", it would look like this:

An algorithm learns a class $$\mathcal V$$ of random variables in $$\mathcal X\times\mathbb R$$ iff for any $$(X, Y)\in\mathcal V$$, then for any $$\delta, \epsilon$$, given enough i.i.d. samples of $$(X, Y)$$, the algorithm returns a function $$h$$ such that $$P(|h(X)-Y|\leq\epsilon)>1-\delta$$.

A class $$\mathcal V$$ of random variables is learnable iff there exists an algorithm that learns it.

I have two questions:

1. Why the emphasis on getting good bounds for approximating the hypothesis class, rather than the target function/distribution, when surely it's the latter we care about?
2. Is something like my definition also studied?
• Maybe I'm misunderstanding your definitions but I would say that the true distribution of X,Y is unknown (or, I think, what you call V) so you can't sample from it and therefore your definition has no practical application. PAC addresses this issue by falling back to the empirical risk instead of the true error. – oW_ Sep 27 at 2:59
• @oW_ You're misunderstanding my definitions I think. Of course you can sample from the distribution of $X, Y$ - otherwise how would you compute an empirical risk? The only reason $X, Y$ appears in my definition but not the standard one is because I made my definition a bit more explicit for clarity, they would appear in the standard one as well if I were more precise. Whatever training and test datasets you have, they are samples of the unknown distribution of $(X, Y)$. – Jack M Sep 27 at 8:55
• The empirical risk is defined over the distribution of the training data and not the true distribution. PAC learning is concerned with generalizing from the training data to the true (unknown) data distribution. You can always do well on just the training data. – oW_ Sep 27 at 17:07

I also suspect that in the universe of all possible functions, the optimal function could always be some kind of infinite non-generalizing function which assigns exactly the true $$Y$$ for any $$X$$ (at least to the extent possible, i.e. when $$X\neq X' \Rightarrow Y\neq Y'$$). In this perspective restricting the class of target functions forces the algorithm to generalize, since it must represent the data in the finite space of the parameters of the class of functions.