Efficient, certifiably optimal clustering with applications to latent variable graphical models

DOI10.1007/S10107-019-01375-2MaRDI QIDQ2425167zbMATH OpenOpenAlexWikidataFDO

Authors Carson Eisenach, Han Liu

Publication date 26 June 2019

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.00530

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Semidefinite programming (90C22) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90)

Abstract: 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 $ildeO(d^{7}logepsilo{n}^{-1})$ to $ildeO(d^6{K}^{-2}epsilo{n}^{-1})$ arithmetic operations for an $epsilon$-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 $ildeO(d^{7}logepsilo{n}^{-1})$ using a standard SDP solver to $ildeO(d^{4}epsilo{n}^{-1})$.

Recommendations

• Probably certifiably correct k-means clustering
• Improved Conic Reformulations for $K$-means Clustering
• Clustering subgaussian mixtures by semidefinite programming
• Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
• Semidefinite spectral clustering

Cites work

• Adaptive restart for accelerated gradient schemes
• An efficient algorithm for a complete link method
• Approximating K‐means‐type Clustering via Semidefinite Programming
• Convex optimization: algorithms and complexity
• Convex relaxation methods for community detection
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Exact clustering of weighted graphs via semidefinite programming
• Exact Recovery in the Stochastic Block Model
• Guaranteed clustering and biclustering via semidefinite programming
• Hanson-Wright inequality and sub-Gaussian concentration
• scientific article; zbMATH DE number 6381735 (Why is no real title available?)
• scientific article; zbMATH DE number 1489799 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Improved spectral-norm bounds for clustering
• Introductory lectures on convex optimization. A basic course.
• Least squares quantization in PCM
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Probably certifiably correct k-means clustering
• Relax, no need to round: integrality of clustering formulations
• SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
• Smooth minimization of non-smooth functions
• Smoothing technique and its applications in semidefinite optimization
• Spectral norm of products of random and deterministic matrices
• The planar \(k\)-means problem is NP-hard

Cited in

(11)

• Probably certifiably correct k-means clustering
• An exemplar-based clustering using efficient variational message passing
• scientific article; zbMATH DE number 6680234 (Why is no real title available?)
• Latent Clustering on Graphs with Multiple Edge Types
• Identifying graph clusters using variational inference and links to covariance parametrization
• Simultaneous Clustering and Estimation of Heterogeneous Graphical Models
• Finding Non-Overlapping Clusters for Generalized Inference Over Graphical Models
• Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
• High-dimensional inference for cluster-based graphical models
• Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
• Sketch-and-solve approaches to \(k\)-means clustering by semidefinite programming

Describes a project that uses

Uses Software

• SDPNAL+
• k-means++
• Mosek

This page was built for publication: Efficient, certifiably optimal clustering with applications to latent variable graphical models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425167)