- | ||||
|
![]()
|
A Deterministic Rescaled Perceptron Algorithm
Javier Pena (jfp 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/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 | |
![]() |