Relating PAC learning results and abstaining classifiers Quite a few results are available on learning miscellaneous concept classes in the PAC learning framework. I would like to know whether any of these results have been extended in the abstaining classifier setting, where the classifier is allowed to refrain from classifying certain examples under various restrictions. In particular, does abstaining improve accuracy in any way, and if so, can this improvement be quantified?
There is work on this, and abstaining can sometimes help. You might be looking for this paper: Trading Off Mistakes with Don't Know Predictions by Sayedi et al. from the last NIPS.