M.Sc Student | Garber Dan |
---|---|

Subject | Approximating Semidefinite Programs in Sublinear Time |

Department | Department of Computer Science |

Supervisor | Professor Elad Hazan |

Full Thesis text |

Semidefinite programming is a convex optimization problem which is wildly used in numerous fields of science and engineering. In combinatorial optimization and machine learning in particular, many algorithms that are based on solving semidefinite programs have been developed in recent years. Although polynomial time algorithms which can solve general semidefinite programs accurately and even faster algorithms that solve such programs only approximately exist, their running may be prohibitive in practice when applied to very large scale problems such as those that are ubiquitous nowadays in machine learning. Thus there is a constant need for faster algorithms for solving these programs.

In this thesis we present an algorithm for solving approximately general semidefinite programs which enjoys a running time that is sublinear in the number of entries in the semidefinite instance and thus computes an approximated solution after reading only a small portion of the input. The algorithm also has the benefit of producing low rank solutions which is computationally favorable. Our algorithm is based on solving a Lagrange relaxation of the semidefinite program using the well known Multiplicative Updates Method and applying recent algorithmic machinery from online learning and random sampling. We also present lower bounds on the running time of any approximation algorithm for semidefinite programming which demonstrate that our algorithm is close to optimal in certain cases.