Nonparametric Kernel Clustering with Bandit Feedback

Victor Thuot; Sebastian Vogt; Debarghya Ghoshdastidar; Nicolas Verzelen

stat.MLJan 12, 2026

Nonparametric Kernel Clustering with Bandit Feedback

Authors: Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar, Nicolas Verzelen

Organizations: MISTEA, UMPA-ENSL · INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France · LRR-TUM · Technical University of Munich, Munich, Germany · MISTEA

Abstract

Clustering with bandit feedback refers to the problem of partitioning the arms of an $N$ -armed stochastic bandit according to their underlying distributions, based on noisy observations collected sequentially and adaptively. This setting has attracted growing interest for its applicability in recommendation systems, crowdsourcing, and adaptive trials. Existing works rely on the strong assumption that arm distributions are sub-Gaussian, which can only distinguish arms whose distributions differ in mean - missing realistic settings where distributional differences lie in shape or higher moments. % We introduce a framework of nonparametric clustering with bandit feedback, free of any parametric assumptions regarding the arm distributions. We adopt a kernel-based approach and reformulate the problem as clustering arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the \kabc\ algorithm, prove that it is $δ$ -PAC, and derive a non-asymptotic high-probability upper bound on its sampling complexity. The bound is governed by a variance-aware signal-to-noise ratio defined as the minimum over pairs of arms in distinct clusters of the ratio between their squared MMD and their RKHS variance. \kabc\ achieves instance-dependent guarantees while being adaptive to this unknown ratio. We validate our approach empirically on synthetic and real-world datasets, demonstrating that \kabc\ succeeds in distributional clustering settings where mean-based methods fail.

Explore similar work

Apr 13, 2026

Distributionally Robust K-Means Clustering

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.

Vikrant Malik, Taylan Kargin, Babak Hassibi

Department of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125 USA. · California Institute of Technology, Pasadena, CA 91125 USA · Massachusetts Institute of Technology, Cambridge, MA 02139 USA.

Clustering Distribution Shift Robustness Wasserstein Distributionally Robust Optimization

Ask PDF

Sep 17, 2024

Clustering with Non-adaptive Subset Queries

Recovering the underlying

k

-clustering of a set

U

n

points by asking pair-wise same-cluster queries has garnered significant interest in the past few years. Given a query

S \subset U

|S|=2

, the oracle returns "yes" if the points are in the same cluster and "no" otherwise. For adaptive algorithms, the query complexity is known to be

Θ(nk)

, while non-adaptive algorithms are extremely limited: even for

k=3

, such algorithms require

Ω(n^2)

queries, matching the trivial upper bound. However, non-adaptivity is highly desirable since it allows queries to be asked in parallel. To break the quadratic barrier for non-adaptive queries, we study a natural generalization of this problem to subset queries for

|S|>2

, where the oracle returns the number of clusters intersecting

S

. Previous work obtained an

O(n)

query adaptive algorithm, but the realm of non-adaptive algorithms remained completely unknown. In this paper, we give the first non-adaptive algorithms for clustering with subset queries. Our main result is a non-adaptive algorithm making

O(n \log k \cdot (\log k + \log\log n)^2)

queries, improving to

O(n \log \log n)

when

k

is constant. In addition to non-adaptivity, we make other practical considerations, such as enforcing a bound,

s

, on the query size. We show

Ω(\max(n^2/s^2,n))

queries are necessary and obtain algorithms making

\smash{\widetilde{O}(n^2k/s^2)}

queries for any

s \leq \sqrt{n}

and

\smash{\widetilde{O}(n^2/s)}

queries for any

s \leq n

. Finally, we obtain improved upper bounds when the clusters are roughly balanced, and when the algorithm is allowed two rounds of adaptivity.

Hadley Black, Euiwoong Lee, Arya Mazumdar +1

CUNY Baruch College · University of Michigan · UC San Diego

Query Complexity Clustering

Ask PDF

Aug 11, 2025

Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters

Clustering algorithms often assume all features contribute equally to the data structure, an assumption that usually fails in high-dimensional or noisy settings. Feature weighting methods can address this, but most require additional parameter tuning. We propose SHARK (Shapley Reweighted

k

-means), a feature-weighted clustering algorithm motivated by the use of Shapley values from cooperative game theory to quantify feature relevance, which requires no additional parameters beyond those in

k

-means. We prove that the

k

-means objective can be decomposed into a sum of per-feature Shapley values, providing an axiomatic foundation for unsupervised feature relevance and reducing Shapley computation from exponential to polynomial time. SHARK iteratively re-weights features by the inverse of their Shapley contribution, emphasising informative dimensions and down-weighting irrelevant ones, and is equivalent to replacing the arithmetic mean of feature dispersions with their harmonic mean. Experiments on synthetic and real-world data sets show that SHARK consistently matches or outperforms existing methods, achieving superior robustness and accuracy, particularly in scenarios where noise may be present. Software: https://github.com/rickfawley/SHARK.

Richard J. Fawley, Renato Cordeiro de Amorim

School of Computer Science and Electronic Engineering, University of Essex, Wivenhoe, UK.

Clustering Unsupervised Clustering

Ask PDF

Abstract

Explore similar work

Distributionally Robust K-Means Clustering

Clustering with Non-adaptive Subset Queries

Shapley-Inspired Feature Weighting in kkk-means with No Additional Hyperparameters

Shapley-Inspired Feature Weighting in $k$ -means with No Additional Hyperparameters