Lloyd's algorithm converges in finitely many steps to a fixed point
ProvedLloydConvergence.lloyd_convergesLloyd's algorithm for -means clustering converges in finitely many steps to a fixed point.
Let be a finite set of points in and . An assignment has centers , the mean of the points assigned to cluster (with if cluster is empty). One Lloyd step reassigns each point to its nearest center — but only when that center is strictly nearer than its current one (strict-move tie-breaking; on ties the point stays put). Then there is a number of steps such that the -fold iterate of the step is a fixed point: every point is already at a nearest centroid, and every centroid is the mean of its cluster.
In other words, the iteration cannot cycle: the -means objective strictly decreases at every step that changes the assignment, and there are only assignments. The fixed point is a local minimum in the sense of Lloyd's algorithm — a stable assignment with optimal centers — not a global optimum of the -means objective.
Formalization Note The iteration is the one defined in the platform definition LloydConvergence (strict-move step, empty-cluster centroid ); the partition in the statement is LloydConvergence.part and the iterate is LloydConvergence.orbit.
import Mathlib import Definitions.Def_UnderstandingML_Clustering import Definitions.Def_LloydConvergence
theorem LloydConvergence.lloyd_converges {n k : ℕ} (S : Finset (UnderstandingML.Vec n)) [NeZero k]
(f₀ : S → Fin k) :
∃ T : ℕ, T ≤ k ^ S.card ∧
(∀ x : S, ∀ j : Fin k,
‖(x : UnderstandingML.Vec n)
- UnderstandingML.centroid (LloydConvergence.part S (LloydConvergence.orbit S f₀ T) ((LloydConvergence.orbit S f₀ T) x))‖
≤ ‖(x : UnderstandingML.Vec n)
- UnderstandingML.centroid (LloydConvergence.part S (LloydConvergence.orbit S f₀ T) j)‖) := by sorry