Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

David Kattermann; Lothar Sebastian Krapp

cs.LGNov 4, 2025

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

Authors: David Kattermann, Lothar Sebastian Krapp

Organizations: Institute for Symbolic Artificial Intelligence, Johannes Kepler University Linz, Austria. · Department of Mathematics and Statistics, University of Konstanz, Germany. · Institute for the Interdisciplinary Study of Language Evolution, University of Zurich, Switzerland.

Abstract

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.

Explore similar work

Aug 31, 2026math.LO

A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC). Blumer, Ehrenfeucht, Haussler, and Warmuth showed, assuming the Continuum Hypothesis, that the "well-behavedness" condition of the concept class cannot be omitted: they constructed a concept class of Borel sets of VC dimension one admitting a consistent learning rule that is not PAC. We show that the Continuum Hypothesis is unnecessary. Working in Zermelo--Fraenkel set theory with the Axiom of Choice (ZFC) alone, we construct a concept class of Borel sets on

[0,1]

of VC dimension one and a proper consistent learning rule that is not PAC. More precisely, for a suitable Borel probability measure and target concept, the rule has true risk one at every sample size on a set of samples of outer probability one. Consequently, finite VC dimension and Borel measurability of the individual concepts do not suffice to guarantee that every proper consistent learning rule is PAC. The result shows, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.

Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira Rodrigues

Probability Measures

Ask PDF

Aug 6, 2026cs.LG

An Optimal Agnostic PAC Algorithm

Let

H\subseteq\{-1,+1\}^X

be a class of finite VC dimension

d\ge1

. Writing

L

for the binary risk and

L^*=\min_{h\in H}L(h)

, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size

n

, for every

0<δ\le 1/2

, with probability at least

1-δ

L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right).

This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed

L^*

, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Optimal Sample Complexity Sample Complexity

Ask PDF

Sep 21, 2026stat.ML

Adversarially Robust PAC Learning with Optimal VC Rates

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over

\mathcal{X} \times \{0,1\}

, as in classical PAC learning. However, given a perturbation map

\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}

known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation

z \in \mathcal{U}(x)

of most future examples

(x,y)

drawn from the same underlying distribution. We determine the \emph{optimal}

\mathcal{U}

-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class

\mathcal{H}

\operatorname{VC}

dimension

d

, we prove upper bounds of

\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)

in the realizable setting and

\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)

in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

Steve Hanneke, Amirreza Shaeiri

Optimal Sample Complexity Distributional Learning

Ask PDF