Perceptron-Like Performance for Intersections of Halfspaces
Lists
Only you see this
Abstract
Given a set of examples on the unit ball in Rn 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}})$ .
BibTeX
@inproceedings{klivans2004perceptron,
author = {Adam R. Klivans and Rocco A. Servedio},
title = {{Perceptron-Like Performance for Intersections of Halfspaces}},
booktitle = {Conference on Learning Theory},
year = {2004},
doi = {10.1007/978-3-540-27819-1\_44},
}Loading related content...