Theoretical upper bounds of classification accuracy? I'm looking for theoretical upper bounds of classification accuracy. Please let me know if you are familiar with results like the following. The setup below is a general one, but please share results you know that apply in particular settings as well. Thanks!
Let $Y$ be the binary variable to classify and $X = (X_1,...,X_K)$ be $K$ explanatory variables. We know the joint distribution (in population) of $(y,X) \sim \mu$ and want to build a model of $\hat{y} = f(X)$. Then for the class of XXX functions $f()$, there will be an upper bound to the maximum classification accuracy: $P(\hat{y} = y) \le g(\mu(y,X))$? 
 A: Apologize in advance for a less-than-definitive answer, but hopefully this answer will be helpful.
In the totally general case, (i.e. arbitrary Y,X) I would conjecture that no such bound exists, except for the trivial answer of perfect classification. 
The reason I make this conjecture is the similar issues addressed by the no free lunch theorem .
I think your question is more likely to be about a specific instance (i.e. with a specific, known data set)
In this case, I can suggest an approach... although this approach may or may not be useful in practice.
I am assuming that the values of X are all finite and discrete, or can be made so without loss of discrimination power.
Consider the set of all your observations, partitioned into a grid consisting of X(k,l) where l is the levels of each variable Xk.
Take the sum of the minority values of y (the binary value you are predicting) in each cell, and divide by n.
Since, in a given cell the best possible prediction is the ratio of majority/minority observations in that cell.  No better prediction is possible for that cell, because, by construction, the cell comprises of a unique combinations of X values.   No additional information is available from X to discriminate further.
