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.
The paper Efficiently Learning Typical Finite Automata from Random Walks [Freund et al. '97] considered default mistakes, where a learner defaults (or chooses not to answer), instead of predicting.
From what I remember, they showed that 1) You can learn (w.h.p.) by making only default mistakes, and 2) If the random walk is reset (to the start state of the DFA) on a default mistake, this helps in learning.