Convex clustering: Model, theoretical guarantee and efficient algorithm

Defeng Sun, Kim Chuan Toh, Yancheng Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)


Clustering is a fundamental problem in unsupervised learning. Popular methods like Kmeans, may suffer from poor performance as they are prone to get stuck in its local minima. Recently, the sum-of-norms (SON) model (also known as the convex clustering model) has been proposed by Pelckmans et al. (2005), Lindsten et al. (2011) and Hocking et al. (2011). The perfect recovery properties of the convex clustering model with uniformly weighted all-pairwise-differences regularization have been proved by Zhu et al. (2014) and Panahi et al. (2017). However, no theoretical guarantee has been established for the general weighted convex clustering model, where better empirical results have been observed. In the numerical optimization aspect, although algorithms like the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA) have been proposed to solve the convex clustering model (Chi and Lange, 2015), it still remains very challenging to solve large-scale problems. In this paper, we establish su

Original languageEnglish
Pages (from-to)1-32
Number of pages32
JournalJournal of Machine Learning Research
Publication statusPublished - Jan 2021


  • Augmented Lagrangian method
  • Conjugate gradient method
  • Convex clustering
  • Semismooth Newton method
  • Unsupervised learning

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Convex clustering: Model, theoretical guarantee and efficient algorithm'. Together they form a unique fingerprint.

Cite this