TY - GEN
T1 - A provably efficient simplex algorithm for classification
AU - Hazan, Elad
AU - Karnin, Zohar
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84877768622&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84877768622&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84877768622
SN - 9781627480031
T3 - Advances in Neural Information Processing Systems
SP - 629
EP - 637
BT - Advances in Neural Information Processing Systems 25
T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Y2 - 3 December 2012 through 6 December 2012
ER -