An Efficient Semismooth Newton based Algorithm for Convex Clustering
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:57185726, 2018.
Abstract
Clustering is a fundamental problem in unsupervised learning. Popular methods like Kmeans, may suffer from instability as they are prone to get stuck in its local minima. Recently, the sumofnorms (SON) model (also known as clustering path), which is a convex relaxation of hierarchical clustering model, has been proposed in (Lindsten et al., 2011) and (Hocking et al., 2011). Although numerical algorithms like alternating direction method of multipliers (ADMM) and alternating minimization algorithm (AMA) have been proposed to solve convex clustering model (Chi & Lange, 2015), it is known to be very challenging to solve largescale problems. In this paper, we propose a semismooth Newton based augmented Lagrangian method for largescale convex clustering problems. Extensive numerical experiments on both simulated and real data demonstrate that our algorithm is highly efficient and robust for solving largescale problems. Moreover, the numerical results also show the superior performance and scalability of our algorithm comparing to existing firstorder methods.
Related Material


