What is the relevance of the concept size to the time constraints in PAC learning?

Question

My question is about the relevance of concept size to the polynomial-time/example constraints in efficient PAC-learning. To ask my question precisely I must first give some definitions.

Definitions:

Define the input space as $X_n = {\left\{ 0,1\right\} }^n$ and a concept $c$ as a subset of $X_n$. For example, all vectorized images of size $n$ representing a particular numeral $i$ (e.g. '5') collectively form the concept $c_i$ for that numeral. A concept class $C_n$ is a set of concepts. Continuing our example, the vectorized numeral concept class $\left\{ c_0, c_1, \dots c_9\right\}$ is the set of all ten vectorized numeral concepts for a given dimension $n$.

As an extension to include all dimensions we define $\mathcal{C} = \cup_{n \geq 1} C_n$. A hypothesis set $H_n$ is also a fixed set of subsets of $X_n$ (which might not necessarily align with $C_n$) and we define $\mathcal{H} = \cup_{n \geq 1} H_n$.

The following definition of efficient PAC-learnability is adapted from An Introduction to Computational Learning Theory by Kearns and Vazirani.

$\mathcal{C}$ is efficiently PAC-learnable if there exists an algorithm $\mathcal{A}$ such that for all $n \geq 1,$ all concepts $c \in C_n$, all probability distributions $D$ on $X_n$, and all $\epsilon, \delta \in \left(0,1\right)$, the algorithm halts within polynomial time $p{\left( n, \text{size}{\left(c\right)}, \frac{1}{\epsilon}, \frac{1}{\delta}\right)}$ and returns a hypothesis $h \in H_n$ such that $$ \underset{x \sim D}{\mathbb{P}}{\left[ h{\left(x\right)} \neq c{\left(x\right)} \leq \epsilon\right]} \geq 1 - \delta.$$

Question:

Now, in the polynomial $p{\left(\cdot, \cdot, \cdot, \cdot \right)}$, I understand the dependence on $\epsilon$ (accuracy) and $\delta$ (confidence). Additionally, I understand why the polynomial should depend on $n$ - the concept of learnability should be invariant to the time burden incurred from increasing the dimension of the input space (e.g. increasing the resolution of the image). What I do not understand is why the dependence on the size of the target concept (which I believe is usually taken to mean the smallest encoding of the target concept)?

Answer 1

The size of a concept representation is important because the time to write/process this representation is a lower bound on the running time of the learning algorithm.

For example, you can represent the boolean parity function with a circuit composed of $\land$, $\lor$ and $\neg$ such that its size is polynomial in $n$, while, if you used a disjunctive normal form (DNF) representation, you might need an exponential number of terms. This may give you some intuition behind this example.

For some concept classes, $\text{size}(c)$ is already bounded by a polynomial in $n$, so the only practical requirement that you need in those cases is that the algorithm runs in time polynomial in $n$. For example, if you consider the class of DNF with at most 3 terms, then you know that the number of literals is at most $3n$ (i.e. each term can contain at most $n$ literals, either $x_i$ or $\neg x_i$ but not both, for all literals $x_1, \dots, x_n$).