Convex clustering: Model, theoretical guarantee and efficient algorithm

Defeng Sun, Kim Chuan Toh, Yancheng Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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
Volume22
Publication statusPublished - Jan 2021

Keywords

  • 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

Cite this