  We present a brief survey of existing mistake bounds and introduce novel
bounds for the Perceptron or the kernel Perceptron algorithm. Our novel bounds
generalize beyond standard margin-loss type bounds, allow for any convex and
Lipschitz loss function, and admit a very simple proof.

Machine Learning