# Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm

arXiv: https://arxiv.org/abs/1810.02677 · HTML: https://mlsanity.com/paper/1810.02677/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2018.

## Built on by (most cited first, 26 of 26)

- [Personalized Federated Learning via Convex Clustering](https://mlsanity.com/paper/2202.00718/) (2022)
- [Non-smooth Bayesian Optimization in Tuning Problems](https://mlsanity.com/paper/2109.07563/) (2021)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [Convex Clustering through MM: An Efficient Algorithm to Perform Hierarchical Clustering](https://mlsanity.com/paper/2211.01877/) (2022)
- [Multi-Prototypes Convex Merging Based K-Means Clustering Algorithm](https://mlsanity.com/paper/2302.07045/) (2023)
- [Sum-of-norms clustering does not separate nearby balls](https://mlsanity.com/paper/2104.13753/) (2021)
- [On Convex Clustering Solutions](https://mlsanity.com/paper/2105.08348/) (2021)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)
- [Multi-Task Learning Regression via Convex Clustering](https://mlsanity.com/paper/2304.13342/) (2023)
- [Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees](https://mlsanity.com/paper/2303.16841/) (2023)
- [Fast inference of latent space dynamics in huge relational event networks](https://mlsanity.com/paper/2303.17460/) (2023)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)
- [Causal Clustering for Conditional Average Treatment Effects Estimation and Subgroup Discovery](https://mlsanity.com/paper/2509.05775/) (2025)
- [Fitting Sparse Markov Models to Categorical Time Series Using Convex Clustering](https://mlsanity.com/paper/2202.05485/) (2022)
- [Simple and Scalable Algorithms for Cluster-Aware Precision Medicine](https://mlsanity.com/paper/2211.16553/) (2022)
- [Re-embedding data to strengthen recovery guarantees of clustering](https://mlsanity.com/paper/2301.10901/) (2023)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Clusterpath Gaussian Graphical Modeling](https://mlsanity.com/paper/2407.00644/) (2024)
- [Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number](https://mlsanity.com/paper/2407.20119/) (2024)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective](https://mlsanity.com/paper/2508.20231/) (2025)
- [Bilevel Models for Adversarial Learning and A Case Study](https://mlsanity.com/paper/2510.25121/) (2025)
- [Enhancing Kernel Power K-means: Scalable and Robust Clustering with Random Fourier Features and Possibilistic Method](https://mlsanity.com/paper/2511.10392/) (2025)
- [Biconvex Biclustering](https://mlsanity.com/paper/2604.03936/) (2026)
- [Affinity Graph Connectivity in Convex Clustering](https://mlsanity.com/paper/2605.24673/) (2026)

## Abstract (arXiv)

Clustering is a fundamental problem in unsupervised learning. Popular methods like K-means, 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 clustering path) has been proposed in 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 sufficient conditions for the perfect recovery guarantee of the general weighted convex clustering model, which include and improve existing theoretical results as special cases. In addition, we develop a semismooth Newton based augmented Lagrangian method for solving large-scale convex clustering problems. Extensive numerical experiments on both simulated and real data demonstrate that our algorithm is highly efficient and robust for solving large-scale problems. Moreover, the numerical results also show the superior performance and scalability of our algorithm comparing to the existing first-order methods. In particular, our algorithm is able to solve a convex clustering problem with 200,000 points in ℝ3 in about 6 minutes.