The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone $F$. At each iteration, the algorithm only involves a query of a separation oracle for $F$ and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a feasible point in $F$ after $\Oh(1/\tau_F^2)$ iterations, where $\tau_F$ is the width of the cone $F$. We propose a version of the perceptron algorithm that includes a periodic rescaling of the ambient space. In contrast to the classical version, our rescaled version finds a point in $F$ in $\Oh(m^5 \log(1/\tau_F))$ perceptron updates. This result is inspired by and strengthens the previous work on randomized rescaling of the perceptron algorithm by Dunagan and Vempala [{\em Math. Program.} 114 (2006), 101–114] and by Belloni, Freund, and Vempala [{\em Math. Oper. Res.} 34 (2009), 621–641]. In particular, our algorithm and its complexity analysis are simpler and shorter. Furthermore, our algorithm does not require randomization nor deep separation oracles.
Citation
Technical Report, Tepper School of Business, Carnegie Mellon University