# On the equivalence of Occam algorithms

arXiv: https://arxiv.org/abs/2308.05906 · HTML: https://mlsanity.com/paper/2308.05906/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 14 references that are in the map.
- First posted on arXiv 11 Aug 2023.

## Abstract (arXiv)

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.