A Polylog Pivot Steps Simplex Algorithm for Classification
Elad Hazan · Zohar S Karnin
2012 Poster
Abstract
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.
Chat is not available.
Successful Page Load