Fast k-means Seeding Under The Manifold Hypothesis

We study beyond worst case analysis for the $k$-means problem where the goal is to model typical instances of $k$-means arising in practice. Existing theoretical approaches provide guarantees under certain assumptions on the optimal solutions to $k$-means, making them difficult to validate in practice. We adopt the manifold hypothesis, where data obtained in ambient dimension $D$ concentrates around a low dimensional manifold of intrinsic dimension $d$, as a reasonable assumption to model real world clustering instances. We identify key geometric properties of datasets which have theoretically predictable scaling laws depending on the quantization exponent $\varepsilon = 2/d$ using techniques from optimum quantization theory. We show how to exploit these regularities to design a fast seeding method called $\operatorname{Qkmeans}$ which provides $O(\rho^{-2} \log k)$ approximate solutions to the $k$-means problem in time $O(nD \log k) + \widetilde{O}(\rho^{-1}k^{1+\gamma})$; where the exponent $\gamma = \varepsilon + \rho$ for an input parameter $\rho < 1$. This allows us to obtain new runtime - quality tradeoffs. We perform a large scale empirical study across various domains to validate our theoretical predictions and algorithm performance to bridge theory and practice for beyond worst case data clustering.

Clustering is a fundamental problem in machine learning, where the goal is to divide a dataset into groups so that similar objects end up together. The k-means formulation is the most widely used version of this problem, but it is computationally hard to solve exactly. Most existing algorithms are data oblivious - they provide worst-case guarantees that hold for any input, even pathological ones rarely seen in practice - and ignore the structure of real-world data. In our work, we leverage a well-established observation, the manifold hypothesis, that high-dimensional data in practice tends to lie near a much lower-dimensional surface. We show that when data satisfies this, key geometric properties of the clustering problem (such as how much the cost improves as you use more clusters) follow predictable scaling laws determined by this hidden low dimensionality. We exploit these regularities to design a fast seeding algorithm based on rejection sampling, which efficiently approximates the expensive initialisation step of k-means++ and efficiently finds near-optimal clusterings, achieving new tradeoffs between solution quality and runtime. We validate our assumptions across image, text, and tabular datasets spanning diverse domains, finding strikingly consistent behaviour throughout.