I'm currently reading Foundations of Machine Learning by M. Mohri, A. Rostamizadeh, A. Talwalkar and according to their definition a concept class $C$ is said to be PAC-learnable if
$$Pr_{S \sim D^m}[R(h_s)\leq\varepsilon] \geq 1-\delta$$
holds for any sample size $m \geq poly(1/\varepsilon,1/\delta,n,\mathrm{size}(c))$.
I have problems understanding the definition of the parameters $n$ and $\mathrm{size}(c)$. The book defines them as follows:
We denote by $\mathcal{O}(n)$ an upper bound on the cost of the computational representation of any element $x \in \mathcal{X}$ (the input space) and by $\mathrm{size}(c)$ the maximal cost of the computational representation of $c \in C$.
A general answer would be greatly appreciated but I also have two examples I would like to understand in detail:
- Axis-aligned rectangles: Each rectangle can be represented by its corners which are points in $\mathbb{R}^2$, so the computational cost is constant. Therefore, $poly$ is actually a polynomial in $1/\varepsilon$ and $1/\delta$, correct?
- Universal concept class: Consider $\mathcal{X} = \{0,1\}^n$ and let $U_n$ be the concept class formed by all subsets of $\mathcal{X}$. Here the computational cost for an element $x \in \mathcal{X}$ is $n$, so $poly$ is a polynomial in $1/\varepsilon, 1/\delta$ and $n$ … ?
Especially the second example illustrates my problem very well: Taking $n$ as an additional parameter only makes sense (imho) if one considers all concept classes $U_n$ at once, because for a fixed class $U_n$ the cost of the computational representation is again constant.
I think my problem is that I don't understand the part
… denote by $\mathcal{O}(n)$ an upper bound on the cost …
- I assume that this is big O notation, but how can we say that $\mathcal{O}(n)$ is an upper bound on the cost?
- And why can we not say that it is constant in the second example?