Summary of Active Clustering with Bandit Feedback, by Victor Thuot (mistea) et al.
Active clustering with bandit feedback
by Victor Thuot, Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
First submitted to arxiv on: 17 Jun 2024
Categories
- Main: Machine Learning (stat.ML)
- Secondary: Machine Learning (cs.LG)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The paper investigates the Active Clustering Problem (ACP), where a learner interacts with an N-armed stochastic bandit and aims to uncover a hidden partition of the arms into K groups. The goal is to do so with the smallest budget possible while ensuring a probability of error below a certain constant δ. The authors derive a non-asymptotic lower bound for the budget and introduce the ACB algorithm, which matches this lower bound in most regimes. The paper also shows that there is no computation-information gap in the active setting, improving on uniform sampling strategies. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper looks at how to group things (called arms) into categories based on what’s known about each arm. Imagine you have a set of options and you want to figure out which ones are similar and which are different. The authors come up with a new way to do this that is more efficient than just picking one option at random. This can help us learn more about the world with fewer tries. |
Keywords
* Artificial intelligence * Clustering * Probability
