publication . Preprint . 2013

Perceptron Mistake Bounds

Mohri, Mehryar; Rostamizadeh, Afshin;
Open Access English
  • Published: 01 May 2013
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.
free text keywords: Computer Science - Learning
Related Organizations
Download from

Mark A. Aizerman, E. M. Braverman, and Lev I. Rozono`er. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837, 1964.

Nicolo` Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.

Nicolo` Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050-2057, 2004.

Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37:277-296, 1999.

Nick Littlestone. From on-line to batch learning. In COLT, pages 269- 284, 1989.

Albert B.J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pages 615-622, 1962.

Frank Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386, 1958. [OpenAIRE]

Any information missing or wrong?Report an Issue