Unsolved

Are all VC-classes CPAC learnable?

Posed by Sushant Agarwal et al. (2021)

§ Problem Statement

Setup

Let X={0,1}\mathcal{X}=\{0,1\}^* and let a (binary) classifier be a function h:X{0,1}h:\mathcal{X}\to\{0,1\}. Call hh computable if there exists a Turing machine that halts on every input xXx\in\mathcal{X} and outputs h(x)h(x) (i.e., hh is total computable). A concept class C\mathcal{C} is a set of computable classifiers; assume C\mathcal{C} is given effectively (e.g., by a computable enumeration of indices of total computable classifiers whose realized functions are exactly the elements of C\mathcal{C}).

For a distribution D\mathcal{D} over X×{0,1}\mathcal{X}\times\{0,1\} and classifier hh, define the risk errD(h)=Pr(X,Y)D[h(X)Y]\mathrm{err}_{\mathcal{D}}(h)=\Pr_{(X,Y)\sim\mathcal{D}}[h(X)\neq Y]. In the realizable setting, assume there exists a target concept cCc\in\mathcal{C} such that Y=c(X)Y=c(X) almost surely under D\mathcal{D}.

Define the VC dimension VC(C)\mathrm{VC}(\mathcal{C}) in the standard way: it is the largest dd for which some x1,,xdXx_1,\dots,x_d\in\mathcal{X} are shattered by C\mathcal{C} (or \infty if unbounded).

A CPAC (computable-PAC) learner for C\mathcal{C} is a single computable algorithm AA that, given rational ϵ,δ(0,1)\epsilon,\delta\in(0,1) and an i.i.d. labeled sample S=((x1,y1),,(xm,ym))S=((x_1,y_1),\dots,(x_m,y_m)) drawn from an unknown realizable distribution D\mathcal{D}, outputs a finite description (e.g., an index) of a total computable classifier hSh_S such that there exists a sample bound m=m(ϵ,δ)m=m(\epsilon,\delta) for which

Pr[errD(hS)ϵ]1δ,\Pr\big[\mathrm{err}_{\mathcal{D}}(h_S)\le \epsilon\big]\ge 1-\delta,

where the probability is over the draw of SS. The learner is proper if it always outputs hSCh_S\in\mathcal{C}, and improper otherwise (but still outputs a total computable classifier).

Unsolved Problem

Problem 2021. If VC(C)<\mathrm{VC}(\mathcal{C})<\infty, must C\mathcal{C} be CPAC learnable by some (possibly improper) CPAC learner? Equivalently, does there exist an effectively given concept class C\mathcal{C} 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

Loading 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 C\mathcal{C} 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

[1]

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.

[2]

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.

§ Tags