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/2013
Entry Accepted: 06/21/2013
Entry Last Modified: 06/25/2013

Modify/Update this entry