Nonparametric Kernel Clustering with Bandit Feedback

• URL: http://arxiv.org/abs/2601.07535v1
• Date: Mon, 12 Jan 2026 13:36:07 GMT
• Title: Nonparametric Kernel Clustering with Bandit Feedback
• Authors: Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar, Nicolas Verzelen,
• Abstract summary: 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.
• Score: 9.68728390492671
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering with bandit feedback refers to the problem of partitioning a set of items, where the clustering algorithm can sequentially query the items to receive noisy observations. The problem is formally posed as the task of partitioning the arms of an N-armed stochastic bandit according to their underlying distributions, grouping two arms together if and only if they share the same distribution, using samples collected sequentially and adaptively. This setting has gained attention in recent years due to its applicability in recommendation systems and crowdsourcing. Existing works on clustering with bandit feedback rely on a strong assumption that the underlying distributions are sub-Gaussian. As a consequence, the existing methods mainly cover settings with linearly-separable clusters, which has little practical relevance. We introduce a framework of ``nonparametric clustering with bandit feedback'', where the underlying arm distributions are not constrained to any parametric, and hence, it is applicable for active clustering of real-world datasets. We adopt a kernel-based approach, which allows us to reformulate the nonparametric problem as the task of clustering the arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the KABC algorithm with theoretical correctness guarantees and analyze its sampling budget. 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. Our algorithm is adaptive to this unknown quantity: it does not require it as an input yet achieves instance-dependent guarantees.

Related papers

• 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)
• Cluster truncated Wigner approximation for bond-disordered Heisenberg spin models [0.0]
  Cluster Truncated Wigner Approximation (cTWA) applied to quench dynamics in bond-disordered Heisenberg spin chains with power-law interactions. We develop a discrete sampling scheme for the initial Wigner function, as an alternative to the originally introduced scheme based on Gaussian approximations.
  arXiv  Detail & Related papers  (2024-07-01T18:00:06Z)
• Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers [24.88026399458157]
  Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur. The key to secure machines in distributed learning is resilient aggregation mechanisms.
  arXiv  Detail & Related papers  (2023-12-20T08:36:55Z)
• Tight integration of neural- and clustering-based diarization through deep unfolding of infinite Gaussian mixture model [84.57667267657382]
  This paper introduces a it trainable clustering algorithm into the integration framework. Speaker embeddings are optimized during training such that it better fits iGMM clustering. Experimental results show that the proposed approach outperforms the conventional approach in terms of diarization error rate.
  arXiv  Detail & Related papers  (2022-02-14T07:45:21Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• 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)
• Recovery Guarantees for Kernel-based Clustering under Non-parametric Mixture Models [26.847612684502998]
  We study the statistical performance of kernel-based clustering algorithms under non-parametric mixture models. We establish a key equivalence between kernel-based data-clustering and kernel density-based clustering.
  arXiv  Detail & Related papers  (2021-10-18T17:23:54Z)
• Correlation Clustering Reconstruction in Semi-Adversarial Models [70.11015369368272]
  Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering corrupted by random noise and adversarial modifications.
  arXiv  Detail & Related papers  (2021-08-10T14:46:17Z)
• Implicit Distributional Reinforcement Learning [61.166030238490634]
  implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs) Semi-implicit actor (SIA) powered by a flexible policy distribution. We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
  arXiv  Detail & Related papers  (2020-07-13T02:52:18Z)
• A generalized Bayes framework for probabilistic clustering [3.3194866396158]
  Loss-based clustering methods, such as k-means and its variants, are standard tools for finding groups in data. Model-based clustering based on mixture models provides an alternative, but such methods face computational problems and large sensitivity to the choice of kernel. This article proposes a generalized Bayes framework that bridges between these two paradigms through the use of Gibbs posteriors.
  arXiv  Detail & Related papers  (2020-06-09T18:49:32Z)

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.