Timezone: »
Poster
Approximating Semidefinite Programs in Sublinear Time
Dan Garber · Elad Hazan
In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric.
Author Information
Dan Garber (Technion)
Elad Hazan (Technion)
More from the Same Authors
-
2016 Poster: Efficient Globally Convergent Stochastic Optimization for Canonical Correlation Analysis »
Weiran Wang · Jialei Wang · Dan Garber · Dan Garber · Nati Srebro -
2016 Poster: Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes »
Dan Garber · Dan Garber · Ofer Meshi -
2016 Oral: Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes »
Dan Garber · Dan Garber · Ofer Meshi -
2016 Poster: Faster Projection-free Convex Optimization over the Spectrahedron »
Dan Garber · Dan Garber -
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 -
2012 Poster: A Polylog Pivot Steps Simplex Algorithm for Classification »
Elad Hazan · Zohar S Karnin -
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