Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/93926
Title: | Convex clustering : model, theoretical guarantee and efficient algorithm | Authors: | Sun, D Toh, KC Yuan, Y |
Issue Date: | 2021 | Source: | Journal of machine learning research, 2021, v. 22, 9, p. 1-32 | Abstract: | 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 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 sufficient conditions for the perfect recovery guarantee of the general weighted convex clustering model, which include and improve existing theoretical results in (Zhu et al., 2014; Panahi et al., 2017) 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 R3 in about 6 minutes. | Keywords: | Convex clustering Augmented Lagrangian method Semismooth Newton method Conjugate gradient method Unsupervised learning |
Publisher: | MIT Press | Journal: | Journal of machine learning research | ISSN: | 1532-4435 | EISSN: | 1533-7928 | Rights: | © 2021 Defeng Sun, Kim-Chuan Toh and Yancheng Yuan. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v22/18-694.html. The following publication Sun, D., Toh, K. C., & Yuan, Y. (2021). Convex Clustering: Model, Theoretical Guarantee and Efficient Algorithm. Journal of Machine Learning Research, 22(9), 1-32 is available at https://www.jmlr.org/papers/v22/18-694.html |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
18-694.pdf | 1.04 MB | Adobe PDF | View/Open |
Page views
57
Last Week
1
1
Last month
Citations as of Apr 28, 2024
Downloads
14
Citations as of Apr 28, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.