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?

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.