Convex Optimization Procedure for Clustering: Theoretical Revisit

Changbo Zhu, Huan Xu, Chenlei Leng, Shuicheng Yan

While clustering is a cornerstone of unsupervised learning, traditional methods like K-means are notoriously unstable due to their non-convex nature. This paper provides a rigorous theoretical foundation for Sum-of-Norms (SON) clustering—a convex alternative—proving that it can perfectly recover cluster memberships as long as the clusters are sufficiently separated relative to their size and sample distribution.

The Problem with Traditional Clustering

Most popular clustering algorithms, such as K-means and Gaussian Mixture Models, are inherently unstable. Because they rely on non-convex optimization, they frequently get stuck in local optima. If you run K-means twice on the same dataset with different random initializations, you might end up with two completely different results.

To solve this, researchers proposed SON clustering (also known as Clusterpath). SON formulates clustering as a convex optimization problem, meaning it has a single global optimum—no random initialization is required. However, until this paper, SON was mostly an empirical curiosity. It was known to work in practice, but there was no mathematical guarantee defining exactly when or why it would succeed. The authors set out to bridge this gap between empirical success and theoretical understanding.

Methodology: Fidelity, Fusion, and Lifting

The core of SON is an objective function that balances two competing goals:

  1. Fidelity: Keeping the "centroid" points ($X$) close to the original data points ($A$).
  2. Fusion: Applying a "sum-of-norms" regularization term $\alpha \sum_{i<j} \|X_{i\cdot} - X_{j\cdot}\|_2$ that penalizes differences between points.

This penalty acts like a "gravitational pull," encouraging data points to merge into the same location. When two rows in the solution matrix $X$ become identical, those two data points are officially assigned to the same cluster.

The authors' primary contribution is a theoretical "lifting" technique. They project the problem into a higher-dimensional space where the complex regularization term becomes easier to analyze. By examining the "dual" version of this optimization problem, they derived the exact conditions under which the algorithm successfully "fuses" the correct points together.

Additionally, they demonstrate a Kernelization approach, showing that SON can be extended to Hilbert spaces to handle clusters with complex, non-linear shapes.

Key Insights and Results

To validate their theoretical revisit, the authors focused on controlled synthetic environments—specifically, data points drawn from two $p$-dimensional hypercubes. They systematically varied the distance between cubes ($d_{1,2}$), the edge lengths of the cubes ($s$), and the number of samples in each cluster ($n_1, n_2$).

The "Weighted Size" Metric and Separation Threshold

The authors introduced a new metric, $w_{1,2}$, called the "weighted size." This value accounts for both the physical size of a cluster and the ratio of samples between clusters. The defining breakthrough of the paper is the proof that SON succeeds if the distance between clusters is greater than this weighted size ($d_{1,2} > w_{1,2}$).

Numerical experiments confirmed that the distance required for successful clustering scales linearly with the size of the clusters, exactly as their theory predicted.

Theoretical bounds vs empirical performance across different sample size ratios, scaling linearly with cluster size.

As seen in the plots above, the theoretical "failure bound" ($w_{1,2}$) closely tracks the empirical failure point ($\bar{d}_{1,2}$) across different sample sizes and cluster dimensions, proving the theory is tight and practical.

The "Overwhelming" Effect of Imbalance

The theory also explains why imbalanced clusters are harder to solve. If one cluster has significantly more points than the other ($n_1 \gg n_2$), the "weighted size" increases. Consequently, the clusters must be much further apart for the algorithm to successfully distinguish them.

The effect of cluster imbalance: required separation distance increases as the sample ratio between clusters grows.

Finally, the authors proved that SON is invariant to isometries (rotations, translations, and reflections). If a dataset is rotated 45 degrees, the clustering logic and performance remain identical.

Limitations and Future Work

While a landmark for SON theory, the paper has a few notable boundaries:

  • Geometric Constraints: The current proof specifically assumes clusters are hypercubes. While this is a standard starting point for mathematical proofs, real-world data is rarely so uniform.
  • Two-Cluster Focus: The primary theoretical results are derived for the two-cluster case. Extending this to an arbitrary number of clusters ($c > 2$) with the same level of rigor remains a mathematical challenge.
  • Computational Complexity: While convex, SON can be computationally expensive for massive datasets compared to lightning-fast (but unstable) algorithms like K-means. Future work will likely focus on making these convex solvers more efficient for "Big Data" scales.

Summary updated

Abstract

In this paper, we present theoretical analysis of SON~--~a convex optimization procedure for clustering using a sum-of-norms (SON) regularization recently proposed in \cite{ICML2011Hocking_419,SON, Lindsten650707, pelckmans2005convex}. In particular, we show if the samples are drawn from two cubes, each being one cluster, then SON can provably identify the cluster membership provided that the distance between the two cubes is larger than a threshold which (linearly) depends on the size of the cube and the ratio of numbers of samples in each cluster. To the best of our knowledge, this paper is the first to provide a rigorous analysis to understand why and when SON works. We believe this may provide important insights to develop novel convex optimization based algorithms for clustering.
BibTeX
@inproceedings{zhu2014convex,
  author = {Changbo Zhu and Huan Xu and Chenlei Leng and Shuicheng Yan},
  title = {{Convex Optimization Procedure for Clustering: Theoretical Revisit}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure