Convergence Properties

We've established that Lloyd's algorithm decreases the WCSS at each iteration. But does it actually terminate? How quickly? Are there cases where it gets stuck or runs forever?

These questions matter for both theory and practice:

• Theoretically: We need to prove the algorithm is well-defined and terminates
• Practically: We need to know how many iterations to budget and when to stop

In this page, we'll rigorously analyze convergence—proving that Lloyd's algorithm always terminates, characterizing its convergence rate, and exploring edge cases where behavior becomes pathological.

Lloyd's algorithm is guaranteed to converge in finite time. The proof relies on two key observations:

Observation 1: WCSS is monotonically non-increasing

Let $J^{(t)}$ denote the WCSS at iteration $t$. We showed earlier that:

• The assignment step can only decrease (or maintain) $J$
• The update step can only decrease (or maintain) $J$

Therefore: $J^{(t+1)} \leq J^{(t)}$ for all $t$.

Observation 2: There are finitely many possible configurations

A configuration is a pair $({C_j}, {\boldsymbol{\mu}_j})$ of cluster assignments and centroids. Since:

• There are at most $k^n$ ways to assign $n$ points to $k$ clusters
• Each centroid is uniquely determined by its cluster (as the mean)

The number of distinct configurations is at most $k^n$ (finite).

Important Caveat: The $k^n$ Bound is Exponential

While convergence is guaranteed, the $k^n$ worst-case bound is exponentially large. For $n = 100$ and $k = 2$, this is $2^{100} \approx 10^{30}$ iterations!

Fortunately, this worst case is rarely (if ever) achieved in practice. Typical convergence is much faster, as we'll see in the next section.

What Does Convergence Mean?

Lloyd's algorithm converges to a fixed point—a configuration where:

• The assignment step doesn't change any assignments
• The update step doesn't move any centroids

At a fixed point, we've reached a local minimum of the WCSS. This may or may not be the global minimum.

The $k^n$ worst-case bound tells us convergence is guaranteed but says nothing about typical behavior. In practice, Lloyd's algorithm converges remarkably fast.

Empirical Observations:

Across decades of empirical studies:

• Most runs converge within 10-100 iterations
• Convergence is typically geometric (constant factor improvement per iteration)
• The number of iterations is largely independent of $n$ for typical data

Smoothed Analysis:

Spielmann and Teng's smoothed analysis explains why Lloyd's algorithm behaves well in practice:

Theorem (Smoothed Polynomial Convergence): If input data is perturbed by small random Gaussian noise (standard deviation $\sigma$), Lloyd's algorithm converges in polynomial expected time: $O\left(\frac{n^{34}k^{34}d^8}{\sigma^6}\right)$ iterations.

Convergence Characterization:

Typical convergence follows a pattern:

1. Initial phase (1-5 iterations): Large WCSS decreases as major cluster structure is discovered
2. Refinement phase (5-20 iterations): Moderate decreases as boundaries are adjusted
3. Stabilization phase (20+ iterations): Tiny decreases; reassignments become rare

This suggests an adaptive stopping criterion based on relative improvement:

if (J_old - J_new) / J_old < tolerance:
    converged = True

While practical convergence is fast, adversarial inputs exist that force Lloyd's algorithm to take exponentially many iterations. Understanding these constructions illuminates the algorithm's behavior.

Arthur & Vassilvitskii Construction (2006):

For any $n$ and $k = 2$, there exist datasets and initializations where Lloyd's algorithm requires $2^{\Omega(n)}$ iterations.

The Construction:

1. Place $n$ points along a line at carefully chosen positions
2. Initialize with specific centroids that create a "cascade" effect
3. Each iteration moves centroids by a tiny amount
4. The cascade must propagate through all $n$ points

The key is that each point's assignment depends on a delicate balance, and changing one assignment triggers a chain reaction that takes exponential time to stabilize.

Other Pathological Cases:

1. Empty Clusters:

If initialization places centroids such that one receives no points:

• The centroid becomes undefined (mean of empty set)
• Common fixes: reinitialize randomly, or keep old centroid

2. Ties:

When a point is equidistant from multiple centroids:

• Assignment is ambiguous (implementation-dependent)
• Can cause non-deterministic behavior
• Usually handled by arbitrary tie-breaking (e.g., lowest index wins)

3. Oscillation:

In rare edge cases, assignments can oscillate:

• Point $x$ alternates between clusters $A$ and $B$
• Each assignment changes the centroids just enough to flip $x$ back
• Handled by tracking previous states and detecting cycles

Modern implementations handle all these cases gracefully.

In practice, we don't wait for exact convergence—we stop when progress becomes negligible. Several stopping criteria are used:

Recommended Practice:

Use a combination of criteria:

for iteration in range(max_iters):
    # ... assignment and update steps ...
    
    # Criterion 1: No assignments changed
    if np.all(labels == old_labels):
        break
    
    # Criterion 2: Centroids barely moved
    centroid_shift = np.sum((centroids - old_centroids) ** 2)
    if centroid_shift < tol:
        break
    
    # Criterion 3: Objective stopped improving
    if (old_inertia - inertia) / old_inertia < rtol:
        break

This ensures termination regardless of edge cases while stopping early when effectively converged.

Monitoring convergence reveals important information about the clustering and potential issues.

Healthy Convergence Signs:

1. Monotonically decreasing inertia: WCSS should never increase
2. Geometric decrease initially: Large improvements in first few iterations
3. Diminishing returns: Later iterations provide smaller improvements
4. Stable assignments: Number of reassignments decreases over time

Warning Signs:

Elbow Plot for Convergence:

Plotting inertia vs. iteration number should show an "elbow":

Inertia
   |
   | 
   |  
   |   \____________________
   |_________________________ Iteration

The flat region indicates convergence. If the curve keeps decreasing steeply, you may need more iterations.

Comparing Restarts:

When running multiple restarts, compare:

• Final inertia values (lower is better)
• Convergence speed (faster may indicate better initialization)
• Cluster sizes (roughly balanced is often desirable)

If restarts produce very different inertias, the objective landscape has multiple distinct local minima—consider increasing n_init.

Several techniques can speed up convergence without changing the final result.

1. Early Termination of Assignment Step:

In the assignment step, we can skip recomputing distances for points that definitely won't change clusters. Using triangle inequality:

If $|\mathbf{x} - \boldsymbol{\mu}{\text{old}}| \leq \frac{1}{2}\min{j eq \text{old}} |\boldsymbol{\mu}_{\text{old}} - \boldsymbol{\mu}_j|$

then $\mathbf{x}$ cannot change clusters (it's too close to its current centroid).

2. Elkan's Algorithm:

Maintains bounds on distances to avoid redundant computation:

• Upper bound: $u(x)$ on distance to assigned centroid
• Lower bounds: $l(x, j)$ on distance to each other centroid

Proven to reduce distance computations by 50-90% on many datasets.

3. Mini-Batch K-Means:

Instead of using all $n$ points per iteration, sample a small batch:

for iteration in range(max_iters):
    batch = random_sample(X, batch_size=1000)
    
    # Assignment step on batch only
    batch_labels = assign_to_nearest(batch, centroids)
    
    # Update centroids using batch (with learning rate)
    for j in range(k):
        batch_cluster = batch[batch_labels == j]
        if len(batch_cluster) > 0:
            update = batch_cluster.mean(axis=0) - centroids[j]
            centroids[j] += learning_rate * update

Trade-offs:

• Much faster per iteration: O(batch_size × k × d)
• More iterations needed to converge
• May converge to slightly worse solution
• Excellent for very large datasets (n > 100,000)

What's Next:

We've now covered the algorithm (Lloyd's), objective (WCSS), initialization (k-means++), and convergence. In the final page of this module, we'll examine the limitations of k-means—understanding when it works well, when it fails, and what alternatives exist.