Convex Clustering Redefined: Robust Learning with the Median of Means Estimator

Koustav Chowdhury 1 , Bibhabasu Mandal 1 , Sagar Ghosh 2 , Swagatam Das 3 , Debolina Paul 4 , and Saptarshi Chakraborty 5 · 2025

Read Convex Clustering Redefined: Robust Learning with the Median of Means Estimator by Koustav Chowdhury 1 , Bibhabasu Mandal 1 , Sagar Ghosh 2 , Swagatam Das 3 , Debolina Paul 4 , and Saptarshi Chakraborty 5 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-14784.txt.

Introduction

Sourav De, Koustav Chowdhury, and five co-authors make convex clustering tougher against noise and outliers. Convex clustering recasts grouping as a convex optimization problem, which guarantees one global answer and avoids guessing the number of groups up front. Still, high-dimensional noisy data can pull its clusters apart or fuse them wrongly.

The new approach pairs the convex method with a median-of-means estimator, a robust way to average that resists bad data points. Strong fusion penalties that once blocked good cluster formation are handled more safely. The authors aim at stable, compact clusters in messy real data, where classic methods such as k-means also suffer from touchy starting points.

Catalog record

CREATORKoustav Chowdhury 1 , Bibhabasu Mandal 1 , Sagar Ghosh 2 , Swagatam Das 3 , Debolina Paul 4 , and Saptarshi Chakraborty 5
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-14784

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convex Clustering Redefined: Robust Learning with the Median of Means Estimator Koustav Chowdhury 1 , Bibhabasu Mandal 1 , Sagar Ghosh 2 , Swagatam Das 3 , Debolina Paul 4 , and Saptarshi Chakraborty 5 Abstract Clustering approaches that utilize convex loss functions have recently attracted growing interest in the formation of compact data clusters. Although classical methods like k − k- means and its wide family of variants are still widely used, all of them require the number of clusters ( k k ) to be supplied as input and many are notably sensitive to initialization. Convex clustering provides a more stable alternative by formulating the clustering task as a convex optimization problem, ensuring a unique global solution. However, it faces challenges in handling high-dimensional data, especially in the presence of noise and outliers. Additionally, strong fusion regularization, controlled by the tuning parameter, can hinder effective cluster formation within a convex clustering framework. To overcome these challenges, we introduce a robust approach that integrates convex clustering with the Median of Means (MoM) estimator, thus developing an outlier-resistant and efficient clustering framework that does not necessitate a prior knowledge of the number of clusters. By leveraging the robustness of MoM alongside the stability of convex clustering, our method enhances both performance and efficiency, especially on large-scale datasets. Theoretical analysis demonstrates weak consistency under specific conditions, while experiments on synthetic and real-world datasets validate the method’s superior performance compared to existing approaches. Sourav De 1 , [email protected], [email protected], [email protected], [email protected],[email protected], [email protected], [email protected] Github Repository: https://tinyurl.com/2v3dx75x Benchmark Dataset (CC BY-NC-ND 4.0): https://tinyurl.com/2zatwkf3 ASU Datasets (GPLv2): https://tinyurl.com/49n36ume Micro-array Datasets: https://tinyurl.com/2f2pjz7j Brain Dataset: https://tinyurl.com/4ntav7b9 Wisconsin Dataset: https://tinyurl.com/58wxjha5 I Introduction Clustering is a fundamental task in unsupervised learning, aiming to organize unlabeled data into coherent groups for better interpretation and downstream applications. It plays a critical role in diverse areas such as customer segmentation [ 21 ] , image analysis [ 32 ] , and anomaly detection [ 11 ] . Traditional algorithms, such as k -means, approach clustering as a non-convex optimization problem [ 28 ] , typically solved using greedy heuristics. Although computationally efficient and widely used, these methods suffer from several well-known limitations [ 20 ] : they require pre-specifying the number of clusters [ 44 , 16 ] , are sensitive to initialization [ 33 , 51 ] , and degrade in performance in high-dimensional spaces or when the data contains noise and outliers [ 48 , 12 , 6 ] . To overcome these challenges, convex relaxations of non-convex clustering problems have gained significant attention [ 45 ] . A prominent example is convex clustering (or sum-of-norms clustering), which enjoys strong theoretical guarantees such as global optimality and convergence, while remaining broadly applicable in practice [ 35 , 19 , 27 ] . Given a data matrix \mathbf{X}\in\mathbb{R}^{n\times d} , where each row represents a data point in d -dimensional Euclidean space, convex clustering solves the following objective: \min_{\mathbf{u}}\frac{1}{2}\left[\|\mathbf{x}_{i.}-\mathbf{u}_{i.}\|_{2}^{2}+\gamma\sum_{i,j}\theta_{ij}\|\mathbf{u}_{i.}-\mathbf{u}_{j.}\|_{p}^{2}\right], (I.1) where \mathbf{u}_{i.} denotes the i -th row of \mathbf{u} , \theta_{ij} are edge weights, and \|\cdot\|_{p} is the \ell^{p} norm. The first term encourages each point to remain close to its centroid, while the second term (controlled by tuning parameter \gamma>0 ) promotes fusion across centroids, effectively determining the number of clusters [ 9 ] . Although convex clustering is effective even in large-sample settings [ 39 ] , strong regularization can lead to undesirable merging of outliers with genuine clusters, especially in high-dimensional data [ 13 ] . This paper focuses on addressing the robustness challenges of clustering in the presence of noise and outliers. Robust methods can mitigate these effects by either discarding outlier features [ 47 ] or directly controlling the influence of anomalous data points. One powerful approach is the Median-of-Means (MoM) estimator, which provides strong robustness and concentration guarantees under mild assumptions [ 29 , 25 , 24 , 23 , 2 ] . Related work by [ 34 ] further unifies robust center-based clustering under general dissimilarity measures. Consider n data points \mathbf{x}_{1},\dots,\mathbf{x}_{n}\in\mathbb{R}^{d} to be grouped into k clusters. Each cluster is represented by a centroid \boldsymbol{\theta}_{j}\in\mathbb{R}^{d} , and the set of centroids forms a matrix \mathbf{\Theta}\in\mathbb{R}^{k\times d} . Using a Bregman divergence d_{\phi}(\cdot,\cdot) as the dissimilarity measure, where \phi:\mathbb{R}^{d}\to\mathbb{R} is a differentiable convex function, clustering can be formulated as f_{\boldsymbol{\Theta}}(\mathbf{x}_{1},\dots,\mathbf{x}_{n})=\frac{1}{n}\sum_{i=1}^{n}\Psi_{\alpha}(d_{\phi}(\mathbf{x}_{i},\boldsymbol{\theta}_{1}),\dots,d_{\phi}(\mathbf{x}_{i},\boldsymbol{\theta}_{k})), (I.2) where \Psi_{\alpha}:\mathbb{R}^{k}_{\geq 0}\to\mathbb{R}_{\geq 0} is a non-decreasing function, \Psi_{\alpha}(0)=0 , and \alpha is a hyperparameter. Different choices of \phi and \Psi_{\alpha} recover well-known clustering algorithms such as k -means, power k -means, and k -harmonic-means. Instead of directly minimizing ( I.2 ), MoM partitions the data into L disjoint subsets B_{1},\dots,B_{L} , each containing b samples, and optimizes a robust median-based objective: \text{MoM}^{n}_{L}(\boldsymbol{\Theta})=\text{Median}\left(\frac{1}{b}\sum_{i\in B_{1}}f_{\boldsymbol{\Theta}}(\mathbf{x}_{i}),\dots,\frac{1}{b}\sum_{i\in B_{L}}f_{\boldsymbol{\Theta}}(\mathbf{x}_{i})\right). (I.3) Because outliers typically contaminate only a fraction of the partitions, the median effectively suppresses their influence, ensuring robustness even in adversarial settings. Formal breakdown-point analyses of MoM estimators support this intuition [ 41 , 15 ] . To demonstrate our method, Figure 1 illustrates results on a benchmark dataset with k=5 , N=1000 , \gamma=5000 , 20\% noise, and varying \mu . Outliers near the boundary are successfully isolated. When any pair \mu_{i},\mu_{j} exceeds the separation threshold \mu , the connecting edge is dropped, preventing spurious merging. While most outliers are identified, some deeply embedded points remain undetected. (a) Dataset (b) \mu=0.4 (c) \mu=0.2 (d) \mu=0.12 Fig. 1 : Figure 1(a) shows the original dataset in yellow, with 20\% added noise represented by blue dots. As \mu decreases, our method progressively identifies more noise points as outliers, which are marked by purple dots in Figures 1(b) , 1(c) , and 1(d) respectively. II Contributions In this paper, we present a novel clustering framework that extends convex clustering with enhanced robustness using the Median-of-Means (MoM) estimator. Our main contributions are summarized below: • Robust Convex Clustering Framework: We propose a new clustering method that integrates the MoM estimator into the convex clustering paradigm, effectively mitigating the adverse impact of outliers and noisy data. We also develop a dedicated algorithm for the proposed framework, ensuring practical applicability and computational efficiency. • Theoretical Guarantees: We establish uniform deviation bounds and concentration inequalities under standard regularity assumptions, providing strong theoretical reliability for our method. • Empirical Validation: Extensive simulation studies demonstrate that our method consistently outperforms conventional clustering approaches, particularly in terms of robustness and efficiency under data contamination. III Related Works Convex Clustering and Semi-definite Programming: Since the introduction of Convex Clustering by [ 36 ] , various extensions and perspectives have been explored [ 26 ] , [ 18 ] , [ 52 ] . Pelckmans and De Moor introduced a shrinkage term to induce sparsity between centroids, enabling hierarchical clustering by tuning the trade-off parameter. [ 19 ] propose a convex relaxation-based clustering algorithm that efficiently traces a regularization path, achieves state-of-the-art performance on non-convex clusters, and simultaneously infers a hierarchical tree structure from the data. In [ 7 ] , two optimization approaches — ADMM and a variant of AMA were introduced to solve convex clustering problems for practical applications. Additionally, convex relaxations of the k- Means problem via Semi-Definite Programming (SDP) have been developed [ 37 , 1 , 30 ] , replacing the k-

Read the complete text