Perceptron - Convergence proof

Question

I studied the perceptron algorithm and I'm trying to prove the convergence by myself. However, I'm wrong somewhere and I am not able to find the error.

Assumption:

1. We assume that there is some $\gamma > 0$ such that $$y_{t}(\theta ^{*})^{T}x_{t} \geq \gamma $$ for all $t = 1, \ldots , n$. The additional number $\gamma > 0$ is used to ensure that each example is classified correctly with a finite margin.

2. We will assume that all the (training) images have bounded Euclidean norms, i.e., $$\left \| \bar{x_{t}} \right \|\leq R$$ for all $t$ and some finite $R$

By hypothesis the learning rule is:

$$\theta ^{(k)}= \theta ^{(k-1)} + \mu y_{t}\bar{x_{t}}$$

Now, $$(\theta ^{*})^{T}\theta ^{(k)}=(\theta ^{*})^{T}\theta ^{(k-1)} + \mu y_{t}\bar{x_{t}} \geq (\theta ^{*})^{T}\theta ^{(k-1)} + \mu \gamma $$ so , by induction $$(\theta ^{*})^{T}\theta ^{(k)}\geq k\mu \gamma $$

At the same time, $$\left \| \theta ^{(k)} \right \|^{2} = \left \| \theta ^{(k-1)}+\mu y_{t}\bar{x_{t}} \right \|^{2} = \left \| \theta ^{(k-1)} \right \|^{2}+2\mu y_{t}(\theta ^{(k-1)^{^{T}}})\bar{x_{t}}+\left \| \mu \bar{x_{t}} \right \|^{2} \leq \left \| \theta ^{(k-1)} \right \|^{2}+\left \| \mu\bar{x_{t}} \right \|^{2}\leq \left \| \theta ^{(k-1)} \right \|^{2}+\mu ^{2}R^{2}$$

So, by induction

$$\left \| \theta ^{(k)} \right \|^{2} \leq k\mu ^{2}R^{2}$$

We can now combine parts 1) and 2) to bound the cosine of the angle between $\theta^∗$ and $\theta(k)$:

$$\cos(\theta ^{*},\theta ^{(k)}) =\frac{\theta ^{*}\theta ^{(k)}}{\left \| \theta ^{*} \right \|\left \|\theta ^{(k)} \right \|} \geq \frac{k\mu \gamma }{\sqrt{k\mu ^{2}R^{2}}\left \|\theta ^{2} \right \|}$$

Since cosine is bounded by one, we get:

$$k \leq \frac{R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$

The problem is that the correct result should be:

$$k \leq \frac{\mu ^{2}R^{2}\left \|\theta ^{*} \right \|^{2}}{\gamma ^{2}}$$

Answer 1

What you presented is the typical proof of convergence of perceptron proof indeed is independent of $\mu$. Hence the conclusion is right.

Typically $\theta^*x$ represents a hyperplane that perfectly separate the two classes.

The formula $k \le \frac{\mu^2 R^2 \|\theta^*\|^2}{\gamma^2}$ doesn't make sense as it implies that if you set $\mu$ to be small, then $k$ is arbitarily close to $0$. It is saying that with small learning rate, it converges immediately. You might want to look at the termination condition for your perceptron algorithm carefully.