A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere

摘要

We show a simple perceptron-like algorithm to learn origin-centered halfspaces in $mathbb{R}^n$ with accuracy $1-epsilon$ and confidence $1-delta$ in time $mathcal{O}left(rac{n^2}{epsilon}left(log rac{1}{epsilon}+log rac{1}{delta}ight)ight)$ using $mathcal{O}left(rac{n}{epsilon}left(log rac{1}{epsilon}+log rac{1}{delta}ight)ight)$ labeled examples drawn uniformly from the unit $n$-sphere. This improves upon algorithms given in Baum(1990), Long(1994) and Servedio(1999). The time and sample complexity of our algorithm match the lower bounds given in Long(1995) up to logarithmic factors.