Timezone: »
Poster
A Polylog Pivot Steps Simplex Algorithm for Classification
Elad Hazan · Zohar S Karnin
Tue Dec 04 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
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
-
2014 Poster: The Blinded Bandit: Learning with Adaptive Feedback »
Ofer Dekel · Elad Hazan · Tomer Koren -
2014 Poster: Bandit Convex Optimization: Towards Tight Bounds »
Elad Hazan · Kfir Y. Levy -
2011 Poster: Approximating Semidefinite Programs in Sublinear Time »
Dan Garber · Elad Hazan -
2011 Poster: Beating SGD: Learning SVMs in Sublinear Time »
Elad Hazan · Tomer Koren · Nati Srebro -
2011 Poster: Newtron: an Efficient Bandit algorithm for Online Multiclass Prediction »
Elad Hazan · Satyen Kale