Convergence speed of perceptron algorithm

Question

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.

Answer 1

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.