NIPS Proceedingsβ

A Polylog Pivot Steps Simplex Algorithm for Classification

Part of: Advances in Neural Information Processing Systems 25 (NIPS 2012)

[PDF] [BibTeX]



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.