Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

In this paper, we consider the problem of partitioning a small data sample of size n drawn from a mixture of 2 sub-gaussian distributions in ℝp. We consider semidefinite programming relaxations of an integer quadratic program that is formulated essentially as finding the maximum cut on a graph, where edge weights in the cut represent dissimilarity scores between two nodes based on their p features. We define the signal-to-noise ratio (SNR) as s2 := minn p γ2, Delta2, where Delta2 := p γ denotes the ℓ22 distance between the two cluster centers. Our contributions are twofold. First, we provide a unified framework for analyzing three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering, yielding universal polynomial-rate misclassification guarantees for all three algorithms. Moreover, our theory allows for partial recovery (success rate < 100%) as long as s2 is lower bounded by a constant. Second, we prove that the misclassification errors for SDP1 and BalancedSDP decay exponentially with respect to the SNR s2 and the BalancedSDP requires no explicit debiasing when the two clusters have equal sizes. To our knowledge, this is the first time such results are obtained for semidefinite relaxations of MAX CUT in population clustering. We provide simulation evidence illuminating the theoretical predictions.