Perceptron Convergence Theorem

If training data $D_n$ is linearly separable, then the Perceptron algorithm is guaranteed to find a linear separator.

Perceptron Convergence Theorem

If there is:

• Some ${\theta }^{\ast }$ such that $y\cdot \frac{{\theta }^{\ast T}x}{||{\theta }^{\ast }||}\ge \gamma >0$ for all $i=1,\cdots ,n$
  • (Margin of ${\theta }^{\ast }$ with respect to dataset $D$ is $\gamma$)
• $||x^{(i)}||\le R$
  • (Magnitude of data points is bounded by R)

Then:

• Perceptron will make at most ${\left(\frac{R}{\gamma }\right)}^2$ mistakes

Proof: