# An efficient re-scaled perceptron algorithm for conic systems

Published

Journal Article

The classical perceptron algorithm is an elementary algorithm for solving a homogeneous linear inequality system Ax > 0, with many important applications in learning theory (e.g., [11,8]). A natural condition measure associated with this algorithm is the Euclidean width T of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/τ2. Dunagan and Vempala [5] have developed a re-scaled version of the perceptron algorithm with an improved complexity of O(n ln(1/τ)) iterations (with high probability), which is theoretically efficient in τ, and in particular is polynomial-time in the bit-length model. We explore extensions of the concepts of these perceptron methods to the general homogeneous conic system Ax∈ int K where if is a regular convex cone. We provide a conic extension of the re-scaled perceptron algorithm based on the notion of a deep-separation oracle of a cone, which essentially computes a certificate of strong separation. We give a general condition under which the re-scaled perceptron algorithm is theoretically efficient, i.e., polynomial-time; this includes the cases when K is the cross-product of half-spaces, second-order cones, and the positive semi-definite cone. © Springer-Verlag Berlin Heidelberg 2007.

### Duke Authors

### Cited Authors

- Belloni, A; Freund, RM; Vempala, SS

### Published Date

- December 1, 2007

### Published In

### Volume / Issue

- 4539 LNAI /

### Start / End Page

- 393 - 408

### Electronic International Standard Serial Number (EISSN)

- 1611-3349

### International Standard Serial Number (ISSN)

- 0302-9743

### Citation Source

- Scopus