mlsanityData to 7 Oct 2026

Active clustering with bandit feedback

arXiv 2406.11485 ↗First posted 17 Jun 2024stat.ML cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

We investigate the Active Clustering Problem (ACP). A learner interacts with an N-armed stochastic bandit with d-dimensional subGaussian feedback. There exists a hidden partition of the arms into K groups, such that arms within the same group, share the same mean vector. The learner's task is to uncover this hidden partition with the smallest budget - i.e., the least number of observation - and with a probability of error smaller than a prescribed constant δ. In this paper, (i) we derive a non-asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the active setting.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 19 of its 39 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

19 of 39 references.

References · 19

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  3. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  4. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  5. 2016Statistical and Computational Guarantees of Lloyd's Algorithm and its Variantscited by 52
  6. 2017On Learning Mixtures of Well-Separated Gaussianscited by 30
  7. 2021Clustering Mixtures with Almost Optimal Separation in Polynomial Timecited by 28
  8. 2018Partial recovery bounds for clustering with the relaxed Kmeanscited by 25
  9. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  10. 2015On the Optimal Sample Complexity for Best Arm Identificationcited by 17
  11. 2022Optimal Clustering with Bandit Feedbackcited by 15
  12. 2016Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clusteringcited by 13
7 more
  1. 2019Online k-means Clusteringcited by 13
  2. 2020The Influence of Shape Constraints on the Thresholding Bandit Problemcited by 11
  3. 2021Improved Convergence Guarantees for Learning Gaussian Mixture Models by EM and Gradient EMcited by 11
  4. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  5. 2018Adaptive Sampling for Coarse Rankingcited by 5
  6. 2019Optimal Clustering from Noisy Binary Feedbackcited by 2
  7. 2022On the Role of Channel Capacity in Learning Gaussian Mixture Modelscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 2.

7 papers.

  1. 2024A General Framework for Clustering and Distribution Matching with Bandit Feedbackcited by 7
  2. 2025Clustering Items through Bandit Feedback: Finding the Right Feature out of Manycited by 2
  3. 2025Online Clustering of Data Sequences with Bandit Informationcited by 1
  4. 2025Near Optimal Best Arm Identification for Clustered Banditscited by 0
  5. 2025Locally Differentially Private Thresholding Banditscited by 0
  6. 2026Nonparametric Kernel Clustering with Bandit Feedbackcited by 0
  7. 2026Efficient Clustering in Stochastic Banditscited by 0