Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on this quantity that are independent of $\hat{f}$, e.g. Fano.
But now suppose we fix a particular classifier $\hat{f}$. To make this concrete, let's take $\hat{f}$ to be a $k$-nearest neighbor classifier (knn), but my question applies to general $\hat{f}$. There is a well-developed theory of upper bounds for the knn misclassification rate, however, I am not aware of any knn-specific lower bounds on the misclassification rate. That is, a lower bound $P(\hat{f}(X)\ne Y)$ that is specific to the knn choice for $\hat{f}$, instead of uniform over all measurable $\hat{f}$ (i.e. $\inf_\hat{f}P(\hat{f}(X)\ne Y)$). (Why would one care about this? For example, to show that a particular classifier is provably suboptimal compared to other classifiers.)
The context for this question is the following: For real-valued quantities (either responses in a prediction problem or parameters in statistical estimation), there is a well-developed theory of estimator-specific lower bounds based on the bias-variance tradeoff of the MSE. Many such lower bounds are known for specific estimators such as least-squares estimators. But I am not aware of any analogous results for classification problems (more generally, discrete estimands).
Any references that provide classifier-specific (not necessarily knn) lower bounds are welcome!
