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

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,

1. $$\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 .$$

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

1. $$||\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.$$

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.