Let $M_{A}(C)$ be the max number of mistakes made by algorithm $A$ to learn
concepts in $C$. (maximum over all possible $c \in C$, and all possible
training sequences)
\[M_{A}(C) \equiv \max_{c \in C} M_{A}(c)\]
Let $C$ be an arbitrary non-empty concept class. The
optimal mistake bound for $C$, denoted $Opt(C)$, is the minimum
over all possible learning algorithms $A$ of $M_{A}(C)$. \[Opt(C)
\equiv \min_{A \in learning algorithms} M_{A}(C) \]
We can relate this to the VC dimension with
\[ VC(C) \leq Opt(C) \leq M_{Halving}(C) \leq log_{2}(|C|). \]