Convex Perturbations for Scalable Semidefinite Programming

Brian Kulis, Suvrit Sra, Inderjit S. DhillonAISTATS 2009 · OpenReview

Abstract

Many important machine learning problems are modeled and solved via semidefinite programs (SDPs), including metric learning, nonlinear embedding, and clustering. However, standard interior-point solvers are often too slow or memory-intensive for large-scale applications. This paper introduces a scalable first-order algorithm for solving SDPs by adding a strictly convex log-det perturbation to the objective function. This approach allows for a trade-off between extreme numerical precision and significant gains in speed and memory efficiency, enabling the solution of large-scale machine learning problems that were previously computationally prohibitive.

Introduction

Semidefinite Programming (SDP) is a versatile optimization framework used in machine learning for tasks such as metric learning, dimensionality reduction (e.g., Maximum Variance Unfolding), and graph clustering. Despite their power, standard "off-the-shelf" solvers like SeDuMi or DSDP typically rely on interior-point methods, which present two major drawbacks for ML:

  1. Computational Complexity: Complexity scales at $O(n^4)$ or $O(n^6)$, making them unsuitable for large datasets.
  2. Memory Overhead: Storing large Hessian matrices quickly exhausts RAM as the number of variables increases.

In most ML applications, high-precision solutions are unnecessary. Instead, there is a need for fast, scalable algorithms that can exploit the specific structure—such as low-rank constraints—common in ML problems.

Methodology

The core innovation is the introduction of a convex perturbation. Instead of solving the standard linear objective $\min \text{Tr}(CX)$, the authors solve: $$\min \text{Tr}(CX) - \epsilon \log \det(X)$$ where $\epsilon$ is a small positive constant.

Technical Components

  • Bregman Projections: The authors derive a first-order algorithm based on Bregman's method, a "row-action" technique that enforces constraints iteratively.
  • Low-Rank Exploitation: Many ML constraints are rank-1 or rank-2. For such constraints, the Bregman projection becomes a simple rank-update to the matrix, computable in $O(n^2)$ time.
  • Kernelization: For the Large Margin Nearest Neighbor (LMNN) problem, the update rule can be formulated using inner products, allowing metric learning in high-dimensional feature spaces without losing convexity.

Experimental Evaluation

The method, SDPLogDet, was evaluated on several benchmarks including UCI datasets, the Caltech-101 vision dataset, and synthetic data for scalability testing.

Figure 3: Convergence of SDPLogDet vs. SeDuMi across different datasets.

Key Results

  • Scalability: In Maximum Variance Unfolding tests, standard solvers failed due to memory limits at $n=1500$. SDPLogDet scaled to $n=3500$ and beyond with minimal overhead.
  • Speed: On metric learning tasks, SDPLogDet was consistently faster than specialized subgradient implementations, often by an order of magnitude.
  • Performance: On the Caltech-101 vision task, the kernelized LMNN (K-LMNN) outperformed Information-Theoretic Metric Learning (ITML) and the Euclidean baseline, particularly with small training sets.
Figure 5: Accuracy on Caltech-101 task comparing K-LMNN, ITML, and Baseline.

Discussion and Insights

The paper proves that for a sufficiently small $\epsilon$, the solution to the perturbed problem is the maximum determinant solution of the original SDP. This provides a theoretical bridge between the approximation and the exact problem. Furthermore, the results highlight that memory, rather than CPU time, is often the true bottleneck for SDPs in machine learning.

While SDPLogDet exhibits linear convergence—making it slower than second-order methods for extreme precision—it provides "good enough" optimization for ML tasks at a fraction of the computational cost. Future work may involve more sophisticated constraint selection strategies to further improve convergence speed.

Summary updated

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-she...
BibTeX
@inproceedings{kulis2009convex,
  author = {Brian Kulis and Suvrit Sra and Inderjit S. Dhillon},
  title = {{Convex Perturbations for Scalable Semidefinite Programming}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2009},
  url = {https://openreview.net/forum?id=mnjl8oH6sz},
}
Figure