PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants

Yu Lu, Harrison H. Zhou

arXiv:1612.02099v1math.STcs.LGstat.MLstat.TH

TL;DR

Although Lloyd’s algorithm is widely used, its statistical and computational guarantees have received limited theoretical study. This paper analyzes it for sub-Gaussian mixtures and develops variants for community detection and crowdsourcing, proving convergence and error-rate guarantees and reporting competitive experiments.

  • Problem

    Despite Lloyd’s algorithm’s widespread use, its statistical and computational guarantees have received little theoretical analysis, including how initialization, separation, convergence, and label-error rates affect performance.

    Source: §1 · p. 2

  • Method

    The paper analyzes Lloyd’s iterative label-and-center updates for sub-Gaussian mixtures and develops related variants for community detection and crowdsourcing.

    Source: §1.1 · pp. 3–4

  • Results

    Lloyd’s algorithm reaches minimax-optimal clustering error under suitable initialization, while the community-detection and crowdsourcing variants improve prior signal-to-noise conditions and perform competitively in experiments.

    Source: §1.1 · pp. 3–4

  • Takeaways & Limitations

    The analysis extends beyond one-step updates and establishes linear convergence to statistical optimal error rates for Lloyd’s algorithm and its two variants.

    Source: §1.1 · pp. 3–4

    The initialization condition is sharp in the stated sense: Lloyd’s algorithm may not converge at G0 = 1/(2λ) or Λ = 1/2.

    Source: §3.2 · p. 10

Abstract

from arXiv · show

Clustering is a fundamental problem in statistics and machine learning. Lloyd's algorithm, proposed in 1957, is still possibly the most widely used clustering algorithm in practice due to its simplicity and empirical performance. However, there has been little theoretical investigation on the statistical and computational guarantees of Lloyd's algorithm. This paper is an attempt to bridge this gap between practice and theory. We investigate the performance of Lloyd's algorithm on clustering sub-Gaussian mixtures. Under an appropriate initialization for labels or centers, we show that Lloyd's algorithm converges to an exponentially small clustering error after an order of $\log n$ iterations, where $n$ is the sample size. The error rate is shown to be minimax optimal. For the two-mixture case, we only require the initializer to be slightly better than random guess. In addition, we extend the Lloyd's algorithm and its analysis to community detection and crowdsourcing, two problems that have received a lot of attention recently in statistics and machine learning. Two variants of Lloyd's algorithm are proposed respectively for community detection and crowdsourcing. On the theoretical side, we provide statistical and computational guarantees of the two algorithms, and the results improve upon some previous signal-to-noise ratio conditions in literature for both problems. Experimental results on simulated and real data sets demonstrate competitive performance of our algorithms to the state-of-the-art methods.

1 Introduction

The paper addresses the gap between Lloyd’s practical popularity and limited theoretical understanding, establishing guarantees for clustering and two related applications. Its contributions include convergence and error-rate results, extensions to community detection and crowdsourcing, and a comparison with prior Gaussian-mixture work.

1.1 Our contributions

  • Under suitable initialization, Lloyd’s algorithm achieves exponentially small, minimax-optimal clustering error for sub-Gaussian mixtures, with exact recovery when the signal-to-noise level exceeds 4 log n.For symmetric two-component Gaussian mixtures, the algorithm reaches the minimax exponential rate after ⌈3 log n⌉ iterations.Source: §1.1 · p. 3
  • For general k and non-spherical sub-Gaussian mixtures, the results extend under initialization and signal-to-noise conditions; for balanced clusters, the separation condition improves by a polylog n factor over the best-known result.The stated condition also covers high-dimensional cases where d may exceed n.Source: §1.1 · p. 3
  • With a label initializer having constant clustering error, Lloyd’s iterations converge linearly, while the analysis requires less than the consistent first-stage estimators assumed in earlier two-stage work [22].The paper introduces a technique for analyzing random indicator functions to obtain this guarantee.Source: §1.1 · pp. 3–4
  • For two-component mixtures, the initialization condition is only slightly stronger than random guessing, and larger signal-to-noise ratios yield faster linear convergence.A random initialization scheme is also shown to work with high probability when Δ ≳ σd^1/4.Source: §1.1 · p. 4
  • The community-detection and crowdsourcing variants improve prior signal-to-noise conditions, and simulated and real-data experiments show competitive performance against state-of-the-art methods.The paper describes the crowdsourcing updates as related to EM for the Dawid–Skene model.Source: §1.1 · p. 4

1.2 Related work on Gaussian mixture models

  • Prior Gaussian-mixture work largely focused on estimating centers, leaving label-estimation convergence rates less clear; for k ≥ 3, counterexamples rule out general global convergence of EM with uniformly data-initialized centers.Earlier Lloyd analyses emphasized exact recovery under strong separation, while its clustering error rate remained unclear.Source: §1 · p. 2, §1.2 · pp. 4–5

2 Model and Lloyd’s algorithm

The paper studies clustering under mixtures of sub-Gaussian distributions and presents Lloyd’s algorithm as an iterative method for estimating labels and centers. It also describes spectral clustering as an initializer.

2.1 Mixture of sub-Gaussians

  • The model consists of independent observations from k sub-Gaussian distributions with unknown centers and underlying labels; the goal is to recover labels up to permutation, not to estimate centers.The symmetric two-component spherical Gaussian mixture is a special case.Source: §2.1 · pp. 5–6

2.2 Lloyd’s Algorithm

  • Lloyd’s algorithm alternates assigning each observation to its nearest center with recomputing each center as the mean of its assigned observations.The paper motivates these updates through the spherical-Gaussian maximum-likelihood objective.Source: §2.2 · p. 6
  • Because Lloyd’s algorithm can reach a local minimum, the paper uses spectral initialization: project data onto leading singular vectors, then run an approximate k-means procedure on the projected data.The described approximate k-means algorithm runs in polynomial time in n, k, and d.Source: §2.2 · p. 7

3 Clustering sub-Gaussian mixtures

For two-component and general k sub-Gaussian mixtures, appropriately initialized Lloyd iterations reach exponentially small clustering error. A matching minimax lower bound establishes optimality of the label-estimation rate for Gaussian mixtures.

3.1 Two mixtures

  • The cited passage says equation (12) implies As < 1/n, and therefore Theorem 3.1 guarantees zero clustering error after ⌈3 log n⌉ Lloyd iterations with high probability.The convergence has three stages: escape from a neighborhood around 1/2, linear convergence, and convergence to optimal statistical precision once the mis-clustering rate is sufficiently small.Source: §3.1 · p. 8
  • For two mixtures, the initializer need only be slightly better than random guessing, and stronger signal-to-noise permits a weaker initialization condition.The initialization factor is determined by the signal-to-noise ratio.Source: §3.1 · pp. 8–9

3.2 k mixtures

  • After an initializer satisfies condition (14), the k-mixture algorithm reaches exponentially small mis-clustering error after ⌈4 log n⌉ iterations.The initialization condition is slightly stronger than in the two-mixture case because of asymmetry.Source: §3.2 · p. 10
  • Lloyd’s algorithm requires neither knowledge nor estimation of the covariance structure and applies to sub-Gaussian mixtures satisfying condition (2).The paper describes this as an advantage over likelihood-based methods such as EM and methods of moments.Source: §3.2 · p. 10
  • For similarly sized clusters, sufficient separation simplifies to ∆ ≳ kσ when n ≥ kd, and to ∆ ≳ σ for finite k.The results provide an explicit exponentially small label-error rate and hold across the range of d, whereas prior results cited here require n ≫ kd.Source: §3.2 · pp. 10–11

3.3 Minimax lower bound

  • When ∆/σ is constant-order, the worst-case mis-clustering rate is bounded below by a constant, so consistent label estimation requires ∆/σ → ∞.Strong consistency requires ∆/σ ≳ √log n; together with Corollary 3.1, the lower bound establishes the minimax rate for Gaussian-mixture labels.Source: §3.3 · p. 11

4 Applications

The paper extends its Lloyd-style analysis to community detection and crowdsourcing. It presents variants for both tasks with theoretical guarantees.

4.1 Community Detection

  • For sparse community detection, CommuLloyd trims the adjacency matrix, initializes labels spectrally, then updates nodes using estimated community connection probabilities.The estimated probabilities are expected to be close to a/n or b/n, depending on community membership.Source: §4.1 · p. 12
  • CommuLloyd shows linear convergence from first-stage group-wise mis-clustering G0 ≤ 1/4; this can be relaxed to G0 ≤ 1/2 − a log(βk)/(βk(a−b)), with exponentially small error under (a−b)^2 ≳ aβ²k³.Source: §4.1 · p. 13
  • Compared with the method in [22], CommuLloyd is computationally more efficient, relaxes assumptions, and improves the best-known signal-to-noise condition by a log k factor.The method in [22] requires n initializers and n network SVDs; the paper says CommuLloyd matches the minimax rate in the stated regime.Source: §4.1 · p. 13

4.2 Crowdsourcing

  • For crowdsourcing, the variant alternates between estimating worker accuracies and item labels; its updates correspond to Lloyd iterations and are related to EM.The label update uses least squares to approximate the multinomial log-likelihood and hard labeling rather than EM's soft-labeling step.Source: §4.2 · p. 14
  • Under the Dawid-Skene model, the paper gives an exponentially small label-error guarantee and removes a prior positivity assumption on worker confusion probabilities.It also states that the guarantee needs no eigenvalue condition on the confusion matrix; majority voting is the initializer.Source: §4.2 · pp. 14–16

5 Numerical Analysis

The experiments test Lloyd’s algorithm and its community-detection and crowdsourcing variants on simulations and real data. Results show competitive performance, with outcomes depending on the task and setting.

5.1.1 Simulation

  • Across Figure 1 simulations, higher SNR speeds Lloyd’s convergence, while larger k slows it and can prevent reaching the optimal mis-clustering rate.The simulations also show an initial linear-convergence phase followed by slower convergence.Source: Figure 1 · p. 16, §5.1.1 · pp. 16–17

5.1.2 Gene Microarray Data

  • RandLloyd is comparable to SpecLloyd and IF-HCT-PCA on six gene datasets, and has the best error rates on Leukemia and Lymphoma.The authors report that Lloyd’s algorithm also works in high dimensions when the signal-to-noise ratio is strong enough.Source: §5.1.2 · pp. 17–18, Table 1 · p. 18

5.2.1 Simulation

  • CommuLloyd significantly outperforms spectral clustering and one-step MLE refinement across three simulated settings, and beats multiple MLE refinements in two of them.In the unequal-community setting, CommuLloyd and MLE have similar performance and both converge linearly.Source: §5.2.1 · p. 18, Figure 2 · p. 19

5.2.2 Political Blog Data

  • CommuLloyd reaches 56/1222 mis-labeled blogs after three iterations, slightly improving on SCORE’s 58/1222.It starts from spectral clustering at 437/1222 errors and then fluctuates between 55 and 56 mis-labeled nodes.Source: §5.2.2 · p. 19, Table 3 · p. 20

5.3.1 Simulation

  • CrowdLloyd consistently outperforms Opt D&S at its first iteration and majority voting across simulated missing-data levels.Its performance is nearly identical to MV+EM and ten-iteration Opt D&S; the authors attribute its slight disadvantage to not using likelihood to update confusion matrices.Source: §5.3.1 · p. 20, Table 4 · p. 21

5.3.2 Real Data

  • CrowdLloyd slightly outperforms the other three methods on four of five real crowdsourcing datasets.The authors suggest its least-squares update may be more robust than likelihood-based EM for general sub-Gaussian distributions.Source: Table 5 · p. 21, §5.3.2 · p. 21

6 Discussion

The discussion considers random initialization and center estimation. It reports a random-start guarantee for symmetric two-component mixtures and linear convergence for estimating centers.

6.1 Random Initialization

  • With 3 log(1/δ) independent random initializers, one run correctly classifies all data with probability greater than 1 − δ.This result concerns the symmetric two-mixture model and data-independent random label initialization.Source: §6.1 · pp. 21–22
  • The paper improves the condition reported by Klusowski and Brinda [36] from ∥θ∗∥≳σ√(d log d) to ∥θ∗∥≳σ(d log d)^(1/4).The stated comparison uses δ = 1/d.Source: §6.1 · p. 22

6.2 Convergence of the centers

  • Lloyd’s algorithm has a linear convergence rate for estimating mixture centers.The paper presents this as a byproduct of its label-clustering result.Source: §6.2 · p. 22

7 Proofs

The proofs establish Lloyd’s error bounds by controlling label and center estimation errors on high-probability events. They use iterative bounds to show label error decreases and derive a sharper error exponent when the signal-to-noise ratio grows.

7 Proofs

  • The proof section develops the preliminary concentration and error bounds needed for the two parts of Theorem 3.1.It is devoted to proving Theorem 3.1; proofs of other theorems are collected in the appendix.Source: §7 · p. 22, §7.1 · p. 24

7.1 Preliminaries

  • The proof conditions on a high-probability event and decomposes center-estimation error into label-estimation error and stochastic noise.It uses concentration lemmas for the noise vectors and analyzes center and label errors deterministically on that event.Source: §7.1 · p. 23

7.2 Proof of (11) in Theorem 3.1

  • For Theorem 3.1(11), the proof bounds two contributions to the next label error and uses induction to keep the error controlled.The bounds use concentration inequalities and the signal-to-noise condition r ≥ 32.Source: §7.2 · pp. 24–26

7.3 Proof of (12) in Theorem 3.1

  • For Theorem 3.1(12), the proof derives the mis-clustering bound and notes that the error exponent improves as r tends to infinity.The proof also sets s = ⌈3 log n⌉ when applying Markov’s inequality.Source: §7.3 · pp. 26–27

A Proof of sub-Gaussian mixtures

The appendix proves the sub-Gaussian mixture results using concentration bounds and relationships between center and label errors. It also establishes a lower bound using a restricted parameter space and a likelihood-ratio test.

A.1 Preliminaries

  • The preliminary lemmas provide concentration bounds for sub-Gaussian noise vectors used in the subsequent proofs.The proof conditions on an event whose complement has probability at most 3n^-3 + ν.Source: §A.1 · pp. 27–28, §A.2 · p. 28

A.2 Two Key Lemmas

  • The cited bound establishes that, if Λ_s ≤ 1/2 and r ≥ 20ε^-2, the right-hand side of (60) is less than 1/2 whenever αn ≥ 32k^2 log n.Source: §A.2 · p. 31

A.3 Proof of Theorem 3.2

  • Theorem 3.2’s proof bounds expected label error and then obtains a high-probability bound using Markov’s inequality.The argument handles the inner product with the noise vectors using concentration bounds.Source: §A.3 · pp. 32–34

A.4 Proof of Lower Bounds

  • The lower-bound proof restricts the label parameter space to control label permutations and uses a likelihood-ratio test.The proof states that any non-identity permutation in the restricted space gives a larger mis-clustering rate.Source: §A.4 · pp. 34–35

A.5 A counterexample

The counterexample shows that a particular mixed initialization can leave Lloyd’s algorithm stationary rather than reaching the true centers. The authors characterize it as a theoretical worst case that may not occur in practice.

A.5 A counterexample

  • In the noiseless example with six equal-size clusters, the initializer mixes each cluster with its paired cluster using a specified fraction of points.The paired centers are separated by λ∆, while the first three centers are separated by ∆.Source: §A.5 · p. 36
  • The mixed initialization places estimated centers midway between true centers, creating ties in the next label update.The caption identifies the figure as a counterexample to convergence when G0 = 1.Source: §A.5 · p. 36, Figure 3 · p. 36
  • The resulting estimated centers can be stationary without matching the true centers, though the authors say this worst case may not occur in practice.The authors present the example to show that the initialization condition is almost necessary.Source: §A.5 · p. 36

A.6 Proofs of Random Initialization

The appendix analyzes when data-independent initialization can satisfy the condition needed for the two-mixture result. For random label assignments, it describes repeated independent initializations and bounds the first update using independence and concentration.

A.6 Proofs of Random Initialization

  • Under the stated condition, the conclusion of Theorem 3.1 continues to hold for a data-independent initializer.Lemma A.8 gives this conclusion with probability greater than 1 − δ.Source: §A.6 · p. 36
  • For random label assignments, the proof describes boosting the chance of obtaining an initializer in the basin by drawing multiple independent initializers.It states that the single-draw probability is greater than 0.3 and proposes 3 log(1/δ) draws.Source: §A.6 · pp. 36–37
  • The first-iteration analysis uses the data independence of the initial labels from the noise vectors to apply concentration inequalities.The proof uses Chernoff’s bound and Hoeffding’s inequality.Source: §A.6 · p. 37

B.1 Proof of Theorem 4.1

The proof controls group-wise misclassification through induction, then uses that bound to establish geometric decay of the overall mis-clustering rate.

B.1 Proof of Theorem 4.1

  • The proof separates control of group-wise error from geometric decay of the overall mis-clustering rate.The two steps are stated for the group-wise rate G_s and mis-clustering rate A_s.Source: §B.1 · p. 38
  • With probability greater than 1−n^-1, induction gives G_s ≤1/3 through 3 log n iterations when n≥3k^2 log n.Source: §B.1 · p. 40
  • Once G_s ≤1/3, the proof averages inequality (74) over observations and applies Lemma B.1 with ε=1/3 to bound A_s.Source: §B.1 · p. 40

C.1 Proof of Theorem 4.2

The proof uses a Markov-bound argument for Theorem 4.2, establishes a sub-Gaussian parameter bound for Corollary 4.2, and frames the technical lemmas through spherical and general sub-Gaussian cases.

C.1 Proof of Theorem 4.2

  • For Theorem 4.2, a Markov-bound argument with t=1/(4k) completes the stated bound for multinomial observations.Source: §C.1 · p. 42

C.2 Proof of Corollary 4.2

  • For Corollary 4.2, the proof bounds the sub-Gaussian parameter of w_i by 2.Source: §C.2 · p. 43

D Proofs of Technical Lemmas

D.1 Proofs for spherical Gaussians

The spherical-Gaussian proofs use concentration and covering arguments; the sub-Gaussian proofs adapt related bounds using independence and union bounds.

D.1 Proofs for spherical Gaussians

  • The spherical-Gaussian net argument uses an ε-net of the unit ball with size at most (1+2/ε)^d, then sets ε=0.05 and t=2(n+9d).Source: §D.1 · p. 44
  • For spherical Gaussians, independence of w_i and W_Gi supports a Chernoff-bound step, combined with earlier inequalities to complete the probability bound.Source: §D.1 · p. 45

D.2 Proofs of sub-Gaussians

  • For sub-Gaussian vectors, the proof uses independence and parameter-1 sub-Gaussian variables, then follows the Lemma 7.3 argument with t=2d+n.Source: §D.2 · p. 46
  • The sub-Gaussian analogue uses independence of w_i and W_S with a bound for λ^2≤1/|S|, then follows the Lemma 7.4 argument.Source: §D.2 · p. 46

Related papers

Loading 1612.02099v1…