Optimal estimation of misclassification rate for two-class clustering with sub-Gaussian noises

The misclassification rate can be used to measure the clustering accuracy. Cai and Zhang (2018) establish an upper bound of misclassification rate for the two-class clustering model \(\begin{aligned} Y_{i}=\mu l_{i}+Z_{i}\in {\mathbb {R}}^{p}, \end{aligned}\) $$\begin{array}{c}\hfill Y_i=\mu l_i+Z_i\in {\mathbb{R}}^p,\end{array}$$ where  \(l_{i}\in \{-1,1\}\) $l_i\in \{-1,1\}$ and \(Z_{i}\overset{i.i.d}{\sim }N(0,I_{p}),~i\in \{1,\ldots ,n\},\) $Z_i\stackrel{i.i.d}{\sim }N(0,I_p),i\in \{1,\dots ,n\},$  when the vector dimension p is larger than sample size n. The authors prove that their key assumption \(\Vert \mu \Vert _{2}\ge C_{gap}(p/n)^{1/4}\) ${\Vert \mu \Vert }_2\ge C_{\mathit{gap}}{(p/n)}^{1/4}$ is necessary for any estimator to be consistent. This paper discusses the same problem with sub-Gaussian noises and \(n\ge p:\) $n\ge p:$ We first use Cai and Zhang’s method to give an upper bound of the misclassification rate for \(\Vert \mu \Vert _{2}\ge C_{gap}.\) ${\Vert \mu \Vert }_2\ge C_{\mathit{gap}}.$ Then a lower bound of the misclassification rate is provided under some technical conditions, which matches the upper bound up to a constant multiple. This shows our upper bound estimation optimal. Examples are given to explain those technical conditions easily satisfied. Similar to Cai and Zhang’s work, we also prove the assumption \(\Vert \mu \Vert _{2}\ge C_{gap}\) ${\Vert \mu \Vert }_2\ge C_{\mathit{gap}}$ in our upper bound estimation necessary for any estimator to be consistent as well. Finally, numerical simulations support our theoretical analysis.