Statistical Learning of Arbitrary Computable Classifiers

TLDR

This work shows that learning over the set of all computable labeling functions is indeed possible, and develops a learning algorithm, and shows that bounding sample complexity independently of the distribution is impossible.

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.