- A Deterministic Rescaled Perceptron Algorithm Javier Pena (jfpandrew.cmu.edu) Negar Soheili (nsoheiliandrew.cmu) Abstract: 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. Keywords: Perceptron algorithm, rescaling, polynomial time algorithm Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Technical Report, Tepper School of Business, Carnegie Mellon University Download: [PDF]Entry Submitted: 06/21/2013Entry Accepted: 06/21/2013Entry Last Modified: 06/25/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.