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⁴ϵ⁻¹).
Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.
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