Relax, no need to round: integrality of clustering formulations
  We study exact recovery conditions for convex relaxations of point cloud
clustering problems, focusing on two of the most common optimization problems
for unsupervised clustering: $k$-means and $k$-median clustering. Motivations
for focusing on convex relaxations are: (a) they come with a certificate of
optimality, and (b) they are generic tools which are relatively parameter-free,
not tailored to specific assumptions over the input. More precisely, we
consider the distributional setting where there are $k$ clusters in
$\mathbb{R}^m$ and data from each cluster consists of $n$ points sampled from a
symmetric distribution within a ball of unit radius. We ask: what is the
minimal separation distance between cluster centers needed for convex
relaxations to exactly recover these $k$ clusters as the optimal integral
solution? For the $k$-median linear programming relaxation we show a tight
bound: exact recovery is obtained given arbitrarily small pairwise separation
$\epsilon > 0$ between the balls. In other words, the pairwise center
separation is $\Delta > 2+\epsilon$. Under the same distributional model, the
$k$-means LP relaxation fails to recover such clusters at separation as large
as $\Delta = 4$. Yet, if we enforce PSD constraints on the $k$-means LP, we get
exact cluster recovery at center separation $\Delta > 2\sqrt2(1+\sqrt{1/m})$.
In contrast, common heuristics such as Lloyd's algorithm (a.k.a. the $k$-means
algorithm) can fail to recover clusters in this setting; even with arbitrarily
large cluster separation, k-means++ with overseeding by any constant factor
fails with high probability at exact cluster recovery. To complement the
theoretical analysis, we provide an experimental study of the recovery
guarantees for these various methods, and discuss several open problems which
these experiments suggest.
