# Optimal Clustering with Noisy Queries via Multi-Armed Bandit

arXiv: https://arxiv.org/abs/2207.05376 · HTML: https://mlsanity.com/paper/2207.05376/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 10 of 10)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Approximate Correlation Clustering Using Same-Cluster Queries](https://mlsanity.com/paper/1712.06865/) (2017)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [Query K-means Clustering and the Double Dixie Cup Problem](https://mlsanity.com/paper/1806.05938/) (2018)
- [Learning to Cluster via Same-Cluster Queries](https://mlsanity.com/paper/2108.07383/) (2021)

## Built on by (most cited first, 5 of 5)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)

## Abstract (arXiv)

Motivated by many applications, we study clustering with a faulty oracle. In this problem, there are n items belonging to k unknown clusters, and the algorithm is allowed to ask the oracle whether two items belong to the same cluster or not. However, the answer from the oracle is correct only with probability frac12+fracδ2. The goal is to recover the hidden clusters with minimum number of noisy queries. Previous works have shown that the problem can be solved with O(fracnklog nδ2 + poly(k,frac1δ, log n)) queries, while Omega(fracnkδ2) queries is known to be necessary. So, for any values of k and δ, there is still a non-trivial gap between upper and lower bounds. In this work, we obtain the first matching upper and lower bounds for a wide range of parameters. In particular, a new polynomial time algorithm with O(fracn(k+log n)δ2 + poly(k,frac1δ, log n)) queries is proposed. Moreover, we prove a new lower bound of Omega(fracnlog nδ2), which, combined with the existing Omega(fracnkδ2) bound, matches our upper bound up to an additive poly(k,frac1δ,log n) term. To obtain the new results, our main ingredient is an interesting connection between our problem and multi-armed bandit, which might provide useful insights for other similar problems.