3
$\begingroup$

The $k$-means++ algorithm is composed of two parts:

  1. Initialization part: the initial $k$ centers are chosen based on $D^2$ sampling.
  2. Expectation maximization part: the standard $k$-means algorithm (or Lloyd's algorithm) is run with these initialized centers.

In the k-means++ paper, the authors show that the $k$-means algorithm can not perform better than $O(\log k)$-approximation in expectation (see Section 4 of the same paper). However, they only give this lower bound for the initialization part without considering the expectation-maximization part. Does that make their lower bound argument incorrect/incomplete? If so, the $k$-means++ algorithm might give better than $O(\log k)$-approximation and the proven lower bound is misleading.

Improve this question
$\endgroup$
3
  • $\begingroup$ The abstract and the introduction might seem to indicate that the authors analyze the full algorithm. But in the later section the authors are very careful to give precise statements, and explain that the upper and lower bound they give applies just to the first part of the algorithm. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    May 17, 2021 at 7:59
  • $\begingroup$ @KristofferArnsfeltHansen You are right. And, I found the first paragraph of section 4 to be straightforward conflicting: "In this section, we show that the D2 seeding used by k-means++ is no better than $\Omega(\log k)$-competitive in expectation, thereby proving Theorem 3.1 is tight within a constant factor." The conflict is that Theorem 3.1 states bound for "k-means++" algorithm as whole. $\endgroup$
    – Inuyasha Yagami
    May 17, 2021 at 13:09
  • 1
    $\begingroup$ I think your understanding is correct and the authors are being a bit sloppy with the distinction between k-means++ and $D^2$ seeding. Even Theorem 4.1 is correctly stated to be about $D^2$ seeding but the proof says to consider a clustering obtained by k-means++. $\endgroup$
    – Tassle
    May 17, 2021 at 19:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.