<p>The <span class="math-container">$k$</span>-means++ algorithm is composed of two parts:</p>
<ol>
<li>Initialization part: the initial <span class="math-container">$k$</span> centers are chosen based on <span class="math-container">$D^2$</span> sampling.</li>
<li>Expectation maximization part: the standard <span class="math-container">$k$</span>-means algorithm (or Lloyd's algorithm) is run with these initialized centers.</li>
</ol>
<p>In the <a href="https://theory.stanford.edu/%7Esergei/papers/kMeansPP-soda.pdf" rel="nofollow noreferrer">k-means++</a> paper, the authors show that the <span class="math-container">$k$</span>-means algorithm can not perform better than <span class="math-container">$O(\log k)$</span>-approximation in expectation (see <a href="https://theory.stanford.edu/%7Esergei/papers/kMeansPP-soda.pdf#page=5" rel="nofollow noreferrer">Section 4</a> 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 <span class="math-container">$k$</span>-means++ algorithm might give better than <span class="math-container">$O(\log k)$</span>-approximation and the proven lower bound is misleading.</p>

CC BY-SA 4.0
2021-05-17T07:59:23.493Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-05-17T13:09:40.780Z
@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.
Inuyasha Yagami
CC BY-SA 4.0
2021-05-17T19:55:34.487Z
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++.
Tassle
<approximation-algorithms><approximation-hardness><clustering>
Incorrect Lower Bound of k-Means++ Algorithm
Inuyasha Yagami
# Incorrect Lower Bound of k-Means++ Algorithm

(Asked by: username_0 on 2021-05-16)

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++](https://theory.stanford.edu/%7Esergei/papers/kMeansPP-soda.pdf) paper, the authors show that the $k$-means algorithm can not perform better than $O(\log k)$-approximation in expectation (see [Section 4](https://theory.stanford.edu/%7Esergei/papers/kMeansPP-soda.pdf#page=5) 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.

**Tags:** approximation-algorithms, approximation-hardness, clustering

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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++.  

---

## 0 answers

