# Convergence speed of perceptron algorithm

I was reading the convergence proof for the perceptron algorithm. It says under the assumption that there are some $$R$$, $$\theta^*$$ with $$|\theta^*| = 1$$ and $$\gamma > 0$$, such that $$y_t(x_t\cdot \theta^*) \geq \gamma$$ and $$|x_t|\leq R$$ for $$t = 1, 2, \dots n$$, the perceptron algorithm makes at most $$\frac{R^2}{\gamma^2}$$ errors.

What I didn't fully understand how $$\theta^*$$ was related to $$x_t$$ and how it affected the convergence of PLA. If I scale down all $$x_t$$ by a factor $$k$$, then I have $$|x_t| \leq \frac{1}{k}R$$, but what happens to $$\theta^*$$ and $$\gamma$$? Does scaling down $$x_t$$ gives a smaller upper bound and thus PLA converges faster? I personally believe how fast PLA converges is decided by how data is distributed rather than $$|x_i|$$, is it correct? Any hint or answer is appreciated, thanks in advance.

• This sounds more like a theoretical question, hence better suited for Cross Validated. Commented Oct 25, 2019 at 9:27