This is how I understand the perceptron algorithm.
The perceptron loss function is the hinge loss $\ell(w,x,y) = \max(0, -yw\cdot x)$. Suppose the data set is $D = \{(x_1,y_1),\dots,(x_n,y_n)\}$ with $y_i \in \{-1,1\}$. The perceptron criterion is $$ E(w) = \sum_i \ell(w, x_i, y_i) = \sum_i \max(0, -y_iw\cdot x). $$ The perceptron algorithm tries to minimize $E(w)$ using gradient descent. The gradient of $E(w)$ with respect to $w$ is $$ \nabla E(w) = \sum_i \left\{ \begin{array}{ll} \mathbf{0} & \text{ if } \ell(w,x_i,y_i) = 0\\ -y_ix_i & \text{ otherwise } \end{array}\right.. $$ So the perceptron updates the $w$ according to $$ w^{(t+1)} = w^{(t)} - \eta \nabla E(w^{(t)}) = w^{(t)} + \eta \sum_{i\in M(t)} y_ix_i $$ where $M(t)$ is the set of points misclassified by $w^{(t)}$. Since we can define another equivalent sequence of weight vectors $v^{(t)} = (1/\eta)w^{(t)}$, we can just take $\eta = 1$.
I know that $w^{(t)}$ will converge to a seperating hyperplane if one exists and $E(w)$ will converge to $0$.
My question is about when the data set is not linearly separable. In that case, does $E(w)$ converge to some minimum?
If $E(w)$ attains some minimum, its gradient there has to be $\mathbf{0}$. One possibility is that all the terms in the sum of $\nabla E$ are 0, which means that the dataset is linearly seperable and this is contradiction. The other possibility is that the sum of $-y_ix_i$ over the misclassified points is somehow $\mathbf{0}$.
