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

• URL: http://arxiv.org/abs/2608.30246v1
• Date: Mon, 31 Aug 2026 04:56:40 GMT
• Title: A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC
• Abstract summary: 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)<n>We show, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision.<n>A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations.<n>We introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $mathbbR_mathttexp$.<n>We prove that learnability is preserved, with sample complexity controlled by the complexity
  arXiv  Detail & Related papers  (2026-05-13T12:21:56Z)
• Null Measurability at the Symmetrization Interface in VC Learning [0.15229257192293197]
  Recent revisiting of measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema.<n>We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary.<n>Results weaken the measurability hypothesis needed by the symmetrization route from finite VC to PAC learnability.
  arXiv  Detail & Related papers  (2026-04-27T22:10:34Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  We study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$.<n>We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness.<n>We show that the generalized smoothness also characterizes private learnability under distributional constraints.
  arXiv  Detail & Related papers  (2026-02-24T06:15:59Z)
• Reconstruction of finite Quasi-Probability and Probability from Principles: The Role of Syntactic Locality [0.0]
  Quasi-probabilities appear across diverse areas of physics, but their conceptual foundations remain unclear.<n>We develop a principled framework that derives quasi-probabilities and their conditional calculus from structural consistency requirements.
  arXiv  Detail & Related papers  (2026-02-12T19:00:08Z)
• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning [0.0]
  We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions.<n>Recent works recovered analogs of the Fundamental Theorem in the computable setting.
  arXiv  Detail & Related papers  (2025-11-04T15:12:38Z)
• Measurability in the Fundamental Theorem of Statistical Learning [0.0]
  The Fundamental Theorem of Statistical Learning states that a hypothesis space is PAC learnable if and only if its VC dimension is finite.<n>This paper presents sufficient conditions for the PAC learnability of hypothesis spaces defined over o-minimal expansions of the reals.<n>This class of hypothesis spaces covers all artificial neural networks for binary classification that use commonly employed activation functions like ReLU and the sigmoid function.
  arXiv  Detail & Related papers  (2024-10-14T08:03:06Z)
• Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes [8.594140167290098]
  We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability. We show that VC dimension generalization upper bounds in previous work are frequently infinite, even for finite-dimensional POVM classes. We show that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable.
  arXiv  Detail & Related papers  (2023-08-21T18:38:24Z)
• Do PAC-Learners Learn the Marginal Distribution? [19.54058590042626]
  The Fundamental Theorem of PAC Learning asserts that learnability of a concept class $H$ is equivalent to the $textituniform convergence$ of empirical error in $H$.<n>This work revisits the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting.
  arXiv  Detail & Related papers  (2023-02-13T11:42:58Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  We construct a Bayes consistent learning rule that satisfies differential privacy (DP) We prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal sample complexity.
  arXiv  Detail & Related papers  (2022-12-08T11:57:30Z)
• Unifying different notions of quantum incompatibility into a strict hierarchy of resource theories of communication [60.18814584837969]
  We introduce the notion of q-compatibility, which unifies different notions of POVMs, channels, and instruments incompatibility. We are able to pinpoint exactly what each notion of incompatibility consists of, in terms of information-theoretic resources.
  arXiv  Detail & Related papers  (2022-11-16T21:33:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.