Technical Report MSC-2012-17

Title: Approximating Semidefinite Programs in Sublinear Time
Authors: Dan Garber
Supervisors: Elad Hazan
Abstract: 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion