Poster
A Polylog Pivot Steps Simplex Algorithm for Classification
Elad Hazan · Zohar S Karnin

Tue Dec 4th 07:00 PM -- 12:00 AM @ Harrah’s Special Events Center 2nd Floor #None

We present a simplex algorithm for linear programming in a linear classification formulation. The paramount complexity parameter in linear classification problems is called the margin. We prove that for margin values of practical interest our simplex variant performs a polylogarithmic number of pivot steps in the worst case, and its overall running time is near linear. This is in contrast to general linear programming, for which no sub-polynomial pivot rule is known.

Author Information

Elad Hazan (Technion)
Zohar S Karnin (Yahoo! Research)

More from the Same Authors