# Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries
## 4 Same Cluster Queries
### An Algorithm Using Few SCQs
#### 4.2.1 The Algorithm
Specifically, for any two clusters and two corresponding centroids, say \(y\in C_{i}^{*}\) and \(z\in C_{j}^{*}\), we use a low-cost comparison to check whether \(d(x,y)<d(x,z)\). Fix a subset of \(C^{\prime}\leq C\) of centroids in each of the \(k\) clusters. Let \(W_{ij}\) denote the number of \"wins\" of \(C_{i}^{*}\) vs \(C_{j}^{*}\), that is, the number of pairs of fixed centroids \((y,z)\) with \(y\in C_{i}^{*}\) and \(z\in C_{j}^{*}\) such that the low-cost comparison '\(d(x,z)>d(x,y)\)' is correct (i.e., the strict inequality holds according to Corollary 3). Since \(W_{ij}\) is the sum of \(N=\binom{C^{\prime}}{2}\) Bernoulli random variables such that \(\Pr[X_{e}=1]\geq 1-p\), standard Chernoff bounds imply the following:  
For \(C_{i}^{*}\) being the correct cluster of \(x\) and any other cluster \(C_{j}^{*}\),  
\[\Pr[W_{ij}\leq N/2]\leq e^{-Nf_{p}}, \tag{10}\]  
where \(N=\binom{C^{\prime}}{2}\), and \(f_{p}\) is a constant depending on \(p\in(0,1/2)\) only. Proof. : For \(\mu=E[W_{ij}]\geq(1-p)N\) and for \(\delta=1-\frac{1}{2(1-p)}\), we have (note that \(\delta>0\) since \(p<1/2\))  
\[\Pr\big{[}W_{ij}\leq N/2\big{]}= \Pr[W_{ij}\leq(1-\delta)(1-p)N]\] \[\leq \Pr[W_{ij}\leq(1-\delta)\mu]\] \[\leq e^{-\frac{\mu^{2}}{2}}\leq e^{-\frac{(1-p)N^{2}}{2}}\]  
where the first and third inequalities are from \(\mu\geq(1-p)N\) and the second inequality is the Chernoff bound. Finally, note that  
\[\mathcal{C}(\mathbf{p})\leq\frac{H_{k}}{p_{1}}=O(\frac{\log k}{p_{1}});\qquad \mathcal{C}(\mathbf{p})\leq\sum_{j=1}^{k}\frac{1}{j\cdot p_{j}};\qquad\mathcal{ C}(\mathbf{p})\leq\sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\]0  
for \(p=1/2-\epsilon\). Thus, \(f_{p}=\frac{\epsilon^{2}}{1+2\epsilon}\). By the union bound, the probability that the correct cluster \(C_{i}^{*}\) of \(x\) wins against all other clusters is at least \(1-ke^{-Nf_{p}}\). In particular, since in the previous step we have chosen \(C=\Omega(\log n)\), we can choose a suitable \(C^{\prime}=\Theta(\sqrt{C})=\Theta(\sqrt{\log n})\) such that \(N=\binom{C^{\prime}}{2}\geq\frac{3\log n}{f_{p}}=\Omega(\log n)\) and the fail probability is bounded as \(ke^{-Nf_{p}}\leq 1/n^{2}\). In order to find the optimal cluster for \(x\), we use a simple \"tournament\" where we compare the current best cluster with the next one that we did not yet consider. Comparing two clusters costs \(O(N)=O(C)\) comparisons, and thus overall we use \(O(kC^{2})\) low-cost operations only for every \(x\). Putting things together, we have the following:  
**Observation 7**. : _In Step 3, with a probability of at least \(1-\frac{1}{n}\), all points are assigned to their optimal clusters using \(O(knC)=O(kn\log n)\) low-cost operations only._  
Putting Things Together (Proof of Theorem 5)  
The number of SCQs and the high-low cost complexity of the three steps are as follows:  
Step 1: \[\mathcal{C}(\mathbf{p})\leq\frac{H_{k}}{p_{1}}=O(\frac{\log k}{p_{1}});\qquad \mathcal{C}(\mathbf{p})\leq\sum_{j=1}^{k}\frac{1}{j\cdot p_{j}};\qquad\mathcal{ C}(\mathbf{p})\leq\sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\]1 Step 2: \[\mathcal{C}(\mathbf{p})\leq\frac{H_{k}}{p_{1}}=O(\frac{\log k}{p_{1}});\qquad \mathcal{C}(\mathbf{p})\leq\sum_{j=1}^{k}\frac{1}{j\cdot p_{j}};\qquad\mathcal{ C}(\mathbf{p})\leq\sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\]2 Step 3: \[\mathcal{C}(\mathbf{p})\leq\frac{H_{k}}{p_{1}}=O(\frac{\log k}{p_{1}});\qquad \mathcal{C}(\mathbf{p})\leq\sum_{j=1}^{k}\frac{1}{j\cdot p_{j}};\qquad\mathcal{ C}(\mathbf{p})\leq\sum_{j=1}^{k}1/\left(\sum_{\ell=1}^{j}\frac{1}{p_{\ell}}\right)\]3  
The overall high-low cost is thus due to the last two steps only, and it is as in (7). Finally, each of the three steps succeeds with a probability of at least \(1-\frac{1}{n}\), conditioned to the previous step being successful. By the union bound, the overall success probability is at most \(1-\frac{3}{n}\).