Uniform Concentration Bounds toward a Unified  Framework for Robust Clustering
Authors: Debolina Paul
Saptarshi Chakraborty
Swagatam Das
Jason Xu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: k-means
median of means
metric entropy bounds
Bregman divergences
Iterative optimization

Abstract: Recent advances in center-based clustering continue to improve upon the drawbacks of Lloyd's celebrated $k$-means algorithm over $60$ years after its introduction. Various methods seek to address poor local minima, sensitivity to outliers, and data that are not well-suited to Euclidean measures of fit, but many are supported largely empirically. Moreover, combining such approaches in a piecemeal manner can result in ad hoc methods, and the limited theoretical results supporting each individual contribution may no longer hold. Toward addressing these issues in a principled way, this paper proposes a cohesive robust framework for center-based clustering under a general class of dissimilarity measures. In particular, we present a rigorous theoretical treatment within a Median-of-Means (MoM) estimation framework, showing that it subsumes several popular $k$-means variants. In addition to unifying existing methods, we derive uniform concentration bounds that complete their analyses, and bridge these results to the MoM framework via Dudley's chaining arguments. Importantly, we neither require any assumptions on the distribution of the outlying observations nor on the relative number of observations $n$ to features $p$. We establish strong consistency and an error rate of $O(n^{-1/2})$ under mild conditions, surpassing the best-known results in the literature. The methods are empirically validated thoroughly on real and synthetic datasets. 

Uniform Concentration Bounds toward a Unified Framework for Robust Clustering
Debolina Paul"
Saptarshi Chakraborty' Department of Statistics University of California, Berkeley cpptarshic@berkell.. edu
Department of Statistics Stanford University
debolinap@stanf ord. edu
Swagatam Das
Jason Xu² Department of Statistical Science Duke University jason. q xu@duke edu
Electronics & Communications Sciences Unit Indian Statistical Institute swagatam das@isical ac in
Abstract
Recent advances in center- based clustering continue improve upon the draw- backs of Lloyd's celebrated k-means algorithm over 60 years after its introduction. Various methods seek to address poor local minima, sensitivity to outliers, and data that are not well-suited to Euclidean measures of fit, but many are supported largely empirically. Moreover, combining such approaches result in ad hoc methods, and the limited theoretical results supporting each individ- ual contribution may no longer hold. Toward addressing these issues in principled way, this paper proposes cohesive robust framework for center-based clustering under a general class dissimilarity measures. In particular, we present a rigorous theoretical treatment within Median-of-Meet showing that it subsumes several popular k-means variants. addition to unifying existing methods, derive uniform concentration bounds that complete their analyses, and bridge these results to the MoM framework via Dudley's 's chaining arguments. Importantly, neither require any assumptions the distribution of the outlying observations nor on the relative number observations n to features
piecemeal manner can
(MoM) estimation framework,
p. We establish strong consistency and an error rate O(n (n2) under mild conditions, surpassing the best-knows known results in the literature. The methods are empirically validated thoroughly on real and synthetic datasets.
Introduction
Clustering is a fundamental task unsupervised learning, which seeks to discover naturally occurring groups within dataset. Among plethora of algorithms in the literature, center-based methods remain widely popular, with k-means [35 (3) as the most prominent example. Given n data points X' (X,
1, ...... n.. C R", k-means seeks to partition the data into À mutually exclusive and exhaustive groups by minimizing the within cluster variance. Representing the cluster centroids . 0 C RR. the k--maan problem is formulated the minimization of the objective C 1 ...,.
function fk meam. ) = Σ minigjęk (X;,, 0z), where d(-..) is dissimilarity measure. Taking the squared Euclidean distance d(xx, y) = x - vll3 yields the classical h-means formulation.
Clustering via k m-masss is delleeeceee to be sensitive to initialization (54), prone to getting stuck poor local optima [57 56 17]. and fragile against linearly non-separable clusters 39 or
Joint first authors contributed equally
Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

in the presence of even a single outlying observation [26]. Researchers continue to tackle these drawbacks of k-means while preserving its simplicity and interpretability 4
40
58
49
Although often successful in practice, few of these approaches are grounded in rigorous theory or provide finite-sample statistical guarantees. The available consistency results are mostly asymptotic in nature 17 51 52], lacking convergence rates or operating under restrictive assumptions on the relation between p and n [42]. For example, the recent large sample analysis [42] of the hard Bregman k-means algorithm + obtains an asymptotic error rate of O(v /log n n//n) under restrictive assumptions the relation between n and p. The approach by [4] focuses on unified framework from an optimization perspective, while [3 49] focus on different divergence- bbssed methods to better understand the underlying feature-space.
The presence of outliers only further complicates matters. Outlying data are common in real applications, but many of the aforementioned approaches are fragile to deviations from the assumed data generating mechanism. On the other hand, recent work on robust clustering methods [88 2 do not integrate the practical advances surveyed above, and similarly lack finite-sample guarantees. To bridge this gap, the Median of Means (MoM) literature provides a promising and attractive framework to robustify center-based clustering methods against outliers. MoM estimators are not only insensitive to outliers, but are also equipped with exponential concentration results under the mild condition of finite variance [3 29 6 31 27]. Recently, near-optimal results for mean estimation
37..
classification [30], regression 36 34,, clustering [26] 13] bandits [4] and optimal transport have been established from this perspective.
46
Under the MoM lens, we propose unified framework for robust center-based clustering. Our treat- ment considers family of Bregman loss functions not restricted to the classical squared Euclidean loss. We explore the exact sample error bounds for a general class algorithms under mild regularity assumptions that apply to popular existing approaches, which we show to be special cases. The proposed framework allows for the data to be divided into two categories: the set of inliers (I) and the set of outliers (O). The inliers are assumed to be independent and identically distributed (i.i.d.), while absolutely no assumption is required on O, allowing outliers to be unboundedly large, dependent on each other, sampled from heavy-tailed distribution and on. Our contributions within the MoM framework make use of Rademacher complexities [5] 7 and symmetrization arguments [53), powerful tools that often find use in the empirical process literature but, in view, are underexplored in the context of robust clustering.
The paper is organized as follows. In Section 2 we identify a general centroid-based clustering framework which encompasses k-means (35), k- k-harmonic means [57], and power k-means (56) as special cases, to name few. We show how this framework is made robust via Median of Means estimation, yielding an array of center-based robust clustering methods. Within this framework, we derive uniform deviation bounds and concentration inequalities under standard regularity conditions through bounding Rademacher complexity by metric entropy via Dudley's ' chaining argument in Section 3 The analysis newly reveals the convergence rate for popularly used clustering methods such as k-harmonic means and power h-means, matching the known rate results for k-means, and elegantly carries over to their MoM counterparts. We then implement and empirically assess the resulting algorithms through simulated and real data experiments. In particular, we find that power k-means (66] under the MoM paradigm outperforms the state-of-the-art in the presence of outliers.
1.1 Related theoretical analyses of clustering
In seminal work, Pollard 43), proved the strong consistency of k-means under a finite second moment assumption, spurring the large sample analysis of unsupervised clustering methods. This result has been extended to separable Hilbert spaces 110 32 and for related algorithms 15] 51 52]. 2. but these do not provide guarantees on the number of samples required so that the excess risk falls below a given threshold. Towards finding probabilistic error bounds, following research derived uniform concentration results for k-means and its variants 44). sub-Gaussian distortion bounds for the k- medians problem 12). and a O /log n/n) bound on k-means with Bregman divergences [41]. More recently, concentration inequalities for k-means under the MoM paradigm have been established
26 under the restriction that sample cluster centroids (O,, in Section 33 are assumed to be bounded. This paper shows how number of center-based clustering methods can be brought under the same umbrella and can be robustified using a general-purpose scheme. The theoretical analyses of this broad spectrum of methods is conducted via Dudley's 's chaining arguments and through the aid

---

of Rademacher complexity-basd based uniform concentration bounds. This approach enables us to replace assumptions on the sample cluster centroids by a bounded support assumption of the (inlying) data points, which yields an intuitive way of ensuring the boundedness of the cluster centroids through the obtuse angle property of Bregman divergences (Leemaa 3.1 below). In contrast to the prior results, our analyses are nor asymptotic in nature, so that the derived bounds hold for all values of the model parameters.
Problem Setting and Proposed Method
We consider the problem of partitioning set of n data points X' (X;: L...=,......2 R2 into mutually exclusive clusters. In a center-based clustering framework, we represent the jth cluster by its centroid 9 IR" for each j {1,..., k). To quantify the notion of "closeness", the dissimilarity measure to be any Bregman divergence. Recall any differentiable, convex function : IR" generates the Bregman divergence dæ RRP R Rz0 (R20 denoting the set of non-negative reals) defined as
allow
dæ(x, y) = 0(x) o (Voly) 4)
For instance, (fu) || generates the Euclidean distance. Without loss of generality, one may assume (00) = (0) 0. In this paradigm, clustering is achieved by minimizing the objective
Va (()(x,,,)))).,,,((((,)) (X)
n
Here Va RR5 R20 is component-wise non-decreasing function (such as a generalized mean) of the dissimilarities [da((: θ5)} which satisfies (0) 0. The hyperparameter a E A C R specified by the user, and we will additionally assume that V Lipsehitz. For intuition, we begin by showing how this setup includes several popular clustering methods.
Examples: Suppose duu) || and (z)) 1 )-
Then the objective | becomes - (E I 0, 2) which is the objective function of k-harmonic means clustering [57. Now consider other generalized means: take V (x) Mx(x) where denote the power mean M,(x:) (h-1 Σ a² 2// for 8 (-00, -1]. Then objective [1 coincides with the recent power
sjss Fyy I recovers Bregman hard clustering Ei= minisss* da( 02) proposed in 4 for any valid ø, while the special case of (uu) = ||]l yields the familiar Euclidean k-means problem 35
k-means method [56], n Em M, (IX; 0 11. ..... I| 0 12) When V (x:)
In what follows, we derive concentration bounds that establish new theoretical guarantees such as consistency and convergence rates for clustering algorithms this framework. These analyses lead us to unified, robust framework by embedding this class of methods within the Median of Means (MoM) estimation paradigm. Via elegant connections between the properties of MoM estimators and Vapnik- mhmnik--hervoeeniis (VC) theory, our MoM estimators too will inherit uniform concentration inequalities from the preceding analysis, extending convergence guarantees to the robust setting.
Median of Means Instead of directly minimizing the empirical risk (I. MoM begins by partitioning the data into sets B,,..., Br, which each contain exactly many elements (discarding a few observations when is not divisible by L). The partitions can be assigned uniformly at random, or can be shuffled throughout the algorithm [30]. MoM then entails a robust version of the estimator defined under I by instead minimizing the following objective with respect to θ:
f6(x.)) E ... J E BE iEB
MoMy (e) = Median
(2)
Intuitively, MoM estimators are more robust than their ERM counterparts since under mild conditions, only a subset of the partitions is contaminated by outliers while others are outlier-free. Taking the median over partitions negates the influence of these spurious partitions, thus reducing the effect of outliers. Formal analysis of robustness via breakdown points also available for MoM estimators 28 44
we will make use of the nice concentration propertics of MoM estimators in Section 3.4
3

---

Algorithm MoM Clustering via Adagrad
Input: X
R=XP, k, L. fe(.). (.),,))
Output: The cluster centroids ④
Initialization: Randomly partition (1....,n) into L many partitions of equal length. Randomly choose k points without replacement from X' to initialize Og. repeat
Step 1: Find & E (l,...,, L), such that MoM)((;) = =t Eien, fe. (X:).
Step 2: 9
EieB, vo,
Step 3: Update by 0g ( - (())
7 V V 110 11
until objective
2 converges
Furthermore, optimizing is made tractable via gradient-based methods. We advocate the Adagrad algorithm whose updates are given by
(++1)
(1)
7
(1)
9j
Ve+ 21=11 9 11
(1) denoting subgradient of MoM)(() at O
for hyperparameter 0, learning rate 0, and gj That is, if l denotes the median partition at step f, then
MoMMo = 1 Σ
fo,
BE
For any Va differentiable, Ve,fe(x) = 2 (do(z, (d..,, 0(4)) chain rule. As a concrete illustration of the general formula, consider the power k-means objective Se (x) = MI 0112..... 12l12): upon partial differentiation, we obtain
dx
Vado(x, 0) by the
1/8-1
k
0
o -0,11(2 1) (0, -x).
=1=1
As another example, the classic k- k-means objective fe( minose | 011 requires the sub- gradient fe = 2(0 - Lj E [@, where J(O, x) = argmin x -0, 0 and 1(- denotes the indicator function.
A pseudocode summary appears in Algorithm I This method tends to find clusters efficiently: for instance, we incur O(ppk) per-iteration complexity applied both the k-means and power k-means instances, which matches that of their original algorithms without robustifying via MoM [35 33 56)
Of course, here we update 0, by an adaptive gradient step rather than by closed form expression.
As emphasized by an anonymous reviewer, one should note that the algorithms under the proposed framework may converge sub-optimal local solutions under the proposed optimization scheme. As is the case for k-means and its variants, this possibility arises due to the non-convexity of the objective functions (T) and (2). A complete theoretical understanding from an optimization perspective for such methods is not yet fully developed and global results are in general notoriously difficult to obtain. Having said that, it worth noting that recent empirical analysis show that techniques such as annealing [36 17] may be effective to circumvent this difficulty. Indeed, our experimental analysis (see Section suggests that robust version power k-means using this annealing technique best overcomes this difficulty even in the presence of outliers.
3 Theoretical Analysis
Here we analyze properties of the proposed framework ① with complete details of all proofs in the Supplement. Denoting M the set of all probability measures P with support on [-M, MPP i.e. P(--M, P) 1, we first make standard assumptions that the data are i.i.d. with bounded
components 99
42

---

A1. X1 XI..,,X, Xn sid. P such that P M.
Let Ps be the empirical distribution based of the data X X.. That is, for any Borel set A, (A) Ex= 1(x; A}. For notational simplicity, write μf f Appealing to the Strong Law of Large Numbers (SLLN) (2), Pafe وقك pfe. Suppose θ,, be a (global) minimizer of ( and e" be the global minimizer of pfe. Since the functions f. and ffe close to each other as become large, we can expect that their respective minimizers, θ, and O* are also close to one another. To show that O, converges to O* as n + oc, we consider bounding the uniform deviation supe Se P. l. Towards establishing such bounds, we will posit two regularity assumptions on ( and (.). beginning with a To. Ta..-Lipschite condition on aa
A2. For all A and any æ, y 2 we have ( Va (x) S Tor | y111.
We also assume weaker form of a standard condition that the gradient VΦ(() is Hp Lipschitz [50]; unlike their work, note we do not additionally require strong convexity of ø.
A3. There exists Hp 0 such that [[Vo(=)= Vo(y))22 S Hp yll2 for all æ, y E I-M, M|P.
These conditions are mild, and can be seen to hold for all of the aforementioned popular special cases. For instance, taking ((u) ||u]² yields the squared Euclidean distances, and we see that VΦ(u)= = 2u that A3is satisfied with constant Hµ = 2. Now, let (x) minigiss Dy in classical k-means, and denote j" E argmin sgjsk Vj-- For any vectors I, y E R
(x) (yy) min Iy min 5/3 min Ij By S ... By S | pee-yll. yll1. 1Sisk
1SJSk
1SJSk
Thus, V is clearly non-negative and componentwise non-decreasing, and satisfies A2 Similarly, if take (x) (x). the conditions met for power k-means: it is again non-negative and non-decreasing in its components, and satisfies A
with Ta, = 1/1 due to (8).
3.1 Bounds on Q, and θ
Toward proving that θ converges to O', we will need to show that both G and O* lie in [-M, M kxp, To this end, we first establish the obtuse angle property for Bregman divergences.
Lemma 3.1. Let C be convex set and suppose Pc(O) be the projection of A onto with respect to the Bregman divergence dol,,)) )). i.e. (0) arg minwgc dæ( 0) (assuming it exists), Then, dx 0) 2 (ax Po)))) + d (0), 0), for all x E C.
We next show that to minimize faje or Pfe. it is enough to restrict the search to [-M, MMMMMK. kxp. Lemma 3.2. Let A2 hold, and Q M. Let de R x RD - R>0 be Bregman divergence. Then for any θ E IR kxp, there exists O E M, kMp,, such that Qfe S Q.fe
Since we can restrict our attention to [-M, MM to minimize Qʃe, we have the following:
Corollary 3.1. Let Q M and dø : RR. x RD + IRzu be a Bregman divergence. If O arg mrggi I fedQ, then O E [-M, AxP.
Now note under All both P and Pr. have support contained in [-M, M| The following corollary thus implied by replacing Q by P and P..
Corollary 3.2. Under A both θ,, O* e [-M,
Now that we have bounded θ, and O" in compact set, the following section supplies probabilistic bounds on the uniform deviation suppe M.M Paaee p.fll via metric entropy arguments.
3.2 Concentration Inequality and Metric Entropy Bounds via Rademacher Complexity
We have proven that 6,,, 0* E [ To bound the difference |Pfa.. - -Pfe-l, we observe
Pl -Ple- = Ple. Pfe- = PSe. Pajs. + PPJo. P./e- + P.Je- Pse-
sup < PSe. Pule. Pale- Pse M
|a,e Pfel. (3)
5

---

Thus, to bound IP Pfe- it is enough to prove bounds on MP PP.ffe Pfel The main idea here is to bound this uniform deviation via Rademacher complexity, and in turn bound the Rademacher complexity itself 220 38) Let {fe θ E M))x)), and denote the F-norm [2] between two probability measures and V as |u v sur |J fdu - fdvl.
We recall the definition Rademacher complexity and covering number as follows.
Definition 1. Let e, 's be i..dd Rademacher random variables independent of X' = {X....., X,).
Le. P(g = = P(e = -1) = 0.5, The population Rademacher complexity of F is defined as where the expectation is over both e and X.
RR.(F) = EsspEEupeeee
Definition 2. (ô-cover and Covering Number) Let (X, be a metric space. The set Xs S X is said to be ô-cover of X for all x E X, x' E X6. such that d(x, x') S. 6. The ò-covering mumber of X w.r.t denoted by N (6; X, d), the size of the smallest ô-cover of X with respect to d.
The following Lemma gives bound for the ô-covering number of F under the supremum norm. The main idea here is to use the Lipschitz property of fe and then to find cover of the search space for O i.e. [-M, M] kxp. This then automatically transcends to cover of F under the sup-norm.
Lemma 3.3. Ler ((;; F, II (loe) be the d-covering number of F under ||
Il Then, under kp
8M To Hpkp
N6: F, 11 1100)
maxx
To bound the Rademacher complexity, we will also need bound the diameter of F under || lloo: Lemma 3.4. Let diam S.e [ - glloo. Then, under diam (F) S 8Ta, H MpM2M kp.
We now ready to state the bound on the Rademacher complexity (F) in Theorem 3.1 We provide a sketch the argument below, with the complete proof details available in the Supplement. Theorem 3.1. Under 4 (F) 4 (k2p)))
Proof Sketch The main idea of the proof is to use Dudley's 's chaining argument 20 55 to bound the Rademacher complexity in terms of an integral involving the metric entropy log N6; F, llxo). Let A 8H, SH,,M22.1-1/9, Using the chaining approach, one can show that
12 (F(
vn / Vlog (e; lloode <
12
A 1
Aplog
max E
(4)
Vn J
12
A de kp kppoo log
Vn
Jo
48 / /TTak H y. (kp)
Here the second inequality 4 follows from Lemma 3.3 Before we proceed, we state the following Lemma, which puts uniform bound on |l Lemma 3.5. For all x E [-M, and E [-M, *
0 < 1/ V (ds (w, 01), ... (z 0x)) S 4T H. M2 pk.
Now that we have established a bound on the Rademacher complexity (F), we are now ready to establish a uniform concentration inequality on Pa. P|| a supjeF [Pn PSI the following Theorem, proven in the Supplement.
Theorem 3.2. Under 7 with probability least 1 5, the following holds.
log log(2/0) (2/8)
PAa P|| < 96 2 Mf
1/2 4Ta, MrM
2n.
The result in Theorem 3.2 reveals non-asymptotic bound on PP P
Corollary 3.3. Under 41 3 with probability at least 1 - 6, the following holds.
[og
Pfe. Pfe
< 192 192 (kp)) 1/2 8T,,HHHH,M. H² pky
2n
Proof. From equation know that Pfe.
pfe 5 2|p,, Pllr. The corollary follows
immediately by application of Theorem 3.2

---

3.3 Inference for Fixed pt Strong and vn Consistency
We now discuss the classical domain where p is kept fixed above imply strong and Vr-consistency, mirroring some known results for existing methods such as k-means. We first solidify the notion of convergence of the centroids @, to O', following Pollard
4
and show that the results
43 Since centroids are unique only up to label permutations, our notion of dissimilarity
diss( O 2
min ||0] 2
MEP,
is considered over Pa the set of all k k real permutation matrices, where -Ir denotes the Frobenius
norm. Now, we say that the sequence O, converges to θ if l diss R, () = We begin by
imposing the following standard identifiablity condition [3 57 P for our analysis.
A4. For all rj > there exists > 0, such that pfe Pfe-
whenever diss( ( O*) > 7)
We now investigate the strong consistency properties of Gn and also investigate the rate which IP ff converges to O. Theorem 3.3 states that indeed strong consistency holds, with
convergence rate O(n 1/2). Note that this rate faster than that found previously in 42 Before we proceed, recall we say that X,, = (a()n) if the sequence X an is tight (2]
Theorem 3.3. (Strong consistency and /n-consistency) If is kept fixed then under O' under P. Moreover, [Pfe. fe Op(n 1/2))
a...
Note: Here A, is Op(an) means that (An/ an JUEN is stochastically bounded or tight.
3.4 Inference Under the MoM Framework
Theorem 3.3 and the bounds we present above already establish novel statistical results that pertain to methods under [1] such as power k-means in the "uncontaminated" setting. In this section, we now extend these findings to the MoM setup under (2) in order to understand their behavior in the presence of outliers. Recall that in this setting, the data are partitioned into equally sized blocks; without loss of generality, we take n L b. We denote the set of all inliers by her and outliers (MoM)
by which PP
Now let @,, (0AM)
denote the minimizer of (2): towards establishing the error rate (18N) - f goes to O, we assume the following:
itd ~ P with P P.M. A5. (Xi
A6. There exists 17 > 0 such that L > (2+1)(0))
We remark A5iis identical to AD. but imposed only the inlying observations. Nolensures least half of the L partitions are free of outliers; note this is much weaker than requiring L >> 4 O as is done in recent work [30]. Importantly, we emphasize that no distributional assumptions regarding the outlying observations are made, allowing them to be unbounded, generated from heavy-tailed distributions, or dependent among each other. Proofs of the following results appear the Supplement.
As point of departure, first establish that θ (MoM) Lemma 3.6. Let 2 such that MoM ( MoM
E {
3 and A5
6 hold. Then for any O E kxp, there exists O' E (
Again, we may restrict the search space for finding θ (MoM)
in M, MXx due to Lemma 3.6
(MoM)
Corollary 3.4. Under
and
- M, K
Similarly to Section
3 we derive uniform bound on M.P.EI-M.M MoM Pfel and
then bound [P/ (MAAD Pfe- in turn. For brevity we define == 2/(4 + 7) - |0] and use the
notation "S" suppress the absolute constants. The uniform deviation bound as follows, with complete proof appearing in the Supplement.
Theorem 3,4. Under
2 and
6 with probability at least 1 - 2e -2182 the following holds.
L
I n
sup OE(-M.M)ix
MoM) - pfel S Ta.k H. max kPy (kp)
3/2 (kp)
n
7

---

We give a brief outline of our proof for Theorem 3.4 below, with details appearing in the Supplement.
Proof sketch We begin by noting that if MuPee[-MMMj E ((P Pe /.2 then MIPee[-M.M]' (fee (
where PB, denotes the empirical distribution of {X (X This implies is suffices to bound the quantity
+ 112 [
L
1.
sup MEI-M. t=1
2
Introducing the function (0(1) = -1- 1)1(1 < 1 2 + 1f1 > 2). we begin by
bounding outlier-free partitions, making use of the inequalities 1 2 2] S ( v
1tt 2 1.. We then proceed by bounding M, Et 1[ - fe. c} by
the sum E
10), where { supec(-M,M)xx ElEc Epp
2(P (IP-Pa,,l 1s and &
MUP Etec 10 2(P 2(PP-Pn)/00) Epp 2(P (2(P-Pn Me0
We bound & by appealing
Hoeffding's inequality, while we show that E2 can be bounded by applying the bounded difference inequality together with the result of Theorem to bound the resulting Rademacher complexity.
The corollary below follows from this uniform bound, giving a non-asymptotic control over the Pfe- in terms of the model parameters.
difference Pf (MoM)
Corollary 3.5. Under 2 and A5
with probability least 2e- 21,62, the following holds.
L kp n
VI
Pfe-1 $ Fa Hp max
(kp)
3.5 Inference for Fixed k and p Under the MoM Framework
We now focus our attention back to the classical setting where the numbers of clusters and features remain fixed. To show θ (MoM) is consistent for O" we need to impose conditions such that the RHS of the bounds presented in Corollary decrease as follows.
+ co. We state the required conditions
A7. The number of partitions L = o(n), and - oc as YL + CO.
These conditions are natural: as n grows, so too must L in order to maintain a proportion outlier- free partitions. On the other hand, L must grow slowly relative to n to ensure each partition can be assigned sufficient numbers datapoints. We note that A7 implies |O] o(n). an intuitive and as outliers should be few by definition.
standard condition 33 46 41
In the following corollary, focus the squared Euclidean distance for center-based clustering under the MoM framework. We show that the (global) estimates obtained from MoM k-means, MoM power k-means etc. consistent. We stress that the obtained convergence rate, as function of n, L and [Z], does not depend on the choice of V. ..).)), as long as it satisfies AQ] i.e. is Lipschitz. In particular, replacing (-)(-) with minigjss Tj, (z( and 1 ")=)) the rate in Corollary 3.6 applies to robustified MoM versions of k-means, power k-means and k-harmonic means alike.
Corollary 3.6. Suppose ((u) || and V (-aissf 1 Then under 22 and A 7
PPggumn uman, Pfell Op (max 12 1/2 n VIZI))
P, Pfe. Moreover whenever A4 additionnaly holds, we have θ (Molr)
and Pigauar (Ma))
Remark These results imply that any MoM center-basee algorithm under our paradigm admits
a convergence rate of (max [1, 1,2// n1 - }): when equipped with squared Fuclidean
distance. Note that as L 2 1, max 11/22 1/2 [ = (n- (1/2). Thus, the convergence
8

---

rates for MoM variants in our framework are generally slower than their ERM counterparts, for which the rate is (n22) This is unsurprising as MoM operates on qutlier-contaminate data; there is "no free lunch" in trading off robustness for rate of convergence. However, if the number of partitions L grows slowly relative to n (say, L = Olog n) so that |O| (log n)), then the convergence rates for MoM estimation become comparable to the ERM counterparts at O(n1)))).
Empirical Studies and Performance
To validate and assess our proposed framework, we now turn an empirical comparison of the proposed and peer clustering methods. We evaluate clustering quality under the Adjusted Rand Index (ARI) [23], with values ranging between 0 and and denoting perfect match with the ground truth. Though it is not feasible to exhaustively survey center- based clustering methods, we consider broad range of competitors, comparing k-means [35], Partition Around Medoids (PAM) (25] k-medians [24]. Robust kmeans++ (RKMpp) [18,, Robust Continuous Clustering (RCC) 45
Bregman Trimmed k-mmaans (BTKM) (2], MoM k-means (MOMKM) (26] and a novel MoM variant of power k-means (MOMPKM) implied under the proposed framework.
We consider two thorough simulated experiments below, with additional simulations and large- scale real data results in the Supplement. While the extended comparisons are omitted for space considerations, they convey the same trends as the studies below. In all settings, we generate data in 5 dimensions, varying the number of clusters and the outlier percentages. True centers are spaced uniformly on a grid with 0₂ = 10
k-1 and observations are drawn from Gaussians around their
generate Gaussian data, we focus here on the Euclidean case, and do not consider other Bregman divergences in the present empirical study. In all experiments,
ground truth centers with variance 0. 1. Because
take the number of partitions I, to be roughly double the number of outliers, and set the hyperparameters and a to be 1.02 and 1 respectively by default. Results are averaged over 20 random restarts, and all competitors are initialized and tuned according to the standard implementations described in their original papers.
Experiment 1: increasing the number of clusters The first experiment assesses performance as the number of true clusters grows, while keeping the proportion of outliers fixed 25%. Datasets are generated with the number of clusters k varying between 3 and 100. For each setting, we create balanced clusters drawing 30 points from each true center. The 25% outliers are generated from a uniform distribution with support on the range of the inlying observations. We repeat this data generation process 30 times under each parameter setting.
The average ARI values at convergence, plotted against the number of clusters along with error bars (+: standard deviations), are shown in the left panel of Figure We see that the robustified version of power k-means implied by our framework (labeled MOMPKM) achieves the best performance here. This may be unsurprising as the recent power k-means method was shown significantly reduce sensitivity to local minima (which tend to increase with k), while MoM further protects the algorithm from outlier influence.
Experiment 2: increasing outlier percentage Following the same data generation process in Experiment 1, we now fix k = 20 while varying the outlier percentage from 0% to 50%. For each parameter setting, we again replicate the experiment 30 times. Average ARI values comparing the inlying observations to their ground truths are plotted in the right panel of Figure [] Not only does this study convey similar trends as Experiment I, but we see that competing methods continue to deteriorate with increasing outliers one might expect, while MOMPKM remarkably remains relatively stable.
We see that the ERM-based methods such as BTKM, MOMKM, and PAM struggle when there is large number of clusters. Similarly, methods such k-medians and RKMpp often stop short at poor local optima, which is quickly exacerbated by outliers despite initialization via clever seeding techniques. These phenomena are consistent with what has been reported in the literature for their non-robust counterparts [56] 17]. Overall, the empirical study suggests that a robust version of power k-means clustering under the MoM framework shows promise to handle several data challenges at
once, in line with our theoretical analysis.

---

BTKM k.means
kimedians
MOMKM
MOMPKM
PAM
PKM
RCC
RKMpp
1.00
1.00
0.75
0.75
Average ARI
0.50
0.50
0.25
0.25
0.00
0.00
25
50
75
100
10
20
30
40
50
Number of Clusters
Outlier Percentage
Figure 1: Average ARI values, along with error bars (#sd), comparing the peer algorithms in Experiments 1 (left) and 2 (right). MOMPKM remains relatively stable even when k or outlier percentages increase, maintaining the best performance among peer methods.
5 Discussion
In this paper, we proposed paradigm for center-based clustering that unifies suite of center-based clustering algorithms. Under this view, developed simple yet efficient framework for robust versions of such algorithms by appealing to the Median of Means (MoM) philosophy. Using gradient- sudieett-baedd based methods, the MoM objectives can be solved with the same per-iteration complexity of Lloyd's k-means algorithm, largely retaining its simplicity. Importantly, derive thorough analysis of the statistical properties and convergence rates by establishing uniform concentration bounds under i.i.d. sampling of the data. These novel theoretical contributions demonstrate how arguments utilizing Rademacher complexities and Dudley's 's chaining arguments can be leveraged the robust clustering context. As result, we able obtain error rates that do require asymptotic assumptions, nor restrictions on the relation between and p. These findings recover asymptotic results such as strong consistency and Vn--consistency under classical assumptions.
As shown in the paper, the robustness MoM estimators comes at the cost of slower convergence rates compared to their ERM counterparts. We emphasize that there is no "median-of- -f-mmnnss magic", and that the efficacy MoM depends on the interplay between the partitions and the outliers. the number of partitions circumvents the impact of the outliers, the performance of MoM clustering estimates under framework scales with the block size b as 1/ Vb VL/n. Since L can be chosen to be approximately 2 2,0), the obtained error rate is roughly O (V/lO//). If |O] scales proportionately with n, however, the error bound of O (V (VVOl//) Ol/n)) becomes meaningless. For our consistency results hold, it is crucial that |O] o(n). which turn allows to choose that satisfies condition A7 If [ O for some 0 < 3 the error rate is (1 1)/2).
This suggests possible future research directions in improving these ERM rates via finding so called "fast rates" under additional assumptions [1]] 55). Moreover, will be fruitful to extend the results for noise distributions that satisfy only moment conditions. Recent works in convex clustering [47] [6 have considered Gabb-Gausiinn models obtain error rates. The work by [10] and recent work by 26 obtain similar error rates under finite second-moment conditions using assumptions that the cluster
centroids θ,, are bounded, and it may be possible to extend our approach using local Rademacher complexities
relax the bounded support assumption. One can also seek lower bounds on the approximation error or can explore high-dimensione proposed paradigm. Finally, we have not explored the implementation and empirical performance of Bregman versions of our MoM estimator, for instance with application to data arising from mixtures of exponential families other than the Gaussian case. These interesting directions remain open for future work.
robust center- based clustering under the
10

---

References
[1] D. Aloise, A. Deshpande, Hansen, and Popat. NP-hardness Euclidean sum-of -q-aressss clustering. Machine Learning, 75(2):245-248, 2009.
[2] K. B. Athreya and S. N. Lahiri. Measure theory and probability theory. Springer Science & Business Media, 2006.
[3] M.-F. Balcan, A. Blum, and S. Vempala. A discriminative framework for clustering via similarity functions. Proceedings of the fortieth annual ACM symposium on Theory of computing. pages 671-680, 2008.
[4] A. Banerjee. S. Merugu, I. S. Dhillon, J. Ghosh, and J. Lafferty. Clustering with Bregman divergences. Journal of Machine Learning Research, 6(10), 2005.
[5] L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(No)):463 4422466344222- 2002.
[6] P. I.. Bartlett, S. Boucheron, and G. Lugosi. Model selection and emror estimation. Machine Learning, 48( 48(1))85--11 2002.
[7] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. The Annals of Statistics, 339):1497711577 2005.
[8] G. Beliakov, Т. Calvo, and James. On Lipschitz properties of generated aggregation functions. Fuzzy Sets and Systems, 161(10): 1437-1444 2010.
[9] S. Ben-David A framework for statistical clustering with constant time approximation algo- rithms for k-median and k-means clustering. Machine Learning. 66(2):243-22 257-7,,, 2007.
[10] G. Biau, I. Devroye, and G. Lugosi. On the performance of clustering in Hilbert spaces. IEEE Transactions Information Theory, 54(2):781-790, 2008.
[11] Boucheron. O. Bousquet, and G. Lugosi. Theory of classification: A survey of some recent advances. ESAIM: Probability and Statistics, 9:323-375, 2005.
[12] C. Brownlees, E. Joly, and G. Lugosi. Empirical risk minimization for heavy-tailed losses. The Annals of Statisticx, 2366)255772 2015.
[13] C. Brunet-Saumard, E. Genetay, and A. Saumard. K-FMOM: A robust lloyd-type clustering algorithm based on bootstrap median-of-means. Computational Statistics & Data Analysis, 167:107370, 2022. ISSN 0167-9473. doi: http:://ooi.or// 10.
URL
https://ww..ccie wtt.aa/w....ctc.oo..c...eaaaaaaa
[14] S. Bubeck, N. Cesa- and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59 1)7771, 2013.
[15] S. Chakraborty and S. Das. Detecting meaningful clusters from high-dimensional data: A strongly consistent sparse center-based clustering approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[16] S. Chakraborty and J. Xu. Biconvex clustering. arXiv preprint arXiv:2008.0176/1 2020.
[17] S. Chakraborty, D. Paul, S. Das. and J. Xu. Entropy weighted power k-means clustering. In International Conference on Artificial Intelligence and Statistics, pages 691-701. PMLR, 2020.
[18] A. Deshpande, P. Kacham, and R. Pratap. Robust k-means++. In Conference on Uncertainty in Artificial Intelligence, pages 799-808. PMLR, 2020.
[19] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12661):121--215, 2011. URL http://jmmr. org/ http:/pape//v1vd/vueeeeee httc///chhhhaaaa html
[20] R. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290-330, 1967.

---

[21] A. Fischer, C. Levrard, and C. Brécheteau. Robust Bregman clustering, Annals of Statistics, 2020.
[22] I. Goodfellow, Y. Bengio, A. Courville, and Y. Bengio. Deep learning, volume MIT press Cambridge, 2016.
[23] L. Hubert and P. Arabie. Comparing partitions. Journal of Classification, 2(1): 218, 1985.
[24] A. K. Jain. Data clustering: 50 years beyond k-means. Pattern recognition letters, 31(8): 651-666, 2010.
[25] L. Kaufman and P. J. Rousseeuw. Finding groups in data: an introduction to cluster analysis, volume 344. John Wiley & Sons, 2009.
[26] Y. Klochkov, A. Kroshnin, and N. Zhivotovskiy. Robust k-means clustering for distributions with two moments. arXiv preprint arXiv:2002.02339 2020.
[27] Laforgue, Clémençon, and P. Bertail. On medians of (randomized) pairwise means. In International Conference on Machine Learning, pages 1272-1281, PMLR, 2019.
[28] G. Lecué and M. Lerasle. Learning from MOM's principles: Le Cam's approach. Stochastic Processes and Their Applications, 129(1 0144885-4111 2019.
[29] G. Lecué and M. Lerasle. Robust machine learning by median-of meannsss: theory and practice. Annals of Statistics, (8(2):906-931) 2020.
[30] G. Lecué, M. Lerasle, and T. Mathieu. Robust classification via mom minimization. Machine Learning, 1030)) 2020.
[31] M. Lerasle. Lecture notes: Selected topics on robust statistical learning theory. arXiv preprint 1908. 10761, 2019.
[32] C. Levrard. Nonasymptotic bounds for vector quantization in Hilbert spaces. The Annals of Statistics, 43(2):592-619, 2015.
[33] S. Lloyd. Least squares quantization in PCM. IEEE Transactions Information Theory, 28(2): 129-137, 1982.
[34] G. Lugosi and S. Mendelson. Regularization, sparse recovery, and median-of-means tourna- ments. Bernoulli, 25(3):2055-2106 2019.
[35] MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281-297. Oakland, CA, USA, 1967.
[36] T. Mathieu and S. Minsker. Excess risk bounds robust empirical risk minimization. Informa- tion and Inference: A Jourmal of the IMA, 2021.
[37] S. Minsker. Uniform bounds for robust mean estimators. arXiv preprint arXiv: 182.0338,, 2018.
[38] M. Mohri, A. Rostamizadeh. and A. Talwalkar, Foundations of machine learning. MIT press, 2018.
[39] A. Ng, M. Jordan, and Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14:849- 856, 2001.
[40] R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy. The effectiveness of Lloyd-type methods for the k-means problem. Journal of the ACM (JACM), 19(6):1-22, 2013.
[41] D. Paul, S. Chakraborty, and S. Das. Robust principal component analysis: A median of means approach. arXiv preprint arxiv:2 20..2022.03000 03443, 2021.
[42] D. Paul, S. Chakraborty, and S. Das. On the uniform concentration bounds and large sample properties of clustering with Bregman divergences. Stat, page e360, 2021.
12

---

[43] D. Pollard. Strong consistency of k-means clustering. The Annals of Statistics, 91): 1981.
[44] D. Rodriguez and M. Valdora. The breakdown point the median of means tournament. Statistics & Probability Letters, 153:108-111 11008-11,, 2019.
[45] S. A. Shah and V. Koltun. Robust continuous clustering. Proceedings of the National Academy of Sciences, 114(37):9814 (117)))881498199) 2017.
[46] G. Staerman, P. Laforgue, P. Mozharovskyi. and F. d' Alché Buc. When OT meets MoM: Robust estimation of Wasserstein distance. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 136-144, PMLR, 2021.
[47] K. M. Tan and D. Witten. Statistical properties of convex clustering. Electronic jourrna of statistics, 92))2332, 2015.
[48] M. Teboulle, A unified continuous optimization framework for center-based clustering methods. Journal of Machine Learning Research, 8(1), 2007.
[49] M. J. Telgarsky and S. Dasgupta. Agglomerative Bregman clustering. In 29th International Conference on Machine Learning, ICML 2012, pages 1527-15344 1534, 2012.
[50] M. J. Telgarsky and S. Dasgupta. Moment-based uniform deviation bounds for k-means and friends. Advances in Neural Information Processing Systems, 2013.
[51] Y. Terada. Strong consistency of reduced k-means clustering. Scandinavian Journal of Statistics, 41(4):913-95 91,93, 2014.
[52] Y. Terada. Strong consistency of factorial k-means clustering. Annals of the Institute of Statistical Mathematics, 67(2):335-357, 2015.
[53] V. Vapnik. The nature of statistical learning theory. Springer science business media, 2013.
[54] S. Vassilvitskii and D. Arthur. k-means++: The advantages careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithms,, pages 1027-1035, 2006.
[55] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[56] Xu and K. Lange. Power k-means clustering. International Conference on Machine Learning, pages 6921-6931. PMLR, 2019.
[57] B. Zhang, M. Hsu, and U. Dayal. K-harmonic means data clustering algorithm. Hewlett- Packard Labs Technical Report HPL-1999. 124, 55, 1999.
[58] Z. Zhang, K. Lange, and J. Xu. Simple and scalable sparse k-means clustering via feature ranking, Advances in Neural Information Processing Systems, 33, 2020.
Funding Transparency Statement
The authors did not receive any third-party funding or third-party support during the last months prior to this submission toward pursuing this work. The authors have no financial relationships with entities that could potentially be perceived to influence the submitted work.
13


Reviews:
[{"review_id": "jnMbGij_jt3", "reviewer": "Reviewer_kBcm", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I find this paper interesting and novel. It is very easy to read and the theoretical results are reasonable.\nI only have a few small comments. \n\nQ1. [Non-convexity of the problem]\nIn general, the minimization of $\\Theta$ is a non-convex problem (like the usual k-meams) so algorithm 1 may stuck at a local optimum. \nIt is worth acknowledge this in the paper and mention that we will re-initialize the starting points.\n\n\nQ2. [Possibility to weaken compact support assumption?]\nA 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).\nSo it allows a much heavier tail distribution. \nI am wondering if the same thing is applicable here or not?\n\nUnder the k-means scenario (squares loss), it seems that we may relax the compact support assumption to be some moment conditions.\nAny comments about this?\n\n\nQ3. [Choice of L to be \\log n]\nJust 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). \nIs there any danger of doing so?\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No apparent limitations of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "SzivLiF62T", "reviewer": "Reviewer_w8MY", "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.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI only have some minor questions/comments:\n- 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.\n- 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).\n- Since you are aiming at robustness it would be interesting to compare to a natural robust clustering scheme like $k$-median too.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not explicitly discuss limitations of their work. I see no direct path to negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "MZQPc38lZK", "reviewer": "Reviewer_2EUB", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "No major ethical concerns as far as I can see.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Fgugjoe3B3v", "reviewer": "Reviewer_TRVt", "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.\n\nThe 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.  \nThe 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\nYet, 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.\n\nIn 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.\n\nIn 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.  \n\n### Minor Issues/Suggestions\n* The name $P$ is used for the objective of $k$-means in the introduction and the probability distribution.\n* 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.\n* 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).\n* Algorithm 1: \n   * Step 2: $g_j^(t)\\leftarrow ..$ ?\n   * Step 3: $\\lVert g_j^(t')\\rVert^2_2$ in the denominator, likewise in L113\n* L159: what is $\\Psi(\\Theta,Q)$?\n* L213: what is $O_P(..)$?\n* it should be $\\in \\mathcal{O}(..)$ and so on, not $=\\mathcal{O}(..)$\n* Did you try using synthetic data with more than 5 dimensions? How does it affect the results?\n* The formatting of the proof sketch of Thm 3.4 makes it impossible to read with all the inline math.\n\n*Supplement*\n* L8: $H_{s,p,M}$?\n* Lemma A.2 is not necessary/ well known, I believe\n* Lemma A.3: the $sup$ is missing in the equations and explanations are missing\n* L24: $\\partial J(P_C(\\theta))=..$ and why is it a set? Why is there talk of a subgradient when $d_\\phi$ is differentiable?\n* L25: it should be $-d_\\phi(P_C(\\theta),\\theta)= \\langle \\nabla \\phi.. $ \n\n## Updates after authors response\nThe 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 :)  \n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)