Optimization Online


A Deterministic Rescaled Perceptron Algorithm

Javier Pena (jfp***at***andrew.cmu.edu)
Negar Soheili (nsoheili***at***andrew.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society