PAC Learning, VC Dimension, and the Arithmetic Hierarchy
This work provides a foundational theoretical insight into the computational limits of PAC learning, which is incremental but clarifies the relationship between learnability and complexity for researchers in computational learning theory.
The paper tackles the problem of characterizing the computational complexity of PAC-learnable concept classes, showing that their index set is m-complete Σ^0_3 within a reasonable family of concept classes, and establishes that PAC learnability is equivalent to finite VC dimension in this context.
We compute that the index set of PAC-learnable concept classes is $m$-complete $Σ^0_3$ within the set of indices for all concept classes of a reasonable form. All concept classes considered are computable enumerations of computable $Π^0_1$ classes, in a sense made precise here. This family of concept classes is sufficient to cover all standard examples, and also has the property that PAC learnability is equivalent to finite VC dimension.