A Universal Learning Algorithm
Webpage for a paper by Oded Goldreich and Dana Ron
Abstract
We observe that there exists a universal learning algorithm
which PAC-learns every concept class within complexity which
is linearly related to the complexity of the best learning
algorithm for this class.
This observation is derived by a straightforward application,
to the learning context,
of Levin's proof of the existence of optimal algorithms for NP.
Material available on-line
COMMENT (October 2008):
The version published in IPL (Vol. 63, pages 131-136, 1997)
states a stronger version of Theorem 4. This stronger version,
which is wrong, claims simultaneous optimality with respect to
the time complexity and the sample complexity.
As shown by David Soloveichik
(in Statistical Learning of
Arbitrary Computable Classifiers)
such a result cannot possibly hold.
Indeed, the proof provided in the IPL version
(like the one provided in the original version posted here)
only refers to optimality with respect to time complexity,
and it seems that the stronger statement was added at a later stage
and without careful examination of the details.
We are grateful to David for bringing this error to our attention.
Back to
either Oded Goldreich's homepage.
or general list of papers.