Efficient Clustering for Stretched Mixtures: Landscape and Optimality
This addresses clustering challenges for stretched distributions, offering a method that improves over existing techniques for specific data types, though it is incremental in its approach.
The paper tackles the problem of clustering data from stretched elliptical mixtures where traditional methods like PCA and k-means fail, by proposing a non-convex program that uses an affine transform to simplify clustering, and proves that an efficient algorithm achieves near-optimal statistical precision without good initialization when sample size exceeds a constant multiple of dimension.
This paper considers a canonical clustering problem where one receives unlabeled samples drawn from a balanced mixture of two elliptical distributions and aims for a classifier to estimate the labels. Many popular methods including PCA and k-means require individual components of the mixture to be somewhat spherical, and perform poorly when they are stretched. To overcome this issue, we propose a non-convex program seeking for an affine transform to turn the data into a one-dimensional point cloud concentrating around $-1$ and $1$, after which clustering becomes easy. Our theoretical contributions are two-fold: (1) we show that the non-convex loss function exhibits desirable geometric properties when the sample size exceeds some constant multiple of the dimension, and (2) we leverage this to prove that an efficient first-order algorithm achieves near-optimal statistical precision without good initialization. We also propose a general methodology for clustering with flexible choices of feature transforms and loss objectives.