  


A Deterministic Rescaled Perceptron Algorithm
Javier Pena (jfpandrew.cmu.edu) 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), 101114] and by Belloni, Freund, and Vempala [{\em Math. Oper. Res.} 34 (2009), 621641]. 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/2013 Modify/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  