Header logo is

Convex Perturbations for Scalable Semidefinite Programming

2009

Conference Paper

ei


Many important machine learning problems are modeled and solved via semidefinite programs; examples include metric learning, nonlinear embedding, and certain clustering problems. Often, off-the-shelf software is invoked for the associated optimization, which can be inappropriate due to excessive computational and storage requirements. In this paper, we introduce the use of convex perturbations for solving semidefinite programs (SDPs), and for a specific perturbation we derive an algorithm 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, and thereby scalable, and c) it can easily exploit the structure of a given SDP (e.g., when the constraint matrices are low-rank, a situation common to several machine learning SDPs). A pleasant byproduct of our method is a fast, kernelized version of the large-margin nearest neighbor metric learning algorithm. We demonstrate that our algorithm is effective in finding fast approximations to large-scale SDPs arising in some machine learning applications.

Author(s): Kulis, B. and Sra, S. and Dhillon, I.
Book Title: JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009
Journal: Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Pages: 296-303
Year: 2009
Month: April
Day: 0
Editors: van Dyk, D. , M. Welling
Publisher: MIT Press

Department(s): Empirical Inference
Research Project(s): Optimization and Large Scale Learning
Bibtex Type: Conference Paper (inproceedings)

Address: Cambridge, MA, USA
Digital: 0
Event Name: Twelfth International Conference on Artificial Intelligence and Statistics
Event Place: Clearwater Beach, FL, USA
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{5650,
  title = {Convex Perturbations for Scalable Semidefinite Programming},
  author = {Kulis, B. and Sra, S. and Dhillon, I.},
  journal = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)},
  booktitle = {JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009},
  pages = {296-303},
  editors = {van Dyk, D. , M. Welling},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = apr,
  year = {2009},
  month_numeric = {4}
}