Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 218 / 4 / c / Solution

This is a normalized perceptron algorithm. Because $\Vert Z_i{\Vert }_2=1$, an update on a misclassified point obeysHere the two inequalities use the update condition $Y_i{Z}_i^T{\gamma }^{(m)}\le 0$ and the assumed unit margin $Y_i{Z}_i^T\hat{\gamma }\ge 1$. A squared distance cannot become negative, so there can be at most $\Vert {\gamma }^{(0)}-\hat{\gamma }{\Vert }_2^2$ updates. The algorithm then returns a vector that correctly separates every training point. The estimate $\hat{\gamma }$ is the comparison vector for the proof; without an additional uniqueness condition the returned separator need not equal that particular vector.