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 (Weinberger
et al., 2005). We demonstrate that our
algorithm is effective in finding fast approximations
to large-scale SDPs arising in some machine
learning applications.
Download: pdf
Citation
- Convex Perturbations for Scalable Semidefinite Programming (pdf, software)
B. Kulis, S. Sra, I. Dhillon.
In International Conference on Artificial Intelligence and Statistics (AISTATS), April 2009.
Bibtex: