On the equivalence of Occam algorithms
This work resolves a technical gap in computational learning theory, supporting foundational proofs and methods in PAC learning.
The paper addresses the limitation in Board and Pitt's partial converse theorem for Occam algorithms by extending it to include δ-independent complexities, thereby justifying prior theoretical results and algorithm designs.
Blumer et al. (1987, 1989) showed that any concept class that is learnable by Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial converse of this theorem: for concept classes that are closed under exception lists, any class that is PAC learnable is learnable by an Occam algorithm. However, their Occam algorithm outputs a hypothesis whose complexity is $δ$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $δ$-independent complexities as well. Thus, we provide a posteriori justification of various theoretical results and algorithm design methods which use the partial converse as a basis for their work.