Almost Asymptotically Optimal Active Clustering Through Pairwise Observations
Rachel S. Y. Teo 1 P. N. Karthik 2 Ramya Korlakai Vinayak 3 Vincent Y. F. Tan 1 · 2026
Read Almost Asymptotically Optimal Active Clustering Through Pairwise Observations by Rachel S. Y. Teo 1 P. N. Karthik 2 Ramya Korlakai Vinayak 3 Vincent Y. F. Tan 1 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-05690.txt.
Description
Grouping items by asking noisy yes or no questions about pairs is the task of active clustering, where each answer costs time. Rachel Teo and 3 co-authors study how few queries can suffice when the number of groups is unknown. At each step an agent picks a pair; the answer is biased toward yes for pairs in the same group and toward no otherwise.
Using a change of measure argument, the authors derive a lower bound on the queries needed for a target confidence. They then design an algorithm whose stopping rule uses a generalized likelihood ratio statistic against a threshold. A cheaper variant keeps the method practical, with a gap to the bound within a constant factor. The work speaks to learning theorists and to practitioners who cluster with costly judgments.
Catalog record
| CREATOR | Rachel S. Y. Teo 1 P. N. Karthik 2 Ramya Korlakai Vinayak 3 Vincent Y. F. Tan 1 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-05690