A Polylog Pivot Steps Simplex Algorithm for Classification
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.
Cite
Text
Hazan and Karnin. "A Polylog Pivot Steps Simplex Algorithm for Classification." Neural Information Processing Systems, 2012.Markdown
[Hazan and Karnin. "A Polylog Pivot Steps Simplex Algorithm for Classification." Neural Information Processing Systems, 2012.](https://mlanthology.org/neurips/2012/hazan2012neurips-polylog/)BibTeX
@inproceedings{hazan2012neurips-polylog,
title = {{A Polylog Pivot Steps Simplex Algorithm for Classification}},
author = {Hazan, Elad and Karnin, Zohar},
booktitle = {Neural Information Processing Systems},
year = {2012},
pages = {629-637},
url = {https://mlanthology.org/neurips/2012/hazan2012neurips-polylog/}
}