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.

  • $\begingroup$ This sounds more like a theoretical question, hence better suited for Cross Validated. $\endgroup$
    – desertnaut
    Oct 25, 2019 at 9:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.