Perceptron Mistake Bounds

2013/05/01 by Mehryar Mohri, Mohri, Mehryar, Afshin Rostamizadeh +1 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Neural Networks and Applications #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1305.0208

openalex publication_date 2013/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The perceptron: A probabilistic model for information storage and organization in the brain.

Cited by

• Efficient Online Bandit Multiclass Learning with O(√(T)) Regret

Related

• The Role of Weight Shrinking in Large Margin Perceptron Learning
• Ahpatron: A New Budgeted Online Kernel Learning Machine with Tighter Mistake Bound
• The Perceptron with Dynamic Margin
• The Margitron: A Generalised Perceptron with Margin
• Contextual bandits with surrogate losses: Margin bounds and efficient algorithms