On the equivalence of Occam algorithms

Zaman Keinath-Esmail
8/11/2023
cs.LGcs.DScs.IT

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

A Parameterized Theory of PAC Learning

81% match2023

On Collusion-Free Teaching in Planar Graphs

81% match2026

Computable learning of natural hypothesis classes

80% match2024

Uniform Computability of PAC Learning

79% match2026

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

79% match2025

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem

79% match2024

Cite this paper

@article{keinathesmail2023equivalence,
  title  = {On the equivalence of Occam algorithms},
  author = {Zaman Keinath-Esmail},
  year   = {2023},
  eprint = {2308.05906},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2308.05906v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2308.05906.svg)](https://codeofpaper.com/paper/2308.05906)

Discussion