# Why does the weight vector in a perceptron monotonically tend to the generously feasible region

In a course on Machine Learning, in the chapter about a Perceptron, there is this statement:

If a generously feasible region exists, then the distance between the current weight vector and a weight vector in the generously feasible region will monotonically decrease as the learning proceeds.

Why is this the case?

## 1 Answer

To summarise, it basically comes down to the fact that all the vectors have a component in the direction of the input vector $x$, so when we update the current weight vector by adding $x$ to it, the new weight vector has either a smaller negative component or a positive component in the $x$ direction. Note that by definition a generously feasible vector is one with a large $x$ component, so by making our current vector's $x$ component more positive we get closer to the generously feasible one. This is the rough idea, and is hopefully made more clear by the following calculations which shows exactly what I mean by all this component stuff.

For simplicity let's assume that we have just the one constraint i.e. let's say there is a vector $x$ and so the feasible region is the set of vectors $w$ such that $\langle x, w \rangle > 0$. Note that from linear algebra we know $w = \alpha x + \beta y$ where $\alpha, \beta \in \mathbb{R}$ and $y$ is an orthogonal vector to $x$. Since we're assuming $w$ is feasible, we have $0 < \langle w, x \rangle = \langle \alpha x + \beta y, x \rangle = \alpha \langle x,x \rangle + \beta \langle y, x \rangle = \alpha \langle x, x\rangle$. And since $\langle x,x \rangle > 0$, we must also have $\alpha > 0$. So now we know that $w$ is a feasible solution if and only if when expressed in the above form we have $\alpha > 0$.

Now say we're starting with an infeasible vector $v = \gamma x + \delta y$ so $\gamma < 0$. Then when taking a learning step we update $v$ to $v' := v + x = (\gamma + 1) x + \delta y$, so $v'$ is either less negative than $v$, or $v'$ is actually positive.

Now let's say that $w$ is a generously feasible i.e. $\langle w, x \rangle > \langle x, x\rangle$. Then $\alpha$ must be at least 1. The distance from $v$ to $w$ is $\| w- v\| = \| (\alpha - \gamma)x + (\beta - \delta)y \| = \sqrt{(\alpha - \gamma)^2 + (\beta - \delta)^2}$ whereas $\|w - v'\| = \sqrt{\langle (\alpha - \gamma - 1)^2 + (\beta - \delta)^2}$. Note that which vector $w$ is closer to basically comes down to whether $|\alpha - \gamma| > | \alpha - \gamma - 1 |$ or not. But since $w$ is generously feasible and $v$ is infeasible by assumption, $\alpha > 1,$ and $\gamma < 0$ so $\alpha - \gamma - 1 > \alpha -1 > 0$ so indeed we have $| \alpha - \gamma | > | \alpha - \gamma - 1|$ so the updated vector $v'$ is closer.