PAC learning model definition

Question

The probably approximately correct (PAC) learning model is defined as:

A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such that for any $ε>0$ and $δ>0$, for all distributions $D$ on $X$ and for any target concept $c∈C$, the following holds for any sample size $m≥poly(1/ε,1/δ,n,size(c))$:

$Pr[R(hs)≤ε]≥1-δ$

where $R(hs)$ is the generalization error over a sample $S$ of size $m$ containing instances of variable $X$ following distribution $D$ and $size(c)$ is the maximal cost of the computational representation of $c∈C$.

I know $poly(1/ε,1/δ,n,size(c))$ is a polynomial. But what is the explicit form of $poly(1/ε,1/δ,n,size(c))$? What are the variables? What is its degree?

Answer 1

There are no constraints on $poly(\cdot,\cdot,\cdot,\cdot)$ other than its being a polynomial, or more generally, a polynomially bounded function (that is, a function bounded by a polynomial); the difference doesn't matter in this case. Without loss of generality, you can assume that for some $A,B > 0$, $poly(x,y,z,w) = A(xyzw)^B$.

The definition is trying to model the situation that only a small number of samples is needed to learn the concept. In order to quantify "small", we need first to decide with respect to what quantities it is going to be small (in this case, $\epsilon,\delta,n,size(c)$), and second, how small is "small". In this case, we define "small" to be any function growing at most polynomially in $1/\epsilon,1/\delta,n,size(c)$. In other cases we have more stringent requirements, say we want "small" to be polynomial in $\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$.

A standard definition in complexity theory is that of polynomial time. We say that an algorithm for solving some problem is efficient if on an input of size $n$ it runs in time polynomial in $n$, that is, its running time $T(n)$ is bounded by some polynomial in $n$. In your terminology, we could state this as $T(n) \leq poly(n)$ for some polynomial $n$. As before, if $T(n) \leq poly(n)$ for some polynomial $poly(\cdot)$, then in fact $T(n) \leq An^B$ for some $A,B>0$, and so without loss of generality we can assume that $poly(n) = An^B$. But we don't want to decide in advance on the values of $A,B$. We are happy as long as some values of $A,B$ work.

Your case is similar, only the polynomial is allow to depend on several quantities rather than just one quantity.