Sublinear time algorithms for approximate semidefinite programming

Dan Garber, Elad Hazan

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

We consider semidefinite optimization in a saddle point formulation where the primal solution is in the spectrahedron and the dual solution is a distribution over affine functions. We present an approximation algorithm for this problem that runs in sublinear time in the size of the data. To the best of our knowledge, this is the first algorithm to achieve this. Our algorithm is also guaranteed to produce low-rank solutions. We further prove lower bounds on the running time of any algorithm for this problem, showing that certain terms in the running time of our algorithm cannot be further improved. Finally, we consider a non-affine version of the saddle point problem and give an algorithm that under certain assumptions runs in sublinear time.

Original languageEnglish (US)
Pages (from-to)329-361
Number of pages33
JournalMathematical Programming
Volume158
Issue number1-2
DOIs
StatePublished - Jul 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Large scale optimization
  • Online algorithms
  • Semidefinite programming
  • Sublinear algorithms

Fingerprint Dive into the research topics of 'Sublinear time algorithms for approximate semidefinite programming'. Together they form a unique fingerprint.

  • Cite this