Header logo is

Scalable Semidefinite Programming using Convex Perturbations


Technical Report


Several important machine learning problems can be modeled and solved via semidefinite programs. Often, researchers invoke off-the-shelf software for the associated optimization, which can be inappropriate for many applications due to computational and storage requirements. In this paper, we introduce the use of convex perturbations for semidefinite programs (SDPs). Using a particular perturbation function, we arrive at an algorithm for SDPs that has several advantages over existing techniques: a) it is simple, requiring only a few lines of MATLAB, b) it is a first-order method which makes it scalable, c) it can easily exploit the structure of a particular SDP to gain efficiency (e.g., when the constraint matrices are low-rank). We demonstrate on several machine learning applications that the proposed algorithm is effective in finding fast approximations to large-scale SDPs.

Author(s): Kulis, B. and Sra, S. and Jegelka, S.
Number (issue): TR-07-47
Year: 2007
Month: September
Day: 0

Department(s): Empirical Inference
Bibtex Type: Technical Report (techreport)

Institution: University of Texas, Austin, TX, USA

Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Scalable Semidefinite Programming using Convex Perturbations},
  author = {Kulis, B. and Sra, S. and Jegelka, S.},
  number = {TR-07-47},
  organization = {Max-Planck-Gesellschaft},
  institution = {University of Texas, Austin, TX, USA},
  school = {Biologische Kybernetik},
  month = sep,
  year = {2007},
  month_numeric = {9}