Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 22, 2008 | Submitted
Report Open

Statistical Learning of Arbitrary Computable Classifiers

Abstract

Statistical learning theory chiefly studies restricted hypothesis classes, particularly those with finite Vapnik-Chervonenkis (VC) dimension. The fundamental quantity of interest is the sample complexity: the number of samples required to learn to a specified level of accuracy. Here we consider learning over the set of all computable labeling functions. Since the VC-dimension is infinite and a priori (uniform) bounds on the number of samples are impossible, we let the learning algorithm decide when it has seen sufficient samples to have learned. We first show that learning in this setting is indeed possible, and develop a learning algorithm. We then show, however, that bounding sample complexity independently of the distribution is impossible. Notably, this impossibility is entirely due to the requirement that the learning algorithm be computable, and not due to the statistical nature of the problem.

Additional Information

I thank Erik Winfree and Matthew Cook for discussions and invaluable support.

Attached Files

Submitted - soloveichik_learning_TMs2008_1_.pdf

Files

soloveichik_learning_TMs2008_1_.pdf
Files (80.7 kB)
Name Size Download all
md5:eabbf490bb25602fdb59add7ff642301
80.7 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023