The perceptron algorithm, introduced in the late fifties in the machine learning community, is a simple greedy algorithm for solving the polyhedral feasibility problem Ay>0. The algorithm's main advantages are its simplicity and noise tolerance. The algorithm's main disadvantage is its slow convergence rate. We propose a modified version of the perceptron algorithm that retains the algorithm's

original simplicity but has a substantially improved convergence rate. This is joint work with doctoral student Negar Soheili at Carnegie Mellon.