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

AI summary

Overview

Research area: Unsupervised machine learning / statistical machine learning (stat.ML) — specifically robust convex clustering.

Technical level: Advanced. The paper combines convex optimization, a Median-of-Means (MoM) estimator, Hanson-Wright-type concentration inequalities, and finite-sample error bounds, alongside empirical benchmarks.

One-sentence scope: The paper proposes COMET (Convex Clustering with Median of Mean Estimator and Adam Optimization), a robust convex-clustering framework that uses the Median-of-Means estimator and a clipped pairwise penalty to resist noise and outliers, establishes weak consistency under stated conditions, and benchmarks it against six clustering baselines on real and simulated data.

What This Paper Is About

Convex clustering turns clustering into a convex optimization problem with a unique global solution, avoiding the initialization sensitivity and the need to pre-specify the number of clusters that plague k-means and its variants. However, convex clustering struggles on high-dimensional data with noise and outliers, and strong fusion regularization (controlled by the tuning parameter) can merge outliers into genuine clusters. This paper's goal is to make convex clustering outlier-resistant by embedding a Median-of-Means objective and a distance-clipping step into the convex clustering loss, and by optimizing the resulting non-convex objective with ADAM gradient descent.

Key Contributions

1. Robust convex clustering framework (COMET): The authors integrate the Median-of-Means estimator into the convex clustering paradigm, adding a clipped penalty of the form min{μ, ||u_i - u_j||²₂} on weighted pairwise centroid distances, and develop a dedicated algorithm (Algorithm 1) using ADAM gradient descent. The method does not require the number of clusters as prior input.
2. Theoretical guarantees: They establish uniform deviation bounds and concentration inequalities under standard regularity assumptions (Theorem 1), plus two corollaries covering convergence of the centroid estimates.
3. Computational complexity comparison: They show COMET has complexity O(Nnkd), matching Robust Convex Clustering and improving on Convex Clustering O(N(n²d + dε)) and Robust Continuous Clustering O(N(n²d + nkd)).
4. Empirical validation: Simulation studies and experiments on real-life datasets (including a case study on the Brain microarray dataset under 0%, 5%, 10%, 15% and 20% noise) show COMET outperforming competing approaches in robustness and efficiency under data contamination.

Main Findings

• Consistency result: Corollary 1.1 states that if ||D_C(i,j) u||₂ ≤ C for all 1 ≤ i,j ≤ n, |ℰ| ≤ kn, γ' ≥ M/(ndb√n) and d = o(n), then 1/(2ndb) ||û - u||² with respect to the estimated selection matrix converges in probability to 0 as n, d → ∞.
• Rate result: Corollary 1.2 states that under the same conditions, 1/(2ndb) ||û - u||² = O(1/√n), as reported in the paper.
• Uniform deviation bound (Theorem 1): With probability at least 1 - δ, the scaled estimation error is bounded by terms involving M², d, b, n, γ', |ℰ| and log(1/δ), provided γ' ≥ M/(ndb√n).
• Complexity advantage: COMET runs in O(Nnkd), the same order as Robust Convex Clustering and better than Convex Clustering (O(N(n²d + dε))) and Robust Continuous Clustering (O(N(n²d + nkd))) as tabulated in the paper.
• Real-life results at 10% noise (Table II): COMET records ARI/AMI of 0.97/0.90 on Newthyroid (k = 3), 0.87/0.76 on Wisconsin (k = 2), 0.79/0.80 on Wine (k = 3), 0.81/0.86 on Dermatology (k = 6), 0.71/0.69 on Lung-Discrete (k = 7), and 0.73/0.81 on ORLRaws10p (k = 10). Except for Wine (k-means marked ∼, statistically similar) and one Wisconsin comparison (RConv, ∼), all competing results are marked as significantly different from the best performer.
• Estimated cluster counts: COMET's k* values were 4.14 ± 0.36 (Newthyroid, true k = 3), 3.00 ± 0.00 (Wisconsin, k = 2), 4.64 ± 0.84 (Wine, k = 3), 5.85 ± 0.53 (Dermatology, k = 6), 9.21 ± 0.80 (Lung-Discrete, k = 7) and 14 ± 0.00 (ORLRaws10p, k = 10).
• Brain dataset case study (Table III): On this microarray dataset with 42 instances and 5597 features across 5 categories (10 medulloblastomas, 10 malignant gliomas, 10 AT/RT, 4 normal cerebellums, 8 supratentorial PNETs), COMET maintains ARI above 0.6 at every noise level — ARI of 0.65, 0.66, 0.66, 0.66 and 0.65 at 0%, 5%, 10%, 15% and 20% noise respectively — while Robust Continuous Clustering reports 0.00 ARI at every noise level.
• Noise-detection behavior (Figure 1): On a benchmark setup with k = 5, N = 1000, γ = 5000 and 20% noise, decreasing μ (0.4, 0.2, 0.12) lets the method flag progressively more noise points as outliers, though some deeply embedded points remain undetected.
• Statistical significance: Wilcoxon-Rank Sum tests are used to check whether COMET's ARI and AMI are significantly higher than those of the other algorithms (details in the supplementary material).
• Ablation studies: Sensitivity analysis of the hyperparameter γ, hyperparameter tuning on the Wisconsin Breast Cancer dataset, and an ablation on the NewThyroid dataset are reported in the supplementary material.

Methodology in Plain English

The authors start from the standard convex clustering idea: each data point gets its own "agent" position, and the method pulls agents together through a weighted penalty on pairwise distances, with weights built from a k-nearest-neighbour graph and a Gaussian similarity w_ij = 1_{ij,k} e^{-φ||x_i − x_j||²}. To make the fit robust, they replace the usual average of per-point costs with a Median-of-Means objective: the data indices are randomly partitioned into l = O(n) bins, each holding exactly b = floor(n/l) points, and the cost is taken as the median of the per-bin average losses. Because outliers can only contaminate a fraction of the bins, the median suppresses their influence. They further clip the pairwise penalty at a threshold μ, using min{μ, ||u_i − u_j||²₂} instead of the raw squared distance, so that distant points or clusters cannot dominate the objective.

The final cost function combines the Median-of-Means term with this clipped fusion penalty. Since the objective is non-convex, it is minimized with the ADAM gradient descent algorithm over N iterations; the gradient only includes points in the selected median bin and pairs whose distance is below μ. After optimization, the agents are turned into clusters by building a graph where two agents are adjacent if their distance is below η₁, taking each connected component as a cluster, and merging any clusters with fewer than half the average cluster size into a single cluster flagged as noise. The hyperparameters are N, k, φ, γ, μ, η₁ (plus ADAM's β₁ and β₂, with the exact update rule in the supplementary material).

Why This Matters

Impact on research: The paper connects two lines of work — convex clustering and median-of-means robustness — and supplies finite-sample concentration bounds plus a weak consistency result, offering a template for reasoning about robust cluster estimation when data are contaminated. It also provides an automatic way to detect and isolate outliers via the μ threshold and the small-cluster merging rule, and it does not require the number of clusters as an input, unlike k-means, MoM k-means and Robust Bregman k-means.

Real-world applications (as cited or demonstrated in the paper):

• Customer segmentation.
• Image analysis.
• Anomaly detection, including flagging outliers via the noise cluster.
• Gene-expression / microarray analysis, demonstrated on the Brain tumor dataset (42 patients, 5597 features, 5 tumor categories) and the Wisconsin breast cancer dataset.

Industry relevance: Clustering under noisy, high-dimensional, contaminated data is common in medical diagnostics, bioinformatics and general analytics pipelines; a method that scales as O(Nnkd) rather than O(N(n²d)) and that reports its own cluster count is attractive for large-scale deployments. The authors note that COMET is "better or at least on par" with recent widely used robust clustering algorithms in computational cost.

Future Directions

• Choosing the cost function systematically: The authors state that while they tested specific noise distributions for synthetic data, a systematic method for selecting an appropriate cost function still needs to be developed.
• Non-random noise patterns: The paper notes it remains obscure how the cost function should be modified if noise follows a definite pattern rather than being randomly distributed.
• Higher-dimensional data: The consistency proof assumes d = o(n); the authors say modifications to the clustering procedure are needed for higher-dimensional datasets.
• Broader framework extensions: Given the flexibility of the framework, the authors suggest other possibilities can be explored by incorporating different methods for different steps of the pipeline.

Target Audience

This paper is best suited to researchers and graduate students in statistical machine learning, convex optimization and robust statistics who work on clustering theory and algorithms. Practitioners in bioinformatics or medical data analysis — particularly those handling high-dimensional, noisy datasets with outliers — will also find the empirical results and the automatic cluster-count and outlier-detection behavior relevant, provided they are comfortable with the algorithmic and hyperparameter setup (N, k, φ, γ, μ, η₁).

Authors’ 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-means and its wide family of variants are still widely used, all of them require the number of clusters 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 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.