Novikoff 's Proof for Perceptron Convergence In Machine Learning, the Perceptron algorithm converges on linearly separable data in a finite number of steps. One can prove that $(R/\gamma)^2$ is an upper bound for how many errors the algorithm will make. This is given for the sphere with radius $R=\text{max}_{i=1}^{n}||\vec{x}_i||$ and data $\mathcal{X}=\{(\vec{x}_i,y_i):1\le i\le n\}$ with separation margin $\gamma>0$ (assumed it is linearly separable).
I'm looking at Novikoff's proof from 1962. Let $\phi$ be the angle between $\vec{w}_t$ (weight vector after $t$ update steps) and $\vec{w}_*$ (the optimal weight vector). $||\vec{w}_*||$ is normalized to $1$.
The maximum number of steps is then bounded by:
$$\text{max}(\text{cos}^2\phi)=1\ge \left( \dfrac{\langle\vec{w}_t , \vec{w}_*\rangle}{||\vec{w}_t||\underbrace{||\vec{w}_*||}_{=1}} \right)^2$$
He then expands the numerator as
$$\langle\vec{w}_t , \vec{w}_*\rangle^2 = \langle\vec{w}_{t-1}+y\vec{x} , \vec{w}_*\rangle^2\stackrel{(1)}{\ge} (\langle\vec{w}_{t-1} , \vec{w}_*\rangle+\gamma)^2\stackrel{(2)}{\ge}t^2\gamma^2.$$
The first equality is true because is just take out the penultimate error. Why (1) is true is the first thing that puzzles me a bit. Is it because $\langle\vec{w}_*,y\vec{x}\rangle\ge\gamma$, i.e. the minimal margine $\gamma$ must always be greater than the inner product of any sample? And in (2) im completely lost, why this must be. In my skript, it just says "induction over $t,\vec{w}_0=0$".
As for the denominator, I have
$$||\vec{w}_t||=||\vec{w}_{t-1}+y\vec{x}||^2\stackrel{(3)}{\le}||\vec{w}_{t-1}||^2+R^2\stackrel{(2)}{\le}tR^2$$
which contains again the induction at (2) and also a new relation at (3), which is unclear to me.
In the end we obtain $$1\ge\dfrac{t^2\gamma^2}{tR^2}=t\left(\dfrac{\gamma}{R}\right)^2\Leftrightarrow t\le \left(\dfrac{R}{\gamma}\right)^2$$
what we wanted to prove.
tl;dr: Explain steps (1), (2), and (3).
 A: In Novikoff's theorem, we assume that
i) The data is linearly separable:
$$\forall(\vec{x}, y) \in \mathcal{X} \text{ } \exists \vec{w}_* \exists \gamma > 0:
\langle\vec{w}_*, \vec{x}\rangle y \ge \gamma .$$
ii) The weights are updated following Hebb's rule:
$$\text{if } \langle\vec{w}_{t-1},\vec{x}\rangle y < 0, \text{ then }
\vec{w}_t \leftarrow \vec{w}_{t-1} + y\vec{x} .$$
Thus,


*

*$$\langle\vec{w}_t , \vec{w}_*\rangle^2 =
\langle\vec{w}_{t-1}+y\vec{x} , \vec{w}_*\rangle^2 =
(\langle\vec{w}_{t-1}, \vec{w}_*\rangle + \langle\vec{w}_*, y\vec{x}\rangle)^2 =
(\langle\vec{w}_{t-1}, \vec{w}_*\rangle + \langle\vec{w}_*, \vec{x}\rangle y)^2 \ge
(\langle\vec{w}_{t-1} , \vec{w}_*\rangle+\gamma)^2 .$$

*$$(\langle\vec{w}_{t-1}, \vec{w}_*\rangle + \langle\vec{w}_*, \vec{x}\rangle y)^2 =
(\langle\vec{w}_{t-2}, \vec{w}_*\rangle + 2\langle\vec{w}_*, \vec{x}\rangle y)^2 =
\ldots =$$
$$= (\langle\vec{w}_{0}, \vec{w}_*\rangle + t\langle\vec{w}_*, \vec{x}\rangle y)^2 =
(\langle0, \vec{w}_*\rangle + t\langle\vec{w}_*, \vec{x}\rangle y)^2 \ge
t^2\gamma^2.$$


*$$||\vec{w}_t||^2 =
||\vec{w}_{t-1} + y\vec{x}||^2 =
||\vec{w}_{t-1}||^2 + 2\langle\vec{w}_{t-1}, \vec{x}\rangle y + ||\vec{x}||^2 \le$$
$$\le ||\vec{w}_{t-1}||^2 + ||\vec{x}||^2 \le
||\vec{w}_{t-1}||^2 + R^2 \le
\ldots \le
||\vec{w}_0||^2 + t^2R^2 =
t^2R^2.$$
A: Consider data ${ (x _1, y _1), \ldots, (x _T, y _T) }$ with feature vectors ${ x _t \in \mathbb{R} ^d }$ and labels ${ y _t \in \lbrace +1, -1 \rbrace }.$
To avoid ambiguity, the (basic) perceptron algorithm is

*

*Initialise ${ \mathbf{\theta} = 0 }$ (where ${ 0 }$ is the zero vector in ${ \mathbb{R} ^d }$)

*For ${ t }$ from ${ 1 }$ to ${ T }$:
If ${  y _t ( \theta \cdot x _t) \leq 0 }$ update ${ \theta \leftarrow \theta + y _t x _t }$ else leave ${ \theta }$ unchanged

*Repeat step ${ 2 }$ until convergence

*Output ${ \theta }.$
If the algo converges, output ${ \theta }$ must be such that each ${ y _t (\theta \cdot x _t) \gt 0 },$ giving a linear separation of data.
Convergence is guaranteed if the data is linearly separable:
Theorem: Say there is a unit vector ${ \theta ^{\ast} }$ such that each ${ y _t (\theta^{\ast} \cdot x _t) \gt 0 }.$
Then above algorithm converges. More specifically, ${ \theta }$ can get updated in the algorithm atmost ${ ( \frac{R}{\gamma}) ^2 }$ many times, where ${ R = \max \lVert x _t \rVert }$ and margin ${ \gamma = \min y _t (\theta ^{\ast} \cdot x _t) \gt 0 }.$
Proof: Let ${ \theta ^{(k)} }$ denote the value of ${ \theta }$ just after ${ k ^{\text{th}} }$ update. So for eg ${ \theta ^{(1)} = y _1 x _1 }.$
Any update ${ \theta \leftarrow \theta + y _t x _t }$ increases the projection ${ \theta \cdot \theta ^{\ast} }$ by atleast ${ \gamma }$ [since ${ (\theta + y _t x _t) \cdot \theta^{\ast} - \theta \cdot \theta^{\ast} }$ ${ = y _t (\theta^{\ast} \cdot x _t) \geq \gamma  }$]. So after ${ k }$ updates, ${ \theta ^{(k)} \cdot \theta^{\ast} \geq k \gamma. }$ Especially, ${ \lVert \theta^{(k)} \rVert \geq k \gamma }.$
Any update ${ \theta \leftarrow \theta + y _t x _t }$ changes ${ \lVert \theta \rVert ^2 }$ as ${ \lVert \theta _{\text{new}} \rVert ^2 - \lVert \theta \rVert ^2 \leq R ^2 }$ [since ${ \lVert \theta + y _t x _t \rVert ^2  - \lVert \theta \rVert ^2 }$ ${ = \underbrace{2 y _t (\theta \cdot x _t)} _{\leq 0} + \underbrace{\lVert y _t x _t \rVert ^2} _{\leq R ^2} }$]. So after ${ k }$ updates, ${ \lVert \theta ^{(k)} \rVert ^2 \leq k R ^2 }$ that is ${ \lVert \theta ^{(k)} \rVert \leq \sqrt{k} R }.$
Hence ${ k \gamma \leq \lVert \theta ^{(k)} \rVert \leq \sqrt{k} R }$ giving ${ k \leq (\frac{R}{\gamma})^2 .}$ So atmost ${ (\frac{R}{\gamma})^2 }$ many updates of ${ \theta }$ can happen in the algorithm.
