Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 E[φ]≤8(ln⁡k+2) φOPT\E[\varphi]\le8(\ln k+2)\,\varphi_{\mathrm{OPT}} 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

SettingWhat is known
k=2k=2, dimension part of the inputNP-hard (Dasgupta, 2008; Aloise, Deshpande, Hansen & Popat, 2009)
d=2d=2, kk part of the inputNP-hard (Mahajan, Nimbhorkar & Varadarajan, 2012)
d=1d=1exact by dynamic programming in O(kn2)\order{kn^2} time, and faster
kk and dd fixedexact in O(ndk+1)\order{n^{dk+1}} time by enumerating Voronoi partitions (Inaba, Katoh & Imai, 1994)
kk fixed, any dd(1+ε)(1+\varepsilon)-approximation in time linear in nn for fixed k,εk,\varepsilon (Kumar, Sabharwal & Sen, 2004)
kk and dd part of the inputconstant-factor approximations: 9+ε9+\varepsilon by local search (Kanungo et al., 2004), about 6.366.36 by primal–dual methods (Ahmadian, Norouzi-Fard, Svensson & Ward, 2017); no PTAS unless P = NP (Awasthi, Charikar, Krishnaswamy & Sinop, 2015)
Lloyd's iterations2Ω(n)2^{\Omega(n)} in the worst case, even in the plane (Vattani, 2011); polynomial smoothed complexity (Arthur, Manthey & Röglin, 2011)
The objective is easy to evaluate and hard to optimize; good practical performance comes from good seeding plus Lloyd's local improvement.
Check your understanding

Which version of the k-means problem can be solved exactly in polynomial time?

  1. k=2k=2 with the dimension dd part of the input
  2. Points on a line (d=1d=1), with kk part of the input
  3. Points in the plane (d=2d=2), with kk part of the input
  4. Any instance, by running Lloyd's algorithm to convergence
Show the answer

B. Points on a line (d=1d=1), with kk 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 O(kn2)\order{kn^2} time. In the plane with general kk, or with k=2k=2 in high dimension, the problem is NP-hard.

k-means++ and its guarantee

text
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 C

Each round costs O(nd)\order{nd} if the distances D(x)D(\mathbf x) are updated incrementally, so seeding takes O(nkd)\order{nkd}, the cost of one Lloyd iteration.

DerivationProof sketch
  1. Ea[φA({a})]=1∣A∣∑a∈A∑x∈A∥x−a∥2=2 φOPT(A)\E_{\mathbf a}\big[\varphi_A(\{\mathbf a\})\big]=\frac1{\abs A}\sum_{\mathbf a\in A}\sum_{\mathbf x\in A}\norm{\mathbf x-\mathbf a}^2=2\,\varphi_{\mathrm{OPT}}(A)

    Lemma 1 (a uniform pick). Let AA be a cluster of an optimal solution, with centroid c(A)\mathbf c(A). If a center a\mathbf a is drawn uniformly from AA, the identity ∑x∈A∥x−a∥2=∑x∈A∥x−c(A)∥2+∣A∣∥a−c(A)∥2\sum_{\mathbf x\in A}\norm{\mathbf x-\mathbf a}^2=\sum_{\mathbf x\in A}\norm{\mathbf x-\mathbf c(A)}^2+\abs A\norm{\mathbf a-\mathbf c(A)}^2, averaged over a\mathbf a, gives

  2. E[φA(C∪{a0}) ∣ a0∈A]≤4⋅1∣A∣∑a0∈A∑a∈A∥a−a0∥2=8 φOPT(A)\E\big[\varphi_A(C\cup\{\mathbf a_0\})\ \big|\ \mathbf a_0\in A\big]\le4\cdot\frac1{\abs A}\sum_{\mathbf a_0\in A}\sum_{\mathbf a\in A}\norm{\mathbf a-\mathbf a_0}^2=8\,\varphi_{\mathrm{OPT}}(A)

    Lemma 2 (a D2D^2 pick). Suppose the next center is drawn by D2D^2 sampling and lands in AA. For a,a0∈A\mathbf a,\mathbf a_0\in A, the triangle inequality and (u+v)2≤2u2+2v2(u+v)^2\le2u^2+2v^2 give D(a0)2≤2D(a)2+2∥a−a0∥2D(\mathbf a_0)^2\le2D(\mathbf a)^2+2\norm{\mathbf a-\mathbf a_0}^2. Averaging over a∈A\mathbf a\in A bounds the sampling weight of a0\mathbf a_0 by its average distance to AA, and Lemma 1's identity then gives

  3. E[φ′]≤(φ(Xc)+8φOPT(Xu))(1+Ht)+u−tu φ(Xu)\E[\varphi']\le\big(\varphi(X_c)+8\varphi_{\mathrm{OPT}}(X_u)\big)(1+H_t)+\frac{u-t}u\,\varphi(X_u)

    Induction. Call an optimal cluster covered once a center lies in it. A D2D^2 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 tt remaining draws and uu uncovered clusters, with covered points XcX_c and uncovered points XuX_u, gives, with HtH_t the harmonic number:

  4. E[φ]≤8 φOPT (1+Hk−1)≤8(ln⁡k+2) φOPT\E[\varphi]\le8\,\varphi_{\mathrm{OPT}}\,(1+H_{k-1})\le8(\ln k+2)\,\varphi_{\mathrm{OPT}}

    Conclusion. The first center covers one cluster AA at expected cost 2φOPT(A)≤8φOPT(A)2\varphi_{\mathrm{OPT}}(A)\le8\varphi_{\mathrm{OPT}}(A) (Lemma 1). Apply the induction with t=u=k−1t=u=k-1 and use Hk−1≤1+ln⁡kH_{k-1}\le1+\ln k:

Predict before you look

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 2φOPT(A)=202\varphi_{\mathrm{OPT}}(A)=20. Each center a\mathbf a costs 10+∣A∣∥a−c(A)∥210+\abs A\norm{\mathbf a-\mathbf c(A)}^2, and averaging ∣A∣∥a−c(A)∥2\abs A\norm{\mathbf a-\mathbf c(A)}^2 over a∈A\mathbf a\in A 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 O(klog⁡log⁡k)\order{k\log\log k} steps of randomized local search yields a constant-factor approximation in expectation (Lattanzi & Sohler, 2019).

EM, precisely

Take any latent-variable model p(x,z∣θ)p(\mathbf x,z\mid\theta) and data x1,…,xn\mathbf x_1,\dots,\mathbf x_n, with log-likelihood ℓ(θ)=∑ilog⁡∑zp(xi,z∣θ)\ell(\theta)=\sum_i\log\sum_zp(\mathbf x_i,z\mid\theta). The log of a sum resists direct maximization, but a family of lower bounds does not.

DerivationThe evidence lower bound and coordinate ascent
  1. log⁡p(xi∣θ)=Eqi[log⁡p(xi,z∣θ)qi(z)]⏟ELBOi(qi,θ)+DKL(qi(z) ∥ p(z∣xi,θ))\log p(\mathbf x_i\mid\theta)=\underbrace{\E_{q_i}\Big[\log\frac{p(\mathbf x_i,z\mid\theta)}{q_i(z)}\Big]}_{\text{ELBO}_i(q_i,\theta)}+\KL\big(q_i(z)\,\big\|\,p(z\mid\mathbf x_i,\theta)\big)

    For any distribution qiq_i over zz, multiply and divide by qi(z)q_i(z) inside the log and rearrange. The identity is exact:

  2. F(q,θ)=∑i=1n(Eqi[log⁡p(xi,z∣θ)]+H(qi))F(q,\theta)=\sum_{i=1}^n\Big(\E_{q_i}\big[\log p(\mathbf x_i,z\mid\theta)\big]+H(q_i)\Big)

    Summing over ii, ℓ(θ)=F(q,θ)+∑iDKL(⋅)≥F(q,θ)\ell(\theta)=F(q,\theta)+\sum_i\KL(\cdot)\ge F(q,\theta), because every KL divergence is nonnegative; here FF is the expected complete-data log-likelihood plus the entropy of qq (in statistical physics, a negative free energy):

  3. q(t)=arg max⁡qF(q,θt),θt+1=arg max⁡θ∑iEqi(t)[log⁡p(xi,z∣θ)]q^{(t)}=\argmax_qF(q,\theta_t),\qquad\theta_{t+1}=\argmax_\theta\sum_i\E_{q_i^{(t)}}\big[\log p(\mathbf x_i,z\mid\theta)\big]

    E-step: maximize FF over qq with θ\theta fixed: qi=p(z∣xi,θt)q_i=p(z\mid\mathbf x_i,\theta_t) zeroes the KL terms, so the bound touches ℓ\ell at θt\theta_t. M-step: maximize FF over θ\theta with qq fixed; the entropy does not depend on θ\theta, so this maximizes the expected complete-data log-likelihood.

  4. ℓ(θt+1) ≥ F(q(t),θt+1) ≥ F(q(t),θt) = ℓ(θt)\ell(\theta_{t+1})\ \ge\ F(q^{(t)},\theta_{t+1})\ \ge\ F(q^{(t)},\theta_t)\ =\ \ell(\theta_t)

    Chain the inequalities. EM is coordinate ascent on FF (Neal & Hinton, 1998), which also licenses partial steps: any θt+1\theta_{t+1} that merely increases FF (generalized EM), or updating one qiq_i 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 Σj→0\Sigma_j\to0 sends ℓ→+∞\ell\to+\infty. 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 θt\theta_t, how large is the gap ℓ(θt)−F(q,θt)\ell(\theta_t)-F(q,\theta_t)?

Zero. The gap is ∑iDKL(qi ∥ p(z∣xi,θt))\sum_i\KL\big(q_i\,\|\,p(z\mid\mathbf x_i,\theta_t)\big), and the E-step sets each qiq_i to exactly that posterior. (It is not the entropy of qq, which is part of FF.) The M-step then moves θ\theta, after which a gap can reopen. Variational EM, which restricts qq to a tractable family, leaves a positive gap and keeps the monotonicity guarantee only for the bound FF, not for ℓ\ell 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 dd, the number of components kk and their separation. For spherical components with unit variance, separation means min⁡i≠j∥μi−μj∥\min_{i\ne j}\norm{\boldsymbol\mu_i-\boldsymbol\mu_j}.

ResultSettingGuarantee
Dasgupta (1999)separation of order d\sqrt dfirst polynomial-time algorithm, via random projection
Vempala & Wang (2002)spherical; separation of order k1/4k^{1/4} (up to logs)polynomial time by projecting onto the top-kk PCA subspace, where the means survive and the noise shrinks
Moitra & Valiant (2010); Belkin & Sinha (2010)no separation; kk fixedpolynomial in dd and 1/ε1/\varepsilon by the method of moments; some exponential dependence on kk is unavoidable
Hsu & Kakade (2013)spherical; linearly independent meanspolynomial time by decomposing the third-moment tensor
Regev & Vijayaraghavan (2017)spherical, kk componentsseparation of order log⁡k\sqrt{\log k} is necessary and sufficient for polynomially many samples
Sum-of-squares methods (2018–2022)sphericalseparation kγk^{\gamma} for any γ>0\gamma>0 (Hopkins & Li; Kothari, Steinhardt & Steurer; Diakonikolas, Kane & Stewart, 2018), then (log⁡k)1/2+c(\log k)^{1/2+c} (Liu & Li, 2022), in polynomial time
Information-theoretic limits and efficient algorithms have nearly met for spherical mixtures; for general covariances and under adversarial corruptions, robust algorithms are much more recent.

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 k=2k=2 in high dimension and for general kk in the plane, exactly solvable on the line, constant-factor approximable in general, and Lloyd can need exponentially many iterations.
  • k-means++ D2D^2 seeding satisfies E[φ]≤8(ln⁡k+2)φOPT\E[\varphi]\le8(\ln k+2)\varphi_{\mathrm{OPT}}: a uniform pick costs 2φOPT(A)2\varphi_{\mathrm{OPT}}(A) on its cluster, a D2D^2 pick at most 8φOPT(A)8\varphi_{\mathrm{OPT}}(A), and an induction over uncovered clusters produces the harmonic number.
  • EM is coordinate ascent on F(q,θ)=ℓ(θ)−∑iDKL(qi∥p(z∣xi,θ))F(q,\theta)=\ell(\theta)-\sum_i\KL(q_i\|p(z\mid\mathbf x_i,\theta)); it never decreases ℓ\ell, converges to stationary points under regularity, and its linear rate is the fraction of missing information.
  • The Gaussian-mixture likelihood is unbounded, and for k≥3k\ge3 it has bad local maxima even with infinite data, so seeding and covariance regularization matter.
  • Spherical mixtures need separation of order log⁡k\sqrt{\log k} for polynomial sample complexity; moment methods remove separation for fixed kk, 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.

Question 1

Which statement about the complexity of k-means is correct?

  1. It is NP-hard only when kk grows with nn
  2. It is solvable in polynomial time by Lloyd's algorithm
  3. It is NP-hard for every fixed dimension, including d=1d=1
  4. It is NP-hard already for k=2k=2 in high dimension, yet exactly solvable on the line by dynamic programming
Show the answer

D. It is NP-hard already for k=2k=2 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 kk; on the line, clusters are intervals of the sorted data and dynamic programming is exact. For fixed kk and dd, enumerating Voronoi partitions is polynomial, O(ndk+1)\order{n^{dk+1}}.

Question 2

What exactly does the Arthur–Vassilvitskii theorem guarantee?

  1. The seeds alone have expected cost at most 8(ln⁡k+2)8(\ln k+2) times the optimum, and Lloyd's iterations can only improve on them
  2. k-means++ followed by Lloyd always finds the global optimum
  3. The seeds are within a factor 2 of optimal with high probability
  4. Lloyd's algorithm converges in O(log⁡k)\order{\log k} iterations from k-means++ seeds
Show the answer

A. The seeds alone have expected cost at most 8(ln⁡k+2)8(\ln k+2) times the optimum, and Lloyd's iterations can only improve on them

It bounds the expected potential of the D2D^2 seeding, E[φ]≤8(ln⁡k+2)φOPT\E[\varphi]\le8(\ln k+2)\varphi_{\mathrm{OPT}}, and the factor Θ(log⁡k)\Theta(\log k) 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.

Question 3

Why can't an EM iteration decrease the log-likelihood?

  1. Because the log-likelihood of a mixture is concave
  2. Because the E-step makes the lower bound FF touch ℓ\ell at θt\theta_t, the M-step raises FF, and FF never exceeds ℓ\ell
  3. Because EM takes gradient steps with a small enough learning rate
  4. Because the M-step maximizes ℓ\ell directly
Show the answer

B. Because the E-step makes the lower bound FF touch ℓ\ell at θt\theta_t, the M-step raises FF, and FF never exceeds ℓ\ell

ℓ(θt+1)≥F(q(t),θt+1)≥F(q(t),θt)=ℓ(θt)\ell(\theta_{t+1})\ge F(q^{(t)},\theta_{t+1})\ge F(q^{(t)},\theta_t)=\ell(\theta_t). No concavity is needed, which is why EM can stall at local maxima or saddle points.

Question 4

For a Gaussian mixture with free covariance matrices, what can be said about the maximum-likelihood estimator?

  1. It is unique up to relabeling the components
  2. It exists, and EM always finds it
  3. It is the k-means solution
  4. 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 det⁡(Σj)−1/2→∞\det(\Sigma_j)^{-1/2}\to\infty, 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.