# 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.

If we scale $$x_t$$ by a factor $$m$$ (not using $$k$$ to prevent any confusion with the number of steps), the inequality becomes $$y_t((x_t/m) \cdot \theta^*)\geq \gamma/m\rightarrow y_t(x_t'\cdot\theta^*)\geq\gamma'$$ $$\gamma$$ acts like a margin of the boundary, i.e. how far the samples are off. If we scale the samples, the margin is also scaled. The boundary weights are always normalized, i.e. $$||\theta^*||=1$$, and isn't affected by scale changes in input, e.g. $$x+2y=5$$ and $$2x+4y=10$$ are the same line. Therefore, both $$R$$ and $$\gamma$$ are scaled the same way and we have $$k\leq \frac{(R/m)^2}{(\gamma/m)^2}=\frac{R^2}{\gamma^2}$$ So, it doesn't converge faster.