Perceptron Mistake Bounds

Abstract

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.

Cited by in corpus (2)

• Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
• Quantum Perceptron Revisited: Computational-Statistical Tradeoffs