Approximating semidefinite programs in sublinear time

Dan Garber, Elad Hazan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 24
Subtitle of host publication25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
StatePublished - Dec 1 2011
Externally publishedYes
Event25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 - Granada, Spain
Duration: Dec 12 2011Dec 14 2011

Publication series

NameAdvances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011

Other

Other25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011
CountrySpain
CityGranada
Period12/12/1112/14/11

All Science Journal Classification (ASJC) codes

  • Information Systems

Fingerprint Dive into the research topics of 'Approximating semidefinite programs in sublinear time'. Together they form a unique fingerprint.

  • Cite this

    Garber, D., & Hazan, E. (2011). Approximating semidefinite programs in sublinear time. In Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011 (Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011, NIPS 2011).