Fast Low-Rank Semidefinite Programming for Embedding and Clustering

Brian Kulis, Arun C. Surendran, John C. PlattAISTATS 2007 · OpenReview

Abstract

Many non-convex problems in machine learning such as embedding and clustering have been solved using convex semidefinite relaxations. These semidefinite programs (SDPs) are expensive to solve and scale poorly with dataset size. This paper introduces a method to solve these problems directly as low-rank SDPs using non-convex optimization, achieving significant speedups and better scalability on large datasets without sacrificing solution quality.

Introduction

Core tasks in machine learning, such as $k$-means clustering and Maximum Variance Unfolding (MVU), are naturally non-convex and computationally challenging. The traditional approach involves Semidefinite Programming (SDP) relaxation, which transforms these hard problems into convex ones. However, standard SDP solvers typically scale at $O(n^3)$ or worse, making them impractical for datasets exceeding a few thousand points. Additionally, recovering a low-rank solution from the relaxed convex result often requires a post-hoc projection that can introduce errors and violate original constraints.

Methodology

This paper proposes a "low-rank first" strategy, reformulating machine learning tasks as low-rank SDPs. The key components of this approach include:

  1. Exact Reformulation: The authors prove that for $k$-means clustering, discrete "0-1" constraints can be replaced exactly by a rank constraint and a positive semi-definite constraint, ensuring the solver addresses the actual problem rather than an approximation.
  2. Burer-Monteiro Factorization: The large $n \times n$ matrix $Z$ is factored into $YY^T$, where $Y$ is a much smaller $n \times k$ matrix, significantly reducing the parameter space.
  3. Non-convex Optimization: The reformulated problem is solved using the Augmented Lagrangian method combined with L-BFGS, a memory-efficient optimization algorithm.
  4. Inequality Handling: A key contribution is extending the solver to handle linear inequality constraints (e.g., $Y \ge 0$), which are essential for clustering tasks but were not supported by previous low-rank solvers.

Experimental Results

The approach was evaluated on vector-based datasets for MVU (e.g., Iris, Pima, Pendigits) and graph-based datasets for clustering (e.g., add20, crack, whitaker3).

Performance comparison of traditional DSDP versus the proposed low-rank (LR) solver on vector datasets. Note the significant time reduction and the ability of LR to handle larger datasets where DSDP fails.

As shown in Figure 3, the low-rank solver (LR) provides dramatic speedups compared to traditional solvers like DSDP. For the Pima dataset, DSDP required 25,109 seconds, whereas the LR10 approach finished in just 153 seconds—a ~160x speedup. Furthermore, for larger datasets like Segment and Satimage, DSDP failed to converge due to resource limits, while the LR solver handled them efficiently.

Clustering performance comparison between the proposed Low-Rank SDP method and state-of-the-art techniques like Graclus and Spectral clustering across various graph datasets.

In graph clustering experiments (Figure 4), the Low-Rank SDP method consistently matched or outperformed established tools like Graclus and spectral clustering. Notably, the low-rank solver often found solutions with higher objective values because it avoids the information loss associated with post-hoc projection steps required by convex relaxations.

Conclusion

By prioritizing low-rank structure over convexity, the proposed method offers a highly scalable alternative for large-scale machine learning tasks. While non-convexity theoretically introduces the risk of local minima, empirical results demonstrate that with proper initialization, the benefits in computational efficiency and solution quality are substantial. Future research directions include automated rank selection and integration with multilevel graph methods for even larger-scale applications.

Summary updated

Abstract

Many non-convex problems in machine learning such as embedding and clustering have been solved using convex semidefinite relaxations. These semidefinite programs (SDPs) are expensive to solve and a...
BibTeX
@inproceedings{kulis2007fast,
  author = {Brian Kulis and Arun C. Surendran and John C. Platt},
  title = {{Fast Low-Rank Semidefinite Programming for Embedding and Clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=GYZbGxnSy0I},
}
Figure