Optimal mistake bound learning is hard
type: Item
instance of: scholarly article
title: Optimal mistake bound learning is hard
zbMATH Open document ID: 0937.68099
author: Moti Frances
author: Ami Litman
published in: Information and Computation
publication date: 2000-05-23T00:00:00Z
review text: The authors have suggested and established the fact that a combinatorial function \(K\) can be constructed in polynomial time for a given optimal MB learning algorithm as subroutine. It is also same as the reverse reduction theorem of Little Stone. Subsequently, the authors have established that the \(k\)-dimension problem and optimal MB learning have the same time complexity.
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 1220704
zbMATH Keywords: MB learning
reviewed by: Laxminarayan Das
MaRDI profile type: Publication
full work available at URL: inco.1998.2709
OpenAlex ID: W1990881200
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Constructing optimal binary decision trees is NP-complete
cites work: A theory of the learnable
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
DOI: 10.1006/INCO.1998.2709
description: scientific article; zbMATH DE number 1220704