Sketch-and-lift: scalable subsampled semidefinite program for K-means clustering

Yubo Zhuang, Xiaohui Chen, Yun Yang

Abstract: Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed K-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the K-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original K-means SDP with substantially reduced runtime.

Introduction

Clustering is a fundamental task in unsupervised learning, but the classic K-means problem is NP-hard. While the ubiquitous Lloyd’s algorithm (standard K-means) is fast, it is prone to getting stuck in local optima and lacks strong theoretical guarantees in noisy settings. Recent research has shown that Semidefinite Programming (SDP) relaxations can achieve "exact recovery"—finding the perfect cluster labels—under the Gaussian Mixture Model (GMM). However, SDPs have a massive computational footprint, typically scaling at $O(n^{3.5})$, where $n$ is the number of data points. This makes them unusable for even moderate-sized datasets.

This paper introduces Sketch-and-Lift (SL), an algorithm that bridges this gap. It achieves the high accuracy of SDP relaxations with linear time complexity by solving the problem on a tiny subsample and "lifting" the solution to the full dataset.

The Sketch-and-Lift (SL) Framework

The SL framework consists of three main steps:

  1. Sketch: Randomly subsample a small subset of $m$ points from the total $n$ points.
  2. Solve: Run the SDP-relaxed K-means on this $m$-sized "sketch" to obtain cluster labels for the subset.
  3. Lift: Use the labels from the subset to calculate cluster centroids, then "lift" the solution by assigning all remaining $n-m$ points to their nearest estimated centroid.

To handle real-world complexities, the authors propose several variants:

  • BCSL (Bias-Corrected SL): Adjusts for unequal cluster sizes by matching variances through further down-sampling before the lift step.
  • WSL (Weighted SL): Uses non-uniform sampling weights to ensure small clusters are adequately represented in the sketch.
  • Multi-epoch SL: Averages centroids from multiple independent subsamples to boost accuracy.
  • Multi-round WSL: Iteratively refines sampling weights based on previous results.

Experimental Evaluation

The methods were evaluated using synthetic Gaussian Mixture Model (GMM) data, where parameters like separation ($\Delta$), dimension ($p$), and sample size ($n$) were controlled. Real-world testing was conducted on the CyTOF (Mass Cytometry) dataset (72,463 cells, 14 populations) and a benchmark Unbalanced 2-D Gaussian dataset designed to test performance on clusters with varying densities.

Key Results and Insights

A surprising theoretical insight is that the subsample size $m$ can be remarkably small—as low as $O(\log^2 n)$—while still allowing for exact recovery of the entire dataset's labels. This is because it is more efficient to get a clean estimate of cluster centers from a small, correctly labeled subset than to use the entire dataset if it includes many mislabeled points.

Error rate as the total number of data points n increases.

As shown in Figure 5, the SL variants (M1-M5) maintain low error rates even as the dataset size $n$ grows, demonstrating superior scalability compared to standard approaches. Because the SDP is only solved on a small, fixed-size sketch, the overall complexity is dominated by the $O(n)$ "lifting" step, giving SL the same scaling behavior as K-means++.

Error rate as the cluster separation parameter λ* varies.

Figure 1 illustrates the error rate relative to the separation parameter $\lambda^*$. The results highlight a sharp transition to exact recovery as separation increases, consistent with theoretical predictions that SL enjoys an exact recovery threshold similar to the full-data SDP, which is information-theoretically tight under GMM.

In practical terms, Multi-epoch SL (M4) consistently outperformed K-means++ in accuracy, matching the performance of the full-data SDP while being orders of magnitude faster. On the CyTOF dataset, the SL approach significantly reduced misclassification errors compared to K-means++, proving its robustness beyond synthetic data.

Conclusion

While the SL method shows great promise, some constraints remain. The basic method requires the dimension $p$ to be smaller than the subsampled size $m$, though BCSL mitigates this. Future work includes formal theoretical studies of multi-round convergence and exploring performance under non-Gaussian noise distributions. Nonetheless, Sketch-and-Lift provides a scalable path for applying the statistical power of SDP to large-scale clustering problems.

Summary updated

Abstract

Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed K-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the K-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original K-means SDP with substantially reduced runtime.
BibTeX
@inproceedings{zhuang2022sketch,
  author = {Yubo Zhuang and Xiaohui Chen and Yun Yang},
  title = {{Sketch-and-lift: scalable subsampled semidefinite program for K-means clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=fo1TCEenol},
}
Figure