Efficient Clustering for Stretched Mixtures: Landscape and Optimality

Kaizheng Wang, Yuling Yan, Mateo Díaz

Introduction

Standard clustering tools like k-means and Principal Component Analysis (PCA) often fail when data clusters are "stretched" into elongated ellipses rather than neat spheres. To address this, researchers introduce CURE (Clustering via Uncoupled REgression), a method that uses non-convex optimization to find a projection where even the most stretched clusters become easily separable. Despite the problem's non-convex nature, simple gradient-based algorithms can reach near-optimal statistical accuracy without needing a lucky starting guess.

The Problem: Spherical Bias in Clustering

Clustering is a foundational task in data science, but most popular algorithms exhibit a "spherical bias." Methods like k-means rely on Euclidean distance, assuming clusters are roughly round "blobs." PCA looks for directions of maximum variance; however, in "stretched" datasets—where clusters are long, thin ellipses—the direction of maximum variance might run along a single cluster rather than between distinct clusters.

This paper tackles the challenge of binary clustering for elliptical distributions. When these distributions are highly anisotropic (stretched), the mean vector does not provide enough signal for traditional methods to separate the groups. The goal is to find a linear classifier that succeeds even when the data is stretched in ways that baffle standard spectral or distance-based methods.

Methodology: CURE

The authors propose CURE (Clustering via Uncoupled REgression). The core idea is to find an affine transformation (a mix of rotation, scaling, and shifting) that projects high-dimensional data onto a one-dimensional line. On this line, the data should concentrate around two distinct points: -1 and 1.

Key technical components include:

  • Uncoupled Regression: Because the data is unlabeled (unsupervised), standard regression is impossible. Instead, CURE matches the distribution of the projected data to a target distribution (a 50/50 mix of -1 and 1).
  • Clipped Quartic Loss: The authors designed a specific loss function that resembles a "double-well" (reaching minima at -1 and 1). To ensure mathematical stability and prevent the "exploding gradient" problem, they "clip" the growth of this function so it does not grow too fast far away from the origin.
  • Perturbed Gradient Descent: To solve the optimization, they use a version of gradient descent that injects a tiny amount of noise. This helps the algorithm "shake" itself out of saddle points—flat areas where the gradient is zero but the algorithm hasn't reached a true minimum.

Key Insights: Benign Landscapes and Statistical Optimality

  • Landscape is Everything: In non-convex optimization, getting stuck in "bad" local minima is a primary concern. The authors prove that for this problem, if the sample size is sufficiently large relative to the dimension ($n/d$ is large enough), the "landscape" of the loss function becomes "benign." Almost all stationary points are either the global minimum or are "riddled" with directions that lead toward it.
  • No "Warm Start" Needed: Most non-convex solvers require a very good initial guess to work. CURE is mathematically shown to be robust enough to start from zero and still find the optimal solution.
  • Statistical Optimality: CURE achieves a statistical error rate of $O(\sqrt{d/n})$. This matches the optimal rate of supervised learning, meaning CURE performs almost as well as if it had access to the true labels.

Key Results

The paper evaluates CURE on synthetic elliptical mixtures and the Fashion-MNIST dataset—specifically, a binary task distinguishing "T-shirts/tops" from "Pullovers." These categories are notoriously difficult to separate with simple methods because they share similar global shapes but differ in fine details.

PCA embedding and histogram for Fashion-MNIST showing a 42.2% error rate.
  • Superiority over PCA/k-means: On the Fashion-MNIST task, PCA-based clustering resulted in a 42.2% error rate, which is barely better than random guessing. In contrast, CURE achieved an impressive error rate of only 5.2%.
  • Robustness to Imbalance: Even when the two clusters were not perfectly balanced, CURE maintained strong performance. For example, at a 4:1 imbalance ratio, CURE maintained a misclassification rate of around 11.3%, while k-means and vanilla spectral methods hovered around 45-49% error.
CURE misclassification rates over iterations across different class imbalance ratios.
  • Efficiency: The algorithm converges in a number of iterations that scales linearly with the sample size and dimension, making it highly practical for real-world, high-dimensional data.

Limitations and Future Work

While CURE presents a significant step forward, the current theoretical framework is primarily built for two-cluster (binary) problems. Although the authors suggest a meta-algorithm for multi-class clustering, rigorous "landscape" proofs for multiple clusters remain an open challenge. Additionally, the theory relies on the data being somewhat elliptical; guarantees might not hold for highly non-convex or "manifold-shaped" clusters like concentric circles. Finally, the authors note that CURE could be extended by using neural networks as the feature transform instead of a simple linear projection, opening the door to advanced unsupervised deep clustering.

Summary updated

Abstract

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.
BibTeX
@inproceedings{wang2020efficient,
  author = {Kaizheng Wang and Yuling Yan and Mateo Díaz},
  title = {{Efficient Clustering for Stretched Mixtures: Landscape and Optimality}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=VZmTTAELzjR},
}
Figure