PAC learning definition and the properties of the problem I am trying to understand the basic definition of realizable PAC learning from Shai Shalev-Shwartz's "understanding machine learning". They define a hypothesis class H to be PAC learnable if for every distribution D over the instances, and for any labeling function f, an approximately correct hypothesis can be learned with high probability over the random choice of a training set. 
An issue that is not entirely clear ot me: they define PAC learnability as a property of an hypothesis class, i.e., of a solution. Intuitively I'd expect that learnability would be a property of the problem, as some problems are harder than others. What role do the properties of the problem play in the definition?
 A: The problem is generally to find a hypothesis for which the generalization bound is small.
For example, if you want to find the best SVM to classify your data, your hypothesis class is given exactly by a set of weights $w$ and biases $b$. The fact that you try to maximize the margin is reflected only in the fact that this will give you a good generalization bound later on. But this works only because SVMs are a relatively simple class. 
However, if you take a very complex class, all NNs of all sizes with appropriate nonlinearities, say, you have a problem. Now your hypothesis class is so large that you can fit arbitrary training data without actually learning anything useful from the data.
A: I would just add to the previous (excellent) answer, that Shai Shalev-Shwartz define the statistical learning framework already in chapter 2, previous to the PAC model, and their Definition 3.1 of PAC learning is actually a refinement of what they already explained in the previous chapter.
"(...) a learning algorithm receives as input a training set S, sampled
from an unknown distribution D and labeled by some target function f , and
should output a predictor hS : X → Y (the subscript S emphasizes the fact that
the output predictor depends on S). The goal of the algorithm is to find hS that
minimizes the error with respect to the unknown D and f" (page 15).
Then they explain that in order to avoid overfitting, one should restrict the empirical risk minimization to a chosen hypothesis class H (introducing therefore some bias). The 'complexity' of this class will then determine the size of he training data that is needed to achieve a given accuracy.
