Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lloyd's algorithm converges in finitely many steps to a fixed point

Proved
LloydConvergence.lloyd_converges

by pitimespi · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

clusteringk-means

Lloyd's algorithm for kkk-means clustering converges in finitely many steps to a fixed point.

Let SSS be a finite set of points in Rn\mathbb{R}^nRn and k≥1k \geq 1k≥1. An assignment f:S→{1,…,k}f : S \to \{1, \dots, k\}f:S→{1,…,k} has centers μi\mu_iμi​, the mean of the points assigned to cluster iii (with μi=0\mu_i = 0μi​=0 if cluster iii 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 T≤k∣S∣T \leq k^{|S|}T≤k∣S∣ such that the TTT-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 kkk-means objective strictly decreases at every step that changes the assignment, and there are only k∣S∣k^{|S|}k∣S∣ 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 kkk-means objective.

Formalization Note The iteration is the one defined in the platform definition LloydConvergence (strict-move step, empty-cluster centroid 000); the partition in the statement is LloydConvergence.part and the iterate is LloydConvergence.orbit.

Preamble
import Mathlib
import Definitions.Def_UnderstandingML_Clustering
import Definitions.Def_LloydConvergence
Formal statement
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
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, Section 22.2, pp. 312-313 (k-means algorithm and Lemma 22.1); Lloyd, Least squares quantization in PCM, IEEE Trans. Inform. Theory 28 (1982)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me