On Accelerated Perceptrons and Beyond

The classical Perceptron algorithm of Rosenblatt can be used to find a linear threshold function to correctly classify n linearly separable data points, assuming the classes are separated by some margin γ > 0. A foundational result is that Perceptron converges after Omega(1/γ2) iterations. There have been several recent works that managed to improve this rate by a quadratic factor, to Omega(√log n/γ), with more sophisticated algorithms. In this paper, we unify these existing results under one framework by showing that they can all be described through the lens of solving min-max problems using modern acceleration techniques, mainly through optimistic online learning. We then show that the proposed framework also lead to improved results for a series of problems beyond the standard Perceptron setting. Specifically, a) For the margin maximization problem, we improve the state-of-the-art result from O(log t/t2) to O(1/t2), where t is the number of iterations; b) We provide the first result on identifying the implicit bias property of the classical Nesterov's accelerated gradient descent (NAG) algorithm, and show NAG can maximize the margin with an O(1/t2) rate; c) For the classical p-norm Perceptron problem, we provide an algorithm with Omega(√(p-1)log n/γ) convergence rate, while existing algorithms suffer the Omega((p-1)/γ2) convergence rate.