Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The paper analyzes the convergence rate of mini-batch k-means, namely, running Lloyd's iteration with a uniform sample of points from the data set, rather than using the entire set in each iteration. It gives strong results: with a sample size nearly quadratic in the dimension, the number of steps needed is linear in the dimension (and independent of the size of the data set). This requires a stopping condition that deviates from practice, and somewhat weaker bounds are shown for the conventional stopping condition.
strength_and_weaknesses: This is an appealing result, the best in my small pile, and should definitely be accepted.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to follow. It uses standard notation.
summary_of_the_review: The convergence bound is strong, and the paper actually indicates a modification in the standard implementation that could result is superior performance in practice.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies from a theoretical perspective the convergence of mini-batch k-means. Traditionally, approaches to mini-batch k-means execute the algorithm for a fixed number of iteration, or until a convergence criterion is met (early stopping). The authors of this paper consider the latter case, i.e. mini-batch k-means algorithms without a fixed number of steps. Within this setup, the authors identify conditions under which the algorithm terminates with high probability rather than run forever. The conditions outlined in the paper relate to the batch size used, and are independent of the size of the dataset, or the initialization of the clusters. 
strength_and_weaknesses: Strength:
- well-written paper and easy to follow
- the transferability of the results to a popular library (sklearn) with minor modifications
- the paper shows that under some conditions, a progress on one batch of k-means leads to global progress, hence supporting the claim that minibatch k-means could be used when computation is a bottleneck

Weaknesses:
- the limiting bounds are nice theoretically, however, from a practical perspective, it would be nice to get a perspective of what these numbers would be. Specifically, the implementation of minibatch k-means in sklearn already has good hyperparameters to start with, and the results are usually good without any tweak. What would be for example the required batch size in order to terminate as fast as the default number of iterations?
- as pointed out by the authors, the paper does not address the quality of the solution, but rather focuses on runtime. From a practical perspective, the quality of the solution is of essence. The obtained solution does not need to amazing, but the quality of the solution should not degrade much. It would be nice to get some analysis about this aspect.
clarity,_quality,_novelty_and_reproducibility: Quality:
- the paper studies thoroughly from a theoretical perspective the convergence of minibatch k-means. It would have been nice to see some connections to the real-world usage of k-means.

Clarity:
- the paper is well-written, and the steps followed by the authors to prove their theorems are intuitive and natural.
- the authors are concise, and only included the information needed for the paper. This has led to a short paper that discusses well the story, without the need for additional jargon of text. (positive feedback)

Originality:
- The authors are aware of one other related to work that analyzes the convergence of the minibatch k-means. The other work depends on the input size, while this work does not. 
summary_of_the_review: The paper presents support theoretically the claim that local progress on minibatch k-means leads to progress on the global objective, assuming the batch size is large enough. This goes in hand with the proof that the algorithm terminates under some conditions without the need for setting a fixed number of iterations. Although the result is nice theoretically, adding some analysis about practical implications would be a big plus, e.g. what would be an estimate of the batch size for some scenarios, and empirically verifying the claims. Furthermore, discussing slightly the quality of the solution would be good in order to have a better idea about the tradeoffs.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper investigates  the convergenence rate of the mini-batch $k$-means algorithm. In the well-known k-means clustering problem, we are given a set of $n$ points and a number $k$ and the goal is to find $k$ centers (the center set) that minimizes the sum (or average as in this paper) of the squared distances of all the points to the nearest center point. The well-known Lloyd's algorithm starts with a random $k$ centers, partitions the $n$-point set into $k$ sets by assigning each point to its nearest center and then computes the centriods of the partition as the new center set and repeats (until a stopping criteria is met).   

In the mini-batch version, which is analyzed in this paper, instead of considering all the $n$ points in each step to update the centers, the algorithm independently and randomly picks $b$ (batch size) points from the point set and performs the center update. This reduces the running time of each iteration. The question that is investigated is how fast this mini-batch algorithm converges: For the given set of $n$ points and a center set $C$, let $f(C)$ be the quantity (average of the squared distances) that we would like to optimize. Then the algorithm at iteration $i$, computes the center set $C_i$. We say that the algorithm $(t,\epsilon)$-converges if $f(C_t)-f(C_{t+1}) < \epsilon$. Clearly if the diameter of the universe is bounded by $d$, then the original algorithm converges in $d/\epsilon$ steps ($f(C_{I+1} \leq f(C_i)$ at all $i$ since the centroid minimizes the sum of squared distances). The paper considers the problem: what is the batch size $b$ that is required to achieve asymptotically the same convergence rate. The paper establishes that if  $b =  \tilde\Omega(d^2/\epsilon^2)$, a variant of the mini-batch k-means algorithm  $(O(d/\epsilon),\epsilon)$ converges.  

strength_and_weaknesses: Strengths: The strength of the paper is that it investigates an important problem and establishes a nice upper bound result. The analysis is also nice and simple. 

Weakness: The research question is very interesting but is in the initial stages. The one result established is nice (and the reviewer is pleasantly surprised that it is not considered earlier) but the picture is far from complete. In particular, the lower bound landscape is completely missing. It will be nice to prove that for $O(d/\epsilon)$ convergence, the sample complexity (or the mini batch size) has to be $\Omega(d^2/\epsilon^2)$. If not why the present algorithm is not optimal? Any concert result indicating that current bounds are optimal will be nice.  More generally is there a generic trade off between the convergence rate and the batch size? Also, as the authors point out, any guarantee on the the quality of solution (does it converge to a local minima) is missing.   
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, barring  some typos. It is reproducible as mostly it consists of theoretical analysis. The analysis is moderately novel.  
summary_of_the_review: The main result is nice and publishable. The main criticism is the completeness of the research conducted. There are many missing issues (lower bounds and tradeoffs) which if addressed will make this submission into a solid paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes the mini-batch k-means algorithm, a version of which is also used in the well-known sklearn. The mini-batch k-means is modeled in the following generic way: in every iteration, sample b (for some b which they bound) uniform samples from the entire dataset X, and run the Lloyd step only on the sampled set.

The main result shows that if b = \tilde{\Omega}(d^2 \eps^{-2}), then the entire algorithm terminates in O(d / eps) iterations, w.h.p., where eps is the termination threshold. An analysis/comparison to the sklearn’s implementation is also provided.
strength_and_weaknesses: # Strength:

Mini-batch clustering is a practical k-means implementation, hence it is well motivated to analyze the performance of the algorithm. An analysis/comparison to the implementation in sklearn is also welcome.

# Weakness:

An empirical evaluation that validates the number of iterations and the accuracy is very interesting. Unfortunately, no empirical evaluation is provided at all.

Another perhaps more severe limitation is that only the number of iterations is analyzed, and the accuracy is not discussed. In particular, I don’t think sampling o(k) points (which the authors do) can lead to any finite approximation. For instance, consider 1D line, and there’re only k distinct points, but they each have multiplicities of e.g., 100. Then, a uniform sample of o(k) points cannot discover all of these k distinct points, and eventually the output center set must also contain less than k distinct points. However, the optimal solution value is 0 which is achieved by simply putting one center point at each distinct point, while what you obtain must have a cost > 0, hence the multiplicative error is unbounded.

clarity,_quality,_novelty_and_reproducibility: # Clarity:

Some places are not written in a rigorous way. Detailed comments:

1. Page 3, the meaning of the notation \Delta(x, C) is not defined; in fact, it is defined that \Delta(S, x) being the sum of \Detal(y, x) for y \in S, but this \Delta(x, C) actually means a different thing. Please consider to improve the notation.
2. In Theorem 2.2, it seems \delta is not quantified. In the summation inside \Pr, the index is I but you used Y_k.
3. I find the definition of learning rate in Sec 1 quite confusing. Also, I don’t find a place that this learning rate is formally defined.
4. It is suggested to add formal theorem statements for your main results.

Originality:

This paper studies a widely used clustering method that is currently not fully understood, hence is timely. However, the techniques are mostly based on standard concentration bounds, which are not particularly novel. At first glance, the main result seemed to be surprising since the number of samples as well as the number of iterations are independent of both k and n which are the fundamental parameters in clustering, but as mentioned in the “Weakness”, this bound is of a cost of accuracy.

summary_of_the_review: Even though the techniques are somewhat standard, the obtained bounds look nice. However, I'd still like to reject the paper, since I believe the paper misses an important aspect, which is the accuracy of the algorithm (as discussed in "Weakness"), and that I don't see the empirical evaluation that justifies the accuracy.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper shows that mini-batch k-means terminates as long as the batch sizes are sufficiently large, with high probability. The result is neat and makes progress on an important algorithm that is also used in practice.
justification_for_why_not_higher_score: Good paper, could be pushed up a bit. 
justification_for_why_not_lower_score: Clearly above acceptance threshold.
Decision: Accept: poster