Optimal mistake bound learning is hard

DOI10.1006/INCO.1998.2709zbMath0937.68099OpenAlexW1990881200MaRDI QIDQ1271479

Ami Litman, Moti Frances

Publication date: 23 May 2000

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2709

zbMATH Keywords

MB learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (2)

From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ A note on hardness of computing recursive teaching dimension

Cites Work

• Constructing optimal binary decision trees is NP-complete
• Learnability and the Vapnik-Chervonenkis dimension
• A theory of the learnable
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Optimal mistake bound learning is hard