# Cost of computational representation in PAC-learning definition

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:

1. 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?
2. 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?

I found a satisfactory answer in chapter 1.2.2 of "An Introduction to Computational Learning Theory" by Michael J. Kearns and Umesh V. Vazirani.

Basically they consider for each natural number $n$ a concept class $\mathcal{C}_n$ over $\mathcal{X}_n$ (where $\mathcal{X}_n$ is either $\{0,1\}^n$ or $\mathbb{R}^n$), and let $\mathcal{C} = \bigcup_{n \geq 1} \mathcal{C}_n$ and $\mathcal{X} = \bigcup_{n \geq 1} \mathcal{X}_n$. So it is indeed necessary to look at all concept classes at once in order to make sense of the parameters $n$ and $\mathrm{size}(c)$ in the polynomial that gives a lower bound of the required sample size.

In the cases $\mathcal{X}_n = \{0,1\}^n$ or $\mathbb{R}^n$ it is also clear that the cost of computational representation is in $\mathcal{O}(n)$.

All this makes sense in any setting that works for arbitrary $n$, e.g. learning axis-aligned rectangles (or $n$-dimensional boxes) can (in a natural way) be generalized to $\mathbb{R}^n$ and the universal concept class $U_n$ is obviously another example.