Perceptron Mistake Bounds

Preprint English OPEN
Mohri, Mehryar; Rostamizadeh, Afshin;
(2013)
  • Subject: Computer Science - Learning

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... View more
  • References (7)

    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.

  • Metrics
Share - Bookmark