k-Means, EM & Mixture Models
Hard and soft clustering, and why EM works.
k-means is simple to state, NP-hard to solve, and solved well in practice thanks to a seeding trick with a provable guarantee. EM is a two-line loop whose monotonicity follows from a single inequality, yet its global behavior is still being mapped. This lesson proves both guarantees and asks when mixture models can be learned at all.
What you’ll learn
- State the complexity of the k-means problem precisely: NP-hardness, exact and approximation algorithms, and the iteration complexity of Lloyd's method.
- Prove the k-means++ guarantee from its two key lemmas and an induction over uncovered clusters.
- Derive EM as coordinate ascent on the evidence lower bound, prove monotonicity, and describe its convergence rate and failure modes for Gaussian mixtures.
- Explain identifiability and separation conditions for learning Gaussian mixtures, and the moment and sum-of-squares methods that decide when learning is efficient.
The k-means problem: hardness and structure
| Setting | What is known |
|---|---|
| , dimension part of the input | NP-hard (Dasgupta, 2008; Aloise, Deshpande, Hansen & Popat, 2009) |
| , part of the input | NP-hard (Mahajan, Nimbhorkar & Varadarajan, 2012) |
| exact by dynamic programming in time, and faster | |
| and fixed | exact in time by enumerating Voronoi partitions (Inaba, Katoh & Imai, 1994) |
| fixed, any | -approximation in time linear in for fixed (Kumar, Sabharwal & Sen, 2004) |
| and part of the input | constant-factor approximations: by local search (Kanungo et al., 2004), about by primal–dual methods (Ahmadian, Norouzi-Fard, Svensson & Ward, 2017); no PTAS unless P = NP (Awasthi, Charikar, Krishnaswamy & Sinop, 2015) |
| Lloyd's iterations | in the worst case, even in the plane (Vattani, 2011); polynomial smoothed complexity (Arthur, Manthey & Röglin, 2011) |
Which version of the k-means problem can be solved exactly in polynomial time?
- with the dimension part of the input
- Points on a line (), with part of the input
- Points in the plane (), with part of the input
- Any instance, by running Lloyd's algorithm to convergence
Show the answer
B. Points on a line (), with part of the input
On a line, optimal clusters are contiguous intervals of the sorted points, so dynamic programming over (prefix, number of clusters) solves it exactly in time. In the plane with general , or with in high dimension, the problem is NP-hard.
k-means++ and its guarantee
KMEANS++-SEED(X, k)
C ← { a point of X chosen uniformly at random }
while |C| < k:
D(x) ← min over c in C of ||x − c|| for every x in X
choose x in X with probability D(x)² / Σ_y D(y)²
C ← C ∪ {x}
return C # then run Lloyd's algorithm from CEach round costs if the distances are updated incrementally, so seeding takes , the cost of one Lloyd iteration.
Lemma 1 (a uniform pick). Let be a cluster of an optimal solution, with centroid . If a center is drawn uniformly from , the identity , averaged over , gives
Lemma 2 (a pick). Suppose the next center is drawn by sampling and lands in . For , the triangle inequality and give . Averaging over bounds the sampling weight of by its average distance to , and Lemma 1's identity then gives
Induction. Call an optimal cluster covered once a center lies in it. A draw lands in the uncovered clusters with probability equal to their share of the current potential, and covers one at cost at most 8 times its optimum (Lemma 2); draws wasted in covered clusters are charged to the potential they leave behind. Induction on remaining draws and uncovered clusters, with covered points and uncovered points , gives, with the harmonic number:
Conclusion. The first center covers one cluster at expected cost (Lemma 1). Apply the induction with and use :
A cluster's points have total squared distance 10 to their centroid. You place a single center at one of the cluster's points, chosen uniformly at random. What is the expected total squared distance of the cluster's points to that center?
Show the answer
20
Lemma 1: the expectation is exactly . Each center costs , and averaging over gives the cluster's total squared distance to its centroid once more.
Two refinements matter in practice. k-means|| (Bahmani, Moseley, Vattani, Kumar & Vassilvitskii, 2012) oversamples centers in a few parallel rounds, for large data. And following k-means++ with steps of randomized local search yields a constant-factor approximation in expectation (Lattanzi & Sohler, 2019).
EM, precisely
Take any latent-variable model and data , with log-likelihood . The log of a sum resists direct maximization, but a family of lower bounds does not.
For any distribution over , multiply and divide by inside the log and rearrange. The identity is exact:
Summing over , , because every KL divergence is nonnegative; here is the expected complete-data log-likelihood plus the entropy of (in statistical physics, a negative free energy):
E-step: maximize over with fixed: zeroes the KL terms, so the bound touches at . M-step: maximize over with fixed; the entropy does not depend on , so this maximizes the expected complete-data log-likelihood.
Chain the inequalities. EM is coordinate ascent on (Neal & Hinton, 1998), which also licenses partial steps: any that merely increases (generalized EM), or updating one at a time (incremental EM).
For Gaussian mixtures this explains the folklore. Well-separated components leave little missing information (responsibilities near 0 or 1), so EM converges in a handful of iterations; heavily overlapping components make it crawl (Redner & Walker, 1984; Xu & Jordan, 1996). And the boundedness hypothesis fails: with free covariances, a component that centers on one data point and shrinks sends . The maximum-likelihood estimator does not exist, and the useful solutions are local maxima, often protected by a floor or a prior on the covariances.
Think first Right after an E-step at parameters , how large is the gap ?
Zero. The gap is , and the E-step sets each to exactly that posterior. (It is not the entropy of , which is part of .) The M-step then moves , after which a gap can reopen. Variational EM, which restricts to a tractable family, leaves a positive gap and keeps the monotonicity guarantee only for the bound , not for itself.
When can mixtures be learned?
Finite Gaussian mixtures are identifiable up to relabeling the components (Teicher, 1963; Yakowitz & Spragins, 1968), so with infinite data the parameters are determined. The questions are how many samples and how much computation, as functions of the dimension , the number of components and their separation. For spherical components with unit variance, separation means .
| Result | Setting | Guarantee |
|---|---|---|
| Dasgupta (1999) | separation of order | first polynomial-time algorithm, via random projection |
| Vempala & Wang (2002) | spherical; separation of order (up to logs) | polynomial time by projecting onto the top- PCA subspace, where the means survive and the noise shrinks |
| Moitra & Valiant (2010); Belkin & Sinha (2010) | no separation; fixed | polynomial in and by the method of moments; some exponential dependence on is unavoidable |
| Hsu & Kakade (2013) | spherical; linearly independent means | polynomial time by decomposing the third-moment tensor |
| Regev & Vijayaraghavan (2017) | spherical, components | separation of order is necessary and sufficient for polynomially many samples |
| Sum-of-squares methods (2018–2022) | spherical | separation for any (Hopkins & Li; Kothari, Steinhardt & Steurer; Diakonikolas, Kane & Stewart, 2018), then (Liu & Li, 2022), in polynomial time |
And EM itself? For a mixture of two symmetric, equal-weight Gaussians, EM converges to the truth from almost every starting point (Xu, Hsu & Maleki, 2016; Daskalakis, Tzamos & Zampetakis, 2017), and local convergence guarantees hold quite generally near the truth (Balakrishnan, Wainwright & Yu, 2017). With three or more components the picture breaks: even with infinitely many samples and well-separated spherical components, the likelihood can have bad local maxima, and EM from random initialization lands in one with high probability (Jin, Zhang, Balakrishnan, Wainwright & Jordan, 2016). Seeding matters for EM exactly as it does for Lloyd.
Key takeaways
- k-means is NP-hard for in high dimension and for general in the plane, exactly solvable on the line, constant-factor approximable in general, and Lloyd can need exponentially many iterations.
- k-means++ seeding satisfies : a uniform pick costs on its cluster, a pick at most , and an induction over uncovered clusters produces the harmonic number.
- EM is coordinate ascent on ; it never decreases , converges to stationary points under regularity, and its linear rate is the fraction of missing information.
- The Gaussian-mixture likelihood is unbounded, and for it has bad local maxima even with infinite data, so seeding and covariance regularization matter.
- Spherical mixtures need separation of order for polynomial sample complexity; moment methods remove separation for fixed , and sum-of-squares algorithms nearly reach the threshold efficiently.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which statement about the complexity of k-means is correct?
- It is NP-hard only when grows with
- It is solvable in polynomial time by Lloyd's algorithm
- It is NP-hard for every fixed dimension, including
- It is NP-hard already for in high dimension, yet exactly solvable on the line by dynamic programming
Show the answer
D. It is NP-hard already for in high dimension, yet exactly solvable on the line by dynamic programming
Two clusters suffice for hardness when the dimension is part of the input, and the planar problem is hard for general ; on the line, clusters are intervals of the sorted data and dynamic programming is exact. For fixed and , enumerating Voronoi partitions is polynomial, .
What exactly does the Arthur–Vassilvitskii theorem guarantee?
- The seeds alone have expected cost at most times the optimum, and Lloyd's iterations can only improve on them
- k-means++ followed by Lloyd always finds the global optimum
- The seeds are within a factor 2 of optimal with high probability
- Lloyd's algorithm converges in iterations from k-means++ seeds
Show the answer
A. The seeds alone have expected cost at most times the optimum, and Lloyd's iterations can only improve on them
It bounds the expected potential of the seeding, , and the factor is tight in the worst case. Lloyd never increases the potential, so the bound survives it; repeating the seeding and keeping the best turns the expectation into a high-probability statement.
Why can't an EM iteration decrease the log-likelihood?
- Because the log-likelihood of a mixture is concave
- Because the E-step makes the lower bound touch at , the M-step raises , and never exceeds
- Because EM takes gradient steps with a small enough learning rate
- Because the M-step maximizes directly
Show the answer
B. Because the E-step makes the lower bound touch at , the M-step raises , and never exceeds
. No concavity is needed, which is why EM can stall at local maxima or saddle points.
For a Gaussian mixture with free covariance matrices, what can be said about the maximum-likelihood estimator?
- It is unique up to relabeling the components
- It exists, and EM always finds it
- It is the k-means solution
- It does not exist: centering one component on a data point and shrinking its covariance sends the likelihood to infinity
Show the answer
D. It does not exist: centering one component on a data point and shrinking its covariance sends the likelihood to infinity
The density of that component at its point grows like , while the other components keep the remaining points' likelihood bounded away from zero. EM's value lies in reaching good local maxima; covariance floors or priors exclude the degenerate ones.
Further reading
- S. P. Lloyd, "Least squares quantization in PCM," IEEE Transactions on Information Theory 28(2), 129–137 (1982).
- D. Arthur & S. Vassilvitskii, "k-means++: the advantages of careful seeding," Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1027–1035 (2007).
- A. P. Dempster, N. M. Laird & D. B. Rubin, "Maximum likelihood from incomplete data via the EM algorithm," Journal of the Royal Statistical Society B 39(1), 1–38 (1977).
- A. Moitra & G. Valiant, "Settling the polynomial learnability of mixtures of Gaussians," IEEE Symposium on Foundations of Computer Science (FOCS) (2010).
- C. M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006), chapter 9.