Research map / Learning theory and algorithms / Clustering

Analyzing $D^\alpha$ seeding for $k$-means

ICML 2024 · Learning theory and algorithms › Clustering · approach: k-means++ seeding analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a theoretical analysis of D^alpha seeding (alpha>2) for standard k-means, showing constant-factor or sub-logarithmic approximation guarantees on beyond-worst-case instances such as Gaussian mixtures.

Problem

Explain why D^alpha seeding with alpha>2 empirically beats k-means++ (D^2 seeding) on the standard k-means objective, where D^2 seeding is only O(log k) approximate and worst-case analysis favors alpha=2.

Approach

Proves that D^alpha seeding with alpha>2 gives an expected approximation depending on the cluster moment parameter g_alpha, the ratio of max to min cluster standard deviation, and the number of distinct cluster-weight scales, using a novel potential function that handles sampling probabilities arbitrarily far from proportional to cost.

Key results

• For alpha>2, D^alpha seeding gives expected approximation O(((sigma_max/sigma_min)^{2-4/alpha}) * (g_alpha * min{l, log k})^{2/alpha}) with respect to standard k-means cost.
• Lower bounds show dependence on g_alpha and sigma_max/sigma_min is tight; for equal-weight Gaussian mixtures with constant alpha>2 the guarantee is constant-factor.
• Greedy k-means++ with Theta(log k) samples per step is shown to be no better than Omega((log log f(k))^2) approximation on a family where D^alpha seeding is constant-factor.

Measured effects reported in the paper

Surprising findings

• Greedy k-means++ as implemented in scikit-learn can have super-constant approximation where D^alpha seeding is constant factor.
• Experiments suggest the advantage of alpha>2 persists after running Lloyd's algorithm to convergence.

Limitations

• Dependence on the number of distinct mixing weights (min{l, log k}) is not shown to be necessary and remains open.
• Experiments are limited to small synthetic Gaussian mixtures (k=4, d=2) and do not validate the bound's scaling on real data at scale.
• Worst-case analysis still favors alpha=2; guarantees rely on beyond worst-case instance parameters.

Experimental setup

Datasets: synthetic mixtures of Gaussians (balanced, k=4, d=2)

Benchmarks: synthetic balanced Gaussian mixtures

Metrics: k-means cost approximation factor (theoretical)

Baselines: D^2 seeding (k-means++) greedy k-means++ (scikit-learn) Lloyd's algorithm

Builds on: k-means++ (D^2 seeding) Balcan et al. 2018 data-driven choice of alpha Dasgupta 2013 potential analysis of D^2 seeding Arthur and Vassilvitskii 2007 (k,alpha)-clustering analysis

Closest papers by meaning

• k-variates++: more pluses in the k-means++ (ICML 2016 · similarity 0.89)
• Fast and Accurate $k$-means++ via Rejection Sampling (NeurIPS 2020 · similarity 0.88)
• Approximate K-Means++ in Sublinear Time (AAAI 2016 · similarity 0.88)
• Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.85)
• Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.85)
• Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.85)