VC dimension and optimal mistake bound

I have a question regarding optimal mistake bound for learning algorithm

There is a famous fact that $VC(C) \leq Opt(C)$,

where $C$ - set of learning concepts,

VC(C) - VC dimension of C,

$Opt(C)$ - the smallest mistake bound (of the best learning algorithm) on the hardest learning concept $c \in C$ .

I don't understand why $VC(C) \leq Opt(C)$, in my opinion the notion of best algorithm $A$ is so vague that you cannot for sure say that $VC(C)$ is not more than $Opt(C)$

For example, $VC(line\ on\ the\ plane)$=3 , it means that $Opt(C) \geq 3$ in words it means for the hardest concept $c \in C$ (represented as a line on the plane) the number of mistakes of the best learning algorithm is more than 3.

Why the above fact is so strong?

• Can you provide a reference or more context? In the realizable case shouldn't $Opt(C) = 0$? Maybe I'm missing something... – alto Dec 19 '13 at 14:57

One way to think of online learning is a game between the learner and an adversarial environment. The environment produces an example $x_t$ at time $t$. The learner then outputs a label $\hat{y}_t \in \{-1,1\}$. Finally the environment outputs the true label of $y_t$ and the learner suffers a mistake if $\hat{y}_t \neq y_t$.
Assume the learner is trying to learn some some finite hypothesis class $C$ over an instance space $\mathcal{X}$ with $\text{VCdim}(C) = d$. Let $X = \{x_1, \cdots, x_d\} \subseteq \mathcal{X}$ be a shattered set. At any time $1 \le t \le d$ the environment reveals $x_t$ and the learner outputs $\hat{y}_t$. The environment then selects a new hypothesis $c \in C$ such that $c(x_t) = -\hat{y}_t$ and $c(x_i) = y_i$ for $1 \le i \le t$. There will always exist such a hypothesis $c \in C$ since $X$ is shattered by $C$. So the learner makes at least $d$ mistakes. Since this argument was independent of the learning algorithm it follows that \begin{align*} \text{VCdim}(C) &\le \text{Opt}(C). \end{align*}