Summary
This paper studies efficient implementations of the kernel k-means problems. In this problem, we are given $n$ datapoints $x_1, \ldots, x_n \in X$ and a kernel function $K : X \times X \to \mathbb{R}$ such that there exists a function $\varphi: X \rightarrow \mathcal{H}$, where $\mathcal{H}$ is a Hilbert space, satisfying $K(x, y) = \langle \varphi(x), \varphi(y)\rangle$ for all $x, y \in X$. The goal is to cluster the set of points $\varphi(x_1), \ldots, \varphi(x_n)$ using the usual $k$-means objective. One key issue here is that the outputs of $\varphi(\cdot)$ can be infinite dimensional. So, we would ideally want to work without ever needing to map the input points into the Hilbert space $\mathcal{H}$, The authors argue that, the $k$-means++ initialization and further iterations of Lloyd's can be implemented without ever needing to apply the map $\varphi(\cdot)$ on the input points. A key issue is that each iteration of the Lloyd's algorithm can take $O(n^2)$ time, since the centers in the intermediate iterations are possibly linear combinations of all the input points.
Thus, the authors propose using mini-batches in each iteration. Instead of using all the points in every iteration, sample only $b$ points in each iteration and update the centers slightly in the centers determined by the Lloyd's update rule. The learning rate parameters set as $\sqrt{b^j/b}$, where $b^j$ is the number of points sampled from the cluster $j$. This was proposed in an earlier work by Schwartzman et al. Using a dynamic programming algorithm, the authors show that this update rule can then be implemented in $O(n \cdot b)$ time. To improve the run time further, the authors propose truncation, whereby a truncated representation of centers is stored instead of storing them all as linear combinations of (possibly all the $n$ points). They show that the quality hit with truncation is not large.
Questions
1. I do not think the proof of Lemma 15 is correct. The way $\bar{\mathcal{C}}\_{{i+1}}$ is defined in line 379 uses, $\alpha_j^i = \sqrt{b^i_j / b}$ values which themselves are functions of the samples $B_i$. So how can you claim that $\bar{\mathcal{C}}_{i+1}$ is independent of $B_i$? Please clarify if I misunderstood anything. I'm willing to update my evaluation after this clarification.
2. While the experimental results do show that the algorithm generates reasonable clusters, I am unconvinced that the iteration bound for minibatch algorithms is super illuminating. Consider an algorithm which outputs the cluster centers unchanged. That algorithm will always terminate in a single iteration by this stopping criteria. So, why should someone (theoretically) care about iteration bound with respect to this stopping criteria (i.e., the value decrease is small) though I understand that the sklearn library uses this stopping criteria and since we are sure that the Lloyd's algorithm only makes progress in terms of the loss, it is a useful criteria to stop the algorithm when the progress is small.
3. In Lemma 13, where is probability coming from?
4. Definition of $\alpha^j_i$ must be highlighted.
I will update my evaluation based on the answers for these questions.