목표 vector $w^\star$, 현재 vector $w$ 라고 하자.
Data set {($(\mathbf{x_1}, y_1)$, ... , $(\mathbf{x_d}, y_d)$} 가 주어졌다고 하자.
WLOG, $||w^\star|| = 1$, $||\mathbf{x}|| \leq 1$ 이라고 하자.
( 모든 data에 $\mathbf{x_i} \leftarrow \mathbf{x_i} / max(\mathbf{x})$ 해도 같은 hyperplane 얻는다 )
WLOG, $w = 0$ 으로 시작한다고 하자.
$w^\star$의 정의에 따라 모든 $(\mathbf{x}, y)$에 대해 $y x^T w^\star > 0$이 성립한다.
Lemma : $y x^T w^\star \geq \gamma$
$\displaystyle \gamma = \min_{x}{|x^T w^\star|}$ 라고 하자.
즉, $\gamma$는 목표 hyperplane으로부터의 minimal margin이다.
이 때, $y x^T w^\star = |x^T w^\star| \geq \gamma$ 가 성립한다. $\square$
어떤 $(x, y)$에 대해 $y x^T w\leq 0$이 성립하여 update가 이루어졌다고 하자.
1. $w_{new}^T w^\star = (w+yx)^T w^\star = w^Tw^\star + yx^Tw^\star \geq w^Tw^\star + \gamma$
2. $w_{new}^T w_{new} = (w+yx)^T (w+yx) = w^T w + 2yx^Tw + y^2x^Tx \leq w^Tw + 1$
이제 M번의 update가 이루어졌다고 해보자.
$M \gamma \leq w^T w^\star \leq ||w^T|| = \sqrt{w^T w} \leq \sqrt{M}$
$\therefore M \leq \frac{1}{\gamma^2}$
Update는 많아야 $\lfloor \frac{1}{\gamma^2} \rfloor$ 번 이루어진다.