Are all VC-classes CPAC learnable?
Posed by Sushant Agarwal et al. (2021)
§ Problem Statement
Setup
Let and let a (binary) classifier be a function . Call computable if there exists a Turing machine that halts on every input and outputs (i.e., is total computable). A concept class is a set of computable classifiers; assume is given effectively (e.g., by a computable enumeration of indices of total computable classifiers whose realized functions are exactly the elements of ).
For a distribution over and classifier , define the risk . In the realizable setting, assume there exists a target concept such that almost surely under .
Define the VC dimension in the standard way: it is the largest for which some are shattered by (or if unbounded).
A CPAC (computable-PAC) learner for is a single computable algorithm that, given rational and an i.i.d. labeled sample drawn from an unknown realizable distribution , outputs a finite description (e.g., an index) of a total computable classifier such that there exists a sample bound for which
where the probability is over the draw of . The learner is proper if it always outputs , and improper otherwise (but still outputs a total computable classifier).
Unsolved Problem
Problem 2021. If , must be CPAC learnable by some (possibly improper) CPAC learner? Equivalently, does there exist an effectively given concept class of total computable classifiers with finite VC dimension that is not PAC learnable by any computable learning algorithm that always outputs a total computable predictor, even allowing improper hypotheses?
§ Discussion
§ Significance & Implications
In classical distribution-free PAC learning (with unrestricted, potentially non-computable learners), finite VC dimension exactly characterizes learnability. Independence results in this unrestricted setting show that even basic questions about learnability can fall outside ZFC, highlighting that the usual definition (learners as arbitrary functions) is too permissive for a purely combinatorial characterization. CPAC restricts both the learner and the produced predictor to be computable, aiming to recover a theory where learnability is a property of algorithms rather than set-theoretic objects. Determining whether finite VC dimension still guarantees learnability under these computability constraints for improper learners would pinpoint whether VC theory remains complete once outputs must be computable, or whether additional (computability-sensitive) structure is inherently required.
§ Known Partial Results
Agarwal et al. (2021): There exist statistical learning problems whose learnability cannot be decided within ZFC when learners are allowed to be arbitrary functions (as cited in the COLT 2021 open-problem note).
Agarwal et al. (2021): introduced CPAC-style frameworks that add basic computability requirements to PAC learning by requiring the learner to be an algorithm and the output predictor to be computable.
Agarwal et al. (2021): In this computability-constrained setting, finite VC dimension does not guarantee CPAC learnability for proper learning: there are finite-VC binary classes for which no computable proper PAC learner exists (as reported in the COLT 2021 open-problem note).
Agarwal et al. (2021): The main unresolved point is whether this failure of VC-based characterization persists for improper learning, i.e., whether some finite-VC computable class is not learnable by any computable PAC learner even when hypotheses may lie outside as long as the output predictor is computable.
Agarwal et al. (2021): The open-problem note further motivates seeking new combinatorial characterizations of learnability that are appropriate for computable learners.
§ References
Open Problem: Are all VC-classes CPAC learnable?
Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner (2021)
Conference on Learning Theory (COLT), PMLR 134
📍 Open-problem note in COLT proceedings.
Open Problem: Are all VC-classes CPAC learnable? (PDF)
Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner (2021)
Conference on Learning Theory (COLT), PMLR 134
📍 Proceedings PDF.