Mistake Bound Theorem

By Novikoff 1962, Block 1962

• For a dataset $\left\{(x_1,y_1),\dots ,(x_N,y_N)\right\}$ with $R\ge \Vert x_n{\Vert }_2$ and labels $y_n\in \left\{-1,1\right\}$
• Suppose $\exists u\in {\mathbb{R}}^D:\exists \gamma >0\wedge \gamma \le y_n{u}^{{}^{\top }}{x}_n$
  • $u$ can be thought of as a $w$ of a candidate for the margin of the dataset
• Then the PerceptronTrainingAlgorithm will make $\le \frac{R^2}{{\gamma }^2}$ mistakes on the training sequence