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?

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

1 Answer 1


So this result pertains to the online mistake bound framework. I found a proof here in Shai Shalev-Shwartz's lecture notes. I'll give a rough sketch of it here for the sake of keeping things self contained.

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$.

The thing to note for the above bound is that it doesn't matter if the environment switches the true hypothesis mid-game, provided the new hypothesis is consistent with all previous labelings. This is because it would be the same as selecting the new hypothesis in the first place.

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*} $$


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.