Theoretical limits on correlation between classification algorithm performances

Are there any known theoretical bounds, or at least heuristic approaches, regarding the relation or correlation between the performances of any two different classification algorithms?

For example, would there exist binary classification datasets for which, say, $$k$$-nearest-neighbour classifiers would perform with say >90% accuracy, whereas say decision tree classifiers would do no better than 50-60%? (Accuracy here is measured by say $$k$$-fold cross-validation.)

It seems to me, at first glance, that a dataset which is able to achieve a very high accuracy on some classification algorithm would necessarily have some structure that would make it highly improbable that some other general classification algorithm would be able to perform very poorly. Yet it's also not impossible that there might be some 'exotic' type of dataset that does exhibit such a phenomenon.

• Did you look at the regret bound?
– Alex
Feb 20 at 14:07