Perceptron - Convergence proof 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:


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