# Perceptron Mistake Bounds

arXiv: https://arxiv.org/abs/1305.0208 · HTML: https://mlsanity.com/paper/1305.0208/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2013.

## Built on by (most cited first, 5 of 5)

- [Quantum Perceptron Revisited: Computational-Statistical Tradeoffs](https://mlsanity.com/paper/2106.02496/) (2021)
- [MIME: Minority Inclusion for Majority Group Enhancement of AI Performance](https://mlsanity.com/paper/2209.00746/) (2022)
- [Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks](https://mlsanity.com/paper/2504.10598/) (2025)
- [Margin-Independent Online Multiclass Learning via Convex Geometry](https://mlsanity.com/paper/2111.08057/) (2021)
- [Predictability of Machine Learning Algorithms and Related Feature Extraction Techniques](https://mlsanity.com/paper/2305.00449/) (2023)

## Abstract (arXiv)

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.