Source-linked AI summary
k-means requires exponentially many iterations even in the plane
Andrea Vattani
TL;DR
The paper studies the gap between k-means’ practical speed and its potentially exponential worst-case running time. It constructs planar instances requiring exponentially many iterations, proving the conjectured low-dimensional lower bound and improving the prior bound. The result also identifies implications for seeding, low-spread instances, and smoothed analysis.
Problem
k-means is popular and observed to be fast, but its worst-case upper bound can be exponential in n and prior superpolynomial lower bounds required higher dimensions.
Method
The paper constructs adversarial k-means instances using n points in R2 and k = Θ(n) initial centers.
Results
2^Ω(n) iterations are required in the plane, improving the previous 2^Ω(√n) lower bound and proving the conjecture for d ≥ 2.
Takeaways & Limitations
Worst-case k-means can be exponentially slow even in two dimensions and with initial centers selected from the data points.
Takeaways & Limitations
For k = o(n), the paper notes an open gadget-construction question needed to obtain stronger bounds matching the general upper bound in constant dimensions.
Abstract
from arXiv · showhide
The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e. O(n^{kd})) can be exponential in the number of points. Recently, Arthur and Vassilvitskii [3] showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to 2^{Ω(\sqrt{n})} with a construction in d=Ω(\sqrt{n}) dimensions. In [3] they also conjectured the existence of superpolynomial lower bounds for any d >= 2. Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2^{Ω(n)}.
1 Introduction
Although k-means is widely used for its simplicity and practical speed, worst-case theory permits extremely long runs. This paper proves superpolynomial behavior already in the plane and strengthens prior lower bounds.
- Motivation: k-means partitions points by alternating nearest-center assignments and recomputation of cluster means until stabilization.It is a local search method initialized with k centers.
- Motivation: Despite observed practical speed, existing worst-case bounds do not corroborate this performance.The general upper bound is O(n^kd), which can be exponential in n.
- Prior work: 2^Ω(√n) iterations was the previous best known lower bound, obtained by Arthur and Vassilvitskii in d = Θ(log n) dimensions.Their result left open whether superpolynomial lower bounds exist for d > 1 with fewer dimensions.
- Our result: 2^Ω(n) iterations are achieved by a construction in the plane with k = Θ(n), proving the conjectured superpolynomial lower bound for d ≥ 2.The construction uses n points in R2 and adversarially chosen centers.
- Our result: The lower bound remains exponential when initial centers are chosen adversarially from the data points.This addresses a common seeding practice rather than relying only on arbitrary centers.
- Further implications: A three-dimensional low-spread variant also requires 2^Ω(n) iterations, disproving the Har-Peled–Sadri conjecture for d ≥ 3.The paper additionally argues that smoothed analysis improves performance for sufficiently large k.
2 The k-means algorithm
The algorithm repeatedly assigns each point to its closest center and replaces each center with the mean of its assigned cluster. It stops when neither clusters nor centers change.
- Algorithm: k-means partitions n points in R^d into k clusters using an initial set of k centers.The centers may be chosen arbitrarily at initialization.
- Assignment: Each point is assigned to the cluster whose center is closest to it, producing a Voronoi-style partition.Ties between equally close centers are broken arbitrarily.
- Update: Each center is recomputed as the center of mass of the points assigned to its cluster.The construction permits constant integer weights, treating the input as a multiset.
- Termination: The assignment and recomputation steps repeat until clusters and centers remain unchanged.The final partition is the set of stabilized clusters.
- Degeneracies: Degeneracies can remove an empty center or resolve equal-distance assignments by arbitrary tie-breaking.The paper states that its lower-bound constructions avoid both situations.
3 Lower bound
The construction models exponentially many k-means iterations with interacting planar gadgets that repeatedly wake one another. With a linear number of gadgets, points, and centers, the resulting instance requires 2^Ω(n) iterations, and extensions preserve the bound under additional constraints.
- High level intuition: 2^Ω(t) wake-ups arise from a watchman chain in which each watchman wakes its predecessor twice before sleeping.The leaf watchman falls asleep after being woken, while higher watchmen repeat their two-call day.
- Gadget construction: Each gadget has two centers and multiple clusterings representing stages such as morning, afternoon, night, and calls that wake the preceding gadget.The sleeping state places a center at S*_i, while temporary point assignments restore the predecessor’s morning clustering.
- Lower bound: 2^Ω(k) iterations follow from using t = Θ(k) constant-center gadgets, and 2^Ω(n) iterations follow because each gadget contributes only constantly many points with k = Θ(n).The full instance contains O(t) points and O(t) initial centers formed by unions over all gadgets.
- Leaf gadget: The leaf gadget G0 consists of one point and one center, falls asleep after being woken by G1, and therefore completes the chain’s terminal behavior.After a temporary wake-up, its point cluster returns to the singleton state.
- Gadget dynamics: During a gadget’s second call and night, points temporarily join neighboring clusters before returning, enabling repeated wake-up transitions.The radii are chosen so assignments begin at the required time and return when a mean crosses the relevant distance threshold.
- Extensions: The same exponential lower bound can be obtained in three dimensions with linear spread, disproving the polynomial-in-spread conjecture for every d ≥ 3.This extension uses the same argument as the planar construction.
4 Conclusions and further discussion
The construction yields exponentially many k-means iterations in the plane and improves prior bounds in both iteration count and dimensionality. The discussion identifies open directions for intermediate k and for the ordinary one-dimensional case.
- Conclusions: The result improves the previous 2^Ω(√n) iteration lower bound and reduces the required dimensionality from d = Ω(√n) to the plane.The prior dimensionality and iteration bounds are stated in the comparison with earlier work.
- Further discussion: For k = o(n), a gadget with Θ(n/k) points that wakes the next gadget Ω(n/k) times would yield a lower bound of (n/k)^Ω(n/k).For k = n^c, this simplifies to n^Ω(k).
- Further discussion: A polynomial upper bound is known for d = 1 in the smoothed regime, while extending this result to the ordinary case remains an open question.The discussion explicitly distinguishes the smoothed and ordinary settings.