An Efficient Semismooth Newton Based Algorithm for Convex Clustering
This work addresses computational bottlenecks for researchers and practitioners applying convex clustering to large datasets, representing an incremental improvement over existing optimization methods.
The authors tackled the challenge of solving large-scale convex clustering problems efficiently by proposing a semi-smooth Newton based augmented Lagrangian method. Their algorithm demonstrated high efficiency and robustness in numerical experiments, showing superior performance and scalability compared to existing first-order methods.
Clustering may be the most fundamental problem in unsupervised learning which is still active in machine learning research because its importance in many applications. Popular methods like K-means, may suffer from instability as they are prone to get stuck in its local minima. Recently, the sum-of-norms (SON) model (also known as clustering path), which is a convex relaxation of hierarchical clustering model, has been proposed in [7] and [5] Although numerical algorithms like ADMM and AMA are proposed to solve convex clustering model [2], it is known to be very challenging to solve large-scale problems. In this paper, we propose a semi-smooth Newton based augmented Lagrangian method for 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 compared to existing first-order methods.