A Universal Learning Algorithm

Webpage for a paper by Oded Goldreich and Dana Ron


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.