Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents

ID: 461786.0, MPI für biologische Kybernetik / Biologische Kybernetik
Convex Perturbations for Scalable Semidefinite Programming
Authors:Kulis, B.; Sra, S.; Dhillon, I.
Editors:Dyk, D. van; Welling, M.
Date of Publication (YYYY-MM-DD):2009-04
Title of Proceedings:Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Start Page:296
End Page:303
Physical Description:8
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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 extsc{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~citep{lmnn}. We demonstrate that our
algorithm is effective in finding fast approximations to large-scale SDPs
arising in some machine learning applications.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.