Perceptron-like Performance for Intersections of Halfspaces
Abstract
Given a set of examples on the unit ball in R^n which are labelled by a halfspace h which has margin ρ (minimum Euclidean distance from any point to the separating hyperplane), the well known Perceptron algorithm finds a separating hyperplane. The Perceptron Convergence Theorem (see e.g. [2]) states that at most 4/ ρ ^2 iterations of the Perceptron update rule are required, and thus the algorithm runs in time $O(\frac{n}{\rho^{2}})$ .
Cite
Text
Klivans and Servedio. "Perceptron-like Performance for Intersections of Halfspaces." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_44Markdown
[Klivans and Servedio. "Perceptron-like Performance for Intersections of Halfspaces." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/klivans2004colt-perceptron/) doi:10.1007/978-3-540-27819-1_44BibTeX
@inproceedings{klivans2004colt-perceptron,
title = {{Perceptron-like Performance for Intersections of Halfspaces}},
author = {Klivans, Adam R. and Servedio, Rocco A.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {639-640},
doi = {10.1007/978-3-540-27819-1_44},
url = {https://mlanthology.org/colt/2004/klivans2004colt-perceptron/}
}