2023/05/22 by Adela DePavia, DePavia, Adela Frances, Olga Medrano Martín del Campo +3
Computer Science · #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2305.13402
openalex publication_date 2023/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error. We first highlight a novel connection between learning partitions and correlation clustering. Then we use this connection to build a Rényi-Ulam style analytical framework for this problem, and prove upper and lower bounds on its worst-case query complexity. Further, we bound the expected performance of a relevant randomized algorithm. Finally, we study the relationship between adaptivity and query complexity for this problem and related variants.