Papers › Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models
Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models
Carson Eisenach, Han Liu
Motivated by the task of clustering either d variables or d points into K groups, we investigate efficient algorithms to solve the Peng-Wei (P-W) K-means semi-definite programming (SDP) relaxation. The P-W SDP has been shown in the literature to have good statistical properties in a variety of settings, but remains intractable to solve in practice. To this end we propose FORCE, a new algorithm to solve this SDP relaxation. Compared to the naive interior point method, our method reduces the computational complexity of solving the SDP from Õ(d⁷logϵ⁻¹) to Õ(d⁶K⁻²ϵ⁻¹) arithmetic operations for an ϵ-optimal solution. Our method combines a primal first-order method with a dual optimality certificate search, which when successful, allows for early termination of the primal method. We show for certain variable clustering problems that, with high probability, FORCE is guaranteed to find the optimal solution to the SDP relaxation and provide a certificate of exact optimality. As verified by our numerical experiments, this allows FORCE to solve the P-W SDP with dimensions in the hundreds in only tens of seconds. For a variation of the P-W SDP where K is not known a priori a slight modification of FORCE reduces the computational complexity of solving this problem as well: from Õ(d⁷logϵ⁻¹) using a standard SDP solver to Õ(d⁴ϵ⁻¹).
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections