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

DOI10.1007/S10107-019-01375-2zbMATH Open1415.90072arXiv1806.00530OpenAlexW2896660788WikidataQ61939693 ScholiaQ61939693MaRDI QIDQ2425167FDOQ2425167

Han Liu, Carson Eisenach

Publication date: 26 June 2019

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

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})$.

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• Least squares quantization in PCM
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• Hanson-Wright inequality and sub-Gaussian concentration
• Exact Recovery in the Stochastic Block Model
• Guaranteed clustering and biclustering via semidefinite programming
• The planar \(k\)-means problem is NP-hard
• Spectral norm of products of random and deterministic matrices
• Improved Spectral-Norm Bounds for Clustering
• Smoothing technique and its applications in semidefinite optimization
• Convex optimization: algorithms and complexity
• Approximating K‐means‐type Clustering via Semidefinite Programming
• An efficient algorithm for a complete link method
• Probably certifiably correct \(k\)-means clustering
• Relax, No Need to Round
• Convex relaxation methods for community detection
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Exact Clustering of Weighted Graphs via Semidefinite Programming

Cited In (8)

• Latent Clustering on Graphs with Multiple Edge Types
• An exemplar-based clustering using efficient variational message passing
• Title not available (Why is that?)
• Simultaneous Clustering and Estimation of Heterogeneous Graphical Models
• Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing
• Finding Non-Overlapping Clusters for Generalized Inference Over Graphical Models
• Identifying graph clusters using variational inference and links to covariance parametrization
• High-Dimensional Inference for Cluster-Based Graphical Models

Uses Software

• Mosek
• SDPNAL+
• k-means++

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)