English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Convex Perturbations for Scalable Semidefinite Programming

Kulis, B., Sra, S., & Dhillon, I. (2009). Convex Perturbations for Scalable Semidefinite Programming. In D. van Dyk, & M. Welling (Eds.), Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009) (pp. 296-303). Cambridge, MA, USA: MIT Press.

Item is

Files

show Files

Locators

show
hide
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Kulis, B, Author
Sra, S1, 2, Author           
Dhillon, I, Author
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s):
 Dates: 2009-04
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 5650
 Degree: -

Event

show
hide
Title: Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Place of Event: Clearwater Beach, FL, USA
Start-/End Date: 2009-04-16 - 2009-04-18

Legal Case

show

Project information

show

Source 1

show
hide
Title: Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Source Genre: Proceedings
 Creator(s):
van Dyk, D, Editor
Welling, M, Editor
Affiliations:
-
Publ. Info: Cambridge, MA, USA : MIT Press
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 296 - 303 Identifier: -

Source 2

show
hide
Title: JMLR Workshop and Conference Proceedings
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 5 Sequence Number: - Start / End Page: - Identifier: -