Optimal Clustering with Noisy Queries via Multi-Armed Bandit
Authors: Jinghui Xia, Zengfeng Huang
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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( n(k+log n)/δ2 + poly(k, 1/δ , log n)) queries is proposed. Moreover, we prove a new lower bound of Ω( n log n/δ2 ) |
| Researcher Affiliation | Academia | 1School of Data Science, Fudan University, Shanghai, China 2Shanghai Key Lab of Intelligent Information Processing. Correspondence to: Zengfeng Huang <huangzf@fudan.edu.cn>. |
| Pseudocode | Yes | Algorithm 1 Sub Cluster(V, k, δ, b): sub-clusters recovery, Algorithm 2 True Cluster Id(u, X1, ..., Xk, δ, α), Algorithm 3 Cluster Verify(v, B), Algorithm 4 Bal Noisy Clustering(V, k, δ, b), Algorithm 5 Gap SBM(T, h, δ), Algorithm 6 Noisy Clustering(V, k, δ), Algorithm 7 A s: algorithm for BAIF. |
| Open Source Code | No | The paper does not contain any statement about making its source code available or provide a link to a code repository. |
| Open Datasets | No | The paper describes a theoretical framework for clustering with noisy queries and does not involve real-world datasets or a training phase. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental setups with data splits (train/validation/test). |
| Hardware Specification | No | The paper describes theoretical algorithms and proofs, and does not mention any hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide details on specific software dependencies or their version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |