[edit]
A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:3285-3295, 2020.
Abstract
We show a simple perceptron-like algorithm to learn origin-centered halfspaces in Rn with accuracy 1−ϵ and confidence 1−δ in time O(n2ϵ(log1ϵ+log1δ)) using O(nϵ(log1ϵ+log1δ)) 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.