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

CREATORRachel S. Y. Teo 1 P. N. Karthik 2 Ramya Korlakai Vinayak 3 Vincent Y. F. Tan 1
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-05690

Browse the full library · About the Tower of Babel