Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a novel method for center-based clustering of i.i.d. points in $\mathbb{R}^d$ under a Bregman divergence. The key idea of the framework is to employ a median of means estimator defined over the objective function, i.e., the data set is partitioned into sets of equal size and the median of the objective values of the elements of the partition is minimized to obtain the clustering. The aim of the paper is to develop a clustering scheme that is more robust against outliers than common $k$-means and its variants/extensions and admits theoretical guarantees. To compute the clustering the well-known Adagrad gradient descent algorithm is used.

The main contribution of the paper is a rigorous theoretical analysis, proving consistency and convergence, i.e., the minimizer of the sample approaches the minimizer of the population as the sample size tends to infinity, at a bounded rate of order $(\sqrt{n})^{-1}$. The efficacy of the novel clustering method is experimentally evaluated and compared to other state of the art clustering algorithms.

main_review: The problem is clearly well-motivated and the paper provides substantial progress in the direction of robust Bregman clustering. I find the experiments meaningful and agree that the novel method outperforms the methods it was compared to. The theoretical results are also compelling to me and underline the viability of the scheme.

I only have some minor questions/comments:
- In the proof of Lemma 3.1 you say that it can be observed that $ d_\phi(x, \theta) - d_\phi(x, P_\mathcal{C}(\theta)) + d_\phi(P_\mathcal{C}(\theta), \theta) \geq 0 $ implies the claim, which is $d_\phi(x, \theta) \geq  d_\phi(x, P_\mathcal{C}(\theta)) + d_\phi(P_\mathcal{C}(\theta), \theta)$. This is clearly not the case. Is this a typo or a major error (the remainder of the analysis depends on this lemma)? - I was out of time to check it myself.
- In the proof of Theorem 3.2, where does the $\sqrt{\frac{\log(2\delta)}{2n}}$ term come from? I assume it stems from some basic inequality like Markov's or some even more basic bound, but this is not immediate to me. Can you explain? Besides it must be $\log(2/\delta)$ (in some other places too).
- Since you are aiming at robustness it would be interesting to compare to a natural robust clustering scheme like $k$-median too.
limitations_and_societal_impact: The authors do not explicitly discuss limitations of their work. I see no direct path to negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed to modify the k-means problem (a more general version) using the principle of median of means (MoM), which leads to a better concentration and robustness against outliers.
main_review: Overall, I find this paper interesting and novel. It is very easy to read and the theoretical results are reasonable.
I only have a few small comments. 

Q1. [Non-convexity of the problem]
In general, the minimization of $\Theta$ is a non-convex problem (like the usual k-meams) so algorithm 1 may stuck at a local optimum. 
It is worth acknowledge this in the paper and mention that we will re-initialize the starting points.


Q2. [Possibility to weaken compact support assumption?]
A feature  of MoM is that we may obtain exponential/Gaussian concentration even if the original random variables only have moment conditions (rather than sub-Gaussian).
So it allows a much heavier tail distribution. 
I am wondering if the same thing is applicable here or not?

Under the k-means scenario (squares loss), it seems that we may relax the compact support assumption to be some moment conditions.
Any comments about this?


Q3. [Choice of L to be \log n]
Just curious: it seems that we can always choose $L \asymp \log n$, which will lead to the almost parametric rate (as indicated in the Remark of page 8). 
Is there any danger of doing so?
 
limitations_and_societal_impact: No apparent limitations of the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper looks at the Median-of-Means estimation framework for clustering and shows that it covers a range of k-means variants. They attempt to unify different frameworks of center-based clustering and introduce an algorithm that uses an adaptive gradient-based MoM algorithm. Under i.i.d. sampling of the data, they provide the convergence rates and the error rates obtained do not require any restrictions on the relation between the dimensions of the input points and the number of input points.
main_review: The paper is well written and provides a well-structured overview of the results. As far as I can see, the statements are well-founded and the mathematics holds true. They show that under standard assumptions, the estimate of the centroids given by the MoM framework approaches the optimal set of centroids as the size of the data is scaled. 
limitations_and_societal_impact: They discuss in Section 5, the performance of MoM (in terms of convergence rate) being slower compared to other methods. Also, they discuss the dependency on the number of outliers (on how the number of outliers scale against the $n$ and state that if it is proportional to $n$ the error does not give a meaningful result. They also make a statement about the societal impacts in the checklist but I feel that any negative concerns that could arise are native to almost any robust framework.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider the minimization of a Median-of-Means (MoM) objective, which is suitable to yield minimizers of a centroid-based clustering which is more robust to outliers. The type of the centroid-based clustering is defined over the employed measurement of distances, which can be any  Bregman divergence. The considered MoM objective is hence suitable to encompass various $k$-means formalizations.

The authors formulate an Adagrad method to minimize the MoM objective, and analyze properties of the global minimizer of the MoM objective with respect to robustness to outliers. They apply concentration inequalities to compare the MoM global minimizer to the global minimizer of the expected value of the generalized distance of points to their centroid. Since outliers do not influence the expected value, a small distance of the MoM minimizer to the one of the expected value indicates robustness to outliers.  
The authors provide an experimental analysis of the power $k$-means objective, optimized by the proposed optimization scheme on synthetic data and one real-world dataset.
main_review: The authors provide a thorough analysis of the global MoM minimizer with respect to the robustness to outliers and their empirical analysis shows that the optimization scheme can actually yield more robust results than comparable clustering methods.
Yet, in spite of all that, I am still on the fence. One of the main reasons for this is the presentation. This is a very technical paper and it is on top of its technicality not easy to follow because of overloaded variables, undefined functions, and errors (cf. minor issues). Then, the related work is not explicitly discussed. In between the text, there are fragments that hint at the improvement of the derived result in comparison to a related result, but there is no overview of the SOTA knowledge of MoM minimizers in general and those for clustering in particular. In that respect, I find it hard to assess the gain of knowledge and the potential impact of the provided theoretical result.

In addition, the practical aspects (the optimization framework and its experimental analysis) and the theoretical results are not really coming together. The experiments do only consider the power $k$-means implementation of the optimization framework, although one of the emphasized strengths of the framework is its general applicability to various $k$-means variants. There is no discussion of the relation of the found local minimizers in comparison to the global minimizer, analyzed in the theoretical part. I am missing an experiment where the number of data points is increased such that the practical convergence can be checked in comparison to the theoretical guarantee. The theoretical results apply regardless of the optimization framework because they address the global minimizer of the objective.

In summary, I wonder if the theoretical results on their own are contribution enough to vote for acceptance. In that case, the related work should be discussed more thoroughly and the paper should maybe just be a theoretical one. If the theoretical results do however not yield enough impact to vote for acceptance, then the experimental analysis should be extended. In that case, some of the Lemmata should be put in the appendix and also other $k$-means variants should be implemented and compared to. The effect of parameters should be evaluated and more datasets should be used. Maybe, this paper would also be better served by being submitted to a journal, such that the 11-page supplement can be integrated into the main body of the paper.  

### Minor Issues/Suggestions
* The name $P$ is used for the objective of $k$-means in the introduction and the probability distribution.
* The term _convergence rate_ for the clustering method is misleading, since I believe that most people associate therewith the convergence rate of the optimization method. In addition, that sentence in L70 is not really true, since the convergence rate does not exactly refer to the results of clustering methods but to the global minimizers of their objectives.
* The objectives in Examples (L88) miss an $1/n$ in front. Not that it would really matter but to be consistent with the objective (1).
* Algorithm 1: 
   * Step 2: $g_j^(t)\leftarrow ..$ ?
   * Step 3: $\lVert g_j^(t')\rVert^2_2$ in the denominator, likewise in L113
* L159: what is $\Psi(\Theta,Q)$?
* L213: what is $O_P(..)$?
* it should be $\in \mathcal{O}(..)$ and so on, not $=\mathcal{O}(..)$
* Did you try using synthetic data with more than 5 dimensions? How does it affect the results?
* The formatting of the proof sketch of Thm 3.4 makes it impossible to read with all the inline math.

*Supplement*
* L8: $H_{s,p,M}$?
* Lemma A.2 is not necessary/ well known, I believe
* Lemma A.3: the $sup$ is missing in the equations and explanations are missing
* L24: $\partial J(P_C(\theta))=..$ and why is it a set? Why is there talk of a subgradient when $d_\phi$ is differentiable?
* L25: it should be $-d_\phi(P_C(\theta),\theta)= \langle \nabla \phi.. $ 

## Updates after authors response
The authors provided a very thoughtful response which shows in particular that the presentation will be overhauled, which was one of my main concerns. Due to the authors' response, I will change my borderline assessment to accept. I very much like the idea that the authors intend to publish an extended journal version. For the Neurips submission, there is the issue of space. From _my side_ I would not request that the authors add more experiments (although I would really like to see this one experiment to observe the convergence of the bound in practice, maybe in the journal version then). I would rather focus on the presentation of the theoretical work and the connection from the theoretical results to practice. The other reviewers may contradict me if they think I am wrong here :)  




limitations_and_societal_impact: The limitations, for example the applicability of the theoretical result, could be discussed more in detail, There are justifications for the assumptions, but there is no discussion in which cases these assumptions might fail. In addition, the translation from the theoretical result to practical applications is not discussed. How does a guarantee on the global minimizer translate to the local minimizers found by the existing algorithms? There does probably not exist a proper answer at this state, but I think it should still be mentioned.
review_title: null

Meta-review: The authors develop a unified framework for robust clustering using the Median of Means approach, and provide an analysis of the consistency and convergence of the algorithms derived through this approach. The framework applies to a diverse set of clustering problems, and empirical comparisons show convincingly that the proposed method is indeed more robust than the baselines considered. Given the wide usage of clustering methods, this work will be of wide interest to the community.
Decision: Accept (Spotlight)