Distributionally Robust K-Means Clustering

• URL: http://arxiv.org/abs/2604.11118v1
• Date: Mon, 13 Apr 2026 07:32:36 GMT
• Title: Distributionally Robust K-Means Clustering
• Abstract summary: K-means clustering is notoriously brittle to outliers, distribution shifts, and limited sample sizes.<n>We develop a distributionally robust variant that protects against such pathologies.<n>A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones.
• Score: 18.037323759791658
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.

Related papers

• Cluster-Based Dimensionality Reduction by Nonparametric Distributional Screening [1.4773309126683776]
  We consider dimensionality reduction for high-dimensional observations accompanied by a supplied partition into two or more clusters.<n>The proposed procedure compares the cluster-specific empirical distribution functions through a several-sample Kolmogorov-Smirnov separation statistic.<n>We formalize the resulting marginal cluster support and establish simultaneous finite-sample concentration over all coordinates.
  arXiv  Detail & Related papers  (2026-09-06T21:58:59Z)
• One-Bit Clustering for Two Component Sub-Gaussian Mixture Models [17.177800879292963]
  We propose the first one-bit clustering method for two-component sub-Gaussian mixture models.<n>The method uses only one bit per entry of each sample obtained via a dithered quantizer.
  arXiv  Detail & Related papers  (2026-06-20T04:18:08Z)
• Seed-Guided Semi-Supervised Clustering by A-Contrario Anomaly Detection [0.0]
  This paper introduces a semi-supervised clustering framework grounded in the statistical duality between grouping principles and anomaly detection.<n>We define a cluster as a maximal subset of data points containing no anomalies relative to a null hypothesis of uniform randomness.<n>We evaluate the method on synthetic and real-world benchmarks, including image and text datasets represented through raw, linear-reduced, and neighbourhood-exclusion embeddings.
  arXiv  Detail & Related papers  (2026-06-17T09:08:02Z)
• Nonparametric Kernel Clustering with Bandit Feedback [9.68728390492671]
  Clustering with bandit feedback refers to the problem of partitioning a set of items, where the clustering algorithm can sequentially query items to receive noisy observations.<n>We introduce a kernel-based approach, which allows us to reform the nonparametric problem as the task of clustering the arms according to their kernel mean embeddings in a Hilbert kernel space (RKHS)<n>We introduce a notion of signal-to-noise ratio for this problem that depends on the maximum mean discrepancy (MMD) between the arm distributions and on their variance in the RKHS.
  arXiv  Detail & Related papers  (2026-01-12T13:36:07Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error [10.266928164137635]
  Algorithmic robust statistics has traditionally focused on the contamination model where a small fraction of the samples are arbitrarily corrupted. We consider a recent contamination model that combines two kinds of corruptions: (i) small fraction of arbitrary outliers, as in classical robust statistics, and (ii) local perturbations, where samples may undergo bounded shifts on average. We show that information theoretically optimal error can indeed be achieved in time, under an even emphstronger local perturbation model.
  arXiv  Detail & Related papers  (2024-10-22T17:51:23Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• A provable initialization and robust clustering method for general mixture models [6.806940901668607]
  Clustering is a fundamental tool in statistical machine learning in the presence of heterogeneous data. Most recent results focus on optimal mislabeling guarantees when data are distributed around centroids with sub-Gaussian errors.
  arXiv  Detail & Related papers  (2024-01-10T22:56:44Z)
• Clustering by the Probability Distributions from Extreme Value Theory [32.496691290725764]
  This paper generalizes k-means to model the distribution of clusters. We use GPD to establish a probability model for each cluster. We also introduce a naive baseline, dubbed as Generalized Extreme Value (GEV) k-means. Notably, GEV k-means can also estimate cluster structure and thus perform reasonably well over classical k-means.
  arXiv  Detail & Related papers  (2022-02-20T10:52:43Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.